Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for Martingale Mixtures

Abstract

We present improved algorithms with worst-case regret guarantees for the stochastic 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 demonstrate that our tighter confidence sequences give improved performance in several hyperparameter tuning tasks.

Accepted at NeurIPS 2023. 35 pages, 6 figures

References in corpus (6)

• Streaming kernel regression with provably adaptive mean, variance, and regularization
• PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales
• A unified recipe for deriving (time-uniform) PAC-Bayes bounds
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance
• Uncertainty quantification using martingales for misspecified Gaussian processes
• Gaussian Process Bandit Optimization with Few Batches