🤖 machine learning

On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments

This paper investigates synchronous federated Q-learning in heterogeneous environments, revealing that while increasing the number of agents ( $K$ ) yields linear speed-up, performing multiple local iterations ( $E>1$ ) fundamentally degrades convergence to a rate of $\Theta(E/T)$ and induces a two-phase error dynamic that can be optimized through phase-dependent stepsize selection.

Original authors: Leo Muxing Wang, Pengkun Yang, Lili Su

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Leo Muxing Wang, Pengkun Yang, Lili Su

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a team of 20 explorers (agents) trying to solve a giant, complex maze together. Their goal is to find the fastest route to the exit (the optimal policy). However, there's a catch: each explorer is in a slightly different version of the maze. One has slippery floors, another has moving walls, and a third has different lighting. They can't see each other's mazes, but they can send text messages to a central Command Center (the server) to share what they've learned.

This paper studies how well this team learns when they use a specific strategy called Federated Q-Learning.

Here is the breakdown of their findings, explained simply:

1. The Strategy: "Work Alone, Then Share"

The explorers don't talk to each other every single second. Instead, they work on their own mazes for a while, make a bunch of guesses about the best path, and then stop to compare notes with the Command Center.

$E$ (The Sync Period): This is the number of steps they take alone before stopping to share.
- If $E=1$ , they share after every single step.
- If $E=10$ , they work for 10 steps, then share.
- If $E=100$ , they work for 100 steps, then share.

The idea is that sharing less often ( $E > 1$ ) saves time and communication bandwidth, so the team should learn faster overall.

2. The Good News: When Everyone is Similar

If all the explorers were in identical mazes (homogeneous environments), the paper confirms that working alone for a bit before sharing is great.

The Result: The team learns faster the more explorers they have. It's like having 20 people solve a puzzle; if they all share their pieces, they finish 20 times faster than one person.
The Catch: This only works perfectly if the mazes are exactly the same.

3. The Bad News: When Mazes are Different (Heterogeneity)

In the real world, mazes are different. This is called heterogeneity. The paper discovered a surprising "tipping point."

The Threshold: There is a specific limit to how long the explorers can work alone before sharing.
Below the Limit: If they share frequently enough (small $E$ ), the team still learns fast, and the "different maze" problem doesn't hurt them much.
Above the Limit: If they wait too long to share (large $E$ $E$ ), the different mazes cause confusion. The explorers start pulling the team in different directions.
- The Analogy: Imagine a group of people trying to steer a boat. If they all paddle in slightly different directions because they are looking at different maps, and they don't talk to each other often enough to correct course, the boat spins in circles.
- The Result: The more they wait to share ( $E$ increases), the slower they get. In fact, waiting too long makes the whole process worse than if they had just shared every single step.

4. The "Two-Phase" Surprise

The paper found something weird happens when the mazes are different and they wait too long to share. The learning curve looks like a rollercoaster:

Phase 1 (The Drop): At the start, the error (mistakes) drops very fast. The team seems to be learning great!
Phase 2 (The Bounce): Suddenly, the error stops dropping and actually bounces back up before settling at a higher level of mistakes.

Why? The initial drop is just them getting familiar with the basics. The bounce happens because their "local" guesses (based on their unique, weird mazes) start conflicting with the "global" truth. They get stuck in a loop of correcting each other's bad habits.

5. The Fundamental Limit

The authors proved that this slowdown isn't just a mistake in their math; it's a fundamental law of this specific setup.

If the mazes are different and the team waits to share ( $E > 1$ ), there is a hard limit on how fast they can learn.
The Takeaway: You cannot simply "work harder" (do more local steps) to overcome the confusion caused by different environments. In fact, doing more local work often just wastes more time and samples.

6. A Practical Trick

Since they know the error drops fast at first and then bounces, they suggest a two-phase strategy:

Phase 1: Use a "bold" learning rate (take big steps) to get the initial drop quickly.
Phase 2: Once the error starts to bounce, switch to a "cautious" learning rate (tiny steps) to stabilize and finish the job.
Result: This two-step approach helps the team reach the finish line faster than using the same strategy the whole time.

Summary

Homogeneous (Same Mazes): Working alone for a bit before sharing is efficient and speeds things up.
Heterogeneous (Different Mazes): Working alone for too long causes confusion. The team learns slower, and the error bounces up.
The Lesson: If your team members are operating in very different environments, you need to talk to each other very frequently. Waiting too long to sync up actually hurts performance, and there is a hard limit on how fast you can learn under these conditions.

Technical Summary: On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments

Problem Statement

Large-scale multi-agent systems, such as those in autonomous driving or industrial automation, often operate across wide geographic areas where agents interact with heterogeneous environments. While Federated Reinforcement Learning (FRL) offers a framework for collaborative training without sharing raw data, the impact of environmental heterogeneity on the convergence of classic algorithms like Q-learning remains under-explored.

Existing literature has established that in homogeneous environments (where all agents share the same transition dynamics), federated Q-learning can achieve linear speedup with respect to the number of agents ( $K$ ). However, in heterogeneous settings, agents encounter distinct transition probabilities ( $P_k$ ), leading to misaligned learning signals. The central problem addressed in this paper is characterizing the convergence rates of synchronous Federated Q-learning (FQL) when agents perform $E$ local updates before synchronizing their Q-estimates, specifically under the condition of environmental heterogeneity.

Methodology

The authors analyze a synchronous FQL algorithm where $K$ agents independently collect samples from their local Markov Decision Processes (MDPs) $\mathcal{M}_k = \langle \mathcal{S}, \mathcal{A}, \mathcal{P}_k, \gamma, R \rangle$ . The agents perform local Q-learning updates for $E$ iterations and then average their Q-estimates via a parameter server.

