Table of contents

5 Temporal-difference learning
Temporal-difference prediction
Temporal-difference on-policy control: SARSA
Temporal-difference off-policy control: Q-learning
Maximization bias and double learning

Oliver Wallscheid Reinforcement learning 164

Temporal-difference learning and the previous methods

Temporal-difference (TD) learning combines the previous ideas introduced in DP and MC:
▶ From Monte Carlo (MC) methods: learns directly from experience.
▶ From dynamic programming (DP): updates estimates based on other learned estimates
(bootstrap).

Hence, TD characteristics are:

▶ Allows model-free prediction and control in unknown MDPs.
▶ Updates policy evaluation and improvement in an online fashion (i.e., not per episode) by
bootstrapping.
▶ Still assumes finite MDP problems (or problems close to that).

Oliver Wallscheid Reinforcement learning 165

General TD prediction updates
Recap the every-visit MC update rule (4.3) for non-stationary problems:
v̂(xk ) ← v̂(xk ) + α [gk − v̂(xk )] . (5.1)

▶ α ∈ {R|0 < α < 1} is the forgetting factor / step size.

▶ gk is the target of the incremental update rule.
▶ To execute (5.1) one has to wait until the episode’s termination to get gk .

One-step TD / TD(0) update

v̂(xk ) ← v̂(xk ) + α [rk+1 + γv̂(xk+1 ) − v̂(xk )] (5.2)
g_k
▶ Here, the TD target is rk+1 + γv̂(xk+1 ).
▶ TD is bootstrapping: estimate v̂(xk ) based on v̂(xk+1 ).
▶ Delay time of one step and no need to wait until the episode’s end.

Oliver Wallscheid Reinforcement learning 166

Algorithmic implementation: TD-based prediction
input: a policy π to be evaluated
output: estimate of vX π (i.e., value estimates for all states x ∈ X )

init: v̂(x) ∀ x ∈ X arbitrary except v0 (x) = 0 if x is terminal

for j = 1, . . . , J episodes do
Initialize x0 ;
for k = 0, 1, 2 . . . time steps do
uk ← apply action from π(xk );
Observe xk+1 and rk+1 ;
v̂(xk ) ← v̂(xk ) + α [rk+1 + γv̂(xk+1 ) − v̂(xk )] ; Sử dụng v value hiện tại của x_k+1

Exit loop if xk+1 is terminal;

Algo. 5.1: Tabular TD(0) prediction
▶ Note that the algorithm can be directly adapted to action-value prediction as it will be used
for the later TD-based control approaches.

Oliver Wallscheid Reinforcement learning 167

TD error

▶ TD as well as MC use sample updates.

▶ Looking ahead to a sample successor state including its value and
the reward along the way to compute a backed up value estimate.
Figure 5.1: Back up
diagram for TD(0)

The TD error is:

δk = rk+1 + γv̂(xk+1 ) − v̂(xk ). (5.3)

▶ δk is available at time step k + 1.

▶ Iteratively δk converges towards zero.

Oliver Wallscheid Reinforcement learning 168

TD error and its relation to the MC error
Let’s assume that the TD(0) estimate v̂(x) is not changing over one episode as it would be for
MC prediction:
gk − v̂(xk ) = rk+1 + γgk+1 − v̂(xk ) + γv̂(xk+1 ) − γv̂(xk+1 )
| {z }
MC-error
= δk + γ(gk+1 − v̂(xk+1 ))
= δk + γδk+1 + γ 2 (gk+2 − v̂(xk+2 )) (5.4)
2 3
= δk + γδk+1 + γ δk+2 + γ (gk+3 − v̂(xk+3 )) = · · ·
−1
TX
= γ i−k δi .
i=k

▶ MC error is the discounted sum of TD errors in this simplified case.

▶ If v̂(x) is updated during an episode (as expected in TD(0)), the above identity only holds
approximately.
Oliver Wallscheid Reinforcement learning 169
Overview of the RL methods considered so far
190 Chapter 8: Planning and Learning with Tabular Methods

width
of update Dynamic
Temporal-
difference programming
learning

depth
(length)
of update

Exhaustive
Monte search
Carlo
...
Until terminate

Figure 5.2: Comparison two

ofofthe RLimportant
methods considered
explored in Partso
I of far withtheregard to the update rules (source: R.
Figure 8.11: A slice through the space of reinforcement learning methods, highlighting the
the most dimensions this book: depth and width of
Sutton and G. Barto, Reinforcement learning: an introduction, 2018, CC BY-NC-ND 2.0)
the updates.

