Best Arm Identification in Graphical Bilinear Bandits

Geovani Rizk, Albert Thomas, Igor Colin, Rida Laraki, Yann Chevaleyre
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:9010-9019, 2021.

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 this Paper

BibTeX
@InProceedings{pmlr-v139-rizk21a, title = {Best Arm Identification in Graphical Bilinear Bandits}, author = {Rizk, Geovani and Thomas, Albert and Colin, Igor and Laraki, Rida and Chevaleyre, Yann}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {9010--9019}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/rizk21a/rizk21a.pdf}, url = {https://proceedings.mlr.press/v139/rizk21a.html}, 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.} }
Endnote
%0 Conference Paper %T Best Arm Identification in Graphical Bilinear Bandits %A Geovani Rizk %A Albert Thomas %A Igor Colin %A Rida Laraki %A Yann Chevaleyre %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-rizk21a %I PMLR %P 9010--9019 %U https://proceedings.mlr.press/v139/rizk21a.html %V 139 %X 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.
APA
Rizk, G., Thomas, A., Colin, I., Laraki, R. & Chevaleyre, Y.. (2021). Best Arm Identification in Graphical Bilinear Bandits. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:9010-9019 Available from https://proceedings.mlr.press/v139/rizk21a.html.

Related Material