---
title: Markov Decision Processes
module: Foundations
moduleNumber: 1
lessonNumber: 5
order: 105
summary: >
  A Markov decision process is the formal interface between an agent and its
  environment: at each step the agent reads a state, chooses an action, and
  receives a reward and a next state. We fix that loop, the dynamics function
  that governs it, and the Markov property that makes the state sufficient; then
  turn goals into a scalar reward and rewards into a discounted return, with one
  notation that covers both episodic and continuing tasks.
topics: [Foundations]
sources:
  - book: Sutton & Barto
    ref: "Ch. 3 — Finite Markov Decision Processes; §3.1 The Agent–Environment Interface"
  - book: Sutton & Barto
    ref: "§3.2 Goals and Rewards; §3.3 Returns and Episodes"
  - book: Sutton & Barto
    ref: "§3.4 Unified Notation for Episodic and Continuing Tasks"
---

A [bandit](/reinforcement-learning/foundations/multi-armed-bandits) has one
state. You pull an arm, you collect a reward, and the next pull faces exactly the
same choice — nothing you did changed the situation. That is the assumption that
makes bandits easy and also the assumption that makes them a toy. Almost every
problem worth calling reinforcement learning breaks it: the move you make now
alters the board you face next, so a good action is not the one that pays most
immediately but the one that steers you toward states from which more reward is
reachable. The **Markov decision process** (MDP) is the formalism that adds this
missing piece — a **state** that the agent's actions can change — and it is the
frame for the rest of the subject.[^sb-mdp]

## The agent–environment interface

Split the world in two. Everything the learner controls and does its learning
inside is the **agent**; everything outside, which it can only influence through
its actions, is the **environment**. They meet at an interface of three signals,
exchanged at each of a sequence of discrete time steps $t = 0, 1, 2, 3, \dots$:

- the **state** $S_t \in \mathcal{S}$, the environment's representation handed to
  the agent;
- the **action** $A_t \in \mathcal{A}(S_t)$, the agent's choice, possibly
  restricted by the current state;
- the **reward** $R_{t+1} \in \mathcal{R} \subset \mathbb{R}$, a single number the
  environment returns one step later, together with the next state $S_{t+1}$.

$$
% caption: The agent–environment loop of a Markov decision process. At step $t$
% the agent reads state $S_t$ and emits action $A_t$; the environment replies with
% reward $R_{t+1}$ and next state $S_{t+1}$, which become the agent's input at
% step $t+1$.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=30mm, minimum height=12mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, draw=acc, text=acc, thick] (ag) at (0,1.8) {agent};
  \node[box] (env) at (0,-1.8) {environment};
  % action: agent -> environment (right side, going down)
  \draw[->, acc, thick] (ag.east) -- ++(3.1,0) node[midway, above] {action}
    node[right, text=acc] {A(t)} |- (env.east);
  % state and reward: environment -> agent (left side, going up)
  \draw[->, thick] (env.west) -- ++(-3.1,0)
    node[midway, below, align=center] {state,\\reward}
    node[left] {S(t+1),\\R(t+1)} |- (ag.west);
\end{tikzpicture}
$$

Running the loop produces a **trajectory**, the alternating record of everything
that happened:

$$
S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \dots
$$

Two conventions are worth fixing now, because they thread through every
later equation. First, the reward for taking $A_t$ in $S_t$ is written
$R_{t+1}$, not $R_t$ — the subscript emphasizes that the reward and the next state
$S_{t+1}$ are _jointly_ determined by the environment, one step after the action.
Second, $S_t$, $A_t$, and $R_t$ are **random variables**: capital letters for the
random quantity, lower-case ($s$, $a$, $r$) for particular values they might take.

The split is not the physical boundary of a robot's body. The rule is control:
anything the agent cannot change at will is part of the environment. A robot's
motors and sensors, even the code that computes its reward, sit on the environment
side — the agent may _know_ how the reward is computed, but it cannot _alter_ that
computation, and that is what keeps the reward an honest yardstick.[^sb-boundary]

## The Markov property

For the loop to be tractable we need the state to be **sufficient**: the future
must depend on the past only through the present state. Formally, the probability
of the next state and reward may depend on $S_t$ and $A_t$, but not on anything
that came before.

> **Definition (Markov property).** A state $S_t$ has the Markov property if the
> distribution of $S_{t+1}$ and $R_{t+1}$ depends on the history only through
> $S_t$ and $A_t$: knowing earlier states and actions adds nothing once the
> current state is known. A state with this property is a sufficient statistic of
> the past for predicting the future.

This is best read as a restriction on the _state_, not on the process. If the
outcome genuinely depends on some earlier fact — a velocity, a card already
played, a counter — then that fact belongs _in_ the state. A chess position is
Markov because the arrangement of pieces (plus castling and en-passant flags) is
all you need to reason about the game; the sequence of moves that produced it is
irrelevant. We assume the Markov property throughout, and treat "design a good
state" as the work of making it hold.