ranging from one-step TD updates to full-return Monte Carlo updates. Between these
is a spectrum including methods based on n-step updates (and in Chapter 12 we will
Oliver Wallscheid extend this to mixtures of n-step updates such as thelearning
Reinforcement -updates implemented by eligibility 170
Driving home example 6.1. TD Prediction 123

45 45
actual outcome actual
outcome
40 40
Predicted Predicted
total total
travel 35 travel 35
time time

30 30

leaving reach exiting 2ndary home arrive leaving reach exiting 2ndary home arrive
office car highway road street home office car highway road street home

Situation Situation

Figure 5.3: Updates by 6.1:

Figure MCChanges
(left) and TD
recommended (right)
in the forexample
driving home (source:
α =by1Monte R. Sutton
Carlo methods (left) and G. Barto,
Reinforcement learning: an introduction, 2018, CC BY-NC-ND 2.0)
and TD methods (right).

▶ TD can learn before knowing

estimate that it willthe
take final outcome.
another 25 minutes to get home, for a total of 50 minutes. As

▶ TD learns after every

you wait in traffic, you already know that your initial estimate of 30 minutes was too
step.
optimistic. Must you wait until you get home before increasing your estimate for the
▶ MC must wait until the episode’s end.
initial state? According to the Monte Carlo approach you must, because you don’t yet
know the true return.
▶ TD could learn without a final
According to a TD outcome.
approach, on the other hand, you would learn immediately, shifting
▶ TD can learn fromyour initial estimate from 30 minutes toward 50. In fact, each estimate would be shifted
incomplete
toward sequences,
the estimate that immediately i.e.,
followsin
it. continuing
Returning to ourtasks.
first day of driving,
▶ MC is only applicable to episodic tasks.
Figure 6.1 (right) shows the changes in the predictions recommended by the TD rule
(6.2) (these are the changes made by the rule if ↵ = 1). Each error is proportional to the
change over time of the prediction, that is, to the temporal di↵erences in predictions.
Oliver Wallscheid Reinforcement learning 171
TD(0) prediction example: forest tree MDP (1)
Let’s reuse the forest tree MDP example with fifty-fifty policy and discount factor γ = 0.8 plus
disaster probability α = 0.2:

Small Medium Large

Gone
Figure 5.4: Forest MDP with fifty-fifty-policy including state values

Oliver Wallscheid Reinforcement learning 172

TD(0) prediction example: forest tree MDP (2)
TD
1.5
2
1 2
0.5 1
0 0 0
0 200 400 0 200 400 0 200 400
TD
1.5
2
1 2
0.5 1
0 0 0
0 200 400 0 200 400 0 200 400
TD
1.5
2
1 2
0.5 1
0 0 0
0 200 400 0 200 400 0 200 400

Figure 5.5: State-value estimate of forest tree MDP using TD(0) prediction over the number of episodes
being evaluated (mean and standard deviation are calculated based on 2000 independent runs)

Oliver Wallscheid Reinforcement learning 173

TD(0) vs. MC prediction example: forest tree MDP (1)
4
TD
3.5 MC
alpha is step_size
TD
3 MC
TD
2.5 MC

1.5

0.5
higher alpha => converge faster
0
0 50 100 150 200 250 300 350 400 450 500

Figure 5.6: Averaged mean of state-value estimates of forest tree MDP using TD(0) and MC over 1000
independent runs with v̂0 (x) = 0 ∀x ∈ X

Oliver Wallscheid Reinforcement learning 174

TD(0) vs. MC prediction example: forest tree MDP (2)
0.15
TD
MC
TD
MC
0.1 TD
MC

0.05

0
0 20 40 60 80 100 120 140 160 180 200

Figure 5.7: Averaged mean of state-value estimates of forest tree MDP using TD(0) and MC over 1000
independent runs with v̂0 (x) ≈ v(x) ∀x ∈ X

Oliver Wallscheid Reinforcement learning 175

Convergence of TD(0)
Theorem 5.1: Convergence of TD(0)
Given a finite MDP and a fixed π the state-value estimate of TD(0) converges to the true vπ
▶ in the mean for a constant but sufficiently small step-size α and
▶ with probability 1 if the step-size holds the condition
∞ ∞
and (5.5)
X X
αk = ∞ αk2 < ∞.
k=1 k=1

Above k is the sample index (i.e., how often the TD update was applied).

▶ In particular, αk = k1 meets the condition (5.5).

▶ Often TD(0) converges faster than MC, but there is no guarantee.
▶ TD(0) can be more sensitive to bad initializations v̂0 (x) compared to MC.

Oliver Wallscheid Reinforcement learning 176

Batch training
▶ If experience → ∞ both MC and TD converge v̂(x) → v(x).
▶ But how to handle limited experience, i.e., a finite set of episodes
x1,1 , u1,1 , r2,1 , . . . , xT1 ,1 ,
x1,2 , u1,2 , r2,2 , . . . , xT2 ,2 ,
..
.
x1,j , u1,j , r2,j , . . . , xTj ,j ,
..
.
x1,J , u1,J , r2,J , . . . , xTJ ,J .

Batch training
▶ Process all available episodes j ∈ [1, J] repeatedly to MC and TD.
▶ If the step size α is sufficiently small both will converge to certain steady-state values.
Oliver Wallscheid Reinforcement learning 177
timate V (A) given this data? Here there are
hatBatch
100% oftraining:
the AB-example (1)
immediately to
already decided r=1
3 75%
▶ Only two states: A, B
value 4 as well. r= 0
s based on first A 100% B ▶ No discounting
r= 0
as shown to the
25%
▶ 8 episodes of experience available
mates given the (see Table 5.1)
A) = 34 . This is
▶ What is v̂(A) and v̂(B) using
Figure 5.8: Example environment (source: R. Sutton and G.
Barto, Reinforcement learning: an introduction, 2018, CC batch training TD(0) and MC?
BY-NC-ND 2.0)

