acceptodds
Under review as a conference paper at ICLR 2027

Search or Refresh? Candidate-Exposure Certificates for Offline Policy Extraction

Abstract

Increasing action-search computation changes the continuation policy that an offline critic must evaluate. We study which unresolved rankings matter for this change through candidate exposure: an error affects selection only when competing actions appear together without being screened by a higher-ranked candidate. We derive an interval envelope, relate it to fixed-vector robust regret within a factor of four, and obtain equality for two supported actions. We provide a certified threshold approximation for larger candidate budgets, while using an exact near-linear algorithm for two draws. An exact moment-tree alternative is near-linear in action count at fixed budget. Model confidence sets built from trajectories support adaptive stopping and policy replacement. Our replacement test lower-bounds shared-model baseline regret and is exact for a common uncertain prefix followed by a known suffix. A stepwise analysis separates marginal-value uncertainty, residual inflation, visitation bounds, and numerical approximation. A certificate-matched study charges every schedule for final verification and uses identical sequential replacement gates. Across 192 trajectory datasets, exposure and robust root-value checks have complementary yields; fixed-episode confidence improves graph certification but does not establish broad computational superiority. The results identify what decision-sensitive certification adds, what it costs, and where its uncertainty relaxations lose useful information.

Primary area:
reinforcement learning
Keywords:
offline reinforcement learning, policy extraction, candidate exposure, robust regret, adaptive certification

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_pFv5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper explores candidate-based policy extraction in offline reinforcement learning. It focuses on how increasing the number of sampled actions can change the downstream policy and cause a mismatch with a critic assessed under a different policy. To tackle this issue, the authors introduce a candidate-exposure framework to measure how uncertain action rankings influence selection within a defined search budget. The key contribution is an interval-based exposure envelope that provides an upper limit on local selection regret, remaining within a factor of four of fixed vector robust regret, achieving equality when two actions are supported. Additionally, the paper presents both exact and approximate algorithms for calculating this envelope and integrates it with trajectory-based model confidence sets to establish criteria for adaptive stopping and safe policy replacement.

The empirical assessment evaluates certificate yield, computational efficiency, and uncertainty-driven conservatism across controlled finite MDPs, including multi-step graph environments, while comparing results to dynamic programming and root-value certification methods.

Critical strengths

1- The candidate-exposure framework formalizes an important distinction between uncertainty in action values and uncertainty that can actually affect decisions under candidate sampling. The interval-envelope result and the associated exact and approximate algorithms make it a nontrivial contribution.

2- The paper distinguishes matched budget near-optimality from safe improvement over a retained policy and establishes its guarantees under explicit finite-MDP and model confidence assumptions. The evaluation also uses certificate-matched comparisons that account for final verification and replacement costs. It should be noted that the authors honestly acknowledge unfavorable results and analyze sources of certificate conservatism.

Critical weaknesses

1-- My main concern is the gap between the theoretical results and the effectiveness of the resulting certification procedure in the studied sequential decision problems. Although the candidate-exposure envelope provides a meaningful characterization of local selection uncertainty, the experimental results suggest that the residual exposure pipeline can become too conservative to issue useful certificates in more demanding environments. In particular, the graph sensitivity study in Section 8 reports no successful residual-exposure certificates across 432 candidate queries under either confidence construction, whereas root-value certification succeeds in 42 and 80 cases, respectively. This limitation is especially relevant given the analysis in Section 7, which shows that replacing shared-model uncertainty with marginal value intervals can produce positive regret bounds even when actual selection regret is zero. While this example does not establish the cause of the experimental failures, it identifies a structural source of conservatism that can undermine the informativeness of the certificates. The authors appropriately acknowledge these limitations. Nevertheless, the results leave me unconvinced that the proposed framework provides sufficiently informative certification in nontrivial sequential RL settings to establish a solid methodological advance.

