论文标题
联合最佳手臂标识中几乎没有成本的沟通
Almost Cost-Free Communication in Federated Best Arm Identification
论文作者
论文摘要
我们研究了与中央服务器和多个客户的联合学习多臂强盗设置中最佳手臂识别的问题。每个客户都与多臂强盗相关联，其中每个手臂在具有未知均值和已知方差的高斯分布之后，每个手臂都会产生{\ em I.i.d。} \奖励。假定所有客户的武器集相同。我们定义了两个最佳手臂的概念 - 本地和全球。客户的当地最好的手臂是客户本地手臂中最大的手臂，而全球最佳手臂是所有客户平均平均值最大的手臂。我们假设每个客户只能从当地的手臂上观察奖励，从而估计其当地最好的手臂。客户与上行链路上的中央服务器进行通信，该上行链路需要每个上行链路的使用费用为$ c \ ge0 $单位。在服务器上估算了全球最佳手臂。目的是确定当地最佳武器和全球最佳臂，总成本最少，定义为所有客户端的ARM选择总数和总通信成本的总和，但在错误概率上取决于上限。我们提出了一种基于连续消除的新颖算法{\ sc fedelim}，仅在指数时间步骤中进行通信，并获得高概率依赖性实例依赖性上限。我们论文的关键要点是，对于任何$ c \ geq 0 $，错误概率和错误概率足够小，{\ sc fedelim}下的ARM选择总数（分别为\ the总费用）最多是〜$ 2 $（分别〜$ 3 $）（分别是〜$ 3 $）在其在每个时间时间步长的变体下，ARM选择的最大总数倍。此外，我们表明后者在期望最高的恒定因素方面是最佳的，从而证明{\ sc fedelim}中的通信几乎是不含成本的。我们从数值验证{\ sc fedelim}的功效。
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}.
