/
Текст
Reinforcement Learning
Prof. Christian Bauckhage
1 / 82
lecture 09
model-based and model-free RL algorithms
in this lecture, we study model-based and model-free RL algorithms
regarding the former, we discuss policy iteration and value iteration
regarding the latter (which are way more important in practice), we
first discuss several variants of Monte Carlo algorithms for prediction
and control
then, we look at the fundamental idea of temporal difference learning
and study algorithms called TD(0) and SARSA
2 / 82
outline
recap
model-based RL
policy iteration
value iteration
model-free RL
Monte Carlo prediction and control
temporal difference learning for prediction (TD(0))
temporal difference learning for control (SARSA)
summary
3 / 82
recap
4 / 82
Bellman’s principle of optimality
”An optimal policy has the property that whatever the initial state
and initial decision are, the remaining decisions must constitute
an optimal policy w.r.t. the state resulting from the first decision.”
⇒ Bellman equations
XX
X
Vπ s =
R s, a π a s + γ
Vπ s ′ p s ′ s, a π a s
a
a
s′
invoke the principle of optimality to relate value functions to themselves
⇔ the expected value of state s under policy π is its immediate return plus
the discounted average of the values of its possible successors
5 / 82
iterative policy evaluation
given a policy π a s and an arbitrary initial value function V0 s
the process
for t ∈ N
for all s ∈ S
XX
X
Vt+1 s =
R s, a π a s + γ
Vt s ′ p s ′ s, a π a s
a
a
s′
is guaranteed to converge to Vπ s , i.e. to the value function for π
6 / 82
example
policy π a s
Vπ s with γ = 0.9
-100.0
Vπ s with γ = 0.99
-36.4
-37.7
-43.2
-46.6
-48.3
-49.0
-49.3
-49.3
-49.1
-48.5
-47.0
-43.7
-37.0
-25.2
-16.7
-42.8
-45.8
-59.4
-63.6
-65.0
-65.5
-65.7
-65.7
-65.6
-65.2
-64.1
-61.5
-53.9
-29.9
-11.7
-60.3
-63.3
-100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0
-41.6
+7.9 +100.0
-50.4
-63.9
-100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0
-51.3
-43.4
-58.7
-100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0
-35.2
-42.1
-58.1
-63.0
-64.6
-65.1
-65.0
-64.6
-65.0
-65.0
-64.5
-62.5
-56.9
-31.6
-34.7
-41.7
-45.8
-47.7
-48.3
-47.8
-45.6
-47.7
-48.2
-47.4
-45.2
-40.4
-41.1
-36.4
-37.7
-43.2
-46.6
-48.3
-49.0
-49.3
-49.3
-49.1
-48.5
-47.0
-43.7
-37.0
-25.2
-16.7
-42.8
-45.8
-59.4
-63.6
-65.0
-65.5
-65.7
-65.7
-65.6
-65.2
-64.1
-61.5
-53.9
-29.9
-11.7
-60.3
-63.3
-100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0
-41.6
+7.9 +100.0
-22.5
-50.4
-63.9
-100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0
-51.3
-22.5
-52.3
-31.4
-43.4
-58.7
-100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0
-52.3
-31.4
-38.5
-29.4
-35.2
-42.1
-58.1
-63.0
-64.6
-65.1
-65.0
-64.6
-65.0
-65.0
-64.5
-62.5
-56.9
-38.5
-29.4
-32.1
-27.8
-31.6
-34.7
-41.7
-45.8
-47.7
-48.3
-47.8
-45.6
-47.7
-48.2
-47.4
-45.2
-40.4
-32.1
-27.8
-100.0
-41.1
7 / 82
remark
looking at these results, we note that
"∞
#
X
t
Vπ s = Eπ
γ Rt+1 S0 = s
t=0
should arguably be better written as
"∞
#
X
t
Vπ s, γ = Eπ
γ Rt+1 S0 = s
t=0
alas, nobody does this (so we don’t, too)
8 / 82
important disclaimer
when we talk about a value function Vπ , it always is w.r.t. an MDP and some γ
in fact, some people are more careful about this and define MDPs as S, A, T, R, γ
9 / 82
Bellman optimality equations for V∗ s
V∗ s = max Q∗ s, a
a
X
= max R s, a + γ
V∗ s ′ p s ′ s, a
a
s′
Bellman optimality equations for Q∗ s, a
X
Q∗ s, a = R s, a + γ
max
Q∗ s ′ , a ′ p s ′ s, a
′
s′
a
10 / 82
optimal (deterministic) policy
π∗ s = argmax Q∗ s, a
a
X
= argmax R s, a + γ
V∗ s ′ p s ′ s, a
a
s′
⇔ if we know Q∗ s, a or V∗ s , we can determine π∗ s
11 / 82
question
so where do we go from here ?
answer
in what follows, we will consider
model-based algorithms
and
model-free algorithms
for estimating an optimal (deterministic) policy π∗ s
12 / 82
two more things . . .
the problem of evaluating a policy π, i.e. the problem of
estimating Vπ (or Qπ ), is also called prediction problem
the problem of optimizing a policy π, i.e. the problem of
finding π∗ , is also called control problem
now, let’s go for it . . .
13 / 82
model-based RL
14 / 82
suppose we are given a policy π a s and use policy evaluation to find
X
Xh
i
Vπ s =
R s, a + γ
Vπ s ′ p s ′ s, a π a s
a
s′
for all s ∈ S
now, let us briefly focus on an arbitrary state si ∈ S and its value w.r.t. π
X
i
Xh
Vπ si =
R si , a + γ
Vπ s ′ p s ′ si , a π a si
a
s′
15 / 82
in particular, let us consider the nature of the weighted sum over actions
X
Xh
i
Vπ si =
R si , a + γ
Vπ s ′ p s ′ si , a π a si
a
s′
since the weights π a si of this linear combination are constrained by
π a si ⩾ 0
X
π a si = 1
a
we realize that . . .
16 / 82
Vπ si is a convex combination of these m values
X
R si , a1 + γ
Vπ s ′ p s ′ si , a1
s′
X
R si , a2 + γ
Vπ s ′ p s ′ si , a2
s′
..
.
X
R si , am + γ
Vπ s ′ p s ′ si , am
s′
17 / 82
⇒ since Vπ si is a convex combination, we must have
X
min R si , a + γ
Vπ s ′ p s ′ si , a
a
⩽ Vπ si
s′
X
⩽ max R si , a + γ
Vπ s ′ p s ′ si , a
a
s′
18 / 82
⇒ there must always exist at least one action
X
a∗ = argmax R si , a + γ
Vπ s ′ p s ′ si , a
a
s′
for which we are guaranteed this inequality
X
Vπ si ⩽ R si , a∗ + γ
Vπ s ′ p s ′ si , a∗
s′
this is interesting because we may now . . .
19 / 82
consider a slightly modified policy π ′ a s with
π′ a s = π a s
for all states s ̸= si and
1 if a = a∗
′
π a si =
0 otherwise
(we break ties if there are several a∗ )
under this new policy the value for state si becomes
X
Xh
i
Vπ ′ si =
R si , a + γ
V π ′ s ′ p s ′ si , a π ′ a si
a
= R si , a∗ + γ
X
s′
Vπ ′ s ′ p s ′ si , a∗
s′
20 / 82
note
we have
X
Vπ ′ si = R si , a∗ + γ
Vπ ′ s ′ p s ′ si , a∗
s′
⩾ Vπ si
⇒ under the new policy, the value for state si will increase
the values of those states that can transition to si , i.e. of
states s with actions a such that p(si |s, a) > 0, increase
as well; the values of all other states remain unchanged
⇒ the new policy exploiting a∗ is better than the initial policy
21 / 82
question
why only consider local policy adaptation ?
answer
why indeed ?
22 / 82
in general, we may update π to a greedy deterministic policy π ′
X
π ′ s = argmax R s, a + γ
Vπ s ′ p s ′ s, a
a
s′
for all s
this update will provide us with a value function Vπ ′ s such that
Vπ ′ s ⩾ Vπ s
for all s
23 / 82
note
all the above suggests this alternating procedure which is known as policy iteration
eval
impr
eval
impr
eval
impr
eval
π0 −→ Vπ0 −→ π1 −→ Vπ1 −→ π2 −→ · · · −→ π∗ −→ V∗
each improved deterministic policy is guaranteed to be better than the previous one
πt ⩾ πt−1
as a finite MDP admits only finitely many deterministic policies, policy iteration must
converge to an optimal policy and to the optimal value function in a finite number of
iterations
24 / 82
policy iteration
“randomly” initialize π∗
repeat
π ← π∗
// evaluate policy π, i.e. solve
for all s ∈ S
X
Xh
i
Vπ s =
R s, a + γ
Vπ s ′ p s ′ s, a π a s
s′
a
// improve policy π greedily, i.e. compute
for all s ∈ S
X
π∗ s ← argmax R s, a + γ
Vπ s ′ p s ′ s, a
a
s′
until π = π∗
25 / 82
question
OK, but how can be sure that the resulting π∗ is an optimal policy
and that the corresponding V∗ is the optimal value function ?
answer
a simple argument goes like this . . .
26 / 82
assume that policy iteration has converged to π∗ so that
X
a∗ = π∗ s = argmax R s, a + γ
V∗ s ′ p s ′ s, a
a
s′
the value function of this deterministic policy then reads
X
V∗ s = R s, a∗ + γ
V∗ s ′ p s ′ s, a∗
s′
X
= max R s, a + γ
V∗ s ′ p s ′ s, a
a
s′
⇒ V∗ fulfills the Bellman optimality criterion
⇔ V∗ is the optimal value function
⇒ π∗ is an optimal policy
27 / 82
note
policy iteration
− is of O |A| · |S|2 + |S|3 per iteration
+ typically requires only few iterations
+ is guaranteed to converge within |A||S| iterations
28 / 82
note
policy iteration
− is of O |A| · |S|2 + |S|3 per iteration
+ typically requires only few iterations
+ is guaranteed to converge within |A||S| iterations
the |S|3 part of the effort is a conservative estimate of the effort
required for the policy evaluation step
numerical computing experts know that we could do better, but
here is an outrageous question . . .
28 / 82
question
can we do without policy evaluation ?
answer
yes, we can !
29 / 82
recall that policy evaluation of π given an initial V0 is to compute
repeat
for all s ∈ S
XX
X
Vt+1 s =
R s, a π a s + γ
Vt s ′ p s ′ s, a π a s
a
a
s′
until convergence
further recall that this process is guaranteed to converge to Vπ s
but how about we stop early and consider a rough approximation
Vπ s ≈ V1 s
30 / 82
under this approximation, policy evaluation reduces to
for all s ∈ S
X
XX
V1 s ←
R s, a π a s + γ
V0 s ′ p s ′ s, a π a s
a
a
s′
the subsequent policy improvement step would then be
for all s ∈ S
X
π1 s ← argmax R s, a + γ
V1 s ′ p s ′ s, a
a
s′
note: π1 s is deterministic
31 / 82
continuing these iterations we would have
for all s ∈ S
X
V1 s ′ p s ′ s, π1 (s)
V2 s ← R s, π1 (s) + γ
s′
for all s ∈ S
X
π2 s ← argmax R s, a + γ
V2 s ′ p s ′ s, a
a
s′
for all s ∈ S
X
V3 s ← R s, π2 (s) + γ
V2 s ′ p s ′ s, π2 (s)
s′
for all s ∈ S
X
π3 s ← argmax R s, a + γ
V3 s ′ p s ′ s, a
a
s′
..
.
32 / 82
note
if
X
πt s = argmax R s, a + γ
Vt s ′ p s ′ s, a
a
s′
then
X
Vt+1 s = R s, πt (s) + γ
Vt s ′ p s ′ s, πt (s)
s′
so that
X
Vt+1 s = max R s, a + γ
Vt s ′ p s ′ s, a
a
s′
this process of updating Vt directly to Vt+1 is called value iteration
33 / 82
value iteration
randomly initialize V∗
repeat
V ← V∗
for all s ∈ S
for all a ∈ A
X
Q s, a ← R s, a + γ
V s ′ p s ′ s, a
s′
V∗ s ← max Q s, a
a
until V − V∗ < ε
for all s ∈ S
X
π∗ s ← argmax R s, a + γ
V∗ s ′ p s ′ s, a
a
s′
not the most efficient implementation
but a very foreshadowing one . . .
34 / 82
note
value iteration
+ is of O |A| · |S|2 per iteration
− typically requires many iterations
− speed of convergence depends on γ
35 / 82
question
but how can we be sure that the resulting V∗ is the optimal value function ?
answer
left as an exercise . . .
36 / 82
example
γ = 0.9, ε = 0.0005
convergence behavior
+17.7 +19.8 +22.1 +24.7 +27.5 +30.7 +34.2 +38.1 +42.5 +47.3 +52.7 +58.6 +65.3 +72.6 +80.8
20
18
+19.8 +22.1 +24.7 +27.5 +30.7 +34.2 +38.1 +42.5 +47.3 +52.7 +58.6 +65.3 +72.6 +80.8 +89.9
16
-100.0 +17.7 +19.8 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 +89.9 +100.0 +100.0
+14.2 +15.8 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 +72.6 +80.8
+15.8 +17.7 +19.8 +22.1 +24.7 +27.5 +30.7 +34.2 +38.1 +42.5 +47.3 +52.7 +58.6 +65.3 +72.6
+14.2 +15.8 +17.7 +19.8 +22.1 +24.7 +27.5 +30.7 +34.2 +38.1 +42.5 +47.3 +52.7 +58.6 +65.3
+27.5
kVnew − Voldk∞
14
+15.8 +17.7 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 -100.0 +80.8 +89.9
12
10
8
6
4
2
0
0
10
20
30
40
50
t
60
70
80
90
100
37 / 82
γ = 0.5, ε = 0.0005
convergence behavior
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.1
-0.0
+0.1
+0.4
+1.1
+2.3
+4.9
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.1
-0.0
+0.1
+0.4
+1.1
+2.3
+4.9
+9.9
-0.2
-0.2
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
+9.9
+20.0 +20.0
-0.2
-0.2
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
+4.9
+9.9
-0.2
-0.2
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
-20.0
+2.3
+4.9
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.1
-0.0
+0.1
+0.4
+1.1
+2.3
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.2
-0.1
-0.0
+0.1
+0.4
+1.1
20
18
16
14
-0.2
kVnew − Voldk∞
-20.0
12
10
8
6
4
2
0
0
10
20
30
40
50
t
60
70
80
90
100
38 / 82
take home messages
policy evaluation (lecture 08)
P
PP
Vt+1 s ←
R s, a π a s + γ
Vt s ′ p s ′ s, a π a s
a
a
s′
uses Bellman equations for fixed point iteration
value iteration (lecture 09)
P
Vt+1 s ← max R s, a + γ Vt s ′ p s ′ s, a
a
s′
uses Bellman optimality equations for fixed point iteration
now, it’s time for a big leap . . .
39 / 82
model-free RL
40 / 82
note
so far, we have seen that MDP models S, A, T, R provide a great framework
for developing a theory of reinforcement learning
however, in most practical situations, MDP models are demanding too much . . .
41 / 82
consider this
how would an agent know an environment’s state transition probabilities T
when being new to said environment ?
how would an agent know an environment’s expected immediate rewards R
when being new to said environment ?
⇔ isn’t it unrealistic that an agent always has a complete model S, A, T, R ?
indeed, when they are new to a task / an environment, agents first have to learn
about it through discovery processes
42 / 82
example
1st discovery process quickly ends in lava
2nd discovery process continues for much longer. . .
...
43 / 82
⇔ an agent finds itself in a state s[0] and “figures out” available actions A s[0]
it then applies “some” policy to choose / execute an action a[0] ∈ A s[0]
this causes a transition to a new state s[1] for which the environment reacts
with a reward r[1] and the agent chooses / executes an action a[1] . . .
such episodes continue until they reach a terminal state (either good or bad)
s[0], a[0] : r[1], s[1], a[1] : r[2], s[2], a[2] : · · · : r[h], s[h], a[h]
over numerous episodes, the agent acquires
knowledge
of the environment
which it could use to estimate p s ′ s, a and E R s, a
however . . .
44 / 82
question
when given episodes, do we
S, A, T, R
really need
to learn T and R to get a model
in order to then learn V∗ s or Q∗ s, a and thus the sought after π∗ s ?
⇔ can’t we learn V∗ s or Q∗ s, a and thus π∗ s directly from the given episodes ???
answer
yes, we can !
45 / 82
if we have a sample of n episodes
s1 [0], a1 [0] : r1 [1], s1 [1], a1 [1] : · · · : r1 [h1 ], s1 [h1 ], a1 [h1 ]
s2 [0], a2 [0] : r2 [1], s1 [1], a2 [1] : · · · : r2 [h2 ], s2 [h2 ], a2 [h2 ]
···
sn [0], an [0] : rn [1], sn [1], an [1] : · · · : rn [hn ], sn [hn ], an [hn ]
starting in some state si [0] = s and following some policy π,
we can compute the finite horizon (hi ) discounted (γ) return
hi
X
Ĝi s =
γt ri t + 1
t=0
for each episode and treat each Ĝi s as an observable estimate of
∞
P
the true but unknown discounted return G0 =
γt Rt+1 after state s
t=0
46 / 82
we can use these surrogates to compute
n hX
i −1
1X
V̂π s, n =
γt ri t + 1
n
i=1 t=0
in order to approximate or empirically estimate
"∞
#
X
Vπ s = Eπ
γt Rt+1 S0 = s
t=0
where the law of large numbers guarantees that
lim V̂π s, n = Vπ s
n→∞
47 / 82
what follows are clever algorithms which cope with the seeming difficulty
that different episodes can have different duration and which furthermore
allow for different starting states . . .
48 / 82
first visit Monte Carlo policy evaluation
for all s ∈ S
V̂(s) ← 0
N(s) ← 0
for many, many trials
sample a state
s[0] ∈ S \ F
follow π to generate an episode
s[0], a[0] : r[1], s[1], a[1] : · · · : r[T], s[T], a[T]
Ĝ ← 0
for t = T − 1, . . . , 0
Ĝ ← γ Ĝ + r[t + 1]
if s[t] ∈
/ s[0]
: · · · : s[t
− 1]
V̂ s[t] ← V̂ s[t] + Ĝ
N s[t] ← N s[t] + 1
// initialize estimate of the value function for each state s
// initialize a counter which counts occurrences of state s
// iterate from the end of the episode to its beginning
// test, if s = s[t] does not occur earlier in the episode
// if not, then t is the first time s is visited in the episode
for all s ∈ S
V̂(s)
V̂(s) ← N(s)
49 / 82
every visit Monte Carlo policy evaluation
for all s ∈ S
V̂(s) ← 0
N(s) ← 0
// initialize estimate of the value function for each state s
// initialize a counter which counts occurrences of state s
for many, many trials
sample a state
s[0] ∈ S \ F
follow π to generate an episode
s[0], a[0] : r[1], s[1], a[1] : · · · : r[T], s[T], a[T]
Ĝ ← 0
for t = T − 1, . . . , 0
// iterate from the end of the episode to its beginning
Ĝ ← γ
Ĝ + r[t + 1]
V̂ s[t] ← V̂ s[t] + Ĝ
// update V̂ s every time s = s[t] is visited in the current episode
N s[t] ← N s[t] + 1
for all s ∈ S
V̂(s)
V̂(s) ← N(s)
50 / 82
“one can show” (via bias-variance decomposition) that
first visit MC computes an unbiased estimator V̂π of the true Vπ
every visit MC computes a biased yet consistent estimator V̂π of the true Vπ
⇒ for N s → ∞, both methods converge to the true Vπ s for all states s ∈ S \ F
here is yet another variant . . .
51 / 82
incremental Monte Carlo policy evaluation
for all s ∈ S
V̂(s) ← 0
N(s) ← 0
Ĝ(s) ← 0
for many, many trials
sample s[0] and follow π to generate episode
s[0], a[0] : r[1], s[1], a[1] : · · · : r[T], s[T], a[T]
for t = 0, . . . , T − 1
ĝ ←
T−1
P
// iterate from the beginning of the episode to its end
γτ−t r[τ + 1]
// compute discounted episodic return for state s[t]
τ=t
Ĝ s[t] ← Ĝ s[t] + ĝ
N s[t] ← N s[t] + 1
V̂ s[t] ←
Ĝ(s[t])
N(s[t])
52 / 82
this is foreshadowing, because
N s counts how often Ĝ s and V̂ s are being updated
(we next briefly abbreviate it to N for better readability)
the assignment
Ĝ(s)
V̂ s ←
N
is but a computer scientific notation for the following iterative process
i
i
1
1 h
1 h
V̂N s = ĜN s =
ĜN−1 s + ĝ =
V̂N−1 s · N − 1 + ĝ
N
N
N
1 h
i
= V̂N−1 s +
ĝ − V̂N−1 s
N
53 / 82
note
⇒ the assignment
Ĝ(s)
V̂ s ←
N(s)
can also be written as
V̂ s ← V̂ s +
i
1 h
ĝ − V̂ s
N(s)
54 / 82
note
Monte Carlo policy evaluation
+ works without knowledge of T s ′, s, a or R s, a
± works best (or basically only) with γ ≈ 1
± only applies to episodic problems / tasks
− requires the creation of many episodes
Monte Carlo policy evaluation for policy improvement
− may waste time on sub-optimal policies
55 / 82
example (every visit MC evaluation of a stochastic policy)
r[t + 1] = Util s[t + 1] , γ = 0.99, episodes = 50, 000
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.9
-9.9
-9.8
-9.5
-9.0
-8.3
-7.2
-6.3
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.9
-9.9
-9.7
-9.3
-8.7
-7.0
-5.2
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-6.7
-2.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-7.9
-5.9
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-8.6
-7.7
-10.0
-10.0
-10.0
-10.1
-10.2
-10.3
-10.5
-10.7
-10.5
-10.2
-10.1
-9.9
-9.5
-8.9
-8.5
-10.0
-10.0
-10.1
-10.1
-10.3
-10.5
-11.0
-12.1
-11.0
-10.5
-10.1
-9.8
-9.5
-9.1
-8.8
+10.0
-14.6
56 / 82
note
when learning from episodes, it is often useful to consider quality functions Q s, a
among others, this immediately allows for policy improvement / control, because if
πt+1 s = argmax Qπt s, a
a
then
Qπt+1 s, πt+1 s = Qπt s, argmax Qπt s, a
a
= max Qπt s, a
a
⩾ Qπt s, πt s
⩾ Vπt s
57 / 82
Monte Carlo control / policy iteration (on-policy version)
for all s ∈ S
π s ← any a ∈ A s
for all a ∈ A s
Q s, a ← 0
N s, a ← 0
for many, many trials
sample a state-action
pair
s[0], a[0] ∈ S \ F × A
follow π to generate an episode
s[0], a[0] : r[1], s[1], a[1] : · · · : r[T], s[T], a[T]
Ĝ ← 0
for t = T − 1, . . . , 0
Ĝ ← γ Ĝ +
r[t + 1]
Q s[t], a[t] ← Q s[t], a[t] + Ĝ
N s[t], a[t] ← N s[t], a[t] + 1
for all s ∈ S
π s ← argmax
a
Q s,a
N s,a
58 / 82
what follows is yet another variant which we don’t
bother to explain in detail (not worth our time ;-))
however, we will need the following technical term
soft policy
⇔ a stochastic policy π a s such that
π a s > 0 for all s, a ∈ S × A s
59 / 82
Monte Carlo control / policy iteration (off-policy version)
πb ← any soft stochastic policy
πe ← any deterministicpolicy
for all s, a ∈ S × A s
Q s, a ← 0
W s, a ← 0
for many, many trials
sample state-action pair and follow πb to generate episode
s[0], a[0] : r[1], s[1], a[1] : · · · : r[T], s[T], a[T]
Ĝ ← 0
Ŵ ← 1
for t = T − 1, . . . , 0
Ĝ ← γ Ĝ + r[t + 1]
W s[t], a[t] ← N s[t], a[t] + Ŵ
h
i
Ŵ
Ĝ − Q s[t], a[t]
Q s[t], a[t] ← Q s[t], a[t] + W(s,a)
πe s[t] ← argmaxa Q s[t], a
if a[t] ̸= πe s[t]
break
Ŵ
Ŵ ← π (a[t]
| s[t])
b
60 / 82
on-policy methods
attempt to improve a given policy π for decision making
off-policy methods
attempt to improve a policy πe different from a policy πb
used to generate data
πb ⇔ behavior policy
πe ⇔ target policy or estimation policy
πb is usually stochastic whereas πe is usually deterministic
we will return to this distinction later . . .
61 / 82
observe
a major inconvenience / drawback of the above Monte Carlo methods
is that we have to wait until an episode has been generated before we
can learn anything from it
question
can’t we learn while running an episode ?
⇔ can we learn Vπ s in an online manner ?
62 / 82
answer
yes, we can !
If one had to identify one idea as central and novel
to reinforcement learning, it would undoubtedly be
temporal-difference (TD) learning.
Sutton and Barto, chapter 6
63 / 82
we have already seen the updates
i
1 h
V̂ St ← V̂ St +
Ĝ − V̂ St
NSt
we next write them less specifically as
h
i
V̂ St ← V̂ St + α Ĝ − V̂ St
with 0 < α < 1 and we moreover recall
V̂ is an estimate of Vπ
Ĝ is an estimate of Gt | St = s
⇔ Ĝ is an estimate of Rt+1 + γ Vπ St+1
St = s
64 / 82
note
⇒ we may consider
temporal difference (TD) updates
h
i
V̂ St ← V̂ St + α Rt+1 + γ V̂ St+1 − V̂ St
65 / 82
we have
h
i
V̂ St ← V̂ St + α Rt+1 + γ V̂ St+1 − V̂ St
or equivalently
h
i
V̂ St ← 1 − α V̂ St + α Rt+1 + γ V̂ St+1
with these ingredients
γ V̂ St+1 − V̂ St is called the temporal difference
Rt+1 + γ V̂ St+1 − V̂ St is called the TD error
Rt+1 + γ V̂ St+1 is called the TD target
0 < α < 1 is a (constant) learning rate
66 / 82
TD(0)
for many, many trials
sample a state
s∈S\F
while s ∈
/F
sample an action
a∼π · s
get a successor
s ′ ← Succ s, a
// note: outcome depends on the dynamics of the environment
receive a reward
r ← Util s ′
// note: outcome depends on the dynamics of the environment
update
h
i
V̂ s ← V̂ s + α r + γ V̂ s ′ − V̂ s
s ← s′
67 / 82
note
TD(0) for policy evaluation
+ works without knowledge of T s ′, s, a or R s, a
+ will provably converge to Vπ if (the mean of) the learning rate α is “small enough”
+ does not really require episodes but also works just with samples of transitions
− requires the creation of many transitions
TD(0) for policy improvement
− may waste time on sub-optimal policies
68 / 82
example
r[t + 1] = Util s[t + 1] , α = 0.25, γ = 0.99, episodes = 100, 000
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.9
-9.6
-9.6
-9.2
-8.1
-6.8
-4.8
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.9
-9.7
-9.8
-9.6
-7.6
-6.5
-4.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.0
-1.4
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-8.6
-5.5
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-8.7
-7.9
-10.0
-10.0
-10.0
-10.1
-10.1
-10.1
-10.4
-10.3
-10.4
-10.1
-10.0
-9.8
-9.4
-8.6
-8.1
-10.0
-10.0
-10.0
-10.1
-10.2
-10.3
-10.6
-11.7
-10.8
-10.3
-10.0
-9.6
-9.5
-8.8
-8.6
+10.0
-15.4
69 / 82
comparison
Monte Carlo prediction
-10.0
TD(0) prediction
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.9
-9.9
-9.8
-9.5
-9.0
-8.3
-7.2
-6.3
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.9
-9.6
-9.6
-9.2
-8.1
-6.8
-4.8
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.9
-9.9
-9.7
-9.3
-8.7
-7.0
-5.2
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.9
-9.7
-9.8
-9.6
-7.6
-6.5
-4.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-6.7
-2.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-9.0
-1.4
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-7.9
-5.9
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-8.6
-5.5
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-8.6
-7.7
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-8.7
-7.9
-10.0
-10.0
-10.0
-10.1
-10.2
-10.3
-10.5
-10.7
-10.5
-10.2
-10.1
-9.9
-9.5
-8.9
-8.5
-10.0
-10.0
-10.0
-10.1
-10.1
-10.1
-10.4
-10.3
-10.4
-10.1
-10.0
-9.8
-9.4
-8.6
-8.1
-10.0
-10.0
-10.1
-10.1
-10.3
-10.5
-11.0
-12.1
-11.0
-10.5
-10.1
-9.8
-9.5
-9.1
-8.8
-10.0
-10.0
-10.0
-10.1
-10.2
-10.3
-10.6
-11.7
-10.8
-10.3
-10.0
-9.6
-9.5
-8.8
-8.6
-14.6
+10.0
-10.0
+10.0
-15.4
70 / 82
note
TD(0) is but a special case of the more general TD(n) and TD(λ) techniques
TD(0) is also called one-step TD hinting at what TD(n) and TD(λ) generalize
TD(0) combines aspects of Monte Carlo sampling and dynamic programming
⇔ TD(0) does not require a model of the environment and does not have to wait
until episodes are completed
⇔ TD(0) estimates value functions in a fully model free- and fully online manner
71 / 82
question
does temporal difference learning also apply to quality functions ?
question
yes, it does !
72 / 82
note
“one can show” that this process will converge (for α “small enough”)
state action reward state action (SARSA) updates
h
i
Q̂ St , At ← Q̂ St , At + α Rt+1 + γ Q̂ St+1 , At+1 − Q̂ St , At
this update rule workswith quintuples
St , At , Rt+1 , St+1 , At+1 hence its name
73 / 82
note
“one can show” that the following process will converge (for α “small enough”)
ϵ-greedy policy ⇔ a stochastic policy where
a s =
Q s, a ′
argmax
′
with probability 1 − ϵ
∼ U a ′ ∈ A s
with probability ϵ
a
74 / 82
SARSA
for all s, a ∈ S × A
0 if s ∈ F
Q̂ s, a =
rnd otherwise
for many, many trials
sample s ∈ S \ F
sample a ∈ A(s) ϵ-greedily (⇔ using Q̂)
while s ∈
/F
s ′ ← Succ s, a
r ← Util s ′
sample a ′ ∈ A(s ′ ) ϵ-greedily (⇔ using Q̂)
update
h
i
Q̂ s, a ← Q̂ s, a + α r + γ Q̂ s ′ , a ′ − Q̂ s, a
s ← s′
a ← a′
75 / 82
note
SARSA
+ works without knowledge of T s ′, s, a or R s, a
+ converges to an optimal π∗ and Q∗ if the learning rate α is “small enough”
+ does not require episodes but also works just with samples of transitions
− requires the creation of many transitions
76 / 82
example
here, we show V s = max Q̂ s, a because Q̂ s, a is difficult to visualize
a
r[t + 1] = Util s[t + 1] , α = 0.25, γ = 0.99, ϵ = 0.1, episodes = 100, 000
-10.0
+6.1
+6.3
+6.6
+6.9
+7.2
+7.4
+7.7
+7.9
+8.3
+8.5
+8.6
+8.4
+9.1
+9.3
+9.5
+6.0
+6.0
+6.2
+6.2
+6.8
+6.9
+7.3
+7.7
+7.8
+8.1
+8.5
+8.6
+9.2
+9.6
+9.8
+5.4
+5.9
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
+9.8
+10.0 +10.0
+4.5
+5.4
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
+9.6
+9.8
+4.2
+4.6
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
+9.3
+9.6
+4.6
+5.0
+4.8
+5.3
+5.7
+6.3
+6.8
+6.9
+7.2
+7.7
+7.7
+8.1
+8.8
+9.0
+9.4
+5.0
+5.6
+5.8
+5.9
+6.3
+7.0
+6.8
+7.3
+7.6
+8.0
+8.2
+8.4
+8.6
+8.8
+8.9
+6.8
77 / 82
remarks (1)
for an ϵ-greedy policy, the SARSA updates cause the policy to become
more and more greedy over time
in the limit t → ∞, the policy will become deterministic ⇔ ϵ = 0-greedy
this behavior will be enforced / accelerated when working with ϵt = 1/t
78 / 82
remarks (2)
for everything, we discussed above
it is strongly suggested to work with γ ≈ 1
it will be beneficial to work with time-dependent learning rates such as αt =
1
t+1
note: if we opt for doing this, we must choose the rates αt such that they obey
∞
X
t=0
∞
X
αt = ∞
α2t < ∞
t=0
(these are the Robbins-Monro conditions which are of fundamental importance
for theory and practice of iterative stochastic approximation and/or optimization)
79 / 82
summary
80 / 82
we now know about
model-based and model-free algorithms for reinforcement learning
practical / pragmatic advantages of model-free algorithms
the notions of on-policy and off-policy learning
in particular . . .
81 / 82
we now know about
model-based algorithms
policy iteration for control ⇔ policy optimization
value iteration for prediction ⇔ policy evaluation
model-free algorithms
Monte Carlo methods for prediction and control
temporal difference learning with V functions ⇔ TD(0) for prediction
temporal difference learning with Q functions ⇔ SARSA for (ϵ-greedy) control
82 / 82