Metraipolis › archive › dc_2c4d330c1ca5

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-03T05:40:36.307Z
SHA-256 of the archived text: 887b71fe8b7f0aacdec1fb41e5a252d3a96f76bb8429a6b1cd04b70e625c8c01
Stable URL of this page: https://metraipolis.com/documento/dc_2c4d330c1ca5

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_2c4d330c1ca5 (Metraipolis archive dc_2c4d330c1ca5, sha256 887b71fe8b7f0aacdec1fb41e5a252d3a96f76bb8429a6b1cd04b70e625c8c01)

BibTeX

@misc{dc2c4d330c1ca5,
  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_2c4d330c1ca5; sha256 887b71fe8b7f0aacdec1fb41e5a252d3a96f76bb8429a6b1cd04b70e625c8c01},
  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-03T05:26:13.914Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).