acceptodds
Under review as a conference paper at ICLR 2027

Decision-Certified Residual Sampling for Average-Reward Policy Verification

Abstract

An existing controller can perform well before the available observations justify accepting it. We study how historical data and additional samples can certify a policy in a finite average-reward Markov decision process. Two stationary-flow programs compare the best plausible gain with the worst plausible gain of the incumbent, giving an anytime-valid bound on policy loss. Separate dual potentials can improve this bound by an unbounded factor over the best common potential for the same incumbent. We then connect acquisition prices to actual sampling efficiency. With full-support dynamics, known rewards, and a unique optimal policy, normalized finite contractions consistently estimate the leading coefficients of the observed certificate excess above true policy loss, including its moving empirical centers. A price-tracking sampler realizes the optimal limiting allocation for this expansion and compares favorably with uniform sampling as the verification margin shrinks. A residual extension characterizes how heterogeneous historical counts reduce the additional samples. General validity and communicating-MDP completion require weaker conditions. Experiments distinguish certificate choice, allocation, policy quality, and computation, using controllers learned from behavior-policy logs and tests of the predicted stopping constants. An exact shared-model comparison also identifies uncertainty that the separate certificate can unnecessarily resolve.

Primary area:
learning theory
Keywords:
policy certification, average-reward MDPs, adaptive sampling, stationary-flow bounds

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_Mb2BOpenReview ↗
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
  1. 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 m=0.00625m=0.00625, 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.

  2. 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
  1. 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.

  2. 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 ℓ1\ell_1 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
  1. 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.
  2. 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.
  3. 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
AuthorsOpenReview ↗

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:

  • On the logged-controller tasks, the matched plug-in baseline is slightly better than original practical DCR.
  • Keeping the two programs' models separate costs a factor of 3 to 19 in a two-state study.
  • At 100 states, a revised allocation rule needs 18.6% fewer new observations than the original plug-in rule, in a structured queue setting only.

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.

Query ruleDCRPlug-in
Design-first, half-batch safeguard (original)2.9662.575
Guard-first, half-batch safeguard2.9222.575
Guard-first, quarter-batch safeguard2.0973.273
  • Savings. Quarter-safeguard DCR saves 18.6% against original plug-in (95% paired-bootstrap interval 12.7–23.7%). Against plug-in under the same quarter-safeguard rule it saves 35.9% (32.1–40.4%), because the smaller safeguard makes plug-in worse here. With all four checks per batch, the saving against original plug-in is 13.1%.
  • How the rule was chosen. Guard-first reserves queries for the least-observed pairs before allocating the rest by the unchanged scores. The quarter share was selected on two development histories, fixed before confirmation data were generated, and applied to both score families. On the development paths, plug-in sent most score-based queries to pairs that were already observed, whereas DCR sent far more to unobserved actions of the candidate and raised the candidate's lower bound (Appendix O.4).
  • Smaller tasks. On 512 fresh smaller-task candidates, the saving over equally modified plug-in is 0.49%. Every method certifies 397/512, including 116 acceptances on the initial data, and all 115 capped runs remain included (Table 20).
  • Scope and negative results. The successful 100-state evidence is for a structured setup: threshold candidates learned from the history, and confidence bounds on the probabilities of predefined groups of successor states. The upper bound still compares against all policies. With coordinate boxes, the initial queue and patrol runs certify 0/6 candidates within the same budget, although five are adequate. On ten further queue histories, seven unrestricted candidates and all ten threshold candidates meet the tolerance, but only the threshold/group combination is certified, and there original DCR costs 17.2% more than plug-in (Table 2; Appendices M.2–N). The new results therefore involve changes to the candidate class, the confidence construction, and the allocation rule.
  • Computation. A separate benchmark uses twenty common saved inputs from an earlier queue cohort. The median time for one complete decision, certificate plus allocation, is 1.963 s for quarter-safeguard DCR and 1.897 s for matched plug-in; the original rules take 1.943 s and 1.919 s (Table 21). Practical DCR uses two LP solves per decision. Finite-contraction DCR-Track would need 402 and was not run at 100 states.
AuthorsOpenReview ↗

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.

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

This paper studies the sampling strategy for verifying the near-optimality of policies in average-reward MDP, where it is allowed to sample transitions from any state-action pairs. The authors introduce two LPs to estimate an upper bound on the suboptimality of the current policy under uncertainty in the environments, and propose to allocate the sampling budget based on estimated reductions of the suboptimality bound. They also reported that the numerical comparisons of the proposed sampling strategy against the uniform strategy.

Critical strengths

None (at least with the current form)

Critical weaknesses
  • It fails to clearly position the contributions relative to prior work, at least in the main text. As a result, it is very hard to assess their significance.
  • It is cluttered with many poorly defined terms (e.g., certification, verification, price, acquisition, certificate excess, allocation, potential, span, witness), which makes the paper extremely difficult to follow.
