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.

在多臂赌博机领域，多智能体多臂赌博机方法已经受到了广泛关注，但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界，并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时，我们证明了实例相关上界的 O（log T）下界和平均差值独立上界的 sqrt（T）下界。在对抗奖励的假设下，我们建立了连接图的 O（T^（2/3））下界，从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时，我们还展示了线性的遗憾下界。与以前的研究相比，本文全面研究了这些情景下的紧密下界。