Toni, L;
Frossard, P;
(2023)
Online Network Source Optimization with Graph-Kernel MAB.
In:
Joint European Conference on Machine Learning and Knowledge Discovery in Databases ECML PKDD 2023: Machine Learning and Knowledge Discovery in Databases: Research Track.
(pp. pp. 242-258).
Springer: Cham, Switzerland.
Preview |
Text
Graph_MAB.pdf - Accepted Version Download (2MB) | Preview |
Abstract
We propose Grab-UCB, a graph-kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks, such that the reward obtained from a priori unknown network processes is maximized. The uncertainty calls for online learning, which suffers however from the curse of dimensionality. To achieve sample efficiency, we describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. This enables a data-efficient learning framework, whose learning rate scales with the dimension of the spectral representation model instead of the one of the network. We then propose Grab-UCB, an online sequential decision strategy that learns the parameters of the spectral representation while optimizing the action strategy. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy We introduce a computationally simplified solving method, Grab-arm-Light, an algorithm that walks along the edges of the polytope representing the objective function. Simulations results show that the proposed online learning algorithm outperforms baseline offline methods that typically separate the learning phase from the testing one. The results confirm the theoretical findings, and further highlight the gain of the proposed online learning strategy in terms of cumulative regret, sample efficiency and computational complexity.
| Type: | Proceedings paper |
|---|---|
| Title: | Online Network Source Optimization with Graph-Kernel MAB |
| Event: | European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases 2023 |
| Location: | Turin, Italy |
| Dates: | 18 Sep 2022 - 22 Sep 2022 |
| ISBN-13: | 9783031434174 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-031-43418-1_15 |
| Publisher version: | https://doi.org/10.1007/978-3-031-43418-1_15 |
| 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. |
| Keywords: | multi-arms bandit, graph dictionary, graph-kernel |
| UCL classification: | UCL 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/10181490 |
Archive Staff Only
 |
View Item |
