Markov Decision Processes

Reinforcement learning frames decision-making as a loop: at every discrete timestep $t$, the agent observes a state $s_t$, picks an action $a_t$, and the environment replies with a reward $r_t$ and a new state $s_{t+1}$. Repeat.

No supervised labels. No explicit model to invert. The only training signal is the scalar reward stream. This stripped-down interface is surprisingly expressive: it subsumes chess, robot locomotion, protein-folding search, and ad-auction bidding under one formalism.

The key design choice is the reward function $r: \mathcal{S} \times \mathcal{A} \to \mathbb{R}$. Get it wrong and your agent will find loopholes you didn't anticipate — an insight sometimes called the specification problem.

The four signals that define every MDP interaction.

A Markov Decision Process (MDP) is the tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ where $P(s' \mid s, a)$ is the transition kernel. The defining assumption:

$P(s_{t+1} = s' \mid s_t, a_t, s_{t-1}, a_{t-1}, \ldots) \;=\; P(s_{t+1} = s' \mid s_t, a_t).$

The future is independent of the past given the present. This is the Markov property. It says the state $s_t$ is a sufficient statistic for the agent's history — you can throw away every previous observation without losing anything.

In practice, raw sensory data (pixels, partial observations) often violates the Markov property. The fix: augment the state with history, use recurrent networks, or switch to the POMDP framework. But MDPs are the foundation everything else builds on.

A policy $\pi(a \mid s)$ is a probability distribution over actions given the current state. Deterministic policies write $\pi(s) = a$. The agent's goal is to find a policy that maximises the expected return — the sum of future rewards.

Because infinite horizons make raw sums diverge, we introduce a discount factor $\gamma \in [0, 1)$:

$G_t \;=\; r_t + \gamma\, r_{t+1} + \gamma^2 r_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k}.$

$\gamma$ close to 1 values the future nearly as much as the present (far-sighted). $\gamma$ close to 0 is myopic — only the immediate reward matters. The geometric series guarantees $G_t \le r_{\max} / (1 - \gamma)$ whenever rewards are bounded, keeping the math finite.

The state-value function of policy $\pi$ is the expected return starting from state $s$:

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

Think of $V^\pi(s)$ as asking: "if I follow $\pi$ forever starting from $s$, how much reward do I expect to accumulate?" High $V^\pi$ means the state is a good position under $\pi$.

Common confusion: $V^\pi$ depends on the policy. Two agents in the same environment can have wildly different value functions if they behave differently. The optimal value $V^\star(s) = \max_\pi V^\pi(s)$ is the ceiling that the best possible policy achieves.

The action-value function answers a more granular question: "how much return do I expect if I take action $a$ in state $s$ right now, then follow $\pi$ thereafter?"

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

The relationship between $Q$ and $V$ is immediate:

$V^\pi(s) \;=\; \sum_a \pi(a \mid s)\, Q^\pi(s, a).$

This identity is important: if you have $Q^\pi$, you can recover $V^\pi$ by averaging over the policy. Conversely, to improve $\pi$, look for states where some action $a'$ has $Q^\pi(s, a') > V^\pi(s)$ — taking $a'$ in $s$ beats following $\pi$. That observation drives policy improvement.

The Bellman equations are the central recursion of RL. They express "now" in terms of "one step later." For the state-value function:

$V^\pi(s) \;=\; \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a)\!\left[R(s, a, s') + \gamma\, V^\pi(s')\right].$

Unpacking: the agent averages over actions (using $\pi$), then over next states (using $P$), collecting the immediate reward $R$ and the discounted future value $\gamma V^\pi(s')$.

This is a linear system in $\{V^\pi(s)\}_{s \in \mathcal{S}}$. For small finite MDPs you can solve it directly via matrix inversion. For large spaces you need approximation — but the equation stays the same; only the solver changes.

The same one-step look-ahead applies to action values:

$Q^\pi(s, a) \;=\; \sum_{s'} P(s' \mid s, a)\!\left[R(s, a, s') + \gamma \sum_{a'} \pi(a' \mid s')\, Q^\pi(s', a')\right].$

The inner sum $\sum_{a'} \pi(a' \mid s') Q^\pi(s', a')$ is just $V^\pi(s')$, so this collapses to $Q^\pi(s, a) = \sum_{s'} P[R + \gamma V^\pi(s')]$ — consistent with the $V/Q$ identity above.

Why prefer $Q$ over $V$? Because with $Q$, choosing the best action requires no model: $\pi^\star(s) = \arg\max_a Q^\star(s, a)$. With only $V$, you'd need to query $P$ to evaluate each action — an expensive or impossible step when the model is unknown.

Consider a 2×2 grid where an agent must reach a goal square.

Stochastic transitions (the 0.8/0.1/0.1 split) are realistic: motors slip, networks drop packets, opponents randomize. The per-step penalty $-0.01$ discourages dawdling even with $\gamma$ near 1. The tension between exploration and exploitation emerges naturally: you must visit enough cells to learn $P$ before you can plan well.

The Bellman equations define what we want; they don't yet say how to compute it.

Three families of algorithms solve MDPs:

• Dynamic programming (policy iteration, value iteration): exact, requires full knowledge of $P$ and $R$, scales to moderate state spaces.
• Monte Carlo methods: sample complete episodes, average returns — no model needed, high variance.
• Temporal-difference learning (Q-learning, SARSA): bootstrap from next-step estimates, update after each transition — the modern workhorse.

All three are grounded in the same Bellman equations. The differences are in how they estimate the right-hand side — from the true model, from full returns, or from one-step bootstrapped estimates. The upcoming lessons cover each family in depth.