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

Question

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

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

我的疑问是，如果您在 PI 中选择一个随机策略 π，即使我们选择多个随机策略，如何保证它是最优策略。

Answer 1

让我们并排看看它们。比较的关键部分被突出显示。图来自 Sutton 和 Barto 的书：强化学习：简介。

关键点：

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

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

我想混乱主要来自所有这些有点相似的术语，这也让我感到困惑。

Answer 2

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

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

从某种意义上说，两种算法的工作原理相同，可以看作是广义策略迭代的两种情况。然而，最优性贝尔曼算子包含一个最大算子，它是非线性的，因此具有不同的特征。此外，可以在纯值迭代和纯策略迭代之间使用混合方法。

Answer 3

基本的区别是——

在策略迭代中——你随机选择一个策略并找到它对应的价值函数，然后根据之前的价值函数找到一个新的（改进的）策略，依此类推，这将导致最优策略。

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

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

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

Answer 4

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

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

在策略迭代 (PI) 中，此最大操作在步骤 1（策略评估）中被省略，只需遵循中间策略来选择动作。

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

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

Answer 5

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

原因很简单，正如您已经知道的，贝尔曼方程用于求解给定策略的价值函数。由于我们可以直接求解最优策略的价值函数，因此求解当前策略的价值函数显然是浪费时间。

至于你关于 PI 收敛性的问题，我想你可能会忽略这样一个事实，即如果你改进了每个信息状态的策略，那么你改进了整个游戏的策略。这也很容易证明，如果你熟悉 Counterfactual Regret Minimization——每个信息状态的后悔之和形成了整体后悔的上界，因此最小化每个状态的后悔将最小化整体后悔，即导致最优策略。