数学推导、伪代码及 pytorch 实现（更新中）

# 资源推荐

• 王树森的深度强化学习课程
• 强化学习经典算法实验之 REINFORCE
• 小崔讲强化

# 相关定义与定理

# 术语

按照个人理解陈述，有误请斧正

• 强化学习 Reinforcement learning: 与监督学习、非监督学习并列，是智能体 (Agent) 以 “试错” 的方式进行学习，通过与环境 (Environment) 进行交互获得的奖赏 (Reward) 指导行为，以使智能体获得最大奖赏的学习方式。
• 环境 Environment: 向智能体提供状态 (State) 及奖励 (Reward)，并根据智能体的动作 (Action) 改变自身状态的对象。内含智能体无法准确获知的状态转移函数。
• 智能体 Agent: 与环境交互的对象，训练的主体。
• 状态 State: 环境提供的，智能体观测到的数据。可以是一幅图像、或者几个关键传感器获取的数值列表，如位置、速度等。智能体通过观测状态给出动作，环境通过当前状态及智能体的动作提供下一个状态。分为离散及连续两种类型，且根据状态的类型不同需要使用不同的智能体训练算法。
• 策略 Policy: 智能体内部的，状态到动作的概率映射函数。智能体观测到状态后，通过策略执行动作。
• 动作 Action: 智能体提供的，与环境交互的数据。分为连续和离散两类。若使用神经网络训练智能体，则两类动作所需的网络有所不同。
• 奖励、回报 Reward: 环境根据当前状态及智能体提供的动作，给智能体提供的数据，通常为标量。智能体学习主要参考值。
• 总奖励、总回报 Return: 标志当前状态下执行当前动作所能获得奖励的期望，与策略及状态转移函数均有关。通常训练智能体时需要使用蒙特卡罗方法估计此数据。
• 回合 episode: 一个回合从环境产生初始状态$s_0$ 开始，智能体根据$s_t$ 做出动作$a_t$，环境再根据动作产生奖励$r_t$ 与下一步的状态$s_{t+1}$，智能体再根据新的状态做出动作$a_{t+1}$，直到环境产生结束信号标志回合结束。
• 轨迹 trajectory: 一个回合内的所有$\left\{s_t, a_t, r_t\mid t \in [0, T]\right\}$ 三元组构成一个轨迹。
• On-Policy 与 Off-Policy: On-Policy 指与环境交互时使用的策略与内部训练的策略相同的训练方式，Off-Policy 指二者不同的训练方式。On-Policy 通常实现及理解更简单，但无法同时兼顾探索新策略与利用原有策略，会导致训练落入局部最优陷阱。而 Off-Policy 的实现可在保持探索的同时，更有可能求得全局最优值。

# 符号及函数

• $s_t$: t 时刻环境所产生的状态。
• $a_t$: t 时刻智能体根据环境状态$s_t$ 执行的动作。
• $r_t$: t 时刻环境根据智能体执行的动作$a_t$ 反馈的奖励。
• $u_t=\sum_{\tau=t}^{T}{\gamma^{\tau-t} r_\tau}$: 折扣回报，智能体从 t 时刻开始到回合结束可以获得的奖励总和。
• $\gamma$: 折扣回报率，用于减弱后续奖励对更新当前动作的影响。
• $\pi(a_t\mid s_t)$: 策略函数，表示 t 时刻智能体观测到$s_t$ 时执行动作$a_t$ 的概率。
• $p(s_{t+1}\mid s_t, a_t)$: 转移概率函数，表示当前状态为$s_t$，执行动作$a_t$ 时，下一个状态为$s_{t+1}$ 的概率。
• $\rho_0(s_0)$: 初始状态概率函数，表示初始状态为$s_0$ 的概率。
• $Q_\pi(s_t, a_t)=\mathbb E_{s_t, a_t}\left[ u_t \right]$: 策略价值函数，表示当前策略下，在 t 时刻观测到状态$s_t$ 并执行动作$a_t$ 所能获取的折扣回报的期望，用于评判状态$q_t$ 下动作$a_t$ 的好坏。
• $Q^\star(s_t, a_t) = \operatorname{argmax}_\pi \left[Q_\pi(s_t, a_t) \right]$: 最优策略价值函数，表示在最优的策略下，在 t 时刻观测到状态$s_t$ 并执行动作$a_t$ 所能获取的折扣回报的期望，用于消除策略影响后，评判状态$q_t$ 下动作$a_t$ 的好坏。
• $V_\pi(s_t)=\mathbb E_{a_t \sim \pi}\left[Q_\pi(s_t, a_t)\right]$: 状态价值函数，用于评判当前策略下状态$s_t$ 的好坏。
• $V^\star(s_t)=\operatorname{argmax}_\pi \left[ V_\pi(s_t) \right]$: 最优策略状态价值函数，用于评判最优策略下状态$s_t$ 的好坏。
• $A_\pi(s_t, a_t)=Q_\pi(s_t, a_t)-V_\pi(s_t)$: 优势函数，衡量当前策略下动作$a_t$ 相对于其他动作的优劣
• $A^\star(s_t, a_t)=Q^\star(s_t, a_t)-V^\star(s_t)$: 最优策略优势函数

