我正在学习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')是从新状态s'中采取动作a'的预期奖励，D是折扣因子。

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

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

最后，为什么SARSA仅限于一步前瞻？为什么不也考虑假设的Q(s'',a'')？

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

回答：

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

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

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

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

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