Reinforcement Learning Part 6: Temporal Difference Learning

Following the previous part, we will continue exploring reinforcement learning with model-free algorithms. The previous parts can be found at the bottom of this article.

For all algorithms from now on, we will be using the Stochastic Gradient Descent (SGD) concepts. Since SGD is a familiar concept for most readers, I will be skipping over the proofs behind it. However, one should note that while we may say SGD multiple times in this and following articles, SGD may refer to any one of the following: Stochastic Gradient Descent (where a single sample is used at each iteration to converge to the optimal solution), Mini-Batch Gradient Descent (sample size is between 2 and all available datapoints), and Batch Gradient Descent (all datapoints are used). Unless otherwise specified, SGD will refer to Stochastic Gradient Descent or, more likely, Mini-Batch Gradient Descent.

Some more concepts first…

Before moving on to Temporal Difference (TD) learning, let us learn two new algorithm properties as these differ when it comes to MC learning vs TD learning.

• Online vs offline algorithms: Offline algorithms are ones that require an entire episode to be completed before updating or evaluating the policy. These require one to wait for experience until a terminal state before performing one round of Policy Evaluation and Policy Improvement. On the other hand, online policies are policies that perform one iteration of PI with each state transition, making the updates much more frequent and incremental.
• On-policy vs off-policy learning: In all RL algorithms, there are two types of policies: the target policy and the behaviour policy. The target policy is the one that we intend will converge to the optimal policy, and is considered the final output. The behaviour policy, on the other hand, is the policy that is used for the agent to explore the environment and is used to collect experience to update the target policy. When the behaviour policy is the same as the target policy, it is known as on-policy learning, and off-policy otherwise. Off-policy learning is quite beneficial as it allows for much more exploration which may get missed out if we use the target policy as we may miss out on some state-action “visits” if we are not careful.

If the two concepts above are clear, it should be clear that all the MC learning algorithms discussed so far were both offline and on-policy. This is because we had to wait for the entire episode to be generated before we performed model-free PI, and the policy used to explore the environment and collect samples was the same as our target policy.

We shall discuss the same properties for all the future algorithms that we are going to introduce.

Temporal Difference Learning

Before moving on to some of the TD algorithms, let us first understand the core idea behind TD learning. TD learning is based on the Robbins–Monro (RM) stochastic approximation framework, the same algorithm that powers SGD. Due to this, the equations we use will be familiar to Gradient Descent equations.

For any trajectory, we can depict it as a set form as follows: {s_t, a_t, r_(t+1), s_(t+1)}_t, where s_t is the initial state at timestep t, a_t is the action taken at timestep t, r_(t+1) is the reward received by the agent for this state-action pair, and s_(t+1) is the final state that the agent reaches. This can further be extended with a_(t+1), which denotes the action the agent takes at the next timestep (this will be useful when we introduce the SARSA algorithm later).

Using this, the core equation behind TD learning is:

This equation depicts an update step that can be used for the Policy Evaluation step. TD learning is primarily a family of online learning algorithms, therefore, this equation is accessed at each state transition. At every transition, the state value of the initial state s_t is updated as per the reward observed in the first half of the equation. The state values of the remaining states stay the same, which is expressed by the second half of the equation.

This equation is derived from the Bellman equation. Since the return from the next state can be expressed as the state value of the next state (as done when deriving the closed-form solution to the Bellman Equation in Part 2), it can be written as:

Therefore to solve this equation, TD learning basically applies the RM algorithm on this and uses samples collected from experience to converge to an optimal policy.

Let us dissect this equation a little further.

Here the terms of the equation have also been labeled. The new estimate and current estimate are the estimated state values for the initial state and are self-explanatory. ⍺_t is the “learning rate” and is a number chosen in the range (0, 1] similar to SGD. Now let us discuss the other two terms.

• TD target: This expression estimates the new state value for the given sample. If we were looking at this algorithm more crudely, we could say that we should assign the new estimated state value using only this expression. If observed closely, setting the learning rate to 1 will achieve this. However, we know that there is noise when we train with experience samples, and therefore instead of directly replacing the current estimate with this new value, we choose to move in the direction of this new value (just like SGD). Therefore it should be clear that this equation is modifying the current estimate closer to the TD target to arrive at the new estimate.
• TD error: This expression is the difference between current estimated state value and the TD target. It serves as direction in which the current estimate should be updated as well as what proportion of magnitude to update it with. When the algorithm has converged, the value of this TD error will be 0. This is easily proved as one can see that v_t = v_𝜋 is a solution of the Bellman equation, thus making the TD error 0. TD error is sometimes referred to as innovation, as this is the magnitude of the new information that the agent receives from this particular experience sample.

TD Learning with State Values

Note that while we have understood the basic TD equation, using it directly in practice is not straightforward. We can use the equation above to perform Policy Evaluation for every experience sample, however, following that, it is not that easy to perform the Policy Improvement step to update our policy from 𝜋_t to 𝜋_(t+1). This is because when we discussed Policy Improvement with known state actions, we had knowledge of the dynamics model. With no information about the model or the action values, updating the policy is not so trivial.

