Markov Decision Processes

This builds on Making Decisions: Utility Theory, which set up expected utility, the MEU principle, and the value of information for a single decision. Real agents rarely decide once. They act, watch the stochastic result, and decide again — and because an intended move can slip off course, the agent needs not a plan but a policy: an action for every state it might land in.

Sequential decisions: the Markov decision process

An agent in the world acts, observes the result, and acts again. Because chance can knock it off course, it cannot commit to a fixed sequence of moves; it needs a rule that says what to do in every situation it might end up in. The framework for this is the Markov decision process. The canonical example is a $4\times 3$ gridworld.¹ The agent starts at $(1,1)$ and can try to move Up, Down, Left, Right. Two terminal squares give reward $+1$ (at $(4,3)$) and $-1$ (at $(4,2)$); one square, $(2,2)$, is a wall. Every other square gives a small reward $-0.04$, a mild incentive to finish quickly. Motion is stochastic: an action moves the agent in its intended direction with probability $0.8$, and at a right angle with probability $0.1$ each; bumping a wall leaves it in place.

Because outcomes are stochastic, a fixed action sequence is useless — an intended path can slip off course. The agent needs an action for every state it might land in. This bundle of formal parts is a Markov decision process.

A solution is not a plan but a policy $\pi$, a mapping from every state to an action, with $\pi (s)$ the recommended action in $s$. An optimal policy${\pi }^{\ast }$ is one whose expected utility is highest. Its shape depends delicately on $R(s)$: with the mild $-0.04$ penalty, the optimal policy in the $4\times 3$ world is conservative — from $(3,1)$ it takes the long way around rather than risk slipping into the $-1$ square. Make the step penalty harsher and the agent sprints for the exit and accepts the risk; make it positive and the agent avoids both exits forever.³

From rewards to the utility of a state

The utility of a policy is the expected utility of the state sequences it generates. To score a sequence, additivity plus a mild stationarity assumption leave essentially one coherent choice: discounted rewards,

where the discount factor $\gamma \in [0,1)$ trades present against future reward. Discounting also keeps the sum finite over an infinite horizon: with rewards bounded by $R_{\max }$, the geometric series gives ${\sum }_t{\gamma }^t{R}_{\max }=R_{\max }/(1-\gamma )$.⁴ With $\gamma =1$ the utility is undiscounted (additive), which is safe only when the agent is guaranteed to reach a terminal state — a proper policy.

Fixing $\gamma <1$, define $S_t$ as the (random) state at time $t$ under policy $\pi$. The expected utility of executing $\pi$ starting from $s$ is

and ${\pi }_s^{\ast }={\mathrm{argmax}}_{\pi }{U}^{\pi }(s)$ is the best policy from $s$. One consequence of infinite-horizon discounting: the optimal policy is independent of the starting state — if two runs ever meet at a state $c$, they have no reason to disagree about what to do from $c$ onward. So we drop the subscript and write one ${\pi }^{\ast }$.⁵ The true utility of a state is then the expected utility under the optimal policy, $U(s)=U^{{\pi }^{\ast }}(s)$: the long-run reward of being in $s$ and behaving optimally thereafter. This $U(s)$ is what lets an agent choose actions by one-step MEU,

Note the two different quantities: $R(s)$ is the immediate, short-term reward for being in $s$; $U(s)$ is the long-term total reward from $s$ onward. In the $4\times 3$ world the utilities are highest near the $+1$ exit and fall off with distance, because fewer steps of $-0.04$ stand between the agent and the exit.

The Bellman equation

The utilities are not independent numbers. Each ties to its neighbors through one recursive constraint: the utility of a state is its immediate reward plus the discounted expected utility of the next state, assuming the agent acts optimally.

For $(1,1)$ in the gridworld the equation expands over the four actions, each a weighted sum over the three squares its intended-and-slipped motions can reach; plugging in the utilities above shows Up is the best action. The Bellman equation is the fixed-point characterization of $U$, and both algorithms below are just different ways to solve it.

Value iteration

The $n$ Bellman equations in $n$ unknowns are nonlinear (the max is not linear), so we cannot use linear algebra. Instead, iterate: start with arbitrary utilities, compute the right-hand side, feed it back into the left, and repeat. Each such Bellman update

is applied to every state simultaneously. This is value iteration.⁷

Convergence. View the update as an operator $B$ on the whole utility vector, $U_{i+1}\leftarrow B{U}_i$, and measure distance with the max norm$\Vert U\Vert ={\max }_s|U(s)|$. The key fact is that $B$ is a contraction by factor $\gamma$:

A contraction has a unique fixed point and drives any two inputs closer on every application, so value iteration converges to the one solution of the Bellman equations whenever $\gamma <1$.⁸ Because the true utilities $U$ are that fixed point, $\Vert B{U}_i-U\Vert \le \gamma \Vert U_i-U\Vert$: the error shrinks by at least $\gamma$ each sweep, so convergence is exponential. The termination test $\delta <\epsilon (1-\gamma )/\gamma$ guarantees the returned utilities are within $\epsilon$ of the true ones. In practice the policy extracted by one-step lookahead becomes optimal well before the utilities themselves converge — the exact magnitudes stop mattering once one action clearly dominates.

Policy iteration

Value iteration converges on the utilities, then reads off a policy — but often the policy stops changing long before the utilities settle, since only the ordering of actions matters. Policy iteration exploits this by working on the policy directly, alternating two steps from an initial policy ${\pi }_0$:⁹

• Policy evaluation: given ${\pi }_i$, compute $U_i=U^{{\pi }_i}$, the utility of each state if ${\pi }_i$ were executed.
• Policy improvement: compute a new MEU policy ${\pi }_{i+1}$ by one-step lookahead on $U_i$.

