Generative Adversarial Imitation Learning

1. GAIL 概念介绍

假如需要从一个示例的专家数据中学习出一个策略，而且学习过程中没有专家的指导和信号预测。一种方是行为克隆方法，主要是通过监督学习模型从专家数据中学习出策略，但是这种方法需要大量数据。另一种方法是通过逆强化学习从专家数据中学习代价函数，该代价函数从专家的角度而言是唯一最优的，但是这种方法不直接而且比较慢，通常需要强化学习在内循环。为什么不可以直接从专家数据中学习出一个策略呢？

本文提出一种可以直接从专家数据中学习出策略的算法，称为 GAIL（Generative Adversarial Imitation Learning），生成对抗模仿学习。GAIL 实际上也运用了 GAN 的训练方法，来拟合状态数据和动作数据的分布，从而定义专家的行为。

2. 相关知识

2.1 符号定义

$\overline{\mathbb{R}}$ 定义为扩展的实数集：$\mathbb{R} \cup \{\infty\}$ 。

定义状态空间为 $\mathcal{S}$，动作空间为 $\mathcal{A}$，$\Pi$ 表示在状态空间 $\mathcal{S} $ 执行动作 $\mathcal{A} $ 的平稳随机策略集合。

状态转移概率定义为 $P(s’|s,a)$ 。

起始状态的分布写为 $p_0(s)$ 。

对于给定的策略 $\pi \in \Pi$，定义性能期望为：$\mathbb{E}_\pi[c(s,a)] \triangleq \mathbb{E}[\sum_{t=0}^\infty \gamma^t c(s_t,a_t)]$ 。

对于采样的轨迹样本，性能期望的符号表示为 $\hat{\mathbb{E}_\tau}$，专家策略表示为 $\pi_E$ 。

2.2 逆强化学习

本文后面采用了 maximum causal entropy (因果熵) IRL [1,2] ，它构造了一个优化问题：

$$\mathop{maximize}_{c \in \mathcal{C}} \left( \min_{\pi \in \Pi} - H(\pi) + \mathbb{E}_\pi[c(s,a)] \right) - \mathbb{E}_{\pi_E}[c(s,a)] \tag{1}$$

其中 $c$ 表示 cost function，$\mathcal{C}$ 表示函数族，$H(\pi) \triangleq \mathbb{E}_\pi[-\log \pi(a|s)]$ 表示 $\gamma$ 折扣因果熵。

$\pi_E$ 实际上只是执行策略 $\pi_E$ 得到的一系列采样轨迹。因此 $\mathbb{E}_{\pi_E}$ 需要从这些样本中估计期望值。

最大化因果熵逆强化学习方法的目的是找到一个代价函数 $c \in \mathcal{C}$，使得对于专家策略，代价最低，而对于其他策略，代价很高。找到代价函数 $c$ 之后，从而通过强化学习过程估计专家策略：

$$RL(c) = \mathop{\arg \min}_{\pi \in \Pi} -H(\pi)+\mathbb{E}_\pi[c(s,a)] \tag{2}$$

3. 算法推导

首先研究 IRL 的表达能力。IRL 建立在庞大的代价函数族 $\mathbb{R}^{\mathcal{S} \times \mathcal{A}} = \{c:\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}\}$ 上。由于拥有庞大的函数族，，对于固定的数据集很容易造成过拟合。因此本文引入一个凸的正则项 $\psi: \mathbb{R}^{\mathcal{S} \times \mathcal{A}} \rightarrow \overline{\mathbb{R}}$ 。加入正则项的最大因果熵 IRL 目标可以表示为：

$$IRL_\psi(\pi_E) = \mathop{\arg \max}_{c \in \mathbb{R}^{\mathcal{S} \times \mathcal{A}}}-\psi(c) + \left( \min_{\pi \in \Pi} - H(\pi) + \mathbb{E}_\pi[c(s,a)] \right) - \mathbb{E}_{\pi_E}[c(s,a)] \tag{3}$$

令 $\tilde{c} \in IRL_\psi(\pi_E)$ ，现在我们感兴趣的是由 $RL(\tilde{c})$ 得出的策略的性能。

