Metraipolis › archive › dc_09107f79fa34

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary — arXiv:2609.13547

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.13547
License (as archived)
CC0-1.0
Archived
2026-10-16T00:10:24.177Z
SHA-256 of the archived text
328bec2416b4d1ca354d9cc39494f76f8d3abd9684d475a9ae83736fa4cfeb89
Stable URL of this page
https://metraipolis.com/documento/dc_09107f79fa34

How to cite

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary — arXiv:2609.13547 — arXiv (en), https://arxiv.org/abs/2609.13547 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_09107f79fa34 (Metraipolis archive dc_09107f79fa34, sha256 328bec2416b4d1ca354d9cc39494f76f8d3abd9684d475a9ae83736fa4cfeb89)
BibTeX
@misc{dc09107f79fa34,
  title = {Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary — arXiv:2609.13547},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.13547},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_09107f79fa34; sha256 328bec2416b4d1ca354d9cc39494f76f8d3abd9684d475a9ae83736fa4cfeb89},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.13547. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-15 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.13547 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T23:54:14.621Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).