曹天明kosora作者

使用DQN算法实现游戏智能

刚刚举行的 WAVE SUMMIT 2019 深度学习开发者峰会上,PaddlePaddle 发布了 PARL 1.1 版本,这一版新增了 IMPALA、A3C、A2C 等一系列并行算法。作者重新测试了一遍内置 example,发现卷积速度也明显加快,从 1.0 版本的训练一帧需大约 1 秒优化到了 0.15 秒(配置:win8,i5-6200U,GeForce-940M,batch-size=32)。

嘿嘿,超级本实现游戏智能的时代终于来临!废话不多说,我们赶紧试试 PARL 的官方 DQN 算法,玩一玩 Flappy-Bird。

关于作者:曹天明(kosora),2011 年毕业于天津科技大学,7 年的 PHP+Java 经验。个人研究方向——融合 CLRS 与 DRL 两大技术体系,并行刷题和模型训练。专注于游戏智能、少儿趣味编程两大领域。

模拟环境

相信大家对于这个游戏并不陌生,我们需要控制一只小鸟向前飞行,只有飞翔、下落两种操作,小鸟每穿过一根柱子,总分就会增加。由于柱子是高低不平的,所以需要想尽办法躲避它们。一旦碰到了柱子,或者碰到了上、下边缘,都会导致 game-over。下图展示了未经训练的小笨鸟,可以看到,他处于人工智障的状态,经常撞柱子或者撞草地:

 未经训练的小笨鸟

先简要分析一下环境 Environment 的主要代码。

BirdEnv.py 继承自 gym.Env,实现了 init、reset、reward、render 等标准接口。init 函数,用于加载图片、声音等外部文件,并初始化得分、小鸟位置、上下边缘、水管位置等环境信息:

def __init__(self):
    if not hasattr(self,'IMAGES'):
        print('InitGame!')
        self.beforeInit()
    self.score = self.playerIndex = self.loopIter = 0
    self.playerx = int(SCREENWIDTH * 0.3)
    self.playery = int((SCREENHEIGHT - self.PLAYER_HEIGHT) / 2.25)
    self.baseShift = self.IMAGES['base'].get_width() - self.BACKGROUND_WIDTH
    newPipe1 = getRandomPipe(self.PIPE_HEIGHT)
    newPipe2 = getRandomPipe(self.PIPE_HEIGHT)
    #...other code

step 函数,执行两个动作,0 表示不采取行动(小鸟会自动下落),1 表示飞翔;step 函数有四个返回值,image_data 表示当前状态,也就是游戏画面,reward 表示本次 step 的即时奖励,terminal 表示是否是吸收状态,{} 表示其他信息:

def step(self, input_action=0):
    pygame.event.pump()
    reward = 0.1
    terminal = False
    if input_action == 1:
        if self.playery > -2 * self.PLAYER_HEIGHT:
            self.playerVelY = self.playerFlapAcc
            self.playerFlapped = True
   #...other code

   image_data=self.render()
   return image_data, reward, terminal,{}

奖励 reward;初始奖励是 +0.1,表示小鸟向前飞行一小段距离;穿过柱子,奖励 +1;撞到柱子,奖励为 -1,并且到达 terminal 状态:

#飞行一段距离,奖励+0.1
reward = 0.1
#...other code

playerMidPos = self.playerx + self.PLAYER_WIDTH / 2
for pipe in self.upperPipes:
    pipeMidPos = pipe['x'] + self.PIPE_WIDTH / 2
    #穿过一个柱子奖励加1
    if pipeMidPos <= playerMidPos < pipeMidPos + 4:             
        self.score += 1
        reward = self.reward(1)
#...other code

if isCrash:
    #撞到边缘或者撞到柱子,结束,并且奖励为-1
    terminal = True
    reward = self.reward(-1)

reward 函数,返回即时奖励 r:

def reward(self,r):
    return r

reset 函数,调用 init,并执行一次飞翔操作,返回 observation,reward,isOver:

def reset(self,mode='train'):
    self.__init__()
    self.mode=mode
    action0 = 1
    observation, reward, isOver,_ = self.step(action0)
    return observation,reward,isOver

render 函数,渲染游戏界面,并返回当前画面:

def render(self):
    image_data = pygame.surfarray.array3d(pygame.display.get_surface())
    pygame.display.update()
    self.FPSCLOCK.tick(FPS)
    return image_data

至此,强化学习所需的状态、动作、奖励等功能均定义完毕。接下来简单推导一下 DQN (Deep-Q-Network) 算法的原理。

DQN的发展过程

