- 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.
Response to Reviewer pFv5
Thank you for the careful review. CE is the submitted exposure verifier, CR the root-value certificate and CP 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, CP 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 CE 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 CP compares with root values. CR certifies 42 and 80, and the union of all valid certificates 58 and 103. The difference between CP and CR is not significant (95% bootstrap intervals [−2, 18] and [−1, 23], resampling the 24 graphs). CP leads at K=2 and is almost the only certificate at tolerance 0.05 (8 and 20 queries, against 0 and 1). CR leads at K=32 and, under the count-spending set, at K=8 and on the five-layer graph, and it usually gives the tighter bound. Almost all certificates that only CP obtains occur at K=2, where no third candidate can screen, so we have not isolated a benefit of screening.
Proposition 13 (Section 7). CP removes this obstruction, because its pairwise bound (Proposition 18) equals −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=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 CP adds. CP 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 CE and 84 for CR, at 1.3 times the cost of CR per certificate (Table 7). Of the 432 main-grid graph attempts, it certifies 8 and the other two checks none.