Temporal Difference learning
Temporal difference
The main drawback of Monte Carlo methods is that the task must be composed of finite episodes. Not only is it not always possible, but value updates have to wait for the end of the episode, what slows learning down.
Temporal difference methods simply replace the actual return obtained after a state or an action, by an estimation composed of the reward immediately received plus the value of the next state or action:
R_t \approx r(s, a, s') + \gamma \, V^\pi(s')
As seen in Section Dynamic programming, this comes from the simple relationship R_t = r_{t+1} + \gamma \, R_{t+1}.
This gives us the following update rule for the value of a state:
V(s) \leftarrow V(s) + \alpha (r(s, a, s') + \gamma \, V(s') - V(s))
The quantity:
\delta = r(s, a, s') + \gamma \, V(s') - V(s)
is called the reward-prediction error (RPE), TD error, or 1-step advantage: it defines the surprise between the current expected return (V(s)) and its sampled target value, estimated as the immediate reward plus the expected return in the next state.
- If \delta > 0, the transition was positively surprising: one obtains more reward or lands in a better state than expected. The initial state or action was actually underrated, so its estimated value must be increased.
- If \delta < 0, the transition was negatively surprising. The initial state or action was overrated, its value must be decreased.
- If \delta = 0, the transition was fully predicted: one obtains as much reward as expected, so the values should stay as they are.
The main advantage of this learning method is that the update of the V-value can be applied immediately after a transition: no need to wait until the end of an episode, or even to have episodes at all: this is called online learning and allows very fast learning from single transitions. The main drawback is that the updates depend on other estimates, which are initially wrong: it will take a while before all estimates are correct.
A similar TD update rule can be defined for the Q-values:
Q(s, a) \leftarrow Q(s, a) + \alpha (r(s, a, s') + \gamma \, Q(s', a') - Q(s, a))
When learning Q-values directly, the question is which next action a' should be used in the update rule: the action that will actually be taken for the next transition (defined by \pi(s', a')), or the greedy action (a^* = \text{argmax}_a Q(s', a)). This relates to the on-policy / off-policy distinction already seen for MC methods.
SARSA
On-policy TD learning is called SARSA (state-action-reward-state-action). It uses the next action sampled from the policy \pi(s', a') to update the current transition. This selected action could be noted \pi(s') for simplicity. It is required that this next action will actually be performed for the next transition. The policy must be \epsilon-soft, for example \epsilon-greedy or softmax:
Q(s, a) \leftarrow Q(s, a) + \alpha (r(s, a, s') + \gamma \, Q(s', \pi(s')) - Q(s, a))
Q-learning
Off-policy TD learning is called Q-learning (Watkins, 1989). The greedy action in the next state (the one with the highest Q-value) is used to update the current transition. It does not mean that the greedy action will actually have to be selected for the next transition. The learned policy can therefore also be deterministic:
Q(s, a) \leftarrow Q(s, a) + \alpha (r(s, a, s') + \gamma \, \max_{a'} Q(s', a') - Q(s, a))
In Q-learning, the behavior policy has to ensure exploration, while this is achieved implicitly by the learned policy in SARSA, as it must be \epsilon-soft. An easy way of building a behavior policy based on a deterministic learned policy is \epsilon-greedy: the deterministic action \mu(s_t) is chosen with probability 1 - \epsilon, the other actions with probability \epsilon. In continuous action spaces, additive noise (e.g. Ohrstein-Uhlenbeck) can be added to the action.
Alternatively, domain knowledge can be used to create the behavior policy and restrict the search to meaningful actions: compilation of expert moves in games, approximate solutions, etc. Again, the risk is that the behavior policy never explores the actually optimal actions. See Section Off-policy Actor-Critic for more details on the difference between on-policy and off-policy methods.
Note that, despite being off-policy, Q-learning does not necessitate importance sampling, as the update rule does not depend on the behavior policy:
Q^\pi(s, a) = \mathbb{E}_{s_t \sim \rho_b, a_t \sim b}[ r_{t+1} + \gamma \, \max_a Q^\pi(s_{t+1}, a) | s_t = s, a_t=a]
but:
Q^\pi(s, a) \leftarrow Q^\pi(s, a) + \alpha (r(s, a, s') + \gamma \, \max_{a'} Q^\pi(s', a') - Q^\pi(s, a))
As we only sample transitions using b and not episodes, there is no need to correct the returns. The returns use estimates Q^\pi, which depend on \pi and not b. The immediate reward r_{t+1} is stochastic, but is the same whether you sample a_t from \pi or from b.
Summary of TD methods
Before moving on, it is worth summarizing what temporal difference brings compared to the Monte Carlo methods of Monte Carlo methods:
TD learns value functions from single transitions (s, a, r, s') instead of complete episodes. This is the main practical difference, and it has a major consequence: while MC only applies to episodic tasks, TD also works on continuing tasks, which never terminate.
Like MC, TD methods are model-free: nothing about p(s' | s, a) and r(s, a, s') needs to be known, one only needs to sample transitions.
Like DP, TD uses bootstrapping: an estimate is updated using other estimates. This is where its bias comes from, and also why it converges so much faster than MC.
The exploration-exploitation dilemma is dealt with in the same two ways as in MC:
- On-policy TD (SARSA) follows the learned stochastic policy, and learns the value of the action that was actually taken next:
Q(s, a) \leftarrow Q(s, a) + \alpha \, (r(s, a, s') + \gamma \, Q(s', a') - Q(s, a))
- Off-policy TD (Q-learning) follows a behavior policy but learns the value of the greedy action, i.e. of a deterministic policy that is not the one generating the data:
Q(s, a) \leftarrow Q(s, a) + \alpha \, (r(s, a, s') + \gamma \, \max_{a'} Q(s', a') - Q(s, a))
Q-learning is the go-to method of tabular RL, and the rest of this book is to a large extent about making it work when the Q-values can no longer be stored in a table.
Actor-critic methods
The TD error after each transition (s_t, a_t, r_{t+1}, s_{t+1}):
\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)
tells us how good the action a_t was compared to our expectation V(s_t).
When the advantage \delta_t > 0, this means that the action lead to a better reward or a better state than what was expected by V(s_t), which is a good surprise, so the action should be reinforced (selected again) and the value of that state increased. When \delta_t < 0, this means that the previous estimation of (s_t, a_t) was too high (bad surprise), so the action should be avoided in the future and the value of the state reduced.
Actor-critic methods are TD methods that have a separate memory structure to explicitly represent the policy and the value function. The policy \pi is implemented by the actor, because it is used to select actions. The estimated values V(s) are implemented by the critic, because it criticizes the actions made by the actor.
The critic computes the TD error or 1-step advantage:
\delta_t = r_{t+1} + \gamma \, V(s_{t+1}) - V(s_t)
This scalar signal is the output of the critic and drives learning in both the actor and the critic. The critic is updated using this scalar signal:
V(s_t) \leftarrow V(s_t) + \alpha \, \delta_t
The actor is updated according to this TD error signal. For example a softmax actor over preferences:
\begin{cases} p(s_t, a_t) \leftarrow p(s_t, a_t) + \beta \, \delta_t \\ \\ \pi(s, a) = \frac{\exp{p(s, a)}}{\sum_b \exp{p(s, b)}} \\ \end{cases}
When \delta_t >0, the preference is increased, so the probability of selecting it again increases. When \delta_t <0, the preference is decreased, so the probability of selecting it again decreases.
The advantage of the separation between the actor and the critic is that now the actor can take any form (preferences, linear approximation, deep networks). It requires minimal computation in order to select the actions, in particular when the action space is huge or even continuous. It can learn stochastic policies, which is particularly useful in non-Markov problems.
However, it is obligatory to learn on-policy: the critic must evaluate the actions taken by the current actor, and the actor must learn from the current critic, not “old” V-values.
Classical TD learning only learn a value function (V^\pi(s) or Q^\pi(s, a)): these methods are called value-based methods. Actor-critic architectures are particularly important in policy search methods.
Advantage estimation
n-step advantages
MC methods have high variance, low bias: Return estimates are correct on average, as we use real rewards from the environment, but each of them individually is wrong, because of the stochasticity of the policy/environment.
R_t^\text{MC} = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}
The small bias ensures good convergence properties, as we are more likely to find the optimal policy with correct estimates. The high variance means that we will need many samples to converge. The updates are not very sensitive to initial estimates.
On the other hand, TD has low variance, high bias, as the target returns contain mostly estimates.
R_t^\text{TD} = r_{t+1} + \gamma \, V^\pi(s_{t+1})
The only stochasticity comes from the immediate rewards, which is low, so the targets will not vary much during learning. But because they use other estimates, which are initially wrong, they will always be off. These wrong updates can, more often than not, lead to suboptimal policies. However, convergence will be much faster than with MC methods.
In order to control the bias-variance trade-off, we would like an estimator for the return with intermediate properties between MC and TD. This is what the n-step return offers:
R^n_t = \sum_{k=0}^{n-1} \gamma^{k} \, r_{t+k+1} + \gamma^n \, V(s_{t+n})
The n-step return uses the next n real rewards, and completes the rest of the sequence with the value of the state reached n steps in the future. Because it uses more real rewards than TD, its bias is smaller, while its variance is lower than MC.
The n-step advantage at time t is defined as the difference between the n-step return and the current estimate:
A^n_t = \sum_{k=0}^{n-1} \gamma^{k} \, r_{t+k+1} + \gamma^n \, V(s_{t+n}) - V (s_t)
It is easy to check that the TD error is the 1-step advantage:
\delta_t = A^1_t = r_{t+1} + \gamma \, V(s_{t+1}) - V(s_t)
n-step advantages are going to play an important role in deep RL, as the right choice of n will allow us to control the bias-variance trade-off: smaller values of n decrease the variance (smaller sample complexity) but may lead to suboptimal policies, while higher values of n converge to better policies, at the cost of necessitating more samples.
Eligibility traces
The main drawback of TD learning is that learning can be slow, especially when the problem provides sparse rewards (as opposed to dense rewards). For example in a game like chess, a reward is given only at the end of a game (+1 for winning, -1 for losing). All other actions receive a reward of 0, although they are as important as the last one in order to win.
Imagine you initialize all Q-values to 0 and apply Q-learning to the Gridworld problem of Figure 5.5. During the first episode, all actions but the last one will receive a reward of 0 and arrive in a state where the greedy action has a value Q^\pi(s', a') of 0 (initially), so the TD error \delta is 0 and their Q-value will not change. Only the very last action will receive a non-zero reward and update its value slightly (because of the learning rate \alpha).
When this episode is performed again, the last action will again be updated, but also the one just before: Q^\pi(s', a') is now different from 0 for this action, so the TD error is now different from 0. It is straightforward to see that if the episode has a length of 100 moves, the agent will need at least 100 episodes to “backpropagate” the final sparse reward to the first action of the episode. In practice, this is even worse: the learning rate \alpha and the discount rate \gamma will slow learning down even more. MC methods suffer less from this problem, as the first action of the episode would be updated using the actual return, which contains the final reward (although it is discounted by \gamma).
Eligibility traces can be seen a trick to mix the advantages of MC (faster updates) with the ones of TD (online learning, smaller variance). The idea is that the TD error at time t (\delta_t) will be used not only to update the action taken at time t (\Delta Q(s_t, a_t) = \alpha \, \delta_t), but also all the preceding actions, which are also responsible for the success or failure of the action taken at time t.
A parameter \lambda between 0 and 1 (decaying factor) controls how far back in time a single TD error influences past actions. This is important when the policy is mostly exploratory: initial actions may be mostly random and finally find the reward by chance. They should learn less from the reward than the last one, otherwise they would be systematically reproduced. There are many possible implementations of eligibility traces (Watkin’s, Peng, Tree Backup, etc. See the Chapter 12 of Sutton and Barto (2017)). Generally, one distinguished a forward and a backward view of eligibility traces.
- The forward view solves the question left open by the n-step return, i.e. how to choose n, by deciding not to choose: all n-step returns are averaged, with a weight decreasing geometrically with n. This defines the \lambda-return:
R^\lambda_t = (1 - \lambda) \, \sum_{n=1}^\infty \lambda^{n-1} \, R^n_t
The term (1 - \lambda) is only there to normalize the weights, as the coefficients \lambda^{n-1} sum to \frac{1}{1-\lambda}:
\sum_{n=1}^\infty \lambda^{n-1} = \dfrac{1}{1 - \lambda}
so the weights (1-\lambda) \lambda^{n-1} sum to one and the \lambda-return is a true weighted average of the n-step returns. Short returns (close to TD) get a high weight, long ones (close to MC) a small one, which is what we want: long returns have a high variance and should not dominate.
To see what \lambda does, one can split the infinite sum at the end of the episode at time T. All n-step returns with n \geq T - t are simply the Monte Carlo return R_t, as there is nothing left to bootstrap from:
R^\lambda_t = (1 - \lambda) \, \sum_{n=1}^{T-t-1} \lambda^{n-1} \, R^n_t + \lambda^{T-t-1} \, R_t
\lambda therefore directly controls the bias-variance trade-off, exactly as n did, but continuously:
- If \lambda = 0, all the weight goes to the first term and the \lambda-return is R^1_t = r_{t+1} + \gamma \, V(s_{t+1}), i.e. plain TD: high bias, low variance.
- If \lambda = 1, all the weight goes to the last term and the \lambda-return is the MC return R_t = \sum_{k=0}^\infty \gamma^k \, r_{t+k+1}: low bias, high variance.
Everything in between interpolates smoothly between the two, which is why TD(\lambda) is usually written as a family of algorithms indexed by \lambda, with TD(0) and MC as its two extremes.
Subtracting the current estimate from the \lambda-return gives the \lambda-advantage, which takes a much simpler form:
A^\lambda_t = R^\lambda_t - V(s_t) = \sum_{k=0}^\infty (\gamma \lambda)^{k} \, \delta_{t+k}
i.e. the discounted sum of all future TD errors. This is a remarkably convenient expression, as it only needs TD errors and no returns at all. We will meet it again under the name of generalized advantage estimation (Generalized Advantage Estimation (GAE)). Note that \gamma and \lambda seem to play a similar role in that formula, but they do not: \gamma is also used inside each TD error \delta_{t+k}, so it defines the horizon of the value function itself, while \lambda only weights how far back a prediction error is propagated.
The drawback of the forward view is visible in the formulas: the future transitions and their TD errors must be known when updating a transition, so the episode must be terminated before applying the updates, exactly as in MC. This prevents online learning.
- The backward view considers that the TD error made at time t is sent backwards in time to all transitions previously executed. The easiest way to implement this is to update an eligibility trace e(s,a) for each possible transition, which is incremented every time a transition is visited and otherwise decays exponentially with a speed controlled by \lambda:
e(s, a) = \begin{cases} e(s, a) + 1 \quad \text{if} \quad s=s_t \quad \text{and} \quad a=a_t \\ \gamma \, \lambda \, e(s, a) \quad \text{otherwise.} \end{cases}
The Q-value of all transitions (s, a) (not only the one just executed) is then updated proportionally to the corresponding trace and the current TD error:
Q(s, a) \leftarrow Q(s, a) + \alpha \, e(s, a) \, \delta_{t} \quad \forall s, a
The forward and backward implementations are equivalent: the first requires to know the future, the second requires to update many transitions at each time step. The best solution will depend on the complexity of the problem.
TD learning, SARSA and Q-learning can all be efficiently extended using eligibility traces. This gives the algorithms TD(\lambda), SARSA(\lambda) and Q(\lambda), which can learn much faster than their 1-step equivalent, at the cost of more computations.
To summarize what eligibility traces bring:
- They are a very useful way to speed learning up in TD methods, by propagating a reward backwards over many transitions at once instead of one per episode.
- They give a continuous control over the bias-variance trade-off through \lambda, rather than the discrete choice of n.
- The modification applies to all TD methods: TD(\lambda) for state values, SARSA(\lambda) and Q(\lambda) for action values.
- Their main drawback is memory: a trace has to be maintained for every state-action pair, not only the one just visited, and all of them have to be updated at each step. Clever implementations limit this by ignoring the traces that have decayed close to zero.
- The value of \lambda has to be chosen carefully for each problem. In particular, when the initial actions of an episode are mostly random and found the reward by chance, a high \lambda would reinforce them although they deserve no credit.
- Finally, if the problem is not strictly Markov, i.e. if it is a POMDP, eligibility traces can actually help, precisely because they update a whole history of transitions rather than a single state that does not contain all the necessary information.
Generalized Advantage Estimation (GAE)
Let’s recall the n-step advantage:
A^{n}_t = \sum_{k=0}^{n-1} \gamma^{k} \, r_{t+k+1} + \gamma^n \, V^\pi(s_{t+n}) - V^\pi(s_t)
It is easy to show recursively that it depends on the TD error \delta_t = r_{t+1} + \gamma \, V^\pi(s_{t+1}) - V^\pi(s_t) of the n next steps:
A^{n}_t = \sum_{l=0}^{n-1} \gamma^l \, \delta_{t+l}
In other words, the prediction error over n steps is the (discounted) sum of the prediction errors between two successive steps. Now, what is the optimal value of n? GAE decides not to choose and to simply average all n-step advantages, weighting them with a decaying parameter \lambda, exactly as the \lambda-return averaged the n-step returns. GAE is in fact nothing else than the \lambda-advantage introduced above, rediscovered in the context of deep RL.
This defines the Generalized Advantage Estimator A^{\text{GAE}(\gamma, \lambda)}_t:
A^{\text{GAE}(\gamma, \lambda)}_t = (1-\lambda) \, \sum_{n=1}^\infty \lambda^{n-1} \, A^n_t = \sum_{l=0}^\infty (\gamma \lambda)^l \, \delta_{t+l}
The GAE is simply a forward eligibility trace over distant n-step advantages: the 1-step advantage is more important than the 1000-step advantage (too much variance).
- When \lambda=0, we have A^{\text{GAE}(\gamma, 0)}_t = A^{1}_t = \delta_t, i.e. the TD advantage (high bias, low variance).
- When \lambda=1, we have (at the limit) A^{\text{GAE}(\gamma, 1)}_t = R_t, i.e. the MC advantage (low bias, high variance).
Choosing the right value of \lambda between 0 and 1 allows to control the bias/variance trade-off.
\gamma and \lambda play different roles in GAE: \gamma determines the scale or horizon of the value functions: how much future rewards rewards are to be taken into account. The higher \gamma <1, the smaller the bias, but the higher the variance. Empirically, Schulman et al. (2015) found that small \lambda values introduce less bias than \gamma, so \lambda can be chosen smaller than \gamma (which is typically 0.99).
In practice, GAE leads to a better estimation than n-step advantages, but is more computationally expensive. It is used in particular in PPO (Section Proximal Policy Optimization (PPO)).