Pith. sign in

REVIEW 4 minor 26 references

This paper proves that exact Natural Policy Gradient converges in finite-horizon MDPs with known dynamics at an O(H^2/t) sublinear rate under constant step sizes, and geometrically under increasing step sizes, handling horizon-dependent tra

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 03:56 UTC pith:FN7OYUHM

load-bearing objection Solid first finite-time analysis of exact NPG in finite-horizon tabular MDPs; the proofs check out and the limitations are honestly flagged.

arxiv 2607.22982 v1 pith:FN7OYUHM submitted 2026-07-25 cs.LG math.OCstat.ML

Finite-Time Analysis of the Natural Policy Gradient in Finite-Horizon Markov Decision Processes

Asha Barua , Sajad Khodadadian This is my paper
classification cs.LG math.OCstat.ML MSC 68T0590C4068W40
keywords natural policy gradientfinite-horizon MDPpolicy mirror descentfinite-time convergencedistribution mismatch coefficientsublinear convergencegeometric convergencelinear MDP
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes the first finite-time convergence guarantees for the exact Natural Policy Gradient (NPG) in finite-horizon Markov decision processes with known, horizon-dependent transition kernels. It shows that a constant step size yields an O(H^2/t) sublinear optimality gap after t iterations, extending a rate previously known only for discounted infinite-horizon problems. With increasing step sizes, it proves a geometric rate of O((1-1/vartheta_rho)^t), where vartheta_rho is a distribution-mismatch coefficient, and identifies a horizon-only schedule that achieves this rate without problem-dependent tuning. These results matter because finite-horizon problems—planning, robotics, sequential decision tasks—lack the contraction provided by discounting, and no finite-time NPG guarantees existed in this setting despite the algorithm's practical popularity.

Core claim

For any finite-horizon tabular MDP with known dynamics, NPG with constant step size eta and uniform initialization satisfies V^{pi*,h}(s) - V^{pi_T,h}(s) <= (H-h+1) log|A|/(eta T) + (H-h+1)^2/T for every horizon h and state s, giving a sublinear O(H^2/T) rate. The same rate holds for linear MDPs under an exact population-projection oracle with a full-support projection distribution, where the Q-NPG parameter update induces exactly the tabular policy-space update. For the tabular setting, the paper further proves that with an increasing step-size schedule satisfying eta_{t+1} >= vartheta_rho/(vartheta_rho-1) eta_t, the horizon-1 optimality gap decays geometrically as O((1-1/vartheta_rho)^T),

What carries the argument

The core mechanism is the multi-start objective J(pi) = (1/H) sum_{h0=1}^H V^{pi,h0}(rho), which averages returns over all starting horizons drawn uniformly. Averaging the state-visitation distributions over starting horizons creates a policy-independent baseline mass at every horizon, yielding the lower bound bar d^{i,pi}_rho(s) >= (1/H) rho(s). This lower bound lets the analysis define a distribution-mismatch coefficient vartheta_rho that controls the geometric convergence rate, playing the role that the discount factor's contraction plays in infinite-horizon analyses.

Load-bearing premise

The geometric convergence rate requires that every state reachable under the optimal policy's multi-start visitation measure also lies in the support of the initial state distribution rho, so that the distribution-mismatch coefficient vartheta_rho is finite; if rho misses any such state, the geometric claim does not apply.

What would settle it

