Markov Decision Processes

A bandit 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.¹

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 S$ , the environment's representation handed to the agent;
the action $A_{t} \in A (S_{t})$ , the agent's choice, possibly restricted by the current state;
the reward $R_{t + 1} \in R \subset R$ , a single number the environment returns one step later, together with the next state $S_{t + 1}$ .

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

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.²

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.

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.

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.

The dynamics function

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

The symbol $≐$ marks a definition, not a derived identity. Because $p$ is a probability distribution over $(s^{'}, r)$ for each fixed $(s, a)$ , it normalizes:

s^{'} \in S \sum r \in R \sum p (s^{'}, r ∣ s, a) = 1, for all s \in S, a \in 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^{'} ∣ s, a) ≐ Pr {S_{t} = s^{'} ∣ S_{t - 1} = s, A_{t - 1} = a} = r \in R \sum p (s^{'}, r ∣ s, a),

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

r (s, a) ≐ E [R_{t} ∣ S_{t - 1} = s, A_{t - 1} = a] = r \in R \sum r s^{'} \in S \sum p (s^{'}, r ∣ s, a),

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

r (s, a, s^{'}) ≐ E [R_{t} ∣ S_{t - 1} = s, A_{t - 1} = a, S_{t} = s^{'}] = r \in R \sum r \frac{p ( s ^{'} , r ∣ s , a )}{p ( s ^{'} ∣ 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).

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^{'} ∣ s, a)

and expected reward. In this two-state example the agent chooses between a safe action and a risky one.

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 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.³

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.⁴

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} ≐ R_{t + 1} + R_{t + 2} + R_{t + 3} + \dots + R_{T} .

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

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} ≐ R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + \dots = k = 0 \sum \infty γ^{k} R_{t + k + 1},

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

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

The discount weight

γ^{k}

on the reward

k

steps ahead, for three discount rates. A small

γ

collapses the horizon to the next few steps; a large

γ

keeps distant rewards in view.

If $γ < 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} = k = 0 \sum \infty γ^{k} = \frac{1}{1 - γ},

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

$γ$	return of $X$ = $\frac{1}{1 - γ}$	return of $Y$ = $γ^{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 $γ = 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 $γ$ 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 $γ$ .

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.

G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + γ^{3} R_{t + 4} + \dots = R_{t + 1} + γ (R_{t + 2} + γ R_{t + 3} + γ^{2} R_{t + 4} + \dots) = R_{t + 1} + γ G_{t + 1} .

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.

The return recursion

G_{t} = R_{t + 1} + γ G_{t + 1}

. Peeling off the first reward leaves the rest of the stream, discounted by one factor of

γ

— the whole tail from step

t + 1

collapses into the single quantity

G_{t + 1}

It is the basis of the Bellman equations and of every bootstrapping method — dynamic programming, Monte Carlo, and temporal-difference learning all lean on it. We build the value functions 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.⁵

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.

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	$- γ^{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.

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.

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} ≐ k = t + 1 \sum T γ^{k - t - 1} R_{k},

allowing $T = \infty$ (continuing) or $γ = 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.⁶ A mobile robot collects soda cans, running on a rechargeable battery whose charge is either $high$ or $low$ , so $S = {high, low}$ . In each state it can $search$ for cans, $wait$ for someone to bring one, or (only when $low$ ) $recharge$ :

A (high) = {search, wait}, A (low) = {search, wait, recharge} .

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

$s$	$a$	$s^{'}$	$p (s^{'} ∣ s, a)$	$r (s, a, s^{'})$
$high$	$search$	$high$	$α$	$r_{s}$
$high$	$search$	$low$	$1 - α$	$r_{s}$
$low$	$search$	$high$	$1 - β$	$- 3$
$low$	$search$	$low$	$β$	$r_{s}$
$high$	$wait$	$high$	$1$	$r_{w}$
$low$	$wait$	$low$	$1$	$r_{w}$
$low$	$recharge$	$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 $α = 0.7$ (a search from $high$ usually keeps the charge high), $β = 0.4$ (a search from $low$ usually drains it), $r_{s} = 2$ , $r_{w} = 1$ , and $γ = 0.9$ . The expected reward of searching from $low$ is the rescue-weighted average

r (low, search) = β r_{s} + (1 - β) (- 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 $π$ : always $search$ when $high$ , always $recharge$ when $low$ . Its two Bellman equations are

v_{π} (high) v_{π} (low) = r_{s} + γ [α v_{π} (high) + (1 - α) v_{π} (low)], = 0 + γ v_{π} (high),

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

v_{π} (high) = 2 + 0.9 [0.7 v_{π} (high) + 0.3 (0.9 v_{π} (high))] = 2 + 0.9 (0.97) v_{π} (high),

so $v_{π} (high) (1 - 0.873) = 2$ , giving $v_{π} (high) = 2/0.127 = 15.75$ and $v_{π} (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.

The recycling robot as a two-state transition graph with the numbers

α = 0.7

β = 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.

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) converges to $v_{*} (high) = 15.75$ , $v_{*} (low) = 14.17$ — the very same values. The optimal action-values from $low$ are $q_{*} (low, search) = 12.6$ , $q_{*} (low, wait) = 13.8$ , $q_{*} (low, 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).⁷ 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.

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.

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.⁸ 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^{'}) = γ Φ (s^{'}) - Φ (s)$ , for any state potential $Φ$ , leaves the set of optimal policies unchanged.⁹ 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} \frac{1}{h} \sum_{t = 1}^{h} 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.¹⁰

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. ↩
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. ↩
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. ↩
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. ↩
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. ↩
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 $α, β$ , and its rewards specified as a table of $p (s^{'}, r ∣ s, a)$ and expected rewards. ↩
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. ↩
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. ↩
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^{'}) = γ Φ (s^{'}) - Φ (s)$ preserves the set of optimal policies for any potential $Φ$ . ↩
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. ↩