# Stochastic Contextual Bandits with Graph-based Contexts

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 2 May 2023.

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

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Latent Bandits Revisited](https://mlsanity.com/paper/2006.08714/) (2020)
- [Improved Algorithm on Online Clustering of Bandits](https://mlsanity.com/paper/1902.09162/) (2019)
- [Online Similarity Prediction of Networked Data from Known and Unknown Graphs](https://mlsanity.com/paper/1302.7263/) (2013)

## Abstract (arXiv)

We naturally generalize the on-line graph prediction problem to a version of stochastic contextual bandit problems where contexts are vertices in a graph and the structure of the graph provides information on the similarity of contexts. More specifically, we are given a graph G=(V,E), whose vertex set V represents contexts with em unknown vertex label y. In our stochastic contextual bandit setting, vertices with the same label share the same reward distribution. The standard notion of instance difficulties in graph label prediction is the cutsize f defined to be the number of edges whose end points having different labels. For line graphs and trees we present an algorithm with regret bound of tildeO(T2/3K1/3f1/3) where K is the number of arms. Our algorithm relies on the optimal stochastic bandit algorithm by Zimmert and Seldin~[AISTAT'19, JMLR'21]. When the best arm outperforms the other arms, the regret improves to tildeO(√KT· f). The regret bound in the later case is comparable to other optimal contextual bandit results in more general cases, but our algorithm is easy to analyze, runs very efficiently, and does not require an i.i.d. assumption on the input context sequence. The algorithm also works with general graphs using a standard random spanning tree reduction.