For example, suppose a robot's state is the single
number "position on a track," and the reward depends on where it will be next.
Position alone is not Markov: from a given position the next one depends on
whether the robot is moving left or right, a fact the past encodes but the
present state omits. The remedy is to
_augment_ the state to the pair (position, velocity). With velocity included, the
next position is a function of the current state and action alone, and the Markov
property is restored. This is the standard move: whenever the future leaks
information from the past, fold that information into the state.

$$
% caption: State augmentation restores the Markov property. With position alone
% (left) the next position is ambiguous — the same cell can move either way — so
% the state is not sufficient. Adding velocity (right) makes the pair
% (position, velocity) determine the next position, and the process is Markov.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=8mm}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % LEFT: non-Markov
  \begin{scope}
    \node[st] (p) at (0,0) {x};
    \node[st] (pl) at (-1.6,-1.7) {x-1};
    \node[st] (pr) at (1.6,-1.7) {x+1};
    \draw[->, red] (p) -- (pl) node[midway, left, font=\scriptsize] {?};
    \draw[->, red] (p) -- (pr) node[midway, right, font=\scriptsize] {?};
    \node[red, anchor=north, font=\scriptsize] at (0,-2.5) {position alone: not Markov};
  \end{scope}
  % RIGHT: Markov
  \begin{scope}[xshift=6.4cm]
    \node[st] (q) at (0,0) {x,+1};
    \node[st] (qr) at (1.6,-1.7) {x+1};
    \draw[->, acc] (q) -- (qr) node[midway, right, font=\scriptsize] {sure};
    \node[st, black] (qx) at (-1.6,-1.7) {x-1};
    \draw[->, black, dashed] (q) -- (qx);
    \node[acc, anchor=north, font=\scriptsize] at (0,-2.5) {(position, velocity): Markov};
  \end{scope}
\end{tikzpicture}
$$

## The dynamics function

When the sets $\mathcal{S}$, $\mathcal{A}$, and $\mathcal{R}$ are all finite, the
process is a **finite MDP**, and its entire behavior is captured by one
four-argument function.

> **Definition (Dynamics).** The dynamics of a finite MDP are the function
> $p : \mathcal{S} \times \mathcal{R} \times \mathcal{S} \times \mathcal{A} \to
> [0,1]$ giving the probability of each next-state / reward pair,
> $$p(s', r \mid s, a) \doteq \Pr\{S_t = s', R_t = r \mid S_{t-1} = s, A_{t-1} = a\},$$
> for all $s', s \in \mathcal{S}$, $r \in \mathcal{R}$, $a \in \mathcal{A}(s)$.

