Markov decision processes

Definition#

A finite MDP is a tuple $\mathcal{M} = (\mathcal{S}, \mathcal{A}, P, R, \gamma)$ where $\mathcal{S}$ and $\mathcal{A}$ are finite sets, $P : \mathcal{S} \times \mathcal{A} \to \Delta(\mathcal{S})$, $R : \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ is bounded, and $\gamma \in [0,1)$.

The Markov property is the statement $$ \Pr(s_{t+1} = s' \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots, s_0) = \Pr(s_{t+1} = s' \mid s_t, a_t) = P(s' \mid s_t, a_t) $$ so the conditional distribution of the next state is independent of everything before $s_t$ given $(s_t, a_t)$.

Value functions#

For a policy $\pi$: $$ V^\pi(s) = \mathbb{E}\pi!\left[ \sum{k=0}^{\infty} \gamma^k r_{t+k+1} \;\middle|\; s_t = s \right], \qquad Q^\pi(s,a) = \mathbb{E}_\pi!\left[ G_t \mid s_t = s, a_t = a \right] $$

$V^\pi$ is the state-value function and $Q^\pi$ the action-value function. They satisfy the Bellman expectation equations:

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

and the Bellman optimality equations:

$$ V^(s) = \max_a \left[ r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^(s') \right], \qquad Q^(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) \max_{a'} Q^(s',a') $$

Symbols: $r(s,a)$ is the expected immediate reward, $P(s' \mid s,a)$ the transition probability, $\gamma$ the discount factor, $V^$ and $Q^$ the optimal value functions. The optimal policy is $\pi^(s) = \arg\max_a Q^(s,a)$, and it is deterministic and stationary — a result that takes real work to prove, and one that holds for discounted infinite-horizon MDPs and fails for constrained or partially observed ones.

Why value iteration converges#

Define the Bellman optimality operator $\mathcal{T} : \mathbb{R}^{|\mathcal{S}|} \to \mathbb{R}^{|\mathcal{S}|}$ by $$ (\mathcal{T}V)(s) = \max_a \left[ r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s') \right] $$

$\mathcal{T}$ is a $\gamma$-contraction in the supremum norm: $$ |\mathcal{T}V - \mathcal{T}U|\infty \le \gamma |V - U|\infty $$

The proof is short. For any $s$, $|(\mathcal{T}V)(s) - (\mathcal{T}U)(s)| \le \max_a \gamma \sum_{s'} P(s'|s,a) |V(s') - U(s')| \le \gamma |V-U|_\infty$, using $|\max_a f - \max_a g| \le \max_a |f-g|$ and that $P(\cdot|s,a)$ sums to one.

Banach's fixed-point theorem then gives a unique fixed point $V^$ and geometric convergence: $|V_k - V^|_\infty \le \gamma^k |V_0 - V^|\infty$. The practical stopping rule follows from it — if $|V{k+1} - V_k|\infty < \epsilon$ then $|V{k+1} - V^|_\infty < \epsilon\gamma/(1-\gamma)$.

Reaching $\epsilon$ accuracy needs $O!\left( \frac{\log(1/\epsilon(1-\gamma))}{1-\gamma} \right)$ iterations, each costing $O(|\mathcal{S}|^2|\mathcal{A}|)$. The $1/(1-\gamma)$ factor is why $\gamma = 0.999$ problems are expensive to plan in.

The three exact methods#

Policy iteration alternates evaluation (solve $V^\pi = r^\pi + \gamma P^\pi V^\pi$, a linear system) with improvement ($\pi'(s) = \arg\max_a Q^\pi(s,a)$). The policy improvement theorem guarantees $V^{\pi'} \ge V^\pi$ pointwise, and since there are finitely many deterministic policies, it terminates at an exact optimum. Ye (2011) proved it is strongly polynomial for fixed $\gamma$, resolving a long-open question.

The curse of dimensionality#

$|\mathcal{S}|$ grows exponentially in the number of state variables. A robot arm with 7 joints discretised at 100 positions each has $10^{14}$ states. Exact dynamic programming is therefore restricted to small problems, and everything else in this section — Q-learning, DQN, policy gradients — exists to sidestep it, by sampling instead of sweeping and by approximating $V$ or $\pi$ with a function rather than a table.

Extensions worth knowing#

• Average-reward MDPs replace discounting with $\rho^\pi = \lim_{T\to\infty} \frac{1}{T}\mathbb{E}[\sum_{t=1}^T r_t]$, and the Bellman equation acquires a bias term. Appropriate for genuinely continuing tasks where discounting is an artefact.
• Constrained MDPs (Altman, 1999) add expected-cost constraints. Optimal policies are then generally stochastic, and the LP formulation handles them naturally while value iteration does not.
• Semi-MDPs allow actions of variable duration, which is the formal basis of the options framework for hierarchical RL (Sutton, Precup and Singh, 1999).
• Robust MDPs (Iyengar, 2005; Nilim and El Ghaoui, 2005) optimise against a set of transition kernels, which matters whenever $P$ is estimated from data.

References#

• Bellman (1957), Dynamic Programming — the origin, and the source of "curse of dimensionality".
• Howard (1960), Dynamic Programming and Markov Processes — policy iteration.
• Puterman (1994), Markov Decision Processes: Discrete Stochastic Dynamic Programming — the definitive reference.
• Ye (2011), The Simplex and Policy-Iteration Methods are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate.
• Sutton and Barto (2018), chapters 3 and 4.

What to learn next#

• Q-learning — solving an MDP when nobody hands you the rulebook.
• Exploration vs exploitation — the cost of not knowing the transition probabilities.
• Probability — the background the transition kernel assumes.