LRL-5: Dynamic Programming - Planning in Known Environments

Let's continue our exploration of Reinforcement Learning with Chapter 5: Dynamic Programming - Planning in Known Environments. In the previous chapter, we established the mathematical foundation with MDPs and Bellman Equations. Now, we'll see how to use these tools to actually solve MDPs when we have complete knowledge of the environment. This is where Dynamic Programming (DP) comes in.

Chapter 5: Dynamic Programming - Planning in Known Environments

In this chapter, we'll explore Dynamic Programming (DP) methods for solving Reinforcement Learning problems. DP is a powerful set of algorithms that can be used to compute optimal policies and value functions for Markov Decision Processes (MDPs), assuming we have a perfect model of the environment. This means we know the state space, action space, transition probabilities, and reward function. While this perfect model assumption is often unrealistic in real-world RL, understanding DP is crucial because it provides the theoretical foundation for many other RL algorithms and gives us a benchmark for optimal performance.

1. Introduction to Dynamic Programming: Breaking Down Complex Problems

Dynamic Programming (DP) is not specific to Reinforcement Learning. It's a general algorithmic technique used to solve complex problems by breaking them down into simpler, overlapping subproblems. DP is particularly useful for optimization problems that exhibit two key properties:

• Optimal Substructure: An optimal solution to a problem can be constructed from optimal solutions to its subproblems. In RL terms, the optimal policy for an MDP can be defined recursively in terms of optimal policies for subsequent states. This is precisely what Bellman equations capture.
• Overlapping Subproblems: The same subproblems are encountered multiple times when solving the larger problem. DP avoids redundant computations by solving each subproblem only once and storing its solution (usually in a table or memoization). In RL, when we calculate value functions, we repeatedly use values of other states, leading to overlapping subproblems.

(Analogy: Finding the Shortest Path in a Graph using DP)

Imagine you want to find the shortest path from point A to point G in a city map (graph).

(Diagram: City Map as a Graph with points A to G and roads with distances)

• Optimal Substructure: If the shortest path from A to G goes through point C, then the part of the path from C to G must also be the shortest path from C to G.
• Overlapping Subproblems: To find the shortest path to G from A, you might need to find the shortest paths to G from various intermediate points (like B, C, D, E, F). These intermediate shortest path problems might overlap. For example, to find the shortest path to G from both B and C, you might need to consider paths from D, E, F to G.

DP algorithms, like Dijkstra's algorithm or Bellman-Ford algorithm (for shortest paths), exploit these properties to efficiently find the optimal solution. In RL, DP algorithms exploit the optimal substructure and overlapping subproblems inherent in MDPs, as expressed by the Bellman equations.

2. Applicability of DP to Reinforcement Learning

DP is applicable in RL when we are dealing with Markov Decision Processes (MDPs) where we have complete knowledge of the environment. This means we know:

• The state space S
• The action space A
• The transition probabilities P(s'|s, a)
• The reward function R(s, a, s')
• The discount factor γ

In such cases, we can use DP algorithms to compute:

• Optimal Policy (π_*): The best strategy for the agent to maximize cumulative reward.
• Optimal State Value Function (V^*(s)): The maximum possible expected return starting from each state s.
• Optimal Action Value Function (Q^*(s, a)): The maximum possible expected return starting from state s, taking action a, and then following an optimal policy.

Important Note: DP methods are considered planning methods in RL because they require a complete model of the environment. They are used to plan optimal behavior before actually interacting with the environment. In contrast, many real-world RL problems involve learning from experience in environments where the model is unknown. However, DP provides a crucial theoretical foundation and serves as a building block for understanding more practical RL algorithms.

3. Policy Evaluation: Calculating Value Functions for a Given Policy

Let's start with Policy Evaluation, also known as prediction problem. Given a policy π, we want to calculate its value function, either the state value function V^π(s) or the action value function Q^π(s, a). We'll focus on V^π(s) first.

We know from the Bellman Expectation Equation for V^π(s):

• V^π(s) = ∑_a∈A π(a|s) ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV^π(s')]

This equation is a system of linear equations (if the state space is finite). We can solve this system directly, but for larger state spaces, iterative methods are more practical.

Iterative Policy Evaluation Algorithm:

1. Initialization: Initialize V^π(s) arbitrarily for all states s ∈ S, e.g., V^π(s) = 0 for all s.

2. Iteration: Repeatedly update the value function for each state s using the Bellman Expectation Equation:

   • V_k+1^π(s) = ∑_a∈A π(a|s) ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV_k^π(s')]

   (Equation: Iterative Policy Evaluation Update Rule)

   • V_k^π(s) is the estimated value of state s at iteration k.
   • The update is done synchronously for all states in each iteration (using values from the previous iteration V_k^π(s')).

3. Convergence: Repeat step 2 until the value function estimates V_k^π(s) converge. Convergence can be checked by monitoring the maximum change in value function across all states between iterations:

   • Stop when max_s∈S |V_k+1^π(s) - V_k^π(s)| < θ, where θ is a small threshold (e.g., 10^-6).

(Algorithm Box: Iterative Policy Evaluation)

Algorithm: Iterative Policy Evaluation

Input: Policy π, MDP (S, A, P, R, γ)
Output: State value function V<sup>π</sup>

Initialize: V<sup>π</sup>(s) = 0 for all s ∈ S (or arbitrarily)
Repeat:
    Δ ← 0  (Initialize maximum change to 0)
    For each state s ∈ S:
        v ← V<sup>π</sup>(s) (Store old value)
        V<sup>π</sup>(s) ← ∑<sub>a∈A</sub> π(a|s) ∑<sub>s'∈S</sub> P(s'|s, a) [R(s, a, s') + γV<sup>π</sup>(s')]  (Update using Bellman Expectation Equation)
        Δ ← max(Δ, |v - V<sup>π</sup>(s)|) (Update maximum change)
Until Δ < θ (Convergence threshold)

Return: V<sup>π</sup>

Example: Let's consider a simple grid world. Imagine a 4x4 grid. Let's say all actions (Up, Down, Left, Right) are equally likely under policy π in every non-terminal state. Let's assume we want to evaluate this random policy. We can initialize V^π(s) = 0 for all states and iteratively update using the Bellman Expectation equation. After several iterations, the value function will converge to the true V^π.

(Image: Example 4x4 Grid World for Policy Evaluation)

4. Policy Improvement: Finding Better Policies based on Value Functions

Now that we know how to evaluate a policy π (i.e., calculate V^π(s)), let's think about how to improve this policy. The idea is to make the policy "greedier" with respect to the value function.

Policy Improvement Theorem:

If we have a policy π and its value function V^π, and we find a new policy π' such that for some state s,

• Q^π(s, π'(s)) > V^π(s)

  where Q^π(s, a) = ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV^π(s')] is the action value function for policy π, and π'(s) is the action chosen by the new policy in state s.

Then, the new policy π' is guaranteed to be better than or equal to π for state s and for all subsequent states reached from s. Specifically, V^π'(s) ≥ V^π(s) for all s.

Greedy Policy Improvement:

A common approach for policy improvement is to make the policy greedy with respect to the current value function. For each state s, we choose the action a that maximizes the action value function Q^π(s, a) (calculated based on the current V^π).

• π'(s) = argmax_a∈A Q^π(s, a) = argmax_a∈A ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV^π(s')]

(Equation: Greedy Policy Improvement)

This creates a new policy π' that is guaranteed to be better than or equal to the original policy π. If there are multiple actions that maximize Q^π(s, a), we can choose any of them (or even randomize among them). If the greedy policy π' is the same as the original policy π, it means that the policy π is already optimal (or at least locally optimal).

5. Policy Iteration: Iteratively Improving Policies and Value Functions

Policy Iteration is an algorithm that combines Policy Evaluation and Policy Improvement to find an optimal policy. It iteratively performs these two steps until the policy stabilizes (no further improvement is possible).

Policy Iteration Algorithm:

1. Initialization: Initialize a policy π arbitrarily, e.g., a random policy.
2. Policy Evaluation: Calculate the value function V^π for the current policy π using Iterative Policy Evaluation (until convergence).

3. Policy Improvement: Create a new policy π' by making it greedy with respect to V^π:

   • For each state s ∈ S:
     • π'(s) = argmax_a∈A ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV^π(s')]
4. Policy Stability Check: If π' = π (i.e., the policy did not change in the improvement step), then π is an optimal policy. Stop and return π. Otherwise, set π = π' and go back to step 2.

(Algorithm Box: Policy Iteration)

Algorithm: Policy Iteration

Input: MDP (S, A, P, R, γ)
Output: Optimal policy π<sub>*</sub> and optimal value function V<sup>*</sup>

Initialization: Initialize policy π arbitrarily (e.g., random policy)
Loop:
    1. Policy Evaluation:
       Calculate V<sup>π</sup> using Iterative Policy Evaluation (until convergence)
    2. Policy Improvement:
       policy_stable ← true
       For each state s ∈ S:
           old_action ← π(s)
           π(s) ← argmax<sub>a∈A</sub> ∑<sub>s'∈S</sub> P(s'|s, a) [R(s, a, s') + γV<sup>π</sup>(s')]
           If old_action ≠ π(s):
               policy_stable ← false
       If policy_stable:
           Return π (Optimal policy) and V<sup>π</sup> (Optimal value function V<sup>*</sup>)

Guarantees of Policy Iteration:

• Policy Iteration is guaranteed to converge to an optimal policy π in a finite number of iterations for finite MDPs.
• Each iteration improves the policy (or keeps it the same if it's already optimal).
• Since there are a finite number of policies (for finite action spaces), the algorithm must eventually converge to an optimal policy.

6. Value Iteration: Directly Computing Optimal Value Functions

Value Iteration is another DP algorithm for finding optimal policies. Instead of iteratively improving policies, Value Iteration directly computes the optimal value function V(s) (or Q(s, a)) using the Bellman Optimality Equation.

Recall the Bellman Optimality Equation for V(s)*:

• V(s) = max_a∈A ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV(s')]

Iterative Value Iteration Algorithm:

1. Initialization: Initialize V(s) arbitrarily for all states s ∈ S, e.g., V(s) = 0 for all s.

2. Iteration: Repeatedly update the value function for each state s using the Bellman Optimality Equation:

   • V_k+1(s) = max_a∈A ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV_k(s')]

   (Equation: Value Iteration Update Rule)

   • V_k(s) is the estimated optimal value of state s at iteration k*.
   • The update is done synchronously for all states in each iteration.

3. Convergence: Repeat step 2 until the value function estimates V_k(s)* converge. Check for convergence using a threshold, similar to Policy Evaluation:

   • Stop when max_s∈S |V_k+1(s) - V_k(s)| < θ.

(Algorithm Box: Value Iteration)

Algorithm: Value Iteration

Input: MDP (S, A, P, R, γ)
Output: Optimal value function V<sup>*</sup> and optimal policy π<sub>*</sub>

Initialize: V<sup>*</sup>(s) = 0 for all s ∈ S (or arbitrarily)
Repeat:
    Δ ← 0  (Initialize maximum change to 0)
    For each state s ∈ S:
        v ← V<sup>*</sup>(s) (Store old value)
        V<sup>*</sup>(s) ← max<sub>a∈A</sub> ∑<sub>s'∈S</sub> P(s'|s, a) [R(s, a, s') + γV<sup>*</sup>(s')] (Update using Bellman Optimality Equation)
        Δ ← max(Δ, |v - V<sup>*</sup>(s)|) (Update maximum change)
    Until Δ < θ (Convergence threshold)

Optimal Policy Extraction:
For each state s ∈ S:
    π<sub>*</sub>(s) = argmax<sub>a∈A</sub> ∑<sub>s'∈S</sub> P(s'|s, a) [R(s, a, s') + γV<sup>*</sup>(s')]

Return: V<sup>*</sup> and π<sub>*</sub>

Optimal Policy Extraction from V^*:

Once Value Iteration converges to the optimal value function V(s), we can extract an optimal policy π. For each state s*, the optimal action is the one that achieves the maximum expected value according to the Bellman Optimality Equation:

• π(s) = argmax_a∈A ∑_s'∈S P(s'|s, a) [R(s, a, s') + γV(s')]

Comparison of Policy Iteration and Value Iteration:

• Policy Iteration: Alternates between full policy evaluation and policy improvement. Typically converges in fewer iterations than Value Iteration, but each iteration can be more computationally expensive (especially policy evaluation step).
• Value Iteration: Performs truncated policy evaluation in each iteration (only one update step based on Bellman Optimality Equation). Generally, each iteration is computationally cheaper than Policy Iteration, but it might require more iterations to converge.

In practice, the choice between Policy Iteration and Value Iteration depends on the specific MDP and computational resources. For smaller MDPs, Policy Iteration can be efficient. For larger MDPs, Value Iteration or variations of it are often preferred.

7. Limitations of Dynamic Programming in Real-World RL

Despite their theoretical importance, classic Dynamic Programming methods like Policy Iteration and Value Iteration have significant limitations when applied to many real-world Reinforcement Learning problems:

• Requires a Complete Model of the Environment: DP algorithms assume that we know the transition probabilities P(s'|s, a) and the reward function R(s, a, s') perfectly. In many real-world scenarios, this is not the case. We often need to learn about the environment through interaction, without a pre-given model.
• Computational Cost (Curse of Dimensionality): DP algorithms typically require iterating over the entire state space in each iteration. If the state space is very large (or continuous), DP becomes computationally intractable. The number of states can grow exponentially with the number of state variables (curse of dimensionality). Similarly, if the action space is also large or continuous, finding the maximum action in policy improvement or value iteration becomes challenging.

Why Study Dynamic Programming then?

Even with these limitations, studying DP is essential for Reinforcement Learning because:

• Theoretical Foundation: DP provides the fundamental concepts and algorithms that underpin many other RL methods. Understanding DP helps in understanding more advanced algorithms.
• Benchmark for Optimal Performance: DP gives us a way to calculate the optimal policy and value function for a given MDP (when a model is available). This serves as a benchmark to compare against when we use approximate methods in model-free RL.
• Building Blocks for More Advanced Techniques: Some advanced RL algorithms, like model-based RL methods, build upon DP ideas and try to combine them with learning from experience to overcome the limitations of classical DP.

What's Next?

In the next chapters, we will move beyond Dynamic Programming and explore methods that can be applied when we don't have a perfect model of the environment, and when dealing with large or even infinite state and action spaces. We will start with Monte Carlo Methods (Chapter 6), which learn directly from episodes of experience without requiring a model of the environment. These methods are the first step towards more practical and widely applicable Reinforcement Learning algorithms.