artificial-intelligence - Q-learning 和 SARSA 有什么区别？

Question

虽然我知道SARSA符合政策，而 Q-learning是偏离策略的，当查看他们的公式时，(对我来说)很难看出这两种算法之间的任何区别。

根据书Reinforcement Learning: An Introduction (萨顿和巴托)。在SARSA算法中，给定一个策略，对应的 Action 值函数Q(在状态s和 Action 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(以及我自己的答案)

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

另一个主要区别是何时发生这种选择(例如在线与离线)以及如何/为何影响学习。如果您在 2019 年阅读本文，并且是一个更注重实践的人，那么玩 RL 玩具问题可能是理解差异的最佳方式。

最后一个重要注意事项是，Suton 和 Barto 以及维基百科经常对以下内容有混合、令人困惑或错误的公式化表示下一个状态最佳/最大行动和奖励:

r(t+1)

事实上

r(t)

Answer 1

当我学习这部分时，我也发现它很困惑，所以我把 R.Sutton 和 A.G.Barto 的两个伪代码放在一起，希望能让区别更清楚。

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

TL；NR:

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

其中 π 是 ε 贪婪策略(例如 ε > 0 进行探索)，μ 是贪婪策略(例如 ε == 0，无探索)。

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

2. 相比之下，SARSA 始终使用 π，因此它是一种在策略算法。

更详细的解释:

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

2. 然而，当实际采取行动时，Q-learning 仍然使用从 ε-贪婪策略采取的行动。这就是为什么“Choose A ...”位于重复循环内。

3. 按照 Q-learning 中的循环逻辑，A' 仍然来自 ε-贪婪策略。