# Best Arm Identification in Graphical Bilinear Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2020.

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

- [Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricing](https://mlsanity.com/paper/2309.08634/) (2023)
- [An α-No-Regret Algorithm For Graphical Bilinear Bandits](https://mlsanity.com/paper/2206.00466/) (2022)
- [Efficient Generalized Low-Rank Tensor Contextual Bandits](https://mlsanity.com/paper/2311.01771/) (2023)
- [Deep Active Learning based Experimental Design to Uncover Synergistic Genetic Interactions for Host Targeted Therapeutics](https://mlsanity.com/paper/2502.01012/) (2025)

## Abstract (arXiv)

We introduce a new graphical bilinear bandit problem where a learner (or a central entity) allocates arms to the nodes of a graph and observes for each edge a noisy bilinear reward representing the interaction between the two end nodes. We study the best arm identification problem in which the learner wants to find the graph allocation maximizing the sum of the bilinear rewards. By efficiently exploiting the geometry of this bandit problem, we propose a decentralized allocation strategy based on random sampling with theoretical guarantees. In particular, we characterize the influence of the graph structure (e.g. star, complete or circle) on the convergence rate and propose empirical experiments that confirm this dependency.