Unbiased Policy Gradient with Random Horizon

Policy gradients for discounted reinforcement learning target rewards arbitrarily far into the future, while practical rollouts stop after finitely many steps. We address the resulting gradient bias by sampling the rollout horizon from a geometric distribution. The resulting unbiased policy gradient (UPG) estimators include new GPOMDP variants and existing random-horizon estimators. Their sampling complexity removes a logarithmic factor in accuracy from the corresponding vanilla policy-gradient bound. Longer expected rollouts reduce the second-moment bound, making trajectory length and estimator variance joint determinants of sampling cost.

The horizon enters the gradient

We consider a Markov decision process with bounded rewards $|r(s,a)|\leq r_{\max}$, initial-state distribution $\rho$, discount $\gamma\in(0,1)$, and differentiable policy $\pi_\theta$. For trajectories $\tau$ sampled under $\pi_\theta$, write $r_t=r(s_t,a_t)$. The objective and its GPOMDP gradient representation are

$$\begin{aligned} J(\theta)&=\mathbb E_\tau \left[\sum_{t=0}^{\infty}\gamma^t r_t\right],\\ v_t&=\sum_{t'=0}^{t}\nabla\log\pi_\theta(a_{t'}\mid s_{t'}),\\ G(\theta)&=\nabla J(\theta) =\mathbb E_\tau\left[\sum_{t=0}^{\infty}\gamma^t r_t v_t\right]. \end{aligned}$$

The vector $v_t$ accumulates policy scores through time $t$. A fixed truncation horizon drops the remaining reward-score terms and introduces bias. Increasing that horizon reduces the error while increasing sampling cost. We instead encode the discount in an independent stopping rule.

Geometric stopping yields unbiased GPOMDP

Sample $H-1\sim\operatorname{Geom}(1-\gamma)$ on the nonnegative integers, then accumulate undiscounted rewards and scores:

$$\begin{aligned} \Pr(H>t)&=\gamma^t,\qquad \mathbb E[H]=\frac{1}{1-\gamma},\\ \widehat G_{\mathrm{UGPOMDP}}(\theta) &=\sum_{t=0}^{H-1}r_t v_t,\\ \mathbb E[\widehat G_{\mathrm{UGPOMDP}}(\theta)]&=G(\theta). \end{aligned}$$

Each time-$t$ term survives with exactly its original discount weight. Every rollout is finite almost surely, and arbitrarily late rewards remain represented across samples. At each step, we update the score accumulator and add the current reward times that accumulator to the gradient estimate. Independent trajectory estimates can then be averaged into a batch.

Splitting discounting between rewards and survival

The broader $\alpha$-UPG family allocates discounting between the stopping distribution and explicit reward weights. For $\alpha\in[0,1)$, its GPOMDP estimator is

$$\begin{aligned} H-1&\sim\operatorname{Geom}(1-\gamma^{1-\alpha}),\\ \widehat G_{\alpha\text{-}\mathrm{UGPOMDP}}(\theta) &=\sum_{t=0}^{H-1}\gamma^{\alpha t}r_t v_t,\\ \mathbb E[H]&=\frac{1}{1-\gamma^{1-\alpha}}. \end{aligned}$$

Multiplying the survival probability $\gamma^{(1-\alpha)t}$ by $\gamma^{\alpha t}$ recovers $\gamma^t$, preserving the same gradient expectation. At $\alpha=0$ we recover UGPOMDP. Increasing $\alpha$ lengthens the expected rollout; the theoretical second-moment bound decreases. We also derive an action-value branch, $\alpha$-QPGT, containing Q-PGT at $\alpha=0$ and RPG at $\alpha=1/2$. These branches provide a common framework for comparing existing and new estimators.

Sampling cost depends on variance and horizon

For a smooth objective $J$, unbiasedness permits a stochastic-gradient convergence analysis under an expected-smoothness bound on the estimator's second moment. Uniform bounds on the policy's expected squared score and expected log-policy Hessian norm yield an explicit second-moment bound $\nu$. Choosing the batch size and constant step size according to these bounds gives

$$\begin{aligned} \mathbb E\|\nabla J(\theta_U)\|^2&\leq\epsilon^2,\\ N&=\mathcal O\!\left( \frac{L\nu\,[J^\star-J(\theta^{(0)})]\,\mathbb E[H]}{\epsilon^4} \right). \end{aligned}$$

Here $\theta_U$ is a uniformly sampled iterate, $\theta^{(0)}$ is the initial policy parameter, and $J^\star=\sup_\theta J(\theta)$ is the optimal objective value. The tolerance $\epsilon$ measures first-order stationarity, $L$ is the objective's smoothness constant, and $N$ counts expected environment samples. For fixed problem constants the accuracy dependence is $\mathcal O(\epsilon^{-4})$, removing the truncation-related logarithmic factor in the vanilla comparison. Choosing $\alpha$ therefore requires considering $\nu\mathbb E[H]$: the smallest second-moment bound occurs with longer rollouts. For UGPOMDP, the sampling bound scales as $\mathcal O((1-\gamma)^{-6}\epsilon^{-4})$.

Discounted return in control benchmarks

We evaluate two-hidden-layer policies with 64 units and Tanh activations, using softmax outputs for discrete actions and Gaussian outputs for continuous actions. The main comparison averages 10 runs with 95% confidence intervals. Both UGPOMDP and $0.5$-UGPOMDP outperform GPOMDP on CartPole, LunarLander, Acrobot, and Pendulum. We use $\gamma=0.99$ for the first three and $0.95$ for Pendulum, with training batches of 64 trajectories. The preferred $\alpha$ varies across environments; $0.75$ performs poorly on Acrobot and best among the tested settings on Pendulum.

We also compare the number of environment interactions and repeat the GPOMDP baseline with twice its truncation horizon to examine how discounted return depends on sampling cost. These experiments use Adam and nonlinear neural policies; the convergence bound applies to stochastic-gradient updates under the assumptions above. In terminating environments, the treatment of terminal states can change gradient estimates, particularly for Q-PGT and RPG, and must preserve the reward and stopping weights used in the unbiasedness calculation.