Federated Best Arm Identification with Heterogeneous Clients
- URL: http://arxiv.org/abs/2210.07780v3
- Date: Tue, 19 Dec 2023 09:31:06 GMT
- Title: Federated Best Arm Identification with Heterogeneous Clients
- Authors: Zhirui Chen, P. N. Karthik, Vincent Y. F. Tan, and Yeow Meng Chee
- Abstract summary: We study best arm identification in a federated multi-armed bandit setting with a central server and multiple clients.
We show that for any algorithm whose upper bound on the expected stopping time matches with the lower bound up to a multiplicative constant (em almost-optimal algorithm)
We propose a novel algorithm that communicates at exponential time instants, and demonstrate that it is almost-optimal.
- Score: 62.36929749450298
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study best arm identification in a federated multi-armed bandit setting
with a central server and multiple clients, when each client has access to a
{\em subset} of arms and each arm yields independent Gaussian observations. The
goal is to identify the best arm of each client subject to an upper bound on
the error probability; here, the best arm is one that has the largest {\em
average} value of the means averaged across all clients having access to the
arm. Our interest is in the asymptotics as the error probability vanishes. We
provide an asymptotic lower bound on the growth rate of the expected stopping
time of any algorithm. Furthermore, we show that for any algorithm whose upper
bound on the expected stopping time matches with the lower bound up to a
multiplicative constant ({\em almost-optimal} algorithm), the ratio of any two
consecutive communication time instants must be {\em bounded}, a result that is
of independent interest. We thereby infer that an algorithm can communicate no
more sparsely than at exponential time instants in order to be almost-optimal.
For the class of almost-optimal algorithms, we present the first-of-its-kind
asymptotic lower bound on the expected number of {\em communication rounds}
until stoppage. We propose a novel algorithm that communicates at exponential
time instants, and demonstrate that it is asymptotically almost-optimal.
Related papers
- Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem [10.994427113326996]
An instance of this problem has $k$ arms, each of whose reward function is a concave and increasing function of the number of times that arm has been pulled so far.
We show that for any randomized online algorithm, there exists an instance on which it must suffer at least an $Omega(sqrtk)$ approximation factor relative to the optimal reward.
We then show how to remove this assumption at the cost of an extra $O(sqrtk log k)$ approximation factor, achieving an overall $O(sqrtk
arXiv Detail & Related papers (2024-04-01T15:55:45Z) - Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
We study best arm identification in a restless multi-armed bandit setting with finitely many arms.
The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite state space.
It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds.
arXiv Detail & Related papers (2023-10-20T10:04:05Z) - Best arm identification in rare events [0.43012765978447565]
A key application of this framework is in online advertising where click rates of advertisements could be a fraction of a single percent and final conversion to sales, while highly profitable, may again be a small fraction of the click rates.
Lately, algorithms for BAI problems have been developed that minimise sample complexity while providing statistical guarantees on the correct arm selection.
We exploit the fact that the reward process for each arm is well approximated by a Compound Poisson process to arrive at algorithms that are faster, with a small increase in sample complexity.
arXiv Detail & Related papers (2023-03-14T04:51:24Z) - Beyond the Best: Estimating Distribution Functionals in Infinite-Armed
Bandits [40.71199236098642]
In the infinite-armed bandit problem, each arm's average reward is sampled from an unknown distribution.
We consider a general class of distribution functionals beyond the maximum, and propose unified meta algorithms for both the offline and online settings.
arXiv Detail & Related papers (2022-11-01T18:20:10Z) - Almost Cost-Free Communication in Federated Best Arm Identification [76.12303738941254]
We study the problem of best arm identification in a federated learning multi-armed bandit setup with a central server and multiple clients.
We propose a novel algorithm sc FedElim that is based on successive elimination and communicates only in exponential time steps.
arXiv Detail & Related papers (2022-08-19T08:37:09Z) - Globally Optimal Algorithms for Fixed-Budget Best Arm Identification [16.500749121196986]
We characterize the optimal rate as a result of global optimization over all possible parameters.
We show that this rate is indeed achievable by introducing a conceptual algorithm called delayed optimal tracking (DOT)
arXiv Detail & Related papers (2022-06-09T17:42:19Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
This paper considers the problem of online clustering with bandit feedback.
It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines.
We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
arXiv Detail & Related papers (2022-02-09T06:05:05Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits.
Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
arXiv Detail & Related papers (2021-11-14T21:49:58Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
We devise a simple algorithm whose sampling complexity matches known instance-specific lower bounds.
Unlike existing best-arm identification strategies, our algorithm uses a stopping rule that does not depend on the number of arms.
arXiv Detail & Related papers (2020-06-29T14:25:51Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.