Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning

Yuchen Jiao, Jiin Woo, Gen Li, Gauri Joshi, Yuejie ChiarXiv 2026 · arXiv

TL;DR

This paper provides significantly tighter sample complexity bounds for vanilla Q-learning in average-reward Markov Decision Processes (MDPs) under a weakly communicating assumption. It also introduces the first federated average-reward Q-learning algorithm, proving that collaboration among $M$ agents yields a linear speedup in sample efficiency while keeping the required communication rounds completely independent of the number of agents.

What Problem Does This Paper Address?

Most reinforcement learning (RL) research focuses on the discounted reward framework, where future rewards are geometrically downweighted. However, many practical, long-running applications (like robotics or network routing) are better modeled by maximizing the long-run average reward per time step over an infinite horizon.

Analyzing average-reward RL is notoriously difficult because the effective planning horizon is infinitely long, leading to massive sample requirements. Existing model-free methods for average-reward MDPs either suffer from highly suboptimal sample complexity or require complex algorithmic modifications (like variance reduction). Furthermore, many methods rely on prior knowledge of environment-specific parameters—such as the mixing time or the span norm of the bias function—which are incredibly difficult to estimate in practice.

This paper addresses these limitations by analyzing a simple, vanilla Q-learning algorithm that requires no prior parameter knowledge, extending it from a single-agent setting to a collaborative, federated learning environment.

Methods

The authors analyze a stage-wise (epoch-based) Q-learning framework. To bridge the gap between discounted and average rewards, the algorithm dynamically drives the discount factor $\gamma_k$ toward 1 across successive epochs (leveraging the concept of Blackwell optimality).

The paper introduces two distinct parameter scheduling regimes for the learning rates and discount factors that eliminate the need for prior knowledge of the environment's mixing time or span norm:

  1. An exponentially decaying regime for the discount factor mismatch.
  2. A polynomially decaying ($1/k$) regime.

They then scale this approach into Federated Average-Reward Q-Learning. In this decentralized setup, $M$ agents independently update their local Q-functions using synchronous sampling from a generative model. Periodically, the agents send their local estimates to a central server, which aggregates them by simply averaging the Q-values before synchronizing them back to the agents.

Datasets

Not discussed in the paper. This work is purely theoretical and focuses on proving mathematical upper bounds for sample and communication complexity.

Key Insights and Ideas

  • The Power of Parameter Scheduling: The paper demonstrates that you don't always need sophisticated algorithmic overhead, like Upper Confidence Bounds (UCB) or variance reduction, to drastically improve Q-learning efficiency. Simply orchestrating the right dynamic schedules for the learning rate and discount factor can yield massive theoretical upgrades.
  • Communication Scalability ("Free Lunch"): In the federated setting, adding more agents accelerates the per-agent sample efficiency linearly ($\frac{1}{M}$). Crucially, the total number of communication rounds required to reach an $\varepsilon$-optimal value remains entirely independent of $M$. This means you can scale up the number of collaborating agents to slash sample collection times without incurring any additional communication overhead.

Key Results

  • Single-Agent Bound: For estimating the optimal value, the proposed algorithm achieves a sample complexity of $\widetilde{O}\left(\frac{|S||A|\|h^\star\|_{\text{sp}}^3}{\varepsilon^3}\right)$, where $\|h^\star\|_{\text{sp}}$ is the span norm of the bias function. This improves upon previous vanilla Q-learning benchmarks by a factor of at least $\frac{\|h^\star\|_{\text{sp}}^2}{\varepsilon^2}$.
  • Federated Bound & Speedup: With $M$ agents, the per-agent sample complexity drops linearly to $\widetilde{O}\left(\frac{|S||A|\|h^\star\|_{\text{sp}}^3}{M\varepsilon^3}\right)$, requiring only $\widetilde{O}\left(\frac{\|h^\star\|_{\text{sp}}}{\varepsilon}\right)$ communication rounds.
  • Policy Learning: For learning an $\varepsilon$-optimal policy (rather than just estimating the value), the federated algorithm achieves a sample complexity of $\widetilde{O}\left(\frac{|S||A|\|h^\star\|_{\text{sp}}^5}{M\varepsilon^5}\right)$.

A comprehensive breakdown of how these results compare to prior model-free average-reward literature is detailed in the table below:

Comparison of algorithms for average-reward MDPs

Limitations and Future Work

  • Suboptimality vs. Minimax Lower Bounds: Because the authors intentionally analyze vanilla Q-learning for its simplicity and practical popularity, the sample complexity bounds still fall short of the theoretical minimax optimal rates achieved by more complex, variance-reduced model-based methods.
  • Generative Model Dependency: The analysis assumes a synchronous generative model (where agents can query any state-action pair at will). Testing these algorithms under more realistic, asynchronous, online Markovian trajectories remains an open challenge.
  • Future Extensions: A natural next step is incorporating variance reduction techniques or UCB exploration into this federated average-reward framework to push the bounds all the way to minimax optimality.

Summary updated

Abstract

Average-reward reinforcement learning offers a principled framework for long-term decision-making by maximizing the mean reward per time step. Although Q-learning is a widely used model-free algorithm with established sample complexity in discounted and finite-horizon Markov decision processes (MDPs), its theoretical guarantees for average-reward settings remain limited. This work studies a simple but effective Q-learning algorithm for average-reward MDPs with finite state and action spaces under the weakly communicating assumption, covering both single-agent and federated scenarios. For the single-agent case, we show that Q-learning with carefully chosen parameters achieves sample complexity $\widetilde{O}\left(\frac{|\mathcal{S}||\mathcal{A}|\|h^{\star}\|_{\mathsf{sp}}^3}{\varepsilon^3}\right)$, where $\|h^{\star}\|_{\mathsf{sp}}$ is the span norm of the bias function, improving previous results by at least a factor of $\frac{\|h^{\star}\|_{\mathsf{sp}}^2}{\varepsilon^2}$. In the federated setting with $M$ agents, we prove that collaboration reduces the per-agent sample complexity to $\widetilde{O}\left(\frac{|\mathcal{S}||\mathcal{A}|\|h^{\star}\|_{\mathsf{sp}}^3}{M\varepsilon^3}\right)$, with only $\widetilde{O}\left(\frac{\|h^{\star}\|_{\mathsf{sp}}}{\varepsilon}\right)$ communication rounds required. These results establish the first federated Q-learning algorithm for average-reward MDPs, with provable efficiency in both sample and communication complexity.
BibTeX
@misc{jiao2026sample,
  author = {Yuchen Jiao and Jiin Woo and Gen Li and Gauri Joshi and Yuejie Chi},
  title = {{Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning}},
  year = {2026},
  eprint = {2601.13642},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.13642},
}
Figure