analiza aiqbench
This paper tightens the theoretical bounds for online learning with bandits that observe feedback through a known graph, improving regret guarantees that scale with a problem-dependent loss term rather than only the horizon. The main contribution is an algorithm that closes a gap between worst-case and first-order results, with the analysis resting on EXP3-style updates and a fixed-point sampling rule. For ML readers, the value is in the refined theory and the polynomial-time computability claim, which matter for sequential decision-making, though the work is algorithmic theory and has no immediate practical deployment evidence.
Near-Optimal First-Order Regret for Bandits with Feedback Graphs
arXiv:2610.40861v1 Announce Type: new 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 $\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].
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 $\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].
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2610.40861 [cs.LG]
(or arXiv:2610.40861v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.40861 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 319 cuvinte