# Bandits on graphs and structures

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 139 references that are in the map.
- First posted on arXiv 5 May 2026.

## Builds on (most cited first, 30 of 41)

- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (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)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)
- [An efficient algorithm for learning with semi-bandit feedback](https://mlsanity.com/paper/1305.2732/) (2013)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Online Influence Maximization (Extended Version)](https://mlsanity.com/paper/1506.01188/) (2015)
- [Online Learning with Gaussian Payoffs and Side Observations](https://mlsanity.com/paper/1510.08108/) (2015)
- [Influence Maximization with Bandits](https://mlsanity.com/paper/1503.00024/) (2015)
- [Online Stochastic Optimization under Correlated Bandit Feedback](https://mlsanity.com/paper/1402.0562/) (2014)
- [Stochastic simultaneous optimistic optimization](https://mlsanity.com/paper/2604.24537/) (2026)
- [Adaptive-treed bandits](https://mlsanity.com/paper/1302.2489/) (2013)
- [Cheap Bandits](https://mlsanity.com/paper/1506.04782/) (2015)
- [Multistage Campaigning in Social Networks](https://mlsanity.com/paper/1606.03816/) (2016)
- [Spectral Thompson sampling](https://mlsanity.com/paper/2604.13739/) (2026)
- [Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning](https://mlsanity.com/paper/2604.14974/) (2026)
- [Efficient learning by implicit exploration in bandit problems with side observations](https://mlsanity.com/paper/2604.24555/) (2026)

## Abstract (arXiv)

The goal of this thesis is to investigate the structural properties of certain sequential problems in order to bring the solutions closer to a practical use. In the first part, we put a special emphasis on structures that can be represented as graphs on actions. In the second part, we study the large action spaces that can be of exponential size in the number of base actions or even infinite. For graph bandits, we consider the settings of smoothness of rewards (spectral bandits), side observations, and influence maximization. For large structured domains, we cover kernel bandits, polymatroid bandits, bandits for function optimization (including unknown smoothness), and infinitely many-arms bandits. The thesis aspires to be a survey of the author's contributions on graph and structured bandits.