Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach

Huizhen Yu; Isaiah Heidt

cs.LGOct 7, 2026

Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach

Authors: Huizhen Yu, Isaiah Heidt

Organizations: Department of Computing Science University of Alberta, Canada

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.

Figures & tables

Panel of Figure 1 — Figure 1 : Two sources of poor transient performance in the base algorithm. Each arrow represents a distinct action with transition probability one, and its label gives the original one-stage reward. Dashed boundaries indicate communicating subsystems.

Information flow:	Algorithm 3 (Phase 1) $\leftarrow$ Algorithm 1;
	Algorithm 3 (Phase 2) $\leftarrow$ {Algorithm 1, Algorithm 3 (Phase 1)}.

Algorithm 3 Approximate Method toward Bias-Optimal Policies (Conceptual Description)

Figure 2 : Comparison of the Phase 1 greedy policies and Phase 2 policies of Algorithm 3 . Curves show the fraction of runs producing a bias-optimal policy across five random seeds. (a) Performance after $10^{6}$ iterations for different discount factors $\beta$ . (b) Performance during learning for $\beta=0.999$ .

Panel of Figure 3 — Figure 3 : Comparison of gain optimality and transient performance across algorithms. In panel (a), the shaded region denotes one standard deviation across the 100 MDPs.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Structural parameters (controlled)
Statistic	Min	Mean	Max
Number of levels	3	4.53	6
Number of communicating classes	3	11.25	23
Number of transient states	1	9.36	20
Number of states	20	71.67	147
Number of actions	29	149.8	359

Appendix

Table 1 : Summary statistics over 100 generated MDPs.

Panel of Figure 4 — Figure 4 : Per-MDP performance across all 100 MDPs.

Explore similar work

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
Jun 15, 2026Jongmin Lee, Ernest K. Ryu, Vaneet AggarwalMarkov Decision Processes Model-Free
Seoul National University · UCLA · Purdue University
Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes
Sep 23, 2026Yue Wang, George AtiaMarkov Decision Processes Bellman Equation
Department of Electrical and Computer Engineering University of Central Florida
Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
May 19, 2026Pierre Boudart, Pierre Gaillard, Alessandro RudiMarkov Decision Processes Minimax
SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3

Jun 15, 2026, cs.LGJ/K move · Enter open · S save

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal

Seoul National University · UCLA · Purdue University

Markov Decision Processes Model-Free Learning Policy Optimal Sample Complexity Single Trajectory

Open paper AskPDF arXiv

While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model. In this work, we establish the first finite sample complexity guarantees from a single trajectory for weakly communicating average-reward MDPs. To this end, we study the dynamics of a single trajectory in weakly communicating MDPs and based on this analysis, we develop novel model-free methods. Notably, our value-based and policy-based methods provide finite sample complexity guarantees of

\widetilde{O}(1/\varepsilon^2)

and

\widetilde{O}(1/\varepsilon^4)

from a single trajectory in weakly communicating MDPs, respectively. Furthermore, we introduce the first model-free method that requires no prior knowledge of problem-dependent quantities for communicating MDPs.

Abstract

Explore similar work

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs