Skip to yearly menu bar Skip to main content


Directional Optimism for Safe Linear Bandits

Spencer Hutchinson · Berkay Turan · Mahnoosh Alizadeh

MR1 & MR2 - Number 84
[ ]
Fri 3 May 8 a.m. PDT — 8:30 a.m. PDT


The safe linear bandit problem is a version of the classical stochastic linear bandit problem where the learner's actions must satisfy an uncertain constraint at all rounds. Due its applicability to many real-world settings, this problem has received considerable attention in recent years. By leveraging a novel approach that we call directional optimism, we find that it is possible to achieve improved regret guarantees for both well-separated problem instances and action sets that are finite star convex sets. Furthermore, we propose a novel algorithm for this setting that improves on existing algorithms in terms of empirical performance, while enjoying matching regret guarantees. Lastly, we introduce a generalization of the safe linear bandit setting where the constraints are convex and adapt our algorithms and analyses to this setting by leveraging a novel convex-analysis based approach.

Live content is unavailable. Log in and register to view live content