acceptodds
Under review as a conference paper at ICLR 2027

When Occupancy Multiplicity Makes Auditing Hard: A Conditional Query Lower Bound

Abstract

Near-optimal reinforcement-learning policies can have different reachable behavior, but their number alone does not determine how difficult they are to audit. We define occupancy Rashomon capacity as the metric entropy of near-optimal discounted state-action occupancies within a declared deployment class. A separated family of policies with -sparse exact local signatures requires state queries for occupancy identification. Expressing this bound exponentially in capacity requires the family to realize the cover number; it is the same search bound in different units. A finite hidden-branch MDP attains the bound, whereas a shortest-path family has high capacity and admits efficient path-following audits. We derive a separate root-reset episode law, a noisy-trigger lower bound of for per-sample KL signal , and reference-policy KL conditions for occupancy-capacity collapse. Learned SAC and DQN families provide finite, pipeline-relative diagnostics of occupancy separation and local agreement. These diagnostics distinguish certified separation from probe-dependent tolerance sparsity and do not establish uniform sparsity or exponential auditing hardness in deployed systems.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, policy auditing, Rashomon capacity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_EQWdOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies when multiplicity among near-optimal reinforcement-learning policies makes occupancy auditing difficult. It defines deployment-class occupancy Rashomon capacity through a covering number of discounted state-action occupancies. Its main result establishes an Ω(M/b) exact-query lower bound for an occupancy-separated family of M policies with b-sparse exact local signatures. A hidden-branch MDP realizes the bound, while a shortest-path construction demonstrates that high occupancy capacity can coexist with efficient identification. Additional results address root-reset episode access, noisy-trigger testing, and reference-policy regularization. The empirical component reports finite-family AntMaze diagnostics of projected occupancy separation, probe-local disagreement, access restrictions, and regularization. The paper explicitly distinguishes these diagnostics from certification of the main theorem’s uniform exact-sparsity assumption.

Critical strengths
  1. Clear separation of multiplicity from information structure. The paper carefully distinguishes occupancy covering numbers, candidate counts, and the information revealed by local queries. The contrasting hidden-branch and shortest-path constructions make the central point concrete: a large near-optimal family alone does not imply difficult auditing. The explicit qualifications surrounding the capacity reformulation and finite-probe diagnostics improve the conceptual reliability of the work.

  2. Coherent theoretical treatment of different access models. The background-transcript argument, the root-reset identification law, and the stopped-trajectory KL argument are clearly presented and appear internally consistent. In particular, distinguishing fixed-error identification from full coupon collection prevents an incorrect extra logarithmic factor. These results provide useful reference examples for reasoning about auditing assumptions and access costs.

Critical weaknesses
  1. The theoretical contribution beyond classical identification arguments is limited. Theorem 5 obtains its lower bound from the assumption that each background response can eliminate at most b candidates; occupancy separation converts approximate occupancy recovery into index identification. The paper correctly acknowledges that expressing this search bound exponentially in capacity does not strengthen it, but the additional RL-specific insight remains relatively modest. The main hard construction also uses H = 16M, a shrinking auditing radius, and actions with identical rewards and transitions. It therefore establishes a valid existence result without demonstrating hardness at fixed resolution or for differences in state trajectories. A more direct comparison with membership-query learning and teaching/disagreement complexity would help establish the contribution’s scope.

  2. The empirical certification and connection to the theory are insufficiently established. Section 8.2 reports a simultaneous projected-occupancy error radius of η_d = 0.04, but Appendices E–F do not specify enough of the sampling and confidence procedure to verify this guarantee, including sample counts, trajectory dependence, truncation, and simultaneous coverage. The return-interval construction is similarly underspecified. These details are consequential because the reported certified packing sizes depend on them. Moreover, tolerance agreement on 512 probes does not establish the theorem’s uniform exact-sparsity premise, as the authors acknowledge. The access experiment evaluates exact checkpoint identification over the full candidate pool, which is not directly equivalent to occupancy recovery at the stated tolerance. Thus, the experiments provide suggestive diagnostics, but do not yet demonstrate the proposed hardness mechanism or its practical predictive value.

Questions for authors
  1. Clarification of statistical certification: What exact estimators, sample counts, and concentration or confidence procedures produce η_d = 0.04 with the stated simultaneous coverage? How are trajectory dependence and truncation handled? Please also specify the return-interval construction and report representative interval widths. This would directly affect my assessment of the certified-packing claims.

  2. Clarification of experimental implementation: How are the 50 candidates constructed from the five training seeds, and how are checkpoints selected? How are continuous-action TV distances and the background distribution in Equation 9 computed? What state-selection and reset-scheduling rules are used in the access comparison? These details are needed to interpret and reproduce the reported results.

  3. Clarification of contribution and evidence: Which result do the authors regard as the principal advance beyond classical query identification, and how does it relate to existing teaching/disagreement complexity measures? Also, Section 8.2 mentions learned MinAtar/DQN families, but I could not locate their corresponding learned-family results; are these available in supplementary material?

These are clarification requests about the current submission. Approximate-signature theory or additional intervention experiments would be possible future directions, rather than prerequisites I expect the authors to complete during rebuttal.

5 comments
AuthorsOpenReview ↗

Response to Reviewer EQWd – Part 1

Thank you for the review. The table summarizes our answers, and the sections after it give every construction and number.

Your pointOur answerWhere in the revision
Scope of the theory, and the fixed-resolution questionA new theorem: at resolution 1/H1/H, separated families with bb-sparse exact signatures have fewer than bH2+1bH^2+1 members, and a family of trajectory deviations attains this order.Appendix K, Lemma 20, Propositions 21–22
Relation to query learningTheorem 5 applies the extended-teaching-dimension argument to average success under a uniform prior, and the hidden-branch family has teaching dimension one.Related Work
The packing certificate needs an explicit statistical constructionAppendix J gives the estimator, sample counts, independence, truncation, return intervals, roster, action TV, and background, with a radius that holds by proof.Appendix J, Proposition 19, Table 13
Return intervals and joint confidence20,000 independent returns per checkpoint give a simultaneous half-width of 0.0144, and the joint confidence levels are stated.Appendix J
The learned-family auditA fresh audit under the certificate finds a 23-member separated packing among 30 near-optimal policies at K=50K=50. The submitted analysis is kept as a separate record.Section 8.2, Tables 2–4; Appendix L
The access studyExact identification falls from 0.861 with fixed-bank resets to 0.582 with ordinary trajectories, and a new score measures occupancy recovery.Section 8.2, Table 3
Discrete-action scopeThe DQN claim is removed, and the MinAtar calculation is labeled analytic.Abstract; Section 8

Scope of the theoretical contribution

Theorem 5 uses the classical search argument by design, and the revision answers the fixed-resolution question with a new theorem, Proposition 21 in a new final Appendix K. The hidden-branch MDP uses H=16MH=16M, a shrinking radius, and actions with identical rewards and transitions, and Proposition 21 shows that this growth is forced. At resolution 1/H1/H, every 2/H2/H-separated family with bb-sparse exact signatures has fewer than bH2+1bH^2+1 members. When all actions share transitions, as in the hidden-branch MDP, it has fewer than bH+1bH+1. The shrinking radius of Theorem 7 is therefore necessary, not a weakness of that construction. At a fixed resolution, Theorem 5 can never require more than (1−δ)H2(1-\delta)H^2 exact queries, whatever bb.

Proposition 22 attains this order with a family whose deviations change state trajectories. A root sends the agent to one of ⌊H/5⌋\lfloor H/5\rfloor chains of length ⌊(H−1)log⁡2⌋\lfloor(H-1)\log2\rfloor, and each policy leaves the background at one chain state for a private absorbing state. This gives about 0.139H20.139H^2 optimal policies with 1-sparse signatures, pairwise occupancy TV above 2/H2/H. Exact sparse signatures can therefore make occupancy auditing at most quadratically hard in the horizon at a fixed resolution. Larger hardness needs weak signals, as in Theorem 10, whose sample requirement grows as 1/β1/\beta. The proof rests on an occupancy coupling for discounted MDPs (Lemma 20), which extends Lemma 3 of Achiam et al. (2017) to state–action occupancies. A deviation that only relabels an action moves the occupancy by at most its own visitation mass, while one that redirects the trajectory moves it by up to HH times that mass.

