关于为什么Q-Learning与DQN有效

前言：

我之前看了不少Q-Learning的介绍和deep mind的两篇论文：play atari with deep reinforcement learning与human control through deep reinforcement learning，后来复习的时候思考了很久为什么DQN会有效，按照a painless q learning tutorial里面的例子写了一个Q-Learning的代码和Q-Learning笔记，想明白了原因。如果理解有误欢迎指正。

本文假设读者明白q-learning和DQN，如果不够明白请参考上面提到的三篇资料和我写的笔记

Q-Learning:

Q-Learning是通过迭代来更新Q表的，在更新Q值时，采取ϵ-greedy实际上就是以ϵ的概率进行贪心，$1-\epsilon$的概率进行蒙特卡罗。Q表按照下面的公式进行更新：




从公式中可以看出，当前位置的Q值（价值）等于当前位置的瞬时回报+在当前位置采取所有动作之后的最大Q值（价值）。 以a painless q learning tutorial中的例子为例，如下图所示（左图为地图，右图中的数字表示回报$R(state, action)$：












使用这个地图定义Q表和R(回报)表：











当我们的目标为5时，我们定义到达5的回报为100,经过第一轮迭代之后，Q表中 $$[1,5]、[4,5]、[5,5]$$ 的Q值就是 $$R(any state, 5) + \gamma \times Max[Q(next state, all actions)]=100+\gamma  \times 0=100$$ ，其他"[状态,动作]对"的Q值为0.而重点在于之后的迭代，当遇到第二轮迭代的时候， $$[3,1]、[3,4]、[0,4]$$ 的Q值由0变为 $$0+\gamma \times100$$ ,实际上Q值在不断地向所有可行初始位置反向扩散，由于$\times<1$，而距离目的地越近，Q值也就越大。也就是说，选择Q值最大的路径就是最优路线。

观看Q表的扩散，可以运行我写的小程序，使用jupyter notebook运行。

地址在这里，也可以通过网页直接观察在我电脑上运行的结果。

DQN为何会有效？

DQN实际上是使用神经元网络来拟合Q表，原本的Q表为$q=Q(state, action)$，现在的Q网络为 $$[q1,q2,q3,q4...]=Q(state)$$ 。其中q1、q2等代表采取第一个动作、第二个动作……的Q值。DQN依赖于神经网络的回归效果，很容易就能想到，这个Q(state)可以替换成任意回归算法。另一个比较容易想到的就是，完全也可以使用回归算法直接拟合Q(state, action)，这样的话就可以通过启发式算法或遍历寻找到Q最大的动作来将DQN利用到连续的动作空间了，当然可以预见的是训练耗时也会相应地变长许多。

为何Q-Learning和DQN会收敛？

假设γ<1，Q-Learning中



为了简化计算，假设 $$Q(state, action) = Max[ Q(next state, all actions)]$$ ，那么   $$Q(state, action) = R( state, action) /(1-γ)$$ ，可计算出Q的极限是有穷的， 虽然没有给出严格证明，通过这个公式读者可以很容易地理解为什么这类算法一定会收敛。