Distributed Optimization via Kernelized Multi-armed Bandits

Multiarmed 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 multiagent kernelized multiarmed 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 local function with a small norm in reproducing kernel Hilbert space. These local functions are unknown and not necessarily convex. We present a fully decentralized algorithm, multiagent improved Gaussian process upper confidence bound (IGP-UCB), which achieves a sublinear 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, multiagent delayed 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.

Paper

Similar papers

© 2026 NYSGPT2525 LLC