Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits
Abstract
We study a network of agents communicating with each other and optimizing
their performance in a common nonstochastic multi-armed bandit problem.
We derive regret minimization algorithms that guarantee for each agent
$v$ an individual expected regret of
\[
\widetilde{O}\left(\sqrt{\left(1+\frac{K}{\left|\mathcal{N}\left(v\right)\right|}\right)T}\right),
\]
where $T$ is the number of time steps, $K$ is the number of actions
and $\mathcal{N}\left(v\right)$ is the set of neighbors of agent
$v$ in the communication graph. We present algorithms both for the
case that the communication graph is known to all the agents, and
for the case that the graph is unknown. When the communication graph
is unknown, each agent knows only the set of its neighbors and a bound
on the total number of agents. The individual regret between the models
differ only by a logarithmic factor. Our work resolves an open problem
from (\citet{cesa2019delay}).