# Stochastic Graph Bandit Learning with Side-Observations

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 29 Aug 2023.

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

- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [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)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [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)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (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)
- [Estimation Considerations in Contextual Bandits](https://mlsanity.com/paper/1711.07077/) (2017)
- [Feedback graph regret bounds for Thompson Sampling and UCB](https://mlsanity.com/paper/1905.09898/) (2019)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Practical Contextual Bandits with Feedback Graphs](https://mlsanity.com/paper/2302.08631/) (2023)
- [Reinforcement Learning with Feedback Graphs](https://mlsanity.com/paper/2005.03789/) (2020)
- [Contextual Bandits with Side-Observations](https://mlsanity.com/paper/2006.03951/) (2020)
- [Adversarial Linear Contextual Bandits with Graph-Structured Side Observations](https://mlsanity.com/paper/2012.05756/) (2020)
- [Efficient Kernel UCB for Contextual Bandits](https://mlsanity.com/paper/2202.05638/) (2022)
- [Efficient Transfer Learning via Causal Bounds](https://mlsanity.com/paper/2308.03572/) (2023)

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

- [Parameter-Adaptive Dynamic Pricing](https://mlsanity.com/paper/2503.00929/) (2025)

## Abstract (arXiv)

In this paper, we investigate the stochastic contextual bandit with general function space and graph feedback. We propose an algorithm that addresses this problem by adapting to both the underlying graph structures and reward gaps. To the best of our knowledge, our algorithm is the first to provide a gap-dependent upper bound in this stochastic setting, bridging the research gap left by the work in [35]. In comparison to [31,33,35], our method offers improved regret upper bounds and does not require knowledge of graphical quantities. We conduct numerical experiments to demonstrate the computational efficiency and effectiveness of our approach in terms of regret upper bounds. These findings highlight the significance of our algorithm in advancing the field of stochastic contextual bandits with graph feedback, opening up avenues for practical applications in various domains.