技术摘要：外生上下文 MDP 中学习的 Minimax PAC 界

1. 问题设定

本文研究了在**带有外生 i.i.d. 上下文的表格化折扣马尔可夫决策过程（MDPs）**中学习的样本复杂度。该模型由元组 $\mathcal{M} = (\mathcal{X}, \mathcal{Z}, \mathcal{A}, P, r, \mu, \gamma)$ 定义，其中：

• $\mathcal{X}$ 是有限的可控状态空间。
• $\mathcal{A}$ 是有限的动作空间。
• $\mathcal{Z}$ 是有限的上下文空间。
• $\gamma \in [0, 1)$ 是折扣因子。
• $P: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to \Delta(\mathcal{X})$ 是转移核。
• $r: \mathcal{X} \times \mathcal{A} \times \mathcal{Z} \to [0, 1]$ 是奖励函数。
• $\mu$ 是未知的上下文分布。

在每个时间步 $t$，上下文 $Z_t$ 从 $\mu$ 中独立抽取并向智能体展示。智能体选择 $A_t$，接收奖励 $r(X_t, A_t, Z_t)$，并转移到 $X_{t+1} \sim P(\cdot | X_t, A_t, Z_t)$。至关重要的是，下一个上下文 $Z_{t+1}$ 独立于智能体的动作和当前状态，仅取决于 $\mu$。

学习目标包括策略评估（PE）、最优价值估计（BVE）以及最优策略提取（BPE）。样本复杂度由一对 $(n_{\text{learn}}, m_{\text{query}})$ 表示，分别代表在离线学习阶段进行的 Oracle 调用次数以及在决策时（查询）阶段进行的调用次数。本文考虑了两种情形：

1. 已知动力学（Known Dynamics）： $P$ 和 $r$ 已知；仅 $\mu$ 未知。
2. 完全未知（Fully Unknown）： $\mu$ 和 $P$ 均未知。

2. 方法论

2.1 核心洞察：平均价值函数

