Policy and Value Iteration in Reinforcement Learning

Understanding Policy and Value Iteration in Reinforcement Learning

Policy and value iteration are fundamental algorithms for solving Markov Decision Processes (MDPs). They belong to the family of dynamic programming methods that assume a complete model of the environment – i.e., transition probabilities and rewards are known. This course explains the key concepts, mathematical foundations, and practical considerations that arise when applying these algorithms, especially in classic environments such as FrozenLake.

1. Deterministic Policies and Their Count

In a deterministic MDP each state selects a single action. If an MDP has S states and A possible actions per state, the number of distinct deterministic policies is:

• Formula: A^S
• Example: With 10 states and 4 actions per state, the total number of deterministic policies is 4^{10}.

This exponential growth highlights why exhaustive search is infeasible for even modestly sized problems, motivating the need for efficient iterative methods.

2. Bellman Update for Policy Evaluation

The Bellman expectation equation describes how to compute the value of a policy \pi. The iterative update used in policy evaluation is:

V_{k+1}(s) = \sum_{a}\pi(a|s)\sum_{s',r}p(s',r|s,a)[r + \gamma V_k(s')]

Key points:

• \pi(a|s) is the probability of taking action a in state s under the current policy.
• p(s',r|s,a) denotes the joint probability of transitioning to state s' and receiving reward r after action a.
• \gamma (0 ≤ γ < 1) is the discount factor, weighting future rewards.

This update performs a full sweep over all states, simultaneously improving the estimate of V^\pi until convergence.

3. Value Iteration vs. Policy Iteration on FrozenLake

FrozenLake is a grid‑world with stochastic dynamics (the agent may slip). Two classic algorithms behave differently:

• Policy Iteration alternates between a full policy evaluation (many sweeps) and a policy improvement step.
• Value Iteration merges these steps by applying the Bellman optimality operator after each sweep, directly updating values toward optimality.

Because value iteration combines evaluation and improvement in each sweep, it typically reaches a near‑optimal policy with fewer total sweeps, making it faster for environments like FrozenLake where the state space is modest but the transition model is stochastic.

4. Why Policy Evaluation Can Update All States Simultaneously

In planning scenarios the agent possesses a complete model of the MDP. This knowledge allows the algorithm to compute the expected return for every state in a single Bellman sweep, without needing to collect samples from the environment. The simultaneous update is possible because:

• The transition probabilities p(s',r|s,a) are known for every (s,a) pair.
• The update equation is a linear system that can be solved iteratively or directly (e.g., via matrix inversion).

Contrast this with model‑free methods, where updates rely on sampled trajectories and therefore affect only visited states.

5. Contraction Property of the Bellman Optimality Operator

The Bellman optimality operator T* applied to a value function V is defined as:

(T^*V)(s) = \max_{a}\sum_{s',r}p(s',r|s,a)[r + \gamma V(s')]

This operator is a γ‑contraction in the sup‑norm:

• For any two value functions V and W,

  \|T^*V - T^*W\|_\infty \le \gamma \|V - W\|_\infty

• Consequently, repeated application of T* drives the error toward zero at a geometric rate.

This property guarantees that value iteration converges to the unique optimal value function V*.

6. Policy Improvement Guarantees

During policy improvement, the algorithm selects for each state the action that maximizes the action‑value function:

\pi_{new}(s) = \arg\max_{a} Q^{\pi_{old}}(s,a)

Because the greedy action maximizes the expected return given the current value estimates, the new policy is guaranteed to be at least as good as the previous one (policy improvement theorem). This monotonic improvement continues until the policy becomes stable, indicating optimality.

7. Computational Trade‑offs: When to Prefer Value Iteration

Policy iteration can be computationally expensive because each improvement step requires a full policy evaluation, often involving many sweeps over the state space. When computational resources (CPU time, memory) are limited, value iteration is attractive because:

• It performs a single sweep per iteration, reducing the total number of passes.
• It does not require solving a linear system; each update is a simple max‑over‑actions.
• It converges sufficiently close to optimality for many practical purposes, especially when an exact solution is unnecessary.

8. Stochastic FrozenLake: Why the Optimal Policy May Not Move Directly Toward the Goal

In the stochastic (slippery) version of FrozenLake, actions do not always result in the intended movement. The transition model may cause the agent to slip into a hole if it follows a naïvely straight‑line path. Therefore, the optimal policy sometimes selects actions that appear to move away from the goal, but actually reduce the probability of falling into a hole and increase the expected return over the long term.

Key insights:

• Optimality is defined with respect to expected cumulative reward, not immediate distance.
• Planning with the full transition model reveals safe detours that a greedy, distance‑based heuristic would miss.

9. Summary of Core Concepts

• Deterministic policies grow exponentially as A^S.
• The Bellman expectation update is the backbone of policy evaluation.
• Value iteration merges evaluation and improvement, often converging faster than policy iteration.
• Having a full model enables simultaneous updates of all states during planning.
• The Bellman optimality operator is a γ‑contraction, guaranteeing convergence.
• Greedy policy improvement ensures monotonic policy improvement.
• Value iteration is computationally cheaper when resources are scarce.
• In stochastic environments, optimal policies may take indirect routes to avoid risk.

10. Further Reading and Practice

To deepen your understanding, explore the following resources:

• Sutton & Barto – Reinforcement Learning: An Introduction – Chapters 4 and 5 cover dynamic programming.
• OpenAI Gym’s FrozenLake environment – experiment with both deterministic and stochastic versions.
• Lecture videos on Policy vs. Value Iteration from MIT’s 6.824 course.

By mastering these concepts, you will be equipped to design efficient planners for a wide range of reinforcement‑learning problems, from simple grid worlds to complex, high‑dimensional domains.