Abstract
In Federated Learning (FL), identifying the single best option among many—the Best Arm Identification (BAI) problem—is a critical task for decentralized decision-making. This paper introduces the first asynchronous federated algorithms for pure exploration in multi-armed and linear bandits: FAMABPE and FALinPE. By employing a novel event-triggered communication protocol, these algorithms allow agents to contribute independently without being delayed by stragglers. Our theoretical and empirical results show that these methods achieve near-optimal sample complexity while significantly reducing communication overhead compared to traditional synchronous approaches.
Introduction
Multi-Armed Bandits (MAB) provide a robust framework for decision-making under uncertainty. In the "pure exploration" setting, the objective is to identify the arm with the highest expected reward with high confidence using minimal samples. While federated settings allow multiple agents to collaborate, existing solutions often rely on synchronous communication, where a central server waits for all agents before proceeding. This approach is highly susceptible to the "straggler problem," where slow or disconnected devices bottleneck the entire system.
This research addresses these challenges by proposing asynchronous protocols that allow agents to explore and communicate on their own schedules without sacrificing statistical accuracy.
Methodology: Asynchronous Event-Triggered Communication
The core innovation lies in the asynchronous event-triggered communication protocol. Instead of communicating at fixed intervals, an agent initiates a data exchange only when it has gathered a significant amount of new information relative to the global state.
- FAMABPE (Multi-Armed Bandits): Uses a trigger based on local observation counts. If new data exceeds a specific proportion of the server's current knowledge, the agent synchronizes its local sums and global averages.
- FALinPE (Linear Bandits): Employs a hybrid trigger monitoring both observation counts and the determinant (volume) of the covariance matrix. This ensures communication only occurs when local exploration substantially improves the estimate of the underlying linear model.
Both algorithms operate in a fixed-confidence setting, guaranteeing the identification of an $\epsilon$-best arm with probability at least $1-\delta$.
Experimental Evaluation
The algorithms were evaluated using both synthetic simulations and real-world data:
- Synthetic Data: Tested across various reward gaps to verify theoretical sample complexity and communication efficiency.
- MovieLens 20M: Transformed into a federated linear bandit problem where 54 simulated agents (users) collaborated to identify the best movie category using 25-dimensional PCA features.
Key Results and Insights
Empirical results demonstrate that the asynchronous approach is both efficient and robust.
- Sample Complexity: FAMABPE matches the theoretical lower bound of $\Omega(\sum \Delta_k^{-2} \log(1/\delta))$, effectively providing an $M$-fold speedup (where $M$ is the number of agents) over single-agent exploration.
- Communication Efficiency: FALinPE significantly outperforms synchronous baselines in communication costs, particularly when the reward gap is small. The event-trigger mechanism ensures that bandwidth is preserved without compromising the quality of the identified best arm.
- Straggler Resilience: The system remains active regardless of individual agent delays, making it far more practical for real-world, unstable networks.
Conclusion and Future Work
This work provides a practical foundation for pure exploration in realistic, asynchronous federated environments. While the current focus is on fixed-confidence settings, future research could extend these principles to fixed-budget scenarios or heterogeneous environments where reward distributions vary across agents. The proposed event-triggered framework offers a scalable path forward for decentralized best-arm identification.
Summary updated