Search for a finite-horizon tabular MDP where constant-step exact NPG's suboptimality gap after T iterations exceeds C (H-h+1)^2 / T for arbitrarily large T and any fixed constant C; such an instance would disprove the claimed sublinear rate of Theorem 1, which the paper notes is not yet matched by a lower bound. For the geometric claim, compute vartheta_rho on an MDP where rho assigns zero probability to a state the optimal policy must visit; vartheta_rho becomes infinite and the theorem's hypothesis fails, so the geometric bound is not expected to hold.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Constant-step exact NPG reaches epsilon suboptimality at horizon h within O((H-h+1)^2/epsilon) iterations in tabular finite-horizon MDPs.
  • The O(H^2/T) rate transfers to linear MDPs under an exact population-projection oracle with full-support projection distribution, establishing an oracle benchmark for sample-based extensions.
  • The horizon-only step-size schedule eta_t = eta_0 (H/(H-1))^t achieves geometric convergence without any problem-dependent tuning whenever vartheta_rho is finite.
  • When vartheta_rho = H, the geometric rate becomes O((1-1/H)^T), and the paper identifies an MDP class (uniform-invariant doubly stochastic kernels) where this bound is achieved.
  • The geometric guarantee applies to the horizon-1 gap only, not to per-horizon gaps for h > 1, due to the multi-start construction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If a matching lower bound confirms the O(H^2/T) dependence, it would show that the absence of a discount contraction inherently costs a factor of H^2 in the finite-horizon setting, guiding whether iteration-count improvements should target this factor or the problem-dependent geometric rate.
  • The mismatch condition vartheta_rho < infinity parallels coverage assumptions in infinite-horizon analyses; a testable extension would relax it to allow additive error terms for poorly covered states, yielding finite-time bounds under partial coverage.
  • The multi-start objective suggests an algorithmic variant that explicitly reinitializes the policy evaluation from random horizons during training, which might improve practical finite-horizon performance if the objective's smoothness is what drives the geometric rate.
  • The linear MDP oracle assumption is strong; a natural next step left implicit by the paper is to quantify how estimation error from a finite-sample projection enters the bound and whether full support of the projection distribution can be replaced by a positive-definite feature covariance condition.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. This paper analyzes exact Natural Policy Gradient (equivalently, KL-based Policy Mirror Descent) in finite-horizon tabular MDPs with known, horizon-dependent transition kernels and nonstationary policies. It proves two main finite-time guarantees: (i) with constant step size, the optimality gap at horizon h after T iterations is bounded by ((H-h+1) log|A|)/(\eta T) + (H-h+1)^2/T, hence O((H-h+1)^2/T) after choosing \eta suitably; and (ii) with increasing step sizes satisfying a growth condition involving a distribution-mismatch coefficient \vartheta_\rho, the horizon-1 expected gap under initial distribution \rho converges geometrically as O((1 - 1/\vartheta_\rho)^T), with the horizon-only schedule \eta_t = \eta_0 (H/(H-1))^t realizing this rate whenever \vartheta_\rho < \infty. The paper also shows that in linear MDPs an exact population-projection oracle with full-support projection distribution reduces linear Q-NPG to the tabular NPG policy update, preserving the same sublinear rate. The appendix supplies complete proofs, and simulations illustrate the predicted scaling.

Significance. The contribution is significant: it provides a first finite-time theory for exact NPG in finite-horizon MDPs, a setting where there is no discount-factor contraction and optimal policies are nonstationary. The multi-start objective with a uniform random starting horizon is a natural device that supplies the policy-independent lower bound needed for the geometric analysis, and the horizon-only robust schedule is a useful parameter-free variant. The paper is transparent about its limitations: it flags the open question whether the H^2 dependence is necessary, the unresolved value of \vartheta_\rho, the absence of a sample-based analysis, and the fact that backward induction is exact when dynamics are known. The proofs are self-contained, no fitted parameters enter the rates, and I found no load-bearing technical error. The weakest point is the support condition for \vartheta_\rho in Definition 2 / Eq. (22); as the authors note in Remark 2, choosing \rho = Unif(S) gives a finite coefficient bounded by H|S|, so this restricts the clean statement but does not undermine the central claim.

minor comments (4)
  1. [Section 4, Definition 2 and Eq. (22)] The geometric result is stated only for \vartheta_\rho \in (1,\infty); when the support condition fails, \vartheta_\rho = \infty and the rate in (25) is vacuous. This is a genuine restriction, but it is mitigated by Remark 2. I suggest stating the uniform-\rho mitigation (\vartheta_\rho \le H|S|) in or immediately after Theorem 2, so that readers see the theorem is non-vacuous without an additional design choice.
  2. [Appendix, proof of Lemma 3] The proof contains grammatical roughness (e.g., 'for each horizon ... to have, V ...') and would benefit from a rewrite. The mathematics is correct.
  3. [Equations (2), (16), and (18)] There are typographical artifacts in some displayed equations (unusual glyphs where inner products and expectations are typeset). These do not affect the mathematics but should be cleaned up in the final version.
  4. [Section 5.2 and Figures 2-3] The horizontal-axis labels and the omission of h=H are explained, but the captions could be more explicit that the h=H case is excluded because the tail has effective horizon 1 and \vartheta_\rho=1, not because of numerical failure. This is a clarity suggestion only.

Circularity Check

0 steps flagged

No significant circularity: all rates derived from stated MDP assumptions; only self-citation is non-load-bearing.

full rationale

The paper is self-contained against its stated model. Theorem 1 follows from the performance difference lemma, Jensen's inequality, the one-step improvement lower bound, and a telescoping argument over KL potentials; no fitted parameter or externally assumed rate enters the proof. Theorem 2 introduces the multi-start objective and the distribution-mismatch coefficient ϑ_ρ, which is a problem-dependent constant defined from the MDP and the optimal policy, not fitted to the observed optimality gaps; its support condition is explicitly stated in Definition 2 and Theorem 2, and Remark 2 notes that taking ρ=Unif(S) makes ϑ_ρ finite. The linear-MDP result (Proposition 1) is an honest reduction: the exact population-projection oracle with full support turns Q-NPG into precisely the tabular NPG update, and the guarantee is inherited from Theorem 1 rather than assumed. The only self-citation is Khodadadian et al. (2022) in Table 1 and the related-work narrative, where it is listed among prior infinite-horizon discounted analyses; it is not used to prove any main result. The simulations evaluate the theoretical bound using the exactly computed ϑ_ρ of the constructed MDP, which is a numerical illustration, not a fitted prediction. Overall, no load-bearing step reduces to its own inputs or to a self-citation chain.

