蒙特卡洛(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$首次被访问之后的回报。步骤如下:初始化:将所有状态$s \in \mathcal{S}$的值估计$V(s)$初始化为任意值(例如0)。为每个状态$s$初始化一个空列表Returns(s),用于存储该状态观察到的回报。幕循环: 重复多“幕”:通过遵循策略$\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$标记为本“幕”已访问。将计算出的回报$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略有不同:初始化: 同首次访问MC。幕循环: 重复多“幕”:使用策略$\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$时:增加计数:$N(s) \leftarrow N(s) + 1$。更新值估计:$V(s) \leftarrow V(s) + \frac{1}{N(s)} (G - V(s))$。(注意:这里使用新的$N(s)$)。使用常数步长有时,特别是在环境或策略可能随时间变化的非平稳问题中,会使用一个常数步长参数$\alpha \in (0, 1]$来代替$1/N(s)$:$$ V(s) \leftarrow V(s) + \alpha (G - V(s)) $$这赋予了近期回报更大的权重,使得估计值能够在真实值$V^\pi(s)$变化时进行调整。然而,使用常数$\alpha$时,估计值不会完全收敛到真实值;它会在真实值附近波动。对于我们希望收敛到真实$V^\pi(s)$的平稳问题,通常更倾向于使用$1/N(s)$步长,因为它满足随机逼近收敛的条件。MC预测提供了一种可靠的、免模型的方法来评估给定策略$\pi$。通过简单地运行“幕”并平均回报,我们可以估计在该策略下处于任何特定状态的好处。这种评估策略的能力是下一步的构成部分:即寻找更好的策略,这是MC控制的目标。