自由推理维度：假设混合下零碰撞导航的复杂性度量

# 自由推理维度：假设混合下零碰撞导航的复杂性度量  
来源：https://arxiv.org/html/2609.17816  
Luiz Carlos Castro Guedes https://orcid.org/0009-0005-2405-2379  
所属机构：巴西里约热内卢天主教大学计算机科学系  
所属机构：巴西军事工程学院计算机工程部  
邮箱：[[email protected], [email protected]](mailto:[email protected],%[email protected])  
Edward Hermann Haeusler https://orcid.org/0000-0002-4999-7476  
††感谢：Edward H. Haeusler 由 FAPERJ 资助 APQ1 E-26/210.258/2019.249292、CNPq 资助 309287/2023-5 以及 CAPES/COFECUB 88881.878969/2023-01 支持。  

###### 摘要  
Solomonoff 归纳将预测构建为在可计算假设上的混合，通常能识别真实环境。在具有嵌套约束族的有限元强化学习设置中，我们在先前工作中观察到不同的机制：一个价值混合（VM）智能体在未识别真实环境的情况下实现了近最优的零碰撞导航，我们称此现象为**自由推理**。该机制持续存在直至一个显著的密度阈值，超过该阈值性能会下降，且后验模态选择（PMS）变得更优。我们通过**自由推理维度** $d_{\text{FI}}(S,N)$ 形式化了这一行为，这是一个组合度量，用于衡量 VM 智能体在保持轨迹连贯性时可处理的环境复杂度。我们证明了 $d_{\text{FI}}$ 严格小于 VC 维，并与 Natarajan 维（相差一个路径长度因子）相关，捕捉了非可分解损失的成本。一种 PAC 风格的松弛产生了由 $d_{\text{FI}}^{\varepsilon,\delta}$ 驱动的泛化界。我们还定义了互补的 PMS 识别维度，并表明一种混合策略——在首次碰撞前进行平均，之后切换至选择——是最优的，这与 Littlestone 类型维度相关，并通过网格世界实验得到验证。  

###### 关键词  
VC 维、Solomonoff、元 RL、贝叶斯模型平均、组合维度、PAC-Bayes、在线学习、安全探索。  

## 1 引言  
元强化学习[5, 2, 8, 11]的一个核心设计问题是智能体应如何利用对候选环境的有限贝叶斯信念。两个经典答案尤为突出。  
*价值混合（VM）智能体*在信念 $\xi$ 下，对 $N$ 个假设环境的最优 $Q$ 函数 $Q_1, \ldots, Q_N$ 进行平均，并相对于 $\bar{Q} = \sum_i \xi(\nu_i) Q_i$ 采取贪心行动；这是对 Solomonoff 风格通用混合[9, 6]的有限构造性近似，受限于环境模型的假设类别，并对应于风险中性的贝叶斯自适应控制规则[4]。  
相比之下，*后验模态采样（PMS）智能体*在每一步选择最大后验概率（MAP）环境并遵循其策略，仅在碰撞时更新信念。平均与选择是在后验不确定性下行动的决定性张力，我们的实验表明，尽管使用相同的后验，这两种策略在动作选择设置中的表现非常不同。  
在该设置的近期工作中，我们识别出两种模式相对性能的显著相变。当候选环境形成一个*嵌套*族（即环境在分类为障碍物的单元格数量上不同，限制性更强的环境包含限制性较弱环境的所有障碍物）时，已证明 VM 智能体能够从起始状态导航到目标状态，*没有任何碰撞且未识别真实环境*，直至一个显著的密度阈值。我们将该机制称为*自由推理*，即智能体在不支付通常的识别成本的情况下收集价值，同时信念在整个轨迹中近似均匀。超过某个密度阈值后，混合在导航上变得不连贯，智能体发生振荡或碰撞，PMS 开始优于 VM。  
经验上，该边界异常稳定：在从 $10 \times 5$ 到 $100 \times 50$ 的不同网格尺寸下，$\rho_c \approx 0.7$。该阈值的经验行为具有组合容量度量的特征。它是一个尖锐的阈值转变，而非渐进式的；它随状态空间线性扩展；并分隔了学习者可靠正确与可靠错误的两种机制。然而，它与学习理论中任何现有维度都不匹配，原因有二。  
首先，损失函数（轨迹成功）是*非可分解的*：在每个状态的局部正确性是全局成功的必要但不充分条件，因此 Vapnik-Chervonenkis 和 Natarajan 风格的逐点论证并不适用[10, 7]。  
其次，对手是*非自适应的*：环境在轨迹开始前就已确定，这与 Littlestone 风格的错误界限维度所假设的自适应对手形成对比。  
本文以经验相变为起点，发展了自由推理的复杂度理论基础。我们的核心问题是：*自由推理的组合维度是什么？它在现有层次结构中处于何种位置？*  

