蒙特卡洛预测：估计 Vπ

蒙特卡洛（MC）方法提供了一种从经验中学习的方式，而无需环境动态模型（$p(s', r | s, a)$）。使用MC方法的第一步通常是预测，这意味着估计给定策略$\pi$的状态值函数$V^\pi(s)$。状态值函数$V^\pi(s)$表示从状态$s$开始并随后遵循策略$\pi$所获得的预期累积折扣回报。

MC预测的核心思想非常直接：我们想要估计一个期望值，$V^\pi(s) = \mathbb{E}_\pi[G_t | S_t = s]$。大数定律告诉我们，可以通过对许多样本取平均来近似期望值。在MC方法中，这些样本是在与环境进行模拟或实际交互过程中，访问状态$s$后观察到的实际回报（$G_t$）。

为了获得这些样本，我们需要按照策略$\pi$运行完整的“幕”（episode）。一“幕”是状态、动作和回报的序列，从初始状态开始并终止于一个结束状态：$S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T$。对于一“幕”中的任何时间步$t$，回报$G_t$是从该点开始的累积折扣回报：

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-t-1} R_T$$

其中$T$是结束状态的时间步，且$\gamma$是折扣因子。

MC预测通过平均在多个“幕”中访问状态$s$后观察到的回报$G_t$来估计$V^\pi(s)$。对于如何处理单个“幕”中多次访问同一状态的情况，主要有两种变体。

首次访问蒙特卡洛预测

在首次访问MC方法中，我们只考虑每个“幕”中状态$s$首次被访问之后的回报。

步骤如下：

1. 初始化:
   • 将所有状态$s \in \mathcal{S}$的值估计$V(s)$初始化为任意值（例如0）。
   • 为每个状态$s$初始化一个空列表Returns(s)，用于存储该状态观察到的回报。
2. 幕循环: 重复多“幕”：
   • 通过遵循策略$\pi$生成一整“幕”。令序列为$S_0, A_0, R_1, S_1, \dots, S_T$。
   • 记录本“幕”中哪些状态已被访问。集合或布尔数组在此处很有用。
   • 从$t = T-1$到$0$向后遍历该“幕”的时间步。
   • 计算回报$G_t = R_{t+1} + \gamma G_{t+1}$（反向计算效率高）。
   • 如果状态$S_t$在此“幕”中尚未被访问过：
     • 将$S_t$标记 (token)为本“幕”已访问。
     • 将计算出的回报$G_t$添加到Returns(S_t)列表中。
     • 通过平均目前在Returns(S_t)中收集到的所有回报来更新状态$S_t$的值估计： $$V(S_t) = \text{平均值}(\text{Returns}(S_t))$$

随着更多“幕”的生成以及每个状态收集到更多回报，Returns(s)中的平均值将收敛到真实的预期回报$V^\pi(s)$。

每次访问蒙特卡洛预测

每次访问MC方法类似，但它平均的是每个“幕”中状态$s$的每次访问之后的回报。

步骤2略有不同：

1. 初始化: 同首次访问MC。
2. 幕循环: 重复多“幕”：
   • 使用策略$\pi$生成一整“幕”：$S_0, A_0, R_1, S_1, \dots, S_T$。
   • 从$t = T-1$到$0$向后遍历时间步。
   • 计算回报$G_t = R_{t+1} + \gamma G_{t+1}$。
   • 将计算出的回报$G_t$添加到Returns(S_t)列表中。
   • 更新状态$S_t$的值估计： $$V(S_t) = \text{平均值}(\text{Returns}(S_t))$$

首次访问和每次访问MC方法都收敛到真实的状态值函数$V^\pi(s)$，因为每个状态的访问次数（分别是首次访问或所有访问）趋于无限。首次访问MC在理论上通常更容易分析，而每次访问MC可能在初步实现时稍简单，并且也已成功应用。对于大量的“幕”，差异通常变得不那么明显。

增量实现

如果运行很多“幕”或者状态空间很大，存储每个状态的所有回报可能会占用大量内存。我们可以增量计算平均值，而无需存储整个回报列表。

假设我们刚从状态$s$的一次访问（首次或每次，取决于方法）中获得了一个新的回报$G$。令$N(s)$为在此新回报之前为状态$s$收集的回报计数。我们想使用新的回报$G$来更新我们当前的估计$V(s)$（即前$N(s)$个回报的平均值）。

在$N(s)+1$个回报之后的新平均值将是：

$$V_{new}(s) = \frac{1}{N(s)+1} \sum_{i=1}^{N(s)+1} G_i = \frac{1}{N(s)+1} (G + \sum_{i=1}^{N(s)} G_i)$$

由于旧的估计是$V_{old}(s) = \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_i$，我们有$\sum_{i=1}^{N(s)} G_i = N(s) V_{old}(s)$。将此代入：

$$V_{new}(s) = \frac{1}{N(s)+1} (G + N(s) V_{old}(s))$$

重新整理后得到常用的增量更新规则：

$$V_{new}(s) = V_{old}(s) + \frac{1}{N(s)+1} (G - V_{old}(s))$$

这个更新规则看起来像：新估计值 = 旧估计值 + 步长 * (目标值 - 旧估计值)。这里，回报$G$充当我们将估计值趋近的“目标”值，步长是$\frac{1}{N(s)+1}$。

为了实现这一点，我们不使用Returns(s)列表，而是维护：

• $V(s)$: 状态$s$的当前平均回报（值估计）。
• $N(s)$: 到目前为止为状态$s$平均的回报计数。

当状态$s$观察到新的回报$G$时：

1. 增加计数：$N(s) \leftarrow N(s) + 1$。
2. 更新值估计：$V(s) \leftarrow V(s) + \frac{1}{N(s)} (G - V(s))$。（注意：这里使用新的$N(s)$）。

使用常数步长

有时，特别是在环境或策略可能随时间变化的非平稳问题中，会使用一个常数步长参数 (parameter)$\alpha \in (0, 1]$来代替$1/N(s)$：

$$V(s) \leftarrow V(s) + \alpha (G - V(s))$$

这赋予了近期回报更大的权重 (weight)，使得估计值能够在真实值$V^\pi(s)$变化时进行调整。然而，使用常数$\alpha$时，估计值不会完全收敛到真实值；它会在真实值附近波动。对于我们希望收敛到真实$V^\pi(s)$的平稳问题，通常更倾向于使用$1/N(s)$步长，因为它满足随机逼近收敛的条件。

MC预测提供了一种可靠的、免模型的方法来评估给定策略$\pi$。通过简单地运行“幕”并平均回报，我们可以估计在该策略下处于任何特定状态的好处。这种评估策略的能力是下一步的构成部分：即寻找更好的策略，这是MC控制的目标。