Reinforcement Learning with Random Time Horizons
Authors: Enric Ribera Borrell
Lorenz Richter
Christof Schuette
Venue: ICML 2025 poster (2025)
Keywords: reinforcement learning
policy gradient theorem
random stopping times
optimal control
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We extend the policy gradient formulas to random time horizons both for stochastic and deterministic policies.

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.

Reinforcement Learning with Random Time Horizons
Enric Ribera Borrell 12
Lorenz Richter +1 13 Christof Schütte 12
Abstract
are random even in deterministic environments. In all those cases the termination depends on previous (random) choices and therefore random itself. However, the common liter- ature has so far largely ignored the fact that runtimes can be random. In particular, policy gradient theorems typically assume that they are either deterministic or infinite (Sutton & Barto, 2018). Nonetheless, it is intuitively evident that considering random times should have an effect on opti- mization formulas since the runtimes mostly depend on the current policy such that in principle one should be careful with taking gradients (ef. Nota & Thomas (2020)).
We extend the standard reinforcement learning framework random time horizons. While the classical setting typically assumes finite and deter- ministic or infinite runtimes of trajectories, we ar- gue that multiple real-world applications naturally exhibit random (potentially trajectory-dent )eeeederyydeeeeeenet stopping times. Since those stopping times typi- cally depend on the policy, their randomness has effect policy gradient formulas, which we (mostly for the first time) derive rigorously in this work both for stochastic and deterministic poli- cies. We present two complementary perspectives, trajectory or state-space based, and establish con- nections to optimal control theory. Our numerical experiments demonstrate that using the proposed formulas can significantly improve optimization convergence compared traditional approaches.
In this work, we close this theoretical gap and systemati- cally investigate the effect of random time horizons in re- inforcement learning problems. Our contributions can be summarized as follows:
We extend the typical reinforcement learning frame- work to random time horizons, including (determinis- tic) finite and infinite runtimes as special cases.
1. Introduction
We state corresponding (random time) policy gradient theorems both for deterministic and stochastic policies.
The goal in reinforcement learning is identify policies π that maximize the expected return
This allows us for the first time rigorously derive a trajectory-based gradient estimator for random time horizons (for stochastic well as deterministic poli- cies) in discrete time.
(m.( =
((T)
Ex
(L)
where the states Sn and the actions A, run until a time N. While the classical framework considers the case where N either finite and deterministic or infinite, runtimes can as well be random. To name two examples, one could consider robots that aim to reach a target in noisy environment one could play a game whose terminating state depends reaching a certain level. Furthermore, considering stochastic policies (as commonly done in practice in order to balance exploration and exploitation) leads to the fact that runtimes
For deterministic policies we derive novel model- based policy gradient formula, which does not rely on learning the Q-value function as actor-critic ap- proaches.
In multiple numerical experiments, we systematically investigate the effect of incorporating the randomness of the time horizon in the gradient computation. For most cases we can see significant performance im- provements of our gradient formulas compared the standard ones, in particular in terms of convergence speed.
'Equal contribution 'Zuse Institute Berlin, 14195 Berlin, Ger- many "Institute of Mathematics, Free University Berlin, 14195 Berlin, Germany 'dida Datenschmiede GmbHH 10827 Berlin, Germany. Correspondence to: Enric Ribera Borrell <rib- cra.borrell@aa
Lorenz Richter trichter@zii.der
1.1. Related work
Gradient based on-policy optimization in reinforcement learning has been pioneered by Sutton et al. (1999), where policy gradient theorem for infinite time horizons and
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Reinforcement Learning with Random Time Horizons
discrete state spaces has been suggested. In Silver et al. (2014) it has been extended to deterministic policies and continuous state-spaces, still in infinite time. In the seminal monograph from Sutton & Barto (2018) random runtimes are mentioned, however, not studied. To the best of our knowledge, the only work that studies trajectory-dependent random runtimes from Bojun (2020). However, it solely focuses on discrete state and action spaces and considers only stochastic policies, mostly relying on Markov chain theory for proving the statements. Our work, in contrast, operates in continuous spaces and adds formulas for deter- ministic policies. For further work on random time horizons in reinforcement learning, we refer to Mandal et al. (2023) and Chen et al. (2024), who, however, only study trajectory- independent stopping times.
2. Reinforcement learning with random time horizons
In the following we will formally introduce the reinforce- ment learning setting we consider in this article. Further details on the notation can be found in Appendix A. We consider the continuous state-space S C Rd and the contin- uous action space A C RR and define a time-discrete Markov decision process M AS, Po. p) on the probability space FP). Here the reward function In S A - R provides the signal that is received after be- ing in state Sn E S and having taken action An E A at time! n E N. The function po: : S + R20 represents the initial probability density of the states and p S S A - R20 is the time-homogeneous (state-action) transition probability density. To be more precise, let C S, then the probability of starting in a set A is given by
We further refer to Nota & Thomas (2020), who show that taking heuristic versions of policy gradients (e.g. dropping discount factors without motivation) might lead to wrong expressions and that in general one should be careful with employing algorithms that are not backed by theory. Also, we refer to White (2017), who unifies finite and infinite time horizons by introducing generalized (transition-based) discount factors, which might in principle be enhanced to random time problems.
/. po(s)ds
P(So E A)
(2)
and the probability of transitioning into the set A condi- tioned on being in state E S and having chosen action E A at time E N is given by
=0)==]]() ppss, (3)
P(S E S. = 8, An =0) =
I
Finally, we want to mention that random time horizons are more popular in stochastic optimal control settings, which consider deterministic policies and are typically stated in continuous time (Pham, 2009). We want to highlight Rib- era Borrell et al. (2024). who derive trajectory- bbsed gradi- ent estimators for random time optimal control problems. In fact, for discrete times, we can generalize their result to non- Gon-Gausiian transition densities. We refer to Lie (2021), who analyzes convexity properties of cost functionals with random stopping times, and to Zhou et al. (2021), who sug- gest an algorithm valid for random stopping times in optimal control that is inspired by the actor-critic method. Lastly, refer to Schütte et al. (2023) for random stopping time problems and related optimization methods in molecular dy- namics and to Quer& & Ribera Borrell (2024) who approach optimal control problems appearing in molecular dynamics applications with reinforcement learning techniques.
A policy is decision rule determining which action A, E A to take when being in state S, E S at time n E N. In this work, we consider stationary Markovian policies, i.e,, for every time step the decision rule is the same and the choice of the action at time n does not depend on the previous states So, . Sn of the trajectory. We distinguish between two types of policies:
A deterministic policy μ : S - is a function that directly maps each state to an action.
A stochastic policy т S + R2o is the probability density of taking an action in given state. To be more precise, let M C A, then the probability choose an action in M when being in state s E S is given by
1.2. Outline of the article
PAA,, E M | Sn =)= = π a(, a),a
(4)
In Section 2 we formally state the reinforcement learning setting allowing for random runtimes. Section 2. comments on taking either trajectory or state-space perspectives on this setting. Using both perspectives. we then derive policy gradient theorems incorporating random time horizons in Section 2.2. In Section 3 we compare our novel gradient formulas to classical formulas in numerical experiments. Finally, Section 4 concludes and provides an outlook for future research.
Remark 2.1 (Deterministic as stochastic policy). Formally, a deterministic policy il can be expressed as a stochastic policy via T(s, a) 0(((s) - a), where ò is the Dirac delta distribution. In the sequel, we will therefore often only refer to the stochastic policy л and only mention the deterministic policy μ explicitly when necessary.
IIn principle, the reward function can be explicitly time- dependent, however, for random time horizons one typically chooses it to time-independent.
2

---

Reinforcement Learning with Random Time Horizons
The goal in reinforcement learning is identify policies π that maximize the expected return (i.e. cumulative reward)
2.1. Trajectory vs. state-space perspective
As commonly done, let us in the following assume the re- ward function to be not explicitly time-dependent, i.e. we set Tn r. For the reinforcement learning problem defined above, we can consider two complementary perspectives, leading to different formulas and different implementations. We can either average the reward function (5) over trajecto- ries, such that the expectation is taken w.r.t. discrete path measures, or we can view the problem on a state-space level, not inherently incorporating any dynamics. Let us elaborate in the following.
N J(T) Ex Σ Enn(Sn: And
(5)
We note that the randomness of the return depends on the policy π and the densities po: p defined before. For nota- tional convenience, only the learnable is included in the subscript of the expectation operator (see Appendix A for more details). Typically, one either considers N to be fixed and deterministic or N = dc. In the latter case one has to discount the reward function, e.g. via (n(ss a) = 7 a), where y E (0,1) is a discount factor and r : S x A - IR not explicitly time-dependent. In this paper we general- ize this setting time horizons N that can be random. In practice, NN often depends on the (random) trajectory and is defined as the first time reaching predefined set of terminal states T C S, i.e.
Trajectory perspective. This viewpoint is the one described above, i.e., we consider trajectories (Sn, An) that evolve over time, given transition densities for the states and poli- cies for the actions.
State-space perspective. In this viewpoint we define the state-space density p" (sometimes also called on-policy distribution) the density of the process S under policy 9.. Recall that the density is independent of time since we consider stationary problems. It can be defined as follows. First, we define the function 0% s.t. for all C S it holds
N == min(n E N: Sn E TT.
(6)
We note that, due to the dependency on the trajectory, also depends on the policy æ. Throughout this paper, we assume that N is almost surely finite, i.e. P(N < xc) = 1.
J. (s) (S E EA,,
so it measures the probability of being in state at a given time" (to be even more precise, the above probability means Ia (S, E A) = (S, E A, n S N)). We can now define the state-space density as the probability of being in a certain state irrespective of the time via
Interestingly, as noted already in Derman (1970) (see also Chapter 5.3 in Puterman (2014)), the discounted infinite horizon case can be considered as a random time hori- zon problem². For convenience, we state the proof in Ap- pendix C.
Z B===/ {
Lemma 2.2 (Random time perspective on discounted infi- nite time problem). Let Nr be a geometrically distributed random variable with success probability 1 - 7, where y E (0,1). 1). Then, choosing N N.. and r' r in objec- tive (5) is equivalent to choosing N xo and r,, = yr.
:= Z
PT
(8)
n=0
In other words, pd measures the frequency of visiting a certain region at some point during the evolution of the tra- jectory and thus does not contain time information anymore. To make this observation more precise, the following lemma shows that the (unnormalized) function 17" defined in (8) can be interpreted as counting how often trajectories stay in certain regions of the space, see Appendix C for the proof. Lemma 2.3. For a set A C - it holds
A notable conclusion is that infinite time horizon problems can in fact be seen as problems that are finite with proba- bility one. To be precise, they can be interpreted as random time horizon problems where the trajectory can be arbitrarily long, however, (almost surely) not infinitely long. We note, however, that the equivalence only holds in expectation and numerical implications might have to be studied further, cf. Paternain (2018), Zhang et al. (2020) and Mandal et al. (2023).
f 11 = ET
Σ IA(
(9)
and in particular
*Markov decision processes with finite runtimes are often called episodic, whereas infinite time processes are called continu- ing. For the episodic case, some works include random, wheres some assume deterministic runtimes. However, computational consequences for random runtimes are typically not studied. We note, however, that due to the time-dependent reward func- tion, the starting time matters for infinite time horizon problems in this setting.
z / 17" (s)ds E& [N +1].
(10)
The state-space perspective is particularly prominent in re- inforcement learning since it readily allows for off-policy
*We assume that the process stops after steps.
3

---

Reinforcement Learning with Random Time Horizons
Trajectory perspective State-space perspective
For infinite time horizons, often the identity
J(T) = Sooff anot(
[r(s, a)]
(12)
Zero policy
is stated, where, in analogy to (8), 17 == 2 is called discounted state distribution, see e.g. Silver al. (2014). We note, however, that f7 is not density since it is not normalized, and the correct expression for the infinite time case would be
Optimal policy
(
E x-pa" [r(s, a)],
(13)
anat(s)))
where 7n is the normalized version of 1f", thus aligning with Lemma 2.2.
Remark 2.5 (Sampling from p²). While we call expecta- tions w.r.t. p" state-spacc-basee we note that typically, in order to approximate the expectations numerically, one still needs to simulate trajectories. However, at the same time, as mentioned before, the state-space perspective allows read- ily design off-policy learning strategies and to use replay buffers (cf. Degris et al. (2012)).
Figure 1. We illustrate trajectory and state-space perspectives the reinforcement learning problem. the left panel, we plot three trajectories that start at the black crosses, respectively, and run under the dynamics
until hitting the target set displayed that is governed by multi-well potential, see Section 3.3 for details. The right-hand hand side displays the corresponding state-space density p², defined in (8). In the first (deterministic) policy that only returns zero actions and in the second consider the (learnd) optimal policy according to the problem defined in Section 3.3.
choose the initial
2.2. Optimization and policy gradient theorems
The notorious question in reinforcement learning is how to optimize the expected return (5) w.r.t. the policy x (for stochastic policies) or w.r.t. the function μ (for deterministic policies). In practice, typically assume that parametrized by the parameter vector 0 E IRP and we may write To μ4o respectively. For ease of notation, we often omit the parameter dependence, however.
learning strategies, see, e.g., Degris et al. (2012); Mnih al. (2013); Lillicrap (2016). We refer Agarwal et al. (2022) for additional context on the state-space perspective in terms of so-called occupancy measures and refer to Figure for an illustration of trajectory and state-space perspectives.
μ
We can now state the state-space version of the expected return defined in (5), which has been derived in Theorem 4 in Bojun (2020) in discrete space setting.
A quantity that often appears in the context of optimization is the so-called Q-value function defined as the expected return conditioned on a state-action pair,
Proposition 2.4 (State-space expected return). Assuming P(N < xc) = 1, the expected return (5) can be written as
N
r( An) So So= =s, s, a d (14)
(= = ES
Σ
((T) E. -E IJ smp" [r(s, a)],
(11)
a<v)(s,))
We note that starting at n = 0 holds without loss of general- ity and one could also start at any other time, since the prob- lem time-autonomous, Further, one can define the value function (or relurn-lo-go) (*()) Eo-x((.-) [QT a)). We note that for the expected return (5) it holds J(T) Egpop [V* (s)] and refer to Appendix B for further details.
where n² is the state state-space density defined in (8).
Contrary to classical results, we note the appearance of the expected runtime in (11), acting as a scaling factor. Loosely speaking, with the change from the trajectory the state- space perspective
omits the dynamics and therefore the runtime information, and Proposition 2.4 shows the correct way of integrating this information back into the state-space perspective. We refer to Appendix C for the proof and to Remark C.1 for an alternative derivation, which might also bring some further intuition.
The following statement shows how one can compute gra- dients w.r.t. stochastic policies of expected returns that incorporate random stopping times. A proof can be found in Appendix C.

---

Reinforcement Learning with Random Time Horizons
Proposition 2.6 (Policy gradient). For the gradient of the expected return (5) it holds
to a different effective learning rale in stochastic gradient ascent. To be precise, let {r(K)}x be sequence of learning
rates, then we may update the parameters via
(OJ(TT)= = F.
Σ
Ve (S An)0 (Sns An)
g(k-1)= g(k) + + ( (TTw))
(19)
(15)
If we instead update
= =E I|
srup" (s,)
(s)
0(h-1) 1) = =0(h) + 7,0 [ (T
(20a)
(16)
-0(h) + +7(0) V (
(20b)
where p² is the state-space density defined in (8).
where
Vol VoJ/EX g(0)) [N +
(21)
We note that analogous to Section 2.1 Proposition 2.6 provides formulas following either trajectory perspective, stated in (15), or a state-space perspective, as in (16). For the former we note that a rigorous derivation for random time horizons has to the best of our knowledge not been conducted before Further, we note that, in contrast deter- ministic stopping times, one cannot simply apply automatic differentiation of the expected return w.r.t. the parameter 0 for optimization due to the policy-dependency of the run- time. However, our formula (15) suggests the alternative objective
is the (wrong) gradient with omitted scaling factor, then 7(k) = / [N + 1] is the effective learning rate relating to gradient ascent relying on the correct gradient. We note that this learning rate may substantially vary with changing expected runtimes in the course of the optimiza- tion and refer to Section 3 for experiments investigating its effect on the optimization performance. Importantly we note that previous policy gradient theorems have either stated the version without expected stopping time, i.e. have considered (21) for finite time scenarios, or only dealt with the infinite time horizon case (Sutton et al., 1999). Both cases lead to incorrect formulas when being applied to ran- dom time horizon problems.
N
(To, Ro) = End Σ
log (S,,
An) (Sn, An)
(17)
For the trajectory-based policy gradient estimator (15) we can additionally derive the following alternative versions, which might be advantageous from a computational perspec- tive and are proved in Appendix C.
which can be (auto- diffferetiree w.r.t 0, yielding (TT) when setting 0- after differentiation, i.e.
VaJett To; mo)l (T)(
(18)
Corollary 2.8 (Alternative trajectory- -aseed versions of the policy gradient). For the gradient of the expected return (5) it holds
(in practice we can simply detach Sn and An from the computational graph; for the analog reasoning in the state- space perspective see Appendix D). Further, we note that the state-space-basee formula (16) in fact also relies on trajectories due to the definition of the Q-value function in (14) it has already been stated in Bojun (2020) in a discrete space setting. To the best of our knowledge, the state-space formula continuous state setting is novel.
N Vo log na (Sn, An)
N Σ m00
VTJ(T) = BE
Σ -
r(Sm, Am)
(22)
E,
Va log no (Sn, An)
Er(Sm
r(S Am)
Am)
Remark 2.7 (Interpretation as effective learning rate). As for the expected return in Proposition 2.4, we note that the expected stopping time appears as a scaling factor in the caat--pacce-aasee policy gradient formula (16). While one could be tempted to argue that this acts only as a constant multiplicative factor that can be absorbed into the learning rate in gradient based optimization (as, e.g., argued in Sutton & Barto (2018)), we note that F,,[[N + 1] depends on the current policy and can therefore substantially vary during the course of optimization. Conversely, omitting the factor leads
0
(23)
Er
Σ
Ve log To (S,, (n) (S,, - b((,))
(24)
where b: S - R is an arbitrary function (sometimes called baseline).
For deterministic policies, the policy gradient takes a slightly different form, which we state in the following. We note that for infinite time horizons it has already been derived in Silver et al. (2014), however, we have not seen a formula for random time horizons before.
"In fact, assuming N to be deterministic yields the same trajectory-based formula as in (15) and it is remarkable that the dependency of N on и in the random stopping time case does not add any extra term.
5

---

Reinforcement Learning with Random Time Horizons
Proposition 2.9 (Policy gradient for deterministic policies). For the gradient of the expected return (5) it holds
compare trajectory and state-space based formulas and in- vestigate the effect of neglecting the factor F, [N 1] in the policy gradient (PG) computations. To be precise, for all our experiments we compute the gradient either with the trajectory-basee -based expression (15) (Irajectory PG), by the state-space expression (16) (state-space PG), or by the mod- ified state-space expression (21), which omits the scaling factor and is therefore. strictly speaking, an incorrect gra- dient (state-space PG (biased)). We refer to Remark 2.7 for interpreting this incorrect formula an effective learn- ing rate that changes over the course of optimization. Cru- cially, note that this effective learning rate is highly problem- specific and can not be controlled easily - this is an obvi- ous downside of the gradient (21). In order to assure fair comparisons, we first search for the optimal learning rate for each gradient approach in all of our experiments and use standard stochastic gradient ascent for optimization (in order to not have interacting effects with sophisticated op- timization methods). We refer to Algorithms 1-4 in Ap- pendix D for further computational details. The code can be found at https: //gps::/giiee git hub. com x wwweeerbbbreel.. rl aandoanddmm-e- times.
N
(HJ( 1pp
Σ
(SN) ( VuQ
(S.)
(25)
E,IN + Es [Vouo(s) VaQu [+)]
(26)
where p is the state-space density defined in (8) (with
deterministic instead of stochastic policy).
For the deterministic policy gradient we can further derive a version in the model-based setting, where we assume the knowledge of the transition density defined in (3).
Corollary 2.10 (Model-basse policy gradient for determin- istic policies). For the gradient of the expected return (5) it holds
N (SHo((s)
VoJ(po) = E1
n==
(27)
3.1. Modified continuous mountain car problem
+ (*(S log ((eppp(S1111
Sn. Snl
(=pp((s))
The mountain car problem is classical benchmark in rein- forcement learning, where the goal to reach the top of a mountain by leveraging gravitational energy additional to the car's acceleration (Singh & Sutton, 1996). We con- sider the state space S D pos x Dvel C R.2, where D pus = [-1.2, 0.6). Dvel = 0.07, 0.07] and the action space A = [-1,1 C R. The target set is defined as T = [0.45, 00) x R and the deterministic dynamics" is described via the function h S A - S, given by
= [ + +1
Vopu(s))(( (Far(s))
(Vrr(s,))
shgth (1 (118)
(28)
+ log (=mo(s)
We note that the alternative versions stated in (22) and (23) for stochastic policies hold for deterministic policies only in the model-based and not in the model-free case, see Corollary C.5 in the appendix.
o' = + + - 0.0025 cos(32), x' ='=
(29)
Remark 2.11 (Relation to stochastic optimal control). The rajectory-based formula (27) is equivalent the control cost gradient in stochastic optimal control problems, e.g. stated in Ribera Borrell et al. (2024), when using certain Gaussian transition densities, see also Remark C.4 in Ap- pendix C. We also note that in Quer & Ribera Borrell (2024) a version of (27) is heuristically derived after assuming N to be deterministic. To the best of our knowledge, the presented model-based policy gradient formula with ran- dom time horizons has not been proved in the discrete time setting yet.
where the state variable s (x,, T) has a position and velocity part. Compared to the typical problem, we consider trajectories that only stop when reaching the target set and make the problem slightly harder as we aim for reaching this goal quickly by integrating the runtime into the reward function,
{ -1 0.1a
if &
r(..
(30)
0 if SET.
We consider a Gaussian stochastic policy whose mean and covariance are given by feed-forward neural network with 3 layers and 32 hidden units per layer. We refer Ap- pendix E.2 for further details. In Figure 2 we compare the
3. Numerical experiments
In this section we compare the previously discussed gra- dient estimators on numerical examples. In particular, we
We think of the transition density defined in (3) Dirac delta distribution p(s', ,, a) = 8(8' Mx,a))-
We denote with Vona the Jacobian matrix of po.
6

---

Reinforcement Learning with Random Time Horizons
Negative expected return
Effective Jearning rate
Negative expected return
Negative expected return
Trajectoyy DG isund
Sace space 2G tbtaae with 5p21 specn 1m11
spoee
10:
Learning rate
1202 12k 2030 Computationl
3002 3293 5030
53800 20000 D200E diéce
30303
Cumputational
I063 2000 2230 2000 9020
Figure2 2. We display the performance of the three different policy gradients (PG) on the mountain car problem described in Section 3.1. In the left plot, the negative expected return is investigated for different learning rates, the different transparency values indicate different runs. For the performance plots, we always choose the best respective learning rate. The second plot shows the effective learning rates, see Remark 2.7 for an explanation (we always display moving average above the raw data). We see that for the biased methods, the effective learning rate increases significantly over the course of the optimization. The two plots on the right-hand side display the negative expected return- - once per gradient step and once per computational time (in minutes). We see that the PG formulas incorporating the expected hitting time perform significantly better. For the biased formula, the algorithm stops at some point duc to increased trajectory lengths and related memory issues.
three different policy gradient formulas and see that the ones incorporating the expected stopping time perform sig- nificantly better. This can be explained with the effective learning rate of the biased method, which increases signif- icantly during the optimization due to the change of the expected hitting times (from N x 10 to N z 10%). We highlight that this behavior is problem-specific and cannot be known priori.
3.3. Importance sampling of hitting times in molecular dynamics
Finally, we consider a problem that is relevant for the esti- mation of rare events in the context of molecular dynamics (Hartmann et al., 2017). The goal to identify deter- ministic policy that allows for the effective simulation of reaching target set T C S by shortening trajectories and reducing the variance of corresponding Monte Carlo estima- tors (Hartmann & Schüttee 2012). To this end, we consider d-dimensional state and action spaces S = A = Rd. a Gaussian transition density defined by
3.2. Two-joint robot arm (reacher)
The reacher environment contains a two-joint robot arm whose goal is to move its fingertip close to the target. It operates on continuous state and action spaces = [] x R c R2, A = [-1, c R22 The dynamics deterministic and the initial state sampled, see Towers et al. (2024) for details. Since the original reacher environ- ment is posed for infinite time horizons, we define the target set such that trajectories terminate if the positions 89, 810 of the fingertip are near the target and the angular velocities 87, S8 of the two arms are low enough,
P(. s, a) = N (s (a VU(s)) At, At (33)
where U : 12d R is a so-called potential function that is given by the specific problem and At >> 0 step size. The reward function is given by
At - 1
||l| 2
if $ T. if SET.
r(s,a) = 0
(34)
Intuitively, (34) can be interpreted aiming to minimize the runtime N, while keeping the actions small. This problem has already been studied with reinforcement learning meth- ods in Quer & Ribera Borrell (2024). In our experiments we consider (s)) = > (x,(,? 1)2, where ar quantifies the amount of metastability in the i-th dimension, as well as a = 22 and At = 10-2, -2 For the gradient computations we rely on the model- based formulas stated in Corollary 2.10.
T = {s E :: [|(,,, ss)ll $ 2, (((5p, s10)ll s 0.055. (31)
We consider the (slightly modified) reward function
r(s, a) { Woontrol |a|| if SÆT, SET,
(32)
We consider d 20 and choose 01 = 0:2 a; = 0.5. for i = {3, . 20} as well as T -- T d where
where Wcontrol = 0.1, again including penalty for long run- times as to motivate the robot to operate quickly, however, with small actions. We again consider a Gaussian stochastic policy, see Appendix E.3 for details. In Figure 3 we can see that our PG formulas lead to faster convergence compared to the classical (biased) formula.
= { 82) E S $1, 82 > (s) < 0.25], (35)
see also Figure for an illustration. As described above, we first search for a suitable learning rate for each approach. In the first panel in Figure 4 we plot the performance de- pendence on the learning rate. As expected, the trajectory
7

---

Reinforcement Learning with Random Time Horizons
Negative expected return
Effective learning rate
Negative expected return
Trajectory PG lours!
State-gane PG (ours)
State (Mased)
10
10
Trajectocy PG lours!
State space PG lours!
State space FC (biaaed)
10a
10
30
10
10 10
105 10-1
1000 1300
2009
1000 2000
Learning rabe
Computational time
Computational
Figure 3. We display the performance of the three different policy gradients (PG) on the reacher problem described in Section 3.2. As hefore, the left plot shows the performance w.r.t. to different learning rates, from which we choose the best learning rate for each method. the second plot we can see that the effective learning rate the biased state-space PG, which ignores expected hitting time, rather small at the beginning and increases over the course of the optimization. This then results in slower convergence to the optimal performance, as can be seen in the plot on the right-hand side.
Negative expected return
Effective learning rate
Negative expected return
Projectory (oum) Stato space DPG (ours) State DPG (stased)
10
10-4
101.
6x000
16-4"
19-4"
10-4
"io-=" "100
10-1
0
50
1:00
150
200
250
350
400
50
100
150
300
350
400
Learning rate
Computat aolputationall
Computational
Figure 4. We consider importance sampling of hitting times in molecular dynamics as described in Section 3.3 and compare the three different deterministic policy gradients (DPG). We display the performance depending on the learning rate as well as the effective learning rate and the negative expected return over the course of the optimization. We see that biased state-spaced PG converges more slowly compared to our DPG methods.
and state-space based gradient computations yield similar results they only differ due to statistical effects. The scaled state-space gradient, on the other hand, yields very different results. For each approach, we choose the optimal learn- ing rate. As noted in Remark 2.7, the scaled state-space approach has effective learning rate that depends the current expected stopping time. In the second panel we plot this quantity over the course of the optimization. Since the stopping times get shorter during the optimization, the effective learning rate increases. Consequently, this leads to slower optimization, since especially the beginning the effective learning rate is comparatively small, see the third panel. In fact, the formulas that incorporate the stop- ping time (and thus provide the correct gradient) converge roughly twice as fast.
performance improvements with the formulas we derived. We anticipate that our framework will allow to design ad- vanced optimization algorithms that cleverly integrate the random time dependency, potentially combined with off- policy algorithms, leading to further improvements on state- of- the-tar problems in the future. In particular, we envision integrations of our corrections for random time horizons into methods such as trust region policy optimization (Schulman et al., 2015) and proximal policy optimization (Schulman et al., 2017). Furthermore, we think that the connection of reinforcement learning to (stochastic) optimal control prob- lems studying e.g. continuous-ting perspectives (Wang et al., 2020), path space measures (Nüsken & Richter, 2021) or diffusion models (Berner et al., 2024) will be fruitful both for further theoretical insights and novel numerical algorithms.
4. Conclusion and outlook
In this work, we have suggested theoretical framework for reinforcement learning problems with random time horizons. In experiments, we have seen that the related (mostly novel) policy gradient formulas can lead to improved and accelerated performance. Crucially, we can explain those
8

---

Reinforcement Learning with Random Time Horizons
Acknowledgments
Lillicrap, T. Continuous control with deep reinforcement
learning. In International Conference Learning Rep- resentations, 2016.
The first author would like to thank A. Sikorski for his helpful insights on understanding the infinite horizon set- ting random time problem and previous fruitful discus- sions. This research has been partially funded by Deutsche Forschungseemeinschaaf (DFG) through grant CRC 1114 (Project No. 235221301) and under Germany's Excellence Strategy MATH+: Berlin Mathematics Research Center (EXC 2046/1, Project No. 390685689).
Mandal, D., Radanovic, G., Gan, J., Singla, A., and Ma- jumdar, R. Online reinforcement learning with uncertain episode lengths. Proceedings of the AAAI Conference on Artificial Intelligence, (7(7):9044-9077 2023.
Mnih. V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. Playing Atari with deep reinforcement learning, arXiv preprint 112.5522 2013.
Impact statement
The goal of this work is advance the theoretical under- standing of the field of reinforcement learning, leading to improvements in applications as well. While there are po- tential societal consequences of our work in principle, we do not see any concrete issues and thus believe that we do not specifically need to highlight any.
Nota, C. and Thomas, P. S. Is the policy gradient gradient? In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 939- 947, 2020.
Nüsken, N. and Richter, I.. Solving high-dimensional Hamiton--Jcobii-ellin PDEs using neural networks: perspectives from the theory of controlled diffusions and measures on path space. Partial differential equations and applications, 2(4):48, 2021.
References
Agarwal, A., Jiang, N., Kakade, M., and Sun, W. Rein- forcement Learning: Theory and Algorithms. 2022. URL https: fitts://rrthere http:///tthhhhoooooekeoo .artoookkiiittt tttthbiu......
Paternain, S. Stochastic control foundations of autonomous
behavior. University of Pennsylvania, 2018.
Berner, J., Richter, L., and Ullrich, K. An optimal con- trol perspective on diffusion-based generative modeling. Transactions Machine Learning Research, 2024.
Pham, H. Continuous-tinn stochastic control and optimiza- tion with financial applications, volume 61. Springer Science & Business Media, 2009.
Bojun, H. Steady state analysis of episodic reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 9335-9345, 2020.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & &oons, 2014.
Chen, S.-W., Ross, K., and Youssef, P. Finite-sammn sample anal- ysis of the Monte Carlo exploring starts algorithm for reinforcement learning. arXiv preprint arXiv:2410.02994, 2024.
Quer, J. and Ribera Borrell, E. Connecting stochastic op- timal control and reinforcement learning. Journal of Mathematical Physics, 65(8):083512, 2024.
Ribera Borrell, E.. Quer, J., Richter, L., and Schütte, C. Improving control based importance sampling strate- gies for metastable diffusions via adapted metadynamics. SIAM Journal on Scientific Computing, (6(2):5298-S322 2024.
Degris, T., White, M., and Sutton, R. S. Off-policy actor- critic. In International Conference on Machine Learning. PMLR, 2012.
Derman, C. Finite state Markovian decision processes. Academic Press, Inc., 1970.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International Con- ference on Machine Learning, pp. 1889-1897. PMLR, 2015.
Hartmann, C. and Schütte, C. Efficient rare event simulation by optimal nonequilibrium forcing. Journal of Statistical Mechanics: Theory and Experiment, 2012(1 1):P1 1004, 2012.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and
Hartmann, C., Richter, L., Schütte, C., and Zhang, W. Vari- ational characterization of free energy: Theory and algo- rithms. Entropy, 19(1 1):626, 2017.
Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Schütte, C., Klus, S., and Hartmann, C. Overcoming the timescale barrier in molecular dynamics: Transfer oper- ators, variational principles and machine learning. Acta Numerica, 32:517-673, 2023.
Lie, H. C. Fréchet derivatives of expected functionals of so- lutions to stochastic differential equations. arXiv preprint arXiv:2/06.09 /990000.99999... 2021.

---

Reinforcement Learning with Random Time Horizons
Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M. Deterministic policy gradient algorithms. In Proceedings of the 31st International Conference Machine Learning, Pp. 387-395. PMLR, 2014.
Singh, S. P. and Sutton, R. Reinforcement learning with replacing eligibility traces. Machine Learning, 22(1): 123-158, 1996.
Sutton, R. and Barto, A. G. Reinforcement learning: An introduction. A Bradford Book, 2018.
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.
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., Tan, H., and Younis, O. G. Gymnasium: standard interface for reinforcement learning environments, 2024.
Wang, H., Zariphopoulou, T., and Zhou, X. Y. Reinforce- ment learning in continuous time and space: A stochastic control approach. Journal of Machine Learning Research, 21(198):1-34, 2020.
White, M. Unifying task specification in reinforcement learning. In Proceedings of the 34th International Confer- ence on Machine Learning. volume 70, pp. 3742-3750 PMLR. 2017.
Zhang. K., Koppel, A., Zhu, H., and Basar, T. Global con- vergence policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimiza- tion, 58)):3386)66311, 2020.
Zhou, M., Han, J., and Lu, J. Actor-critic method for high di- Jacobi-Bellmal Bellman partial differ- ential equations based on neural networks. SIAM Journal on Scientific Computing, 4304)) 2021.
mensional static Hamilton Jacobi-
10

---

Reinforcement Learning with Random Time Horizons
A. Notation and setting
As stated Section 2, we denote with .M = (S,A, Tn. Po, P) a time-discrete Markov decision process, where S C Rd. the state space, AA IR is the action space, In the reward function, Po is the initial probability density of the states (defined in (2)) and p is the time-homogeneous (state-action) transition density (defined in (3)). Further, we consider the stochastic policy or the deterministic policy μ.. The dynamics of the Markov decision process is defined via So Po as well as An (SSn:)) and S p(,,Sn. An) for each ni E {O..... N 1}, and we call the resulting set a (state) trajectory.
{So, Ag, $1, A1....... SN} } state-action trajectory and
For the expectation operator we write E, if the random variables the expectation depend on the policy я,, however note that the randomness not only depends on n, but also on the initial density po and the transition density p. i.e. for function pp : (S A)N S + and random variables So, .o, SN. and for fixed N, we write
Fx (sp(S, Ao...., ,N]]
[w]]= =
Epo.p. (pp(So, , SN.)..,SN)
(36a)
NN-1
SSSAAK po(30)
πI
(8n, an (n)p((s+4 8n, an) dogdao
(36b)
==0
In our work, the stopping N is typically considered to be random, so the expectation is also over N, i.e.
7 (p Ag..... ....... Sy]] Eoo.p.n,N Ip(So, SN):
(37a)
P(N m) /
mm1
[(SXA)mxS po(so)
II n=
(sn an an)p(sn+1, sn an) dsgdoo ...
(37b)
where (PN m) is the probability of N having the value and the convention IT (r), 1. This probability is typically dependent on the dynamics, and therefore the policy, and is thus unknown. For deterministic policies we write E,, (even though S + A is deterministic function). Also, note that for state-space expectations stated e.g. in (11) we write E. 8-pT [-] to denote Be- [Ban((s))]l]] an.)(s,))
Further, we assume that π are parametrized by the parameter vector e RR, and we may interchangeably write л = To or /4 = PAg for ease notation. We write Vo to denote the gradient w.r.t. the parameter vector 0 and for any 8 E we write V (o)o(s) to denote the Jacobian matrix of f w.r.t.
B. Additional background on reinforcement learning
Let us consider the (state-action) reward function" rn S x A + R and recall that it provides the signal that is received after being in state S, E S and having taken action A, A at time E N. In our work we consider a time-independent reward function and we denote it by r. We define the return (from step n onward) by
G
Σ r(Sms Am)
(38)
m=n
and denote Go by the (initial) return. We define the expected (initial) return (sometimes also called objective function) as
N
= = E& Σ ((S
(39)
We note that starting at n = 0 holds without loss of generality and one could also start at any other time, since the problem tume-autonomous. Further, we can define the value function (or return-to-go) as the expected return conditioned on starting state E S,
N Σ
:=
r(Sn. An) So
(40)
===
'In principle, the reward function can also depend following next state.

---

Reinforcement Learning with Random Time Horizons
We further condition applying the action A, and define the so-called Q-value function
(= E Σ (S An) So =s, A.
(41)
We note that it holds J(x) Ep VV (s) and (*()) (a 1Qt a)). For all expressions we have the Bellman equation", e.g.
N r(S,, Ao) + Σ
(TT) E,
r(Sn:
An) An)
(42a)
n=1
E,
r(So. Ao) + Ex
Σ
r(Sn A1
(42b)
E, (r Au) (V)()
(42c)
Analogously, it holds for all s T
("(() Fr [r(So, Ao) (S))ss s]
(43a)
/ a(s,a) (r(s,a)+ + / ( da,
(43b)
and
sb (= = r((, + E, (15 = A =
(44a)
= + | pl5.,, / =(d','')Q"' ,'', d'dd''ss
(44b)
For deterministic policies the above equations reduce to
V*(s) rsss (()) + E, (V ("
(45a)
= (((s + / p(s' (()))
(45b)
and
a") = =)(s,a)
= A, = aa
(46a)
=r(s,a)+ / s.''' ((s((ss)))ss
(46b)
=r(s,a)+ + / pls' (ls
(46c)
Further, note that control theory the value function denotes the optimal cost-to-go, i.e. the optimal value of the cost functional w.r.t. all possible controls. In contrast, in reinforcement learning the term value function is used for any arbitrary policy. If the policy is optimal it is called optimal value function.
In practice, one often chooses _N,,, o² Id), for which μ and a are learnable functions. We note that with a approaching the zero function r + 0, i.c. with reducing the stochasticity of the stochastic policy, π approaches a Dirac distribution and therefore a deterministic policy, see also Remark 2.1 in the main text and Theorem in Silver et al. (2014).
C. Proofs and additional statements
Proof of Lemma 2.2. First note the following re-ordering of sums, containing the sequences {ashe and (by h It holds that
Σ a:
by
lim
a;
Σ b
lim
b;
Σ a:
b
a:.
(47)
1-000
+000
j=
j=0
Note that for the infinite time horizon case the value function is scaled by the discount factor 7.
12

---

Reinforcement Learning with Random Time Horizons
Assuming that Ny G1 7) with 7 (0, 1), have that P(N, =m) (1 7) and compute
F
Σ n=0
Snn And
F.N,,
FF
Σ
r(Sn:
And
(48a)
m==
8
m
P(N, m E
Σ
r(Sn An)
(48b)
8
oc r(S An -7) Σ ym
E
(48c)
E
(S An)
(48d)
where we used the tower property in the first line, the fact that Nr does not depend on the policy in (48b) and identity (47)
in (48c). We can further check that
P(N, = 00)= lim (N = m) lim m=-00
7'1(1 - O. m-000
(49)
Proof of Lemma 2.3. Recalling the definitions (7) and (8),
J (s)dds Px(S, E A);
17"
n
(50)
n=0
we compute
J Σ
/
(s)dds
Σ
(S EA) = Σ En [1A(S,)] = E,
Σ
1 (Sa)
= F
Σ ===0
N
1 (Sa))
n=0
n=0
==0
kn=0
(51)
Further, we note that choosing A = S yields
( 17 (s)ds= (s)ds= [x]]
7
(52)
Proof of Proposition 2.4. Let us first define the n-step transition function (s 8) via
/ (s,''' s)ds' = =P, (S, E A = s).
(53)
Note that we have
| s)ds' = P- (S,, E S|S, 3) P. (S,, E S,n & NIS, =) = (n < N =)
(54)
13

---

Reinforcement Learning with Random Time Horizons
so it is only a density conditioned on the fact that n N. We can compute
8
Σ r(S
An)
( An)
(55a)
r(s, (1
(55b)
n=0
1 / r(s,a)T(s,,)
Σ
p 8) po 8) d5 da
(55c)
n=0
/ / r(s,,))((s,)) Σ (s) da
(55d)
/ / r(s, ((s,a)((s,a)) a)) (s) da
(55e)
[. + 1| s~p" [r(s,a)], a~))
(551)
where in the last line we used
[ 17" (s)ds = p p= [N + 1]
1"=
(56)
via definition (8) and Lemma 2.3. Note that the sum in (55b) switches from a sum until the (potentially random) time N to an infinite sum since the transition probability P. defined in (54) encodes not only the states, but also a potential stopping of corresponding trajectories and thus encodes the potential randomness of N.
Remark C.1 (Alternative derivation of state-space expected return). The state-space based formula for the expected return stated in Proposition 2.4 can also be derived as follows. The trajectory- based formula
J(T) =F Er,T
Σ (S An)
(57)
stated in (5), can be approximated by K trajectories via
1 K ((
Σ Σ r(S
1()),
(58)
K
noting that each trajectory has a different length, namely NT()) - 1 steps in the k-th trajectory. We note that we can consider the particles
K (k)
B B:
U
A00
(59)
as an unbiased sample from the action-state-space density p² (s)T(s,,)) a), defined in (8). Let us merge the two indices the elements of B and write
M
B=
U
(m)
A(m]
(60)
m=1
noting that M = Ek (NT()) + 1)..
We can now write the sample estimator of the trajectory-based expected return (58) as
1
K
((S())
A(
1
Σ ((S(m)
M
K
Σ ((5(m)
A(m))
(61)
K
K
M
Now, noting that M/K converges E, N 1] for K + oo by the law of large numbers, we conclude that (61) converges to the state-space expected return
J(T) IN expT [r(s,a)),
(62)
a~J((;))
as stated (11).
14

---

Reinforcement Learning with Random Time Horizons
Lemma C.2 (Unrolling for stochastic policies). For any 2 1 it holds that
Σ pi((s / FoTols',a) a ds' + pi pi Vo (s')dd''
VoV*
(63)
n=0
Proof. For the sake of notational convenience, let us define the shorthand notation
( == (oTo(s,a)Q*(
(64)
We prove Lemma C.2 via induction over Let us start by the initial case I 1. Recalling that V*((s) (s 1Q" we can compute
(8)
/ (VoTo(s,a) + (30 da
VoV V (8)
(65a)
/ ho(s, no(s, To(s,a)Vo r(s,a)+
p(s' a)) )aa da
(65b)
ho(s, S no((,a) / ( (s')d'da A
(65c)
= / ho(s,a)da+
(65d)
where we use the Bellman equation stated (44) and where of is defined in (53). The expression (65) coincides with (63) for Let us now assume that (63) holds for We can compute
VoV = Σ
s)) .)) / hols', a))a + V)
(66a)
==
Σ piils' is) /f hols' adda (i- (f hols' ( / ("""", ds'
(66b)
pi((s',)) 8) / a)) + ()) ("
(66c)
ss) ss) / hols' a))a + (
(66d)
where we have used (65) in the second line. Since (66d) conincides with (63) have proved the statement by induction.
Proof of Proposition 2.6. We assume that the gradient of the value function with respect to the policy parameters is bounded, i.e., for any 0 TRP there exists an L.g > 0 such that
sup
VoV S Lo.
(67)
Then it holds
lim
V pi ())l. (s')llds' < lim To P1 $ N S, = s) = 1-000
(68)
by assumption of the (potentially random, but almost surely finite) time N. In the limit + co, the expression from Lemma C.2 therefore turns into
VoV*(s) - Σ
(H(s''8)
"omols',a)'" (s, (s)aadddd''
(69)
n=
15

---

Reinforcement Learning with Random Time Horizons
Further, can compute
VoJ(mo) / (oTT)) = po(sa) Σ
/ (s,,
Pi, 80)
(70a)
==
[ (s(()) /
(70b)
FIN + 1] / 1r (0(() TT(s. 7e add
(70c)
EIN + 1]
smpp"
[ (oologmo(s.0)007..00
(70d)
where we have again used
17" p== (n (
""ss)ds=p"'E: p= E, 1]
(71)
via definition (8) and Lemma 2.3. Finally, by choosing! 10 r(s,a) Vo log as) in Proposition 2.4 and using
identity (70), we readily get
N
VoJ(TO)) = ET
V log no (S,, A,) 12 (S,, (S,, An)
(72)
Proof of Comollary 2.8. We first note that for an arbitrary function yp: (8 x A) - IR it holds
N
By (s((S: Ao...., An, S,)a"
An)
E
(S Ao: Ao..... Ans Spy
Σ
r(S Am) Say An
(73a)
Ex
E
((S0, Ao..., An Sn)
Σ r r(Sm; Am)
(73b)
m=n
N Σ
F
(So, Ao.... Any Sn)
r(Sm, Am)
(73c)
=1=
where we used the tower property, the fact that (So, .o...., Sn, An) is F, measurabll and the Markov property. Equality (23) now follows from choosing ((So, ,o,., An) = V log TT Sn,, An) and summing over n. For this choice we can even show that
N
F Vo TS,, AN)QT An) = E Vo log rt (Sn, An)
Σ r(Sm: Am) ===
(74)
which implies (22). This can be seen by defining the n-step transition function p..(s', s, a), analogy (53), via
J p ( s, =Px (S, e A/So Ao a)
(75)
and noting that for < n it holds
(Vo log x (Sn, An (S Am)
(76a)
[ J [ Pm (m((m)T (8mm am (8mm mm; am (p)) 1 88n,8m;
Sm, am V log (8n, (T domd
(76b)
[ Pm Pm(sm))(e (smm and (5m) am P% Sya am) (/ Vo (sn an an) (s an dan, ds da de
(76c)
0
10 Note that Proposition 2.4 holds for any arbitrary function r: S A RR
16

---

Reinforcement Learning with Random Time Horizons
since
Ve log (8n,, an) ( an dan Va / T(Ens an)dan 0.
(77)
We can readily prove (24) in the state-space perspective by noting that
(T)( = / (s)
/ (o add = S 1((() J
b(s))ds
(78)
since
/ (o) b() Vo no(s, ()(s,a)da- =
(79)
Then, by choosing as),a) Vo log no (8, (V)) in Proposition 2.4, arrive (24) in the trajectory- based perspective.
Lemma C.3 (Unrolling for deterministic policies), For any 1 2 1 it holds that
ds' + ( (f VVV VoV*(s) = Σ s Vo a=ma(ss) n=0
1-1
(80)
Proof. The proof of the unrolling lemma for deterministic policies follows the same idea as for stochastic policies stated in Lemma C.2. In analogy to (53), let define the n-step transition function ph 5 via
J, pi s)ds' Pp (S,, S s).
(81)
As before, let us first consider 1. Recalling the Bellman equation, V²(s) = r(s, + E2 [V"(St) = s). stated already in (45), we can compute
(s) = Vo (r(s
p(s', s, (o
(82a)
= VeHo(s) Var(s, a=po(s)
(82b)
1 (pl5,s,no(())VVo44(1 VeHo(s) Vap(s', va(s') ds'
a=mo(s)
VoHo(s) V. ((8,))+ pls' p (a=a((s)
(82c)
1 pls Vo
= (o)o(s) VaQ"(s, a=po(s) + 11046)))0000700000
(82d)
For notational convenience, let us define
(o((s) = VoNo(s) (VNN(s))(QQ"ssaa)) a=
(83)
For the induction step, we can then compute
1-2
VoV"(s)= = Σ , s) + (i (po(6)) + / VVV"" do
(84a)
Σ (s', s)po(s')ds' + 1 (s (s" (o"""""
(84b)
Σ s)poss) + pf(s's VVo
(84c)
where we used (82) the first line.
17

---

Reinforcement Learning with Random Time Horizons
Proof of Proposition 2.9. The proof is analog the one of Proposition 2.6. First, we that in the limit of / - oc, the second summand of (80) vanishes. We can then compute
Voo() / Po(50) Vo (
(85a)
| Po(50) Σ (s, 80) Vopu(s) (o.
(otNooo)))V/V((((s____ a=
ds dso
(85b)
/ ( (s,"(s (c)
ds
(85c)
EN + E Vona(s) Vapo(s)VVa("(( (s (=mo(S)
(85d)
where we have used
1f" ="=0² x") / 1*
(86)
via definition (8) and Lemma 2.3 (however, replacing the stochastic policy æ with the deterministic policy p). Finally, by (=)m((()) in the deterministic policy version of Proposition 2.4 and using identity
choosing r(s; a) Vopa(s) (85d), we readily get
Vx,"(s, Vopoos))Va.((.,,))))))
E
Σ
(oND(Sn)
"VQut a)
(87)
(=
Proof of Corollary 2.10. Using the Bellman equation (46), we can compute
VoQ"(s,o) = Var(s,a) + Js (
(88a)
Var(s,a)+ [ Valogp(s' 8, a))p((' s.)) (s)))'
(88b)
()) + -xrp((aa.) Va V.logp(''s.. a,))
(88c)
Using Proposition 2.9, we get
N
(oJ()))) = E2
(V. VaQ"" a)
(89a)
a=po(Sh))
E2
(oHo((S)) (Var(SVv + E Ba'ppissaaa Va Vologp(s Sn, an)))(((s))) (=
(89b)
Fp
(oHo(S
(Var(( Eno [V. (. (m=po(sa)
(89c)
E2
Σ (SHH)(S))
(Var(V V. So a))"
(89d)
l==no(8m)
where we used the tower property in the last line. The second equality follows from plugging in (88) into the second equation of Proposition 2.9.
Remark C.4 (Connection to stochastic optimal control gradient). From Corollary 2.10 we can recover the gradient estimator of stochastic optimal control problems with random stopping times, as for instance stated in Corollary 3.3 in Ribera Borrell et al. (2024). To this end, we realize that the continuous time SDE
dx (b + ap) (X di dW.)
(90)
18

---

Reinforcement Learning with Random Time Horizons
where W is standard Brownian motion, b Rd R2 arbitrary drift and Rd Rdxd is the diffusion matrix, be discretized via the Fuler-Maruyama scheme
Sn+1 = + (b + (S.
(91)
with step size At and Gaussian increment Eu+1 ~ W(O,Td). Calling the terminal time NAt, the continuous control costs
J(m) EE [ ( (+ 1 =11l111)) (X dt +
(92)
correspond to r(s,a) = (f(s) + ||a|3)) At 17 (s) g(s) (s)) in the discrete setting (5) and we can thus compute
(ar(s, - aas LTc(s))
(93)
Va logop(Sn+:: Sn. o (S.) (Sn+1 (S, + oa) (S,) En+1 Vat.
(94)
We can therefore see that (27) from Corollary 2.10 corresponds to the time-discretized version of Corollary 3.3 in Rib- era Borrell et al. (2024). We highlight that a derivation in discrete time including random stopping times has not been rigorously done before (ef. Hartmann & Schüitte (2012), where it has been conjectured that the formula is inexact due to the random time).
Corollary C,5 (Alternative trajectory-bast based versions of the model-basee policy gradient for deterministic policies). For the gradient of the expected return (5) holds
VOJ(HO) EN
V (Sp) (Var(Sn.)))))
Σ
r(Sm. uo (ossss
a=po(Ss))
(95)
m=U
EN
Σ (oHH(( (Var(S)) a))
Σ m=n+1
r(Sm: no (S.))) Va Sn; (=pp(ts))
(96)
E2
(S.)
Va a=po((s) - b(Ss))
(97)
where b: S an iantitt (sometimes called baseline).
Proof of Corollary C.S. The proof of the alternative versions of the deterministic policy gradient follows the same idea as for stochastic policies stated in Corollary 2.8.
We first note that for an arbitrary function &o S R. holds
N Σ im=n+1
Ep
r(Sm, ((Sm)) Say An
(98a)
Fpp
Fy
Snt1)
Σ
r r(Sm (5nn)(((m))
(98b)
m=n+1
N
= F ,S
Σ r(Sm ((
(98c)
m=n+1
where we used the tower property, the fact that S(S.....,,.t. is Fats-ruauuabbll and the Markov property. Equality (96) now follows from choosing .......,,+)] = (S,) T TV, log Dog((S,,) (S0SS111550 Sn, a)) Ia-potss)) For this choice we can even show that
F2 Vopl(Sa)) (S*+((tt)V log la-po(s))
N = E2 (S Σ
(99)
r(Sm (o (og Sn, (mmpos_-
m=
19

---

Reinforcement Learning with Random Time Horizons
which implies (95). This can be by using the n-step transition function (s', ss,())), which is stated in Corollary 2.8 for stochastic policies, here denoted by ph (s', s), well by noting that for < n + it holds
E [ (oolo(Sn) (r(m::rsmmmm (o(Sm)) log Io Sn. a) (a-po(sw)
(100a)
/ J Pm (mm)))((mm)) (m Dr (sns 8m Vol((sn) T p ( Sn,) Va Sn
8n) a=)a==( ds ds,
(100b)
| Pm (emm Vou((()) ( (8 logr(sut 8n; a) lazaten) dss+1 dömds
(100c)
since for any tuple (s', s, E ESX XxXSx it holds that
[ V logglp'' s.)
Vap(s',s,a)ds = V. p(d',
(101)
We can readily prove (97) in the state-space perspective by noting that
(oJ(H)) = -So (5) (V.
( (s. a) (s=m)) ds 1/" ((" Va(Q"(ssa)) - -((s) (s ds. (102)
By choosing r(s,a) a) r(s, (o()) Vouo(s)V.(("(s.0) -(()))s))))(bs)lll.. b(s))la=mo(6) Proposition 2.4 we arrive at (97) in trajectory-baste based perspective.
D. Computational details
In this section we provide computational details that are necessary for the numerical approximation of the gradients discussed in the main part.
For policy gradients of stochastic policies we consider non-actor-critic approaches where the Q-value function is estimated, but not learned. The alternative objectives corresponding to the trajectory PG stated in (22) and to the state-space PG stated in (16) are given by
N
N Σ r(S Am) m==
J (TO, (e) ; Ex
Σ
log To (S., An)
(103)
Jatate Jatate(Te, ;= Ex [N
1] E s a~aa(s.)
[log mo a)
(104)
We refer to Algorithms and for implementational details.
For policy gradients of deterministic policies we consider non-actor-erite approaches as well. Recall that this is possible due the -bdeld formulas provided in (27) and (95). Moreover, we have assumed that the state-action probability density is Gaussian and is motivated by controlled SDE (see Remark C.4), The corresponding alternative objectives are given by
jeral (Ho. pa) Epp Σ nS (S,) (
r(Sm pio No (5m) At
(105)
Jot Jetate (Ho pa) E [N
E snip"> 8 Vappta (-,8)
(Var(s, Vuo (s') V
(106)
We refer to Algorithms 3 and 4 for implementational details and note that algorithm Algorithm 3 is already sketched in Quer & Ribera Borrell (2024).
E. Experimental details and additional experiments
In this section we provide further details on the numerical examples presented in Section
20

---

Reinforcement Learning with Random Time Horizons
Algorithm Trajectory Policy Gradient (REINFORCE with random time horizon).
1: Initialize stochastic policy %o with random parameters.
2: Choose a gradient based optimization algorithm, a learning rate X, sample size K, and a stopping criterion.
3: repeat
4: Simulate samples of trajectories following the policy тæ. where the k-th trajectory has runtime N(
5: Estimate alternative objective stated in (103) and compute the gradient via automatic differentiation
N(
NCCR
1
log ne (5
(
Σ
r(s
A
off
6: Update policy network parameters based the optimization algorithm. until stopping criterion is fulfilled.
7:
Algorithm 2 State-space Policy Gradient.
1: Initialize stochastic policy Ne with random parameters.
2: Choose gradient based optimization algorithm, learning rate X, a sample size K for the trajectories, a sample size M for the experiences and stopping criterion.
3: repeat
4: Simulate samples of trajectories following the policy ne, where the k-th trajectory has runtime N(k)
5: Compute estimate 2" ΣK (T(k)
6: for each time step n do
7: Compute return G -m=n
r(sh) (k) and store the tuple (5% Al (K(k) in memory.
8: Sample M experiences from memory (S(m), A(m) G(m)) Jm=1 where ((m), A(m) are unbiased samples from pM
and TTS(m),)) -), respectively, and ((m) estimates (S((m), A(m)).
9:
Estimate alternative objective stated in (104) and compute the gradient via automatic differentiation
Jatate 7.
log (5(m)) (((m)
.
10: Update policy network parameters based on the optimization algorithm.
11:
Empty memory.
12:
until stopping criterion is fulfilled.
Algorithm Trajectory and model-based Deterministic Policy Gradient.
1: Initialize deterministic policy μ4 with random parameters.
2: Choose a gradient based optimization algorithm, a learning rate X, a sample size K, and a stopping criterion.
3: repeat
4: Simulate samples of trajectories following the policy pi.
5: Estimate alternative objective stated in (105) and compute the gradient via automatic differentiation
(A) Σ n=0
(ar(((()) ())) ()) + Σ . ( ) ( SHAAvar)
jinaj
(T
K
k=1
6: Update the parameters 0 based on the optimization algorithm.
7: until stopping criterion is fulfilled.
21

---

Reinforcement Learning with Random Time Horizons
Algorithm 4 State-space and model-based Deterministic Policy Gradient.
1: Initialize deterministic policy di with random parameters.
2: Choose a gradient based optimization algorithm, a learning rate X, a sample size for the trajectories, a sample size M for the experiences and stopping criterion.
3: repeat
4: Simulate K' trajectories following the policy A4 and store them in memory.
5: Compute estimate 2 = K E N(R) 1.
6: for each time step n. do
7: Compute return G Σm m rSm (o((S)))) and store the tuple (Sh ((k) (lk) s Sn+1 G in memory.
8: Sample M experiences from memory (S(m), S (m)) ((m)) ) where ((m) is unbiased sample from p",
((m)) (V,O,dd) and ((m) estimates V (5((m)))
9: Estimate alternative objective Jell given in (106) and compute the gradient via automatic differentiation
1 Jalate- ²u M
Σ (o(Smm))
(V .a) ()la=no(Stmn) + ((m) A
10: Update policy network parameters based the optimization algorithm.
11: Empty memory.
12:
until stopping criterion is fulfilled.
E.1. Architecture of the neural networks
Let din, dout E N+ be the input and output dimensions of the feed-forward network ypo Rdn -> Rdduut defined by
(o( = Pout
p(A10 + b1) ...) + bL-1) + bz),
(107)
where L is the number of layers do = din dz = dout. A E [d and by E Rd < S L are the weights and the bias vectors for each layer and p. Pout R + R are the inner and outer nonlinear activation functions applied componentwise. The collection of matrices A and vectors by contains the learnable parameters 0 E R.. For all the experiments we choose the inner and outer activation functions p tanh and Pout ld if not otherwise stated.
For the stochastic policy experiments described in Sections 3.1 and 3.2 consider Gaussian stochastic policy ITs. N (n((s, o² (s) Td), for which 1 and a are learnable functions represented by two 7. = 3 layer feed-forwart neural networks sharing the first L = 2 layers (a so-called two-head neural network). To guarantee that o² ld is positive definite, the final activation function of the corresponding neural network is chosen as Pont = x + II.
To ensure that the initial output of the networks is close to zero, the final layer weights and biases are initialized by sampling from the uniform distribution (1--5 3 10-3 x 10 10-3). We also note that each experiment requires only one CPU core, and the maximum value of allocated memory is set 64 GB.
E.2. Modified continuous mountain car problem
For the experiment described in Section 3.1 we consider a Gaussian stochastic policy for which μ and a are represented
by two-head neural network (see details in Appendix E.1) with L layers and di d2 32 units. We compare the three different policy gradient formulas by implementing Algorithm (trajectory PG), Algorithm 2 (state-space PG) and Algorithm 2 without estimating the -a-factor (state-space PG unbiased) for a batch of K = 100 trajectories, batch of experiences containing all the information in the memory (M = 100% of the memory size), and we stop the optimization algorithm after -= 5 x 1 gradient iterations. The best performing learning rates for each gradient approach are Auraj = Astate = 10 4 A biased = 5 x 10 respectively. Note that for biased > 10 the optimization algorithm fails due to high instabilities which lead long trajectories and hence exceed the allowed allocated memory.
10-4,
E.3. Two-joint robot arm (reacher)
For the experiment described in Section 3.2 we consider a Gaussian stochastic policy with L 3 layers and d1 = dg = 32 units and compare the performance of Algorithm (trajectory PG), Algorithm (state-space PG), and Algorithm 2 without
22

---

Reinforcement Learning with Random Time Horizons
estimating the 2" -f-tor (stale-space PG unbiased) for K 100 trajectories, M 100% of experiences in memory, and 10 gradient iterations. The best performing learning rates for each gradient approach are Aeraj Astate 5 10-1 biased 5 10-2 respectively.
state
E.4. Importance sampling of hitting times in molecular dynamics
For the experiment described in Section 3.3 consider deterministic policy represented by neural network with L 2 layers and dj = 32. We compare the three different model-basee policy gradient formulas for deterministic policies by implementing Algorithm& 3 (trajectory DPG), Algorithm 4 (state-space DPG) and Algorithm 4 without estimating the -fctoo (state-space DPG unbiased) for = 500 trajectories, M 100% of experiences in memory, and / 5 x 10
gradient iterations. The best performing learning rates for each gradient approach are Acraj = Astate 2 x 10 3 biased state
10-1, respectively.
23


Reviews:
[{"review_id": "zq4rTUgvMA", "reviewer": "Reviewer_aYkS", "summary": "This paper considers a more realistic setting of reinforcement learning when the time horizon is random rather than fixed finite or infinite. The authors extend the RL to incorporate random time horizons and present the expected returns under the random time horizon from both trajectory-based and state space based perspectives.  The author also present the corresponding gradient descent theorems for both cases with rigorous theoretical proofs. Multiple numerical experiments are presented to show the importance of using the proposed GD strategy when the time horizon is not fixed in real applications.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review. We are happy that you value our \"clear theoretical advances\", addressing \"the gap between the standard formulation and the real application\", thus leading to a \"valuable contribution to the field of reinforcement learning\".\n\nThanks for asking for more comprehensive empirical evaluations. First, note that we have already chosen examples that exhibit highly variable time horizons. This can be seen by the \"effective learning rates\" in Figures 2 - 4, which directly correspond to the current expected stopping times, see equation (21). For the rebuttal, we furthermore ran the *Hopper* environment, see https://tinyurl.com/mtxcnudu. One can see similar advantages of our gradient estimator compared to the standard one. Note also that in all experiments we can achieve major speed-ups compared to the standard policy gradient (time reductions of 60-80%) as well as improved convergence (see Section 3).\n\nYour comment regarding clearer guidelines for practical implementation is a good one. First, we want to refer to Appendix D, where we already stated computational details and implementation guidelines - see in particular Algorithms 1 - 4. If space permits, we will move one of the algorithm environments to the main part. Further, note that Appendix E contains details on the conducted experiments, in particular stating the used hyperparameters. In the revised version, we will make both appendices even more verbose and add further details. We will also release our code (which is already added to this submission). Please let us know if you have further suggestions and we would be happy to incorporate them.\n\nThank you for pointing out that a comparison to more advanced RL algorithms would be interesting - this is valuable feedback for us. You mention that PPO and TRPO already have mechanisms for handling variable-length episodes. We politely disagree, as those methods explicitly operate on finite and fixed or infinte time horizons. We would prefer the interpretation that PPO and TPRO somehow fix potential issues with too large step sizes that potentially originate from the \"incorrect\" gradient scaling, by considering trust regions or by employing clipping. Our attempt, on the other hand, is principled and provides the correct gradient scaling by design, cf. Remark 2.7. In fact, in our experiments it turns out that the \"incorrect\" scaling factor can be off from the \"correct\" one by orders of magnitude, see the \"effective learning rate\" e.g. in Figures 2 - 4.\n\nTRPO aims to maximize the expected reward, while making sure that in each gradient step $ \\mathbb{E} [\\operatorname{KL}( \\widetilde{\\pi}(\\cdot, s)  | \\pi(\\cdot, s)) ] \\le \\delta$ holds, $\\widetilde{\\pi}$ is the old policy, so the policy is not changed too much. In practice, the constrained optimization is typically conducted with conjugate gradient algorithms and line searches, where a linear approximation of the expected reward and a quadratic approximation of the constrain is employed. This results in\n$$\\widetilde{G}^{(k)} := {(H^{-1})}^{(k)} G^{(k)},$$\n\nwhere $G^{(k)}$ is the policy gradient and $H^{(k)}$ is the Hessian of the estimated KL divergence. One then considers the update\n\n$$\\theta^{(k+1)}=\\theta^{(k)}+\\alpha^{(k)} \\sqrt{\\frac{2 \\delta}{\\widetilde{G}^{(k)} \\cdot H^{(k)} \\widetilde{G}^{(k)}}} \\widetilde{G}^{(k)},$$\n\nwhere $\\alpha^{(k)} > 0$ can be found via line search. In the setting of random time horizons, TRPO uses the \"incorrect\" gradient estimator $G^{(k)}$, however, the scaling and the \"line searching\" of the step size may cure potentially bad choices. One can readily replace $G^{(k)}$ with our novel formulas that give the \"correct\" gradient. We anticipate that this should further improve the performance of TRPO, however, due to the limited time in the rebuttal, we need to leave experiments for the next weeks. We will try to incorporate them in the final version of the paper, thus being able to better contextualize the practical implications within contemporary RL research.\n\nPPO makes even further approximations and considers the loss\n$$ \\mathcal{L}(\\pi) = \\mathbb{E}\\left[\\min \\left( \\log \\pi (a, s) A, \\mathrm{clip}\\left(\\log \\pi(a, s), 1-\\varepsilon, 1 + \\varepsilon \\right) A \\right) \\right], $$\n\nwhere $A$ is the advantage function and $\\varepsilon > 0$ is a hyperparameter. Also here, we can incoporate the findings of our novel gradient estimator, by adding the scaling factor $\\mathbb{E}[N + 1]$ to \"fix\" the \"incorrect\" gradient estimators, cf. Propositions 2.4 and 2.6.\n\nFinally, we note that in Section 3 we compared the vanilla gradient estimators on purpose in order to properly study the effect of the random time horizons on the (novel) \"correct\" and (typically used) \"incorrect\" gradient formulas and in order to exclude confounding effects.\n\nYou further ask for a comparison against RL algorithms that have strategies for handling variable time horizons. Could you please let us know which ones you have in mind?", "claims_and_evidence": "Yes, this paper is generally well-supported by both theoretical analysis and empirical results. The theorems are presented with clear description and rigorous proofs in the appendix. In addition, the experiments presented with real world applications support the claimed statement.", "methods_and_evaluation_criteria": "Yes, the proposed method is to address the gap between the standard formulation and the real application. Under the random time horizon assumption, the proposed method incorporate the randomness into the gradient calculation makes sense to me.", "theoretical_claims": "Yes, I read most parts of the proofs provided in the appendix. They looks correct to me. The authors are thorough in their derivations and clearly state their assumptions.", "experimental_designs_or_analyses": "Both experiment setups in the paper are relatively simple RL tasks. While these setups do demonstrate the idea, they may not fully capture the challenges of real-world applications with random time horizons. \n\nThe selected baseline line in the paper is the standard policy gradient algorithm. I think the similar approach can be applied to other algorithm directly. And comparison against more advance RL algorithm that have strategies for handling variable time horizons are needed to support the claims of the paper.", "relation_to_broader_scientific_literature": "The paper makes clear theoretical advances but could better contextualize its practical implications within contemporary RL research.", "essential_references_not_discussed": "No, I am not aware of any.", "other_strengths_and_weaknesses": "Overall, the paper presents theoretical analysis and shows promising empirical results. Its main strengths lie in its originality and theoretical rigor. However, it could be improved by providing more comprehensive empirical evaluations and clearer guidelines for practical implementation. Despite these limitations, the work represents a valuable contribution to the field of reinforcement learning, particularly in handling the important and often overlooked aspect of random time horizons.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "1.Could you elaborate on how your approach compares to modern RL algorithms (like PPO, TRPO) that already have mechanisms for handling variable-length episodes? \n2.Have you tested the approach on more complex environments with highly variable time horizons? Results from such environments would help demonstrate the method's scalability and practical utility.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MglcFWciuH", "reviewer": "Reviewer_TpCt", "summary": "In this paper, the authors consider the problem of undiscounted, random horizon RL.  In this setting, a learner is attempting to optimize the cumulative reward of a policy interacting with an MDP such that the horizon, $N$, is a possibly random stopping time adapted to the filtration of the episode thus far.  The authors develop formalism involving such MDPs from both a trajectory and state-space based perspective.  The authors proceed to prove a number of basic results about this setting before focusing on computing policy gradients to aid in RL.  They then interpret the difference between the true policy gradient and the standard computation using reinforce but ignoring the random horizon as a rescaling of the learning rate.\n\nThe authors then conduct a number of empirical investigations of their gradient computation as compared to that which ignores the random horizon in a modified mountain car environment, a reacher environment, and a problem in molecular dynamics.  The authors demonstrate that their approach improves significantly on that which ignores the random horizon.\n\n\n####\n\nThe authors answered my questions and I maintain my initial (positive) score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer TpCt. Thank you very much for your educated review. We are happy that you conclude that our contribution is closing an important gap in reinforcement learning and we appreciate that you value our numerical benchmarks as appropriate.\n\n\n\nThank you also for raising the aspect of time-independent densities, leading to stationarity, which you spotted very well. In our paper we consider expected cumulative rewards of the form \n\n$$ J(\\pi) = \\mathbb E_\\pi \\left[  \\sum\\limits_{n=0}^N r(S_n, A_n) \\right], $$\n\nwhere $N$ is a random stopping time, i.e. $N = \\min(n \\in \\mathbb{N}: S_n \\in \\mathcal{T})$, and where $\\mathcal{T}$ is some target set. In this setting the stationarity assumption is natural and we will highlight this more in the revised version of the paper. We could, however, replace $N$ with $\\min(N, N_\\mathrm{max})$, where $N_\\mathrm{max} \\in \\mathbb{N}$ is a fixed value. This would in fact lead to time-dependend state densities as well as policies that are explicitly time-dependent. Our theory should still go through, however, would be notationaly more challenging and slighly change proof details and formulas. For instance, the value function would also be time-dependent in this case. Since the time-dependent case is typically less prominent in applications, we decided to focus on the time-independent case in our paper. We will, however, comment on this subtle issue in the revised version of the paper and thank you again for the comment.\n\n(Also note that in time-continuous (stochastic) optimal control theory time-independent problems correspond to elliptic partial differential equations, whereas time-dependent problems correspond to parabolic partial differential equations, leading to slightly different assumptions and to slightly modified algorithms.)\n\nPlease do not hesitate to ask further questions, we would be happy to answer them.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "I think the benchmarks do make sense.  They are clearly chosen so as to introduce random stopping times in a natural way and all three are fairly standard proofs of concept in RL, especially the first two.", "theoretical_claims": "I did check the theoretical claims and, while somewhat basic, they are correct.", "experimental_designs_or_analyses": "I did not spend as much time perusing the precise experimental setup in the supplementary section, but from my reading of the main body's discussion of the experiments, it seems reasonable to me.", "relation_to_broader_scientific_literature": "There has been quite a lot of prior work on policy gradient methods in a number of directions and they are of course fundamental to modern empirical RL pipelines.  This paper observes that there is a gap in the prior work in that it does not rigorously address the question of how such methods should change when the horizon is random as opposed to deterministically finite or infinite.  This is an important gap in cases where the horizon can vary quite a bit because the horizon itself can depend on the policy.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "I think the paper overall clearly presents an important correction to prior policy gradient methods in settings where the horizon can vary in policy-dependent ways.  One weakness is the emphasis on stationarity, which is necessary for the state-dependent perspective to be time-invariant.  I wonder how reasonable this is as an assumption and the extent to which it can be removed?  I also think that a more clear discussion of this assumption could be included as I only realized that this was essential in lines 130-131 from the parenthetical clause.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g4KXhOk6Or", "reviewer": "Reviewer_WigC", "summary": "The paper derives the policy gradient theorem for the setting where the MDP horizon is random (and typically policy dependent). Algorithmically, the \"corrected\" PG boils down to the standard PG with a multiplicative factor correction for the expected horizon length.\n\nNumerical experiments are carried in two environments (continuous mountain car, reacher, hitting times in molecular\ndynamics), demonstrating a certain advantage of the corrected PG computation (to the extent permitted by these experiments).\n\n## update after rebuttal\nI appreciate the rebuttal by the authors, however my main concern remains that the scope of this work sums up to a relatively straightforward extension to the policy gradient theorem. As a result I choose to maintain my initial rating.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer WigC. We thank you very much for your careful review and are happy that you - similar to the other reviewers - think our \"corrected\" policy gradient in principle \"has merit\" and adds a meaningful contribution to the reinforcement learning community. We want to highlight that - compared to the standard policy gradient - the added multiplicative factor can indeed vary substantially over the course of the optimization, see the \"effective learning rates\" e.g. in Figures 2 - 4 and also Remark 2.7. This not only leads to small improvements, but to major speed-ups (time reductions of 60-80%) as well as to improved convergence in our experiments (see Section 3).\n\nThank you for your comment regarding PPO - this is very valuable in order to better position our achievements in the context of the algorithms that are most commonly used in practice. We believe that our novel formulas can also be applied to PPO and other advanced algorithms, however, in the short time of the rebuttal phase, we could not run experiments yet. But let us make the theoretical agrument.\n\nPPO builds on TRPO, which aims to maximize the expected reward, while making sure that in each gradient step $ \\mathbb{E} [\\operatorname{KL}( \\widetilde{\\pi}(\\cdot, s)  | \\pi(\\cdot, s)) ] \\le \\delta$ holds, $\\widetilde{\\pi}$ is the old policy, i.e. the policy is not changed too much. In practice, the constrained optimization is typically conducted with conjugate gradient algorithms and line searches, where a linear approximation of the expected reward and a quadratic approximation of the constrain is employed. This then results in\n$$\\widetilde{G}^{(k)} := {(H^{-1})}^{(k)} G^{(k)},$$\n\nwhere $G^{(k)}$ is the policy gradient and $H^{(k)}$ is the Hessian of the estimated KL divergence. One then considers the update\n\n$$\\theta^{(k+1)}=\\theta^{(k)}+\\alpha^{(k)} \\sqrt{\\frac{2 \\delta}{\\widetilde{G}^{(k)} \\cdot H^{(k)} \\widetilde{G}^{(k)}}} \\widetilde{G}^{(k)},$$\n\nwhere a good value for $\\alpha^{(k)} > 0$ can be found via line search. In the setting of random time horizons, the TRPO algorithm uses the \"incorrect\" gradient estimator $G^{(k)}$, however, the scaling and the \"line searching\" of the step size may cure potentially bad choices. One can readily replace $G^{(k)}$ with our novel formulas that give the \"correct\" gradient in random time horizon settings. We anticipate that this should further improve the performance of TRPO, however, due to the limited time in the rebuttal, we need to leave experiments for the next weeks. We will, however, incorporate them in the final version of the paper, thus being able to better contextualize the practical implications within contemporary RL research.\n\nPPO makes even further approximations/simplifications and considers the loss\n$$ \\mathcal{L}(\\pi) = \\mathbb{E}\\left[\\min \\left( \\log \\pi (a, s) A, \\mathrm{clip}\\left(\\log \\pi(a, s), 1-\\varepsilon, 1 + \\varepsilon \\right) A \\right) \\right], $$\n\nwhere $A$ is the advantage function and $\\varepsilon > 0$ is a hyperparameter. Also here, we can incoporate the findings of our novel gradient estimator, by adding the scaling factor $\\mathbb{E}[N + 1]$ to \"fix\" the \"incorrect\" gradient estimators, cf. Propositions 2.4 and 2.6.\n\nFinally, we note that in Section 3 we compared the vanilla gradient estimators on purpose in order to properly study the effect of the random time horizons on the (novel) \"correct\" and (typically used) \"incorrect\" gradient formulas and in order to exclude confounding effects.\n\nAdditional comments:\n\n - Thank you for pointing out Agarwal et al., 2019, as a good reference. We will add it to the revised version upon acceptance.\n - *\"More challenging environments.\"* For the rebuttal, we ran the *Hopper* environment, see https://tinyurl.com/mtxcnudu. One can see similar advantages of our gradient estimator compared to the standard one.\n - *\"Arbitrarily fixed number of iterations.\"* We chose the number of iterations such that all algorithms converge.\n - *\"Didn't find how many seeds were used in the experiments, standard errors of the results.\"* The experiments were run for three different seeds. Notice that in the left plot of Fig. 2-4 the transparency values indicate different seeds. Observe consistent behavior, see, e.g., https://tinyurl.com/3r3y6bxm. We will add more elaborate plots (e.g. containing standard deviations) in the final version.\n - We agree that we state some known facts in the introduction, however, we would like to keep this since our results and story line heavily depends on concepts such as occupancy measures. Also, we think that certain connections between random time horizons and existing approaches (e.g. Lemma 2.2) are not well known within the community. In case we will have space issues, we will however consider shortening the introduction - thanks for this helpful advice!\n\nIf you have any further questions or concerns, please let us know. Otherwise we would be happy if you consider reevaluating our contribution. Thank you very much!", "claims_and_evidence": "The theoretical claims are, the experiments are quite minimal.\n\nThey show an advantage of corrected PG in a very limited experimental setup (just three environments, arbitrarily fixed number of iterations, etc.). I didn't find how many seeds were used in the experiments, standard errors of the results, etc.\n\nIn any case, I believe the corrected PG expression has merit regardless of the experiments. However, if it does not make a great difference in practice, this should also be discussed and it is currently unclear due to the minimal experimental setup.", "methods_and_evaluation_criteria": "The theoretical arguments are clear and make sense. The experimental setup is limited.", "theoretical_claims": "I went over proof of Proposition 2.6 and Lemma C.2, they look ok.", "experimental_designs_or_analyses": "I looked at both experiments, didn't find any particular issues, except for the limited setup.", "relation_to_broader_scientific_literature": "Yes, the relevant PG papers Sutton et al. 99 and Silver et al. 2014 are mentioned.\n\nOther related works are mentioned in the introduction.", "essential_references_not_discussed": "I think citing the Agarwal et el. 2019 (RL Theory Book) could provide some additional context on basic matters (for example, the state space perspective is prevalent in the theory of RL, these are called occupancy measures).\n\nAgarwal, A., Jiang, N., Kakade, S. M., & Sun, W. (2019). Reinforcement learning: Theory and algorithms.", "other_strengths_and_weaknesses": "### Strengths\n\n* The paper points to the fact that vanilla policy gradients are \"incorrect\" for random time horizons in the sense that there is a normalization factor missing from their expressions, that is non constant over training. This means that the effective step size used by a vanilla PG algorithm changes over the course of training, which is generally undesirable when not intended.\n\n### Weaknesses\n\n* The technical contribution here is quite minimal in terms of RL theory, and the experiments are very scarce. In particular, vanilla PGs are rarely used in practice. I would be more curious to see if this observation has an effect on more modern policy optimization algorithms such as PPO, and in more challenging environments.\n\n* The paper goes through a rather elaborate exposition of well known facts; e.g., the state-space perspective (known as occupancy measures), Figure 1, and Lemma 2.3 (indeed, adapted to the random horizon setup, but still).\n\n\nThe bottom line is that while I feel random time horizons and their consequence on PGs and PO algorithms in general should be considered more carefully in applied RL, there isn't sufficient substance in this paper for publication as is.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses a particular RL setting where the time horizon is a random variable which is common in practice (and especially in LLMs) but poorly studied. In particular, the authors provide corrections to the formulation of the policy gradient that take this specific setting into account. Experiments show that making this correction impacts positively the performance on a set of simple RL benchmarks. 

The reviewers appreciated the significance of the problem addressed, which is a more realistic setup for reinforcement learning. They also appreciated the rigor of the methodology. 

Several concerns were raised, including the simplicity of the experimental setup, which was considered somewhat toy-ish. The most significant concern relates to a potential lack of novelty. The modification introduced to the policy gradient computation was regarded as relatively straightforward. 

This paper may open the path for a more systematic study of this specific setup which relatively common in practice, which seems to be a good contribution to the community.
Decision: Accept (poster)