SARSA实施
SARSA Implementation
我正在学习 SARSA 算法实现并有一个问题。我知道一般的 "learning" 步骤采用以下形式：
机器人（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) 值？或者为什么不更新当前 s 的所有 Q(a,s)？
最后，为什么 SARSA 仅限于一步前瞻？比如说，为什么不也研究一个假设的 Q(s'',a'')？
我想总的来说我的问题归结为是什么让 SARSA 比另一种呼吸优先或深度优先搜索算法更好？
为什么我们要减去Q(a,s)？ r + DQ(a',s1)是我们在这个运行上得到的奖励，通过从到达状态s 通过采取行动 a。理论上，这是 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) 以便 逐渐收敛到正确的值 。`
为什么我们随机选择动作？不总是以确定性方式选择下一个状态或动作的原因基本上是我们对哪个状态的猜测最好可能是错的。当我们第一次启动 运行ning SARSA 时，我们有一个全是 0 的 table。我们通过探索这些状态区域 space 并发现有与之相关的奖励，将非零值放入 table。因此，我们探索过的并不可怕的东西看起来会比我们没有探索过的东西更好。也许是。但也许我们尚未探索的事物实际上比我们已经看到的要好得多。这就是所谓的 探索与利用问题 - 如果我们只是继续做我们知道有效的事情，我们可能永远找不到最好的解决方案。 随机选择后续步骤可确保我们看到更多选项。
为什么我们不能从给定状态采取所有可能的行动？ 这将迫使我们基本上在每次迭代时查看整个学习 table。如果我们使用 SARSA 之类的工具来解决问题，table 可能太大 无法在合理的时间内完成此操作。
为什么SARSA只能做一步look-ahead？好问题。 SARSA 背后的想法是它通过 table 向后传播预期奖励。折扣因子 D 确保在最终解决方案中，您将拥有逐渐增加的预期奖励，从而获得最佳奖励。如果您随意填写 table，则情况并非总是如此。这不一定会破坏算法，但我怀疑它会导致效率低下。
为什么 SARSA 比搜索更好？ 同样，这归结为效率问题。任何人都使用学习算法而不是搜索算法的根本原因是，一旦状态和动作有太多选项，搜索算法就太慢了。为了知道从任何其他状态动作对（这是 SARSA 计算的）采取的最佳动作，您需要从每个节点搜索整个图。这将花费 O(s*(s+a)) 时间。如果你正在尝试解决现实世界的问题，那通常太长了。
我正在学习 SARSA 算法实现并有一个问题。我知道一般的 "learning" 步骤采用以下形式：
机器人（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) 值？或者为什么不更新当前 s 的所有 Q(a,s)？
最后，为什么 SARSA 仅限于一步前瞻？比如说，为什么不也研究一个假设的 Q(s'',a'')？
我想总的来说我的问题归结为是什么让 SARSA 比另一种呼吸优先或深度优先搜索算法更好？
为什么我们要减去Q(a,s)？ r + DQ(a',s1)是我们在这个运行上得到的奖励，通过从到达状态s 通过采取行动 a。理论上，这是 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) 以便 逐渐收敛到正确的值 。`
为什么我们随机选择动作？不总是以确定性方式选择下一个状态或动作的原因基本上是我们对哪个状态的猜测最好可能是错的。当我们第一次启动 运行ning SARSA 时，我们有一个全是 0 的 table。我们通过探索这些状态区域 space 并发现有与之相关的奖励，将非零值放入 table。因此，我们探索过的并不可怕的东西看起来会比我们没有探索过的东西更好。也许是。但也许我们尚未探索的事物实际上比我们已经看到的要好得多。这就是所谓的 探索与利用问题 - 如果我们只是继续做我们知道有效的事情，我们可能永远找不到最好的解决方案。 随机选择后续步骤可确保我们看到更多选项。
为什么我们不能从给定状态采取所有可能的行动？ 这将迫使我们基本上在每次迭代时查看整个学习 table。如果我们使用 SARSA 之类的工具来解决问题，table 可能太大 无法在合理的时间内完成此操作。
为什么SARSA只能做一步look-ahead？好问题。 SARSA 背后的想法是它通过 table 向后传播预期奖励。折扣因子 D 确保在最终解决方案中，您将拥有逐渐增加的预期奖励，从而获得最佳奖励。如果您随意填写 table，则情况并非总是如此。这不一定会破坏算法，但我怀疑它会导致效率低下。
为什么 SARSA 比搜索更好？ 同样，这归结为效率问题。任何人都使用学习算法而不是搜索算法的根本原因是，一旦状态和动作有太多选项，搜索算法就太慢了。为了知道从任何其他状态动作对（这是 SARSA 计算的）采取的最佳动作，您需要从每个节点搜索整个图。这将花费 O(s*(s+a)) 时间。如果你正在尝试解决现实世界的问题，那通常太长了。