In exact learning with membership queries, the extended teaching dimension lower-bounds the number of queries (Hegedűs, 1995). Theorem 5 applies its worst-case background labeling to the average success under a uniform prior, as for the class of singletons (Angluin, 1988). Separation lifts that bound from index identification to occupancy recovery at radius 1/H1/H. By contrast, the hidden-branch family has teaching dimension one (Goldman and Kearns, 1995), because a single branch state identifies each policy to a teacher who knows it. Its difficulty therefore lies with an auditor who must search. The revision adds this comparison to the Related Work section, and the reply to Reviewer Q6kS lists the results that use RL structure beyond the search argument.

AuthorsOpenReview ↗

Response to Reviewer EQWd – Part 2

The packing certificate

The numerical packing certificate needs a more explicit statistical construction. Page 8 reports 200 return rollouts per checkpoint, five training seeds, projection settings, 512 probes, and familywise error levels. Appendix E proves the packing implication conditional on simultaneous occupancy-error bounds. The submitted text did not specify the occupancy estimator, independent sample count, truncation rule, or return-interval construction behind the reported ηd=.04\eta_d=.04. We therefore specify an explicit construction under which the radius holds by proof, and we report a fresh audit of the trained checkpoints under it. The rerun uses its own projection, roster, and confidence family, and it is not used to reconstruct the statistical provenance of the submitted value of 0.04. Its numbers replace the submitted ones. Section 8 now reports the rerun, and Appendix L keeps the submitted analysis, with its declared radius, as a separate record.

Estimator, sample counts, dependence, and truncation

For each trajectory, draw TT independently with Pr⁡(T=t)=(1−γ)γt\Pr(T=t)=(1-\gamma)\gamma^t and record only ϕ(ST,AT)\phi(S_T,A_T) and the reward at TT. For a fixed JJ-bin projection, these are independent categorical samples from the projected discounted occupancy pip_i. With NiN_i trajectories per policy and KK policies,

\le \eta_i = \min\left\\{1,\sqrt{\frac{J\log 2+\log(K/\delta_d)}{2N_i}}\right\\}$$ holds simultaneously with probability at least $1-\delta_d$ (Proposition 19 in Appendix J). For each subset of bins, Hoeffding bounds its empirical mass error by $\exp(-2N_i\eta_i^2)$. TV is the largest positive subset-mass discrepancy, and union bounds over at most $2^J$ subsets and $K$ policies yield the display. Cross-policy independence is unnecessary, but within-policy trajectories must be independent. Several time steps from one trajectory cannot be treated as independent observations. Geometric stopping with no cap needs no truncation correction. If sampling must stop at time $L$, late draws enter a cemetery bin, the alphabet grows by one, and the radius grows by $\gamma^L$. The audit has four regularization banks, at $\lambda\in\{0,0.01,0.05,0.10\}$, of 50 checkpoints each, and each bank's confidence event covers its $K=50$ checkpoints. Each checkpoint receives 20,000 independent trajectories, and the 15- and 30-checkpoint pools are nested subsets that use the bank's bounds. For the 64-bin projection, $$\eta_d=\sqrt{\frac{64\log2+\log(50/.025)}{2(20{,}000)}}=0.0360.$$ A radius of 0.04 would need at least 16,239 observations per checkpoint, and the four banks cost about 400 million sampled states at $\gamma=.99$. With $H=100$, the radii .005, .01, and .02 equal $0.5/H$, $1/H$, and $2/H$. At $r=.01$, a certified packing edge requires an empirical TV above $2r+2\eta_d=0.0921$. ### Return intervals and joint confidence The geometric-time draw also gives $r(S_T,A_T)\in[0,1]$, an unbiased estimate of normalized discounted return without truncation. Hoeffding and a union bound over the 50 checkpoints of a bank give the simultaneous half-width $$h_V=\sqrt{\frac{\log(2\cdot50/.025)}{2(20{,}000)}}=0.0144,$$ and the intervals are $L_i=\bar G_i-h_V$ and $U_i=\bar G_i+h_V$. The occupancy and return estimators may share trajectories, because their joint bound needs no independence between them. With $\delta_d=\delta_V=.025$, the two events hold jointly with probability at least .95 for each bank. Adding the numerical action-TV allocation below gives at least .925 per bank, and at least .70 for all four banks together. The submitted 200 return rollouts cannot support the reported classes under a conservative interval. At $K=50$, $n_i=200$, and $\delta_V=.025$, the Hoeffding half-width is 0.143997. The inner-class rule requires $U_\star-L_i\le\epsilon$, but $U_\star-L_i\ge2h_i\approx0.288$ for every candidate, so this interval gives an empty inner class at $\epsilon=.05$. The submission specifies only a valid bounded-return method with a family-wise allocation (Appendix C), not the interval behind the reported inner classes. The new construction replaces it with 20,000 independent returns per checkpoint, and Section 8.2 now uses these intervals.
AuthorsOpenReview ↗

