为什么价值迭代和策略迭代虽然具有不同的价值函数,却得到相似的策略?

人工智能 强化学习 比较 政策 价值迭代 政策迭代
2021-10-29 19:32:09

我正在尝试实现价值和策略迭代算法。我的策略迭代的价值函数看起来与价值迭代的价值大不相同,但从两者获得的策略非常相似。这怎么可能?这可能是什么原因?

2个回答

值迭代 (VI) 和策略迭代 (PI) 算法都保证收敛到最优策略,因此预计您会从两种算法中获得相似的策略(如果它们已经收敛)。

但是,他们这样做的方式不同。VI 可以看作是 PI 的截断版本。

让我首先说明这两种算法的伪代码(取自Barto 和 Sutton 的书),我建议您熟悉一下(但如果您实现了这两种算法,您可能已经熟悉它们)。

在此处输入图像描述

如您所见,策略迭代会多次更新策略,因为它交替进行策略评估步骤和策略改进步骤,其中更好的策略是从价值函数的当前最佳估计中得出的。

在此处输入图像描述

另一方面,值迭代只更新一次策略(最后)。

在这两种情况下,策略都以相同的方式从价值函数中导出。因此,如果您获得类似的策略,您可能会认为它们必然来自类似的最终价值函数。但是,一般情况下,情况可能并非如此,这实际上是价值迭代存在的动机,即你可以从非最优价值函数中推导出最优策略。

Barto 和 Sutton 的书提供了一个例子。请参见第 77 页的图 4.1(pdf 的第 99 页)。为了完整起见,这是该图的屏幕截图。

在此处输入图像描述

除了接受的答案之外,还有更多评论。

OP 说这两种算法具有不同的价值函数。这实际上并不精确,可能是混乱的根源。特别是,只有在策略迭代算法中,v是状态值函数,它是贝尔曼方程的解。然而,价值v在值迭代中不是状态值函数!这仅仅是因为它不是任何贝尔曼方程的一般解。那么,究竟是什么v在价值迭代中?请参阅我的另一个答案。

为什么不计算状态值的值迭代能找到最优策略?如果您将其视为解决贝尔曼最优性方程的简单数值迭代算法,则会更容易看出这一点。当我们分析贝尔曼最优方程时,该算法遵循收缩(或称为定点)定理。