策略迭代与值迭代

策略迭代交替进行策略评估与贪心改进；值迭代直接迭代 Bellman 最优算子。本章给出两者的收敛性、复杂度，以及广义策略迭代（GPI）这一统一视角。

已知模型时的动态规划

本卷假设转移 $P$ 与奖励 $R$ 已知——这是动态规划（DP）的设定，也是唯一能"精确求解"的情形。已知模型时，价值函数可以按第 $k$ 步对全部状态同步更新：

$V_{k+1}(s) = \mathcal{T}V_k(s) = \max_a \sum_{s'} P(s' \mid s, a)\,\big[\,R(s,a) + \gamma V_k(s')\,\big].$

每次扫描的代价是 $O(\lvert \mathcal{S} \rvert^2 \lvert \mathcal{A} \rvert)$ （对每个状态、每个动作、每个后继状态），这是 DP 方法的规模瓶颈：状态数一大，全表扫描不可行。

策略迭代

策略迭代（policy iteration）交替两步：

策略评估：对当前策略 $\pi_k$ 解 Bellman 期望方程。线性方程组 $V^\pi = R^\pi + \gamma P^\pi V^\pi$ 可以精确求解（ $O(\lvert \mathcal{S} \rvert^3)$ ），或迭代到收敛；
策略改进： $\pi_{k+1}(s) = \arg\max_a \sum_{s'} P(s' \mid s,a)\,[R + \gamma V^{\pi_k}(s')]$ 。

性质：每轮改进不会更差（ $V^{\pi_{k+1}} \ge V^{\pi_k}$ 逐状态成立），且策略数有限、严格改进至多有限次，因此有限步收敛到最优策略。实践中常在几十轮内收敛——步数少，但每步的精确评估很贵。

值迭代

值迭代（value iteration）不维护显式策略，直接迭代 Bellman 最优算子 $V_{k+1} = \mathcal{T}V_k$ 。由压缩映射性质（→ 价值函数与 Bellman 方程），从任何初值出发都以几何速度收敛到 $V^*$ ：

$\lVert V_k - V^* \rVert_\infty \le \gamma^k\, \lVert V_0 - V^* \rVert_\infty.$

把误差压到 $\epsilon$ 需要 $k = O\big(\log(1/\epsilon) / \log(1/\gamma)\big)$ 次扫描； $\gamma$ 越接近 1 收敛越慢。中途任意时刻对 $V_k$ 贪心即得到近似策略。

两者的比较

	策略迭代	值迭代
外层步数	少（常几十轮）	多（ $\gamma$ 接近 1 时显著变多）
每步代价	贵（精确评估解线性方程组）	便宜（一次全表扫描）
收敛保证	有限步终止	渐近收敛（几何速度）

两者不是非此即彼，而是同一个模式上的两个端点。

广义策略迭代（GPI）

Sutton & Barto 用 GPI 统一视角描述几乎所有 RL 算法：任何时刻都持有一个近似的 $(V, \pi)$ ，评估步让 $V$ 逼近 $\pi$ 的真实价值，改进步让 $\pi$ 对 $V$ 贪心；两股力互相拉扯，最终同时收敛到 $V^*$ 与 $\pi^*$ 。这个视角的解释力在于：DP、蒙特卡洛、时序差分、Actor-Critic、甚至 MCTS（搜索是改进步、训练是评估步，→ MCTS 与 AlphaZero），都可以读作"评估与改进以不同方式交替"。

异步 DP 与优先级扫描

同步更新对全表扫描，代价大且做了大量无用功（远离奖励的区域更新价值不大）。异步 DP 只更新有变化传播到的状态；优先级扫描（prioritized sweeping）进一步维护一个按"预测变化量"排序的队列，每次只更新前驱变化最大的状态。这些思想在深度时代以优先经验回放的形式回归（→ DQN 及其改进）。

本章要点

策略迭代步数少但每步贵，值迭代反之
GPI：评估与改进交替进行、不必做到收敛
异步 DP 与优先级扫描