arXiv:2606.00414cs.LG2026-06

在近优策略中区分行为差异极难,可能需要指数级查询量。

Auditing Near-Optimal Policies Can Be Exponentially Hard: Conditional Query Lower Bounds via Occupancy Rashomon Capacity

  • 用占据测度的Rashomon容量定义审计难度,聚焦行为等价类。
  • 精确查询下,若策略有稀疏局部特征,则需至少Ω(M/b)次查询。
  • 适用于高容量复杂环境的可信审计,对强化学习安全评估意义重大。

当多个强化学习策略达到近似最优回报时,事后审计者需在行为迥异但回报等价的策略间做出区分。本文通过占据测度的Rashomon容量形式化该现象:以审计部署类为基准,计算近优占据区域的度量熵。由于占据测度仅识别行为等价类,我们区分精确局部查询与噪声样本查询。主要结果为条件性:若审计类包含2/H-分离的近优填充集,且其局部签名b-稀疏,则精确局部查询审计至少需Ω(M/b)次查询;当填充集达到部署类容量且b=O(1)时,下界变为Ω(2^{Hopt^F(ε)})。我们构造了一个有限折扣隐藏分支MDP实现此界,并给出精确贝叶斯成功定律。对于噪声隐藏触发测试,证明混合下界为M/β,其中β为每样本KL信号,当β=O(ρ²Δ²)时得Ω(2^{Hopt^F(ε)}/(ρ²Δ²))。此外提供静态目标识别信息下界、兼容转录的查询覆盖验证上界,以及一个正则化器,当存在可信参考占据测度时其审计容量坍缩。受控基准区分稀疏签名实例与高容量负例,揭示精确审计易难差异,并将噪声触发律映射至后处理连续控制与视觉强化学习审计场景。

原文摘要 · Abstract (English)

When many reinforcement-learning policies achieve near-optimal return, a post-hoc auditor may have to distinguish among many behaviorally distinct but return-equivalent policies. We formalize this phenomenon through an occupancy-measure analogue of Rashomon capacity: the metric entropy of the near-optimal occupancy region, computed relative to an audited deployment class. Because occupancy measures identify behavior only up to occupancy equivalence, we formulate auditing at the occupancy-class level and distinguish exact local-query oracles from noisy sample-query oracles. Our main exact-query result is conditional: if the audited class contains a $2/H$-separated near-optimal packing whose local signatures are $b$-sparse, then exact local-query auditing requires $Ω(M/b)$ queries; when the packing realizes deployment-class capacity and $b=O(1)$, this becomes $Ω(2^{\Hopt^\cF(\eps)})$. We give a finite discounted hidden-branch MDP attaining this bound and show the exact Bayes success law. For noisy hidden-trigger testing, we prove a mixture lower bound of order $M/β$, where $β$ is the per-sample KL signal, yielding $Ω(2^{\Hopt^\cF(\eps)}/(ρ^2Δ^2))$ for capacity-order packings with $β=O(ρ^2Δ^2)$. We also provide a static target-recognition information lower bound, a transcript-compatible oracle-cover verification upper bound, and a canonical occupancy regularizer whose regularized audited capacity collapses when a trusted reference occupancy is available. Controlled benchmarks distinguish positive sparse-signature instances from high-capacity negative controls where exact auditing is easy, and map the noisy-trigger law to post-processed continuous-control and visual-RL auditing regimes.

强化学习审计复杂性策略区分

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。