2- The proposed exact and geometric exposure-stopping procedures do not demonstrate an end-to-end computational advantage over backward dynamic programming followed by the same final exposure certificate in the main experimental comparison. Specifically, Table 1 reports identical certificate yields (144/720) for these methods, while DP with the final exposure check requires less total computation than either adaptive stopping variant. This matters because determining when further critic refreshing is unnecessary is one of the paper's central methodological objectives. The authors correctly distinguish the computational complexity of the local exposure calculation from the cost of the complete certification workflow and do not claim broad superiority. However, the experiments do not establish a setting where the proposed adaptive stopping procedures offer a meaningful end-to-end efficiency benefit over the evaluated DP alternative. Thus, while the underlying mathematical characterization is interesting, the current evidence does not convincingly establish that the integrated certification methodology offers a sufficiently consequential practical advantage for sequential reinforcement learning.

Questions for authors

1- Can the authors identify which uncertainty relaxations predominantly explain the zero residual-exposure certificate yield in the multistep graph experiments? In particular, is this failure mainly driven by marginal value uncertainty, residual inflation, or worst-state/visitation aggregation?

2- Can the authors identify a representative problem regime in which adaptive exposure stopping achieves a computational advantage over backward DP followed by the same final exposure check, under matched certification requirements and complete cost accounting? This would help clarify whether the stopping procedure offers a practical algorithmic contribution beyond the theoretical exposure certificate.

1 comment
AuthorsOpenReview ↗

Response to Reviewer pFv5

Thank you for the careful review. CEC_E is the submitted exposure verifier, CRC_R the root-value certificate and CPC_P the new verifier (Sections 6.2 and 7). Number pairs refer to the count-spending and the tighter fixed-episode confidence sets, in that order.

W1 and Q1: Which relaxation explains the zero graph yield? The main cause is marginal value uncertainty, which has two parts here: the width of our confidence sets and the projection of values onto rectangular intervals (Appendix F.2–F.3, Table 6). In 326 and 276 of the 432 queries, the confidence set contains a model under which the candidate's regret exceeds the tolerance, so no certificate built on these sets can succeed there. We have not shown this to be an information limit, since the tighter fixed-episode set already makes 50 more queries feasible.

Without shared continuation values, CPC_P certifies 20 and 59 instead of 50 and 91. With worst-state aggregation instead of robust visitation, it certifies 41 and 74. Adding the tightenings in a fixed order, we recorded the first step that certifies each query that CEC_E fails (Appendix F.3). State–action residual bounds, which remove layerwise residual inflation, come first for 8 and 32 queries, the model hull (tight marginal boxes) for 12 and 27, and shared continuation for 30 and 32. On the main grid, residual inflation dominates instead: of the 68 attempts that a tighter step recovers, the residual-bound and hull steps come first for 58.

How CPC_P compares with root values. CRC_R certifies 42 and 80, and the union of all valid certificates 58 and 103. The difference between CPC_P and CRC_R is not significant (95% bootstrap intervals [−2, 18] and [−1, 23], resampling the 24 graphs). CPC_P leads at K=2K=2 and is almost the only certificate at tolerance 0.05 (8 and 20 queries, against 0 and 1). CRC_R leads at K=32K=32 and, under the count-spending set, at K=8K=8 and on the five-layer graph, and it usually gives the tighter bound. Almost all certificates that only CPC_P obtains occur at K=2K=2, where no third candidate can screen, so we have not isolated a benefit of screening.

Proposition 13 (Section 7). CPC_P removes this obstruction, because its pairwise bound (Proposition 18) equals −g-g on that family, so the envelope is zero. Offsets that reach the two actions through different successors are still lost (Appendix F.1), and we claim no factor four for the extension.

W2 and Q2: Is there a regime where stopping beats DP plus the same check? We found none, and the revision now says so (Remark 20). In layered models, DP plus the verifier never needs more backups than stopping. DP's single backward pass already leaves a zero empirical residual, every residual-certified schedule needs at least one backup per row, and stopping also evaluates the verifier at every iterate it tests. In a timed replay, residual and verifier checks took 97% of the refresh time of exact stopping (Appendix F.5). In discounted planning, where no backward pass exists, exposure stopping saved 10.2% of sweeps at K=2K=2 but was slower than the generic residual rule in all 32 runs (Proposition 21, Table 9). We therefore no longer claim stopping as a contribution (abstract and Sections 1, 8 and 9), and Section 6 is retitled.

