Publikation
Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures
Hamish Flynn; David Reeb; Melih Kandemir; Jan Peters
In: Alice Oh; Tristan Naumann; Amir Globerson; Kate Saenko; Moritz Hardt; Sergey Levine (Hrsg.). Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023. Neural Information Processing Systems (NeurIPS), Pages 1-35, ArXiv, 2023.
Zusammenfassung
We present improved algorithms with worst-case regret guarantees for the stochas-
tic linear bandit problem. The widely used “optimism in the face of uncertainty”
principle reduces a stochastic bandit problem to the construction of a confidence
sequence for the unknown reward function. The performance of the resulting bandit
algorithm depends on the size of the confidence sequence, with smaller confidence
sets yielding better empirical performance and stronger regret guarantees. In this
work, we use a novel tail bound for adaptive martingale mixtures to construct
confidence sequences which are suitable for stochastic bandits. These confidence
sequences allow for efficient action selection via convex programming. We prove
that a linear bandit algorithm based on our confidence sequences is guaranteed to
achieve competitive worst-case regret. We show that our confidence sequences are
tighter than competitors, both empirically and theoretically. Finally, we demon-
strate that our tighter confidence sequences give improved performance in several
hyperparameter tuning tasks.