DQN 的进化历史可谓源远流长,从最开始 Bellman 在 1956 年提出的动态规划,到后来 Watkins 在 1989 年提出的的 Q-learning,再到 DeepMind 的 Nature-2015 稳定版,最后到 Dueling DQN、Priority Replay Memory、Parameter Noise 等优化算法,横跨整整一个甲子,凝聚了无数专家、教授们的心血。如今的我们站在先贤们的肩膀上,从以下角度逐步分析:

  • 贝尔曼(最优)方程与 VQ 树

  • Q-learning

  • 参数化逼近

  • DQN 算法框架

贝尔曼 (最优) 方程与VQ树

我们从经典的表格型强化学习(Tabular Reinforcement Learning)开始,回忆一下马尔可夫决策(MDP)过程,MDP 可由五元组 (S,A,P,R,γ) 表示,其中:

  • S 状态集合,维度为 1×|S| 

  • A 动作集合,维度为 1×|A| 

  • P 状态转移概率矩阵,经常写成,其维度为 |S|×|A|×|S| 

  • R 回报函数,如果依赖于状态值函数 V,维度为 1×|S|,如果依赖于状态-动作值函数 Q,则维度为 |S|×|A| 

  • γ 折扣因子,用来计算带折扣的累计回报 G(t),维度为 1 

S、A、R、γ 均不难理解,可能部分同学对有疑问——既然 S 和 A 确定了,下一个状态 S' 不是也确定了吗?为什么会有概率转移矩阵呢?

其实我初学的时候也曾经被这个问题困扰过,不妨通过如下两个例子以示区别:

1. 恒等于 1.0 的情况。如图 1 所示,也就是上一次我们在策略梯度算法中所使用的迷宫,假设机器人处于左上角,这时候你命令机器人向右走,那么他转移到红框所示位置的概率就是 1.0,不会有任何异议:

 图1. 迷宫寻宝

2. 不等于 1.0 的情况。假设现在我们下一个飞行棋,如图 2 所示。有两种骰子,第一种是普通的正方体骰子,可以投出 1~6,第二种是正四面体的骰子,可以投出 1~4。现在飞机处于红框所示的位置,现在我们选择投掷第二种骰子这个动作,由于骰子本身具有均匀随机性,所以飞机转移到终点的概率仅仅是 0.25。这就说明,在某些环境中,给定 S、A 的情况下,转移到具体哪一个 S' 其实是不确定的:

 图2. 飞行棋

除了经典的五元组外,为了研究长期回报,还经常加入三个重要的元素,分别是:

  • 策略 π(a∣s),维度为 |S|×|A|

  • 状态值函数,维度为 1×|S|,表示当智能体采用策略 π 时,累积回报在状态 s 处的期望值:

 图3. 状态值函数


  • 状态-行为值函数,也叫状态-动作值函数,维度为 |S|×|A|,表示当智能体采取策略 π 时,累计回报在状态 s 处并执行动作 a 时的期望值:

 图4. 状态-行为值函数

知道了 π、v、q 的具体含义后,我们来看一个重要的概念,也就是 V、Q 的递归展开式。

学过动态规划的同学都知道,动态规划本质上是一个 bootstrap(自举)问题,它包含最优子结构重叠子问题两个性质,也就是说,通常有两种方法解决动态规划

  • 将总问题划分为 k 个子问题,递归求解这些子问题,然后将子问题进行合并,得到总问题的最优解;对于重复的子问题,我们可以将他们进行缓存(记忆搜索 MemorySearch,请回忆 f(n)=f(n-1)+f(n-2) 这个递归程序);

  • 计算最小的子问题,合并这些子问题产生一个更大的子问题,不断的自底向上计算,随着子问题的规模越来越大,我们会得到最终的总问题的最优解(打表 DP,请回忆杨辉三角中的 dp[i-1,j-1]+dp[i-1,j]=dp[i,j])。

这两种切题技巧,对于有过 ACM 或者 LeetCode 刷题经验的同学,可以说是老朋友了,那么能否把以上思想迁移到强化学习呢?答案是肯定的!

分别考虑 v、q 的展开式:

  • 处在状态 s 时,由于有策略 π 的存在,故可以把状态值函数 v 展开成以下形式:

 图5. v展开成q

这个公式表示:在状态 s 处的值函数,等于采取策略 π 时,所有状态-行为值函数的总和。

  • 处在状态 s、并执行动作 a,可以把状态-行为值函数 q 展开成以下形式:

 图6. q展开成v

这个公式表示:在状态 s 采用动作 a 的状态行为值函数,等于回报加上后序可能产生的的状态值函数的总和。

我们可以看到:v 可以展开成 q,同时 q 也可以展开成 v。

所以可以用以下 v、q 节点相隔的树来表示以上两个公式,这颗树比纯粹的公式更容易理解,我习惯上把它叫做 V-Q 树,它显然是一个递归的结构:

 图7. V-Q树