What CPC_P adds. CPC_P certifies more candidates but leaves the retained policies unchanged, because every method uses the same gate. On the main grid it certifies 212 of 720 attempts, against 144 for CEC_E and 84 for CRC_R, at 1.3 times the cost of CRC_R per certificate (Table 7). Of the 432 main-grid graph attempts, it certifies 8 and the other two checks none.

Reviewer_EHQ3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies best-of-K policy extraction in offline RL, where K candidate actions are sampled from a known proposal and the one with the highest critic score is executed. The paper asks which uncertain action rankings actually matter for this choice, and answers with a candidate-exposure envelope that counts only the ranking mistakes that can change the sampled decision. Building on it, the paper gives certificates for when to stop refreshing the critic and when to replace the current policy, and evaluates them on small tabular MDPs. Overall, the analysis is careful and correct, and the reporting is honest. However, the setting is far from the learned-critic problem that motivates it, and the proposed certificate rarely succeeds beyond the simplest examples, so the practical contribution seems limited in its current form.

Critical strengths
  1. The local analysis is sound and insightful. The exposure envelope cleanly formalizes which uncertain rankings can affect a sampled choice, and the screening effect is a nice observation. I roughly checked the closed form, the factor-four argument, the two-action equality, and the loss propagation, which are generally correct.
  2. The evaluation protocol is careful. Every schedule is charged for its final certificate and for failed attempts. Datasets and replacement gates are shared across methods, and one confidence event covers all adaptive queries. Others could reuse this protocol, and the ordered slack decomposition is informative in its own right.
  3. The motivating example is clear. The fork example isolates the continuation mismatch without any estimation error, which makes the problem concrete.
Critical weaknesses
  1. The covered setting is far from the motivating problem. The motivation is sampling-based extraction with learned critics. The theory and experiments, however, are restricted to finite layered MDPs with a known proposal, at most five layers, and at most 32 actions. As the paper notes, one backward pass solves the matched problem exactly in this setting. The experiments confirm that DP followed by the same exposure check obtains the same certificates as the proposed stopping schedules, at lower cost. So in the covered setting, "search or refresh" does not seem to be a real tradeoff. It would help to identify a regime where adaptive stopping has an advantage, even a tabular one, or to show how the ideas carry over to approximate critics.
  2. By the paper's own decomposition, marginal-box uncertainty and residual inflation account for nearly all of the slack. The menu-envelope step and numerical integration contribute little. So the new local object and its fast computation address only a small part of what limits the certificate. The paper already has tighter valid boxes on the same event, namely the row-wise radii in Appendix B.3 and the robust hull. Yet the deployed certificate uses layer maxima and worst-state aggregation. The most promising route to higher yield seems to be using those tighter boxes with robust visitation, or uncertainty sets that keep shared-value structure.
  3. The experimental design is slightly narrow. The evaluation uses five hand-designed families with eight seeds each, and the sensitivity structures were chosen after examining the main grid. The retained-policy gain is identical across methods within each family, so the experiments compare only time and certificate counts. For the replacement step, standard safe policy improvement baselines are missing, for example SPIBB or interval-based off-policy tests. There are also no sweeps over proposal quality, larger action spaces, or larger K.
  4. The presentation is dense. The main text compresses many results into nine pages, and the frequent disclaimers make it hard to tell what is claimed and what is not. The abstract reads as a list without a single main message. Key comparators such as CE, CR, and the generic bound are defined late or only in the appendix. Table 1 also hides the per-family pattern that drives the conclusions. Focusing the main text on the envelope, the certificate pipeline, and one or two decisive experiments would make the paper much easier to assess.
Questions for authors

See Weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer EHQ3 (1/2)

Thank you for checking the analysis and for the concrete suggestions. CEC_E is the submitted exposure verifier, CRC_R the root-value certificate and CPC_P the new verifier (Sections 6.2 and 7). Number pairs refer to the count-spending and the tighter fixed-episode confidence sets, in that order.

W1: "Search or refresh" is not a real trade-off. We agree for layered models, and the revision says so (Remark 20). DP plus the verifier never needs more backups than stopping, and stopping also pays for the verifier at every iterate it tests. CPC_P itself needs a full robust backward pass, so partial refreshing saves no work there. We also found no other regime where stopping helps: in discounted planning, exposure stopping was slower than generic residual stopping in all 32 runs (Table 9). We therefore no longer claim stopping as a contribution, Section 6 is retitled, and Proposition 6 is renamed "Residual band".

For learned critics, Theorem 2 and Proposition 17 apply unchanged at any state with valid interval or pairwise-gap bounds and a known finite proposal. The return bound also needs such bounds at every reachable state and a visitation bound, and CPC_P needs an explicit model set. We provide these only in the tabular case and give no learned-critic demonstration, as Sections 1 and 9 state.

W2: Tighter boxes, robust visitation and shared-value structure. We agree that the envelope step and numerical integration add little slack, and all gains below come from tighter inputs to the envelope (Appendix F.1–F.3, Table 6). All three of your suggestions help, but only shared-value structure, combined with robust visitation, brings exposure checks level with root values. With row radii, the robust hull and robust visitation, the yield rises from 0 to 20 and 59 of 432 queries, still below the 42 and 80 of CRC_R. Adding a pairwise bound that keeps the next-state values shared by two actions (Propositions 17–18) gives CPC_P, which certifies 50 and 91, and all valid certificates together certify 58 and 103. The difference from CRC_R is not significant, with CPC_P ahead at K=2K=2 and at tolerance 0.05 and CRC_R ahead at K=32K=32.

In 326 and 276 of the 432 queries, the confidence set contains a model under which the candidate's regret exceeds the tolerance (Remark 19), so no certificate built on our sets can succeed there. Three limits remain. Proposition 18 shares only continuation values, and neither the factor four nor the fast algorithms of Section 5 apply to it. All our graphs also have two states per layer, which favors CPC_P because competing actions then share successors.

AuthorsOpenReview ↗

Response to Reviewer EHQ3 (2/2)

W3: Narrow design. We agree that the sensitivity structures were chosen after the main grid, so we added a sweep on fresh graphs with a grid fixed in advance (Appendix F.8, Table 12). It varies the proposal, including an informed proposal that mixes in a softmax of the true Q⋆Q^\star, and takes the number of actions AA and the budget KK up to 128, with 384 attempts per confidence set. CPC_P certifies 88 and 156, CRC_R 86 and 130, and their union 106 and 169. CPC_P is ahead or tied at K=2K=2 for every AA, while CRC_R is at least as strong at A=32A=32 with K≥8K\ge8. At A=128A=128, no certificate can succeed on 112 of the 128 attempts, and the union certifies only 0 and 4, all through CPC_P. As the paper now states, exposure checks are weakest at large KK, where nearly every candidate set contains the top few actions. The proposal changes yields less than AA and KK do. With the informed proposal, CRC_R leads under count-spending (32 against 24 of 96) and CPC_P under fixed-episode (46 against 41).

Retained gains are identical because all schedules share one gate, which isolates the verifier. The baselines below are therefore our only comparison of policy quality, and they do not favor us (Appendix F.7, Table 11).

  • An importance-sampling test with an empirical Bernstein bound accepts 100 main-grid proposals against our 116, including 28 on graphs where our gate accepts none. On the sensitivity grid it accepts 77 and 73 against our 54 and 75, but none at K=32K=32.
  • Split-sample high-confidence policy improvement (HCPI) has a lower mean gain than ours on the main grid (0.213 against 0.271), but it improves more datasets (56 against 50).
  • Πb\Pi_b-SPIBB (safe policy improvement with baseline bootstrapping) with count threshold N∧=10N_\wedge=10 realizes larger true gains, 0.543 on the main grid and 0.498 on the sensitivity grid, against our 0.271 and 0.167. With N∧=200N_\wedge=200, its main-grid gain of 0.250 is below ours. Our gate certifies 49 of the 120 main-grid outputs of SPIBB with N∧=10N_\wedge=10. Deploying only those outputs, and keeping the behavior policy otherwise, gives a mean true gain of 0.291, slightly above our 0.271. Most of SPIBB's lead therefore comes from outputs that our gate does not certify.

