机器算法验证 - 为什么值迭代会在**有限**步数内收敛到最优值函数？ - 吾爱随笔录

回忆一下强化学习（特别是符号）：

假设我们有一个有限的 MDP。为什么值迭代会在有限的步数内收敛到最优值函数？我们可以用变量（可能是状态的数量等）来精确地渐近地表达这个运行时间吗？

跟大家分享一下我的想法：

但首先召回值迭代：

在此处输入图像描述

回想一下贝尔曼方程：

在此处输入图像描述

如果我们接受贝尔曼方程实际上是最优的，那么为什么值迭代一旦收敛（如果它收敛）就会达到最优值函数就很明显了。一旦收敛，则：

V^{*} (s) = R (s) + \underset{a \in A}{m a x} \sum_{s^{'} \in S} P_{s a} (s^{'}) V^{*} (s^{'})

$V^*(s) = R(s) + \underset{a \in A}{max} \sum_{s' \in S} P_{sa}(s')V^*(s')$

应该是真的，所以我们完成了！但是，它是否达到这一点并不完全清楚，即更新规则是否这样做（即使在无限数量的步骤中）。

我希望以下是真的（但我不确定）：

更新规则只会增加。 $V(s)$

如果这是真的，那么很明显它最终会达到最大。然而，尚不清楚即使这是真的，它是否会在有限的步骤甚至无限的步骤中完成。很高兴看到这一点的证明，有人有吗？ $V(s)$

每次我尝试它时，我都会遇到这个问题，更新规则真的有帮助吗？

直觉上，它试图强迫贝尔曼方程为真，但是，它最终真的让它成为真的吗？多久时间？运行时间是多少？

此外，更新可以通过不同的方式实现，因此请选择您想要的任何方式。要了解我的意思，请阅读以下内容：

在此处输入图像描述