An α-No-Regret Algorithm For Graphical Bilinear Bandits

06/01/2022
by   Geovani Rizk, et al.
0

We propose the first regret-based approach to the 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 Õ(√(T)) on the α-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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset