Value Iteration与Policy Iteration哪一种算法运行速度更快？

这俩算法根本没有绝对的谁快谁慢，你看到的两种完全相反的结论都没说错，只是各自的测试场景、前提假设不一样，脱离具体场景谈速度都是耍流氓。

策略迭代更快的适用情况 #

• 状态空间大但动作空间很小的时候，策略迭代的开销优势非常明显。
  策略迭代分两步：策略评估阶段固定当前策略，每个状态只需要计算当前策略选定的那1个动作的期望收益，单轮复杂度只有O(S²)；只有每次做策略改进的时候，才需要遍历所有状态的所有动作，复杂度是O(S²A)。如果整个迭代过程只需要3~5轮策略更新就收敛到最优策略，总计算量比需要跑几十上百轮的值迭代小很多。
• 收敛阈值设得极严的时候，策略迭代的终止逻辑更高效。
  值迭代的终止条件是值函数的变化量小于阈值，很多时候最优策略早在值函数完全收敛前很多轮就已经确定了，后面跑的所有值更新全是冗余开销；但策略迭代只要某一轮策略改进后，所有状态的动作选择和上一轮完全一致，就直接终止，根本不需要等值函数磨到完全收敛，少跑很多无用步骤。

值迭代更快的适用情况 #

• 动作空间大、策略需要迭代很多轮才能收敛到最优的时候，值迭代的优势很大。
  经典版本的策略迭代每一轮都要把当前次优策略的值函数评估到完全收敛，要是策略本身还在反复调整、离最优还差得远，这些针对次优策略的全量评估全是白费功夫。
• 值迭代本质上把策略评估和策略改进合并成了单步操作：每轮只做一次值更新，直接对每个状态取所有动作的最大值作为新的状态值，不需要等单轮策略评估跑收敛。在很多中等规模的MDP场景里，值迭代的总计算步数比策略迭代"多轮全量评估+改进"的总步数少得多，实际跑起来快很多。

• 如果你的场景动作空间极小（比如网格世界只有上下左右4个动作），最优策略通常几轮就能收敛，优先试策略迭代，大概率速度更快。
• 如果场景动作空间很大（比如机器人控制、推荐系统这类动作数成百上千的场景），策略收敛需要的轮数多，优先试值迭代；也可以直接用截断式策略迭代——每轮策略评估不跑到完全收敛，只跑固定k步更新就进入策略改进环节，相当于两个算法的折中，实际表现往往比两个经典原版都好。
• 别死磕理论时间复杂度，那都是最坏情况的上界，实际运行时状态转移矩阵的稀疏度、代码优化程度、收敛阈值的设置对运行速度的影响，比理论复杂度的差异大得多。

内容的提问来源于stack exchange，提问作者Osama Ahmad