【RL入门】Policy-based算法

TRPO算法
PPO 算法原理
GAE

Policy-based强化学习优化目标

\underset{π_{θ}}{\arg max} J (π_{θ}) = E_{τ \sim π_{θ}} [R (τ)] = \sum_{τ} R (τ) P (τ | π_{θ})

$τ \sim π_{θ}$ : 即该轨迹在策略 $π_{θ}$ 下采样出来的，即
$\begin{matrix} a_{t} \sim π_{θ} (a_{t} | s_{t}) \\ s_{0} \sim ρ_{0} (.) \\ s_{t + 1} \sim P (. | s_{t}, a_{t}) \\ r_{t} = R (s_{t}, a_{t}, s_{t + 1}) \end{matrix}$

RL 优化过程：策略（价值）评估+策略迭代（改善）
策略评估与价值评估可以同时进行
- value-based：只要我们知道状态空间 $S$ 和动作空间 $A$ ， $V_{π}$ 就可以作用到这两个空间上帮助衡量哪个状态/动作的价值最大，进而隐式地承担起制定策略的角色
- policy-based：让策略和环境交互多次，采样足够多的轨迹数据，用这些数据去对策略的价值做评估，然后再据此决定策略的迭代方向
- actor-critic（actor表示策略，critic表示价值）：同时有价值实体 $V_{π}$ 和策略实体 $π$ ，然后按照上面过程进行迭代

策略梯度上升（REINFORCE 算法）

计算梯度：

\begin{aligned} \nabla J (π_{θ}) & = E_{τ \sim π_{θ}} [R (τ) \nabla \log (P (τ | π_{θ}))] \\ = E_{τ \sim π_{θ}} [R (τ) \sum_{t = 0}^{T - 1} \nabla \log π_{θ} (a_{t} | s_{t})] \end{aligned}

Proof

$\begin{aligned} \nabla J (π_{θ}) & = \sum_{τ} R (τ) \nabla P (τ | π_{θ}) \\ = \sum_{τ} R (τ) P (τ | π_{θ}) \frac{\nabla P (τ | π_{θ})}{P (τ | π_{θ})} \\ = \sum_{τ} R (τ) P (τ | π_{θ}) \nabla \log (P (τ | π_{θ})) \\ = E_{τ \sim π_{θ}} [R (τ) \nabla \log (P (τ | π_{θ}))] \end{aligned}$

对 $\nabla \log (P (τ | π_{θ}))$ 展开推导：
基于策略产生轨迹的概率：

P (τ | π_{θ}) = ρ_{0} (s_{0}) \prod_{t = 0}^{T - 1} P (s_{t + 1} | s_{t}, a_{t}) π_{θ} (a_{t} | s_{t})

上述式子中仅 $π_{θ} (a_{t} | s_{t})$ 与策略有关，因此：

\begin{aligned} \nabla \log (P (τ | π_{θ})) & = \nabla [\log ρ_{0} (s_{0}) + \sum_{t = 0}^{T - 1} \log P (s_{t + 1} | s_{t}, a_{t}) + \sum_{t = 0}^{T - 1} \log π_{θ} (a_{t} | s_{t}))] \\ = \sum_{t = 0}^{T - 1} \nabla \log π_{θ} (a_{t} | s_{t}) \end{aligned}

在实践中，可以通过采样足够多的轨迹来估计这个期望。假设采样 $N$ 条轨迹， $N$ 足够大，每条轨迹涵盖 $T_{n}$ 步，则上述优化目标可被写成

\begin{aligned} J (π_{θ}) & = E_{τ \sim π_{θ}} [\sum_{t = 0}^{T - 1} R (τ) \log π_{θ} (a_{t} | s_{t})] \\ \approx \frac{1}{N} \sum_{n = 0}^{N - 1} \sum_{t = 0}^{T_{n} - 1} R (τ_{n}) \log π_{θ} (a_{t} | s_{t}) \end{aligned}

梯度为

\nabla J (π_{θ}) \approx \frac{1}{N} \sum_{n = 0}^{N - 1} \sum_{t = 0}^{T_{n} - 1} R (τ_{n}) \nabla \log π_{θ} (a_{t} | s_{t})

REINFORCE 算法能够直接优化策略的期望回报，是一种 on-policy 算法，比基于价值的强化学习算法的优化目标更直接；但同时梯度估计方差较大（随机动作时间沿着轨迹不断累积导致），可能会造成不稳定，这也是后续Actor-Critic算法试图解决的问题

基线 REINFORCE（VPG）

Vanilla Policy Gradient or REINFORCE with baseline, 处理算法中的梯度估计方差大的问题

使用部分 Return 而非全部，来改变动作的对数概率。
但同时概率会随着 reward 变化明显导致难以区分好坏。比如冰湖环境中，reward 均为正的，一旦随机选取了某个动作就会导致其概率增大，而不考虑其他动作的平均结果，从而影响其他动作选取, 因此体现 baseline 的重要性
这里便采用 action-advantage 函数区分相同状态下动作-值的收益 $A (S_{t}, A_{t}) \approx R_{t} + γ R_{t + 1} + . . . + γ^{T - 1} R_{T} - v_{π} (S_{t})$

L_{π} (θ) = - \frac{1}{N} \sum_{n = 0}^{N} [(G_{t} - V (S_{t}; ϕ)) \log π (A_{t} | S_{t}; θ) + β H (π (S_{t}; θ))]

REINFORCE 基线算法是 actor-critic 法吗？

First, according to one of the fathers of RL, Rich Sutton, policy-gradient methods approximate the gradient of the performance measure, whether or not they learn an approximate value function. However, David Silver, one of the most prominent figures in DRL, and a former student of Sutton, disagrees. He says that policy-based methods don’t additionally learn a value function, only actor-critic methods do. But, Sutton further explains that only methods that learn the value function using bootstrapping should be called actor-critic, because it’s bootstrapping that adds bias to the value function, and thus makes it a “critic.” I like this distinction; therefore, REINFORCE and VPG, as presented in this book, aren’t considered actor-critic methods. But beware of the lingo, it’s not consistent.

价值函数

上述 $\nabla J (π_{θ})$ 的公式中， $R (τ)$ 是整条轨迹奖励，但 $π_{θ} (a_{t} | s_{t})$ 却是针对单步的。不合理之处在于：用整条轨迹的回报去评估单步动作的价值，然后决定要提升/降低对应的概率（但又不能完全忽视轨迹的最终回报，因为最终目标是让这个回合的结果是最优的。）

衡量单步价值时，在【单步回报】和【轨迹整体回报】间找到一种平衡方式

\nabla J (π_{θ}) \approx \frac{1}{N} \sum_{n = 0}^{N - 1} \sum_{t = 0}^{T_{n} - 1} Ψ_{t} \nabla \log π_{θ} (a_{t} | s_{t})

用更一般的符号 $Ψ_{t}$ 表示可行的价值函数

$Ψ_{t}$ 的形式：
- $\sum_{t = 0}^{+ \infty} r_{t}$
- $\sum_{t^{'} = t}^{\infty} r_{t^{'}}$
- $\sum_{t^{'} = t}^{\infty} r_{t^{'}} - b (s_{t})$ (baseline version)
- $Q^{π} (s_{t}, a_{t})$
- $A^{π} (s_{t}, a_{t})$
- $r_{t} + V^{π} (s_{t + 1}) - V^{π} (s_{t})$

这里采用累计折扣奖励好些

Actor-Critic

在actor-critic方法下，我们用神经网络 $θ$ 来表示策略（actor），神经网络 $ϕ$ 来表示价值（critic），所以这里我们进一步把 $V_{π}$ 写成 $V_{ϕ}$

选择第6种（TD error）作为 $Ψ_{t}$ ，它衡量在某个时刻 $t$ 选择某个动作 $a$ 会比在策略 $π$ 下（ $π_{θ} (a_{t} | s_{t})$ ）选取动作要好多少

当 $V_{π}$ 等于客观存在的真值 $V_{π}^{*}$ 时，TD-error是 $A^{π} (s_{t}, a_{t})$ 的无偏估计

Proof

$\begin{aligned} A_{π} (s_{t}, a_{t}) & = Q_{π} (s_{t}, a_{t}) - V_{π} (s_{t}) \\ = E_{s_{t + 1} \sim P (. | s_{t}, a_{t})} [r_{t} + γ V_{π} (s_{t + 1})] - E_{s_{t + 1} \sim P (. | s_{t}, a_{t})} [V_{π} (s_{t})] \\ = E_{s_{t + 1} \sim P (. | s_{t}, a_{t})} [r_{t} + γ V_{π} (s_{t + 1}) - V_{π} (s_{t})] \\ = E_{s_{t + 1} \sim P (. | s_{t}, a_{t})} [TD error] \end{aligned}$

Actor 优化目标

\arg max_{π_{θ}} J (π_{θ}) \approx \frac{1}{N} \sum_{n = 0}^{N - 1} \sum_{t = 0}^{T_{n} - 1} (r_{t} + γ V_{ϕ} (s_{t + 1}) - V_{ϕ} (s_{t})) \log π_{θ} (a_{t} | s_{t})

