acceptodds
Withdrawn from ICLR 2027

Markov Decision Processes with Terminal States: Occupancy Measure and Algorithms

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Motivated by text generation in large language models, where the policy determines both the response content and termination via an end-of-sequence token, we study Markov decision processes (MDPs) with terminal states without discounting. In contrast to the fixed-horizon and infinite-horizon MDPs widely studied in the literature, in our setting, both cumulative reward and trajectory length depend on the policy. While infinite-horizon MDPs typically use discounted rewards to ensure finite returns, the undiscounted cumulative reward objective is finite in this setting, provided that every stationary policy terminates almost surely. Assuming every stationary policy terminates almost surely, we establish that feasible state-action occupancy measures form a compact convex polytope, with expected return and termination time acting as linear functionals. Building on this geometry, we prove that any convex combination of these measures is realizable by an explicitly constructed stationary policy, and that the -fold undiscounted Bellman operator is a strict contraction. Finally, we derive Trust-Region Policy Optimization (TRPO) and Natural Policy Gradient (NPG) algorithms for this setting, providing sufficient conditions for monotonic improvement and non-asymptotic convergence rates.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Markov decision process, Natural policy gradient, Trust region policy optimization, Occupancy measure

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_B4FxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper focuses on undiscounted MDPs with terminal states, motivated by LLM text generation, where the policy determines both the content and the length of the trajectory. They assume that every stationary policy terminates almost surely, and show that this implies a uniform bound on the expected termination time. They show that the K-fold composition of the policy-evaluation Bellman operator is a contraction in the sup-norm for K larger than the expected termination time. They show that the feasible set of occupancy measures is a compact convex polytope, on which the expected return and the expected termination time are linear functionals, and that any convex combination of occupancy measures is realized by an explicitly constructed stationary policy. They derive a performance-difference lemma for this setting, use it to bound the TRPO surrogate error, and give a mixture update with guaranteed monotonic improvement. They derive the policy gradient and the NPG update under tabular softmax policies, and prove an O(1/K)O(1/K) convergence rate for NPG with exact advantages. They also provide numerical simulations on a discretized mountain-car environment, comparing TRPO and NPG.

Critical strengths
  1. The setting explored is a relevant setting where RL for LLMs truly operates. Thus, the stated contributions have the claimed impact and applications to LLMs.
  2. The proofs appear to be correct and self-contained and the paper is well organized and easy to follow.
Critical weaknesses
  1. The introduction states that “the geometry of occupancy measures and the non-asymptotic convergence properties of policy optimization in this setting remain unclear” (lines 63–68). Weakness 2 addresses the geometry part. The convergence part is contradicted by the paper’s related-work section (Appendix A), which cites Lee and Ryu (2025) and Nanda and Chen (2026). Lee and Ryu study undiscounted total-reward MDPs under a weaker assumption, that all policies have finite values, which holds under Assumption 1. Their constant-step NPG bound yields an O(1/K)O(1/K) rate with policy-specific constants that are at least as tight as those of Theorem 5. Their transient performance-difference lemma and policy gradient theorem also overlap with Lemma 3 and Theorem 4. Nanda and Chen prove geometric convergence of NPG under exactly the paper’s assumption that all stationary policies are proper. The remaining differences are minor (e.g., Lee and Ryu assume a full-support initial distribution).

  2. Most of Sections 3–4 are already known. Assumption 1 is exactly Kallenberg’s transient MDP, with entering S⊥S_\bot is playing the role of his breakdown probability. For this class, Kallenberg (2016, Theorem 9.18) shows that for any initial distribution the occupation vectors of all policies form exactly the polyhedron given by Equation. 1, and that a feasible point is realized by π(a∣s)=ν(s,a)/ν(s)\pi(a|s) = ν(s,a)/ν(s). This is Lemma 2. Theorem 2 and Corollaries 1–2 follow immediately from it, using the bounded total mass (2016, Thm 4.8) and the linearity of the return. Lemma 1 and Theorem 1 follow from his Theorem 4.10, with N = |X|. In fact, this already gives a contraction at K=N+1K = N+1, whereas the paper’s threshold K>TmaxK > T_{max} can be much larger. Apart from the explicit constants, I could not find anything in Sections 3–4 that is novel, which significantly undermines three of the five stated contributions.

Questions for authors
  1. Can you clarify the differences between their results and the related work mentioned?

  2. Can assumption 1 be relaxed in a manner that allows the results to be applied to a wider variety of MDPs?

