5. Monte Carlo Methods

MC can be incremental in an episode-by-episode sence, but not in a step-by-step(online) sense.

MC算法的改变是episode-by-episode的，而不是step-by-step(online).

5.1 Monte Carlo Prediction

First-visit
Every-visit：更容易扩展到函数近似 and 资格迹方法

对于MC来说：

对于每个状态的估计都是independent，完全不依赖于对其他状态的估计
与DP算法的==自举==不同，MC没有自举==（bootstrapping）==

特别注意的是：

计算一个状态的代价与状态的个数无关（？）
适合在仅仅需要获得一个或者一个子集的状态的价值函数时使用

由此，MC相比于DP的3个优势在于：

可以从某个特定状态开始采样生成episodes，然后获取回报的平均值，完全不需要考虑其他状态
可以从实际经历中学习
可以从模拟经历中学习

第四个优点：MC不自举，所以在马尔可夫性不成立的时候，性能损失比较小，因为它不用后续状态的估计值来更新当前的估计值。

5.2 Monte Carlo Estimation of Action Values

在Model-free的前提下，计算$v$是没有用的，需要计算$q$

由此引申出了Exploring Starts，因为需要获得每个状态所有可用动作的$q$

5.3 Monte Carlo Control

MC的收敛依赖于两个假设

Exploring Starts
无限多episodes的样本序列

如何去除假设2？

实际上无限多的思想与Policy iteration中解BE的无限，是一样的意思。实际上并没有必要一次就达到无限多，逐渐逼近也是可以的。

5.4 Monte Carlo Control without Exploring Starts

如何去除假设1？

唯一的一般性解决方法：智能体持续不断地选择所有可能的动作，分为两种

on-policy：生成采样数据序列的策略与用于实际决策的待评估改进的策略，相同
off-policy：上述两种策略不同

在on-policy中，policy一般为soft，即$\forall s \in \mathcal{S}$ and $\forall a \in \mathcal{A}(s)$，都有$\pi(a \mid s) > 0$

例如：$\varepsilon$-greedy

使用$\varepsilon$-greedy时，==策略改进定理==也是成立的

5.5 Off-policy Prediction via Importance Sampling

所有控制问题都会面临的困境：

希望学习到的动作，使之后的策略是最优的，但是为了搜索所有的动作，必须采用非最优的策略。

如何遵循试探策略，同时学习到最优策略？

在on-policy中，并不学习最优策略，而是学习一个保留了试探性的、接近最优的策略

在off-policy中，直接采用两个策略：

target policy $\pi$：一个用来学习并最终成为最优策略
behavior policy $b$：另一个具有更强的试探性，用来产生动作样本（生成采样序列）

off-policy方差更大，收敛更慢，但是更强更通用

为了使用从$b$得到的episodes样本序列能够预测$\pi$，要求在$\pi$下发生的每个动作，至少偶尔能够在$b$下发生。

即对于$\forall \pi(a \mid s) > 0$，要求$b(a \mid s) > 0$，称为==覆盖==假设。

5.5.1 Importance Sampling

Importance Sampling：在给定来自其他分布的样本的条件下，估计某种分布的期望值

应用于off-policy，对回报值根据其轨迹，在目标策略与行动策略中出现的相对概率进行加权
相对概率：importance-sampling ratio

给定起始状态$S_t$，后续的state-action轨迹$A_t, S_{t + 1}, A_{t + 1}, \dots. S_T$，在策略$\pi$下发生的概率为：

$\begin{aligned} \text{Pr}\{ & A_t, S_{t + 1}, \dots, S_T \mid S_t, A_{t: T - 1} \sim \pi \} \\ & = \pi(A_t \mid S_t) p(S_{t + 1} \mid S_t, A_t) \pi(A_{t + 1} \mid S_{t + 1}) \cdots p(S_T \mid S_{T - 1}, A_{T - 1}) \\ & = \prod^{T - 1}_{k = t} \pi(A_k \mid S_k) p(S_{k + 1} \mid S_k, A_k) \end{aligned}$

其中$p$是状态转移概率。所以在目标策略和行动策略轨迹下的相对概率（importance-sampling ratio）为：

$\rho_{t: T - 1} \dot{=} \frac{\prod^{T - 1}_{k = t} \pi(A_k \mid S_k) p(S_{k + 1} \mid S_k, A_k)}{\prod^{T - 1}_{k = t} b(A_k \mid S_k) p(S_{k + 1} \mid S_k, A_k)} = \prod^{T - 1}_{k = t} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}$

虽然$\rho$与$p$有关，并且$p$通常是未知的，但是在此处可以约分。最终$\rho$只与两个策略、样本序列数据有关，与MDP的动态特性$p$无关

通过$b$生成的样本数据，希望估计$\pi$的期望回报，但是目前只有$b$对应的$G_t$，不能直接平均后作为$\pi$的估计值。因此需要用到$\rho$，调整$b$的$G_t$：

$\mathbb{E}[\rho_{t:T-1} G_t \mid S_t = s] = v_\pi(s)$

由此引申出了两种方法：

ordinary importance sampling

$V(s) \dot{=} \frac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t) - 1}G_t}{|\mathcal{T}(s)|}$

其中，所有访问过的状态$s$的集合为$\mathcal{T}(s)$

weighted importance sampling

$V(s) \dot{=} \frac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t) - 1}G_t}{\sum_{t \in \mathcal{T}(s)} \rho_{t:T(t) - 1}}$

如果分母为0，则公式(5)也为0。

两种方法的区别：

对于first-visit，获得单个episode的估计值

在加权平均的过程中，公式(5)中$\rho$可以直接约分，所以估计值就等于回报值，而与importance-sampling ratio无关，显然这是一个有偏估计。

而公式(4)的结果，在期望上总是无偏估计，但是这个值可能变得很极端，估计值和观测值的差距取决于比例系数。

从数学上来说：
1. 期望：oridinary是无偏的，weighted是有偏的（渐进收敛到0）
2. 方差：oridinary方差无界（ratio的方差无界），weighted中任何回报值的最大权重都为1，即使ratio的方差无穷，weighted方差仍然可以收敛到0

Sutton-Chap5