Follow the Perturbed Leader for Linear Bandits: √T Regret over General Action Sets
Abstract
We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves √T regret over general action sets. Our algorithm attains 𝒪̃(d5/4√T) regret using only linear optimization oracles, and the near-optimal 𝒪̃(d√T) regret when an optimal-design exploration distribution is further available. This improves on the T2/3 regret of the FTPL algorithm of Dani and Hayes (2006) for general action sets, and generalizes the √T regret of Lévy et al. (2026) over two special action sets (hypercube and Euclidean ball). Compared to previous oracle-efficient linear bandit algorithms based on continuous exponential weights, the FTPL approach generally has better computational efficiency, and is much simpler to implement. The key algorithmic element is a perturbation distribution that adapts to the past reward estimators. Its simplest form, an adaptive Gaussian perturbation, is straightforward to implement and already attains the regret bound above. We further extend it to two general constructions, random-weighting and elliptical perturbations, each covering distributions from light tails (Gaussian) to heavy tails (Student-t2). On the technical side, we develop a systematic way to analyze the stability term in the FTPL regret through the Fisher information of the perturbation distribution. This builds a general framework for FTPL beyond existing ones such as the hazard rate and the FTRL-FTPL duality.
Related
- Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
- General Leader-Follower Linear-Quadratic Stochastic Graphon Games with Indefinite Control Weights
- The Follow-the-Leader scheme with non-monotone velocity
- Follow the Regularized Leader Does Not Converge in Constrained Optimization
- Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
BibTeX
@misc{wei2026follow,
title = {{Follow the Perturbed Leader for Linear Bandits: $\sqrtT$ Regret over General Action Sets}},
author = {Chen-Yu Wei},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17818},
eprint = {2610.17818},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17818},
}
RIS
TY - UNPB
TI - Follow the Perturbed Leader for Linear Bandits: √T Regret over General Action Sets
AU - Chen-Yu Wei
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.17818
UR - https://arxiv.org/abs/2610.17818
AB - We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves √T regret over general action sets. Our algorithm attains 𝒪̃(d^5/4√T) regret using only linear optimization oracles, and the near-optimal 𝒪̃(d√T) regret when an optimal-design exploration distribution is further available. This improves on the T^2/3 regret of the FTPL algorithm of Dani and Hayes (2006) for general action sets, and generalizes the √T regret of Lévy et al. (2026) over two special action sets (hypercube and Euclidean ball). Compared to previous oracle-efficient linear bandit algorithms based on continuous exponential weights, the FTPL approach generally has better computational efficiency, and is much simpler to implement. The key algorithmic element is a perturbation distribution that adapts to the past reward estimators. Its simplest form, an adaptive Gaussian perturbation, is straightforward to implement and already attains the regret bound above. We further extend it to two general constructions, random-weighting and elliptical perturbations, each covering distributions from light tails (Gaussian) to heavy tails (Student-t_2). On the technical side, we develop a systematic way to analyze the stability term in the FTPL regret through the Fisher information of the perturbation distribution. This builds a general framework for FTPL beyond existing ones such as the hazard rate and the FTRL-FTPL duality.
ER -