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

Oct 28, 2025

Self-Concordant Perturbations for Linear Bandits

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.

Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1

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

Ask PDF

Mar 26, 2026

Parameter-Free Dynamic Regret for Unconstrained Linear Bandits

We study dynamic regret minimization in unconstrained adversarial linear bandit problems. In this setting, a learner must minimize the cumulative loss relative to an arbitrary sequence of comparators

\boldsymbol{u}_1,\ldots,\boldsymbol{u}_T

\mathbb{R}^d

, but receives only point-evaluation feedback on each round. We provide a simple approach to combining the guarantees of several bandit algorithms, allowing us to optimally adapt to the number of switches

S_T = \sum_t\mathbb{I}\{\boldsymbol{u}_t \neq \boldsymbol{u}_{t-1}\}

of an arbitrary comparator sequence. In particular, we provide the first algorithm for linear bandits achieving the optimal regret guarantee of order

\mathcal{O}\big(\sqrt{d(1+S_T) T}\big)

up to poly-logarithmic terms without prior knowledge of

S_T

, thus resolving a long-standing open problem.

Alberto Rumi, Andrew Jacobsen, Nicolò Cesa-Bianchi +1

Intesa Sanpaolo Innovation Center

Dynamic Regret Minimization Adversarial Bandits Multi-Armed Bandits

Ask PDF

Mar 30, 2026

A Perturbation Approach to Unconstrained Linear Bandits

We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO). We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem. Our framework improves on prior work in several ways. First, we derive expected-regret guarantees when our perturbation scheme is combined with comparator-adaptive OLO algorithms, leading to new insights about the impact of different adversarial models on the resulting comparator-adaptive rates. We also extend our analysis to dynamic regret, obtaining the first guarantees with optimal

\sqrt{P_T}

path-length dependencies without prior knowledge of

P_T

. We then develop the first high-probability guarantees for both static and dynamic regret in uBLO. Finally, we discuss lower bounds on the static regret, and prove the folklore

Ω(\sqrt{dT})

rate for adversarial linear bandits on the Euclidean ball, which is of independent interest.

Andrew Jacobsen, Dorian Baudry, Shinji Ito +1

Università degli Studi di Milano · Politecnico di Milano · Inria, Univ. Grenoble Alpes, Grenoble INP, CNRS, LIG, 38000 Grenoble, France +1

Adversarial Bandits Dynamic Regret Minimization Multi-Armed Bandits

Ask PDF