---
title: Foundations of Reinforcement Learning
module: Reinforcement Learning
moduleNumber: 11
lessonNumber: 1
order: 1101
summary: >
  Reinforcement learning is the third paradigm: an agent learns to act by
  interacting with an environment that returns rewards, not labels. We formalize
  the interaction as a Markov decision process, define the value functions that
  rank states and actions, and derive the Bellman expectation and optimality
  equations that every method downstream solves. Dynamic programming gives the
  exact answer when the model is known, and its convergence rests on a single
  fact: the Bellman operator is a contraction.
topics: [Reinforcement Learning]
sources:
  - book: Goodfellow
    ref: "Ch. 1 — RL as a paradigm distinct from supervised/unsupervised learning"
---

Supervised learning fits a function to labelled examples; unsupervised learning
models the structure of unlabelled data. **Reinforcement learning** is the third
paradigm: there are no labels, only a stream of interaction, and a scalar
**reward** that says how good the last move was but never which move was right.[^gf-paradigm]
An agent must discover a good behaviour by trying actions and observing their
consequences, trading off the reward available now against the states its choices
lead to later. This lesson builds the formal object that makes the problem
tractable, the Markov decision process, and derives the equations that every
algorithm in the rest of the module solves, exactly or approximately.

## The agent-environment interface

At each discrete step $t$ the agent observes a **state** $S_t \in \mathcal{S}$,
selects an **action** $A_t \in \mathcal{A}$, and the environment responds with a
scalar **reward** $R_{t+1} \in \mathbb{R}$ and a next state $S_{t+1}$. The loop
closes and repeats. Everything the agent can learn is contained in the resulting
trajectory $S_0, A_0, R_1, S_1, A_1, R_2, \dots$.

$$
% caption: The agent-environment loop. The agent picks action $A_t$ in state
% $S_t$; the environment returns reward $R_{t+1}$ and next state $S_{t+1}$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % two boxes
  \draw[acc, very thick, fill=acc!12] (-2.7,0.75) rectangle (0.0,2.05);
  \node[acc] at (-1.35,1.4) {agent};
  \draw[black, very thick, fill=black!8] (4.0,0.75) rectangle (6.9,2.05);
  \node[black] at (5.45,1.4) {\texttt{environment}};
  % action: agent -> environment (top)
  \draw[acc, very thick, ->] (0.0,1.75) -- (4.0,1.75);
  \node[acc, anchor=south] at (2.0,1.82) {action $A_t$};
  % reward and state: environment -> agent (bottom, looping under)
  \draw[black, very thick, ->] (4.0,1.05) -- (0.0,1.05);
  \node[black, anchor=north] at (2.0,0.98) {state $S_{t+1}$, reward $R_{t+1}$};
  % time index hint
  \node[anchor=north, font=\footnotesize] at (2.0,0.55) {\texttt{one step per transition}};
\end{tikzpicture}
$$

The environment is the source of both signals the agent does not control, the
reward and the next state. The agent controls only its action. The whole of
reinforcement learning is the question of how to choose actions, from experience
alone, so that the long-run reward is large.

> **Definition (Reward hypothesis).** Every goal can be encoded as the
> maximization of the expected cumulative scalar reward. The agent's purpose is
> not to maximize the immediate $R_{t+1}$ but the **return**, the total reward
> accumulated from $t$ onward.

The single most important distinction from supervised learning: the reward is
**evaluative**, not **instructive**. A label tells the model the correct output;
a reward only scores the action taken, leaving the agent to infer, across many
trials, which actions were responsible. This is the credit-assignment problem,
and it is why the value functions below exist.

## Markov decision processes

The interface becomes solvable once we assume the dynamics are **Markov**: the
next state and reward depend only on the current state and action, not on the
full history. The history collapses into the present state.

