stat.MLJan 31, 2026

Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotients

Authors: Yang Xu, Vaneet Aggarwal

Organizations: Purdue University, USA 47907

Abstract

We study fixed-policy evaluation for finite Markov chains that may be reducible and periodic. Classical evaluation methods with gain and bias decomposition are not always diagnostic: the gain records only invariant Cesàro averages, while persistent phase-dependent behavior is absorbed into the bias together with genuinely transient effects. We identify the real peripheral invariant subspace K(P)\mathcal{K}(P) of the transition matrix PP as the source of this ambiguity. Quotienting by K(P)\mathcal{K}(P) is the minimal exact quotient that removes all non-decaying modes and makes the remaining dynamics strictly stable. After choosing a gauge projection ΠΠ with kernel K(P)\mathcal{K}(P), the reward admits a unique decomposition r=gΠ⋆+(I−P)vΠ⋆r = g_Π^\star + (I-P)v_Π^\star, where gΠ⋆g_Π^\star is a persistent regime profile and vΠ⋆v_Π^\star is a gauge-fixed transient component. An exact comparison with classical normalized gain and bias shows that the new pair reallocates the same information into a persistent profile and a gauge-fixed representative of the transient quotient. This decomposition reconstructs finite-horizon returns, recovers statewise average reward, admits a transient-cost interpretation, and yields a stable estimator under a generative model.

Figures & tables

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jul 29, 2026

Minimal Markovization via Stable Quotients in Holonomy-Cover Decision Processes

An agent acting under partial observability must retain a recursively updateable statistic of history that restores the Markov property, but the smallest such statistic is generally unknown. We characterize this minimal Markov sufficient statistic for holonomy-cover decision processes, a structured POMDP class in which the visible dynamics are Markov and every realized visible transition applies a fixed permutation to a hidden mode. In particular, we construct the stable quotient, the coarsest observation-wise abstraction preserving one-step rewards and quotient successors, and prove that the pair of the current observation and stable class forms an exact finite Markov state. When the current class is correctly initialized, exact class tracking requires exactly the minimal memory symbols, in the sense that under reachability and pairwise decision separation at a maximizing observation, no arbitrary finite-memory controller can use fewer. Under resettable diagnostics, nearest-prototype class inference has exponentially decaying error, and a calibrate-then-restart reduction transfers finite-MDP guarantees to the recovered state. The results enable Holonomy Memory Reinforcement Learning. It represents memory by the current stable class, updates it through ordered edge transports, identifies local class coordinates when diagnostics are available, and applies a standard finite-MDP RL backbone after synchronization. Experiments recover an exact compression from raw states to quotient states and achieve perfect paired-order accuracy with three decision-time memory states, matching the quotient oracle and outperforming the non-oracle baselines.
Oct 7, 2026

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

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.
May 1, 2026

Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation

For a risk-averse finite-horizon Markov Decision Process, we introduce a special class of Markov coherent risk measures, called mini-batch measures. We also define the class of multipattern risk-averse problems that reduce to linear MDPs in the risk-neutral case. We use both concepts in a feature-based QQ-learning method with multipattern QQ-factor approximation and we prove a high-probability regret bound of O~(d3/2HNH−1K)\widetilde{\mathcal{O}}\big(d^{3/2}HN^{H-1}\sqrt{K}\big), where dd is the number of features, HH is the horizon, N≥2N\ge2 is the mini-batch size, KK is the number of episodes, and O~\widetilde{\mathcal{O}} hides logarithmic factors. We also propose an economical version of the QQ-learning method that streamlines the policy evaluation (backward) step. The theoretical results are illustrated on a stochastic assignment problem and a short-horizon multi-armed bandit problem.