ST455: Reinforcement Learning

Lecture 3: Elementary Solution Methods

Dynamic Programming and Monte Carlo

Chengchun Shi

1 / 65
Lecture Outline

1. Preliminaries

2. Dynamic Programming
2.1 Policy Iteration
2.2 Value Iteration

3. Monte Carlo Methods

3.1 MC Policy Evaluation (Prediction)
3.2 MC Policy Optimization (Control)

2 / 65
Lecture Outline (Cont’d)

Dynamic Programming (DP) Monte Carlo (MC)

3 / 65
1. Preliminaries

2. Dynamic Programming
2.1 Policy Iteration
2.2 Value Iteration

3. Monte Carlo Methods

3.1 MC Policy Evaluation (Prediction)
3.2 MC Policy Optimization (Control)

4 / 65
Learning v.s. Planning

Two fundamental problems in sequential decision making

• Planning
• A model of the environment (e.g., state transition, reward function) is known
• The agent performs computations with its model, without any external interaction
• a.k.a. deliberation, reasoning, introspection, pondering, thought, search
• Example: Dynamic Programming
• Learning
• The environment is initially unknown
• The agent interacts with the model
• The agent learns the optimal policy from experience
• Example: Monte Carlo methods, temporal difference learning, policy-based
learning, model-based learning

5 / 65
Example: Go Game
• Planning: Rules of Go are known • Learning: No need to know the rules
• Exhaustive search of the optimal move • Learn the optimal move from experience
• No need to play Go with others • Practice makes perfect

6 / 65
Models: Finite MDPs

• Environment modelled by a finite MDP ⟨S, A, P, R, γ⟩

• MDP model assumption: Markovianity & time-homogeneity
• S: state space (a finite set of states)
• A: action space (a finite set of actions)
• P: state transition probability matrix, P ass ′ = Pr(St+1 = s ′ |At = a, St = s)
• R: reward function, Ras = E(Rt |At = a, St = s)
• γ: discounted factor ∈ [0, 1], allowed to be 1 if all sequences terminate (e.g., finite
horizons)
• Dynamic Programming (DP) and Monte Carlo methods (MC) are equally
applicable to settings with continuous state or action space

7 / 65
Bellman Equations
• Bellman equation for the (state) value function:

V π (s) = Eπ [Rt + γV π (St+1 )|St = s],

• or equivalently,
X h X i
V π (s) = π(a|s) Ras + γ P ass ′ V π (s ′ ) .
a∈A s′

• Bellman optimality equation for the optimal value function:

opt opt
V π (s) = max E[Rt + γV π (St+1 )|At = a, St = s],
a

• or equivalently,
opt
h X opt
i
V π (s) = max Ras + γ P ass ′ V π (s ′ ) .
a∈A
s′

8 / 65
Bellman Equation: The Random Walk Example
• Consider a simple random walk on a path:

• Reward for transition to State S of value 1, zero reward for other transitions
• Bellman equations:

V π (A) = Eπ [Rt + γV π (St+1 )|St = A] = γV π (B)

γ γ
V π (B) = Eπ [Rt + γV π (St+1 )|St = B] = V π (C ) + V π (A)
2 2
..
.
1 γ
V π (E ) = Eπ [Rt + γV π (St+1 )|St = E ] = + V π (D)
2 2
9 / 65
Bellman Optimality Equation: Random Walk
• The random walk example:

• Reward for transition to State S of value 1, zero reward for other transitions
• Bellman optimality equations:
opt opt opt
V π (A) = max E[Rt + γV π (St+1 )|At = a, St = A] = γV π (B)
a
opt opt opt
V π (B) = max E[Rt + γV π (St+1 )|At = a, St = B] = γV π (C )
a
..
.
opt opt
V π (E ) = max E[Rt + γV π (St+1 )|At = a, St = E ] = 1
a

10 / 65
State-Action Value Function

Definition
The state-action value function (better known as the Q-function) is expected return
starting from s and a under π,
+∞
!
X
π π π i
Q (s, a) = E (Gt |At = a, St = s) = E γ Ri +t |At = a, St = s .
i =0

• Q π is independent of the time t in its definition, under time-homogeneity

