Reinforcement Learning with Random Time Horizons

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).

Thank 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.

PPO 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 $\widetilde{G}^{(k)} := {(H^{-1})}^{(k)} G^{(k)},$

where $G^{(k)}$ is the policy gradient and $H^{(k)}$ is the Hessian of the estimated KL divergence. One then considers the update

$\theta^{(k+1)}=\theta^{(k)}+\alpha^{(k)} \sqrt{\frac{2 \delta}{\widetilde{G}^{(k)} \cdot H^{(k)} \widetilde{G}^{(k)}}} \widetilde{G}^{(k)},$

where 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.

PPO makes even further approximations/simplifications and considers the loss $\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],$

where $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.

Finally, 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.

Additional comments:

• Thank you for pointing out Agarwal et al., 2019, as a good reference. We will add it to the revised version upon acceptance.
• "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.
• "Arbitrarily fixed number of iterations." We chose the number of iterations such that all algorithms converge.
• "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.
• 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!

If 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!

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".

Thanks 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).

Your 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.

Thank 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.

TRPO 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 $\widetilde{G}^{(k)} := {(H^{-1})}^{(k)} G^{(k)},$

where $G^{(k)}$ is the policy gradient and $H^{(k)}$ is the Hessian of the estimated KL divergence. One then considers the update

$\theta^{(k+1)}=\theta^{(k)}+\alpha^{(k)} \sqrt{\frac{2 \delta}{\widetilde{G}^{(k)} \cdot H^{(k)} \widetilde{G}^{(k)}}} \widetilde{G}^{(k)},$

where $\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.

PPO makes even further approximations and considers the loss $\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],$

where $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.

Finally, 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.

You 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?

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.

Thank 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

$J(\pi) = \mathbb E_\pi \left[ \sum\limits_{n=0}^N r(S_n, A_n) \right],$

where $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.

(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.)

Please do not hesitate to ask further questions, we would be happy to answer them.