Reviewer_irfeOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies finite, undiscounted MDPs in which every stationary policy reaches a terminal state almost surely. It characterizes occupancy measures and their mixtures, establishes a multi-step contraction property for policy evaluation, and derives a TRPO surrogate-error bound with a conservative update ensuring monotonic improvement. It also proves an O(1/K)O(1/K) convergence bound for exact tabular NPG.

Critical strengths

The paper gives a explanation of how occupancy measures connect cumulative reward, expected episode length, and policy optimization. The distinction between mixing policies and mixing occupancy measures is useful, and the analysis explicitly tracks how termination times affect the TRPO error bound and NPG convergence rate.

Critical weaknesses

My main concern is the overlap with prior work and the lack of a clear explanation of the paper’s distinct contributions. Although the authors cite relevant work in the related-work appendix, they do not adequately discuss these connections in the introduction or main text.

In particular, Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs already establishes a transient policy-gradient theorem and an O(1/K)O(1/K) convergence guarantee for constant-step-size natural policy gradient (NPG). Lemma 3, Theorem 4, and the NPG convergence result in the submitted manuscript appear closely related to results established in that work. The authors should explicitly compare the assumptions and conclusions of these results and explain what their paper adds.

The authors should also expand their comparisons with Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework and Policy Optimization for Stochastic Shortest Path, which study policy optimization methods in the stochastic shortest-path setting. The key distinctions should be presented in the introduction or main text, rather than confined to the appendix. Without these comparisons, it is difficult to assess the paper’s novelty.

Questions for authors

How do Lemma 3, Theorem 4, and the NPG convergence guarantee differ from the corresponding results in Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs, particularly in their assumptions and conclusions?

How do the NPG convergence results in Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework relate to those established in this work?

Reviewer_75buOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies finite MDPs with absorbing terminal states and an undiscounted total-reward objective. Under the assumption that every stationary policy terminates almost surely, it describes the set of occupancy measures, gives a K-fold contraction for the undiscounted Bellman operator, and analyzes TRPO and softmax NPG, with a mixing rule for monotonic TRPO updates and an O(1/K)\mathcal{O}(1/K) last-iterate bound for NPG. A discretized experiment compares the two methods.

Critical strengths

The problem is formulated clearly, with a policy-dependent horizon and a uniform bound on expected length from the assumption that every stationary policy terminates. Occupancy measures, the performance-difference lemma, and the TRPO and NPG analyses are developed in this setting with explicit constants in that bound. The presentation is self-contained, and the experiment is consistent with the claimed behavior of the two methods.

Critical weaknesses

The contribution and novelty of this paper are limited. Theorem 2, Corollary 1, and Theorem 5 seem to be known results. Theorem 2 and Corollary 1 are the standard occupancy linear program and occupancy-to-policy map, as used in Chen, Luo & Rosenberg (COLT 2022); Theorem 5 is already in Lee & Ryu (2025) and Nanda & Chen (2026). Theorem 1 is more like a remark on Bertsekas & Tsitsiklis (1991).

The presentation needs substantial improvement. Additionally, the experiments appear a little toy-like and would benefit from more realistic and challenging evaluation settings.

I also suggest that the authors include the appendix in the main submission file rather than providing it separately as supplementary material, which is difficult to follow. Note that the 'related work' section is necessary in the main manuscript.

Questions for authors
  1. Theorem 2 claims that feasible occupancies form a compact convex polytope. This is the occupancy linear program of Altman (2021). Compactness under a uniform hitting-time bound is Theorem 4.10 of Dufour & Prieto-Rumeau (ESAIM COCV 2024; arXiv:2309.07059), and the same set is used by Rosenberg et al. (2020) and Chen, Luo & Rosenberg (2022). Corollary 1 is the standard map π(a∣s)=ω(s,a)/ω(s)\pi(a|s)=\omega(s,a)/\omega(s) (Altman, 2021; Kakade & Langford, 2002). Could the authors explain the novelty of Theorem 2?

  2. Theorem 5 claims an O(1/K)\mathcal{O}(1/K) last-iterate NPG rate, presented as closing a gap. Lee & Ryu (2025, Theorem 6.2) already give this rate for undiscounted total reward; under Assumption 1, Nanda & Chen (2026, Theorem D.6) give geometric last-iterate NPG for SSP. Both papers are in the bibliography. How is Theorem 5 not implied by Lee & Ryu (2025, Theorem 6.2), and why is it a contribution relative to Nanda & Chen (2026, Theorem D.6)?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.