# A Closer Look at Small-loss Bounds for Bandits with Graph Feedback

arXiv: https://arxiv.org/abs/2002.00315 · HTML: https://mlsanity.com/paper/2002.00315/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2020.

## Built on by (most cited first, 21 of 21)

- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Practical Contextual Bandits with Feedback Graphs](https://mlsanity.com/paper/2302.08631/) (2023)
- [uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABs](https://mlsanity.com/paper/2410.03284/) (2024)
- [Efficient Contextual Bandits with Uninformed Feedback Graphs](https://mlsanity.com/paper/2402.08127/) (2024)
- [Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs](https://mlsanity.com/paper/2210.01376/) (2022)
- [Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2107.09572/) (2021)
- [Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization](https://mlsanity.com/paper/2608.04149/) (2026)
- [Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality](https://mlsanity.com/paper/2206.10022/) (2022)
- [Data-Dependent Regret Bounds for Constrained MABs](https://mlsanity.com/paper/2505.20010/) (2025)
- [Online Network Source Optimization with Graph-Kernel MAB](https://mlsanity.com/paper/2307.03641/) (2023)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression](https://mlsanity.com/paper/2306.08320/) (2023)
- [Incentive-compatible Bandits: Importance Weighting No More](https://mlsanity.com/paper/2405.06480/) (2024)
- [Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach](https://mlsanity.com/paper/2602.06404/) (2026)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)
- [Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2608.15996/) (2026)

## Abstract (arXiv)

We study small-loss bounds for adversarial multi-armed bandits with graph feedback, that is, adaptive regret bounds that depend on the loss of the best arm or related quantities, instead of the total number of rounds. We derive the first small-loss bound for general strongly observable graphs, resolving an open problem of Lykouris et al. (2018). Specifically, we develop an algorithm with regret mathcaltildeO(√kappa L_*) where kappa is the clique partition number and L_* is the loss of the best arm, and for the special case of self-aware graphs where every arm has a self-loop, we improve the regret to mathcaltildeO(min√α T, √kappa L_*) where α ≤ kappa is the independence number. Our results significantly improve and extend those by Lykouris et al. (2018) who only consider self-aware undirected graphs. Furthermore, we also take the first attempt at deriving small-loss bounds for weakly observable graphs. We first prove that no typical small-loss bounds are achievable in this case, and then propose algorithms with alternative small-loss bounds in terms of the loss of some specific subset of arms. A surprising side result is that mathcaltildeO(√T) regret is achievable even for weakly observable graphs as long as the best arm has a self-loop. Our algorithms are based on the Online Mirror Descent framework but require a suite of novel techniques that might be of independent interest. Moreover, all our algorithms can be made parameter-free without the knowledge of the environment.