A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$-Set Semi-Bandit Problem

Botao Chen; Jongyeong Lee; Chansoo Kim; Junya Honda

cs.LGMar 12, 2026

A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$ -Set Semi-Bandit Problem

Authors: Botao Chen, Jongyeong Lee, Chansoo Kim, Junya Honda

Organizations: 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 · Center for Advanced Intelligence Project, RIKEN Tokyo, Japan

Abstract

This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in $m$ -set semi-bandit problems. FTPL has been studied extensively as a promising candidate of an efficient algorithm with favorable regret for adversarial combinatorial semi-bandits. Nevertheless, the optimality of FTPL has still been unknown unlike Follow-the-Regularized-Leader (FTRL) whose optimality has been proved for various tasks of online learning. In this paper, we extend the analysis of FTPL with geometric resampling (GR) to $m$ -set semi-bandits, which is a special case of combinatorial semi-bandits, showing that FTPL with Fréchet and Pareto distributions with certain parameters achieves the best possible regret of $O(\sqrt{mdT})$ in adversarial setting. We also show that FTPL with Fréchet and Pareto distributions with a certain parameter achieves a logarithmic regret for stochastic setting, meaning the Best-of-Both-Worlds optimality of FTPL for $m$ -set semi-bandit problems. Furthermore, we extend the conditional geometric resampling to $m$ -set semi-bandits for efficient loss estimation in FTPL, reducing the computational complexity from $O(d^2)$ of the original geometric resampling to $O(md(\log(d/m)+1))$ without sacrificing the regret performance.

Figures & tables

Symbol	Meaning
$\mathcal{A}\subset\{0,1\}^{d}$	Action set
$d\in\mathbb{N}$	Dimensionality of action set
$m\in[d]$	$m=\\|a\\|_{1}$ for any $a\in\mathcal{A}$ , i.e., the size of each action
$\eta_{t}\in\mathbb{R}^{+}$	Learning rate
$\ell_{t}\in[0,1]^{d}$	Loss vector
$\hat{\ell}_{t}\in[0,\infty)^{d}$	Estimated loss vector

Table 1: Notation.

Explore similar work

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets
Oct 13, 2026Chen-Yu WeiAdversarial Bandits Bandit Convex Optimization
University of Virginia
An Efficient Minimax-Optimal Algorithm for Adversarial $m$ -Set Bandits
Aug 12, 2026Francesco Bacchiocchi, Tommaso Cesari, Roberto ColomboniCombinatorial Multi-Armed Bandits Adversarial Bandits
DEIB, Politecnico di Milano, Milano, Italy · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom
m-Set Adversarial Bandits with Winner Feedback
Oct 7, 2026Nicolò Cesa-Bianchi, Matteo PapiniMulti-Armed Bandits Adversarial Bandits
Universit`a degli Studi di Milano · Politecnico di Milano

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

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

Chen-Yu Wei

University of Virginia

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 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.

Abstract

Explore similar work

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

An Efficient Minimax-Optimal Algorithm for Adversarial mmm-Set Bandits

m-Set Adversarial Bandits with Winner Feedback

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

An Efficient Minimax-Optimal Algorithm for Adversarial $m$ -Set Bandits