- 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
-
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.
-
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
-
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.
-
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
-
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.
-
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.
-
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
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 . 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 independently with and record only and the reward at . For a fixed -bin projection, these are independent categorical samples from the projected discounted occupancy . With trajectories per policy and 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.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 , 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 define , the action is assigned to its nearest prototype under frozen normalization with ties broken by index, and has 64 bins.
For densities and ,
=\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.
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.
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=16M, a shrinking radius, and actions with identical rewards and transitions, and Proposition 21 shows that this growth is forced. At resolution 1/H, every 2/H-separated family with b-sparse exact signatures has fewer than bH2+1 members. When all actions share transitions, as in the hidden-branch MDP, it has fewer than bH+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 exact queries, whatever b.
Proposition 22 attains this order with a family whose deviations change state trajectories. A root sends the agent to one of ⌊H/5⌋ chains of length ⌊(H−1)log2⌋, and each policy leaves the background at one chain state for a private absorbing state. This gives about 0.139H2 optimal policies with 1-sparse signatures, pairwise occupancy TV above 2/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/β. 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 H 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/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.