Comprehensive Lecture Notes:

Markov Decision Processes (MDPs) &

Reinforcement Learning
Compiled from Lecture Notes 2A - 7

Contents
1 Lecture 2A: MDP Structure & Bellman Equations 2
1.1 1. Mathematical Structure of MDPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 2. The Value Function (Vµ ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 3. Contraction Mapping Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Lecture 3A: Optimal Value & Bellman Optimality 3

2.1 1. The Optimal Value Function (V ∗ ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 2. Bellman Optimality Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 3. Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Lecture 4A: Algorithms & Error Bounds 3

3.1 1. Value Iteration (VI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 2. Policy Iteration (PI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.3 3. Modified Policy Iteration (MPI) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

4 Lecture 5: Convergence of MPI 4

4.1 The ”Sandwich” Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

5 Lecture 6A: Linear Programming & SSP 4

5.1 1. Linear Programming (LP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5.2 2. Stochastic Shortest Path (SSP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

6 Lecture 7: Model-Free Reinforcement Learning 5

6.1 1. Monte Carlo (MC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
6.2 2. Temporal Difference (TD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
6.3 3. n-Step TD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1
MDP & RL Lecture Notes 2

1 Lecture 2A: MDP Structure & Bellman Equations

1.1 1. Mathematical Structure of MDPs
An MDP is defined by the tuple ⟨S, A, r, p, γ⟩:
• S: Finite, discrete State space .
• A: Finite, discrete Action space .

• r(s, a, s′ ): Immediate reward function .

• p(s′ |s, a): Transition probability function .
• γ: Discount factor, where 0 ≤ γ < 1 .
Policies:

• Stationary Policy (µ): A decision rule that does not change over time, i.e., at = µ(st ) .
• Trajectory (ω): A sequence of states and actions ω = (s0 , a0 , s1 , a1 , . . . ) .

1.2 2. The Value Function (Vµ )

The value of a state under policy µ is the expected discounted return:
"∞ #
X
Vµ (s) = E γ t r(st , at , st+1 ) | s0 = s (1)
t=0

Recursive Bellman Equation:

X
Vµ (s) = p(s′ |s, a) [r(s, a, s′ ) + γVµ (s′ )] (2)
s′

In matrix form:
Vµ = rµ + γPµ Vµ (3)

1.3 3. Contraction Mapping Proof

The Bellman Operator Tµ (J) = rµ + γPµ J is a Contraction Mapping under the infinity norm (|| · ||∞ ).

Key Concept

Theorem:
˜ − Tµ (J)||
||Tµ (J) ˆ ∞ ≤ γ||J˜ − J||
ˆ ∞ (4)

Implication: Iterating Jk+1 = Tµ (Jk ) will always converge to the unique fixed point Vµ .
MDP & RL Lecture Notes 3

2 Lecture 3A: Optimal Value & Bellman Optimality

2.1 1. The Optimal Value Function (V ∗ )
V ∗ (s) represents the maximum possible value achievable from state s by any policy.

V ∗ (s) = max Vπ (s) (5)

π

2.2 2. Bellman Optimality Equation

To find V ∗ , we use the non-linear ”max” operator:
" #
X
V ∗ (s) = max r(s, a) + γ p(s′ |s, a)V ∗ (s′ ) (6)
a∈A
s′

2.3 3. Properties
• Contraction: The optimality operator T is also a contraction mapping with modulus γ .

• Optimal Policy (π ∗ ): Once V ∗ is known, the greedy policy with respect to V ∗ is optimal.
" #
X
∗ ′ ∗ ′
π (s) = arg max r(s, a) + γ p(s |s, a)V (s ) (7)
a
s′

There always exists an optimal policy that is stationary and deterministic .

3 Lecture 4A: Algorithms & Error Bounds

3.1 1. Value Iteration (VI)
• Algorithm: Vk+1 = T (Vk ) .
• Error Bound: If we stop at step k, the distance to the true optimal value is bounded:

γk
||Vk − V ∗ ||∞ ≤ ||V1 − V0 ||∞ (8)
1−γ
Between steps, the bound is:
γ
||Vk − V ∗ ||∞ ≤ ||Vk − Vk−1 ||∞ (9)
1−γ

3.2 2. Policy Iteration (PI)

• Step 1 (Evaluation): Calculate exact Vπk by solving the linear system (I − γPπk )V = rπk .
• Step 2 (Improvement): Update policy πk+1 by being greedy w.r.t Vπk .

• Result: Converges because Vπk+1 ≥ Vπk monotonically .

3.3 3. Modified Policy Iteration (MPI)

A hybrid approach. Instead of calculating Vπk exactly (infinite steps), we estimate it by running m steps
of the Bellman operator.
• m = 1: Equivalent to Value Iteration.
• m = ∞: Equivalent to Policy Iteration.

• Equation: Vk+1 = Tπmkk (Vk ) .

MDP & RL Lecture Notes 4

4 Lecture 5: Convergence of MPI

4.1 The ”Sandwich” Proof
To prove MPI converges, we show that the value estimate Vk is bounded between two sequences that
both converge to V ∗ : P
T k V0 ≤ Vk ≤ T mi V0 (10)

• Case A (V0 is low): If T V0 ≥ V0 , the values increase monotonically (Vk+1 ≥ Vk ) .

• Case C (Arbitrary V0 ): We can shift any arbitrary value function by a large constant −c to
satisfy the condition of Case A. Since shifting the value function by a constant does not change
the greedy policy, the convergence properties hold .

5 Lecture 6A: Linear Programming & SSP

5.1 1. Linear Programming (LP)
We can find V ∗ by solving a single optimization problem :
• Minimize:
P
s V (s)

• Subject to: V (s) ≥ r(s, a) + γ s′ p(s′ |s, a)V (s′ ) for all s, a.
P

Why? V ∗ is the ”smallest” function that satisfies the Bellman inequalities. The LP ”minimization”
pushes the value surface down until it hits V ∗ .

5.2 2. Stochastic Shortest Path (SSP)

An MDP where γ = 1 (no discount) but there exists a termination state .
• Goal: Reach the termination state with minimum cost.
• Assumption: All policies must be ”proper” (eventually reach the goal). Improper policies incur
infinite cost .
• Convergence: Standard contraction proofs fail because γ = 1. We use a Weighted Norm || · ||ξ
to prove convergence, creating an ”effective” discount factor β < 1 .
MDP & RL Lecture Notes 5

6 Lecture 7: Model-Free Reinforcement Learning

6.1 1. Monte Carlo (MC)
Learns V (s) by averaging returns from complete episodes .
N
1 X
Vπ (s) ≈ Gi (11)
N i=1

• First-Visit MC: Averages return only after the first visit to s in an episode. Unbiased .
• Every-Visit MC: Averages returns after every visit to s. Biased but consistent.
• For Q(s, a): Requires ”Exploring Starts” or stochastic policies to ensure all pairs are visited.

6.2 2. Temporal Difference (TD)

Learns by ”bootstrapping” (guessing based on a guess)
• TD(0) Update: V (s) ← V (s) + α[r + γV (s′ ) − V (s)] .
• Benefit: Can learn during the episode; does not need to wait for the end. Lower variance than
MC .

6.3 3. n-Step TD
A bridge between MC and TD.

• Target: Sum of n actual rewards + estimated value of state n steps later.

• Formula:
n
(n)
X
Qt = γ i−1 Rt+i + γ n Q(St+n , At+n ) (12)
i=1

• Error Decomposition: The n-step error is a weighted sum of individual 1-step TD errors.