Q-learning 算法 | Codeboy's Blog

形式陈述

Q-learning 观察转移 $(S_t,A_t,R_{t+1},S_{t+1})$ 后更新

Q_{t+1}(S_t,A_t)=Q_t(S_t,A_t)+\alpha_t(S_t,A_t) \left[R_{t+1}+\gamma\max_{a'}Q_t(S_{t+1},a')-Q_t(S_t,A_t)\right],

终止状态的最大值按零处理。方括号是最优 Bellman 方程残差的一次样本，因此该算法属于时序差分学习，但其目标策略是对当前 $Q$ 贪心的策略，数据却可由另一行为策略收集。

实现时可以把更新次数设为有限预算，耗尽后输出当前动作值表及其贪心策略。渐近收敛定理描述预算无限增长的极限，有限预算下的性能还需另给误差分析。若不另行维护最大值，非终止转移的目标需扫描 $A(S_{t+1})$ 中的动作，耗时 $O(|A(S_{t+1})|)$ ，随后单个表项的回写为 $O(1)$ ；表格及逐对计数占 $O(|S||A|)$ 空间，行为动作选择与环境交互另计。

表格收敛定理要求条件明确：MDP 状态与动作有限，奖励有界， $0\le\gamma<1$ ；每个非终止合法状态—动作对被无限访问，终止续值固定为零；步长取值在 $[0,1]$ ，在本次转移抽样前由已有信息确定，并按每对访问次数满足

\sum_n\alpha_n(s,a)=\infty, \qquad \sum_n\alpha_n(s,a)^2<\infty;

行为选择可以依赖过去信息，但给定这些信息和当前状态—动作后，奖励与下一状态仍按真实环境联合核抽样。在这些假设下，整个表 $Q_t\to q_*$ 几乎必然。只更新某个子集不构成其他表项的收敛保证。行为策略不必 GLIE，甚至不必趋向贪心；无限覆盖才是该离策略定理的核心。 $\varepsilon$ -greedy 是实现覆盖的一种办法，不是定义的一部分。

直觉

一次经验告诉算法“采取了什么”，目标却问“到了下一状态后，若从此采取当前看来最好的动作，会值多少”。这把探索行为和被优化的贪心策略分开，使任意充分覆盖的数据都有机会改进同一个最优动作值表。

最大值也会带来选择偏差：带噪估计中最大的那一个往往恰好被高估。Double Q-learning 用不同估计器选择与评价动作来减轻这一偏差，但不改变基本离策略思想。

实际采取的下一动作只决定以后采到哪条数据，不进入当前 backup；行为与备份目标的这层分离正是离策略性的核心。

Q-learning：单个经验在下一状态枚举动作，并由最大 Q 分支回传 — 离策略最大动作值回传

例子与边界

与 SARSA 的配对算例中，从 $(s,a)$ 获得 $0$ 到 $u$ ，当前 $Q(s,a)=1$ ，而 $Q(u,\mathrm{safe})=2,Q(u,\mathrm{risky})=5$ ；行为这次实际选择了 safe。取 $\gamma=0.9,\alpha=1/2$ ，Q-learning 不使用实际下一动作，其目标为

0+0.9\max\{2,5\}=4.5,

于是

Q(s,a)\leftarrow1+\tfrac12(4.5-1)=2.75.

和 SARSA 的 $1.4$ 不同，是因为这里估计“到 $u$ 后转为贪心”的反事实续程。若 risky 从未在 $u$ 被尝试，其数值 $5$ 可能只是初始化幻觉；无限访问条件正是为了最终纠正这种幻觉。

经典保证不覆盖常见的“致命三元组”。线性函数逼近下，离策略 Q-learning 已可发散；深度网络加入目标网络、回放和梯度裁剪能改善实践，却没有把表格定理自动搬过来。有限数据、固定步长或不断变化的环境也只允许误差界或跟踪分析，不能宣称几乎必然到达 $q_*$ 。

推论与应用

若 $Q$ 已精确等于 $q_*$ ，逐状态取最大动作得到最优策略。训练期间仍需探索，否则未选择动作没有更新；部署阶段是否保留探索取决于环境是否继续变化。离线数据中，最大化可能挑中数据支持之外的动作，产生外推误差，这是覆盖条件的有限样本版本。

价值迭代用完整模型计算下一状态期望，Q-learning 用一个实际样本作随机近似。DQN 再用神经网络表示 $Q$ ；Double DQN、dueling 架构等修补具体误差来源，但不改变目标里的最优 Bellman backup。

离线拟合 Q 迭代给出固定数据复用的具体算法：冻结上一轮函数生成整批目标，再拟合下一轮函数。其误差递推与未覆盖动作的双环境反例说明，表格在线算法的无限访问定理不能替代离线数据的覆盖分析。

参考资料

Christopher J. C. H. Watkins and Peter Dayan, “Q-learning,” Machine Learning 8, 1992, pp. 279–292.
John N. Tsitsiklis, “Asynchronous Stochastic Approximation and Q-Learning,” Machine Learning 16, 1994, pp. 185–202.
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed., MIT Press, 2018, Sec. 6.5.

形式陈述 ​

反向链接

形式陈述