Reinforcement Learning: Temporal Difference

Methods

00:00:07,400 --> 00:00:07,700

Welcome back!

00:00:08,400 --> 00:00:11,100

In Lesson 2, we are describing what are known as

00:00:11,100 --> 00:00:14,400

temporal difference methods in reinforcement learning.

00:00:14,400 --> 00:00:17,400

The tools that we will describe here

00:00:17,400 --> 00:00:20,300

are going to get us even closer to the

00:00:20,300 --> 00:00:23,300

optimization tools that we started in Module 5, relative to

00:00:23,300 --> 00:00:25,100

the Monte Carlo method.

00:00:26,200 --> 00:00:29,200

So, temporal difference methods allow the

00:00:29,200 --> 00:00:32,500

agent to learn from experience without waiting

00:00:32,500 --> 00:00:35,600

until the end of an episode to improve upon

00:00:35,600 --> 00:00:38,600

a guessed policy. With Monte Carlo

00:00:38,600 --> 00:00:40,600

methods, having to wait until the end

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 1
00:00:41,600 --> 00:00:44,500
of the episode can slow down the learning process.

00:00:45,400 --> 00:00:48,200

Now, temporal difference methods allow the

00:00:48,200 --> 00:00:51,900

agent to update the state-action functions after each

00:00:51,900 --> 00:00:54,100

action. The advantage of

00:00:54,100 --> 00:00:57,400

this method is that it is more relevant in instances where the agent

00:00:57,400 --> 00:01:00,700

faces very long episodes. This approach

00:01:00,700 --> 00:01:04,000

resembles the "bootstrapping" approach

00:01:03,500 --> 00:01:06,800

in the value or Q-function

00:01:06,800 --> 00:01:09,700

iteration and the "in place" dynamic

00:01:09,700 --> 00:01:12,300

programming techniques that we developed in Module 5.

00:01:12,300 --> 00:01:15,400

If you recall, these tools allow the

00:01:15,400 --> 00:01:18,500

agent to update information to make new guesses

00:01:18,500 --> 00:01:19,900

as quickly as possible.

00:01:21,300 --> 00:01:24,500

So, in this lesson, we will introduce two

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 2
00:01:24,500 --> 00:01:27,300
temporal difference methods, SARSA and

00:01:27,300 --> 00:01:30,300

Q-Learning. Although we are not explicitly mentioning

00:01:30,300 --> 00:01:34,700

this, in all these methods, we will keep exploring starts

00:01:33,700 --> 00:01:36,500

and epsilon-greedy

00:01:36,500 --> 00:01:39,200

policies due to the need to force the agent to

00:01:39,200 --> 00:01:43,200

explore the space of actions

00:01:42,200 --> 00:01:44,300

and states.

00:01:45,300 --> 00:01:48,300

So, let's begin with the SARSA method and the

00:01:48,300 --> 00:01:51,100

SARSA method consists of keeping a record

00:01:51,100 --> 00:01:54,300

of each transition from state-action to state-

00:01:54,300 --> 00:01:57,800

action and the implied rewards. That is,

00:01:57,800 --> 00:02:00,300

given a visit to a state-action

00:02:00,300 --> 00:02:02,100

pair "(st,at)",

00:02:03,600 --> 00:02:06,700

we store the associated reward

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 3
00:02:06,700 --> 00:02:07,600
"rt"

00:02:09,200 --> 00:02:12,800

and use our guess for the optimal policy to determine

00:02:12,800 --> 00:02:15,800

the next action and then

00:02:15,800 --> 00:02:18,200

from the environment we reach the

00:02:18,200 --> 00:02:21,400

next state, "(st+1,at+1)".

00:02:22,100 --> 00:02:25,500

Because we have a guess for the state-action function

00:02:25,500 --> 00:02:27,400

at "(st,at)"

00:02:28,700 --> 00:02:31,200

and at "(st+1,at+1)",

00:02:31,200 --> 00:02:34,500

as well as the value for the reward obtained by

00:02:34,500 --> 00:02:37,900

the agent, we can obtain a new guess for the state-action

00:02:37,900 --> 00:02:41,600

function at "(st,at)".

00:02:42,300 --> 00:02:45,700

Now, notice the similarities of this updating scheme with

00:02:45,700 --> 00:02:48,600

the updating scheme we described in the context of

00:02:48,600 --> 00:02:51,500

the Multi-Armed bandits of Module

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 4
00:02:51,500 --> 00:02:54,500
6. This updating scheme gives us

00:02:54,500 --> 00:02:57,800

a weighted average of all previous updates

00:02:57,800 --> 00:02:58,500

of the function,

00:02:59,500 --> 00:03:03,200

where we give more weight to current relative to more

00:03:02,200 --> 00:03:05,600

distant information and the

00:03:05,600 --> 00:03:08,200

relative importance of each is determined

00:03:08,200 --> 00:03:12,600

by the parameter "alpha". Thus, after each SARSA

00:03:11,600 --> 00:03:14,800

sequence, the agent can

00:03:14,800 --> 00:03:17,600

update the state action pair and derive

00:03:17,600 --> 00:03:20,400

new candidate optimal policies. Now, this

00:03:20,400 --> 00:03:23,600

type of algorithm is called an "on-policy"

00:03:23,600 --> 00:03:27,100

algorithm in contrast to the Q-Learning

00:03:26,100 --> 00:03:28,800

algorithm that we are going to describe next.

00:03:29,600 --> 00:03:32,200

Now, SARSA is on-policy because the

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 5
00:03:32,200 --> 00:03:35,400
updating of the state-action function is determined by

00:03:35,400 --> 00:03:38,700

the visits to the actions that are determined by the

