# Feedback graph regret bounds for Thompson Sampling and UCB

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2019.

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

- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [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)
- [Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality](https://mlsanity.com/paper/2206.10022/) (2022)
- [Graph Feedback Bandits on Similar Arms: With and Without Graph Structures](https://mlsanity.com/paper/2501.14314/) (2025)
- [Graph Feedback Bandits with Similar Arms](https://mlsanity.com/paper/2405.11171/) (2024)
- [Ranking In Generalized Linear Bandits](https://mlsanity.com/paper/2207.00109/) (2022)
- [Invariant Lipschitz Bandits: A Side Observation Approach](https://mlsanity.com/paper/2212.07524/) (2022)
- [Online Network Source Optimization with Graph-Kernel MAB](https://mlsanity.com/paper/2307.03641/) (2023)
- [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)
- [An improved regret analysis for UCB-N and TS-N](https://mlsanity.com/paper/2305.04093/) (2023)
- [Asymptotically-Optimal Gaussian Bandits with Side Observations](https://mlsanity.com/paper/2505.10698/) (2025)
- [Online Learning with Multiple Fairness Regularizers via Graph-Structured Feedback](https://mlsanity.com/paper/2508.14311/) (2025)
- [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026)

## Abstract (arXiv)

We study the stochastic multi-armed bandit problem with the graph-based feedback structure introduced by Mannor and Shamir. We analyze the performance of the two most prominent stochastic bandit algorithms, Thompson Sampling and Upper Confidence Bound (UCB), in the graph-based feedback setting. We show that these algorithms achieve regret guarantees that combine the graph structure and the gaps between the means of the arm distributions. Surprisingly this holds despite the fact that these algorithms do not explicitly use the graph structure to select arms; they observe the additional feedback but do not explore based on it. Towards this result we introduce a "layering technique" highlighting the commonalities in the two algorithms.