Preprint
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
arXiv
arXiv
09/11/2026
DOI: 10.48550/arxiv.2609.13547
Abstract
We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at mostStimes. WhenSis known, an optimal expected regret of\widetilde{𝓞}{(}{√(̅S̅+̅1̅)̅K̅T̅})is obtainable [Auer et al., 2002]. However, whenSis 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{𝓞}{(}{√(̅S̅+̅1̅)̅K̅T̅})expected regret for everySagainst 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 switchesS .
Details
- Title: Subtitle
- Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
- Creators
- Mengxiao Zhang
- Resource Type
- Preprint
- Publication Details
- arXiv
- DOI
- 10.48550/arxiv.2609.13547
- ISSN
- 2331-8422
- Publisher
- arXiv
- Language
- English
- Date posted
- 09/11/2026
- Academic Unit
- Business Analytics
- Record Identifier
- 9985230782802771
Metrics
1 Record Views