Value and Policy Iteration

Hello! Welcome to our third lesson in the Reinforcement Learning Foundations module.

In our last two lessons, we formulated problems as Markov Decision Processes (MDPs) and derived the Bellman equations, which provide the theoretical bedrock for solving them. We saw how the Bellman optimality equation defines the value of an optimal policy:

$v_{\ast }(s)={\max }_{a\in A}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma v_{\ast }(s^{\prime })\right]$

We briefly introduced two algorithms based on this principle: Value Iteration and Policy Iteration. Today, we're moving from theory to practice. Your goal for this lesson is to implement these two foundational dynamic programming algorithms from scratch. Given your software engineering background and fluency in Python, this will be an excellent opportunity to turn these mathematical concepts into working code.

Let's get started.

1. Value Iteration: Finding the Optimal Value Function

Value Iteration (VI) is a straightforward way to solve for the optimal value function, $v_{\ast }$. The idea is to turn the Bellman optimality equation into an iterative update rule. We start with a random or zero-initialized value function and repeatedly update it for every state until it converges.

The update rule, which we saw last time, is:

$v_{k+1}(s)\leftarrow {\max }_{a\in A}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma v_k(s^{\prime })\right]$

This process is sometimes called applying the "Bellman backup operator."

The Algorithm

The algorithm proceeds as follows:

1. Initialize $V(s)=0$ for all states $s$.
2. Loop until convergence:
   • For each state $s$:
     • Calculate the value for each action $a$: $q(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V(s^{\prime })]$
     • Update the state-value: $V(s)\leftarrow {\max }_{a}q(s,a)$
3. Output: Once $V$ has converged to $V_{\ast }$, extract the optimal policy ${\pi }_{\ast }$ by choosing the action that maximizes the expected value for each state:
   ${\pi }_{\ast }(s)=\arg {\max }_{a\in A}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V_{\ast }(s^{\prime })]$

The following video provides a clear, detailed explanation of this process.

Implementation in Python

Now, let's see what this looks like in code. The next video demonstrates how to implement Value Iteration in Python, including how to structure the data and manage the iterative updates.

Now it's your turn to code. You will implement Value Iteration yourself. The following GitHub repository contains a Jupyter Notebook with a solution for the "Gridworld" environment from the Sutton & Barto textbook.

2. Policy Iteration: The Dance of Evaluation and Improvement

Policy Iteration (PI) takes a different approach. Instead of directly targeting $V_{\ast }$, it iterates on the policy itself until it finds the optimal one. It does this by repeating two steps in a loop: Policy Evaluation and Policy Improvement.

The Algorithm

1. Initialization: Start with a random policy, $\pi$.
2. Loop until the policy no longer changes:
   • a) Policy Evaluation: Given the current policy $\pi$, calculate its value function, $V^{\pi }$. This is done by solving the Bellman expectation equation. In practice, we solve it iteratively:
     • Loop until $V^{\pi }$ converges:
       $V_{k+1}^{\pi }(s)\leftarrow {\sum }_{s^{\prime },r}p(s^{\prime },r|s,\pi (s))\left[r+\gamma V_k^{\pi }(s^{\prime })\right]$
   • b) Policy Improvement: For each state $s$, update the policy by choosing the action that is greedy with respect to $V^{\pi }$:
     ${\pi }^{\prime }(s)\leftarrow \arg {\max }_{a\in A}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma V^{\pi }(s^{\prime })\right]$
     • If ${\pi }^{\prime }=\pi$, the algorithm has converged. Otherwise, set $\pi \leftarrow {\pi }^{\prime }$ and repeat.

Let's return to Andrew Ng's lecture for an explanation of this two-step process.

Implementation in Python

Now, you'll implement Policy Iteration. The structure will be slightly more complex than Value Iteration, involving an outer loop for policy improvement and an inner loop for policy evaluation.

3. Value Iteration vs. Policy Iteration

So, which algorithm is better? There's no single answer; it depends on the problem.

• Policy Iteration often converges in very few policy iterations. However, each iteration is computationally expensive because it requires a full policy evaluation (which is itself an iterative process).
• Value Iteration involves simpler, cheaper updates in each iteration. It may take more iterations to converge to the optimal value function, but each one is faster.

For large state spaces, solving the linear system for policy evaluation becomes very costly, so Value Iteration is often preferred.

Conclusion

Congratulations! You have now implemented the two foundational algorithms for solving MDPs when the model is known. These dynamic programming methods are the theoretical basis for many more advanced reinforcement learning techniques.

Key Takeaways:

• Dynamic Programming in RL refers to algorithms that solve MDPs using the Bellman equations, assuming a perfect model of the environment.
• Value Iteration directly computes the optimal value function $V_{\ast }$ by repeatedly applying the Bellman optimality update.
• Policy Iteration alternates between two steps: evaluating the current policy to find $V^{\pi }$ and improving it by acting greedily with respect to $V^{\pi }$.
• The choice between VI and PI involves a trade-off between the number of iterations and the computational cost per iteration.

Preview of the Next Lesson:

So far, we've operated under a critical assumption: we know the environment's dynamics, $p(s^{\prime },r|s,a)$. This is why these are called model-based methods. But what happens when we don't have a model? How can an agent learn to navigate a world it doesn't understand beforehand?

In our next lesson, we will step into the world of model-free reinforcement learning. We will start with Monte Carlo methods, where an agent learns the value of states simply by running through many episodes of experience and averaging the results. This marks a crucial shift from planning with a known model to learning directly from interaction.