上述符号中，$s_t, r_t$ 均是环境提供，$p(s_{t+1}\mid s_t, a_t)$ 为环境内部参数，智能体无法获取其信息。

强化学习根据学习函数为$Q_\pi(s_t, a_t)$ 或者$\pi(a_t\mid s_t)$ 可分为基于价值的学习与基于策略的学习两类。

# 相关定理

# 时序差分 (Temporal-Difference)

// TODO: 证明：蒙特卡洛

定义

$$\operatorname{TD}(n) = \gamma^n Q(s_{t+n},a_{t+n}; \boldsymbol \omega) + \sum_{i=t}^{t+n-1}\gamma^{i-t}r_i$$

对于$u_t$ 的估计，$\operatorname{TD}(1) = r_t + \gamma Q(s_{t+1}, a_{t+1}; \boldsymbol \omega)$ 比$Q(s_t, a_t; \boldsymbol \omega)$ 更好；当$n>m$ 时，$\operatorname{TD}(n)$ 比$\operatorname{TD}(m)$ 更好。

但单步 TD target 实现最为简单，故实际应用中需要取舍。

# 基于价值的学习 (Value-based learning)

# 学习算法

# Sarsa

核心公式为

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \cdot \hat \delta_t$$

其中

$$\begin{aligned} \hat u_t(TD \ target) & = r_t+\gamma Q(s_{t+1}, a_{t+1}) \\ \hat \delta_t(TD \ error) & = \hat u_t - Q(s_t, a_t) \end{aligned}$$

动作函数$\pi(a_t \mid s_t) = \operatorname{argmax}_{a_t}(Q(s_t,a_t))$

On-Policy 算法，使用离散的数组储存 Q 值，并用 TD 估测 Return。

适用于离散状态、离散动作模型的价值学习。单步采集的数据有$\{s_t, a_t, r_t, s_{t+1}, a_{t+1}\}$，这也是其名称的由来。

# Q-learning

核心公式为

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \cdot \hat \delta_t$$

其中

$$\begin{aligned} \hat u_t(TD \ target) & = r_t+\gamma \max_a Q(s_{t+1}, a) \\ \hat \delta_t(TD \ error) & = \hat u_t - Q(s_t, a_t) \end{aligned}$$

Off-Policy 算法，SARSA 的变体。单步采集的数据有$\{s_t, a_t, r_t, s_{t+1}\}$。

# DQN

使用神经网络替代$Q$ 函数的 Q-learning 算法。

对于网络$Q_\pi(s_t, a_t; \boldsymbol \omega)$，损失函数为

$$L^{DQN}(\boldsymbol \omega)=\hat \delta_t$$

其中

$$\begin{aligned} \hat u_t(TD \ target) & = r_t+\gamma \max_a Q(s_{t+1}, a) \\ \hat \delta_t(TD \ error) & = \hat u_t - Q(s_t, a_t) \end{aligned}$$

该网络及下文所述所有网络，更新方式均为：

$$\boldsymbol \omega \leftarrow \boldsymbol \omega - \alpha \cdot \frac{\partial L(\boldsymbol \omega)}{\partial \boldsymbol \omega}$$

DQN 使用神经网络$Q_\pi(s_t, a_t; \boldsymbol \omega)$ 拟合函数$Q_\pi(s_t, a_t)$，解决了连续状态下强化学习的问题。

# 基于策略的学习 (Policy-based learning)

# 基础理论推导