W4: Presentation. We revised each part you flagged.

  • The abstract (page 1) now states one main message: certifying a sampled decision requires resolving only the rankings that search exposes.
  • Section 1 (page 2) lists the four claims in a Contributions paragraph and gathers the scope disclaimers, previously repeated in Sections 2, 4, 5, 8 and 9, into one Scope paragraph.
  • Section 6.2 (page 7) defines the generic bound BgB_g, CEC_E and CRC_R before the experiments use them, and Section 5 now points there. Section 7 (page 8) defines CPC_P, the model hull and robust visitation before their first use.
  • Table 1 (page 9) has three new columns that split the certificates into the fork, the one-step control and the graph families, and the captions of Figure 1 and Tables 1–2 now define every symbol they use.
  • In Section 8, the two restricted gate checks now take one short paragraph (page 10), with their grid details in Appendices B.7–B.8.

The main text still covers the envelope (Sections 4–5), the certificate pipeline (Section 6), the sources of conservatism (Section 7) and two main experiments (Tables 1–2). We kept Section 7 and the slack decomposition because all three reviews, including your W2, rely on them. All new analyses are in Appendix F, and Section 8 gained only one paragraph, on CPC_P, plus a few sentences on stopping and per-family results.

I appreciate the authors' substantial work on the additional experiments and the revision, and I especially appreciate their honesty in clarifying the paper's contribution. Overall, the rebuttal makes the paper clearer, and I think the pairwise verifier is a promising direction. However, I still have some concerns about the contribution, since the new results do not support adaptive stopping, and a standard SPIBB baseline gives more gain in most settings with no harmful outputs.

I will thus keep my rating, and I encourage the authors to reframe the paper around the pairwise verifier and the analysis of where the slack comes from. Thank you.

AuthorsOpenReview ↗

Response to Reviewer EHQ3 (follow-up)

Thank you for your careful reading of the revision and for the constructive suggestion.

We agree that the new results do not support adaptive stopping, and we will reframe the final version as you suggest. The paper will be built around the pairwise verifier (Section 7) and the analysis of where the slack comes from (Section 8), and the title would name the verifier. Adaptive stopping will appear only as a negative result, as the abstract and Section 1 already state.

SPIBB. We also agree that SPIBB achieves larger true gains (0.543 against our 0.271 on the main grid) and that none of its outputs was harmful on these datasets (Appendix F.7, Table 11). The two methods answer different questions. SPIBB's guarantee is fixed in advance, whereas our replacement gate gives a certificate, computed from the data, that the deployed policy improves on the retained one. The two also work well together. Our gate certifies 49 of 120 SPIBB outputs with no harmful acceptance, and deploying only those outputs gives a mean true gain of 0.291, slightly above our own 0.271. The reframed paper will present this combination as one of the gate's uses.

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

This paper studies certification for offline policy extraction when an agent samples (K) actions from a fixed proposal and selects the highest-scoring candidate. Increasing (K) changes downstream behavior, so a critic that exactly evaluates a reference policy can still induce worse returns as search increases. The central contribution is a candidate-exposure envelope that measures whether uncertain action rankings can affect selection, accounting for both co-occurrence and screening by higher-ranked candidates. The paper establishes a factor-four relationship between this envelope and fixed-vector robust regret over the same value box, equality for two supported actions, and exact and certified approximate algorithms for evaluating the envelope.

The paper then combines model confidence sets with residual bounds for adaptive stopping and a propagated-advantage test for safe policy replacement. It characterizes a shared-uncertain-prefix setting in which the replacement test is exact and analyzes successive sources of certificate conservatism. Validation uses 192 trajectory datasets from synthetic tabular environments, together with restricted exact comparisons. The results demonstrate complementary certificate yields and additional power for the propagated gate, while showing substantial conservatism on stochastic graph tasks and no overall computational advantage for exposure-based stopping over planning followed by verification.

Critical strengths
  1. A precise and computable characterization of decision-relevant uncertainty.

