Policy Gradient

1. Policy Gradient

对于RL来说，我们想要找出一个最好的policy来完成任务，比如打游戏的时候见到坑要知道跳，见到怪要知道打，见到金币得知道吃等等。前面说的RL的最终任务就是要最大化期望累计reward，这里的最大化是通过找一个最优的policy来实现的。下面公式中的\theta是policy \pi的参数（比如我们用神经网络来计算policy，那么\theta就是网络的参数）

学过监督学习的我们知道，在监督学习中很多很多的算法都是可以通过梯度下降的方法来求解的，那么给定RL的目标方程，我们同样也可以使用梯度的方法来更新求解policy，使得最大化期望累计reward。也就是说，只需要用积分那一项（令他为J(\theta)）对\theta求导就可以了。注意，这里我们假定了policy是可导的。policy的形式往往是人定的（比如gaussian，神经网络等等），所以policy可不可导也是可控的。

问题就变成求出\bigtriangledown_\theta\pi_\theta(\tau)就ok了，大牛们当然不会直接去求解这一项，因为从最开始的式子里可以看到，\pi_\theta(\tau)涉及到多项相乘，直接求导会很心累。所以大牛提出了一个 convenient identity

其中在贝叶斯里往往把\bigtriangledown_\theta log \pi_\theta(\tau)叫做score function。比如以一次动作为例，当我们用softmax来近似policy \pi_{\theta}(\tau)的时候（这叫做Softmax Policy），这时的score function可以写成下式，这个式子衡量了当前动作相比于平均动作的好坏。

同理，如果我们使用的是Gaussian，也就对应着叫Gaussian Policy:

这个score function的含义还是类似的，他也刻画了action与平均action的差异。注意，以上两个例子中，我们都假定了policy中的输入参数state是policy 参数\theta和state feature \phi(s)之间的linear combination \phi(s) ^T \theta。如果需要加大表达能力，则完全可以采用其他函数，比如神经网络f(s)。

现在，我们把convenient identity带入到\bigtriangledown_\theta J(\theta)中就得到

也就是说，这个identity可以在保证期望形式不变的条件下，简化计算。形式优美，让当下RL科研工作者沿用至今，是一个常用的方法。那么这个导数里的期望怎么算？采样！

到这里，policy gradient和极大似然估计还是比较神似的。只是说，RL中对episode加权咯，优化的结果就是，它会偏好reward高的episodes，使得它们出现概率更高，相反不好的action所导致的episode，出现概率低。

其实，REINRORCE算法就是这么做的，这里折扣因子\gamma=1

该算法会在每次迭代中，从当前的policy中采样，也就是用这个policy来玩一下游戏，得到一些episodes，然后用采样样本计算梯度，执行梯度上升算法（因为我们要max，而不是min）以提升当前policy。所以REINFORCE算法是一种On-Policy Monte-Carlo Policy-Based RL算法。这里的On-policy指用于学习policy \pi的样本是原于\pi本身的；相反则是off-policy，用于学习policy \pi的样本是原于其他策略。

2. Improved Policy Gradients

Policy Gradient和大家常用的SGD同样都有high variance，slow convergence以及难以选择learning rate的问题。对于variance的问题，可以想象成如果policy空间铺得太开，就不容易选中最应该选择的action（比如高斯的均值处）。下面就reduce variance做一个总结，其他的问题可以通过叫natural policy gradient的方法解决。一般来说，降低variance，可以走两种方案

Causality, reward to go：今天做的动作，不会影响昨天发生的事

Baselines：选一个比平均动作更好的动作

Causality, Reward to go简单的形式如下。唯一不同的地方就是对reward的sum，不在是从1开始，而是从当前action发生的时刻开始，对于当前action动作以前的时刻所产生的reward不在考虑。这时候的方差减小的原因是。。reward叠加的数值变小咯，相对variance也会减少。

BaselinesBaseline想做的是，与其直接最大化每个episode的累计reward，不如最大化每个episode reward 与 平均reward的差值，使得episode能做得比平均值更好。对于比平均做得差的，那就降低他的出现概率。

与之前的公式相比，新添加的b并不会带来影响，因为期望是等于0的

那么b应该取什么值呢？一开始引入Baseline的原因是为了降低variance，那么引入b之后的variance等于啥呢

为了最小化上面的式子，可以对b求导，可以得到下面的第一个式子，但是在实际使用中往往使用第二个，也就是第一个的不加权求和的版本。

3. Off-policy policy gradients

之前说到的policy gradient是on-policy的，我们使用源于同一个policy下的样本来更新policy本身。当然，我们也可以使用off-policy的方式。on-policy的方式，一旦policy改变了，就必须在下一次迭代的时候。重新采样新的episode，折痕inefficient！off-policy是从别的策略（叫做behaviour policy）中采样，来更新我们想要的策略（target policy），这种方式最大的好处就在于可以做policy exploration，而不是仅仅的policy exploitation。啥意思？RL最大的bug就在于policy和value funciton的搜索空间实在是太大了，在寻找最优解的时候，我们要竟可能的去探索未知（exploration），同时需要在已经探索过的地方，充分挖掘，找出最好（exploitation）。这两者之间的矛盾就好比晚饭吃去过的最好餐馆还是去尝试新馆子，新馆子当然会有好有坏。总的来说，off-policy提供了一个behavior policy，以便我们用别的知识来接入。

从别的地方采样，用于自己的任务，这种方式就是大家熟悉而喜爱的Importance Sampling干的事。简单的说，重要性采样提供了直接近似期望的框架，它假定直接从目标分布P(X)中采样无法完成，但是对于任意给定的X值，我们可以很容易地计算P(X)的值。如此，为了计算其期望E[f(X)]=\int f(X)P(X)dX，我们希望对P(X)值大（质量大）的区域中尽可能多的进行采样，因为这部分的样本对期望的计算发挥的作用更大。重要性采样，把容易被采样的新的分布Q(X)作为目标采样分布，并且赋予这些采样的样本一定的权重，整个样本上的不同大小的权重值的则构成了真实的P(X)的采样数据，如下所示。

那么应用到RL的目标中就是

对应的梯度是下式，其中第三个式子，是在第二个式子的基础上考虑到Causality之后得到的：第三项表示现在的动作不会影响以前的reward，第二项是表示当前的动作仅仅与之前的策略有关。

4. Other Policy Gradients Methods

前面都是要求policy是可导的，但是如果policy实在不可导怎么办？有一个简单的办法就是去一维一维的近似梯度。这个方式很低效而且也会有很大error，但是也算是一种策略嘛

对于REINFORCE算法，他的梯度计算方式下式。这里的r(\tau)是整个episode的累计reward，这也就意味着，必须要等到episode执行完了之后才能更新

这之外还有很多其他的算法针对r(\tau)这项做变化