Deep Reinforcement Learning

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, M. Nau, S. Jaganathan, C. Liu, N. Maul, L. Folle,
K. Packhäuser, M. Zinnen
Pattern Recognition Lab, Friedrich-Alexander-Universität Erlangen-Nürnberg
April 24, 2023
Outline

Sequential Decision Making

Reinforcement Learning
Markov Decision Processes
Policy Iteration
Other Solution Methods

Deep Reinforcement Learning

Deep Q Learning
AlphaGo
AlphaGo Zero
Sequential Decision Making
 Sequential decision making: Multi-armed bandit problem

Action Formalize choosing a machine as action a at time t from a set A

Reward Action at has a different1 unknown pdf p(r |a) generating reward rt

1
This is not how gambling works

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 1
 Sequential decision making: Multi-armed bandit problem

Action Formalize choosing a machine as action a at time t from a set A

Reward Action at has a different1 unknown pdf p(r |a) generating reward rt
Policy Formalize choosing an action a as pdf π(a) which we call a policy

1
This is not how gambling works

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 1
 Evaluative Feedback

• Find action a producing the maximum expected reward over time t:

max E [p(r |a)]

a

• Difference to supervised learning: No feedback on what action to choose

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 2
 Evaluative Feedback

• Find action a producing the maximum expected reward over time t:

max E [p(r |a)]

a

• Difference to supervised learning: No feedback on what action to choose

• E [p(r |a)] is not known in advance

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 2
 Evaluative Feedback

• Find action a producing the maximum expected reward over time t:

max E [p(r |a)]

a

• Difference to supervised learning: No feedback on what action to choose

• E [p(r |a)] is not known in advance
• We can form a one-hot encoded vector r which reflects which action from a
caused the reward

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 2
 Evaluative Feedback

• Find action a producing the maximum expected reward over time t:

max E [p(r |a)]

a

• Difference to supervised learning: No feedback on what action to choose

• E [p(r |a)] is not known in advance
• We can form a one-hot encoded vector r which reflects which action from a
caused the reward
1
Pt
: Estimate the joint pdf online as t i =1 ri := Qt (a)

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 2
 Evaluative Feedback

• Find action a producing the maximum expected reward over time t:

max E [p(r |a)]

a

• Difference to supervised learning: No feedback on what action to choose

• E [p(r |a)] is not known in advance
• We can form a one-hot encoded vector r which reflects which action from a
caused the reward
P
: Estimate the joint pdf online as 1t ti=1 ri := Qt (a)
• We call Qt (a) the action-value function, which changes with every new
information
A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 2
 Incremental update of Qt (a)

t
X
1
Qt +1 (a) = ri
t
i =1
t −1
!
1 X
= rt + ri
t
i =1
t −1
!
1 1 X
= rt + ( t − 1) ri
t t −1 i =1
1
= (rt + (t − 1)Qt (a))
t
1
= (rt + t Qt (a) − Qt (a))
t
1
= Qt (a) + (rt − Qt (a))
t
A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 3
 Exploitation

• Reward is maximized by a policy π(a) choosing maxa Qt (a)

• We exploit a known good action
• This is a deterministic1 policy called greedy action selection

1
If Qt is equal for two a, the tie has to be broken e.g. randomly

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 4
 Exploitation

• Reward is maximized by a policy π(a) choosing maxa Qt (a)

• We exploit a known good action
• This is a deterministic1 policy called greedy action selection
• However we need to obtain samples ra

1
If Qt is equal for two a, the tie has to be broken e.g. randomly

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 4
 Exploitation

• Reward is maximized by a policy π(a) choosing maxa Qt (a)

• We exploit a known good action
• This is a deterministic1 policy called greedy action selection
• However we need to obtain samples ra
: This means we cannot follow the greedy action selection policy for learning

1
If Qt is equal for two a, the tie has to be broken e.g. randomly

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 4
 Exploitation Exploration

• Reward is maximized by a policy π(a) choosing maxa Qt (a)

• We exploit a known good action
• This is a deterministic1 policy called greedy action selection
• However we need to obtain samples ra
: This means we cannot follow the greedy action selection policy for learning
: Sometimes explore by selecting other moves which could potentially be better
1
If Qt is equal for two a, the tie has to be broken e.g. randomly

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 4
 We sample discrete actions a from π(a), but what distributions can we use?

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 5
 We sample discrete actions a from π(a), but what distributions can we use?
Uniform random
1
π(a) =
|A|

• |A| is the cardinality of the set of different actions A

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 5
 We sample discrete actions a from π(a), but what distributions can we use?
Uniform random
1
π(a) =
|A|

• |A| is the cardinality of the set of different actions A

Epsilon Greedy
(
1− if a = maxQt (a)
π(a) = a
/(n − 1) else

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 5
 We sample discrete actions a from π(a), but what distributions can we use?
Uniform random
1
π(a) =
|A|

• |A| is the cardinality of the set of different actions A

Epsilon Greedy
(
1− if a = maxQt (a)
π(a) = a
/(n − 1) else

Softmax

eQt (a)/τt
π(a) = P|A|
n =1 eQt (an )/τt

• τt is called temperature and used to decrease exploration over time

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 5
 Summary

So far we ...
• considered sequential decision making in a setting known as multi-armed
bandits

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 6
 Summary

So far we ...
• considered sequential decision making in a setting known as multi-armed
bandits
• found out that estimating a function Q (a) and the greedy action selection
policy π(a) = maxQ (a) maximized our reward
a

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 6
 Summary

So far we ...
• considered sequential decision making in a setting known as multi-armed
bandits
• found out that estimating a function Q (a) and the greedy action selection
policy π(a) = maxQ (a) maximized our reward
a
• learned that exploration of different actions is necessary

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 6
 Summary

So far we ...
• considered sequential decision making in a setting known as multi-armed
bandits
• found out that estimating a function Q (a) and the greedy action selection
policy π(a) = maxQ (a) maximized our reward
a
• learned that exploration of different actions is necessary
• assumed rewards didn’t depend on a state of the world

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 6
 Summary

So far we ...
• considered sequential decision making in a setting known as multi-armed
bandits
• found out that estimating a function Q (a) and the greedy action selection
policy π(a) = maxQ (a) maximized our reward
a
• learned that exploration of different actions is necessary
• assumed rewards didn’t depend on a state of the world
• and our action at time t doesn’t influence the rewards from a at t +1

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning April 24, 2023 6
Deep Reinforcement Learning - Part 2

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, M. Nau, S. Jaganathan, C. Liu, N. Maul, L. Folle,
K. Packhäuser, M. Zinnen
Pattern Recognition Lab, Friedrich-Alexander-Universität Erlangen-Nürnberg
April 24, 2023
Reinforcement Learning
 Associativity

We extend the multi-armed bandits problem:

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 8
 Associativity

We extend the multi-armed bandits problem:

• We introduces a state of the world at any time t: st
• Rewards now additionally depend on the state st :

p(rt |st , at )

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 8
 Associativity

We extend the multi-armed bandits problem:

• We introduces a state of the world at any time t: st
• Rewards now additionally depend on the state st :

p(rt |st , at )

• However this setting is known as contextual bandit

• In the full reinforcement learning problem, actions influence the state:

p(st +1 |st , at )

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 8
 Markov Decision Processes

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 9
 Markov Decision Process

Agent

st +1 rt +1 at

Environment

Action An action at at time t from a set A

State A state st from a set S

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 10
 Markov Decision Process

Agent

st +1 rt +1 at

Environment

Action An action at at time t from a set A

State A state st from a set S
A state transition pdf p(st +1 |st , at )

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 10
 Markov Decision Process

Agent

st +1 rt +1 at

Environment

Action An action at at time t from a set A

State A state st from a set S
A state transition pdf p(st +1 |st , at )
Reward Transition produces reward rt +1 ∈ R ⊂ R according to p(rt +1 |st , at )

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 10
 Markov Decision Process

Agent

st +1 rt +1 at

Environment

Action An action at at time t from a set A

State A state st from a set S
A state transition pdf p(st +1 |st , at )
Reward Transition produces reward rt +1 ∈ R ⊂ R according to p(rt +1 |st , at )
Policy Agents choose actions at by a policy π(a|s)

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 10
 Markov Decision Process

Agent

st +1 rt +1 at

Environment

Action An action at at time t from a set A

State A state st from a set S
A state transition pdf p(st +1 |st , at )
Reward Transition produces reward rt +1 ∈ R ⊂ R according to p(rt +1 |st , at )
Policy Agents choose actions at by a policy π(a|s)
If all those sets are finite we call this a finite MDP
A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 10
 A B

+5

+10 B’

A’

: Here s is the field we are currently on.

• The agent can move in all four directions
• Any action which would leave the grid has p(st +1 |at , st ) equal to a δ
distribution on st +1 = st and a similarly deterministic rt = −1

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 11
 A B

+5

+10 B’

A’

: Here s is the field we are currently on.

• The agent can move in all four directions
• Any action which would leave the grid has p(st +1 |at , st ) equal to a δ
distribution on st +1 = st and a similarly deterministic rt = −1
• Every state we reach other than tile A0 and B 0 deterministically causes rt =0

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 11
 A B

+5

+10 B’

A’

: Here s is the field we are currently on.

• The agent can move in all four directions
• Any action which would leave the grid has p(st +1 |at , st ) equal to a δ
distribution on st +1 = st and a similarly deterministic rt = −1
• Every state we reach other than tile A0 and B 0 deterministically causes rt =0
• On A or B any action will take us to A0 or B 0 respectively
A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 11
 Example policy

• Policies now depend on st

• We can extend the uniform random policy to be independent from st

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 12
 Example policy

• Policies now depend on st

• We can extend the uniform random policy to be independent from st
• However there’s no reason to believe that this policy is any good

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 12
 Example policy

• Policies now depend on st

• We can extend the uniform random policy to be independent from st
• However there’s no reason to believe that this policy is any good
• How can we estimate good policies?
A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 12
 What is a good policy?

: We have to be precise about good

• Preliminary we have to state two kinds of tasks
1. Episodic tasks which have an end
2. Continuing tasks which are infinitely long
• Unify them using a terminal state in episodic tasks which only transition to
themselves with deterministic rt =0
• Goal is to maximize the future return

T
X
max gt = γ k −t −1 rk
π(st ,at )
k =t +1

• γ is a discount reducing influence of rewards far in the future

• γ ∈ (0, 1] meaning that γ = 1 is allowed as long as T 6= ∞

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 2 April 24, 2023 13
Deep Reinforcement Learning - Part 3

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, M. Nau, S. Jaganathan, C. Liu, N. Maul, L. Folle,
K. Packhäuser, M. Zinnen
Pattern Recognition Lab, Friedrich-Alexander-Universität Erlangen-Nürnberg
April 24, 2023
 Policy Iteration

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 15
 • Before we used the action-value function Q (a)

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 16
 • Before we used the action-value function Q (a)
• Now at has to depend on st

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 16
 • Before we used the action-value function Q (a)
• Now at has to depend on st
: Use an oracle predicting the future reward gt following π(st , at ) from st

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 16
 • Before we used the action-value function Q (a)
• Now at has to depend on st
: Use an oracle predicting the future reward gt following π(st , at ) from st
• We introduce the state-value function Vπ (s)
" T
#
X
Vπ (s) = Eπ [gt |st ] = Eπ γ k −t −1 rk |st
k =t +1

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 16
 State-value Function Example

A B

+5

+10 B’

A’

The definition of the gridworld

• Recall our grid example

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 17
 State-value Function Example

A B 3.3 8.8 4.4 5.3 1.5

+5 1.5 3.0 2.3 1.9 0.5

+10 B’ 0.1 0.7 0.7 0.4 -0.4

-1.0 -0.4 -0.4 -0.6 -1.2

A’ -1.9 -1.3 -1.2 -1.4 -2.0

The definition of the gridworld Vπ (s) for the uniform random policy

• Recall our grid example

• Some edge tiles are negative since the policy can’t control the move

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 17
 State-value Function Example

A B 3.3 8.8 4.4 5.3 1.5

+5 1.5 3.0 2.3 1.9 0.5

+10 B’ 0.1 0.7 0.7 0.4 -0.4

-1.0 -0.4 -0.4 -0.6 -1.2

A’ -1.9 -1.3 -1.2 -1.4 -2.0

The definition of the gridworld Vπ (s) for the uniform random policy

• Recall our grid example

• Some edge tiles are negative since the policy can’t control the move
• What if we use the greedy action selection policy on this Vπ (s) ?

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 17
 State-value Function Example

A B 3.3 8.8 4.4 5.3 1.5

+5 1.5 3.0 2.3 1.9 0.5

+10 B’ 0.1 0.7 0.7 0.4 -0.4

-1.0 -0.4 -0.4 -0.6 -1.2

A’ -1.9 -1.3 -1.2 -1.4 -2.0

The definition of the gridworld Vπ (s) for the uniform random policy

• Recall our grid example

• Some edge tiles are negative since the policy can’t control the move
• What if we use the greedy action selection policy on this Vπ (s) ?
• We get a better policy!
A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 17
 Action-value function

• Before we used the action-value function Q (a)

• Now we introduced Vπ (s) filling a similar role

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 18
 Action-value function

• Before we used the action-value function Q (a)

• Now we introduced Vπ (s) filling a similar role
• We can also introduce the action-value function Qπ (s, a)
• Basically this accounts for the transition probabilities
" T
#
X
Qπ (s, a) = Eπ [gt |st , at ] = Eπ γ k −t −1 rk |st , at
k =t +1

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 18
 Are Value Functions Created Equal?

1
in a finite MDP

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 19
 Are Value Functions Created Equal?

• No.
• There can only be one1 optimal V ∗ (s)

1
in a finite MDP

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 19
 Are Value Functions Created Equal?

• No.
• There can only be one1 optimal V ∗ (s)
• We can state its existence without referring to a specific policy:

V ∗ (s) = maxVπ (s) (1)

π

1
in a finite MDP

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 19
 Are Value Functions Created Equal?

• No.
• There can only be one1 optimal V ∗ (s)
• We can state its existence without referring to a specific policy:

V ∗ (s) = maxVπ (s) (1)

π

• Q ∗ (s, a) can also be defined and is related to V ∗ (st )by:

Q ∗ (s, a) = E [rt +1 + γ V ∗ (st +1 )] (2)

1
in a finite MDP

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 19
 Optimal Value-function Example

3.3 8.8 4.4 5.3 1.5

1.5 3.0 2.3 1.9 0.5

0.1 0.7 0.7 0.4 -0.4

-1.0 -0.4 -0.4 -0.6 -1.2

-1.9 -1.3 -1.2 -1.4 -2.0

Vπ (s) for the uniform random policy

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 20
 Optimal Value-function Example

3.3 8.8 4.4 5.3 1.5 22.0 24.4 22.0 19.4 17.5

1.5 3.0 2.3 1.9 0.5 19.8 22.0 19.8 17.8 16.0

0.1 0.7 0.7 0.4 -0.4 17.8 19.8 17.8 16.0 14.4

-1.0 -0.4 -0.4 -0.6 -1.2 16.0 17.8 16.0 14.4 13.0

-1.9 -1.3 -1.2 -1.4 -2.0 14.4 16.0 14.4 13.0 11.7

Vπ (s) for the uniform random policy V∗

• Observe that V ∗ is strictly positive since it’s deterministic

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 20
 Optimal Policies

• Policies can now be ordered: π ≥ π 0 if and only if Vπ (s) ≥ Vπ0 (s), ∀s ∈ S

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 21
 Optimal Policies

• Policies can now be ordered: π ≥ π 0 if and only if Vπ (s) ≥ Vπ0 (s), ∀s ∈ S

• Any policy π with Vπ = V ∗ is an optimal policy π ∗

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 21
 Optimal Policies

• Policies can now be ordered: π ≥ π 0 if and only if Vπ (s) ≥ Vπ0 (s), ∀s ∈ S

• Any policy π with Vπ = V ∗ is an optimal policy π ∗
• This implies there might be more than one optimal policy

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 21
 Optimal Policies

• Policies can now be ordered: π ≥ π 0 if and only if Vπ (s) ≥ Vπ0 (s), ∀s ∈ S

• Any policy π with Vπ = V ∗ is an optimal policy π ∗
• This implies there might be more than one optimal policy
• Given either V ∗ or Q ∗ an optimal policy is directly obtained by greedy action
selection

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 21
 Greedy Action Selection on V ∗ (s) or Q ∗ (s, a)

π 0 (s, a) = Greedy Action Selection on Vπ (s) with

π(s, a) being uniform random

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 22
 Greedy Action Selection on V ∗ (s) or Q ∗ (s, a)

π 0 (s, a) = Greedy Action Selection on Vπ (s) with

π ∗ (s, a) = Greedy Action Selection on V ∗ (s)
π(s, a) being uniform random

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 22
 A Tool to Compute Optimal Value-functions

• We still need to compute V ∗ (s) and Q ∗ (s, a)

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 23
 A Tool to Compute Optimal Value-functions

• We still need to compute V ∗ (s) and Q ∗ (s, a)

• For this the Bellman equations can be utilized
• They are consistency conditions for the value functions
Bellman equation for Vπ (s)
X X
Vπ (s) = π(a|s) p(st +1 , r |s, a) [r + γ Vπ (st +1 )]
a s t + 1 ,r

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 23
 Policy Evaluation

• The Bellman equations form a system of linear equations which can be

solved for small problems
• Better: Iteratively solve, by turning the Bellman equations into update rules:
X X
Vk +1 (s) = π(a|s) p(st +1 , r |s, a) [r + γ Vk (st +1 )]
a s t +1 , r

For all s ∈S

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 24
 Policy Improvement

• Vπ (s) is used to guide our search for good policies

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 25
 Policy Improvement

• Vπ (s) is used to guide our search for good policies

• Another necessary step is to update the policy

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 25
 Policy Improvement

• Vπ (s) is used to guide our search for good policies

• Another necessary step is to update the policy
• However if we use greedy action selection an update of Vπ (s) is
simultaneously an update of π(s)

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 25
 Policy Improvement

• Vπ (s) is used to guide our search for good policies

• Another necessary step is to update the policy
• However if we use greedy action selection an update of Vπ (s) is
simultaneously an update of π(s)
• Now iterate evaluation of the greedy policy on Vπ (s)

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 25
 Policy Improvement

• Vπ (s) is used to guide our search for good policies

• Another necessary step is to update the policy
• However if we use greedy action selection an update of Vπ (s) is
simultaneously an update of π(s)
• Now iterate evaluation of the greedy policy on Vπ (s)
• Stop iterating if the policy stops changing

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 25
 Policy Improvement

• Vπ (s) is used to guide our search for good policies

• Another necessary step is to update the policy
• However if we use greedy action selection an update of Vπ (s) is
simultaneously an update of π(s)
• Now iterate evaluation of the greedy policy on Vπ (s)
• Stop iterating if the policy stops changing
• But is this guaranteed to work?

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 25
 Policy Improvement Theorem

• We consider changing a single action at in state st but following π

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 26
 Policy Improvement Theorem

• We consider changing a single action at in state st but following π

• In general if

Qπ (s, π 0 (s)) ≥ Vπ (s) , ∀s ∈ S =⇒ π 0 ≥ π

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 26
 Policy Improvement Theorem

• We consider changing a single action at in state st but following π

• In general if

Qπ (s, π 0 (s)) ≥ Vπ (s) , ∀s ∈ S =⇒ π 0 ≥ π

• This also implies:

Vπ 0 (s) ≥ Vπ (s)

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 26
 Policy Improvement Theorem

• We consider changing a single action at in state st but following π

• In general if

Qπ (s, π 0 (s)) ≥ Vπ (s) , ∀s ∈ S =⇒ π 0 ≥ π

• This also implies:

Vπ 0 (s) ≥ Vπ (s)
• Because we only select greedy we have Qπ (s, a) > Vπ (s) before
convergence

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 26
 Policy Improvement Theorem

• We consider changing a single action at in state st but following π

• In general if

Qπ (s, π 0 (s)) ≥ Vπ (s) , ∀s ∈ S =⇒ π 0 ≥ π

• This also implies:

Vπ 0 (s) ≥ Vπ (s)
• Because we only select greedy we have Qπ (s, a) > Vπ (s) before
convergence
• So iteratively updating Vπ (s) and using greedy action selection is
guaranteed to work here

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 26
 Policy Improvement Theorem

• We consider changing a single action at in state st but following π

• In general if

Qπ (s, π 0 (s)) ≥ Vπ (s) , ∀s ∈ S =⇒ π 0 ≥ π

• This also implies:

Vπ 0 (s) ≥ Vπ (s)
• Because we only select greedy we have Qπ (s, a) > Vπ (s) before
convergence
• So iteratively updating Vπ (s) and using greedy action selection is
guaranteed to work here
• We terminate if the policy no longer changes

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 26
 Policy Improvement Theorem

• We consider changing a single action at in state st but following π

• In general if

Qπ (s, π 0 (s)) ≥ Vπ (s) , ∀s ∈ S =⇒ π 0 ≥ π

• This also implies:

Vπ 0 (s) ≥ Vπ (s)
• Because we only select greedy we have Qπ (s, a) > Vπ (s) before
convergence
• So iteratively updating Vπ (s) and using greedy action selection is
guaranteed to work here
• We terminate if the policy no longer changes
• Last remark: If we don’t loop over all s ∈ S for policy evaluation, but update
the policy directly this algorithm is called Value iteration
A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 3 April 24, 2023 26
Deep Reinforcement Learning - Part 4

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, M. Nau, S. Jaganathan, C. Liu, N. Maul, L. Folle,
K. Packhäuser, M. Zinnen
Pattern Recognition Lab, Friedrich-Alexander-Universität Erlangen-Nürnberg
April 24, 2023
 Other Solution Methods

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 28
 Limitations

• Both policy iteration and value iteration require using the updated policies
during learning to obtain better approximations to V ∗ (s)

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 29
 Limitations

• Both policy iteration and value iteration require using the updated policies
during learning to obtain better approximations to V ∗ (s)
• For this reason we call them on-policy algorithms

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 29
 Limitations

• Both policy iteration and value iteration require using the updated policies
during learning to obtain better approximations to V ∗ (s)
• For this reason we call them on-policy algorithms
• Additionally we assumed the state-transition pdf and reward pdf are known

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 29
 Limitations

• Both policy iteration and value iteration require using the updated policies
during learning to obtain better approximations to V ∗ (s)
• For this reason we call them on-policy algorithms
• Additionally we assumed the state-transition pdf and reward pdf are known
• Can we relax this?

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 29
 Limitations

• Both policy iteration and value iteration require using the updated policies
during learning to obtain better approximations to V ∗ (s)
• For this reason we call them on-policy algorithms
• Additionally we assumed the state-transition pdf and reward pdf are known
• Can we relax this?
• Yes. The methods differ mostly how they perform policy evaluation

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 29
 Monte Carlo Techniques

Properties

• Only for episodic tasks

• Off-policy - learns V ∗ (s) by following any arbitrary π(s, a)
• Does not need information about dynamics of the environment

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 30
 Monte Carlo Techniques

Properties

• Only for episodic tasks

• Off-policy - learns V ∗ (s) by following any arbitrary π(s, a)
• Does not need information about dynamics of the environment

Scheme
• Generate an episode by using some policy
• Loop backwards over the episode accumulating the expected future reward
gt = gt +1 + rt +1
• If a state was not yet visited append gt to a list returns(st )
1
PN
• Update Vst = n=1 returnsn (st )
N

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 30
 Temporal Difference Learning

Properties

• On-policy
• Does not need information about dynamics of the environment

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 31
 Temporal Difference Learning

Properties

• On-policy
• Does not need information about dynamics of the environment

Scheme
• Loop and follow π(st , at )
• Use a from π(st , at ), observe rt , st +1
• Update: Vt +1 (s) = Vt (s) + α [rt + γ Vt (st +1 ) − Vt (st )]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 31
 Temporal Difference Learning

Properties

• On-policy
• Does not need information about dynamics of the environment

Scheme
• Loop and follow π(st , at )
• Use a from π(st , at ), observe rt , st +1
• Update: Vt +1 (s) = Vt (s) + α [rt + γ Vt (st +1 ) − Vt (st )]

• Converges to the optimal solution

• A variant of this estimates Q(s,a) and is known as SARSA

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 31
 Q Learning

Properties

• Off-policy
• Temporal difference type of method
• Does not need information about dynamics of the environment

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 32
 Q Learning

Properties

• Off-policy
• Temporal difference type of method
• Does not need information about dynamics of the environment

Scheme
• Loop and follow π(st , at ) derived from Qt (s, a) e.g. -greedy
• Use a from π(st , at ), observe rt , st +1
h i
• Update: Qt +1 (s, a) = Qt (st , at ) + α rt + γmaxQt (st +1 , at ) − Qt (st , at )
a

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 32
 If you have Universal Function Approximators

• What about just parametrizing π(st , at , w) by weights w and use some

loss-function L?

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 33
 If you have Universal Function Approximators

• What about just parametrizing π(st , at , w) by weights w and use some

loss-function L?
: Known as policy gradient and this instance is called REINFORCE

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 33
 If you have Universal Function Approximators

• What about just parametrizing π(st , at , w) by weights w and use some

loss-function L?
: Known as policy gradient and this instance is called REINFORCE
• Generate an episode using π(st , at , w)
• Go forwards in the episode: t = 0, ... , T − 1
t
• w = w + ηγ gt ∇w ln (π(at |st , w))

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 4 April 24, 2023 33
Deep Reinforcement Learning - Part 5

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, M. Nau, S. Jaganathan, C. Liu, N. Maul, L. Folle,
K. Packhäuser, M. Zinnen
Pattern Recognition Lab, Friedrich-Alexander-Universität Erlangen-Nürnberg
April 24, 2023
Deep Reinforcement Learning
 Deep Q Learning

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 35
 Atari Games: Human-level control through deep reinforcement
learning [4]

• Volodymyr Mnih et al. (Google DeepMind)

2013/2015
• Idea: Let a neural network play Atari
games!
• Input: Current and three subsequent video
frames from game
• Processed by network trained with
reinforcement learning Atari Pac-Man

• Goal: learn best controller movements

Source: Human-level control through deep reinforcement learning [4]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 36
 Atari Games: Human-level control through deep reinforcement
learning [4]

• Volodymyr Mnih et al. (Google DeepMind)

2013/2015
• Idea: Let a neural network play Atari
games!
• Input: Current and three subsequent video
frames from game
• Processed by network trained with
reinforcement learning Atari Pac-Man

• Goal: learn best controller movements

• Convolutional layers for frame processing,
fully-connected for final decision making

Source: Human-level control through deep reinforcement learning [4]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 36
 Learning Atari Games

Source: Human-level control through deep reinforcement learning [4]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 37
 Learning Atari Games

• Deep Q-network: Deep network that applies Q-learning

• State st of the game: current + 3 previous frames (image stack)
• 18 outputs associated with an action
: Each output estimates optimal action value for “its” action given the input
• Instead of label & cost function, update to maximize reward
• Reward: +1/-1 when game score increased/decreased, 0 otherwise
• -greedy policy with  decreasing to a low value during training
• Semi-gradient form of Q-learning to update network weights w
• Uses mini-batches to accumulate weight updates

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 38
 Target Network

• Weight update:
h i
wt +1 = wt + α rt +1 + γ max q̂ (st +1 , a, wt ) − q̂ (st , at , wt ) · ∇wt q̂ (st , at , wt )
a

• Problem: The target γ maxa q̂ (st +1 , a, wt ) is a function of wt .

: Target changes simultaneously with the weights we want to learn!
: Training can oscillate or diverge

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 39
 Target Network

• Weight update:
h i
wt +1 = wt + α rt +1 + γ max q̂ (st +1 , a, wt ) − q̂ (st , at , wt ) · ∇wt q̂ (st , at , wt )
a

• Problem: The target γ maxa q̂ (st +1 , a, wt ) is a function of wt .

: Target changes simultaneously with the weights we want to learn!
: Training can oscillate or diverge
• Idea: Use a second target network:
• After each C steps, copy weights of action-value network to a duplicate
network and keep them fixed
• Use output q̄ of “target network” as a target to stabilize:

γ max q̄ (st +1 , a, wt )
a

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 39
 Experience Replay

Goal: Reduce correlation between updates

• After performing action at for image stack st (state) and receiving reward rt ,
add (st , at , rt , st +1 ) to replay memory
: Memory accumulates experiences
• To update the network, draw random samples from memory, instead of taking
the most recent ones
: Removes dependence on current weights
: Increases stability

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 40
 Atari Breakout Example

Video on learning Atari Breakout. Click here

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 41
 AlphaGo

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 42
 Mastering the game of Go with deep neural networks and tree
search [1]

• Go is an ancient Chinese boardgame: Black

plays against white for control over the
board
• Simple rules but extremely high number of
possible moves and situations
• Performance on par with professional
human players thought years away

Traditional Go board

Source: [Link]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 43
 Challenges in Go

• Go is a “perfect information” game: No hidden information and no chance

• Theoretically, we can construct a full game tree and traverse it with Minimax
to find the best moves

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 44
 Challenges in Go

• Go is a “perfect information” game: No hidden information and no chance

• Theoretically, we can construct a full game tree and traverse it with Minimax
to find the best moves
• Problem: High number of legal moves (≈ 250 – chess ≈ 35)
• Games involve many moves (≈ 150)
: Exhaustive search is infeasible!

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 44
 Challenges in Go (cont.)

• Search tree can be pruned if we have an accurate evaluation function

• For chess (DeepBlue) already extremely complex and based on massive
human input
• For Go: “No simple yet reasonable evaluation function will ever be found for
Go.” (Müller 2002) [5]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 45
 Challenges in Go (cont.)

• Search tree can be pruned if we have an accurate evaluation function

• For chess (DeepBlue) already extremely complex and based on massive
human input
• For Go: “No simple yet reasonable evaluation function will ever be found for
Go.” (Müller 2002) [5]
• Still: AlphaGo beat Lee Sedol and Ke Jie, two of the world’s strongest
players in 2016 and 2017!

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 45
 Mastering the game of Go with deep neural networks and tree
search [1]

• AlphaGo was developed by Silver et al. (also Google DeepMind)

• Combination of multiple methods:
• Deep neural networks
• Monte Carlo tree search (MCTS)
• Supervised learning and
• Reinforcement learning

• First improvement compared to a full tree search: Monte Carlo Tree Search
(MCTS)
• Networks to support efficient search through tree

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 46
 Monte Carlo Tree Search

• Idea: Run many Monte Carlo simulations of episodes (=entire Go games) to

select action (=where to place a stone)
• Starting from a root node representing the current state, MCTS iteratively
extends the search tree

Source: Mastering the game of go without human knowledge [2]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 47
 Monte Carlo Tree Search (cont.)

Algorithm:

• Selection: Starting at root, traverse with tree policy to a leaf node

• Expansion: (Optional) add one or more child nodes to the current leaf
• Simulation: From the current or the child node, simulate episode with
actions according to rollout policy
• Backup: Propagate the received reward back through the tree

• Repeat for a certain amount of time, then stop

• Then, choose action from root node according to accumulated statistics
• Start again with new root node

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 48
 Monte Carlo Tree Search (cont.)

• Tree policy guides in how far successful paths are frequented more often.
• Typical exploration/exploitation trade-off.
• Problem: Estimation via MCTS not accurate enough for Go.

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 49
 Monte Carlo Tree Search (cont.)

• Tree policy guides in how far successful paths are frequented more often.
• Typical exploration/exploitation trade-off.
• Problem: Estimation via MCTS not accurate enough for Go.

• Ideas in AlphaGo:
• Control tree expansion by using a neural network to find promising actions.
• Improve value estimation by a neural network.

• More efficient extension & evaluation of search tree : better at Go!

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 49
 Deep Neural Networks for Go

Utilization of three different networks:

• Policy network: Suggests the next move in leaf nodes for extension
• Value network: Given the current board position, get chances of winning
• Rollout policy network: Guide rollout action selection
• All networks are deep convolutional networks
• Input: Current board position and additional precomputed features

Source: Mastering the game of Go with deep neural networks and tree search [1]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 50
 Policy Network
• 13 conv-layers, one output for each point on the Go
board.
• Huge database of expert human moves (30 mio)
available.
• Start with supervised learning: Train network to
predict the next move in human expert plays
• Further train network with reinforcement learning by
playing against older versions of itself. Reward
when winning the game
• Older versions avoid correlation and instability
• Training time: 3 weeks on 50 GPUs + 1 day for RL

Source: Mastering the game of Go with deep neural networks and tree search [1]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 51
 Value network
• Same architecture as policy network but just one
output node
• Goal: Estimate how likely the current state leads to
a win
• Training utilized self-play games of reinforcement
learned policy
: Trained using Monte-Carlo policy evaluation for 30
mio positions from these games
• Training time: 1 week on 50 GPUs

Source: Mastering the game of Go with deep neural networks and tree search [1]

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 52
 Rollout policy network

• AlphaGo could use policy network to select moves during roll-out

• Problem: Inference comparatively high: 5 ms
• Solution: Train simpler, linear network on subset of data that provides actions
fast
• Speedup of ≈ 1000 compared to policy network : more simulations possible

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 53
 AlphaGo Zero

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 54
 AlphaGo Zero: Do we even need humans for training?

• After minor improvements, Silver et al. proposed AlphaGo Zero:

: Solely trained with reinforcement learning & playing against itself!
• Simpler MCTS, no rollout policy
• Include MCTS in self-play games
• Multi-task training: Policy and value network share initial layers
• Further extension in Dec. ’17: AlphaZero [3] – able to also play chess and
shogi

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 55
 Next Time

• Algorithms to learn if we don’t even observe rewards

• How to benefit from adversaries
• Extensions to perform image processing tasks

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 57
 Comprehensive Questions

• What is a policy?
• What are value functions?
• Explain the exploitation vs exploration dilemma.
• Describe typical solutions to the dilemma.
• What is the difference of a multi armed bandit problem to the full
reinforcement learning problem?
• Describe a Markov decision process.
• Is an optimal policy necessarily unique?
• What do the Bellman equations represent?
• Describe policy iteration.
• Why does policy iteration work?
• How can you beat your friends in every Atari game?
• How can one master the game of Go?
A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 58
 Further Reading

Reinforcement Learning Richard Sutton

• Link - the one real reference for Reinforcement learning in its 2018 draft,
including Deep Q learning and Alpha Go details

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 59
References
 References I

[1] David Silver, Aja Huang, Chris J Maddison, et al. “Mastering the game of Go
with deep neural networks and tree search”. In: Nature 529.7587 (2016),
pp. 484–489.
[2] David Silver, Julian Schrittwieser, Karen Simonyan, et al. “Mastering the
game of go without human knowledge”. In: Nature 550.7676 (2017), p. 354.
[3] David Silver, Thomas Hubert, Julian Schrittwieser, et al. “Mastering Chess
and Shogi by Self-Play with a General Reinforcement Learning Algorithm”. In:
arXiv preprint arXiv:1712.01815 (2017).
[4] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, et al. “Human-level control
through deep reinforcement learning”. In: Nature 518.7540 (2015),
pp. 529–533.
[5] Martin Müller. “Computer Go”. In: Artificial Intelligence 134.1 (2002),
pp. 145–179.

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 59
 References II

[6] Richard S. Sutton and Andrew G. Barto.

Introduction to Reinforcement Learning. 1st. Cambridge, MA, USA: MIT
Press, 1998.

A. Maier, V. Christlein, K. Breininger, Z. Yang, L. Rist, A. Barnhill | Deep Reinforcement Learning - Part 5 April 24, 2023 59