Markov Decision Processes

An MDP is the rulebook for learning by trial and error: state, action, reward, next state, repeated so the agent can chase long term return.

One loop from state through action to reward and next state feeds a return of 2.62 at discount 0.9

Why Does This Exist?

You cannot train sequential choices without writing down the rules first. What states exist, which moves are legal, what the world does next, and what counts as success. Without that shared model every algorithm means something slightly different by reward or value.

The Markov decision process gives you that contract in five parts. It also names the delay problem directly: a move that looks fine now can cost you ten steps later, so the objective sums rewards far into the future with discounting. This page defines the five parts and works one return by hand. For the values built on top see value functions, for the recursion see bellman equations, and for the mapping from states to moves see policy.

You need one idea first. Expectation averages over randomness. Transitions and rewards vary, so returns and values are always averages over possible futures, not single fixed paths.

Think of It Like This

Delivering parcels across a small town

Your state is the corner you stand on. Your actions are turn left, turn right, or go straight. Each choice moves you to a new corner, sometimes with a traffic delay you did not choose. Each leg pays a small cost in minutes, and a delivered parcel pays a bonus.

You want the route with the best total over the whole shift, not the fastest single block. A shortcut that saves one minute now but strands you in a jam later loses. That total over time is the return, and your usual route is the policy.

Where the analogy stops: town maps stay fixed while many RL worlds change as you learn, and traffic randomness is mild compared with a truly stochastic transition model.

How It Actually Works

An MDP is the tuple $(S, A, T, R, \gamma)$ . Let $s$ be state, $a$ action, $s'$ next state, $R_t$ reward at time $t$ , and $\gamma$ in $[0, 1]$ the discount factor.

$S$ is the state space, every situation the agent can be in.
$A$ is the action space, every move it can take.
$T(s' \mid s, a)$ is the transition probability of landing in $s'$ from $s$ after $a$ .
$R(s, a, s')$ is the immediate reward for that triple.
$\gamma$ weights near rewards above far ones.

The Markov property says the future needs only the present:

$P(s_{t+1} \mid s_0, a_0, \ldots, s_t, a_t) = P(s_{t+1} \mid s_t, a_t) = T(s_{t+1} \mid s_t, a_t)$

History does not matter once you know $s_t$ . That is what keeps the math workable.

A policy $\pi(a \mid s)$ maps states to action chances. The return sums discounted rewards from time $t$ :

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$

The state value $V^\pi(s)$ is expected return from $s$ under $\pi$ , and $Q^\pi(s, a)$ fixes the first action too. Those expectations lead straight to the Bellman recursion covered in the linked page.

Worked example

Three steps, $\gamma = 0.9$ , rewards $R_1 = 1.0$ , $R_2 = 0.0$ , $R_3 = 2.0$ :

Step 1 contributes $1.0$ .
Step 2 contributes $0.9 \times 0.0 = 0.0$ .
Step 3 contributes $0.9^2 \times 2.0 = 0.81 \times 2.0 = 1.62$ .
Return $G_0 = 1.0 + 0.0 + 1.62 = 2.62$ .

Late reward still matters but less than immediate reward. That 2.62 is the number the diagram carries around the loop.

Code

The snippet adds the same discounted sum.

1def discounted_return(rewards: list[float], gamma: float = 0.9) -> float:2    """Sum rewards with compounding discount gamma."""3    total = 0.04    for t, r in enumerate(rewards):5        total += (gamma**t) * r6    return total7
8
9if __name__ == "__main__":10    print(round(discounted_return([1.0, 0.0, 2.0], gamma=0.9), 2))

1# -> expected output:22.62

Watch Out For

Tabulating every state until the table explodes

The symptom: value iteration works on a grid demo, then stalls on a real task with dozens of sensors. Twenty binary features already mean about one million states, and continuous sensors mean infinitely many. The code runs but never visits the same state twice.

The fix: keep the MDP framing and change the solver. Use function approximation that generalizes across states, and track sampled Bellman error instead of sweeping a table.

Paying for the proxy instead of the goal

The symptom: the agent scores high and behaves badly. A cleaning robot paid per area covered drives in circles, because the reward counts motion rather than dirt removed. Training curves look great while the real task fails.

The fix: rewrite the reward to match the outcome you want, then test on held out starts. When a proxy is all you have, cap its loopholes with penalties before scaling training.

The Quick Version

An MDP is $(S, A, T, R, \gamma)$ : states, actions, transition chances, rewards, and discount.
The Markov property says the next state needs only the current state and action, not the full history.
Return $G_t$ sums discounted future rewards, so near rewards weigh more than far ones.
Rewards 1.0, 0.0, and 2.0 at discount 0.9 give return 2.62, with the late 2.0 worth 1.62 today.
Values are expected returns, and Bellman equations turn them into one step backups.