探索起点并不足够：Monte Carlo探索起点的反例与修正

# 蒙特卡洛探索启动的反例与修复方法
来源：https://arxiv.org/html/2606.15247 Octave Oliviers
Department of Engineering
University of Cambridge
Cambridge, UK
ofao2@cam\.ac\.uk &Glenn Vinnicombe
Department of Engineering
University of Cambridge
Cambridge, UK
gv103@cam\.ac\.uk

###### 摘要

蒙特卡洛探索启动（MCES）的渐近行为是强化学习中一个长期存在的开放问题，即使在表格设置中也是如此。我们通过构造算法收敛到次优解的例子，研究了表格 MCES 的收敛性质。本文给出了初始访问和首次访问 MCES 的新反例，并为初始访问情况提供了一种恢复收敛性的修改方案。我们表明，即使贪心动作平均而言比非贪心动作更频繁地更新，使用样本平均更新的初始访问 MCES 也可能存在稳定的次优解。然而，通过在逐个状态的基础上将学习率与更新频率成反比缩放，可以保证收敛到最优。与先前的均匀化方法不同，此修改适用于需要近似估计值函数的大规模问题。然后我们扩展该例子，表明样本平均首次访问 MCES 也可能收敛到次优解。这基本上解决了一个基本开放问题，并表明探索启动本身并不能保证收敛到最优。更广泛地说，这些结果强调收敛关键取决于对不同动作应用的更新的相对大小和频率，使得学习率的选择以及探索与利用之间的平衡成为 MCES 分析和可扩展蒙特卡洛控制方法实施的核心。

## 1 引言

强化学习旨在训练智能体在特定环境中做出最优行为。在本文中，我们将这种交互建模为一个有限马尔可夫决策过程（MDP），在离散步骤上演化。在时间 \(t\)，智能体根据策略 \(\pi(a_t|s_t)\) 观察状态 \(s_t \in \mathcal{S}\) 并选择动作 \(a_t \in \mathcal{A}(s_t)\)。然后环境产生奖励 \(r_t\) 并根据动力学 \(p(s_{t+1}, r_t|s_t, a_t)\) 转移到新状态 \(s_{t+1}\)。对于策略 \(\pi\)，动作值函数 \(q_\pi\) 为每个对 \((s,a)\) 分配在状态 \(s\) 中采取动作 \(a\) 然后遵循策略 \(\pi\) 所获得的期望折扣回报：
\[
q_\pi(s,a) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty} \gamma^t r_t \;\middle|\; s_0=s, a_0=a\right].
\]
在标准有限 MDP 假设下，存在一个最优策略 \(\pi_*\)，满足对所有 \((s,a)\) 有 \(q_{\pi_*}(s,a) = \max_\pi q_\pi(s,a)\)。此外，\(\pi_*\) 可以选择为关于 \(q_{\pi_*}\) 的确定性贪心策略，即对所有 \(s\) 有 \(\pi_*(s) \in \arg\max_{a\in\mathcal{A}(s)} q_{\pi_*}(s,a)\)。

蒙特卡洛探索启动（MCES）维护动作值估计 \(q_k\) 和关于 \(q_k\) 的贪心策略 \(\pi_k\)。在迭代 \(k\)，算法根据分布 \(\sigma_k\) 采样初始状态-动作对，并从该对开始模拟一幕：
\[
\mathcal{E}_k := \bigg\{ s_0, a_0, r_0, s_1, a_1, r_1, \ldots : (s_0,a_0) \sim \sigma_k,\; (s_{t+1}, r_t) \sim p(\cdot,\cdot|s_t,a_t),\; a_t = \pi_k(s_t),\; \forall t\ge 1 \bigg\}.
\]
然后它在出现在 \(\mathcal{E}_k\) 中的对 \((s,a)\) 上更新估计 \(q_k\)：
\[
q_{k+1}(s,a) = q_k(s,a) + \eta_k(s,a)\big(\tilde{q}_k(s,a) - q_k(s,a)\big), \quad (1)
\]
而对于未更新的对，\(q_{k+1}(s,a) = q_k(s,a)\)。这里，\(\eta_k(s,a)\) 是满足 Robbins-Monro 条件 \(\sum_k \eta_k(s,a) = \infty\) 和 \(\sum_k \eta_k^2(s,a) < \infty\) 对每个 \((s,a)\) 的学习率，\(\tilde{q}_k(s,a)\) 是从该对开始的观测回报：
\[
\tilde{q}_k(s_t,a_t) = \sum_{i\ge 0} \gamma^i r_{t+i} \qquad \forall t\ge 0. \quad (2)
\]

