价值迭代和策略迭代有什么区别？

Question

在强化学习中，“策略迭代”和“值迭代”有什么区别？

据我所知，在值迭代中，您使用贝尔曼方程求解最优策略，而在策略迭代中，您随机选择一个策略π，并找到该策略的奖励。

我的疑问是，如果在策略迭代中选择了随机策略π，即使我们选择了多个随机策略，它如何保证是最优策略？

- Arslán

---

在像 https://ai.stackexchange.com/、https://stats.stackexchange.com 或者 https://datascience.stackexchange.com 这样的网站上提问会更加合适。 - nbro

我投票关闭此问题，因为机器学习（ML）理论问题不适合在Stack Overflow上讨论 - Cross-Validated的礼品包装候选人。 - Daniel F

Answer 1

让我们并排看一下它们。高亮显示了比较的关键部分。这些数字来自Sutton和Barto的书：强化学习导论。

关键点：

1. 策略迭代包括：策略评估 + 策略改进，两者反复迭代直到策略收敛。
2. 价值迭代包括：找到最优价值函数 + 一次策略提取。因为一旦价值函数是最优的，那么从中提取的策略也应该是最优的（即已收敛），所以这两个不需要重复执行。
3. 找到最优价值函数也可以看作是策略改进（由于最大值）和截断策略评估（在所有状态上只进行一次扫描而不管是否收敛）的组合。
4. 策略评估和找到最优价值函数的算法非常相似，除了一个max操作（如所示）。
5. 同样，策略改进和策略提取的关键步骤相同，只是前者涉及稳定性检查。

根据我的经验，策略迭代比价值迭代更快，因为策略收敛比价值函数更快。我记得这也在书中有描述。

我想混淆主要来自这些有些相似的术语，这也在之前让我感到困惑。

- zyxue

---

我同意政策迭代在较少迭代次数内收敛，并且我也在多个地方读到它更快的事实。我在Burlap中使用两种方法进行了一些简单的盒子世界和迷宫解决实验。我发现价值迭代执行了更多的迭代，但需要更少的时间来达到收敛。你的结果可能会有所不同。 - Ryan

@Chrom，你应该读反了。这是书中的一句话：“策略迭代通常在很少的迭代次数内收敛。这可以通过图4.1中的示例来说明”，摘自书籍第65页2017nov5版本。 - zyxue

是的，我已经尝试过几种不同风格的网格世界。我只是想指出，在迭代次数方面，“更快”可能会更有利于策略迭代（PI）。但是，以秒为单位的“更快”可能实际上更适合价值迭代（VI）。 - Ryan

澄清一下，策略迭代需要的迭代次数较少，但计算复杂度比价值迭代高；哪种方法更快取决于具体环境。 - R.F. Nelson

我知道这篇文章已经过时了，但我强烈建议你查看这个链接（https://medium.com/@m.alzantot/deep-reinforcement-learning-demysitifed-episode-2-policy-iteration-value-iteration-and-q-978f9e89ddaa）这个链接提供了一些代码，并且让我更容易理解了。 - tandem

Answer 2

在政策迭代算法中，您首先从随机策略开始，然后找到该策略的价值函数（策略评估步骤），然后基于以前的价值函数找到一个新的（改进的）策略，依此类推。在这个过程中，每个策略都保证严格优于以前的那一个（除非它已经是最优的）。给定一个策略，可以使用贝尔曼算子获取其价值函数。

在价值迭代中，您从一个随机价值函数开始，然后在迭代过程中找到一个新的（改进的）价值函数，直到达到最优价值函数为止。请注意，您可以轻松地从最优价值函数中推导出最优策略。此过程基于最优贝尔曼算子。

某种意义上，两种算法共享相同的工作原理，并且它们可以被视为广义策略迭代的两种情况。但是，最优贝尔曼算子包含max运算符，它是非线性的，因此具有不同的特征。此外，可以使用纯价值迭代和纯策略迭代之间的混合方法。

- Pablo EM

---

这是一个很好的描述。让我补充一下，在策略迭代中使用贝尔曼期望方程，在值迭代中使用墨尔曼最大方程。对于值迭代来说，可能需要较少的迭代次数，但每次迭代的工作量可能会很大。对于策略迭代来说，则需要更多的迭代次数。 - Shamane Siriwardhana

策略迭代中没有最大算子吗？否则，如何基于新的价值函数更新策略？ - hzh

不，SARSA算法是策略迭代的典型示例。正如您可以在此伪代码中看到的那样（http://incompleteideas.net/book/ebook/node64.html），价值函数更新不包含任何最大操作符。然而，如果您指的是从价值函数中选择最佳动作（即贪婪动作）的最大操作符，那么在这个过程中确实存在一个最大操作符。 - Pablo EM

Answer 3

基本区别是 -

在策略迭代中 - 您随机选择一个策略并找到相应的值函数，然后基于先前的值函数找到一个新的（改进的）策略，以此类推，这将导致最优策略。

在值迭代中 - 您随机选择一个值函数，然后通过迭代过程找到一个新的（改进的）值函数，直到达到最优值函数，然后从该最优值函数推导出最优策略。

策略迭代的工作原理是“策略评估 - > 策略改进”。

值迭代的工作原理是“最优值函数 - > 最优策略”。

- Himanshu Gupta

Answer 4

就我个人而言，与 @zyxue 的想法相反，VI通常比PI要快得多。原因非常简单，正如您所知，Bellman方程用于解决给定策略的价值函数。由于我们可以直接解决最优策略的价值函数，因此解决当前策略的价值函数显然是浪费时间。

至于您关于PI收敛性的问题，我认为您可能忽视了这样一个事实：如果您改进每个信息状态的策略，那么您将改进整个游戏的策略。这也很容易证明，如果您熟悉反事实后悔最小化——每个信息状态的后悔总和形成了总后悔的上限，因此减少每个状态的后悔将减少总后悔，从而导致最优策略。

- T. Jiang

Answer 5

每次值迭代 (VI) 中速度的主要差别是由于最大操作。

在 VI 中，每个状态将只使用一个动作（具有最大效用值）来计算更新的效用值，但它必须先计算所有可能动作的值，以便通过贝尔曼方程找到这个动作。

在策略迭代 (PI) 中，在第 1 步（策略评估）中省略了此 max 操作，只需按照中间策略选择动作即可。

如果有 N 种可能的动作，VI 必须为每个状态计算 N 次贝尔曼方程，然后取最大值，而 PI 只需计算一次（对于当前策略指定的动作）。

但是在 PI 中，仍有一个策略改进步骤使用最大运算符，与 VI 中的步骤一样慢，但由于 PI 收敛的迭代次数较少，因此此步骤不会像 VI 中那样经常发生。

- bcbertyboy