In policy gradient methods why do we compute the gradient of the objective function through a one-trajectory estimate?

Question

Taking as an example the Advantage Actor Critic, the objective function is: \begin{equation} \nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta})=\mathbb{E}_{\tau \sim \pi_{\boldsymbol{\theta}}}\left[\sum_{t=0}^T \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}\left(a_t \mid s_t\right)A^{\pi, \gamma}(s_t, a_t)\right], \end{equation} where $A^{\pi, \gamma}(s_t, a_t) = Q^{\pi, \gamma}(s_t, a_t) - V^{\pi, \gamma}(s_t)$ is the advantage function.

In principle in order to compute the gradient we should collect many trajectories and take the average of the desired quantity (which is what REINFORCE does). I guess that computing many trajectory is very costly, and indeed in Actor-Critic-like algorithms, such gradient is estimated by sampling just one trajectory (the policy is updated after every episode).

I understand that we exploit baselines in order to reduce variance for better estimates but I would like to understand why the one-trajectory sample is a good estimator of $\nabla_{\theta}J(\theta)$. Are there any rigorous references about this?

Answer 1

The one-trajectory sample is the Monte-Carlo way to estimate the gradient, which, turns out, to be an unbiased estimator although with high-variance due to relying only on one sample: I think this is proven in the Sutton's RL book. Unbiased means that it converges (in the limit of infinite experience) to the true gradient, which is something good but the high-variance makes everything more difficult, slow and ustable.

To reduce the variance people usually use a baseline, but you can also have parallel environments, which should be uncorrelated (i.e., initialized all differently), allowing you to collect a batch of trajectories that you can average on to reduce a bit the noise due to the stochastic nature of the agent-environment interaction.

There are also combinations of ideas from both MC and TD learning that allow you to trade the bias for the variance, for example by truncating the trajectory early (to reduce variance) and then bootstrapping (which introduces bias.)

Answer 2

Sutton & Barto's book of Reinforcement Learning mentions below:

When the state-value function is used to assess actions in this way it is called a critic, and the overall policy-gradient method is termed an actor–critic method. Note that the bias in the gradient estimate is not due to bootstrapping as such; the actor would be biased even if the critic was learned by a Monte Carlo method... The natural state-value-function learning method to pair with this is semi-gradient TD(0).

Thus this inherent bias in actor-critic algo using one-trajectory sample during every episode to update both its actor's and critic's parameters at every step (see page 332 for its algo detail) faces the same convergence issue as any TD boostrapping learning algo whose convergence is a theoretical result from stochastic approximation methods as discussed here and the relevant source in the same reference is summarized below. So long as the advantage function as approximated by the difference of the one-step return and the current state value as the baseline (both values are from the same critic) converges to their true values just like TD state values learning, the policy actor and critic parameters would optimize the policy's performance metric per the policy gradient theorem.

converges with probability 1 to an optimal policy and action-value function, under the usual conditions on the step sizes (2.7), as long as all state–action pairs are visited an infinite number of times and the policy converges in the limit to the greedy policy... but not for the case of constant step-size parameter, $α_n(a)=α$. In the latter case, the second condition is not met, indicating that the estimates never completely converge but continue to vary in response to the most recently received rewards. As we mentioned above, this is actually desirable in a nonstationary environment, and problems that are effectively nonstationary are the most common in reinforcement learning.

Therefore actor-critic algo usually needs tons of data for training in order to approximately satisfy above convergence conditions, yet it's often superior mainly due to substantially reduced variance.