# An α-No-Regret Algorithm For Graphical Bilinear Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 26 references that are in the map.
- First posted on arXiv 1 Jun 2022.

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

- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Best Arm Identification in Graphical Bilinear Bandits](https://mlsanity.com/paper/2012.07641/) (2020)

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

- [Bandits with Single-Peaked Preferences and Limited Resources](https://mlsanity.com/paper/2510.09425/) (2025)

## Abstract (arXiv)

We propose the first regret-based approach to the Graphical Bilinear Bandits problem, where n agents in a graph play a stochastic bilinear bandit game with each of their neighbors. This setting reveals a combinatorial NP-hard problem that prevents the use of any existing regret-based algorithm in the (bi-)linear bandit literature. In this paper, we fill this gap and present the first regret-based algorithm for graphical bilinear bandits using the principle of optimism in the face of uncertainty. Theoretical analysis of this new method yields an upper bound of tildeO(√T) on the α-regret and evidences the impact of the graph structure on the rate of convergence. Finally, we show through various experiments the validity of our approach.