# Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration

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

## Key facts

- Cited by 1 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 5 of its 35 references that are in the map.
- First posted on arXiv 5 Dec 2025.

## 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, 5 of 5)

- [Learning and Planning in Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2006.16318/) (2020)
- [On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes](https://mlsanity.com/paper/2408.16262/) (2024)
- [Average-Reward Learning and Planning with Options](https://mlsanity.com/paper/2110.13855/) (2021)
- [Continuity of Cost in Borkar Control Topology and Implications on Discrete Space and Time Approximations for Controlled Diffusions under Several Criteria](https://mlsanity.com/paper/2209.14982/) (2022)
- [Asynchronous Stochastic Approximation with Applications to Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2409.03915/) (2024)

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

- [Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach](https://mlsanity.com/paper/2610.10326/) (2026)

## Abstract (arXiv)

This paper applies the authors' recent results on asynchronous stochastic approximation (SA) in the Borkar-Meyn framework to reinforcement learning in average-reward semi-Markov decision processes (SMDPs). We establish the convergence of an asynchronous SA analogue of Schweitzer's classical relative value iteration algorithm, RVI Q-learning, for finite-space, weakly communicating SMDPs. In particular, we show that the algorithm converges almost surely to a compact, connected subset of solutions to the average-reward optimality equation, with convergence to a unique, sample path-dependent solution under additional stepsize and asynchrony conditions. Moreover, to make full use of the SA framework, we introduce new monotonicity conditions for estimating the optimal reward rate in RVI Q-learning. These conditions substantially expand the previously considered algorithmic framework and are addressed through novel arguments in the stability and convergence analysis of RVI Q-learning.