# Practical Contextual Bandits with Feedback Graphs

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 37 references that are in the map.
- First posted on arXiv 17 Feb 2023.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [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)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [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)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Small-loss bounds for online learning with partial information](https://mlsanity.com/paper/1711.03639/) (2017)
- [Contextual Bandits with Smooth Regret: Efficient Learning in Continuous Action Spaces](https://mlsanity.com/paper/2207.05849/) (2022)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Stochastic Online Learning with Probabilistic Graph Feedback](https://mlsanity.com/paper/1903.01083/) (2019)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Contextual Bandits with Side-Observations](https://mlsanity.com/paper/2006.03951/) (2020)
- [Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs](https://mlsanity.com/paper/2210.01376/) (2022)
- [Adversarial Linear Contextual Bandits with Graph-Structured Side Observations](https://mlsanity.com/paper/2012.05756/) (2020)

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

- [Efficient Contextual Bandits with Uninformed Feedback Graphs](https://mlsanity.com/paper/2402.08127/) (2024)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Contextual Multinomial Logit Bandits with General Value Functions](https://mlsanity.com/paper/2402.08126/) (2024)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [Provably Efficient Interactive-Grounded Learning with Personalized Reward](https://mlsanity.com/paper/2405.20677/) (2024)
- [Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing](https://mlsanity.com/paper/2607.09015/) (2026)
- [Stochastic Graph Bandit Learning with Side-Observations](https://mlsanity.com/paper/2308.15107/) (2023)
- [Laplacian Kernelized Bandit](https://mlsanity.com/paper/2601.00461/) (2026)
- [Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback](https://mlsanity.com/paper/2602.08307/) (2026)
- [Efficient contextual partial monitoring with general function approximation](https://mlsanity.com/paper/2610.19804/) (2026)

## Abstract (arXiv)

While contextual bandit has a mature theory, effectively leveraging different feedback patterns to enhance the pace of learning remains unclear. Bandits with feedback graphs, which interpolates between the full information and bandit regimes, provides a promising framework to mitigate the statistical complexity of learning. In this paper, we propose and analyze an approach to contextual bandits with feedback graphs based upon reduction to regression. The resulting algorithms are computationally practical and achieve established minimax rates, thereby reducing the statistical complexity in real-world applications.