Response to Reviewer EQWd – Part 3

Roster, projection, TV, and background

Training seeds 0–4 contribute checkpoints every 100,000 steps through 1,000,000. The 15-checkpoint pool uses each seed's last three checkpoints, the 30-checkpoint pool its last six, and the 50-checkpoint pool all ten. The roster is repeated for each λ\lambda, and checkpoint hashes and training configurations identify the candidates. The projection crosses four spatial macroregions with 16 full-action-vector prototypes fitted on a separate calibration split. Geometry-based cutpoints x0,y0x_0,y_0 define bxy(s)=21{x≥x0}+1{y≥y0}b_{xy}(s)=2\mathbf1\{x\ge x_0\}+\mathbf1\{y\ge y_0\}, the action is assigned to its nearest prototype c(a)c(a) under frozen normalization with ties broken by index, and ϕ(s,a)=16bxy(s)+c(a)\phi(s,a)=16b_{xy}(s)+c(a) has 64 bins.

For densities pp and qq,

=\mathbb E_{A\sim(p+q)/2} \frac{|p(A)-q(A)|}{p(A)+q(A)},$$ and the integrand lies in $[0,1]$. With 16,384 fresh draws per comparison over the $K\times512$ candidate–probe comparisons of a pool and $\delta_{\rm TV}=.025$, the simultaneous numerical half-width is 0.0211 at $K=50$. Tolerance decisions use the resulting upper and lower bounds. The background is chosen on 128 independent design states from the bank's 50 candidates, by minimizing the maximum estimated number of candidates farther than 0.10 in TV, with ties broken by seed and training step. It is frozen before the evaluation draws. Each probe uses $Y_s=\{\pi_{\rm bg}(\cdot\mid s)\}$, so the count is the restricted-background upper bracket of Equation 10, not the unrestricted optimum or the exact parameter $b$. If all policies share a bijective tanh and action scaling, TV can be computed before that transformation, and clipping or discrete atoms need separate treatment. ### Audit of the learned families Section 8.2 now reports the fresh audit of the trained SAC checkpoints. At $\lambda=0$, the classes, certified packings, and probe counts are: | Pool | Inner / outer size | Inner packing at $0.5/H$ / $1/H$ / $2/H$ | Outer packing at $0.5/H$ / $1/H$ / $2/H$ | $\widehat b^Y$ at $\tau=.05$ / .10 / .20 | |---|---:|---:|---:|---:| | 15 | 8 / 13 | 8 / 7 / 6 | 12 / 11 / 9 | 8 / 4 / 2 | | 30 | 17 / 26 | 16 / 14 / 11 | 24 / 22 / 18 | 15 / 7 / 3 | | 50 | 30 / 39 | 27 / 23 / 19 | 36 / 31 / 27 | 24 / 11 / 5 | The certified inner packing at $K=50$ and $r=1/H$ is 23 of the 30 pipeline-relative near-optimal policies, against 20 in the submitted analysis. The packings shrink as the radius grows, and the probe counts fall as the tolerance grows, as Equation 9 requires. The probe counts are taken over all candidates of a pool. The forward-KL banks give: | $\lambda$ | Return, mean ± SD | Outer class $M_{\rm out}$ | Outer packing at $1/H$ | $\widehat b^Y$ at $\tau=.10$ | |---|---:|---:|---:|---:| | 0 | .914 ± .024 | 39 | 31 | 11 | | .01 | .917 ± .021 | 37 | 29 | 9 | | .05 | .889 ± .026 | 27 | 22 | 6 | | .10 | .866 ± .030 | 18 | 15 | 5 | Increasing the penalty from 0 to 0.10 shrinks the outer class from 39 to 18, its certified packing from 31 to 15, and the probe statistic from 11 to 5, while return falls from .914 to .866. A declining certified packing does not upper-bound full occupancy capacity. Section 8.2 now discusses this frontier with Table 4. ### Access study and occupancy recovery The valid-state bank holds 8,192 reachable simulator snapshots from 128 held-out rollouts, collected independently of the audit deployments. Fixed-bank access starts each segment from a bank snapshot and resets after at most 40 interactions, or earlier at termination. Trajectory access observes ordinary trajectories from the initial-state distribution and never resets to a stored state. Both use a 20,000-interaction budget and 1,000 deployments per pool. Exact checkpoint identification differs from occupancy recovery at the declared tolerance. The new score, plug-in projected-occupancy recovery, counts a deployment as recovered when the returned checkpoint's estimated projected occupancy lies within $1/H$ of the deployed one's. | Pool | Fixed-bank: exact identity | Fixed-bank: plug-in recovery | Trajectory: exact identity | Trajectory: plug-in recovery | |---|---:|---:|---:|---:| | 15 | .966 | .991 | .824 | .941 | | 30 | .913 | .973 | .705 | .887 | | 50 | .861 | .941 | .582 | .809 | Chance is $1/K$. The confidence radius of 0.036 exceeds $1/H$, so the confidence event does not certify plug-in recoveries even in the projected metric, and projection contracts TV. Exact identity gives zero occupancy error for the same frozen checkpoint and initial law, so its rate is the certified lower bound on full occupancy recovery. Restricting access lowers both scores in every pool, and at $K=50$ exact identification falls from .861 to .582. Table 3 of the revision reports these results. The submitted analysis also compared resets to previously observed states, and the rerun reports the two conditions at the ends of that range.
Reviewer_Q6kSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks when a large family of near-optimal RL policies makes auditing hard, i.e., identifying which policy is deployed from black-box queries. The main claim is that the number of policies, or occupancy capacity, alone does not determine difficulty. Hardness comes from sparse signatures, where at every state almost all candidates respond the same. Under this condition, identification needs Ω(M/b)\Omega(M/b) queries. A hidden-branch MDP attains this bound, while a shortest-path grid has high capacity but is easy to audit. The paper also covers episode access, noisy triggers, and KL regularization, with finite-family diagnostics on AntMaze and MinAtar.