A, 0, B, 0 B,1
B,1 B,1
B,1 B,1
B,1 B,0
Table 5.1: Example state-reward sequences for Figure 5.8

Oliver Wallscheid Reinforcement learning 178

Batch training: AB-example (2)
First, recap MC and TD(0) update rules:
MC : v̂(xk ) ← v̂(xk ) + α [gk − v̂(xk )] ,
TD : v̂(xk ) ← v̂(xk ) + α [rk+1 + γv̂(xk+1 ) − v̂(xk )] .
Then, in steady state one receives:
MC : 0 = α [gk − v̂(xk )] = gk − v̂(xk ),
TD : 0 = α [rk+1 + γv̂(xk+1 ) − v̂(xk )] = rk+1 + γv̂(xk+1 ) − v̂(xk ).
Considering a batch learning sweep over j = 1, . . . , J episodes:
J
MC :
X
0= gk,j − v̂(xk,j ),
j=1
J
TD :
X
0= rk+1,j + γv̂(xk+1,j ) − v̂(xk,j ).
j=1

Oliver Wallscheid Reinforcement learning 179

Batch training: AB-example (3)

Apply the previous equations first to state B. Since B is a terminal state, v̂(xk+1 ) = 0 and
gk,j = rk+1,j apply, i.e., the MC and TD updates are identical for B:
J J
1X
MC|x=B :
X
0= gk,j − v̂(xk,j ) ⇔ v̂(B) = gk,j ,
j=1
J j=1
J J
1X
TD|x=B :
X
0= rk+1,j − v̂(xk,j ) ⇔ v̂(B) = gk,j .
j=1
J j=1

This is the average return of the available episodes from Table 5.1 , i.e., 6 × 1 and 2 × 0:
6
v̂(B)|MC = v̂(B)|TD = = 0.75 . (5.6)
8

Oliver Wallscheid Reinforcement learning 180

Batch training: AB-example (4)
Now consider state A assuming the steady state of batch learning process:
▶ The instantaneous reward is always r = 0.
▶ The TD bootstrap estimate of B is v̂(xk+1,j ) = v̂(B) = 34 .

J J
MC :
X X
0= gk,j − v̂(xk,j ) = gk,j − v̂(A)
j=1 j=1
J J
TD :
X X
0= rk+1,j + γv̂(xk+1,j ) − v̂(xk,j ) = γv̂(B) − v̂(A).
j=1 j=1

Looking at Table 5.1 there is only one episode visiting state A, where the sample return is
gk,j = 0. Hence, it follows:
3
v̂(A)|MC = 0, v̂(A)|TD = γv̂(B) = .
4
Where does this mismatch between the MC and TD estimates come from?
Oliver Wallscheid Reinforcement learning 181
Certainty equivalence
▶ MC batch learning converges to the least squares fit of the sampled returns:
Tj
J X
(gk,j − v̂(xk,j ))2 . (5.7)
X

