Policy Gradient and Advantage Estimation

一、策略梯度推导 (Policy Gradient derivation)

策略优化的目标是找到一组参数来最大化期望回报。我们使用的策略是随机性策略，它表示在状态下采取动作的概率。

目标函数

我们的目标是最大化期望的累积奖励：

我们将一个状态-动作序列（即轨迹）表示为，该轨迹的回报为。

目标函数可以写成对所有可能轨迹的期望：

其中是在策略下，轨迹发生的概率。

似然比策略梯度 (Likelihood Ratio Policy Gradient)

为了通过梯度上升来优化参数，我们需要计算目标函数对的梯度。推导过程如下：

对目标函数求导：
将梯度算子移入求和号内：
应用 "log-derivative trick" (即 )：
重新整理：
将分数形式转换为对数梯度形式：这个最终的表达式是梯度的一个期望形式。

梯度估计

在实践中，我们无法遍历所有可能的轨迹。因此，我们通过从当前策略采样条轨迹，来近似计算梯度：

这个估计是无偏的，即。

直观理解

策略梯度的直观含义是：

对于回报为正的轨迹，我们增大概率，即增大。
对于回报为负的轨迹，我们减小概率，即减小。

这种方法即使在回报函数不连续或未知的情况下也有效。

二、时间分解 (Temporal decomposition)

在上一步中，策略梯度是基于整条轨迹的概率来计算的。为了让这个表达式更易于计算，特别是为了消除对环境动态模型（dynamics model）的依赖，我们将其分解到每个时间步。

分解路径概率的对数梯度

一条轨迹的概率是初始状态概率、所有时间步的环境转移概率和策略概率的乘积：其中是环境动态，与策略参数无关，而是我们的策略，与相关。
对其取对数，乘积就变成了求和：
对求梯度。由于环境动态和初始状态概率都不依赖于，它们的梯度为零。因此，梯度表达式可以简化为：
将梯度算子移入求和号内：

最终的策略梯度估计

通过将上述分解后的结果代入我们之前的梯度估计公式，我们得到了一个更实用、无需知道环境动态模型的表达式：

这个估计仍然是无偏的，并且我们完全可以根据采样的轨迹数据（状态和动作）以及我们的策略模型来计算它，不再需要环境模型。

三、基线缩减 (Baseline subtraction)

尽管我们推导出的策略梯度估计是无偏的，但它通常具有非常高的方差，这使得训练过程不稳定且效率低下。为了解决这个问题，我们可以引入一个“基线”（Baseline）来降低方差。

引入基线

我们从轨迹的回报中减去一个基线值。新的梯度估计器形式如下：

只要基线不依赖于动作，这个新的估计器就仍然是无偏的。证明如下：

我们只需证明减去项的期望为零：

利用时间结构

一个重要的观察是：在时刻的策略只会影响时刻及之后的回报，而不会影响过去的回报。因此，我们可以将梯度估计器中的总回报替换为“未来回报总和”（reward-to-go），从而进一步降低方差。

结合基线，梯度估计器可以写成：

这里的基线可以依赖于状态。

基线的选择

选择一个好的基线对于有效降低方差至关重要。常见的选择有：

常数基线:
最优常数基线: 。
时变基线: 。
状态相关的期望回报 (价值函数): 一个非常有效且常用的基线是状态价值函数。使用价值函数作为基线，意味着我们根据一个动作的回报比当前状态的期望回报好多少，来成比例地增加该动作的对数概率。这时，被称为优势函数 (Advantage Function)。

四、价值函数估计 (Value function estimation)

为了使用状态价值函数作为基线，我们需要一种方法来估计它的值。通常使用一个带参数的函数逼近器（如神经网络）来进行估计。主要有两种方法：蒙特卡洛估计和自举法（Bootstrapping）。

1. 蒙特卡洛估计 (Monte Carlo Estimation)

这种方法使用完整的轨迹来获取回报的经验样本作为的目标值。

步骤:
1. 使用当前策略收集一批轨迹。
2. 对于每条轨迹中的每一个时间步，计算从该点开始的实际累积回报（reward-to-go）: 。
3. 通过最小化预测值与实际回报之间的均方误差来更新参数。
优化目标:

2. 自举法/时序差分估计 (Bootstrap Estimation / TD Estimation)

这种方法不依赖于完整的轨迹，而是使用贝尔曼方程，通过下一个状态的价值估计来更新当前状态的价值。这也被称为“拟合V迭代”（Fitted V iteration）。

贝尔曼方程:
步骤:
1. 使用当前策略收集转换样本数据 (当前状态，动作，下一状态，奖励)。
2. 使用“TD目标值” 作为当前状态价值的学习目标。这里的是用旧参数计算的下一状态的价值估计。
3. 通过最小化“TD误差” 的平方来更新参数。
优化目标: （这里的是一个正则化项系数，防止更新步长过大）

五、优势函数估计 (Advantage Estimation (A2C/A3C/GAE))

策略梯度更新的核心是优势函数。其中，是在状态执行动作后期望的回报，而是在状态的期望回报。使用蒙特卡洛方法直接从单次交互中估计值（即使用作为估计）会有很高的方差，且不利用样本间的泛化。因此，发展出了更精细的估计方法来在偏差和方差之间做权衡。

这些方法通过使用一个“评论家”（Critic，即价值函数）来降低“行动家”（Actor，即策略）的梯度估计方差。

1. 通过函数逼近降低方差

我们可以用不同的方式来估计Q值，从而得到不同偏差和方差的优势函数估计。

可以被展开为不同步数（k-step）的回报：

1步估计:
2步估计:
k步估计:
蒙特卡洛估计 (无穷步):

2. A2C / A3C (优势行动家-评论家)

异步优势行动家-评论家（Asynchronous Advantage Actor-Critic）算法通常采用k步估计中的一种来计算目标Q值（例如使用5步回报）。这是一种在偏差（使用函数逼近导致）和方差（使用真实回报导致）之间的折中。

3. GAE (泛化优势估计)

泛化优势估计（Generalized Advantage Estimation）通过引入一个额外的参数 (其中 )，对所有k步估计进行加权平均，从而更灵活地控制偏差和方差的平衡。

GAE是所有k步回报的指数加权平均。
这个思想与 TD(lambda) 和资格迹（eligibility traces）有关。

使用A3C或GAE的策略梯度算法流程

初始化策略网络和价值网络。
循环以下步骤：
1. 收集数据: 在环境中执行当前策略，收集转换数据。
2. 计算优势函数: 使用收集的数据和当前价值网络计算Q值的估计（例如，使用k步回报或GAE），并由此得到优势函数估计。
3. 更新价值网络: 通过最小化预测值与目标值之间的误差来更新评论家（价值网络）的参数。
4. 更新策略网络: 使用计算出的优势函数估计来更新行动家（策略网络）的参数：