Critical strengths
  1. The message that multiplicity is not the same as auditing difficulty is clean and useful. The hidden-branch vs. grid contrast shows this well.
  2. The assumptions and scope are stated carefully.
Critical weaknesses
  1. The main bound is a classical hidden-index search argument, and the authors say so themselves ("the same search bound in different units"). The capacity form does not strengthen it. So the contribution is mostly the definitions and framing. That can still be valuable, but the paper does not show what the RL structure adds beyond the standard argument. The heavy hedging throughout also makes it hard to see what the new contribution is. I think the theoretical novelty is limited.
  2. The theoretical part and the experiment part is disconnected. The key assumption (b-sparse signatures) is never verified on learned policies, and the authors state that b^\hat{b} is not b and RQR_Q is not a lower bound. With K = 50 (at most ~5.6 bits), the experiments also cannot speak to the exponential regime. It is unclear what the empirical section is supporting.
Questions for authors
  1. Apart from the definitions, which result do you consider new, i.e., not following directly from the standard search argument?
  2. In what real auditing scenario does the auditor know a finite candidate family that contains the deployed policy? I do not think the problem setting considered in this paper reflects the usual setting for backdoor detection.
  3. Is there any evidence that learned policies actually have sparse signatures? If not, what do the AntMaze results tell us about the regime of Theorem 5?
3 comments
AuthorsOpenReview ↗

Response to Reviewer Q6kS – Part 1

Thank you for the review. The table summarizes our answers, and the text after it gives the details.

