Timezone: »

An $\alpha$-No-Regret Algorithm For Graphical Bilinear Bandits
Geovani Rizk · Igor Colin · Albert Thomas · Rida Laraki · Yann Chevaleyre

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #728
We propose the first regret-based approach to the \emph{Graphical Bilinear Bandits} problem, where $n$ agents in a graph play a stochastic bilinear bandit game with each of their neighbors. This setting reveals a combinatorial NP-hard problem that prevents the use of any existing regret-based algorithm in the (bi-)linear bandit literature. In this paper, we fill this gap and present the first regret-based algorithm for graphical bilinear bandits using the principle of optimism in the face of uncertainty. Theoretical analysis of this new method yields an upper bound of $\tilde{O}(\sqrt{T})$ on the $\alpha$-regret and evidences the impact of the graph structure on the rate of convergence. Finally, we show through various experiments the validity of our approach.

Author Information

Geovani Rizk (EPFL)
Igor Colin (Huawei)
Albert Thomas (Huawei)
Rida Laraki (University of Liverpool)
Yann Chevaleyre (Université Paris Dauphine)

More from the Same Authors