Metraipolis › archive › dc_d2e82036accf

Near-Optimal First-Order Regret for Bandits with Feedback Graphs — arXiv:2610.40861

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.40861
License (as archived)
CC0-1.0
Archived
2026-11-03T08:11:39.232Z
SHA-256 of the archived text
8790af36b25a49db53256d13d7a5fe61f1d10f4075d55c9cd5ac706899e4c7c3
Stable URL of this page
https://metraipolis.com/documento/dc_d2e82036accf

How to cite

Near-Optimal First-Order Regret for Bandits with Feedback Graphs — arXiv:2610.40861 — arXiv (en), https://arxiv.org/abs/2610.40861 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d2e82036accf (Metraipolis archive dc_d2e82036accf, sha256 8790af36b25a49db53256d13d7a5fe61f1d10f4075d55c9cd5ac706899e4c7c3)
BibTeX
@misc{dcd2e82036accf,
  title = {Near-Optimal First-Order Regret for Bandits with Feedback Graphs — arXiv:2610.40861},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40861},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d2e82036accf; sha256 8790af36b25a49db53256d13d7a5fe61f1d10f4075d55c9cd5ac706899e4c7c3},
  year = {2026}
}

Archived text

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

We study first-order regret guarantees for adversarial bandits with a fixed, known directed feedback graph. For strongly observable graphs, [ACBDK15] establishes a minimax regret of $\widetilde{\Theta}(\sqrt{\alpha T})$, where $\alpha$ denotes the independence number of the graph and $T$ denotes the horizon. On the other hand, the best existing first-order bound scales as $\widetilde{O}(\sqrt{(\kappa+1) L^\star})$ [LLZ20], where $\kappa$ denotes the clique partition number, satisfying $\kappa+1\geq\alpha$, and $L^\star$ denotes the cumulative loss of the best arm, leaving a gap between the graph dependence in worst-case and first-order guarantees. In this paper, we bridge this gap by obtaining an expected regret bound of $\widetilde{O}(\sqrt{\alpha L^\star}+\alpha)$. Our first result is an algorithm for the special case of self-aware graphs, in which every vertex has a self-loop. The algorithm combines the update of EXP3 [ACBFS02] with a sampling rule inspired by exploration by optimization [LS20]. More specifically, we construct a map whose fixed points yield sampling distributions that control the one-round regret remainder in terms of the learner's loss and the graph's independence number, which is crucial in deriving optimal first-order guarantees. We further show that a sufficiently accurate fixed point can be computed in polynomial time by a geometrically convergent iteration. Finally, we extend the algorithm to general strongly observable graphs and achieve the same $\widetilde{O}(\sqrt{\alpha L^\star}+\alpha)$ guarantee by adapting the two-level aggregation approach of [LLZ20].

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.40861 — 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-03T08:02:38.894Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).