# Online Learning with Feedback Graphs: The True Shape of Regret

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 5 Jun 2023.

## Builds on (most cited first, 6 of 6)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)

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

- [On Interpolating Experts and Multi-Armed Bandits](https://mlsanity.com/paper/2307.07264/) (2023)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [Adversarial Combinatorial Semi-bandits with Graph Feedback](https://mlsanity.com/paper/2502.18826/) (2025)
- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)

## Abstract (arXiv)

Sequential learning with feedback graphs is a natural extension of the multi-armed bandit problem where the problem is equipped with an underlying graph structure that provides additional information - playing an action reveals the losses of all the neighbors of the action. This problem was introduced by citetmannor2011 and received considerable attention in recent years. It is generally stated in the literature that the minimax regret rate for this problem is of order √α T, where α is the independence number of the graph, and T is the time horizon. However, this is proven only when the number of rounds T is larger than α3, which poses a significant restriction for the usability of this result in large graphs. In this paper, we define a new quantity R^*, called the problem complexity, and prove that the minimax regret is proportional to R^* for any graph and time horizon T. Introducing an intricate exploration strategy, we define the mainAlgorithm algorithm that achieves the minimax optimal regret bound and becomes the first provably optimal algorithm for this setting, even if T is smaller than α3.