Dynamic Programming (DP) is a core set of algorithms used in Reinforcement Learning (RL) to solve problems modeled as a Markov Decision Process (MDP)1. DP methods are particularly effective when the agent has full knowledge of the environment’s dynamics (the transition probabilities P(s’|s, a) and the reward function R(s, a, s’).
The fundamental challenge in solving MDPs is that the Bellman Equation — which defines the value of a state or action — creates a massive system of simultaneous equations. For a problem with S states and A actions, solving this system directly is computationally infeasible.
DP circumvents this by using iterative updates and the concept of bootstrapping (where updates to the value function are based on estimated values of successor states). This approach falls into two main categories: Policy Iteration and Value Iteration.
1. The Two Goals: Policy Evaluation and Policy Control
DP algorithms are built around two interlocking sub-problems:
Policy Evaluation: Given a specific policy pi, calculate the state-value function $V_{\pi}(s)$ (the expected long-term return from state s if policy pi is followed). This is an intermediate step.
Policy Control: Find the optimal policy pi* that maximizes the value function V*(s) for all states. This is the ultimate goal.
2. Policy Iteration: Evaluate, then Improve
The Policy Iteration method is a complete solution that alternates between Policy Evaluation and Policy Improvement until the optimal policy is found.
This step calculates the value function $V_{\pi}$ for the current policy pi. It uses the Bellman Expectation Equation iteratively:
Process: Starting with an arbitrary value function $V_0(s)$ (often all zeros) , the value of each state $s$ is updated based on the estimated value of the next state s’ (bootstrapping).
Convergence: This process is repeated until the maximum change in the value function ($\Delta$) across all states drops below a small threshold. The value function $V_k$ is guaranteed to converge to the true $V_{\pi}$ under the given policy $\pi$.
Update Style: A “in-place” update (where the current state’s new value is used immediately to calculate the next state’s value, known as the “overwrite method”) is generally faster than using a separate new_V table.
Step 2: Policy Improvement (Greedy Policy)
Once $V_{\pi}$ is accurately calculated, the policy is improved by taking an action that is greedy with respect to the new value function.
Greedy Action: For each state $s$, the new policy $\pi’(s)$ chooses the action $a$ that leads to the best combination of immediate reward ($R$) and discounted value of the next state ($\gamma V_{\pi}(s’)$).
Policy Improvement Theorem: This theorem guarantees that the new greedy policy $\pi’$ will be better than or equal to the previous policy $\pi$. If $\pi’$ is strictly better, the process repeats.
Convergence to Optimal Policy
Policy iteration alternates between evaluation and improvement. Since there is a finite number of policies in a finite MDP, this process is guaranteed to converge to the optimal policy pi* and its optimal value function V*.
3. Value Iteration: Combining Evaluation and Improvement
Value Iteration is a simplified DP algorithm that implicitly combines the Policy Evaluation and Policy Improvement steps. It does not require a full, separate policy evaluation phase.
The Core Idea: Bellman Optimality Equation
Instead of iteratively solving the Bellman Expectation Equation (Policy Evaluation), Value Iteration directly uses the Bellman Optimality Equation for V*:
Single Step: In each iteration ($k \to k+1$), the value of state $V(s)$ is updated by taking the maximum expected value over all possible actions $a$. This $\max_{a}$ operationis the policy improvement step.
Evaluation and Improvement: By taking the $\max_{a}$, the algorithm effectively performs a one-step greedy policy improvement at the same time it’s updating the value function (evaluation).
Convergence and Final Policy
Convergence: Like policy evaluation, the value function $V_k$ is guaranteed to converge to the optimal value function V*.
Extracting pi*: Once V*is found, the optimal policy pi* can be extracted in a single step by performing a final greedy policy operation with respect to the converged V*.
Policy Iteration vs. Value Iteration (Generalized Policy Iteration)
Both Policy Iteration and Value Iteration are forms of Generalized Policy Iteration (GPI), where Policy Evaluation ($V \to V$) and Policy Improvement ($\mu \to \mu’$) interact until convergence.
Policy Iteration performs a full evaluation (many V updates) before a single improvement (one pi update).
Value Iteration performs a one-step improvementfor every state update (no need for the separate, time-consuming full evaluation).
Value Iteration typically converges faster by reducing the number of evaluation steps, making it computationally more efficient, especially in large MDPs.
