acceptodds
Under review as a conference paper at ICLR 2027

Post-Edit Regret for Lifted Quotients: Exact Accounting and Feasible Certificates

Abstract

A state-action abstraction is deployed through a particular coarse model, optimizer, and policy lift; its realized regret reflects this full deployment, beyond the aggregation map. For finite-horizon Kullback-Leibler (KL)-regularized control, we derive an exact signed ledger for this solve-lift-deploy process, separating prior, transition, optimization, and evaluation-cost mismatch. We identify the local price of fixing the environment dynamics as an information projection, decompose it into successor tilting and action reweighting, and allocate the global price through counterfactual occupancies. A residual-control identity then combines this information cost with the original-to-surrogate cost difference. It yields a coupled, dynamics-feasible regret envelope contained in the separate-error envelope. Its raw width vanishes exactly when the combined residual is policy-invariant, equivalently a Bellman potential difference; cancellation can therefore give exact certificates even when separate error budgets remain positive. Finite-model benchmark results evaluate the separate envelope: among 370 strictly positive-width candidate pools, 54 uniquely certify the true optimum, 102 partially prune, and 214 abstain, with no false certifications. Taxi action refinement reduces exact regret by 37.1%; uniform model-error padding covers all 556 nonzero-error pools and remains informative in 494. Independent path enumeration and randomized algebraic audits support the underlying identities. Together, these results provide exact post-deployment accounting and an interpretable hierarchy of certificates for explaining abstraction effects and certifying decisions.

Primary area:
reinforcement learning
Keywords:
state-action abstraction, KL-regularized control, regret certificates, information projection, model misspecification, reinforcement learning, robust control, policy evaluation

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_Kg45OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

I understand that the authors are investigating how much additional regret is generated in KL-regularized finite-horizon control when a policy is first solved in an abstracted/compressed MDP and then lifted back to the original environment for execution. The paper decomposes this loss into a four-term signed identity and compares two types of posterior certification intervals: independent and coupled. I believe precise error accounting is valuable, but it is not the same as a practical policy selection method.

Critical strengths

S1/S2: I prefer the treatment of signed regret accounting. Simply taking the absolute values of the solution error, abstraction error, and policy-lifting error and summing them may obscure the offsetting effects between them; the authors’ precise decomposition clarifies these offsets. The zero-width condition for the coupled certificate is not just a vague claim that “the bound is tighter,” but rather the result of explicit structural assumptions.

Critical weaknesses

W1: My first concern is that the paper does not clearly articulate the theoretical contributions relative to existing results on KL-control, Gibbs’ identities, and potential-based reward invariance. I’d like to know exactly what new theorems the quotient model and policy lifting yield—beyond simply rearranging a few familiar control identities.

W2: I have questions about the practical utility of the certificate. Even if the coupled interval is narrower than the independent interval, this does not mean it can select high-reward policies faster. I would prefer to see, given the same set of policy candidates and tolerance, exactly how many more feasible policies it certifies, how many fewer candidates it retains, and how much solution time it saves; if direct target policy evaluation is faster, the practical advantage of the certificate method needs to be redefined.

Questions for authors

Q1: I hope the authors will specify which of the new theorems relies on quotient-policy lifting, relative to existing KL-regularized control and reward invariance theories.

Q2: I request a comparison of the coupled/independent certification methods with direct target interval filtering, using the same candidate pool, the same threshold, and the same computational cost.

3 comments
AuthorsOpenReview ↗

The specific contribution beyond stochastic-control corrections and reward invariance

We thank you for recognizing the exactness and interpretability of the signed regret decomposition, including its separation of deployment mismatches while preserving cancellation. We also appreciate your positive assessment of the structural characterization of certificate tightness through dynamical feasibility, error cancellation, and the Bellman-potential condition for zero width.

Thank you as well for your constructive criticism concerning the focus and novelty of the contribution, its relationship to prior work, and the practical significance and empirical evaluation of the certificates.

Your suggestions helped us sharpen the paper's focus and identify the comparisons needed to assess its contribution. We have clarified the distinction between our results and the stochastic-control and reward-transformation principles they build on, including a more explicit discussion of Arriojas et al. (Sections 1 and 8). We have also added matched evaluations of the coupled and separate certificates, direct objective screening, and exact regret on additional energy and inventory tasks, reporting interval widths, certification outcomes, and computational costs (Sections 7.2–7.4; Appendix J.4). We hope these additions make the contribution and its measured benefits and limitations clearer as we address your questions below.

Q1. Which theoretical results are genuinely new relative to existing work on KL-regularized control, stochastic dynamics corrections (e.g., Arriojas et al., UAI 2023), and potential-based reward invariance, and what fundamentally new insight does the quotient-model construction provide? (W1: Insufficiently established novelty, unfocused contribution, and incomplete related work)

We revised Sections 1 and 8 to distinguish the established foundations from the specific contribution. Arriojas et al. (UAI 2023) address fixed versus unconstrained stochastic dynamics through a transformed inference problem with the same optimal policy. Gibbs/KL identities, corrective soft tasks, and potential-based invariance are principles we build on.

We connect those principles to the coarse model we solved and the policy lift we used and a regret breakdown that keeps the real dynamics and lets positive and negative terms cancel. Theorems 3.1–3.2 identify signed prior and continuation-value witnesses for the actual coarse solve and lift that keeps the prior's relative action probabilities within each group, evaluated under the original dynamics. Theorems 4.1–4.2 connect the projection that keeps the environment's transition probabilities fixed to a joint residual that adds the accumulated information premium to the evaluation-cost difference.

Theorem 5.2 identifies the raw coupled width as:

F_C &= H+(C-\widetilde C),\\\\ W_{\mathrm{cpl}} &= \mathbb E_{Q^\rho}F_C-\min_{Q\in\mathcal Q_D}\mathbb E_QF_C. \end{aligned}$$ The expectation follows the projected policy, and the minimum keeps the original dynamics fixed. Their difference is the projected policy's extra expected residual cost above the best feasible value, without the KL penalty. The projected policy's positive visit probability for each allowed, reachable state–action pair makes zero raw width equivalent to the expected residual cost being the same for every allowed policy, or the stated Bellman-potential condition. Thus the exactness criterion concerns the controllable part of the combined residual. To show why this distinction matters, Appendix E (p. 17) fixes the surrogate and chooses the evaluation-cost difference to cancel the information premium. The coupled residual is then zero and the coupled certificate is exact, while separate mismatch budgets can remain positive. This is an analytical example, not a benchmark result. The quotient records which model was solved and how its policy was lifted. Identical state/action maps can therefore lead to different regret when the declaration changes. The residual and invariance principles do not themselves require a quotient; our claim concerns their connection to the deployment account and this certificate's exactness criterion.
Reviewer_Kg45OpenReview ↗

Assessment after the coupled comparison

The coupled comparison answers my earlier concern about missing evaluation. At tolerance 0.01, certifying 83 of 160 inventory candidates rather than 65 is a useful improvement over the separate envelope. The signed ledger and the zero-width condition also have clear explanatory value, and the discussion of prior work is much clearer now. I still find the case for acceptance borderline, and will keep my score at 2. In the matched study, both regret screens retain every candidate, while direct evaluation makes a unique choice in all 37 pools. For absolute regret, exact evaluation is also cheaper even after including the shared fine-optimum solve: 5.27 versus 24.7 seconds in the energy study. All 160 threshold-test candidates already meet the strictest tolerance, so that experiment shows better certification of acceptable policies but leaves the wider decision benefit open. I appreciate the more focused claim about interpretation and exactness; I just don't yet find that contribution strong enough, together with the current results, to recommend acceptance.

My concerns regarding whether to accept the paper have not yet been resolved; I still need to continue discussing this with the other reviewers and the AC.

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

This paper proposes a theory to account for the regret of a policy from an abstracted state-action space once it is deployed in the original environment, decomposing it into regret that sources from either the prior, transition, optimisation, or evaluation-cost mismatch. They demonstrate empirically that the theory holds empirically to numerical precision, and that the decomposition can be used to guide abstraction edits to reduce policy regret.

Critical strengths
  • The problem, of improving abstracted policies that are to be deployed in more fine-grained environments, is a compelling one.
