# Online Network Source Optimization with Graph-Kernel MAB

arXiv: https://arxiv.org/abs/2307.03641 · HTML: https://mlsanity.com/paper/2307.03641/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 58 references that are in the map.
- First posted on arXiv 7 Jul 2023.

## Builds on (most cited first, 30 of 32)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [A Geometric Perspective on Optimal Representations for Reinforcement Learning](https://mlsanity.com/paper/1901.11530/) (2019)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development](https://mlsanity.com/paper/1702.05122/) (2017)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [Q-Learning in enormous action spaces via amortized approximate maximization](https://mlsanity.com/paper/2001.08116/) (2020)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [Feedback graph regret bounds for Thompson Sampling and UCB](https://mlsanity.com/paper/1905.09898/) (2019)
- [Laplacian-regularized graph bandits: Algorithms and theoretical analysis](https://mlsanity.com/paper/1907.05632/) (2019)
- [Learning parametric dictionaries for graph signals](https://mlsanity.com/paper/1401.0887/) (2014)
- [Grid-Graph Signal Processing (Grid-GSP): A Graph Signal Processing Framework for the Power Grid](https://mlsanity.com/paper/2103.06068/) (2021)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Graph Neural Network Bandits](https://mlsanity.com/paper/2207.06456/) (2022)
- [Blind Community Detection from Low-rank Excitations of a Graph Filter](https://mlsanity.com/paper/1809.01485/) (2018)
- [Modelling Opinion Dynamics in the Age of Algorithmic Personalisation](https://mlsanity.com/paper/1811.03341/) (2018)
- [Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis](https://mlsanity.com/paper/2109.13573/) (2021)
- [Social Learning over Weakly-Connected Graphs](https://mlsanity.com/paper/1609.03703/) (2016)
- [Multi-user Communication Networks: A Coordinated Multi-armed Bandit Approach](https://mlsanity.com/paper/1808.04875/) (2018)
- [Graph-Based Recommendation System](https://mlsanity.com/paper/1808.00004/) (2018)
- [Adaptation and learning over networks under subspace constraints -- Part I: Stability Analysis](https://mlsanity.com/paper/1905.08750/) (2019)
- [Thompson Sampling with Diffusion Generative Prior](https://mlsanity.com/paper/2301.05182/) (2023)
- [Cheap Bandits](https://mlsanity.com/paper/1506.04782/) (2015)
- [Online Similarity Prediction of Networked Data from Known and Unknown Graphs](https://mlsanity.com/paper/1302.7263/) (2013)

## Built on by (most cited first, 1 of 1)

- [Graph Neural Thompson Sampling](https://mlsanity.com/paper/2406.10686/) (2024)

## Abstract (arXiv)

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.