本文的核心方法论贡献是将问题从增广空间 $\mathcal{X} \times \mathcal{Z}$ 约简到受控状态空间 $\mathcal{X}$。作者定义了平均价值函数 $\bar{V}(x) := \mathbb{E}_{Z \sim \mu}[V(x, Z)]$。
由于下一个上下文是根据 $\mu$ 独立抽取的，因此平均价值 $\bar{V}^\star$ 的贝尔曼最优方程仅依赖于对 $\mu$ 进行平均后的转移核：
$$\bar{V}^\star(x) = \mathbb{E}_{Z \sim \mu} \left[ \max_{a \in \mathcal{A}} \left( r(x, a, Z) + \gamma \sum_{x'} P(x' | x, a, Z) \bar{V}^\star(x') \right) \right]$$
这种形式化方法允许学习者估计一个 $\mathbb{R}^{|\mathcal{X}|}$ 中的向量，而不是 $\mathbb{R}^{|\mathcal{X}||\mathcal{Z}|}$ 中的向量，从而有效地将复杂度与上下文空间的大小 $|\mathcal{Z}|$ 解耦。

2.2 算法框架：方差缩减减半法

本文采用了一种方差缩减价值迭代方案（改编自 Sidford 等人，2019），用于估计平均价值函数。该算法分为两个阶段运行：

1. 离线阶段（锚点估计）： 算法计算应用于初始价值估计的贝尔曼算子的高概率下界（锚点）。这需要大量的样本来控制经验均值的方差。
2. 在线/迭代阶段（方差缩减更新）： 随后的迭代仅估计当前贝尔曼回溯与锚点之间的差异。通过重复使用相同的样本来计算差异项，方差得到了显著降低，从而允许更小的每轮迭代样本量。

该算法使用一种“减半”策略，反复调用一个子程序（HALFERR），将误差界 $u$ 不断减半，直到达到目标精度 $\epsilon$。

2.3 处理未知动力学

在完全未知的情形下，算法无法即使在给定采样上下文的情况下也无法精确计算贝尔曼回溯。相反，对于每一个采样的上下文 $Z$，算法抽取一个转移样本 $X' \sim P(\cdot | x, \pi(x, Z), Z)$，以形成对回溯的无偏估计。这引入了一个与转移核相关的额外方差项，该项通过考虑上下文和转移随机性的鞅分解得到了严格限制。

3. 关键结果

3.1 已知动力学，上下文分布未知（$P, r$ 已知，$\mu$ 未知）

当转移核和奖励已知时，本文证明样本复杂度与上下文空间的大小 $|\mathcal{Z}|$ 无关。

• 复杂度： 算法实现的复杂度为 $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(\beta^3/\epsilon^2), 0)$，其中 $\beta = (1-\gamma)^{-1}$。
• 最优性： 文中证明了 $\Omega(\beta^3/\epsilon^2)$ 的 Minimax 下界，表明该上界在对数因子范围内是紧致的。
• 启示： 学习者不需要为每个 $(x, z)$ 对估计价值；估计平均价值 $\bar{V}$ 就足够了。查询阶段不需要额外的样本（$m_{\text{query}}=0$），因为从 $\bar{V}$ 到 $V(x, z)$ 的提升是一个使用已知 $P$ 和 $r$ 的确定性贝尔曼回溯。

3.2 在完美单步前瞻中的应用

该框架被应用于完美单步转移前瞻设置（即智能体在行动前能观察到所有动作的所有可能下一状态）。

• 该设置被证明是外生上下文 MDP 的一个特例，其中上下文空间是所有可能的转移张量的集合。
• 结果得出样本复杂度为 $\tilde{O}(\beta^3/\epsilon^2)$ 次前瞻样本。
• 就单个表格化转移而言，这对应于 $\tilde{O}(\beta^3 |\mathcal{X}||\mathcal{A}|/\epsilon^2)$，相比 Lu 等人 (2025) 的结果，通过一个 $\beta$ 因子改进了界限。

3.3 完全未知情形（$P$ 和 $\mu$ 均未知）

在动力学和上下文分布均未知的场景下，本文侧重于策略评估（PE）。

• 复杂度： 算法实现的复杂度为 $(n_{\text{learn}}, m_{\text{query}}) = (\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2), \tilde{O}(\beta^2/\epsilon^2))$。
• 权衡： 离线阶段学习平均价值 $\bar{V}^\pi$（每个上下文样本消耗 $|\mathcal{X}|$ 次转移）。查询阶段使用新鲜样本来估计实现状态 $(x, z)$ 的最终单步转移期望。
• 下界： 本文证明了匹配的下界，表明：
  • $m_{\text{query}} = \Omega(\beta^2/\epsilon^2)$ 对于决策时精度是必要的。
  • $n_{\text{learn}} + |\mathcal{X}| m_{\text{query}} = \Omega(|\mathcal{X}|\beta^3/\epsilon^2)$ 对于离线学习是必要的。
• 意义： 即使在完全未知的情形下，复杂度仍然与 $|\mathcal{Z}|$ 无关。未知的动力学并不会强制在增广空间上进行估计；它们仅在从 $\bar{V}$ 到 $V(x, z)$ 的决策时“提升”过程中引入随机性。

4. 重要性与主张

本文声称提供了学习外生上下文 MDP 的首个 Minimax 最优 PAC 界。其主要贡献包括：

1. 与上下文大小解耦： 它证明了可以避免大规模上下文空间带来的统计代价。样本复杂度取决于受控状态空间 $|\mathcal{X}|$，而非上下文空间 $|\mathcal{Z}|$。
2. 最优速率： 推导出的速率（已知动力学下的 $\tilde{O}(\beta^3/\epsilon^2)$ 以及完全未知下的 $\tilde{O}(|\mathcal{X}|\beta^3/\epsilon^2)$）在对数因子范围内被证明是 Minimax 最优的。
3. 统一框架： 该框架涵盖并改进了现有的完美单步前瞻结果，并对离线/在线样本权衡进行了严谨的分析。

作者指出，虽然下界在纯在线点（$n_{\text{learn}}=0$）和可重用 Oracle 点（他们提出的算法）处是紧致的，但对于中间权衡的紧致性仍是一个开放性问题。此外，由于在利用转移样本估计关于动作的最大值时处理选择偏差存在困难，将这些结果扩展到完全未知情形下的最优策略提取（BPE）被留作未来的工作。