**贡献**。我们做出了以下贡献：  
1. 引入**自由推理维度** $d_{\text{FI}}(S,N)$，定义为在所有 $N$ 级嵌套分配下可被 FI 打散的约束单元格的最大集合大小（定义6）。  
2. 证明 $d_{\text{FI}} \leq |\mathcal{S}|$，当 $|\mathcal{S}| > N+2$ 且 $N \geq 2$ 时，$d_{\text{FI}}(S,N)$ 严格介于 $\lfloor \log_2 N \rfloor$ 与 $N-1$ 之间。  
3. 给出 $d_{\text{FI}}$ 的封闭形式：$d_{\text{FI}}(S,N) = \min\left(N-1, \left\lfloor \frac{|\mathcal{S}|-1}{N-1} \right\rfloor\right)$，当 $|\mathcal{S}| > N+2$ 时。  
4. 推导 PAC-Bayes 泛化界：对任意 $\varepsilon > 0$ 与置信度 $\delta > 0$，定义松弛维度 $d_{\text{FI}}^{\varepsilon,\delta}(S,N)$，使得对 $m$ 个独立嵌套分配的随机样本，经验失败率 $\hat{p}_m = \frac{1}{m} \sum_{i=1}^m \mathbf{1}\{\varepsilon_{\text{margin}}(\mathcal{V}_{C,\ell_i}) > \varepsilon\}$ 满足：以至少 $1-\delta$ 的概率，对新的随机分配 $\ell_{\text{new}}$，有  
   $\Pr_{\ell_{\text{new}}}[\varepsilon_{\text{margin}}(\mathcal{V}_{C,\ell_{\text{new}}}) > \varepsilon] \leq \hat{p}_m + \sqrt{\frac{d \log mN + \log(1/\delta)}{2m}}$，  
   其中 $d = d_{\text{FI}}^{\varepsilon,\delta}(S,N)$。  
5. 定义互补的 PMS 识别维度 $d_{\text{PMS}}(S,N) = \max_{\mathcal{V},\nu^*} B_{\text{PMS}}(\mathcal{V},\nu^*)$，并证明 $\lfloor \log_2 N \rfloor \leq d_{\text{PMS}}(S,N) \leq N-1$。  
6. 表明最优策略是混合策略：在首次碰撞前运行 VM，之后切换至 PMS，其性能由 $d_{\text{FI}}$ 与 $d_{\text{PMS}}$ 的连续过渡带控制。  

## 2 问题设置与核心现象  
考虑一个网格世界导航任务，其中 $\mathcal{S}$ 为单元格集合，$N$ 个环境假设 $\{\nu_1, \ldots, \nu_N\}$ 形成嵌套族：每个 $\nu_i$ 将 $\mathcal{S}$ 的一个子集标记为障碍物，且若 $i < j$，则 $\nu_i$ 的障碍物集合是 $\nu_j$ 的子集。智能体从起点出发，需导航至终点，碰撞定义为进入任一环境下的障碍单元格。  

**价值混合智能体** 在每一步根据信念 $\xi$ 对 $Q$ 函数取平均并采取贪心行动：$\bar{Q} = \sum_i \xi(\nu_i) Q_i$。  
**后验模态采样智能体** 则遵循 MAP 假设 $\hat{\nu}_t = \arg\max_\nu \xi_t(\nu)$ 的策略。  

**自由推理现象**：在嵌套族中，VM 智能体在达到某个密度阈值 $\rho_c$ 之前，能够实现零碰撞导航，且无需识别真实环境。该阈值在不同网格尺寸下稳定在 $\rho_c \approx 0.7$ 附近。  

## 3 自由推理维度  
**定义 6**：自由推理维度 $d_{\text{FI}}(S,N)$ 定义为在所有 $N$ 级嵌套分配下可被 FI 打散的最大约束单元格集合的大小。  

**定理 1**：对 $|\mathcal{S}| > N+2$ 与 $N \geq 2$，有  
$d_{\text{FI}}(S,N) = \min\left(N-1, \left\lfloor \frac{|\mathcal{S}|-1}{N-1} \right\rfloor\right)$。  

**解释**：$d_{\text{FI}}$ 衡量了 VM 智能体在保持轨迹连贯性时可处理的环境复杂度，且严格小于 VC 维。它与 Natarajan 维相关，但受路径长度因子影响，以捕捉非可分解损失的成本。  

