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

Jun 15, 2026cs.LG

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

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.

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

Ask PDF

Sep 23, 2026cs.LG

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

Robust average-reward Markov decision processes provide a fundamental framework for long-term performance optimization under uncertainty, and can have optimal long-run rewards that depend on the initial state. This state dependence requires a vector Bellman theory that accounts for both recurrent-class rewards and transition uncertainty. We develop such a theory for finite models with compact, post-action

(s,a)

-rectangular ambiguity. A gain-first, bias-second optimization principle yields a coupled vector gain-bias system, and every finite solution identifies the optimal robust gain and supplies stationary saddle strategies against history-dependent opponents, simultaneously from all initial states. We further characterize solvability through stationary gain conditions and a uniform bound on canonical transient corrections, and give sufficient conditions that permit distinct recurrent-class gains. The certificates also yield asymptotically affine trajectories of the robust Bellman operator, based on which we design a robust approximately shifted Halpern planning algorithm. Under finite Bellman solvability, the gain estimates and Bellman displacements converge to the optimal gain vector, and every extracted greedy controller is average-optimal after a finite, instance-dependent budget. These results thus connect finite Bellman certificates to undiscounted planning for state-dependent robust average rewards, providing theoretical understandings.

Yue Wang, George Atia

Department of Electrical and Computer Engineering University of Central Florida

Markov Decision Processes Bellman Equation Theory

Ask PDF

May 19, 2026cs.AI

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

We study reinforcement learning for episodic Markov Decision Processes (MDPs) whose transitions are modelled by a multinomial logistic (MNL) model. Existing algorithms for MNL mixture MDPs yield a regret of

\smash{\tilde{O}(dH^2\sqrt{T})}

(Li et al., 2024), where

d

is the feature dimension,

H

the episode length, and

T

the number of episodes. Inspired by the logistic bandit literature (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026), we introduce a problem-dependent constant

\barσ\_T \leq 1/2

, measuring the normalised average variance of the optimal downstream value function along the learner's trajectory. We propose an algorithm achieving a regret of

\smash{\tilde{O}(dH^2\barσ\_T\sqrt{T})}

, which recovers the existing bound in the worst case and improves upon it for structured MDPs. For instance, for KL-constrained robust MDPs,

\barσ\_T = O(H^{-1})

, reducing the horizon dependence by a factor

H

. We further establish a matching

\smash{Ω(dH^2\barσ\_T\sqrt{T})}

lower bound, proving minimax optimality (up to logarithmic factors) and fully characterising the regret complexity of MNL mixture MDPs for the first time.

Pierre Boudart, Pierre Gaillard, Alessandro Rudi

SIERRA · INRIA, École Normale Supérieure CNRS, PSL Research University Paris, France · Thoth +3

Markov Decision Processes Minimax Entropy Regularized Reinforcement Learning Regret

Ask PDF