Near-Optimal First-Order Regret for Bandits with Feedback Graphs
Abstract
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 Θ̃(√(αT)), where α denotes the independence number of the graph and T denotes the horizon. On the other hand, the best existing first-order bound scales as Õ(√((κ+1) L⋆)) [LLZ20], where κ denotes the clique partition number, satisfying κ+1≥α, and L⋆ 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 Õ(√(αL⋆)+α). 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 Õ(√(αL⋆)+α) guarantee by adapting the two-level aggregation approach of [LLZ20].
Related
- Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
- Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
- Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
- Bandits with Probing: Optimal Coverage and the Role of Feedback
BibTeX
@misc{zhang2026nearoptimal,
title = {{Near-Optimal First-Order Regret for Bandits with Feedback Graphs}},
author = {Mengxiao Zhang and Yuheng Zhang and Haipeng Luo and Paul Mineiro},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40861},
eprint = {2610.40861},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40861},
}
RIS
TY - UNPB
TI - Near-Optimal First-Order Regret for Bandits with Feedback Graphs
AU - Mengxiao Zhang
AU - Yuheng Zhang
AU - Haipeng Luo
AU - Paul Mineiro
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40861
UR - https://arxiv.org/abs/2610.40861
AB - 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 Θ̃(√(αT)), where α denotes the independence number of the graph and T denotes the horizon. On the other hand, the best existing first-order bound scales as Õ(√((κ+1) L^⋆)) [LLZ20], where κ denotes the clique partition number, satisfying κ+1≥α, and L^⋆ 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 Õ(√(αL^⋆)+α). 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 Õ(√(αL^⋆)+α) guarantee by adapting the two-level aggregation approach of [LLZ20].
ER -