- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies how historical data and additional observations can certify the near-optimality of an existing policy in a finite average-reward MDP. The certificate subtracts a robust lower bound on the incumbent’s gain from an optimistic upper bound on the optimal gain. Both bounds are computed through stationary-flow linear programs over rectangular confidence sets. The paper establishes anytime validity for data-dependent policy selection and stopping, and demonstrates an unbounded separation from optimized common-potential certificates for a fixed incumbent. The certificate also provides uncertainty prices for allocating additional samples. In the known-reward setting, under full-support transitions, unique optimality, and a fixed deterministic incumbent, the authors connect finite-contraction prices to the leading expansion of the observed certificate and derive an asymptotic allocation result. Further results address growing historical coverage and completion in communicating MDPs without a supplied diameter bound. Experiments test the predicted stopping behavior on three-state models and evaluate verification of controllers learned from behavior-policy logs.
Critical strengths
-
A concrete connection between a computable certificate and sampling efficiency. The contribution goes beyond proposing a sensitivity-based acquisition heuristic. The observed-certificate expansion accounts for moving empirical centers, and the consistency of finite-contraction prices connects the acquisition rule to explicit predictions about stopping behavior. The known-reward experiments closely match the predicted sampling ratios: at , the observed ratios are 0.550, 0.362, and 0.270, compared with predictions of 0.558, 0.364, and 0.259. The separation from common-potential verification further explains why certificate choice matters.
-
Carefully controlled comparisons and transparent reporting. The logged-controller study shares incumbents, historical observations, and supplemental row streams across acquisition methods, while comparing both certificates on identical datasets. All incumbent cases and budget-censored runs remain included. The reported reductions of 10.7% and 11.8% in mean capped additional observations support a benefit over uniform supplementation. The paper also reports unfavorable results, including increased costs for the common-potential checker along DCR sampling paths and worse RiverSwim policy loss under the empirical router. These results appropriately delimit the contribution.
Critical weaknesses
-
The allocation result optimizes a certificate whose conservatism may substantially exceed the uncertainty relevant to the decision. The upper and lower programs can select different plausible models, preventing cancellations available in a shared-model comparison. Appendix I demonstrates that this gap can be arbitrarily large and that positive acquisition prices can persist after the underlying policy comparison is already resolved. Rectangular row-wise confidence sets may introduce additional conservatism by aggregating adverse perturbations across rows. Consequently, the allocation rule characterizes the cost of the specified certificate rather than the intrinsic difficulty of policy verification. The authors acknowledge this distinction, but it limits the broader significance of the efficiency result.
-
The strongest efficiency theorem and the main practical implementation remain only partially connected, and the comparative evidence is limited. Theorem 4.2 concerns DCR-TRACK with finite contractions of balls and vanishing forced exploration. The logged-controller experiment instead uses dual prices, probability boxes, and a half-least-filled safeguard. The general completion theorem holds for arbitrary scores and therefore does not establish the efficiency of these practical prices. The plug-in comparison also leaves an important question open. In the three-state known-reward study, plug-in allocation matches finite-contraction stopping checkpoints at the smallest reported margin, whereas finite contractions perform substantially better in the unknown-reward study. The logged-controller tasks use known rewards but do not include a matched plug-in comparator. The three-state result does not establish equivalence on these different tasks, but it motivates this comparison.
Finally, the logged-controller experiments use five or twelve states. Appendix R.6 provides useful computation timings up to 32 states, but larger-scale end-to-end evidence on sample requirements and certification success remains absent.
Questions for authors
- Practical allocation baseline — clarification and targeted experimental suggestion. Is there existing evidence comparing practical DCR with an empirical-model plug-in allocator on the logged-controller tasks, using the same incumbent, confidence sets, and half-least-filled safeguard? Such a comparison would help isolate the value of dual pricing beyond a simpler adaptive allocation rule. If unavailable, this is a suggested experiment rather than a correctness concern.
- Certificate conservatism — clarification of scope. Can the authors clarify whether the existing experiments reveal how much sampling is spent resolving uncertainty that would cancel in a shared-model comparison? Appendix I establishes that this can happen, but the extent of this effect in the stochastic sampling studies is less clear. A small-instance comparison, where feasible, would help assess the practical significance of the certificate-specific allocation result.
- Scaling — extension of the existing evidence. Appendix R.6 reports computation timings up to 32 states, but the main sampling-efficiency experiments use only five or twelve states. Could the authors provide larger-scale experiments, ideally on MDPs with approximately one hundred states or more, reporting per-check computation time, additional sample requirements, and the fraction of incumbents certified within the budget? Please distinguish practical dual-price DCR from finite-contraction DCR-TRACK, since their computational costs differ substantially. I would consider raising my rating if larger-scale experiments provide convincing evidence of computational feasibility and improved certification efficiency relative to matched baselines, with results reported across all seeds, including runs that reach the sampling budget without certification.
2 comments
Official Comment (Part II)
4. Connection between the theorem and the practical rule.
Propositions 6.1–6.2 analyze the dual scores, box and group regions, and fixed safeguards. They assume known rewards, a fixed deterministic candidate, a unique optimal policy, irreducibility under every deterministic policy, and exact LP solutions. Under these assumptions they give the limiting sampling proportions and the leading coefficient of the certificate. Matched plug-in has the same limits for each allocation order and safeguard share. These results describe the practical rule at geometric checkpoints; they do not establish finite-sample superiority. The exact stopping-time result, Theorem 4.1, remains specific to finite-contraction DCR-Track with finer checks and vanishing forced exploration.
Official Comment (Part I)
Thank you for the careful review and the targeted suggestions. All three requested experiments are now in the paper. In short:
1. Matched plug-in baseline on the logged-controller tasks (Question 1).
Result: original practical DCR needs 0.67% and 0.94% more new observations than matched plug-in, at history lengths 8,192 and 65,536. This comparison was not in the original submission. It keeps all 512 original candidates and matches histories, observation streams, confidence boxes, checks, budgets, and the half-batch safeguard. Both methods certify 192/256 candidates at the shorter history and 206/256 at the longer one. Every run contributes its stopping count or its budget (Appendix M.1, Table 7).
2. Sampling spent on uncertainty that cancels under a shared model (Question 2).
Result: 18.98 times and 3.06 times as many new observations in a two-state study. The original experiments did not measure this cost. In the added study, the separate-model test and an exact shared-model test see identical uniform sampling paths and confidence sets. Mean new observations are 63,008 versus 3,320.4 for an optimal candidate, and 48,659 versus 15,907.3 for a suboptimal candidate within tolerance. Both tests certify all 32 seeds in each case (Section 5; Appendix I.2, Table 4).
What this does not show. The overhead on the larger tasks, and the additional cost of independent adverse choices across rows, remain unmeasured. The allocation optimum is specific to the chosen certificate. Section 5 now opens with this statement, and the main text closes with it as a limitation.
3. Larger-scale experiments (Question 3).
Result: on twenty fresh 100-state queue histories, all seven rules certify 20/20 candidates within the 2²⁴ budget, and quarter-safeguard DCR needs 18.6% fewer new observations than the original plug-in rule.
Mean new observations in millions, with checks at batch ends (Table 3). Uniform needs 11.863.