Distributed Optimization via Kernelized Multi-armed Bandits
Ayush Rai Shaoshuai Mou
Multi-armed bandit algorithms provide solutions for sequential
decision-making where learning takes place by interacting with the environment.
In this work, we model a distributed optimization problem as a multi-agent
kernelized multi-armed bandit problem with a heterogeneous reward setting. In
this setup, the agents collaboratively aim to maximize a global objective
function which is an average of local objective functions. The agents can
access only bandit feedback (noisy reward) obtained from the associated unknown
local function with a small norm in reproducing kernel Hilbert space (RKHS). We
present a fully decentralized algorithm, Multi-agent IGP-UCB (MA-IGP-UCB),
which achieves a sub-linear regret bound for popular classes for kernels while
preserving privacy. It does not necessitate the agents to share their actions,
rewards, or estimates of their local function. In the proposed approach, the
agents sample their individual local functions in a way that benefits the whole
network by utilizing a running consensus to estimate the upper confidence bound
on the global function. Furthermore, we propose an extension, Multi-agent
Delayed IGP-UCB (MAD-IGP-UCB) algorithm, which reduces the dependence of the
regret bound on the number of agents in the network. It provides improved
performance by utilizing a delay in the estimation update step at the cost of
more communication.