强化学习(二)
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