Due to this, all of the TD algorithms do not operate on this form of the TD equation. Instead they estimate the action values making it much simpler to update the policy. We shall see this now with the first algorithm.

SARSA

We now tackle the first TD algorithm. Let us rewrite the TD base equation in the form with action values instead of state values.

This equation is very similar to the base TD equation, with the only difference being that the state values have been replaced with the action values for that particular state and the action taken at that state. This equation is also a form of the Bellman equation. Note that this equation also requires a_(t+1), i.e. the action the agent takes at the next experience sample. This is why the algorithm is named as such: State-Action-Reward-State-Action.

Using the action values estimated with this equation in the Policy Evaluation step, we can update the policy in the Policy Improvement step. Since we may end up not visiting all state-action pairs using this approach, it is recommended to use an ε-greedy policy instead of a deterministic one to encourage more exploration.

Here is the pseudocode for this algorithm:

It is clear that this algorithm is online as well as on-policy.

For a working example of SARSA, please visit here. Here is a sample console output of the same:

Maze:
A  ·  ·  V  ·  V  
·  ·  ·  ·  ·  V  
V  ·  ·  ·  E  ·  
·  ·  ·  V  ·  E  
·  ·  V  ·  ·  ·  
·  ·  E  ·  V  ·  
Reward to exit:                   1.0
Reward to move (excludes 'stay'): -0.1
Reward to enter vortex:           -1.0

Running SARSA...
Iteration 0 complete. Sum of state_values: -0.046859431677930476
Iteration 20 complete. Sum of state_values: 20.913859377877273
Iteration 40 complete. Sum of state_values: 33.455622406359815
Iteration 60 complete. Sum of state_values: 43.549669100220235
Iteration 80 complete. Sum of state_values: 50.60935216540872

Policy table:
 state \ action  left  right  down   up  stay 
     (4, 0)      0.1    0.6   0.1   0.1  0.1  
     (3, 4)      0.1    0.6   0.1   0.1  0.1  
     (4, 3)      0.1    0.6   0.1   0.1  0.1  
     (3, 1)      0.1    0.1   0.6   0.1  0.1  
     (5, 4)      0.1    0.1   0.1   0.6  0.1  
     (5, 1)      0.1    0.6   0.1   0.1  0.1  
     (0, 2)      0.1    0.1   0.6   0.1  0.1  
     (0, 5)      0.1    0.1   0.6   0.1  0.1  
     (2, 2)      0.1    0.6   0.1   0.1  0.1  
     (1, 0)      0.6    0.1   0.1   0.1  0.1  
     (2, 5)      0.1    0.1   0.6   0.1  0.1  
     (1, 3)      0.1    0.6   0.1   0.1  0.1  
     (4, 2)      0.1    0.1   0.6   0.1  0.1  
     (3, 0)      0.1    0.1   0.6   0.1  0.1  
     (4, 5)      0.1    0.1   0.1   0.6  0.1  
     (3, 3)      0.1    0.6   0.1   0.1  0.1  
     (5, 0)      0.1    0.6   0.1   0.1  0.1  
     (5, 3)      0.6    0.1   0.1   0.1  0.1  
     (0, 1)      0.1    0.1   0.1   0.1  0.6  
     (2, 4)      0.1    0.1   0.1   0.1  0.6  
     (1, 2)      0.1    0.1   0.6   0.1  0.1  
     (0, 4)      0.1    0.1   0.6   0.1  0.1  
     (2, 1)      0.1    0.6   0.1   0.1  0.1  
     (1, 5)      0.1    0.1   0.6   0.1  0.1  
     (3, 2)      0.1    0.1   0.1   0.6  0.1  
     (4, 1)      0.1    0.1   0.6   0.1  0.1  
     (3, 5)      0.1    0.6   0.1   0.1  0.1  
     (5, 2)      0.1    0.1   0.1   0.1  0.6  
     (4, 4)      0.1    0.1   0.1   0.6  0.1  
     (5, 5)      0.1    0.1   0.1   0.6  0.1  
     (0, 0)      0.1    0.1   0.1   0.1  0.6  
     (1, 1)      0.1    0.6   0.1   0.1  0.1  
     (0, 3)      0.1    0.6   0.1   0.1  0.1  
     (2, 0)      0.1    0.1   0.1   0.6  0.1  
     (1, 4)      0.1    0.1   0.6   0.1  0.1  
     (2, 3)      0.1    0.6   0.1   0.1  0.1  

 ↺   ↺   ↓  V→   ↓  V↓  
 ←   →   ↓   →   ↓  V↓  
V↑   →   →   →  E↺   ↓  
 ↓   ↓   ↑  V→   →  E→  
 →   ↓  V↓   →   ↑   ↑  
 →   →  E↺   ←  V↑   ↑

Expected SARSA

Expected SARSA is similar to SARSA; however, instead of using the sampled action value in the TD target, we substitute it with the expected action value over all possible actions under the policy. Here is the equation:

While this method requires more computation in each Policy Evaluation step, it reduces the estimation variance as we no longer depend on a_(t+1). This equation also follows the Bellman Equation. The rest of the algorithm remains the same. This algorithm is also online as well as on-policy. It is on-policy as the expectation term depends on the policy for the probabilities for taking each action from state s_(t+1).

