Best Arm Identification in Graphical Bilinear Bandits
arXiv:2012.07641
Abstract
We introduce a new graphical bilinear bandit problem where a learner (or a \emph{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 \emph{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.
References in corpus (11)
- Best-Arm Identification in Linear Bandits
- From Bandits to Experts: On the Value of Side-Observations
- Spectral bandits for smooth graph functions
- Bandits on graphs and structures
- Optimal Best-arm Identification in Linear Bandits
- Bilinear Bandits with Low-rank Structure
- Graphical Models for Bandit Problems
- Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
- Towards Optimal and Efficient Best Arm Identification in Linear Bandits
- Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback
- Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback