深度强化学习相关总结

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

资源推荐

相关定义与定理

术语

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

  • 强化学习 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: 证明：蒙特卡洛

定义

对于$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

核心公式为

其中

动作函数$\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

核心公式为

其中

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

DQN

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

对于网络$Q_\pi(s_t, a_t; \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)$，所以需要做梯度上升：

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

根据定义，可以推导出

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

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

为便于后续推导，定义

则有

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

REINFORCE

损失函数为：

参考：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)$的无偏估计

故有

REINFORCE with Baseline

损失函数为：

其中：

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

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

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

证明如下：

证毕。

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

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

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

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

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

Advantage Actor-Critic(A2C)

损失函数为：

其中：

使用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

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

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

训练伪代码如下：

损失函数为：

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

以及超参数$\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$，满足如下规则：

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

理论推导如下：

咕。