强化学习（二）
DQN
前面我们讲到TD算法结合了动态规划和蒙特卡洛算法的优点，不依赖具体的环境模型，并且更新时采用滑动平均的方式，因此单步就能更新，而不需要生成整个episode，在非episode情况下仍然适用。TD算法又分为on policy的sarsa算法和off policy的Q learning算法，其中Q learning算法直接使用下一状态的最大动作值函数进行更新，加快了算法收敛速度，因此Q learning算法在实际应用中更加普遍。
Q learning例子
我们用一个例子来说明Q learning算法的过程。下图是一个二叉树表示的路径规划问题，每一个节点代表环境中的一个状态，叶子节点表示终止状态，每个非叶子节点都可以选择向上或向下的动作，然后转移到下一个节点，并获得相应的得分。
首先初始化所有状态动作对的动作值函数：\(Q(S_{i},a)=0, \forall i\in[1，6],a\in[上, 下]\)，并且初始化\(\epsilon = 0.1，\alpha = 0.1\)。
随机选择一个初始状态\(S\)，假设为\(S_0\)
根据\(\epsilon-greedy\)策略选择一个动作，假设为上，转移到状态\(S_1\)，那么更新\(Q(S_0,上)=Q(S_0,上)+\alpha\cdot(R_{1}+\max_aQ(S_1,a)-Q(S_0,上))=0+0.1\cdot(10+0-0)=1\)，接下来继续根据\(\epsilon-greedy\)策略选择下一个动作，比如下，并且转移到终止状态\(S_4\)，因此\(Q(S_1,下)=Q(S_0,下)+\alpha\cdot(R_{2}+\max_aQ(S_4,a)-Q(S_1,下))=0+0.1\cdot(100+0-0)=10\)。随机选择一个初始状态\(S\)，假设为\(S_2\)
根据\(\epsilon-greedy\)策略选择一个动作，假设为上，转移到终止状态\(S_5\)，则更新\(Q(S_2,上)=0+0.1\cdot（100+0-0）=10\)随机选择一个初始状态\(S\)，假设为\(S_0\)
根据\(\epsilon-greedy\)策略选择一个动作，假设为上，转移到状态\(S_1\)，则更新\(Q(S_0,上)=1+0.1\cdot(10+10-1)=2.9\)，选择下一个动作，比如上，则\(Q(S_1,上)=0+0.1\cdot(50+0-0)=5\)随机选择一个初始状态\(S\)，假设为\(S_0\)
根据\(\epsilon-greedy\)策略选择一个动作，假设为上，转移到状态\(S_1\)，则更新\(Q(S_0,上)=2.9+0.1\cdot(10+10-2.9)=4.61\)，选择下一个动作，比如下，则\(Q(S_1,下)=10+0.1\cdot(100+0-10)=19\)…
下面是该例子的python实现：
1 | """ |
最终收敛结果为:
1 | [[109.99999999999989, 139.99999999999977], |
函数逼近
上面的例子中非终止状态数只有3个，每个非终止状态对应的动作只有2个，因此状态动作对总共有6个，使用表格存储完全没有问题，但实际上我们需要解决的并不是一个如此简单的问题。比如在【Playing Atari with Deep Reinforcement Learning】中DeepMind就使用Q learning使得agent玩Atari 2600游戏的水平超越了人类水平。在Atari 2600游戏中，每个游戏画面都是一个状态，如果每个画面都是像素为84*84的256灰度图像，那么将会产生\(256^{84\cdot84}\)个状态，用表格进行存储将会变得非常不现实。为了解决状态数爆炸的问题，通常可以使用函数逼近的方法。下面有几种函数表示的方式：
并且逼近函数的形式可以采用：
- Linear combinations of features
- Neural network
- Decision tree
- Nearest neighbour
- Fourier / wavelet bases
- ...
下面我们研究的DQN（Deep Q Network）就是采用Deep neural network进行动作值函数逼近的一种方法，结构如下。
为推导方便，假设中间的Network为一层的全连接，即\(\hat{V}(s, a)=x(S)^{T}w=\sum_{j=1}^{n}{x_{j}(S)w_{j}}\)，代价函数选择最小均方误差：\(J(w)=\frac{1}{2}(V(s,a)-\hat{V}(s,a))^2\)，采用随机梯度下降算法进行优化。
\[\begin{split}\frac{\partial{J(w)}}{\partial{w}}&=\left(V(s,a)-\hat{V}(s,a)\right)\frac{\partial{\hat{V}(s,a)}} {\partial{w}} \\ &=\left(V(s,a)-\hat{V}(s,a)\right)x(S) \end{split}\tag{1-1}\]
\[\begin{split}w^k&=w^{k-1}+\eta \Delta(w)\\&=w^{k-1}-\eta \frac{\partial{J(w)}}{\partial{w}}\\&=w^{k-1}-\eta \left(V(s,a)-\hat{V}(s,a;w^{k})\right)x(S)\end{split}\tag{1-2}\]
由于我们并没有动作值函数的真实值，因此与Q learning类似，\(V(s,a,)\)可以使用下一个状态的动作值函数进行估计，即\(V(s,a)=V(s,a;w^{k-1})=r+\gamma \max_{a^{'}}V(s^{'},a^{'};w^{k-1})\)。
整个训练过程仍然与Q learning一样，采用\(\epsilon-greedy\)策略选择动作，并按照公式(1-2)更新权重\(w\)，实际上也就更新了策略的动作值函数。使用值函数逼近的方法不需要枚举每个状态动作对，突破了状态数的限制，使得Q learning在一些复杂任务上得到广泛应用，但仍然没有解决动作数爆炸或者连续动作的问题。
DQN
DQN最先出现于DeepMind发表的【Playing Atari with Deep Reinforcement Learning】论文中，由于需要直接输入图像画面，因此论文中使用CNN来表示Q函数，下面简单剖析一下该论文。
使用的是典型的CNN，其结构为：
与一般的CNN有所不同的是，没有pooling层，因为我们这里不是做图像分类，pooling层带来的旋转和数值不变性对分类是有作用的，但在这个任务中对物体的具体位置是非常敏感的，因此移除了pooling层。
Atari原始的游戏帧为210*160像素的RGB图像，由于该任务对画面色彩不敏感，为了减少计算开销，将游戏帧预处理成84*84的灰度图像。但为了获得动态特征，最终是将前3帧图像与当前帧stack到一起组成一个4*84*84的图像作为CNN的输入，输出为每个动作对应的Q值。
经验回放
现在我们知道可以使用Q learning去估计每个状态的未来回报的期望，并且可以使用CNN去逼近动作值函数，也就是可以使用DQN去解决一个复杂的MDP任务。但在实际应用时会出现更新波动较大，导致收敛非常慢的问题，DeepMind因此使用了一个经验回放（Experience Replay）机制，就是将每步的经验数据\(<s,a,r,s^{'}>\)存放在回放内存中，更新时都从回放内存中随机采样一个batch的数据进行更新。
经验回放机制相比标准的DQN有两个好处：首先每一步的经验数据会被保存起来，更新时可以多次使用到经验数据，使得数据利用更高效；此外直接从连续的样本中学习是低效的，因为一个episode内样本具有很强的相关性，随机挑选样本打破了这种相关性，因此减小了更新时的变化，使得更新更加稳定（注：因为同一次实验过程的样本相关性很强，不同实验之间的相关性就显得相对比较小，如果使用连续的样本进行训练，在切换到下一次实验的样本时会导致模型更新不稳定）。
由于内存大小限制，回放内存不可能将所有的经验数据都保存起来，因此只会保留最新的N组经验数据，比较久远的数据就会被遗忘。
训练
DeepMind使用DQN对 ATARI中七个游戏进行了实验，由于每个游戏的得分尺度不一致，因此他们将得分分为正回报、负回报和无回报，正回报得分为1，负回报得分为-1，无回报得分为0。
使用 RMSProp算法进行优化，batch size为32，采用\(\epsilon-greedy\)行动策略，前一百万帧的\(\epsilon\)从1线性减少到0.1，最后固定为0.1。总共训练了一千万帧，并且使用了一百万大小的回放内存。
训练过程伪代码：
Gym使用
Gym简介
目前强化学习的研究主要由DeepMind和OpenAI两家在主导，去年底到今年初DeepMind和OpenAI相继开源了自家的3D learning environment平台DeepMind Lab和Universe。DeepMind Lab目前给出的文档和例子都比较少，使用也稍显复杂，所以暂时可以不考虑使用。Universe包含了1000+的游戏环境，并且将程序打包在docker环境中运行，提供与Gym一致的接口。Universe的环境由一个client和一个remote组成，client是一个VNCenv，主要负责接收agent的动作，传递回报和管理本地episode的状态，remote是指在docker环境中运行的程序，remote可以运行在本地、远程服务器或在cloud上。client和remote通过VNC远程桌面系统进行交互，通过WebSocket传递回报、诊断和控制信息。
由于Universe环境提供Gym接口，而Gym是OpenAI去年4月份发布的一套开发和比较强化学习算法的toolkit。Gym本身是可以独立于Universe使用的，并且Universe和Gym中agent代码基本没有什么区别。我们下面就单独讲讲Gym接口和如何使用Gym训练自己的agent。
Gym目前提供python接口，并支持任何的计算框架，比如tensorflow、theano等。强化学习解决的是agent和环境交互的任务，agent根据当前环境状态做出某个动作，然后观察下一个状态和回报，环境根据agent的动作转移到下一个状态，并发送回报。Gym提供的实际上是环境这个角色，每个Gym环境都提供一致的接口。
创建一个Gym环境
创建一个环境时只需要指定环境id，比如agent需要玩Atari Breakout-v0这个游戏，可以如下创建一个Breakout-v0的环境。
1 | import gym |
step
输入agent的动作，返回4个值，分别为：
- observation：表示agent观察到的下一个状态，比如在一些游戏中，observation为RGB的图像
- reward：表示执行输入的动作后得到的回报值
- done：表示返回的observation是不是结束状态
- info：调试信息，一般没什么用处
1 | next_state, reward, terminal, _ = env.step(action) |
reset
在开始一个新的episode时，Gym环境都要reset，获得一个初始状态。
1 | init_state = env.reset() |
render
render是Gym用来渲染环境状态的函数，当调用该函数时会出现一个动图框。一般agent执行一个动作，环境都要渲染一次，这样就可以实时看到agent的执行情况了。
1 | env.render() |
Spaces
Gym环境有两个space属性，一个是action_space，一个是observation_space，分别表示该Gym环境下合法的动作和状态。action_space是Gym中的一个Discrete对象，Discrete对象有一个成员n，表示合法的动作数，比如Discrete(2)表示有两个合法动作，编号从0开始，因此两个动作编号为0和1。observation_space是Gym中的一个Box对象，Box的shape表示observation的数据组织方式，比如Box(210, 160, 3)表示合法的observation是一个210*160*3的数组，而Box(4,)表示observation是一个大小为4的向量。
1 | observation_space = env.observation_space # observation_space: Discrete(6) |
Breakout-v0例子
采用了github上Flood Sung的DQN实现，感谢Flood Sung大神的无私贡献。
1 | # ----------------------------- |
下面是使用上面的DQN让agent玩Gym的Breakout-v0游戏。
1 | # ------------------------- |
参考资料
1、Reinforcement Learning: An Introduction, Richard S. Sutton and
Andrew G. Barto，2012
2、Playing Atari with Deep Reinforcement Learning，DeepMind
Technologies，Arxiv 2013.12
3、Human-level control through deep reinforcement learning，DeepMind
Technologies，Nature 2015.02
4、DeepMind官网
https://deepmind.com/blog/deep-reinforcement-learning
5、https://www.nervanasys.com/demystifying-deep-reinforcement-learning
6、http://www.cnblogs.com/jinxulin/p/3511298.html
7、Introduction to Reinforcement Learning，David Silver
