PPO when does the update happen?

Question

In many places, it says PPO and Actor-Critic methods in general use TD-updates, but in the loss function for PPO, the Value function loss component uses the difference between output of the value function and the value target, which I can only assume is the discounted sum of rewards that can only be obtained at the END of the episode?

So this might be a moment of stupidity for me, but

1. Is the value target in PPO set only at the end of the episode using the discounted sum of rewards? or is there a secret way of setting these value targets that I am missing?

2. If a learning update indeed takes place every learning step (before the end of the episode), then how does this TD-learning happen - does it use some other approximate of the value target?

Thank you. Please help.

Sincerely, a frustrated student

Answer 1

Updated response to include more information from the discussion.

Monte Carlo vs. Temporal Difference (TD)

Let's start with the distinction between these two. When you have a sequence of rewards observed from the environment and a neural network predicting the value of each state, then you can create target values that your predictions should move closer to in a couple of ways. You can look at the full episode and use the actual observed rewards with discounting to create your target, this is called the Monte Carlo estimation. This target value is an estimation of the value function from your initial state.

$$ \widehat v_\pi(s_0) = y^{MC} = r_1 + \gamma r_2 + \gamma^2 r_3 + \cdot\cdot\cdot + \gamma^{T-1}r_T $$

Then, you update the NN parameters to get better at predicting the value of the state based on this estimate. Another way is to update your neural network sooner by only using a partial trajectory (of length $k$) and rely on your NN to estimate the rest of the trajectory.

$$ \widehat v(s_0) = y^{TD} = r_1 + \gamma r_2 + \gamma^2 r_3 + \cdot\cdot\cdot + \gamma^{k-1} r_k + \gamma^k \widehat v(s_k) $$

The last term uses the NN to estimate the remaining discounted rewards from the episode without observing it.

Proximal Policy Optimisation

You don't need to wait until the end of an episode to receive rewards. If you have access to intermediate rewards, then you can update the value network sooner. PPO uses the advantage function when calculating the objective (and the loss) which is also done similarly to the TD approach. Both the n-step and the Generalised Advantage Estimation relies on the NN to fill in some of the unobserved values.

Original paper on PPO gives a nice description of the algorithm (the version with clipping the probability ratio is probably easier to understand): Proximal Policy Optimization Algorithms (Schulman et al., 2017)

OpenAI has a good description of general policy gradient algorithms and PPO as well, it's worth checking out.

Answer 2

So the loss function that you want to optimize to improve your policy is given by:

$$ L^{CLIP} = \mathbb{E} \Big[ \frac{\pi_\theta (a|s)}{\pi_{\theta_{old}}(a|s)} \Big( R(s,a) - V_\phi(s) \Big) \Big]. $$

And to improve the value network you optimize a squared-error loss between the output of your value network and the return:

$$ L^{VF} = 0.5\Big(V_\phi(s) - R(s,a)\Big)^2.$$

And really the question is: How do you compute the return $R(s,a)$?

If you use a Monte-Carlo estimate of the return, i.e. $$ R(s_t,a_t) = \sum_{i=t}^{T} r_{i+1},$$ well, then you have to rollout the episode until a terminal state is reached. Only then you can calculate the returns for each state that was visited during the rollout, and update the policy and the value networks.

If, instead, you use a one-step bootstrapped estimate (also called TD), i.e. $$ R(s_t,a_t) = r_{t+1} + V_\phi(s_{t+1}),$$ then you can actually update the networks after every single step.

What is usually done in practice is to use an n-step bootstrapped estimate: $$ R(s_t, a_t) = r_{t+1} + r_{t+2} + \cdots + r_{t+n} + V(s_{t+n}).$$ Now you rollout $n$ steps and then you update.

Even better than the n-step bootstrapped estimate would be to use the Generalized Advantage Estimate (GAE).

If you want to read more about all of these please check out:
https://pi-tau.github.io/posts/actor-critic/