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

arXiv:2606.00414v1 Announce Type: new Abstract: 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 Omega(M/b) queries; when the packing realizes deployment-class capacity and b=O(1), this becomes Omega(2^{opt^F(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/eta, where eta is the per-sample KL signal, yielding Omega(2^{opt^F(eps)}/(rho^2Delta^2)) for capacity-order packings with eta=O(rho^2Delta^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.

Source: arXiv cs.LG | 2026-06-02