Critical weaknesses
  • The paper is very difficult to read. The text is poorly written, with numerous terms introduced without explanation, and the notation is very heavy, making the main arguments and method hard to follow. E.g. in the Introduction alone, hth_t, CC, C~\tilde C, RtR_t, and Ωf\Omega_f are all used without explanation.The paper seems heavily AI generated with limited human editing to improve the legibility. I am unable to properly discern the novelty and impact of the contribution due to the poor presentation.
  • The analysis is limited only to tabular policies, which is a very restricted setting. It is unclear to me how well this can transfer to learned policies.
  • The coupled certificate, which would be the stronger result, is not evaluated empirically, only the looser separate certificate is. It remains unclear whether this tighter certificate resolves anything more than the other empirically.
Questions for authors
  • Can the authors elaborate clearly on the novel contribution of this paper? And can the key ideas be relayed succinctly and more legibly than in the current manuscript?
  • Can this accounting easily extend to more complex environments/non-tabular policies, or would that require significant new material?Wh
  • Why is the coupled certificate not empirically validated?
3 comments
AuthorsOpenReview ↗

A clearer statement of the contribution and its key ideas

We thank you for recognizing the importance of improving abstracted policies for deployment in finer environments and for describing this problem as compelling.

Thank you as well for your constructive criticism of the presentation and notation, the clarity of the novelty and impact, the applicability to learned policies, and the missing empirical evaluation of the coupled certificate.

Your feedback helped us identify where the exposition needed to be clearer. We have rewritten the introduction to explain the central questions before introducing the notation, clarified the contribution and its relationship to prior work, and added experiments with the coupled certificate and trained neural policies in finite energy and inventory models (Sections 1–2, 7.2–7.3, and 8; Appendix J.1). We hope these changes make the paper easier to follow and provide a clearer account of what the theory and experiments establish for learned policies.

Q1. Can the authors elaborate clearly on the novel contribution of this paper? And can the key ideas be relayed succinctly and more legibly than in the current manuscript? (Presentation, heavy notation, and unclear novelty and impact)

We agree that the original introduction introduced too much notation before explaining the main idea. We rewrote Sections 1–2 to start with the deployment problem and define the main quantities before the detailed analysis. We now explain how the main results fit together:

We account for the full deployment because the same state/action partition can accompany different coarse models, priors, costs, and lifts. Theorems 3.1–3.2 (p. 3) weight each mismatch by the states and actions the deployed policy actually visits.

We also distinguish the controller's choices from random outcomes. An unconstrained inference calculation can favor unusually good random successors, while the controller chooses actions under the fixed environment transition law. Theorem 4.1 (p. 4) quantifies that restriction and separates treating favorable next states as more likely from changing how likely each action is to be chosen.

We combine this information cost with evaluation-cost mismatch before bounding regret. Write HH for the accumulated information premium, CC for the evaluation cost, and C~\widetilde C for the surrogate cost. Theorem 5.2 (p. 5) gives

FC=H+(C−C~).F_C = H+(C-\widetilde C).

Wcpl=EQρFC−min⁡Q∈QDEQFC.W_{\mathrm{cpl}} = \mathbb{E}_{Q^\rho}F_C-\min_{Q\in\mathcal{Q}_D}\mathbb{E}_QF_C.

Here QρQ^\rho is the projected policy's trajectory distribution, and QD\mathcal{Q}_D contains the feasible trajectory distributions with the original initial law and transition dynamics. The raw width WcplW_{\mathrm{cpl}} is measured before setting negative lower bounds to zero. Under the stated support conditions, it vanishes exactly when every feasible policy gives the same expected combined residual. The certificate can therefore be exact even when separate error budgets are positive; the regret itself can still be positive.

We make this connection between deployment accounting and certificate exactness the focus of the paper. Section 8 (p. 10) credits the established Gibbs/KL identities, stochastic-control corrections, corrective soft tasks, and reward-invariance results, including Arriojas et al. We build on those principles to obtain the stated deployment account and certificate characterization.

We also explain the fine and surrogate costs, which states could be reached through allowed actions and transitions, local information premium, and how much the expected cost difference can vary across allowed policies before using them in the main analysis. These changes aim to let readers understand the purpose of each quantity before following its notation.

