/
Text
Reinforcement Learning
Prof. Christian Bauckhage
1 / 70
lecture 10
Q-learning
in this lecture, it’s finally time to meet the real contender in tabular reinforcement
learning, namely Q-learning
we will discuss Q-learning in stochastic- and deterministic environments and look
at an (arguably interesting) application of the latter
2 / 70
outline
recap
Q-learning
in stochastic environments
in deterministic environments
an interesting application ?!?
summary
3 / 70
recap
4 / 70
prediction and control
the problems of evaluating and optimizing policies
model-based reinforcement learning
allows for prediction
and/or control in settings where a complete MDP
model S, A, T, R of an environment is available
model-free reinforcement learning
allows for prediction and/or control in settings where only incomplete
knowledge about states, actions, and basic environment dynamics is
available
5 / 70
model-based policy iteration
repeat
for all s Ph
i
P
Vπ s =
R s, a + γ Vπ s ′ p s ′ s, a π a s
// evaluate
s′
a
for all s
P
π s ← argmax R s, a + γ Vπ s ′ p s ′ s, a
// improve
s′
a
until convergence to π∗
model-based value iteration
repeat
for all s
P
Vt+1 s ← max R s, a + γ Vt s ′ p s ′ s, a
a
// update
s′
until convergence to V∗
use V∗ to determine π∗
6 / 70
model-free temporal difference updates for value functions
h
i
V̂ St ← V̂ St + α Rt+1 + γ V̂ St+1 − V̂ St
0 < α ≪ 1 is a learning rate
TD(0) for prediction (based on episodes)
for many,many trials
s∼U S\F
while s ∈
/F
a∼π · s
s ′ ← Succ s, a
r ← Util s ′
h
i
V̂ s ← V̂ s + α r + γ V̂ s ′ − V̂ s
// outcome depends on “physics engine”
// outcome depends on “physics engine”
s ← s′
7 / 70
model-free temporal difference updates for quality functions
h
i
Q̂ St , At ← Q̂ St , At + α Rt+1 + γ Q̂ St+1 , At+1 − Q̂ St , At
0 < α ≪ 1 is a learning rate
SARSA for control (based on episodes)
for many,many trials
s∼U S\F
a ∼ ϵ-greedy policy (using Q̂)
while s ∈
/F
s ′ ← Succ s, a
r ← Util s ′
a ′ ∼ ϵ-greedy policy (using
Q̂)
h
i
Q̂ s, a ← Q̂ s, a + α r + γ Q̂ s ′ , a ′ − Q̂ s, a
// outcome depends on “physics engine”
// outcome depends on “physics engine”
s ← s′
a ← a′
8 / 70
ϵ-greedy policy ⇔ a stochastic policy where
Q s, a ′
with probability 1 − ϵ
argmax
a′
a=
∼ U a ′ ∈ A s
with probability ϵ
on-policy methods
attempt to improve a given policy π for decision making
off-policy methods
attempt to improve a target policy πt different from a behavior policy πb used
to generate data; πb is usually stochastic whereas πt is usually deterministic
9 / 70
benefits of temporal difference methods
they can learn before knowing the final outcome of a episode
⇔ they can learn from transitions or from incomplete episodes
they apply to episodic and to continuing tasks / environments
10 / 70
just for completeness . . .
n-step return methods
update V̂ or Q̂ not after one step but after n steps using n-step returns
Gt:t+n = Rt+1 + γ Rt+2 + · · · + γn−1 Rt+n + γn Vt+n−1 St+n
Gt:t+n =
Rt+1 + γ Rt+2 + · · · + γn−1 Rt+n
+ γn Q
t+n−1
St+n , At+1
where neither is available until time t + n
⇒ TD(n) and SARSA(n) update V̂ St and Q̂ St , At only n steps after St , At have occurred in an episode
h
i
V̂t+n St ← V̂t+n−1 St + α Gt:t+1 − V̂t+n−1 St
h
i
Q̂t+n St , At ← Q̂t+n−1 St , At + α Gt:t+1 − Q̂t+n−1 St , At
while these are a bit messy to implement (not too messy though), they constitute a compromise between
n = 1 (common TD) and an n = ∞ (Monte Carlo) methods and usually learn faster than either extreme
“one can show” the error reduction property of n-step returns which implies that n-step methods converge
11 / 70
λ-return methods
consider averages of n-step returns such as, say, 12 Gt:t+3 + 12 Gt:t+6
a very general form of such averaged returns are λ-returns
∞
X
Gλ
λn−1 Gt:t+n
t = 1−λ
n=1
where 0 ⩽ λ ⩽ 1 is a decay rate
⇒ λ-returns provide another compromise between one-step TD methods and Monte Carlo methods
TD(λ) played a key role in Tesauro’s TD-Gammon, the first AI program ever that could play a truly
“interesting” game (backgammon) at the level of seasoned human players
G. Tesauro, Temporal Difference Learning and TD-Gammon, Communications of the ACM, 38 (3), 1995
12 / 70
Q-learning
13 / 70
finally, it’s time to meet the real contender in tabular reinforcement learning . . .
14 / 70
note
“one can show” that this process will converge (for α “small enough”)
Q-learning updates
h
i
Q̂ St , At ← Q̂ St , At + α Rt+1 + γ max Q̂ St+1 , a − Q̂ St , At
a
15 / 70
Q-learning (from episodes)
for all s, a ∈ S × A
0 if s ∈ F
Q̂ s, a =
rnd otherwise
for many, many trials
sample s ∈ S \ F
while s ∈
/F
sample a ∈ A(s) ϵ-greedily (using Q̂)
s ′ ← Succ s, a
′
r ← Util s
h
i
Q̂ s, a ← Q̂ s, a + α r + γ max Q̂ s ′ , a ′ − Q̂ s, a
a′
s ← s′
16 / 70
Q-learning (from transitions)
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̂)
s ′ ← Succ s, a
r ← Util s ′
h
i
Q̂ s, a ← Q̂ s, a + α r + γ max Q̂ s ′ , a ′ − Q̂ s, a
a′
17 / 70
note
Q-learning
+ works without knowledge of T s ′, s, a or R s, a
+ converges to an optimal Q∗ and π∗ if the learning rate α is “small enough”
+ does not require episodes but also works just with samples of transitions
± is exploration insensitive ⇔ converges to an optimal solution independent
of the exploration strategy(i.e. could be different than ϵ-greedy selection)
as long as every pair s, a is tried “often enough” (see next slide)
− requires the creation of many transitions
18 / 70
note
Q-learning faces the exploration / exploitation dilemma
⇔ without invoking some form of exploration, Q-learning won’t really learn
above, we cunningly addressed this issue by sampling action a ∈ A(s)
using an ϵ-greedy policy
this is common practice and how the exploration / exploitation dilemma
is usually handled during Q-learning
19 / 70
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
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+9.6
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+9.6
+9.8
+7.0
+7.2
-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
+6.9
+7.0
-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
+6.7
+6.9
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
+9.4
+9.6
+6.9
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+6.7
+6.9
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+7.7
20 / 70
comparison
SARSA
-10.0
Q-learning
+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
-10.0
vs
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+9.6
+9.6
+9.8
+7.0
+7.2
-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
+6.9
+7.0
-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
+6.7
+6.9
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
+9.4
+9.6
+6.9
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+6.7
+6.9
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+7.7
21 / 70
note
SARSA is an on-policy control algorithm
⇔ updates Q̂ using value of the next state s ′ and an ϵ-greedy policy’s action a ′
⇔ estimates values assuming the current ϵ-greedy policy is followed throughout
Q-learning is an off-policy control algorithm
⇔ updates Q̂ using value of the next state s ′ and a deterministic policy’s action a ′
⇔ estimates values assuming a greedy policy was followed but actually follows
an ϵ-greedy policy, i.e. implicitly considers two policies, namely
πb ⇔ stochastic ϵ-greedy policy
πt ⇔ deterministic greedy policy
(when sampling a)
(when updating Q̂ s, a )
22 / 70
question
can we be sure that Q-learning works ?
⇔ are we guaranteed that the following updates converge to Q∗ ?
h
i
Q̂ s, a ← Q̂ s, a + α r + γ max
Q̂ s ′ , a ′ − Q̂ s, a
′
a
⇔ are we guaranteed that the following sequence converges to Q∗ ?
h
i
Q̂t+1 St , At = 1 − α Q̂t St , At + α Rt+1 + γ max Q̂t St+1 , a
a
23 / 70
answer
for a constant learning rate α, we actually have no real guarantee
however, we have the following result (theorem on the next slide) from
T. Jaakkola, M.I. Jordan, S.P. Singh, Convergence of Stochastic
Iterative Dynamic Programming Algorithms, Proc. NIPS, 1993
24 / 70
Theorem (Jaakkola, Jordan, Singh (1993))
given an MDP S, A, T, R , the following (modified) Q-learning algorithm
h
i
h
i
Qt+1 St , At = 1 − αt St , At Qt St , At + αt St , At Rt+1 + γ max Qt St+1 , a ′
a′
converges to the optimal quality function Q∗ s, a , if
the state- and action spaces S and A are finite
the variance V Rt of reward values is bounded
P
P
the Robins-Monro conditions t αt St , At = ∞ and t α2t St , At < ∞ do hold
for their proof, we need the following . . .
25 / 70
Lemma (Jaakkola, Jordan, Singh (1993))
a stochastic process ∆t over Rn such that
∆t+1 (x) = 1 − αt (x) ∆t (x) + αt (x) ft (x)
converges to 0 with probability 1, if
P
P
0 ⩽ αt (x) < 1, t αt (x) = ∞, t α2t (x) < ∞
E ft (x)
V ft (x)
fpast
⩽ γ ∆t where 0 < γ < 1
h
i2
fpast ⩽ C 1 + ∆t
where C > 0
this is a statement on the convergence of a process
under what the business calls “mild conditions”
we will not prove this statement but also recall . . .
26 / 70
Bellman optimality equation for Q∗ s, a
X
Q∗ s, a = R s, a + γ
max Q∗ s ′ , a ′ p s ′ s, a
s′
a′
⇔ if we consider the Bellman optimality operator Bmax with
X
max Q s ′ , a ′ p s ′ s, a
Bmax Q s, a = R s, a + γ
s′
a′
we realize that Q∗ s, a is a fixed point of this operator
moreover, Bmax is a contraction operator such that
Bmax Q1 − Bmax Q2
∞
⩽ γ Q1 − Q2
∞
here is a quick sanity check . . .
27 / 70
we have that
Bmax Q1 − Bmax Q2
= max R s, a − γ
s,a
= max γ
s,a
⩽ max γ
s,a
⩽ max γ
s,a
= max γ
s,a
X
∞
X
max Q1 s ′ , a ′ p s ′ s, a − R s, a − γ
max Q2 s ′ , a ′ p s ′ s, a
s′
a′
s′
a′
Xh
i
max Q1 s ′ , a ′ − max Q2 s ′ , a ′ p s ′ s, a
a′
s′
X
max Q1 s ′ , a ′ − max Q2 s ′ , a ′ p s ′ s, a
a′
s′
X
s′
a′
a′
max Q1 s ′′ , a ′ − Q2 s ′′ , a ′ p s ′ s, a
s ′′ ,a ′
X
Q1 − Q2
s′
= γ Q1 − Q2
∞
∞
p s ′ s, a
⩽ Q1 − Q2
∞
28 / 70
Proof of the theorem by Jaakkola, Jordan, Singh (1993).
consider the Q-learning updates
h
i
h
i
Qt+1 St , At = 1 − αt St , At Qt St , At + αt St , At Rt+1 + γ max Qt St+1 , a ′
a′
subtracting Q∗ from both sides, adding 0 = αt ∆t − αt ∆t on the right, and defining
∆t s, a = Qt s, a − Q∗ s, a
ft s, a = R s, a + γ max Qt s ′ , a ′ − Q∗ s, a
a′
gives us the following stochastic process
h
i
∆t+1 St , At = 1 − αt St , At ∆t St , At + αt St , At ft St , At
29 / 70
Proof (cont.)
we have
h
i Xh
i
R St , At + γ max Qt s ′ , a ′ − Q∗ St , At p s ′ St , At
E ft St , At fpast =
s′
a′
= Bmax Qt St , At − Q∗ St , At
= Bmax Qt St , At − Bmax Q∗ St , At
⇒ we have
h
i
E ft St , At fpast ⩽ γ Qt St , At − Q∗ St , At = γ ∆t St , At
30 / 70
Proof (cont.)
we also have
h
i
h
i2
V ft St , At fpast = E R St , At + γ max Qt St+1 , a ′ − Q∗ St , At − Bmax Qt St , At + Q∗ St , At
a′
h
i2
= E R St , At + γ max Qt St+1 , a ′ − Bmax Qt St , At
a′
h
i
= V R St , At + γ max Qt St+1 , a ′ fpast
a′
next, we argue more intuitively (i.e. less rigorously) than Jaakkola, Jordan, and Singh
for the dirty details, ask our theoretical computer scientists ;-)
31 / 70
recall
h
i2
2
V X =E X−E X
= E X2 − E X
2
V X Y = X2 Y − E X Y
2
h
i2
V X + Y Z = E (X + Y)2 Z − E X + Y Z = E X 2 + Y 2 + 2XY Z − E X Z + E Y Z
2
2
= E X 2 Z + E Y 2 Z + 2 E XY Z − E X Z − E Y Z − 2 E X Z E Y Z
= V X Z + V Y Z + 2 cov X, Y Z
cov X, Y Z = E XY Z − E Y Z E Y Z
32 / 70
Proof (cont.)
we found
h
i
h
i
V ft St , At fpast = V R St , At + γ max Qt St+1 , a ′ fpast
a′
using the above identities, we can rewrite this as
i
h
i
h
i
h
V ft St , At fpast = V R St , At fpast + V γ max Qt St+1 , a ′ fpast + 2 cov R St , At , γ max Qt St+1 , a ′ fpast ∈ O Q2t
a′
a′
|
{z
}
|
{z
} |
{z
}
bounded by assumption
qudratic in Qt
linear in Qt
if we finally write maxa ′ Qt St+1 , a ′ = maxa ′ ∆t St+1 , a ′ + Q∗ St+1 , a ′ , we realize that
i
h
i2
h
V ft St , At fpast ⩽ C 1 + ∆t
(for some large enough C)
33 / 70
Proof (cont.)
for our definitions
∆t s, a = Qt s, a − Q∗ s, a
ft s, a = R s, a + γ max Qt s ′ , a ′ − Q∗ s, a
a′
we have confirmed that
h
i
E ft St , At fpast ⩽ γ ∆t
h
i
h
i2
V ft St , At fpast ⩽ C 1 + ∆t
⇒ ∆t approaches 0
⇔
Qt approaches Q∗
34 / 70
remarks (1)
we could go through a similar ordeal to prove the convergence of SARSA
Q-learning was introduced by Watkins (1989), the first proof for its convergence
by Watkins and Dayan (1992) was a bit flawed
the proof by Jaakkola, Jordan, and Singh (1993) leans of heavy machinery and
there exist alternative but equally heavy proofs
people are still looking for more elementary arguments, e.g. Regehr and Ayoub
(2021), but the resulting proofs are still anything but trivial
so there are still opportunities to get famous ;-)
35 / 70
remarks (2)
the fact that the Robbins-Monro conditions must hold for the learning rate αt
of a provably converging Q-learning process translates to this slogan
“the learning rate must decay quickly, but not too quickly”
indeed, if αt would decay
too rapidly, Q-learning couldn’t “investigate” enough
state action pairs s, a to learn reliably
however, the most common practice is to work with constant learning rates α
(we did it ourselves)
if we opt for doing this, we have no convergence guarantees; yet it is common
(empirical) lore that Q-learning works just fine as long as α is “small enough”
however . . .
36 / 70
note
things are much easier in deterministic environments
a deterministic environment
is an environment where
each state-action pair s, a has a unique successor
ssa = Succ s, a
⇔ a deterministic environment is an environment where
transition probabilities reduce to
1 if s ′ = ssa
′
p s s, a =
0 otherwise
37 / 70
example
stochastic environment
deterministic environment
consider
consider
2
St = s =
0
2
St = s =
0
At = a = →
At = a = →
St+1 ∼ p s ′ s, a
St+1 ∼ p s ′ s, a
38 / 70
stochastic environment
we have
St+1 =
deterministic environment
we have
[1, 0]T
[3, 0]T
with prob 0.1
with prob 0.9
St+1 = [3, 0]T with prob 1.0
39 / 70
in a stochastic environment, we have
h
i
′
′
Q̂ s, a ← 1 − α Q̂ s, a + α Util s ′ + γ max
Q̂
s
,
a
′
a
⇔ new Q̂ s, a is a convex combination of the old Q̂ s, a and Util s ′ + γ max
Q̂ s ′ , a ′
′
a
s ′ is sampled according to p s ′ s, a
⇔ s ′ is stochastic and may be different any time we update Q̂ s, a
convex combination updates take this into account since they are “not overly eager”
40 / 70
in a deterministic environment, we have
h
i
′
Q̂ s, a ← 1 − α Q̂ s, a + α Util ssa + γ max
Q̂
s
,
a
sa
′
a
⇔ new Q̂ s, a is a convex combination of the old Q̂ s, a and Util ssa + γ max
Q̂ ssa , a ′
′
a
ssa is a function of s and a
⇔ ssa is deterministic and therefore the same every time we update Q̂ s, a
Q̂ ssa , a ′ ???
so then why only “carefully” step into the direction of Util ssa + γ max
′
a
41 / 70
claim w/o proof
the optimal learning rate for Q-learning in deterministic environments is
α=1
⇒ Q-learning updates for deterministic environments simplify considerably
Q̂ s, a ← Util ssa + γ max
Q̂ ssa , a ′
′
a
42 / 70
note
all our grid world examples up to now considered a deterministic environment
so far, we never took advantage of this but . . .
let’s see how deterministic Q-learning performs
43 / 70
w.r.t. the learned Q function, there is no discernible difference
Q-learning with α = 0.25
-10.0
Q-learning with α = 1
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+9.6
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+9.6
+9.8
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+9.6
+9.8
+7.0
+7.2
-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
+7.0
+7.2
-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
+6.9
+7.0
-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
+6.9
+7.0
-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
+6.7
+6.9
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
+9.4
+9.6
+6.7
+6.9
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
-10.0
+9.4
+9.6
+6.9
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+6.9
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+9.4
+6.7
+6.9
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+6.7
+6.9
+7.0
+7.2
+7.4
+7.6
+7.7
+7.9
+8.1
+8.3
+8.5
+8.6
+8.8
+9.0
+9.2
+7.7
-10.0
+9.6
+7.7
44 / 70
w.r.t. convergence speed, however, there is a difference
Q-learning with α = 0.25
Q-learning with α = 1
10.8
9.6
9.6
8.4
8.4
kQnew − Qoldk∞
12.0
10.8
kQnew − Qoldk∞
12.0
7.2
7.2
6.0
6.0
4.8
4.8
3.6
3.6
2.4
2.4
1.2
1.2
0.0
0.0
0
5000
10000
15000
20000
25000
t
30000
35000
40000
45000
50000
0
5000
10000
15000
20000
25000
t
30000
35000
40000
45000
50000
45 / 70
an interesting application ?!?
(why your instructor is interested in reinforcement learning)
46 / 70
observe
(deep) neural networks compute functions
y x = φ · · · φ W2 φ W1 x
= φL ◦ · · · ◦ φ2 ◦ φ1 s0
where, for instance
φl sl−1 = ReLU W l sl−1
20
21
WL
17
18
19
14
15
16
..
.
10
11
12
13
6
7
8
9
W2
W1
1
2
3
4
5
47 / 70
crazy idea
define an initial state and a goal state
S0 = x1 , x2 , . . . , xn
Sg = y1 , y2 , . . . , yn
(matrix of all n training inputs)
(matrix of all n training outputs)
and consider two humongous (infinite) sets of states and actions
S=
S ∈ Rml ×n
l = 0, . . . , L ∧ ml = # neurons in layer l
A = W ∈ Rml ×ml−1 l = 1, . . . , L ∧ ml = # neurons in layer l
then the (matrix valued) activations Sl = ReLU W l Sl−1 in layer l
are produced by a state transition function φ : S × A → S
48 / 70
seen like this, neural network training is to find a sequence of weight matrices
W1 : W2 : · · · : WL
where each W l ∈ A
crucially, when plugged into the network, the sought after sequence of weight
matrices should minimize a loss- or error function such as
E = ∥ y S0 − Sg ∥2
49 / 70
note
we can simultaneously “generalize and restrict” this idea
⇔ we might think of a (deep) network in terms of a function
y x = φL ◦ · · · ◦ φ2 ◦ φ1 x
that is composed of L elementary functions of more general type
if we had a library of N useful elementary functions, then training
becomes searching for an appropriate sequence φ1 : φ2 : · · · : φL
where
φl ∈
f1 , f2 , . . . , fN
50 / 70
the noisy bi-polar XOR problem
given labeled data
xi , yi
n
i=1
with
1
xi ∈ R2
yi ∈ −1, +1
train a binary classifier such that
−1 if x1 ≈ x2
y x =
+1 otherwise
0
−1
0
1
−1
51 / 70
library of elementary functions
R2 → R2
R2 → R
f0 (x) = id(x)
g1 (x) =
f1 (x) = R x
g2 (x) =
f2 (x) = wa wa x
f3 (x) = wb wTb x
T
P
Q
R→R
i xi
h1 (x) = 2 x
i xi
h2 (x) = −x
2
g3 (x) = ∥ x∥
h3 (x) = x − 1
T
h4 (x) = x + 1
T
h5 (x) = | x |
g4 (x) = wa x
g5 (x) = wb x
h6 (x) = exp − 12 x2
h7 (x) = tanh x
h8 (x) = sign x
R=
0
−1
+1
0
wa =
sin π
4
cos π
4
wb =
− sin π
4
cos π
4
52 / 70
possible solutions
+1
+1
1
1
0
−1
0
0
0
−1
1
−1
0
0
1
−1
−1
y x = h7 ◦ h2 ◦ g2 x
Y
= tanh −
xi
i
−1
y x = h2 ◦ h1 ◦ h6 ◦ h3 ◦ g2 ◦ f1 x
Y
2
= − 2 exp − 12
Rx i − 1
i
53 / 70
+1
+1
1
1
0
−1
0
0
0
−1
1
−1
0
0
1
−1
−1
y x = h3 ◦ h1 ◦ h6 ◦ g4 x
−1
y x = h2 ◦ h3 ◦ h1 ◦ h6 ◦ g5 x
54 / 70
+1
+1
1
1
0
−1
0
0
0
−1
1
−1
0
0
1
−1
−1
y x = h3 ◦ h1 ◦ h6 ◦ g3 ◦ f2 x
−1
y x = h2 ◦ h3 ◦ h1 ◦ h6 ◦ g3 ◦ f3 x
55 / 70
+1
+1
1
1
0
−1
0
0
0
0
−1
1
−1
0
−1
−1
y x = h8 ◦ h3 ◦ h5 ◦ g5 x
1
−1
y x = h8 ◦ g2 ◦ f1 x
Y
= sign
Rx i
i
and many more . . .
56 / 70
questions
it should be obvious that we can find appropriate sequences using MCTS, right ?
but can we also resort to Q-learning ?
⇔ can we set up search as Q-learning ?
answer
yes, we can !
57 / 70
modeling (1)
we are given X, y, and sets of functions
F = f0 , f1 , . . .
G = g1 , g2 , . . .
H = h1 , h2 , . . .
and also define a specific subset of H
D = h7 , h8
(functions R2 → R2 )
(functions R2 → R )
(functions R → R )
(decision functions)
58 / 70
modeling (2)
actions are elementary functions
a∈F∪G∪H
states are composite functions
s = aL ◦ · · · ◦ a2 ◦ a1 ◦ f0
where L ⩽ Lmax and the domain of al agrees with the range of al−1
⇔ states are sequences of actions (which always begin with f0 = id)
59 / 70
modeling (3)
the environment is deterministic, because
s ′ = Succ s, a = a ◦ s
we define a deterministic reward function
function R EWARD(s, a, rigorous)
if a ∈
/H
return −0.1
E = ∥a ◦ s X − y∥2
if rigorous ∧ E = 0
return 10
return 1/(E + 1)
60 / 70
so far, so good but . . .
if N and especially Lmax are large, an in-memory table implementation of Q s, a
will likely be infeasible due to combinatorics and memory requirements
(it may be impossible to list all states (i.e. valid sequences of actions))
however, in episodic Q-learning, we may grow such a table table iteratively and
do not have to worry about initializing all Q s, a up front
working with python, we can implement Q s, a as a dictionary of dictionaries
which we initialize as
Q = s0 : a : rnd a ∈ A s0
and extend similarly whenever we encounter a (successor) state s ′ not yet in Q
61 / 70
episodic Q-learning
overall procedure
more efficient reward computation
Q ← INITIALIZE Q( )
function R EWARD(a, z, y, rigorous)
if a ∈
/H
return −0.1
for t = 1, . . . , tmax
s ← f0
z ← f0 X
E = ∥z − y∥2
for l = 1, . . . , Lmax
ϵ-greedily sample “appropriate”
action a ∈ A(s) ⊂ F ∪ G ∪ H
s ′ ← a ◦ s
z ←a z
r ← R EWARD(a, z, y, rigorous)
return 1/(E + 1)
Q-dictionary book-keeping
if s ′ ̸∈ Q
EXTEND Q(Q, s ′ )
Q[s][a] ← r + γ · max Q[s ′ ][a ′ ]
a′
if a ∈ D
break
if rigorous ∧ E = 0
return 10
function INITIALIZE Q( )
return s0 : a : rnd a ∈ A s0
function EXTEND Q(Q, s ′ )
Q s ′ = a : rnd a ∈ A s ′
s ← s′
62 / 70
shortest sequences found (using rigorous = 0 and rigorous = 1)
+1
+1
1
1
0
−1
0
0
0
−1
1
−1
0
0
1
−1
Q
xi
h2 ◦ g2 (x) = −
i
−1
Q
xi
h8 ◦ h2 ◦ g2 (x) = sign −
−1
i
63 / 70
a 3 × 3 × 1 neural net would do something like this
+1
y
ϕ
1
ϕ
1
ϕ
0
−1
0
0
1
−1
1
x1
x2
−1
h7 ◦ h3 h7 ◦ h4 ◦ g4 (x) − h7 ◦ h3 ◦ g4 (x)
64 / 70
note
the resulting classifiers can explain themselves because their building blocks can !!!!!
def g1(X):
"""
fct: g1
dom: 2
rng: 1
act: compute the sum of all entries of the input vector to produce a scalar
"""
return np.sum(X,axis=0)
def getActionDescription(f):
docstr = f.__doc__
lines = docstr.split(’\n’)
for line in lines:
if line.lstrip().startswith(’act’):
return line.split(’:’)[-1].lstrip()
def explainActionSequence(s):
for i, a in enumerate(s):
print (’%d)’%(i+1), getActionDescription(a))
65 / 70
example
+1
>>> explainActionSequence([g5, h5, h3, h8])
1
0
−1
0
0
1
1)
2)
3)
4)
compute the inner product of the 2D input vector and w_b to produce a scalar
compute the absolute value of the input scalar to produce a new scalar
subtract 1 from the input scalar to produce a new scalar
compute sign of the input scalar to produce a new scalar
−1
−1
h8 ◦ h3 ◦ h5 ◦ g5 (x)
66 / 70
note
the above approach follows the paradigm of informed machine learning
⇔ it uses data-independent background knowledge in data-driven learning
based on expert knowledge in form of domain specific functional building blocks,
it automatically assembles interpretable and accountable models for the data
goal states and rewards could be tuned to reflect (combinations of) user targets
(quality, efficiency, security, . . . ) for the application at hand
67 / 70
future work
frequently occurring function sequences could be turned into building blocks
parameterized functions could be post-tuned using gradient-free optimization
B. Wulff, J. Schuecker, and C. Bauckhage, SPSA for Layer-wise Training of Deep Networks,
Proc. ICANN, 2018
functions with multiple arguments could maybe dealt with using currying ???
..
.
⇒ many of open questions ⇔ lot’s of potential for MSc theses
talk to me !!!
68 / 70
summary
69 / 70
we now know about
Q-learning in stochastic environments
h
i
′
′
Q̂ s, a ← Q̂ s, a + α R s, a + γ max
Q̂
s
,
a
−
Q̂
s,
a
′
a
⇔
h
i
h
i
′
′
Q̂ s, a ← 1 − α Q̂ s, a + α R s, a + γ max
Q̂
s
,
a
′
a
Q-learning in deterministic environments
Q̂ s, a ← Util ssa + γ max
Q̂ ssa , a ′
′
a
70 / 70