122

虽然我知道SARSA是 on-policy 而Q-learning是 off-policy，但在查看他们的公式时（对我来说）很难看出这两种算法之间有什么区别。

根据《强化学习：简介》一书（Sutton 和 Barto 着）。在 SARSA 算法中，给定一个策略，对应的动作值函数 Q（在状态 s 和动作 a，时间步长 t），即 Q(s t , a t )，可以更新如下

Q(s t , a t ) = Q(s t , a t ) + α*(r t + γ*Q(s t+1 , a t+1 ) - Q(s t , a t ))

另一方面，Q-learning 算法的更新步骤如下

Q(s t , a t ) = Q(s t , a t ) + α*(r t + γ*max a Q(s t+1 , a) - Q(s t , a t ))

也可以写成

Q(s t , a t ) = (1 - α) * Q(s t , a t ) + α * (r t + γ*max a Q(s t+1 , a))

其中 γ (gamma) 是折扣因子，r t是在时间步 t 从环境收到的奖励。

这两种算法的区别在于 SARSA 只查找下一个策略值，而 Q-learning 查找下一个最大策略值吗？

TLDR（和我自己的答案）

感谢自从我第一次提出这个问题以来所有回答这个问题的人。我用 Q-Learning 制作了一个github repo，并凭经验理解了其中的区别。这一切都取决于您如何选择下一个最佳操作，从算法的角度来看，这可以是平均值、最大或最佳操作，具体取决于您选择实现它的方式。

另一个主要区别是这种选择何时发生（例如，在线与离线）以及如何/为什么会影响学习。如果您在 2019 年阅读这篇文章并且更喜欢动手实践，那么玩 RL 玩具问题可能是了解差异的最佳方式。

最后一个重要的注意事项是，Suton 和 Barto 以及 Wikipedia对于下一个状态的最佳/最大动作和奖励经常有混合、混淆或错误的公式表示：

r(t+1)

实际上是

r(t)

希望这可以帮助任何人陷入困境。

4

7 回答 7

110

当我学习这部分的时候，我也觉得很困惑，所以我把 R.Sutton 和 AGBarto 的两个伪代码放在一起，希望能更清楚地区分。

在此处输入图像描述

蓝色框突出显示了两种算法实际不同的部分。数字突出了稍后将解释的更详细的差异。

TL;NR：

|             | SARSA | Q-learning |
|:-----------:|:-----:|:----------:|
| Choosing A' |   π   |      π     |
| Updating Q  |   π   |      μ     |

其中 π 是一个 ε-贪婪策略（例如 ε > 0 进行探索），μ 是一个贪婪策略（例如 ε == 0，不进行探索）。

  1. 鉴于 Q-learning 使用不同的策略来选择下一个动作 A' 和更新 Q。换句话说，它试图在遵循另一个策略 μ 的同时评估 π，因此它是一种离策略算法。

  2. 相比之下，SARSA 一直使用 π，因此它是一种 on-policy 算法。

更详细的解释：

  1. 两者之间最重要的区别是每次操作后如何更新 Q。SARSA 使用 Q' 完全遵循 ε-greedy 策略，因为 A' 是从中得出的。相比之下，Q-learning 在下一步的所有可能动作中使用最大 Q'。这使它看起来像遵循 ε=0 的贪婪策略，即在这部分没有探索。

  2. 然而，当实际采取行动时，Q-learning 仍然使用从 ε-greedy 策略中采取的行动。这就是为什么“选择 A ...”在重复循环中的原因。

  3. 遵循 Q-learning 中的循环逻辑，A' 仍然来自 ε-greedy 策略。

于 2017-01-02T01:51:47.580 回答
68

是的，这是唯一的区别。On-policy SARSA 学习与其遵循的策略相关的动作值，而 off-policy Q-Learning 则相对于贪婪策略进行学习。在一些常见的条件下，它们都收敛到实际价值函数，但速度不同。Q-Learning 趋于收敛速度较慢，但​​能够在更改策略的同时继续学习。此外，Q-Learning 在与线性近似结合时不能保证收敛。

实际上，在 ε-greedy 策略下，Q-Learning 计算 Q(s,a) 与最大动作值之间的差异，而 SARSA 计算 Q(s,a) 与平均动作的加权和之间的差异值和最大值：

Q-Learning：Q(s t+1 ,a t+1 ) = max a Q(s t+1 ,a)

SARSA：Q(s t+1 ,a t+1 ) = ε·mean a Q(s t+1 ,a) + (1-ε)·max a Q(s t+1 ,a)

于 2011-07-28T00:39:51.623 回答
43

数学上有什么区别？

