深度强化学习初窥之DQN
最近对强化学习特别是深度强化学习做了一番了解，不像以前只是大概模模糊糊有个影子，为了加深印象，决定把相关内容记到这里。首先对强化学习做简要的介绍，之后介绍一下需要的相关背景知识，然后重点介绍一下深度Q学习（DQN）的算法理论以及实现过程。
关于强化学习，今年最为着名成功实践莫过于谷歌deep mind的alpha go，其于今年三月以4：1的比分击败了现役围棋选手中冠军数最多的李世石九段。由于围棋自身的复杂性，在之前很长的一段时间内被认为是计算机无法超越人类脑力的一个瓶颈。而这次alpha go引起的轰动之大，以至于有人评论说很有可能这是从弱人工智能向强人工智能转变的一个分水岭。这些套话我就不多说了，Alpha go所用的核心算法就是深度强化学习，要了解深度强化学习，就要先了解强化学习。
我们知道，在机器学习中，无论是分类聚类亦或是回归等其他场景，都可以根据训练数据中有无lable，可以将机器学习算法分为监督学习，无监督的学习以及半监督的学习。而有部分人将强化学习归为无监督学习的类别里面，我认为这样并不是十分准确。比如在很多强化学习中，人们会首先利用有监督的样本进行预训练，然后再进行深层次的训练。不过这个不是重点，重点是我们要理解强化学习是做什么的。
那么，什么是强化学习呢？
机器中的很多算法都是借鉴于人或者其他动物学习的过程。强化学习也不例外。
机器进行强化学习也是这个道理。就拿下中国象棋来说，一开始机器只知道简单的走棋规则（马走日字，象走田字等），然后机器会按照基本的规则漫无目的地走，这时候我们可以设定一定的奖励或者惩罚。比如当机器走这一步之后对方的炮就会被吃掉，那么我们就给机器一个小的奖励，假如当机器走了下一步之后对方的帅会被吃掉的话就给机器一个超大的奖励。对应的，假如因为机器自己的走子失误导致自己的帅被吃掉哦，我们可以给机器一个很大的惩罚。机器要做的就是在一次又一次的尝试之中，尽可能获得更大的奖励同时尽可能减少惩罚。训练中，机器刚开始可能会漫无目的地走子，而后经过逐步的奖惩的迭代会收敛于一个还算比较能接受的结果的解。
以上说完之后可能还是模模糊糊，那么我们具体来看一下Q学习是如果让机器自主寻路的一个例子。
首先用极其简单的语言解释一下什么事马尔科夫决策过程，所谓马尔科夫决策过程就是你接下来的所有状态和决策只取决于你当前的状态和决策。比如你在下象棋，和人下到了一半，这时候另一个人过来要帮助你下棋，你就可以走了，为什么他可以帮助你下棋？因为他只要看到当前棋局的状态就可以决定以后该怎么走了，并不需要关注你之前是如果经过那么多步下到现在棋局的状态的。无论你之前下的好坏都已经过去了，现在唯一能对未来发生改变的只有活在当下。
知道了马尔科夫决策过程，以下所有的讨论都是基于马尔科夫决策过程的了。
现在我们回到之前举的下象棋的例子。下棋的时候每一步的决策（具体来说是在某种棋局或状态下的决策）都会对应一个奖励或者回报（惩罚可以看做为负数的奖励）。
这里我们新定义一个概念，叫做价值。在某时刻某个状态下执行动作a会得到一个回报，然后在下一时刻执行某动作又会得到一个回报，然后下下一时刻……
我们把这些回报累加起来。
即（其中λ为0~1之间的数）
这里的G即相当于目前状态决策下的总回报。如果我们把该汇报的价值用一个价值函数来表示：
即价值函数为目前状态下回报的期望。
对上式进行展开运算，有
即得到以上贝尔曼方程。当前状态下的价值取决于当前的回报加上之后状态的价值（根据λ决定其权重）。这其实就相当于一种动态规划的思想。
具体到每个不同的状态都有不同的动作。每个动作的价值都是不一样的，所以根据状态和动作，有以下动作价值函数Q：
这个意思就是说，当前状态下执行动作a的价值等于当前状态下执行动作a的回报再加上之后状态和动作下的价值（根据λ决定其权重）。
由于可选择的状态和动作很多，而我们优化自然要选择最优的方式，最优动作价值函数和一般价值函数的关系是：
意思就是，从所有策略π里面选择一个策略使得Q的值最大。
带入之前的动作价值函数，有以下结果：
以上公式表达的意思是最优价值就是当前的回报加上之后最优决策下的价值（根据λ决定其权重）。
我们可以用迭代的方法来更新Q值，那么如何迭代呢？
我们可以按照以上公式，用之前的Q值来预测当前的Q值即可，这意味值我们可能会在最初随机初始化一些Q值，不过可以证明这样的迭代最后可以收敛于最优的动作价值函数。
以上即Q-learning中对更新的部分和原来的部分各占不同的权重来得到新的Q。
以上是理论部分，接下来用一个游戏实例说明整个迭代的思想。
如上图，带有0~5五个数字的圆圈代表五个不同的状态，而状态之间的箭头表示可以经过一个动作从该状态过渡到另一个状态。现在，我们游戏的目的就是给定我们所处的一个状态，我们如何找到一个策略，使得由该状态达到状态5。
我们首先为上面的箭头边设置回报值。如果一个状态能够通过动作直接到达状态5，则动作的回报为100，否则为0。假如两个状态之间没有通路，则将二者的回报设置为-1。
按此设置，我们有以下回报矩阵：
同时，我们也可以有一个矩阵Q，即之前提到的那个Q，用来表示价值。它和以上回报矩阵同阶。行表示状态，列表示行为。迭代初期，我们几乎对所有情况都一无所知，所以我们将Q初始化为零矩阵。
Q的迭代规则即：Q(state, action) = R(state, action) + γ * Max[Q(next state, all actions)]
根据上面的描述可以更直观的理解之前理论部分Q的计算过程。
下面我们一步一步地进行迭代学习以便理解其思想。
我们选取学习的参数γ=0.8，并且假设我们初始的状态为1状态。
我们观察上图第二行（状态1），发现非零值有两个，状态3和状态5，假设我们随机地选择到了状态5，从R矩阵中状态5那一行的非负值可以看出，从状态5可以转换到状态1,4,5，而状态五所对应的Q矩阵中的Max[Q(5, all actions)]也就是自然为Max[Q(5, 1), Q(5, 4), Q(5, 5)]。现在我们来计算Q（1,5）：
Q(1, 5) = R(1, 5) + 0.8 * Max[Q(5, 1), Q(5, 4), Q(5, 5)] = 100 + 0.8 * 0 = 100
现在我们的当前状态变成了状态5，由于状态5就是我们所要的目标结果，所以一次episode就算完成。
这时候我们的Q函数矩阵变成了：
现在进行下一次episode的迭代。
假设我们随机选取了一个初始状态3。由R矩阵可知3对应三个可能的通路状态，1，2,4。我们随机选择状态1.又由R可知，状态1可转到两个状态，3和5.
则Q(3, 1) = R(3, 1) + 0.8 * Max[Q(1, 3), Q(1, 5)] = 0 + 0.8 * 100 = 80
此时，矩阵Q变为：
这次计算之后我们的状态为状态1，由于状态1不是目标状态所以继续迭代，由R可知1可以通向3和5，假设我们这次选择了通向5状态，则由之前的计算公式可知：
Q(1, 5) = R(1, 5) + 0.8 * Max[Q(5, 1), Q(5, 4), Q(5, 5)] = 100+0=100
此次episode没有对Q矩阵做任何改变。由于5为目标状态，所以一次episode完了。
如此继续往复迭代，最终我们会形成类似于如下的Q价值矩阵：
我们队上述Q矩阵进行标准化（除以最大值），可以得到（该处省略了百分号）：
这样我们给定初始状态，每次找Q里面的最大值，即可得到最佳路径。
以上为一个例子用于直观地理解Q-learning迭代的思想，在以下公式中
我们假设了α=1，λ=0.8.
普通的Q-learning就是这样迭代的，那么为什么要有深度Q学习呢？
刚才的例子为状态数目特别少（只有物种状态），但很多问题状态数目往往特别多，比如一个棋盘特别是围棋棋盘的局势，几乎是无穷无尽多种，再有一张图片的像素罗列等等，这些状态价值函数根本无法用之前所提到的Q函数矩阵的方式来存储。所以就应该有一个新的方式来代替之前的Q函数矩阵的方式。这个方法就是用一个函数f来近似Q函数。即：
我们的Q函数可以输出：
这是一个向量形式，针对某一种状态，不同的动作所对应的Q，类似的，我们的f也应该是这个形式，那么该怎么表示了！
用深度神经网络！
理论上，神经网络可以拟合任何你想要的函数，这样用来训练和计算Q值的就是Q网络，这也就是DQN名称的由来。
我们把Q值作为标签，按照以下过程进行训练：
以下是NIPS2013中DQN的算法：
在DQN中增强学习Q-Learning算法和深度学习的SGD训练是同步进行的。
以上基本就是用深度神经网络做Q-learning的内容了。以后会再完善这部分。