Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary

Mengxiao Zhang

cs.LGSep 11, 2026

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary

Authors: Mengxiao Zhang

Organizations: University of Iowa

Abstract

We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at most $S$ times. When $S$ is known, an optimal expected regret of $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ is obtainable [Auer et al., 2002]. However, when $S$ is unknown, Marinov and Zimmert [2021] show that this guarantee is impossible under an adaptive adversary. In this paper, we show that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al. [2019b]. Our algorithm combines a fixed-share learner initialized with a small learning rate and dyadic-interval subroutines that search for local improvements using randomized learning rates and implicit exploration. Importantly, a non-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switches $S$ .

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

History	Information already determined	Remaining randomness used in the analysis
$\mathcal{H}_{t}^{\mathrm{end}}$	Actual play through round $t$ , including its restart decision	Future launch, routing, and action draws
${\mathcal{F}}_{j}$	History before epoch $j$ starts; $\tau_{j}$ and the reset state	All random variables assigned to epoch $j$
$\mathcal{H}_{t}$	Past play, current interval rates and states, and $q_{t}$	Routing bit $b_{t}$ , followed by the branch action
$\mathcal{G}_{t}$	$\mathcal{H}_{t}$ plus $b_{t}$ and $p_{t}$	Arm $i_{t}\sim p_{t}$
${\mathcal{F}}_{j}^{\mathrm{path}}$	Continuation routing bits and reference path; ${\mathcal{D}}_{j}(n)$ and $(A_{J}(n))_{J\in{\mathcal{D}}_{j}(n)}$ for fixed $n$	Interval-rate and challenge-branch action-sampling variables
${\mathcal{F}}_{j}^{\mathrm{rate}}$	${\mathcal{F}}_{j}^{\mathrm{path}}$ plus all continuation rates, fixed-endpoint selections, and $\Gamma_{j}$	Challenge-branch action-sampling variables

Appendix

Table 1: Actual histories and the enlarged histories used to analyze a fixed-rate continuation. The lower three rows describe the successive conditioning steps in the proof.

Figure 1: Maximal canonical dyadic intervals contained in

I=\{3,\ldots,13\}

, with

T=16

. The highlighted intervals form the disjoint partition

[3,4]\cup[5,8]\cup[9,12]\cup\{13\}

, where brackets denote integer intervals. Each highlighted interval’s parent crosses a dashed boundary of

I

, and at most two highlighted intervals occur at each length.

Explore similar work

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

Sep 29, 2026

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For

K

-armed bandits with

A

optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a

\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)

minimax regret, where

T

is the total number of interactions and

\tilde O(\cdot)

drops all constant and logarithmic factors, improving the previous

\tilde{O}(\sqrt{KT/A})

regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of

A

up to

\tilde{O}(1)

factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of

K

-armed bandits with

A

over the entire range of

1 \leq A \leq K-1

Kaixuan Ji, Qiwei Di, Qingyue Zhao +2

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Multi-Armed Bandits Minimax Regret Regret Minimization

Ask PDF

Aug 10, 2026

Tracking the Best Strategy in an Extensive-Form Game

We consider the extensive-form bandit problem where on each trial the learner plays an extensive-form game against an oblivious adversary. We focus on the notion of switching regret, which measures the expected performance of the learner against that of any switching sequence of mixed strategies in retrospect. Our algorithm takes a parameter

ρ>0

and achieves a switching regret of

\tilde{\mathcal{O}}((1/ρ+ρK)\sqrt{H A T})

where

K

is the number of switches in the comparator sequence,

H

is the maximum number of the learner's information sets that can be traversed during a play of the game and

A

is the number of actions that the learner can possibly take. Our algorithm is extremely efficient, taking a per trial time of only

\mathcal{O}(H B)

where

B

is the maximum number of actions available to the learner at any of its information sets.

Stephen Pasteris, Rahul Savani, Theodore Turocy

The Alan Turing Institute · London, United Kingdom · The University of Liverpool +3

Imperfect-Information Games Regret Minimization Adversarial Bandits

Ask PDF