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

arXiv: https://arxiv.org/abs/2309.14298 · HTML: https://mlsanity.com/paper/2309.14298/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 25 Sep 2023.

## Builds on (most cited first, 19 of 19)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales](https://mlsanity.com/paper/2210.00928/) (2022)
- [Online PAC-Bayes Learning](https://mlsanity.com/paper/2206.00024/) (2022)
- [Streaming kernel regression with provably adaptive mean, variance, and regularization](https://mlsanity.com/paper/1708.00768/) (2017)
- [Uncertainty quantification using martingales for misspecified Gaussian processes](https://mlsanity.com/paper/2006.07368/) (2020)
- [The E-Posterior](https://mlsanity.com/paper/2301.01335/) (2023)

## Built on by (most cited first, 12 of 12)

- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Confidence Sequences for Generalized Linear Models via Regret Analysis](https://mlsanity.com/paper/2504.16555/) (2025)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization](https://mlsanity.com/paper/2402.07341/) (2024)
- [Linear Causal Bandits: Unknown Graph and Soft Interventions](https://mlsanity.com/paper/2411.02383/) (2024)
- [Vector-valued self-normalized concentration inequalities beyond sub-Gaussianity](https://mlsanity.com/paper/2511.03606/) (2025)
- [A variational approach to dimension-free self-normalized concentration](https://mlsanity.com/paper/2508.06483/) (2025)
- [Impact of Connectivity on Laplacian Representations in Reinforcement Learning](https://mlsanity.com/paper/2603.08558/) (2026)
- [Bayesian Bandit Algorithms with Approximate Inference in Stochastic Linear Bandits](https://mlsanity.com/paper/2406.14071/) (2024)
- [Linear Bandits with Non-i.i.d. Noise](https://mlsanity.com/paper/2505.20017/) (2025)
- [Best-of-Both Worlds for linear contextual bandits with paid observations](https://mlsanity.com/paper/2510.07424/) (2025)

## Abstract (arXiv)

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.