n-step SARSA

n-step SARSA combines concepts from TD learning and MC learning to reduce bias in the estimated values. Instead of performing Policy Evaluation for every experience, we wait to collect n experience samples, and then perform the step. If we wait for infinite steps, we obtain MC learning, as will we be wait for the entire episode and then run Generalized Policy Iteration. Here is a visualization of the same:

The update step in n-step SARSA looks like this:

Therefore, this is a more generalized form of SARSA. If n=1, we have SARSA, and if n is sufficiently large, we have MC learning, with intermediate values blending the performance of both accordingly. This equation also follows the Bellman Equation. The rest of the algorithm remains the same. This algorithm is neither strictly online not offline, however, it is still on-policy.

Q-Learning

Q-learning is one of the most widely used RL algorithms in practice. In formulation, it looks very similar to the SARSA algorithm:

Mathematically, the only difference is that instead of taking the action value corresponding to a_(t+1), we use the maximum action value that one can achieve at state s_(t+1). However, under the hood, there are a lot of differences.

• Q-Learning is actually built on top of the Bellman Optimality Equation and not the Bellman Equation.
• Q-Learning is actually off-policy, which means that the behaviour policy used to generate experience samples is actually different from the target policy. It is off-policy as the action a_(t+1) can be anything and is not required in the Policy Evaluation step. This allows for a much more exploratory nature of experimentation. It also allows us to keep the target policy deterministic instead of ε-greedy as we don’t have to worry about exploitation overpowering exploration in the trade-off.
• In SARSA, the learned action values are not guaranteed to be the optimal action values for the given experience. This is because we use a_(t+1) i.e. the action taken at the next time step based on the policy, which may not correspond to the state value of that state i.e. v_t(s_(t+1)). However, in Q-Learning, as we take the max action value, we are actually using the state value, and therefore obtaining the optimal action value for the given state-action pair given the experience we have had till now.

Note that this equation still needs to be clubbed with the Policy Improvement step to complete the algorithm.

If we use the on-policy version of this algorithm, we still need to use an ε-greedy version of this policy to ensure sufficient exploration. Here is the pseudocode for the on-policy version:

When using the off-policy variant, target policy can be deterministic, while a separate exploratory behavior policy collects experience. Here is the pseudocode:

Note that in the off-policy version pseudocode, the policy improvement step has been shown to be part of the iteration, however it can just as easily be kept outside the loop i.e. Q-learning directly tries to learn the optimal action values (it directly learns Q* and not Q_𝜋), eliminating the need to calculate the target policy at every step. The target policy can be identified once at the very end of the algorithm. In practice, however, the exploratory behaviour policy is periodically updated with the target policy in order to get rid of mistakes identified earlier, and therefore the target policy will have to be evaluated after a fixed number of iterations to replace the behaviour policy.

Advantages and Disadvantages of TD learning and MC learning

• We have already seen that TD learning is an online algorithm whereas MC learning is offline. Therefore TD learning allows us to update the state/action values immediately rather than having to wait for an entire episode to end. For long episodes, this time gain can be beneficial.
• Since TD learning is online, it can also be applied on continuing tasks, i.e. tasks that do not end. MC learning cannot be applied to such tasks as an episode is required for the Policy Evaluation step in MC learning to be activated.
• TD learning depends on fewer random variables (only the ones in that particular sample, i.e. R_t, S_(t+1), A_(t+1)) whereas MC learning depends on multiple (all the random variables in the episode i.e. R_(t+1), R_(t+2), R_(t+3), R_(t+4),…). Therefore, TD learning has low variance, but is a biased estimator of the state/action values. On the other hand, MC learning has higher variance but is an unbiased estimator of the value.

tl;dr

The model-free algorithms we have learned so far can be expressed using this base equation (in the action value format):

Here, the term in blue varies for each algorithm. Here are the values for each of the algorithms:

All of these algorithms except Q-learning operate on the Bellman Equation. Q-learning operates on the Bellman Optimality Equation.

[embed]Reinforcement Learning Part 5: Monte Carlo Learning Up until now, we have assumed we know the dynamics model of our environment. However, this is often not the case as…medium.com

[embed]Reinforcement Learning Part 4: Value Iteration and Policy Iteration By now we are comfortable with the terminology used in RL, the Bellman equation, the Bellman Optimality equation (BOE)…medium.com

[embed]Reinforcement Learning Part 3: The Bellman Optimality Equation and Optimal Policies Those joining us directly at Part 3 should be familiar with the Bellman Equation and how it can be used to compare two…medium.com

Some resources for further learning:

• https://youtube.com/playlist?list=PLEhdbSEZZbDaFWPX4gehhwB9vJZJ1DNm8&si=IAK7iuvDEtLYRimW

[embed]Glossary: A Reference to All My Articles I wanted to provide a method for readers to be able to find any and all of my articles in one place with some sort of…medium.com

This article presents my interpretation of the material presented. This analysis does not claim to be exhaustive or definitive, and any misinterpretations are unintentional. I welcome constructive discussion and alternative viewpoints in the comments.