Your pointOur answerWhere in the revision
Third question: do learned policies ever satisfy the theorem's premises?Yes. In a gridworld with exact occupancies, 36 policies fine-tuned with planted triggers form a separated near-optimal packing with exact b=1b=1. Auditing them takes 18.47 state queries on average and 35 at most, the expectation and worst case that Theorem 5 gives. Thirteen independent seeds in the same gridworld have b=9b=9 and take 2.15.Appendix M, Table 19; Section 8
First question: what does the RL setting add to the search argument?Five RL-specific results, including the new fixed-resolution cap of fewer than bH2+1bH^2+1 members at resolution 1/H1/H.Introduction; Sections 4–7; Appendix K
Where the known-family setting appliesChecking deployment against an approved checkpoint bank. Theorem 10 covers detection of one anomalous trigger among candidate locations.Sections 3 and 6

The hidden-index counting step is classical, and the paper uses it as a tool. The contributions are the RL results that decide when that tool applies. The hidden-branch and shortest-path constructions identify which combinations of occupancy geometry and local information permit or prevent hardness, and the new fixed-resolution theorem bounds how large a hard family can be. The root-reset law, coverage-capped extension, and forward-policy-KL condition then address different RL access and regularization assumptions. Corollary 6 explicitly requires a family realizing the cover number before substituting capacity for candidate count.

To answer the first question directly, five results use RL structure that the search argument does not supply. The first is new in the revision. Proposition 21 shows that the discounted occupancy geometry caps every exact sparse family at fewer than bH2+1bH^2+1 members at resolution 1/H1/H. Theorem 5 therefore can never require more than (1−δ)H2(1-\delta)H^2 queries there, and Proposition 22 attains this order with trajectory deviations. The cap comes from how far one deviation can move a discounted occupancy, and the plain search argument has no analogue of it. Theorem 7 realizes feasible discounted flow, optimal return, occupancy separation above 2/H2/H, and one-sparse signatures in one MDP. Proposition 17 gives the exact root-reset law, which needs Θ(M)\Theta(M) episodes rather than the coupon-collection Θ(Mlog⁡M)\Theta(M\log M). Lemma 8 adds discounted visitation outside a covered region to the state-query bound. Theorem 11 bounds occupancy distance through a stopped-history policy-KL chain rule and gives the penalty at which capacity collapses. The counterexample after Theorem 10 also shows that the Mlog⁡M/βM\log M/\beta scan scale is not universal. The revision adds a contributions paragraph to the introduction that names these results and a sentence in Section 4 that states the fixed-resolution cap.

The known-family setting applies, for example, to checking deployment against an approved checkpoint bank with a recorded training and selection pipeline. It does not cover generic backdoor detection when the deployed policy may be outside that bank. Theorem 10 is the result closest to backdoor detection, since it lower-bounds detection of one anomalous trigger among MM candidate locations. Membership-query and teaching/disagreement complexity provide the appropriate comparison for the information structure. The RL constructions supply occupancies, reachability, and episode costs.

The AntMaze study measures what a finite audit can certify: separation under an explicit simultaneous certificate, and tolerance agreement on declared probes. For an unrestricted policy class on a continuous state space, exact agreement at every state cannot be certified from finitely many probes (Appendix E), so no experiment of this kind can supply it. Proposition 21 also sets the relevant scale. At a fixed resolution, a hard exact family has fewer than bH2+1bH^2+1 members, so the hard regime is at most quadratic in the horizon for learned and constructed families alike.

AuthorsOpenReview ↗

Response to Reviewer Q6kS – Part 2

To answer the third question directly: yes, learned policies can satisfy both premises exactly, and the revision adds a family that does (Appendix M). In a 20×2020\times20 gridworld with exact occupancies, 36 copies of one near-optimal policy were fine-tuned for 5,000 updates, each with a small reward bonus for one action at its own trigger state. The copies form a 36-member 2/H2/H-separated near-optimal packing with exact b=1b=1, and their returns of 0.656–0.683 stay within the tolerance of 0.05 fixed before fine-tuning. Each deployed policy is deterministic and greedy in its learned action values. An auditor needs 18.5 queries on average and 35 at most, matching the expectation of 18.47 and the worst case (M−1)/b=35(M-1)/b=35 of Theorem 5. No auditor can do better on this family, because querying the triggers one at a time attains the bound (n+1)/M(n+1)/M. In the same gridworld, 13 independently trained seeds form a separated near-optimal packing with exact b=9b=9, and an auditor needs only 2.15 queries on average and 3 at most. A shared base with local triggers, not independent training, produces the hard regime. The hardness concerns the state queries of Theorem 5. Root-reset episodes are cheap on this family, because every episode follows the base path on which the triggers lie, which is the access distinction of Section 5.