j=1 k=1

▶ TD batch learning converges to the maximum likelihood estimate such that X , U, P̂, R̂, γ
D E

explains the data with highest probability:

J XTj
1
1(Xk+1 = x′ |Xk = x, Uk = u),
X
p̂uxx′ =
n(x, u) j=1 k=1
(5.8)
J X Tj
1 X
R̂ux = 1(Xk = x|Uk = u)rk+1,j .
n(x, u) j=1 k=1

▶ Here, TD assumes an MDP problem structure and is absolutely certain that its internal
model concept describes the real world perfectly (so-called certainty equivalence).
Oliver Wallscheid Reinforcement learning 182
Table of contents

5 Temporal-difference learning
Temporal-difference prediction
Temporal-difference on-policy control: SARSA
Temporal-difference off-policy control: Q-learning
Maximization bias and double learning

Oliver Wallscheid Reinforcement learning 183

Applying generalized policy iteration (GPI) to TD control
GPI concept is directly applied to the TD framework using action values:
π0 → q̂π0 → π1 → q̂π1 → · · · π ∗ → q̂π∗ . (5.9)

One-step TD / TD(0) action-value update (SARSA)

The TD(0) action-value update is:

q̂(xk , uk ) ← q̂(xk , uk ) + α [rk+1 + γ q̂(xk+1 , uk+1 ) − q̂(xk , uk )] . (5.10)

SARSA: state, action, reward, (next) state, (next) action evaluation

▶ In contrast to MC: continuous online updates of policy evaluation and improvement.