注意画红圈中的两个节点,体现了重叠子问题特性。如何理解这个性质呢?不妨回忆一下上文提到的飞行棋,假设飞机处在起点位置 1,那么无论投掷 1 号骰子还是 2 号骰子,都是有机会可以到达位置 3 的,这就是重叠子问题的一个例子。

有了这棵递归树之后,就不难推导出 v 和 v',以及 q 和 q' 自身的递归展开式:

 图8. 状态值函数v自身的递归展开式

 图9. 状态-行为值函数q自身的递归展开式

其实无论是 v 还是 q,都拥有最优子结构特性。不妨利用反证法加以证明:

假设要求总问题 V(s) 的最优解,那么它包含的每个子问题 V(s') 也必须是最优解;否则,如果某个子问题 V(s') 不是最优,那么必然有一个更优的子问题 V'(s') 存在,使得总问题 V'(s) 比原来的总问题 V(s) 更优,与我们的假设相矛盾,故最优子结构性质得证,q(s) 的最优子结构性质同理。

计算值函数的目的是为了构建学习算法得到最优策略,每个策略对应着一个状态值函数,最优策略自然也对应着最优状态值函数,故而定义如下两个函数:

  • 最优状态值函数,表示在所有策略中最大的值函数,即:

 图10. 最优状态值函数

  • 最优状态-行为值函数,表示在所有策略中最大的状态-行为值函数:

 图11. 最优状态-行为值函数

结合上文的递归展开式和最优子结构性质,可以得到 v 与 q 的贝尔曼最优方程

 图12. v的贝尔曼最优方程

 图13. q的贝尔曼最优方程

重点理解第二个公式,也就是关于 q 的贝尔曼最优方程,它是今天的主角 Q-learning 以及 DQN 的理论基础。

有了贝尔曼最优方程,我们就可以通过纯粹贪心的策略来确定 π,即:仅仅把最优动作的概率设置为 1,其他所有非最优动作的概率都设置为 0。这样做的好处是:当算法收敛的时候,策略 π(a|s) 必然是一个 one-hot 型的矩阵。用数学公式表达如下:

 图14. 算法收敛时候的策略π

强化学习中的动态规划方法实质上是一种 model-based(模型已知)方法,因为 MDP 五元组是已知的,特别是状态转移概率矩阵是已知的。

也就是说,所有的环境信息对于我们来说是 100% 完备的,故而可以对整个解空间树进行全局搜索,下图展示了动态规划方法的示意图,在确定根节点状态 S(t) 的最优值的时候,必须遍历他所有的 S(t+1) 子节点并选出最优解:


 图15. 动态规划方法的解空间搜索过程

不过,和传统的刷题动态规划略有不同,强化学习往往是利用值迭代(Value Iteration)、策略迭代(Policy Iteration)、策略改善(Policy Improve)等方式使 v、q、π 等元素达到收敛状态,当然也有直接利用矩阵求逆计算解析解的方法,有兴趣的同学可以参考相关文献,这里不再赘述。

Q-learning

上文提到的动态规划方法是一种 model-based 方法,仅仅适用于已知的情况。若状态转移概率矩阵未知,model-free(无模型)方法就派上用场了,上一期的 MCPG 算法就是一种典型的 model-free 方法。它搜索解空间的方式更像是 DFS(深度优先搜索),而且一条道走到黑,没有指针回溯的操作,下图展示了蒙特卡洛算法的求解示意图:

 图16. MC系列方法的解空间搜索过程

虽然每次只能走一条分支,但随机数发生器会帮助算法遍历整个解空间,再通过大量的迭代,所有节点也会收敛到最优解。

不过,MC 类方法有两个小缺点:

1. 使用作为训练标签,其本身就是值函数准确的无偏估计。但是,这也正是它的缺点,因为 MC 方法会经历很多随机的状态和动作,使得每次得到的 G(t) 随机性很大,具有很高的方差。

2. 由于采用的是一条道走到黑的方式从根节点遍历到叶子节点,所以必须要等到 episode 结束才能进行训练,而且每轮 episode 产生的数据只训练一次,每轮 episode 产生数据的 batch-size 还不一定相同,所以在训练过程中,MC 方法的 loss 函数(或者 TD-Error)的波动幅度较大,而数据利用效率不高。

那么,能否边产生数据边训练呢?可以!时序差分(Temporal-Difference-Learning,简称 TD)算法应运而生了。

时序差分学习是模拟(或者经历)一段序列,每行动一步(或者几步)就根据新状态的价值估计当前执行的状态价值。大致可以分为两个小类:

1. TD(0) 算法,只向后估计一个 step。其值函数更新公式为:

 图17. TD(0)算法的更新公式

其中,α 为学习率称为 TD 目标,MC 方法中的 G(t) 也可以叫做 TD 目标,称为 TD-Error,当模型收敛时,TD-Error 会无限接近于 0。

