一文读懂深度强化学习算法A3C（Actor-CriticAlgorithm）
2017-12-2516:29:19
对于A3C算法感觉自己总是一知半解，现将其梳理一下，记录在此，也给想学习的小伙伴一个参考。
想要认识清楚这个算法，需要对DRL的算法有比较深刻的了解，推荐大家先了解下DeepQ-learning和PolicyGradient算法。
我们知道，DRL算法大致可以分为如下这几个类别：ValueBasedandPolicyBased，其经典算法分别为：Q-learning和PolicyGradientMethod。
而本文所涉及的A3C算法则是结合Policy和ValueFunction的产物，其中，基于Policy的方法，其优缺点总结如下：
Advantages:1.Betterconvergenceproperties（更好的收敛属性）2.Effectiveinhigh-dimensionalorcontinuousactionspaces（在高维度和连续动作空间更加有效）3.Canlearnstochasticpolicies（可以Stochastic的策略）Disadvantages:1.Typicallyconvergetoalocalratherthanglobaloptimum（通常得到的都是局部最优解）2.Evaluatingapolicyistypicallyinefficientandhighvariance（评价策略通常不是非常高效，并且有很高的偏差）
我们首先简要介绍一些背景知识（Background）：
在RL的基本设置当中，有agent，environment,action,state,reward等基本元素。agent会与environment进行互动，而产生轨迹，通过执行动作action，使得environment发生状态的变化，s->s'；然后environment会给agent当前动作选择以reward（positiveornegative）。通过不断的进行这种交互，使得积累越来越多的experience，然后更新policy，构成这个封闭的循环。为了简单起见，我们仅仅考虑deterministicenvironment，即：在状态s下，选择actiona总是会得到相同的状态s‘。
为了清楚起见，我们先定义一些符号：
1.stochasticpolicy$\pi(s)$决定了agent'saction,这意味着，其输出并非singleaction，而是distributionofprobabilityoveractions(动作的概率分布)，sum起来为1.
2.$\pi(a|s)$表示在状态s下，选择actiona的概率；
而我们所要学习的策略$\pi$，就是关于states的函数，返回所有actions的概率。
我们知道，agent的目标是最大化所能得到的奖励（reward），我们用reward的期望来表达这个。在概率分布P当中，valueX的期望是：
其中Xi是X的所有可能的取值，Pi是对应每一个value出现的概率。期望就可以看作是valueXi与权重Pi的加权平均。
我们再来定义policy$\pi$的valuefunctionV(s)，将其看作是期望的折扣回报(expecteddiscountedreturn)，可以看作是下面的迭代的定义：
这个函数的意思是说：当前状态s所能获得的return，是下一个状态s‘所能获得return和在状态转移过程中所得到rewardr的加和。
此时，我们可以定义一个新的functionA(s,a)，这个函数称为优势函数（advantagefunction）:
其表达了在状态s下，选择动作a有多好。如果actiona比average要好，那么，advantagefunction就是positive的，否则，就是negative的。
PolicyGradient：
当我们构建DQNagent的时候，我们利用NN来估计的是Q(s,a)函数。这里，我们采用不同的方法来做，既然policy$\pi$是state$s$的函数，那么，我们可以直接根据state的输入来估计策略的选择嘛。
这里，我们NN的输入是states，输出是anactionprobabilitydistribution$\pi_\theta$，其示意图为：
实际的执行过程中，我们可以按照这个distribution来选择动作，或者直接选择概率最大的那个action。
但是，为了得到更好的policy，我们必须进行更新。那么，如何来优化这个问题呢？我们需要某些度量（metric）来衡量policy的好坏。
我们定一个函数$J(\pi)$，表示一个策略所能得到的折扣的奖赏，从初始状态s0出发得到的所有的平均：
我们发现这个函数的确很好的表达了，一个policy有多好。但是问题是很难估计，好消息是：wedon'thaveto。
有一个很简便的方法来计算这个函数的梯度：
这里其实从目标函数到这个梯度的变换，有点突然，我们先跳过这个过程，就假设已经是这样子了。后面，我再给出比较详细的推导过程。
简单而言，这个期望内部的两项：
第一项，是优势函数，即：选择该action的优势，当低于averagevalue的时候，该项为negative，当比average要好的时候，该项为positive；是一个标量（scalar）；
第二项，告诉我们了使得log函数增加的方向；
将这两项乘起来，我们发现：likelihoodofactionsthatarebetterthanaverageisincreased,andlikelihoodofactionsworsethanaverageisdecreased.
Actor-Critic：
我们首先要计算的是优势函数A(s,a)，将其展开：
运行一次得到的sample可以给我们提供一个Q(s,a)函数的unbiasedestimation。我们知道，这个时候，我们仅仅需要知道V(s)就可以计算A(s,a）。
这个valuefunction是容易用NN来计算的，就像在DQN中估计action-valuefunction一样。相比较而言，这个更简单，因为每个state仅仅有一个value。
我们可以将valuefunction和action-valuefunction联合的进行预测。最终的网络框架如下：
这里，我们有两个东西需要优化，即：actor以及critic。
actor：优化这个policy，使得其表现的越来越好；
critic：尝试估计valuefunction，使其更加准确；
这些东西来自于thePolicyGradientTheorem:
简单来讲，就是：actor执行动作，然后critic进行评价，说这个动作的选择是好是坏。
Parallelagents：
Wecanrunseveralagentsinparallel,eachwithitsowncopyoftheenvironment,andusetheirsamplesastheyarrive.
2.Anotherbenefitisthatthisapproachneedsmuchlessmemory,becausewedon’tneedtostorethesamples.
此外，还有一个概念也是非常重要的：N-stepreturn。
通常我们计算的Q(s,a),V(s)orA(s,a)函数的时候，我们只是计算了1-step的return。
在这种情况下，我们利用的是从sample（s0,a0,r0,s1）获得的即刻奖励（immediatereturn），然后该函数下一步预测value给我们提供了一个估计approximation。但是，我们可以利用更多的步骤来提供另外一个估计：
或者n-stepreturn：
Then-stepreturnhasanadvantagethatchangesintheapproximatedfunctiongetpropagatedmuchmorequickly.Let’ssaythattheagentexperiencedatransitionwithunexpectedreward.In1-stepreturnscenario,thevaluefunctionwouldonlychangeslowlyonestepbackwardswitheachiteration.Inn-stepreturnhowever,thechangeispropagatednstepsbackwardseachiteration,thusmuchquicker.
N-stepreturnhasitsdrawbacks.It’shighervariancebecausethevaluedependsonachainofactionswhichcanleadintomanydifferentstates.Thismightendangertheconvergence.
这个就是异步优势actor-critic算法（Asynchronousadvantageactor-critic,即：A3C）。
以上是A3C的算法部分，下面从coding的角度来看待这个算法：
所涉及到的大致流程，可以归纳为：
在这其中，最重要的是lossfunction的定义：
下面分别对这三个部分进行介绍：
1.PolicyLoss：
我们定义objectivefunction$J(\pi)$如下：
这个是：通过策略$\pi$平均所有起始状态所得到的总的reward（totalrewardanagentcanachieveunderpolicy$\pi$averagedoverallstartingstates）。
根据PolicyGradientTheorem我们可以得到该函数的gradient：
我们尝试最大化这个函数，那么，对应的loss就是这个负函数：
我们将A(s,a)看做是一个constant，然后重新将上述函数改写为如下的形式：
我们就对于minibatch中所有样本进行平均，来扫一遍这个期望值。最终的loss可以记为：
2.ValueLoss:
thetruthvaluefunctionV(s)应该是满足BellmanEquation的：
而我们估计的V(s)应该是收敛的，那么，根据上述式子，我们可以计算该error：
这里大家可能比较模糊，刚开始我也是比较晕，这里的groundtruth是怎么得到的？？？
其实这里是根据sampling到的样本，然后计算两个V(s)之间的误差，看这两个valuefunction之间的差距。
所以，我们定义Lv为meansquarederror（givenallsamples）:
3.RegularizaitonwithPolicyEntropy:
为何要加这一项呢？我们想要在agent与environment进行互动的过程中，平衡探索和利用，我们想去以一定的几率来尝试其他的action，从而不至于采样得到的样本太过于集中。所以，引入这个entropy，来使得输出的分布，能够更加的平衡。举个例子：
fullydeterministicpolicy[1,0,0,0]的entropy是0；而totallyuniformpolicy[0.25,0.25,0.25,0.25]的entropy对于四个value的分布，值是最大的。
我们为了使得输出的分布更加均衡，所以要最大化这个entropy，那么就是minimize这个负的entropy。
总而言之，我们可以借助于现有的deeplearning的框架来minimize这个这些totalloss，以达到优化网络参数的目的。
Reference：
======================================================
PolicyGradientMethod目标函数梯度的计算过程：
referencepaper：policy-gradient-methods-for-reinforcement-learning-with-function-approximation（NIPS2000,MITpress）
过去有很多算法都是基于value-function进行的，虽然取得了很大的进展，但是这种方法有如下两个局限性：首先，这类方法的目标在于找到deterministicpolicy，但是最优的策略通常都是stochastic的，以特定的概率选择不同的action；
其次，一个任意的小改变，都可能会导致一个action是否会被选择。这个不连续的改变，已经被普遍认为是建立收敛精度的关键瓶颈。
而策略梯度的方法，则是从另外一个角度来看待这个问题。我们知道，我们的目标就是想学习一个，从state到action的一个策略而已，那么，我们有必要非得先学一个valuefunction吗？我们可以直接输入一个state，然后经过NN，输出action的distribution就行了嘛，然后，将NN中的参数，看做是可调节的policy的参数。我们假设policy的实际执行的表现为$\rho$，即：theaveragedrewardperstep。我们可以直接对这个$\rho$求偏导，然后进行参数更新，就可以进行学习了嘛：
1.PolicyGradientTheorem（策略梯度定理）
这里讨论的是标准的reinforcementlearningframework，有一个agent与环境进行交互，并且满足马尔科夫属性。
在每个时刻$t\in{0,1,2,...}$的状态，动作，奖励分别记为：st,at,rt。而环境的动态特征可以通过状态转移概率（statetransitionprobability）来刻画。