很多时候历史轨迹(s, a, s’, r)采集使用到的policy，与产生待评估轨迹的策略不同，于是产生off-policy的情况。
模仿学习中需要在每一步评估训练中的策略$\pi$，但抛开可训练的agent不管，单纯评估一个策略产生的轨迹，是否符合历史轨迹，可以通过更加全局的指标，例如稳态状态-策略联合分布$d^{\pi}(s,a)=\pi(a\mid s)d^{\pi}(s) := (1-\gamma)\sum\limits_{t=0}^{\infty}\gamma^t Pr(s_t=s, a_t=a \mid s_0 \sim \beta, a_t \sim \pi(s_t), s_{t+1} \sim Tr(s_t, a_t))$
原本的稳态状态分布就涉及到状态转移时使用的策略，在不计算策略的预期，而是使用联合分布时，就产生了两个联合分布：
一是历史轨迹采集时使用的策略 $d^{\mathcal{D}}(s, a)$，二是由agent训练中或是训练结束后的策略，也是我们想要评估的策略产生的稳态联合分布$d^{\pi}(s, a)$。
RL的优化目标也可以看作是最大化稳态分布下的平均每步收益：
$\rho_{A}(\pi)=\mathbb{E}_{(s,a \sim d^{\pi}(s, a))}[R_s^a] $
假如我们要使用从其他轨迹中采集的预期，进行off-policy评估$\rho_{A}(\pi)$，那么就需要使用importance sampling
$\rho_{A}(\pi)=\mathbb{E}_{(s,a \sim d^{\mathcal{D}}(s, a))}[\frac{d^{\pi}(s, a)}{d^{\mathcal{D}}(s, a)} R_s^a] $
$\rho_{A}(\pi)$与单条轨迹或单个时间戳t无关，在假设历史轨迹满足马尔可夫决策过程的情况下，假设奖赏机制$R_s^a$相同，通过distribution correction ratio $\zeta(s,a):=\frac{d^{\pi}(s, a)}{d^{\mathcal{D}}(s, a)}$来调整相同轨迹（Data轨迹）内，由于不同策略的概率分布不同导致的reward累计差异，进行reward修正，以还原出如果使用$\pi$得到的轨迹的预期累计收益。
问题的关键变成了如何在历史采样轨迹中准确评估distribution correction ration的estimation，即基于DICE的off-policy estimation评估。
任务型对话也可以看作是一个马尔可夫决策过程，《Towards Automatic Evaluation of Dialog Systems: A Model-Free Off-Policy Evaluation Approach》使用DualDICE方法对训练完的agent进行评估，总共24个不同表现的agent，其方法评估出的分数$\rho_{A}(\pi)$与人工与agent交互后的任务得分呈现出较强的相关性，可以作为一种BLEU、PPL，以及Self-play Evaluation方法的自动化评估方式的替代。
接下来是详细推理如何计算出历史轨迹里的correction ration $\zeta(s,a)$：
以效果最好的DualDICE为例，核心思想是考虑以下式子
$min_{x} J(x) := \frac{1}{2} mx^2 – nx$，它的唯一非0解是$x^*=\frac{n}{m}$
把m和n都当作是某种概率，再在外面加一个sum，上面的式子即可看作是从相同的空间内，由不同分布产生的两项预期。
\begin{equation}
min_{x:S \times A \rightarrow C}J_{1}(x):= \frac{1}{2} \mathbb{E}_{(s,a)\sim d^{\mathcal{D}}}[x(s,a)^2]-\mathbb{E}_{(s,a)\sim d^{\pi}}[x(s,a)]
\label{eq1}
\end{equation}
解则是我们想要求得的correction ratio $x^*(s,a)=\frac{d^{\pi}(s,a)}{d^{\mathcal{D}}(s,a)}$
在找到$x(s, a)$的意义以及合适的表达式之前，首先注意到第二项需要从$d^{\pi}(s, a)$里采样，现实里我们不可能让agent跑那么多个time step来评估这个稳态分布，所以要稍微转化一下问题。
定义$v(s, a):= x(s,a) + \gamma \mathbb{E}_{s’\sim \mathcal{Tr}(s, a), a’ \sim \pi(s’)}[v(s’,a’)]$
然后定义状态概率分布，给定起点s0，经过任意不超过当前t步内跳转到st的概率。
$\beta_t(s):=Pr(s=s_t \mid s_0 \sim \beta, a_k \sim \pi(s_k), s_{t+1} \sim \mathcal{Tr}(s_k, a_k) for 0\le k\le t)$
可以展开预期。即需求解的\eqref{eq1}式的第二项：
$\mathbb{E}_{(s,a)\sim d^{\pi}}[x(s,a)] = \mathbb{E}_{(s,a)\sim d^{\pi}}[v(s,a) – \gamma \mathbb{E}_{s’\sim \mathcal{Tr}(s, a), a’ \sim \pi(s’)}[v(s’,a’)]$
$=(1-\gamma) \sum\limits_{t=0}^{\infty} \gamma^t \mathbb{E}_{s\sim \beta_t, a \sim \pi(s)}[v(s, a)-\gamma \mathbb{E}_{s’\sim\mathcal{Tr}(s,a), a’\sim \pi(s’)}[v(s’,a’)]]$
注意到$\mathbb{E}_{s\sim \beta_t, a \sim \pi(s)}[\mathbb{E}_{s’\sim\mathcal{Tr}(s,a), a’\sim \pi(s’)}]$实际上就是后推一轮$s \leftarrow s’$后的$\mathbb{E}_{s\sim \beta_{t+1}, a \sim \pi(s)}$
可得
$\mathbb{E}_{(s,a)\sim d^{\pi}}[x(s,a)]=(1-\gamma) \sum\limits_{t=0}^{\infty} \gamma^t \mathbb{E}_{s\sim \beta_t, a \sim \pi(s)}[v(s, a)] – (1-\gamma) \sum\limits_{t=0}^{\infty} \gamma^{t+1} \mathbb{E}_{s\sim \beta_{t+1}, a \sim \pi(s)}[v(s, a)]$
两项展开后大部分抵消，只剩
$=(1-\gamma)\mathbb{E}_{s\sim \beta_0, a\sim \pi(s)}[v(s, a)]$
使用换元方法绕开on-policy采样后，\eqref{eq1}式第一项的x也要替换成$v(s, a)$
定义Bellman operator $\mathcal{B}^{\pi} v(s,a) := \gamma \mathbb{E}_{s’\sim \mathcal{Tr}(s,a), a’ \sim \pi(s’)}[v(s’,a’)]$
含义是推演一步，则\eqref{eq1}变成
\begin{equation}
\min\limits_{v: S \times A \rightarrow \mathbb{R}} J(v) := \frac{1}{2} \mathbb{E}_{(s,a)\sim Data}[(v-\mathcal{B}^{\pi}v)(s, a)^2] – (1-\gamma)\mathbb{E}_{s\sim \beta_0, a\sim \pi(s)}[v(s, a)]
\label{eq2}
\end{equation}
根据简单二次方程的解，可知
$(v^* – \mathcal{B}^{\pi}v^*)(s,a)=x^*(s,a)=\zeta(s,a)=\frac{d^{\pi}(s,a)}{d^{\mathcal{D}}(s,a)}$
直接求解min式以获得$v^*$再计算上面的表达式作为correction ratio的话会碰到两个问题：
-
- 计算bellman operator时也使用到了期望预估，即使已经解出$v^*$，计算$(v^* – \mathcal{B}^{\pi}v^*)(s,a)$也很难。
为了解决bellman预期的问题，同时解决$(s,a)\sim Data$采样并不是依照轨迹采样$(s,a,s’)\sim Data$，于是使用到了Fenchel’s duality。
关于共轭函数，以及Legendre-Fenchel transform的知识可以参考
https://zhuanlan.zhihu.com/p/188702379
简而言之就是可定义对偶函数$f^*(s):= s^T x – f(x)$，其中$s$是$f(x)$在x点的切线斜率，$f^*$是$-b$，即$f(x)$切线与y轴相交点的y值坐标值取负号。
之后Fenchel发现在求极值时可以将上面原版仅可用于凸函数的Legendre变换推广到非凸甚至是非连续函数上。
给定斜率$s$的直线，直线穿过$f(x)$后在y轴的截距最小值（即$b$的最大值），就正好是对偶函数$f^*(s)$。
于是可以重新定义对偶函数$f^*(s):= \sup\limits_{x} s^T x – f(x)$
可以证明对偶的对偶是原本函数 $f^*(f^*(x)) = f(x) = \sup\limits_{s} x^T s – f^*(s)$
且$\min\limits_{x} f(x)$的解$x^*$处的斜率$s(x^*)$就应该是$\min\limits_{x} \sup\limits_{s} x^T s – f^*(s)$的解$s^*$
现在使用interchangeability principle
$\min\limits_{x \in X} \sup\limits_{\mathcal{S} \in \boldsymbol{\mathcal{S}}} g(x, \mathcal{S}(x)) = \sup\limits_{s \in S} \min\limits_{x \in X} g(x, s)$
其中$\mathcal{S}$是mapping $\mathcal{S} : X \rightarrow S$，$\boldsymbol{\mathcal{S}}$是这类mapping的集合。$\mathcal{S}(x)$实际上就是求导操作，左边写得复杂不过是用于区别右边的自由变量$s$
可得
$\min\limits_{x} f(x) = \sup\limits_{s} \min\limits_{x} x^T s – f^*(s)$
回到我们的求解核心式子\eqref{eq2}
$f(x)$换元变成了$\frac{1}{2} \mathbb{E}_{(s,a)\sim Data}[(v-\mathcal{B}^{\pi}v)(s, a)^2]$
斜率变量（并非状态）$s$实际上就是$\zeta$
然后考虑对偶函数的形式：
$f^*(\frac{1}{2} x^2) = \sup\limits_{s} [x \frac{\partial 0.5 x^2}{\partial x} – \frac{1}{2} x^2] = \sup\limits_{s} \frac{1}{2} x^2 = \sup\limits_{s} \frac{1}{2} \left( \frac{\partial 0.5x^2}{\partial x} \right)^2 = \sup\limits_{s} \frac{1}{2} s^2$
于是得到下面式子（里面的s是状态而非斜率）
\begin{equation}
\min\limits_{v: S \times A \rightarrow \mathbb{R}} \max\limits_{\zeta} J(v, \zeta) = \min\limits_{v: S \times A \rightarrow \mathbb{R}} \max\limits_{\zeta} \mathbb{E}_{(s,a,s’)\sim Data, a’\sim \pi(s’)}[ (v(s,a)-\gamma v(s’,a’)) \cdot \zeta(s,a) – \frac{1}{2} \zeta(s,a)^2] \\ – (1-\gamma)\mathbb{E}_{s\sim \beta_0, a\sim \pi(s)}[v(s, a)]
\label{eq3}
\end{equation}
上面使用到的技巧是先把原本的优化目标函数转化为对偶的对偶，于是引入对偶斜率$\zeta$，之后使用interchangeability principle让$\zeta$作为一个新的联合变量，把原本很难求解的目标变成较好求解（鞍点min-max）的问题。然后利用鞍点解就在$(v^*, \zeta^*)$，就可以绕开$x$直接获得correction ratio。
使用DualDICE方法求解\eqref{eq3}可以获取correction ratio，但也有其他一些论文提出的方法，求解公式有一些相似的地方。《Off-Policy Evaluation via the Regularized Lagrangian》提出了一种统一的min-max目标公式，包含多种DICE求解的优化目标，不过实验中发现还是Dual表现更好。
Unified DICE优化目标里，$\frac{1}{2} \zeta(s,a)^2$被当作regularizer，系数$\frac{1}{2}$被改成可训练的$\alpha_{\zeta}$
然后新增一个归一化条件：$\mathbb{E}_{(s,a,s’) \in Data}[\zeta(s,a)]=1$，意味着经过correction ratio修正后的reward累计，不应被过分放大或缩小。一个不随策略变化的reward奖赏机制（例如每步t都获得固定奖励），应该对所有策略下的平均每步预期$\rho_A(\pi)$都给出相同的estimation，即$r_{const}=\mathbb{E}_{(s,a,s’) \in Data}[\zeta(s,a) r_{const}] \forall \zeta_{\pi}$
将该条件作为constraint，乘以可训练的Lagrange multiplier $\lambda$ 后放入min-max公式，可得correction ratio estimator的优化目标
\begin{equation}
\max\limits_{\zeta \ge 0} \min\limits_{v, \lambda} L_{Data}(\zeta, v, \lambda) = \max\limits_{\zeta \ge 0} \min\limits_{v, \lambda} \mathbb{E}_{(s,a,s’) \sim Data, a’ \sim \pi(s’)} \left[ \left( v(s’,a’) – v(s,a) \right) \cdot \zeta(s, a) – \alpha_{\zeta} \zeta(s,a)^2 – \lambda(1-\zeta(s,a)) \right] \\ – (1-\gamma)\mathbb{E}_{s_0\sim \beta_0, a_0\sim \pi(s_0)}[v(s_0, a_0)]
\label{eq4}
\end{equation}
第二项的$\beta_0$与$\pi(\alpha_0)$在对话中一般都是初始化预设固定的，对于所有轨迹而言$v(s_0,a_0)$都是一个相同的bias，所以实际优化时基本上都忽略，只初始化时计算好$v_0$之后优化第一项的Data预期即可。
训练时梯度更新计算以下内容：$\frac{\partial L}{\partial \theta_{v}}$, $\frac{\partial L}{\partial \lambda}$, $\frac{\partial -L}{\partial \theta_{\zeta}}$
$\theta$是$v$与$\zeta$各自网络的参数。
训练完成后使用$\zeta(s,a)$网络对测试集内所有数据i的每一步t进行评估，再计算 $\rho(\pi)=\sum\limits_{i,t} \zeta(s_t^{(i)}, a_t^{(i)}) r_t^{(i)}$
得到平均每步收益$\mathbb{E}_{(s,a \sim d^{\pi}(s, a))}[R_s^a]$，但并未被归严格一化。尽管我们通过$\lambda$项添加了限制条件，但由于SGD更新，仍需要使用评估后再归一化的方法，变成：
$\rho(\pi)=\sum\limits_{i,t \in \tau_{Data}} \zeta(s_t^{(i)}, a_t^{(i)}) r_t^{(i)} / \sum\limits_{i,t \in \tau_{Data}}\zeta(s_t^{(i)}, a_t^{(i)})$
最终得到完整的评估流程：
一些个人的感想：
使用DICE方法有以下的优势
- 放弃单步策略相似度评估，改用稳态分布的相似度，某种程度上更接近轨迹相似度，避免Value函数评估时$\frac{1}{(1-\gamma)^2}$的误差。
- eward稀疏时更好训练，因为训练$\zeta$网络的过程已经与reward无关，GAIL在reward稀疏时很难学习到正确轨迹。
-