• Q π is the state value V π under a Markov policy that implements a at the first time
and follows π afterwards
• Reduces to action value function Eπ (Rt |At = a) in Lecture 1 when γ = 0, S = ∅

11 / 65
State-Action Value Function (Cont’d)

Relationships between V π and Q π

• Qπ → V π:
X X
V π (s) = Eπ (Gt |St = s) = π(a|s)Eπ (Gt |At = a, St = s) = π(a|s)Q π (s, a)
a∈A a∈A

• V π → Qπ:

Q π (s, a) = E(Rt |At = a, St = s) + γE(Gt+1 |At = a, St = s)

= E(Rt |At = a, St = s) + γE[Eπ (Gt+1 |St+1 )|At = a, St = s]
= E[Rt + γV π (St+1 )|At = a, St = s]

12 / 65
1. Preliminaries

2. Dynamic Programming
2.1 Policy Iteration
2.2 Value Iteration

3. Monte Carlo Methods

3.1 MC Policy Evaluation (Prediction)
3.2 MC Policy Optimization (Control)

13 / 65
Dynamic Programming

Definition (Dynamic Programming)

A collection of algorithms used to compute optimal policies given perfect knowledge of
the environment
• Dynamic: sequential or temporal component to the problem
• Programming: optimise a “program”, i.e., a policy
• Dynamic programming (DP) is rarely used in practice (the environment is usually
unknown)
• However, they provide a foundation for other solution methods

14 / 65
Dynamic Programming (Cont’d)

“Dynamic programming” is used to solve many other statistical learning problems

• Learning optimal dynamic treatment regimes (DTRs)
• Multi-scale change point detection
• De Boor algorithm for evaluating B-spline basis functions

Also used in bioinformatics, optimisation, control theory (see wiki page)

15 / 65
Dynamic Programming Methods

• Policy Iteration: an iterative method that alternates between

• Policy Evaluation
• Policy Improvement

• Value Iteration: simultaneously combine policy evaluation and policy

improvement

16 / 65
1. Preliminaries

2. Dynamic Programming
2.1 Policy Iteration
2.2 Value Iteration

3. Monte Carlo Methods

3.1 MC Policy Evaluation (Prediction)
3.2 MC Policy Optimization (Control)

17 / 65
Policy Iteration: Policy Evaluation
• Computation of the (state) value function V π for a given π
• According to the Bellman equation, for any s,
X h X i
V π (s) = π(a|s) Ras + γ P ass ′ V π (s ′ ) ,
a∈A s′

• written in matrix form, V π = R + γPV π

• V π is a column vector with one entry per state

π(a|1)Ra1
 π      π 
V (1) P 11 · · · P 1n V (1)
..  X ..  . ..   ..
=  + γ  .. ,
  
 .  . .  .
π
V (n) a∈A π(a|n)Rna P n1 · · · P nn π
V (n)

where P ij = a∈A π(a|i )P aij

P

18 / 65
Policy Evaluation (Cont’d)
• V π is a solution of a system of n linear equations with n unknowns
• It can be computed directly

V π = R + γPV π
(I − γP)V π = R
Vπ = (I − γP)−1 R

• I − γP is invertible when γ is strictly smaller than 1, since

X
x ⊤ (I − γP)x = (1 − γ)∥x∥22 + γ P ij (xi − xj )2 > 0,
i ,j

when x ̸= 0. The equality holds due to that each row of P sums up to 1.

19 / 65
Policy Evaluation: Algorithm

• Iterative Policy Evaluation: an iterative method that outputs a sequence of value

functions V0 , V1 , V2 , · · ·, Vk → V π
• Initial value function V0 is chosen arbitrarily subject to the constraint that at
terminal state it has value 0
• Iterative update rule (according to the Bellman equation):

Vk+1 = R + γPVk

• Convergence is guaranteed when γ is strictly smaller than 1 (more in appendix), or

eventual termination is guaranteed from all states under π

20 / 65
Policy Evaluation: Pseudocode

• Input: a policy π, a threshold parameter ϵ > 0

