off-policy learner 学习最优策略的值，不论 agent采取的行动action。 on-policy learner 学习策略的值并伴随着agent的改变，包括探索的步数（exploration steps）。
也可以理解为区别就是在进行iteration的时候，是不是需要根据新的policy产生新的样本。off-policy 用的都是已经存好的数据。on-policy 在边学习的时候边产生新的sample。
【出处：Identification and Off-Policy Learning of Multiple Objectives Using Adaptive Clustering】
Off-policy algorithms
- Q-learning (last time)
- R-learning (a variant of Q-learning)
On-policy algorithms
- SARSA
- TD(λ)
- Actor-critic methods
Q-learning
Q-learning学习一个最优策略，只要它足够地探索，不需要管系统做什么。当时，有时候可能有些情况下忽略系统实际做的事情是危险的（将会有大量的负面回报）。另一种方法是了解系统实际执行的策略的值，以便可以迭代地改进它。因此，on-policy学习算法可以考虑到与探索相关的花费。
off-policy learner 异策略学习独立于系统的行为,它学习最优策略的值。Q-learning Q学习是一种off-policy learn算法。on-policy算法，它学习系统正在执行的策略的代价，包括探索步骤。
在Q-learning和相关算法中，agent试图从与环境交互的历史中学习最优策略。一个代理的历史是一个状态，行动，奖励的序列:
⟨s0,a0,r1,s1,a1,r2,s2,a2,r3,s3,a3,r4,s4...⟩,
这意味着该代理处于状态S0，并采取行动A0，导致它收到奖励R1和状态S1，然后它采取行动A1，收到奖励R2，并最终在状态S2，然后它采取行动A2，收到奖励R3，并最终在状态S3，等等。
那么要给经验得样本就是：⟨s,a,r,s'⟩,状态s,执行action a后获得奖励r,会处于新状态是、s',在决策理论规划中，目的是为了使代理最大化其价值，这通常是报酬。
Q*(s,a)， 当a是一个动作，s是一个状态，是在状态s中执行a的期望值(累计折现奖励)，然后遵循最优策略。Q-learning利用时间差来估计Q*(s,a)的值。在Q-learning中，代理会保留一个Q[S, A]的表，其中S为状态集，A为动作集合。Q[s,a]表示当前Q*(s,a)的估计值。
⟨s,a,r,s'⟩样本提供Q(s,a得值的数据点。这个数据点就是获得的新的预期值r+ γV(s')，这里，选取最优值为V(s')，V(s') =maxa'Q(s',a');r+ γV(s')是实际的当前回报加上贴现后的估计未来价值。这个新的数据点称为return。如伪代码倒数第三行的公式对Q(s,a)进行更新。
SARSA算法（state-action-reward-state-action）是一个on-policy 强化学习的算法。在s状态时，跟据当前网络以及一定的策略（e-greedy）来选取动作a，获得奖励r, 进而观测到下一状态s'，并再次根据当前网络及相同的e- greedy策略选择动作a',这样就有了一个<s，a，r，s'，a'>序列，成为一个sample。然后通过这个样本更新Q(s,a).新的值为r+γQ(s',a').下图就是SARSA得伪代码。
SARSA考虑到了当前得探索策略，比如是以随机得贪婪步骤。当它探索可能招致巨大的惩罚时，它可以找到一个和Q-learning不同得策略。比如：当一个机器人几乎到了台阶得顶端时，即使它是一个最优策略，但是继续探索台阶是很危险的。SARSA将会发现这个问题，并且放弃这个策略，来保持机器人远离台阶。将会找到一种最优的政策，考虑到策略中固有的代价。
这两个算法的流程基本一致，唯一不同在于Q函数的更新：
Q-learning在计算下一状态的预期收益时使用了max操作，直接选择最优动作，而当前policy并不一定能选择到最优动作，因此这里生成样本的policy和学习时的policy不同，为off-policy算法；
而SARAS则是基于当前的policy直接执行一次动作选择，然后用这个样本更新当前的policy，因此生成样本的policy和学习时的policy相同，算法为on-policy算法。
而最近深度强化学里中使用的experience-replay机制将生成的样本与训练的样本独立开来，使用某一policy生成的样本拿来训练的时候，很可能当前policy已经和之前有所差别，因此使用experience-replay机制的DRL算法基本上是off-policy算法
发展历史
Q-learning是Watkins在1989年引入的。在1992年，Watkins和Dayan提出了一个收敛证明。在1994年，Tsitsiklis给出了更详细的数学证明，而Bertsekas和Tsitsiklis在他们1996年的《Neuro-Dynamic Programming》书中给出了这一证据。
沃特金斯Watkins的博士论文题目是“学习延迟奖励”(Learning from delayed rewards)。在1981年的，一个名为“延迟强化学习”“Delayed reinforcement learning”的系统被一个名为“交叉适应阵列”(Crossbar Adaptive Array，CAA)的系统所解决。最初发表于1982年。所提出的CAA体系结构的记忆矩阵W(a,s)与Q-learning的q表相同。体系结构在强化学习中引入了“状态评估”一词。
“二次强化secondary reinforcemen” 一词是从动物学习理论中借鉴来的，通过反向传播来模拟状态值:结果情境的状态值v(s)被反向传播到之前遇到的情况。在 a crossbar fashion，CAA通过水平的方式计算出垂直和动作的状态值。演示图显示延迟强化学习包含状态(理想的、不受欢迎的和中立的状态)，这些状态是由状态评估函数计算的。这种学习系统在1997年被认为是q学习算法的先驱。
SARSA 是一种学习马尔可夫决策过程策略 (MDP) 的算法，用于机器学习的强化学习领域。它是由Rummery和Niranjan在 (1994)一个名为“Modified Connectionist Q-Learning”(MCQ-L)的技术注释中提出的。富萨顿(Rich Sutton)提出的另一个名字Sarsa，只是作为一个脚注被提及。1998年，Wiering认为一些对Watkin的Q-learning的优化可以应用于SARSA。
Van Hasselt很喜欢处理Over-Estimate问题，他先搞出一个Double Q-learning [van Hasselt 2010]，发表于NIPS，六年后设计出深度学习版本的Double DQN[van Hasselt 2016a]。
Deep Q-learning：通过谷歌DeepMind(名为“深度强化学习”或“deep Q-learning”)，Q-learning在深度学习上的应用，在专家人类层次的Atari 2600游戏中获得了成功。初步结果于2014年公布。该系统使用了一个深度卷积神经网络，该神经网络使用分层结构的卷积滤波器来模拟接受域的效果。当一个非线性函数逼近器(如神经网络)用来表示q时，强化学习是不稳定或发散的。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1992 | Watkins, C. J., & Dayan, P.提出Q学习 | Watkins, C. J., & Dayan, P. (1992). Q-learning. Machine learning, 8(3-4), 279-292. |
| 1994 | Rummery, G. A., & Niranjan, M.提到sarsa算法 | Rummery, G. A., & Niranjan, M. (1994). On-line Q-learning using connectionist systems (Vol. 37). University of Cambridge, Department of Engineering. |
| 1994 | Tsitsiklis, J. N给出了更详细的数学证明 | Tsitsiklis, J. N. (1994). Asynchronous stochastic approximation and Q-learning. Machine learning, 16(3), 185-202. |
| 2016 | Van Hasselt, H., Guez, A.使用双Q-learning的深度强化学习 | Van Hasselt, H., Guez, A., & Silver, D. (2016, February). Deep Reinforcement Learning with Double Q-Learning. In AAAI (Vol. 16, pp. 2094-2100). |
发展分析
瓶颈
深度强化学习堪忧的采样效率；奖励函数设计困难；最合理的奖励也不能避免局部最优；Deep RL起作用时，它可能只是过度适应环境中的怪异模式；Deep RL起作用时，它可能只是过度适应环境中的怪异模式；Deep RL的落地应用艰难等问题都阻碍了深度强化学习的发展。
未来发展方向
- 添加更多的learning signal。稀疏奖励很难学习，因为我们无法获得足够已知的有帮助的信息；
- 基于模型的学习可以释放样本效率。原则上来说，一个好模型可以解决一系列问题，就像AlphaGo一样，也许加入基于模型的方法值得一试；
- 像参数微调一样使用强化学习。第一篇AlphaGo论文从监督学习开始，然后在其上进行RL微调。这是一个很好的方法，因为它可以让我们使用一种速度更快但功能更少的方法来加速初始学习；
- 奖励是可以学习的。如果奖励设计如此困难，也许我们能让系统自己学习设置奖励，现在模仿学习和反强化学习都有不错的发展，也许这个思路也行得通；
- 用迁移学习帮助提高效率。迁移学习意味着我们能用以前积累的任务知识来学习新知识，这绝对是一个发展趋势
Contributor：Ruiying Cai