Critic 优化目标

a r g min_{V_{ϕ}} L (V_{ϕ}) = E_{t} [∥ r_{t} + γ V_{ϕ} (s_{t + 1}) - V_{ϕ} (s_{t}) ∥_{2}]

当我们推动critic loss（优势）趋于0时：
- 对critic来说，是推动它准确衡量当前策略的价值，逐步逼近 $V_{π^{*}}$
- 由于逼近到 $V_{π^{*}}$ 时，TD-error 是 $A^{π} (s_{t}, a_{t})$ 的无偏估计。因此对 actor 来说相当于逼近 $A_{π^{*}} (s_{t}, a_{t})$ ，即向 $π^{*}$ 拟合

PPO

Actor 的梯度

\begin{aligned} \nabla J (π_{θ}) & = E_{t} [A_{ϕ} (s_{t}, a_{t}) \nabla l o g π_{θ} (a_{t} | s_{t})] \\ \approx \frac{1}{N T} \sum_{n = 0}^{N - 1} \sum_{t = 0}^{T_{n} - 1} (r_{t} + γ V_{ϕ} (s_{t + 1}) - V_{ϕ} (s_{t})) \nabla \log π_{θ} (a_{t} | s_{t}) \end{aligned}

存在的问题
- 每次执行这个梯度更新时，都需要对 $π_{θ}$ 进行若干次回合采样。时间成本比较高，整个训练过程会比较慢 ———> 重要性采样
- 实际训练的过程中，用critic网络拟合出来 $V_{π}$ 并不一定是能准确衡量 $π$ 的那个价值函数，所以这里我们用TD error去估计优势函数其实是有偏的 ———> GAE

重要性采样

通过 off-policy（产出数据的策略和用这批数据做更新的策略不是同一个），重复利用 $k$ 次策略 $π_{o l d}$ 采样的数据， $k$ 次更新后再令 $π_{o l d} = π_{θ}$

理论分析

假设有两个分布 $p (x), q (x)$ 因为某些原因，我们无法从中直接采样，只能从另一个分布中进行采样了，那么此时我们要怎么表示 $E_{x \sim p (x)} [f (x)]$ ，采用如下变换：

\begin{aligned} E_{x \sim p (x)} [f (x)] & = \int p (x) f (x) d x \\ = \int \frac{p (x)}{q (x)} q (x) f (x) d x \\ = E_{x \sim q (x)} [\frac{p (x)}{q (x)} f (x)] \end{aligned}

上述的转换即添加了一个权重 $p (x) / q (x)$ 过程叫【重要性采样】。
实际操作中，可能遇到 $p (x), q (x)$ 分布差异较大的问题。在某次采样中，从 $q (x)$ 里进行采样，大概率会采集到图中绿色曲线的高处，此时 $f (x)$ 是正的。也就是说，在单次采样中，我们大概率会得到一个正的 $f (x)$ ，但权重 $p (x) / q (x)$ 较小。因此，只有经过尽可能多次的采样，让某次能命中 $q (x)$ 这个绿色曲线的低处，同时配以较大的权重，才足以抵消正 $f (x)$ 的影响
|500

当p(x)和q(x)差异较大时，仍需要通过足够多的采样来抵消这种差异对期望的最终影响。

重要性采样后的策略梯度

\nabla J (π_{θ}) = \underset{τ \sim π_{θ_{o l d}}}{E_{t}} [\frac{π_{θ} (a_{t} | s_{t})}{π_{o l d} (a_{t} | s_{t})} A_{ϕ} (s_{t}, a_{t}) \nabla \log π_{θ} (a_{t} | s_{t})]

反推出新的 actor 优化目标

\arg max_{π_{θ}} J (π_{θ}) = \underset{τ \sim π_{θ_{o l d}}}{E_{t}} [\frac{π_{θ} (a_{t} | s_{t})}{π_{θ_{o l d}} (a_{t} | s_{t})} A_{ϕ} (s_{t}, a_{t})]

仍需解决 $π_{θ}, π_{θ_{o l d}}$ 分布差异大的情况

GAE：平衡优势函数的方差和偏差

假设 $V_{π}$ 能正确评估策略 $π$ 的价值的前提下，我们用 TD error 作为优势函数的无偏估计。但在训练过程中， $V_{π}$ 往往无法完全正确评估出策略的价值，引发系统性偏差，无法用多次采样逼近真实值

A_{π} (s_{t}, a_{t}) = E_{s_{t + 1} \sim P (. | s_{t}, a_{t})} [r_{t} + γ V_{π} (s_{t + 1}) - V_{π} (s_{t})]

