Proposition: Optimality Conditions in Policy Iteration

Let’s examine a fundamental proposition that establishes optimality conditions for policy iteration in infinite horizon discounted cost problems. This proposition provides crucial insights into why policy iteration converges to optimal policies.

Statement of the Proposition

Consider a stationary policy $\bar{\mu}$ that satisfies the Bellman optimality condition:

$$ \underbrace{T_{\bar{\mu}}J^{\bar{\mu}} = TJ^{\bar{\mu}}}_{\substack{\text{Policy } \bar{\mu} \text{ achieves the minimum} \\ \text{in the Bellman equation for all states}}} $$

This can be expressed more explicitly for all states $i = 1,2,\ldots,n$ as:

$$ \underbrace{g(i,\bar{\mu}(i)) + \alpha \sum_{j=1}^n p_{ij}(\bar{\mu}(i))J^{\bar{\mu}}(j)}_{\substack{\text{Expected discounted cost} \\ \text{following policy } \bar{\mu} \text{ from state } i}} = \underbrace{\min_{u \in A(i)} \left[g(i,u) + \alpha \sum_{j=1}^n p_{ij}(u)J^{\bar{\mu}}(j)\right]}_{\substack{\text{Minimum expected discounted cost} \\ \text{over all possible actions in state } i}} $$

Key Properties

The proposition establishes two fundamental properties:

  1. Global Policy Dominance: For all states $i = 1,2,\ldots,n$ and any alternative policy $\mu$:

    $$ \underbrace{J_{\bar{\mu}}(i) \leq J_{\mu}(i)}_{\substack{\text{Policy } \bar{\mu} \text{ achieves lower or equal cost} \\ \text{compared to any other policy } \mu \text{ at every state}}} $$

  2. Strict Improvement Condition: If $\bar{\mu}$ is not optimal, then there exists at least one state $s$ where:

    $$ \underbrace{J_{\bar{\mu}}(s) < J_{\mu}(s)}_{\substack{\text{Strict cost improvement exists} \\ \text{at state } s \text{ for some better policy}}} $$

Implications and Significance

This proposition has several important implications:

  • Optimality Verification: A policy satisfying the Bellman equation is guaranteed to be at least as good as any other policy across all states
  • Improvement Guarantee: Non-optimal policies must have room for improvement in at least one state
  • Convergence Foundation: These properties ensure that policy iteration will continue improving until reaching an optimal policy
  • Termination Condition: When no further improvements are possible, we have reached global optimality

This theoretical foundation explains why policy iteration is a powerful algorithm for finding optimal policies in infinite horizon discounted cost problems.

Policy Iteration Algorithm

The policy iteration algorithm consists of three main steps that are repeated until convergence:

Step 1: Policy Initialization

Initialize with any stationary policy $\mu^0$:

$$ \underbrace{\mu^0: S \to A}_{\substack{\text{Initial mapping from} \\ \text{states to actions}}} $$

Step 2: Policy Evaluation

Given a stationary policy $\mu^k$, compute the corresponding cost $J^{\mu^k}$ by solving the linear system:

$$ \underbrace{(I - \alpha P_{\mu^k})J^{\mu^k} = g_{\mu^k}}_{\substack{\text{System of linear equations} \\ \text{for policy evaluation}}} $$

Which can be equivalently written as:

$$ \underbrace{J^{\mu^k} = g_{\mu^k} + \alpha P_{\mu^k}J^{\mu^k}}_{\substack{\text{Fixed point equation} \\ \text{for policy evaluation}}} $$

Or in operator notation:

$$ \underbrace{J^{\mu^k} = T_{\mu^k}J^{\mu^k}}_{\substack{\text{Policy evaluation as} \\ \text{a fixed point}}} $$

Step 3: Policy Improvement

Obtain a new stationary policy $\mu^{k+1}$ satisfying:

$$ \underbrace{T_{\mu^{k+1}}J^{\mu^k} = TJ^{\mu^k}}_{\substack{\text{New policy achieves the minimum} \\ \text{in the Bellman equation}}} $$

Termination Check

  • If $J^{\mu^{k+1}} = J^{\mu^k}$: then the current policy $\mu^k$ is optimal and the algorithm terminates.
  • Else: Set $k = k + 1$ and return to Step 2

Note that both $g_{\mu^k}$ and $P_{\mu^k}$ are computed using the current policy $\mu^k$ as follows:

  • For the cost vector $g_{\mu^k}$:
$$ g_{\mu^k} = \begin{bmatrix} g(1,\mu^k(1)) \\ g(2,\mu^k(2)) \\ \vdots \\ g(n,\mu^k(n)) \end{bmatrix}_{n \times 1} $$
  • For the probability transition matrix $P_{\mu^k}$:
$$ P_{\mu^k} = \begin{bmatrix} p(1,\mu^k(1),1) & p(1,\mu^k(1),2) & \cdots & p(1,\mu^k(1),n) \\ p(2,\mu^k(2),1) & p(2,\mu^k(2),2) & \cdots & p(2,\mu^k(2),n) \\ \vdots & \vdots & \ddots & \vdots \\ p(n,\mu^k(n),1) & p(n,\mu^k(n),2) & \cdots & p(n,\mu^k(n),n) \end{bmatrix}_{n \times n} $$

where $n$ is the total number of states in the system.

This algorithm systematically improves the policy until reaching optimality, with each iteration guaranteed to either:

  • Strictly improve the policy, or
  • Confirm the current policy is optimal

The convergence is finite since:

  • There are only finitely many deterministic stationary policies
  • Each iteration either improves or terminates
  • The algorithm cannot revisit a previous policy