The exposure envelope in Theorem 2 captures both candidate co-occurrence and screening, making it more informative than a uniform value-error bound or an unweighted ranking condition. Its comparison with fixed-vector robust regret gives an interpretable bound on the additional relaxation introduced by allowing the adversary to depend on the sampled set. The exact two-action and two-draw cases, fixed-budget moment-tree algorithm, and certified geometric approximation make the contribution concrete. This is the strongest technical reason to consider acceptance: the paper identifies a useful mathematical object and develops both its interpretation and its computation.

  1. Careful integration of certification, replacement, and evaluation.

The paper correctly separates certifying a candidate’s matched-budget near-optimality from certifying that it can replace the retained policy. The propagated-advantage gate has demonstrable additional power, including exactness for a shared uncertain prefix followed by a known suffix and a strict separation from the union of simpler gates. The certificate-matched evaluation also charges all methods for final verification and replacement, includes unsuccessful attempts in the cost, and distinguishes candidate certificates from certificates attached to retained policies. These choices make the reported benefits and limitations substantially more credible.

Critical weaknesses
  1. The strongest approximation guarantee concerns a local relaxation whose connection to useful MDP-level certification remains limited.

The factor-four guarantee compares two objectives over the same rectangular value box. It does not control the information lost when model-consistent values are projected into marginal intervals. Proposition 13 makes this limitation particularly concrete: with values ((C,C+g)), the ranking is known throughout the model family and the shared-model selection regret is zero, yet even the exact two-action exposure envelope can be positive. Thus, accurate evaluation of the envelope cannot recover decision information discarded before the envelope is applied.

The paper acknowledges and usefully analyzes this obstruction. Nevertheless, it leaves the positive scope of the central guarantee insufficiently established: beyond the special cases, when does the finite-data construction preserve enough information for exposure to yield useful sequential certificates? The reported ordered slack decomposition reinforces this concern, attributing 61.1% to the initial marginal-uncertainty step and 34.1% to row/layer residual inflation (Section 8; Appendix B.4). These are conditional, ordered attributions, but they indicate that the dominant limitations lie outside the local approximation guarantee.

  1. The integrated experiments do not establish a consequential benefit for the proposed stopping workflow in the richer sequential settings.

In Table 1, exact and geometric exposure stopping obtain the same 144/720 certificates as backward DP followed by the exposure verifier, while requiring 120.8 and 103.0 ms per sequence, respectively, compared with 67.9 ms for DP plus verification. Table 3 shows that all exposure certificates in the main grid arise from the fork and one-step control; the multiaction graph families have zero yield. This persists in the sensitivity study, including episode counts up to 200,000: exposure yields 0/432 certificates under either confidence construction, while root-value certification yields 42/432 or 80/432 (Table 2).

The authors are appropriately candid about these outcomes, and I do not regard them as a contradiction of the stated claims. However, the evidence currently establishes useful complementary behavior in relatively simple settings more convincingly than it establishes the significance of adaptive exposure-based stopping. Together with the local-to-global limitation above, this leaves me insufficiently convinced that the contribution reaches the acceptance threshold.

Questions for authors
  1. Clarification of the stopping comparison. What update cap is used in Table 1, and do unsuccessful refresh procedures terminate once the empirical critic has converged? Could you report the number of backups and the division of time between refresh and diagnostics? In particular, is there an evaluated regime in which exposure-based stopping improves the certificate-matched cost/yield tradeoff over backward DP followed by the same verifier? This would help distinguish the contribution of adaptive stopping from that of the final exposure check.

  2. Additional analysis of the existing graph instances. Using the constructions in Appendices B.3–B.4, how much of the graph certification failure disappears when layerwise residual boxes are replaced by state–action residual bounds or tight marginal boxes, and worst-state aggregation is replaced by robust visitation? Reporting whether these tighter variants cross the stated certification thresholds, together with their additional computational cost, would clarify whether the observed failure is primarily due to the chosen fast implementation or persists for the underlying exposure approach.

  3. Clarification of the propagated gate’s incremental value. In the main and sensitivity experiments with uncertain transitions, how many proposed updates are accepted uniquely by the propagated-advantage gate after the all-state and root-value tests both fail? How many of those updates also carry a matched-budget near-optimality certificate? The shared-prefix and known-transition experiments establish additional power in restricted settings; this breakdown would clarify its contribution within the complete offline workflow.

