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

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 𝒪̃(√((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 𝒪̃(√((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.

Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
Shion Takeno, Shogo Iwazaki, Ichiro Takeuchi
arXiv20 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
Kaixuan Ji, Qiwei Di, Qingyue Zhao +2
arXiv1 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Online carpooling against an oblivious adversary
Yuhao Lei
arXiv1 Nov 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv
Near-Optimal First-Order Regret for Bandits with Feedback Graphs
Mengxiao Zhang, Yuheng Zhang, Haipeng Luo +1
arXiv29 Oct 2026PreprintarXiv licenceFull textStatisticsarXiv
Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
Qiwei Di, Quanquan Gu
arXiv28 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhang2026toward,
  title = {{Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary}},
  author = {Mengxiao Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.13547},
  eprint = {2609.13547},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.13547},
}

RIS

TY  - UNPB
TI  - Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
AU  - Mengxiao Zhang
PY  - 2026
DA  - 2026/09/11
PB  - arXiv
DO  - 10.48550/arxiv.2609.13547
UR  - https://arxiv.org/abs/2609.13547
AB  - 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 𝒪̃(√((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 𝒪̃(√((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.
ER  -

Abstract

Related

Cite