两年前，位于伦敦的一家小公司，在arxiv上提交了一篇论文——Playing Atari with Deep Reinforcement Learning，之后同样的方法由试了7个游戏的挑战上，令人惊喜的是其中3个游戏上机器的表现超过了普通玩家。这家小公司叫DeepMind。
从那之后，通用意义的人工智能开启了第一步，要知道这与下象棋之类的挑战由着本质区别——环境是可连续变化的，而非严格固定的集合。毫无疑问，DeepMind从一家小公司到被Google关注并收购，同时领跑DL领域的研究。在2015年2月，在Nature杂志封面上出现了他们的论文“Human-level control through deep reinforcement learning”——将同样的模型放到了49种不同的游戏上，并且在一半以上超越了人类玩家的表现。
一、RL解决的问题——信用分配问题+E&E问题
大家在“古老”的游戏机上都玩过弹乒乓球的游戏，左右移动乒乓球拍来反弹乒乓球，击打掉障碍来获得分数。考虑下如何能用神经网络来玩这个游戏呢？首先，网络的输入是屏幕的画面，输出只有2种动作：左移、右移。这很像一个简单的2分类问题的模型。如何训练呢？一个直观的想法是有监督的，可以找专业玩家来玩，并记录每次完整的动作。但这个想法显然不太现实（说到这，曾经我想过无人驾驶是不是可以记录所有司机开车时做出的动作，然后有监督的训练一个DL模型。。）。
这正是RL想要解决的问题，RL介于有监督和无监督之间（是不是有点像半监督。。其实没什么关系）。RL的Label是一个稀疏的、（时间上）延后的激励rewards，根据这个激励，Agent在变换的环境中做出反应。
然而，游戏中当你得分时 ，其他人并不知道你之前的动作是什么，它已经发生过了，并不在同一时间。这就RL的挑战——所谓的信用分配问题（credit assignment problem），已经发出的动作会影响后续事情的发生。
即使你已经找到了一个好的办法能够得到不错的分数，你是应该坚持这个策略，还是去尝试新的策略也许会获得更高的分数呢？这就是著名的E&E问题（explore-exploit dilemma）。
二、RL的数学表示——马尔可夫决策过程
对RL问题最普遍的数据表示为马尔可夫决策过程Markov decision process（Markov类似上帝一样的存在。。）,它主要描述状态State到状态Satet之间的转移，这个转移是由于动作Action导致，如何选择动作Action的规则Rule叫做策略Policy
State1—>[Policy][Action1]—>State2—>[Policy][Action2]—>State3...—>[Policy][Actionn]—>Staten
S/A/P构成了一个马尔可夫决策过程，每一个连续的决策片段形成了一个有限的state/action/rewards序列
三、如何给出比较长期的策略，而非“短视”的策略——折扣激励
为了得到一个相对长的决策序列，除了当前动作的即时激励reward之外，我们还要考虑后序能拿到的激励是怎样的。
一个完整的马尔可夫决策过程片段episode的激励可以如下表示：
R= r1 + r2 + r3…+rn
时间t的后序激励表示为：
Rt = rt + r(t+1) + r(t+2)+…+rn
考虑决策过程的环境是随机的，同样的动作可能会导致不同的后序序列，因此过多的依赖后序的期望可能会导致不收敛，因此添加一个折扣因子
Rt = rt + γr(t+1) + γ^2r(t+2)+…+γ^(n-t)rn
递归表达为：
R(t) = r(t) + γ*R(t+1)
四、怎样对未来的奖励进行估计或者近似——贝尔曼方程（动态规划）
在Q-Learning算法中，用Q(s,a)表示最大的折扣后序激励
Q(St,at) = max R(t+1)，物理意义可以认为是在状态s下采取动作a在游戏结束时我们可能拿到的最好的成绩，也就是所谓的Q函数
类似折扣激励的表示，Q函数也可以表示为：
Q(s,a) = r(t) + γ*maxQ(S`,a`)，高大上的名字叫Bellman equation贝尔曼方程，其实也就是动态规划啦。。。
Q-Learning算法的核心思想也就是通过不断的迭代这个动态规划来拟合Q函数。
PS：最简单的Q函数实现是用一个表table，行为state，列为action
五、如何解决状态空间规模巨大的问题——DQN模型
按照DeepMind的论文，用像素来表示决策环境，具体的取最后的4帧图像，缩放到84*84，每个像素点映射到256级的灰度数值，那么总的状态数将是256^(84*84*4)≈10^67970个，意味着表的行数会是个可怕的数字，那么如何使状态数在可控的范围内，同时又能保证对Q函数的拟合效果呢？
深度学习登场！神经网络正合适抽取有用的特征，忽略掉无用的。
一个直观的想法是把屏幕截图和动作都作为输入，输出即是对应的Q值（最大可能激励）。也可以仅仅把屏幕图片作为输入，输出是每个可能动作对应的Q值。如果我们想对Q函数进行更新或者找到最大Q值的动作，后面的方法更方便一些，只做一次forward计算就可以。
DQN的训练：仅针对一个对举例
1、对当前状态s做一次forward计算，预测所有动作的Q-value
2、对下一步动作s`做一次forward计算，得到所有输出中的最大值maxQ(s`,a`)
3、将r+γ*maxQ(s`,a`)作为step1的target，其他的动作的target保持step1的输出，使error为0
4、计算梯度更新网络的参数
六、怎样才能在实际中应用RL
如上我们基本有一个完整的Q-Leaning的模型方案了，但实际中发现非线性函数并不稳定，为了得到不错的模型，有很多trick需要做。其中最重要的trick是experience replay。
在模型的训练过程中，已经训练过的experience 将会被存储在一个replay memory中，每次随机mini batch样本的时候，会从replay memory中获取，而不是从最近的中取。这主要是考虑解决模型陷入局部最小的问题。
七、E&E
Q-learning试图通过及时的反馈激励来解决信用分配问题。我们按上面的过程做一个假设，首先Q-network被随机的初始化，于是它的预测也是随机的，也就意味着它按照最大Q-value选择的动作也是随机的。智能体Agent表现出绝对的随机“探索”exploration。当模型越来越收敛时，模型将返回相对一致的Q-value，此时“探索”在减少。因此有人说Q-learning在内部完成了Exploration的机制，但实际上这种探索是贪婪的，只考虑了最大激励的动作而已。
因此，e-greedy策略更适合（在个性化推荐模型中其实比较常用到，还有其他的一些E&E算法如UCB等，可以自行百度）。e-greedy保持了在概率e上随机选择一个动作，而不是选择最大Q-value的动作。在DeepMind的系统中，e随时间递减，范围是1->0.1
Reference：https://www.nervanasys.com/demystifying-deep-reinforcement-learning/