• Initialization: V (s) = 0 for any s ∈ S
• Repeat:
∆←0
For each s ∈ S
ν ← V (s) h i
V (s) ← a∈A π(a|s) Ras + γ s ′ P ass ′ V (s ′ )
P P

∆ ← max(∆, |ν − V (s)|)
until ∆ < ϵ
• Output V

21 / 65
GridWorld Example

• Undiscounted, episodic, finite MDP task

• A = {up, down, right, left}. Actions leading out of the grid leave state unchanged
• Rewards: for each transition, the reward of value −1
22 / 65
GridWorld Example (Cont’d)

Figure: Values of uniform random policy

π(n|·) = π(s|·) = π(w |·) = π(e|·) = 0.25

23 / 65
GridWorld Example (Cont’d)
By symmetry and Bellman equation,

24 / 65
GridWorld Example (Cont’d)

Figure: Value functions at each iteration

25 / 65
Policy Iteration: Policy Improvement

• Identify some π ′ that is no worse than π based on V π

• For any s, consider a hybrid policy
• implements a at the first time
• follows π afterwards
• Its value is given by Q π (s, a) (can be computed based on V π )
• Select π ′ among the class of hybrid policies that maximizes the value

π ′ (s) = arg max Q π (s, a)

a

• Its value is given by Q π (s, π ′ (s)) ≥ V π (s), since the hybrid policy class contains π
′
• Surprisingly, according to policy improvement theorem, V π (s) ≥ V π (s) for any
s!

26 / 65
Policy Improvement (Cont’d)
Given a policy π, improve π by acting greedily with respect to V π ,

π ′ (s) = arg max Q π (s, a) = arg max E[Rt + γV π (St+1 )|At = a, St = s]

a a
X
π ′
= arg max[Ras + γ a
Pss ′ V (s )]
a
s′

Theorem
The greedy policy π ′ with respect to V π is as good as or better than π,
′
V π (s) ≥ V π (s),

for any s ∈ S.
Proof can be found in the Appendix.
27 / 65
GridWorld Example

28 / 65
Policy Iteration: Revisit

• Policy Evaluation: Compute V π via iterative policy evaluation

• Policy Improvement: Generate π ′ via greedy policy improvement

29 / 65
Policy Iteration: Pseudocode
• Initialization: V (s) = 0, π(s) ∈ A arbitrarily for any s ∈ S
• Repeat:
∆←0
For each s ∈ S
ν ← V (s) h i
V (s) ← a∈A π(a|s) Ras + γ s ′ P ass ′ V (s ′ )
P P

