Q 学习

1992 年 5 月，Watkins 与 Dayan 在《Machine Learning》期刊上发表了一篇技术札记（technical note），标题就叫「Q-learning」^[1]。这篇札记做了两件事：把 Q 学习这个方法讲清楚，并证明它会收敛。

要解决的问题

问题可以这样表述：在一个受控马尔可夫域（controlled Markovian domain）里——也就是环境的状态会随智能体的动作而改变——智能体怎样通过不断尝试，学会采取最优行动^[1]。这类问题的难点在于延迟回报：一步动作的好坏，往往要等若干步之后才看得出来，因此智能体必须回过头去判断早先的动作起了多大作用。

Q 学习并不是这篇札记首次提出的。札记的摘要把 Q 学习标注为 Watkins 1989 年的工作，参考文献里列出的是他在剑桥大学的博士论文《Learning from delayed rewards》，作为这一方法的出处^[1]。1992 年的这篇札记由 Watkins 与 Dayan 合写，把这个方法以期刊论文的形式完整呈现，并补上了博士论文中只是勾勒过的详细收敛性证明^[1]。

方法怎么工作

按摘要的说法，Q 学习是一种让智能体学会在受控马尔可夫域中最优行动的简单办法^[1]。它本质上是一种增量式的动态规划（dynamic programming）方法，计算量要求有限，工作方式是不断改进自己对「某个状态下某个动作有多好」的估计^[1]。

说得具体一点：智能体为每一个「状态—动作」组合保存一个数值，可以把它理解为在这个状态下做这个动作、并把之后能拿到的回报都算进来，究竟值多少。每执行一次动作、观察到回报和下一个状态，它就把这个数值往更准确的方向调整一点。整个过程不需要建立环境如何转移的模型，这正是它计算量小的原因。

收敛性定理

札记的核心贡献是一个收敛性定理，它被详细给出并加以证明，基础是 Watkins 1989 年论文中勾勒过的那个证明^[1]。定理说：只要满足两个条件——所有动作在每个状态下都被反复采样，并且动作价值用离散的方式表示——Q 学习就以概率 1 收敛到最优动作价值^[1]。

两个条件各有分量。采样条件要求每个状态下的每个动作都持续被尝试，否则对应的估计就没有机会被修正；离散表示条件约束的是数值的存放方式。「以概率 1」是说收敛几乎必然发生，而不是说每一次更新都会让估计变好。

两处推广

札记还勾勒了两个方向的扩展^[1]。一类是环境不带折扣但会吸收（absorbing）的情形；另一类是每次迭代不只改动一个 Q 值，而可以同时改动许多个 Q 值^[1]。

发表信息

这篇题为「Q-learning」的技术札记发表在《Machine Learning》1992 年 5 月号，第 8 卷，第 279–292 页，DOI 为 10.1007/BF00992698^[1]。两位作者当时的地址是：Watkins 在伦敦，Dayan 在爱丁堡大学认知科学中心（Centre for Cognitive Science）^[1]。

为什么重要

这篇札记的分量在于它把两样东西放在了一起：一条计算代价很低的更新规则，和一份关于这条规则何时可信的明确说明。证明并没有简单地宣称方法管用，而是点名了它管用的两个条件——这正是一个人判断该方法能否用在自己问题上所需要的东西。由于算法既不需要环境模型，计算量又有限，这两个条件就成了方法与保证之间最主要的关卡。