Convergence, Bias, and Fairness in Federated Learning: A Non-Stationary Multi-Armed Bandit Approach for Heterogeneous Client Selection

In practical federated learning (FL) environments, clients often possess non-IID data, which can degrade model performance and extend convergence times. Effective client selection strategies have emerged as a promising approach to mitigate the challenges posed by statistical heterogeneity across clients. This paper proposes two novel non-stationary multi-armed bandit (MAB) approaches for dynamic client selection, addressing the inherent challenges of time-varying client data distributions and their impact on model performance. Unlike traditional methods that assume stationary reward distributions, our approach adapts to evolving client behaviors and data characteristics, ensuring that selection decisions reflect current relevance rather than outdated information. We evaluate client selection as a trade-off among three critical objectives: 1) Maximizing convergence rate to expedite training, 2) Minimizing solution bias to enhance model generalizability, 3) Promoting fairness to ensure consistently high performance across clients.  

Leveraging non-stationary MAB techniques, Discounted Upper Confidence Bound (D-UCB) and Sliding Window UCB (SW-UCB), we effectively balance exploration and exploitation to address client variability.  Additionally, our method evaluates the potential contributions of each client by dynamically weighting recent data trends, providing an opportunity for under-represented clients to participate. Through comprehensive experiments, we examine the trade-offs between accelerating convergence and reducing bias while maintaining fair performance distribution across clients. The proposed approach provides a robust solution to the nuanced trade-offs inherent in federated client selection.