关于为什么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的极限是有穷的虽然没有给出严格证明通过这个公式读者可以很容易地理解为什么这类算法一定会收敛

此博客中的热门博文

免费爬墙网站项目(ShadowSocksShare)开发简记

Ubuntu Gnome 酷炫完整指南(一):小工具篇