1 of 36

Lecture 11�� n-Step Bootstrapping

1

Institute for Data Science & Artificial Intelligence

Lecturer: Ercan Atam

Course: DSAI 542-Reinforcement Learning

2 of 36

2

List of contents for this lecture

n-step TD prediction

n-step SARSA

n-step off-policy learning with importance sampling

n-step off-policy learning with tree backup approach

3 of 36

3

Relevant readings for this lecture

Chapter 7 of “Reinforcement Learning: An Introduction”, Richard S. Sutton and Andrew G. Barto, Second Edition, MIT Press, Cambridge, MA, 2018

4 of 36

4

In this lecture, we unify the Monte Carlo (MC) methods and the one-step temporal difference (TD) methods presented in the previous lectures.

Neither MC methods nor one-step TD methods are always the best.

In this lecture, we present n-step TD methods that generalize both methods so that one can shift from one to the other smoothly as needed to meet the demands of a particular task.

n-step methods span a spectrum with MC methods at one end and one-step TD methods at the other.

The best methods are often intermediate between the two extremes.

Introduction (1)

5 of 36

5

With one-step TD, the same time step is used for

changing action and bootstrapping.

n-step TD decouples this and has different time

scales for action and bootstrapping.

As usual, we first consider the prediction problem

and then the control problem.

Introduction (2)

6 of 36

6

Monte Carlo methods perform an update for each state based on the entire sequence of observed rewards from that state until the end of the episode.

The update of one-step TD methods, on the other hand, is based on just the one next reward, bootstrapping from the value of the state one step later as a proxy for the remaining rewards.

An intermediate method, then, would perform an update based on an intermediate number of rewards: more than one, but less than all of them until termination.

For example, a two-step update would be based on the first two rewards and the estimated value of the state two steps later.

The methods that use n-step updates are still TD methods because they still change an earlier estimate based on how it differs from a later estimate.

n-step TD prediction (1)

7 of 36

7

n-step TD prediction (2)

8 of 36

8

n-step TD prediction (3)

Fig: The idea of n-step returns for n=3

9 of 36

9

n-step TD prediction (4)

Fig: How n-step bootstrapping deals with the end of episodic sequence, where n=3.

10 of 36

10

n-step TD prediction (5)

11 of 36

11

Whereas in Monte Carlo updates the target is the return, in one-step updates the target is the first reward plus the discounted estimated value of the next state, which we call the one-step return:

n-step TD prediction (6)

We are at time “t+1” and use

the estimate at the previous time “t”

12 of 36

12

More generally, the target for an n-step update is the n-step return:

n-step TD prediction (7)

13 of 36

13

n-step TD prediction (8)

14 of 36

14

n-step TD prediction algorithm

15 of 36

15

Convergence of n-step TD prediction

Theorem: error reduction property of n-step TD prediction

▶ Assuming an infinite number of steps/episodes and an appropriate step-size according to

n-step TD prediction converges to the true value.

▶ In a more practical framework with limited number of steps/episodes:

▶ Choosing the best n-step lookahead horizon is an engineering degree of freedom.

▶ This is highly application-dependent (i.e., no predefined optimum).

▶ Prediction/estimation errors can remain due to limited data.

(Source, W. Kirchgässner, M. Schenke, O. Wallscheid and D. Weber, RL Course Material, Paderborn University, 2020)

16 of 36

16

n-step TD prediction algorithm: a simple run

17 of 36

17

n-step TD prediction methods on the random walk (1)

18 of 36

18

n-step TD prediction methods on the random walk (2)

19 of 36

19

Note: Based on the results of the 5-state random walk process, it seems the larger n, the better results are. However, this example is of small size to come to a definite answer!

Next, let us construct an empirical test for a larger random walk process where

there are 19 states instead of 5

−1 for outcome on the left side

all state values are initialized to 0

n-step TD prediction methods on the random walk (3)

20 of 36

20

n-step TD prediction methods on the random walk (4)

21 of 36

21

n-step methods can be combined with SARSA in a straightforward way to produce an on-policy TD control method, which we call n-step SARSA.

The main idea here is to learn q functions instead of v functions.

We redefine n-step returns (update targets) in terms of estimated action values:

The natural update rule is then

n-step SARSA (1)

22 of 36

22

n-step SARSA (2)

Fig: The backup diagrams for the spectrum of n-step methods for state–action values (including the backup diagram of the n-step expected SARSA) .

23 of 36

23

n-step SARSA algorithm

24 of 36

24

The first panel shows the path taken in a single episode, ending at location G of high reward.

The action values were all initially 0, and all rewards were 0 except for a positive reward at G.

The arrows in the other two panels show which action values were strengthened as a result of this path by one-step and n-step SARSA methods.

The one-step method strengthens only the last action of the sequence of actions that led to the high reward, whereas the n-step method strengthens the last n actions of the sequence, so that much more is learned from the one episode.

n-step SARSA application to gridworld

Fig: Executed updates (denoted by arrows) for different n-step SARSA methods during an episode.

25 of 36

25

n-step Expected SARSA (1)

Fig: The backup diagrams for the spectrum of n-step methods for state–action values (including the backup diagram of the n-step Expected SARSA) .

26 of 36

26

Therefore, expected SARSA algorithm can be described by the same algorithm as n-step SARSA, except with the n-step return redefined as

n-step Expected SARSA (2)

27 of 36

27

n-step off-policy learning with importance sampling (1)

28 of 36

28

n-step off-policy learning with importance sampling (2)

…

29 of 36

29

Similarly, our previous n-step SARSA update can be completely replaced by a simple off-policy form:

Note that the importance sampling ratio here starts and ends one step later compared to before. This is because here we are updating a state–action pair and hence we do not have to care how likely we were to select the action at time t.

n-step off-policy learning with importance sampling (3)

…

30 of 36

30

Off-policy n-step SARSA algorithm

31 of 36

31

n-step off-policy learning without importance sampling: the tree backup approach (1)

Q1: Is off-policy learning possible without importance sampling?

A1: Yes! Q-learning and Expected SARSA are such examples for the one-step case.

Q2: Is there an “n-step” off-policy learning without importance sampling?

A2: Yes! It is the tree backup approach we describe next…

32 of 36

32

n-step off-policy learning without importance sampling: the tree backup approach (2)

Fig.: the 3-step tree-backup update

Hanging off to the sides of each state are the actions that were not selected.

(For the last state, all the actions are considered to have not (yet) been selected.)

Because we have no sample data for the unselected actions, we bootstrap and

use the estimates of their values in forming the target for the update.

33 of 36

33

n-step off-policy learning without importance sampling: the tree backup approach (3)

Fig.: the 3-step tree-backup update

Update Rule

Update is based on the estimated action values of the leaf nodes of the tree.

Each arrow to a “dangling action” node in the diagram is weighted

by the action’s probability of being selected under the target policy.

If there is a tree below a “spinal action” node, then that weight applies

to all the leaf nodes in the tree.

Actions

dangling action

spinal action

(=action taken)

34 of 36

34

n-step off-policy learning without importance sampling: the tree backup approach (4)

Fig.: the 3-step tree-backup update

One-step return:

Two-step tree-backup return:

n-step tree-backup return:

(same as Expected SARSA)

35 of 36

35

n-step off-policy learning without importance sampling: the tree backup approach (5)

36 of 36

References �(utilized for preparation of lecture notes or Matlab code)

36