Rizk, G, Thomas, A, Colin, I, Laraki, R ORCID: 0000-0002-4898-2424 and Chevaleyre, Y
(2021)
Best Arm Identification in Graphical Bilinear Bandits.
In: 38th International Conference on Machine Learning.
Text
ICML2021.pdf - Submitted version Download (563kB) | Preview |
Abstract
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.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
Depositing User: | Symplectic Admin |
Date Deposited: | 22 Jun 2021 08:04 |
Last Modified: | 30 Jun 2023 21:45 |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3127080 |