mlsanityData to 14 Oct 2026

Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Sets

arXiv 2610.17818 ↗First posted 13 Oct 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves √T regret over general convex action sets. Our algorithm attains widetildeO(d5/4√T) regret using only linear optimization oracles, and the near-optimal widetildeO(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 convex sets, and generalizes the √T regret of L'evy 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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 41 of its 62 references that are in the map. First posted on arXiv 13 Oct 2026.

Builds on

41 of 62 references.

References · 41

  1. 2021Convex optimizationcited by 2,515
  2. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 52
  3. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  4. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 52
  5. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  6. 2015Fighting Bandits with a New Kind of Smoothnesscited by 47
  7. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 43
  8. 2018Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Banditscited by 34
  9. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 33
  10. 2016Oracle-Efficient Online Learning and Auction Designcited by 33
  11. 2019Online Non-Convex Learning: Following the Perturbed Leader is Optimalcited by 32
  12. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 30
29 more
  1. 2019Perturbed-History Exploration in Stochastic Linear Banditscited by 29
  2. 2015First-order regret bounds for combinatorial semi-banditscited by 26
  3. 2013Volumetric Spanners: an Efficient Exploration Basis for Learningcited by 24
  4. 2014Online Linear Optimization via Smoothingcited by 24
  5. 2019Improved Path-length Regret Bounds for Banditscited by 23
  6. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 21
  7. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 19
  8. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  9. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 17
  10. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  11. 2015Importance weighting without importance weights: An efficient algorithm for combinatorial semi-banditscited by 16
  12. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 15
  13. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
  14. 2026Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimizationcited by 14
  15. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 13
  16. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 12
  17. 2019On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problemscited by 11
  18. 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 10
  19. 2017Online Learning via the Differential Privacy Lenscited by 9
  20. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 7
  21. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 4
  22. 2026Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputscited by 3
  23. 2018Regularized Finite Dimensional Kernel Sobolev Discrepancycited by 2
  24. 2026A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for m-Set Semi-Bandit Problemcited by 2
  25. 2026Online combinatorial optimization with stochastic decision sets and adversarial lossescited by 2
  26. 2025Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problemscited by 1
  27. 2025Self-Concordant Perturbations for Linear Banditscited by 1
  28. 2026Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leadercited by 1
  29. 2026Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learningcited by 1

Built on by

Not cited yet.