为了解决因为估计不准而引发的“高偏差”问题，直观上可以尽量少信任 $V_{π}$ 的策略（把 $V_{π} (s_{t + 1})$ 递归展开，相信实际采样结果）

r_{t} + γ V_{π} (s_{t + 1}) - V_{π} (s_{t}) = - V_{π} (s_{t}) + \sum_{l = 0}^{\infty} γ^{l} r_{t + l}

但改为实际采样结果相当于增加了随机性（ $r_{t}, r_{t + 1}, \dots$ 均为随机变量），即偏差降低，方差增加。需要更多数据训练

GAE(Generalized Advantage Estimator)：平衡优势函数的方差和偏差

Ψ_{t} = \sum_{l = 0}^{T - 1} (γ λ)^{l} δ_{t + l}

$δ_{t} = r_{t} + γ V_{π} (s_{t + 1}) - V_{π} (s_{t})$
$γ$ : 超参，折扣因子
$λ$ : 超参，平衡方差-偏差的因子。 $Ψ_{t} = r_{t} + γ V_{π} (s_{t + 1}) - V_{π} (s_{t}), λ = 0$ ； $Ψ_{t} = - V_{π} (s_{t}) + \sum_{l = 0}^{\infty} γ^{l} r_{t + l}, λ = 1$ 。即 $λ$ 越大，方差越大，偏差越小

PPO前身：TRPO

Trust Region Policy Optimization (TRPO)

引入重要性采样解决采样效率问题，引入 GAE 解决单步优势的方差-偏差问题。
考虑当 $π_{θ}$ 和 $π_{o l d}$ 差异较大时，采样效率仍不高， $J (π_{θ})$ 估计不准确，TRPO 解决方法为把两者分布的相似性作为 constraint
优化目标：

\begin{aligned} \arg max_{π_{θ}} & J (π_{θ}) = E_{t} [\frac{π θ (a_{t} | s_{t})}{π_{o l d} (a_{t} | s_{t})} A_{ϕ}^{G A E} (s_{t}, a_{t})] \\ s . t . & E_{t} [K L (π_{θ o l d} (\cdot | s_{t}), π_{θ} (\cdot | s_{t}))] \leq δ \end{aligned}

缺陷：由于 constraint 不在优化函数中，因此优化过程变得复杂

PPO 的改进：PPO-Clip

把 constraint 放回 $J (π_{θ})$ 中
Clip 思想
- $A_{ϕ}^{G A E} (s_{t}, a_{t}) > 0$ 时，说明当前动作 $a_{t}$ 相比别的动作更好——>提升 $π_{θ} (a_{t} | s_{t})$ 。
  但由于较少采样数，因此 $π_{θ}, π_{o l d}$ 不能差异过大，因此保证其上限，设为 $1 + ϵ$ （保证持续不反应过度的“进步”）
- $A_{ϕ}^{G A E} (s_{t}, a_{t}) < 0$ 反之同理，clip 不超过 $1 - ϵ$

J^{C L I P} (π_{θ}) = \underset{τ \sim π θ_{o l d}}{E_{t}} {m i n [\frac{π_{θ} (a_{t} | s_{t})}{π_{θ_{o l d}} (a_{t} | s_{t})} A_{ϕ}^{G A E} (s_{t}, a_{t}), c l i p (\frac{π_{θ} (a_{t} | s_{t})}{π_{θ_{o l d}} (a_{t} | s_{t})}, 1 - ϵ, 1 + ϵ) A_{ϕ}^{G A E} (s_{t}, a_{t})]}

PPO 的改进：PPO-Penalty

把 constraint 作为 KL-penalty

\arg max_{π_{θ}} J (π_{θ}) = E_{t} [\frac{π_{θ} (a_{t} | s_{t})}{π_{θ_{o l d}} (a_{t} | s_{t})} A_{ϕ}^{G A E} (s_{t}, a_{t}) - β K L (π_{θ o l d} (\cdot | s_{t}), π_{θ} (\cdot | s_{t}))]

超参 $β$ 调整：
1. 对 KL 散度设置 threshold， $K L_{m a x}, K L_{m i n}$
2. $K L \geq K L_{m a x}$ 时说明策略偏离 old 策略较远，增大 $β$
3. $K L \leq K L_{m a x}$ 时说明策略可能找到了捷径（只优化 KL），此时应降低 $β$

PPO (Proximal Policy Optimization，近端策略优化)。通过以上方法限制了策略更新的幅度，以避免过大的更新导致的训练不稳定，由此体现了“近端”

参考

人人都能看懂的RL-PPO理论知识