为了评估 $RL(\tilde{c})$，将原先优化问题转化为凸问题。首先定义策略 $\pi \in \Pi$ 的占有率（occupancy measure） $\rho_\pi: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ 为 $\rho_\pi(s,a) = \pi(a|s) \sum_{t=0}^\infty \gamma^t P(s_t=s|\pi)$ 。

占有率可以理解为状态动作对在策略 $\pi$ 执行下的概率分布。此时对于 $c(s,a)$，期望值的计算可以写为：$\mathbb{E}_\pi[c(s,a)]=\sum_{s,a} \rho_\pi(s,a)c(s,a)$ 。论文 [3] 中证明了占有率集合 $\mathcal{D} \triangleq \{\rho_\pi: \pi \in \Pi \}$ ，可以写成仿射约束的可行集：$\mathcal{D}=\left\{ \rho:\rho \ge 0 \;\; and \;\; \sum_a \rho(s,a)=\rho_0(s) + \gamma \sum_{s’,a} P(s’|s,a)\rho(s’,a) \;\; \forall s \in \mathcal{S} \right\}$ 。（PS：仿射变换就是线性变化加上一个平移）注意，$\Pi$ 和 $\mathcal{D}$ 是一一映射的。

• 命题 3.1：如果 $\rho \in \mathcal{D}$，那么 $\rho$ 是策略 $\pi_\rho \triangleq \rho(s,a)/\sum_{a’} \rho(s,a’)$ 的占有率，$\pi_{\rho}$ 也是唯一的占有率为 $\rho$ 的策略。

• 命题 3.2：$RL \circ IRL_\psi(\pi_E) = \arg \min_{\pi \in \Pi} -H(\pi)+\psi^*(\rho_\pi-\rho_{\pi_E})$

为了评估 $RL(\tilde{c})$，需要一个数学工具：共扼函数。对于函数 $f:\mathbb{R}^{\mathcal{S} \times \mathcal{A}} \rightarrow \overline{\mathbb{R}}$，它的共扼函数 $f^:\mathbb{R}^{\mathcal{S} \times \mathcal{A}} \rightarrow \overline{\mathbb{R}}$ 表示为$f^(x)=\sup_{y\in \mathbb{R}^{\mathcal{S} \times \mathcal{A}}} x^Ty -f(y) $ 。共扼函数一定是凸函数。

命题 3.1 出自论文 [4] 。命题 3.2 在本文的附录 A 有证明。

命题 3.2 告诉我们带有 $\psi$ 正则项的 IRL 在含蓄地寻找一个策略，其占有率接近专家策略，通过共扼函数 $\psi^*$ 来度量。本文接下来将会阐述采用不同的 $\psi$ 设置，将会导致不同的模仿学习方法。

3.1 constant function $\psi$

最特殊的情况是 $\psi$ 是一个常数（也就是不采用正则项）。

引理 3.1：令 $\bar{H}(\rho) = -\sum_{s,a}\rho(s,a) \log \left( \rho(s,a)/\sum_{a’}\rho(s,a’) \right)$ 。 那么 $\bar{H}$ 是严格的凹函数，并且对于所有的 $\pi \in \Pi$ 和 $\rho \in \mathcal{D}$，都有 $H(\pi)=\bar{H}(\rho_\pi)$ 和 $\bar{H}(\rho)=H(\pi_\rho)$ 。

引理 1 在本文的附录 A 有证明。引理 3.1 告诉我们可以随意在策略和占有率两者间切换，因此得到下面引理。

引理 3.2：如果令 $L(\pi,c)=-H(\pi)+\mathbb{E}_\pi[c(s,a)]$，令 $\bar{L}(\rho,c)=-\bar{H}(\rho)+\sum_{s,a}\rho(s,a)c(s,a)$ 。那么对于所有的代价函数 $c$，都有 $L(\pi,c) = \bar{L}(\rho_\pi,c) \;\; \forall \pi \in \Pi$ ，并且都有 $\bar{L}(\rho,c)=L(\pi_\rho,c) \;\; \forall \rho \in \mathcal{D}$ 。

根据上面两条引理，可以得出以下推论：

推论 3.2.1：​如果 $\psi$ 是一个常数，并且 $\tilde{c} \in IRL_\psi(\pi_E)$，$\tilde{\pi} \in RL(\tilde{c})$，那么 $\rho_{\tilde{\pi}}=\rho_{\pi_E}$ 。

