Markov Decision Processes

A Markov Decision Process is a tuple

where $\mathcal{S}$ is the set of states, $\mathcal{A}$ is the set of actions, $P(s' \mid s, a)$ is the transition dynamics giving the probability of landing in state $s'$ after taking action $a$ in state $s$, $R(s, a, s')$ (or a simpler $R(s,a)$) is the expected immediate reward, and $\gamma \in [0, 1]$ is the discount factor. An agent interacts with this process over a sequence of discrete time steps $t = 0, 1, 2, \dots$: at each step it observes state $S_t$, selects action $A_t$, receives reward $R_{t+1}$, and transitions to $S_{t+1} \sim P(\cdot \mid S_t, A_t)$. The crucial structural assumption is the Markov property, already familiar as a precondition for this framework: $P(S_{t+1}, R_{t+1} \mid S_t, A_t, S_{t-1}, A_{t-1}, \dots) = P(S_{t+1}, R_{t+1} \mid S_t, A_t)$. The state is a sufficient statistic for the future — everything relevant about the history is compressed into $S_t$. This is not merely a simplifying convenience; it is what makes the value of a state well-defined independent of how the agent arrived there, which in turn is what allows recursive (dynamic programming) solutions rather than search over entire histories. A policy $\pi$ is a mapping from states to (distributions over) actions; it is the object an agent is ultimately trying to choose well, and it will be treated fully in Policies and Value Functions. Given a policy, the return $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$ aggregates future rewards, discounted by $\gamma$ — this quantity was introduced under Rewards and Returns and the MDP is precisely the generative model that produces the reward sequence being summed. The discount factor serves double duty: it encodes a preference for sooner reward over later reward, and — critically — it guarantees the return is a finite, well-defined random variable even in infinite-horizon tasks with bounded rewards, since $\sum_k \gamma^k R_{\max} = R_{\max}/(1-\gamma) < \infty$ for $\gamma < 1$.

The payoff of formalizing a problem as an MDP is that value functions become computable via recursion. Define the state-value function under policy $\pi$ as the expected return starting from $s$ and following $\pi$:

and the action-value function

Because the return can be unrolled one step, $G_t = R_{t+1} + \gamma G_{t+1}$, and because of the Markov property, $V^\pi$ satisfies the Bellman expectation equation:

An optimal policy $\pi^*$ achieves $V^{\pi^*}(s) \ge V^\pi(s)$ for every state $s$ and every policy $\pi$ simultaneously (a nontrivial existence fact, justified below). Its value function $V^* = V^{\pi^*}$ satisfies the Bellman optimality equation:

This equation is not a formula to evaluate directly — $V^*$ appears on both sides — but a fixed-point condition. Three classical dynamic-programming algorithms exploit it, assuming the model $(P, R)$ is fully known.

1. Iterative policy evaluation computes $V^\pi$ for a fixed policy by repeatedly applying the Bellman expectation equation as an update rule until it stabilizes.

2. Policy iteration alternates full policy evaluation with a greedy policy improvement step.

3. Value iteration collapses evaluation and improvement into a single sweep using the max directly. ```

# --- Iterative Policy Evaluation ---

# Input: MDP (S, A, P, R, gamma), policy pi, tolerance theta

# Output: V approximating V_pi initialize V(s) = 0 for all s in S repeat: delta = 0 for each s in S: v_old = V(s) V(s) = sum over a of pi(a|s) sum over s' of P(s'|s,a) (R(s,a,s') + gamma * V(s')) delta = max(delta, |v_old - V(s)|) until delta < theta return V ``` ```

# --- Policy Iteration ---

# Input: MDP (S, A, P, R, gamma)

# Output: optimal policy pi, optimal value V initialize pi(s) arbitrarily for all s in S initialize V(s) = 0 for all s in S loop:

# 1. Policy evaluation: compute V ~= V_pi (as above, using current pi) V = PolicyEvaluation(pi, V)

# 2. Policy improvement policy_stable = true for each s in S: old_action = pi(s) pi(s) = argmax over a of sum over s' of P(s'|s,a) (R(s,a,s') + gamma V(s')) if old_action != pi(s): policy_stable = false if policy_stable: return pi, V ``` ```

# --- Value Iteration ---

# Input: MDP (S, A, P, R, gamma), tolerance theta

# Output: optimal value V, optimal (greedy) policy pi initialize V(s) = 0 for all s in S repeat: delta = 0 for each s in S: v_old = V(s) V(s) = max over a of sum over s' of P(s'|s,a) (R(s,a,s') + gamma V(s')) delta = max(delta, |v_old - V(s)|) until delta < theta

# Extract greedy policy for each s in S: pi(s) = argmax over a of sum over s' of P(s'|s,a) (R(s,a,s') + gamma V(s')) return V, pi ```

Complexity. Let $n = |\mathcal{S}|$ and $m = |\mathcal{A}|$. Each Bellman backup at a single state — computing the sum or max over actions and successor states — costs $O(m n)$ time in the worst case (dense transition matrices), or $O(m b)$ if each state has at most $b$ possible successors under any action ("branching factor"). One full sweep over all states therefore costs $O(n^2 m)$ (dense) or $O(n m b)$ (sparse). Memory is $O(n)$ for the value table plus $O(n^2 m)$ to store $P$ explicitly, or less if the model is given as a generative simulator rather than a table.

• Policy evaluation to tolerance $\theta$ takes $O\left(\frac{\log(1/\theta)}{\log(1/\gamma)}\right)$ sweeps in the worst case (derived below), each $O(n^2 m)$, so total $O\left(n^2 m \cdot \frac{\log(1/\theta)}{\log(1/\gamma)}\right)$.
• Policy iteration performs at most $m^n$ possible deterministic policies in principle, but in practice terminates after a small number of improvement steps; each step requires one policy evaluation. A classical (non-trivial) result shows policy iteration terminates in a number of iterations that is polynomial in $n$, $m$, and $1/(1-\gamma)$ for a fixed discount, and always terminates finitely because the policy strictly improves at every non-terminal step and there are finitely many deterministic policies.
• Value iteration requires no inner evaluation loop; each outer sweep is $O(n^2 m)$, and the number of sweeps to reach tolerance $\theta$ is again $O\left(\frac{\log(1/\theta)}{\log(1/\gamma)}\right)$.

Correctness — the contraction argument. Define the Bellman optimality operator $T$ acting on any value function $V : \mathcal{S} \to \mathbb{R}$ by

Claim: $T$ is a contraction in the max-norm $\|V\|_\infty = \max_s |V(s)|$, with contraction factor $\gamma$:

Proof sketch. Fix $s$. Let $a^*$ be the maximizing action for $TV_1(s)$. Then

using that $P(\cdot \mid s, a^*)$ is a probability distribution so the weighted average is bounded by the max, and reward terms cancel since both use the same $R(s,a^*,s')$. By symmetry, swapping $V_1, V_2$, we get $|(TV_1)(s) - (TV_2)(s)| \le \gamma\|V_1-V_2\|_\infty$ for every $s$, hence the same bound in max-norm. $\blacksquare$ Since $\gamma < 1$, the Banach fixed-point theorem guarantees $T$ has a unique fixed point $V^*$, and iterating $V_{k+1} = TV_k$ from any starting $V_0$ converges to it geometrically: $\|V_k - V^*\|_\infty \le \gamma^k \|V_0 - V^*\|_\infty$. This is exactly what value iteration does, which is why it converges regardless of initialization, and why the number of sweeps to reach error $\theta$ scales as $\log(1/\theta) / \log(1/\gamma)$. The same contraction argument (with $\max_a$ replaced by $\sum_a \pi(a\mid s)$) shows the Bellman expectation operator $T^\pi$ is also a $\gamma$-contraction, so iterative policy evaluation converges to $V^\pi$ for the same reason.

Correctness of policy improvement. The policy improvement theorem states: if $\pi'(s) = \arg\max_a Q^\pi(s,a)$ for all $s$, then $V^{\pi'}(s) \ge V^\pi(s)$ for all $s$, with strict inequality somewhere unless $\pi$ is already optimal. The proof unrolls the inequality $V^\pi(s) \le Q^\pi(s,\pi'(s))$ repeatedly, substituting the Bellman equation at each step, which shows the return under $\pi'$ dominates term by term. Because there are only finitely many deterministic policies ($m^n$ of them) and each improvement step either strictly improves some state's value or leaves the policy unchanged (signaling optimality reached), policy iteration must terminate at the true optimum in finitely many steps — it cannot cycle.

Tradeoffs. Value iteration needs no nested evaluation loop but its single-sweep updates converge only asymptotically to $V^*$; you must choose a tolerance $\theta$. Policy iteration converges in exact, finitely many outer steps but each step's inner evaluation is itself an iterative (or, if you solve the linear system directly, an $O(n^3)$-cost) computation. Both require the full model $(P,R)$ — this is dynamic programming, not learning from samples, and it scales poorly when $n$ is astronomically large (e.g. Go's $\sim 10^{170}$ states), which is precisely the gap that model-free reinforcement learning and function approximation are built to close.

Consider a tiny robot-navigation MDP with three states $\{s_1, s_2, s_3\}$, where $s_3$ is a terminal goal state (self-absorbing, reward 0 thereafter). Two actions: Wait (stay put, small cost) and Move (advance toward the goal, but may slip). Discount $\gamma = 0.9$.

Initialize $V_0(s_1) = V_0(s_2) = V_0(s_3) = 0$. Run value-iteration sweeps:

Sweep 1.

Sweep 2.

Sweep 3 (values continue climbing, differences shrinking by roughly a factor bounded by $\gamma = 0.9$ each sweep):

Continuing until $\delta < \theta = 0.01$ yields approximately:

Extracting the greedy policy: at $s_1$, Move has higher backed-up value than Wait once $V(s_2)$ is large enough (this flips after sweep 1, exactly when the chance of reaching the high-value $s_2$ outweighs the wasted step) — so $\pi^*(s_1) = \text{Move}$. At $s_2$, Move is optimal from the very first sweep since the 0.9 chance of the +10 terminal reward dominates. This matches intuition: always push toward the goal, never wait, because waiting only accrues cost with no chance of progress. The example also illustrates why value iteration's early sweeps can recommend the wrong action (at sweep 1, $s_1$ was a tie) before enough backed-up information propagates from the reward source — a concrete instance of the $\gamma^k$ convergence bound in action.

MDPs underlie the control loops of robotics research, where a robot's joint angles, velocities, and sensor readings form the state and torque commands the actions. Recommendation systems at scale — deciding which content to show a user next — are frequently modeled as MDPs to account for the long-term effect of a recommendation on future engagement, not just immediate clicks. Inventory management and supply-chain optimization use finite or infinite-horizon MDPs solved by dynamic programming or approximate variants when the state space is large. Operations research applications such as elevator scheduling, network routing, and revenue management were classical MDP successes well before deep learning existed. In modern AI, the MDP formalism (or its extension, the POMDP, for partial observability) is the object every reinforcement learning algorithm is implicitly trying to solve — including the algorithms used to fine-tune large language models via reward signals, where the "state" is the generated text so far and the "action" is the next token. Anywhere a system must choose actions sequentially under uncertainty, balancing immediate and future consequences, an MDP is the formal skeleton underneath the engineering solution.

Ask the tutor: How does the Bellman equation change when the reward depends only on $(s,a)$ instead of $(s,a,s')$, and why does it not affect the contraction argument?