Value Iteration and Policy Iteration

Now that we've reviewed the essential components of Markov Decision Processes (MDPs) and the Bellman equations, let's examine two fundamental dynamic programming algorithms used to solve MDPs when the model (transitions and rewards) is known: Policy Iteration and Value Iteration. These methods provide a basis for many reinforcement learning techniques that operate without a known model.

Policy Iteration (PI)

Policy Iteration is an approach that finds the optimal policy $\pi^*$ by iteratively performing two steps: evaluating the current policy and then improving it based on that evaluation. It starts with an arbitrary initial policy $\pi_0$ and alternates between these two phases until the policy no longer changes.

1. Policy Evaluation

In this step, we calculate the state-value function $V^\pi(s)$ for the current policy $\pi$. Recall the Bellman expectation equation for $V^\pi$:

$$V^\pi(s) = \sum_{a} \pi(a|s) \sum_{s'} P(s'|s, a) [R(s, a, s') + \gamma V^\pi(s')]$$

For a finite MDP with $|S|$ states, this equation defines a system of $|S|$ linear equations in $|S|$ unknowns ($V^\pi(s)$ for all $s \in S$). This system can be solved directly. However, a common iterative approach involves repeatedly applying the Bellman expectation backup operator to an initial estimate $V_k(s)$ until the values converge:

$$V_{k+1}(s) \leftarrow \sum_{a} \pi(a|s) \sum_{s'} P(s'|s, a) [R(s, a, s') + \gamma V_k(s')]$$

This iterative update is performed for all states $s$ until the change in the value function between iterations is sufficiently small (e.g., $\max_s |V_{k+1}(s) - V_k(s)| < \theta$). The result is an accurate estimate of $V^\pi$.

2. Policy Improvement

Once we have the value function $V^\pi$ for the current policy $\pi$, we check if we can improve it. We do this by considering, for each state $s$, whether acting differently than prescribed by $\pi$ would yield a better expected return. This involves calculating the action-value function $Q^\pi(s, a)$ using the computed $V^\pi$:

$$Q^\pi(s, a) = \sum_{s'} P(s'|s, a) [R(s, a, s') + \gamma V^\pi(s')]$$

Then, we define a new, potentially improved policy $\pi'$ that acts greedily with respect to $Q^\pi(s, a)$:

$$\pi'(s) = \arg\max_a Q^\pi(s, a)$$

This means $\pi'(s)$ selects the action that maximizes the expected one-step lookahead value, assuming we follow the original policy $\pi$ thereafter (as captured by $V^\pi$). The Policy Improvement Theorem guarantees that this new policy $\pi'$ is at least as good as, and possibly better than, $\pi$. That is, $V^{\pi'}(s) \ge V^\pi(s)$ for all $s \in S$.

The Policy Iteration Algorithm

The overall algorithm alternates these two steps:

1. Initialize a policy $\pi_0$ arbitrarily.
2. Repeat: a. Policy Evaluation: Compute $V^{\pi_k}$ (e.g., using iterative Bellman expectation backups). b. Policy Improvement: Compute $Q^{\pi_k}(s, a)$ using $V^{\pi_k}$. Define a new greedy policy $\pi_{k+1}(s) = \arg\max_a Q^{\pi_k}(s, a)$ for all $s$. c. Stopping Condition: If $\pi_{k+1}(s) = \pi_k(s)$ for all $s$, then stop and return $\pi_{k+1}$ and $V^{\pi_k}$. Otherwise, continue to the next iteration ($k \leftarrow k+1$).

Because a finite MDP has a finite number of policies, and each policy improvement step yields a policy that is strictly better or equal, Policy Iteration is guaranteed to converge to the optimal policy $\pi^*$ in a finite number of iterations.

The Policy Iteration process alternates between evaluating the current policy and improving it greedily based on the evaluation.

A potential drawback of PI is that the Policy Evaluation step can be computationally intensive, requiring many sweeps through the state space until $V^\pi$ converges accurately.

Value Iteration (VI)

Value Iteration offers a different approach. Instead of alternating between full policy evaluation and improvement, VI directly iteratively computes the optimal value function $V^*$ by repeatedly applying the Bellman optimality backup operator.

Recall the Bellman optimality equation for $V^*$:

$$V^*(s) = \max_a \sum_{s'} P(s'|s, a) [R(s, a, s') + \gamma V^*(s')]$$

Value Iteration turns this equation into an update rule. It starts with an initial guess $V_0(s)$ (often all zeros) and iteratively refines it:

$$V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s'|s, a) [R(s, a, s') + \gamma V_k(s')]$$

This update is applied synchronously (or asynchronously) to all states $s$ in each iteration $k$. Notice how the maximization over actions (policy improvement aspect) is directly incorporated into the value update (policy evaluation aspect).

The Value Iteration Algorithm

1. Initialize $V_0(s)$ for all $s \in S$ (e.g., $V_0(s) = 0$).
2. Initialize a threshold $\theta > 0$ (a small positive number).
3. Repeat: a. $\Delta \leftarrow 0$ b. For each state $s$: i. $v \leftarrow V_k(s)$ ii. $V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s'|s, a) [R(s, a, s') + \gamma V_k(s')]$ iii. $\Delta \leftarrow \max(\Delta, |v - V_{k+1}(s)|)$ c. $k \leftarrow k+1$ d. Stopping Condition: Until $\Delta < \theta$.
4. Output: A deterministic policy $\pi^*$ such that $\pi^*(s) = \arg\max_a \sum_{s'} P(s'|s, a) [R(s, a, s') + \gamma V_{k}(s')]$.

Value Iteration is guaranteed to converge to the optimal value function $V^*$ because the Bellman optimality operator is a contraction mapping, ensuring that the value estimates get progressively closer to the true $V^*$ with each iteration. Once $V^*$ (or a close approximation) is found, the optimal policy $\pi^*$ can be extracted by performing a single step of policy improvement, as shown in the final output step.

Example convergence of the value function for a specific state during Value Iteration. The value approaches the optimal value $V^*(s)$ over iterations.

Comparing Policy Iteration and Value Iteration

• Policy Iteration: Alternates between full policy evaluation (potentially many sweeps) and one policy improvement step. Guaranteed to find $\pi^*$ in a finite number of policy updates, but evaluation can be slow.
• Value Iteration: Performs one Bellman optimality backup per iteration. Each iteration is computationally simpler than a full policy evaluation in PI (no need to wait for $V^\pi$ to converge), but VI might require more iterations overall to converge to $V^*$.

In practice, Value Iteration often converges faster, especially when the number of possible policies is very large. Variations exist, such as modified policy iteration, which performs only a fixed number of Bellman expectation backups during the evaluation phase instead of iterating until full convergence.

Both VI and PI are fundamental dynamic programming methods for finding optimal policies in known MDPs. They illustrate the core concepts of evaluating policies and improving them using Bellman backups, which are central ideas adapted by many model-free reinforcement learning algorithms we will study later.