Independently trained seeds are a different case. In the AntMaze rerun, one probe state separates 11 of the 50 candidates from a fixed background at tolerance 0.10, and 24 at 0.05. A fixed background bounds the unrestricted count from above, so these counts do not show sparsity, but they do not rule it out either. Expanding the probes shows how the statistic grows (Appendix J):

Probe count1282565121,0242,048
Maximum exceptions at τ=0.10\tau=0.10910111112

On the 512 probes, 282 states have no exception and 117 have one. Fixed-bank access identifies the deployed checkpoint in 86.1% of audits against chance of 2%, and ordinary trajectories in 58.2%, consistent with the reachability cost of Lemma 8. The planted family shows that the hard regime can arise through training, and the seed families do not show that ordinary independent training typically produces it.

Please let us know if you have any other questions.

Thanks for the substantial revision. I think the revision addresses most of my earlier concerns, especially the disconnect between the theory and the experiments. My main remaining reservation is that the overall theoretical novelty is still modest, and the approved-checkpoint-bank setting is narrower than generic backdoor detection.

One thing I could not verify from the paper is the new experiment in Appendix M. It would be helpful to provide enough details to reproduce the training procedure, trigger construction, and minimum pairwise occupancy separation. I see this as a reproducibility concern rather than a correctness issue.

Overall, the authors have answered my main questions, and I will raise my score to 3 accordingly.

Reviewer_ytVTOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This research paper makes significant contributions to the field of reinforcement learning (RL) conducting a rigorous investigation into the concept of occupancy Rashomon capacity.

Moving beyond standard analytical frameworks, this work establishes a rigorous exponential lower bound of $\Omega(M/b),

This characterizes fundamental theoretical limits in this domain. Furthermore, to substantiate these theoretical insights and demonstrate their practical relevance, the paper provides a thorough empirical evaluation results by showing comprehensive experiments that validate the derived bounds.

Critical strengths

The research questions, introductions, and background context are articulated with exceptional clarity, ensuring that readers fully grasp the scope, boundaries, and environmentel framework of the study from the outset.

The main inquiry and primari hypothesis are explicitly and rigorously defined, leaving no ambiguity regarding the specific objectives, motivations, and drivig questions that structure the investigation.

From the overall contribution side, this work delivers a comprehensive, dual-faceted validation strategy by incorporating both high-level theoretical proof. More specifically, it meticulously outline the crucial mathematical and logical underpinnings. In alongside extensive empirical and experimental results that robustly demonstrate practical applicability and performance.

Critical weaknesses

There are too much white space in page 23

The formation can be improved

More discussions on contribution can be added. A separate part after introduction for introduction or expand the introduction. The introduction is too short.

Questions for authors

Could you clarify why TV distance is used as a measure in Definition 3? It seems that there are several other choices. I was wondering why this is chosen is paper. Coud you add more discussions.

Additionally, the notation Pr^pi represent in that line 089 could be desposed better

What does nats mean in line 1155

2 comments
AuthorsOpenReview ↗

Response to Reviewer ytVT

Thank you for the review. The table summarizes our answers, and the text after it gives the details.

Your pointOur answerWhere in the revision
Why total variation?TV turns approximate recovery into a unique index, contracts under the finite projection, and bounds differences in bounded rewards.Text below
NotationPr⁡π\Pr^\pi is defined directly after Equation 1, and the nats and bits convention follows Definition 9.Sections 3 and 6
Clarity of the introductionThe conditional result is in the first paragraph, and a contributions paragraph names the result of each section.Section 1
Table 12 alone on page 23The forced page break is removed, and the table floats with its discussion.Appendix H.7

TV is useful because normalized discounted occupancies are probability measures, disjoint TV balls turn approximate recovery into unique identification, and TV contracts under the finite projection used in the diagnostics. It also bounds discrepancies in expectations of bounded rewards and connects to the policy-KL argument. Other metrics are possible, but the separation and transfer steps would need their corresponding assumptions.

