重要性采样在策略梯度类算法的应用
PPO算法是重要性采样在策略梯度类算法中应用的典型成果。策略梯度类算法通常以最大化期望奖励（Expected Reward）为目标：
\[ \bar{R}_{\theta}=\sum R(\tau) p_{\theta}(\tau)=\int R(\tau) p_{\theta}(\tau) d \tau=\mathrm{E}_{\mathrm{r} \sim p_{0}(t)}[R(\tau)] \]
求导后，梯度可以化为以下形式：
\[ \begin{aligned} \nabla \bar{R}_{\theta} &=\sum_{\tau} R(\tau) \nabla p_{\theta}(\tau)=\sum_{\tau} R(\tau) {p_{\theta}(\tau) \frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)}} \\ &=\sum R(\tau) p_{\theta}(\tau) \nabla \operatorname{log}\left(p_{\theta}(\tau)\right)=\mathrm{E}_{\tau \sim p_{\theta}(\tau)}\left[R(\tau) \nabla \log \left(p_{\theta}(\tau)\right)\right] \end{aligned} \]
对上式使用重要性采样后，梯度化为以下形式：
\[ \nabla \bar{R}_{\theta}=E_{{\tau \sim p_{\theta^{\prime}}(\tau)}}\left[\frac{p_{\theta}(\tau)}{p_{\theta^{\prime}}(\tau)} R(\tau) \nabla \log p_{\theta}(\tau)\right] \]
由于\(p_{\theta}(\tau)\)中包含的状态转移概率与策略无关，因此对上式化简并积分后，可以得到经过重要性采样的目标函数（Objective）：
\[ \bar{R}_{\theta}=E_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} \mid s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right)\right] \]
由于在策略前后分布差距较大时会为目标函数引入较大方差，PPO算法引入了两种解决方案：将两种分布的KL散度作为惩罚项（penalty）引入目标函数；使用clip函数对原目标函数的值进行限制。 如下所示。
\[ L^{C L I P}(\theta)=\hat{\mathbb{E}}_{t}\left[\min \left(r_{t}(\theta) \hat{A}_{t}, \operatorname{clip}\left(r_{t}(\theta), 1-\epsilon, 1+\epsilon\right) \hat{A}_{t}\right)\right] \]
在PPO算法中，重要性采样技术将原来只能使用on-policy训练的策略梯度方法修改成能根据不同策略产生的样本进行训练的方法。
DDPG为什么不需要重要性采样
DDPG不需要重要性采样的原因是其使用了确定性策略梯度。对于PG算法，其梯度为：
\[ \begin{aligned} \nabla_{\theta} J\left(\pi_{\theta}\right) &=\int_{\mathcal{S}} \rho^{\pi}(s) \int_{\mathcal{A}} \nabla_{\theta} \pi_{\theta}(a \mid s) Q^{\pi}(s, a) \mathrm{d} a \mathrm{d} s \\ &=\mathbb{E}_{s \sim \rho^{\pi}, a \sim \pi_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}(a \mid s) Q^{\pi}(s, a)\right] \end{aligned} \]
但是因为DDPG使用的是确定性策略梯度，其动作可以表示为\(\mu_{\theta}(s)\)，因此对策略梯度的目标函数可以化为：
\[ \begin{aligned} J\left(\mu_{\theta}\right) &=\int_{\mathcal{S}} \rho^{\mu}(s) r\left(s, \mu_{\theta}(s)\right) \mathrm{d} s \\ &=\mathbb{E}_{s \sim \rho^{\mu}}\left[r\left(s, \mu_{\theta}(s)\right)\right] \end{aligned} \]
从上式可以看出，因为动作可以表示为状态的确定性函数，对动作的积分可以省去。因此，其策略梯度可以化为：
\[ \begin{aligned} \nabla_{\theta} J\left(\mu_{\theta}\right) &=\left.\int_{\mathcal{S}} \rho^{\mu}(s) \nabla_{\theta} \mu_{\theta}(s) \nabla_{a} Q^{\mu}(s, a)\right|_{a=\mu_{\theta}(s)} \mathrm{d} s \\ &=\mathbb{E}_{s \sim \rho^{\mu}}\left[\left.\nabla_{\theta} \mu_{\theta}(s) \nabla_{a} Q^{\mu}(s, a)\right|_{a=\mu_{\theta}(s)}\right] \end{aligned} \]
DQN为什么不用重要性采样
DQN类型的方法与PG系列的方法不同，PG系列的方法是以最大化期望奖励为目标，而DQN系列方法是为了拟合出Bellman最优函数（Bellman Optimality Equation）。
Bellman最优函数的状态价值版本如下：
\[ V^{\pi}(s)=E_{s^{\prime} \sim p(s, \pi(s))}\left[r\left(s, a, s^{\prime}\right)+\gamma V^{\pi}\left(s^{\prime}\right)\right] \]
Bellman最优函数的动作价值版本如下：
\[ Q(s, a)=E_{s^{\prime} \sim p(s, a)}\left[r\left(s, a, s^{\prime}\right)+\gamma\max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right)\right] \]
根据随机收敛理论，如果\(X_n\)的更新过程如下，其中\(\varepsilon_{n}\)为有界的随机变量，期望是\(E\)：
\[ X_{n+1}=X_{n}+B_{n}\left(\varepsilon_{n}-X_{n}\right) \]
且
\[ 0 \leq B_{n}<1, \quad \sum_{i=1}^{\infty} B_{n}=\infty, \quad \sum_{i=1}^{\infty} B_{n}^{2}<\infty \]
那么当\(n \rightarrow \infty\)时，\(X_n\)将以概率1收敛到\(E\)。
将上式的\(\varepsilon_{n}\)替换为\(r\left(s, a, s^{\prime}\right)+\gamma\max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right)\)就得到了TD-based的Q-learning方法。
\(Q(s, a)\)期望中所涉及的概率为\(p\left(s^{\prime} \mid s, a\right)\)，因为动作\(a\)在一开始已经被决定，不管是由什么策略产生，涉及的概率均不存在生成\(a\)的概率，而\(p\left(s^{\prime} \mid s, a\right)\)由环境决定，对于不同策略具有相同的取值，因此不需要重要性采样。
而对于2 step Q-learning来说
\[ Q(s, a)=E_{s^{\prime} \sim p(s, a), s^{\prime \prime} \sim p\left(s^{\prime}, \pi\left(s^{\prime}\right)\right)}\left[r\left(s, a, s^{\prime}\right)+\gamma r\left(s^{\prime}, a^{\prime}, s^{\prime \prime}\right)+\gamma^{2} \max _{a^{\prime \prime}} Q\left(s^{\prime \prime}, a^{\prime \prime}\right)\right] \]
此期望涉及的概率为\(p\left(s^{\prime} \mid s, a\right) \pi\left(a^{\prime} \mid s^{\prime}\right) p\left(s^{\prime \prime} \mid s^{\prime}, a^{\prime}\right)\)，其中包含策略\(\pi\)，因此如果使用\(\epsilon - greedy\)方法产生动作\(a\)的话，就要乘上重要性因子。