蒙特卡洛方法

在上一节中，我们介绍了策略迭代，它依赖于明确的环境模型（model-based）来进行策略评估和改进。然而，在许多现实问题中，环境模型不可用，或者我们无法轻易获得完整的转移概率 T 和奖励函数 R。这时，蒙特卡洛学习算法（Monte Carlo Learning）作为一种无模型（model-free）方法，提供了一种通过样本进行策略优化的途径。

蒙特卡洛方法的核心思想是：通过对环境的采样，基于多次模拟的经验回报，估计状态值函数或状态-动作值函数（Monte Carlo Estimation）。其依据就是经典的大数定律。

蒙特卡洛学习主要依赖以下几个关键特性：

基于样本：直接使用采样的经验（例如状态序列、奖励序列）进行学习。
延迟更新：直到采样结束后，才对策略或值函数进行更新。
无需环境模型：完全基于与环境的交互，适用于复杂环境。

蒙特卡罗算法

与策略迭代类似，蒙特卡洛方法需要基于一个固定策略$\pi$。我们知道策略迭代包含两个主要步骤：

策略评估 (PE): $v_{\pi^{(k)}}=r_{\pi^{(k)}}+\gamma P_{\pi^{(k)}}v_{\pi^{(k)}}$
策略改进(Pl):$\pi^{(k+1)}=\arg\max_{\pi}\left(r_{\pi}+\gamma P_{\pi}v_{\pi^{(k)}}\right)$

这里面最核心的地方就是状态值$v_{\pi^{(k)}}$的求解，此时有两种办法：

基于模型$T$和$R$,使用迭代法求解：

$$
v_{\pi^{(k)}}(s)=\sum_a\pi^{(k)}(a\mid s)\left[\sum_rp(r\mid s,a)r+\gamma\sum_{s’}p(s’\mid s,a)v_{\pi^{(k)}}(s’)\right]
$$

免模型求解，回归状态值的原始定义：

$$
v_\pi(s)=\mathbb{E}_\pi\left[G_t\mid S_t=s\right]
$$

换句话说，我们可以从任意状态$s$出发，随机采样若干轨迹${\tau}$,使用这些轨迹的累计回报${g_t}$的平均
值来估计$s$的期望累计回报：
$$
v_\pi(s)=\mathbb{E}\pi\left[G_t\mid S_t=s\right]\approx\frac{1}{N}\sum{i=1}^Ng^{(i)}(s)
$$
同理，也可以估计动作$a$的期望累计回报：

$$
q_\pi(s,a)=\mathbb{E}_\pi\left[G_t\mid S_t=s,A_t=a\right]\approx\frac{1}{N}\sum_{i=1}^Ng^{(i)}(s,a)
$$
总之就是一句话：没有模型时，就得有数据！这里采样到的轨迹在统计学或概率学上会称为样本
(Sample),而在强化学习中则称为经验(Experience)。

具体步骤如下：

1.采样：从待求解状态$s_t$和动作$a_t$出发，基于策略$\pi$生成多条完整的轨迹，每条轨迹由状态、动作，
奖励序列组成，例如：

$$
\tau={s_t,a_t,r_{t+1},s_{t+1},a_{t+1},r_{t+2},\ldots,s_T}
$$

其中$T$ 是终止时刻。

2.回报计算：对于每个轨迹，计算累计回报(Return):
$$
g_t=\sum_{k=t}^T\gamma^{k-t}r_{k+1}
$$

3.更新：通过多次采样得到的回报${g_t}$,对动作价值函数进行更新：

$$
q_\pi(s_t,a_t)\leftarrow\frac{\text{累计回报和}}{\text{访问次数}}
$$

之后在策略改进 (PI)步骤中，依旧是贪心选择最大动作价值来更新策略。

有趣的现象——回合（Episode）的长度：

为了 Gt 估计的准确性，我们希望每次采样到的 gt 都尽量精确，因此 Episode 也是越长越好。
如果 Episode 长度很短，例如 1，即模型只会探索一个步骤，最终只有目标周围一步的状态值会得到准确估计，其他地方均为 0，因为无法得到最终奖励。
推广开来，只有当 Episode 长度超过一个状态距离目标状态的最短路径时，该状态值才能得到更新；并且超过得越多，这个估计状态值就离真实值越接近。