Q2. Can this accounting easily extend to more complex environments/non-tabular policies, or would that require significant new material? (Restricted tabular setting and applicability to learned policies)

To examine learned policies directly, we trained two-hidden-layer networks of widths 64 and 128 on five energy models and 32 inventory models. We used reverse-KL distillation for 50 passes and trajectory-based regularized policy gradients for 2,000 updates. The study contains 148 configurations and three scheduled evaluations per configuration, giving 444 checkpoints (Section 7.3; Appendix J.1).

The accounting uses the action probabilities induced by a policy, so using a neural network for the policy does not itself invalidate the finite-model identity. For a supported approximate coarse policy, Eq. (6) (p. 3; Appendix B.2, p. 14) adds the nonnegative solver-error term

Esolve=ε∑t<TEXt∼Q^πˉKL!(πˉt(⋅∣ϕ(Xt)),∥,πˉt⋆(⋅∣ϕ(Xt))).E_{\mathrm{solve}} = \varepsilon\sum_{t < T}\mathbb{E}_{X_t\sim\widehat Q^{\bar\pi}} \mathrm{KL}\\!\left( \bar\pi_t(\cdot\mid\phi(X_t)) \\,\Vert\\, \bar\pi_t^\star(\cdot\mid\phi(X_t)) \right).

Here πˉ\bar\pi is the learned coarse policy, πˉ⋆\bar\pi^\star is the coarse optimum, ϕ\phi maps fine states to coarse states, and ε\varepsilon is the regularization temperature. We take the expectation under Q^πˉ\widehat Q^{\bar\pi}, the trajectory distribution obtained by lifting the learned policy and running it under the original fine dynamics. This weights the KL difference by how often the deployed policy actually visits each state. The coarse model's own training occupancy generally gives a different quantity.

We used exact finite-model evaluation of the learned probabilities to check this correction. Across the 444 scheduled checkpoints, the maximum ledger discrepancy is 1.02×10−131.02 \times 10^{-13}. The coarse-own and fine-deployment solver quantities differ by more than 10−810^{-8} in every final configuration. These results support the deployment-weighted correction for the trained policies.

We used one neural seed, so the study checks the accounting for these policies rather than learning stability across seeds. Continuous spaces and approximate evaluators require additional assumptions and error control; our results do not establish that extension.

Q3. Why is the coupled certificate not empirically validated? (Missing coupled-certificate evaluation and evidence of improvement over the separate certificate)

The submitted benchmark experiments tested only the separate envelope. We agree that this left the coupled construction without an empirical benchmark comparison, so we added matched evaluations in Section 7.2.

The full-population study uses five energy markets and all 4,202 eligible inventory products. We compare the same candidate policies and fine objectives within each pool. Coupling narrows all 21,035 main intervals and reduces mean clipped width by 14.25% in energy and 21.75% in inventory (Table 3, p. 9). Both regret screens still retain every candidate in the main pools, while direct evaluation uniquely selects. The measured improvement is interval precision, not better candidate ordering.

To test whether that precision supports additional absolute-regret decisions, we evaluated 160 candidates on a separate 32-product representative cohort. At regret-per-step tolerance 0.001, coupling certifies 22 candidates versus 9 separately; at 0.01, it certifies 83 versus 65 (Table 4, p. 9). Every affirmative decision agrees with exact regret. All 160 candidates satisfy even the strictest tolerance, so the experiment tests certification of acceptable policies. The thresholds are exploratory, and energy candidates remain unresolved.

We also report matched runtime and memory measurements in Table 11 (p. 25), including an exact-regret baseline with a shared fine-optimum solve. Direct evaluation and exact regret remain cheaper in the measured implementation. We report these outcomes so readers can assess what coupling adds and what it costs.