00:03:38,700 --> 00:03:41,400

current policy. In other words, we use the guess

00:03:41,400 --> 00:03:44,800

at the future pair "(st+1,at+1)" to

00:03:44,800 --> 00:03:48,400

update the guess at "(st,at)" because

00:03:47,400 --> 00:03:51,000

the current policy prescribes that

00:03:50,400 --> 00:03:52,200

we must take action

00:03:53,100 --> 00:03:56,400

"at+1" when we reach state "st+1".

00:03:57,300 --> 00:04:00,600

So next, we are going to describe Q-Learning.

00:04:01,400 --> 00:04:04,500

Instead of focusing on transitions from

00:04:04,500 --> 00:04:07,800

state-action pairs to state-action pairs, Q-

00:04:07,800 --> 00:04:11,100

Learning exploits only transitions across states.

00:04:11,700 --> 00:04:14,800

In other words, the Q-Learning algorithm works as follows.

00:04:16,600 --> 00:04:20,000

Consider the agent reaching in an episode the state-

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 6
00:04:19,200 --> 00:04:21,700
action pair (st,at),

00:04:22,700 --> 00:04:24,500

which implies a reward "rt".

00:04:25,500 --> 00:04:28,500

Now, suppose that we observe a transition to a

00:04:28,500 --> 00:04:32,000

state "st+1". Then, we update

00:04:31,200 --> 00:04:34,600

the state-action value function

00:04:34,600 --> 00:04:37,300

at "(st,at)" assuming that

00:04:37,300 --> 00:04:40,600

the future optimal action at "t+1" is the

00:04:40,600 --> 00:04:43,400

one that maximizes the state-action value function

00:04:43,400 --> 00:04:46,300

in state "st+1". With this

00:04:46,300 --> 00:04:49,700

updating rule, we can obtain a new policy guess

00:04:49,700 --> 00:04:51,100

at state "st".

00:04:52,200 --> 00:04:55,100

This method, contrary to the previous

00:04:55,100 --> 00:04:58,600

one, is an off-policy method because we update

00:04:58,600 --> 00:05:01,100

the Q function without considering what is

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 7
00:05:01,100 --> 00:05:04,500
the current guess for the optimal policy in state

00:05:04,500 --> 00:05:05,500

"st+1".

00:05:06,700 --> 00:05:09,600

So, how do both methods

00:05:09,600 --> 00:05:12,500

of temporal difference learning compare?

00:05:13,200 --> 00:05:16,800

Now asymptotically, they should in general reach the

00:05:16,800 --> 00:05:19,700

same optimal policies, but they can generate different

00:05:19,700 --> 00:05:23,000

outcomes when the agent has a limited scope

00:05:22,400 --> 00:05:25,400

to gather experience, to explore.

00:05:25,400 --> 00:05:28,500

In the Jupyter notebook created for Lesson 2,

00:05:28,500 --> 00:05:31,400

we implement the SARSA and the Q-

00:05:31,400 --> 00:05:34,500

Learning algorithms to the windy gridworld we also

00:05:34,500 --> 00:05:37,600

analyzed in the past, Lesson 1. Now, the

00:05:37,600 --> 00:05:40,400

most striking difference between both sets of results

00:05:40,400 --> 00:05:43,800

is the fact that SARSA prescribes a

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 8
00:05:43,800 --> 00:05:46,100
right movement in cell 1 instead of

00:05:46,100 --> 00:05:48,700

a left movement that leads to the

00:05:49,700 --> 00:05:52,000

agent to reach the terminal cell immediately.

00:05:53,100 --> 00:05:57,000

Now, the reason why this choice is optimal according to SARSA, is

00:05:56,200 --> 00:05:59,400

that epsilon-greedy policies allow the

00:05:59,400 --> 00:06:01,600

agent to explore potential actions

00:06:01,900 --> 00:06:04,100

and the value of the random actions generated by

00:06:04,100 --> 00:06:07,300

the epsilon-greedy policy are used to update the

00:06:07,300 --> 00:06:10,700

Q-function in the current state, that is the "A" in SARSA.

00:06:12,900 --> 00:06:16,300

In contrast, Q-Learning ignores future

00:06:15,300 --> 00:06:18,400

actions that are determined by the epsilon-greedy

00:06:18,400 --> 00:06:21,800

policy updating the state-action value function

00:06:21,800 --> 00:06:25,300

using a greedy-based criterion. This "greedy"

00:06:24,300 --> 00:06:27,700

bias of Q-Learning leads to

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 9
00:06:27,700 --> 00:06:31,200
a quicker identification of the best policy.

00:06:30,200 --> 00:06:33,400

This is not always a positive aspect

00:06:33,400 --> 00:06:36,200

of Q-Learning, however, as we are

00:06:36,200 --> 00:06:39,700

going to illustrate its drawbacks relative to SARSA in

00:06:39,700 --> 00:06:42,100

Lesson 3. Again, if we

00:06:42,100 --> 00:06:46,900

allow for longer episodes or more exploration, SARSA

00:06:45,900 --> 00:06:48,600

should converge to

00:06:48,600 --> 00:06:51,300

the optimal left movement in cell 1, here.

00:06:52,800 --> 00:06:55,900

So, this has been all for Lesson 2.

00:06:56,700 --> 00:06:59,600

In the next lesson, we will analyze another

00:06:59,600 --> 00:07:02,200

implementation of these temporal difference methods to

00:07:02,200 --> 00:07:05,300

compare SARSA vs. Q-Learning. So, I'll

00:07:05,300 --> 00:07:05,700

see you there!

MScFE | © 2022 - WorldQuant University – All rights reserved. Video Transcript | PAGE 10