15.4 Markov decision processes
A Markov decision process (MDP) has states \(s\), actions \(a\) available in each state, costs \(c_a(s)\), and transition matrices \(P_a\); future costs are discounted by \(\beta < 1\) per period. A policy chooses an action in each state; under a policy \(\sigma \) the discounted cost from each state is \(v_\sigma = (I - \beta P_\sigma )^{-1}c_\sigma \).
Theorem 15.4.1 (Bellman equation and value iteration). The optimal discounted cost \(v^*\) is the unique solution of \[ v(s) = \min _a\Bigl \{c_a(s) + \beta \sum _{s'}P_a(s, s')v(s')\Bigr \} , \] and a policy choosing a minimising action in each state is optimal. Value iteration \(v_{k + 1} = Tv_k\), with \(T\) the right-hand side, converges to \(v^*\) from any start, with \(\|v_k - v^*\|_\infty \leq \beta ^k\|v_0 - v^*\|_\infty \).
Proof. For any \(u\), \(v\) and each \(s\) and \(a\), \(|\beta \sum _{s'}P_a(s, s')(u(s') - v(s'))| \leq \beta \|u - v\|_\infty \), since the transition probabilities sum to \(1\); taking minima over \(a\) preserves the bound, so \(\|Tu - Tv\|_\infty \leq \beta \|u - v\|_\infty \). \(T\) is a contraction, and by Banach’s fixed-point theorem it has a unique fixed point, reached geometrically by iteration. That the fixed point is the optimal cost, and that a greedy policy attains it, is Bellman’s principle (Theorem 11.1.1) applied to the horizon \(k\) and letting \(k \to \infty \). □
Policy iteration (Howard, 1960) evaluates the current policy exactly, by solving the linear system for \(v_\sigma \), then improves it by choosing in each state the action minimising \(c_a(s) + \beta P_a(s, \cdot )v_\sigma \); it never gets worse and stops in finitely many steps, usually very few. The optimal costs are also the solution of an LP (maximise \(\sum _sv(s)\) subject to \(v(s) \leq c_a(s) + \beta P_a(s, \cdot )v\) for all \(s\), \(a\)), whose dual variables are discounted state–action frequencies.
Example 15.4.2. A machine is in condition \(0\) (good), \(1\), \(2\) or \(3\) (broken), with running costs \(0\), \(1000\), \(3000\), \(6000\) a period. If kept, it deteriorates by the transition matrix with rows \((0.7, 0.2, 0.1, 0)\), \((0, 0.6, 0.3, 0.1)\), \((0, 0, 0.5, 0.5)\), \((0, 0, 0, 1)\); it can instead be replaced at cost \(4000\), after which it behaves as new. With \(\beta = 0.9\), value iteration and policy iteration agree that the machine should be kept in conditions \(0\) and \(1\) and replaced in conditions \(2\) and \(3\) (Software 15.5.3): a control-limit policy, of the kind that is optimal whenever deterioration and costs are monotone.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.