策略迭代是一种用于求解马尔可夫决策过程（MDP）的动态规划算法。它交替进行两项操作：计算某一策略（强化学习）带来的长期结果，以及用能够改善这些结果的行动替换原有决策。对于动态规律已知的有限折扣问题，精确策略迭代经过有限次改进即可得到最优策略。它也是强化学习的一项基本组织原则；在强化学习中，评估和改进也可以借助经验和近似方法来完成。(andrew.cmu.edu)
数学设定
标准设定是一个离散时间马尔可夫决策过程，具有有限状态集 (S)、有限的可选行动集 (A(s))、转移概率 (P(s' \mid s,a)) 和期望即时奖励 (r(s,a))。马尔可夫性质意味着下一状态的分布取决于当前状态和行动，而不依赖此前的全部历史。折扣因子 (0\leq\gamma<1) 使较晚获得的奖励具有较低的权重。(introml.mit.edu)
平稳确定性策略在每次出现状态 (s) 时都选择行动 (\pi(s))。其价值函数是折扣奖励序列的期望值：
[ V^\pi(s)= \mathbb E_\pi!\left[ \sum_{t=0}^{\infty}\gamma^tR_{t+1} ,\middle|,S_0=s \right]. ]
当奖励有界时，折扣机制使这一无穷和有良好定义。目标是找到一个从每个状态出发都能使价值达到最大的策略。在这种有限折扣设定下，存在平稳确定性最优策略；达到最优并不需要随机选择行动。(introml.mit.edu)
策略评估
策略评估在不改变当前策略决策的情况下，计算其 (V^\pi)。该价值满足贝尔曼方程：
[ V^\pi(s)=r(s,\pi(s)) +\gamma\sum_{s'}P(s'\mid s,\pi(s))V^\pi(s'). ]
将奖励写成向量 (r^\pi)，并将依赖于策略的转移概率写成转移矩阵 (P^\pi)，可得
[ (I-\gamma P^\pi)V^\pi=r^\pi. ]
这里，(I) 是单位矩阵。由于 (\gamma<1)，系数矩阵可逆，因此评估可归结为求解一个线性方程组。其形式解为 (V^\pi=(I-\gamma P^\pi)^{-1}r^\pi)，不过实际实现可以直接求解方程组，而不必显式计算逆矩阵。(gradml.mit.edu)
另一种评估方法是反复应用固定策略下的更新：
[ v_{j+1}=r^\pi+\gamma P^\pi v_j. ]
这一更新在最大范数下是一个压缩映射，并收敛到唯一的不动点 (V^\pi)。数值实现通常在相邻两次价值估计的差异或贝尔曼残差低于容差时停止。这种截断评估不同于最简单的收敛定理所假设的精确评估。(web.mit.edu)
策略改进与算法
策略改进利用已评估的策略来比较各个行动：
[ Q^\pi(s,a)=r(s,a) +\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s'). ]
这一量包括采取行动 (a) 所获得的即时奖励，以及随后继续遵循 (\pi) 的价值。改进后的策略选择
[ \pi_{\mathrm{new}}(s)\in \operatorname*{arg,max}_{a\in A(s)}Q^\pi(s,a). ]
尽管这是一种单步比较，但其中的后续价值项包含未来奖励，而不只是即时收益。(gradml.mit.edu)
该过程可用伪代码表示如下：
选择一个初始确定性策略 π。
重复：
评估 π，得到 Vπ。
对每个状态 s：
选择使 Qπ(s, a) 最大的行动。
若 π(s) 已是最大化行动之一，则保留它。
若没有任何行动发生变化：
返回 π 和 Vπ。
用改进后的策略替换 π。
保留已有的最大化行动，可以避免在价值相同的决策之间进行不必要的切换。随后不断重复评估与改进，直到策略不再变化。(andrew.cmu.edu)
改进与终止
策略改进定理指出，采用贪心方式替换行动后，有
[ V^{\pi_{\mathrm{new}}}(s)\geq V^\pi(s) \qquad\text{对每个 }s\text{ 均成立}. ]
因此，改进步骤不会降低任何状态的价值。如果当前策略不是最优策略，精确的贪心改进会使至少一个状态的价值严格增加。如果当前策略相对于自身的价值已经是贪心策略，那么该价值就满足贝尔曼最优性方程，从而证明该策略是最优的。(web.mit.edu)
平稳确定性策略的数量是有限的，确切地说为 (\prod_{s\in S}|A(s)|)。因此，在精确评估并以一致方式处理并列最优行动的条件下，策略迭代会在有限次改进后终止。这一论证并不意味着每个问题都只需要少量迭代，也不能自动用于无折扣问题：终止型问题和平均奖励问题各自需要相应的假设与评估方程。(web.mit.edu)
与价值迭代的关系
价值迭代直接对价值估计反复应用最优性更新，不会在相邻两次更新之间完整评估一个策略。相比之下，策略迭代会在改变决策之前投入更多计算来进行评估。对于稠密转移，一轮改进需要考察每个状态、每个行动以及每个可能的后继状态；评估还需要求解线性方程组，或在固定策略下进行多轮遍历更新。稀疏转移可以大幅减少这些计算。因此，仅凭迭代次数无法判断哪种方法更快。(airr.mit.edu)
修正策略迭代只进行有限轮评估更新，就再次改进策略。它介于价值迭代计算成本较低的更新与策略迭代较完整的评估之间。评估的程度因而成为计算上的权衡，而不是只能选择完整评估或完全不评估。(airr.mit.edu)
近似与强化学习
经典策略迭代假设可以获得转移概率和期望奖励。广义策略迭代描述了评估与改进之间更广泛的相互作用，包括两者同时进行或以不同精度进行的过程。评估可以使用蒙特卡洛方法或时序差分学习，而演员—评论家方法则将策略调整与价值估计分开进行。(andrew.cmu.edu)
大型状态空间可能需要使用函数逼近，而不是用表格记录各状态的价值。近似误差和采样误差可能使简单的单调改进保证失效，因此近似策略迭代需要单独进行性能分析。有关相关算法的研究给出了将评估误差与最终策略性能联系起来的界限。(jmlr.csail.mit.edu)
参考来源
- Reinforcement Learning: An Introductionandrew.cmu.edu
- Neuro-Dynamic Programmingweb.mit.edu
- Value functions and Bellmangradml.mit.edu
- 11 Markov Decision Processes – 6.390 - Intro to Machine Learningintroml.mit.edu
- Performance Bounds for λ Policy Iteration and Application to the Game of Tetrisjmlr.csail.mit.edu