Dense reinforcement learning for safety validation of autonomous vehicles

Shuo Feng, Henry X. Liu*, et. al. 22 March 2023 Nature Vol 615

---

Motivation

• 基于RL的自动驾驶测试方法存在以下困难：
  • 奖励非常稀疏，绝大部分经验都没什么用处
  • 测试环境不是无偏的，只能产生碰撞场景，无法回答：
    • 碰撞场景在现实中发生的可能性有多大
    • 测试环境的测试里程能否代替真实世界的测试里程
• 真实世界对AV进行测试需要大量测试里程，在现实中几乎不可能满足 进一步讲，这是一种罕见奖励的强化学习问题，并且不能用传统的稀疏奖励解决方案（那样就有点类似先开枪再画靶）。它的特点是：==只有极少的状态转移才是有意义的，而大量无意义的状态转移，其实际的价值函数可能几乎等于0。==因为这些无用经验的存在，会导致策略梯度的方差非常之大，使得学习过程很容易被误导。密集强化学习就是在保持无偏性的前提下，尽量减小策略梯度的方差。

Method：密集强化学习D2RL

原理

1. 无偏性

无偏性保证了使用该环境测试得到的结果与在真实世界中进行测试的结果相当。D2RL采用重要性采样来保证这一点。

Review: 重要性采样

为了在分布$P$上估计随机变量$X:\mathrm{\Omega }\to \mathbb{R}$的期望，我们可以采用蒙特卡洛方法：

$${\hat{\mathbf{E}}}_n[X;P]=\frac{1}{n}\sum _{i=1}^n{x}_i$$

该估计的精确度取决于$X$的方差：

$$\mathbf{Var}[{\hat{\mathbf{E}}}_n;P]=\frac{1}{n}\mathbf{Var}[X;P]$$

如果采用另一个随机变量$Y:\mathrm{\Omega }\to \mathbb{R},Y\ge 0$，并保证$\mathbf{E}[Y;P]=1$，且几乎处处^[1]有$Y\ne 0$，那么就可以找到一个分布$Q$满足$\mathbf{E}[X;P]=\mathbf{E}[\frac{X}{Y};Q]$，并在$Q$上对$Y$进行采样：

$$\mathbf{E}[X;P]=\mathbf{E}[\frac{X}{Y};Q]\approx \frac{1}{n}\sum _{i=1}^n\frac{X({\omega }_i)}{Y({\omega }_i)},{\omega }_i\sim Q$$

那么这个估计的方差为：

$$\frac{1}{n}\mathbf{Var}[\frac{X}{Y};Q]$$

我们可以取$Y(\omega )=\frac{q(\omega )}{p(\omega )}$，它的倒数

$$W(\omega )=1/Y(\omega )=\frac{p(\omega )}{q(\omega )}$$

就是重要性权重。

Ref: https://artowen.su.domains/mc/

记AV在自然驾驶环境（NDE）中发生碰撞为事件$A$，其发生的概率为$P(A)$，则使用蒙特卡洛对其进行估计：

$$P(A)={\mathbb{E}}_{\mathbf{x}\sim P(\mathbf{x})}[P(A|\mathbf{x})]\approx \frac{1}{n}\sum _{i=1}^{n}P(A|{\mathbf{x}}_i),{\mathbf{x}}_i\sim P(\mathbf{x})$$

使用重要性采样：

$$P(A)={\mathbb{E}}_{\mathbf{x}\sim q(\mathbf{x})}[P(A|\mathbf{x})W_q(\mathbf{x})]\approx \frac{1}{n}\sum _{i=1}^{n}P(A|{\mathbf{x}}_i)W_q({\mathbf{x}}_i),{\mathbf{x}}_i\sim q(\mathbf{x})$$

这里

$$\begin{array}{}\text{(1)}& W_q(\mathbf{x})=\frac{P(\mathbf{x})}{q(\mathbf{x})}\end{array}$$

为了提高重要性采样的效率，应该最小化方差

$$\begin{array}{rl}{\sigma }_q^2=& {\mathbb{E}}_q[(P(A|\mathbf{x})W_q(\mathbf{x}){)}^2]-{\mathbb{E}}_q^2[P(A|\mathbf{x})W_q(\mathbf{x})]\\ =& {\mathbb{E}}_q[P^2(A|\mathbf{x})\cdot W_q^2(\mathbf{x})]-P^2(A)\end{array}$$

于是我们有目标函数：

