昨天，“EasyRL强化学习入门与实践”第一课的直播已圆满结束！阿里巴巴算法专家王桢为大家带来了强化学习开源库EasyRL的介绍。
内容包括强化学习的入门与实践，从基本的概念到具体的例子，如何利用EasyRL快速运行强化学习算法解决一些实际的问题。
今天会进行第二课的直播哦，具体直播安排如下：
直播时间：今晚19:00-20:00
课程内容：
1. 马尔可夫决策过程（值函数与贝尔曼方程）
2. 强化学习算法（基于值的方法，策略梯度方法，算法归类）
直播传送门：阿里云开发者社区
https://developer.aliyun.com/live/2287
接下来让我们回顾一下昨日的精彩内容！没能观看直播的同学可以通过以下链接观看回放，再配上下面的内容回顾，妙哉啊！
第一课回放：
https://study.163.com/course/courselive/1280452094.htm?share=2&shareId=10146755
关键词：人工智能，大数据，分布式强化学习算法，开源EasyRL，马尔可夫决策过程
EasyRL简介
概述
在实践中，强化学习相较于监督学习对工程师往往提出了更高的要求，包括但不限于：
- 监督学习往往只需要在计算图中描述目标函数并选择优化器，强化学习需要描述策略，值函数，目标的估计等等多个模块。
- 在分布式训练的设定下，监督学习仅需要在进程间交换同质的梯度和参数，而强化学习还需要传递格式更复杂的样本（即(state, action, reward, next state)元组组成的序列）。
- 不同流派的强化学习算法在不同场景中往往各有优劣。工程师往往需要一套较为齐全的算法库来尝试和验证不同算法。
EasyRL针对上述困难与挑战而设计，在易用性上满足用户能一键运行各种算法（包括单机和分布式设定），同时提供清晰的接口和扁平的类层次关系方便开发者复用已有模块来定制新算法。
设计理念
1. 轻量易用
绝大多数已有的强化学习算法库依赖MPI，NCCL，或者Ray来实现分布式强化学习算法，给用户在搭建环境，二次开发，或移植部署等环节造成了一定困难。
EasyRL完全基于TensorFlow开发实现，包括表达算法本身的计算图描述以及分布式模式下不同进程间的通信。
用户可以方便地跑通我们提供的任意算法，安装、移植、以及嵌入业务代码中都是非常方便的。
2. 可扩展性
如下图所示，EasyRL将不同进程在概念上划分为四种角色，统一地表达了不同Actor-Learner架构：
- Actor：负责和环境交互产生样本。
- Replay Memory：存储交互产生的样本，提供重复采样。
- Learner：利用收集的数据计算梯度，更新模型。
- Parameter Server (PS)：参数服务器。
Actor利用CPU资源，和环境交互产生样本并存入Replay Memory中；Learner从Replay Memory取出数据，利用GPU计算梯度并将梯度更新到PS上。
具体地，每个actor上维护一份本地的模型副本，间隔地从PS上同步最新的模型参数，在与环境进行交互的过程中不需要额外的通信开销。
为了进一步提高系统的样本吞吐，EasyRL为actor提供了wrapper将环境包装在独立进程中执行，独立于主进程中actor的推理步骤，使得actor可以与多个进程的环境同时交互，充分利用单个actor上的cpu资源。
除了PS之外，每个actor，memory 或者learner与其他角色的通信均由独立的线程负责，与主线程用队列通信，主线程仅负责计算，一定程度将计算和通信的开销重叠，从而提高效率。
我们提供了多种replay memory：均匀采样的replay buffer，按priority进行采样的priority replay buffer，用于on-policy算法的仅保存单个trajectory的TrajectoryBuffer，以及适用于Evolutional strategy (ES)/PPO，累积存储多个actor采样数据，一次性读取的AggregateBuffer。
由于设计上将replay memory作为一种角色，针对memory采样策略的二次开发变得非常方便。
Learner和PS则类似监督学习中的PS-worker架构，进行纯粹的分布式训练，避免了其他数据流的处理，learner可以更好地利用GPU的算力。
Ape-X架构下支持异步训练的随机梯度下降，可以根据整个系统吞吐增加learner的数量进行扩展。
在ES/PPO等每一轮迭代都需要同步的算法，目前的设计是1个learner+多个actors的模式，重点是提高交互的效率（例如ES算法需要大量的实验来收集数据），通过单机多卡并行的方式，提高模型训练的效率。
这其中不同角色的进程的数量均可以任意调节，从而避免某一个角色的进程成为系统的瓶颈。
3. 模块化
models模块采用了扁平的设计，仅通过基类描述了一些必要实现的接口，提供了常用算法的实现，不同model之间没有耦合，方便算法同学对模型进行定制。
model类构建计算图的逻辑分解成相对独立的类方法，主要包括：构建网络结构、构建策略输出的动作分布、计算目标/损失函数、使用的优化器（包括对梯度的处理）四个部分。
开发者可以根据自己的需求，继承Model类并单独重载需要定制的类方法，例如修改网络结构、实现新的损失函数、或者是采用更加复杂的优化器。
同时，EasyRL也提供了一种通过配置文件来自动构建网络结构的途径。
4. 算法种类齐全
EasyRL提供的算法种类全面，且覆盖单机和分布式的实现，下面通过一个表格显示与其它开源库的对比。
o：表示支持该功能；x：表示不支持该功能（表中调研的各开源库的功能覆盖情况截止2019年3月）
对上述开源强化学习库调研发现，部分项目缺乏持续更新，例如RLLab、Tensorflow Agents；部分项目算法种类过于单一，例如Dopamine 仅提供了 DQN（Rainbow）算法，而PARL、TensorForce没有提供Rainbow的实现，RLGraph则是一个meta graph的实现，开发复杂并且缺少DDPG、模仿学习等。
另一些项目则缺少良好分布式的实现，例如OpenAI的Baselines没有actor-learner的架构；包括coach，PARL没有对Ape-X的支持。
部分项目仅是op层面的优化工作，例如Uber-research/ape-x和Trfl。
Ray RLlib是功能全面且分布式性能优异的项目，但是不支持任意扩展leanrer进程的数量，在样本产出速度非常快的场景会导致learner成为瓶颈。
性能比较
本节比较EasyRL与Ray RLLib在Actor-Learner架构下的吞吐和收敛速度。
使用的环境Atari-Pong是一个视频游戏，其状态经过预处理后是一个形状为(42, 42, 4)的numpy数组，可以比较典型的反映系统对交互产出的样本进行通信和消费的效率。
1. IMPALA架构
针对actor-leaner资源灵活配置的特性，我们动态调节actor和learner的数量，同时保持memory和learner数量一致，观察整个系统的吞吐变化。
可以看到当learner与actor数量保持1:8时，sample产生的速率和消耗的大致速率达到一个平衡。
此时，只有继续增加learner之后，再次增加actor的数量才能使整体的吞吐提升。
在16个learner和128个actor的配置下，系统平均每秒可以产生和训练12万条样本，并且在这个配置下，继续增加资源还能提升整体吞吐。
再看模型的收敛效果：
如上图所示，a代表actor，m代表memory，l代表learner，我们分别在5组配置下进行了收敛性的实验。
其中actor和memory使用CPU机器，learner使用GPU机器。可以看到随着系统的吞吐提升，平均累积奖励达到17+的时间也越来越短。
这里记录了不同配置下，第一个episode累积奖励达到17+所用的时间：
相较于Ray RLLib IMPALA算法在Atari-Pong环境下所得到的实验结果。
- Ray RLLib使用2个V100 GPU+32个actors在6~7分钟左右episode累积奖励达到17+，其吞吐为10k samples/sec左右；
- EasyRL使用同样的GPU+16个actors在400～500s左右episode累积奖励达到17+，吞吐在16k samples／sec左右。
其中吞吐更大而收敛偏慢，在于我们的learner是处在不同机器上，进行的异步训练，而Ray RLLib是单机多卡的实现。
单机多卡使得梯度更新同步做的更好，但是同时限制了其扩展性，超出单机卡数的更多learner的并行成为其瓶颈。
2. Ape-X架构
在Ape-X下，由于replay buffer的存在，样本会被重复使用，因而actor端样本产生的速率变得不那么关键。
当使用priority replay buffer时，由于priority采样和更新的开销巨大，系统的瓶颈处在memory上。
EasyRL可以通过增加memory的数量来消除priority replay造成的瓶颈。
可以看到在1个learner设定下，通过增加priority buffer的数量，可以提高整体的吞吐。
当priority buffer数量达到4个之后，继续增加，则获得的提升非常小，此时系统性能的瓶颈已经从memory转移到learner上了。
收敛性实验：
与IMPALA参数含义相同，在Ape-X上我们做了四组实验，保持actor和learner的数量不变，增加priority replay memory的数量，通过提高整体throughput从而减少episode累积奖励达到17+的时间。
Ray RLLib Ape-X算法在Atari-Pong上的实验结果：
可以看到同样1个GPU配置下，Ray RLlib Ape-X利用32个cpu需要接近1个小时才能达到17+，而EasyRL在1个learner+8个memory+4个actor设定下，需要1200s～1400s就可以让episode累积奖励达到17+，时间减少了一半以上。
马尔可夫决策过程
定义与样例
马尔可夫决策过程（MDP）是一个四元组，由状态空间，动作空间，状态转移概率，奖励函数四个元素定义。如下图所示，给出了一个简单的MDP样例，绿色节点代表状态 ，红色节点代表动作，从红色节点指向绿色节点的边上标出了状态转移概率和奖励。
求解MDP
求解马可夫决策过程，是去学习某种策略，最大化智能体接收到的标量信号（称之为收益）累积和的概率期望值。
所谓策略就是从环境当中观察到智能体所处的一个状态，根据策略去选取某个动作，然后去执行并反馈给这个环境。或者说我们作用于这个环境，这个环境会按照它本身MDP的这个状态转移以及奖励函数相应的反馈给智能体一个奖励的信号，即一个实数。然后内在的环境会跳转到下一个状态，再根据策略去选取某个动作，以此类推。
强化学习有两种，第一种是回合式任务，比如走迷宫，走到出口，智能体和环境交互的过程就结束了。第二种是持续性任务，智能体和环境的交互永远没有一个终止的状态。为了使得总的奖励在持续性任务中不趋于无穷大，且使其在上述两种任务中有一个统一的表示法，引入一个衰减因子gamma，是一个小于1的正的实数。
更多样例
如下图所示，分别给出了4个不同任务的MDP四元组的描述。
从贪心策略到动态规划
在算法和数据结构的课程中，有两种常用的算法，贪心策略和动态规划。如下图所示，左图中的MDP的求解，如果采用贪心策略，我们会在第一步选择a1，而最优策略应该是选择a0。右图以经典的求解最长公共子序列为例，将其描述成MDP四元组，用动态规划求出这张表，再从后往前根据表格中数值贪心地做决策，从而求解出最长公共子序列
值函数与贝尔曼方程
为了解释下图中的表格是什么含义，需要引入值函数的概念。值函数是状态（或状态与动作二元组）的函数，用来评估当前智能体在给定状态（或给定状态与动作）下总奖励的期望值。当然，智能体期望未来能得到的收益取决于智能体所选择的动作。因此，值函数是与特定的行为方式相关的，称之为策略。严格地说，策略是从状态到每个动作的选择概率之间的映射。
值函数有一个基本特性，就是它们满足某种递归关系，如下图所示，在给出状态值函数和动作值函数的表达式之后，以此为基础，进一步定义了状态（动作）值函数的最优贝尔曼方程。最优策略是最优贝尔曼方程的唯一解。
在强化学习中，动态规划的核心思想是使用值函数来结构化地组织对最优策略的搜索。下图中的表格是最优状态值函数的表，它是从前往后计算得到的。再根据最优贝尔曼方程的递推式，从后往前推理决策，就得到图中黄色的路径，即最优策略。