Questions for authors

Please correct my assessment if it contains factual error.

2 comments

Thank you for the review. The two weaknesses you list were fair, and we have revised the main text on both.

1. Positioning relative to prior work.

The Introduction now ends with a list of contributions, a table of each result's assumptions (Table 1), and a "Relation to prior work" paragraph. In brief:

Line of workWhat it doesWhat we do differently
Learning with a generative model (Wang et al., 2024; Zurek & Chen, 2024, 2025; Lee et al., 2025), also without prior knowledge of the MDP (Tuynman et al., 2024)Sample complexity of learning an ε-optimal average-reward policyWe fix the policy and ask what certifying it costs on the given instance and history
Best-arm and discounted best-policy identification (Garivier & Kaufmann, 2016; Zanette et al., 2019; Al Marjani & Proutiere, 2021)Track allocations that attain instance-dependent sample complexitiesOur allocation follows from expanding a computable certificate, so its optimality is relative to that certificate (Section 5)
Hybrid RL and identification with offline data (Song et al., 2023; Wagenmaker & Pacchiano, 2023; Agrawal et al., 2023)Combine logged and new data to learnWe combine them to verify, and quantify the remaining query cost (Section 4.4)
Occupation-measure LPs, optimism, robust average-reward evaluation (Puterman, 1994; Jaksch et al., 2010; Tewari & Bartlett, 2007; Wang et al., 2023)Supply the tools for our two bounds; optimize or evaluate a robust objectiveOur decision concerns a fixed policy's loss in the true MDP

What is new. The acceptance test itself is built from known tools. The contribution is the link between this test and its sampling cost. Narrowing a confidence region hypothetically keeps its empirical estimate fixed, whereas collecting observations changes both. We expand the certificate recomputed from actual data, prove that the narrowing scores estimate each pair's weight in it, and obtain the sampling proportions that minimize the leading number of queries until acceptance (Theorem 4.1). A separate result gives the remaining cost when the history grows with the required precision (Section 4.4).

2. Terminology.

The main text now defines each term at its first use and uses one term per concept. For the terms you listed:

TermWhat we didWhere
verification, certificationA verifier is a query rule plus an acceptance test; a candidate is certified when the verifier accepts itSection 2
certificateC = (upper bound on the optimal average reward) − (lower bound on the candidate's)Section 3
priceRemoved. We say "score": the contraction score and the dual scoreSections 4.1 and 6
acquisitionRemoved. We say "query" and "sampling"Section 2
certificate excessNot used in the main text. We write C − Δ_πSection 4.2
allocationThe limiting fraction of observations at each state–action pairSection 4.2
spanspan(h) = max h − min hSection 4.2
potential, witnessNot used in the main text, which speaks of the bias and of LP dual variables. Defined in the appendixAppendix C.1

The appendix also opens with a table that collects all notation and terms.

We would be grateful for your reconsideration of the revised manuscript.

Dear Reviewer,

Thank you for the time and effort you’ve put into reviewing our manuscript. As the discussion period draws to a close, we would appreciate it if you could take another look at the revised manuscript. If you feel that the revisions have addressed your concerns about the writing, we would be grateful if you would reconsider your score.

Reviewer_XtPxOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

As far as I can understand, the paper considers the problem of policy certification and provides certain theoretical results concerning this problem, although I am not entirely sure.

Critical strengths

The paper may contain some valuable theoretical results, but I was unable to properly understand and assess them.

Critical weaknesses

The paper is extremely poorly written. The authors frequently fail to define the quantities they use and do not establish clear logical connections between different parts of the paper. Despite having years of experience in theoretical reinforcement learning, I struggled even to understand the precise problem the paper aims to solve. In particular:

  1. The abstract reads like a collection of disconnected statements, without a clear explanation of the problem, the proposed approach, or how the claimed contributions relate to one another.

  2. The "Problem and Data" section is extremely difficult to follow from the very beginning due to numerous undefined quantities and insufficiently explained terminology. For example, I assume that g∗g^* denotes the optimal gain, but this is never explicitly defined. Similarly, the diameter (D) deserves a precise mathematical definition rather than the informal description "the largest, over ordered state pairs, of the minimum expected hitting time." The terms "retained incumbent" and "tolerance," introduced in the following sentence, are also not explained.

The same problem continues in the next paragraph:

"The historical data consist of prefixes of the reward/next-state observation stream of each row, with counts (n_{0,i}) that can be zero or highly unequal." What exactly are these prefixes? What are the "rows" being referred to?

"New observations may be requested directly, or obtained on a trajectory by choosing actions. In either case, the conditional law of the next observation at row (i) is the same stationary row law." What conditional distribution is being considered here? What exactly is meant by the "same stationary row law"?

"This includes nonanticipatory logging and trajectory collection; it excludes outcome-filtered logs or unmodeled changes in dynamics." What is meant by "nonanticipatory logging"? What model is being referred to in "unmodeled changes in dynamics"?

The following paragraph then introduces the confidence set Ct\mathcal C_t, using the notation r−r^- and r+r^+ without explicitly defining these quantities.

The presentation does not improve in the subsequent sections. For example, Section 3 introduces state-action occupancy measures and transition flows without providing clear definitions or sufficient explanation of their meaning.

These problems persist throughout the paper, making it extremely difficult to follow the mathematical development, understand the connections between the different results, and assess the paper's contributions.

Questions for authors

I do not have any specific technical questions for the authors.

5 comments

We apologize that we did not sufficiently consider the reader's perspective, making the problem and contributions difficult to understand and assess. We have revised the abstract, Introduction, definitions, and explanations throughout the paper.

  1. The problem and the connections between results. The abstract and Introduction now begin with the verification problem: a policy has been learned from historical data, but poorly observed actions may still allow another policy to achieve substantially higher average reward. We hold the learned policy fixed and query additional one-step observations at any state–action pair to establish that no policy exceeds the candidate's average reward by more than a prescribed tolerance. The two LPs bound this possible improvement; their response to uncertainty guides sampling; the analysis then gives the observations needed for that bound to reach the acceptance threshold. The Introduction illustrates these connections with a queue-control example.

  2. The undefined quantities and data terminology. Section 2 now defines g_M^*(s) as the best average reward attainable from initial state s, and policy loss as the largest gap from this optimum over initial states. The “incumbent” is the candidate held fixed during verification; ε is the permitted loss, and δ bounds the probability of false acceptance. We removed the diameter notation from the setup. The confidence-set paragraph defines r⁻ and r⁺ as the lower and upper confidence limits for each pair's mean reward before using them.

A “row” is a state–action pair. Its “prefix” consists of the first observations collected there; grouping a trajectory's transitions by state and action gives such observations. Conditional on the past and the selected pair, the next reward and successor follow that pair's fixed joint distribution. Historical and new observations follow the same law, so the assumed reward and transition dynamics remain unchanged. Logging actions may depend on earlier observations but must precede their own outcomes; observations cannot be selectively retained according to those outcomes. Section 2 states these conditions directly in place of the unexplained logging terminology.

  1. Occupancies, flows, and the subsequent development. Section 3.1 defines occupancy as the long-run expected fraction of time spent taking an action in a state, and transition flow as the corresponding fraction of transitions to a successor. It explains flow balance before presenting the constraints and interpreting the LP objectives. Figure 1 shows how the loss bound connects sampling and acceptance. Sections 4.1–4.3 proceed from each pair's uncertainty contribution to its sampling weight and verification cost; Section 4.4 explains how history reduces the remaining work, and Table 1 separates the results' assumptions.

We would be grateful for the opportunity to have the revised manuscript reassessed.

I thank the authors for their response and for the revisions made to the paper. These changes have certainly improved the clarity of the presentation, particularly in Section 2, and it is now possible to understand the actual problem the paper aims to address. However, I still cannot recommend accepting the paper in its current form, as significant issues with clarity and presentation remain.

In particular, several questions remain unresolved. For example, that paragraph that starts at line 95 now describes what the verifier receives as input and what it returns, but the paper never clearly explains what the verifier as an object actually is or how it operates. In Equation (1), the verifier is denoted by PM\mathcal{P}_M, and the authors state that the probability of accepting a policy π\pi at a finite time when its suboptimality gap Δπ\Delta_\pi exceeds ε\varepsilon is at most δ\delta. However, in Equation (2), the same notation is used for a verifier that accepts a set E\mathcal{E}. It is unclear how these two formulations are related and what the verifier actually does.

Overall, I appreciate the effort the authors have put into revising the manuscript, and I believe the paper may contain valuable theoretical results. Nevertheless, the presentation still makes it unnecessarily difficult to understand the proposed framework and evaluate its contributions. For this reason, I maintain my recommendation to reject the paper in its current form.

I would encourage the authors to devote more attention to the exposition, carefully review the manuscript for undefined terminology and unclear notation, and revise the presentation to make the logical connections between its components more explicit. I believe that a substantially clearer presentation would make the work much more accessible and strengthen a future submission.

Thank you so much for your honest feedback and for taking the time to review our paper so carefully! Although you gave a negative rating, we really think your suggestions are fair and valuable, and we truly appreciate them. Your responsibility is important to the whole community, we think!

We'll try our best to make the paper as strong as possible as quickly as we can (we've actually been working really hard on it these past days!).

If possible, we'd still really love it if you could take another look before the discussion ddl. And if the new version addresses your concerns well enough, we'd also really hope you might consider changing your rating.

Thanks again for all your time and help!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.