I thank the authors for their response. The additional policy experiments, and evaluation of the coupled construction are useful improvements to the paper. Nevertheless, I remain unsatisfied with the presentation of the work, and the clarity of the writing. Unfortunately, the work remains very difficult to parse, and while removing the unexplained notation from the introduction is a useful first step, I think the text needs significant re-writing to be deemed legible. Many terms are still left unexplained, leaving the reader (or at least me) very confused. For example, the entire fourth paragraph of the introduction introduces numerous terms (e.g. "coupled certificate", "separate envelope", "combined residual") that are not well defined previously, or explained afterwards. As a result, I think the paper cannot be accepted in its current form, and needs to undergo significant re-writing to convey the setting, contribution, and message of the work clearly. I will therefore maintain my score

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

The paper analyzes what occurs when one solves a finite-horizon, KL-regularized control problem after applying a state–action abstraction, then maps the resulting policy back via a prior-preserving lift, and finally executes it in the original environment. The focus is not on worst-case abstraction quality, but on explaining the specific losses incurred by this solve–lift–deploy pipeline.

The core contribution is an exact signed breakdown of deployed regret into four components—prior, transition, surrogate optimization, and cost transfer (Thm 3.2). It further describes the Gibbs-relaxation “fictitious control” as an information projection, decomposing it into successor tilting and action reweighting (Thm 4.1). A residual-control reformulation (Thm 4.2) yields a coupled regret interval contained within a simpler “separate” interval, and this bound is tight exactly when the residual is a Bellman potential difference (Thm 5.2). Lastly, a simulation-lemma-like padding argument addresses model mismatch (Thm 6.1).

The experiments use exact tabular dynamic programming on Taxi and several other small domains, and they evaluate only the separate interval with uniform padding. Across 370 pools with positive width, the screening procedure certifies 54, partially prunes 102, and abstains on 214, with zero false certifications.

Critical strengths

S1. The math is sound, and the paper is transparent about its scope

Every central claim is accompanied by a full proof. The authors clearly state what is not established: the ledger terms are not causal, the coupled interval is used only for the proof, and they do not assert any speedup. The protocol was set in advance of examining exact regret, and the screening step never incorrectly certifies.

S2. Distinguishing between mismatches that are significant for decision-making and those that are not is beneficial.

Thm 5.2 provides a precise characterization: the coupled width is zero if and only if FC=H+DCF_C = H + D_C is a Bellman potential difference. The example in App. E.4 demonstrates a case where the separate width is 2k2k while the coupled width is 0. Thm 4.1 also offers a clean framework for defining the "optimism" inherent in the "control-as-inference" paradigm within the context of stochastic dynamics; the condition for a "zero" value in this theorem is remarkably conciset(Cor. C.1). A single abstraction radius can't say any of this.

Critical weaknesses

W1. It remains unclear under what circumstances this certificate would actually be used.

Performing this calculation requires a complete, high-fidelity model and dynamic programming (DP) at a granular level. With such a model, each candidate can be evaluated precisely (see Prop A.1; all 32 candidates in Table 1 are evaluated correctly). App. E.3 further notes that solving Eq. (62) also yields exact values, with a comparable computational cost. Consequently, when the model is known, employing intervals offers no additional benefit.

Next, we consider the case of model uncertainty (Section 6), for which evidence remains limited. The maximum transition error tested is TV 3×10−53\times10^{-5} (Table 2), and already there 2B≈2.342B \approx 2.34 (Table 7). BB grows linearly in δt\delta_t, so at TV 10−210^{-2}, which is still quite small for a model estimated from samples, 2B2B would be about 780. That is more than ten times the Taxi regrets being compared (e.g. 55.99 vs. 35.24). The authors themselves note that it has not been proven whether the radii derived from data satisfy the "non-vacuity" property; furthermore, the paper does not test the tighter "padding" approach proposed for specific candidate models (Thm F.1).

This explanatory usage is also not particularly convincing. The figure is derived by performing addition and subtraction operations on two reference values ​​(Eq. 43):

RegC(Q^)=[JC~(Q^)−V‾dec]+[V‾dec−V~]+[EQ^DC−(VC−V~)]\mathrm{Reg}_C(\widehat Q)=\big[J_{\widetilde C}(\widehat Q)-\overline V^{\mathrm{dec}}\big]+\big[\overline V^{\mathrm{dec}}-\widetilde V\big]+\big[\mathbb E_{\widehat Q}D_C-(V_C-\widetilde V)\big]