▶ On-policy approach requires exploration, e.g., by an ε-greedy policy:
(
1 − ε + ε/|U|, u = ũ,
πi (u|x) ← (5.11)
ε/|U|, u ̸= ũ.
Oliver Wallscheid Reinforcement learning 184
TD-based on-policy control (SARSA)
parameter: ε ∈ {R|0 < ε << 1} , α ∈ {R|0 < α < 1}
init: q̂(x, u) arbitrarily (except terminal states) ∀ {x ∈ X , u ∈ U}
for j = 1, 2, . . . episodes do
Initialize x0 ;
Choose u0 from x0 using a soft policy (e.g., ε-greedy) derived from q̂(x, u);
k ← 0;
repeat
Take action uk , observe rk+1 and xk+1 ;
Choose uk+1 from xk+1 using a soft policy derived from q̂(x, u);
q̂(xk , uk ) ← q̂(xk , uk ) + α [rk+1 + γ q̂(xk+1 , uk+1 ) − q̂(xk , uk )];
k ← k + 1;
until xk is terminal;
Algo. 5.2: TD-based on-policy control (SARSA)
Convergence properties are comparable to MC-based on-policy control:
▶ Policy improvement theorem Theo. 4.1 holds.
▶ Greedy in the limit with infinite exploration (GLIE) from Def. 4.1 and step-size requirements
in Theo. 5.1 apply.
Oliver Wallscheid Reinforcement learning 185
SARSA example: forest tree MDP (1)

Figure 5.9: SARSA-based control with αSARSA = 0.2 and ε-greedy policy with ε = 0.2 of forest tree
MDP over the number of episodes being evaluated (mean and standard deviation are calculated based
on 2000 independent runs)

Oliver Wallscheid Reinforcement learning 186

SARSA example: forest tree MDP (2)

Figure 5.10: SARSA-based control with αSARSA = 0.1 and ε-greedy policy with ε = 0.2 of forest tree
MDP over the number of episodes being evaluated (mean and standard deviation are calculated based
on 2000 independent runs)

Oliver Wallscheid Reinforcement learning 187

SARSA example: forest tree MDP (3)

Figure 5.11: SARSA-based control with adaptive αSARSA = √1j (j =episode) and ε-greedy policy with
ε = 0.2 of forest tree MDP over the number of episodes being evaluated (mean and standard deviation
are calculated based on 2000 independent runs)

Oliver Wallscheid Reinforcement learning 188

Table of contents

5 Temporal-difference learning
Temporal-difference prediction
Temporal-difference on-policy control: SARSA
Temporal-difference off-policy control: Q-learning
Maximization bias and double learning

Oliver Wallscheid Reinforcement learning 189

Q-learning approach
Similar to SARSA updates, but Q-learning directly estimates q ∗ :
Q-learning action-value update
The Q-learning action-value update is:
h i
q̂(xk , uk ) ← q̂(xk , uk ) + α rk+1 + γ max q̂(xk+1 , u) − q̂(xk , uk ) . (5.12)
u

This is an off-policy update, since the optimal action-value function is updated independent of
a given behavior policy.

Requirement for Q-learning control:

▶ Coverage: behavior policy b has nonzero probability of selecting actions that might be taken
by the target policy π.
▶ Consequence: behavior policy b is soft (e.g., ε-soft).
▶ Step-size requirements (5.5) regarding α apply.

Oliver Wallscheid Reinforcement learning 190

TD-based off-policy control (Q-learning)
parameter: ε ∈ {R|0 < ε << 1} , α ∈ {R|0 < α < 1}
init: q̂(x, u) arbitrarily (except terminal states) ∀ {x ∈ X , u ∈ U}
for j = 1, 2, . . . episodes do
Initialize x0 ;
k ← 0;
repeat
Choose uk from xk using a soft behavior policy;
Take action uk , observe rk+1 and xk+1 ;
q̂(xk , uk ) ← q̂(xk , uk ) + α [rk+1 + γ maxu q̂(xk+1 , u) − q̂(xk , uk )];
k ← k + 1;
until xk is terminal;
Algo. 5.3: TD-based off-policy control (Q-learning)

▶ As discussed with MC-based off-policy control: alternative to the exploration-exploitation

trade-off for on-policy methods.
▶ No importance sampling required as for off-policy MC-based control.

Oliver Wallscheid Reinforcement learning 191

 is a standard undis-
sodic task, with start
ates, and the usual ac-
Q-learning control example: cliff walking
g movement up, down,
ft. Reward is 1 on all R = -1
R = -1
xcept those into the re- safe Rpath
r =(! ! sa
SaferRpath
“The Cli↵.” Stepping
ion incurs a reward of
optimal path
nds the agent instantly Optimal path
S T h e C l i f f G
op
▶ r = −1 per time step
start. S T h e C l i f f G
h to the right shows the
R = -100
Sarsa ▶ Large penalty if you fall off the cliff
of the Sarsa and Q- !Rr%∃= ! ! ∀∀ R = -100
hods with "-greedy ac-
n, " = 0.1. After an
▶ No discounting
Sum of ! ∃∀
ent, Q-learning learns Reward
he optimal policy, that rewards
per -25
Sarsa
Q-learning ▶ ε = 0.1
during
s right along the edge epsiode
episode
Unfortunately, this re- ! #∃
occasionally falling o↵ Sum of -50
rewards Q-learning
ause of the "-greedy ac-
during
n. Sarsa, on the other episode ! ! ∀∀
-75 ∀ !∀∀ %∀∀ &∀∀ ∍∀∀ ∃∀∀
the action selection into
learns the longer but Episodes
Episodes ▶ Why is SARSA better in this
hrough the upper part
Although Q-learning ac-
-100
0 100 200 300 400 500 example?
the values of the opti- Episodes
its online performance ▶ And what policy’s performance is
n that of Sarsa, which
Figure 5.12: Cliff walking environment (source: R. Sutton
undabout policy. Of course, if " were gradually reduced, then both methods shown here in particular?
and G. Barto, Reinforcement learning: an introduction,
ptotically converge to the optimal policy.
1
2
2018, CC BY-NC-ND 2.0) ⇤
Why is Q-learning considered an o↵-policy control method?
Suppose action selection is greedy. Is Q-learning then exactly the same
s Sarsa? Will they make exactly the same action selections and weight
⇤
Oliver Wallscheid Reinforcement learning 192
Table of contents

5 Temporal-difference learning
Temporal-difference prediction
Temporal-difference on-policy control: SARSA
Temporal-difference off-policy control: Q-learning
Maximization bias and double learning

Oliver Wallscheid Reinforcement learning 193

Maximization bias
All control algorithms discussed so far involve maximization operations:
▶ Q-learning: target policy is greedy and directly uses max operator for action-value updates.
▶ SARSA: typically uses an ε-greedy framework, which also involves max updates during
policy improvement.
This can lead to a significant positive bias:
▶ Maximization over sampled values is used implicitly as an estimate of the maximum value.
▶ This issue is called maximization bias.
Small example:
▶ Consider a single state x with multiple possible actions u.
▶ The true action values are all q(x, u) = 0.
▶ The sampled estimates q̂(x, u) are uncertain, i.e., randomly distributed. Some samples are
above and below zero.
▶ Consequence: The maximum of the estimate is positive.
Oliver Wallscheid Reinforcement learning 194
Double learning approach
Split the learning process:
▶ Divide sampled experience into two sets.
▶ Use sets to estimate independent estimates q̂1 (x, u) and q̂2 (x, u).

Assign specific tasks to each estimate:

▶ Estimate the maximizing action:

u∗ = arg max q̂1 (x, u). (5.13)

u

▶ Estimate corresponding action value:

q(x, u∗ ) ≈ q̂2 (x, u∗ ) = q̂2 (x, arg max q̂1 (x, u)). (5.14)
u

Oliver Wallscheid Reinforcement learning 195

Double Q-learning algorithm
parameter: ε ∈ {R|0 < ε << 1} , α ∈ {R|0 < α < 1}
init: q̂1 (x, u), q̂2 (x, u) arbitrarily (except terminal states) ∀ {x ∈ X , u ∈ U}
for j = 1, 2, . . . episodes do
Initialize x0 ;
k ← 0;
repeat
Choose uk from xk using the policy ε-greedy based on q̂1 (x, u) + q̂2 (x, u);
Take action uk , observe rk+1 and xk+1 ;
if n ∼ N (µ = 0, σ) > 0 then
q̂1 (xk , uk ) ← q̂1 (xk , uk ) + α [rk+1 + γ q̂2 (xk+1 , arg maxu q̂1 (xk+1 , u)) − q̂1 (xk , uk )];
else
q̂2 (xk , uk ) ← q̂2 (xk , uk ) + α [rk+1 + γ q̂1 (xk+1 , arg maxu q̂2 (xk+1 , u)) − q̂2 (xk , uk )];
k ← k + 1;
until xk is terminal;
Algo. 5.4: TD-based off-policy control with double learning
▶ Doubles memory demand while computational demand per episode is remains unchanged
▶ Less sample efficient than regular Q-learning (samples are split between two estimators)
Oliver Wallscheid Reinforcement learning 196
 6.7. Maximization Bias and Double Learning 135

Maximization bias 100%

example
N( 0.1, 1)
0 0
B A

...
75% left right

% left
actions 50%
Q-learning
from A
Double
25% Q-learning

5% optimal
0
1 100 200 300
Episodes

Figure 5.13: Comparison

Figure of Q-learning
6.5: Comparison andand
of Q-learning double
Double Q-learningon
Q-learning on aa simple
simpleepisodic
episodic
MDP MDP.
(shown
Q-learning
inset). Q-learning initially learns to take the left action much more often than the right action,
initiallyand
learns to take the left action much more often than the right action,
always takes it significantly more often than the 5% minimum probability enforced by
and always takes it
significantly more often than the 5% minimum probability enforced by ε-greedy action
"-greedy action selection with " = 0.1. In contrast, Double Q-learning is essentially una↵ected by selection with
ε = 0.1. In contrast, double
maximization Q-learning
bias. These is essentially
data are averaged unaffected
over 10,000 by maximization
runs. The bias.
initial action-value These data are
estimates
averagedwere overzero.
10,000 runs.
Any ties The initial
in "-greedy action-value
action estimates
selection were were zero. (source: R. Sutton and G.
broken randomly.
Barto, Reinforcement learning: an introduction, 2018, CC BY-NC-ND 2.0)
Oliver Wallscheid Reinforcement learning 197
Summary: what you’ve learned today
▶ TD unites two key characteristics from DP and MC:
▶ From MC: sample-based updates (i.e., operating in unknown MDPs).
▶ From DP: update estimates based on other estimates (bootstrapping).
▶ TD allows certain simplifications and improvements compared to MC:
▶ Updates are available after each step and not after each episode.
▶ Off-policy learning comes without importance sampling.
▶ Exploits MDP formalism by maximum likelihood estimates.
▶ Hence, TD prediction and control exhibit a high applicability for many problems.
▶ Batch training can be used when only limited experience is available, i.e., the available
samples are re-processed again and again.
▶ Greedy policy improvements can lead to maximization biases and, therefore, slow down the
learning process.
▶ TD requires careful tuning of learning parameters:
▶ Step size α: how to tune convergence rate vs. uncertainty / accuracy?
▶ Exploration vs. exploitation: how to visit all state-action pairs and the optimal policy?

Oliver Wallscheid Reinforcement learning 198