In value iteration, we were focused on finding the optimal value function $J^*$. In policy iteration, we start with a random policy and then improve it iteratively.

Algorithm Description

Policy iteration alternates between two main steps:

  1. Policy Evaluation: Given a policy $\mu_k$, compute its cost-to-go vector $J^{\mu_k}$ by solving the system of linear equations:

    $$ J^{\mu_k}(i) = \sum_{j=1}^n p_{ij}(\mu_k(i))(g(i,\mu_k(i),j) + J^{\mu_k}(j)) \quad i=1,\ldots,n $$

    where $J^{\mu_k}(1), J^{\mu_k}(2), \ldots, J^{\mu_k}(n)$ are the unknowns to be solved for.

    This is equivalent to solving the fixed point equation:

    $$ J^{\mu_k} = T_{\mu_k}J^{\mu_k} $$

  2. Policy Improvement: Given the cost-to-go vector $J^{\mu_k}$, find an improved policy $\mu_{k+1}$ by: $$ \mu_{k+1}(i) = \arg\min_{u \in \mathcal{A}(i)} \sum_{j=1}^n p_{ij}(u)(g(i,u,j) + J^{\mu_k}(j)) \quad \forall i=1,\ldots,n $$ This is equivalent to: $$ T_{\mu_{k+1}}J^{\mu_k} = TJ^{\mu_k} $$

The algorithm terminates when:

$$ J^{\mu_{k+1}}(i) = J^{\mu_k}(i) \quad \forall i=1,\ldots,n $$

indicating that an optimal policy has been found.

Algorithm Structure

The policy iteration algorithm has a nested loop structure, contrasting with value iteration’s single loop:

  1. Outer Loop (Policy Iteration)
    • Continues until policy convergence
    • Each iteration represents a complete policy update cycle
  2. Inner Loop (Policy Evaluation)
    • Solves the linear system of equations to evaluate current policy
    • Computes exact cost-to-go values for current policy
  3. Policy Improvement Step
    • Single-pass improvement of policy using current cost values
    • Not a loop, but rather a direct computation for each state

This structure can be represented mathematically as:

$$ \underbrace{\text{repeat}}_{\text{outer loop}} \left\{ \begin{array}{l} \underbrace{\text{solve } J^{\mu_k} = T_{\mu_k}J^{\mu_k}}_{\text{inner loop: policy evaluation}} \\ \underbrace{\mu_{k+1}(i) = \arg\min_{u \in \mathcal{A}(i)} \sum_{j=1}^n p_{ij}(u)(g(i,u,j) + J^{\mu_k}(j))}_{\text{policy improvement (no loop)}} \end{array} \right\} $$
This nested structure differs fundamentally from value iteration's single loop approach, where policy improvement is implicit in each iteration's value update.

Proposition

The policy iteration procedure generates an improving sequence of proper policies and terminates with an optimal policy in a finite number of iterations, assuming the starting policy is proper. This can be formalized in the following proposition:

Proposition 4 (Policy Iteration Convergence): Under Assumptions 1 and 2, if the initial policy $\mu_0$ is proper, then:

  1. Improving Sequence: The sequence of policies ${\mu_k}$ generated by policy iteration satisfies:
$$ \underbrace{J^{\mu_{k+1}}(i)}_{\substack{\text{Cost under} \\ \text{new policy}}} \leq \underbrace{J^{\mu_k}(i)}_{\substack{\text{Cost under} \\ \text{current policy}}} \quad \forall i=1,\ldots,n $$

with strict inequality for at least one state unless $\mu_k$ is optimal.

  1. Finite Termination: The algorithm terminates with an optimal policy $\mu^*$ in a finite number of iterations.

  2. Proper Policies: Each generated policy $\mu_k$ is proper, ensuring: $$ \underbrace{J^{\mu_k}(i)}_{\substack{\text{Cost under} \ \text{policy } \mu_k}} < \infty \quad \forall i=1,\ldots,n $$

Key implications:

  • The algorithm makes steady progress, never cycling between policies
  • Each iteration produces a strictly better policy until optimality
  • The finite termination property is particularly valuable for practical implementation
  • The proper policy requirement ensures well-defined cost functions throughout the process

Modified Policy Iteration

Modified policy iteration (MPI) is a hybrid algorithm that combines elements of both value iteration and policy iteration to achieve better computational efficiency. It addresses the main computational bottleneck of policy iteration - the exact policy evaluation step - by replacing it with a partial policy evaluation using a fixed number of value iterations.

Algorithm Structure

The algorithm consists of two main components:

  1. Partial Policy Evaluation: Instead of solving the linear system exactly, perform $m_k$ iterations of value iteration for the current policy:
$$ \underbrace{J_{k,l+1}}_{\substack{\text{Value estimate} \\ \text{at step l+1}}} = \underbrace{T_{\mu_k}J_{k,l}}_{\substack{\text{Policy Bellman} \\ \text{operator applied}}}, \quad l = 0,\ldots,m_k-1 $$