我们考虑两种更新规则。
*初始访问*（IV）方法只更新初始对 \((s_0, a_0)\)。
*首次访问*（FV）方法更新一幕中的每个状态-动作对，使用其在该幕中首次出现时的回报。
我们还考虑不同的学习率选择。
*样本平均*（SA）规则设置 \(\eta_k(s,a) = 1/n_k(s,a)\)，其中 \(n_k(s,a)\) 是截至时间 \(k\)（含）\((s,a)\) 被更新的次数。在此规则下，\(q_k(s,a)\) 是截至时间 \(k\) 观测到的 \((s,a)\) 回报的样本平均值。或者，学习率 \(\{\eta_k\}_{k\ge 0}\) 可以独立于 \((s,a)\) 并仅形成一个标量序列。

为确保充分探索，*探索启动*条件要求对所有 \(k\) 和所有 \((s,a)\)，\(\sigma_k(s,a) > 0\)。为确保所有状态-动作对被无限次访问，我们引入更严格的条件：存在常数 \(\sigma_{\min} > 0\)，使得对所有 \(k\) 和所有 \((s,a)\)，\(\sigma_k(s,a) \ge \sigma_{\min}\)。

对于 IV 和 FV，观测回报 \(\tilde{q}_k\) 是 \(q_{\pi_k}\) 的无偏估计 (Singh and Sutton, 1996)。因此，定义零均值扰动 \(v_k(s,a) := \tilde{q}_k(s,a) - q_{\pi_k}(s,a)\)，方程 (1) 可以写为：
\[
q_{k+1}(s,a) = q_k(s,a) + \eta_k(s,a)\big(q_{\pi_k}(s,a) - q_k(s,a) + v_k(s,a)\big). \quad (3)
\]
因此，MCES 是与当前贪心策略相关的策略评估映射的一种随机近似。只要 \(q_k\) 保持在相同策略为贪心的区域，动力学就是固定的。对于策略 \(\pi\)，将此区域定义为：
\[
Q(\pi) \coloneqq \big\{ q: q(s,\pi(s)) = \max_{a\in\mathcal{A}(s)} q(s,a),\; \forall s\in\mathcal{S} \big\}. \quad (4)
\]

在讨论 FV/SA 变体的 MCES 时，Sutton 写道：“几乎难以想象任何比这更简单或更可能收敛的 RL 方法……如果这个最简单的情况仍然开放，我们不太可能在 \(\lambda > 0\) 的任何控制方法上取得进展。”(Sutton, 1999, p. 13)（此处 \(\lambda\) 指 Q(\(\lambda\))、TD(\(\lambda\)) 等中的参数。）Sutton 和 Barto 后来通过将其标记为“强化学习中最基本的开放理论问题之一”来强化该问题的重要性。(Sutton and Barto, 2018, p. 99)

### 1.1 先前的工作

仅仅 Robbins-Monro 条件并不能阻止 IV MCES 收敛到次优解 (Bertsekas and Tsitsiklis, 1996; Wang et al., 2022)。在这些反例中，采样分布强烈偏向非贪心动作（即当 \(q_k(s, a_*) > q_k(s, \bar{a})\) 时，\(\sigma_k(s, a_*) > \sigma_k(s, \bar{a})\) 对每个状态，且 \(q_k(s, a)\) 是样本平均值）。……