- 目录
- 同轨策略方法的缺陷
- 离轨策略简介
- 重要性采样(Importance Sampling)
- 两种常用的重要性采样
- 普通重要性采样
- 加权重要性采样
上一节介绍了同轨策略(on-policy)的基本原理和公式推导。即便同轨策略可以通过避免试探性出发假设来表现蒙特卡洛控制问题，但是同轨策略同样存在缺陷。因此，我们从同轨策略缺陷的角度出发，介绍另外一种求解蒙特卡洛控制的方法——离轨策略(off-policy)。
同轨策略方法的缺陷上一节介绍到，同轨策略主要对策略改进后的结果 π \pi π使用 ϵ \epsilon ϵ-贪心策略进行修正。但在实际情况中， ϵ \epsilon ϵ- 贪心策略仍然是一种约束性强的策略：它会将策略改进后的确定性策略 通过人为设定的方式强行转化为软性策略。
这种强行转化可能带来什么样的后果呢？示例2种情况：
- 人为误差：由于 ϵ \epsilon ϵ是人为设定的， ϵ \epsilon ϵ代表某一具体动作对应的概率分布 → \to → ϵ \epsilon ϵ的人为设定可能在算法执行过程中带来人为误差；
- 系统误差：在算法执行过程中，可能需要某一步的策略是确定性策略，但这与 ϵ \epsilon ϵ-贪心算法产生的软性策略相矛盾——导致 ϵ \epsilon ϵ结果本身完全沦为了算法执行过程的误差。
相比于同轨策略，离轨策略方法的目标策略(target policy) π ( a ∣ s ) \pi(a \mid s) π(a∣s)和行为策略(behaviour policy) b ( a ∣ s ) b(a \mid s) b(a∣s)是区分开的：
- 所有情节(样本) 的生成都遵循单独的行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)；
- 利用 b ( a ∣ s ) b(a \mid s) b(a∣s)产生的情节来更新目标策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s)；
这样做的优势在于：两种策略无必然联系，行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)仍然是软性策略， π ( a ∣ s ) \pi(a \mid s) π(a∣s)既可能是确定性策略，也可能是随机性策略(不受 b ( a ∣ s ) b(a \mid s) b(a∣s)影响)。
但这种方式也存在问题：采样难；使用常规方法很难将样本采出来。 在蒙特卡洛控制问题的策略评估过程，我们要求解的是状态价值函数 V π ( s ) V_\pi(s) Vπ(s)/状态-动作价值函数 q π ( s , a ) → q_\pi(s,a) \to qπ(s,a)→ 回报结果 G t G_t Gt在目标策略 π ( a ∣ s ) \pi(a \mid s) π(a∣s) 中的期望。 V π ( s ) = E π [ G t ∣ S t = s ] q π ( s , a ) = E π [ G t ∣ S t = s , A t = a ] \begin{aligned} V_\pi(s) & = \mathbb E_\pi[G_t \mid S_t = s] \\ q_\pi(s,a) & = \mathbb E_\pi[G_t \mid S_t = s,A_t = a] \end{aligned} Vπ(s)qπ(s,a)=Eπ[Gt∣St=s]=Eπ[Gt∣St=s,At=a]
在产生样本过程中，每一个情节的每一个步骤都是由行为策略 b ( a ∣ s ) b(a \mid s) b(a∣s)产生的；现在 b ( a ∣ s ) b(a \mid s) b(a∣s)和 π ( a ∣ s ) \pi(a \mid s) π(a∣s)之间没有必然联系——两个无关联的策略(概率分布)相互更新，产生的更新结果必然是不准确的。
具体的难点在于：将一个分布与另一个分布关联起来； 或者避开分布本身——将一个分布的期望与另一个分布的期望关联起来。 对于动态特性函数
p
(
s
′
,
r
∣
s
,
a
)
p(s',r \mid s,a)
p(s′,r∣s,a)未知的情况下，如何通过采样方式解决这个问题。这里介绍一种采样方法：重要性采样(Importance Sampling)。 重要性采样(Importance Sampling)是马尔可夫链蒙特卡洛(MCMC)采样方法的一种经典方法，我们在后续开设其他专栏中详细介绍(先隔空画个饼)。
重要性采样并没有直接针对待求解分布进行采样，而是对 待求解分布的期望进行采样。 其原理主要基于待求解分布过于复杂，无法基于该分布直接求解期望。具体做法是：
- 选择另一个采样分布，针对其重要性(Importance)进行采样；
- 通过采样结果与重要性的加权和来近似待求解分布的期望。
具体什么是重要性，又如何根据重要性求解待分布期望的？场景设计如下：
- 假设 x x x是服从待求解概率分布 p ( x ) p(x) p(x)的离散型随机变量， p ( x ) p(x) p(x)对应期望表示如下( f ( x ) f(x) f(x)为随机变量 x x x的一个函数)： E x ∼ p ( x ) [ f ( x ) ] = ∑ x p ( x ) f ( x ) ≈ 1 N ∑ i = 1 N f ( x ( i ) ) \mathbb E_{x\sim p(x)}[f(x)] = \sum_{x}p(x)f(x) \approx \frac{1}{N}\sum_{i=1}^N f(x^{(i)}) Ex∼p(x)[f(x)]=x∑p(x)f(x)≈N1i=1∑Nf(x(i))
- 由于 p ( x ) p(x) p(x)过于复杂，没有办法采出样本集合 { x ( 1 ) , x ( 2 ) , . . . , x ( N ) } \{x^{(1)},x^{(2)},...,x^{(N)}\} {x(1),x(2),...,x(N)}近似求解 E x ∼ p ( x ) [ f ( x ) ] \mathbb E_{x\sim p(x)}[f(x)] Ex∼p(x)[f(x)]。因此，在这里引入一个采样分布(能够直接进行采样的分布) q ( x ) q(x) q(x)，并对原式进行如下变换(将 f ( x ) f(x) f(x)提到前面)： E x ∼ p ( x ) [ f ( x ) ] = ∑ x p ( x ) f ( x ) = ∑ x p ( x ) q ( x ) q ( x ) f ( x ) = ∑ x [ p ( x ) q ( x ) f ( x ) ] q ( x ) \begin{aligned} \mathbb E_{x\sim p(x)}[f(x)] & = \sum_{x}p(x)f(x) \\ & = \sum_{x}\frac{p(x)}{q(x)}q(x)f(x) \\ & = \sum_{x}[\frac{p(x)}{q(x)}f(x)]q(x) \end{aligned} Ex∼p(x)[f(x)]=x∑p(x)f(x)=x∑q(x)p(x)q(x)f(x)=x∑[q(x)p(x)f(x)]q(x)
- 根据上式变换结果，将 x x x看成服从 q ( x ) q(x) q(x)的期望表示： E x ∼ p ( x ) [ f ( x ) ] = ∑ x [ p ( x ) q ( x ) f ( x ) ] q ( x ) = E x ∼ q ( x ) [ p ( x ) q ( x ) f ( x ) ] \begin{aligned} \mathbb E_{x\sim p(x)}[f(x)] & = \sum_{x}[\frac{p(x)}{q(x)}f(x)]q(x) \\ & = \mathbb E_{x\sim q(x)}[\frac{p(x)}{q(x)}f(x)] \end{aligned} Ex∼p(x)[f(x)]=x∑[q(x)p(x)f(x)]q(x)=Ex∼q(x)[q(x)p(x)f(x)]
- 由于 q ( x ) q(x) q(x)同样是一个分布，并且容易进行采样，根据蒙特卡洛方法，近似表示如下： E x ∼ p ( x ) [ f ( x ) ] = E x ∼ q ( x ) [ p ( x ) q ( x ) f ( x ) ] ≈ 1 N ∑ i = 1 N p ( x ( i ) ) q ( x ( i ) ) f ( x ( i ) ) \mathbb E_{x\sim p(x)}[f(x)] = \mathbb E_{x\sim q(x)}[\frac{p(x)}{q(x)}f(x)] \approx \frac{1}{N} \sum_{i=1}^N \frac{p(x^{(i)})}{q(x^{(i)})}f(x^{(i)}) Ex∼p(x)[f(x)]=Ex∼q(x)[q(x)p(x)f(x)]≈N1i=1∑Nq(x(i))p(x(i))f(x(i))
通过观察发现， x x x服从 p ( x ) p(x) p(x)的蒙特卡洛方法表示结果于 q ( x ) q(x) q(x)相差一个系数： p ( x ( i ) ) q ( x ( i ) ) \frac{p(x^{(i)})}{q(x^{(i)})} q(x(i))p(x(i))，我们称这个系数为重要性采样比率(importance-sampling ratio)，也称重要度系数。
两种常用的重要性采样总结一下重要性采样(Importance Sampling)的特点：
- 采样分布 q ( x ) q(x) q(x)和待求解分布 p ( x ) p(x) p(x)之间具有相同的定义域 → \to → 它们都是基于随机变量 x x x的概率分布；
- 采样分布 q ( x ) q(x) q(x)与待求解分布 p ( x ) p(x) p(x)越接近，方差越小；反之，方差越大； 证明如下： 根据期望与方差的联系： V a r ( X ) = E ( X 2 ) − [ E ( X ) ] 2 Var(X)=E(X^2)-[E(X)]^2 Var(X)=E(X2)−[E(X)]2 分别求解随机变量 x x x分别服从于待求解分布 p ( x ) p(x) p(x)和采样分布 q ( x ) q(x) q(x)的方差如下： V a r x ∼ p ( x ) [ f ( x ) ] = E x ∼ p ( x ) [ f ( x ) 2 ] − ( E x ∼ p ( x ) [ f ( x ) ] ) 2 V a r x ∼ q ( x ) [ f ( x ) p ( x ) q ( x ) ] = E x ∼ q ( x ) [ ( f ( x ) p ( x ) q ( x ) ) 2 ] − ( E x ∼ q ( x ) [ f ( x ) p ( x ) q ( x ) ] ) 2 \begin{aligned} Var_{x \sim p(x)}[f(x)] & = \mathbb E_{x \sim p(x)}[f(x)^2] - (\mathbb E_{x \sim p(x)}[f(x)])^2 \\ Var_{x \sim q(x)}[f(x)\frac{p(x)}{q(x)}] & = \mathbb E_{x \sim q(x)}[(f(x)\frac{p(x)}{q(x)})^2] - (\mathbb E_{x \sim q(x)}[f(x)\frac{p(x)}{q(x)}])^2 \end{aligned} Varx∼p(x)[f(x)]Varx∼q(x)[f(x)q(x)p(x)]=Ex∼p(x)[f(x)2]−(Ex∼p(x)[f(x)])2=Ex∼q(x)[(f(x)q(x)p(x))2]−(Ex∼q(x)[f(x)q(x)p(x)])2 将 V a r x ∼ q ( x ) [ f ( x ) p ( x ) q ( x ) ] Var_{x \sim q(x)}[f(x)\frac{p(x)}{q(x)}] Varx∼q(x)[f(x)q(x)p(x)]第1项展开，根据重要性采样中两种分布期望的关联关系(将 f ( x ) 2 f(x)^2 f(x)2替换成 f ( x ) f(x) f(x))： E x ∼ p ( x ) [ f ( x ) 2 ] = E x ∼ q ( x ) [ p ( x ) q ( x ) f ( x ) 2 ] \mathbb E_{x\sim p(x)}[f(x)^2] = \mathbb E_{x\sim q(x)}[\frac{p(x)}{q(x)}f(x)^2] Ex∼p(x)[f(x)2]=Ex∼q(x)[q(x)p(x)f(x)2] 有： E x ∼ q ( x ) [ ( f ( x ) p ( x ) q ( x ) ) 2 ] = E x ∼ q ( x ) [ ( ( p ( x ) q ( x ) ) f ( x ) 2 ) p ( x ) q ( x ) ] = E x ∼ p ( x ) [ p ( x ) q ( x ) f ( x ) 2 ] \mathbb E_{x \sim q(x)}[(f(x)\frac{p(x)}{q(x)})^2]= \mathbb E_{x \sim q(x)}[((\frac{p(x)}{q(x)})f(x)^2)\frac{p(x)}{q(x)}] = \mathbb E_{x\sim p(x)}[\frac{p(x)}{q(x)}f(x)^2] Ex∼q(x)[(f(x)q(x)p(x))2]=Ex∼q(x)[((q(x)p(x))f(x)2)q(x)p(x)]=Ex∼p(x)[q(x)p(x)f(x)2] 因此，采样分布 q ( x ) q(x) q(x)的方差变换结果如下： V a r x ∼ q ( x ) [ f ( x ) p ( x ) q ( x ) ] = E x ∼ q ( x ) [ ( f ( x ) p ( x ) q ( x ) ) 2 ] − ( E x ∼ q ( x ) [ f ( x ) p ( x ) q ( x ) ] ) 2 = E x ∼ p ( x ) [ p ( x ) q ( x ) f ( x ) 2 ] − ( E x ∼ p ( x ) [ f ( x ) ] ) 2 \begin{aligned} Var_{x \sim q(x)}[f(x)\frac{p(x)}{q(x)}] & = \mathbb E_{x \sim q(x)}[(f(x)\frac{p(x)}{q(x)})^2] - (\mathbb E_{x \sim q(x)}[f(x)\frac{p(x)}{q(x)}])^2 \\ & = \mathbb E_{x\sim p(x)}[\frac{p(x)}{q(x)}f(x)^2] - (\mathbb E_{x \sim p(x)}[f(x)])^2 \end{aligned} Varx∼q(x)[f(x)q(x)p(x)]=Ex∼q(x)[(f(x)q(x)p(x))2]−(Ex∼q(x)[f(x)q(x)p(x)])2=Ex∼p(x)[q(x)p(x)f(x)2]−(Ex∼p(x)[f(x)])2 观察两个方差结果，发现 q ( x ) q(x) q(x)的方差结果比 p ( x ) p(x) p(x)多了一个系数 p ( x ) q ( x ) \frac{p(x)}{q(x)} q(x)p(x),因此如果二者分布差距过大，会导致方差变大。
普通重要性采样的函数估计即上面描述的重要性采样，在采样过程中各样本间分配相同权重； E x ∼ p ( x ) [ f ( x ) ] = E x ∼ q ( x ) [ p ( x ) q ( x ) f ( x ) ] ≈ 1 N ∑ i = 1 N p ( x ( i ) ) q ( x ( i ) ) f ( x ( i ) ) \mathbb E_{x\sim p(x)}[f(x)] = \mathbb E_{x\sim q(x)}[\frac{p(x)}{q(x)}f(x)] \approx \frac{1}{N} \sum_{i=1}^N \frac{p(x^{(i)})}{q(x^{(i)})}f(x^{(i)}) Ex∼p(x)[f(x)]=Ex∼q(x)[q(x)p(x)f(x)]≈N1i=1∑Nq(x(i))p(x(i))f(x(i))
加权重要性采样介绍一个简单例子： 已知包含3个数的数组： [ 3 , 4 , 5 ] [3,4,5] [3,4,5]；并赋予3个数字不同的权重：
345 1 5 \frac{1}{5} 51 1 7 \frac{1}{7} 71 1 8 \frac{1}{8} 81求解带权重的数组的均值： s = 3 × 1 5 + 4 × 1 7 + 5 × 1 8 1 5 + 1 7 + 1 8 ≈ 3.3 s = \frac{3\times \frac{1}{5} + 4 \times \frac{1}{7} + 5 \times \frac{1}{8}}{\frac{1}{5} + \frac{1}{7} + \frac{1}{8}} \approx 3.3 s=51+71+813×51+4×71+5×81≈3.3 可以看到，由于数字 3 3 3的权重更高，因此结果偏向数字 3 3 3一侧； 基于上述例子，加权重要性采样的函数估计表达如下(将普通重要性采样分母中的 N N N替换成各样本的重要度系数之和 1 ∑ i = 1 N p ( x ( i ) ) q ( x ( i ) ) \frac{1}{\sum_{i=1}^N \frac{p(x^{(i)})}{q(x^{(i)})}} ∑i=1Nq(x(i))p(x(i))1)： E x ∼ p ( x ) [ f ( x ) ] ≈ ∑ i = 1 N [ p ( x ( i ) ) q ( x ( i ) ) f ( x ( i ) ) ] ∑ j = 1 N p ( x ( j ) ) q ( x ( j ) ) \mathbb E_{x\sim p(x)}[f(x)] \approx \frac{\sum_{i=1}^N[\frac{p(x^{(i)})}{q(x^{(i)})}f(x^{(i)})]}{\sum_{j=1}^N \frac{p(x^{(j)})}{q(x^{(j)})}} Ex∼p(x)[f(x)]≈∑j=1Nq(x(j))p(x(j))∑i=1N[q(x(i))p(x(i))f(x(i))]
下一节将介绍基于普通重要性采样和加权重要性采样的离轨策略方法。
相关参考： 【强化学习】蒙特卡洛方法-同轨VS离轨 机器学习-白板推导系列(十三)-MCMC（Markov Chain Monte Carlo） 重要性采样(Importance Sampling)详细学习笔记 期望、方差
