REVIEW 2 major objections 4 minor 31 references
Reinforcement Learning with Random Time Horizons
T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proves exact policy-gradient formulas for random, policy-dependent episode lengths and shows the often-dropped expected-runtime factor is a real, policy-varying signal.
desk verdict Correct for hitting times, overclaimed for arbitrary random horizons; the counterexample in the stress test is real. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery has two parts. The first is the state-space density $\rho^\pi = \eta^\pi / Z^\pi$, built from the visit-count density $\eta^\pi = \sum_{n=0}^\infty \rho^\pi_n$ and its total mass $Z^\pi = \int_S \eta^\pi(s)\,ds = \mathbb{E}^\pi[N+1]$ (Lemma 2.3); this object turns trajectory sums into state-space integrals and makes the runtime factor explicit. The second is an unrolling expansion (Lemmas C.2 and C.3) that pushes $\nabla_\theta V^\pi$ through the transition densities, producing a sum of terms $\nabla_\theta\log \pi_\theta(S_n,A_n)Q^\pi(S_n,A_n)$ (or $\nabla_\theta\mu_\theta(S_n)^\top\nabla_a Q^\mu$ for deterministic policies) plus a boundary term $\int p^\pi_l \nabla_\theta V^\pi$. The boundary term vanishes as $l\to\infty$ because the stopping time is almost surely finite and the gradient of the value function is bounded, and its disappearance is exactly why the policy-dependence of $N$ contributes no extra term. Lemma 2.2 completes the picture by identifying discounted infinite-horizon returns with a geometrically distributed stopping time, so the random-time framework contains the classical discounting case.
What would settle it
Test the factorization on a simple tabular MDP with a target set and a stopping time that is almost surely finite but has infinite expectation—for instance a one-dimensional random walk with an absorbing boundary and a heavy-tailed first-passage time—and check whether Lemma 2.3's identity $Z^\pi = \mathbb{E}^\pi[N+1]$ and the state-space gradient (16) still hold; a divergence of the state-space side while the trajectory expectation (15) stays finite would falsify the central claim. A cheaper check is to take the paper's own mountain car problem and record $\mathbb{E}^\pi[N+1]$ during training: if the biased and correct gradients converge identically under per-step learning-rate rescaling, the effective-learning-rate interpretation would need revision.
Extended reading notes
Core claim
On its own terms, the paper establishes two identities. For stochastic policies the gradient of the expected return $J(\pi_\theta)$ is $$\nabla_\$\theta$ J(\pi_\$\theta$) = \mathbb{E}^\pi\Big[\sum_{n=0}^N \nabla_\$\theta$ \log \pi_\$\theta$(S_n,A_n)\, Q^\pi(S_n,A_n)\Big], \tag{15}$$ and for deterministic policies $$\nabla_\$\theta$ J(\mu_\$\theta$) = \mathbb{E}^\mu\Big[\sum_{n=0}^N \nabla_\$\theta$ \mu_\$\theta$(S_n)^\top \nabla_a Q^\mu(S_n,a)\big|_{a=\mu_\$\theta$(S_n)}\Big], \tag{25}$$ with no extra term arising from the fact that the stopping time $N$ depends on the policy. Read from the state-space perspective, the same gradients equal $\mathbb{E}^\pi[N+1]$ times the corresponding state-space expectation, Equations (16) and (26). The paper proves these formulas rigorously for continuous state and action spaces, derives a model-based deterministic version that avoids learning a Q-function, and shows via a geometric stopping time that the discounted infinite-horizon objective is a special case of the random-time setting. Its experiments compare the trajectory formula, the state-space formula, and a biased state-space gradient that omits the runtime factor; the biased version's effective learning rate drifts as trajectories shorten, and the correct formulas converge roughly twice as fast in the deterministic example.
Load-bearing premise
The load-bearing assumption is that the expected runtime $\mathbb{E}^\pi[N+1]$ is finite; the paper only assumes almost-sure finiteness of $N$, and if a policy produced heavy-tailed hitting times with infinite mean, the state-space formulas and their runtime factor would not be well defined.
Editorial extensions
If this is right
- The trajectory-based estimator (15) is valid as-is for policy-dependent random stopping times, so REINFORCE-style implementations that sample until a random terminal condition need no correction, as long as returns are accumulated over the random horizon.
- The commonly used state-space gradient that omits $\mathbb{E}^\pi[N+1]$ is strictly incorrect for random horizons; the omitted factor behaves as a policy-dependent learning rate (Remark 2.7) and can explain slow or unstable convergence.
- Episodic problems defined by hitting a terminal set are random-time problems, and the deterministic, model-based formula (27) needs no learned Q-function whenever the transition density is known.
- The discounted infinite-horizon setting is the random-time setting with a geometric horizon, which unifies episodic and continuing formulations at the level of the objective (Lemma 2.2 and Equation (13)).
- Baseline and return-to-go variants of the gradient (Corollary 2.8) remain valid under random stopping times, so variance-reduction techniques carry over without change.
Reading between the lines
- The clean form of (15) depends on using the Q-function of the random-time process itself; a Q-function learned for a fixed or discounted horizon would not satisfy the identity, so mixing replay buffers across different stopping rules could silently reintroduce bias—a concern the paper does not address.
- Because the omitted factor acts as a policy-dependent learning rate, monitoring $\mathbb{E}^\pi[N+1]$ during training gives a practical drift diagnostic: a runtime that changes by orders of magnitude implies the effective step size is changing with it.
- The same factorization suggests an off-policy extension in which the runtime factor is reweighted by an importance ratio; the paper notes the state-space view enables replay buffers but does not derive such an estimator.
- The bias is not uniformly harmful: in the mountain car example the biased gradient's effective learning rate first collapses then grows, so a deliberately tuned runtime factor might be used as a scheduled learning-rate device—an optimization trick the paper does not propose.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper extends policy gradient theory to Markov decision processes with random time horizons. It presents trajectory-based and state-space-based gradient formulas for stochastic policies (Prop. 2.6, Eqs. 15-16) and deterministic policies (Prop. 2.9, Eqs. 25-26), a model-based deterministic variant (Cor. 2.10), and alternative return/baseline versions (Cor. 2.8, Cor. C.5). The main structural claims are that the policy-dependence of the stopping time does not add an extra term in the trajectory formula, and that the state-space formula carries an explicit factor E^pi[N+1] whose omission changes the effective learning rate. Numerical experiments on a mountain car problem, a two-joint reacher, and a molecular-dynamics hitting-time problem compare the proposed estimators with a version that omits the expected-runtime factor.
Significance. If restricted to the setting for which the proofs are valid, this is a useful and mostly rigorous treatment of a gap in the policy-gradient literature. The appendices contain explicit, self-contained unrolling proofs; the derivations are parameter-free; the distinction between trajectory and state-space perspectives is clearly drawn; and the effective-learning-rate interpretation in Remark 2.7 is insightful. The paper also provides code and reproducible experimental settings. However, the theorems are stated for arbitrary almost surely finite random time horizons, and that level of generality is false: Eq. (15) can fail for policy-dependent stopping times whose remaining length depends on the history. Since the main practical examples are first hitting times, the core message can survive a restriction to time-homogeneous stopping rules, but the stated claims need revision.
major comments (2)
- [Prop. 2.6, Eq. (15); also Prop. 2.9, Eq. (25); proof in Appendix C] The proof relies on the restart property stated in the remark after Eq. (14) ('the problem is time-autonomous'). This property holds for first hitting times of the form (6) and for the geometric time in Lemma 2.2, but it does not hold for a general policy-dependent stopping time whose remaining length depends on the realized history. For such an N, the Q-function entering (15) at time n is not the same as the Q-function defined in (14) for a fresh start, the Bellman equation (44) is not valid, and the tower-property step used in the proof of Proposition 2.6 and Corollary 2.8 fails. Concretely, take state space {A,T}, start at A, actions 0 and 1, deterministic transition to T after action 1 in A and to A after action 0 in A, reward 1 only for (A,1), and the stopping rule N=0 if A0=1, N=1 if A0=0. With pi(A,1)=theta, one computes J(theta)=2theta-theta^2, so the true gradient is 2-2theta, whereas the right-hand side of (15) with Q^pi defined by (14) equals (1-theta)+(1-theta)^2=2-3theta+theta^2. The theorem's stated scope is therefore too broad; it should be restricted to time-homogeneous stopping rules, or a correct history-dependent Q-function and Bellman argument must be supplied.
- [Section 2, Lemma 2.3, Prop. 2.4, Eqs. (10)-(11), (16), (26); proof of Prop. 2.6, Eq. (67)] The assumption P(N<infinity)=1 is insufficient for the state-space formulas. Lemma 2.3 defines Z^pi=E^pi[N+1], and Eqs. (11), (16), and (26) factor through this quantity. Almost sure finiteness does not imply finite expectation; for instance, return times of a null-recurrent Markov chain can be almost surely finite with infinite mean. Without E^pi[N+1]<infinity, rho^pi is not a probability density and the factorization eta^pi = Z^pi rho^pi used in the proofs of Props. 2.4, 2.6, and 2.9 is invalid. The theorems should state E^pi[N+1]<infinity as an explicit hypothesis. In addition, the proof of Prop. 2.6 assumes the sup-norm bound (67), sup_s ||nabla_theta V^pi(s)|| < infinity, and an interchange of sums and integrals; these regularity conditions appear only in the proof and not in the theorem statements.
minor comments (4)
- [Eq. (5) and Appendix A] The objective sums r(S_n,A_n) over n=0,...,N, but the trajectory construction in Appendix A defines actions only for n=0,...,N-1. It should be clarified whether A_N is a dummy action at the terminal state or the sum should run to N-1 plus a separate terminal reward; this ambiguity also affects the algorithms in Appendix D.
- [Appendix E.2 and E.3] The labels 'state-space PG unbiased' and 'state-space DPG unbiased' in the experimental details appear to refer to what the main text calls 'state-space PG (biased)' and 'state-space DPG (biased)'; please make the terminology consistent.
- [Lemma 2.2] The support of the geometric distribution should be specified explicitly. With P(N_gamma=m)=gamma^m(1-gamma), the parameterization on {0,1,2,...} gives E[N_gamma+1]=1/(1-gamma) and is consistent with Eq. (13), whereas the conventional 'Geom(1-gamma)' notation often means support starting at 1; please disambiguate.
- [Remark 2.7] The sentence 'Both cases lead to incorrect formulas when being applied to random time horizon problems' is too strong for finite deterministic horizons, where the omitted factor is constant and only rescales the gradient by a fixed learning-rate factor; the surrounding effective-learning-rate discussion already makes the intended point, so consider rewording to 'can lead to different effective learning rates'.
Circularity Check
No significant circularity: gradient formulas are derived self-containedly from Bellman equations; self-citations are contextual, not load-bearing.
full rationale
The central policy-gradient formulas (15), (16), (25), and (26) are derived in Appendix C from the Bellman equations, the unrolling lemmas (Lemma C.2 and Lemma C.3), and the definition of the state-space density ηπ = ρπ E[N+1] (Lemma 2.3). Proposition 2.6 unrolls ∇θV, takes the large-l limit under the stated bound (67), and then re-expresses the result via Proposition 2.4 applied to an auxiliary integrand; this is a legitimate use of a proven lemma rather than a circular reduction. The deterministic-policy statements follow the same proof structure. The paper's self-citations, notably Ribera Borrell et al. (2024) and Quer & Ribera Borrell (2024), appear as related control-theoretic context or as heuristic antecedents, and the discrete-time proofs here do not rely on those citations to close an argument. The numerical experiments compare the proposed formulas against the standard biased gradient after tuning learning rates, so the empirical claims are not fitted inputs renamed as predictions. The manuscript does contain an unflagged scope limitation: it assumes only a.s.-finiteness of N (Section 2) while Lemma 2.3 and the state-space formulas require E[N+1] < ∞, and the proof of Proposition 2.6 additionally assumes sup_s ||∇θV^π(s)|| < ∞ (Eq. 67). These are correctness restrictions, not circularity. Overall, the derivation chain is self-contained, with only minor context-setting self-citations; hence the low score.
Assumptions & free parameters
assumptions (4)
- domain assumption The stopping time N is almost surely finite; additionally the expected runtime E[N+1] is finite (implicitly assumed for Z^π = E[N+1] in Lemma 2.3 and Proposition 2.4).
- domain assumption The value function gradient is bounded: sup_s ||∇θ V^π(s)|| ≤ L_θ for each θ (Eq. 67).
- domain assumption The transition density p(s'|s,a) and policies are smooth enough for the required derivatives and the Leibniz rule to hold.
- standard math The stopped process retains the Markov property and the tower property holds for expectations over the random-time trajectories.
Cite this review
Pith. "Pith review of Reinforcement Learning with Random Time Horizons." pith.science (2026). https://pith.science/paper/3VNVW4CC
@misc{pith2026250600962,
author = {Pith},
title = {Pith review of: Reinforcement Learning with Random Time Horizons},
year = {2026},
howpublished = {\url{https://pith.science/paper/3VNVW4CC}},
note = {Machine review of arXiv:2506.00962}
}
read the original abstract
We extend the standard reinforcement learning framework to random time horizons. While the classical setting typically assumes finite and deterministic or infinite runtimes of trajectories, we argue that multiple real-world applications naturally exhibit random (potentially trajectory-dependent) stopping times. Since those stopping times typically depend on the policy, their randomness has an effect on policy gradient formulas, which we (mostly for the first time) derive rigorously in this work both for stochastic and deterministic policies. We present two complementary perspectives, trajectory or state-space based, and establish connections to optimal control theory. Our numerical experiments demonstrate that using the proposed formulas can significantly improve optimization convergence compared to traditional approaches.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Reinforcement Learning : Theory and Algorithms . 2022. URL https://rltheorybook.github.io/
work page 2022
-
[2]
An optimal control perspective on diffusion-based generative modeling
Berner, J., Richter, L., and Ullrich, K. An optimal control perspective on diffusion-based generative modeling. Transactions on Machine Learning Research, 2024
work page 2024
-
[3]
Steady state analysis of episodic reinforcement learning
Bojun, H. Steady state analysis of episodic reinforcement learning. In Advances in Neural Information Processing Systems , volume 33, pp.\ 9335--9345, 2020
work page 2020
-
[4]
Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
Chen, S.-W., Ross, K., and Youssef, P. Finite-sample analysis of the M onte C arlo exploring starts algorithm for reinforcement learning. arXiv preprint arXiv:2410.02994, 2024
work page Pith review arXiv 2024
-
[5]
Degris, T., White, M., and Sutton, R. S. Off-policy actor-critic. In International Conference on Machine Learning. PMLR, 2012
work page 2012
-
[6]
Finite state Markovian decision processes
Derman, C. Finite state Markovian decision processes. Academic Press, Inc., 1970
work page 1970
-
[7]
Hartmann, C. and Sch \"u tte, C. Efficient rare event simulation by optimal nonequilibrium forcing. Journal of Statistical Mechanics: Theory and Experiment, 2012 0 (11): 0 P11004, 2012
work page 2012
-
[8]
Variational characterization of free energy: Theory and algorithms
Hartmann, C., Richter, L., Sch \"u tte, C., and Zhang, W. Variational characterization of free energy: Theory and algorithms. Entropy, 19 0 (11): 0 626, 2017
work page 2017
Show all 31 references
-
[9]
Lie, H. C. Fr\'echet derivatives of expected functionals of solutions to stochastic differential equations. arXiv preprint arXiv:2106.09149, 2021
2021 arXiv
-
[10]
Continuous control with deep reinforcement learning
Lillicrap, T. Continuous control with deep reinforcement learning. In International Conference on Learning Representations, 2016
2016
-
[11]
Online reinforcement learning with uncertain episode lengths
Mandal, D., Radanovic, G., Gan, J., Singla, A., and Majumdar, R. Online reinforcement learning with uncertain episode lengths. Proceedings of the AAAI Conference on Artificial Intelligence, 37 0 (7): 0 9064--9071, 2023
2023
-
[12]
Playing A tari with deep reinforcement learning
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. Playing A tari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013
2013 arXiv
-
[13]
and Thomas, P
Nota, C. and Thomas, P. S. Is the policy gradient a gradient? In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp.\ 939--947, 2020
2020
-
[14]
and Richter, L
N \"u sken, N. and Richter, L. Solving high-dimensional H amilton-- J acobi-- B ellman PDE s using neural networks: perspectives from the theory of controlled diffusions and measures on path space. Partial differential equations and applications, 2 0 (4): 0 48, 2021
2021
-
[15]
Stochastic control foundations of autonomous behavior
Paternain, S. Stochastic control foundations of autonomous behavior. University of Pennsylvania, 2018
2018
-
[16]
Continuous-time stochastic control and optimization with financial applications, volume 61
Pham, H. Continuous-time stochastic control and optimization with financial applications, volume 61. Springer Science & Business Media, 2009
2009
-
[17]
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014
2014
-
[18]
and Ribera Borrell, E
Quer, J. and Ribera Borrell, E. Connecting stochastic optimal control and reinforcement learning. Journal of Mathematical Physics, 65 0 (8): 0 083512, 2024
2024
-
[19]
Improving control based importance sampling strategies for metastable diffusions via adapted metadynamics
Ribera Borrell, E., Quer, J., Richter, L., and Sch \"u tte, C. Improving control based importance sampling strategies for metastable diffusions via adapted metadynamics. SIAM Journal on Scientific Computing, 46 0 (2): 0 S298--S323, 2024
2024
-
[20]
Trust region policy optimization
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International Conference on Machine Learning, pp.\ 1889--1897. PMLR, 2015
2015
-
[21]
Proximal policy optimization algorithms
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017
2017 arXiv
-
[22]
Overcoming the timescale barrier in molecular dynamics: Transfer operators, variational principles and machine learning
Sch \"u tte, C., Klus, S., and Hartmann, C. Overcoming the timescale barrier in molecular dynamics: Transfer operators, variational principles and machine learning. Acta Numerica, 32: 0 517--673, 2023
2023
-
[23]
Deterministic policy gradient algorithms
Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M. Deterministic policy gradient algorithms. In Proceedings of the 31st International Conference on Machine Learning , pp.\ 387--395. PMLR, 2014
2014
-
[24]
Singh, S. P. and Sutton, R. S. Reinforcement learning with replacing eligibility traces. Machine Learning, 22 0 (1): 0 123--158, 1996
1996
-
[25]
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. A Bradford Book, 2018
2018
-
[26]
S., McAllester, D., Singh, S., and Mansour, Y
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999
1999
-
[27]
U., De Cola, G., Deleu, T., Goulão, M., Kallinteris, A., Krimmel, M., KG, A., Perez-Vicente, R., Pierré, A., Schulhoff, S., Tai, J
Towers, M., Kwiatkowski, A., Terry, J., Balis, J. U., De Cola, G., Deleu, T., Goulão, M., Kallinteris, A., Krimmel, M., KG, A., Perez-Vicente, R., Pierré, A., Schulhoff, S., Tai, J. J., Tan, H., and Younis, O. G. Gymnasium: A standard interface for reinforcement learning envir...
2024
-
[28]
Wang, H., Zariphopoulou, T., and Zhou, X. Y. Reinforcement learning in continuous time and space: A stochastic control approach. Journal of Machine Learning Research, 21 0 (198): 0 1--34, 2020
2020
-
[29]
Unifying task specification in reinforcement learning
White, M. Unifying task specification in reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning , volume 70, pp.\ 3742--3750. PMLR, 2017
2017
-
[30]
Global convergence of policy gradient methods to (almost) locally optimal policies
Zhang, K., Koppel, A., Zhu, H., and Basar, T. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58 0 (6): 0 3586--3612, 2020
2020
-
[31]
Actor-critic method for high dimensional static H amilton-- J acobi-- B ellman partial differential equations based on neural networks
Zhou, M., Han, J., and Lu, J. Actor-critic method for high dimensional static H amilton-- J acobi-- B ellman partial differential equations based on neural networks. SIAM Journal on Scientific Computing, 43 0 (6): 0 A4043--A4066, 2021
2021
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.