Follow-the-Perturbed-Leader

Follow this topic Ask about this topic

Latest papers

9 papers3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets
Oct 13, 2026Chen-Yu WeiFollow-the-Perturbed-Leader Adversarial Bandits
University of Virginia
Oracle-Efficient and Parameter-Free Agnostic Smoothed Online Learning
Oct 7, 2026Sasha Voitovych, Adam Block, Alexander Rakhlin +1Follow-the-Perturbed-Leader
MIT · Columbia University · Georgia Tech
Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs
Sep 27, 2026Gon Buzaglo, Elad HazanFollow-the-Perturbed-Leader Binary Classification
Department of Computer Science, Princeton University · Google DeepMind
Toward Simultaneously Optimal Regret in U-Calibration
Jun 16, 2026Rafael Frongillo, Haipeng Luo, Nishant A. Mehta +1Follow-the-Perturbed-Leader Probabilistic Forecasting
University of Colorado Boulder · University of Southern California and Google Research · University of Victoria +1
Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader
Jun 4, 2026Jongyeong Lee, Junya Honda, Shinji Ito +1Multi-Armed Bandits Follow-the-Perturbed-Leader
Korea Institute of Science and Technology · Kyoto University · RIKEN AIP +2
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
Jun 1, 2026Moses Charikar, Chirag Pabbaraju, Ambuj TewariOnline Convex Optimization Follow-the-Perturbed-Leader
Stanford University. · University of Michigan, Ann Arbor.
Online combinatorial optimization with stochastic decision sets and adversarial losses
Apr 28, 2026Gergely Neu, Michal ValkoMulti-Armed Bandits Follow-the-Perturbed-Leader
SequeL team, INRIA Lille – Nord Europe, France
A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$ -Set Semi-Bandit Problem
Mar 12, 2026Botao Chen, Jongyeong Lee, Chansoo Kim +1Follow-the-Perturbed-Leader Combinatorial Semi-Bandits
Department of Systems Science Graduate School of Informatics, Kyoto University Kyoto, Japan · Computational Science Research Center Korea Institute of Science and Technology Seoul, Korea · Computational Science Research Center Korea Institute of Science and Technology & University of Science and Technology Seoul, Korea +1
Self-Concordant Perturbations for Linear Bandits
Oct 28, 2025Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1Multi-Armed Bandits Follow-the-Perturbed-Leader
Ecole Polytechnique and University of Oxford · ENSAE Paris and University of Oxford · University of Oxford and Ecole Polytechnique +1

Oct 13, 2026J/K move · Enter open · S save

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets

Chen-Yu Wei

University of Virginia

Follow-the-Perturbed-Leader Adversarial Bandits Bandit Convex Optimization Exploration-Exploitation Tradeoff

Open paper AskPDF arXiv

We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves

\sqrt{T}

regret over general action sets. Our algorithm attains

\widetilde{\mathcal{O}}(d^{5/4}\sqrt{T})

regret using only linear optimization oracles, and the near-optimal

\widetilde{\mathcal{O}}(d\sqrt{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

\sqrt{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.