目录 RL 定义 RL基本元素 RL与其他机器学习的关系 基于值的算法 基于策略的算法 Actor-Critic 框架 强化学习算法 scsn_dango 第一部分： RL 基本概念介绍 RL 定义 ​ 在中文维基百科中，强化学习被定义为机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期收益 wikipedia。Richard S. Sutton and Andrew G. Barto 最新的强化学习书籍《Reinforcement Learning: An Introduction II》中对强化学习的定义为: Reinforcement learning is learning what to do—how to map situations to actions——so as to maximize a numerical reward signal. RL基本元素 ​ 可以看出强化学习至少有这样几个基本概念： 环境(Environment)、主体(Agent)、状态(State)、行动(Action)和收益(Reward) 。 RL 图1 ​ 环境是一个外部系统，主体处于这个系统中，能够感知到这个系统并且能够基于感知到的状态做出一定的行动。比如在 MR(Montezuma's Revenge) 中，环境就是80x80像素大小的游戏界面。 ​ 主体是一个嵌入到环境中的系统，能够通过采取行动来改变环境的状态。比如在MR中，主体就是玩家操控的小人，小人能够根据当前环境的状态做出一个动作（上下左右移动或者跳跃），从而改变环境的状态。 ​ 状态是指当前环境的一个时间切片。在MR中就是一张特定时间的80x80大小的图片。 ​ 行动是指主体做出的行为。在MR中指上下左右、跳跃的操作。 ​ 收益是一个标量，指的是环境对当前动作或者状态的一个奖励。在MR中指的是系统定义的一个收益，既可以是在游戏回合结束的时候给的 Game Over 或者 Win 这样的全局收益，也可以是一个局部收益，比如拿到 钥匙 或者去到另一个 房间。 RL与其他机器学习的关系 ​ RL和传统的机器学习(监督学习 Supervised Learning，非监督学习 Unsupervised Learning，半监督学习 Semi-Supervised Learning)既有一定的联系，也存在很大的区别。大致的包含关系如图2所示。 RL and ML 图2 ​ 强化学习主要有以下几个特点： ​ 1. 试错学习：强化学习一般没有直接的指导信息，Agent 要以不断与 Environment 进行交互，通过试错的方式来获得最佳策略(Policy)。 ​ 2. 延迟回报：强化学习的指导信息很少，而且往往是在事后（最后一个状态(State)）才给出的。比如 MR 中可能只有在每一次游戏结束以后才有一个 Game Over 或者 Win 的回报。 ​ 总的来说，RL与其他机器学习算法不同的地方在于： 1. 没有监督者，只有一个Reward信号； 2. 反馈是延迟的，不是立即生成的； 3. 强化学习是序列学习，时间在强化学习中具有重要的意义； 4. Agent的行为会影响以后所有的决策。 ​ RL可以被抽象为一个序列预测的问题，只不过序列是通过类似图灵机一样的原理产生的，后一个State只有在前一个Action做出以后才可以得到。 S0 a0 ⟶ S1 a1 ⟶ ... an−1 ⟶ Sn ​ 其中Si表示i时刻的State，ai表示i时刻的Action。RL学习的目标就是学习一个根据当前State选择一个能够最大化全局收益的Action，我们把Agent根据State选择Action的方法叫做策略(Policy)。 第二部分：RL 算法 ​ 强化学习的算法主要分为两大类： 基于值的算法(Value-Based) 和 基于策略的算法(Policy-Based)。我首先分别介绍一下基于值和基于策略的经典算法，然后介绍一个将基于值和基于策略的算法的优点结合起来的框架——Actor-Critic(AC)框架。在AC框架下进一步介绍目前学术界用得最多的几种强化学习算法，也包括《RND》这篇论文中使用的PPO算法。 基于值的算法 ​ 在介绍基于值的算法之前首先介绍两个概念 状态价值函数(State Value Function)-V(s) 和 行为价值函数(Quality of State-Action function)-Q(s,a)。 ​ 状态价值函数：状态价值函数V(s)，输入是一个状态，输出是该状态的预期Reward。 Vπ(s)=Eπ[G0|S0=s] ​ 其中π表示Agent选择Action的策略的概率分布， G0|S0=s表示从状态s开始到G0状态整个序列。所以Vπ(s)表示从当前状态开始到达G0状态的预期收益。 ​ 特别地，如果我们用Rt表示t时刻的预期收益，那么有 Vπ(s)=Eπ[G0|S0=s]=Eπ[ ∞ ∑ t=0 γtRt+1|S0=s] ​ 其中γ表示折扣因子，体现与当前状态更近的状态对与当前状态的预期期望贡献更大。 ​ 行为价值函数：行为价值函数Q(s,a)，输入是一个状态和一个行动，输出是在该状态下采取该行动的预期收益，那么有 Qπ(s,a)=Eπ[G0|S0=s,A0=a]=Eπ[ ∞ ∑ t=0 γtRt+1|S0=s,A0=a] ​ 易知，V(s)和Q(s,a)之间有这样的关系 Vπ(s)= ∑a∈A Qπ(s,a) Q-learning ​ 下面我们给出经典的Q-learning的算法，伪代码如下所示 Q-learning pseudocode ​ Q-learning 算法通过构建和维护一个Q表，Q表中的每一项表示Q(s,a)，来找到一个最优策略，这个策略能够最大化从当前状态开始所有的后继行动的期望收益。 ​ Q-learning最重要的部分在于对于Q值的更新，从伪代码中我们可以看到，对于Q值的更新ΔQ是两部分的差值乘以系数α。一部分是r+γmaxa′Q(s′,a′)表示当前环境给出的即时回报，r表示当前环境给出的即时回报，γmaxa′Q(s′,a′)是对是对Q(s′,a′)的最大估计（折扣因子为的最大估计（折扣因子为γ），所以第一部分总的表示对于当前(s,a)的Q值的现实值；另一部分为Q(s,a)表示Q(s,a)的估计值。 ​ 除了Q-learning以外，还有Deep Q-learning、Double Q-learning 和 SARSA等基于值的算法。一般来说基于值的算法都是先评估每个(s, a) 元组的Q值-Q(s,a)，再根据Q值求最优策略，基于值的方法适用于比较简单（状态空间比较小，或者Action数目较小）的问题，它有较高的数据利用率并且能稳定收敛。 ​ 对于Q-learning来说，因为需要构建一个Q表，每一个(s,a)元组都需要对应一个Q值，所以只能解决State和Action均可数并且数目较小的问题。Deep Q-learning通过深度神经网络(Deep Neural Network, DNN)来估计一个函数g:S→R|A|用于对每一个State s，计算一个|A|维的向量，向量的每一维表示Q(s,a)对应的值，这样就能够应对State数目无穷的情况，但是仍然没办法解决|A|→∞的情况。 基于策略的算法 ​ 我们已经知道Q-learning、DQN等基于价值的方法通过计算每一个状态动作的价值，选择价值最大的动作执行。这是一种间接选择策略的做法，并且几乎没办法处理Action数目无穷的情况。那么我们能不能直接对策略进行建模呢？ ​ 一种比较直观的想法是我们可以构建这样一个策略网络(Policy Network) PN:S→A，输入一个状态直接输出对应的Action，而不是得到一个状态价值V(s)或者每个Action对应的Q值Q(s, a)，然后直接对这个策略网络进行更新，从而直接对策略选择建模。如果我们用神经网络来模拟PN，那么可以形式化的表示为： a=π(s,θ) or a=π(a|s,θ) ​ 可以直接输出确定的Action，也可以输出Action的一个概率分布。在输出概率分布的时候，虽然形式上和DQN类似都是S→R|A|，但是DQN输出的是Q值，并且是基于Q值做Action的决策，而PN直接得到的是Action的概率分布，并且对于|A|→∞，PN能够直接预测出Action。 Policy Gradient ​ Policy Gradient是基于策略的算法中最基础的一种算法。通过对收益期望求梯度，从而对Policy Network的参数进行更新。 ​ 定义收益期望J(θ)如下： J(θ)=Eτ∼πθ(τ)[r(τ)]=∫τ∼π(τ)r(τ)πθ(τ)dτ θ∗= argmaxθ (J(θ)) ​ 对J(θ)求导有 ▽θJ(θ)=▽θ∫τ∼π(τ)r(τ)πθ(τ)dτ=∫τ∼π(τ)r(τ)▽θπθ(τ)dτ ​ 又因为 ▽θπθ(τ)=πθ(τ) ▽θπθ(τ) πθ(τ) =πθ(τ)▽θlogπθ(τ) ▽θJ(θ) =∫τ∼π(τ)πθ(τ)r(τ)▽θlogπθ(τ)dτ =Eτ∼πθ(τ)[r(τ)▽θlogπθ(τ)] logπθ(τ) =logπθ(s1,a1,s2,a2,...sT,aT) =log{p(s1) T ∏ t=1 [πθ(at|st)p(st+1|st,at)]} =logp(s1)+ T ∑ t=1 logπθ(at|st)+ T ∑ t=1 logp(st+1|st,at) =logp(sT)+ T ∑ t=1 logπθ(at|st)= T ∑ t=1 logπθ(at|st) r(τ)= T ∑ t=1 r(st,at) ▽θJ(θ)=Eτ∼πθ(τ)[ T ∑ t=1 ▽θlogπθ(at|st) T ∑ t=1 r(st,at)] ​ 最终我们得到了一个漂亮的▽θJ(θ)的表达式，期望里面包括两个部分∑ T t=1 ▽θlogπθ(at|st)表示的是获取当前Trace的概率的梯度，∑ T t=1 r(st,at)表示的是当前路径的总的回报。因为回报是一个总的回报，只能在一个轮次之后才能得到，所以Policy Gradient算法只能针对每一轮次更新，无法针对每个step更新。 ​ 一个Policy Gradient算法REINFORCE的伪代码如下: ​ 1. sample{τi} from πθ(at|st) (run the policy) ​ 2. ▽θJ(θ)≈∑i(∑ T t=1 ▽θlogπθ(a i t |s i t )∑ T t=1 r(s i t ,a i t )) ​ 3. θ←θ+α▽θJ(θ)​ Actor-Critic 框架 Based Actor-Critic ​ 由于最基础的Policy Gradient算法只能实现每轮次更新，很难准确地把Reward反馈回去，训练效率很差，并且很容易不收敛。所以想要将∑ T t=1 r(s i t ,a i t ) 替换为Q(s i t ,a i t )使用价值函数对当前的(s i t ,a i t )二元组的期望收益做一个评估，这样就能在每一步获取▽θlogπθ(a i t |s i t )Q(s i t ,a i t )从而更新参数。 ​ 所以最基础的AC框架的期望收益函数J(θ)的梯度有如下的形式： ▽θJ(θ)=Eτ∼πθ(τ)[ T ∑ t=1 ▽θlogπθ(at|st)Q(st,at)] Advantage Actor Critic(A2C) ​ 后来研究表明这样的形式计算Q(st,at)有很大的方差。为了减小方差，将Q(st,at)替换为Q(st,at)−V(st)，又结合Q(s,a)和V(s)之间的关系（前文有过相关讨论），得到了一个Advantage函数，形式如下： Aπ(st,at)=r(st,at)+Vπ(st+1)−Vπ(st) ​ 所以想要求得Aπ(st,at)的值，我们只需要用一个神经网络对V(st)建模就好了。伪代码如下： ​ batch actor critic algorithm ​ 1. sample {si,ai} from πθ(a|s) (run it on the robot) ​ 2. fit ˆ V π Φ (s) to sampled reward sums ​ 3. evaluate ˆ A π(si,ai)=r(si,ai)+ ˆ V π Φ (s ′ i )− ˆ V π Φ (si) ​ 4. ▽θJ(θ)=∑i▽θlogπθ(ai|si) ˆ A π(si,ai) ​ 5. θ←θ+α▽θJ(θ) Trust Region Policy Optimization (TRPO) ​ 虽然A2C很好的把Policy-Based和Value-Based两种方法结合了起来，并且能够做到step级别的更新，但是A2C没有考虑这样的问题：每一次的更新是否能够保证新的策略的Jnew(θ)大于Jold(θ)。 ​ Schulman 2015年发表在ICML的论文《Trust Region Policy Optimization》讨论了这个问题，并且提出了TRPO算法，从理论上能够证明Jnew(θ)≥Jold(θ) 。Schulman把最终的优化问题转换成了 θk+1= argmaxθ L(θk,θ)s.t. ˉ D KL(θ||θk)≤δwhere L(θk,θ)= Es,a∼πθk [ πθ(a|s) πθk(a|s) Aπθk(s,a)] ​ 利用KL距离来限制old policy和new policy之间的距离，并且修改了目标函数，使得在满足KL限制下，Jnew(θ)≥Jold(θ)。 ​ TRPO在理论上和实践中都有很好的效果。 Proximal Policy Optimization(PPO) ​ TRPO虽然在理论上和实践中都有很好的效果，但是因为最后求解的问题过于复杂，导致训练时间复杂度很高。为了减少时间上的开销，OpenAI又提出了一个TRPO的改进方法PPO，通过一个Clip函数来截断rt(θ)，从而用很小的代价实现了和KL距离的限制条件类似的功能。新的目标函数为： LCLIP(θ)= ˆ E t[min(rt(θ) ˆ A t),clip(rt(θ),1−ϵ,1+ϵ) ˆ A t]rt(θ)= πθ(at|st) πθk(at|st) Reference [1] Burda Y, Edwards H, Storkey A, et al. Exploration by Random Network Distillation[J]. arXiv preprint arXiv:1810.12894, 2018. [2] Schulman J, Wolski F, Dhariwal P, et al. Proximal policy optimization algorithms[J]. arXiv preprint arXiv:1707.06347, 2017. [3] Schulman J, Levine S, Abbeel P, et al. Trust region policy optimization[C]//International Conference on Machine Learning. 2015: 1889-1897. [4] Sutton R S, McAllester D A, Singh S P, et al. Policy gradient methods for reinforcement learning with function approximation[C]//Advances in neural information processing systems. 2000: 1057-1063. [5] Sutton R S, Barto A G. Reinforcement learning: An introduction[M]. MIT press, 2018. [6] Watkins C J C H, Dayan P. Q-learning[J]. Machine learning, 1992, 8(3-4): 279-292. 分类: Reinforcement Learning(强化学习)https://www.cnblogs.com/yeyuan111/p/10320050.html