  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.
