Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry

Canzhe Zhao; Vincent Y. F. Tan

cs.LGOct 31, 2026

Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry

Authors: Canzhe Zhao, Vincent Y. F. Tan

Organizations: Department of Mathematics, National University of Singapore · Department of Electrical and Computer Engineering, National University of Singapore

Abstract

We study best-of-both-worlds (BOBW) algorithms for linear bandits, which aim to simultaneously guarantee $\gO(\sqrt T)$ regret in the adversarial regime and $\gO(\log T)$ regret in the stochastic regime over $T$ rounds. For finite action sets, we introduce information-acquisition follow-the-regularized-leader (\IAFTRL{}), the first BOBW algorithm based purely on the follow-the-regularized-leader (FTRL) framework that attains an $\gO(\cstar\log T)$ -type regret in the stochastic regime, where $\cstar$ is the information-acquisition complexity that characterizes instance-dependent optimality in linear bandits, while retaining the $\gO(\sqrt{T})$ regret guarantee in the adversarial regime. This resolves the open problem posed in~\cite{LeeEtAl2021,KongZ023,ItoT23,ZhaoItoLi2025}.

Figures & tables

	Stochastic Regime	Adversarial Regime	Purely FTRL-based?	Infinite Action Set?
[ LLW+21 ] §	${\mathcal{O}}\!\left(\begin{gathered}c^{*}\log T\log(KT)\\[-2.0pt] {}+\frac{d\log^{3/2}(KT)}{\Delta_{\min}}\end{gathered}\right)$	${\mathcal{O}}\!\left(\begin{gathered}\sqrt{dT\log T\log(KT)}\\[-2.0pt] {}+d\log^{3/2}(KT)\end{gathered}\right)$	✗	✗
[ KZL23 ]	${\mathcal{O}}\!\left(\frac{d\log T\log(KT)}{\Delta_{\min}}\right)$	${\mathcal{O}}\!\left(\sqrt{dT\log T\log(KT)}\right)$	✓	✗
[ IT23a ]	${\mathcal{O}}\!\left(\frac{d^{3}\log T}{\Delta_{\min}}\right)$	${\mathcal{O}}\!\left(d^{3/2}\sqrt{T\log T}\right)$	✓	✗ †
[ DWZ23c , Thm. 3]	${\mathcal{O}}\!\left(\frac{d^{3}\log T}{\Delta_{\min}}\right)$	${\mathcal{O}}\!\left(d^{3/2}\sqrt{T\log T}\right)$	✓	✗ †
[ DWZ23c , Cor. 7]	${\mathcal{O}}\!\left(\frac{d^{2}\log T}{\Delta_{\min}}\right)$	${\mathcal{O}}\!\left(d\sqrt{T\log T}\right)$	✓	✗ †
[ DWZ23c , Cor. 12]	${\mathcal{O}}\!\left(\frac{d\log K\log T}{\Delta_{\min}}\right)$	${\mathcal{O}}\!\left(\sqrt{dT\log K}\right)$	✓	✗

Table 1: Comparisons with existing works for BOBW linear bandits. Additive remainders independent of

T

are omitted from upper bounds.

Adversarial Bandits

Adversarial bandits study how to choose actions and learn from partial feedback when rewards or losses can change strategically over time.

See all 56 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
Best-of-Both Worlds for linear contextual bandits with paid observations
Oct 8, 2025Nathan Boyer, Dorian Baudry, Patrick RebeschiniMulti-Armed Bandits Follow-the-Regularized-Leader
ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford
Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
Oct 28, 2026Qiwei Di, Quanquan GuAdversarial Bandits Follow-the-Regularized-Leader
Department of Computer Science, University of California, Los Angeles, CA 90095, USA

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.

Abstract

Adversarial Bandits

Explore similar work

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

Best-of-Both Worlds for linear contextual bandits with paid observations

Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

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