Therefore, this method of decomposition is precise in its construction; choosing different intermediate values ​​or altering their sequence would yield a different, yet equally precise, decomposition. Since these terms do not represent causal relationships and may shift depending on the strategy employed, their diagnostic value must be empirically verified. Currently, the only evidence comes from Fig. 3—a scenario in which only one fault is injected at a time, and the "right channel" is known in advance. I would like to see a concrete example where examining the ledger reveals information that could not be obtained by merely observing the declarations.

W2. Major new tools are never tested, while those that have been tested are rarely adopted.

All screening results pertain to the "separate interval" scenario. The primary methodological contribution of this paper—the "coupled interval" approach—was not implemented in the experiments, even though it would only require one additional "hard" dynamic programming (DP) pass and one policy evaluation. In contrast, the "separate interval" method quickly fails. As shown in Fig. 2(a), when the transition probability drops to 0.995 or below, all geometric-transition pools opt to "abstain"; furthermore, in stochastic dynamic environments, only 77 out of 1,096 randomized programs are able to achieve an exact solution (if Ωf>0\Omega_f > 0, no exact solution exists at all; see Table 4).

Overall, out of 370 candidate pools, 214 opted not to participate (abstained). This includes all 40 "passenger-cost" candidate pools, even though the proportion of harmful candidates within these pools was as high as 53%–73%. Furthermore, the ranking results were inconclusive (with a navigation correlation of −0.24).

There's also no comparison with radius-, bisimulation- or simulation-lemma-based bounds, even though the introduction positions the work against abstraction radii. Everything is small and tabular, and the main text doesn't say which environment each pool family comes from.

Questions for authors

Q1. When would someone use the certificate instead of exact regret?

In light of Proposition A.1 and App. E.3, in what practical scenarios would using a "certificate" be a preferable choice? If the goal is to work with an estimated model, would it be possible to demonstrate "padded decisions" based on radii estimated from data (e.g., derived from sample counts), rather than the fixed radii presented in Table 2? Furthermore, providing information on runtime and memory usage for the Taxi task—as well as the largest state-space scale you have experimented with—would be highly valuable.

Q2. How does the coupled interval do on the existing pools?

Could you run the analysis on the current pools, especially the p≤0.995p \le 0.995 cells of Fig. 2(a) where the separate interval always abstains? It would also be useful to compare candidate-specific padding (Thm F.1) with uniform 2B2B on the 556 nonzero-error pools.

Q3. How should the ledger terms be read?

The split in Eq. (43) depends on which reference values are inserted and in what order. Would another order change the terms, and if so, which reading do you intend? Is there a non-injected example where the row-wise allocation shows something the totals hide?

3 comments
AuthorsOpenReview ↗

Absolute-regret decisions, sample-derived padding, and matched comparisons

We thank you for recognizing the soundness and completeness of the proofs, the transparency about the scope of the claims, the tests we planned in advance, and the absence of false certifications. We also appreciate your positive assessment of the Bellman-potential characterization of zero coupled width and the information-projection interpretation of stochastic-dynamics optimism.

Thank you as well for your constructive criticism concerning the practical use of the certificates, the tests of the tighter bounds, and the interpretation and diagnostic value of the ledger.

Your suggestions helped us identify where the paper needed stronger evidence and clearer explanation. We have added energy and inventory experiments comparing the coupled and separate certificates, comparisons with alternative bounds, sampling-based uncertainty experiments, and matched runtime and memory measurements (Sections 7.2 and 7.4; Appendix J). We have also added a natural deployment example and clarified the choice of reference tasks and what we can learn from the ledger (Sections 3 and 7.3). We hope these additions provide a clearer basis for addressing your questions and assessing the practical benefits and limitations of the certificates.

Q1. When would someone use the certificate instead of exact regret? (W1: Practical usefulness, model uncertainty, and computational requirements; W2: Benchmark scale)

We agree that a known fine model lets us rank the candidates by cost because every regret subtracts the same optimum. We use the certificates to explain absolute regret and characterize when combined discrepancies permit exact certification. A fine-optimum solve also determines regret exactly; we give a range for regret and show when it narrows to one exact value.

