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

Chen-Yu Wei

cs.LGOct 13, 2026

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

Authors: Chen-Yu Wei

Organizations: University of Virginia

Abstract

We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves $\sqrt{T}$ regret over general convex 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 convex 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 estimated rewards. 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.

Figures & tables

Method	Action set	Regret in $\widetilde{\mathcal{O}}$	Regret notion	Exploration basis
Awerbuch and Kleinberg (2004)	general	$d^{5/3}T^{2/3}$	pseudo regret	barycentric spanner
McMahan and Blum (2004) Dani and Hayes (2006)	general	$dT^{2/3}$	expected regret	barycentric spanner
Lévy et al. (2026)	hypercube or Euclidean ball	$d\sqrt{T}$	pseudo regret	–
This paper	general	$(d+Rd^{3/4})\sqrt{T}$	pseudo regret	barycentric spanner ( $R\leq 4\sqrt{d}$ ) optimal design ( $R=1$ )

Table 1: Comparison of FTPL algorithms for adversarial linear bandits.

R

is an outer radius of the action set after normalizing the covariance of the exploration basis; see Assumption 1 for its definition. Obtaining the optimal design exploration basis may be computationally hard for general action sets, but it can be efficiently constructed in special cases such as the hypercube, Euclidean ball,

m

-set, probability simplex, and the space of permutation matrices.

Panel of Figure 1 — Figure 1: The action set $\mathcal{A}$ in Theorem 3 . Its exposed edges $[v_{i},v_{i+1}]$ accumulate at $e_{1}$ , and their lengths converge to zero.

Figure 2: Two adaptive perturbation constructions for Algorithm 1 .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Table 4

Distribution	$P_{\Sigma}(z)\propto$	$\mathcal{I}^{v}(P_{\Sigma})\preceq\mathcal{O}(1)\Sigma^{-1}$ ?	$\mathcal{J}^{v}(P_{\Sigma})\preceq\mathcal{O}(1)\Sigma^{-1}$ ?	$\mathcal{J}^{v,\mathsf{L}}(P_{\Sigma})\preceq$	$\mathbb{E}[S^{2}\mathbf{1}_{\{S\leq\mathsf{L}\}}]\leq$	$\mathbb{E}[S\mathbf{1}_{\{S>\mathsf{L}\}}]\leq$
Gaussian	$e^{-\\|z\\|_{\Sigma^{-1}}^{2}/2}$	$\checkmark$	$\checkmark$	(not needed)
Radial Laplace	$e^{-\sqrt{d}\\|z\\|_{\Sigma^{-1}}}$	$\checkmark$	$\checkmark$	(not needed)
Student- $t_{2}$	$\big(1+\\|z\\|_{\Sigma^{-1}}^{2}\big)^{-(d+2)/2}$	$\checkmark$	–	$6\log(e\mathsf{L})\Sigma^{-1}$	$\frac{d}{2}\log(1+\mathsf{L}^{2})$	$\frac{d}{\sqrt{1+\mathsf{L}^{2}}}$

Appendix

Table 4: Elliptical perturbation bounds for

\kappa=\lVert v\rVert_{\Sigma^{-1}}\leq 1/8

and

\mathsf{L}\geq 1

. Here

S=\lVert Z\rVert_{\Sigma^{-1}}

for

Z\sim P_{\Sigma}

. The clipping columns give explicit upper bounds and are only needed for Student-

t_{2}

. The dash marks the only failed bound: the Student-

t_{2}

untruncated update information is infinite, even at zero shift. Proofs appear in Appendix H .

Method	Oracle calls to $\mathcal{A}$			Arithmetic outside oracles
Method	Linear optimization	Membership	Separation	Arithmetic outside oracles
Our elliptical FTPL	$d^{2}+d^{3/4}T^{3/2}$	$0$	$0$	$d^{4}+d^{11/4}T^{3/2}$
GeometricHedge with volumetric spanner ( Hazan and Karnin, 2016 ) + Liu et al. (2026) ’s sampling	$d^{2}$	$d^{2}T^{5/2}$	$0$	$d^{4}T^{5/2}$
Ito et al. (2019) + Liu et al. (2026) ’s sampling	$0$	$0$	$dT$	$d^{5}T^{3}+d^{4}T^{4}$

Appendix

Table 5: Comparison on the oracle complexity and the computational complexity beyond oracle calls for three linear bandit algorithms. The complexities of Hazan and Karnin (2016) and Ito et al. (2019) are improved from the original work through the use of the state-of-the-art log-concave sampling procedure ( Liu et al., 2026 ) . For example, the membership oracle complexity of Hazan and Karnin (2016) is of order

d^{3}T^{7}

in their work, but improved to

d^{2}T^{5/2}

in our table.

Explore similar work

Self-Concordant Perturbations for Linear Bandits
Oct 28, 2025Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1Multi-Armed Bandits Exploration-Exploitation Tradeoff
Ecole Polytechnique and University of Oxford · ENSAE Paris and University of Oxford · University of Oxford and Ecole Polytechnique +1
Parameter-Free Dynamic Regret for Unconstrained Linear Bandits
Mar 26, 2026Alberto Rumi, Andrew Jacobsen, Nicolò Cesa-Bianchi +1Dynamic Regret Minimization Adversarial Bandits
Intesa Sanpaolo Innovation Center
A Perturbation Approach to Unconstrained Linear Bandits
Mar 30, 2026Andrew Jacobsen, Dorian Baudry, Shinji Ito +1Adversarial Bandits Dynamic Regret Minimization
Università degli Studi di Milano · Politecnico di Milano · Inria, Univ. Grenoble Alpes, Grenoble INP, CNRS, LIG, 38000 Grenoble, France +1

Oct 28, 2025J/K move · Enter open · S save

Self-Concordant Perturbations for Linear Bandits

Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini

Ecole Polytechnique and University of Oxford · ENSAE Paris and University of Oxford · University of Oxford and Ecole Polytechnique+1

Multi-Armed Bandits Exploration-Exploitation Tradeoff Follow-the-Regularized-Leader Adversarial Bandits

Open paper AskPDF arXiv

We consider the adversarial linear bandits setting and present a unified algorithmic framework that bridges Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FTPL) methods, extending the known connection between them from the full-information setting. Within this framework, we introduce self-concordant perturbations, a family of probability distributions that mirror the role of self-concordant barriers previously employed in the FTRL-based SCRiBLe algorithm. Using this idea, we design a novel FTPL-based algorithm that combines self-concordant regularization with efficient stochastic exploration. Our approach achieves a regret of

\mathcal{O}(d\sqrt{n \ln n})

on both the

d

-dimensional hypercube and the

\ell_2

ball. On the

\ell_2

ball, this matches the rate attained by SCRiBLe. For the hypercube, this represents a

\sqrt{d}

improvement over these methods and matches the optimal bound up to logarithmic factors.

Abstract

Explore similar work

Self-Concordant Perturbations for Linear Bandits

Parameter-Free Dynamic Regret for Unconstrained Linear Bandits

A Perturbation Approach to Unconstrained Linear Bandits