David silver强化学习课程第七课 策略梯度
第七课 策略梯度
快开学了比较懒，这两天督促一下自己把后面的笔记都整理一下。。。
强化学习方法分为两种：基于策略的方法和基于价值的方法。前面课程中提到的方法都是基于价值的方法，包括策略迭代、值迭代和值函数近似。基于价值的方法是根据价值函数来制定策略，这是一种间接优化策略的方式。那么我们可不可以直接得到策略？类似于值函数近似，我们用参数拟合策略，直接得到策略，这就是本课要讲的基于策略的方法—策略梯度。
本节先引入了策略的直接表示形式，接着描述了最优策略的目标方程，最后提出三种梯度上升方法优化策略参数，得到最优策略。这三种方法分别是：有限差分策略梯度、蒙特卡洛策略梯度和演员-评论家(Actor-Cretic)策略梯度。
前言
首先回顾一下上节课，我们讲了使用参数θ近似状态值函数、状态-动作值函数：
策略从值函数中产生，例如使用ε-贪婪策略。
在本节课中，我们直接用参数表示策略：
和之前的Pπ(a|s)不一样的是，Pπ(a|s)是概率集合，而这里的πθ(s,a)是概率密度函数，它决定了在一定参数和状态下选择任何动作的概率，在实际应用策略产生行为时，是按照这个概率分布进行行为采样的。本节课解决的也是model-free强化学习。
基于价值和基于策略的强化学习对比
基于价值的强化学习方法通过学习价值函数来指导策略制定(例如ε-贪婪)。而基于策略的强化学习方法没有价值函数，它直接学习策略，通过优化策略参数θ来获得较优的策略，以此最大化目标函数。
还有一种方法结合以上两种学习方法，称为演员-评论家(Actor-Critic)。
基于策略学习的优劣
优点：
- 相较于基于价值的学习方法，有更好的收敛性。
- 在高维或者连续的动作空间效率更高。因为基于价值学习的方法需要选择最大的q(s,a)，动作集很大的情况下计算量就很大。基于策略学习的方法不存在这种问题。
- 可以学习随机策略。基于价值学习的方法通过greedy提升策略，最终将会得到一个确定性策略，而基于策略学习的方法会得到关于动作的概率密度函数。
缺点：
- 通常会收敛到局部最优解。
- 评估一个策略通常是效率低下且具有很高的方差（没明白）
这里有两个例子说明了随机策略优于确定策略：
1）在石头剪刀布游戏中，每次出拳最好是随机的，因为确定的策略很容易被对方猜到。
2）在格子游戏中，当代理无法区分灰色格子的状态时（认为灰色格子是同一个状态），随机策略优于确定策略。对于确定性策略代理将永远向左/右走而无法获得宝藏（就算使用ε-贪婪策略也会长时间陷入困局中）：
而此时使用随机策略，较高的概率在几步内获得宝藏：
基于策略的强化学习可以学习到最优随机策略。
策略目标函数
现在有了策略函数πθ(s,a)，那么我们需要优化θ来找到最优随机策略。可是我们如何评价策略πθ的好坏呢？
自然而然的想到，遵循πθ(s,a)我们想要获得更多的奖励。针对不同的问题类型，提出三种目标函数：
-
start value，在有终止的episodic环境下，代理按照策略πθ从某一状态s1开始，直到episode结束获得的期望回报：
-
average value，在连续环境下，没有开始和结束状态，用所有状态的平均回报表示：
-
average reward per time-step，在连续环境下，也可以用所有状态所有动作的平均奖励表示：
其中，dπθ(s)是基于策略πθ生成的马尔科夫链关于状态的静态分布。
基于策略的强化学习方法是一个优化问题，我们的目的就是找到θ来最大化J(θ)。有一些方法不需要使用梯度，例如爬山法、遗传算法等。还有一些方法使用梯度，例如梯度下降、共轭梯度、拟牛顿法等。通常使用梯度的方法有更高的效率。在本节中，集中讲解使用梯度下降/上升的方法，同时利用序列结构。（不太明白这里序列结构是指什么）
1 有限差分策略梯度
策略梯度
令J(θ)可以是任何类型的策略目标函数，策略梯度算法可以使J(θ)沿着其梯度上升至局部最大值。同时确定获得最大值时的参数θ：
策略梯度为：
α是学习率/步长参数。
有限差分策略梯度
对于参数θ的任意维度k∈[1,n]，利用一个小的扰动ε来计算θk的偏导：
uk是一个单位向量，仅在第k个维度上值为1，其余维度为0。利用n次计算就可以得到n维的策略梯度。这种方法不要求策略函数是可微的。
2 蒙特卡洛策略梯度
Score Function
这里计算策略梯度要求策略πθ是可微分的(只要采取动作时是可微的就行），假设我们知道策略梯度
利用似然比的小技巧得到（不明太为什么称利用似然比？）：
将
称为score function。课程中提到它可以指导你调整策略以便可以朝着获取更多的某种东西的方向前进，同时便于计算目标函数的梯度。
这里举了两个例子，当策略采用softmax策略或高斯策略时的score function：
-
Softmax策略
首先使用特征的线性组合对动作进行加权：
选择动作的概率与权重的指数成正比:
score function为：
我看其它博主讲到φ(s,a)是动作的分值，应该是有问题的。这里φ(s,a)应该是特征向量。
-
高斯策略
softmax处理的是离散的动作，在连续的动作空间中，我们可以使用高斯策略。
使用高斯策略时，我们通常对于均值有一个参数化的表示，同样可以是一些特征的线性代数和：
方差可以是固定值，也可以用参数化表示，策略可以表示为：
那么score function为：
策略梯度定理
策略的梯度无法用来优化策略，现在我们考虑目标函数的梯度，使用梯度上升优化策略。首先考虑一个简单地单步MDP：从一个分布d(s)中采样得到一个状态s，从s开始采取一个行为a获得奖励Rs,a，然后终止。此时使用似然比来计算策略梯度：
可以看出来，利用似然比后可以表示为策略πθ下score funtion和奖励r乘积的期望形式。这两部分是很容易确定的，同时可以利用采样的形式去掉期望。（这里是引入score function的目的之一？）
利用似然比方法推广到多步的MDP问题，只需要将奖励r替换为长期奖励
。
定理：对于任何可微的策略πθ(s,a)，对于任何策略的目标函数有以下定理：
在这里引入了状态-动作值。策略梯度定理对参数的更新是向着奖励最大化的方向进行的。
蒙特卡洛策略梯度(REINFORCE)
结合策略梯度定理，利用随机梯度上升去掉其中的期望来更新参数，使用回报vt(这里没写成Gt)作为
的无偏估计得到REINFORCE算法：
（既然有蒙特卡洛策略梯度，那么有没有时间差分策略梯度？如果利用TD算法，应当使用Rt+1+Qπθ(st+1,at+1)作为
的有偏估计，这里用到的是其他策略的经验，属于异策略学习；同时更新θ的同时，Qπθ是不变的，肯定也要对Qπθ进行更新，这不是又回到了值函数更新。。。。但是我在网上没有查到类似的算法。。。。所以有没有呢）
3 Actor-Critic策略梯度
MC策略梯度具有很大的方差，为了达到更好的学习效果，这里使用参数化方法对动作-状态值函数进行估计，也就是critic：
actor-critic算法由两部分参数组成：
- Critic：使用w参数化状态-动作值函数
- Actor：使用critic得到的价值引导策略参数θ的更新
Actor-critic算法服是近似策略梯度：
实际上critic做的就是策略评估（有点类似于上面提到的问题TD策略迭代？这里是参数化Q）它评价了当前θ确定的策略πθ的好坏。关于这里的策略评估，如何更新参数w呢？可以使用上节课讲过的MC\TD(0)\TD(λ)\最小二乘法。
一个简单的actor-critic算法可以使用基于行为价值的critic，它使用一个线性价值函数来近似状态行为价值函数：
其中Critic的w使用TD(0)进行更新，Actor的θ使用策略梯度进行更新。算法如下：
注：该算法仅是基于线性价值函数的近似的Actor-Critic算法，它是online更新方式。
课程中提到，近似值函数引入了偏差(bias)，在有偏差的值函数下得到的策略梯度不一定能找到较好的解决方案。比如如果Qw(s,a)使用了重名特征(类似本文开头的灰色格子问题)。不过仔细涉及的近似值函数可以避免引入偏差，由此引入兼容函数估计(Compatible function approximation):
满足以下两个条件：
-
近似价值函数的梯度完全等同于策略函数对数的梯度
-
价值函数参数w使得均方差最小：
符合这两个条件，则认为策略梯度是准确的，此时：
之前为了减小Reinforce的方差，引入了critic。现在为了进一步减小方差，引入baseline。它在不改变期望的同时减小方差：
可以看到引入的B(s)与动作a无关，因此可以从求和中提出来。这样最后一项策略求和等于1，那么他的导数等于0，整个期望等于0。
一个比较好的baseline就是
，所以我们可以使用advantage function改写策略梯度：
advantage function显著降低了策略梯度的方差。现在critic变成了估计advantage function，例如可以使用两套参数同时估计：
并且可以通过TD学习来更新两套参数。
实际上，TD误差可以根据真实Vπθ(s)算出：
这样得到的TD误差是advantage function估计：
那么可以使用TD误差计算策略梯度：
此时使用近似TD误差，只有一套参数v：
针对Critic使用TD(λ)（这块参数有点乱，θ应该是cretic的参数）：
对于Actor过程使用TD(λ)：
这里critic和actor的更新应该可以选择不同的方式，例如critic选择TD(λ)，actor选择TD(0)更新。一般应该不会这样做吧?