《nndl》的 RL 极简笔记

我读了邱锡鹏老师写的《nndl》的 RL 相关章节，很通顺，让我复习巩固了一遍知识。我非常喜欢这本书！

我做个极简笔记方便回顾。

马尔可夫决策过程（Markov Decision Process, MDP）

一个标准强化学习问题通常建模为折扣 MDP：

$$(\mathcal{S}, \mathcal{A}, p, r, \gamma)$$

其中：状态空间为 S，动作空间为 A，状态转移概率为：

$$p(s'|s,a)$$

即时奖励：

$$r(s,a,s')$$

折扣率：

$$\gamma \in [0,1]$$

策略（Policy）

$$\pi(a|s) \triangleq p(a|s)$$

且有

$$\sum_{a \in \mathcal{A}} \pi(a|s)=1$$

轨迹（Trajectory）

$$\tau = s_0,a_0,s_1,r_1,a_1,\cdots,s_T,r_T$$

给定策略后，有轨迹概率

$$p(\tau)=p(s_0)\prod_{t=0}^{T-1}\pi(a_t|s_t)p(s_{t+1}|s_t,a_t)$$

回报（Return）

从时刻 t 开始，return 是

$$G_t=\sum_{k=0}^{T-t-1}\gamma^k r_{t+k+1}$$

目标函数（Objective）

强化学习目标是最大化期望回报：

$$\mathcal{J}(\theta) = \mathbb{E}_{\tau \sim p_\theta(\tau)}[G_0] = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[ \sum_{t=0}^{T-1}\gamma^t r_{t+1} \right]$$

状态值函数（State Value Function）

表示在状态 s 出发并遵循策略 π 的期望回报：

$$V^\pi(s)=\mathbb{E}_\pi[G_t|s_t=s]$$

策略 $\pi$ 的期望回报可以写为（初始状态分布）：

$$\mathbb{E}_{\tau \sim p(\tau)}[G_0] = \mathbb{E}_{s \sim p(s_0)}[V^\pi(s)]$$

贝尔曼方程：

$$V^\pi(s) = \mathbb{E}_{a\sim \pi(a|s)} \mathbb{E}_{s'\sim p(s'|s,a)} [ r(s,a,s')+\gamma V^\pi(s') ]$$

贝尔曼方程怎么来的，首先，

$$G_t=R_{t+1}+\gamma G_{t+1}$$

代入到 $V^\pi(s)=\mathbb{E}_\pi[G_t|s_t=s]$ 有

$$V^\pi(s) = \mathbb E_\pi[R_{t+1}+\gamma G_{t+1}\mid S_t=s]$$

在 $S_t=s$ 之后，按策略选动作，$a\sim \pi(a\mid s)$，然后环境转移到下一个状态，$s’\sim p(s’\mid s,a)$，所以期望可以拆成

$$\mathbb E_\pi[\cdots\mid S_t=s] = \mathbb E_{a\sim\pi(a\mid s)} \mathbb E_{s'\sim p(s'\mid s,a)}[\cdots].$$

又，既然当前状态是 $s$，动作是 $a$，下一个状态是 $s’$，那么当前这一步的奖励可以写成

$$\mathbb E_\pi[R_{t+1} \mid S_t=s,A_t=a,S_{t+1}=s'] = r(s,a,s').$$

而从下一个状态 $s’$ 继续执行策略 $\pi$，未来回报的期望 $G_{t+1}$ 就是

$$\mathbb E_\pi[G_{t+1}\mid S_t=s,A_t=a,S_{t+1}=s'] = V^\pi(s')$$

综上，之前的上式就是

$$V^\pi(s) = \mathbb E_{a\sim\pi(a\mid s)} \mathbb E_{s'\sim p(s'\mid s,a)} \left[ r(s,a,s')+\gamma V^\pi(s') \right]$$

状态-动作值函数（State-Action Value Function, Q-Function）

Q 函数表示在状态 s 执行动作 a 后再遵循策略 π 的期望回报：

$$Q^\pi(s,a)=\mathbb{E}_\pi[G_t|s_t=s,a_t=a]$$

状态值函数 $V^\pi(s)$ 是 $Q^\pi(s,a)$ 关于动作 $a$ 的期望，

$$V^\pi(s)=\mathbb{E}_{a\sim \pi(a|s)}[Q^\pi(s,a)]$$

Q 函数的贝尔曼方程是

