Research map / Reinforcement learning / MDPs and planning

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

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: Average-reward and regularized MDPs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a fixed-policy evaluation decomposition r = g* + (I-P)v* for finite (reducible, periodic) Markov chains, quotienting by the real peripheral invariant subspace, and a sample-based estimator under a generative model.

Problem

Classical gain-bias evaluation of a fixed policy on reducible or periodic Markov chains entangles persistent phase-dependent behavior with transient cost, because the invariant gain collapses cyclic phases and the bias absorbs the rest.

Approach

Quotient by the real peripheral invariant subspace K(P) (the minimal invariant subspace making the quotient dynamics strictly stable), pick a gauge projection with kernel K(P), and decompose the reward into a persistent regime profile g* (in K(P)) and a gauge-fixed transient component v*; the anchor gauge gives v* a transient-cost (hitting-time) interpretation.

Key results

• Theorem: K(P) is the unique minimal real invariant subspace whose quotient has spectral radius below one, and the gauge-fixed decomposition r = g* + (I-P)v* is unique for any projection with kernel K(P).
• Deterministic cycle example: classical bias has ||h||_inf = d/8 for even d with a half-on/half-off reward while the new transient component v* is zero.
• Estimator guarantee: E||[v_T]-[v*]||_q = O(T^{-1/2}) + O(eps_b), and E||g_hat - g*||_inf = O(T^{-1/2}) + O(sqrt(log N / J)) + O(eps_b), with no experiments reported in the main text.

Surprising findings

• A large classical bias can arise purely from persistent periodic phase structure, with no transient burden, as in a deterministic cycle.

Limitations

• Estimator guarantees hold only on a high-probability structural recovery event, and exact support recovery requires a rare-edge sample size depending on p_min.
• Authors do not claim uniform dominance over plug-in estimation of the transition matrix.
• Analysis is tabular and under a generative model; the gauge choice is a normalization and the results depend on it.

Experimental setup

Metrics: finite-horizon return error bound quotient error persistent profile error

Baselines: classical normalized gain and bias plug-in estimation

Builds on: gain-bias Poisson equation multichain average reward dynamic programming semi-norm Lyapunov stability

Closest papers by meaning

• The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize (NeurIPS 2024 · similarity 0.85)
• Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes (NeurIPS 2024 · similarity 0.85)
• The surprising efficiency of temporal difference learning for rare event prediction (NeurIPS 2024 · similarity 0.85)
• Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.85)
• Finite-Time Bounds for Average-Reward Fitted Q-Iteration (NeurIPS 2025 · similarity 0.84)
• On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation (NeurIPS 2024 · similarity 0.84)