基于策略的学习中，需要训练的函数为$\pi(a_t\mid s_t;\boldsymbol \theta)$。其结构与 DQN 类似，但输出需要增加一层 softmax，保证各个策略的概率和为 1。

Softmax 函数的定义：$Softmax(\boldsymbol{x_i})=e^{\boldsymbol{x_i}} \div \sum_j{e^{\boldsymbol{x_j}}}$

为了使策略在调整时变好，需要使$V_\pi(s_t)$ 接近$V^\star(s_t)$，所以需要做梯度上升：

$$\boldsymbol \theta \leftarrow \boldsymbol \theta + \alpha \frac{\partial V\pi}{\partial \boldsymbol \theta}$$

关于梯度上升的正确性，可以有个直观理解：根据$V^\star(s_t)$ 的定义，使用随机初始化的策略函数$\pi$ 得到的$V_\pi(s_t)$ 一定小于等于$V^\star(s_t)$，仅需其不断上升即可不断逼近$V^\star(s_t)$

根据定义，可以推导出

$$V_\pi(s_t)=\mathbb E_{a_t \sim \pi}\left[Q_\pi(s_t, a_t)\right] = \left \{ \begin{aligned} \sum_{a} & { \pi(a\mid s_t;\boldsymbol \theta) Q_\pi(s_t, a)}, & & (a\text{离散}) \\ \int_a & \pi(a\mid s_t;\boldsymbol \theta) Q_\pi(s_t, a) \, da, & & (a\text{连续}) \end{aligned} \right .$$

假设$Q_\pi$ 不依赖于$\boldsymbol \theta$，则$a$ 连续时，有

$$\begin{aligned} \frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta} & = \int_a \frac{\pi(a\mid s_t;\boldsymbol \theta)}{\pi(a\mid s_t;\boldsymbol \theta)} \frac{\partial \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} Q_\pi(s_t, a) \, da\\ & = \int_a \pi(a\mid s_t;\boldsymbol \theta) \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} Q_\pi(s_t, a) \, da\\ & = \mathbb E_{a \sim \pi}\left [ \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} Q_\pi(s_t, a) \right ] \end{aligned}$$

离散时结论相同。故做梯度上升时，仅需求出此期望即可。

为便于后续推导，定义

$$g(a)=\frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} Q_\pi(s_t, a)$$

则有

$$\frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta}=\mathbb E_{a \sim \pi}\left [ g(a) \right]$$

以下按时间顺序介绍几个经典的 PG 算法。

# REINFORCE

损失函数为：

$$\pi(a_t\mid s_t;\boldsymbol \theta): \ L(\boldsymbol \theta)= - V_\pi(s_t) =-u_t \cdot \ln \pi(a_t\mid s_t;\boldsymbol \theta)$$

参考：https://paperexplained.cn/aplayground/iarticle/detail/0454c3b5-be1a-4aff-a146-9c5adaf76600/

朴素的策略学习算法。

使用蒙特卡罗方法，有

• 由 t 时刻获取的$s_t$, $a_t$ 算得的$g(a_t)$ 是$\frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta}$ 的无偏估计
• 由一个回合求得轨迹计算而得的$u_t$ 是$Q_\pi(s_t, a_t)$ 的无偏估计

故有

$$\begin{aligned} \frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta}&= \mathbb E_{a \sim \pi}\left [ g(a) \right] \\ & \approx \frac{\partial \ln \pi(a_t\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} Q_\pi(s_t, a_t) \\ & \approx \frac{\partial \ln \pi(a_t\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} u_t \end{aligned}$$

# REINFORCE with Baseline

损失函数为：

$$\begin{aligned} \pi(a_t\mid s_t; \boldsymbol \theta):& &L(\boldsymbol \theta) & = -\hat A_t(s_t, a_t) \\ V^\star(s_t; \boldsymbol \omega):& &L(\boldsymbol \omega) & = \frac{1}{2} \delta_t ^ 2 \end{aligned}$$

其中：

$$\delta_t = V^\star(s_t; \boldsymbol \omega) - u_t = -\hat A_t(s_t, a_t)$$

注： 策略网络更新时使用的是梯度下降，但与 without baseline 的方法比较可见含$u_t$ 的一项仍为正号

式中的$\hat A_t(s_t, a_t)$ 表示在 t 时刻的优势函数$A_t(s_t, a_t)$ 的无偏估计量。

首先证明引理：对于与$\pi$ 无关的任意变量$b$，均有

$$\mathbb E_{a \sim \pi}\left [ b\cdot \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} \right ] = 0$$

证明如下：

$$\begin{aligned} \mathbb E_{a \sim \pi}\left [ b\cdot \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} \right ]&= \int_a b\cdot \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} \cdot \pi(a\mid s_t;\boldsymbol \theta) \, da \\ & = \int_a b \cdot \frac{\partial \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} \, da \\ & = b \cdot \frac{\partial}{\partial \boldsymbol \theta}\int_a \pi(a\mid s_t;\boldsymbol \theta) \, da \\ & = b \cdot \frac{\partial}{\partial \boldsymbol \theta}1 \\ & = b \cdot 0 \\ & = 0 \\ \end{aligned}$$