where $m_k$ is the number of inner loop iterations for the $k$th policy.

  1. Policy Improvement: Update the policy using the approximate value function:
$$ \underbrace{\mu_{k+1}(i)}_{\substack{\text{New policy} \\ \text{at state i}}} = \arg\min_{u \in \mathcal{A}(i)} \sum_{j=1}^n p_{ij}(u)(g(i,u,j) + J_{k,m_k}(j)) $$

The algorithm can be represented mathematically as:

$$ \underbrace{\text{repeat}}_{\text{outer loop}} \left\{ \begin{array}{l} \underbrace{\text{for } l=0 \text{ to } m_k-1: J_{k,l+1} = T_{\mu_k}J_{k,l}}_{\text{partial policy evaluation}} \\ \underbrace{\mu_{k+1}(i) = \arg\min_{u \in \mathcal{A}(i)} \sum_{j=1}^n p_{ij}(u)(g(i,u,j) + J_{k,m_k}(j))}_{\text{policy improvement}} \end{array} \right\} $$

Convergence Properties

The modified policy iteration algorithm maintains the convergence guarantees of standard policy iteration while potentially reducing computational cost. Key properties include:

  1. Convergence to Optimal Policy: The sequence of policies converges to an optimal policy $\mu^*$
  2. Value Function Convergence: The sequence of value functions converges to the optimal value function $J^*$
  3. Flexibility in Implementation: The number of inner iterations $m_k$ can be:
    • Fixed across all outer iterations
    • Varied based on convergence criteria
    • Adapted dynamically during execution

Computational Advantages

Modified policy iteration offers several benefits:

  • Reduces computational cost per iteration compared to exact policy evaluation
  • Maintains monotonic improvement in policy quality
  • Allows tuning of computational effort through $m_k$ parameter
  • Can be more efficient than both value iteration and policy iteration in practice

Note that

Modified policy iteration includes two special cases:

  1. Value Iteration: When $m_k = 1$ for all $k$

    • Each iteration performs just one value update
    • The policy improvement step becomes:
$$ \underbrace{J_{k+1}}_{\substack{\text{New value} \\ \text{estimate}}} = \underbrace{T_{\mu_k}J_k}_{\substack{\text{Policy Bellman} \\ \text{operator}}} = \underbrace{TJ_k}_{\substack{\text{Optimal Bellman} \\ \text{operator}}} $$
  1. Policy Iteration: When $m_k = \infty$ for all $k$
    • Each iteration solves the policy evaluation exactly
    • Equivalent to solving the linear system:
$$ \underbrace{J_k}_{\substack{\text{Value function} \\ \text{for policy } \mu_k}} = \underbrace{T_{\mu_k}J_k}_{\substack{\text{Fixed point of} \\ \text{policy Bellman operator}}} $$

The algorithm becomes value iteration when we set $m_k=1$ because $J_{k+1} = T_{\mu_k}J_k = TJ_k$, making each iteration equivalent to applying the optimal Bellman operator once.

Multi-stage look ahead policy iteration

Multi-stage look-ahead policy iteration extends regular policy iteration by looking ahead multiple stages when making policy decisions. Let’s understand this algorithm in detail.

Key Idea

The core concept is to improve upon regular policy iteration, which uses one-step look-ahead to find optimal decisions for one-stage problems with stage cost $g(i,a,j)$ and terminal cost $J^*(j)$. Instead, we look ahead multiple stages to find improved policies.

Mathematical Formulation

In an m-step look-ahead approach, we:

  1. Start at state $i$ and make $m$ subsequent decisions
  2. Incur corresponding stage costs $g$ over $m$ stages
  3. Get a terminal cost $J^*(j)$ where $j$ is the state after $m$ stages

Algorithm Properties

  • Claim: m-stage policy iteration terminates with optimal policy under same conditions as regular policy iteration

Formal Definition

Let

$$ \bar{\mu}_0,\bar{\mu}_1,...,\bar{\mu}_{m-1} $$

be an optimal policy for m-stage dynamic programming with terminal cost $J^*$. Then:

$$ \underbrace{T_{m-1}T...T_{m-k-1}J^*}_{\substack{\text{Composition of Bellman} \\ \text{operators for m stages}}} = \underbrace{TJ^*}_{\substack{\text{Single-stage} \\ \text{Bellman operator}}} $$
where:
  • $T_k$ represents the Bellman operator at stage $k$
  • $J^*$ is the optimal cost-to-go function
  • The equation starts with $k = m-1$

Implementation Considerations

  1. Computational Complexity:

    • Increases with look-ahead horizon $m$
    • Requires solving m-stage optimization problems
    • May need approximate methods for large $m$

  2. Trade-offs:

    • Longer look-ahead potentially improves policy quality
    • Computational cost grows exponentially with $m$
    • Need to balance accuracy vs. computational efficiency

  3. Practical Applications:

    • Games (like chess) with deep look-ahead search
    • Planning problems with clear future state predictions
    • Control systems with well-defined dynamics