CS234 Lecture Notes: Foundations of RL and MDPs (Lectures 1 & 2)

I have been working through Stanford's CS234 course on Reinforcement Learning, taught by Professor Emma Brunskill, as part of building a solid theoretical foundation in RL. These are my notes from the first two lectures. Lecture 1 covers the framing of RL and builds up to Markov Reward Processes. Lecture 2 introduces Markov Decision Processes and the two core planning algorithms: policy iteration and value iteration. I have included active recall questions after each section, which I have found useful for making the material actually stick rather than just reading passively.

Lecture 1: What is Reinforcement Learning?

The Core Idea

Reinforcement learning is about learning through experience to make good decisions under uncertainty. Unlike supervised learning, there is no labeled dataset. The agent learns by interacting with an environment and receiving reward signals.

Four properties define most RL problems:

Optimization. The agent has an explicit objective: find the best possible policy, not just a good enough one.

Delayed consequences. Actions taken now affect rewards far in the future. This creates two sub-challenges: during planning, you have to reason about long-term ramifications, not just immediate effects. During learning, the credit assignment problem asks which past action actually caused a good or bad outcome.

Exploration. The agent learns about the world by acting in it. You only observe the reward for the action you took. You never see the counterfactual.

Generalization. A policy is a mapping from past experience to action. Effective RL requires generalizing from a limited number of observations to unseen states.

Sequential Decision Making

At each discrete timestep $t$, the agent-environment loop proceeds as follows:

1. Agent takes action $a_t$
2. World transitions, emits observation $o_t$ and reward $r_t$
3. Agent receives $o_t$ and $r_t$, updates its history

The full history up to time $t$ is:

$h_t = (a_1, o_1, r_1, \ldots, a_t, o_t, r_t)$

The agent selects its next action based on this history. In practice we compress the history into a state $s_t = f(h_t)$.

The Markov Assumption

A state $s_t$ is Markov if and only if:

$p(s_{t+1} \mid s_t, a_t) = p(s_{t+1} \mid h_t, a_t)$

The future is independent of the past, given the present. Instead of conditioning on the entire history, you only need the current state. In practice, we often assume $s_t = o_t$ (the most recent observation is a sufficient statistic). The state representation has big implications for computational complexity, data requirements, and resulting performance.

Markov Process (Markov Chain)

A Markov Process is the simplest building block: a memoryless random process over states with no rewards and no actions. It is a tuple $(\mathcal{S}, P)$ where:

• $\mathcal{S}$ is a finite set of states
• $P$ is a transition model: $P(s_{t+1} = s' \mid s_t = s)$

For $N$ states, $P$ is an $N \times N$ matrix. Given a Markov chain, you can sample episodes: sequences of states drawn according to the transition probabilities.

Markov Reward Process (MRP)

A Markov Reward Process adds a reward signal to a Markov Chain. It is a tuple $(\mathcal{S}, P, R, \gamma)$ where:

• $R(s) = \mathbb{E}[r_t \mid s_t = s]$ is the expected reward in state $s$
• $\gamma \in [0, 1]$ is the discount factor

There are still no actions.

The Return $G_t$. The foundational quantity in RL. It is the actual total discounted reward received from a specific trajectory starting at time $t$:

$G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}$

All value functions are simply the expected value $\mathbb{E}$ of this return $G_t$.

State Value Function $V(s)$. The expected return from starting in state $s$:

$V(s) = \mathbb{E}[G_t \mid s_t = s]$

Discount factor intuition:

• $\gamma = 0$: agent only cares about immediate reward
• $\gamma \to 1$: future rewards are weighted almost as heavily as immediate rewards
• If $H < \infty$ (finite episode), it is safe to use $\gamma = 1$

Two Views of the Value Function

The value function can be written in two mathematically equivalent ways.

Expectation form (global view). Defines value as the infinite sum of all future discounted rewards:

$V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \mid s_t = s \right]$

Bellman form (local / recursive view). Decomposes value into an immediate reward plus the discounted expected value of the next state:

