Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling
  on Sparse Hypergraphs
Tianyuan Jin Hao-Lun Hsu William Chang Pan Xu
We study the multi-agent multi-armed bandit (MAMAB) problem, where $m$ agents
are factored into $\rho$ overlapping groups. Each group represents a hyperedge,
forming a hypergraph over the agents. At each round of interaction, the learner
pulls a joint arm (composed of individual arms for each agent) and receives a
reward according to the hypergraph structure. Specifically, we assume there is
a local reward for each hyperedge, and the reward of the joint arm is the sum
of these local rewards. Previous work introduced the multi-agent Thompson
sampling (MATS) algorithm \citep{verstraeten2020multiagent} and derived a
Bayesian regret bound. However, it remains an open problem how to derive a
frequentist regret bound for Thompson sampling in this multi-agent setting. To
address these issues, we propose an efficient variant of MATS, the
$\epsilon$-exploring Multi-Agent Thompson Sampling ($\epsilon$-MATS) algorithm,
which performs MATS exploration with probability $\epsilon$ while adopts a
greedy policy otherwise. We prove that $\epsilon$-MATS achieves a worst-case
frequentist regret bound that is sublinear in both the time horizon and the
local arm size. We also derive a lower bound for this setting, which implies
our frequentist regret upper bound is optimal up to constant and logarithm
terms, when the hypergraph is sufficiently sparse. Thorough experiments on
standard MAMAB problems demonstrate the superior performance and the improved
computational efficiency of $\epsilon$-MATS compared with existing algorithms
in the same setting.