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[cite: 3]. [cites tart]

• A: Finite, discrete Action space[cite: 4]. [cites tart]

• r(s, a, s′ ): Immediate reward function[cite: 5]. [cites tart]

• p(s′ |s, a): Transition probability function[cite: 11]. [cites tart]

• γ: Discount factor, where 0 ≤ γ < 1[cite: 12].

Policies:
• Stationary Policy (µ): A decision rule that does not change over time, i.e., at = µ(st )[cite: 21].
[cites tart]

• Trajectory (ω): A sequence of states and actions ω = (s0 , a0 , s1 , a1 , . . . )[cite: 25].

1.2 2. The Value Function (Vµ )

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

Recursive Bellman Equation:

X
[cites tart]Vµ (s) = p(s′ |s, a) [r(s, a, s′ ) + γVµ (s′ )] [cite: 76] (2)
s′

In matrix form:
[cites tart]Vµ = rµ + γPµ Vµ [cite: 84] (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)||
[cites tart]||Tµ (J) ˆ ∞ ≤ γ||J˜ − J||
ˆ ∞ [cite: 118] (4)

[cites tart]Implication:IteratingJk+1 = Tµ (Jk ) will always converge to the unique fixed point Vµ [cite:
96, 112].
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.

[cites tart]V ∗ (s) = max Vπ (s) [cite: 123] (5)

π

2.2 2. Bellman Optimality Equation

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

2.3 3. Properties
• Contraction: The optimality operator T is also a contraction mapping with modulus γ[cite: 172].
• Optimal Policy (π ∗ ): Once V ∗ is known, the greedy policy with respect to V ∗ is optimal.
" #
X
[cites tart]π ∗ (s) = arg max r(s, a) + γ p(s′ |s, a)V ∗ (s′ ) [cite: 192] (7)
a
s′

[cites tart]T herealwaysexistsanoptimalpolicythatisstationaryanddeterministic[cite : 189].

3 Lecture 4A: Algorithms & Error Bounds

3.1 1. Value Iteration (VI)
• Algorithm: Vk+1 = T (Vk )[cite: 237].
• Error Bound: If we stop at step k, the distance to the true optimal value is bounded:
γk
[cites tart]||Vk − V ∗ ||∞ ≤ ||V1 − V0 ||∞ [cite: 240] (8)
1−γ
Between steps, the bound is:
γ
[cites tart]||Vk − V ∗ ||∞ ≤ ||Vk − Vk−1 ||∞ [cite: 266] (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 [cite:
273]. [cites tart]

• Step 2 (Improvement): Update policy πk+1 by being greedy w.r.t Vπk [cite: 275]. [cites tart]

• Result: Converges because Vπk+1 ≥ Vπk monotonically[cite: 281].

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. [cites tart]
• Equation: Vk+1 = Tπmkk (Vk )[cite: 323].
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
[cites tart]T k V0 ≤ Vk ≤ T mi V0 [cite: 331] (10)

• Case A (V0 is low): If T V0 ≥ V0 , the values increase monotonically (Vk+1 ≥ Vk ) [cite: 332-346].
[cites tart]

• 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[cite: 364, 370].

5 Lecture 6A: Linear Programming & SSP

5.1 1. Linear Programming (LP)
[cites tart]W ecanf indV∗ by solving a single optimization problem [cite: 390-393]:

• 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. [cites tart]T heLP ”minimization”pushesth
[cite: 398-401].

5.2 2. Stochastic Shortest Path (SSP)

[cites tart]AnM DP whereγ = 1 (no discount) but there exists a termination state [cite: 417-419].
• Goal: Reach the termination state with minimum cost.

• Assumption: All policies must be ”proper” (eventually reach the goal). [cites tart]Improperpoliciesincurinf initeco
426 − 429].
• Convergence: Standard contraction proofs fail because γ = 1. [cites tart]W euseaWeighted Norm——·||ξ
to prove convergence, creating an ”effective” discount factor β < 1 [cite: 469-471].
MDP & RL Lecture Notes 5

6 Lecture 7: Model-Free Reinforcement Learning

6.1 1. Monte Carlo (MC)
1
PN
[cites tart]LearnsV(s)byaveragingreturnsf romcompleteepisodes[cite : 502, 516].Vπ (s) ≈ N i=1 Gi (11)
• First-Visit MC: Averages return only after the first visit to s in an episode. [cites tart]U nbiased[cite :
518].

• Every-Visit MC: Averages returns after every visit to s. [cites tart]Biasedbutconsistent[cite :

527].[cites tart]

• For Q(s, a): Requires ”Exploring Starts” or stochastic policies to ensure all pairs are visited [cite:
566-568].

6.2 2. Temporal Difference (TD)

[cites tart]Learnsby”bootstrapping”(guessingbasedonaguess)[cite : 569].
TD(0) Update: V (s) ← V (s) + α[r + γV (s′ ) − V (s)][cite: 595].
Benefit: Can learn during the episode; does not need to wait for the end. [cites tart]LowervariancethanM C[cite :
610 − 612].

6.3 3. n-Step TD
[cites tart]AbridgebetweenM CandT D[cite : 598].
Target: Sum of n actual rewards + estimated value of state n steps later[cite: 601].
Formula:
n
(n)
X
Qt = γ i−1 Rt+i + γ n Q(St+n , At+n ) (12)
i=1

[cites tart]
Error Decomposition: The n-step error is a weighted sum of individual 1-step TD er-
rors[cite: 616].