## 4 PAC-Bayes 泛化界  
**定义 7**：松弛自由推理维度 $d_{\text{FI}}^{\varepsilon,\delta}(S,N)$ 使得对 $m$ 个独立嵌套分配的随机样本，经验失败率 $\hat{p}_m$ 满足上述泛化界。  

**定理 5.1**：该界是自由推理的统计学习理论陈述：$d_{\text{FI}}^{\varepsilon,\delta}$ 控制需测试的嵌套方案数量，以便以置信度 $1-\delta$ 和容差 $\varepsilon$ 证明 VM 智能体将在未测试的嵌套上连贯导航。收敛率为 $O(1/\sqrt{m})$，是典型的 PAC 缩放。  

## 5 相变处的分级容量  
**定理 5.2（相变）**：对 $N=10$ 的网格世界，连贯性得分 $\mathcal{C}$ 在粗密度分辨率（$\Delta\rho \approx 0.1$）下表现出尖锐阈值：在所有测试的网格尺寸下，从 $\mathcal{C}=0$ 单步跳至 $\mathcal{C} \approx -0.43$。在更细分辨率（$\Delta\rho = 0.025$）下，该跳变解析为宽度约 $0.10–0.15$ 的连续过渡带，其中 $d_{\text{FI}}^{\varepsilon,\delta}(S,N)$ 是 $\varepsilon$ 的严格递增函数。  

## 6 PMS 识别维度与 VM-PMS 对偶性  
**定义 10**：PMS 识别维度 $d_{\text{PMS}}(S,N) = \max_{\mathcal{V},\nu^*} B_{\text{PMS}}(\mathcal{V},\nu^*)$，即 PMS 在真实环境 $\nu^*$ 中遭受的最坏情况碰撞数。  

**命题 3**：$\lfloor \log_2 N \rfloor \leq d_{\text{PMS}}(S,N) \leq N-1$。  

**VM-PMS 对偶性**：$(d_{\text{FI}}, d_{\text{PMS}})$ 提供了互补的复杂度度量：$d_{\text{FI}}$ 以约束单元格为单位，衡量 VM 的*零碰撞*容量；$d_{\text{PMS}}$ 以碰撞为单位，衡量 PMS 在零碰撞导航不可行时的*识别成本*。连续过渡带将 $d_{\text{FI}}$ 附近区域细分为梯度。  

**定理 6.1（分级混合策略）**：对容差 $\varepsilon \geq 0$，混合策略（运行 VM 并仅在碰撞率超过操作密度下过渡带的预期速率时切换至 PMS）实现的碰撞数 $B_{\text{hybrid}}(\varepsilon)$ 满足：  
$$
B_{\text{hybrid}}(\varepsilon) \leq
\begin{cases}
0 & \text{若 } \|C\| \leq d_{\text{FI}}, \\
\varepsilon \cdot \|P^*\| & \text{若 } d_{\text{FI}} < \|C\| \leq d_{\text{FI}}^{\varepsilon,\delta}, \\
1 + d_{\text{PMS}} & \text{若 } \|C\| > d_{\text{FI}}^{\varepsilon,\delta}.
\end{cases}
$$  
零容差设置下的确定性“首次碰撞即切换”规则是 $\varepsilon \to 0$ 的极限情况。  

## 7 与在线学习理论的联系  
**随机化 Littlestone**：VM 智能体在专家建议意义上是随机学习者：$\bar{Q}$ 产生类似于预测 $p_i \in [0,1]$ 的软动作偏好，对应于随机化 Littlestone 维。  

## 8 实验验证  
我们在不同网格尺寸（$10 \times 5$ 到 $100 \times 50$）上验证了理论预测。  
**相变**：连贯性得分 $\mathcal{C}$ 在 $\rho_c \approx 0.7$ 附近表现出尖锐阈值。  
**泛化界**：在 100% 的信息性配置中，即使 $\hat{p}_m \in (0.2, 0.8)$，Hoeffding 形式也成立。  
**混合策略**：实验表明，在过渡带内，混合策略显著优于纯 VM 或纯 PMS 策略。  

## 9 结论  
本文提出了自由推理维度及其松弛形式，为嵌套环境下 VM 智能体的零碰撞导航能力提供了组合度量。通过与 PMS 识别维度的对偶性，我们建立了混合策略的最优性，并将该框架与 PAC-Bayes 泛化界和在线学习理论联系起来。未来工作可将此扩展至非嵌套环境与其他导航任务。