策略迭代

策略迭代（policy iteration）交替计算当前策略的长期代价，再改进各状态的行动。在有限状态、有限行动、折扣系数严格小于一的马尔可夫决策过程中，精确策略评估与保持平局时原行动的改进规则，可在有限次策略变化后得到最优的平稳确定性策略。

评估与改进是两种运算

令 $c(s,a)$ 为一步成本、$P(s^{\prime }\mid s,a)$ 为转移概率、$0\le \gamma <1$。固定策略 $\pi (s)$ 的值满足 $$v^{\pi }=c_{\pi }+\gamma P_{\pi }{v}^{\pi },v^{\pi }=(I-\gamma P_{\pi }{)}^{-1}{c}_{\pi }.$$ 逆矩阵存在，因为级数 $\sum _{k\ge 0}{\gamma }^k{P}_{\pi }^k$ 收敛。随后在每个状态选择使 $c(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }\mid s,a)v^{\pi }(s^{\prime })$ 最小的行动；它使用旧值函数评价“这一步换行动、以后继续旧策略”的代价。

为何这种局部比较能够改进整条策略？记新策略为 ${\pi }^{\prime }$，其Bellman算子 $T_{{\pi }^{\prime }}v=c_{{\pi }^{\prime }}+\gamma P_{{\pi }^{\prime }}v$ 单调且是压缩映射。贪心改进给出 $T_{{\pi }^{\prime }}{v}^{\pi }\le v^{\pi }$；重复应用算子得到不增序列，其极限为 $v^{{\pi }^{\prime }}$，故 $v^{{\pi }^{\prime }}\le v^{\pi }$。若一次改进在某状态严格降低右侧，则该策略的值向量至少有一个分量严格改进，不会循环回旧策略。有限策略数保证有限停止；停止时贪心策略满足最优Bellman方程。

两状态例子的三次评估

取 $\gamma =1/2$。状态零的行动零成本一并留在零，行动一成本一并到一；状态一的行动零成本零并留在一，行动一成本四并到零。初始策略为 $(0,1)$，于是 $v_0=1+v_0/2=2$、$v_1=4+v_0/2=5$。

第一次改进只把状态一改为行动零，策略变为 $(0,0)$，值为 $(2,0)$。再看状态零：留在零的评价是二，到一的评价是一，所以改成行动一，策略变为 $(1,0)$，值为 $(1,0)$。这时再改进已无变化。

先改善状态一，下一轮它较低的长期代价才传播回状态零。每轮都应重新评估完整策略。

可运行实现

下面使用NumPy求解稠密线性方程。$P$ 形状为“状态、行动、下一状态”，$c$ 形状为“状态、行动”。代码不改输入，返回策略、值和评估历史；每轮时间 $O(n^3+m{n}^2)$，额外空间 $O(m{n}^2+n^2)$，包括复制的转移数组、不含返回的历史。浮点比较设置容差，因此实现给出容差内稳定策略，有限步精确最优的定理针对精确算术。

Python 3

import numpy as np

def policy_iteration(P, costs, gamma, max_iter=100):
    P = np.array(P, dtype=float, copy=True)
    c = np.array(costs, dtype=float, copy=True)
    if P.ndim != 3 or c.shape != P.shape[:2] or P.shape[0] != P.shape[2]:
        raise ValueError("incompatible dimensions")
    n, m = c.shape
    if n == 0 or m == 0 or not (0 <= gamma < 1):
        raise ValueError("nonempty model and discount below one required")
    if not np.isfinite(P).all() or not np.isfinite(c).all():
        raise ValueError("finite data required")
    if (P < 0).any() or not np.allclose(P.sum(axis=2), 1, rtol=0, atol=1e-12):
        raise ValueError("invalid transition rows")
    policy = np.zeros(n, dtype=int)
    policy[-1] = m - 1
    history = []
    for _ in range(max_iter):
        pp = P[np.arange(n), policy]
        v = np.linalg.solve(np.eye(n) - gamma * pp, c[np.arange(n), policy])
        history.append((policy.tolist(), v.tolist()))
        q = c + gamma * np.einsum("sak,k->sa", P, v)
        improved = policy.copy()
        for s in range(n):
            best = int(np.argmin(q[s]))
            if q[s, best] < q[s, policy[s]] - 1e-12:
                improved[s] = best
        if np.array_equal(improved, policy):
            return policy.tolist(), v.tolist(), history
        policy = improved
    raise RuntimeError("iteration limit reached")

P = [[[1, 0], [0, 1]], [[0, 1], [1, 0]]]
print(policy_iteration(P, [[1, 1], [0, 4]], 0.5))

变式。 把折扣系数改成零，长期代价就是当前成本：状态零两个行动平局，保持初始行动零；状态一选成本零的行动。最优策略不必唯一。若 $\gamma =1$，上述逆矩阵与压缩证明一般不再成立，随机最短路或平均成本模型需要另外的终止性等条件。