3

我正在学习 SARSA 算法的实现并且有一个问题。我了解一般的“学习”步骤采取以下形式：

机器人 (r) 处于状态 s。有四种可用的操作：

North (n), East (e), West (w) and South (s)

这样的动作列表，

a = {n,w,e,s}

机器人随机选择一个动作，并更新如下：

Q(a,s) = Q(a,s) + L[r + DQ(a',s1) - Q(a,s)]

其中L是学习率，r是与 相关的奖励(a,s)，是新状态下Q(s',a')动作的预期奖励，是折扣因子。a's'D

首先，我不理解这个术语的作用 - Q(a,s)，为什么我们要重新减去当前的 Q 值？

其次，在选择动作时a，a'为什么这些必须是随机的？我知道在某些实现或 SARSA 中，所有可能Q(s', a')的因素都被考虑在内，并选择了最高值。（我相信这是 Epsilon-Greedy？）为什么不为此也选择Q(a,s)要更新的值？或者为什么不更新所有Q(a,s)的当前s？

最后，为什么 SARSA 仅限于一步前瞻？为什么，说，不也研究一个假设Q(s'',a'')？

我想总的来说，我的问题归结为是什么让 SARSA 比另一种呼吸优先或深度优先搜索算法更好？

4

1 回答 1

9

为什么要减去 Q(a,s)？ r + DQ(a',s1)是我们s通过采取行动达到状态所获得的奖励a。理论上，这是Q(a,s)应该设置的值。但是，我们不会总是在从 action 到达状态 s 后采取相同的行动a，并且与进入未来状态相关的奖励将在未来发生变化。所以我们不能只设置Q(a,s)等于r + DQ(a',s1)。相反，我们只想将其推向正确的方向，以便最终收敛到正确的值。因此，我们查看预测中的误差，这需要从 中Q(a,s)减去r + DQ(a',s1)。这是我们需要更改Q(a,s)的数量，以使其与我们刚刚观察到的奖励完全匹配. 由于我们不想一次完成所有操作（我们不知道这是否总是最好的选择），我们将这个错误项乘以学习率，l然后将此值添加到Q(a,s)一个更渐进的收敛到正确的值。`

为什么我们随机选择动作？不总是以确定性的方式选择下一个状态或动作的原因基本上是我们对哪个状态最好的猜测可能是错误的。当我们第一次开始运行 SARSA 时，我们有一个满是 0 的表。我们通过探索状态空间的这些区域并发现与它们相关的奖励将非零值放入表中。结果，我们探索过的并不可怕的东西看起来比我们没有探索过的东西更好。也许是的。但也许我们尚未探索的东西实际上比我们已经看到的要好得多。这被称为探索与利用问题——如果我们只是继续做我们知道有效的事情，我们可能永远找不到最佳解决方案。随机选择下一步可确保我们看到更多选项。

为什么我们不能从给定状态采取所有可能的行动？这将迫使我们基本上在每次迭代时查看整个学习表。如果我们使用 SARSA 之类的东西来解决问题，那么表格可能太大而无法在合理的时间内完成。

为什么SARSA只能做一步前瞻？好问题。SARSA 背后的想法是，它通过表格向后传播预期奖励。折扣因子 D 确保在最终解决方案中，您将获得逐渐增加的预期奖励，从而获得最佳奖励。如果你随机填写表格，这并不总是正确的。这不一定会破坏算法，但我怀疑它会导致效率低下。

为什么 SARSA 比搜索更好？同样，这归结为效率问题。任何人使用学习算法而不是搜索算法的根本原因是，一旦你有太多的状态和动作选项，搜索算法就会太慢。为了知道从任何其他状态动作对中采取的最佳动作（这是 SARSA 计算的），您需要从每个节点搜索整个图。这将花费 O(s*(s+a)) 时间。如果你试图解决现实世界的问题，那通常太长了。

于 2015-04-26T16:46:47.073 回答