To test whether tighter bounds produce additional decisions, we evaluated five candidates on each of 32 inventory targets. Table 4 (p. 9) reports candidates certified below each regret-per-step tolerance:

ToleranceSeparateCoupled
0.0019/16022/160
0.0165/16083/160
0.1160/160160/160

We checked exact regret, and every candidate we marked as acceptable met the limit. All 160 inventory candidates satisfy even the strictest tolerance, so this tests certification of acceptable policies. The thresholds are exploratory; energy candidates remain unresolved.

We estimated uncertainty from new samples from the underlying distributions and simulated model runs. We repeated the sampling experiment for all 32 products five times at each sample count, and every model row met its error bound. The exact 95% interval ([47.82%, 100%]) is still wide, so we cannot assess reliability precisely. We tightened the bounds under the stated assumptions, but still could not rule out any candidate (Section 7.4; Appendix J.3).

To make costs transparent, we timed identical five-candidate pools on five energy and 32 inventory tasks. Table 11 (p. 25) gives evaluation time after building the candidates (in seconds) as the median across tasks, after taking the median of five H200 timings per task:

MethodEnergyInventory
Direct evaluation4.390.0476
Exact regret5.270.0582
Coupled24.70.215
Separate37.20.562

Exact regret includes solving the detailed model once for all five candidates and remains cheaper. The coupled method allocated at most 4.78 GiB of GPU memory at one time. The timed energy model has 62,208 states; the finer evaluated model has 247,296 states, seven actions, and horizon 168 (Table 2). These measurements do not supply the isolated Taxi runtime and memory you requested.

Q2. How does the coupled interval do on the existing pools? (W2: Missing coupled-certificate evaluation and frequent abstention; W1: Untested candidate-specific padding)

We added matched comparisons on five energy markets and 4,202 inventory products to measure tightening and screening separately (Section 7.2; Table 3). We keep each pool's policies, fine dynamics, costs, starting state distribution, reference, support, and precision fixed.

Coupling narrows all 21,035 main intervals. Average widths after setting negative lower bounds to zero decrease from 106.34 to 91.19 in energy (14.25%) and from 0.4284 to 0.3352 in inventory (21.75%). Both regret screens nevertheless retain every candidate; direct evaluation uniquely selects in every main pool. Tighter intervals therefore do not establish better ordering.

To test padding, we used the same 32-product sampled-model cohort. At 1,024 samples per primitive row, mean coupled widths are 140.52 with uniform padding, 100.87 with submitted candidate-specific asymmetric padding, and 61.20 with the all-row symmetric refinement, which uses the completed estimated optimum (Section 7.4; Appendix J.3).

The requested original p≤0.995p \le 0.995 and 556-pool reruns remain incomplete because their primitive inputs are unavailable. We present the added tasks as additional evidence, without claiming that coupling resolves those original abstaining pools.

We show that 77/1,096 counts separate intervals that narrow to a single value, rather than programs admitting exact DP solutions. The 40 passenger-cost pools are separate from the 370 positive-width frontier evaluations (Appendix H.2–H.3).

Q3. How should the ledger terms be read? (W1: Reference dependence and diagnostic value of the ledger)

We agree that reference choices matter. We fix the intermediate tasks to follow deployment: the coarse problem actually solved, the coarse model's costs under the original dynamics, and the original evaluation task. The breakdown may change if we choose different comparison tasks. It stays the same if we only change the order of addition. We clarified this distinction in Section 3 and Appendix J.1.

To demonstrate diagnostic information without injecting faults, we added the unchanged Belgian deployment (Section 7.3). Positive transition contributions total +1.6957 and negative contributions −0.7592, leaving +0.9366. Their absolute sum is 2.4549, so 61.85% cancels. The net total hides these opposing contributions.

The 12 classes with the highest unweighted transition discrepancy each contribute at most 0.0000304 in absolute signed class total; the largest absolute signed class contributes +0.0374. We find different locations because we consider both how often the policy visits each state–action pair and the expected future costs.

We tested repairs separately because editing changes the solution and its occupancies. The signed-transition selector worsens regret on 3,340/4,202 inventory tasks, versus 2,308 for the predetermined random edit (Appendix I.4). These results show why a large ledger contribution does not identify a beneficial repair.

