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

arXiv: https://arxiv.org/abs/2606.00414 · HTML: https://mlsanity.com/paper/2606.00414/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 26 references that are in the map.
- First posted on arXiv 29 May 2026.

## Builds on (most cited first, 14 of 14)

- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously](https://mlsanity.com/paper/1801.01489/) (2018)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [The Effects of Reward Misspecification: Mapping and Mitigating Misaligned Models](https://mlsanity.com/paper/2201.03544/) (2022)
- [Predictive Multiplicity in Classification](https://mlsanity.com/paper/1909.06677/) (2019)
- [On the Existence of Simpler Machine Learning Models](https://mlsanity.com/paper/1908.01755/) (2019)
- [Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12909/) (2020)
- [One Solution is Not All You Need: Few-Shot Extrapolation via Structured MaxEnt RL](https://mlsanity.com/paper/2010.14484/) (2020)
- [BACKDOORL: Backdoor Attack against Competitive Reinforcement Learning](https://mlsanity.com/paper/2105.00579/) (2021)
- [Rashomon Capacity: A Metric for Predictive Multiplicity in Classification](https://mlsanity.com/paper/2206.01295/) (2022)
- [Cautious Reinforcement Learning with Logical Constraints](https://mlsanity.com/paper/2002.12156/) (2020)
- [An Empirical Evaluation of the Rashomon Effect in Explainable Machine Learning](https://mlsanity.com/paper/2306.15786/) (2023)
- [Poisoning Deep Reinforcement Learning Agents with In-Distribution Triggers](https://mlsanity.com/paper/2106.07798/) (2021)

## Abstract (arXiv)

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(2Hopt^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 Omega(2Hopt^cF(eps)/(ρ2Delta2)) for capacity-order packings with β=O(ρ2Delta2). 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.