$$Q^\pi(s,a) = \mathbb{E}_{s'\sim p(s'|s,a)} \left[ r(s,a,s') + \gamma \mathbb{E}_{a'\sim \pi(a'|s')} [Q^\pi(s',a')] \right]$$

深度强化学习

例如，DQN 用 NN 近似 $Q^\pi(s,a)$ 或 $V^\pi(s)$

例如，REINFORCE 用可微的 $\pi_\theta(a\mid s)$ 建模决策分布。

例如，Actor-Critic、PPO 同时学习策略和值函数。

基于值函数的学习方法

最优策略 $\pi^\ast$ 是

$$\forall \pi,\forall s,\quad V^{\pi^\ast}(s) \ge V^\pi(s).$$

难实现，因为策略空间为 $\lvert \mathcal{A}\rvert^{\lvert \mathcal{S}\rvert}$ 很大。可以通过迭代改进策略。先随机初始化一个策略，计算该策略的值函数，$\pi’(s)=\operatorname*{arg\,max}_{a} Q^{\pi}(s,a)$ 来设置新的策略，然后反复迭代直到策略稳定。

关键是如何计算或估计策略 $\pi$ 的值函数。方法：动态规划、蒙特卡罗和时序差分学习。

动态规划略。

蒙特卡罗方法（Monte Carlo Method）用于模型未知的情况，通过完整轨迹采样估计回报。方差大。

$$Q^\pi(s,a) \approx \hat Q^\pi(s,a) \frac{1}{N} \sum_{n=1}^{N}G_t^{(n)}$$

在近似估计出来后，进行策略改进，再采样来估计 $Q$ 函数，重复，直至收敛。

策略过于确定，探索不足。要用 $\epsilon$-贪心法，

$$\pi_\epsilon(s) \begin{cases} \pi(s), & \text{概率 } 1-\epsilon \\ \text{随机选择动作}, & \text{概率 } \epsilon \end{cases}$$

最后引入 2 个名词，

同策略（On-Policy）：采样策略 $\pi^\epsilon(s)$ 和优化策略相同。

异策略（Off-Policy）：采样策略和优化策略不同。

时序差分学习（Temporal-Difference Learning, TD）

蒙特卡罗方法要拿到完整的轨迹。T-D 方法不必等待完整轨迹结束。

T-D 每走几步就用贝尔曼方程评估行动前状态的价值。

蒙特卡洛的 Q 的估计先改为增量计算，

$$\begin{aligned} \hat{Q}^{\pi}_{N}(s,a) &= \frac{1}{N} \sum_{n=1}^{N} G_t^{(n)} \\[4pt] &= \frac{1}{N} \left( G_t^{(N)} + \sum_{n=1}^{N-1} G_t^{(n)} \right) \\[4pt] &= \frac{1}{N} \left( G_t^{(N)} + (N-1)\hat{Q}^{\pi}_{N-1}(s,a) \right) \\[4pt] &= \hat{Q}^{\pi}_{N-1}(s,a) + \frac{1}{N}\left( G_t^{(N)} - \hat{Q}^{\pi}_{N-1}(s,a) \right). \end{aligned}$$

$G_t^{(N)}$ 是第 $n$ 次实验从 $(s,a)$ 出发总回报。

为了高效近似，用贝尔曼方程 $G_t \approx r(s,a,s’)+\gamma \hat Q^\pi(s’,a’)$。然后

把 $1/N$ 换为 $\alpha$ ，得到更新公式：

