8.1 策略学习的高级技巧：置信域策略优化 (TRPO)
策略学习的高级技巧：置信域策略优化 (TRPO)
PPO算法就是在TRPO的基础上推出的。
Trust Region Policy Optimization (TRPO)
置信域策略优化 (trust region policy optimization, TRPO) 是一种策略学习方法，跟以前学的策略梯度有很多相似之处。跟策略梯度方法相比，TRPO 有两个优势：第一，TRPO 表现更稳定，收敛曲线不会剧烈波动，而且对学习率不敏感；第二，TRPO 用更少的经验(即 智能体 收集到的状态、动作、奖励) 就能达到与策略梯度方法相同的表现。
学习TRPO 的关键在于理解置信域方法(trust region methods)。置信域方法不是TRPO 的论文提出的，而是数值最优化领域中一类经典的算法，历史至少可以追溯到 1970 年。TRPO 论文的贡献在于巧妙地把置信域方法应用到强化学习中，取得非常好的效果。
置信域方法
有这样一个优化问题：\(\max_\theta J(\theta)\)这里的\(J(\theta)\)是目标函数，\(\theta\)是优化变量。求解这个优化问题的目的是找到一个变量\(\theta\)使得目标函数\(J(\theta)\)取得最大值。有各种各样的优化算法用于解决这个问题。几乎所有的数值优化算法都是做这样的迭代：
\(\theta_{\text{new}} \leftarrow \text{Update}(Data; \theta_{\text{now}})\)
此处的\(\theta_{\text{now}}\)和\(\theta_{\text{new}}\)分别是优化变量当前的值和新的值。不同算法的区别在于具体怎么样利用数据更新优化变量。
置信域方法用到一个概念——置信域。下面介绍置信域。给定变量当前的值\(\theta_{\text{now}}\),用\(\mathcal{N} (\theta_{\text{now}})\)表示\(\theta_{\text{now}}\)的一个邻域。举个例子：
\(\mathcal{N}(\theta_{\text{now}}) = \{ \theta \mid \|\theta - \theta_{\text{now}}\|_2 \leq \Delta \}\)
这个例子中，集合\(\mathcal{N}(\theta_{\text{now}})\)是以\(\theta_{\text{now}}\)为球心、 以\(\Delta\)为半径的球；见右图。球中的点都足够接近\(\theta_{\text{now}}\)。
置信域方法需要构造一个函数\(L(\theta | \theta_{\text{now}})\),这个函数要满足这个条件：
\(L(\theta | \theta_{\text{now}}) \text{ 很接近 } J(\theta), \quad \forall \theta \in \mathcal{N}(\theta_{\text{now}})\)
那么集合\(\mathcal{N}(\theta_{\text{now}})\)就被称作置信域。顾名思义，在\(\theta_{\text{now}}\)的邻域上，我们可以信任\(L(\theta | \theta_{\text{now}})\), 可以拿\(L(\theta | \theta_{\text{now}})\)来替代目标函数\(J(\theta)\)。
图 9.2 用一个一元函数的例子解释\(J(\theta)\)和\(L(\theta | \theta_{\text{now}})\)的关系。图中横轴是优化变量\(\theta\),纵轴是函数值。如图 9.2(a)所示，函数\(L(\theta | \theta_{\text{now}})\)未必在整个定义域上都接近\(J(\theta)\),而只是在\(\theta_{\text{now}}\)的领域里接近\(J(\theta)\)。\(\theta_{\text{now}}\)的邻域就叫做置信域。
通常来说，\(J\)是个很复杂的函数，我们甚至可能不知道\(J\)的解析表达式(比如\(J\)是某个函数的期望)。而我们人为构造出的函数\(L\)相对较为简单，比如\(L\)是\(J\)的蒙特卡洛近似，或者是\(J\)在\(\theta_{\text{now}}\)这个点的二阶泰勒展开。既然可以信任\(L\),那么不妨用\(L\)代替复杂的函数\(J\),然后对\(L\)做最大化。这样比直接优化\(J\)要容易得多。这就是置信域方法的思想。
具体来说，置信域方法做下面这两个步骤，一直重复下去，当无法让\(J\)的值增大的时候终止算法。
第一步——做近似：给定\(\theta_{\text{now}}\),构造函数\(L(\theta | \theta_{\text{now}})\),使得对于所有的\(\theta \in \mathcal{N}(\theta_{\text{now}})\),函数值\(L(\theta | \theta_{\text{now}})\)与\(J(\theta)\)足够接近。图9.2(b) 解释了做近似这一步。
第二步一一最大化：在置信域\(\mathcal{N}(\theta_{\text{now}})\)中寻找变量\(\theta\)的值， 使得函数\(L\)的值最大化。把找到的值记作：
\(\theta_{\text{new}} = \mathrm{argmax}_{\theta \in \mathcal{N}(\theta_{\text{now}})} L(\theta | \theta_{\text{now}})\)
图 9.2( c) 解释了最大化这一步。
置信域方法其实是一类算法框架，而非一个具体的算法。有很多种方式实现实现置信域方法。第一步需要做近似，而做近似的方法有多种多样，比如蒙特卡洛、二阶泰勒展开。第二步需要解一个带约束的最大化问题；求解这个问题又需要单独的数值优化算法，比如梯度投影算法、拉格朗日法。除此之外，置信域\(\mathcal{N}(\theta_{\text{now}})\)也有多种多样的选择， 既可以是球，也可以是两个概率分布的 KL 散度 (KL Divergence)。
ChatGPT对梯度投影算法的介绍
梯度投影算法的基本步骤可以通过数学公式进行介绍。考虑带有约束的优化问题：
\(min_{x} f(x)\)
其中 (f(x)) 是目标函数，(x) 是优化变量，同时满足一组约束条件：
\(g_i(x) \leq 0, \quad i = 1, 2, \ldots, m\)
梯度投影算法的迭代过程如下：
- 初始化： 选择初始解 (\(x_0\))，设置学习率 (\(\alpha\)) 和停止准则。
- 梯度计算： 计算目标函数在当前解 (\(x_k\)) 处的梯度 (\(\nabla f(x_k)\))。
- 梯度投影： 将梯度投影到满足约束条件的空间中。假设投影操作为 (P(x))，则更新方向为 (\(\Delta x_k = P(x_k - \alpha \nabla f(x_k)) - x_k\))。
- 更新变量： 使用投影后的梯度信息来更新变量 (\(x_k\))：
\(x_{k+1} = x_k + \alpha \Delta x_k\)
- 收敛判断： 判断算法是否达到停止条件，例如目标函数的变化足够小或者达到预定的迭代次数。
在这里，梯度投影的关键在于投影操作 (P(x)) 的定义。具体的投影形式取决于约束条件的性质。例如，对于线性约束 (\(g_i(x) \leq 0\))，投影操作可以表示为 (\(P(x) = \max(0,g_i(x))\))。对于更一般的非线性约束，可能需要使用专门的数学工具或算法来进行梯度投影。
需要注意的是，实际应用中可能需要根据具体问题对算法进行调整和定制。
策略学习
首先复习策略学习的基础知识。策略网络记作\(\pi(a | s; \theta)\), 它是个概率质量函数。动作价值函数记作\(Q_{\pi}(s, a)\),它是回报的期望。状态价值函数记作：
\(V_{\pi}(s) = \mathbb{E}_{A \sim \pi(\cdot | s; \theta)}[Q_{\pi}(s, A)] = \sum_{a \in A} \pi(a | s; \theta) \cdot Q_{\pi}(s, a)\)
注意，\(V_{\pi}(s)\)依赖于策略网络\(\pi\), 所以依赖于\(\pi\)的参数\(\theta\)。策略学习的目标函数是：
\(J(\theta) = \mathbb{E}_S[V_{\pi}(S)]\)
\(J(\theta)\)只依赖于\(\theta\),不依赖于状态\(S\)和动作\(A\)。前面介绍的策略梯度方法 (包括 REINFORCE 和 Actor-Critic) 用蒙特卡洛近似梯度\(\nabla_{\theta}J(\theta)\), 得到随机梯度，然后做随机梯度上升更新\(\theta\),使得目标函数\(J(\theta)\)增大。
下面我们要把目标函数\(J(\theta)\)变换成一种等价形式。从等式出发，把状态价值写成：
\(V_{\pi}(s) = \sum_{a \in A} \pi(a | s; \theta_{\text{now}}) \cdot \frac{\pi(a | s; \theta)}{\pi(a | s; \theta_{\text{now}})} \cdot Q_{\pi}(s, a) = \mathbb{E}_{A \sim \pi(\cdot | s; \theta_{\text{now}})}[\frac{\pi(A | s; \theta)}{\pi(A | s; \theta_{\text{now}})} \cdot Q_{\pi}(s, A)]\)
第一个等式很显然，因为连加中的第一项可以消掉第二项的分母。第二个等式把策略网络\(\pi(A | s; \theta_{\text{now}})\)看做动作\(A\)的概率质量函数，所以可以把连加写成期望。由公式 可得定理 9.1。定理 9.1 是 TRPO 的关键所在，甚至可以说 TRPO 就是从这个公式推出的。
定理 9.1. 目标函数的等价形式目标函数\(J(\theta)\)可以等价写成：
\(J(\theta) = \mathbb{E}_S \left[ \mathbb{E}_{A \sim \pi(\cdot | S, \theta_{\text{now}})} \left[ \frac{\pi(A | S; \theta)}{\pi(A | S; \theta_{\text{now}})} \cdot Q_{\pi}(S, A) \right] \right]\)
上面\(Q_{\pi}\)中的\(\pi\)指的是\(\pi(A | S; \theta)\)。
公式中的期望是关于状态\(S\)和动作\(A\)求的。状态\(S\)的概率密度函数只有环境知道， 而我们并不知道，但是我们可以从环境中获取\(S\)的观测值。动作\(A\)的概率质量函数是策略网络\(\pi(A | S; \theta_{\text{now}})\); 注意，策略网络的参数是旧的值\(\theta_{\text{now}}\).
TRPO 数学推导
前面介绍了数值优化的基础和价值学习的基础，终于可以开始推导 TRPO。TRPO 是置信域方法在策略学习中的应用，所以 TRPO 也遵循置信域方法的框架，重复做近似和最大化这两个步骤，直到算法收敛。收敛指的是无法增大目标函数\(J(\theta)\), 即无法增大期望回报。
第一步——做近似：
我们从定理 9.1 出发。定理把目标函数\(J(\theta)\)写成了期望的形式。我们无法直接算出期望，无法得到\(J(\theta)\)的解析表达式；原因在于只有环境知道状态\(S\)的概率密度函数，而我们不知道。我们可以对期望做蒙特卡洛近似，从而把函数\(J\)近似成函数\(L\)。用策略网络\(\pi(A | S; \theta_{\text{now}})\)控制智能体跟环境交互，从头到尾玩完一局游戏观测到一条轨迹：
\(s_1, a_1, r_1, s_2, a_2, r_2, \cdots, s_n, a_n, r_n.\)
其中的状态\(\{s_t\}_{t=1}^n\)都是从环境中观测到的，其中的动作\(\{a_t\}_{t=1}^n\)都是根据策略网络\(\pi(\cdot | s_t; \theta_{\text{now}})\)抽取的样本。所以，
\(\frac{\pi(a_t | s_t; \theta)}{\pi(a_t | s_t; \theta_{\text{now}})} \cdot Q_{\pi}(s_t, a_t)\)
是对定理 9.1 中期望的无偏估计。我们观测到了\(n\)组状态和动作，于是应该对公式求平均，把得到均值记作：
\(L(\theta | \theta_{\text{now}}) = \frac{1}{n} \sum_{t=1}^{n} \frac{\pi(a_t | s_t; \theta)}{\pi(a_t | s_t; \theta_{\text{now}})} \cdot Q_{\pi}(s_t, a_t)\)
既然连加里每一项都是期望的无偏估计，那么\(n\)项的均值\(L\)也是无偏估计。所以可以拿\(L\)作为目标函数\(J\)的蒙特卡洛近似。
公式中的\(L(\theta | \theta_{\text{now}})\)是对目标函数\(J(\theta)\)的近似。可惜我们还无法直接对\(L\)求最大化，原因是我们不知道动作价值\(Q_{\pi}(s_t, a_t)\)。解决方法是做两次近似：
\(Q_{\pi}(s_t, a_t) \Longrightarrow Q_{\pi_{\text{old}}}(s_t, a_t) \Longrightarrow u_t.\)
公式中\(Q_{\pi}\)中的策略是\(\pi(a_t | s_t; \theta)\), 而\(Q_{\pi_{\text{old}}}\)中的策略则是旧策略\(\pi(a_t | s_t; \theta_{\text{now}})\)。我们用旧策略\(\pi(a_t | s_t; \theta_{\text{now}})\)生成轨迹\(\{(s_j, a_j, r_j, s_{j+1})\}_{j=1}^n\)。所以折扣回报
\(u_t = r_t + \gamma \cdot r_{t+1} + \gamma^2 \cdot r_{t+2} + \cdots + \gamma^{n-t} \cdot r_n\)
是对\(Q_{\pi_{\text{old}}}\)的近似，而未必是对\(Q_{\pi}\)的近似。仅当\(\theta\)接近\(\theta_{\text{now}}\)的时候，\(u_t\)才是\(Q_{\pi}\)的有效近似。这就是为什么要强调置信域，即\(\theta\)在\(\theta_{\text{now}}\)的邻域中。
拿\(u_t\)替代\(Q_{\pi}(s_t, a_t)\),那么公式中的\(L(\theta | \theta_{\text{now}})\)变成了
\(\tilde{L}(\theta | \theta_{\text{now}}) = \frac{1}{n} \sum_{t=1}^{n} \frac{\pi(a_t | s_t; \theta)}{\pi(a_t | s_t; \theta_{\text{now}})} \cdot u_t.\)
总结一下，我们把目标函数\(J\)近似成\(L\),然后又把\(L\)近似成\(\tilde{L}\)。在第二步近似中，我们需要假设\(\theta\)接近\(\theta_{\text{now}}\)。
第二步——最大化：
TRPO 把公式 中的\(\tilde{L}(\theta | \theta_{\text{now}})\)作为对目标函数\(J(\theta)\)的近似，然后求解这个带约束的最大化问题：
\(\max_{\theta} \tilde{L}(\theta | \theta_{\text{now}}); \quad \text{s.t.} \quad \theta \in \mathcal{N}(\theta_{\text{now}}).\)
公式中的\(\mathcal{N}(\theta_{\text{now}})\)是置信域，即\(\theta_{\text{now}}\)的一个邻域。该用什么样的置信域呢？
- 一种方法是用以\(\theta_{\text{now}}\)为球心、以\(\Delta\)为半径的球作为置信域。这样的话，公式就变成
\(\max_{\theta} \tilde{L}(\theta | \theta_{\text{now}}); \quad \text{s.t.} \quad \|\theta - \theta_{\text{now}}\|_2 \leq \Delta.\)
- 另一种方法是用 KL 散度衡量两个概率质量函数——\(\pi(\cdot | s_i; \theta_{\text{now}})\)和\(\pi(\cdot | s_i; \theta)\)—— 的距离。两个概率质量函数区别越大，它们的 KL 散度就越大。反之，如果\(\theta\)很接近\(\theta_{\text{now}}\),那么两个概率质量函数就越接近。用 KL 散度的话，公式就变成
\(\max_{\theta} \tilde{L}(\theta | \theta_{\text{now}}); \quad \text{s.t.} \quad \frac{1}{t} \sum_{i=1}^{t} \text{KL}[\pi(\cdot | s_i; \theta_{\text{now}}) \| \pi(\cdot | s_i; \theta)] \leq \Delta.\)
用球作为置信域的好处是置信域是简单的形状，求解最大化问题比较容易，但是用球做置信域的实际效果不如用 KL 散度。
TRPO 的第二步—最大化—需要求解带约束的最大化问题。注意，这种问题的求解并不容易；简单的梯度上升算法并不能解带约束的最大化问题。数值优化教材通常有介绍带约束问题的求解，有兴趣的话自己去阅读数值优化教材，这里就不详细解释如何求解问题。读者可以这样看待优化问题：只要你能把一个优化问题的目标函数和约束条件解析地写出来，通常会有数值算法能解决这个问题。
训练流程
在本节的最后，我们总结一下用 TRPO 训练策略网络的流程。TRPO 需要重复做近似和最大化这两个步骤：
- 做近似——构造函数\(\tilde{L}\)近似目标函数\(J(\theta)\):
- 设当前策略网络参数是\(\theta_{\text{now}}\)。用策略网络\(\pi(a | s; \theta_{\text{now}})\)控制智能体与环境交互，玩完一局游戏，记录下轨迹\(s_1, a_1, r_1, s_2, a_2, r_2, \cdots, s_n, a_n, r_n\).
- 对于所有的\(t = 1, \cdots, n\), 计算折扣回报\(u_t = \sum_{k=t}^n \gamma^{k-t} \cdot r_k\).
- 得出近似函数：\(\tilde{L}(\theta | \theta_{\text{now}}) = \frac{1}{n} \sum_{t=1}^{n} \frac{\pi(a_t | s_t; \theta)}{\pi(a_t | s_t; \theta_{\text{now}})} \cdot u_t.\)
- 最大化——用某种数值算法求解带约束的最大化问题：
\(\theta_{\text{new}} = \arg\max_{\theta} \tilde{L}(\theta | \theta_{\text{now}}) ; \quad \text{s.t.} \quad \|\theta - \theta_{\text{now}}\|_2 \leq \Delta.\)
此处的约束条件是二范数距离。可以把它替换成 KL 散度，即公式 (9.10)。
TRPO 中有两个需要调的超参数：一个是置信域的半径\(\Delta\), 另一个是求解最大化问题的数值算法的学习率。通常来说，\(\Delta\)在算法的运行过程中要逐渐缩小。虽然 TRPO 需要调参，但是 TRPO 对超参数的设置并不敏感。即使超参数设置不够好，TRPO 的表现也不会太差。相比之下，策略梯度算法对超参数更敏感。
TRPO 算法真正实现起来并不容易，主要难点在于第二步一一最大化。不建议读者自己去实现 TRPO。