Axiom & Free-Parameter Ledger

3 free parameters · 6 axioms · 0 invented entities

The analysis rests on standard finite MDP assumptions, the exact NPG/PMD update, imported mirror-descent inequalities, and a finite distribution-mismatch coefficient. No new physical or algorithmic entities are postulated; the multi-start objective is a mathematical device.

free parameters (3)
  • initial step size eta_0 = arbitrary positive (e.g., 1)
    In the horizon-only schedule eta_t = eta_0(H/(H-1))^t, Theorem 2 holds for any eta_0>0; it only scales the additive constant, so it is not fitted to data.
  • initial-state distribution rho = full-support distribution, e.g., Unif(S)
    rho enters the multi-start objective and the definition of vartheta_rho; the theorem's rate and the finiteness of vartheta_rho depend on it. The paper notes rho is analysis-only and can be chosen as uniform.
  • projection distribution v (linear MDP) = any full-support distribution, e.g., Unif(S x A)
    In Proposition 1, v defines the exact population projection oracle; the result holds for any v with full support, so it is a design choice rather than a fitted parameter.
axioms (6)
  • domain assumption Finite state/action sets, rewards in [0,1], horizon-dependent transition kernels
    Section 2.1 defines the MDP; all results are conditional on this model.
  • domain assumption NPG update (Eq. 1) and softmax parametrization (Eq. 5) for linear MDPs
    The algorithm analyzed is exactly this update; the softmax parametrization in the linear setting is used to preserve full support.
  • standard math KL mirror-descent three-point inequality (Lan 2023, Xiao 2022)
    Used in Lemma 6 and Lemma 7 as a known identity; must be imported from the cited literature.
  • domain assumption Linear MDP realizability (Assumption 1)
    In Proposition 1, Q is assumed exactly linear in features and the oracle returns an exact minimizer; this is a strong oracle condition.
  • domain assumption Full-support initial policy and finite step sizes
    Used to keep KL divergences finite and vartheta_t finite; standard in PMD analyses.
  • ad hoc to paper Support condition for vartheta_rho (Eq. 22): supp(bar d^{i,pi*}_rho) subseteq supp(rho) or vartheta_rho < infinity
    Required for Theorem 2's geometric rate; can be guaranteed by choosing rho with full support, but the rate's contraction factor depends on vartheta_rho which is generally unknown.

pith-pipeline@v1.3.0-alltime-deepseek · 26090 in / 16126 out tokens · 143077 ms · 2026-08-01T03:56:55.517921+00:00 · methodology

0 comments
read the original abstract

Natural Policy Gradient (NPG) is a well-established Reinforcement Learning algorithm that underlies widely used methods such as Trust Region Policy Optimization and Proximal Policy Optimization, both of which have demonstrated strong empirical success. In this paper, we study exact NPG in finite-horizon Markov Decision Processes with known dynamics and horizon-dependent transition kernels. We provide the first finite-time convergence guarantees for this algorithm in this setting, for which we consider both constant and increasing step size regimes. With a constant step size $\eta_t=\eta$, we prove that NPG converges sublinearly with a rate of $\mathcal{O}(H^{2}/t)$ after $t$ iterations, where $H$ is the horizon length. We also extend this constant step size analysis to linear MDPs in an exact population-projection oracle under a full support projection distribution, recovering the same sublinear rate as in the tabular setting. Furthermore, with increasing step sizes, we prove that this algorithm achieves a linear convergence rate of $\mathcal{O}\left(\left(1-\frac{1}{\vartheta_\rho}\right)^t\right)$ for a problem-dependent constant $\vartheta_\rho > 1$, and the horizon-only robust schedule of the form $\eta_t=\eta_0(H/(H-1))^t$ where $\eta_0>0$ and $H \geq 2$, attains this same geometric rate.

Figures

Figures reproduced from arXiv: 2607.22982 by Asha Barua, Sajad Khodadadian.

