# Understanding Bandits with Graph Feedback

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 39 references that are in the map.
- First posted on arXiv 29 May 2021.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [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)
- [From Bandits to Experts: A Tale of Domination and Independence](https://mlsanity.com/paper/1307.4564/) (2013)
- [Online Learning with Feedback Graphs Without the Graphs](https://mlsanity.com/paper/1605.07018/) (2016)
- [Information Directed Sampling for Stochastic Bandits with Graph Feedback](https://mlsanity.com/paper/1711.03198/) (2017)
- [Connections Between Mirror Descent, Thompson Sampling and the Information Ratio](https://mlsanity.com/paper/1905.11817/) (2019)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Bandits with Feedback Graphs and Switching Costs](https://mlsanity.com/paper/1907.12189/) (2019)
- [Stochastic Online Learning with Probabilistic Graph Feedback](https://mlsanity.com/paper/1903.01083/) (2019)
- [Thompson Sampling For Stochastic Bandits with Graph Feedback](https://mlsanity.com/paper/1701.04238/) (2017)
- [Online learning with feedback graphs and switching costs](https://mlsanity.com/paper/1810.09666/) (2018)
- [Online learning with graph-structured feedback against adaptive adversaries](https://mlsanity.com/paper/1804.00335/) (2018)

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

- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback](https://mlsanity.com/paper/2206.07908/) (2022)
- [Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs](https://mlsanity.com/paper/2210.01376/) (2022)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [On Interpolating Experts and Multi-Armed Bandits](https://mlsanity.com/paper/2307.07264/) (2023)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing](https://mlsanity.com/paper/2607.09015/) (2026)
- [Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition](https://mlsanity.com/paper/2205.15076/) (2022)
- [Stochastic Graph Bandit Learning with Side-Observations](https://mlsanity.com/paper/2308.15107/) (2023)
- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)
- [Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback](https://mlsanity.com/paper/2502.04678/) (2025)
- [Online Learning with Multiple Fairness Regularizers via Graph-Structured Feedback](https://mlsanity.com/paper/2508.14311/) (2025)
- [Active Hypothesis Testing for Correlated Combinatorial Anomaly Detection](https://mlsanity.com/paper/2601.17430/) (2026)

## Abstract (arXiv)

The bandit problem with graph feedback, proposed in [Mannor and Shamir, NeurIPS 2011], is modeled by a directed graph G=(V,E) where V is the collection of bandit arms, and once an arm is triggered, all its incident arms are observed. A fundamental question is how the structure of the graph affects the min-max regret. We propose the notions of the fractional weak domination number δ^* and the k-packing independence number capturing upper bound and lower bound for the regret respectively. We show that the two notions are inherently connected via aligning them with the linear program of the weakly dominating set and its dual -- the fractional vertex packing set respectively. Based on this connection, we utilize the strong duality theorem to prove a general regret upper bound Oleft(left( δ^*log |V|right)^frac13T^frac23right) and a lower bound Omegaleft(left(δ^*/αright)^frac13T^frac23right) where α is the integrality gap of the dual linear program. Therefore, our bounds are tight up to a left(log |V|right)^frac13 factor on graphs with bounded integrality gap for the vertex packing problem including trees and graphs with bounded degree. Moreover, we show that for several special families of graphs, we can get rid of the left(log |V|right)^frac13 factor and establish optimal regret.