$$\hat Q^\pi(s,a) \leftarrow \hat Q^\pi(s,a) + \alpha [ r(s,a,s') + \gamma \hat Q^\pi(s',a') - \hat Q^\pi(s,a) ]$$

增量 $\delta := G_t-\hat Q^\pi(s,a)$ 是蒙特卡罗误差。

增量 $\delta := r_{t+1}+\gamma Q^\pi(s_{t+1},a_{t+1})-Q^\pi(s_t,a_t)$ 是 TD error。

这就是 SARSA。SARSA 是同策略 TD 算法。

初始化 Q(s,a)
repeat:
    选择 a = π_ε(s)
    执行动作，得到 r, s'
    选择 a' = π_ε(s')
    Q(s,a) ← Q(s,a) + α[r + γQ(s',a') - Q(s,a)]
    s ← s', a ← a'
until 收敛

Q 学习（Q-Learning）

Q 学习是异策略 TD 算法。

$$Q(s,a) \leftarrow Q(s,a) + \alpha [ r+\gamma \max_{a'}Q(s',a')-Q(s,a) ]$$

深度 Q 网络（Deep Q-Network, DQN）

DQN 用 NN 近似 Q 函数。

$$Q_\phi(\mathbf{s},\mathbf{a}) \approx Q^\pi(s,a)$$

$\phi$ 是 NN 的参数，$\mathbf{s},\mathbf{a}$ 是状态、动作的向量表示。如果动作是离散的 M 个，让 NN 输出 M 维向量即可。

TD 目标：

$$y = r+\gamma \max_{a'}Q_{\hat\phi}(\mathbf{s}',a')$$

损失函数：

$$\mathcal{L}(s,a,r,s'|\phi)= (y-Q_\phi(\mathbf{s},\mathbf{a}))^2$$

DQN 的两个稳定训练技巧：

1. 目标网络（Target Network）：固定一段时间的目标参数。
2. 经验回放（Experience Replay）：从经验池中随机采样，降低样本相关性。

策略梯度

策略梯度优化参数化的策略。

现在 $\pi_\theta(a|s)$ 是关于 $\theta$ 连续可微分的了。

记 $G_0=G_0(\tau)$，

$$\begin{aligned} \frac{\partial \mathcal{J}(\theta)}{\partial \theta} &= \frac{\partial}{\partial \theta} \int p_\theta(\tau) G_0 \, d\tau \\[4pt] &= \int \left( \frac{\partial}{\partial \theta} p_\theta(\tau) \right) G_0 \, d\tau \\[4pt] &= \int p_\theta(\tau) \left( \frac{1}{p_\theta(\tau)} \frac{\partial}{\partial \theta} p_\theta(\tau) \right) G_0 \, d\tau \\[4pt] &= \int p_\theta(\tau) \left( \frac{\partial}{\partial \theta} \log p_\theta(\tau) \right) G_0 \, d\tau \\[4pt] &= \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[ \frac{\partial}{\partial \theta} \log p_\theta(\tau) G_0 \right]. \end{aligned}$$

又有

$$\begin{aligned} \frac{\partial}{\partial \theta}\log p_\theta(\tau) &= \frac{\partial}{\partial \theta} \log\left( p(s_0) \prod_{t=0}^{T-1} \pi_\theta(a_t \mid s_t) p(s_{t+1}\mid s_t,a_t) \right) \\[4pt] &= \frac{\partial}{\partial \theta} \left( \log p(s_0) + \sum_{t=0}^{T-1} \log \pi_\theta(a_t \mid s_t) + \sum_{t=0}^{T-1} \log p(s_{t+1}\mid s_t,a_t) \right) \\[4pt] &= \sum_{t=0}^{T-1} \frac{\partial}{\partial \theta} \log \pi_\theta(a_t \mid s_t). \end{aligned}$$

$\frac{\partial \mathcal{J}(\theta)}{\partial \theta}$ 和状态转移概率无关，只和策略函数相关，

$$\frac{\partial \mathcal{J}(\theta)}{\partial \theta} = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[ \left( \sum_{t=0}^{T-1} \frac{\partial}{\partial \theta} \log \pi_\theta(a_t \mid s_t) \right) G_0 \right].$$

又有总回报

$$G_0 = G_{<t} + \gamma^t G_t$$

令

$$h_t=s_0,a_0,s_1,r_1,a_1,\cdots,a_{t-1},s_t.$$

$G_{<t}$ 只依赖于时刻 $t$ 之前的历史。

$$\begin{aligned} \mathbb{E}_{\tau} \left[ \frac{\partial}{\partial \theta} \log \pi_\theta(a_t \mid s_t) G_{<t} \right] &= \mathbb{E}_{h_t} \left[ G_{<t} \sum_{a_t} \pi_\theta(a_t \mid s_t) \frac{\partial}{\partial \theta} \log \pi_\theta(a_t \mid s_t) \right] \\[4pt] &= \mathbb{E}_{h_t} \left[ G_{<t} \sum_{a_t} \frac{\partial}{\partial \theta} \pi_\theta(a_t \mid s_t) \right] \\[4pt] &= \mathbb{E}_{h_t} \left[ G_{<t} \frac{\partial}{\partial \theta} \sum_{a_t} \pi_\theta(a_t \mid s_t) \right] \\[4pt] &= \mathbb{E}_{h_t} \left[ G_{<t} \frac{\partial}{\partial \theta} 1 \right] = 0. \end{aligned}$$

所以

$$\frac{\partial \mathcal{J}(\theta)}{\partial \theta} = \mathbb{E}_{\tau \sim p_\theta(\tau)} \left[ \sum_{t=0}^{T-1} \left( \frac{\partial}{\partial \theta} \log \pi_\theta(a_t \mid s_t) \gamma^t G_t \right) \right]$$

REINFORCE

REINFORCE 是最基本的蒙特卡罗策略梯度算法。它采样多个完整轨迹。对每个轨迹，对每个 $t$，

$$\theta \leftarrow \theta + \alpha \gamma^t G_t \frac{\partial}{\partial \theta} \log \pi_\theta(a_t|s_t)$$

带基准线的 REINFORCE（REINFORCE with Baseline）

为降低方差，引入与动作无关的基准线。略。

演员-评论员算法（Actor-Critic, AC）

Critic 用 TD 误差评价动作好坏，Actor 根据评价更新策略。

近似回报：

$$\hat G_t = r_{t+1}+\gamma V_\phi(s_{t+1})$$

现在，Actor 学策略，Critic 学值函数。

值函数优化参数 $\phi$：

$$\min_{\phi} \left( \hat{G}_t - V_{\phi}(s_t) \right)^2$$

策略优化参数 $\theta$：

$$\theta \leftarrow \theta + \alpha \gamma^t \left( \hat{G}_t - V_{\phi}(s_t) \right) \frac{\partial}{\partial \theta} \log \pi_{\theta}(a_t \mid s_t).$$

TD 误差：

$$\delta_t = r+\gamma V_\phi(s')-V_\phi(s)$$

信赖域策略优化（Trust Region Policy Optimization, TRPO）

策略更新不能离旧策略太远。

优势函数

$$A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)$$

重要性采样比值：

$$r_t(\theta) = \frac{\pi_\theta(a_t|s_t)} {\pi_{\theta_{\text{old}}}(a_t|s_t)}$$

TRPO 目标：

$$\max_\theta \mathbb{E}_{s_t,a_t\sim \pi_{\theta_{\text{old}}}} [ r_t(\theta)A_t ]$$ $$\text{s.t.} \quad \mathbb{E}_{s_t\sim \pi_{\theta_{\text{old}}}} [ KL(\pi_{\theta_{\text{old}}}(\cdot|s_t)\Vert \pi_\theta(\cdot|s_t)) ] \leq \delta$$

近端策略优化（Proximal Policy Optimization, PPO）

PPO 保留 TRPO 的限制更新幅度。用更简单的一阶优化目标实现。

带 KL 惩罚的 PPO，是 PPO-Penalty：

$$\max_\theta \mathbb{E}_{s_t, a_t \sim \pi_{\theta_\text{old}}} [ r_t(\theta)A_t ] -\beta KL(\pi_{\theta_{\text{old}}}\Vert \pi_\theta)$$

更常用的是，裁剪目标 PPO-Clip。RLHF 中 PPO-Clip 同时在 reward 中加入相对于 reference model 的 KL 惩罚。

$$\mathcal{L}^{clip}(\theta) = \mathbb{E}_{s_t, a_t \sim \pi_{\theta_\text{old}}} \left[ \min \left( r_t(\theta)A_t, \text{clip}(r_t(\theta),1-\epsilon,1+\epsilon)A_t \right) \right]$$

其中，ratio 定义：

$$r_t(\theta) = \frac{ \pi_\theta(a_t|s_t) }{ \pi_{\theta_{\text{old}}}(a_t|s_t) }$$

当优势为正时，PPO 限制动作概率不要增大太多；当优势为负时，限制动作概率不要减小太多。

以上为策略损失。价值函数的损失：

$$\mathcal{L}^{VF}(\phi) = \mathbb{E}_t \left[ \left( V_\phi(s_t) - \hat{R}_t \right)^2 \right]$$

是均方误差。

策略熵奖励如下，表示策略的随机性：

$$\mathcal{H} \left( \pi_\theta(\cdot|s_t) \right) = - \sum_a \pi_\theta(a|s_t) \log \pi_\theta(a|s_t)$$

综上，PPO 总损失：

$$\mathcal{L}^{PPO}(\theta, \phi) = \mathcal{L}^{policy} + c_1 \mathcal{L}^{VF} - c_2 \mathcal{H} \\ = \mathbb{E}_t \left[ - \min \left( r_t(\theta) A_t, \operatorname{clip} \left( r_t(\theta), 1-\epsilon, 1+\epsilon \right) A_t \right) + c_1 \left( V_\phi(s_t) - \hat{R}_t \right)^2 - c_2 \mathcal{H} \left( \pi_\theta(\cdot|s_t) \right) \right]$$

价值函数是帮忙计算 advantage 的，比方说可以是

$$A_t = \hat{R}_t - V(s_t)$$

或者用 GAE：

$$A_t^\text{GAE}= \sum_{l=0}^{\infty} (\gamma \lambda)^l \delta_{t+l}$$

其中：

$$\delta_{t+l}=r_t + \gamma V(s_{t+1}) - V(s_t)$$

常用 GAE 估计 advantage。

$R_t$ 是 reward + KL 惩罚或某种加权组合，reward 是训练的奖励模型得到的。比方说，

$$R_t= r_{\text{RM}} - \beta KL(\pi_\theta \Vert \pi_{\text{ref}})$$

广义优势估计（Generalized Advantage Estimation, GAE）

TRPO、PPO 都需要估计优势函数

$$A_{\mathrm{old}}^{\pi_\theta}(s_t,a_t).$$

GAE 用多步 TD 误差平衡偏差和方差。

一步 TD 误差：

$$\delta_t = r_{t+1} + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)$$

把未来若干步的时序差分也累积进来，用衰减系数 $\lambda$ 做指数加权，得 GAE：

$$\hat A_t^{GAE(\gamma,\lambda)} = \sum_{l=0}^{T-t-1} (\gamma\lambda)^l \delta_{t+l}$$

λ 越小，方差越小但偏差越大；λ 越大，更接近真实优势但方差更大。

$\lambda$ 怎么来的？几何级数求和公式：

$$1+\lambda+\lambda^2+\lambda^3+\cdots=\frac{1}{1-\lambda},\quad |\lambda|<1$$

而展开 GAE 的 A，有：

$$A_t^{GAE} = (1-\lambda) \left( A_t^{(1)} + \lambda A_t^{(2)} + \lambda^2 A_t^{(3)} + \lambda^3 A_t^{(4)} + \cdots \right) \\ A_t^{GAE} = (1-\lambda) \left[ \delta_t + \lambda(\delta_t+\gamma\delta_{t+1}) + \lambda^2(\delta_t+\gamma\delta_{t+1}+\gamma^2\delta_{t+2}) + \cdots \right]$$

整理对比

A 怎么算，

方法	公式	简介
真实 Advantage	$A^\pi(s_t,a_t)=Q^\pi(s_t,a_t)-V^\pi(s_t)$	理论定义。表示动作 $a_t$ 相比当前状态平均水平 $V^\pi(s_t)$ 好多少。实际中 $Q^\pi$ 通常不知道。
Monte Carlo Advantage	$\hat A_t=G_t-V(s_t)$ $G_t=\sum_{k=0}^{T-t}\gamma^k r_{t+k}$	用完整轨迹的真实回报 $G_t$ 减去价值函数。偏差小，但方差大。
One-step TD Advantage	$\hat A_t=r_t+\gamma V(s_{t+1})-V(s_t)$	也叫 TD error：$\delta_t$。只看一步奖励和下一状态价值，方差小，但偏差较大。
n-step Advantage	$\hat A_t^{(n)}=\sum_{k=0}^{n-1}\gamma^k r_{t+k}+\gamma^n V(s_{t+n})-V(s_t)$	介于 one-step TD 和 Monte Carlo 之间。看未来 $n$ 步，再用 $V(s_{t+n})$ bootstrap。
GAE Advantage	$\hat A_t^{GAE(\gamma,\lambda)}=\sum_{l=0}^{T-t-1}(\gamma\lambda)^l\delta_{t+l}$ $\delta_t=r_t+\gamma V(s_{t+1})-V(s_t)$	Generalized Advantage Estimation。广义优势估计把多个未来 TD error 加权求和，是 PPO/TRPO 里最常用的 advantage 估计。
$\lambda$-return Advantage	$\hat A_t^{\lambda}=R_t^\lambda - V(s_t)$	和 GAE 等价的一种写法。先构造 $\lambda$-return，再减去 $V(s_t)$。

另有 GAE 的递推式：

GAE 的递推式是：

$$\hat A_t= \delta_t + \gamma\lambda \hat A_{t+1}$$

Reference

《nndl》