证毕。

故可以在求解$\frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta}$ 时，人为添加一项$b$，使其变为如下形式而不影响其正确性：

$$\begin{aligned} \frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta} &= \mathbb E_{a \sim \pi}\left [ \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} Q_\pi(s_t, a) \right ] \\ &= \mathbb E_{a \sim \pi}\left [ \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} [Q_\pi(s_t, a) - b] \right ] \end{aligned}$$

在选取合适的$b$ 时，不但不会影响其正确性，还可以有效减小蒙特卡罗方法引入的方差，降低训练时的波动（TODO: 证明）

$b$ 的选取有多种方式，一种比较好的选取方式为，使用神经网络拟合优势函数：$b=V^\star(s_t; \boldsymbol \omega)$，并使用训练 DQN 的方法训练此网络。本节核心公式中即使用了此方法。带入上式，则有：

$$\frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta} = \mathbb E_{a \sim \pi}\left [ \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} [Q_\pi(s_t, a) - V^\star(s_t; \boldsymbol \omega)] \right ]$$

由于梯度上升最终结果为 $V_\pi=V^\star $, $Q_\pi=Q^\star $ ，故部分论文中未严格区分最优策略函数与当前策略下的函数，统一用$V$ 和$Q$ 分别代替两者，故上式改写为