In Equation 1, Pr⁡π\Pr^\pi denotes the trajectory law induced by the initial-state distribution, transition kernel, and policy. “Nats” denotes natural-log units of KL, and capacity is expressed in base-two bits. The revision will define Pr⁡π\Pr^\pi directly after Equation 1 and state the nats and bits convention after Definition 9. It will also state the conditional result in the first paragraph of the introduction and add a contributions paragraph at the end of the introduction, which will name the result of each section. Table 12 sat alone on page 23 because a forced page break followed it. The revision removes that break and let the table float with its discussion in Appendix H.7.

Please let us know if you have any other questions.

Great to see the insightful comments.

I keep my original rating.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the reviewers for questions that strengthened both the theory and the experiments. Three new results answer the main concerns.

  • A fixed-resolution theorem. At resolution 1/H1/H, every 2/H2/H-separated family with bb-sparse exact signatures has fewer than bH2+1bH^2+1 members, and fewer than bH+1bH+1 when actions share transitions (Proposition 21). A family of trajectory deviations attains this order (Proposition 22), so the growing horizon of the hidden-branch construction is necessary.
  • A learned family that realizes Theorem 5. In a 20×2020\times20 gridworld with exact occupancies, 36 policies fine-tuned from one base policy, each with its own planted trigger, form a separated near-optimal packing with exact b=1b=1. Auditing them takes 18.47 state queries on average and 35 at most, the expectation and worst case that Theorem 5 gives. Thirteen independently trained seeds in the same gridworld have b=9b=9 and take 2.15 queries.
  • An explicit certificate and a fresh audit. Appendix J gives the estimator, sample counts, independence, truncation, and return intervals behind every certified packing. Under it, a fresh audit of the trained SAC checkpoints finds a 23-member separated packing among 30 near-optimal policies, and restricting access to ordinary trajectories lowers identification from 0.861 to 0.582.

Revisions at a glance

New resultRequested byWhere in the revision
Fixed-resolution cap and a family that attains itEQWd, Q6kSSection 4; Appendix K, Lemma 20, Propositions 21–22
Explicit finite-sample certificate for projected packingsEQWdAppendix J, Proposition 19, Table 13
Fresh audit of the learned SAC familiesEQWd, Q6kSSection 8.2, Tables 2–4; Appendix J, Tables 14–15
Submitted analysis kept as a separate recordEQWdAppendix L, Tables 16–18
Planted-trigger family against independent seedsQ6kSAppendix M, Table 19
Comparison with exact learning and the teaching dimensionEQWdRelated Work
Conditional result in the first paragraph, and a contributions paragraphQ6kS, ytVTSection 1
Definition of Pr⁡π\Pr^\pi, the nats and bits convention, and Table 12 placementytVTSections 3 and 6; Appendix H.7
DQN claim removed from the abstract and setupEQWdAbstract; Section 8

What the result covers

The main result is conditional: occupancy separation converts approximate recovery into index identification, while sparse local signatures restrict how quickly queries identify that index. The classical success bound is (nb+1)/M(nb+1)/M, and its capacity form restates it in capacity units. The new fixed-resolution theorem bounds how large a family realizing it can be. The RL contribution is to realize these two conditions together, contrast them with an easy high-capacity family, and distinguish state-query and root-reset episode access. Learned-family diagnostics concern finite projected separation and probe-local agreement, not certification of the theorem's uniform exact-sparsity assumption. The revision states this conditional result in the first paragraph of the introduction, adds a contributions paragraph, and restricts the learned-family claims to SAC.

The revision also adds a new final Appendix J with an explicit statistical certificate for projected packings. It specifies the estimator, sample counts, truncation handling, return intervals, candidate roster, action-TV computation, background selection, state bank, and reset schedule. With 20,000 independent trajectories per checkpoint, the occupancy radius is 0.0360 and the return half-width 0.0144, simultaneously over the 50 checkpoints of each bank. Section 8 now reports a fresh audit of the trained SAC checkpoints under this certificate (Tables 2–4), with an occupancy-recovery score in the access study and a probe set expanded from 128 to 2,048 states in Appendix J. The submitted analysis, whose radius of 0.04 cannot be reconstructed, moves to a new final Appendix L as a separate record.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.