正如大多数其他答案中已经描述的那样，两次更新之间的数学差异确实在于，当更新状态-动作对(S t , A t )的Q值时：

  • Sarsa 使用行为策略（意思是代理在环境中产生经验的策略，通常是epsilon -greedy）选择一个额外的动作A t+1，然后使用Q(S t+1 , A t +1 )（按gamma折现）作为更新目标计算中的预期未来回报。
  • Q- learning 不使用行为策略来选择附加动作A t+1。相反，它将更新规则中的预期未来回报估计为max A Q(S t+1 , A)。这里使用的max运算符可以被视为“遵循”完全贪婪的策略。代理实际上并没有遵循贪婪的政策；它只是在更新规则中说，“假设我从现在开始遵循贪婪策略，那么我预期的未来回报是多少？”。

这在直觉上意味着什么？

如其他答案所述，上述差异使用技术术语意味着Sarsa是一种on-policy学习算法，而Q-learning是一种off-policy学习算法。

在有限的情况下（给定无限的时间来产生经验和学习），并且在一些额外的假设下，这意味着 Sarsa 和 Q-learning 收敛到不同的解决方案/“最佳”策略：

  • Sarsa将收敛到一个最优的解决方案，假设我们继续遵循用于产生体验的相同策略。这通常是一个带有一些（相当“愚蠢”）随机性元素的策略，比如epsilon -greedy，因为否则我们无法保证我们会收敛到任何东西。
  • Q-Learning将收敛到一个最优解，假设在产生经验和训练之后，我们切换到贪婪策略。

何时使用哪种算法？

在我们关心智能体在学习/产生经验过程中的表现的情况下，像Sarsa这样的算法通常更可取。例如，考虑代理是一个昂贵的机器人，如果它掉下悬崖就会摔断。我们不想让它在学习过程中经常掉下来，因为它很贵。因此，我们关心它在学习过程中的表现。然而，我们也知道有时我们需要它随机行事（例如 epsilon-greedy）。这意味着机器人沿着悬崖行走是非常危险的，因为它可能会决定随机行动（概率为 epsilon）并跌倒。因此，我们希望它能够快速了解​​靠近悬崖是危险的；即使贪心策略能够顺着它走而不会跌倒，我们知道我们正在遵循一个随机的 epsilon-greedy 策略，并且我们关心优化我们的性能，因为我们知道有时我们会很愚蠢。这是 Sarsa 更可取的情况。

在我们不关心代理在训练过程中的表现的情况下，像Q-learning这样的算法会更可取，但我们只是希望它学习一个我们最终会切换到的最优贪心策略。例如，考虑一下我们玩了几场练习游戏（有时我们不介意由于随机性而输掉比赛），然后参加一场重要的比赛（我们将停止学习并从 epsilon-greedy 切换到 greedy 策略）。这是 Q-learning 更好的地方。

于 2018-03-20T16:54:35.893 回答
5

您的 Q-Learning 公式中有一个索引错误。萨顿和巴托的第 148 页。

Q(st,at) <-- Q(st,at) + alpha * [r(t+1) + gamma * max Q(st+1,a) - Q(st,at) ]

错字在 max 的参数中：

索引是 st+1 和 a，而在您的问题中它们是 st+1 和 at+1（这些对于 SARSA 是正确的）。

希望这个对你有帮助。

于 2013-10-22T11:03:35.763 回答
1

在 Q 学习中

这是你的：Q-Learning：Q(St,At) = Q(St,At) + a [ R(t+1) + discount * max Q(St+1, At ) - Q(St,At) ]

应改为 Q-Learning：Q(St,At) = Q(St,At) + a [ R(t+1) + discount * max Q(St+1, a ) - Q(St,At) ]

正如您所说，您必须找到更新 eq 的最大 Q 值。通过更改a，您将获得一个新的 Q(St,At)。小心，给你最大 Q 值的 a 不是下一步行动。在这个阶段，你只知道下一个状态（St+1），在进入下一轮之前，你想用 St+1 更新 St（St <-- St+1）。

对于每个循环；

  • 使用 Q 值从 St 中选择 At

  • 取 At 并观察 Rt+1 和 St+1

  • 使用 eq 更新 Q 值。

  • St <-- St+1

直到 St 是终点站

于 2014-03-11T17:43:03.877 回答
1

SARSA 和 Qlearning 之间的唯一区别是 SARSA 根据当前策略采取下一个动作，而 qlearning 采取下一个状态效用最大的动作

于 2019-10-03T06:41:12.640 回答
0

我没有读过任何书，只是看到了它们的含义 q 学习只关注（动作网格） SARSA 学习只关注（状态到状态）并观察 s 和 s' 的动作列表，然后更新（州到州电网）

于 2021-11-12T17:50:54.023 回答