Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
Abstract
We study learning optimal policies in average-reward multichain Markov decision processes (MDPs), where the optimal gain may depend on the initial state and recurrence structures vary across policies, creating challenges for reinforcement learning (RL) methods. We propose an asynchronous value-iteration-based RL algorithm that requires no model knowledge beyond the MDP's transition graph and leverages Bather's decomposition to hierarchically partition the state space into communicating subsystems and transient states. This decomposition induces a recasting of the global decision problem into structured subproblems, which our algorithm exploits. We show that the algorithm converges to the optimal gain and produces gain-optimal policies after finite time. Building on this base algorithm, we develop two further algorithms: one approximately solves the multichain average optimality equations to obtain near gain-optimal policies, and another targets near bias-optimality by approximating the optimal bias function and solving an induced average-reward multichain MDP using the base algorithm. We provide almost-sure convergence guarantees for all three algorithms and empirically compare their tradeoffs, showing that the latter two also consistently improve transient performance relative to the base algorithm. To our knowledge, these are the first essentially model-free average-reward RL algorithms for general multichain MDPs without reductions to discounted problems.
Related
- Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
- Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
- HALO: Hierarchical Evidence Selection and Reinforcement Learning for Allocating Budgeted Label Optimization from Longitudinal Clinical Records
- Safety-Certified Hierarchical Control of DC Microgrids via Continuous Deep Reinforcement Learning and Covariance-Weighted Sliding Mode Synthesis
- Contact, Power, and Balls in Play: A Three-Rate Decomposition of Batting Average and the Disappearance of the .400 Hitter
BibTeX
@misc{yu2026averagereward,
title = {{Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach}},
author = {Huizhen Yu and Isaiah Heidt},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10326},
eprint = {2610.10326},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10326},
}
RIS
TY - UNPB
TI - Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
AU - Huizhen Yu
AU - Isaiah Heidt
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10326
UR - https://arxiv.org/abs/2610.10326
AB - We study learning optimal policies in average-reward multichain Markov decision processes (MDPs), where the optimal gain may depend on the initial state and recurrence structures vary across policies, creating challenges for reinforcement learning (RL) methods. We propose an asynchronous value-iteration-based RL algorithm that requires no model knowledge beyond the MDP's transition graph and leverages Bather's decomposition to hierarchically partition the state space into communicating subsystems and transient states. This decomposition induces a recasting of the global decision problem into structured subproblems, which our algorithm exploits. We show that the algorithm converges to the optimal gain and produces gain-optimal policies after finite time. Building on this base algorithm, we develop two further algorithms: one approximately solves the multichain average optimality equations to obtain near gain-optimal policies, and another targets near bias-optimality by approximating the optimal bias function and solving an induced average-reward multichain MDP using the base algorithm. We provide almost-sure convergence guarantees for all three algorithms and empirically compare their tradeoffs, showing that the latter two also consistently improve transient performance relative to the base algorithm. To our knowledge, these are the first essentially model-free average-reward RL algorithms for general multichain MDPs without reductions to discounted problems.
ER -