LaplacianRegularized Graph Bandits: Algorithms and Theoretical Analysis
[edit]
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:31333143, 2020.
Abstract
We consider a stochastic linear bandit problem with multiple users, where the relationship between users is captured by an underlying graph and user preferences are represented as smooth signals on the graph. We introduce a novel bandit algorithm where the smoothness prior is imposed via the randomwalk graph Laplacian, which leads to a singleuser cumulative regret scaling as $\Tilde{\mathcal{O}}(\Psi d \sqrt{T})$ with time horizon $T$, feature dimensionality $d$, and the scalar parameter $\Psi \in (0,1)$ that depends on the graph connectivity. This is an improvement over $\Tilde{\mathcal{O}}(d \sqrt{T})$ in \algo{LinUCB} \Ccite{li2010contextual}, where user relationship is not taken into account.In terms of network regret (sum of cumulative regret over $n$ users), the proposed algorithm leads to a scaling as $\Tilde{\mathcal{O}}(\Psi d\sqrt{nT})$, which is a significant improvement over $\Tilde{\mathcal{O}}(nd\sqrt{T})$ in the stateoftheart algorithm \algo{Gob.Lin} \Ccite{cesa2013gang}. To improve scalability, we further propose a simplified algorithm with a linear computational complexity with respect to the number of users, while maintaining the same regret. Finally, we present a finitetime analysis on the proposed algorithms, and demonstrate their advantage in comparison with stateoftheart graphbased bandit algorithms on both synthetic and realworld data.
Related Material


