Q学习

Q-学习是强化学习的一种方法。Q-学习就是要记录下学习过的策略，因而告诉智能体什么情况下采取什么行动会有最大的奖励值。Q-学习不需要对环境进行建模，即使是对带有随机因素的转移函数或者奖励函数也不需要进行特别的改动就可以进行。

对于任何有限的马可夫决策过程（FMDP），Q-学习可以找到一个可以最大化所有步骤的奖励期望的策略。^[1]，在给定一个部分随机的策略和无限的探索时间，Q-学习可以给出一个最佳的动作选择策略。

“Q”这个字母在强化学习中表示一个动作的期望奖励。^[2]

强化学习

强化学习涉及一个智能代理人（agent），一组“状态” $S$ 和每个状态下的动作集合 $A$ 。通过执行一个行动 $\,a\in A$ ，该智能代理人从一个状态转移到另一个状态。在一个特定的状态下执行一个动作时，智能代理人可以得到一个奖励。

智能代理人的目标是最大化其奖励的总和。这个潜在的奖励是所有未来可以拿到的奖励值的期望的加权和。

例如，假设现在你要上地铁，奖励就是你所花的时间的相反数。一种策略就是车门一开就往上挤，但是还有很多人要下车，逆着人流往上挤也会花费不少时间，这个时候你花的总时间可能是：

0秒钟等待时间+15秒挤上去的时间

在接下来的一天，很巧合，你决定先让别人下车。虽然这个时候看起来等待的时间稍微增加了，但是下车的人也会下的更顺畅，这个时候你可能花的时间是：

5秒等待时间+0秒挤上去的时间。

算法

将Q表格的值初始化为零，每个单元会经过训练而更新其值。

Q-学习算法，主要内容为计算状态与行为对应的最大期望奖励函式 $Q$ ：

Q:S\times A\to \mathbb {R}

.

在算法初始化阶段， $Q$ 初始值为零(由设计者设计)。在时间 $t$ 时，环境的状态为 $s_{t}$ ，智能代理人选择一个行为 $a_{t}$ ，并且获得奖励 $r_{t}$ ，环境因为代理人的行为导致状态改变为新的状态 $s_{t+1}$ ，此时便可根据以下公式更新 $Q$ 值。算法的核心为简单的利用过去与最近的权重平均值来迭代更新数值。

Q^{new}(s_{t},a_{t})\leftarrow (1-\alpha )\cdot \underbrace {Q(s_{t},a_{t})} _{\text{old value}}+\underbrace {\alpha } _{\text{learning rate}}\cdot \overbrace {{\bigg (}\underbrace {r_{t}} _{\text{reward}}+\underbrace {\gamma } _{\text{discount factor}}\cdot \underbrace {\max _{a}Q(s_{t+1},a)} _{\text{estimate of optimal future value}}{\bigg )}} ^{\text{learned value}}

其中 $r_{t}$ 代表从状态 $s_{t}$ 到状态 $s_{t+1}$ 所得到的奖励值, $\alpha$ 为学习率( $0<\alpha \leq 1$ )。 $\gamma$ 为衰减系数( $0\leq \gamma \leq 1$ )，当 $\gamma$ 数值越大时，智能代理人便更加重视未来获得的长期奖励， $\gamma$ 数值越小时，智慧代理人便更加短视近利，只在乎目前可获得的奖励。

实现

Q-学习最简单的实现方式就是将奖励值存储在一个表格（Q-table）中，但是这种方式受限于状态和动作空间的数目。

函数逼近

Q-学习可以结合函数逼近。^[3] 这使得在更大的状态空间中使用 Q-学习，即使状态空间是连续的。

一个解决方案是以使用人工神经网络来进行函数逼近。^[4]。函数逼近的方法在一些问题中会有很好的加速效果，某些时候算法可以通过早期经验的总结可以在一些未出现的状态中依然可以有很好的效果。

变种

深度Q-学习

这是一个由DeepMind公司开发的利用深度卷积神经网络来进行Q-学习的算法。在使用非线性函数逼近的时候，强化学习经常会有不稳定性或者发散性：这种不稳定性来于当前的观测中有比较强的自相关。DeepMind 通过使用经历回放，也就是每次学习的时候并不直接从最近的经历中学习，而是从之前的经历中随机采样来进行训练。

深度双Q-学习

尽量深度Q-学习的效果已经很好了，但是人们发现了一个问题，它会过高的估计Q值。DeepMind在2015年证明了这个估值错误真的存在，并且采用双Q-学习的方法改进了算法，从而降低了过高估值带来的影响。

参见

强化学习
时序差分学习（英语：Temporal difference learning）
SARSA算法
囚徒困境
博弈论

参考文献

^ Francisco S. Melo, "Convergence of Q-learning: a simple proof" （页面存档备份，存于互联网档案馆）
^ Matiisen, Tambet. Demystifying Deep Reinforcement Learning | Computational Neuroscience Lab. neuro.cs.ut.ee. December 19, 2015 [2018-04-06]. （原始内容存档于2018-04-07）（美国英语）.
^ Hasselt, Hado van. Reinforcement Learning in Continuous State and Action Spaces. Wiering, Marco; Otterlo, Martijn van (编). Reinforcement Learning: State-of-the-Art. Springer Science & Business Media. 5 March 2012: 207–251 [2018-09-18]. ISBN 978-3-642-27645-3. （原始内容存档于2022-06-01）.
^ Tesauro, Gerald. Temporal Difference Learning and TD-Gammon. Communications of the ACM. March 1995, 38 (3): 58 [2010-02-08]. doi:10.1145/203330.203343. （原始内容存档于2010-02-09）.

外部链接

Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England.（页面存档备份，存于互联网档案馆）
Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning
Reinforcement Learning: An Introduction by Richard Sutton and Andrew S. Barto, an online textbook. See "6.5 Q-Learning: Off-Policy TD Control".
Piqle: a Generic Java Platform for Reinforcement Learning（页面存档备份，存于互联网档案馆）
Reinforcement Learning Maze（页面存档备份，存于互联网档案馆）, a demonstration of guiding an ant through a maze using Q-learning.
Q-learning work by Gerald Tesauro（页面存档备份，存于互联网档案馆）
Q-learning work by Tesauro Citeseer Link - Doesn't work
Q-learning algorithm implemented in processing.org language - Doesn't work
JavaScript Example with Reward Driven RNN learning
A Brain Library^{[永久失效链接]}
A Genetics Library used by the Brain^{[永久失效链接]}

[auto-1] Francisco S. Melo, "Convergence of Q-learning: a simple proof" （页面存档备份，存于互联网档案馆）

[:0-2] Matiisen, Tambet. Demystifying Deep Reinforcement Learning | Computational Neuroscience Lab. neuro.cs.ut.ee. December 19, 2015 [2018-04-06]. （原始内容存档于2018-04-07）（美国英语）.

[3] Hasselt, Hado van. Reinforcement Learning in Continuous State and Action Spaces. Wiering, Marco; Otterlo, Martijn van (编). Reinforcement Learning: State-of-the-Art. Springer Science & Business Media. 5 March 2012: 207–251 [2018-09-18]. ISBN 978-3-642-27645-3. （原始内容存档于2022-06-01）.

[CACM-4] Tesauro, Gerald. Temporal Difference Learning and TD-Gammon. Communications of the ACM. March 1995, 38 (3): 58 [2010-02-08]. doi:10.1145/203330.203343. （原始内容存档于2010-02-09）.

[1]

[2]

[3]

[4]