UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Laplacian-Regularized Graph Bandits: Algorithms and Theoretical Analysis

Yang, K; Dong, X; Toni, L; (2020) Laplacian-Regularized Graph Bandits: Algorithms and Theoretical Analysis. In: Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics. (pp. pp. 3133-3143). PMLR Green open access

[img]
Preview
Text
main.pdf - Accepted version

Download (1MB) | Preview

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 random-walk graph Laplacian, which leads to a single-user cumulative regret scaling as \TildeO(ΨdT−−√) with time horizon T, feature dimensionality d, and the scalar parameter Ψ∈(0,1) that depends on the graph connectivity. This is an improvement over \TildeO(dT−−√) 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 \TildeO(ΨdnT−−−√), which is a significant improvement over \TildeO(ndT−−√) in the state-of-the-art 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 finite-time analysis on the proposed algorithms, and demonstrate their advantage in comparison with state-of-the-art graph-based bandit algorithms on both synthetic and real-world data.

Type: Proceedings paper
Title: Laplacian-Regularized Graph Bandits: Algorithms and Theoretical Analysis
Event: International Conference on Artificial Intelligence and Statistics
Open access status: An open access version is available from UCL Discovery
Publisher version: http://proceedings.mlr.press/v108/yang20c.html
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Electronic and Electrical Eng
URI: https://discovery.ucl.ac.uk/id/eprint/10110895
Downloads since deposit
17Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item