以上推论告诉我们，如果不采用正则项，那么 $RL(\tilde{c})$ 得到的策略将完全与专家策略 $\pi_E$ 匹配。

推论 3.2.1 证明过程如下（涉及到最优化中的原问题和对偶问题）：

---

定义 $\bar{L}(\rho,c) = -\bar{H}(\rho)+\sum_{s,a}c(s,a)(\rho(s,a)-\rho_E(s,a))$ 。给定 $\psi$ 是常数。

根据引理 3.2，可得：

$$\begin{aligned} \tilde{c} & \in IRL_\psi (\pi_E) = \mathop{\arg \max}_{c \in \mathbb{R}^{\mathcal{S}\times \mathcal{A}}} \min_{\pi \in \Pi} -H(\pi) + \mathbb{E}_\pi[c(s,a)] - \mathbb{E}_{\pi_E}[c(s,a)] + const \\ & = \mathop{\arg \max}_{c \in \mathbb{R}^{\mathcal{S}\times \mathcal{A}}} \min_{\rho \in \mathcal{D}} -\bar{H}(\rho) + \sum_{s,a} \rho(s,a)c(s,a) - \sum_{s,a} \rho_E(s,a)c(s,a) = \mathop{\arg \max}_{c \in \mathbb{R}^{\mathcal{S}\times \mathcal{A}}} \min_{\rho \in \mathcal{D}} \bar{L}(\rho,c) \end{aligned} \tag{4} \label{4}$$

以上问题的对偶问题如下：

$$\mathop{minimize}_{\rho \in \mathcal{D}} -\bar{H}(\rho) \;\; subject \;\; to \;\; \rho(s,a) = \rho_E(s,a) \;\; \forall s \in \mathcal{S}, a\in \mathcal{A} \tag{5} \label{5}$$

因此 $\tilde{c}$ 是等式 $\eqref{5}$ 的对偶最优解。

引理 3.1 保证了 $-\bar{H}$ 是严格的凸函数，因此最优解是唯一的。原始问题的最优解可以通过对偶问题的最优解得到，即：

$$\tilde{\rho} = \mathop{\arg \min}_{\rho \in \mathcal{D}} \bar{L}(\rho, \tilde{c}) = \mathop{\arg \min}_{\rho \in \mathcal{D}} -\bar{H}(\rho) + \sum_{s,a} \tilde{c}(s,a)\rho(s,a)=\rho_E \tag{6}$$

如果 $\tilde{\pi} \in RL(\tilde{c})$，根据引理 3.2，$\tilde{\pi}$ 的占有率 $\rho_{\tilde{\pi}} = \tilde{\rho} = \rho_E$ 。

---

从推论的结果，本文得出以下两条结论：

• IRL 是占有率匹配问题的一个对偶形式。
• 从占有率匹配对偶问题中导出的最优策略就是原始问题的最优策略。

3.2 occupancy measure matching

在上一节中，阐述了如果正则项是常数，则原问题相当于与专家数据进行状态动作数据占有率匹配的问题，也就是说占有率越与专家数据的占有率匹配，则推导出的策略越接近专家策略。但在实际运用中，占有率匹配算法实际是不可行的。因为专家轨迹数据的分布仅仅是一个有限样本的集合，在大规模环境中，很多数据不在专家数据集中，因此导致这些数据的占有率在专家数据集中为零。这回导致让学习出策略避开专家数据集中没有的状态动作对。

另外还有一个问题，占有率匹配的约束条件数量与定义域 $\mathcal{S} \times \mathcal{A}$ 的大小相同，这就导致在函数逼近的参数优化过程中产生大量的运算。

为了在大规模环境中运用模仿学习算法，松弛公式 $\eqref{5}$ 的形式，写成：

$$\mathop{minimize}_\pi \; d_\psi(\rho_\pi,\rho_E) - H(\pi) \tag{7} \label{7}$$

其中 $d_\psi(\rho_\pi,\rho_E)$ 定义为 $\rho_\pi$ 和 $\rho_E$ 两个占有率的正则项，即 $d_\psi(\rho_\pi,\rho_E) \triangleq \psi^*(\rho_\pi-\rho_E)$ ，与命题 3.2 的形式类似。

3.2.1 apprenticeship learning

