Interactively Learning Preference Constraints in Linear Bandits
METADATA ONLY
Author / Producer
Date
2022
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We study sequential decision-making with known rewards and unknown constraints, motivated by situations where the constraints represent expensive-to-evaluate human preferences, such as safe and comfortable driving behavior. We formalize the challenge of interactively learning about these constraints as a novel linear bandit problem which we call constrained linear best-arm identification. To solve this problem, we propose the Adaptive Constraint Learning (ACOL) algorithm. We provide an instance-dependent lower bound for constrained linear best-arm identification and show that ACOL’s sample complexity matches the lower bound in the worst-case. In the average case, ACOL’s sample complexity bound is still significantly tighter than bounds of simpler approaches. In synthetic experiments, ACOL performs on par with an oracle solution and outperforms a range of baselines. As an application, we consider learning constraints to represent human preferences in a driving simulation. ACOL is significantly more sample efficient than alternatives for this application. Further, we find that learning preferences as constraints is more robust to changes in the driving scenario than encoding the preferences directly in the reward function.
Permanent link
Publication status
published
Book title
Proceedings of the 39th International Conference on Machine Learning
Journal / series
Volume
162
Pages / Article No.
13505 - 13527
Publisher
PMLR
Event
39th International Conference on Machine Learning (ICML 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03908 - Krause, Andreas / Krause, Andreas
02150 - Dep. Informatik / Dep. of Computer Science
02661 - Institut für Maschinelles Lernen / Institute for Machine Learning
Notes
Funding
815943 - Reliable Data-Driven Decision Making in Cyber-Physical Systems (EC)