Figure 1
Figure 1. Figure 1: Constant step size NPG on a randomly generated finite-horizon tabular MDP: (a) error [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Increasing step size NPG on the structured instance with [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Increasing step size NPG on the randomly generated MDP under the problem-dependent [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 3 linked inside Pith

  1. [1]

    Advances in neural information processing systems , volume=

    A natural policy gradient , author=. Advances in neural information processing systems , volume=

  2. [2]

    Journal of Machine Learning Research , volume=

    On the theory of policy gradient methods: Optimality, approximation, and distribution shift , author=. Journal of Machine Learning Research , volume=

  3. [3]

    International conference on machine learning , pages=

    Trust region policy optimization , author=. International conference on machine learning , pages=. 2015 , organization=

    2015

  4. [4]

    arXiv preprint arXiv:1707.06347 , year=

    Proximal policy optimization algorithms , author=. arXiv preprint arXiv:1707.06347 , year=

    Pith/arXiv arXiv

  5. [5]

    2014 , publisher=

    Markov decision processes: discrete stochastic dynamic programming , author=. 2014 , publisher=

    2014

  6. [6]

    CS Dept., UW Seattle, Seattle, WA, USA, Tech

    Reinforcement learning: Theory and algorithms , author=. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep , volume=

  7. [7]

    Artificial Intelligence Review , volume=

    Reinforcement learning in robotic applications: a comprehensive survey , author=. Artificial Intelligence Review , volume=. 2022 , publisher=

    2022

  8. [8]

    nature , volume=

    Mastering the game of Go with deep neural networks and tree search , author=. nature , volume=. 2016 , publisher=

    2016

  9. [9]

    Conference on learning theory , pages=

    Provably efficient reinforcement learning with linear function approximation , author=. Conference on learning theory , pages=. 2020 , organization=

    2020

  10. [10]

    International Conference on Machine Learning (ICML) , year=

    Global convergence of policy gradient methods for the linear quadratic regulator , author=. International Conference on Machine Learning (ICML) , year=

  11. [11]

    Advances in Neural Information Processing Systems , volume=

    Optimal convergence rate for exact policy mirror descent in discounted markov decision processes , author=. Advances in Neural Information Processing Systems , volume=

  12. [12]

    Deep Reinforcement Learning: A Brief Survey , year=

    Arulkumaran, Kai and Deisenroth, Marc Peter and Brundage, Miles and Bharath, Anil Anthony , journal=. Deep Reinforcement Learning: A Brief Survey , year=

  13. [13]

    Mathematical programming , volume=

    Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes , author=. Mathematical programming , volume=. 2023 , publisher=

    2023

  14. [14]

    SIAM Journal on Optimization , volume=

    Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence , author=. SIAM Journal on Optimization , volume=. 2023 , publisher=

    2023

  15. [15]

    Operations Research , volume=

    Global optimality guarantees for policy gradient methods , author=. Operations Research , volume=. 2024 , publisher=

    2024

  16. [16]

    arXiv preprint arXiv:2509.08827 , year=

    A survey of reinforcement learning for large reasoning models , author=. arXiv preprint arXiv:2509.08827 , year=

    Pith/arXiv arXiv

  17. [17]

    Advances in Neural Information Processing Systems (NeurIPS) , year=

    Training language models to follow instructions with human feedback , author=. Advances in Neural Information Processing Systems (NeurIPS) , year=

  18. [18]

    ArXiv , year=

    Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback , author=. ArXiv , year=

  19. [19]

    International Conference on Learning Representations (ICLR) , year =

    Beyond Stationarity: Convergence Analysis of Stochastic Softmax Policy Gradient Methods , author =. International Conference on Learning Representations (ICLR) , year =

  20. [20]

    Reinforcement learning algorithms: A brief survey , journal =

    Ashish Kumar Shakya and Gopinatha Pillai and Sohom Chakrabarty , keywords =. Reinforcement learning algorithms: A brief survey , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.eswa.2023.120495 , url =

    arXiv 2023

  21. [21]

    Journal of Machine Learning Research , volume=

    On the convergence rates of policy gradient methods , author=. Journal of Machine Learning Research , volume=

  22. [22]

    Proceedings of the AAAI conference on artificial intelligence , volume=

    Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps , author=. Proceedings of the AAAI conference on artificial intelligence , volume=

  23. [23]

    Systems & Control Letters , volume=

    On linear and super-linear convergence of natural policy gradient algorithm , author=. Systems & Control Letters , volume=. 2022 , publisher=

    2022

  24. [24]

    International conference on machine learning , pages=

    On the global convergence rates of softmax policy gradient methods , author=. International conference on machine learning , pages=. 2020 , organization=

    2020

  25. [25]

    Operations Research , volume=

    Fast global convergence of natural policy gradient methods with entropy regularization , author=. Operations Research , volume=. 2022 , publisher=

    2022

  26. [26]

    arXiv preprint arXiv:2404.03372 , year=

    Elementary analysis of policy gradient methods , author=. arXiv preprint arXiv:2404.03372 , year=

    Pith/arXiv arXiv