学徒学习（apprenticeship learning）算法也是公式 $\eqref{7}$ 的一种特殊形式。令代价函数集合 $\mathcal{C} \subset \mathbb{R}^{\mathcal{S} \times \mathcal{A}}$，学徒学习算法的目标为：

$$\mathop{minimize}_{\pi} \; \max_{c \in \mathcal{C}} \mathbb{E_\pi}[c(s,a)]-\mathbb{E}_{\pi_E}[c(s,a)] \tag{8} \label{8}$$

接下来说明公式 $\eqref{8}$ 为什么属于是公式 $\eqref{7}$ 的形式。

定义一个指示函数 $\delta_\mathcal{C}: \mathbb{R}^{\mathcal{S}\times\mathcal{A}} \rightarrow \overline{\mathbb{R}}$，表达式为：

$$\delta_\mathcal{C} = \left\{ \begin{aligned} &0 &c \in \mathcal{C} \\ &+\infty &otherwise \end{aligned} \right.$$

则公式 $\eqref{8}$ 可以写为如下形式：

$$\max_{c \in \mathcal{C}} \mathbb{E_\pi}[c(s,a)]-\mathbb{E}_{\pi_E}[c(s,a)] = \max_{c \in \mathbb{R}^{\mathcal{S}\times \mathcal{A}}} -\delta_\mathcal{C} + \sum_{s,a}(\rho_\pi(s,a)-\rho_{\pi_E}(s,a))c(s,a) = \delta^*(\rho_\pi - \rho_{\pi_E}) \tag{9}$$

因此学徒学习算法实际上采用的代价函数正则项为 $\psi = \delta_\mathcal{C}$，也就是将代价函数的范围限制在集合 $\mathcal{C}$ 中。带有熵正则项的学徒学习算法的目标可以写为：

$$\mathop{minimize}_{\pi} \; -H(\pi) + \max_{c \in \mathcal{C}} \mathbb{E_\pi}[c(s,a)]-\mathbb{E}_{\pi_E}[c(s,a)] \tag{10} \label{10}$$

对于集合 $\mathcal{C}$ 的形式，经典的学徒学习算法主要是将 $\mathcal{C}$ 限制子一个凸集中，该集合由一系列基函数进行线性组合得来：$f(s,a)=[f_1(s,a),\dots,f_d(s,a)]$。文中给出两种凸集：$\mathcal{C}_{linear}$ [5] 和 $\mathcal{C}_{convex}$[4] 。

$$\begin{aligned} \mathcal{C}_{linear} &= \{ \sum_i w_i f_i : \| w \|_2 \le 1 \} \\ \mathcal{C}_{convex} &= \{ \sum_i w_i f_i : \sum_iw_i = 1, w_i \ge 0 \;\;\forall_i \} \end{aligned} \tag{11} \label{11}$$

3.2.2 学徒学习的优点

学徒学习采用了限制的代价函数范围 $\mathcal{C}$，因此能够将这样的 $\mathcal{C}$ 与策略函数逼近结合起来，运用到大规模的状态空间和动作空间中。比如论文 [6] 就将策略梯度公式和学徒学习的目标公式 $\eqref{8}$ 结合起来：

$$\nabla_\theta \max_{c\in \mathcal{C}} \mathbb{E}_{\pi_\theta}[c(s,a)]-\mathbb{E}_{\pi_E}[c(s,a)] = \nabla_\theta \mathbb{E}_{\pi_\theta}[c^*(s,a)] = \mathbb{E}_{\pi_\theta}[\nabla_\theta \log \pi_\theta(a|s)Q_{c^*}(s,a)] \\ \mathscr{where} \;\; c^* = \mathop{\arg \max}_{c \in \mathcal{C}} \mathbb{E}_{\pi_\theta}[c(s,a)] - \mathbb{E}_{\pi_E}[c(s,a)], \;\; Q_{c^*}(\bar{s},\bar{a})=\mathbb{E}_{\pi_\theta}[c^*(\bar{s},\bar{a})|s_0=\bar{s},a_0=\bar{a}] \tag{12}$$

3.2.3 学徒学习的缺点

如果对 $\mathcal{C}$ 的限制过于严格，很有可能找不到和专家策略一样优秀的策略。因此对于基函数 $f_1,\dots,f_d$ 的设计需要十分精致。

4. GAIL 算法

正如前面所说的，如果正则项 $\psi$ 是常数，则对应的模仿学习算法可以与专家策略的占有率完全匹配，但是对于大规模的环境并不适用；如果正则项 $\psi$ 是线性函数类，如公式 $\eqref{11} $ ，则对应的模仿学习算法也许不能与专家策略的占有率完全匹配，但是可以适用于大规模的环境。

本文将提出新的正则器，结合以上两种正则器的优点：

$$\psi_{GA}(c) \triangleq \left\{ \begin{aligned} &\mathbb{E}_{\pi_E}[g(c(s,a))] &if \;\; c < 0 \\ &+\infty &otherwise \end{aligned}, \right. \;\; where \;\; g(x) = \left\{ \begin{aligned} &-x-\log(1-e^x) &if \;\; x < 0 \\ &+\infty &otherwise \end{aligned} \right. \tag{13} \label{13}$$

注意到以上的代价函数的上界为零。公式 $\eqref{13} $ 的意义在于，代价函数对于专家轨迹的值如果是一个小的负数，则正则器给予一个很低的惩罚；如果是一个很大的值（即为零），则正则器给予一个很高的惩罚。

之所以采用这样的正则器，是因为从公式 $ \eqref{13}$ 中可以得到以下推论（证明过程在文中的附录）：

$$\psi^*_{GA}(\rho_\pi-\rho_{\pi_E}) = \max_{D \in (0,1)^{\mathcal{S}\times \mathcal{A}}} \mathbb{E}_\pi[\log(D(s,a))] + \mathbb{E}_{\pi_E}[\log(1-D(s,a))] \tag{14}$$

其中判别器类别的范围是 $D:\mathcal{S \times \mathcal{A}} \rightarrow (0,1)$。现在我们的优化目标是：

$$\mathop{minimize}_\pi \psi^*_{GA}(\rho_\pi - \rho_{\pi_E}) - \lambda H(\pi) \tag{15} \label{15}$$

公式 $\eqref{15}$ 将模仿学习算法和生成对抗网络建立了连接，$D$ 就是生成对抗模型中的判别器。$D$ 的任务就是负责识别生成器 $G$ 生成的数据分布和真实的数据分布的差异，当 $D$ 不再能辨别出差异时，$G$ 的任务就完成了。在公式 $\eqref{15}$ 中，$\rho_\pi$ 就相当于 $G$ 生成的数据分布，而 $\rho_E$ 就相当于真实数据分布。

首先引入 $\pi$ 和 $D$ 的函数逼近形式。定义一个策略网络 $\pi_\theta$ 和判别器网络 $D_w:\mathcal{S}\times \mathcal{A} \rightarrow (0,1)$。然后交替运用 Adam优化 $w$ 和运用TRPO 优化 $\theta$ 。

伪代码中对熵的求导如下：

$$\nabla_\theta H(\pi_\theta) = \nabla_\theta \mathbb{E}_{\pi_\theta}[-\log \pi_\theta(a|s)] = \mathbb{E}_{\pi_\theta}[\nabla_\theta \log \pi_\theta(a|s) Q_{\log}(s,a)], \\ where \;\; Q_{\log}(\bar{s},\bar{a}) = \mathbb{E}_{\pi_\theta}[-\log \pi_\theta(a|s) | s_0=\bar{s},a_0=\bar{a}] \tag{16}$$

参考文献

[1] B. D. Ziebart, A. Maas, J. A. Bagnell, and A. K. Dey. Maximum entropy inverse reinforcement learning. In AAAI, AAAI’08, 2008.

[2] B. D. Ziebart, J. A. Bagnell, and A. K. Dey. Modeling interaction via the principle of maximum causal entropy. In ICML, pages 1255–1262, 2010.

[3] M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.

[4] U. Syed, M. Bowling, and R. E. Schapire. Apprenticeship learning using linear programming. In Proceedings ofthe 25th International Conference on Machine Learning, pages 1032–1039, 2008.

[5] P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings ofthe 21st International Conference on Machine Learning, 2004.

[6] J. Ho, J. K. Gupta, and S. Ermon. Model-free imitation learning with policy optimization. In Proceedings ofthe 33rd International Conference on Machine Learning, 2016.