model-based方法与model-free方法的对比如下：
model-based:
- 一旦模拟器构建好，就可以使用on-policy learning
- 无需从真实环境采集更多的交互数据。
- 样本利用率更高。
- 模拟器误差会影响强化学习效果。
model-free:
- 收敛后效果更好
- 适用于有大批量历史数据
- off-policy模型训练仍然可能不稳定
- 低样本利用率
强化学习的环境在游戏里很容易得到，但是很多现实业务中，需要开发环境模拟器。
使用已有数据得到一个最接近真实的model: $q(s’ \mid s, a) \rightarrow p(s’ \mid s, a)$是一个非常有用的目标。
然而误差总会伴随出现，在时间与state空间有两种误差来源：
- 来自模拟器在时序上的误差，$\epsilon_m = max_{t} \mathbb{E}_{s \sim \pi_D, t}[ D_{TV}(p(s’, r \mid s, a)) || q_{\theta}(s’, r \mid s, a)]$
- 当强化学习训练时遇到新的state，在模拟器训练时没见到的state时，导致决策策略不同的误差$ \epsilon_{\pi} \ge max_s D_{TV}(\pi || \pi_D)$
$\pi_D$是采样$s \rightarrow s’$时使用的策略。
优化目标$\eta= \sum\limits_{s, a,t} p(s, a) r(s, a)$，在真实环境下的分布是$p(s, a)$
模拟器环境下则变成了$\hat{\eta} = \sum\limits_{s, a,t} q(s, a) r(s, a)$
$\eta \ge \hat{\eta} – C(\epsilon_m, \epsilon_{\pi})$假设了存在一个优化量C，只要我们保证让C减小，就能确保在使用模拟器时，真实优化目标的表现$\eta$也会改善。
问题在于如何找到C。
计算任意两个优化目标的差值
$|\eta_1 – \eta_2| = |\sum\limits_t\sum\limits_{s, a} \gamma^t(p_t(s, a) – q_t(s, a)) r(s, a)|$
$\le \sum\limits_t\sum\limits_{s, a} \gamma^t |p_t(s, a) – q_t(s, a)| r(s, a)$
$\le r_{max} \sum\limits_t\sum\limits_{s, a} \gamma^t |p_t(s, a) – q_t(s, a)|$
其中total variance distance $D_{TV}(p_t(s, a) || q_t(s, a)) = \frac {1}{2} \sum\limits_{s, a} |p_t(s, a) – q_t(s, a)|$
$=\frac{1}{2} \sum\limits_{s, a} |p(s)p(a \mid s) – p(s)q(a \mid s) + p(s)q(a \mid s) – q(s)q(a \mid s)|$
$\le \frac{1}{2} \sum\limits_{s, a} p(s) |p(a\mid s) – q(a \mid s)| + \frac{1}{2} \sum\limits_{s, a} |p(s) – q(s)| q(a \mid s)$
$= \mathbb{E}_{s \sim p}[D_{TV} (p(a \mid s) || q(a \mid s))] + D_{TV}(p(s) || q(s))$
所以根据先前对$\epsilon_{\pi}$的定义，得到
$|\eta_1 – \eta_2| \le 2 r_{max} \sum\limits_t \gamma^t \left[ \mathbb{E}_{s \sim p}[D_{TV} (p(a \mid s) || q(a \mid s))] + D_{TV}(p(s) || q(s)) \right]$
\begin{equation}
|\eta_1 – \eta_2| \le 2 r_{max} \sum\limits_t \gamma^t \left[ \epsilon_{\pi} + D_{TV}(p(s) || q(s)) \right]
\label{xx1}
\end{equation}
接下来需要考虑$D_{TV}(p(s) || q(s))$在时间t的sum下要如何计算。
从t-1步到t步满足
$|p_t(s) – q_t(s)| = |\sum\limits_{s^*} p(s_t=s \mid s^*)p_{t-1}(s^*) – q(s_t=s \mid s^* ) q_{t-1}(s^*)|$
$\le \sum\limits_{s^*} |p(s_t=s \mid s^*)p_{t-1}(s^*) – q(s_t=s \mid s^* ) q_{t-1}(s^*)|$
$=\sum\limits_{s^*} |p_t(s \mid s^*)p_{t-1}(s^*) – q_t(s \mid s^*)p_{t-1}(s^*) + q_t(s \mid s^*)p_{t-1}(s^*) – q_t(s \mid s^*) q_{t-1}(s^*) |$
$\le \sum\limits_{s^*} p_t(s^*) |p(s \mid s^*) – q(s \mid s^*)| + \sum\limits_{s^*} p(s \mid s^*) |p_{t-1}(s^*)-q_{t-1}(s^*)|$
$= \mathbb{E}_{s^* \sim p_{t-1}}[|p(s \mid s^*) – q(s \mid s^*)|] + \sum\limits_{s^*} p(s \mid s^*) |p_{t-1}(s^*)-q_{t-1}(s^*)|$
考虑计算$D_{TV}$时还需要最外面加上$\frac{1}{2} \sum\limits_{s, a}$
于是
$D_{TV}(p_t(s) || q_t(s)) = \frac {1}{2} \mathbb{E}_{s^* \sim p_{t-1}}[ \sum\limits_s |p(s \mid s^*) – q(s \mid s^*)|] + D_{TV}(p_{t-1}(s^*) || q_{t-1}(s^*))$
可以看到存在一个递归
$\epsilon_t = D_{TV}(p_t(s) || q_t(s)) = \delta_t + \epsilon_{t-1}$
$\delta_t = \delta = \frac {1}{2} \mathbb{E}_{s^* \sim p_{t-1}}[ \sum\limits_s |p(s \mid s^*) – q(s \mid s^*)|] $
第0步时不需要模拟器做预测所以$\epsilon_0 = 0$
那么$\epsilon_t = \epsilon_0 + \sum\limits_{i=1}^t \delta t = t\delta$
带入\eqref{xx1}得到
$|\eta_1 – \eta_2| \le 2 r_{max} \sum\limits_t \gamma^t D_{TV}(p_t(s, a) || q_t(s, a)) = 2 r_{max} \sum\limits_t \gamma^t \left[ \epsilon_{\pi} + t\delta \right]$
其中$\delta$里的$s^* \rightarrow s$又可以拆成最开始提到的两部分误差，即模拟器时序上的，以及state空间上的。于是$\delta = \epsilon_m + \epsilon_{\pi}$
$|\eta_1 – \eta_2| \le 2 r_{max} \sum\limits_t \gamma^t \left( t(\epsilon_m + \epsilon_{\pi}) + \epsilon_{\pi} \right)$
$\le 2 r_{max} \sum\limits_{t=1}^{\infty} \gamma^t \left( t(\epsilon_m + \epsilon_{\pi}) + \epsilon_{\pi} \right)$
使用将$\sum\limits_t t\gamma^t$替换为$\gamma \frac {d } {d \gamma} \sum\limits_t \gamma^t$可以转换第一项，之后再使用geometric sum $\sum\limits_{t=1}^{\infty} \gamma^t = \frac {1} {1-\gamma}$，就能得到：
\begin{equation}
|\eta_1 – \eta_2| \le 2r_{max} \left( \frac{\gamma (\epsilon_{\pi} + \epsilon_m)} {(1-\gamma)^2} + \frac{\epsilon_{\pi}}{1-\gamma} \right)
\label{xx2}
\end{equation}
$\eta_2$是真实环境$p(s’ \mid s, a)$在强化学习过程中以运行策略$\pi_D$，采样到的数据集，训练出一个模拟器环境$q_{\theta}(s’ \mid s, a)$（对应$\eta_1$）后，两个环境下的Value函数。
使用两个环境的$V(s)$的差的绝对值来描述模拟器的准确性，其误差上界就是不等式右边的部分。
训练模拟的数据的器采样的$\pi_D = p(a \mid s)$，与训练强化学习模型时从模拟器采样训练得到的策略$\pi = q(a \mid s)$也会有不同，造成的误差就导致了误差上界里$\epsilon_{\pi}$的部分。
一般的模拟器训练思路是优化每一步t时的
$\mathbb{E}_{s \sim \pi_D}[ D_{KL}(p(s’_{t+1}, r \mid s_t, a)) || q_{\theta}(s’_{t+1}, r \mid s_t, a)]$
主要导致的问题是模拟器会拟合出最常见的几种用户行为，多样性不足，与seq2seq的生成问题类似。
而且$\frac {1} {(1-\gamma)^2}$的存在使得远期收益（$\gamma$接近1时）的误差非常大。
Generative Adversarial Imitation Learning:
$$\mathop{\arg\min}_{\pi} \mathop{\arg\max}_{D \in (0,1)} \mathbb{E}_{\pi}[log D(s, a)] + \mathbb{E}_{\pi_E}[log(1-D(s, a))] – \lambda H(\pi)$$
其中$D(s, a)$是评价(s, a)来自强化学习模型$\pi$还是专家历史经验$\pi_E$的概率。$H(\pi)=\mathbb{E}_{\pi}[-log \pi(a \mid s)]$，表示策略的熵，鼓励策略多样性。
更新策略时的目标$\frac {\partial} {\partial \theta} l(s, \pi_{\theta}(s)) =\frac {\partial}{\partial \theta} \left( \mathbb{E}_{\pi_{\theta}}[log D(s, a)] – \lambda H(\pi) \right) \approx \mathbb{E}_{\pi_{\theta}, \tau_i}[\nabla_{\theta} log \pi_{\theta}( a \mid s) Q(s, a)] – \frac {\partial} {\partial \theta}\lambda H(\pi_{\theta})$
要让使用策略梯度的更新方向与GAN的Generator的更新方向一致，就需要满足$Q(s, a)=\mathbb{E}_{\tau_i}[log(D(s,a)) \mid s_0=s, a_0=a]$
所以Q网络实际上和Discriminator共用了主体编码部分，评估$Q(s,a)$时假设s和a都是初始状态的情况下的$logD(s, a)$。这里要作为初始状态就需要在batch采样时忽略所有$\gamma$，来得到路径上所有timestep的未经衰减的discriminate分数。
这样只需要按照正常的policy gradient方向更新策略，就可以让策略更接近Discriminator得分0，即更接近专家策略（只要判别器表现也足够好）。
训练完成后得到的策略也不再是最大化累积收益的策略，而是最接近专家的策略。
还有一些技术细节，例如让每次策略更新时不会比上次的策略偏离太远，使用TRPO方法，具体就不细讲了。
GAIL只是训练了一个agent，但要训练模拟器，则需要从Multi-agent的角度考虑，MAIL将用户模拟器与bot视作了两个agent。不同于GAIL只在静态环境中学习专家的agent，MAIL将用户视作策略是$\pi^c$的agent，模仿用户面对不同bot时的行为，所以可以对不同bot具有一定泛化能力。用户（模拟器）与bot相互影响对方的state，所以用上标c代指用户视角的状态、操作。
具体步骤在《virtual-taobao: virtualizing real-world online retail environment for reinforcement learning》中的描述如下：
- 训练一个GAN-SD模型用于生成用户的初始状态分布$P^c$，这样就可以使用随机噪音z来初始化一个用户，具体细节参见论文。
- 再用1得到的虚拟用户初始意图$P^c$中采样用户request，得到bot感受到的$s_0 \sim P^c$；使用bot模型获得$a \sim \pi_{\theta} (s)$，所以模拟器获得的状态是一个tuple $s^c=<s, a>$。之后让模拟器（参数$\kappa$）运行得到用户操作$a^c \sim \pi_{\kappa}(s^c)$。与bot不断交互，直到触发终止条件（最大轮数或用户购买下单）。得到一条完整的模拟器轨迹$\tau_g$
- 重复2若干次得到batch的$\tau_g$；再从专家与真实用户的交互历史记录里得到一个batch的轨迹$\tau_e$。按照GAIL的思路，需要让生成路径更接近专家路径，Q的定义是$Q_{\sigma}(s, a)=\mathbb{E}_{\tau_g} [log D(s, a)]$。从bot的角度看，GAIL让reward与模仿专家时的每一步的策略相似度相关，这个策略相似度也是multi-agent的reward。但当模拟器训练完，实际使用它来训练bot的时候，reward还是需要根据具体问题重新定义的。
- 根据3，执行优化如下：锁定$\kappa$与$\theta$，优化判别器目标$\mathbb{E}_{\tau_g}[log R_{\sigma}^c(s, a)] + \mathbb{E}_{\tau_e}[log(1-R_{\sigma}^c(s, a))]$
- 更新$\kappa$与$\theta$，优化策略$\pi_{\kappa}(s^c)$与$\pi_{\theta}(s)$，使用Multi-Agent RL的方法。其中Mixed reward如果按照传统的预测t+1步方式的定义，是 $R_{\sigma}^c(s, a) = D_{KL}( p(s’_g \mid s, a), p(s’_e \mid s, a) )$，但路径$\tau_g$上其实没法得到$ p(s’_g \mid s, a)$，所以还是使用了神经网络判别器$R_{\sigma}^c(s, a) =D_{\sigma}(s^c, a^c)$来进行判别。最大化Mixed reward同时也让Generator变得更优秀。其中$s^c=<s, \pi_{\theta}(s), n>$，n是模拟器当前轮数。
到目前为止模型已经可以训练了，但如同之前推导的误差公式里的描述，错误还是会随着推演很快累积的，尤其是当$\gamma$比较大时。使用\eqref{xx2}可得模拟器效果$|\eta – \hat{\eta}| = |\sum\limits_t\sum\limits_{s,a} (p(s,a) – q(s, a)) R_{\sigma}^c(s, a)| \le \frac{2r_{max}} {(1-\gamma)^2} \epsilon_m +Const$
接下来探索reward的定义方式，是否可以修改原本的reward来改善误差上限。
实际上无论使用哪种距离，只要是基于每一步的条件概率$p(s’ \mid s, a)$的距离的reward，就无法摆脱误差分母上的$(1-\gamma)^2$，需要转换一下思路。
定义一个静态sa联合概率分布$\rho(s, a)$如下：$\sum\limits_{t=0}^{\infty} \gamma^t \rho_{\pi}(s, a) := \sum\limits_{t=0}^{\infty} \gamma^t p_{\pi}(s_t=s, a_t=a)$
则$\rho_{\pi}(s, a) = (1-\gamma) \sum\limits_{t=0}^{\infty} \gamma^t p_{\pi}(s_t=s, a_t=a)$
一个与时间无关的模拟器联合分布于是能够被这样定义$\mu_g(s, a, s’) = p_{\pi}(s’_g \mid s, a) \rho_{\pi}(s, a)$。用类似的方法也可以定义专家联合概率$\mu_e(s, a, s’)$
本质上是对$p(s’ \mid s, a)$添加了一个权重修正，使得$p(s’ \mid s, a)$能够适应路径上的任何t的位置。
将reward的定义修改$R_{\sigma}^c(s, a) = D_{KL}( p(s’_g \mid s, a), p(s’_e \mid s, a) ) \rightarrow R_{\sigma}^c(s, a)=D_{JS}(\mu_e(s, a, s’) || \mu_g(s, a, s’))$
模仿学习的reward正好是代表了模型误差的时间部分：$D_{JS}(\mu_e || \mu_g) \le \epsilon_m$，所以通过$\epsilon_m$和$\mu$，$\rho$定义里的$(1-\gamma)$正好能消去误差分母的二次幂，只剩下$\frac {1} {(1-\gamma)}$。注意这种方法无法消除$\epsilon_{\pi}$部分的误差。
改进的具体实施方法就是在MAIL的第三步和第四步时，不先计算每步的KL距离之后再按$\tau$的顺序加起来，而是先按Generated与Expert各自的自然分布$(s, a)$从$\tau$中分别采样，并计算每个采样时间上的$p(s’ \mid s, a)$，再以每步$\gamma^t$的衰减累加$\tau$上每一步的$p(s’ \mid s, a)$。于是得到$\mu(s, a, s’) \approx (1-\gamma) \sum\limits_{(s, a, t) \in \tau} \gamma^t p(s’ \mid s, a)$
最后计算$D_{JS}(\mu_g || \mu_e)$作为GAIL里discriminator评估生成与专家路径的区分分数，使用GAIL同样的策略梯度更新。
