基于完整回合的学习

动态规划方法非常依赖于拥有一个完整的环境模型。这些方法要求了解状态转移概率 $p(s', r | s, a)$ 来计算期望值并找到最优策略。然而，在许多实际问题中，这样的模型不可得，或者过于复杂而难以精确描述。代理如何在不知道游戏规则的前提下，学会做出好的决策呢？

蒙特卡洛（MC）方法通过直接从经验中学习来提供解决方案。MC 方法不依赖于模型，而是通过与环境交互并观察结果来学习价值函数和策略。对于基本的 MC 方法来说，经验的基本单位是回合。

回合是从初始状态开始并终止于终止状态的一系列交互。可以将其视为一次任务的完整执行。例如：

• 一局二十一点游戏，从首次发牌直到有人赢牌或爆牌。
• 从起始位置导航迷宫，直到到达出口（或被定义为终止的死胡同）。
• 机械臂抓取物体的一次尝试，以成功或失败告终。

每个回合都包含一系列状态、动作和奖励：$S_0, A_0, R_1, S_1, A_1, R_2, \dots, S_T$，这里 $T$ 是最终时间步，$S_T$ 是终止状态。

蒙特卡洛方法的核心思想很简单：它们基于在许多回合中访问某个状态（或状态-动作对）后观察到的平均回报来估计价值函数。它们的工作方式是等待整个回合完成。只有这样，才能计算出该回合中访问的每个状态之后的实际回报。

回顾回报 $G_t$ 的定义，它是从时间步 $t$ 开始的总折扣奖励：

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

这里，$\gamma$ 是折扣因子 ($0 \le \gamma \le 1$)，$T$ 是回合的终止时间步。

因为 MC 方法需要直到回合终止的完整奖励序列才能计算 $G_t$，它们只能直接应用于回合型任务，即那些保证最终会终止的任务。

一旦一个回合结束，我们就会得到一个 $(S_t, A_t, R_{t+1})$ 元组的样本序列。接着，我们可以回溯计算该回合中每个时间步 $t$ 的观测回报 $G_t$。如果我们想估计状态价值函数 $V^\pi(s)$，我们会查看状态 $s$ 在许多回合中被访问过的所有时刻。对于每一次访问，我们都会计算随之而来的回报 $G_t$。$V^\pi(s)$ 的估计值就是这些观测回报的平均值。类似地，要估计动作价值函数 $Q^\pi(s, a)$，我们对在状态 $s$ 中执行动作 $a$ 后观察到的回报取平均值。

这个过程依赖于大数定律：随着我们收集越来越多的回合（即更多的样本），样本回报的平均值会收敛到真实的期望回报，这正是价值函数的定义。

这种方法与动态规划形成鲜明对比。动态规划方法使用环境模型 ($p(s', r | s, a)$) 进行自举，即基于其他一步之遥的价值估计来更新价值估计。另一方面，MC 方法不进行自举。它们使用从经验中观测到的实际完整回报 $G_t$。这种不依赖模型是一个重要优点，但这也意味着我们必须等到回合结束才能进行任何更新。

在接下来的章节中，我们将探讨这种从完整回合中学习的原理，如何应用于预测价值（为给定策略 $\pi$ 估计 $V^\pi$ 或 $Q^\pi$）以及寻找最优策略（控制）。