The evaluation step is the reason this is cheap. With the policy fixed, the action in each state is determined, so the max vanishes and the Bellman equation becomes linear:

For $n$ states these are $n$ linear equations in $n$ unknowns, solvable exactly in $O(n^3)$ by standard linear algebra — or approximately, by a few simplified Bellman sweeps with the policy held fixed (modified policy iteration). The loop terminates when improvement changes nothing; the utilities are then a fixed point of the Bellman update, so the policy is optimal. Since there are finitely many policies and each round strictly improves, termination is guaranteed.

Value iteration and policy iteration are the same idea at different granularities: both alternate estimating utilities and improving the policy. Loosening the schedule — updating any subset of states, with either kind of update — gives asynchronous dynamic programming, which converges under mild conditions and lets an agent concentrate work on the states a good policy actually visits.

Partial observability: the belief-state MDP

MDPs assume the environment is fully observable — the agent always knows which state it is in. Drop that and you get a partially observable MDP (POMDP), with all the MDP elements plus a sensor model $P(e\mid s)$ giving the probability of observing evidence $e$ in state $s$. Now the agent cannot execute $\pi (s)$, because it does not know $s$.¹⁰

The fix is to act on what the agent does know: its belief state $b$, a probability distribution over the actual states. After doing action $a$ and observing $e$, the belief updates by filtering, $b^{\prime }=\text{Forward}(b,a,e)$. The fundamental result is that the optimal action depends only on the current belief state — so an optimal policy is a map ${\pi }^{\ast }(b)$ from beliefs to actions. This converts the POMDP into an ordinary MDP over the (continuous) belief-state space, with its own transition model $P(b^{\prime }\mid b,a)$ and reward $\rho (b)={\sum }_{s}b(s)R(s)$; solving that belief-MDP solves the original POMDP.¹¹ The difficulty is that the belief space is continuous and high-dimensional, so exact POMDP solving is very hard (PSPACE-hard); practical agents use approximate look-ahead search over dynamic decision networks.

Bandits, regret, and scalable MDP solvers

The classical picture in this lesson — a fixed, fully known model, solved offline to optimality by dynamic programming — is only the base of a large modern literature. Three strands extend it in directions the textbook treatment gestures at but does not develop.

The multi-armed bandit is the MDP stripped to a single state: $k$ actions (arms), each returning a reward from an unknown distribution, and the agent wants to maximize total reward over $T$ pulls. There is no transition dynamics, only the tension between exploiting the arm that has looked best so far and exploring arms whose value is still uncertain — the exploration/exploitation trade-off in its purest form. The right yardstick is regret, the shortfall against always pulling the best arm. Lai and Robbins (1985) proved that no strategy can do better than regret growing as $O(\log T)$, and that this bound is achievable.¹² The upper confidence bound rule UCB1 attains it by adding an exploration bonus to each arm's empirical mean, picking ${\mathrm{argmax}}_i{\hat{\mu }}_i+\sqrt{2\ln t/n_i}$ so that seldom-tried arms stay attractive until their estimates sharpen (Auer, Cesa-Bianchi, and Fischer, 2002).¹³ The Bayesian alternative, Thompson sampling, keeps a posterior over each arm's value and pulls in proportion to the posterior probability that the arm is best; it is decades old (Thompson, 1933) but its strong empirical and theoretical performance was only established recently.¹⁴ Bandits are the theory behind A/B testing, ad selection, and clinical-trial design, and are the natural setting in which VPI becomes a live, repeated decision rather than a one-shot calculation.

When the state space is astronomically large, value and policy iteration over an explicit table are hopeless, and the standard tool is sampling. Monte-Carlo tree search (MCTS) with the UCT rule — UCB applied to the tree of a sequential decision problem — estimates action values by rolling out random continuations and concentrating simulations on promising branches (Kocsis and Szepesvári, 2006).¹⁵ Combined with deep neural networks that supply value and policy priors, MCTS drives AlphaGo (Silver et al., 2016) and its successors, which solve enormous game-tree MDPs that no exact method could touch.¹⁶ The same model-based planning appears in AlphaZero and MuZero, where the transition model itself is learned, closing the loop back to reinforcement learning.

POMDP solving at scale has its own approximate methods. Exact belief-space value iteration is intractable, but point-based value iteration (Pineau, Gordon, and Thrun, 2003) keeps the piecewise-linear value function only at a sampled set of reachable belief points, and the online solver POMCP (Silver and Veness, 2010) runs Monte-Carlo tree search directly in belief space using particle filters. These turn the belief-MDP idea of this lesson from a theoretical reduction into agents that run on real robots.

The common thread is that every extension here keeps the MEU objective and the Bellman structure intact, and only changes how the intractable expectation or maximization is approximated — by confidence bounds, by sampling, or by learned function approximators.

The bridge to reinforcement learning

Everything above assumes the agent is handed the MDP — it knows $P(s^{\prime }\mid s,a)$ and $R(s)$ and merely computes an optimal policy. That is planning, not learning. The whole apparatus carries over verbatim to reinforcement learning, with one thing removed: the model.

The objects are identical — states, actions, a transition model, a reward, a discount, policies, the utility of a state, the Bellman equation. Value iteration and policy iteration reappear under the name dynamic programming, the model-based backbone of RL. What changes is only that the expectations ${\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)U(s^{\prime })$ can no longer be computed in closed form: without $P$, the agent must sample the transition by acting, and average the results over time. Monte-Carlo and temporal-difference methods are those same Bellman updates with the unknown expectation replaced by a sampled estimate. The MDP theory of this lesson is RL with a known model; every RL algorithm is a way of running these same updates while estimating $P$ and $R$ from experience.