Client Selection for Federated Policy Optimization with Environment Heterogeneity

Zhijie Xie, Shenghui Song

Abstract

The development of Policy Iteration (PI) has inspired many recent algorithms for Reinforcement Learning (RL), including several policy gradient methods that gained both theoretical soundness and empirical success on a variety of tasks. The theory of PI is rich in the context of centralized learning, but its study under the federated setting is still in the infant stage. This paper investigates the federated version of Approximate PI (API) and derives its error bound, taking into account the approximation error introduced by environment heterogeneity. We theoretically prove that a proper client selection scheme can reduce this error bound. Based on the theoretical result, we propose a client selection algorithm to alleviate the additional approximation error caused by environment heterogeneity. Experiment results show that the proposed algorithm outperforms other biased and unbiased client selection methods on the federated mountain car problem and the Mujoco Hopper problem by effectively selecting clients with a lower level of heterogeneity from the population distribution.

Introduction

Federated Reinforcement Learning (FRL) enables multiple agents, such as autonomous vehicles or robotic systems, to collaboratively learn a shared policy without centralizing raw trajectory data. While Federated Learning (FL) has matured in supervised contexts, FRL faces unique challenges, most notably environment heterogeneity. In these scenarios, clients operate under varying physical dynamics—such as different friction coefficients for tires or varying limb lengths for robots. Standard FRL methods often struggle to aggregate these diverse experiences, as the resulting "average" policy may fail to perform adequately in any specific environment.

This paper addresses the theoretical gap in Federated Policy Iteration (PI) by deriving error bounds under environmental mismatch and proposing a novel client selection mechanism, FedPOHCS, to mitigate these effects.

Theoretical Framework: Federated Approximate Policy Iteration

The authors focus their analysis on Federated Approximate Policy Iteration (FAPI). To analyze the convergence properties in a heterogeneous setting, they introduce the concept of an "Imaginary MDP." This theoretical construct represents a weighted average of the transition dynamics across all participating clients.

A key contribution of this work is the formal derivation of an error bound for FAPI. The analysis demonstrates that the global policy's error is directly influenced by the "heterogeneity gap"—the distance between individual client dynamics and the Imaginary MDP. Specifically, the researchers prove that the approximation error introduced during aggregation can be minimized by selecting clients that represent the "median" of the population distribution, rather than extreme outliers.

The FedPOHCS Algorithm

Building on these theoretical insights, the authors propose FedPOHCS (Federated Policy Optimization with Heterogeneity-aware Client Selection). The algorithm aims to select a subset of clients in each round that maximizes learning progress while minimizing the destabilizing effects of environmental mismatch.

The selection process utilizes a metric, $\Delta_n$, calculated for each client $n$. This metric incorporates two primary components:

  1. State Visitation Frequency: A measure of which parts of the state space the client has explored.
  2. Advantage Function: A measure of the relative benefit of specific actions compared to the current policy's average performance.

By evaluating the Frobenius norm of these matrices, the server identifies clients that possess high "learning potential" (significant unexplored advantages) but remain sufficiently aligned with the global average dynamics to ensure stable aggregation. This approach avoids the pitfalls of selecting clients solely based on high loss, which often identifies extreme outliers that can lead to divergence.

Experimental Evaluation

The performance of FedPOHCS was evaluated across three diverse environments:

  • Mountain Car (Continuous): A setup involving 60 clients where engine power varies across cars, simulating shifts in input action dynamics.
  • Mujoco Hopper: A robotic simulation with 60 clients where each "hopper" has different leg dimensions, altering the fundamental balance and movement physics.
  • HongKongOSMs: A high-fidelity autonomous vehicle simulation using SUMO. This environment features 10 distinct traffic networks based on real-world OpenStreetMap data from Hong Kong (e.g., Central, Mong Kok), characterized by varying lane configurations and traffic densities.

Key Results and Insights

The experimental results confirm the theoretical advantages of FedPOHCS:

  • Accelerated Convergence: In the Mujoco Hopper task, FedPOHCS reached a target reward of 1450 in only 20 rounds, a 4x improvement over the Power-of-Choice baseline, which required 80 rounds.
  • Enhanced Stability: In the Mountain Car environment, FedPOHCS exhibited significantly lower variance and more consistent learning curves compared to standard FedAvg or GradientNorm selection methods.
  • Robustness in Complex Scenarios: The HongKongOSMs simulation demonstrated that FedPOHCS effectively manages high-variance transition probabilities in complex urban layouts, outperforming all baseline methods in total reward.

The study also highlights a fundamental Linearity Trade-off: while complex non-linear neural networks provide better local fits for individual clients, they tend to increase aggregation error when weights are averaged at the server.

Limitations and Future Directions

Despite its success, FedPOHCS introduces certain challenges. The algorithm currently requires a two-phase communication process to calculate selection metrics before training, though a "one-phase" variant was tested with minor early-stage stability trade-offs. Additionally, the requirement for clients to share state visitation and advantage matrices raises potential privacy concerns, which might necessitate the integration of Homomorphic Encryption. Finally, the current reliance on estimating transition probabilities may require further approximation to scale to extremely high-dimensional state spaces.

Conclusion

This research provides a rigorous theoretical foundation for Federated Policy Iteration in heterogeneous environments. By prioritizing clients based on a balance of learning potential and environmental alignment, FedPOHCS offers a robust solution for practical FRL applications in robotics and autonomous systems.

Summary updated

Abstract

The development of Policy Iteration (PI) has inspired many recent algorithms for Reinforcement Learning (RL), including several policy gradient methods that gained both theoretical soundness and empirical success on a variety of tasks. The theory of PI is rich in the context of centralized learning, but its study under the federated setting is still in the infant stage. This paper investigates the federated version of Approximate PI (API) and derives its error bound, taking into account the approximation error introduced by environment heterogeneity. We theoretically prove that a proper client selection scheme can reduce this error bound. Based on the theoretical result, we propose a client selection algorithm to alleviate the additional approximation error caused by environment heterogeneity. Experiment results show that the proposed algorithm outperforms other biased and unbiased client selection methods on the federated mountain car problem and the Mujoco Hopper problem by effectively selecting clients with a lower level of heterogeneity from the population distribution.
BibTeX
@misc{xie2023client,
  author = {Zhijie Xie and Shenghui Song},
  title = {{Client Selection for Federated Policy Optimization with Environment Heterogeneity}},
  year = {2023},
  eprint = {2305.10978},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.10978},
}
Figure