2. Sarsa(λ) 算法,向后估计 n 步,n 为有限值,还有一个衰减因子 λ。其值函数的更新公式为:

 图18. Sarsa(λ)算法的更新公式

 图19. 的计算方法

与 MC 方法相比,TD 方法只用到了一步或者有限步随机状态和动作,因此它是一个有偏估计。不过,由于 TD 目标的随机性比 MC 方法的 G(t) 要小,所以方差也比 MC 方法小的多,值函数的波动幅度较小,训练比较稳定。

看一下 TD 方法的解空间搜索示意图,红框表示 TD(0),蓝框表示 Sarsa(λ)。虽然每次估计都有一定的偏差,但随着算法的不断迭代,所有的节点也会收敛到最优解:

 图20. TD方法的解空间搜索过程

有了 TD 的框架,既然我们要求状态值函数 v、状态-行为值函数 q 的最优解,那么是否能直接选择最优的 TD 目标作为 Target 呢?答案是肯定的,这也是 Q-Learning 算法的基本思想,其公式如下所示:

 图21. Q-learning算法的学习公式

其中,动作 a 由 ε-greedy 策略选出,从而在状态 s 处执行 a 之后产生了另一个状态 s',接下来选出状态 s' 处最大的状态-行为值函数 q(s',a'),这样,TD 目标就可以确定为 R+γmax[a′]Q(s′,a′)。这种思想很像贪心算法中的总是选择在当前看来最优的决策,它一开始可能会得到一个局部最优解,不过没关系,随着算法的不断迭代,整个解空间树也会收敛到全局最优解。

以下是 Q-learning 算法的伪代码,和 on-policy 的 MC 方法对应,它是一种 off-policy(异策略)方法:

#define maxEpisode=65535 //定义最大迭代轮数
#define maxStep=1024 //定义每一轮最多走多少步
initialize Q_table[|S|,|A|] //初始化Q矩阵
for i in range(0,maxEpisode):
    s=env.reset()  //初始化状态s
    for j in range(0,maxStep):
        //用ε-greedy策略在s行选一个动作a
        choose action a using ε-greedy from Q_table[s] 
        s',R,terminal,_=env.step(a) //执行动作a,得到下一个状态s',奖励R,是否结束terminal
        max_s_prime_action=np.max(Q_table[s',:]) //选s'对应的最大行为值函数
        td=R+γ*max_s_prime_action //计算TD目标
        Q_table[s,a]= Q_table[s,a]+α*(td-Q_table[s,a]) //学习Q(s,a)的值
        s=s' //更新s,注意,和sarsa算法不同,这里的a不用更新
        if terminal:
            break

Q-learning 是一种优秀的算法,不仅简单直观,而且平均速度比 MC 快。在 DRL 未出现之前,它在强化学习中的地位,差不多可以媲美 SVM 在机器学习中的地位。

参数化逼近

有了 Q-learning 算法,是否就能一招吃遍天下鲜了呢?答案是否定的,我们看一下它存在的问题。

上文所提到的,无论是 DP、MC 还是 TD,都是基于表格(tabular)的方法,当状态空间比较小的时候,计算机内存完全可以装下,表格式型强化学习是完全适用的。但遇到高阶魔方(三阶魔方的总变化数是)、围棋()这类问题时,S、V、Q、P 等表格均会出现维度灾难,早就超出了计算机内存甚至硬盘容量。这时候,参数化逼近方法就派上用场了。

所谓参数化逼近,是指值函数可以由一组参数 θ 来近似,如 Q-learning 中的 Q(s,a) 可以写成 Q(s,a|θ) 的形式。这样,不但降低了存储维度,还便于做一些额外的特征工程,而且 θ 更新的同时,Q(s,a|θ) 会进行整体更新,不仅避免了过拟合情况,还使得模型的泛化能力更强。

既然有了可训练参数,我们就要研究损失函数了,Q-Learning 的损失函数是什么呢?

先看一下 Q-Learning 的优化目标——使得 TD-Error 最小:

 图22. Q-Learning的优化目标

加入参数 θ 之后,若将 TD 目标作为标签 target,将 Q(s,a) 作为模型的输出 y,则问题转化为:

 图23. 带参数的优化目标

这是我们所熟悉的监督学习中的回归问题,显然 loss 函数就是 mse,故而可以用梯度下降算法最小化 loss,从而更新参数 θ:

 图24. loss函数的梯度下降公式

注意到,TD 目标是标签,所以 Q(s',a'|θ) 中的 θ 是不能更新的,这种方法并非完全的梯度法,只有部分梯度,称为半梯度法,这是 NIPS-2013 的雏形。

后来,DeepMind 在 Nature-2015 版本中将 TD 网络单独分开,其参数为 θ',它本身并不参与训练,而是每隔固定步数将值函数逼近的网络参数 θ 拷贝给 θ',这样保证了 DQN 的训练更加稳定:

 图25. 含有目标网络参数θ'的梯度下降公式

至此,DQN 的 Loss 函数、梯度下降公式推导完毕。

DQN算法框架

接下来,还要解决两个问题——数据从哪里来?如何采集?

针对以上两个问题,DeepMind 团队提出了深度强化学习的全新训练方法:经验回放(experience replay)。

强化学习过程中,智能体将数据存储到一个 ReplayBuffer 中(任何一种集合,可以是哈希表、数组、队列,也可以是数据库),然后利用均匀随机采样的方法从 ReplayBuffer 中抽取数据,这些数据就可以进行 Mini-Batch-SGD,这样就打破了数据之间的相关性,使得数据之间尽量符合独立同分布原则。

DQN 的基本网络结构如下:

 图26. DQN的基本网络结构

要特别注意:

1. 与参数 θ 做线性运算 (wx+b) 的仅仅是输入状态 s,这一步没有动作 a 的参与;

2. output_1 的维度为 |A|,表示神经网络 Q(s,θ) 的输出;

3. 输入动作 a 是 one-hot,与 output_1 作哈达马积后产生的 output_2 是一个数字,作为损失函数中的 Q(s,a|θ),也就是 y。

以下是 DQN 算法的伪代码:

#Deep-Q-Network,Nature 2015 version

#定义为一个双端队列D,作为经验回放区域,最大长度为max_size
Initialize replay_memory D as a deque,mas_size=50000

#初始化状态-行为值函数Q的神经网络,权值随机
Initialize action-value function Q(s,a|θ) as Neural Network with random-weights-initializer

#初始化TD目标网络,初始权值和θ相等
Initialize target action-value function Q(s,a|θ) with weights θ'=θ

#迭代max_episode个轮次
for episode in range(0,max_episode=65535):

    #重置环境env,得到初始状态s
    s=env.reset()

    #循环事件的每一步,最多迭代max_step_limit个step
    for step in range(0,max_step_limit=1024):

        #通过ε-greedy的方式选出一个动作action
        With probability ε select a random action a or select a=argmax(Q(s,θ))

        #在env中执行动作a,得到下一个状态s',奖励R,是否终止terminal
        s',R,terminal,_=env.step(a)

        #将五元组(s,a,s',R,terminal)压进队尾
        D.addLast(s,a,s',R,terminal)

        #如果队列满,弹出队头元素
        if D.isFull():
            D.removeFirst()

        #更新状态s
        s=s'

        #从队列中进行随机采样
        batch_experience[s,a,s',R,terminal]=random_select(D,batch_size=32)

        #计算TD目标
        target = R + γ*(1- terminal) * np.max(Q(s',θ'))

        #对loss函数执行Gradient-decent,训练参数θ
        θ=θ+α*(target-Q(s,a|θ))▽Q(s,a|θ)

        #每隔C步,同步θ与θ'的权值
        Every C steps set θ'=θ

        #是否结束
        if terminal:
           break 

我们玩的游戏 Flappy-Bird,它的输入是一帧一帧的图片,所以,经典的 Atari-CNN 模型就可以派上用场了:

 图27. Atari游戏的CNN网络结构

网络的输入是被处理成灰度图的最近 4 帧 84*84 图像(4 是经验值),经过若干 CNN 和 FullyConnect 后,输出各个动作所对应的状态-行为值函数 Q。以下是每一层的具体参数,由于 atari 游戏最多有 18 个动作,所以最后一层的维度是 18:

 图28. 神经网络的具体参数

至此,理论部分推导完毕。下面,我们分析一下 PARL 中的 DQN 部分的源码,并实现 Flappy-Bird 的游戏智能。

代码实现

依次分析 env、model、algorithm、agent、replay_memory、train 等模块。

1. BirdEnv.py,环境;上文已经分析过了。

2. BirdModel.py,神经网络模型;使用三层 CNN+两层 FC,CNN 的 padding 方式都是 valid,最后输出状态-行为值函数 Q,维度为 |A|。注意输入图片归一化,并按照官方模板填入代码:

class BirdModel(Model):
    def __init__(self, act_dim):
        self.act_dim = act_dim
        #padding方式为valid
        p_valid=0
        self.conv1 = layers.conv2d(
            num_filters=32, filter_size=8, stride=4, padding=p_valid, act='relu')
        self.conv2 = layers.conv2d(
            num_filters=64, filter_size=4, stride=2, padding=p_valid, act='relu')
        self.conv3 = layers.conv2d(
            num_filters=64, filter_size=3, stride=1, padding=p_valid, act='relu')
        self.fc0=layers.fc(size=512)
        self.fc1 = layers.fc(size=act_dim)

    def value(self, obs):
        #输入归一化
        obs = obs / 255.0
        out = self.conv1(obs)
        out = self.conv2(out)
        out = self.conv3(out)
        out = layers.flatten(out, axis=1)
        out = self.fc0(out)
        out = self.fc1(out)
        return out

3. dqn.py,算法层;官方仓库已经提供好了,我们无需自己再写,直接复用算法库(parl.algorithms)里边的 DQN 算法即可。 

简单分析一下 DQN 的源码实现。

define_learn 函数,用于神经网络的学习。接收 [状态 obs, 动作 action, 即时奖励 reward, 下一个状态 next_obs, 是否终止 terminal] 这样一个五元组,代码实现如下:

#根据obs以及参数θ计算状态-行为值函数pred_value,对应伪代码中的Q(s,θ)
pred_value = self.model.value(obs)

#根据next_obs以及参数θ'计算目标网络的状态-行为值函数next_pred_value,对应伪代码中的Q(s',θ')
next_pred_value = self.target_model.value(next_obs)

#选出next_pred_value的最大值best_v,对应伪代码中的np.max(Q(s',θ'));注意θ'不参与训练,所以要stop_gradient
best_v = layers.reduce_max(next_pred_value, dim=1)
best_v.stop_gradient = True

#计算TD目标
target = reward + (1.0 - layers.cast(terminal, dtype='float32')) * self.gamma * best_v

#输入的动作action与pred_value作哈达玛积,选出要评估的状态-行为值函数pred_action_value,对应伪代码中的 Q(s,a|θ)
action_onehot = layers.one_hot(action, self.action_dim)
action_onehot = layers.cast(action_onehot, dtype='float32')
pred_action_value = layers.reduce_sum(layers.elementwise_mul(action_onehot, pred_value), dim=1)

#mse以及梯度下降,对应伪代码中的θ=θ+α*(target-Q(s,a|θ))▽Q(s,a|θ)
cost = layers.square_error_cost(pred_action_value, target)
cost = layers.reduce_mean(cost)
optimizer = fluid.optimizer.Adam(self.lr, epsilon=1e-3)
optimizer.minimize(cost)

sync_target 函数用于同步网络参数

def sync_target(self, gpu_id):
    """ sync parameters of self.target_model with self.model
    """
    self.model.sync_params_to(self.target_model, gpu_id=gpu_id)

4. BirdAgent.py,智能体。其中,build_program 函数封装了 algorithm 中的 define_predict 和 define_learn,sample 函数以 ε-greedy 策略选择动作,predict 函数以 100% 贪心的策略选择 argmax 动作,learn 函数接收五元组 (obs, act, reward, next_obs, terminal) 完成学习功能,这些函数和 Policy-Gradient 的写法类似。

除了这些常用功能之外,由于游戏的训练时间比较长,所以附加了两个函数,save_params 用于保存模型,load_params 用于加载模型:

#保存模型
def save_params(self, learnDir,predictDir):
    fluid.io.save_params(
        executor=self.fluid_executor,
        dirname=learnDir,
        main_program=self.learn_programs[0])   
    fluid.io.save_params(
        executor=self.fluid_executor,
        dirname=predictDir,
        main_program=self.predict_programs[0])     

#加载模型
def load_params(self, learnDir,predictDir): 
    fluid.io.load_params(
        executor=self.fluid_executor,
        dirname=learnDir,
        main_program=self.learn_programs[0])  
    fluid.io.load_params(
        executor=self.fluid_executor,
        dirname=predictDir,
        main_program=self.predict_programs[0]) 

另外,还有四个超参数,可以进行微调:

#每训练多少步更新target网络,超参数可调
self.update_target_steps = 5000

#初始探索概率ε,超参数可微调
self.exploration = 0.8

#每步探索的衰减程度,超参数可微调
self.exploration_dacay=1e-6

#最小探索概率,超参数可微调
self.min_exploration=0.05

5. replay_memory.py,经验回放单元。双端队列 _context 是一个滑动窗口,用来记录最近 3 帧(再加上新产生的 1 帧就是 4 帧);state、action、reward 等用 numpy 数组存储,因为 numpy 的功能比双端队列更丰富,max_size 表示 replay_memory 的最大容量:

self.state = np.zeros((self.max_size, ) + state_shape, dtype='int32')
self.action = np.zeros((self.max_size, ), dtype='int32')
self.reward = np.zeros((self.max_size, ), dtype='float32')
self.isOver = np.zeros((self.max_size, ), dtype='bool')
#_context是一个滑动窗口,长度永远保持3
self._context = deque(maxlen=context_len - 1)

其他的 append、recent_state、sample_batch 等函数并不难理解,都是基于 numpy 数组的进一步封装,略过一遍即可看懂。

6. Train_Test_Working_Flow.py,训练与测试,让环境 evn 和智能体 agent 进行交互。最重要的就是 run_train_episode 函数,体现了 DQN 的主要逻辑,重点分析注释部分与 DQN 伪代码的对应关系,其他都是编程细节:

 #训练一个episode
def run_train_episode(env, agent, rpm):
    global trainEpisode
    global meanReward
    total_reward = 0
    all_cost = []
    #重置环境
    state,_, __ = env.reset()
    step = 0
    #循环每一步
    while True:
        context = rpm.recent_state()
        context.append(resizeBirdrToAtari(state))
        context = np.stack(context, axis=0)
        #用ε-greedy的方式选一个动作
        action = agent.sample(context)
        #执行动作
        next_state, reward, isOver,_ = env.step(action)
        step += 1
        #存入replay_buffer
        rpm.append(Experience(resizeBirdrToAtari(state), action, reward, isOver))
        if rpm.size() > MEMORY_WARMUP_SIZE:
            if step % UPDATE_FREQ == 0:
                #从replay_buffer中随机采样
                batch_all_state, batch_action, batch_reward, batch_isOver = rpm.sample_batch(batchSize)
                batch_state = batch_all_state[:, :CONTEXT_LEN, :, :]
                batch_next_state = batch_all_state[:, 1:, :, :]
                #执行SGD,训练参数θ
                cost=agent.learn(batch_state,batch_action, batch_reward,batch_next_state, batch_isOver)
                all_cost.append(float(cost))
        total_reward += reward
        state = next_state
        if isOver or step>=MAX_Step_Limit:
            break
    if all_cost:
        trainEpisode+=1
        #以滑动平均的方式打印平均奖励
        meanReward=meanReward+(total_reward-meanReward)/trainEpisode
        print('\n trainEpisode:{},total_reward:{:.2f}, meanReward:{:.2f} mean_cost:{:.3f}'\
              .format(trainEpisode,total_reward, meanReward,np.mean(all_cost)))
    return total_reward, step

除了主要逻辑外,还有一些常见的优化手段,防止训练过程中出现 trick:

#充满replay-memory,使其达到warm-up-size才开始训练
MEMORY_WARMUP_SIZE = MEMORY_SIZE//20

##一轮episode最多执行多少次step,不然小鸟会无限制的飞下去,相当于gym.env中的_max_episode_steps属性
MAX_Step_Limit=int(1<<12)

#用一个双端队列记录最近16次episode的平均奖励
avgQueue=deque(maxlen=16)

另外,还有其他一些超参数,比如学习率 LEARNING_RATE、衰减因子 GAMMA、记录日志的频率 log_freq 等等,都可以进行微调:

#衰减因子
GAMMA = 0.99

#学习率
LEARNING_RATE = 1e-3 * 0.5

#记录日志的频率
log_freq=10

main 函数在这里,输入 train 训练网络,输入 test 进行测试:

if __name__ == '__main__':
    print("train or test ?")
    mode=input()
    print(mode)
    if mode=='train':
        train()
    elif mode=='test':
        test()
    else:
        print('Invalid input!')

这是模型在我本机训练的输出日志,大概 3300 个 episode、50 万步之后,模型就收敛了:

 图29. 模型训练的输出日志

平均奖励:

 图30. 最近16次平均奖励变化曲线

各位同学可以试着调节超参数,或者修改网络模型,看看能不能遇到一些坑?哪些因素会影响训练效率?如何提升收敛速度?

接下来就是见证奇迹的时刻,当初懵懂的小笨鸟,如今已修炼成精了!

 训练完的FlappyBird

观看 4 分钟完整版:https://www.bilibili.com/video/av49282860/
Github源码https://github.com/kosoraYintai/PARL-Sample/tree/master/flappy_bird

参考文献
[1] Bellman, R.E. & Dreyfus, S.E. (1962). Applied dynamic programming. RAND Corporation. 
[2] Sutton, R.S. (1988). Learning to predict by the methods of temporal difference.Machine Learning, 3, pp. 9–44.
[3] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, et al., "Human-level control through deep reinforcement learning," Nature, vol. 518(7540), pp. 529-533, 2015.
[4] https://leetcode.com/problems/climbing-stairs/ 
[5] https://leetcode.com/problems/pascals-triangle-ii/ 
[6] https://github.com/yenchenlin/DeepLearningFlappyBird
[7] https://github.com/MorvanZhou/Reinforcement-learning-with-tensorflow

PaddlePaddle
PaddlePaddle

PaddlePaddle是百度独立研发的深度学习平台,易用,高效,灵活可伸缩,可支持海量图像识别分类、机器翻译和自动驾驶等多个领域业务需求,现已全面开源。

工程模型训练
2
相关数据
DeepMind机构

DeepMind是一家英国的人工智能公司。公司创建于2010年,最初名称是DeepMind科技(DeepMind Technologies Limited),在2014年被谷歌收购。在2010年由杰米斯·哈萨比斯,谢恩·列格和穆斯塔法·苏莱曼成立创业公司。继AlphaGo之后,Google DeepMind首席执行官杰米斯·哈萨比斯表示将研究用人工智能与人类玩其他游戏,例如即时战略游戏《星际争霸II》(StarCraft II)。深度AI如果能直接使用在其他各种不同领域,除了未来能玩不同的游戏外,例如自动驾驶、投资顾问、音乐评论、甚至司法判决等等目前需要人脑才能处理的工作,基本上也可以直接使用相同的神经网上去学而习得与人类相同的思考力。

深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

动态规划技术

动态规划(也称为动态优化),是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划将复杂的问题分解成一系列相对简单的子问题,只解决一次子问题并存储它的解决方案(solution),下一次遇到同样的子问题时无需重新计算它的解决方案,而是简单地查找先前计算的解决方案,从而节省计算时间。动态规划适用于有最优子结构(Optimal Substructure)和重叠子问题(Overlapping Subproblems)性质的问题。

深度强化学习技术

强化学习(Reinforcement Learning)是主体(agent)通过与周围环境的交互来进行学习。强化学习主体(RL agent)每采取一次动作(action)就会得到一个相应的数值奖励(numerical reward),这个奖励表示此次动作的好坏。通过与环境的交互,综合考虑过去的经验(exploitation)和未知的探索(exploration),强化学习主体通过试错的方式(trial and error)学会如何采取下一步的动作,而无需人类显性地告诉它该采取哪个动作。强化学习主体的目标是学习通过执行一系列的动作来最大化累积的奖励(accumulated reward)。 一般来说,真实世界中的强化学习问题包括巨大的状态空间(state spaces)和动作空间(action spaces),传统的强化学习方法会受限于维数灾难(curse of dimensionality)。借助于深度学习中的神经网络,强化学习主体可以直接从原始输入数据(如游戏图像)中提取和学习特征知识,然后根据提取出的特征信息再利用传统的强化学习算法(如TD Learning,SARSA,Q-Learnin)学习控制策略(如游戏策略),而无需人工提取或启发式学习特征。这种结合了深度学习的强化学习方法称为深度强化学习。

策略迭代技术

策略迭代算法直接操纵策略,而不是通过最优值函数间接找到策略。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

深度优先搜索技术

深度优先搜索算法是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

学习率技术

在使用不同优化器(例如随机梯度下降,Adam)神经网络相关训练中,学习速率作为一个超参数控制了权重更新的幅度,以及训练的速度和精度。学习速率太大容易导致目标(代价)函数波动较大从而难以找到最优,而弱学习速率设置太小,则会导致收敛过慢耗时太长

损失函数技术

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

伪代码技术

伪代码,又称为虚拟代码,是高层次描述算法的一种方法。它不是一种现实存在的编程语言;它可能综合使用多种编程语言的语法、保留字,甚至会用到自然语言。 它以编程语言的书写形式指明算法的职能。相比于程序语言它更类似自然语言。它是半形式化、不标准的语言。

数据库技术

数据库,简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以对文件中的数据运行新增、截取、更新、删除等操作。 所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

时序差分学习技术

时间差(TD)学习是一种基于预测的机器学习方法。 它主要用于强化学习问题,被称为是“蒙特卡罗思想和动态规划(DP)思想的结合”。 TD类似于蒙特卡洛方法,因为它通过对环境进行取样来学习 一些策略;其与动态规划技术相关,因为它基于先前学习的预估(自助法的过程)对当前状态进行近似估计。 TD学习算法也与动物学习的时间差模型有关

特征工程技术

特征工程是利用数据所在领域的相关知识来构建特征,使得机器学习算法发挥其最佳的过程。它是机器学习中的一个基本应用,实现难度大且代价高。采用自动特征工程方法可以省去采用人工特征工程的需求。Andrew Ng 说“挖掘特征是困难、费时且需要专业知识的事,应用机器学习其实基本上是在做特征工程。”

Q学习技术

Q学习是一种用于机器学习的强化学习技术。 Q-Learning的目标是学习一种策略,告诉智能体在什么情况下要采取什么行动。 它不需要对环境建模,可以处理随机转换和奖励的问题,而无需进行调整。

监督学习技术

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

独立同分布技术

在概率论与统计学中,独立同分布(缩写为IID)是指一组随机变量中每个变量的概率分布都相同,且这些随机变量互相独立。一组随机变量独立同分布并不意味着它们的样本空间中每个事件发生概率都相同。例如,投掷非均匀骰子得到的结果序列是独立同分布的,但掷出每个面朝上的概率并不相同。

贪心算法技术

贪心法,又称贪心算法、贪婪算法、或称贪婪法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中,如果旅行员每次都选择最近的城市,那这就是一种贪心算法。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

暂无评论
暂无评论~