$V(s) = \underbrace{R(s)}_{\text{immediate reward}} + \underbrace{\gamma \sum_{s' \in \mathcal{S}} P(s' \mid s) V(s')}_{\text{discounted future value}}$

These two forms are equivalent. The Bellman form is what makes computation tractable.

Computing the Value of an MRP

Analytic solution. In matrix form, $V = R + \gamma P V$, which rearranges to:

$V - \gamma P V = R \implies (I - \gamma P)V = R \implies V = (I - \gamma P)^{-1} R$

This requires a matrix inverse: $O(N^3)$ complexity. Only practical for small state spaces.

Iterative solution (dynamic programming). Initialize $V_0(s) = 0$ for all $s$. Then repeat until convergence:

$V_k(s) = R(s) + \gamma \sum_{s' \in \mathcal{S}} P(s' \mid s) V_{k-1}(s')$

Each iteration costs $O(|\mathcal{S}|^2)$, which is generally preferred.

Agent Components

An RL agent may include any combination of:

• Model: the agent's representation of how the world transitions ($P$) and what rewards look like ($R$)
• Policy $\pi$: a mapping from states to actions. Can be deterministic $\pi(s) = a$, or stochastic $\pi(a \mid s) = P(a_t = a \mid s_t = s)$
• Value function: quantifies the expected future return from a state or state-action pair

Model-based agents have an explicit model. Model-free agents learn a policy and/or value function directly without building one.

Lecture 2: MDPs, Policy Iteration, and Value Iteration

Markov Decision Process (MDP)

An MDP is an MRP with actions. It is a tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ where:

• $\mathcal{A}$ is a finite set of actions
• $P(s_{t+1} = s' \mid s_t = s, a_t = a)$ is the transition model conditioned on action
• $R(s, a) = \mathbb{E}[r_t \mid s_t = s, a_t = a]$ is the reward for taking action $a$ in state $s$

MDP + policy = MRP. Given a policy $\pi(a \mid s)$, the MDP reduces to an MRP with:

$R^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) R(s, a), \qquad P^\pi(s' \mid s) = \sum_{a \in \mathcal{A}} \pi(a \mid s) P(s' \mid s, a)$

This means all MRP techniques carry over directly for policy evaluation.

Value Functions in an MDP

With actions in the picture, there are two distinct value functions.

State-value function $V^\pi(s)$. The expected return starting from state $s$ and following policy $\pi$:

$V^\pi(s) = \mathbb{E}_\pi [G_t \mid s_t = s]$

Action-value function $Q^\pi(s, a)$. The expected return starting from state $s$, taking action $a$, then following policy $\pi$ thereafter:

$Q^\pi(s, a) = \mathbb{E}_\pi [G_t \mid s_t = s, a_t = a]$

Interdependence of $V$ and $Q$

$V^\pi$ and $Q^\pi$ are intrinsically linked. Each can be written in terms of the other:

Bellman Equations for $V^\pi$ and $Q^\pi$

Substituting the interdependence relations into each other gives the full Bellman expectation equations:

$V^\pi(s) = \mathbb{E}_\pi \left[ r_{t+1} + \gamma V^\pi(s_{t+1}) \mid s_t = s \right]$

$Q^\pi(s, a) = \mathbb{E}_\pi \left[ r_{t+1} + \gamma Q^\pi(s_{t+1}, a_{t+1}) \mid s_t = s, a_t = a \right]$

Policy Evaluation (Iterative)

Initialize $V_0^\pi(s) = 0$ for all $s$, then apply the Bellman expectation backup repeatedly:

$V_k^\pi(s) = \sum_a \pi(a \mid s) \left[ R(s, a) + \gamma \sum_{s'} p(s' \mid s, a)\, V_{k-1}^\pi(s') \right]$

For a deterministic policy this simplifies to:

$V_k^\pi(s) = R(s, \pi(s)) + \gamma \sum_{s' \in \mathcal{S}} p(s' \mid s, \pi(s))\, V_{k-1}^\pi(s')$

Continue until $\Delta = \max_s |V_k(s) - V_{k-1}(s)| < \theta$ for some small threshold $\theta$.

MDP Control

The goal of control is to find the optimal policy:

$\pi^*(s) = \arg\max_\pi V^\pi(s)$

Key facts about the optimal policy in an infinite-horizon MDP:

• It is deterministic: randomness is never needed at optimality
• It is stationary: the same action is prescribed for a given state regardless of the timestep
• The optimal value function $V^*$ is unique, but the optimal policy is not necessarily (ties are possible)

The number of deterministic policies is $|\mathcal{A}|^{|\mathcal{S}|}$, so exhaustive search is never feasible.

Policy Iteration

Policy Iteration (PI) discovers the optimal policy by alternating between exact policy evaluation and greedy policy improvement.

Step 1: Initialization. Initialize $V(s) \in \mathbb{R}$ and $\pi(s)$ arbitrarily for all states. Set a small convergence threshold $\theta > 0$.

Step 2: Policy Evaluation (inner loop). Repeat until $\Delta < \theta$:

$\Delta \leftarrow 0, \quad v \leftarrow V(s), \quad V(s) \leftarrow \sum_{s', r} p(s', r \mid s, \pi(s))\left[r + \gamma V(s')\right], \quad \Delta \leftarrow \max(\Delta, |v - V(s)|)$

Step 3: Policy Improvement. For each state $s$:

$\pi(s) \leftarrow \arg\max_a \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma V(s')\right]$

If the policy changed for any state, return to Step 2. Otherwise, stop and return $V^*$ and $\pi^*$.

The Policy Improvement Theorem

Theorem. Given two deterministic policies $\pi$ and $\pi'$, if for all $s \in \mathcal{S}$:

$Q^\pi(s, \pi'(s)) \geq V^\pi(s)$

then $\pi'$ is globally at least as good:

$V^{\pi'}(s) \geq V^\pi(s) \quad \forall s \in \mathcal{S}$

Proof by unrolling the Bellman equation:

1. Assumption: $V^\pi(s) \leq Q^\pi(s, \pi'(s))$

2. Expand $Q^\pi$ at $t=1$:

$V^\pi(s) \leq \mathbb{E}_{\pi'}\left[r_{t+1} + \gamma V^\pi(s_{t+1}) \mid s_t = s\right]$

3. Apply the inequality again at $s_{t+1}$ ($t=2$):

$V^\pi(s) \leq \mathbb{E}_{\pi'}\left[r_{t+1} + \gamma r_{t+2} + \gamma^2 V^\pi(s_{t+2}) \mid s_t = s\right]$

4. Continue unrolling for $n$ steps:

$V^\pi(s) \leq \mathbb{E}_{\pi'}\left[r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{n-1} r_{t+n} + \gamma^n V^\pi(s_{t+n}) \mid s_t = s\right]$

5. Take $n \to \infty$. Because $\gamma < 1$, the remainder $\gamma^n V^\pi(s_{t+n}) \to 0$:

$V^\pi(s) \leq \mathbb{E}_{\pi'}\left[\sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \mid s_t = s\right] = V^{\pi'}(s)$

$\therefore V^{\pi'}(s) \geq V^\pi(s)$ $\blacksquare$

Convergence of PI. If the policy does not change after an improvement step, it can never change again (since $Q^{\pi_{i+1}} = Q^{\pi_i}$ implies $\pi_{i+2} = \pi_{i+1}$). Because there are at most $|\mathcal{A}|^{|\mathcal{S}|}$ distinct policies and each step is strictly improving, policy iteration always terminates.

Value Iteration

Value Iteration (VI) merges evaluation and improvement into a single step by applying the Bellman optimality operator $B$ directly at each iteration.

Bellman Optimality Equations. These define the maximum expected return achievable by acting optimally:

$V^*(s) = \max_a \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma V^*(s')\right]$

$Q^*(s, a) = \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma \max_{a'} Q^*(s', a')\right]$

Algorithm:

1. Initialize $V_0(s) = 0$ for all states. Set threshold $\theta > 0$.
2. For each state $s$, apply the Bellman optimality backup:

$V_{k+1}(s) = \max_{a \in \mathcal{A}} \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma V_k(s')\right]$

3. Compute $\Delta = \max_s |V_{k+1}(s) - V_k(s)|$. If $\Delta < \theta$, stop.
4. Extract the optimal policy greedily:

$\pi^*(s) = \arg\max_a \sum_{s', r} p(s', r \mid s, a)\left[r + \gamma V^*(s')\right]$

Equivalently in operator notation: $V_{k+1} = BV_k$.

Convergence of Value Iteration (Contraction Mapping)

VI converges because $B$ is a $\gamma$-contraction mapping under the infinity norm $\|V\| = \max_s |V(s)|$.

Proof. For any two value functions $V$ and $U$:

$\|(BV)(s) - (BU)(s)\| = \left|\max_a \mathbb{E}\left[r + \gamma V(s')\right] - \max_a \mathbb{E}\left[r + \gamma U(s')\right]\right|$

Apply $|\max f - \max g| \leq \max|f - g|$:

$\leq \max_a \left|\mathbb{E}\left[r + \gamma V(s')\right] - \mathbb{E}\left[r + \gamma U(s')\right]\right|$

Cancel the reward $r$ (identical in both):

$= \max_a \left|\gamma\, \mathbb{E}\left[V(s') - U(s')\right]\right|$

Bound by the worst-case difference across all states:

$\leq \gamma \max_{s'} |V(s') - U(s')| = \gamma \|V - U\|_\infty$

Since this holds for all $s$:

$\|BV - BU\|_\infty \leq \gamma \|V - U\|_\infty$

Because $\gamma < 1$, the distance to $V^*$ shrinks by a factor of $\gamma$ at every iteration. Value iteration converges to the unique optimal value function $V^*$. $\blacksquare$

Finite Horizon Value Iteration

For a finite horizon $H$, the algorithm runs for exactly $H$ steps rather than until convergence:

• $V_k$: optimal value with $k$ decisions remaining
• $\pi_k$: optimal policy with $k$ decisions remaining
• Initialize $V_0(s) = 0$, iterate $k = 1$ to $H$

The optimal policy in a finite-horizon problem is non-stationary: $\pi_k$ depends on how many steps remain, not just the current state. This is a fundamental difference from the infinite-horizon case.

Policy Iteration vs Value Iteration

I will keep adding notes as I work through the rest of the course, along with my solutions to each assignment. More to come.