∆ ← max(∆, |ν − V (s)|)
until ∆ < ϵ
• policystable ← True
• For each s ∈ S:
b ← π(s)
a V (s ′ )]
π(s) ← arg maxa [Ras + γ s ′ Pss
P
′

If b ̸= π(s) then policystable ← False

• If policystable, then Return π, else go to bullet point #2
30 / 65
1. Preliminaries

2. Dynamic Programming
2.1 Policy Iteration
2.2 Value Iteration

3. Monte Carlo Methods

3.1 MC Policy Evaluation (Prediction)
3.2 MC Policy Optimization (Control)

31 / 65
Value Iteration
• Policy iteration is computationally inefficient, as each iteration requires executing
policy evaluation which requires multiple iterations
• According to the Bellman optimality equation,
opt
h X opt
i
V π (s) = max Ras + γ P ass ′ V π (s ′ ) .
a∈A
s′
• Value iteration idea: iteratively apply the above updates
h X i
Vk+1 (s) = max Ras + γ P ass ′ Vk (s ′ ) .
a∈A
s′
• Drive the optimal deterministic policy
h X opt
i
π opt (s) = arg max Ras + γ P ass ′ V π (s ′ ) .
a∈A
s′
• Convergence is guaranteed when γ is strictly smaller than 1 (more in Appendix), or
eventual termination is guaranteed from all states.
32 / 65
Value Iteration: Pseudocode
• Initialization: V (s) = 0, π(s) ∈ A arbitrarily for any s ∈ S
• Repeat:
∆←0
For each s ∈ S
ν ← V (s) h i
V (s) ← maxa∈A Ras + γ s ′ P ass ′ V (s ′ )
P

∆ ← max(∆, |ν − V (s)|)
until ∆ < ϵ
• Output: optimal deterministic policy given by
h X opt
i
π opt (s) = arg max Ras + γ P ass ′ V π (s ′ ) .
a∈A
s′

33 / 65
Example: Gambler’s Problem

• A gambler makes bets on the outcomes of a sequence of coin flips

• The gambler must decide for each coin flip what proportion of capital to stake
• If the outcome of the coin flip = heads, then:
The gambler wins as much money as they have staked on this flip
• Else:
The gambler loses their stake
• The game ends when the gambler reaches the goal of £100 or runs out of money

34 / 65
Example: Gambler’s Problem (Cont’d)

• Undiscounted, episodic, finite MDP task

• S: {0, 1, · · ·, 99, 100}, termination states 0 and 100
• A(s): {1, 2, · · ·, min(s, 100 − s)}, depends on the state
• Pr(outcome of coin flip is heads) = p (known parameter)
• Seminars:
• Show the value function for different iterations
• Show the optimal policy

35 / 65
Example: Gambler’s Problem, the Optimal Policy

36 / 65
Some Technical Questions

opt
• How do we know that value iteration converges to V π ?
• Or that iterative policy evaluation converges to V π ?
opt
• And therefore that policy iteration converges to V π ?
• Is the solution unique?
• These questions are resolved by Banach fixed-point theorem (or contraction
mapping theorem), mentioned in Seminar 2 (more in the appendix)

37 / 65
1. Preliminaries

2. Dynamic Programming
2.1 Policy Iteration
2.2 Value Iteration

3. Monte Carlo Methods

3.1 MC Policy Evaluation (Prediction)
3.2 MC Policy Optimization (Control)

38 / 65
Monte Carlo (MC) Methods

• Learning methods for solving the RL problem based on averaging sample returns
• Estimating value functions and discovering optimal policies
• Not assuming a model of the environment, based only on experiences (model free)
• Defined for episodic tasks
• Value functions and policies are updated upon completion of an episode
• Different from step-by-step methods (e.g., temporal difference learning)

39 / 65
1. Preliminaries

2. Dynamic Programming
2.1 Policy Iteration
2.2 Value Iteration

3. Monte Carlo Methods

3.1 MC Policy Evaluation (Prediction)
3.2 MC Policy Optimization (Control)

40 / 65
MC Policy Evaluation
• Objective: estimate the value function V π for a given policy π, from a set of
episodes obtained by following π

S0 , A0 , R0 , · · ·, ST ∼ π

• Vπ is the expected return Eπ ( 0≤t≤T γ t Rt |S0 = s)

P

• Monte Carlo idea: use empirical mean return to approximate expected return
• Convergence is guaranteed by law of large numbers
• Types of MC methods:
• First-visit MC method: V π (s) estimated by the average of returns following each
first visit to s in a set of episodes
• Every-visit MC method: V π (s) estimated by the average of returns following each
visit to s in a set of episodes

41 / 65
First-Visit MC Policy Evaluation: Pseudocode
• Initialization:
N (counter), N(s) ← 0 for all s ∈ S
Returns(s) ← an empty list, for all s ∈ S
• Repeat:
Generate an episode following policy π
For each distinct s appearing in the episode
G ← return following the first occurrence of s
N(s) ← N(s) + 1
Returns(s) ← Returns(s) + G
• Output:
For each distinct s
N −1 (s)Returns(s)

42 / 65
Every-Visit MC Policy Evaluation: Pseudocode
• Initialization:
N ← counter, N(s) ← 0 for all s ∈ S
Returns(s) ← an empty list, for all s ∈ S
• Repeat:
Generate an episode following policy π
For each s appearing in the episode
G ← return following the occurrence of s
N(s) ← N(s) + 1
Returns(s) ← Returns(s) + G
• Output:
For each distinct s
N −1 (s)Returns(s)

43 / 65
1. Preliminaries

2. Dynamic Programming
2.1 Policy Iteration
2.2 Value Iteration

3. Monte Carlo Methods

3.1 MC Policy Evaluation (Prediction)
3.2 MC Policy Optimization (Control)

44 / 65
MC Control
• Objective: use MC estimation to learn the optimal policy.
• Recall the policy iteration algorithm

• Policy Evaluation: Compute V π via iterative policy evaluation

• Policy Improvement: Generate π ′ via greedy policy improvement
45 / 65
MC Control with Generalized Policy Iteration
• Objective: use MC estimation to learn the optimal policy.
• Integrate policy iteration with MC methods

• Policy Evaluation: Compute V π via MC policy evaluation

• Policy Improvement: Generate π ′ via greedy policy improvement?
46 / 65
Policy Iteration Using State-Action Value Function

• Greedy policy improvement over V π requires model of MDP

X
π ′ (s) = arg max[Ras + γ a
Pss π ′
′ V (s )]
a
s′

• Greedy policy improvement over Q π (s, a) is model free

π ′ (s) = arg max Q π (s, a)

a

47 / 65
MC Version of Policy Iteration

• Policy Evaluation: MC estimation of state-action value function

• Policy Improvement: Improve the policy wrt the current state-action value function

48 / 65
MC Estimation of State-Action Values

• Many state-action pairs may never be visited under a policy

• Ex. if π is deterministic, only one state-action pair is observed for each distinct state
• Need to ensure exploration!
• Two approaches for ensuring exploration:
• Exploring starts: the first step of each episode starts at a state-action pair and every
such pair has non-zero probability of being selected at the start
• Stochastic policies: use policies that ensures a non-zero probability of selecting each
action from the set of available actions in each given state

49 / 65
MC Control with Exploring Starts
• Initialization:
N (counter), N(s, a) ← 0 for all s ∈ S, a ∈ A
Returns(s, a) ← an empty list, for all s ∈ S, a ∈ A
π ← arbitrary
Q ← arbitrary
• Repeat:
Generate an episode using exploring starts and policy π
For each distinct (s, a) appearing in the episode
G ← return following the first occurrence of (s, a)
N(s, a) ← N(s, a) + 1
Returns(s, a) ← Returns(s, a) + G
Q(s, a) ← Returns(s, a)/N(s, a)
π(s) ← arg maxa Q(s, a) for all s

50 / 65
MC Control with ε-Greedy Exploration

• Simplest idea for ensuring continual exploration

• All m actions are tried with non-zero probabilities
• With probability 1 − ε choose the greedy action
• With probability ε choose an action at random

ε/m + 1 − ε, if a = arg maxa′ Q(s, a ′ )


π(a|s) =
ε/m, otherwise

51 / 65
MC Control with ε-Greedy Exploration (Cont’d)

52 / 65
Pseudocode
• Initialization:
N (counter), N(s, a) ← 0 for all s ∈ S, a ∈ A
Returns(s, a) ← empty lists, for all s ∈ S, a ∈ A
π ← arbitrary ε-greedy policy
Q ← arbitrary
• Repeat:
Generate an episode using exploring starts and policy π
For each distinct (s, a) appearing in the episode
G ← return following the first occurrence of (s, a)
N(s, a) ← N(s, a) + 1
Returns(s, a) ← Returns(s, a) + G
Q(s, a) ← Returns(s, a)/N(s, a)
For each distinct s:

ε/m + 1 − ε, if a = arg max Q(s, a)
π(a|s) ←
ε/m, otherwise
53 / 65
Summary

• Planning v.s. Learning

• Dynamic programming v.s. Monte Carlo Methods
• Policy Iteration v.s. Value Iteration
• Policy Evaluation v.s. Policy Improvement
• MC Policy Evaluation v.s. MC Control
• γ-Contraction, Banach Fixed Point Theorem

54 / 65
Summary (Cont’d)

Dynamic Programming (DP) Monte Carlo (MC)

55 / 65
Seminar
• Solution to HW2 (due Wed 12pm)
• Iterative policy evaluation: Gridworld problem

• Value iteration: Gambler’s problem

• Monte Carlo prediction & control: Black jack example

56 / 65
Questions

57 / 65
Appendix: Proof of Policy Improvement Theorem

Consider a sequence of policies:

• π0 : a given stationary policy π
• πk : a Markov policy that implements π ′ at the first k times and follows π afterwards
• π∞ : the greedy policy π ′

We show in the appendix

• Step 1: π1 is no worse than π0 , i.e., Q π (s, π ′ (s)) ≥ V π (s)
• Step 2: πk+1 is no worse than πk for any k ≥ 1
This proves the policy improvement theorem

58 / 65
Appendix: Policy Improvement Theorem, Step 1

• π0 : a given stationary policy π

• π1 : a Markov policy that implements π ′ at the initial time and follows π afterwards
• By definition,

π ′ (s) = arg max Q π (s, a)

a

• This yields
X
Q π (s, π ′ (s)) = max Q π (s, a) ≥ π(a|s)Q π (s, a) = V π (s)
a
a

• i.e., π1 is no worse than π0

59 / 65
Appendix: Policy Improvement Theorem, Step 2

• πk : a Markov policy that implements π ′ at the first k times and follows π afterwards
• The difference between two value functions is given by
′ ′
V πk+1 (s) − V πk (s) = γ k Eπ [Q π (Sk , π ′ (Sk ))|S0 = s] − γ k Eπ [V π (Sk )|S0 = s]

• Results in Step 1 yield Q π (Sk , π ′ (Sk )) ≥ V π (Sk ), and hence V πk+1 (s) ≥ V πk (s)
• i.e., πk+1 is no worse than πk

60 / 65
Appendix: Value Function ∞-Norm

• Measure distance between two value functions V1 and V2 by the ∞-norm

• i.e., the largest difference between state values,

∥V1 − V2 ∥∞ = max |V1 (s) − V2 (s)|

s∈S

• Given a sequence of values {Vk }k , convergences requires ∥Vk − V ∗ ∥∞ → 0 for

some V ∗ as k → ∞

61 / 65
Appendix: Bellman Expectation Operator
Definition
Define the Bellman Expectation Operator T π as a function that maps a given value
function V into another value function T π V such that
X h X i
T π V (s) = π(a|s) Ras + γ P ass ′ V (s ′ ) , ∀s ∈ S.
a∈A s′

• The Bellman equation can be rewritten as V π = T π V π

• This operator is a γ-contraction, i.e. it makes value function closer by at least γ
X
max |T π V1 (s) − T π V2 (s)| = γ max π(a|s)P ass ′ [V1 (s ′ ) − V2 (s ′ )]
s s
a,s ′
X
≤ γ max |V1 (s) − V2 (s)| max π(a|s)P ass ′ = γ max |V1 (s) − V2 (s)|
s s s
a,s ′
• Iterative Policy Evaluation: V0 → T π V0 → T π T π V0 → · · ·
62 / 65
Appendix: Banach Fix Point Theorem

Theorem
Suppose T is a γ-contraction. Then under certain conditions,
• T admits a unique fix point V ∗ , i.e. TV ∗ = V ∗ ;
• V ∗ can be found as follows: define a sequence {Vk }k such that Vk+1 = TVk .
Then V ∗ = limk Vk

• Proof can be found here

• T π is has a unique fix point
• V π is the fix point, according to the Bellman equation
• Iterative policy evaluation converges to V π

63 / 65
Appendix: Bellman Optimality Operator
Definition
Define the Bellman Expectation Operator T as a function that maps a given value
function V into another value function TV such that
h X i
TV (s) = max Ras + γ P ass ′ V (s ′ ) , ∀s ∈ S.
a∈A
s′

opt opt
• The Bellman optimality equation can be rewritten as V π = TV π
• This operator is a γ-contraction as well
X
max |TV1 (s) − TV2 (s)| = γ max P ass ′ [V1 (s ′ ) − V2 (s ′ )]
s s,a
s′
≤ γ max
′
|V1 (s ′ ) − V2 (s ′ )|
s

64 / 65
Appendix: Convergence of Dynamic Programming

• T has a unique fix point

opt
• V π is the fix point, according to the Bellman optimality equation
opt
• According to the Banach fix point theorem, value iteration converges to V π
• Policy iteration (that integrates iterative policy evaluation & policy improvement)
converges to π opt

65 / 65