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

Question

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

根据我的理解，在价值迭代中，您使用Bellman方程来求解最优策略，而在策略迭代中，您随机选择策略π，并找到该策略的奖励。

我怀疑的是，如果你在PI中选择随机策略π，即使我们选择了几个随机策略，它如何保证成为最优策略。

Answer 1

让我们并排看看它们。强调了比较的关键部分。数据来自Sutton和Barto的书：强化学习：简介。

要点：

1. 政策迭代包括：政策评估+政策改进，两者反复重复，直到政策收敛。
2. 值迭代包括：找到最优值函数+一个策略提取。这两者没有重复，因为一旦价值函数是最优的，那么它之外的政策也应该是最优的（即收敛）。
3. 寻找最优值函数也可以看作是策略改进（由于最大值）和截断策略评估（在所有状态的一次扫描之后重​​新分配v_（s）而不管收敛的组合）。
4. 除了最大操作（如突出显示）之外，策略评估和查找最佳值函数的算法非常相似
5. 同样，政策改进和政策提取的关键步骤是相同的​​，除了前者涉及稳定性检查。

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

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

Answer 2

在策略迭代算法中，您从随机策略开始，然后找到该策略的值函数（策略评估步骤），然后根据先前的值函数找到新的（改进的）策略，依此类推。在这个过程中，每个策略都保证是对前一个策略的严格改进（除非它已经是最优的）。给定策略，可以使用Bellman运算符获得其值函数。

在值迭代中，您从随机值函数开始，然后在迭代过程中找到新的（改进的）值函数，直到达到最优值函数。请注意，您可以从最佳值函数轻松派生出最优策略。该过程基于贝尔曼算子的最优性。

从某种意义上说，两种算法都有相同的工作原理，它们可以被视为generalized policy iteration的两种情况。然而，Bellman算子的最优性包含max运算符，它是非线性的，因此具有不同的特征。此外，可以在纯值迭代和纯策略迭代之间使用混合方法。

Answer 3

基本的区别是 -

在策略迭代中 - 您随机选择策略并查找与其对应的值函数，然后根据先前的值函数找到新的（改进的）策略，依此类推，这将导致最优策略。

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

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

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

Answer 4

就我而言，与@zyxue的想法相反，VI通常比PI快得多。

原因非常简单，正如您所知，Bellman方程用于解决给定策略的价值函数。由于我们可以直接解决最优政策的价值函数，解决当前政策的价值函数显然是浪费时间。

至于关于PI收敛性的问题，我认为你可能会忽略这样一个事实，即如果你改进每个信息状态的策略，那么你就会改进整个游戏的策略。这也很容易证明，如果你熟悉反事实后悔最小化 - 每个信息状态的遗憾总和已形成整体遗憾的上限，从而最大限度地减少每个州的遗憾将最大限度地减少整体后悔，导致最优政策。