On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
Not on the map. Why?
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.
Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 8 of its 45 references that are in the map. First posted on arXiv 29 Aug 2024.
Builds on
8 of 45 references.
References · 8
- 2020Batch Policy Learning in Average Reward Markov Decision Processescited by 69
- 2020Learning and Planning in Average-Reward Markov Decision Processescited by 54
- 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
- 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
- 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 23
- 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
- 2022Toward Discovering Options that Achieve Faster Planningcited by 3
- 2023A Note on Stability in Asynchronous Stochastic Approximation without Communication Delayscited by 1
Built on by
Citing papers per year: 2024: 1; 2025: 2; 2026: 3.
6 papers.
- 2024Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learningcited by 2
- 2025Planning and Learning in Average Risk-aware MDPscited by 2
- 2025Average-reward reinforcement learning in semi-Markov decision processes via relative value iterationcited by 1
- 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 1
- 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
- 2026Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approachcited by 0
- 2026Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach7 Oct 2026
- 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process15 Jun 2026
- 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning20 Jan 2026
- 2025Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration5 Dec 2025
- 2025Planning and Learning in Average Risk-aware MDPs22 Mar 2025
- 2024Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning5 Sep 2024