深度增强学习（DRL）漫谈-从AC（Actor-Critic）到A3C（Asynchron。。。前⾔
之前在⽂章扯了⼀些关于DRL的内容，但因为是以DQN为主线，其中⼤部分谈的是value-bad⽅法。我们知道传统增强学习（Reinforcement learning, RL）中除了value-bad⽅法，还有⼀⼤类就是policy-bad⽅法。在RL任务中，我们本质上最终要学习的是策略（Policy）。前者⽤的是间接⽅法，即通过学习值函数（value function）或者动作值函数（action-value function）来得到policy。⽽后者是直接对policy进⾏建模和学习，因此后者也称为policy optimization。Policy-bad⽅法⼜可分为两⼤类：gradient-bad⽅法和gradient-free⽅法。前者也称为policy gradient（PG）⽅法。⽽policy gradient⽅法⼜可细分为⼏类，如finite difference，Monte-Carlo和Actor-Critic等。Actor-Critic（AC）⽅法其实是policy-bad和value-bad⽅法的结合。因为它本⾝是⼀种PG⽅法，同时⼜结合了value estimation⽅法，所以有些地⽅将之归为PG⽅法的⼀种，有些地⽅把它列为policy-bad和value-bad 以外的另⼀种⽅法，都好理解。在AC框架中，actor负责policy gradient学习策略，⽽critic负责policy evaluation估计value function。可以看到，⼀⽅⾯actor学习策略，⽽策略更新依赖critic估计的value function；另⼀⽅⾯critic估计value function，⽽value function ⼜是策略的函数。Policy和value function互为依赖，相互影响，因此需要在训练过程中迭代优化。这种多元优化的迭代思想其实在机器学习中有很多体现。
有了critic和actor的概念，再看当时其它的⽅法，就可以分为critic-only⽅法和actor-only⽅法两类。前者基于value estimation。它⼴泛应⽤于各种领域，但有⼀些缺点使它的应⽤受到局限。如 1） ⽐较难应⽤
到随机型策略（stochastic policy）和连续的动作空间。2）value function的微⼩变化会引起策略变化巨⼤，从⽽影响训练收敛性。尤其是引⼊函数近似（function approximation，FA）后，虽然算法泛化能⼒提⾼了，但也引⼊了bias，从⽽使得训练的收敛性更加难以保证。⽽后者通过将策略参数化，从⽽直接学习策略。这样做的好处是与前者相⽐拥有更好的收敛性，以及适⽤于⾼维连续动作空间及stochastic policy。但缺点包括梯度估计的variance⽐较⾼，且容易收敛到⾮最优解。另外因为每次梯度的估计不依赖以往的估计，意味着⽆法充分利⽤⽼的信息，因此数据利⽤率低。
可以看到，两类⽅法各有利弊，⽽AC算法结合了两者的优点。其实AC的历史其实⾮常悠久。反直觉地，它⽐critic-only和actor-only⽅法更早。我们知道，学术中很多时候⼀般是先有了⽜逼算法A，再有了⽜逼算法B。但A，B算法⼀般都有缺点，于是有⼀天有⼈将两者整合，结合了两者优点，避免了两者缺点，皆⼤欢喜，喜⼤普奔。但对于AC算法来说其架构可以追溯到三、四⼗年前。 最早由Witten在1977年提出了类似AC算法的⽅法，然后Barto, Sutton和Anderson等⼤⽜在1983年左右引⼊了actor-critic架构。但由于AC算法的研究难度和⼀些历史偶然因素，之后学界开始将研究重点转向value-bad⽅法。之后的⼀段时间⾥value-bad⽅法和policy-bad⽅法都有了蓬勃的发展。前者⽐较典型的有TD系的⽅法。经典的Sarsa, Q-learning等都属于此列；后者⽐如经典的REINFORCE算法。之后AC算法结合了两者的发展红利，其理论和实践再次有了长⾜的发展。直到深度学习（Deep learning, DL）时代，AC⽅法结合了DNN作为FA，产⽣了化学反应，出现了DDPG，A3C这样⼀批先进算法，以及其它基于它们的⼀些改进和变体。可以看到，这是⼀个先分后合的圆满故事。
理论背景
前⾯主要简略瞎扯了AC算法相关的发展史。下⾯罗列下本⽂涉及的⼏篇论⽂的主要相关理论背景。前⾯也提到，PG⽅法是⼀⼤类基于梯度的策略学习⽅法。经典的REINFORCE算法和AC算法都可以纳⼊其框架。我们就以它开始。其基本做法是先定义policy为参数的函数，记作，然后定义为⽬标函数（Objective function，or performance objective），接着通过利⽤⽬标函数相对于参数的梯度更新参数，从⽽达到⽬标函数的局部最⼤值。记作：
在Sutton的奠基性论⽂《Policy Gradient Methods for Reinforcement Learning with Function Approximation》中证明了结合可微FA的PG⽅法可收敛到局部最优点。论⽂中提出了两种objective fu
nction定义，但结论是⼀致的 。以average reward formulation为例，它把定义为平均回报（average reward），对其求导，得到了(Stochastic) Policy Graidient定理。详细证明请见论⽂附录。其核⼼结论给出了⽬标函数相对于策略参数的梯度公式：
重点是它其中不含有状态稳态分布对于策略参数的导数，这意味着参数的变化对于状态稳态分布没有影响，这样有利于通过采样来逼近和估计梯度。因为这样的话通过执⾏策略来得到状态的分布就可以得到⽆偏估计。注意如果其中的函数⽤真实的累积回报来估计，那就是REINFORCE算法。但结合了FA，即后，会引⼊bias。因此Sutton还证明了如果FA是compatible的，那就不会有bias。但注意机器学习bias只是⼀⽅⾯，因为error=bias+variance。因此即使no bias，但variance⼤，算法收敛不了，那也⽩瞎。后⾯会看到⼀些减⼩variance的⽅法。
曾经有⼀段时间⼤家普遍认为online的TD⽅法在有linear FA时只有在on-policy情况下才有收敛性保证。⽽off-policy⽅法（如Q-
learning）虽然在tabular情况下可以保证收敛，但是在有linear FA情况下就⽆法保证收敛。⽽least-squares⽅法（如LSTD, LSPI）虽能解决off-policy和linear FA下的收敛性问题，但计算复杂度⽐较⾼。Sutton和Maei等⼈提出的GTD（Gradient-TD）系⽅法（如Greedy-GQ）解决了off-policy，FA，online算法的收敛性问题。它最⼩化⽬标MSPBE（mean-squared projected Bellman error），通过S
GD优化求解。但因为它仍是TD⽅法，因此仍然逃不了TD⽅法在上⾯提到的固有缺点。要避免这些缺点，⼀般的做法是⽤PG算法（如AC 算法）。在Degris等⼈的论⽂《Off-Policy Actor-Critic》中将AC算法扩展到off-policy场景，提出了OffPAC算法，它是⼀种online,off-policy的AC算法。 OffPAC中的critic部分采⽤了上⾯提到的GTD系⽅法-GTD(λ)算法。
相关论⽂选读
好了，下⾯看下⽬前业界⽐较领先的DRL算法-A3C算法。我们先来看下其它两篇近年AC发展历史中⽐较重要的论⽂，最后再来看A3C算法。
美女电脑桌面壁纸ICML 2014 DeepMind 《Deterministic Policy Gradient Algorithms》
这篇⽂章主要提出了⽤于连续动作空间的deterministic policy gradient(DPG)定理，和⼀种学习确定性⽬标策略（Deterministic target policy）的off-policy AC算法。回忆之前的stochastic policy 定义为动作的分布。⽽deterministic policy则为状态到动作的映射。背后的基本思想是，虽然policy可以⽤概率分布表⽰，但我们想要的其实就是⼀个动作⽽已。以往⼀般认为deterministic policy gradient不存在，⽽这篇论⽂将PG框架推⼴到deterministic policy，证明了deterministic policy gradient不仅存在，⽽且是
model-free形式且是action-value function的梯度，形式简单。Deterministic Policy Gradient（DPG）定理给出了⽬标函数对于策略参数的梯度：
并且证明了它是之前stochastic policy gradient定理当policy的variance趋向于0时的极限。这意味着compatible FA，natural
gradients等⼀众理论都可以应⽤到DPG场景。⽤stochastic policy gradient算法时，当学习进⾏到后期，policy的分布的variance变⼩。因为policy对其参数的导数在均值附近会变得⾮常⼤（⽐如⾼斯分布），从⽽导致变化很⼤。另外，在⾼维动作空间问题
中，stochastic policy gradient定理中的梯度内积需要在⾼维空间中采样，⽽deterministic policy gradient不需要积分，有解析解。这些都是引⼊deterministic policy后带来的好处。
θπ(θ)J (θ)θΔθ=α∇J (θ)
θJ =∂θ∂J (θ)d (s )Q (s ,a )
s ∑πa ∑∂θ∂π(s ,a )
πd (s )ππQ Q (s ,a )w π(a ∣s )θa =μ(s )θ∇J (μ)=θθρ(s )∇μ(s )∇Q (s ,a )∣ds
∫S μθθa μa =μ(s )θ
但deterministic policy⼜会导致exploration不⾜。解决⽅案是选择动作时⽤stochastic behavior policy，⽽学习⽬标为deterministic target policy。这就意味着需要off-policy。定义behavior policy ，target policy为。这off-policy和stochastic policy 下，根据论⽂《Off-Policy Actor-Critic》中的结论，performance objective和其对于的梯度可写为：
对应的OffPAC算法中crtic部分⽤了gradient TD⽅法。Actor和critic是基于target policy，通过importance sampling进⾏估计。接下来，理论指导实践，该论⽂根据DPG定理论⽂提出了deterministic AC算法。先是基于on-policy(Sarsa)和off-policy（Q-learning）情况提出了deterministic AC算法，然后基于OffPAC算法提出了OPDAC（off-policy deterministic actor-critic
过洁世同嫌algorithm）算法。OPDAC算法将前⾯的OffPAC中的梯度公式扩展到deterministic policy，给出off-policy deterministic policy gradient：月是故乡明全诗
但它们⾃然不是最⽜的，就和电影⼀样，是为了将剧情⼀波⼀波推向⾼潮，⼤boss总是最后出来的。前⾯这些只是作为更清楚解释原理的引⼦ 。它们都有收敛性问题（因为FA引⼊的bias和off-policy引⼊的不稳定性），于是论⽂最后放出⼤招，结合compatible FA和gradient TD给出了COPDAC-GQ算法。
后安粉
ICLR 2016 DeepMind 《Continuous Control with Deep Reinforcement Learning》
之前是前DL时代的研究。近年来随着DL的兴起，PG进⼊DL时代就成了必然趋势了。我们看到value-bad⽅法已和DQN结合产⽣了DQN，⽽DL在其中其实主要充当了FA的⾓⾊。⽽另⼀⽅⾯PG中也需要FA，那PG和DL的结合也很⾃然了。这篇论⽂提出model-free,off-policy，actor-critic的DRL算法。称为Deep DPG，即DDPG算法 。我们知道原始的DQN⽆法应⽤到连续动作空间。直觉上当然可以通过离散化动作空间解决，但会导致维度灾难（cur of dimensionality）。DDPG基于DPG算法，它将AC⽅法与DQN结合。回顾⼀下DQN的理论意义，在它之前，学术界普遍认为⼤型⾮线程FA⽤于学习value function或者action-value function理论上收敛不可保证，且实际学习效果也不稳定。不⽤⼤型⾮线性FA，算法⼜扩展不到⼤型状态空间，只能在⼩规模场景中⽤⽤，没啥意思，⽤了么⼜没收敛性保证，挺尴尬的。⽽DQN有⼒地推翻了这个认识，这才是DQN⽐较⼤的理论贡献。它证明了⽤⾮线程FA来表⽰value function也可以稳定收敛。当然这很⼤程度上归功于replay buffer和target Q network。前者直观上就是让obrvation（或称为sample, experience）不要⽴即⽤于更新，⽽是存下来再从中随机选取来更新，从⽽解决了sample之间相互关联的问题；后者作⽤上起到参数更新的平滑作⽤，即不是基于sample更新参数后⽴即⽣效，⽽是通过"soft"的⽅式更新到⽬标⽹络（通过参数控制其⽐例）。从⽽解决了Q函数更新的发散问题，使训练过程更加稳定。DDPG同样⽤到了这两⼤法器，同时再加上2015年Ioffe和Szegedy提出的batch normalization（它是DNN优化上general的⽅法，在DNN
世界第一大洲的优化中⼴泛应⽤）。在⼀些问题，尤其是低维问题中，不同的components的物理单位是不同，或者说相差很⼤。这会影响学习效率和使通⽤超参数学习更困难。⾯对这种不同状态不同分量scale不同的问题第⼀反应当然是normalization。⼀种是在input feature阶段就做scale，另⼀种就是batch normalization。它维护mean和variance的running average，将每⼀维度在minibatch 中的sample间进⾏normalization，使它们有unit mean & variance。该⽅法减少了深度⽹络训练过程中的covariance shift，使得算法
可以更好地适应各种不同任务，处理各种不同类型输⼊。
飞特族
综合以上⽅法，DDPG算法（具体参见论⽂中的Algorithm 1）将DPG中的linear FA扩展到nonlinear FA，即DNN，并使之适⽤于online 情况和⾼维状态和动作空间。
β(a ∣s )π(a ∣s )θθ∇J (π)≈θβθE ∇log π(a ∣s )Q (s ,a )]
s ∼ρ,a ∼βββ(a ∣s )θπθ(a ∣s )
θθπ∇J (μ)≈θβθE [∇μ(s )∇Q (s ,a )∣]
s ∼ρβθθa μa =μ(s )θτ
另外还有就是连续动作空间中的exploration问题。这⾥使⽤了加⼀个noi process中产⽣的noi sample到actor policy来得到exploration policy（也就是behaviour policy）。
算法中actor和critic均⽤DNN表⽰，分为称为actor network和critic network。它们分别是deterministic policy 和value-action function 的FA，参数分别为和。在维度⽐较低时，有下⾯的结构：
μQ θQ θμ
清明节简介
⽽当输⼊为image（即raw pixels）时，按套路需要加卷积层和全连接层（这⾥是3层Conv，2层FC）来学习特征。这⾥⽤的深度⽹络优化⽅法为Adam optimizer（当前DNN主流优化算法之⼀）。在迭代更新过程中，先积累experience replay buffer直到达到minibatch指定个数，然后根据sample分别更新两个DNN。先更新critic，通过loss函数更新参数。然后，通过critic得到函数相对于动作的梯度，因为在actor的更新公式（也就是DPG定理）中会⽤到，然后应⽤actor更新公式更新参数。刚才得到的和，对于的更新，会按⽐例（通过参数）更新到target network。这个target network会在下⼀步的训练中⽤于predict策略和函数值。
这篇⽂章主打解决⾼维连续动作控制问题，最⼤的特点就是简单。实验包括cartpole swing-up, dexterous manipulation, legged locomotion和car driving（Torcs）等各种控制场景。
ICML 2016 DeepMind 《Asynchronous Methods for Deep Reinforcement Learning》
这篇论⽂中提出了A3C（asynchronous advantage actor-critic）算法。它不仅适⽤于离散也适⽤于连续动作空间的控制问题。这是2016提出的⽅法，到现在已有不少基于该算法的改进，但基本思想和框架没有⼤改，如今仍是最⽜逼的DRL算法之⼀。之前⼀想到DRL，⾔必集群，⾔必GPU，不提这些不好意思跟⼈打招呼。当然，DRL领域也确实有很成功的分布式机器学习系统，⽐如Google的Gorila。这篇⽂章另辟蹊径，发明了“平民版”的DRL算法，证明了我们这些架不起集群，买不起GPU的穷⼈也照样能玩转前沿⾼端科技，⽽且效果还不⽐前者差。
北京营业执照
传统经验认为，online的RL算法在和DNN简单结合后会不稳定。主要原因是观察数据往往波动很⼤且前后sample相互关联。像Neural fitted Q iteration和TRPO⽅法通过将经验数据batch，或者像DQN中通过experience replay memory对之随机采样，这些⽅法有效解决了前⾯所说的两个问题，但是也将算法限定在了off-policy⽅法中。本⽂提出了另⼀种思路，即通过创建多个agent，在多个环境实例中并⾏且异步的执⾏和学习。于是，通过这种⽅式，在DNN下，解锁了⼀⼤批online/offline的RL算法（如Sarsa, AC, Q-learning）。它还有个潜在的好处是不那么依赖于GPU或⼤型分布式系统。A3C可以跑在⼀个多核CPU上。总得来说，这篇论⽂更多是⼯程上的设计和优化。另外，将value function的估计作为baline可以使得PG⽅法有更低的variance。这种设定下，，即就是advantage function的估计。这也是A3C名字中其中⼀个A - advantage的由来。
这篇⽂章将one-step Sarsa, one-step Q-learning, n-step Q-learning和advantage AC扩展⾄多线程异步架构。注意这⼏种⽅法特点迥异，AC是on-policy的policy搜索⽅法，⽽Q-learning是off-policy value-bad⽅法。这也体现了该框架的通⽤性。简单地说，每个线程都有agent运⾏在环境的拷贝中，每⼀步⽣成⼀个参数的梯度，多个线程的这些梯度累加起来，⼀定步数后⼀起更新共享参数。它有⼏个显著优点：1）它运⾏在单个机器的多个CPU线程上，⽽⾮使⽤parameter rver的分布式系统，这样就可以避免通信开销和利⽤lock-free 的⾼效数据同步⽅法（Hogwild!⽅法）。2）多个并⾏的actor可以有助于exploration。在不同线程上使⽤不同的探索策略，使得经验数据在时间上的相关性很
⼩。这样不需要DQN中的experience replay也可以起到稳定学习过程的作⽤，意味着学习过程可以是on-policy的。其它好处包括更少的训练时间，另外因为不需要experience replay所以可以使⽤on-policy⽅法（如Sarsa），且能保证稳定。
在这篇⽂章中提出的⼏种算法中主打的是A3C（asynchronous advantage actor-critic）算法（具体参见论⽂中的Algorithm S3）。该算法和DDPG类似，通过DNN维护了policy和value function的估计，但它没⽤deterministic policy。在学习过程中使⽤n-step回报来同时更新policy和value function。⽹络结构使⽤了CNN，其中⼀个softmax output作为policy ，⽽另⼀个linear output为value function ，其余layer都共享。另外，作者还发现⼀个古⽼的技巧，即将policy的entropy加到⽬标函数可以避免收敛到次优确定性解。直观上，加上该正则项后⽬标函数更⿎励找entropy⼤的，即形状“扁平”的分布，这样就不容易在训练过程中聚集到某⼀个动作上去。在优化⽅法上，作者使⽤了基于RPMProp的⼀种变体。整个过程⼤致如图L θQ Q a θμθQ θτQ R −t b (s )t t A (s ,s )=t t Q (a ,s )−t t V (s )t π(a ∣s ;θ)t t V (s ;θ)t v
