# Stochastic contextual bandits with graph feedback: from independence number to MAS number

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 37 references that are in the map.
- First posted on arXiv 12 Feb 2024.

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

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [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)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces](https://mlsanity.com/paper/2207.05849/) (2022)
- [Feedback graph regret bounds for Thompson Sampling and UCB](https://mlsanity.com/paper/1905.09898/) (2019)
- [Contextual Information-Directed Sampling](https://mlsanity.com/paper/2205.10895/) (2022)
- [On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring](https://mlsanity.com/paper/2305.00684/) (2023)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret](https://mlsanity.com/paper/2202.10997/) (2022)
- [Practical Contextual Bandits with Feedback Graphs](https://mlsanity.com/paper/2302.08631/) (2023)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [Reinforcement Learning with Feedback Graphs](https://mlsanity.com/paper/2005.03789/) (2020)
- [Optimal cross-learning for contextual bandits with unknown context distributions](https://mlsanity.com/paper/2401.01857/) (2024)
- [Stochastic One-Sided Full-Information Bandit](https://mlsanity.com/paper/1906.08656/) (2019)
- [Online Learning with Feedback Graphs: The True Shape of Regret](https://mlsanity.com/paper/2306.02971/) (2023)

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

- [The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions](https://mlsanity.com/paper/2605.01756/) (2026)
- [Nearly Tight Bounds for Cross-Learning Contextual Bandits with Graphical Feedback](https://mlsanity.com/paper/2502.04678/) (2025)
- [Adversarial Combinatorial Semi-bandits with Graph Feedback](https://mlsanity.com/paper/2502.18826/) (2025)
- [Decentralized Contextual Bandits with Network Adaptivity](https://mlsanity.com/paper/2508.13411/) (2025)
- [Learning from Local Walks on Dynamic Graphs with Bandit Feedback](https://mlsanity.com/paper/2607.10571/) (2026)

## Abstract (arXiv)

We consider contextual bandits with graph feedback, a class of interactive learning problems with richer structures than vanilla contextual bandits, where taking an action reveals the rewards for all neighboring actions in the feedback graph under all contexts. Unlike the multi-armed bandits setting where a growing literature has painted a near-complete understanding of graph feedback, much remains unexplored in the contextual bandits counterpart. In this paper, we make inroads into this inquiry by establishing a regret lower bound Omega(√βM(G) T), where M is the number of contexts, G is the feedback graph, and βM(G) is our proposed graph-theoretic quantity that characterizes the fundamental learning limit for this class of problems. Interestingly, βM(G) interpolates between α(G) (the independence number of the graph) and mathsfm(G) (the maximum acyclic subgraph (MAS) number of the graph) as the number of contexts M varies. We also provide algorithms that achieve near-optimal regret for important classes of context sequences and/or feedback graphs, such as transitively closed graphs that find applications in auctions and inventory control. In particular, with many contexts, our results show that the MAS number essentially characterizes the statistical complexity for contextual bandits, as opposed to the independence number in multi-armed bandits.