Regret Lower Bounds in Multi-agent Multi-armed Bandit
Mengfan Xu Diego Klabjan
Multi-armed Bandit motivates methods with provable upper bounds on regret and
also the counterpart lower bounds have been extensively studied in this
context. Recently, Multi-agent Multi-armed Bandit has gained significant
traction in various domains, where individual clients face bandit problems in a
distributed manner and the objective is the overall system performance,
typically measured by regret. While efficient algorithms with regret upper
bounds have emerged, limited attention has been given to the corresponding
regret lower bounds, except for a recent lower bound for adversarial settings,
which, however, has a gap with let known upper bounds. To this end, we herein
provide the first comprehensive study on regret lower bounds across different
settings and establish their tightness. Specifically, when the graphs exhibit
good connectivity properties and the rewards are stochastically distributed, we
demonstrate a lower bound of order $O(\log T)$ for instance-dependent bounds
and $\sqrt{T}$ for mean-gap independent bounds which are tight. Assuming
adversarial rewards, we establish a lower bound $O(T^{\frac{2}{3}})$ for
connected graphs, thereby bridging the gap between the lower and upper bound in
the prior work. We also show a linear regret lower bound when the graph is
disconnected. While previous works have explored these settings with upper
bounds, we provide a thorough study on tight lower bounds.