Q学习和SARSA有何区别？

Question

Q学习和SARSA有何区别？

artificial-intelligencereinforcement-learningq-learningsarsa

146

虽然我知道SARSA是on-policy算法，而Q-learning是off-policy算法，但是当我看它们的公式时，很难（对我来说）看出这两个算法之间的任何区别。

根据书籍Reinforcement Learning: An Introduction（作者为Sutton和Barto），在SARSA算法中，给定一个策略，相应的动作值函数Q（在时间步t的状态s和动作a中）即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（和我的回答）

感谢所有回答这个问题的人，自从我第一次问这个问题以来，我已经制作了一个github repo，并通过实证理解了其中的差异。这主要取决于你如何选择下一步最好的行动，从算法角度来说，它可以是平均值、最大值或最佳行动，具体取决于你选择的实现方式。

另一个主要区别是选择发生的时间（例如，在线与离线）以及如何/为什么影响学习。如果您正在2019年阅读此内容并且更喜欢亲自动手，那么玩强化学习玩具问题可能是理解差异的最佳方式。

最后一个重要说明是，Suton＆Barto以及维基百科经常涉及“下一个状态最佳/最大操作和奖励”的混合，混淆或错误的公式表示：

r（t+1）

实际上是

r（t）

- Ælex

8个回答

78

是的，这就是它们唯一的区别。On-policy SARSA相对于遵循的策略学习动作价值，而off-policy Q-Learning则相对于贪心策略学习。在一些共同条件下，它们都会收敛到真实的价值函数，但速度不同。Q-Learning倾向于收敛速度稍慢一些，但有能力在改变策略时继续学习。此外，当与线性逼近结合时，Q-Learning不能保证收敛。

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

Q-Learning: Q(s_t+1,a_t+1) = max_aQ(s_t+1,a)

SARSA: Q(s_t+1,a_t+1) = ε·mean_aQ(s_t+1,a) + (1-ε)·max_aQ(s_t+1,a)

- Don Reba

4

那么，Sarsa如何选择策略呢？我知道Q-learning将始终遵循承诺将您带到下一个最佳策略的策略。在Sarsa中选择下一个策略的标准是什么（基本上我想知道如何评估策略Q（S，A），如何选择最佳行动）。难道不是一样的吗？也就是说，选择状态S的行动A，其Q'（S，A）最高吗？ - Ælex

9

策略是选择下一步行动的规则，算法实现时需要进行选择。最简单的策略是贪心策略——代理程序总是选择最佳行动。使用这种策略，SARSA和Q-Learning是相同的。更好的学习选择是ε-贪心策略，其中一些行动是随机选择的。 - Don Reba

2

好的，这就是我一开始问问题的原因，这种情况下它们两个是相同的。非常感谢！我正在使用e-Greedy算法。所以只有在Off-Policy的情况下，Qlearning才会有所不同，即动作被随机选择但更新时使用Q-learning最大化策略值？ - Ælex

2

在ε-贪心策略下，SARSA的期望值是平均动作价值和最佳动作价值的加权和：Q(s_t+1,a_t+1)=ε·mean(Q(s,a))+(1-ε)·max(Q(s,a))。该内容可在教材第5.4章节"On-Policy Monte Carlo Control"中找到。 - Don Reba

69

从数学角度上讲，这两种算法有什么区别？

正如其他回答所描述的那样，在更新状态-动作对（(S_t, A_t)）的Q-值时，这两个算法在数学上的区别确实在于：

Sarsa使用行为策略（即代理用来生成环境经验的策略，通常是epsilon-贪心），选择一个额外的动作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-贪心策略，否则我们无法保证我们会收敛到任何结果。
Q-Learning会收敛到在生成经验并训练后，切换到贪心策略的假设下最优的解决方案。

何时使用哪种算法？

像Sarsa这样的算法通常更适合在我们关心代理程序学习/生成经验过程中的表现的情况下使用。例如，如果代理是一个昂贵的机器人，如果它掉下悬崖就会损坏，我们不希望在学习过程中它太频繁地掉下去，因为它很昂贵。因此，我们关心其在学习过程中的表现。但是，我们也知道有时需要让它随机行动（例如epsilon-greedy）。这意味着，机器人沿着悬崖行走非常危险，因为它可能决定随机行动（以epsilon的概率）并掉下去。因此，我们更希望它能快速学习到靠近悬崖是危险的；即使贪婪策略可以在不掉下来的情况下靠近悬崖，我们知道我们正在遵循一个具有随机性的epsilon-greedy策略，并且我们关心在知道我们有时会变得愚蠢的情况下优化我们的表现。这是Sarsa更好的情况。

在我们不关心代理在训练过程中的表现，而只想让它学习最优贪婪策略并最终切换到该策略的情况下，像Q-learning这样的算法更适合。例如，我们玩几场练习比赛（在其中有时输掉是可以接受的），然后参加重要的锦标赛（在那里我们将停止学习并从epsilon-greedy切换到贪婪策略）。这就是Q-learning更好的地方。

- Dennis Soemers

6

不论算法如何，这都是最佳解释政策。 - Ege

2

这是一个特别好的答案，我认为应该被接受。 - Scrimbibete