Key technical components include:

Error Decomposition: The authors define the error $\Delta_t = Q^* - \bar{Q}_t$ $Δ_{t} = Q^{*} - \overset{ˉ}{Q}_{t}$ , where $Q^*$ $Q^{*}$ is the optimal Q-function of the global MDP (defined by the average transition kernel $\bar{P}$ $\overset{ˉ}{P}$ ) and $\bar{Q}_t$ $\overset{ˉ}{Q}_{t}$ is the averaged local estimate. They derive a recursive error iteration formula (Lemma 1) that separates the error into three components:
- Initial error decay.
- Sampling noise (deviation between sampled and true transitions).
- Heterogeneity-induced perturbation (deviation between local transitions $P_k$ and the global average $\bar{P}$ ).
Heterogeneity Metric: The degree of heterogeneity is quantified by $\kappa = \sup_{k,s,a} \|\bar{P}(\cdot|s,a) - P_k(\cdot|s,a)\|_\infty$ .
Lower Bound Construction: To prove fundamental limitations, the authors construct a specific counter-example with two states and binary actions where the transition kernels alternate between identity and permutation matrices. This setup isolates the effect of $E > 1$ in heterogeneous environments.

Key Contributions

1. Characterization of Error Evolution and Sample Complexity

The paper provides a tight characterization of the error evolution, showing that the convergence behavior depends critically on the product $K(E-1)$ relative to a threshold determined by heterogeneity $\kappa$ and the target accuracy $\epsilon$ .

Regime 1 (Linear Speedup): When $K(E-1)$ is below a threshold of $\tilde{\mathcal{O}}((\kappa\epsilon)^{-1}(1-\gamma)^{-2})$ , the system behaves similarly to the homogeneous setting. The sample complexity is $\tilde{\mathcal{O}}\left(\frac{|\mathcal{S}||\mathcal{A}|}{K(1-\gamma)^5\epsilon^2}\right)$ , exhibiting a linear speedup with respect to the number of agents $K$ .
Regime 2 (Performance Degradation): When $K(E-1)$ exceeds the threshold, heterogeneity dominates. The sample complexity degrades to $\tilde{\mathcal{O}}\left(\frac{\kappa|\mathcal{S}||\mathcal{A}|E}{(1-\gamma)^3\epsilon}\right)$ . In this regime, increasing the number of local updates $E$ linearly increases the sample complexity, negating the benefits of parallelism.

2. Fundamental Limitation of Local Updates ( $E > 1$ )

The paper proves that the slowdown in convergence for $E > 1$ in heterogeneous environments is fundamental, not merely an artifact of the analysis.

Theorem 2 establishes a lower bound on the $\ell_\infty$ norm of the error: $\|\Delta_T\|_\infty \geq \Theta_R\left(\frac{E}{(1-\gamma)T}\right)$ .
This implies that for a wide range of step sizes, the error cannot decay faster than a rate proportional to $E/T$ . Consequently, performing multiple local updates ( $E > 1$ ) eventually consumes $E$ times more samples than performing a single update ( $E=1$ ) to reach the same target accuracy.

3. Two-Phase Convergence Phenomenon

Through numerical experiments, the authors identify a distinct two-phase phenomenon in heterogeneous settings with constant step sizes:

Phase 1: The error decays rapidly, driven by the reduction of initial error.
Phase 2: The error "bounces up" and stabilizes at a residual level determined by the collective perturbation from heterogeneity and local updates.
The paper suggests that a two-phase training strategy—using a larger step size in Phase 1 and a smaller (or decaying) step size in Phase 2—can mitigate this residual error and improve overall convergence compared to using a single constant step size.

Results and Experimental Validation

The theoretical findings are validated through experiments on $K=20$ agents interacting with randomly generated 5x5 maze environments with varying transition probabilities (simulating high heterogeneity, $\kappa \approx 1.2$ ).

Step Size Sensitivity: In heterogeneous environments, large constant step sizes lead to significant error bouncing and high residual errors. In contrast, homogeneous environments show no such bounce regardless of step size.
Impact of $E$ : Increasing the synchronization period $E$ in heterogeneous settings leads to higher final errors, confirming the theoretical degradation.
Two-Phase Strategy: Experiments demonstrate that switching step sizes at the estimated phase transition point ( $t_0$ ) yields faster convergence and lower final errors compared to uniform step size strategies.

Significance and Claims

The paper claims to be the first to provide a tight sample complexity analysis for federated Q-learning that explicitly accounts for environmental heterogeneity and the synchronization period $E$ .

Theoretical Gap: Unlike prior works (e.g., Zhang et al., 2024; Wang et al., 2023) which provided upper bounds that did not necessarily decay to zero or failed to characterize the fundamental impact of $E$ and $\kappa$ , this work provides bounds that decay to zero and explicitly identifies the trade-off between communication frequency and convergence speed.
Fundamental Insight: The paper challenges the intuition that "more local updates are always better" in federated settings. It demonstrates that in the presence of environmental heterogeneity, increasing $E$ can fundamentally hinder convergence, imposing a lower bound on the error rate that cannot be overcome by tuning step sizes alone.
Practical Implication: The findings suggest that for heterogeneous multi-agent systems, frequent synchronization (small $E$ ) or adaptive step-size strategies are necessary to achieve robust performance, as the "blessing of heterogeneity" observed in homogeneous settings does not extend to the convergence rates of Q-learning under these conditions.