mlsanityData to 14 Oct 2026

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

arXiv 2601.13642 ↗First posted 20 Jan 2026stat.ML cs.LGcited by 3

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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 widetildeOleft(frac|S||A||hstar|_mathsfsp3varepsilon3right), where |hstar|_mathsfsp is the span norm of the bias function, improving previous results by at least a factor of frac|hstar|_mathsfsp2varepsilon2. In the federated setting with M agents, we prove that collaboration reduces the per-agent sample complexity to widetildeOleft(frac|S||A||hstar|_mathsfsp3Mvarepsilon3right), with only widetildeOleft(frac|hstar|_mathsfspvarepsilonright) 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.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 38 of its 49 references that are in the map. First posted on arXiv 20 Jan 2026.

Builds on

38 of 49 references.

Closest ancestors · 5

Same direction, newest first

  1. 2025From Set Convergence to Pointwise Convergence: Finite-Time Guarantees for Average-Reward Q-Learning with Adaptive Stepsizes25 Apr
  2. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes29 Aug
  3. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach26 Jul
  4. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learning19 Mar
  5. 2024On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes11 Mar

Other references · 33

  1. 2019Advances and Open Problems in Federated Learningcited by 3,046
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  5. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  6. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  7. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  8. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  9. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  10. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  11. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  12. 2020Learning and Planning in Average-Reward Markov Decision Processescited by 54
21 more
  1. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
  2. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  3. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  4. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 36
  5. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  6. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  7. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  8. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 31
  9. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  10. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  11. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 26
  12. 2023Federated Q-Learning: Linear Regret Speedup with Low Communication Costcited by 19
  13. 2024Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPscited by 17
  14. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  15. 2025Near-Optimal Sample Complexity for MDPs via Anchoringcited by 14
  16. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 13
  17. 2023Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learningcited by 11
  18. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  19. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 9
  20. 2024The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysiscited by 9
  21. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductionscited by 2
  2. 2026Fast Rates for Offline Q-Learning with KL Regularizationcited by 0
  3. 2026Average-Reward Policy Identification from a Single Continuing Trajectorycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Achieving varepsilon-2 Dependence for Average-Reward Q-Learning with a New Contraction Principle
  2. 2025Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
  3. 2026Non-asymptotic Convergence of Average-reward Q-learning with Options
  4. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  5. 2024Learning the Model While Learning Q: Finite-Time Sample Complexity of Online SyncMBQ
  6. 2026Optimal Multi-Reward Reinforcement Learning
  7. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  8. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning