Table of contents

3 Dynamic programming
Policy evaluation
Policy improvement
Policy and value iteration
Further aspects

Oliver Wallscheid Reinforcement learning 98

What is dynamic programming (DP)?

Basic DP definition
▶ Dynamic: sequential or temporal problem structure
▶ Programming: mathematical optimization, i.e., numerical solutions

Further characteristics:
▶ DP is a collection of algorithms to solve MDPs and neighboring problems.
▶ We will focus only on finite MDPs.
▶ In case of continuous action/state space: apply quantization.
▶ Use of value functions to organize and structure the search for an optimal policy.
▶ Breaks problems into subproblems and solves them.

Oliver Wallscheid Reinforcement learning 99

Requirements for DP
DP can be applied to problems with the following characteristics.
▶ Optimal substructure:
▶ Principle of optimality applies.
▶ Optimal solution can be derived from subproblems.

▶ Overlapping subproblems:
▶ Subproblems recur many times.
▶ Hence, solutions can be cached and reused.

How is that connected to MDPs?

▶ MDPs satisfy above’s properties:
▶ Bellman equation provides recursive decomposition.
▶ Value function stores and reuses solutions.

Oliver Wallscheid Reinforcement learning 100

Example: DP vs. exhaustive search (1)

Figure 3.1: Shortest path problem to travel from Paderborn to Bielefeld: Eshaustive search requires 14
travel segment evaluations since every possible travel route is evaluated independently.

Oliver Wallscheid Reinforcement learning 101

Example: DP vs. exhaustive search (2)

Figure 3.2: Shortest path problem to travel from Paderborn to Bielefeld: DP requires only 10 travel
segment evaluations in order to calculate the optimal travel policy due to the reuse of subproblem
results.

Oliver Wallscheid Reinforcement learning 102

Utility of DP in the RL context
DP is used for iterative model-based prediction and control in an MDP.
▶ Prediction:
▶ Input: MDP ⟨X , U, P, R, γ⟩ and policy π
▶ Output: (estimated) value function v̂π ≈ vπ
▶ Control:
▶ Input: MDP ⟨X , U, P, R, γ⟩
▶ Output: (estimated) optimal value function v̂π∗ ≈ vπ∗ or policy π̂ ∗ ≈ π ∗

In both applications DP requires full knowledge of the MDP structure.

▶ Feasibility in real-world engineering applications (model vs. system) is therefore limited.
▶ But: following DP concepts are largely used in modern data-driven RL algorithms.

Oliver Wallscheid Reinforcement learning 103

Policy evaluation background (1)
▶ Problem: evaluate a given policy π to predict vπ .
▶ Recap: Bellman expectation equation for xk ∈ X is given as
vπ (xk ) = Eπ [Gk |Xk = xk ]
= Eπ [Rk+1 + γGk+1 |Xk = xk ]
= Eπ [Rk+1 + γvπ (Xk+1 )|Xk = xk ] .
▶ Or in matrix form:
π π
vX = rX π
+ γP πxx′ vX ,
 π  π  π
v1 R1 p11 · · · pπ1n v1π
 
 ..   ..   .. ..   ..  .
 . = . +γ . .  . 
vnπ Rπn pπn1 · · · pπnn vnπ

▶ Solving the Bellman expectation equation for vπ requires handling a linear equation system
with n unknowns (i.e., number of states).
Oliver Wallscheid Reinforcement learning 104
Policy evaluation background (2)
▶ Problem: directly calculating vπ is numerically costly for high-dimensional state spaces (e.g.,
by matrix inversion).
▶ General idea: apply iterative approximations v̂i (xk ) = vi (xk ) of vπ (xk ) with decreasing
errors:
∥vi (xk ) − vπ ∥∞ → 0 for i = 1, 2, 3, . . . (3.1)

▶ The Bellman equation in matrix form can be rewritten as:

(I − γP πxx′ ) vX
π π
= rX . (3.2)
| {z } |{z} |{z}
A ζ b

▶ To iteratively solve this linear equation Aζ = b, one can apply numerous methods such as
▶ General gradient descent,
▶ Richardson iteration,
▶ Kyrlov subspace methods.
Oliver Wallscheid Reinforcement learning 105
Richardson iteration (1)
In the MDP context, the Richardson iteration became the default solution approach to
iteratively solve:
Aζ = b.
The Richardson iteration is
ζi+1 = ζi + ω(b − Aζi ) (3.3)
with ω being a scalar parameter that has to be chosen such that the sequence ζi converges. To
choose ω we inspect the series of approximation errors ei = ζi − ζ and apply it to (3.3):

ei+1 = ei − ωAei = (I − ωA) ei . (3.4)

To evaluate convergence we inspect the following norm:

∥ei+1 ∥∞ = ∥(I − ωA) ei ∥∞ . (3.5)

Oliver Wallscheid Reinforcement learning 106

Richardson iteration (2)
Since any induced matrix norm is sub-multiplicative, we can approximate (3.5) by the
inequality:
∥ei+1 ∥∞ ≤ ∥(I − ωA)∥∞ ∥ei ∥∞ . (3.6)
Hence, the series converges if
∥(I − ωA)∥∞ < 1. (3.7)
Inserting from (3.2) leads to:
∥(I(1 − ω) + ωγP πxx′ )∥∞ < 1. (3.8)
For ω = 1 we receive:
γ ∥(P πxx′ )∥∞ < 1. (3.9)
Since the row elements of P πxx′ always sum up to 1,
γ<1 (3.10)
follows. Hence, when discounting the Richardson iteration always converges for MDPs even if
we assume ω = 1.
Oliver Wallscheid Reinforcement learning 107
Iterative policy evaluation by Richardson iteration (1)
Applying the Richardson iteration (3.3) with w = 1 to the Bellman equation (2.17) for any
xk ∈ X at iteration i results in:
 

(3.11)
X X
vi+1 (xk ) = π(uk |xk ) Rux + γ puxx′ vi (xk+1 ) .
uk ∈U xk+1 ∈X

Matrix form based on (2.19) then is:

π
vX π π π
,i+1 = rX + γP xx′ vX ,i . (3.12)

Figure 3.3: Backup diagram for iterative policy evaluation

Oliver Wallscheid Reinforcement learning 108

Iterative policy evaluation by Richardson iteration (2)

▶ During one Richardson iteration the ’old’ value of xk is replaced with a ’new’ value from the
’old’ values of the successor state xk+1 .
▶ Update vi+1 (xk ) from vi (xk+1 ), see Figure 3.3.
▶ Updating estimates (vi+1 ) on the basis of other estimates (vi ) is often called bootstrapping.
▶ The Richardson iteration can be interpreted as a gradient descent algorithm for solving
(3.2).
▶ This leads to synchronous, full backups of the entire state space X .
▶ Also called expected update because it is based on the expectation over all possible next
states (utilizing full model knowledge).
▶ In subsequent lectures, the expected update will be supplemented by data-driven samples
from the environment.

Oliver Wallscheid Reinforcement learning 109

Iterative policy evaluation example: forest tree MDP
Let’s reuse the forest tree MDP example from Figure 2.10 with fifty-fifty policy :
1−α 1+α
   
0 2 0 2 0.5
0 1−α 1+α 
0  1 
P πxx′ = 2 2 
1+α  ,
π
rX = .
  
1−α
0 0 2 2   2 
0 0 0 1 0

i vi (x = 1) vi (x = 2) vi (x = 3) vi (x = 4)
0 0 0 0 0
1 0.5 1 2 0
2 0.82 1.64 2.64 0
3 1.03 1.85 2.85 0
.. .. .. .. ..
. . . . .
∞ 1.12 1.94 2.94 0
Table 3.1: Policy evaluation by Richardson iteration (3.12) for forest tree MDP with γ = 0.8 and α = 0.2

Oliver Wallscheid Reinforcement learning 110

Variant: in-place updates
Instead of applying (3.12) to the entire vector vX
π
,i+1 in ’one shot’ (synchronous backup), an
elementwise in-place version of the policy evaluation can be carried out:
input: full model of the MDP, i.e., ⟨X , U, P, R, γ⟩ including policy π
parameter: δ > 0 as accuracy termination threshold
init: v0 (x) ∀ x ∈ X arbitrary except v0 (x) = 0 if x is terminal
repeat
∆ ← 0; delta = large value
for ∀ xk ∈ X do
ṽ ← v̂(xk );
 
v̂(xk ) ← u
uk ∈U π(uk |xk ) Rx + γ puxx′ v̂(xk+1 ) ;
P P
xk+1 ∈X
∆ ← max (∆, |ṽ − v̂(xk )|);
min?
until ∆ < δ;
Algo. 3.1: Iterative policy evaluation using in-place updates (output: estimate of vX
π
)

Oliver Wallscheid Reinforcement learning 111

In-place policy evaluation updates for forest tree MDP
▶ In-place algorithms allow to update states in a beneficial order.
▶ May converge faster than regular Richardson iteration if state update order is chosen wisely
(sweep through state space).
▶ For forest tree MDP: reverse order, i.e., start with x = 4.
▶ As can be seen in Table 3.2 the in-place updates especially converge faster for the ’early
states’.
i vi (x = 1) vi (x = 2) vi (x = 3) vi (x = 4)
0 0 0 0 0
1 1.03 1.64 2 0
2 1.09 1.85 2.64 0
3 1.11 1.91 2.85 0
.. .. .. .. ..
. . . . .
∞ 1.12 1.94 2.94 0
Table 3.2: In-place updates for forest tree MDP
Oliver Wallscheid Reinforcement learning 112
Table of contents

3 Dynamic programming
Policy evaluation
Policy improvement
Policy and value iteration
Further aspects

Oliver Wallscheid Reinforcement learning 113

General idea on policy improvement
▶ If we know vπ of a given MDP, how to improve the policy?
▶ The simple idea of policy improvement is:
▶ Consider a new (non-policy conform) action u ̸= π(xk ).
▶ Follow thereafter the current policy π.
▶ Check the action value of this ’new move’. If it is better than the ’old’ value, take it:
qπ (xk , uk ) = E [Rk+1 + γvπ (Xk+1 )|Xk = xk , Uk = uk ] . (3.13)

Theorem 3.1: Policy improvement

If for any deterministic policy pair π and π ′

qπ (x, π ′ (x)) ≥ vπ (x) ∀x ∈ X (3.14)

applies, then the policy π ′ must be as good as or better than π. Hence, it obtains greater or
equal expected return
vπ′ (x) ≥ vπ (x) ∀x ∈ X . (3.15)

Oliver Wallscheid Reinforcement learning 114

Proof of policy improvement theorem
Start with (3.14) and recursively reapply (3.13):
vπ (xk ) ≤ qπ (xk , π ′ (xk ))
= E Rk+1 + γvπ (Xk+1 )|Xk = xk , Uk = π ′ (xk )
 
action value is >= expected state value for
= Eπ′ [Rk+1 + γvπ (Xk+1 )|Xk = xk ] every state (3.14)

≤ Eπ′ Rk+1 + γqπ (xk+1 , π ′ (xk+1 ))|Xk = xk

 

= Eπ′ Rk+1 + γEπ′ Rk+2 + γvπ (Xk+2 )|Xk+1 , π ′ (xk+1 ) |Xk = xk

   
h i
= Eπ′ Rk+1 + γRk+2 + γ 2 vπ (Xk+2 )|Xk = xk (3.16)
h i
≤ Eπ′ Rk+1 + γRk+2 + γ 2 Rk+3 + γ 3 vπ (Xk+3 )|Xk = xk
..
.
h i
≤ Eπ′ Rk+1 + γRk+2 + γ 2 Rk+3 + γ 3 Rk+4 + · · · |Xk = xk
= vπ′ (xk ).

Oliver Wallscheid Reinforcement learning 115

Greedy policy improvement (1)

▶ So far, policy improvement addressed only changing the policy at a single state.
▶ Now, extend this scheme to all states by selecting the best action according to qπ (xk , uk ) in
every state (greedy policy improvement):

π ′ (xk ) = arg max qπ (xk , uk )

uk ∈U
= arg max E [Rk+1 + γvπ (Xk+1 )|Xk = xk , Uk = uk ]
uk ∈U (3.17)
X
= arg max Rux + γ puxx′ vπ (xk+1 ) .
uk ∈U xk+1 ∈X

Oliver Wallscheid Reinforcement learning 116

Greedy policy improvement (2)
▶ Each greedy policy improvement takes the best action in a one-step look-ahead search and,
therefore, satisfies Theo. 3.1.
▶ If after a policy improvement step vπ (xk ) = vπ′ (xk ) applies, it follows:

vπ′ (xk ) = max E [Rk+1 + γvπ′ (Xk+1 )|Xk = xk , Uk = uk ]

uk ∈U
X (3.18)
= max Rux + γ puxx′ vπ′ (xk+1 ) .
uk ∈U
xk+1 ∈X

▶ This is the Bellman optimality equation, which guarantees that π ′ = π must be optimal
policies.
▶ Although proof for policy improvement theorem was presented for deterministic policies,
transfer to stochastic policies π(uk |xk ) is possible.
▶ Takeaway message: policy improvement theorem guarantees finding optimal policies in finite
MDPs (e.g., by DP).
Oliver Wallscheid Reinforcement learning 117
Table of contents

3 Dynamic programming
Policy evaluation
Policy improvement
Policy and value iteration
Further aspects

Oliver Wallscheid Reinforcement learning 118

Concept of policy iteration

▶ Policy iteration combines the previous policy evaluation and policy improvement in an
iterative sequence:

π0 → vπ0 → π1 → vπ1 → · · · π ∗ → vπ∗ (3.19)

▶ Evaluate → improve → evaluate → improve ...

▶ In the ’classic’ policy iteration, each policy evaluation step in (3.19) is fully executed, i.e.,
for each policy πi an exact estimate of vπi is provided either by iterative policy evaluation
with a sufficiently high number of steps or by any other method that fully solves (3.2).

Oliver Wallscheid Reinforcement learning 119

Policy iteration example: forest tree MDP (1)
Small Medium Large

Gone

▶ Two actions possible in each state:

▶ Wait u = w: let the tree grow.
▶ Cut u = c: gather the wood.

Oliver Wallscheid Reinforcement learning 120

Policy iteration example: forest tree MDP (2)
Assume α = 0.2 and γ = 0.8 and start with ’tree hater’ initial policy:
1 π0 = π(uk = c|xk ) ∀xk ∈ X .
h iT
π0
2 Policy evaluation: vX
= 1 2 3 0
3 Greedy policy improvement:
π1 (xk ) = arg max E [Rk+1 + γvπ0 (Xk+1 )|Xk = xk , Uk = uk ]
uk ∈U
= {π(uk = w|xk = 1), π(uk = c|xk = 2), π(uk = c|xk = 3)}
h iT
π1
4 Policy evaluation: vX = 1.28 2 3 0
5 Greedy policy improvement:
π2 (xk ) = arg max E [Rk+1 + γvπ1 (Xk+1 )|Xk = xk , Uk = uk ]
uk ∈U
= {π(uk = w|xk = 1), π(uk = c|xk = 2), π(uk = c|xk = 3)} ,
= π1 (xk )
= π∗
Oliver Wallscheid Reinforcement learning 121
Policy iteration example: forest tree MDP (3)
Assume α = 0.2 and γ = 0.8 and start with ’tree lover’ initial policy:
1 π0 = π(uk = w|xk ) ∀xk ∈ X .
h iT
π0
2 Policy evaluation: vX
= 1.14 1.78 2.78 0
3 Greedy policy improvement:
π1 (xk ) = arg max E [Rk+1 + γvπ0 (Xk+1 )|Xk = xk , Uk = uk ]
uk ∈U
= {π(uk = w|xk = 1), π(uk = c|xk = 2), π(uk = c|xk = 3)}
h iT
π1
4 Policy evaluation: vX = 1.28 2 3 0
5 Greedy policy improvement:
π2 (xk ) = arg max E [Rk+1 + γvπ1 (Xk+1 )|Xk = xk , Uk = uk ]
uk ∈U
= {π(uk = w|xk = 1), π(uk = c|xk = 2), π(uk = c|xk = 3)}
= π1 (xk )
= π∗
Oliver Wallscheid Reinforcement learning 122
Value iteration (1)

▶ Policy iteration involves full policy evaluation steps between policy improvements.
▶ In large state-space MDPs the full policy evaluation may be numerically very costly.

▶ Value iteration: One step iterative policy evaluation followed by policy improvement.
▶ Allows simple update rule which combines policy improvement with truncated policy
evaluation in a single step:

vi+1 (xk ) = max E [Rk+1 + γvi (Xk+1 )|Xk = xk , Uk = uk ]

uk ∈U
X (3.20)
= max Rux + γ puxx′ vi (xk+1 ) .
uk ∈U
xk+1 ∈X

Oliver Wallscheid Reinforcement learning 123

Value iteration (2)
input: full model of the MDP, i.e., ⟨X , U, P, R, γ⟩
parameter: δ > 0 as accuracy termination threshold
init: v0 (x) ∀ x ∈ X arbitrary except v0 (x) = 0 if x is terminal
repeat
∆ ← 0;
for ∀ xk ∈ X do
ṽ ← v̂(xk );
 
v̂(xk ) ← maxuk ∈U Rux + γ puxx′ v̂(xk+1 ) ;
P
xk+1 ∈X
∆ ← max (∆, |ṽ − v̂(xk )|);
until ∆ < δ;
output: deterministic policy
 π ≈ π ∗ , such that 
π(xk ) ← arg maxuk ∈U Rux + γ xk+1 ∈X puxx′ v̂(xk+1 ) ;
P

Algo. 3.2: Value iteration (note: compared to policy iteration, value iteration does not require an
initial policy but only a state-value guess)

Oliver Wallscheid Reinforcement learning 124

Value iteration example: forest tree MDP

▶ Assume again α = 0.2 and γ = 0.8.

▶ Similar to in-place update policy evaluation, reverse order and start value iteration with
x = 4.
▶ As shown in Table 3.3 value iteration converges in one step (for the given problem) to the
optimal state value.

i vi (x = 1) vi (x = 2) vi (x = 3) vi (x = 4)
0 0 0 0 0
1 1.28 2 3 0
* 1.28 2 3 0
Table 3.3: Value iteration for forest tree MDP

Oliver Wallscheid Reinforcement learning 125

Table of contents

3 Dynamic programming
Policy evaluation
Policy improvement
Policy and value iteration
Further aspects

Oliver Wallscheid Reinforcement learning 126

Summarizing DP algorithms
▶ All DP algorithms are based on the state value v(x).
▶ Complexity is O(m · n2 ) for m actions and n states.
▶ Evaluate all n2 state transitions while considering up to m actions per state.
▶ Could be also applied to action values q(x, u).
▶ Complexity is inferior with O(m2 · n2 ).
▶ There are up to m2 action values which require n2 state transition evaluations each.

Problem Relevant Equations Algorithm

prediction Bellman expectation eq. policy evaluation
Bellman expectation eq. &
control policy iteration
greedy policy improvement
control Bellman optimality eq. value iteration

Table 3.4: Short overview addressing the treated DP algorithms

Oliver Wallscheid Reinforcement learning 127

Curse of dimensionality

▶ DP is much more efficient than an exhaustive search over all n states and m actions in
finite MDPs in order to find an optimal policy.
▶ Exhaustive search for deterministic policies: mn evaluations.
▶ DP results in polynomial complexity regarding m and n.
▶ Nevertheless, DP uses full-width backups:
▶ For each state update, every successor state and action is considered.
▶ While utilizing full knowledge of the MDP structure.
▶ Hence, DP is can be effective up to medium-sized MDPs (i.e., million finite states)
▶ For large problems DP suffers from the curse of dimensionality:
▶ Single update step may become computational infeasible.
▶ Also: if continuous states need quantization, number of finite states n grows exponentially with
the number of state variables (assuming fixed number of discretization levels).

Oliver Wallscheid Reinforcement learning 128

 urrent value function (policy improvement). In
ernate, each completing before the other begins,
Generalized policy iteration (GPI)
iteration, for example, only a single iteration of
n each policy improvement. In asynchronous DP
▶ Almost
t processes all RLatmethods
are interleaved an even finer are well-described as GPI.
grain.
cy of process
n one Dynamic before Programming
returning to the other. As 87
▶ Push-pull:
te all states, Improving
the ultimate the policy
result is typically the will deteriorate value estimation.
▶ Well
function and an balanced trade-off between evaluating and improving is required.
optimal policy.
iteration (GPI) to re-
-evaluation and policy-
tndentalso think of the interaction
of the granularity
evaluation between
V v⇡
on
Almost and improvement processes in GPI
all reinforcement
v=
GPI. That is, all have ⇡
wo constraints
with the policy always
or goals—forVexample, v⇡
ein two-dimensional
function and the value space
⇡
as suggested
greedy(V )

e value function for the

ram to the right. Although
the right. If both the
improvement the real v, ⇡
v⇤ , ⇡⇤
much
t processmore stabilize,complicated
that than this, the
alue function and policy
gests what happens in the real case. y( v )
stabilizes only when it
= greed
s drives
nd the policythe value
stabilizes ⇡⇤ function vor ⇤ policy
⇡
e current value function.
of
en athe policy lines representing
has been found that is greedya solution
with to
o goals.
his impliesFigureThe
that 3.4:
the Interpreting
goals
Bellman optimality generalized
interact because the
equation policy
twoiteration
lines are to switch back and forth
not orthogonal. between (arbitrary)
Driving
d the value evaluations
function areand improvement steps (source: R. Sutton and G. Barto, Reinforcement learning: an
optimal.
ard one goal causes some movement away from the other goal. Inevitably,
cesses in GPI can be viewed as both competing introduction, 2018, CC BY-NC-ND 2.0)
nsejoint process
that they is brought
pull in opposing [Link]
Makingto the overall goal of optimality. The arrows
lue function typically makes the value function
am
king thecorrespond
Oliver Wallscheid
value to thewith
function consistent behavior
the policy of policy iteration
Reinforcement learning in that each takes the 129
Summary: what you’ve learned in this lecture

▶ DP is applicable for prediction and control problems in MDPs.

▶ But requires always full knowledge about the environment (i.e., it is a model-based solution).
▶ DP is more efficient than exhaustive search.
▶ But suffers from the curse of dimensionality for large MDPs.
▶ (Iterative) policy evaluations and (greedy) improvements solve MDPs.
▶ Both steps can be combined via value iteration.
▶ This idea of (generalized) policy iteration is a basic scheme of RL.
▶ Implementing DP algorithms comes with many degrees of freedom regarding the update
order.

Oliver Wallscheid Reinforcement learning 130