We track how the best policy's visits change as we shift from planning to evaluation costs. The deployed cost difference alone misses this. Across 160 representative inventory integrations, endpoint discrepancies remain below 8×10−158 \times 10^{-15} (Appendix G.3).

Missing comparisons with abstraction-radius, bisimulation, and simulation-lemma bounds

We added matched Bellman-residual, TV/span simulation, and bisimulation-related diameter bounds to test how coupling compares under identical policies and fine models (Section 7.4; Appendix J.2). Across 185 representative comparisons—25 energy and 160 inventory—the coupled intervals are narrower than each comparator, and every compared interval covers exact regret. The bisimulation comparator is an upper bound that may overestimate the exact value, not the exact pairwise metric; we restrict the comparison claim accordingly.

Inconclusive ranking performance

We compared certificate rankings with exact regret because some upper bounds overshoot more than others, which can change the ranking. Taxi Spearman correlations are 0.6339 versus 0.4041 for the uniform score, but the paired 95% difference interval [−0.0365, 0.4957] includes zero. The cross-domain interval [−0.0948, 0.6895] also includes zero; navigation correlation is −0.2381 (Appendix H.4).

Unclear correspondence between candidate pool families and environments

We now name the pool environments so readers can trace each result to its model (Section 7.1; Appendix H.1). Geometric-transition and passenger-cost pools use Taxi models that group states together; movement-action pools refine its action classes. Taxi has 501 planning states, six actions, horizon 50, and temperature 1.

We report added studies separately in Section 7.2 and Table 2

Thank you for the detailed rebuttal and additional experiments. I appreciate the authors' efforts, particularly the new evaluation of the coupled certificate, baseline comparisons, and experiments on model uncertainty. These additions address several of my original concerns.

However, my main concern regarding practical utility remains. The results still suggest that computing exact regret is cheaper when the fine model is available, and the advantages of the proposed certificates in realistic settings remain unclear.

Overall, while the rebuttal meaningfully strengthens the paper, I will maintain my original rating of 2 (Weak Rejection).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Exact deployment accounting, empirical coupling, and learned-policy validation

We thank the reviewers for their careful reading and constructive comments. Their feedback helped us see where the paper needed a clearer explanation and stronger experimental support.

We rewrote the introduction to explain the deployment problem before introducing the notation, and expanded the related-work discussion to clarify what our results add to existing theory (Sections 1–2 and 8). We now focus the contribution on accounting for a particular deployment and identifying when combined mismatches allow an exact regret certificate.

To test the coupled certificate, we added comparisons under the same conditions on finite models for five energy markets and 4,202 inventory products (Section 7.2). Coupling narrows all 21,035 main candidate intervals, reducing average reported widths by 14.25% in energy and 21.75% in inventory. We report this improvement separately from candidate ordering: both regret screens still retain every candidate in these main pools. We also tested absolute-regret thresholds to show when tighter bounds certify additional acceptable candidates.

To address the questions about learned policies, we trained neural policies and checked the extended accounting at 444 scheduled checkpoints (Section 7.3). The largest difference between the ledger and directly computed regret is 1.02×10−131.02 \times 10^{-13}. We used one random seed and finite models, so these checks support the accounting for the trained policies without establishing stable learning across seeds or a continuous-space extension.

To clarify what the ledger tells us, we added an unchanged Belgian deployment example (Section 7.3). It shows how positive and negative transition contributions can cancel, and why model discrepancies alone need not identify the parts that matter most during deployment. We also explain why these contributions do not tell us which repair will improve performance.

To assess practical use, we added experiments that estimate uncertainty from samples, comparisons with alternative bounds, and runtime and memory measurements under the same conditions, including direct evaluation and exact regret (Section 7.4; Appendix J). We state the limits of this evidence explicitly: exact evaluation remains cheaper in the measured implementation, the tests with sample-based bounds still do not rule out candidates, and we have not completed the requested reruns on the original candidate groups.

We hope that these revisions, additional experiments, and the detailed responses below have sufficiently addressed the concerns raised by the reviewers.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.