Federated X-armed Bandit

Wenjie Li, Qifan Song, Jean Honorio, Guang LinAAAI 2024 · DOI

Introduction

In many real-world applications, such as determining optimal medical dosages or tuning hyper-parameters for mobile apps, we face the challenge of optimizing a complex function across multiple distributed clients. This paper introduces the first framework for the Federated $\mathcal{X}$-armed Bandit problem. Unlike traditional multi-armed bandits that deal with a finite set of choices, this framework addresses optimization over continuous or infinite search spaces $\mathcal{X}$.

Federated optimization of medicine dosages across multiple hospitals without sharing raw data.

The primary hurdles in this setting are heterogeneity—where local optima differ from the global optimum—and privacy constraints, which prevent clients from sharing raw reward data. Communication efficiency is also critical, as constant interaction with a central server is often impractical.

The Fed-PNE Algorithm

To address these challenges, the authors propose Fed-PNE (Federated Phased-Node-Elimination). The algorithm leverages several key techniques:

  • Hierarchical Partitioning: The continuous search space is represented as a tree structure, which is recursively refined into smaller regions.
  • Phased Elimination: The server coordinates sampling across clients in distinct phases. After each phase, sub-optimal regions of the search space are "pruned" based on aggregated statistical summaries.
  • Privacy-Preserving Communication: Clients only transmit empirical averages of rewards, never raw data. This protocol ensures that communication costs remain logarithmic relative to the time horizon.
  • Smoothness Exploitation: By assuming "weak smoothness" of the reward function, the algorithm maintains robust confidence bounds, preventing the premature discard of regions containing the global optimum.

Experimental Evaluation

The researchers validated Fed-PNE using synthetic benchmarks (Garland and DoubleSine functions) and real-world tasks, including landmine detection hyper-parameter tuning and COVID-19 vaccine dosage optimization.

Cumulative regret comparison on the Garland synthetic function.

The results demonstrate that Fed-PNE consistently outperforms centralized baselines like HCT and standard federated multi-armed bandit algorithms like Fed-UCB. Specifically, the algorithm achieves a near-optimal expected cumulative regret of $\tilde{O}(M^{-\frac{1}{d+2}} T^{\frac{d+1}{d+2}})$, where $M$ is the number of clients and $d$ is the near-optimality dimension.

Key Insights and Future Directions

A major takeaway is the "Power of Federation": by collaborating, clients achieve lower average regret than they would individually. Furthermore, the algorithm scales effectively; as the number of participating clients increases, the individual regret per client decreases.

While Fed-PNE is a significant step forward, it currently requires prior knowledge of the objective function's smoothness parameters. Future research could focus on adaptive partitioning strategies and methods to estimate these parameters online, further enhancing the framework's applicability to black-box optimization problems.

Summary updated

BibTeX
@inproceedings{li2024federated,
  author = {Wenjie Li and Qifan Song and Jean Honorio and Guang Lin},
  title = {{Federated X-armed Bandit}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i12.29267},
}
Figure