SARSA实现

Question

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

机器人(r)在美国。有四种行动：

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')都会被考虑进去，并选择最高的值。(我相信这是贪婪的？)为什么不对此也选择更新哪个Q(a,s)值呢？或者为什么不更新当前Q(a,s)的所有s？

最后，为什么SARSA只限于一步向前看？为什么，比方说，也不研究假设的Q(s'',a'')？

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

Answer 1

，为什么我们要减去Q(a，s)? r + DQ(a',s1)是我们在这个过程中得到的奖励，我们通过采取a的行动到达州s。理论上，这是Q(a,s)应该设置的值。然而，在从操作a到达状态后，我们不会总是采取相同的操作，而与未来状态相关的奖励在未来将发生变化。所以我们不能把Q(a,s)设为r + DQ(a',s1)。相反，我们只想把它推向正确的方向，这样它最终会收敛到正确的值上。所以我们来看看预测中的错误，这需要从Q(a,s) r + DQ(a',s1)**.中减去。这是我们需要改变** Q(a,s) 的数量，以使其与我们刚刚观察到的的奖励完全匹配。由于我们不想一次做到这一点(我们不知道这是否总是最好的选择)，所以我们将这个错误项乘以学习速率l，并将这个值添加到Q(a,s) for 中，在正确的.`上逐步收敛。

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

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

为什么SARSA只能一步向前看？的问题很好。SARSA背后的想法是，它通过表格向后传播预期的回报。折扣因子D，确保在最终的解决方案中，你将有一个逐步增加的预期回报，最终得到最好的回报。如果你随意填这张桌子，那就不一定是真的。这并不一定会破坏算法，但我怀疑会导致效率低下。

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