- 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 convergence rate for NPG with exact advantages. They also provide numerical simulations on a discretized mountain-car environment, comparing TRPO and NPG.
Critical strengths
- 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.
- The proofs appear to be correct and self-contained and the paper is well organized and easy to follow.
Critical weaknesses
-
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 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).
-
Most of Sections 3–4 are already known. Assumption 1 is exactly Kallenberg’s transient MDP, with entering 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 . 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 , whereas the paper’s threshold 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
-
Can you clarify the differences between their results and the related work mentioned?
-
Can assumption 1 be relaxed in a manner that allows the results to be applied to a wider variety of MDPs?