$$\begin{array}{}\text{(2)}& \underset{q}{min}{\sigma }_q^2=\underset{\pi }{max}\{-{\mathbb{E}}_{q_{\pi }}[P^2(A|\mathbf{x})\cdot W_{q_{\pi }}^2(\mathbf{x})]\}\end{array}$$

使用式（1）和条件概率公式，可以将（2）变为

$$\begin{array}{}\text{(3)}& \begin{array}{rl}& \underset{\pi }{max}\{-{\mathbb{E}}_{q_{\pi }}[P^2(A|\mathbf{x})\cdot W_{q_{\pi }}^2(\mathbf{x})]\}\\ \\ =& \underset{\pi }{max}\{-{\mathbb{E}}_{q_{\pi }}\left[\frac{P^2(A,\mathbf{x})}{q_{\pi }^2(\mathbf{x})}\right]\}\\ =& \underset{\pi }{max}\{-{\mathbb{E}}_{q_{\pi }}[{\mathbb{I}}_A(\mathbf{x})W_{q_{\pi }}^2(\mathbf{x})]\}\end{array}\end{array}$$

注

$$P(A,\mathbf{x})={\mathbb{I}}_A(\mathbf{x})P(\mathbf{x})$$

这就是同轨策略下的目标函数。由于[[#3. 离轨学习机制]]中所述原因，采用了离轨策略，因此需要对式（3）进一步变换。离轨策略下，优化的目标是针对目标策略$\pi$，但负责采样的是表观策略${\pi }_b$，也就是说我们只能对${\pi }_b$求期望。再次利用重要性采样，将式（3）中对$q_{\pi }$的期望转化为对$q_{{\pi }_b}$的期望：

$$\begin{array}{}\text{(4)}& \underset{\pi }{max}\{-{\mathbb{E}}_{q_{{\pi }_b}}[{\mathbb{I}}_A(\mathbf{x})W_{q_{\pi }}(\mathbf{x})W_{q_{{\pi }_b}}(\mathbf{x})]\}\end{array}$$

于是有奖励函数：

$$\begin{array}{}\text{(5)}& r(\mathbf{x})=-{\mathbb{I}}_A(\mathbf{x})W_{q_{\pi }}(\mathbf{x})W_{q_{{\pi }_b}}(\mathbf{x})\end{array}$$

Info

这里也有一点问题。根据原文的图

奖励是有正有负的，但是两个$W$作为PDF的比，应该是非负的，这样$r$应该是非正的才对。另外根据实际训练结果，奖励受一个epoch内${\mathbb{I}}_A\ne 0$的比例影响远远大过$W_{q_{\pi }}$的影响

2. 密集性

D2RL只将触发critical条件的状态作为经验喂给RL去学习：

原始的DRL，策略梯度为：

$$\mathrm{\nabla }\hat{J}(\theta )={\hat{q}}_{\pi }(S_t,A_t)\frac{\mathrm{\nabla }\pi (A_t\mid S_t,\theta )}{\pi (A_t\mid S_t,\theta )}$$

而D2RL的策略梯度为：

$$\begin{array}{}\text{(6)}& {\mathrm{\nabla }}_{\mathrm{dense}}\hat{J}(\theta )={\hat{q}}_{\pi }(S_t,A_t)\frac{\mathrm{\nabla }\pi (A_t\mid S_t,\theta )}{\pi (A_t\mid S_t,\theta )}{\mathbb{I}}_{S_t\in {\mathbb{S}}_c}\end{array}$$

其中${\mathbb{S}}_c$表示critical states的集合。 Uncritical states的定义为：如果状态$s$有

$$\begin{array}{}\text{(7)}& v_{\pi }(s)=q_{\pi }(s,a),\mathrm{\forall }a\end{array}$$

也就是说该状态下采取任何动作，都不会影响未来回报的期望。于是可以定义${\mathbb{S}}_c\triangleq \{s|v_{\pi }(s)\ne q_{\pi }(s,a),\mathrm{\exists }a\}$.

定理1

$$\begin{array}{}\text{(Theo. 1.1)}& {\mathbb{E}}_{\pi }[{\mathrm{\nabla }}_{\mathrm{dense}}\hat{J}(\theta )]={\mathbb{E}}_{\pi }[\mathrm{\nabla }\hat{J}(\theta )]\end{array}$$$$\begin{array}{}\text{(Theo. 1.2)}& {\mathrm{Var}}_{\pi }[{\mathrm{\nabla }}_{\mathrm{dense}}\hat{J}(\theta )]\le {\mathrm{Var}}_{\pi }[\mathrm{\nabla }\hat{J}(\theta )]\end{array}$$$$\begin{array}{rl}\text{(Theo. 1.3)}& {\mathrm{Var}}_{\pi }[{\mathrm{\nabla }}_{\mathrm{dense}}\hat{J}(\theta )]\le & {\rho }_{\pi }{\mathrm{Var}}_{\pi }[\mathrm{\nabla }\hat{J}(\theta )],\mathrm{if}{\mathbb{E}}_{\pi }[{\sigma }_{\pi }^2(S_t,A_t){\mathbb{I}}_{S_t\in {\mathbb{S}}_c}]=& {\mathbb{E}}_{\pi }[{\sigma }_{\pi }^2(S_t,A_t)]{\mathbb{E}}_{\pi }[{\mathbb{I}}_{S_{t}n{\mathbb{S}}_c}]\end{array}$$

其中${\rho }_{\pi }\triangleq {\mathbb{E}}_{\pi }({\mathbb{I}}_{S_t\in {\mathbb{S}}_c})\in [0,1]$是critical states在所有states中所占的比例，${\sigma }_{\pi }(S_t,A_t)={\hat{q}}_{\pi }(S_t,A_t)\frac{\mathrm{\nabla }\pi (A_t\mid S_t,\theta )}{\pi (A_t\mid S_t,\theta )}$

证明参见论文的Supplementary Information 2.c节.

Theo. 1.1表明了排除那些uncritical states不会影响策略梯度（无偏）。Theo. 1.2则证明了这一做法能够减小策略梯度的方差。Theo. 1.3则在一个前提假设下，给出了方差的上界。这个前提假设其实就是说，${\sigma }_{\pi }^2(S_t,A_t)$与${\mathbb{I}}_{S_t\in {\mathbb{S}}_c}$是独立的。在训练刚开始时，由于策略和$q$函数都是随机初始化的，这时${\sigma }_{\pi }^2$对所有的states基本都差不多，所以这个条件基本上成立。这证明D2RL能够在训练刚开始时极大地缩小策略梯度的方差，使得策略快速地收敛。

基于式（6），PPO算法的优势函数$A_t$也需要修改。原始的GAE-Lambda优势函数为：

$$A_t={\delta }_t+(\gamma \lambda ){\delta }_{t+1}+\cdots +(\gamma \lambda {)}^{L-t+1}{\delta }_{L-1}$$

其中

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

D2RL的优势函数为：

$$A_t={\delta }_{z(t,0)}+(\gamma \lambda ){\delta }_{z(t,1)}+\cdots +(\gamma \lambda {)}^{L-t+1}{\delta }_{z(t,L-1)}$$

其中

$${\delta }_{z(t,j)}=r_t+\gamma V(s_{z(t,j+1)})-V(s_{z(t,j)})$$

而

$$z(t,j)=\{\begin{array}{ll}0,& j=0\\ \underset{i}{min}\{s_i\in {\mathbb{S}}_c|i>z(t,j-1)\},& j>0\end{array}$$

Info

这里其实有点小问题。按照这个$z(t,j)$的定义方法，其实就是把$t$时刻后的critical状态重新连起来构成Markov链。但是，这样链的长度会变短，因此$z(t,L-1)$应该是取不到的。这种情况怎么处理，原文并没有说明。我怀疑这个时候的$L$已经不再是原始的Markov链长度，而是缩短以后的长度了。

论文的Supplementary Information中给出了更general的适用于罕见奖励的强化学习理论，并指出，式（7）其实是更一般的要求：

$$\mathrm{A}\cap \mathrm{B}=\mathrm{\varnothing },\mathrm{A}\cup \mathrm{B}=\mathrm{\Omega },{\mathbb{E}}_P[X\cdot {\mathbb{I}}_A(X)]=0,{\mathbb{E}}_P[X\cdot {\mathbb{I}}_B(X)]\ne 0$$

的弱化形式。这里$A$表示非罕见状态集合，$B$是罕见状态集合，$X$是我们需要估计的随机变量。满足这一要求的划分$(A,B)$有很多，显然如果集合$B^{\prime }$满足，那么总可以找到$B^{″}\supset B^{\prime }$同样满足。式（7）给出的是满足条件的划分，但不一定这样的划分下$B$是最小的。

3. 离轨学习机制

为什么选择离轨学习机制呢？ 根据重要性采样理论，如果采用分布$q(x)$来估计${\mathbb{E}}_p[f(X)]$，那么最优的$q^{\ast }(x)\propto f(x)p(x)$，此时能够得到一个0方差的estimator。 在式（4）中，我们用了一次重要性采样，根据上述理论可以得到这里最优的$q_{{\pi }_b}$:

$$q_{{\pi }_b^{\ast }}\propto {\mathbb{I}}_A(\mathbf{x})W_{q_{\pi }}(\mathbf{x})P(\mathbf{x})=\frac{{\mathbb{I}}_A(\mathbf{x})P^2(\mathbf{x})}{q_{\pi }(\mathbf{x})}$$

而在式（1）中，我们也使用了一次重要性采样。这里的$q(\mathbf{x})$也就是$q_{\pi }(\mathbf{x})$，最优时有：

$$q_{{\pi }^{\ast }}\propto {\mathbb{I}}_A(\mathbf{x})P(\mathbf{x})$$

于是有：

定理2

$$q_{{\pi }_b^{\ast }}(\mathbf{x})\propto \frac{q_{{\pi }^{\ast }}^2(\mathbf{x})}{q_{\pi }(\mathbf{x})}$$

这也就是说，最优的表观策略与目标策略是成反比的，那么如果采用的是同轨策略，$q_{\pi }\equiv q_{{\pi }_b}$，那么学习到的策略就会与最优的目标策略相反。实际表现就会是，在训练过程中碰撞的概率增加，但在测试过程中的碰撞概率反而更低。

具体实现

1. 状态与动作

作者进行了两类实验：单纯生成碰撞场景的corner-case generation，和使用D2RL策略构建无偏测试环境的intelligent-testing-environment generation。 CCG没有使用式（5）的奖励函数，而是单纯奖励碰撞（+20）。ITEG同时使用了D2RL和式（5）的奖励函数。 state由AV和周围的8辆BV的位置和速度组成，对于corner-case generation，动作为周围的8量BV采取的动作（每辆车33个离散动作）。对于intelligent-testing-environment generation，动作为一个连续值${ϵ}_{\pi }\in [0.001,0.999]$，表示最critical的BV采取对抗操作的概率。具体哪辆BV采取操作以及采取什么操作，由criticality measure决定。这辆BV采取其余操作的概率根据NDE模型以$(1-{ϵ}_{\pi })$正则化，而其它BV则根据NDE模型采取行动。

2. NDE模型

NDE模型由作者在2021年提出^[2]。具体的建模过程我还没有读，本文称他们使用了简化的NDE模型，由经过修改的IDM和MOBIL构成（修改为概率性的模型）。NDE模型可以给出每一步下BV采取各种操作的分布，并与真实数据集的分布保持一致。

基于Markov假设，NDE被用于计算$P(\mathbf{x})$，并进一步计算两个重要性权重。

3. 表观策略

[[#3. 离轨学习机制]]中已经提过，最优的表观策略和目标策略基本上是相反的。本文采用了一个简单的方法：表观策略在训练过程中始终不变。作者采用的表观策略是恒定的${ϵ}_{{\pi }_b}=0.01$，以平衡探索和利用。作者指出算法的表现对这个值不敏感。

4. criticality measure

式（7）给出了critical states的定义，但实际上很难直接检查这个条件是否满足。作者使用基于特定知识的measure来判断。比如说，如果根据TTC等条件判断当前的状态安全，那么就认为它近似满足式（7），反之亦然。作者使用的criticality measure是^[3]中提出的。

实验

作者使用AR技术进行了实体实验，基于修改的SUMO仿真器和AR渲染技术。

这两张图说明了同轨策略的D2RL在训练中能观察到碰撞率提升，但在测试时却表现出碰撞率低于ground truth。而离轨策略则在测试中表现出得碰撞率与ground truth基本一致（经过重要性采样加权），体现出无偏性。

无偏性：碰撞率接近NDE

D2RL比自然驾驶环境NDE的效率提高了约${10}^4$

对比D2RL与NDE各种参数分布体现出无偏性

AR实验环境

---

1. 几乎处处：不满足条件的集合是零测的 ↩︎

2. https://arxiv.org/abs/2101.02828, Distributionally Consistent Simulation of Naturalistic Driving Environment for Autonomous Vehicle Testing; https://www.nature.com/articles/s41467-021-21007-8, Intelligent driving intelligence test for autonomous vehicles with naturalistic and adversarial environment ↩︎

3. https://arxiv.org/abs/1905.03419, Testing Scenario Library Generation for Connected and Automated Vehicles, Part I: Methodology ↩︎