These questions concern the interpretation and strength of the present evidence. I am not requesting neural-network benchmarks or a general solution to shared-model robust regret as prerequisites for this theoretical contribution.

2 comments
AuthorsOpenReview ↗

Response to Reviewer E1w5 (1/2)

Thank you for the precise questions. CEC_E is the submitted exposure verifier, CRC_R the root-value certificate and CPC_P the new verifier (Sections 6.2 and 7). Number pairs refer to the count-spending and the tighter fixed-episode confidence sets, in that order.

W1: Positive scope beyond the local factor four. We agree that the factor four does not control the projection onto marginal intervals. The revision gives only a partial fix. Given large datasets and graphs with two states per layer, CPC_P is stronger at small KK and tight tolerance, and root values are stronger elsewhere.

In theory, the upper bound and tail formula of Theorem 2 hold for any pairwise bounds Dji≥vj−viD_{ji}\ge v_j-v_i on any value set (Proposition 17). Proposition 18 derives such bounds on QK(s,j)−QK(s,i)Q_K(s,j)-Q_K(s,i) from the same confidence set while keeping the next-state value vector common to both actions. These bounds hold for every model in the set, and on the family of Proposition 13 they equal −g-g, so the envelope is zero there. The fix stays partial because offsets that reach the two actions through different successors are still lost (Appendix F.1) and neither the factor four nor the fast algorithms apply. Beyond this special case, CPC_P has no proven relation to shared-model regret.

Empirically, CPC_P certifies 50 and 91 of 432 graph queries, against 42 and 80 for CRC_R, and the difference over 24 graphs is not significant. CPC_P is ahead at K=2K=2, by 16 and 18 queries with bootstrap intervals that exclude zero, and it is almost the only certificate at tolerance 0.05 (8 and 20 queries, against 0 and 1). CRC_R certifies as many or more at K=32K=32, at K=8K=8 under the count-spending set, and at tolerance 0.2. In 326 and 276 queries, a search of the confidence set finds a model under which the candidate's regret exceeds the tolerance (a witness, Remark 19), so no certificate built on our sets can succeed there. For candidates whose witness regret exceeds 0.01, the smallest valid certificate has a median ratio to the witness regret of 1.41 and 1.48, mostly owing to CRC_R. For CPC_P alone, the medians are 2.25 and 2.20. We did not split the 61.1% share you cite into statistical width and lost shared-value dependence. The lead of CPC_P over CRC_R comes from the three-layer graph, and we do not claim that the exposure construction yields tight certificates.

W2: Benefit of adaptive stopping. We agree that our experiments show no benefit of adaptive stopping over DP followed by the same verifier (see our answer to Q1). On the main grid, the gap between 144 certificates for CEC_E and 84 for CRC_R comes from the fork and the one-step control (new columns of Table 1). Of the 432 main-grid graph attempts, CPC_P certifies 8, and CEC_E and CRC_R certify none. As all methods share one gate, these certificates do not change the retained policy.

AuthorsOpenReview ↗

Response to Reviewer E1w5 (2/2)

Q1: Update cap, backups, time split and regime. The cap is HH sweeps (HH is the horizon), enough to reach the exact empirical fixed point. All 576 unsuccessful main-grid runs of exact stopping therefore end at convergence of the empirical critic, and the Table 1 caption now states the cap.

Over the 720 main-grid attempts, exact and geometric stopping use 2,928 backups each, generic stopping 3,144, HH sweeps 2,448, and one sweep and DP 720 each (Table 8). Stopping counts include the final residual backup, whereas those for the sweeps and DP exclude the residual sweep that their final check recomputes. DP needs one pass per attempt because its backward pass already yields a zero empirical residual (Remark 20). Our implementation recomputes that residual with a second sweep, so as implemented DP performs 1,440 backups.

