Federated X-Armed Bandit

Federated bandit is a newly-developed bandit problem that incorporates federated learning with sequential decision making [McMahan et al., 2017, Shi and Shen, 2021a]. Unlike the traditional bandit models where the exploration-exploitation tradeoff is the only major concern, federated bandit problem also takes account of the modern concerns of data heterogeneity and privacy protection towards trustworthy machine learning. In particular, in the federated learning paradigm, the data available to each client could be drawn from non-i.i.d distributions, making collaborations between the clients necessary to make valid inferences for the aggregated global model. However, due to user privacy concerns and the large communication cost, such collaborations across the clients must be restricted and avoid direct transmissions of the local data. To make correct decisions in the future, the clients have to utilize the limited communications from each other and coordinate exploration and exploitation correspondingly. To the best of our knowledge, existing results of federated bandits, such as Dubey and Pentland [2020], Huang et al. [2021], Shi and Shen [2021a], Shi et al. [2021b], focus on either the case where the number of arms is finite (multi-armed bandit), or the case where the expected reward is a linear function of the chosen arm (linear contextual bandit). However, for problems such as dynamic pricing [Chen and Gallego, 2022] and hyper-parameter optimization [Shang et al., 2019], the available arms are often defined on a domain X with infinite or even uncountable cardinality, and the reward function is usually non-linear with respect to the metric employed by the domain X. These problems challenge the applications of existing federated bandit algorithms to more complicated real-world problems. Two applications (Figure 1) that motivate our study of federated X -armed bandit are given below.