Dynamic Programming in RL

Dynamic programming solves MDPs exactly when the model ($P$, $R$) is known. Foundation for understanding all RL algorithms.

Policy Evaluation — compute $V^\pi$ for a given policy: Iterate: $V_{k+1}(s) = \sum_a \pi(a|s)[R(s,a) + \gamma\sum_{s'}P(s'|s,a)V_k(s')]$ Converges to $V^\pi$ as $k \to \infty$.

Policy Improvement — make the policy greedy w.r.t. current value: $\pi'(s) = \arg\max_a [R(s,a) + \gamma\sum_{s'}P(s'|s,a)V^\pi(s')]$ Guaranteed to be at least as good as $\pi$ (policy improvement theorem).

Policy Iteration:

1. Evaluate current policy (policy evaluation)
2. Improve policy greedily (policy improvement)
3. Repeat until convergence Always converges to optimal policy in finite steps.

Value Iteration: Combine evaluation and improvement in one step: $V_{k+1}(s) = \max_a [R(s,a) + \gamma\sum_{s'}P(s'|s,a)V_k(s')]$ This is iterating the Bellman optimality equation. Converges to $V^*$.

Limitation: requires full knowledge of $P(s'|s,a)$ and $R(s,a)$, and iterates over all states — only works for small, discrete MDPs. Model-free methods (Q-Learning, Miscoral Difference Learning) remove these requirements.

See also: Bellman Equations, Value Functions, Markov Decision Process