1

为了进行苹果与苹果的比较，假设我们设计了一个非常便宜的机器人，我们可以承受它多次损坏和摔落。现在我们可以在这里使用Q-learning而不是Sarsa。机器人不断摔倒并摔断腿，因为Q值不反映现实（即我们实际遵循的策略）。如果使用Sarsa，系统会立即意识到沿着悬崖行走是危险的，因为Q值是根据正在遵循的策略更新的。在Q学习中，Q值是根据不同的策略计算的（可能最终采用的策略）。 - Allohvk

1

@Allohvk 确实如此。从这个角度来看，Sarsa可能具有优势（在学习速度方面），即使我们不关心代理在学习过程中的表现，也可能更可取。虽然，在某种程度上，我们也可以认为这是关心代理在学习过程中的表现。这并不是因为它是一台昂贵的机器人，而是因为一个在学习过程中表现良好的代理可能会收集更有价值的经验并更有效地学习。 - Dennis Soemers

1

@Sam 我认为在训练期间关注性能的情况（直接或间接由于先前评论中提到的副作用）和不关注性能的情况都很常见。真的不敢说其中任何一种情况是“大多数情况”。如果我们可以在“模拟”中进行培训（例如，游戏，机器人模拟器等），那么不关心可能更为普遍；如果在物理机器人上进行培训，或者在已经部署并正在运行的系统中继续在线培训（例如，提供广告，捕获欺诈等），则关注性能可能更为普遍。 - Dennis Soemers

显示剩余3条评论

5

您的Q-Learning公式中存在索引错误。这是Sutton和Barto的第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是正确的）。

希望这能有所帮助。

- Alvin

1

SARSA和Qlearning唯一的区别在于，SARSA基于当前策略选择下一步动作，而qlearning选择具有下一个状态最大效用的动作。

- Beyhan Gul

1

这是不正确的。两种方法都采取相同的确切行动（ε-greedy）。区别在于（如其他答案中所述），它们使用不同的策略来更新Q函数。 - mobeets

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) ]

正如你所说，你必须通过改变a来找到更新方程的最大Q值，然后你将有一个新的Q(St,At)。请注意，给出最大Q值的a不是下一个动作。在这个阶段，您只知道下一个状态（St+1），并且在进入下一轮之前，您想通过St+1更新St（St <-- St+1）。

对于每个循环；

使用Q值从状态St中选择行为At
执行行为At并观察Rt+1和下一个状态St+1
使用公式更新Q值
将状态St更新为St+1

直到状态St为终止状态

- comx

实际上，他们让观众产生了困惑；它不是R[t+1]，而是R[t]，但在书中的某个地方确实将其显示为R[t+1]。然而（不要相信我的话，自己试试），如果您设置R[t+1]，则奖励值不会在0-1之间缩放，甚至更糟的是，您会遇到算法迭代问题，因为当状态终止时，Q[t]=R[t]，如果使用R[t+1]，这将永远不会成立。维基百科错了（我已经编辑过了），Sutton和Barto在书中使用了这两种变体，但并没有真正解释原因。 - Ælex

0

我没有阅读任何书籍，只是看到它们的含义 Q学习只关注于（动作网格） SARSA学习只关注于（状态到状态），观察s和s'的行动列表，然后更新（状态到状态网格）

- Aref Yelghi

你的回答可以通过添加额外的支持信息来改进。请 [编辑] 添加更多细节，例如引用或文档，以便其他人可以确认你的答案是正确的。你可以在帮助中心找到有关如何编写好的回答的更多信息。 - Community

0

SARSA和Q-learning代理都遵循e-greedy策略与环境进行交互。

SARSA代理使用下一个时间步的Q值来更新其Q函数，该Q值是由策略提供的任何操作（大多数仍然是贪婪的，但也接受随机操作）计算得出的。执行的策略和更新的策略是相同的。

Q-learning代理仅使用带来最大下一状态Q值的操作来更新其Q函数（相对于策略而言是完全贪婪的）。执行的策略和更新的策略是不同的。

因此，SARSA是on-policy，Q-learning是off-policy。

- cookiemonster

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- zyxue · Accepted Answer

当我学习这部分内容时，我也觉得非常困惑，所以我整理了来自 R.Sutton 和 A.G.Barto 的两个伪代码，希望能使它们之间的差异更加清晰。

蓝色框标出了两个算法实际上有区别的部分。数字标出了稍后需要解释的更详细的差异。

TL;NR:

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

其中π是ε-贪心策略（例如，ε>0代表探索），而μ是贪心策略（例如，ε=0，没有探索）。

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

更详细的解释：

两者之间最重要的区别在于每个动作后如何更新Q。SARSA完全使用ε-贪心策略下的Q'，因为A'是从中抽取的。相反，Q-learning使用下一步所有可能动作中最大的Q'，这使其看起来像是在此部分上遵循ε=0的贪心策略，即没有探索。
但是，当实际采取行动时，Q-learning仍然使用从ε-贪心策略中采取的动作。这就是为什么“选择A…”在重复循环内部的原因。
按照Q-learning中的循环逻辑，A'仍然来自ε-贪心策略。