Per three-budget sequence (Table 8), exact stopping spends 71.6 ms on refresh, against 2.9 ms for DP plus CEC_E. Both spend 16.4 ms on setup and 32.8 ms on the gate. The final check costs 15.9 ms for DP and 0.0 ms for exact stopping, which has already evaluated the verifier on its last iterate. A separate timed replay with its own clock (Appendix F.5) splits the refresh time of exact stopping into 2.0 ms of backups and 55.7 ms (97%) of residual and verifier checks. For geometric stopping, the split is 1.9 ms and 30.8 ms (94%).

We found no regime in which exposure-based stopping helps. In layered models DP plus the verifier never needs more backups (Remark 20), and the yields in Table 1 coincide, although stopping could in principle certify more. In discounted planning (Proposition 21, Table 9), exposure stopping saved 10.2% of sweeps at K=2K=2 and at most 0.1% at K=32K=32 relative to the generic residual rule, yet was slower than that rule in all 32 runs. Policy iteration was fastest in 20 runs and the generic rule in the other 12.

Q2: Tighter variants, thresholds and cost. The failure comes mostly from the width of our confidence sets and only partly from the fast implementation and the projection onto intervals. Your variants certify at most 20 and 59 of the 432 attempts, below the 42 and 80 of root values. Only the pairwise extension with robust visitation (CPC_P) beats root values. The table below, from Table 6, counts certified attempts out of 432.

VariantWorst-state aggregationRobust visitation
Layerwise boxes (CEC_E)0 and 0—
State–action residual bounds8 and 198 and 32
Tight marginal boxes (hull)11 and 5320 and 59
Pairwise extension41 and 7450 and 91 (CPC_P)

All valid certificates together certify 58 and 103. On the main grid, yield rises from 0 to 8 of 144 attempts on the three-layer graph and stays at 0 on the five-layer and 32-action graphs, where a witness rules out 136 of 144 attempts in each.

Per candidate on the sensitivity grid, excluding the construction of the confidence set and the empirical DP, the hull with robust visitation takes 9.4 ms on the three-layer graph and 34.2 ms on the 32-action graph. CRC_R takes 8.9 and 33.4 ms, and CPC_P takes 24.4 and 154.4 ms (Appendix F.4). Per certificate (Table 7), CPC_P costs 148.8 ms against 117.2 ms for CRC_R on the main grid, and about 3 times as much on the sensitivity grid.

Q3: Incremental value of the propagated gate. On the main grid, the gate accepts 116 replacements that change the policy, and 24 of them pass only through propagation (Table 10). Sixteen are in the fork and 8 in the three-layer graph, where they are all of that graph's acceptances. Eight of the fork replacements also carry both CEC_E and CRC_R, at tolerance 0.2 only. CPC_P certifies 17 of the 24 at tolerance 0.2, including all 8 graph replacements, and 9 at tolerance 0.05.

On the sensitivity grid, propagation alone accepts 5 of 54 and 9 of 75 replacements. None of them carries CEC_E, while CRC_R certifies 2 and 3 of them and CPC_P certifies 4 and 6, all at tolerance 0.2. These replacements have mean true gains of 0.362 on the main grid and 0.157 and 0.176 on the sensitivity grid, and none was harmful.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: summary of the revision

We thank the reviewers for careful and constructive reviews. The new analyses are in Appendix F of the revised PDF, and each reply gives the section of every change it mentions.

A new verifier certifies graph queries. It keeps the next-state values that two actions share (Section 7, Propositions 17–18). On the 432 graph queries where the submitted verifier certified none, it certifies about as many as the robust root-value certificate, and each certifies queries that the other misses.

We concede the point on adaptive stopping. In layered models, backward dynamic programming (DP) followed by the verifier never needs more Bellman backups than adaptive stopping (Remark 20). The paper's claims are now the exposure envelope and its computation, the verifier, and the propagated replacement gate.

The presentation is reorganized. The abstract states one main message, and Section 1 lists the four claims and gathers the scope limits into one paragraph. Sections 6.2 and 7 define every certificate before the experiments use it.

We also added safe-policy-improvement baselines (Table 11) and a wider sweep (Table 12), and the replies report the unfavorable results. If the AC agrees, we would retitle the paper around the verifier, for example "Candidate-Exposure Certificates for Best-of-K Policy Extraction".

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.