# On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes

arXiv: https://arxiv.org/abs/2408.16262 · HTML: https://mlsanity.com/paper/2408.16262/

## Key facts

- Cited by 9 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 8 of its 45 references that are in the map.
- First posted on arXiv 29 Aug 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 8 of 8)

- [Batch Policy Learning in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2007.11771/) (2020)
- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2401.07844/) (2024)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)
- [Toward Discovering Options that Achieve Faster Planning](https://mlsanity.com/paper/2205.12515/) (2022)
- [A Note on Stability in Asynchronous Stochastic Approximation without Communication Delays](https://mlsanity.com/paper/2312.15091/) (2023)

## Built on by (most cited first, 9 of 9)

- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2409.03915/) (2024)
- [Planning and Learning in Average Risk-aware MDPs](https://mlsanity.com/paper/2503.17629/) (2025)
- [Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration](https://mlsanity.com/paper/2512.06218/) (2025)
- [Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2609.28792/) (2026)
- [Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication](https://mlsanity.com/paper/2609.32727/) (2026)
- [Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach](https://mlsanity.com/paper/2610.10326/) (2026)

## Abstract (arXiv)

This paper analyzes reinforcement learning (RL) algorithms for Markov decision processes (MDPs) under the average-reward criterion. We focus on Q-learning algorithms based on relative value iteration (RVI), which are model-free stochastic analogues of the classical RVI method for average-reward MDPs. These algorithms have low per-iteration complexity, making them well-suited for large state space problems. We extend the almost-sure convergence analysis of RVI Q-learning algorithms developed by Abounadi, Bertsekas, and Borkar (2001) from unichain to weakly communicating MDPs. This extension is important both practically and theoretically: weakly communicating MDPs cover a much broader range of applications compared to unichain MDPs, and their optimality equations have a richer solution structure (with multiple degrees of freedom), introducing additional complexity in proving algorithmic convergence. We also characterize the sets to which RVI Q-learning algorithms converge, showing that they are compact, connected, potentially nonconvex, and comprised of solutions to the average-reward optimality equation, with exactly one less degree of freedom than the general solution set of this equation. Furthermore, we extend our analysis to two RVI-based hierarchical average-reward RL algorithms using the options framework, proving their almost-sure convergence and characterizing their sets of convergence under the assumption that the underlying semi-Markov decision process is weakly communicating.