We study the problem of best arm identification in a federated learning
multi-armed bandit setup with a central server and multiple clients. Each
client is associated with a multi-armed bandit in which each arm yields {\em
i.i.d.}\ rewards following a Gaussian distribution with an unknown mean and
known variance. The set of arms is assumed to be the same at all the clients.
We define two notions of best arm -- local and global. The local best arm at a
client is the arm with the largest mean among the arms local to the client,
whereas the global best arm is the arm with the largest average mean across all
the clients. We assume that each client can only observe the rewards from its
local arms and thereby estimate its local best arm. The clients communicate
with a central server on uplinks that entail a cost of $C\ge0$ units per usage
per uplink. The global best arm is estimated at the server. The goal is to
identify the local best arms and the global best arm with minimal total cost,
defined as the sum of the total number of arm selections at all the clients and
the total communication cost, subject to an upper bound on the error
probability. We propose a novel algorithm {\sc FedElim} that is based on
successive elimination and communicates only in exponential time steps and
obtain a high probability instance-dependent upper bound on its total cost. The
key takeaway from our paper is that for any $C\geq 0$ and error probabilities
sufficiently small, the total number of arm selections (resp.\ the total cost)
under {\sc FedElim} is at most~$2$ (resp.~$3$) times the maximum total number
of arm selections under its variant that communicates in every time step.
Additionally, we show that the latter is optimal in expectation up to a
constant factor, thereby demonstrating that communication is almost cost-free
in {\sc FedElim}. We numerically validate the efficacy of {\sc FedElim}.

本研究基于联邦学习多臂赌博机模型，在中心服务器和多个客户端之间定义了本地和全局最佳臂的概念，并提出了一种名为 FedElim 的新算法，以最小化总成本，其中总成本是所有客户处进行的臂数的总数和通信成本的总和，同时满足误差概率的上限约束。