策略迭代 / 价值迭代

环境模型已知时，反复更新价值或策略来求最优策略的两种经典动态规划算法。

策略迭代和价值迭代是求解马尔可夫决策过程（描述状态、动作、奖励和转移的数学框架）的两种经典动态规划算法，前提是转移概率和奖励函数都已知。价值迭代由 Bellman 在 1957 年提出，反复用贝尔曼最优方程更新每个状态的价值，收敛后按价值挑动作。策略迭代由 Howard 在 1960 年提出，交替做两步：策略评估（算出当前策略下各状态的价值）和策略改进（每个状态改选价值最高的动作），直到策略不再变化。真实机器人的状态连续、模型未知，没法直接套用，但 Q 学习、演员-评论家等算法都可以看成它们在采样和函数近似下的变体。

例子在一个 4×4 的网格迷宫里，每走一步奖励 -1、走到终点结束，且移动结果确定。价值迭代反复更新各格的价值，收敛后每格的价值等于它到终点最短步数的相反数，沿价值升高的方向走就是最短路径。

也叫

动态规划、Dynamic Programming、值迭代

相关

马尔可夫决策过程、贝尔曼方程、价值函数、Q 学习、基于模型的强化学习、策略梯度

来源

Wikipedia: Markov decision process（Algorithms 一节）
Wikipedia: Bellman equation