关于为什么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(state, action) = R(state, action) + \gamma \times Max[Q(next state, all actions)]$

从公式中可以看出,当前位置的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) = R(state, action) + \gamma \times Max[Q(next state, all actions)]$

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

此博客中的热门博文

Flash被淘汰后打开swf文件的最佳方法

[SOLVED] Supermicro cannot connect to VGA video port or iKVM

MacBook日文键盘四种输入模式输入法切换(同样适用于其他布局的键盘)