Best Arm Identification in Graphical Bilinear Bandits
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.
Cite
Text
Rizk et al. "Best Arm Identification in Graphical Bilinear Bandits." International Conference on Machine Learning, 2021.Markdown
[Rizk et al. "Best Arm Identification in Graphical Bilinear Bandits." International Conference on Machine Learning, 2021.](https://mlanthology.org/icml/2021/rizk2021icml-best/)BibTeX
@inproceedings{rizk2021icml-best,
title = {{Best Arm Identification in Graphical Bilinear Bandits}},
author = {Rizk, Geovani and Thomas, Albert and Colin, Igor and Laraki, Rida and Chevaleyre, Yann},
booktitle = {International Conference on Machine Learning},
year = {2021},
pages = {9010-9019},
volume = {139},
url = {https://mlanthology.org/icml/2021/rizk2021icml-best/}
}