基于DICE的off-policy estimation评估

很多时候历史轨迹(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)]$

是一个类似于$V^{\pi}(s_0)$这样只与初始状态与策略相关的指标,与轨迹是否on-policy无关。

使用换元方法绕开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的话会碰到两个问题:

  1. 二次项在期望里,并不是简单的二次项,使用随即优化可能有很大误差(例如使用蒙特卡洛估计的梯度,在环境存在随机时,一定是有偏。平方项放大了偏差)

  2. 计算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方法有以下的优势

  1. 放弃单步策略相似度评估,改用稳态分布的相似度,某种程度上更接近轨迹相似度,避免Value函数评估时$\frac{1}{(1-\gamma)^2}$的误差。
  2. eward稀疏时更好训练,因为训练$\zeta$网络的过程已经与reward无关,GAIL在reward稀疏时很难学习到正确轨迹。
  3. 使用post regularization进一步稳定了训练。

 

发表评论

邮箱地址不会被公开。 必填项已用*标注