The symbol $\doteq$ marks a _definition_, not a derived identity. Because $p$ is a
probability distribution over $(s', r)$ for each fixed $(s, a)$, it normalizes:

$$
\sum_{s' \in \mathcal{S}} \sum_{r \in \mathcal{R}} p(s', r \mid s, a) = 1,
\qquad \text{for all } s \in \mathcal{S},\ a \in \mathcal{A}(s).
$$

In plain terms, $p$ is a giant lookup table: for every situation you could be in and
every move you could make, it lists the chances of each thing that could happen next
and the reward that comes with it. Nothing about the environment is left out.

This one function _completely characterizes_ the environment. Everything else you
might want to know is a marginal or expectation of it. The **state-transition
probabilities** drop the reward argument,

$$
p(s' \mid s, a) \doteq \Pr\{S_t = s' \mid S_{t-1} = s, A_{t-1} = a\}
  = \sum_{r \in \mathcal{R}} p(s', r \mid s, a),
$$

the **expected reward** for a state–action pair sums out the next state,

$$
r(s, a) \doteq \mathbb{E}[R_t \mid S_{t-1} = s, A_{t-1} = a]
  = \sum_{r \in \mathcal{R}} r \sum_{s' \in \mathcal{S}} p(s', r \mid s, a),
$$

and the expected reward for a full $(s, a, s')$ triple divides by the transition
probability,

$$
r(s, a, s') \doteq \mathbb{E}[R_t \mid S_{t-1} = s, A_{t-1} = a, S_t = s']
  = \sum_{r \in \mathcal{R}} r\,\frac{p(s', r \mid s, a)}{p(s' \mid s, a)}.
$$

The four-argument $p$ is the master object; the rest are conveniences. The
framework is general. Time steps need not be seconds — they can
be arbitrary stages of decision making. Actions range from motor voltages to
"whether to go to graduate school." States range from raw sensor readings to
symbolic descriptions of a room. Any goal-directed learning-from-interaction
problem reduces to three signals crossing the interface: **actions** (the
choices), **states** (the basis for the choices), and **rewards** (the goal).

$$
% caption: A finite MDP as a transition graph. Large open circles are states,
% small solid circles are actions. Each arrow out of an action is one possible
% outcome, labelled with its probability $p(s'\mid s,a)$ and expected reward. In
% this two-state example the agent chooses between a safe action and a risky one.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=11mm},
  act/.style={circle, fill=black, inner sep=1.6pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st] (A) at (0,0) {A};
  \node[st] (B) at (6.5,0) {B};
  % action nodes off state A
  \node[act] (as) at (2.0,1.1) {};
  \node[act] (ar) at (2.0,-1.1) {};
  \draw[black] (A) -- (as) node[midway, above, sloped] {safe};
  \draw[black] (A) -- (ar) node[midway, below, sloped] {risky};
  % safe: A stays at A, reward 0
  \draw[->, acc] (as) to[out=90, in=140, looseness=1.3] node[above] {1.0, r=0} (A.110);
  % risky: to B with 0.7 reward +5, back to A with 0.3 reward -1
  \draw[->, acc] (ar) to[out=0, in=210] node[below, sloped] {0.7, r=+5} (B.240);
  \draw[->, black] (ar) to[out=180, in=250] node[below, sloped] {0.3, r=-1} (A.290);
  % action node off state B
  \node[act] (bs) at (4.5,1.1) {};
  \draw[black] (B) -- (bs) node[midway, above, sloped] {stay};
  \draw[->, acc] (bs) to[out=90, in=40, looseness=1.3] node[above] {1.0, r=+1} (B.70);
\end{tikzpicture}
$$

## Goals and the reward hypothesis

The agent's purpose enters through exactly one channel: the reward. At each step
the environment sends a number $R_t \in \mathbb{R}$, and the agent's entire goal is
to maximize the total it collects — not the immediate reward, but the accumulated
reward over the long run. Sutton and Barto elevate this to a hypothesis about all
purposive behavior.[^sb-reward]

> **Definition (Reward hypothesis).** That all of what we mean by goals and
> purposes can be well thought of as the maximization of the expected value of the
> cumulative sum of a received scalar signal (called reward).

Formalizing goals with a single scalar looks restrictive and turns out not to be.
A robot learning to walk gets reward proportional to its forward motion; an agent
escaping a maze gets $-1$ per step, so hurrying minimizes the penalty; a
game-player gets $+1$ for a win, $-1$ for a loss, $0$ otherwise. In each case the
agent that maximizes reward is the agent that does what we wanted.

### Reward is what, not how

The single most common way to break an RL system is to reward the _method_ instead
of the _goal_. A chess agent should be rewarded only for winning — never for
subgoals like capturing pieces or controlling the center. Reward a proxy and the
agent will find a way to maximize the proxy _without_ achieving the real aim: it
learns to grab material even at the cost of the game.[^sb-what]

> **Definition (Reward is what, not how).** The reward signal communicates _what_
> you want achieved, never _how_ to achieve it. Prior knowledge about method
> belongs in the initial policy or the value estimates, not in the reward — a
> reward for a subgoal invites the agent to satisfy the subgoal and skip the goal.

The reward's residence on the environment side of the boundary is what enforces
this: the agent cannot rewrite its own objective, so the objective stays a faithful
statement of the task.

## Returns

"Maximize cumulative reward" needs a precise target. If the rewards after step $t$
are $R_{t+1}, R_{t+2}, R_{t+3}, \dots$, the agent maximizes the **expected return**
$G_t$, some function of that reward sequence. The simplest choice is the plain sum
up to a final step $T$:

$$
G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \cdots + R_T.
$$

This is well defined whenever there is a natural final step — when the interaction
breaks into **episodes**.

> **Definition (Episodic task).** A task whose agent–environment interaction
> breaks naturally into subsequences called episodes — a play of a game, a trip
> through a maze — each ending in a special **terminal state**, after which the
> environment resets to a start state. The final step $T$ is itself a random
> variable, varying from episode to episode.

The alternative is a task that never resets. A process-control loop or a long-lived
robot goes on **continually, without limit**; these are **continuing tasks**, and
the plain-sum return is useless for them because $T = \infty$ would make the sum
run away. A reward of $+1$ every step already gives an infinite return, and
infinities cannot be compared or maximized.

## Discounting

The fix is to weight rewards by how soon they arrive, discounting the far future
geometrically. The agent chooses $A_t$ to maximize the **discounted return**:

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

where $\gamma \in [0, 1]$ is the **discount rate**. It sets the present value of a
future reward: a reward $k$ steps ahead is worth only $\gamma^{k-1}$ of what the
same reward would be worth now. The parameter tunes the agent's horizon.

- **$\gamma = 0$** — the agent is _myopic_, caring only about $R_{t+1}$; it maximizes
  each immediate reward in isolation.
- **$\gamma \to 1$** — the agent is _farsighted_, weighing distant rewards nearly as
  heavily as near ones.

$$
% caption: The discount weight $\gamma^k$ on the reward $k$ steps ahead, for three
% discount rates. A small $\gamma$ collapses the horizon to the next few steps; a
% large $\gamma$ keeps distant rewards in view.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (7.6,0) node[right, black] {k (steps ahead)};
  \draw[->, black] (0,0) -- (0,3.6) node[above, black] {weight};
  \foreach \k in {0,1,2,3,4,5,6} \draw[black] (\k+0.4,0.03) -- (\k+0.4,-0.03) node[below, black]{\k};
  \node[left, black] at (0,3.2) {1};
  \draw[black] (0,3.2) -- (7.4,3.2);
  % gamma = 0.5
  \foreach \k in {0,...,6} \fill[red] ({\k+0.4}, {3.2*(0.5)^\k}) circle (1.4pt);
  \draw[red, thick] (0.4,3.2) \foreach \k in {1,...,6} {-- ({\k+0.4},{3.2*(0.5)^\k})};
  \node[red, anchor=west] at (6.55, {3.2*(0.5)^6 + 0.28}) {gamma=0.5};
  % gamma = 0.9
  \foreach \k in {0,...,6} \fill[acc] ({\k+0.4}, {3.2*(0.9)^\k}) circle (1.4pt);
  \draw[acc, thick] (0.4,3.2) \foreach \k in {1,...,6} {-- ({\k+0.4},{3.2*(0.9)^\k})};
  \node[acc, anchor=west] at (6.55, {3.2*(0.9)^6}) {gamma=0.9};
\end{tikzpicture}
$$

If $\gamma < 1$ and the reward sequence is bounded, the infinite sum is _finite_.
The constant-reward case makes this concrete: if every $R_k$ equals $1$, then

$$
G_t = \sum_{k=0}^{\infty} \gamma^k = \frac{1}{1 - \gamma},
$$

the familiar geometric series. So discounting buys a well-defined objective for
continuing tasks at the cost of one extra parameter.

A worked comparison shows what the discount rate actually decides. Two reward
streams: stream $X$ pays $R = 1$ every step forever; stream $Y$ pays $0$ for the
first four steps, then $10$ once, then $0$ forever. Which does the agent prefer?
It depends entirely on $\gamma$.

| $\gamma$ | return of $X$ = $\tfrac{1}{1-\gamma}$ | return of $Y$ = $\gamma^{4}\cdot 10$ | preferred |
| --- | --- | --- | --- |
| $0.5$ | $2.0$ | $0.625$ | $X$ (near reward) |
| $0.9$ | $10.0$ | $6.56$ | $X$ |
| $0.99$ | $100.0$ | $9.61$ | $X$ |
| $0.5$, but $X$ pays $0.3$/step | $0.6$ | $0.625$ | $Y$ (delayed payoff) |

At $\gamma = 0.5$ the future is discounted so hard that a reward five steps away
is worth $0.5^4 = 0.0625$ of its face value, so the big-but-late payoff of $Y$
counts for little. Raising $\gamma$ toward $1$ lets the distant $10$ count for more, but a
steady stream of small rewards still wins here because it never stops. The last
row flips the comparison: shrink the steady reward and the delayed payoff wins.
The discount rate sets how the agent trades near reward
against far reward, and every value in the subject is computed relative to a
chosen $\gamma$.

### The recursive form

The return starting now is
the next reward plus the discounted return starting one step later, so the
infinite tail never has to be summed — it is deferred to the next step. Peeling off the
first term makes this exact; it is the most-used identity in reinforcement
learning.

$$
\begin{aligned}
G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots \\
    &= R_{t+1} + \gamma\bigl(R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots\bigr) \\
    &= R_{t+1} + \gamma\,G_{t+1}.
\end{aligned}
$$

The return from now is the immediate reward plus the discounted return from the
next step. This recursion holds for every $t < T$, and if we define $G_T = 0$ at
termination it holds there too.

$$
% caption: The return recursion $G_t = R_{t+1} + \gamma G_{t+1}$. Peeling off the
% first reward leaves the rest of the stream, discounted by one factor of $\gamma$
% — the whole tail from step $t+1$ collapses into the single quantity $G_{t+1}$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  rw/.style={draw, circle, minimum size=6.5mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[rw, draw=acc, text=acc] (r1) at (0,0) {R+1};
  \node[rw] (r2) at (1.7,0) {R+2};
  \node[rw] (r3) at (3.4,0) {R+3};
  \node[rw] (r4) at (5.1,0) {R+4};
  \node (dots) at (6.5,0) {. . .};
  % bracket over R+2 onward, drawn from plain line segments
  \draw[black] (1.25,0.55) -- (1.25,0.75) -- (6.3,0.75) -- (6.3,0.55);
  \node[anchor=south, font=\scriptsize, black] at (3.8,0.75) {this tail = G(t+1), times gamma};
  \node[acc, anchor=north, font=\scriptsize] at (0,-0.55) {kept as is};
  \node[anchor=north, font=\scriptsize] at (0,-1.05) {G(t) = R+1 + gamma . G(t+1)};
\end{tikzpicture}
$$
It is the basis of the Bellman equations and of
every bootstrapping method — [dynamic programming](/reinforcement-learning/tabular-methods/dynamic-programming),
[Monte Carlo](/reinforcement-learning/tabular-methods/monte-carlo-methods),
and [temporal-difference learning](/reinforcement-learning/tabular-methods/temporal-difference-learning)
all lean on it. We build the [value functions](/reinforcement-learning/foundations/value-functions-and-optimality)
that formalize "expected return from a state" in the next lesson; this recursion is
what makes them computable.

### Pole-balancing: episodic or continuing

The same task can be framed either way, and the choice of return shows how. In
**pole-balancing** a cart moves along a track and must keep a hinged pole upright;
failure is the pole tipping past a fixed angle or the cart leaving the track, after
which the pole resets.[^sb-pole]

$$
% caption: The pole-balancing task. A cart moves along a track to keep a hinged
% pole from falling past a fixed angle or running off either end of the track. As
% an episodic task, reward is $+1$ per step survived; as a continuing task, reward
% is $-1$ at failure and $0$ elsewhere. Either return is maximized by balancing as
% long as possible.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % track with end walls
  \draw[black, thick] (-3.2,0) -- (-2.2,0) -- (-2.2,0.35);
  \draw[black, thick] (3.2,0) -- (2.2,0) -- (2.2,0.35);
  \draw[black, thick] (-2.2,0) -- (2.2,0);
  % cart
  \draw[black, thick, fill=acc!8] (-0.6,0.05) rectangle (0.6,0.65);
  \fill[black] (-0.35,0.05) circle (2.2pt);
  \fill[black] (0.35,0.05) circle (2.2pt);
  % pole, leaning
  \draw[acc, very thick] (0,0.65) -- (0.85,3.0);
  \fill[acc] (0,0.65) circle (1.6pt);
  % failure-angle guide
  \draw[black, dashed] (0,0.65) -- (0,3.0);
  \draw[black] (0,2.15) ++(0,0) arc (90:70:1.5);
  \node[black, anchor=west] at (0.72,2.55) {angle};
  % motion arrows on cart
  \draw[->, black] (-0.9,0.35) -- (-1.35,0.35);
  \draw[->, black] (0.9,0.35) -- (1.35,0.35);
  \node[black, anchor=north] at (0,-0.25) {cart force};
\end{tikzpicture}
$$

Two framings, same behavior:

| Framing | Reward | Return | Goal it induces |
| --- | --- | --- | --- |
| Episodic | $+1$ per step, $0$ at failure | steps until failure | balance forever $\Rightarrow$ return $\to \infty$ |
| Continuing (discounted) | $-1$ at failure, $0$ elsewhere | $-\gamma^{K}$, $K$ steps to failure | push failure far off $\Rightarrow$ return $\to 0$ |

Both returns are maximized by keeping the pole up as long as possible. The episodic
framing counts successes; the continuing framing, with discounting, penalizes the
next failure less the further away it is pushed. The task is the same; only the
bookkeeping differs.

## Unified notation

Two return definitions — a finite sum for episodic tasks, an infinite discounted
sum for continuing ones — is one too many. A single trick collapses them: treat
**episode termination as entering an absorbing state**.

> **Definition (Absorbing state).** A special state that transitions only to
> itself and emits reward $0$ forever after. Routing every terminal state into an
> absorbing state turns a finite episode into an infinite reward sequence padded
> with zeros, so the episodic and continuing returns become one expression.

$$
% caption: The absorbing-state construction. An episode of three rewards ends at a
% terminal step; the solid square is the absorbing state, which loops to itself and
% emits reward 0 thereafter. Summing the first three rewards or the padded infinite
% tail gives the same return.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=8mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st] (s0) at (0,0) {S0};
  \node[st] (s1) at (2.2,0) {S1};
  \node[st] (s2) at (4.4,0) {S2};
  \node[draw, fill=black!12, minimum size=8mm] (sq) at (6.6,0) {};
  \draw[->, acc, thick] (s0) -- (s1) node[midway, above] {R=+1};
  \draw[->, acc, thick] (s1) -- (s2) node[midway, above] {R=+1};
  \draw[->, acc, thick] (s2) -- (sq) node[midway, above] {R=+1};
  % self-loop on absorbing state
  \draw[->, black] (sq) to[out=40, in=-40, looseness=6] node[right] {R=0} (sq);
\end{tikzpicture}
$$

Starting from $S_0$ the reward sequence is $+1, +1, +1, 0, 0, 0, \dots$; summing the
first $T = 3$ rewards or the whole infinite tail gives the same return, and this
stays true with discounting. So we write one return for both worlds,

$$
G_t \doteq \sum_{k=t+1}^{T} \gamma^{k-t-1} R_k,
$$

allowing $T = \infty$ (continuing) or $\gamma = 1$ (episodic, all episodes
terminate) — but not both at once. We also drop the explicit episode index: $S_t$
stands in for $S_{t,i}$, the state at step $t$ of episode $i$, because we almost
always reason about a single generic episode. With one dynamics function $p$, one
reward hypothesis, and one return, the finite MDP frames every problem in the
subject.

## Worked example: the recycling robot

A concrete finite MDP ties the pieces together.[^sb-robot] A mobile robot collects
soda cans, running on a rechargeable battery whose charge is either $\texttt{high}$
or $\texttt{low}$, so $\mathcal{S} = \{\texttt{high}, \texttt{low}\}$. In each
state it can $\texttt{search}$ for cans, $\texttt{wait}$ for someone to bring one,
or (only when $\texttt{low}$) $\texttt{recharge}$:

$$
\mathcal{A}(\texttt{high}) = \{\texttt{search}, \texttt{wait}\}, \qquad
\mathcal{A}(\texttt{low}) = \{\texttt{search}, \texttt{wait}, \texttt{recharge}\}.
$$

Searching collects more cans than waiting (expected rewards $r_{\text{s}} >
r_{\text{w}}$) but drains the battery, and if it drains while searching from
$\texttt{low}$ the robot must be rescued — a reward of $-3$. A search from
$\texttt{high}$ keeps the charge $\texttt{high}$ with probability $\alpha$; a search
from $\texttt{low}$ keeps it $\texttt{low}$ with probability $\beta$ and otherwise
depletes it. The full dynamics $p(s', r \mid s, a)$ is a small table:

| $s$ | $a$ | $s'$ | $p(s' \mid s, a)$ | $r(s, a, s')$ |
| --- | --- | --- | --- | --- |
| $\texttt{high}$ | $\texttt{search}$ | $\texttt{high}$ | $\alpha$ | $r_{\text{s}}$ |
| $\texttt{high}$ | $\texttt{search}$ | $\texttt{low}$ | $1 - \alpha$ | $r_{\text{s}}$ |
| $\texttt{low}$ | $\texttt{search}$ | $\texttt{high}$ | $1 - \beta$ | $-3$ |
| $\texttt{low}$ | $\texttt{search}$ | $\texttt{low}$ | $\beta$ | $r_{\text{s}}$ |
| $\texttt{high}$ | $\texttt{wait}$ | $\texttt{high}$ | $1$ | $r_{\text{w}}$ |
| $\texttt{low}$ | $\texttt{wait}$ | $\texttt{low}$ | $1$ | $r_{\text{w}}$ |
| $\texttt{low}$ | $\texttt{recharge}$ | $\texttt{high}$ | $1$ | $0$ |

Every row is a $(s, a, s')$ outcome with its probability and expected reward, and
the probabilities out of each state–action pair sum to $1$ — a complete, if tiny,
Markov decision process. This is the object the next lessons learn to _solve_:
what to search or wait or recharge from each charge level, so as to maximize the
discounted return.

### Solving the recycling robot with real numbers

Put numbers on it. Fix $\alpha = 0.7$ (a search from $\texttt{high}$ usually
keeps the charge high), $\beta = 0.4$ (a search from $\texttt{low}$ usually
drains it), $r_{\text{s}} = 2$, $r_{\text{w}} = 1$, and $\gamma = 0.9$. The
expected reward of searching from $\texttt{low}$ is the rescue-weighted average

$$
r(\texttt{low}, \texttt{search}) = \beta\,r_{\text{s}} + (1 - \beta)(-3)
  = 0.4(2) + 0.6(-3) = -1.0,
$$

so a search from a low battery loses reward _on average_ — the $-3$ rescue is
common enough to make it a bad bet. Now evaluate a sensible policy $\pi$: always
$\texttt{search}$ when $\texttt{high}$, always $\texttt{recharge}$ when
$\texttt{low}$. Its two Bellman equations are

$$
\begin{aligned}
v_\pi(\texttt{high}) &= r_{\text{s}} + \gamma\big[\alpha\,v_\pi(\texttt{high}) + (1-\alpha)\,v_\pi(\texttt{low})\big], \\
v_\pi(\texttt{low})  &= 0 + \gamma\,v_\pi(\texttt{high}),
\end{aligned}
$$

the second line because recharging moves deterministically to $\texttt{high}$
for reward $0$. Substituting the second into the first and using the numbers,

$$
v_\pi(\texttt{high}) = 2 + 0.9\big[0.7\,v_\pi(\texttt{high}) + 0.3(0.9\,v_\pi(\texttt{high}))\big]
  = 2 + 0.9(0.97)\,v_\pi(\texttt{high}),
$$

so $v_\pi(\texttt{high})(1 - 0.873) = 2$, giving $v_\pi(\texttt{high}) = 2/0.127 =
15.75$ and $v_\pi(\texttt{low}) = 0.9(15.75) = 14.17$. Check the first equation
directly: $2 + 0.9[0.7(15.75) + 0.3(14.17)] = 2 + 0.9(15.28) = 15.75$. It holds
exactly, which is the whole point of the Bellman equation — the two values are
not independent numbers but a pair determined jointly by one-step consistency.

$$
% caption: The recycling robot as a two-state transition graph with the numbers
% $\alpha=0.7$, $\beta=0.4$, $r_s=2$, $r_w=1$. Open circles are the battery
% states high and low; solid dots are actions. Each action arrow carries its
% probability and reward. Searching from low risks a rescue of reward -3.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=11mm},
  act/.style={circle, fill=black, inner sep=1.6pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st] (H) at (0,0) {high};
  \node[st] (L) at (7.0,0) {low};
  % high: search
  \node[act] (hs) at (2.4,1.4) {};
  \draw[black] (H) -- (hs) node[midway, above, sloped] {search};
  \draw[->, acc] (hs) to[out=100, in=150, looseness=1.4] node[above] {0.7, r=2} (H.120);
  \draw[->, acc] (hs) to[out=20, in=120] node[above, sloped] {0.3, r=2} (L.140);
  % low: recharge
  \node[act] (lr) at (4.6,-1.4) {};
  \draw[black] (L) -- (lr) node[midway, below, sloped] {recharge};
  \draw[->, acc] (lr) to[out=170, in=250] node[below, sloped] {1.0, r=0} (H.290);
  % low: search (risky)
  \node[act] (ls) at (7.0,-1.9) {};
  \draw[black] (L) -- (ls) node[midway, right] {search};
  \draw[->, red] (ls) to[out=200, in=310] node[below, sloped] {0.6, r=-3} (H.310);
  \draw[->, acc] (ls) to[out=-30, in=-80, looseness=1.6] node[right] {0.4, r=2} (L.315);
\end{tikzpicture}
$$

Is this policy the best one? Running the same recursion with a $\max$ over
actions instead of the fixed choice (value iteration, taken up in
[dynamic programming](/reinforcement-learning/tabular-methods/dynamic-programming))
converges to $v_\ast(\texttt{high}) = 15.75$, $v_\ast(\texttt{low}) = 14.17$ — the very
same values. The optimal action-values from $\texttt{low}$ are
$q_\ast(\texttt{low}, \texttt{search}) = 12.6$, $q_*(\texttt{low}, \texttt{wait}) =
13.8$, $q_*(\texttt{low}, \texttt{recharge}) = 14.2$, so recharging is best and
searching (expected reward $-1$) is worst. Our hand-picked policy was already
optimal for these numbers. That coincidence is the exception; the reason the next
several lessons exist is that reading the optimal policy off the equations is easy
only for a two-state toy.

## Partial observability, reward design, and average reward

The finite MDP assumes the agent sees a Markov state. Three extensions matter
enough in modern practice to name here, each relaxing one of the lesson's clean
assumptions.

**When the state is hidden.** Real agents often observe not the state $S_t$ but a
noisy, incomplete _observation_ $O_t$ — a camera frame, a sensor reading — from
which the true state must be inferred. This is a **partially observable MDP**
(POMDP), formalized by Kaelbling, Littman, and Cassandra (1998).[^pomdp] The
standard result is that a POMDP is again an MDP, but over a different state: the
**belief state**, a probability distribution over the underlying states, updated
by Bayes' rule as observations arrive. The belief is Markov even when the raw
observation is not, so all the theory of this lesson applies to it — at the cost
that the belief space is continuous even when the underlying MDP is finite. In
deep RL the same problem is met by feeding a _history_ of observations into a
recurrent network, letting it learn an approximate belief; this is why Atari
agents stack the last four frames rather than acting on a single image.

$$
% caption: A POMDP inserts an observation between the state and the agent. The
% true state $S_t$ is hidden; the agent sees only an observation $O_t$ drawn from
% it, and maintains a belief (a distribution over states) that it updates by Bayes'
% rule. The belief is Markov, so the MDP theory applies to it.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=22mm, minimum height=10mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, black] (s) at (0,0) {hidden state S(t)};
  \node[box] (o) at (3.8,0) {observation O(t)};
  \node[box, draw=acc, text=acc] (b) at (8.0,0) {belief over states};
  \draw[->, black, thick] (s) -- (o) node[midway, above, font=\scriptsize, text=black] {noisy};
  \draw[->, acc, thick] (o) -- (b) node[midway, above, font=\scriptsize, text=black] {Bayes update};
\end{tikzpicture}
$$

**Designing the reward is the hard part.** The lesson warns that rewarding a
subgoal invites the agent to satisfy the proxy and skip the goal. Modern systems
hit this constantly, under the name **reward hacking** or specification gaming: a
boat-racing agent trained by OpenAI (2016) learned to spin in circles collecting
respawning bonus targets rather than finish the race, scoring high while losing
every race.[^rewardhack] There is one principled tool for adding guidance without
changing the optimal policy: Ng, Harada, and Russell (1999) proved that a shaping
reward of the form $F(s, s') = \gamma\,\Phi(s') - \Phi(s)$, for any state
**potential** $\Phi$, leaves the set of optimal policies unchanged.[^shaping]
Such **potential-based shaping** can speed learning by making progress toward the
goal immediately rewarding, while the telescoping form guarantees the extra
reward sums to zero along any path back to the start, so it cannot be
farmed. This is the safe way to inject prior knowledge that the reward hypothesis
otherwise forbids.

**Continuing tasks without discounting.** Discounting is not the only way to make
an infinite return finite. For continuing tasks one can instead maximize the
**average reward per step**, $\lim_{h \to \infty} \tfrac{1}{h}\sum_{t=1}^{h}
\mathbb{E}[R_t]$, and measure a state's value by how much its returns exceed that
average (the _differential_ value). Sutton and Barto develop this setting later,
under function approximation, and Mahadevan (1996) surveyed the earlier
average-reward algorithms; it is the natural criterion when there is no principled
reason to discount and every step counts equally, as in a long-running server or
queueing system.[^avgreward]

[^sb-mdp]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 3 — Finite Markov Decision Processes: MDPs as the formalization of sequential decision making, where actions influence not just immediate rewards but subsequent states and, through them, future rewards.
[^sb-boundary]: **Sutton & Barto**, §3.1 — The Agent–Environment Interface: the boundary is the limit of the agent's absolute control, not the physical body; anything the agent cannot change arbitrarily, including the reward computation, is part of the environment.
[^sb-reward]: **Sutton & Barto**, §3.2 — Goals and Rewards: the reward hypothesis, that goals and purposes can be framed as maximizing the expected cumulative scalar reward, and the flexibility of scalar rewards across walking, maze-escape, and game-playing.
[^sb-what]: **Sutton & Barto**, §3.2 — Goals and Rewards: the reward signal communicates what to achieve, not how; rewarding subgoals (capturing pieces, controlling the center) lets the agent satisfy the proxy while missing the true objective.
[^sb-pole]: **Sutton & Barto**, §3.3 — Returns and Episodes, Example 3.4 (Pole-Balancing): the same balancing task framed episodically ($+1$ per step) or as a continuing discounted task ($-1$ at failure), both maximized by balancing as long as possible.
[^sb-robot]: **Sutton & Barto**, §3.1 — The Agent–Environment Interface, Example 3.3 (Recycling Robot): a two-state finite MDP with search / wait / recharge actions, its transition probabilities $\alpha, \beta$, and its rewards specified as a table of $p(s',r\mid s,a)$ and expected rewards.
[^pomdp]: **Kaelbling, L. P., Littman, M. L. & Cassandra, A. R. (1998)**, "Planning and acting in partially observable stochastic domains", _Artificial Intelligence_ 101(1–2), 99–134 — the POMDP framework and the reduction to a belief-state MDP, where the agent acts on a Bayes-updated probability distribution over hidden states.
[^rewardhack]: **Clark, J. & Amodei, D. (2016)**, "Faulty reward functions in the wild", OpenAI blog — the CoastRunners boat-racing agent that maximized a proxy score by looping through respawning targets instead of finishing the race, a widely-cited example of specification gaming / reward hacking.
[^shaping]: **Ng, A. Y., Harada, D. & Russell, S. (1999)**, "Policy invariance under reward transformations: theory and application to reward shaping", _Proceedings of the 16th International Conference on Machine Learning (ICML)_, 278–287 — the proof that potential-based shaping $F(s,s') = \gamma\Phi(s') - \Phi(s)$ preserves the set of optimal policies for any potential $\Phi$.
[^avgreward]: **Mahadevan, S. (1996)**, "Average reward reinforcement learning: foundations, algorithms, and empirical results", _Machine Learning_ 22(1–3), 159–195 — a survey of the average-reward optimality criterion and differential value functions as an alternative to discounting for continuing tasks.