Metraipolis › archive › dc_430f8f8340fb
Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits — arXiv:2608.15996
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.15996
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T19:41:14.714Z
- SHA-256 of the archived text
a53cc112fc0fcf818d4b5b762170cedc7534376f4d2da8c34c832dcb5190e0e8- Stable URL of this page
https://metraipolis.com/documento/dc_430f8f8340fb
How to cite
Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits — arXiv:2608.15996 — arXiv (en), https://arxiv.org/abs/2608.15996 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_430f8f8340fb (Metraipolis archive dc_430f8f8340fb, sha256 a53cc112fc0fcf818d4b5b762170cedc7534376f4d2da8c34c832dcb5190e0e8)
BibTeX
@misc{dc430f8f8340fb,
title = {Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits — arXiv:2608.15996},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.15996},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_430f8f8340fb; sha256 a53cc112fc0fcf818d4b5b762170cedc7534376f4d2da8c34c832dcb5190e0e8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.15996. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study second-order path-length regret in adversarial $K$-armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves $\widetilde{\mathcal{O}}(K+\sqrt{KQ_{\infty,1}})$ regret, where $Q_{\infty,1}$ is the first-order path length, and left open whether $\widetilde{\mathcal{O}}(\text{poly}(K)\sqrt{1+Q_{\infty,2}})$ regret is achievable under bandit feedback, where $Q_{\infty,2}$ is the second-order path length. Somewhat surprisingly, we resolve this question positively by showing that with a more involved analysis, the exact same algorithm of Bubeck et al. [2019] achieves $\mathcal{O}\left(K\log(KT)+\sqrt{K\log(KT)\bigl(1+Q_{\infty,2}\bigr)}\right)$ expected regret when $Q_{\infty,2}$ is known, where $T$ is the horizon. This matches the $\Omega(\sqrt{KQ_{\infty,2}})$ lower bound up to logarithmic factors and additive terms. We further remove the knowledge of $Q_{\infty,2}$ using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-18 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.15996 — 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-18T19:02:44.141Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).