22. 离线MC强化学习算法（1）

1. 理解离线MC强化学习的关键

离线强化学习的特点是采样策略${\pi }^{\prime }\ne 待评估策略\pi$，这就带来一个问题：

如何根据${\pi }^{\prime }$获取的多条完整轨迹数据，计算得到$Q_{\pi }(s,a)$的估计值，而不是$Q_{{\pi }^{\prime }}(s,a)$的估计值。

重要性采样定理为解决上述问题指明了方向，因此，理解重要性采样定理是理解离线MC强化学习的关键。

2. 什么是重要性采样

• 重要性采样定理的积分描述

已知随机变量$x$的函数$f(x)$、$x$的两个不同概率分布$p(x),q(x)$,令$g(x)=\frac{p(x)f(x)}{q(x)}$，设$E_p(f)$为$f(x)$在$p(x)$下的期望，$E_q(g)$为$g(x)$在$q(x)$分布下的期望,则：
$$\begin{array}{r}?\begin{array}{l}{E}_p(f)=E_q(g)\\ E_p(f)={\int }_{x}p(x)f(x)dx\\ E_q(g)={\int }_{x}q(x)g(x)dx\end{array}\end{array}\text{\hspace{1em}?}$$

• 重要性采样定理的统计学描述

根据重要性采样定理的积分描述，很容易推导出其统计学描述，如下：

已知对$x$按照$q(x)$进行采样得到的样本集为 S q = { x q , 1 , x q , 2 , ? ? , x q , m } S_q=\{x_{q,1},x_{q,2},\cdots,x_{q,m}\} Sq?={xq,1?,xq,2?,?,xq,m?},则
可利用如下公式计算出$E_p(f)$的渐进无偏估计$\widehat{E_p}(f)$和$E_q(g)$的
渐进无偏估计$\widehat{E_q}(g)$:
$$\begin{array}{r}\widehat{E_p}(f)=\widehat{E_q}(g)=\frac{1}{m}\sum _{k=1}^m\frac{p(x_{q,k})f(x_{q,k})}{q(x_{q,k})}\end{array}\text{\hspace{1em}?}$$

3.重要性采样定理给我们的一般启示

在估计$x$的函数$f(x)$在$p(x)$下的期望时，若实际情形不允许按照$p(x)$对$x$进行采样，从而直接根据公式$\widehat{E_p}(f)=\frac{1}{m}{\sum }_{k=1}^{m}f(x_{p,k})$估计$E_p(f)$时，可以按照概率$q(x)$
对$x$进行采样获得样本集$S_q$，然后利用公式(2)进行间接估计，得到$E_p(f)$

4.重要性采样定理给离线蒙特卡洛强化学习的启示

在离线MC强化学习中，要解决的问题是：

已知采样策略${\pi }^{\prime }$、待评估策略$\pi$、利用${\pi }^{\prime }$采集获得m条完整轨迹 E P = { E p 1 , E p 2 , ? ? , E p m } EP=\{Ep_1,Ep_2,\cdots,Ep_m\} EP={Ep1?,Ep2?,?,Epm?},其中,$E{p}_k=\{(s_{k,0},a_{k,0},r_{k,1}),(s_{k,1},a_{k,1},r_{k,2}),?,(s_{k,N_k?1},a_{k,N_k?1},r_{k,N_k}),(s_{k,N_k},a_{k,N_k},r_{k,N_k+1})\},k=1,2,?,m$，所有轨迹的
最后一个状态$s_{k,N_k}\equiv s_T(终止状态)$
，若固定$s_t=s,a_t=a$,则每条轨迹中三元组$(s,a,r)$中的$r$可以看做是随机变量，累积回报$G^{{\pi }^{\prime }}(s,a)$是$r$的函数

求解：策略$\pi$下的累积回报函数$G^{\pi }(s,a)$的期望$Q_{\pi }(s,a)$的估计值$\widehat{Q_{\pi }}(s,a)$。

求解过程：

• 1.根据$EP$，利用公式计算得到$(s,a)$固定时，随机变量$r$的函数$G^{{\pi }^{\prime }}(s,a)$在m个采样点
  的样本函数值$G_k^{{\pi }^{\prime }}(s,a),k=1,2,?,m$
• 2.根据重要性采样公式(2)，及$G_k^{{\pi }^{\prime }}(s,a)=G_k^{\pi }(s,a)$可得：
  $$\begin{array}{rl}\widehat{Q_{\pi }}(s,a)& =\frac{1}{m}\sum _{k=1}^m\frac{p_k^{\pi }}{p_k^{{\pi }^{\prime }}}{G}_k^{\pi }(s,a)\\ & =\frac{1}{m}\sum _{k=1}^m\frac{p_k^{\pi }}{p_k^{{\pi }^{\prime }}}{G}_k^{{\pi }^{\prime }}(s,a)\\ p_k^{\pi }& ?策略\pi 下，出现完整轨迹E{p}_k的概率\\ p_k^{{\pi }^{\prime }}& ?策略{\pi }^{\prime }下，出现完整轨迹E{p}_k的概率\\ {\rho }_k=\frac{p_k^{\pi }}{p_k^{{\pi }^{\prime }}}& ?重要性采样比例，表示待评估策略\pi 下和采样策略{\pi }^{\prime }下获得轨迹E{p}_k的概率之比\\ p_k^{\pi }& =[\pi (a_{k,0}|s_{k,0})P_{s_{k,0}{s}_{k,1}}^{a_{k,0}}]\times [\pi (a_{k,1}|s_{k,1})P_{s_{k,1}{s}_{k,2}}^{a_{k,1}}]\times ?\times [\pi (a_{k,N_k?1}|s_{k,N_k?1})P_{s_{k,N_k?1}{s}_{k,N_k}}^{a_{k,N_k?1}}]\\ & =\prod _{i=0}^{N_k?1}\pi (a_{k,i}|s_{k,i})P_{s_{k,i}{s}_{k,i+1}}^{a_{k,i}}\\ p_k^{{\pi }^{\prime }}& =\prod _{i=0}^{N_k?1}{\pi }^{\prime }(a_{k,i}|s_{k,i})P_{s_{k,i}{s}_{k,i+1}}^{a_{k,i}}\\ {\rho }_k& =\frac{{\prod }_{i=0}^{N_k?1}\pi (a_{k,i}|s_{k,i})}{{\prod }_{i=0}^{N_k?1}{\pi }^{\prime }(a_{k,i}|s_{k,i})}\end{array}$$