Directional Optimism for Safe Linear Bandits

Spencer Hutchinson, Berkay Turan, Mahnoosh Alizadeh
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:658-666, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-hutchinson24a, title = {Directional Optimism for Safe Linear Bandits}, author = {Hutchinson, Spencer and Turan, Berkay and Alizadeh, Mahnoosh}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {658--666}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/hutchinson24a/hutchinson24a.pdf}, url = {https://proceedings.mlr.press/v238/hutchinson24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Directional Optimism for Safe Linear Bandits %A Spencer Hutchinson %A Berkay Turan %A Mahnoosh Alizadeh %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-hutchinson24a %I PMLR %P 658--666 %U https://proceedings.mlr.press/v238/hutchinson24a.html %V 238 %X 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.
APA
Hutchinson, S., Turan, B. & Alizadeh, M.. (2024). Directional Optimism for Safe Linear Bandits. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:658-666 Available from https://proceedings.mlr.press/v238/hutchinson24a.html.

Related Material