4.5　离线策略蒙特卡罗

4.4节给出的在线策略蒙特卡罗方法，产生数据的策略和评估改进的策略都是ε-贪心策略。引入ε-贪心策略的目的是产生丰富的采样数据，因其具有一定的随机性，不适合作为最终的策略使用。可考虑在策略评估时引进随机性策略，如ε-贪心策略或随机策略，而在策略改进时改进原始的非ε-贪心策略，如贪心策略。基于这个思想，就有了离线策略蒙特卡罗方法。

4.5.1　重要性采样离线策略蒙特卡罗

在离线蒙特卡罗强化学习中，使用了重要性采样的方法，通过随机性策略（如ε-贪心策略）产生的数据，对原始贪心策略进行评估和改进。其中，产生采样数据的策略叫行为策略，用π'表示；评估和改进的策略叫原始策略，用π表示。

先来看重要性采样的原理。一般的，假设p、q为两个不同的概率分布，函数f（x）在概率分布p下的期望可表示为

E（f）=∫_xp（x）f（x）dx

可使用从概率分布p上的采样{x₁，x₂，…，x_m}来估计f的期望，有：

上式也可看成是函数在分布q下的期望：

使用从q上的采样，估计f的期望，有：

可见，当随机变量f（x）的分布（f（x）服从于p分布）无法产生样本，或者产生的样本比较复杂的时候，就可以考虑使用一个已知样本或者比较简单的概率分布（如使用f（x）服从于q分布）来逼近随机变量f（x）的期望。

回到我们的问题，分别用π和π'产生两条采样轨迹。两条轨迹的区别是每个“状态行为对”被采样的概率不同。

使用策略π的采样轨迹评估策略π，实际上是在求取状态行为对（s，a）的累积回报期望，即行为值函数：

G_i表示第i条轨迹上，自状态行为对（s，a）到结束的累积回报，若使用策略π'的采样轨迹来评估策略π，则对累积回报加权，得到

和分别表示两个策略产生第i条轨迹的概率，对于一条给定的轨迹<s₀，a₀，r₀，s₁，a₁，r₁，s₂，a₂，r₂，…，s_T，a_T，r_T>，策略π产生该轨迹的概率为：

同理可得π'产生该轨迹的概率为：

称为重要采样比率，i表示第i条轨迹，T为轨迹终止时刻。可见，原始策略和行为策略产生轨迹概率的比值转化为了两个策略概率的比值。

则使用策略π'的采样轨迹评估策略π，增量式更新公式如下：

推导过程如下，其中m为轨迹数。

若π为贪心策略，而π'是π的ε-贪心策略，则π（a_j|s_j）对于a_j=π（s_j）为1，π'（a_j|s_j）为或者。则可以通过行为策略（ε-贪心策略）对原始策略（贪心策略）进行评估。

以下为重要采样的离线策略蒙特卡罗算法的描述。算法中产生数据的策略为ε-贪心策略，评估改进的策略是贪心策略。

4.5.2　加权重要性采样离线策略蒙特卡罗

基于重要性采样的积分是无偏估计，因此使用重要性采样进行策略评估时，得到的行为值函数的估计也是无偏估计。然而由于在进行计算时，对被积函数乘以了一个重要性比率，如下：

使得被积函数方差发生较大变化，如果轨迹存在循环不终止的情况，对应的方差会变为无穷大。为了解决采样方差问题，就有了加权重要性采样方法：

与普通重要采样相比，分母由m变为重要采样比率之和。

用加权重要性采样方法解决离线策略蒙特卡罗问题时，对应的行为值函数估计可表示为

现在来推导使用加权重要采样方法更新行为值函数的公式：

称为加权重要性采样权重。若π为贪心策略，而π'是随机策略。m为轨迹数，则可以通过行为策略（随机策略）对原始策略（贪心策略）进行评估。以下为加权重要性采样离线策略蒙特卡罗算法的描述。