$$\frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta} = \mathbb E_{a \sim \pi}\left [ \frac{\partial \ln \pi(a\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} [A_\pi(s_t, a)] \right ]$$

带入 REINFORCE 一节的推导，则有：

$$\begin{aligned} \frac{\partial V_\pi(s_t)}{\partial \boldsymbol \theta} & \approx \frac{\partial \ln \pi(a_t\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} [Q_\pi(s_t, a_t) - V_\pi(s_t)] \\ & \approx \frac{\partial \ln \pi(a_t\mid s_t;\boldsymbol \theta)}{\partial \boldsymbol \theta} [u_t - V_\pi(s_t)] \end{aligned}$$

# Advantage Actor-Critic(A2C)

损失函数为：

$$\begin{aligned} \pi(a_t\mid s_t; \boldsymbol \theta):& & L^{A2C}(\boldsymbol \theta) & = - \hat A_t(s_t, a_t)\\ V^\star(s_t; \boldsymbol \omega):& & L^{A2C}(\boldsymbol \omega) & = \delta_t \cdot V^\star(s_t; \boldsymbol \omega) \end{aligned}$$

其中：

$$\begin{aligned} \delta_t = - \hat A_t(s_t, a_t) & = \left \{ \begin{aligned} V^\star(s_t; \boldsymbol \omega) - (r_t + \gamma \cdot V^\star(s_{t+1}; \boldsymbol \omega)), & & (\operatorname{TD}(1)) \\ V^\star(s_t; \boldsymbol \omega) - \left[ \left( \sum_{i=t}^{t+n-1}\gamma^{i-t} r_i \right) + \gamma^n \cdot V^\star(s_{t+n}; \boldsymbol \omega)\right], & & (\operatorname{TD}(n)) \end {aligned} \right. \\ & = V^\star(s_t; \boldsymbol \omega) - R - \gamma_{discount}*V^\star(s_{next};\boldsymbol \omega) \end {aligned}$$

使用 TD target 代替上一节公式中的$u_t$ 即为 A2C：

# 优化方法

# 训练时优化方法

通过在训练时增设环节以达到比简单训练方式收敛速度更快、或实现更容易的优化方法。大部分方法都可混合使用。

# 经验回放 Replay buffer

Off-Policy 使用的优化方式。由于 Off-Policy 的数据生成与训练使用的不同的 agent,

咕

# Target network

缓解 DQN 的高估问题

咕

# Multi-step TD target

在使用 TD target 的算法中，将$TD(1)$ 更换为$TD(n)$，以更多地使用与环境交互获得的奖励，降低更新时网络本身的权重。由此可使算法更快地收敛。

# Double DQN

另一种方式缓解高估问题。

咕

# Target network

进一步缓解高估问题。

咕

# TRPO

参考：arXiv:1502.05477

Off-Policy。

使用 Target network 改进 REINFORCE。

原理较为复杂，并且 lr 难以选取。

下一节的 PPO 是其简化版本。

# PPO

参考：arXiv:1707.06347

使用不同的网络进行数据生成和训练，并定时将训练网络的参数同步至数据生成网络。

文章中提出了两种损失函数的设计方式，均已列在下方。

训练伪代码如下：

损失函数为：

$$\begin{aligned} & & L_t^{CLIP}(\boldsymbol \theta)&=\mathbb E_{a\sim\pi}\left[ \min\left( r_t(\boldsymbol\theta)\hat A_t, \operatorname{clip}\left(r_t(\boldsymbol\theta), 1-\epsilon, 1+\epsilon\right)\hat A_t\right ) \right] \\ or & & L^{KLPEN}(\boldsymbol \theta)&=\mathbb E_{a\sim \pi}\left[ r_t(\boldsymbol \theta)\hat A_t-\beta\operatorname{KL}[\pi_{\theta_{old}}(\cdot \mid s_t), \pi_\theta(\cdot \mid s_t)] \right] \end{aligned}$$

式中有概率比函数$r_t(\boldsymbol \theta)$、裁剪函数$\operatorname{clip}(x,B,C)$ 以及 KL 散度$KL(p(x), q(x))$：

$$\begin{aligned} r_t(\boldsymbol \theta)&=\frac{\pi_{\theta_{old}}(a_t \mid s_t)}{\pi_\theta(a_t \mid s_t)}, \\ \operatorname{clip}(x,B,C) \ (B<C) &=\left \{ \begin{aligned} B, & & x < B \\ x, & & B < x < C \\ C, & & x > C \end {aligned} \right. \\ KL(p(x), q(x)) & = \left \{ \begin{aligned} \int_x p(x)\ln{\frac{p(x)}{q(x)}}\, dx & & \text{for continuous x} \\ \sum_x p(x)\ln{\frac{p(x)}{q(x)}} & & \text{for discrete x} \\ \end{aligned} \right . \end{aligned}$$

以及超参数$\epsilon$、$\beta$。

若使用$L^{KLPEN}(\boldsymbol \theta)$ 作为参数，则需引入额外超参数$d_{targ}$，并在进行梯度下降时按如下规则更新$\beta$:

• 计算 $d=\mathbb E_{a\sim \pi}\left[\operatorname{KL}[\pi_{\theta_{old}}(\cdot \mid s_t), \pi_\theta(\cdot \mid s_t)]\right]$
• 做如下判断：
  • 如果$d < d_{targ} / 1.5$, $\beta \leftarrow \beta / 2$
  • 如果$d > d_{targ} \times 1.5$, $\beta \leftarrow \beta \times 2$

根据原文所述，1.5 和 2 是启发性地选取的，但算法对它们并不敏感。$\beta$ 的初始值虽然也需要设置，但其并不重要，因为在更新时$\beta$ 的值会迅速调整。

# 结构优化方法

# Dueling Network

适用于 DQN 的强化学习。

为方便叙述，定义动作总数为$n$。

使用优势函数，将 DQN 的输出层的$n$ 维向量$Y$ 调整为$n+1$ 维（新增一个代表$V(s_t)$ 的数据），并额外增设一层$Y \rightarrow X$，满足如下规则：

$$\begin{aligned} X = Y[n-1] + Y[0:n-1] - \operatorname{mean}(Y[0:n-1]) & & or \\ X = Y[n-1] + Y[0:n-1] - \operatorname{max}(Y[0:n-1]) \end{aligned}$$

虽然按照理论推导，使用$\max$ 函数才具有实际意义，但实践中使用$\operatorname{mean}$ 得到的效果更好。

理论推导如下：

咕。