深度增强学习系列:Black-Box Optimization

围棋因其巨大的计算复杂度一度被认为是极难被人工智能攻克的一个领域,AlphaGo在围棋项目上击败李世乭之后,新兴的人工智能技术又引起了广泛的关注,人工智能在经历数次低估之后,似乎又有了新的曙光,而本系列要讲述的正是AlphaGo成功的关键算法 - 深度增强学习(Deep Reinforcement Learning)

什么是增强学习(Reinforcement Learning)

imgage

在人工智能领域,通常定义一个学习到某些知识并具有了决策能力的个体为Agent,Agent会从环境(Environment)获取一些观察(Observation),从而执行某种动作(Action),最后这个动作会获的某种奖励(Reward)。强化学习就是一类可以训练Agent做出正确决策的机器学习算法。这里以训练一个Agent学习打乒乓球为例,乒乓球从Agent左前方30度位置飞来(观察),Agent做出了决策向左移动15cm挥拍(动作),结果正确击中了乒乓球(奖励),如果经历过N次这个过程,增强学习就会根据每种情形下的动作获取的奖励来进行训练,让Agent学习到如何做出正确的挥拍动作,提高成功率。

让机器学会打乒乓球的一个实例,感兴趣的朋友可以看下:http://karpathy.github.io/2016/05/31/rl/

什么是深度增强学习(Deep Reinforcement Learning)

深度增强学习是将增强学习与深度学习相结合产生的一类新的机器学习算法。它实现了从Perception感知到Action动作的端对端学习,其真正成功的开端是DeepMind在NIPS 2013上发表的[Playing Atari with Deep Reinforcement Learning]一文,之后DeepMind在Nature上发表了改进版的DQN文章,引起了广泛的关注。尤其是AlphaGo在围棋大赛战胜李世乭以后,深度增强学习方法被认为是通往通用学习机器的一把有力钥匙。

提到深度增强学习,大家可能首先想到的是著名的DQN算法,它是Q-Learning结合深度神经网络形成的。传统的强化学习算法在面临高维输入问题的时候,其Q矩阵往往面临维度爆炸,无法进行有效训练,而如果使用神经网络来代替Q矩阵的作用,就诞生了一种新的深度增强方法-DQN。DQN是“价值迭代”类算法的一种,当然还有一个重要的分支“策略迭代”,其代表算法是策略梯度算法(Policy Gradients)。

因此,深度增强学习是传统的增强学习结合深度神经网络之后,诞生的一类通用性很强的增强学习算法。

本系列将基于John SchulmanMLSS-2016上的PPT来讲解Deep Reinforcement Learning 的几种常见的算法,可能适合对增强学习有一定了解的同学来参考。

黑盒优化

所谓黑盒优化,就是将强化学习的决策网络当作是一个黑盒来进行优化,仅关心输入和输出,而忽略其内部机制。我们知道增强学习的监督信号是Agent的一个动作(Action)所引起的奖励(Reward),其学习目标便是不断优化决策网络,使得所有动作的奖励最大化。决策网络通常可以是Q矩阵(如DQN),或者神经网络(如PG),也就是说决策网络通常是可以参数化的,这时候我们进行优化首先要考虑的是收敛性。以神经网络为例,它是一个参数化的多层网络,常用的优化方法可以是误差反向传播(BP),我们可以将激励目标作为调控信号,在参数网络上进行梯度下降,使得网络的输出目标尽可能获得最大激励,这其中的核心便是我们依赖“梯度”来保证收敛。

黑盒优化面临最大的问题就是“收敛性”问题,它是不依赖梯度的(Derivative Free Optimization Approach),只关心输入的动作和输出的奖励,如何保证收敛性?讨论收敛性问题显然超出了本文的讨论范畴,庆幸的是我们生活的宇宙恰好能够使这类算法几乎收敛,这种优化方法跟进化算法(EA)十分相似,而且 works embarrassingly well 。

OK,到这里我们可以总结下黑盒优化的目标函数了。
imgage

CMA-ES 算法的一个有趣的应用, 让机器自己学会站立走路

imgage

交叉熵方法(Cross-Entropy Method)

本文重点讨论的黑盒优化方法是交叉熵方法,它的工作机制跟进化算法里面的CMA-ES算法十分相似。基本流程如下:

imgage

其基本思路是从一个概率分布中采样出我们的策略网络参数Θ ,进行奖励评估,选择得分高的参数,重新估计概率分布,最终返回最优的Θ 。这里将策略参数看成是染色体的话,跟进化算法如出一辙了,就是在进化网络参数。

代码实例

我在GitHub上给出了John Schulman的一个交叉熵方法作业题的实现,可以直观的看到这种算法的控制效果,供大家参考

题目:
http://rl-gym-doc.s3-website-us-west-2.amazonaws.com/mlss/lab1.html

代码:stiger104/DeepRL

更多的学习资源

墙裂推荐UC Berkeley的CS-294课程,有精力的同学可以修这门课
http://rll.berkeley.edu/deeprlcourse/

Open-AI提供的深度增强学习练兵场,各种算法的效果都可以使用它们的接口来检验!

https://gym.openai.com

必读经典书籍

http://ufal.mff.cuni.cz/~straka/courses/npfl114/2016/sutton-bookdraft2016sep.pdf

Sutton书上的很多DRL实例的代码

https://github.com/dennybritz/reinforcement-learning
https://github.com/ShangtongZhang/reinforcement-learning-an-introduction

关于新达达算法应用组

新达达算法团队由国内一线互联网公司工程师组成,我们致力于通过算法来解决快送众包服务场景下的各种充满挑战的问题,如百万级订单的动态定价/订单分配/路径规划等,快送众包服务系统具有高度的动态性,所以这些问题复杂而有趣,我们十分欢迎对这个方向感兴趣的朋友加入我们。

职位:https://www.imdada.cn/job/detail?id=510077804

投递邮箱:zhuangxuekun@imdada.cn

参考资料

声明:本文部分内容参考了John Schulman的PPT讲座,版权归原作者所有,转载请注明出处。

更多关于新达达技术的文章,敬请关注新达达技术公众号。
新技术公众号