Metraipolis › archive › dc_422673eb763a
Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits — arXiv:2611.04307
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04307
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T18:55:52.739Z
- SHA-256 of the archived text
cfdc7ca4be5e58783f3b0914d56ab17a1544af4d4e9e86fd93938721601d4c4a- Stable URL of this page
https://metraipolis.com/documento/dc_422673eb763a
How to cite
Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits — arXiv:2611.04307 — arXiv (en), https://arxiv.org/abs/2611.04307 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_422673eb763a (Metraipolis archive dc_422673eb763a, sha256 cfdc7ca4be5e58783f3b0914d56ab17a1544af4d4e9e86fd93938721601d4c4a)
BibTeX
@misc{dc422673eb763a,
title = {Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits — arXiv:2611.04307},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04307},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_422673eb763a; sha256 cfdc7ca4be5e58783f3b0914d56ab17a1544af4d4e9e86fd93938721601d4c4a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04307. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study online learning with directed weakly observable feedback graphs and propose a Follow-the-Perturbed-Leader (FTPL) policy that achieves best-of-both-worlds guarantee with nearly linear expected time complexity. To preserve the simple structure of FTPL, we develop a novel graph-based loss estimator that combines forced exploration, conditional geometric resampling and adaptive learning rates with surrogate probabilities. Our policy achieves $\tilde{\mathcal{O}}(\delta_*^{1/3} T^{2/3})$ regret for adversarial regimes as well as $\tilde{\mathcal{O}}(\delta_* \log T / \Delta_{\min}^2)$ regret for stochastic regimes, where $\delta_*$ and $\Delta$, respectively, denote the fractional weak domination number and the suboptimality gap. These results show that refined guarantees for problems with minimax regret of $\Theta(T^{2/3})$ can be obtained through appropriately designed adaptive learning rates and loss estimators without sacrificing the simplicity of FTPL.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.04307 — 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-11-04T18:35:37.527Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).