强化学习及其常见算法介绍
⽬录
强化学习算法
scsn_dango
第⼀部分： RL 基本概念介绍
RL 定义
在中⽂维基百科中，强化学习被定义为机器学习中的⼀个领域，强调如何基于环境⽽⾏动，以取得最⼤化的预期收益 。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) 。
asd是什么意思
RL
图1
环境是⼀个外部系统，主体处于这个系统中，能够感知到这个系统并且能够基于感知到的状态做出⼀定的⾏动。⽐如在 MR(Montezuma's Revenge) 中，环境就是80x80像素⼤⼩的游戏界⾯。
主体是⼀个嵌⼊到环境中的系统，能够通过采取⾏动来改变环境的状态。⽐如在MR中，主体就是玩家操控的⼩⼈，⼩⼈能够根据当前环境的状态做出⼀个动作（上下左右移动或者跳跃），从⽽改变环境的状态。
状态是指当前环境的⼀个时间切⽚。在MR中就是⼀张特定时间的80x80⼤⼩的图⽚。
⾏动是指主体做出的⾏为。在MR中指上下左右、跳跃的操作。
高一英语周记
收益是⼀个标量，指的是环境对当前动作或者状态的⼀个奖励。在MR中指的是系统定义的⼀个收益，既可以是在游戏回合结束的时候给
的 Game Over 或者 Win 这样的全局收益，也可以是⼀个局部收益，⽐如拿到 钥匙 或者去到另⼀个 房间。
RL与其他机器学习的关系
RL和传统的机器学习(监督学习 Supervid Learning，⾮监督学习 Unsupervid Learning，半监督学习 Semi-Supervid 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⟶a0S1⟶a1...⟶an−1SnS0⟶a0S1⟶a1...⟶an−1Sn
其中SiSi表⽰i时刻的State，aiai表⽰i时刻的Action。RL学习的⽬标就是学习⼀个根据当前State选择⼀个能够最⼤化全局收益的Action，我们把Agent根据State选择Action的⽅法叫做策略(Policy)。
第⼆部分：RL 算法
强化学习的算法主要分为两⼤类： 基于值的算法(Value-Bad) 和 基于策略的算法(Policy-Bad)。
我⾸先分别介绍⼀下基于值和基于策略的经典算法，然后介绍⼀个将基于值和基于策略的算法的优点结合起来的框架——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]Vπ(s)=Eπ[G0|S0=s]
其中ππ表⽰Agent选择Action的策略的概率分布， G0|S0=sG0|S0=s表⽰从状态s开始到G0G0状态整个序列。所以Vπ(s)Vπ(s)表⽰从当前状态开始到达G0G0状态的预期收益。rearwindow
特别地，如果我们⽤RtRt表⽰t时刻的预期收益，那么有
Vπ(s)=Eπ[G0|S0=s]=Eπ[∑t=0∞γtRt+1|S0=s]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]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∈AQπ(s,a)Vπ(s)=∑a∈AQπ(s,a)
Q-learning
下⾯我们给出经典的Q-learning的算法，伪代码如下所⽰
Q-learning pudocode
Q-learning 算法通过构建和维护⼀个Q表，Q表中的每⼀项表⽰Q(s,a)，来找到⼀个最优策略，这个策略能够最⼤化从当前状态开始所有
的后继⾏动的期望收益。
Q-learning最重要的部分在于对于Q值的更新，从伪代码中我们可以看到，对于Q值的更新ΔQΔQ是两部分的差值乘以系数αα。⼀部分
是r+γmaxa′Q(s′,a′)r+γmaxa′Q(s′,a′)表⽰当前环境给出的即时回报，r表⽰当前环境给出的即时回
报，γmaxa′Q(s′,a′)γmaxa′Q(s′,a′)是对是对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|g:S→R|A|⽤于对每⼀个State s，计amy是什么意思
算⼀个|A||A|维的向量，向量的每⼀维表⽰Q(s,a)对应的值，这样就能够应对State数⽬⽆穷的情况，但是仍然没办法解决|A|→∞|A|→∞
的情况。
基于策略的算法
我们已经知道Q-learning、DQN等基于价值的⽅法通过计算每⼀个状态动作的价值，选择价值最⼤的动作执⾏。这是⼀种间接选择策略的
做法，并且⼏乎没办法处理Action数⽬⽆穷的情况。那么我们能不能直接对策略进⾏建模呢？
⼀种⽐较直观的想法是我们可以构建这样⼀个策略⽹络(Policy Network) PN:S→APN:S→A，输⼊⼀个状态直接输出对应的Action，⽽不
是得到⼀个状态价值V(s)或者每个Action对应的Q值Q(s, a)，然后直接对这个策略⽹络进⾏更新，从⽽直接对策略选择建模。如果我们⽤
神经⽹络来模拟PNPN，那么可以形式化的表⽰为：
a=π(s,θ) or a=π(a|s,θ)a=π(s,θ) or a=π(a|s,θ)
可以直接输出确定的Action，也可以输出Action的⼀个概率分布。在输出概率分布的时候，虽然形式上和DQN类似都是
S→R|A|S→R|A|，但是DQN输出的是Q值，并且是基于Q值做Action的决策，⽽PNPN直接得到的是Action的概率分布，并且对于|A|
→∞|A|→∞，PNPN能够直接预测出Action。
小学生上网的坏处Policy Gradient
Policy GradientPolicy Gradient是基于策略的算法中最基础的⼀种算法。通过对收益期望求梯度，从⽽对Policy Network的参数进⾏更
新。
定义收益期望J(θ)J(θ)如下：
J(θ)=Eτ∼πθ(τ)[r(τ)]=∫τ∼π(τ)r(τ)πθ(τ)dτJ(θ)=Eτ∼πθ(τ)[r(τ)]=∫τ∼π(τ)r(τ)πθ(τ)dτpayot
θ∗=argmaxθ(J(θ))θ∗=argmaxθ(J(θ))
galvanized steel
对J(θ)J(θ)求导有
▽θJ(θ)=▽θ∫τ∼π(τ)r(τ)πθ(τ)dτ=∫τ∼π(τ)r(τ)▽θπθ(τ)dτ▽θJ(θ)=▽θ∫τ∼π(τ)r(τ)πθ(τ)dτ=∫τ∼π(τ)r(τ)▽
⼜因为
▽θπθ(τ)=πθ(τ)▽θπθ(τ)πθ(τ)=πθ(τ)▽θlogπθ(τ)▽θπθ(τ)=πθ(τ)▽θπθ(τ)πθ(τ)=πθ(τ)▽θlogπθ(τ
▽θJ(θ)=∫τ∼π(τ)πθ(τ)r(τ)▽θlogπθ(τ)dτ=Eτ∼πθ(τ)[r(τ)▽θlogπθ(τ)](1)(2)
desire
(1)▽θJ(θ)=∫τ∼π(τ)πθ(τ)r(τ)▽θlogπθ(τ)dτ(2)=Eτ∼πθ(τ)[r(τ)▽θlogπθ(τ)]
河南学位英语
logπθ(τ)=logπθ(s1,a1,s2,a2,...sT,aT)=log{p(s1)∏t=1T[πθ(at|st)p(st+1|st,at)]}=logp(s1)+∑t=1Tlogπθ(at|st)+∑t=1Tlogp( (3)(4)(5)(6)(3)logπθ(τ)=logπθ(s1,a1,s2,a2,...sT,aT)(4)=log{p(s1)∏t=1T[πθ(at|st)p(st+1|st,at)]}
(5)=logp(s1)+∑t=1Tlogπθ(at|st)+∑t=1Tlogp(st+1|st,at)(6)=logp(sT)+∑t=1Tlogπθ(at|st)=∑t=1Tlogπθ(at|st)
r(τ)=∑t=1Tr(st,at)r(τ)=∑t=1Tr(st,at)
▽θJ(θ)=Eτ∼πθ(τ)[∑t=1T▽θlogπθ(at|st)∑t=1Tr(st,at)]▽θJ(θ)=Eτ∼πθ(τ)[∑t=1T▽θlogπθ(at|st)∑t=1Tr(st,at)]
最终我们得到了⼀个漂亮的▽θJ(θ)▽θJ(θ)的表达式，期望⾥⾯包括两个部分∑Tt=1▽θlogπθ(at|st)∑t=1T▽θlogπθ(at|st)表
⽰的是获取当前Trace的概率的梯度，∑Tt=1r(st,at)∑t=1Tr(st,at)表⽰的是当前路径的总的回报。因为回报是⼀个总的回报，只能在⼀个
轮次之后才能得到，所以Policy Gradient算法只能针对每⼀轮次更新，⽆法针对每个step更新。
⼀个Policy Gradient算法REINFORCE的伪代码如下:
1. sample{τi} from πθ(at|st) (run the policy)1. sample{τi} from πθ(at|st) (run the policy)
2. ▽θJ(θ)≈∑i(∑Tt=1▽θlogπθ(ait|sit)∑Tt=1r(sit,ait))2. ▽θJ(θ)≈∑i(∑t=1T▽θlogπθ(ati|sti)∑t=1Tr(sti,ati))
3. θ←θ+α▽θJ(θ)3. θ←θ+α▽θJ(θ)
Actor-Critic 框架
Bad Actor-Critic
法国文化
由于最基础的Policy Gradient算法只能实现每轮次更新，很难准确地把Reward反馈回去，训练效率很差，并且很容易不收敛。所以想要
将∑Tt=1r(sit,ait)∑t=1Tr(sti,ati) 替换为Q(sit,ait)Q(sti,ati)使⽤价值函数对当前的(sit,ait)(sti,ati)⼆元组的期望收益做⼀个评估，这样就
能在每⼀步获取▽θlogπθ(ait|sit)Q(sit,ait)▽θlogπθ(ati|sti)Q(sti,ati)从⽽更新参数。
所以最基础的AC框架的期望收益函数J(θ)J(θ)的梯度有如下的形式：
▽θJ(θ)=Eτ∼πθ(τ)[∑t=1T▽θlogπθ(at|st)Q(st,at)]▽θJ(θ)=Eτ∼πθ(τ)[∑t=1T▽θlogπθ(at|st)Q(st,at)]
Advantage Actor Critic(A2C)
后来研究表明这样的形式计算Q(st,at)Q(st,at)有很⼤的⽅差。为了减⼩⽅差，将Q(st,at)Q(st,at)替换为Q(st,at)−V(st)Q(st,at)−V(st)，
⼜结合Q(s,a)Q(s,a)和V(s)V(s)之间的关系（前⽂有过相关讨论），得到了⼀个Advantage函数，形式如下：
Aπ(st,at)=r(st,at)+Vπ(st+1)−Vπ(st)Aπ(st,at)=r(st,at)+Vπ(st+1)−Vπ(st)
所以想要求得Aπ(st,at)Aπ(st,at)的值，我们只需要⽤⼀个神经⽹络对V(st)V(st)建模就好了。伪代码如下：
batch actor critic algorithmbatch actor critic algorithm
1. sample {si,ai} from πθ(a|s) (run it on the robot)1. sample {si,ai} from πθ(a|s) (run it on the robot)
2. fit V^πΦ(s) to sampled reward sums2. fit V^Φπ(s) to sampled reward sums
3. evaluate A^π(si,ai)=r(si,ai)+V^πΦ(s′i)−V^πΦ(si)3. evaluate A^π(si,ai)=r(si,ai)+V^Φπ(si′)−V^Φπ(si)
4. ▽θJ(θ)=∑i▽θlogπθ(ai|si)A^π(si,ai)4. ▽θJ(θ)=∑i▽θlogπθ(ai|si)A^π(si,ai)
5. θ←θ+α▽θJ(θ)5. θ←θ+α▽θJ(θ)
Trust Region Policy Optimization (TRPO)
虽然A2C很好的把Policy-Bad和Value-Bad两种⽅法结合了起来，并且能够做到step级别的更新，但是A2C没有考虑这样的问题：每⼀次的更新是否能够保证新的策略的Jnew(θ)Jnew(θ)⼤于Jold(θ)Jold(θ)。
Schulman 2015年发表在ICML的论⽂《Trust Region Policy Optimization》讨论了这个问题，并且提出了TRPO算法，从理论上能够
证明Jnew(θ)≥Jold(θ)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)]θ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)]
利⽤KLKL距离来限制old policy和new policy之间的距离，并且修改了⽬标函数，使得在满⾜KLKL限制
下，Jnew(θ)≥Jold(θ)Jnew(θ)≥Jold(θ)。
TRPO在理论上和实践中都有很好的效果。
Proximal Policy Optimization(PPO)
TRPO虽然在理论上和实践中都有很好的效果，但是因为最后求解的问题过于复杂，导致训练时间复杂度很⾼。为了减少时间上的开
销，OpenAI⼜提出了⼀个TRPO的改进⽅法PPO，通过⼀个Clip函数来截断rt(θ)rt(θ)，从⽽⽤很⼩的代价实现了和KLKL距离的限制条
件类似的功能。新的⽬标函数为：
LCLIP(θ)=E^t[min(rt(θ)A^t),clip(rt(θ),1−ϵ,1+ϵ)A^t]rt(θ)=πθ(at|st)πθk(at|st)LCLIP(θ)=E^t[min(rt(θ)A^t),clip(rt(θ),1−ϵ,1+ϵ)A
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.