> **Definition (Markov property).** A state $S_t$ is Markov if
> $$
> \Pr\!\brackets{S_{t+1}=s',\, R_{t+1}=r \mid S_0,A_0,\dots,S_t,A_t}
> = \Pr\!\brackets{S_{t+1}=s',\, R_{t+1}=r \mid S_t,A_t}.
> $$
> The present state is a sufficient statistic of the past for predicting the
> future.

A finite **Markov decision process** packages the dynamics into a five-tuple.

> **Definition (Markov decision process).** An MDP is a tuple
> $\parens{\mathcal{S},\mathcal{A},P,R,\gamma}$ where $\mathcal{S}$ is the state
> set, $\mathcal{A}$ the action set,
> $P\parens{s' \mid s,a} = \Pr\!\brackets{S_{t+1}=s' \mid S_t=s, A_t=a}$ the
> transition kernel, $R\parens{s,a} = \mathbb{E}\!\brackets{R_{t+1} \mid S_t=s, A_t=a}$
> the expected reward, and $\gamma \in [0,1]$ the discount factor. The dynamics
> satisfy $\sum_{s'} P\parens{s' \mid s,a} = 1$ for every $s,a$.

The kernel $P$ and reward $R$ together are the **model**. When the agent knows
them, the problem is one of planning, solved exactly by the dynamic programming of
the last section. When it does not, it must learn from sampled transitions, the
subject of later lessons. For example, in a small gridworld, states are
cells, actions move between adjacent cells, and the reward is $-1$ per step until a
goal cell is reached.

$$
% caption: A $3\times 3$ gridworld MDP. States are cells, four actions move to
% adjacent cells, reward is $-1$ per step; reaching the goal $G$ ends the episode.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % 3x3 grid of cells
  \foreach \i in {0,1,2}
    \foreach \j in {0,1,2}
      \draw[black, thick] (\i*1.4,\j*1.4) rectangle (\i*1.4+1.4,\j*1.4+1.4);
  % start cell (bottom-left)
  \draw[acc, very thick, fill=acc!12] (0,0) rectangle (1.4,1.4);
  \node[acc] at (0.7,0.7) {start};
  % goal cell (top-right)
  \draw[green, very thick, fill=green!15] (2.8,2.8) rectangle (4.2,4.2);
  \node[green] at (3.5,3.5) {goal $G$};
  % a sample action arrow inside the grid
  \draw[acc, very thick, ->] (0.7,1.5) -- (0.7,2.5);
  \node[acc, anchor=west, font=\footnotesize] at (4.45,2.7) {\texttt{action: up}};
  \draw[acc, very thick, ->] (1.5,3.5) -- (2.5,3.5);
  \node[acc, anchor=west, font=\footnotesize] at (4.45,3.4) {\texttt{action: right}};
  % reward label
  \node[red, anchor=west, font=\footnotesize] at (4.45,1.9) {\texttt{penalty 1 per step}};
\end{tikzpicture}
$$

The Markov assumption is a modelling choice, not a law of nature. If the raw
observation is not Markov (a single video frame hides velocity), the standard fix
is to engineer a state that is, by stacking frames or carrying a recurrent summary,
so that the tuple above applies to the constructed state.

## Returns and discounting

The agent maximizes the **return** $G_t$, the discounted sum of future rewards. The
discount $\gamma$ weights a reward $k$ steps away by $\gamma^k$.

$$
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}.
$$

The definition obeys a one-step recursion that drives every equation downstream:
peel off the first reward and the rest is a return from $t+1$.

$$
G_t \;=\; R_{t+1} + \gamma\parens{R_{t+2} + \gamma R_{t+3} + \cdots}
\;=\; R_{t+1} + \gamma\, G_{t+1}.
$$

Two regimes arise. An **episodic** task terminates in an absorbing state (a game
ends, a maze is solved), so the sum is finite and $\gamma=1$ is admissible. A
**continuing** task runs forever, and the sum converges only because $\gamma<1$
bounds it: if $\abs{R} \le R_{\max}$ then
$\abs{G_t} \le R_{\max}\sum_{k\ge 0}\gamma^k = R_{\max}/\parens{1-\gamma}$.

> **Definition (Discount factor).** The scalar $\gamma \in [0,1]$ trading present
> against future reward. At $\gamma=0$ the agent is myopic, maximizing only
> $R_{t+1}$; as $\gamma \to 1$ it becomes far-sighted. The effective horizon is
> $1/\parens{1-\gamma}$ steps.

| Quantity | $\gamma = 0$ | $\gamma = 0.9$ | $\gamma = 0.99$ |
| --- | --- | --- | --- |
| Effective horizon $1/\parens{1-\gamma}$ | $1$ step | $10$ steps | $100$ steps |
| Weight on reward $10$ steps out | $0$ | $0.35$ | $0.90$ |
| Behaviour | myopic | balanced | far-sighted |

Beyond guaranteeing convergence, discounting encodes a genuine preference: a
reward now is worth more than the same reward later, and it caps the influence of
the distant, uncertain future on the present decision. The weight the return
places on the reward $k$ steps ahead is exactly $\gamma^k$, and the two discount
factors decay at visibly different rates.

$$
% caption: Discount weight $\gamma^k$ on the reward $k$ steps ahead, for
% $\gamma=0.9$ (blue) and $\gamma=0.99$ (green). The smaller discount forgets the
% future quickly; the larger one keeps distant rewards nearly at full weight.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (-0.2,0) -- (9.4,0) node[right, font=\scriptsize] {step $k$};
  \draw[->, thick] (0,-0.2) -- (0,3.3) node[above, font=\scriptsize] {weight};
  \node[anchor=east, font=\scriptsize] at (-0.1,3.0) {$1$};
  \draw[black, thin] (-0.08,3.0) -- (0.08,3.0);
  % gamma = 0.9 bars (blue), 0.9^k * 3.0, k = 0..8
  \foreach \k in {0,1,2,3,4,5,6,7,8} {
    \pgfmathsetmacro{\h}{3.0*pow(0.9,\k)}
    \fill[acc!70] (\k*1.0+0.12,0) rectangle (\k*1.0+0.46,\h);
  }
  % gamma = 0.99 bars (green), 0.99^k * 3.0
  \foreach \k in {0,1,2,3,4,5,6,7,8} {
    \pgfmathsetmacro{\h}{3.0*pow(0.99,\k)}
    \fill[green!70] (\k*1.0+0.52,0) rectangle (\k*1.0+0.86,\h);
  }
  % legend below the axis, clear of the bars
  \fill[acc!70] (2.2,-0.75) rectangle (2.5,-0.5);
  \node[acc, anchor=west, font=\footnotesize] at (2.6,-0.62) {\texttt{small discount}};
  \fill[green!70] (5.3,-0.75) rectangle (5.6,-0.5);
  \node[green, anchor=west, font=\footnotesize] at (5.7,-0.62) {\texttt{large discount}};
\end{tikzpicture}
$$

## Policies and value functions

A **policy** is the agent's behaviour: a mapping from states to a distribution
over actions, $\pi\parens{a \mid s} = \Pr\!\brackets{A_t = a \mid S_t = s}$. A
deterministic policy is the special case that puts all mass on one action,
$\pi(s) = a$. The agent's task is to find a policy whose return is large, and to
rank policies we need to measure the return a policy earns, which is what the value
functions do.

> **Definition (State-value function).** For a policy $\pi$, the **state-value**
> of $s$ is the expected return starting from $s$ and following $\pi$ thereafter,
> $$
> V^{\pi}(s) \;=\; \mathbb{E}_{\pi}\!\brackets{G_t \mid S_t = s}
> \;=\; \mathbb{E}_{\pi}\!\brackets{\textstyle\sum_{k\ge 0}\gamma^{k} R_{t+k+1} \,\middle|\, S_t = s}.
> $$

> **Definition (Action-value function).** The **action-value** of taking $a$ in
> $s$ and following $\pi$ afterward,
> $$
> Q^{\pi}(s,a) \;=\; \mathbb{E}_{\pi}\!\brackets{G_t \mid S_t = s,\, A_t = a}.
> $$
> It scores a state-action pair, which is what an agent must compare to choose an
> action.

The two are linked by averaging $Q^\pi$ over the policy's action distribution, and
conversely by expanding one step of dynamics:

$$
V^{\pi}(s) = \sum_{a} \pi\parens{a \mid s}\, Q^{\pi}(s,a),
\qquad
Q^{\pi}(s,a) = R(s,a) + \gamma \sum_{s'} P\parens{s' \mid s,a}\, V^{\pi}(s').
$$

The first identity says a state's value is the policy-weighted average of its
action-values; the second says an action's value is its immediate reward plus the
discounted value of where it leads.

## The Bellman expectation equations

Substituting each identity into the other produces a self-consistency condition on
$V^\pi$ alone, the **Bellman expectation equation**. We derive it from the return
recursion $G_t = R_{t+1} + \gamma G_{t+1}$.

$$
\begin{aligned}
V^{\pi}(s)
&= \mathbb{E}_{\pi}\!\brackets{G_t \mid S_t = s} \\
&= \mathbb{E}_{\pi}\!\brackets{R_{t+1} + \gamma\, G_{t+1} \mid S_t = s}
   && \text{(return recursion)} \\
&= \mathbb{E}_{\pi}\!\brackets{R_{t+1} \mid S_t = s}
   + \gamma\, \mathbb{E}_{\pi}\!\brackets{G_{t+1} \mid S_t = s}
   && \text{(linearity)} \\
&= \sum_{a} \pi\parens{a \mid s}\, R(s,a)
   + \gamma \sum_{a}\pi\parens{a \mid s}\sum_{s'} P\parens{s' \mid s,a}\,
     \mathbb{E}_{\pi}\!\brackets{G_{t+1} \mid S_{t+1}=s'} \\
&= \sum_{a} \pi\parens{a \mid s}
   \brackets{ R(s,a) + \gamma \sum_{s'} P\parens{s' \mid s,a}\, V^{\pi}(s') }.
\end{aligned}
$$

The third line splits the expectation and conditions the second term on the next
state; the fourth uses $\mathbb{E}_\pi[G_{t+1} \mid S_{t+1}=s'] = V^\pi(s')$, the
definition of the value function one step later. The same argument applied to
$Q^\pi$ gives its Bellman expectation equation:

$$
Q^{\pi}(s,a) = R(s,a) + \gamma \sum_{s'} P\parens{s' \mid s,a}
  \sum_{a'} \pi\parens{a' \mid s'}\, Q^{\pi}(s',a').
$$

> **Definition (Bellman expectation equation).** A linear system that the value
> of a fixed policy must satisfy: each state's value equals the expected immediate
> reward plus the discounted expected value of the successor state, with the
> expectation taken over both the policy and the dynamics.

These equations are read off a **backup diagram**: a one-step look-ahead tree that
averages over the action chosen by $\pi$ (open circles) and the next state drawn
by $P$ (filled circles), backing the successor values up to the root.

$$
% caption: Backup diagram for $V^{\pi}$. From state $s$ average over actions
% $a \sim \pi$, then over next states $s' \sim P$, backing values up to the root.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % root state s
  \fill[black] (0,0) circle (3pt);
  \node[anchor=east] at (-0.15,0) {$s$};
  % two action nodes
  \draw[black, very thick] (0,0) -- (-1.6,-1.2);
  \draw[black, very thick] (0,0) -- (1.6,-1.2);
  \draw[acc, very thick, fill=acc!12] (-1.6,-1.2) circle (3.5pt);
  \draw[acc, very thick, fill=acc!12] (1.6,-1.2) circle (3.5pt);
  \node[acc, anchor=east, font=\scriptsize] at (-1.78,-1.2) {$a$};
  \node[acc, anchor=west, font=\scriptsize] at (1.78,-1.2) {$a$};
  \node[acc, anchor=east, font=\footnotesize] at (-1.15,-0.35) {\texttt{policy}};
  % next-state nodes under each action
  \foreach \ax in {-1.6,1.6} {
    \draw[black, very thick] (\ax,-1.2) -- (\ax-0.9,-2.6);
    \draw[black, very thick] (\ax,-1.2) -- (\ax+0.9,-2.6);
    \fill[black] (\ax-0.9,-2.6) circle (3pt);
    \fill[black] (\ax+0.9,-2.6) circle (3pt);
  }
  \node[anchor=west, font=\scriptsize] at (2.65,-1.7) {$P$};
  \node[anchor=north, font=\footnotesize] at (-0.7,-2.7) {\texttt{next}};
  \node[anchor=north, font=\footnotesize] at (2.5,-2.7) {\texttt{next}};
  % reward annotation
  \node[green, anchor=west, font=\footnotesize] at (2.7,-0.6) {\texttt{reward R(s,a)}};
\end{tikzpicture}
$$

### A backup by hand

Take a gridworld cell $s$ whose
action is fixed by the policy to _up_, with reward $-1$ per step and $\gamma=0.9$.
Suppose the move is stochastic: with probability $0.8$ the agent lands in the
intended cell $s_\uparrow$, and with probability $0.1$ each it slips left into
$s_\leftarrow$ or right into $s_\rightarrow$. From a current value estimate
$V(s_\uparrow)=5$, $V(s_\leftarrow)=2$, $V(s_\rightarrow)=1$, the Bellman
expectation backup evaluates one line of arithmetic:

$$
\begin{aligned}
V(s)
&= R(s,a) + \gamma\!\sum_{s'} P\parens{s'\mid s,a}\, V(s') \\
&= -1 + 0.9\,\brackets{ 0.8\cdot 5 + 0.1\cdot 2 + 0.1\cdot 1 } \\
&= -1 + 0.9\,\brackets{ 4.0 + 0.2 + 0.1 }
 = -1 + 0.9\cdot 4.3
 = 2.87.
\end{aligned}
$$

The successor values are averaged under the transition probabilities, scaled by
$\gamma$, and offset by the one-step reward. Every method in this module reduces to
a rule for producing and repeating that single number.

$$
% caption: One value backup on a gridworld cell. The successor values $5,2,1$ are
% weighted by $P=0.8,0.1,0.1$, discounted by $\gamma=0.9$, and added to the reward
% $-1$, giving $V(s)=-1+0.9(4.3)=2.87$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % root
  \fill[acc] (0,0) circle (3pt);
  \node[acc, anchor=east] at (-0.15,0) {$s$};
  \node[acc, anchor=south, font=\footnotesize] at (0,0.2) {\texttt{V(s) = 2.87}};
  % three successor branches
  \draw[black, very thick] (0,0) -- (-2.4,-2.0);
  \draw[black, very thick] (0,0) -- (0,-2.0);
  \draw[black, very thick] (0,0) -- (2.4,-2.0);
  \fill[green] (-2.4,-2.0) circle (3pt);
  \fill[green] (0,-2.0) circle (3pt);
  \fill[green] (2.4,-2.0) circle (3pt);
  % successor value labels
  \node[green, anchor=north, font=\footnotesize] at (-2.4,-2.15) {\texttt{V = 5}};
  \node[green, anchor=north, font=\footnotesize] at (0,-2.15) {\texttt{V = 2}};
  \node[green, anchor=north, font=\footnotesize] at (2.4,-2.15) {\texttt{V = 1}};
  % probability labels on branches
  \node[black, font=\footnotesize] at (-1.55,-0.75) {\texttt{P = 0.8}};
  \node[black, font=\footnotesize] at (0.55,-1.0) {\texttt{P = 0.1}};
  \node[black, font=\footnotesize] at (1.55,-0.75) {\texttt{P = 0.1}};
  % reward tag
  \node[acc, anchor=west, font=\footnotesize] at (2.9,-0.5) {\texttt{reward -1, discount 0.9}};
\end{tikzpicture}
$$

## Optimal value functions

A policy $\pi$ is at least as good as $\pi'$ if $V^{\pi}(s) \ge V^{\pi'}(s)$ for
every state. This partial order has a maximum: there always exists an **optimal
policy** $\pi^\star$ that dominates all others simultaneously. Its
value functions are the **optimal value functions**:

$$
V^{\star}(s) = \max_{\pi} V^{\pi}(s),
\qquad
Q^{\star}(s,a) = \max_{\pi} Q^{\pi}(s,a),
\qquad \text{for all } s,a.
$$

Optimality replaces the policy-average in the Bellman equation with a $\max$ over
actions: the optimal value of a state is the value of its **best** action, not the
average over a fixed policy. The two backups differ at exactly one node, where the
action branches meet.

$$
% caption: Expectation backup (left) averages the action values under
% $\pi(a\mid s)$; optimality backup (right) takes the $\max$ over actions. Both
% then average over next states under $P$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % ---- left tree: expectation (average) ----
  \node[acc, anchor=west, font=\footnotesize] at (-1.6,0.7) {\texttt{expectation: average}};
  \fill[black] (0,-0.2) circle (2.5pt);
  \node[anchor=west, font=\scriptsize] at (0.12,-0.1) {$s$};
  \draw[black, very thick] (0,-0.2) -- (-0.9,-1.4);
  \draw[black, very thick] (0,-0.2) -- (0.9,-1.4);
  \draw[acc, very thick, fill=acc!12] (-0.9,-1.4) circle (3pt);
  \draw[acc, very thick, fill=acc!12] (0.9,-1.4) circle (3pt);
  \node[anchor=north, font=\footnotesize] at (0,-1.75) {\texttt{V(s): mean over a}};
  % ---- right tree: optimality (max) ----
  \begin{scope}[xshift=5.2cm]
    \node[green, anchor=west, font=\footnotesize] at (-1.6,0.7) {\texttt{optimality: max}};
    \fill[black] (0,-0.2) circle (2.5pt);
    \node[anchor=west, font=\scriptsize] at (0.12,-0.1) {$s$};
    \draw[black, very thick] (0,-0.2) -- (-0.9,-1.4);
    \draw[green, ultra thick] (0,-0.2) -- (0.9,-1.4);
    \draw[acc, very thick, fill=acc!12] (-0.9,-1.4) circle (3pt);
    \draw[green, very thick, fill=green!18] (0.9,-1.4) circle (3pt);
    \node[anchor=north, font=\footnotesize] at (0,-1.75) {\texttt{V(s): best a}};
  \end{scope}
\end{tikzpicture}
$$

> **Theorem (Bellman optimality equations).** The optimal value functions are the
> unique solutions of
> $$
> V^{\star}(s) = \max_{a}\brackets{ R(s,a) + \gamma \sum_{s'} P\parens{s' \mid s,a}\, V^{\star}(s') },
> $$
> $$
> Q^{\star}(s,a) = R(s,a) + \gamma \sum_{s'} P\parens{s' \mid s,a}\, \max_{a'} Q^{\star}(s',a').
> $$

The optimality equation immediately yields the optimal policy: act **greedily**
with respect to $Q^\star$. There is no need to look further than one step, because
$Q^\star$ has already folded the entire future into each action-value.

> **Theorem (Greedy optimality).** Any policy greedy with respect to $Q^{\star}$
> is optimal:
> $$
> \pi^{\star}(s) \in \arg\max_{a} Q^{\star}(s,a) = \arg\max_{a}\brackets{ R(s,a) + \gamma\sum_{s'} P\parens{s'\mid s,a}\,V^{\star}(s') }.
> $$
> Knowing $Q^{\star}$ reduces control to a one-step maximization; knowing
> $V^{\star}$ requires one extra look-ahead through the model.

> **Proof.** Let $\pi^\star$ be greedy w.r.t. $Q^\star$. Then
> $\sum_a \pi^\star(a\mid s) Q^\star(s,a) = \max_a Q^\star(s,a) = V^\star(s)$ by the
> optimality equation, so $V^{\pi^\star}(s) = V^\star(s)$ at every state: the greedy
> policy attains the optimal value, hence is optimal. The contrast with $V^\star$ is
> that selecting the best action from $V^\star$ still needs the model $P$ to evaluate
> the look-ahead, whereas $Q^\star$ stores the result of that look-ahead directly. $\qed$

This is why the model-free methods of later lessons, such as $Q$-learning, target
$Q^\star$ rather than $V^\star$: with $Q^\star$ in hand, the agent acts optimally
without ever consulting a model.

## Dynamic programming

When the model $\parens{P,R}$ is known, the Bellman equations can be turned into
algorithms that compute the value functions exactly. Two ideas combine:
**policy evaluation** computes $V^\pi$ for a fixed policy, and **policy
improvement** turns a value function into a better policy.

**Iterative policy evaluation** treats the Bellman expectation equation as an
assignment, sweeping it to convergence:

$$
V_{k+1}(s) \;\gets\; \sum_{a}\pi\parens{a\mid s}\brackets{ R(s,a) + \gamma \sum_{s'} P\parens{s'\mid s,a}\, V_{k}(s') }.
$$

**Policy improvement** replaces $\pi$ with the policy greedy w.r.t. its own value:

$$
\pi'(s) \;\gets\; \arg\max_{a}\brackets{ R(s,a) + \gamma\sum_{s'} P\parens{s'\mid s,a}\, V^{\pi}(s') }.
$$

> **Theorem (Policy improvement).** If $\pi'$ is greedy w.r.t. $V^{\pi}$, then
> $V^{\pi'}(s) \ge V^{\pi}(s)$ for all $s$, with strict inequality somewhere
> unless $\pi$ is already optimal.

Alternating the two is **policy iteration**: evaluate the current policy fully,
then improve it, and repeat until the policy stops changing.

```algorithm
caption: $\textsc{PolicyIteration}(\mathcal{S},\mathcal{A},P,R,\gamma)$ — exact optimal policy from a known model
initialize $V(s) \gets 0$ and an arbitrary policy $\pi(s)$ for all $s$
repeat
  repeat // policy evaluation: solve $V^{\pi}$
    for each $s \in \mathcal{S}$ do
      $V(s) \gets R(s,\pi(s)) + \gamma \sum_{s'} P(s' \mid s,\pi(s))\, V(s')$
  until $V$ changes by less than tolerance
  stable $\gets$ true
  for each $s \in \mathcal{S}$ do // policy improvement: act greedily
    $a^{\ast} \gets \arg\max_{a} \brackets{R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V(s')}$
    if $a^{\ast} \ne \pi(s)$ then
      $\pi(s) \gets a^{\ast}$; stable $\gets$ false
until stable
return $\pi, V$
```

The two operations alternate around a cycle: evaluation makes $V$ consistent
with $\pi$, improvement makes $\pi$ greedy w.r.t. $V$, and the fixed point of the
cycle satisfies the Bellman optimality equation.

$$
% caption: The policy-iteration cycle. Evaluation drives $V$ toward $V^{\pi}$;
% improvement makes $\pi$ greedy in $V$. The fixed point is $\parens{V^{\star},\pi^{\star}}$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % two nodes: policy and value
  \draw[acc, very thick, fill=acc!12] (-2.6,0) circle (1.0);
  \node[acc, align=center] at (-2.6,0) {\texttt{policy}};
  \draw[black, very thick, fill=black!8] (2.6,0) circle (1.0);
  \node[black, align=center] at (2.6,0) {\texttt{value} $V$};
  % top arrow: evaluation policy -> V
  \draw[black, very thick, ->] (-1.7,0.55) .. controls (0,1.7) .. (1.7,0.55);
  \node[black, anchor=south] at (0,1.35) {\texttt{evaluate}};
  % bottom arrow: improvement V -> policy
  \draw[acc, very thick, ->] (1.7,-0.55) .. controls (0,-1.7) .. (-1.7,-0.55);
  \node[acc, anchor=north] at (0,-1.35) {\texttt{improve: greedy in} $V$};
  % convergence target
  \node[green, anchor=west, font=\footnotesize] at (3.9,0) {\texttt{converges to optimum}};
\end{tikzpicture}
$$

**Value iteration** short-circuits the cycle: rather than evaluate each policy to
convergence, it applies the Bellman _optimality_ update once per sweep, folding
improvement and evaluation into a single $\max$.

```algorithm
caption: $\textsc{ValueIteration}(\mathcal{S},\mathcal{A},P,R,\gamma,\varepsilon)$ — iterate the Bellman optimality operator
initialize $V(s) \gets 0$ for all $s$
repeat
  $\Delta \gets 0$
  for each $s \in \mathcal{S}$ do
    $v \gets V(s)$
    $V(s) \gets \max_{a} \brackets{R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V(s')}$ // optimality backup
    $\Delta \gets \max\parens{\Delta,\ \abs{v - V(s)}}$
  until $\Delta < \varepsilon$
for each $s \in \mathcal{S}$ do // extract the greedy policy
  $\pi(s) \gets \arg\max_{a} \brackets{R(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V(s')}$
return $\pi, V$
```

Each sweep contracts the error toward zero, so the value estimate converges
geometrically to $V^\star$. The error after $k$ sweeps shrinks like $\gamma^k$.

$$
% caption: Value-iteration convergence. The max-norm error $\norm{V_k - V^{\star}}$
% falls geometrically as $\gamma^{k}$; a larger $\gamma$ (blue) decays slower than a
% smaller one (red).
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, thick] (-0.3,0) -- (8.6,0) node[right, font=\footnotesize] {sweep $k$};
  \draw[->, thick] (0,-0.3) -- (0,3.6) node[above, font=\footnotesize] {error};
  % geometric decay curve for gamma close to 1
  \draw[acc, very thick] plot[domain=0:8.2, samples=80]
    (\x, {3.2*exp(-0.42*\x)});
  \node[acc, anchor=south west, font=\footnotesize] at (3.6,1.25) {\texttt{slow decay, large discount}};
  % faster decay for smaller gamma
  \draw[red, very thick] plot[domain=0:8.2, samples=80]
    (\x, {3.2*exp(-0.92*\x)});
  \node[red, anchor=south west, font=\footnotesize] at (4.5,0.85) {\texttt{fast decay, small discount}};
  % tolerance line
  \draw[black, thick, dashed] (0,0.3) -- (8.2,0.3);
  \node[black, anchor=south east, font=\footnotesize] at (8.2,0.32) {\texttt{tolerance}};
\end{tikzpicture}
$$

## Convergence as a contraction

Both algorithms converge for the same reason: the Bellman operator is a
**contraction** in the max norm, so iterating it is a Banach fixed-point iteration
that converges geometrically to the unique fixed point. Define the optimality
operator $\mathcal{T}$ acting on a value function $V$ by

$$
\parens{\mathcal{T}V}(s) = \max_{a}\brackets{ R(s,a) + \gamma\sum_{s'} P\parens{s'\mid s,a}\, V(s') }.
$$

> **Theorem ($\gamma$-contraction).** $\mathcal{T}$ is a $\gamma$-contraction in
> the max norm $\norm{V} = \max_s \abs{V(s)}$: for any $U,V$,
> $$
> \norm{\mathcal{T}U - \mathcal{T}V} \le \gamma\, \norm{U - V}.
> $$
> By the Banach fixed-point theorem it has a unique fixed point, $V^{\star}$, and
> the iterates $V_{k+1} = \mathcal{T}V_k$ converge to it from any start, with
> $\norm{V_k - V^{\star}} \le \gamma^{k}\,\norm{V_0 - V^{\star}}$.

> **Proof.** Fix a state $s$ and let $a^\ast$ attain the max for $\mathcal{T}U(s)$.
> Then, using $\max_a f(a) - \max_a g(a) \le \max_a \parens{f(a)-g(a)}$,
> $$
> \parens{\mathcal{T}U}(s) - \parens{\mathcal{T}V}(s)
> \le \gamma \sum_{s'} P\parens{s'\mid s,a^\ast}\,\brackets{U(s') - V(s')}
> \le \gamma \sum_{s'} P\parens{s'\mid s,a^\ast}\,\norm{U - V} = \gamma\,\norm{U-V},
> $$
> since $\sum_{s'} P\parens{s'\mid s,a^\ast} = 1$. The symmetric argument bounds
> $\parens{\mathcal{T}V}(s) - \parens{\mathcal{T}U}(s)$ identically, so
> $\abs{\parens{\mathcal{T}U}(s) - \parens{\mathcal{T}V}(s)} \le \gamma\norm{U-V}$.
> Taking the max over $s$ gives the contraction. The fixed-point and geometric-rate
> claims are the Banach theorem applied to the complete metric space
> $\parens{\mathbb{R}^{\abs{\mathcal{S}}}, \norm{\cdot}}$. $\qed$

The discount factor is doing double duty: it makes the return finite _and_ it is
exactly the contraction modulus that guarantees the algorithms converge. As
$\gamma \to 1$ the contraction weakens, convergence slows, and planning over a long
horizon becomes harder, the geometric counterpart of the discounting trade-off in
the table above.

## Policy iteration versus value iteration

The same idea, alternating evaluation and improvement, admits a spectrum of
schedules collectively called **generalized policy iteration**. Policy iteration
evaluates fully before improving; value iteration improves after a single
evaluation sweep; the general scheme interleaves partial amounts of each.

| Property | Policy iteration | Value iteration | Generalized PI |
| --- | --- | --- | --- |
| Evaluation per round | to convergence | one sweep | partial, any amount |
| Improvement | greedy, after full eval | folded into the $\max$ backup | greedy, interleaved |
| Backup operator | Bellman expectation, then $\max$ | Bellman optimality $\mathcal{T}$ | mixture |
| Cost per round | high (inner loop) | low (one sweep) | tunable |
| Rounds to converge | few | more | between |
| Fixed point | $\parens{V^{\star},\pi^{\star}}$ | $\parens{V^{\star},\pi^{\star}}$ | $\parens{V^{\star},\pi^{\star}}$ |

> **Definition (Generalized policy iteration).** Any scheme that lets evaluation
> and improvement interact, each pulling the value and the policy toward mutual
> consistency, without insisting either run to completion before the other. Almost
> every reinforcement-learning method is an instance.

The two processes are simultaneously cooperative and competitive: improvement makes
the value stale by changing the policy, evaluation corrects the value, and the
joint fixed point, where the policy is greedy in its own value, is precisely the
Bellman optimality equation, hence $\pi^\star$.

## Where the model breaks down

Dynamic programming is exact, but it needs two things that vanish at scale: the model $(P,R)$ and a value table with one entry per state. Both fail the moment the state space is large, and the failures are what the rest of this module — and the standalone [reinforcement-learning subject](/reinforcement-learning/foundations/what-is-reinforcement-learning) — exist to fix.

**The model is usually unknown.** A robot does not know its transition kernel; a game-playing agent is not handed the rules as equations. When $(P,R)$ is unavailable, the Bellman backups above cannot be computed, and the agent must _sample_ transitions instead. Replacing the expectation $\sum_{s'} P(s'\mid s,a)\,V(s')$ with an average over sampled successors carries dynamic programming into [Monte Carlo and temporal-difference learning](/deep-learning/reinforcement-learning/model-free-prediction-and-control), the subject of the next lesson.

**The table does not fit.** A tabular $V(s)$ needs one number per state; backgammon has $10^{20}$ states and Go has $10^{170}$, so no table can hold them and no sweep can visit them all. The fix is **function approximation**: replace the table with a parameterized $V_\theta(s)$ or $Q_\theta(s,a)$ — a neural network — and learn $\theta$ from samples. That single substitution is what makes the subject "deep" reinforcement learning, and it is where the [deep Q-network](/deep-learning/reinforcement-learning/deep-q-networks) lesson picks up.

**The contraction guarantee is fragile under approximation.** The clean $\gamma$-contraction proof above assumes exact backups on a table. Combine it with function approximation and off-policy sampling and the guarantee can break — the value estimates can diverge. This is the **deadly triad** (function approximation, bootstrapping, off-policy training), and much of modern deep RL is engineering around it. Sutton and Barto's text treats it at length; this module meets it concretely when DQN's target network and replay buffer appear, both of which exist precisely to keep the approximate backup stable.[^gf-paradigm]

In short, this lesson is the exact, small-state ideal, and everything downstream is what survives when the model disappears and the table is replaced by a network. The Bellman equations do not change; only how their expectations are computed and stored does.

## Takeaways

- Reinforcement learning is interaction-driven: an agent maps states to actions and
  receives an **evaluative** reward, maximizing the discounted **return**
  $G_t = \sum_{k\ge 0}\gamma^k R_{t+k+1}$ rather than any immediate signal.
- The **Markov decision process** $\parens{\mathcal{S},\mathcal{A},P,R,\gamma}$ is
  the formal object; the **Markov property** lets the present state summarize the
  past, and $\gamma$ sets the effective horizon $1/\parens{1-\gamma}$.
- **Value functions** rank behaviour: $V^\pi(s)$ scores a state, $Q^\pi(s,a)$ a
  state-action pair, and they satisfy the **Bellman expectation equations**, a
  linear self-consistency on the value of a fixed policy.
- The **optimal** value functions satisfy the **Bellman optimality equations**
  (a $\max$ over actions), and any policy **greedy** w.r.t. $Q^\star$ is optimal,
  which is why model-free methods target $Q^\star$.
- With a known model, **policy iteration** and **value iteration** compute
  $V^\star$ exactly; both converge because the Bellman operator is a
  **$\gamma$-contraction** in the max norm, giving the geometric rate
  $\norm{V_k - V^\star} \le \gamma^k\norm{V_0 - V^\star}$.
- The unifying picture is **generalized policy iteration**: evaluation and
  improvement drive the value and policy to the mutually consistent fixed point
  $\parens{V^\star,\pi^\star}$. The same loop, with sampled experience replacing the
  model, becomes Monte Carlo and temporal-difference learning; the sampling and
  convergence intuitions connect to
  [Monte Carlo methods](/deep-learning/probabilistic-methods/monte-carlo-and-mcmc)
  and to the fixed-point geometry of
  [the optimization landscape](/deep-learning/optimization/the-optimization-landscape).

[^gf-paradigm]: **Goodfellow**, _Deep Learning_, Ch. 1 — reinforcement learning as a paradigm distinct from supervised and unsupervised learning: an agent learns from an evaluative reward signal rather than labelled or unlabelled data.