acceptodds
Withdrawn from ICLR 2027

Candidate Completion for Exact Off-Policy Calibration of Best-of-M Policies

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

11 views

Abstract

Choosing the highest-scoring action from several candidates changes which prediction errors a controller encounters. A bound calibrated on the original policy's data can therefore lose its intended coverage. We introduce candidate completion, which calibrates best-of-M policies using logged trajectories and samples from the preserved data-collection policy. It places each logged action among fresh competitors and tests whether the deployed rule selects it. Applying these tests along a trajectory yields exact target-policy samples without evaluating action densities or collecting new environment outcomes. Ordinary and weighted calibration then provide finite-sample prediction bounds. In repeated-selection experiments on directly observed control rewards, completion corrects Walker2d-high coverage from 78.7% to 90.4% under two-step best-of-four selection. Across all 27 setting/group comparisons, its mean absolute coverage difference from a target-data oracle is 0.69 percentage points, versus 2.12 for behavior calibration. In controlled equal-budget comparisons with 500 logged actions, completion achieves 90.4–91.7% coverage for 4–16 candidates, while score-CDF weighting achieves 86.6–87.3%. Additional selection sweeps, tied-score experiments, and complete-trajectory checks support the sampling and calibration guarantees.

Primary area:
reinforcement learning
Keywords:
conformal prediction, off-policy evaluation, best-of-N selection, calibration, distribution shift, offline reinforcement learning, prediction bounds

Reviews

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

The paper studies off-policy prediction of a fixed policy’s finite-horizon return using independent trajectories collected by a behavior policy μ\mu. The target policy samples MM i.i.d. actions from μ(⋅∣s)\mu(\cdot\mid s), selects a highest-scoring candidate, and optionally mixes this selection rule with μ\mu. Given a fixed predictor G(s,a)G(s,a), the objective is to construct a lower prediction bound G(s,a)−q^G(s,a)-\widehat q with marginal coverage at least 1−α1-\alpha under the target policy.


The authors propose candidate completion (CC) method that adds M−1M-1 fresh behavior actions around each logged action and uses candidate comparisons to accept or reject the logged trajectory, without collecting new environment outcomes or evaluating action densities. The retained trajectories have exactly the target-policy distribution, with expected sample count n/[1+ϵ(M−1)]Hn/[1+\epsilon(M-1)]^H. Standard conformal calibration of their prediction residuals then provides the desired finite-sample marginal coverage guarantee.


The paper also develops weighted calibration and approximate-sampler extensions. Experiments on synthetic problems and MuJoCo tasks evaluate coverage and prediction loss against behavior-policy calibration, score-CDF weighting, and target-policy calibration.

Critical strengths

Strengths. The paper includes extensive empirical validation across controlled synthetic problems and multiple MuJoCo environments, with additional studies of tied scores, early termination, candidate budgets, and approximate behavior samplers. The breadth of these experiments reflects substantial implementation and evaluation effort. The tables and accompanying numerical results are generally well organized and visually clear, and the detailed supplementary results help readers inspect the method’s behavior across different settings.

Critical weaknesses

Beyond the strengths, I have concerns about the theoretical analysis, presentation, and practical value, organized into three main concerns below.


(a) Writing and problem formulation. The presentation does not adequately orient readers with a standard RL background to the problem being studied. The abstract introduces prediction errors, calibration, coverage, and best-of-MM policies before identifying the predicted outcome and the form of the returned bound, leaving readers to infer how these familiar terms fit together. In particular, the intended meaning of predictive coverage should be made explicit at its first appearance in the abstract, given the established use of “coverage” for behavior-target overlap in offline RL and OPE [1, 2]. The explanations subsequently provided in the introduction do not sufficiently clarify the relationship between this prediction task and familiar OPE objectives. The opening requires substantial revision to establish the research question and its scope before presenting the mechanism and experimental results.

Furthermore, Eq. 5 and 6 use the informal event labels “passes” and “retained” without displaying their mathematical definitions alongside the equations, requiring readers to assemble the event structure and the relevant randomness from the surrounding text and Algorithm 1. These examples illustrate a broader lack of precision and clarity in the presentation, and the paper therefore requires a substantially reorganized introduction and a more explicit problem formulation that establishes the objects, assumptions, and distinctions before presenting the method and its significance.


(b) Limited contribution and practical value. Sec. 3 requires GG to be “fixed before calibration” but imposes no accuracy or informativeness conditions. Thm. 2 therefore guarantees coverage even for an uninformative predictor, without ruling out practically vacuous bounds, see Eq. 7 that explicitly permits q^=+∞\widehat q=+\infty. The paper provides no theoretical characterization of how predictor error affects bound tightness or excess prediction loss, despite related conformal OPE work establishing asymptotic oracle approximation under known behavior policies and consistent conditional quantile estimation [3]. This gap between coverage validity and predictive usefulness is my central concern and the main reason for my low score. Unless the authors substantively address it (as well as other main concerns), I would maintain 1 (strong reject).

In addition, the paper provides no theoretical comparison of prediction-bound tightness between CC and other baselines. Its optimality result concerns acceptance rates within the restricted class of “exact rejection of unchanged whole trajectories” (App. C.5). Table 1 reports normalized pinball losses of 0.16030.1603 for CC and 0.15970.1597 for score-CDF weighting. The direct paired comparisons in App. B.3, Table 14, also report positive mean loss differences for CC relative to CDF at the minimum candidate budgets for M=4,8,16M=4,8,16, while Table 8 reports identical rounded losses of 0.15950.1595 for weighted CC and score-CDF weighting at M=4,R=64M=4,R=64. Thus, the reported RL experiments do not demonstrate a consistent prediction-loss advantage over score-CDF weighting, and the corresponding theoretical tightness comparison remains absent.


(c) Missing discussion of modern OPE and distributional RL studies. Sec. 2 discusses conformal OPE but omits directly relevant work on distributional OPE and its connection to distributional RL [4]. In particular, Huang et al. [5] develop doubly robust return-CDF estimation with efficiency analysis, and Hong et al. [6] provide finite-sample error analysis for distributional OPE under function approximation.

The authors should explain how their residual-quantile calibration relates to these established objectives and compare the information requirements, approximation assumptions, and statistical guarantees. This omission leaves CC’s relationship to existing distributional OPE methods and its distinct contribution insufficiently articulated.


References

[1] Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., & Russell, S. (2023). Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism. arXiv [Cs.LG]. http://arxiv.org/abs/2103.12021

[2] Chen, J., & Jiang, N. (2019). Information-Theoretic Considerations in Batch Reinforcement Learning. arXiv [Cs.LG]. http://arxiv.org/abs/1905.00360

[3] Zhang, Y., Shi, C. & Luo, S.. (2023). Conformal Off-Policy Prediction. <i>Proceedings of The 26th International Conference on Artificial Intelligence and Statistics</i>, in <i>Proceedings of Machine Learning Research</i> 206:2751-2768 Available from https://proceedings.mlr.press/v206/zhang23c.html.

[4] Bellemare, M.G., Dabney, W. & Munos, R.. (2017). A Distributional Perspective on Reinforcement Learning. <i>Proceedings of the 34th International Conference on Machine Learning</i>, in <i>Proceedings of Machine Learning Research</i> 70:449-458 Available from https://proceedings.mlr.press/v70/bellemare17a.html.

[5] Huang, A., Leqi, L., Lipton, Z. & Azizzadenesheli, K.. (2022). Off-Policy Risk Assessment for Markov Decision Processes . <i>Proceedings of The 25th International Conference on Artificial Intelligence and Statistics</i>, in <i>Proceedings of Machine Learning Research</i> 151:5022-5050 Available from https://proceedings.mlr.press/v151/huang22b.html.

[6] Hong, S., Qi, Z. & Wong, R.K.W.. (2025). Distributional Off-policy Evaluation with Bellman Residual Minimization. <i>Proceedings of The 28th International Conference on Artificial Intelligence and Statistics</i>, in <i>Proceedings of Machine Learning Research</i> 258:4006-4014 Available from https://proceedings.mlr.press/v258/hong25c.html.

Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Usefulness of the bounds: a new finite-sample risk bound, a predictor experiment, and a rewritten problem setup

Thank you for the detailed review. The revision resolves your central concern with a finite-sample risk bound (Theorem 6) and a predictor experiment (Table 2); we answer each point in order.

(a) Writing and problem formulation. The abstract now states the predicted quantity (the HH-step return), the form of the output (the predictor minus a calibrated correction) and the guarantee before the method, and defines predictive coverage at first use. The introduction separates it from the overlap sense of coverage [1, 2]; Section 5.4 relates the two through a state-occupancy ratio. Section 3 defines the data, the target policy, the outcome and validity before the method. The events are written out: Equation 4 defines passes (U≤W/CU \le W/C), retained means Ut≤ptU_t \le p_t at every step, and Equations 6 and 7 display these events. The method names were reduced to three rules (rejection, weighted, certified).

(b) Validity versus usefulness. This was the main gap.

Theory (Theorem 6). Let εG\varepsilon_G be the excess pinball risk of the best constant shift of the predictor GG over the ideal conditional quantile; it depends on GG alone. With probability 1−δ1 - \delta:

  • for the original rule with mm retained trajectories, excess risk ≤εG+am2/(2λ)\le \varepsilon_G + a_m^2/(2\lambda), with am=O(log⁡(1/δ)/m)a_m = O(\sqrt{\log(1/\delta)/m});
  • for the certified rule, excess risk ≤εG+(β+γn)2/(2λ)\le \varepsilon_G + (\beta + \gamma_n)^2/(2\lambda), where β\beta is the certified clipped mass and γn=O(Vlog⁡(1/δ)/n+Llog⁡(1/δ)/n)\gamma_n = O(\sqrt{V \log(1/\delta)/n} + L \log(1/\delta)/n) (cap LL, second-moment bound VV).

Here λ\lambda is a lower bound on the error density over the band in which the estimated quantile can fall (stated in Theorem 6), and the error is assumed continuous with a finite mean. So calibration adds a term that vanishes with more data (up to the chosen β\beta), and a predictor close to the conditional quantile yields a near-optimal bound. Part one is a finite-sample form of the asymptotic result of [3], without propensities.

Experiment (Table 2). We fit a quantile regression of the predictor's error on separate data and calibrate the adjusted predictor. On the 243 short-horizon evaluations this lowers the loss of the certified bound by 19% on average (in 98% of evaluations), and by 14–26% on the new long-horizon data, with coverage remaining at the nominal level; in the short-horizon experiment the calibrated bound stays within 0.6% of calibration on target data for either predictor.

Infinite corrections. Proposition 1 bounds the probability that the certified rule returns +∞+\infty as a function of nn, and Theorem 4 shows that with too few trajectories every valid procedure must be uninformative in the worst case. This also replaces the earlier optimality statement, which was restricted to rejection of whole trajectories: the lower bound now covers every valid procedure.

Tightness against score-distribution weighting (Proposition 5). Completion weights are the minimum-variance unbiased estimates of the ratio. The plug-in is biased for M≥3M \ge 3 at any fixed number RR of competitors, so a weighted rule using it targets a different error distribution and its coverage error does not vanish with more logged data. The controlled sequential comparison shows this directly: with M=4M = 4 and R=3R = 3 the plug-in covers 81.4% over three steps and 76.5% over five, as the proposition predicts, while completion gives 90.0–91.4% with the same competitors. In the original MuJoCo comparison at the minimum budget (Table 24), completion is at or above the requested 90% in every setting (90.5%, 90.9%, 92.2% for M=4,8,16M = 4, 8, 16), where the plug-in gives 89.8%, 89.6% and 91.4%. At larger budgets the plug-in's bias is of order 1/R1/R and the two losses are nearly identical, which explains the identical rounded losses you noted (Table 8 of the original submission, Table 22 in the revision). Completion therefore provides finite-sample validity at every competitor budget with comparable prediction loss.

(c) Distributional off-policy evaluation. Section 2 discusses [4], [5], [6]; Appendix F compares information requirements, assumptions and guarantees. In short: the estimators of [5] need behavior and target action probabilities (and a model for the doubly robust version) and give error bounds for the estimated return distribution; [6] fits the return distribution in a Markov model, with error bounds under realizability and a multi-step variant for the non-realizable case; completion needs only a sampler and gives finite-sample predictive coverage. Table 3 compares with the finite-sample importance-sampling constructions we could run (UnO band, OPRA IS-CDF band, PAC rejection sampling, weighted conformal rule): with exact ratios and 50,000 trajectories they return no bound at 15 and 20 steps, where the certified rule covers 92.2% and 96.6%.

We would welcome your assessment of whether these results address your concerns.

I thank the authors for their response and the additional analysis. However, the revision does not give me sufficient grounds to raise my rating.


(a) The writing still needs substantial restructuring. I still find it difficult to follow a central argument through the rejection, clipping, stitching and pinball-risk results (Secs. 4–6, pp. 4–8), particularly as their assumptions and objectives change (Sec. 5.4, p. 7, lines 334–337, and Theorem 6, p. 7, lines 364–377). The revision often reads as a series of responses to individual objections, and this reinforces my impression of defensive writing from the authors without a sufficiently coherent account of their core insights. These points need to be worked into a coherent explanation of the problem, the key idea and why the subsequent results matter.

(b) I remain unsure what substantive new insight the combination provides. Still, several ingredients discussed in the paper have close precedents, including state-wise rejection and stitching in Mandel et al. [1] (Sec. 2, p. 3, lines 123–124), clipping corrections in Wang and Goel [2] (lines 117–120), and KL-dependent sampling costs in Chatterjee and Diaconis [3] (lines 124–127). Though the revision during rebuttal discusses these connections (Appendix F, p. 46, lines 2464–2479), I am still missing a convincing explanation of how the inherited ideas lead to something substantively new. A discussion organized around individual differences leaves the conceptual overlap and the significance of the combination unresolved.

(c) This brings me back to the central contribution. If the authors believe that their central contribution is correcting the distribution shift induced by best-of-MM selection from a fixed behavior policy through candidate completion and certified weighting (Sec. 1, p. 2, lines 72–92, and Lemma 1, p. 6, lines 270–281), the paper should focus on that contribution and present standard quantile calibration as an application (Theorem 2 and its rank argument, p. 5, lines 227–240). In that case, what makes the quantile-estimation component in this paper a substantive contribution beyond the distribution correction? Since the authors’ main contributions lie in candidate completion and its clipping certificate, the paper would tell a clearer story by centering this off-policy distribution correction, and perhaps the entire quantile-calibration component could even be removed to improve the flow of the paper.

If quantile estimation is instead central, the authors need to explain what specific structure of this RL problem enables an advance beyond this distribution correction. As currently presented, the pinball-risk decomposition appears to overlap substantially with those in existing work (Sec. 6, p. 8, lines 382–388, and Appendix F, p. 46, lines 2479–2481).


References

[1] Mandel, T., Liu, Y.-E., Brunskill, E., & Popović, Z. (2016). Offline Evaluation of Online Reinforcement Learning Algorithms. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10312

[2] Wang, J., & Goel, S. (2026). Weight Clipping for Robust Conformal Inference under Unbounded Covariate Shifts. arXiv [Cs.LG]. http://arxiv.org/abs/2605.02072

[3] Chatterjee, S., & Diaconis, P. (2017). The sample size required in importance sampling. arXiv [Math.PR]. http://arxiv.org/abs/1511.01437

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

The paper studies off-policy calibration of best-of-MM policies in finite-horizon MDPs. The problem can essentially be formulated as a quantile off-policy evaluation (OPE) problem. Specifically, the objective is to estimate the upper α\alphath quantile of the prediction error G(S0,A0)−YHG(S_0,A_0)-Y_H under a target policy π\pi, using trajectories generated by a behavior policy μ\mu. Compared with standard quantile OPE, the problem is specialized in two respects: (i) the quantity of interest is the prediction error rather than the cumulative reward; and (ii) the target policy is a best-of-MM policy constructed from the behavior policy.

The author(s) proposes candidate completion, an algorithm that consists of two main components: (a) a rejection-sampling procedure that corrects for the distribution shift between the behavior and target policies and (b) conformal prediction applied to the retained trajectories to obtain finite-sample coverage guarantees. To mitigate the sample inefficiency of rejection sampling for longer horizons, the author(s) further develops a weighted completion approach that uses importance weights together with weighted conformal prediction. They demonstrate the empirical performance of their approach through MuJoCo environments .

Critical strengths

I see two critical strengths of this paper. The first is that the proposed approach leverages conformal prediction to ensure finite-sample coverage guarantees under the target policy, which is desirable. Second, the paper is reasonably well written.

Critical weaknesses

My main concern is that the paper does not adequately engage with the large literature on quantile and distributional OPE, nor with relevant work on rejection sampling.

As discussed in the summary, the calibration problem can naturally be formulated as a quantile OPE problem, with two specializations: (i) the quantity of interest is the prediction error and (ii) the target policy is a best-of-MM policy constructed from the behavior policy. However, the authors do not discuss the existing literature on quantile and distributional OPE (e.g., [1–3], to mention a few), nor do they empirically compare their method with these approaches. They also do not compare with the off-policy conformal prediction approaches in their related work section.

Methodologically, I see two ingredients in the proposed approach that distinguish it from quantile or distributional OPE.

  • First, the authors employ conformal prediction to obtain finite-sample coverage guarantees. While this is a desirable property, conformal prediction has already been applied to OPE, as cited in the related work section.

  • Second, the authors propose a rejection sampling procedure to correct for the distribution shift between the behavior and target policies. However, rejection sampling has already been studied in the literature on statistical inference under distribution shift; see, for example, [4]. Although the paper considers finite-horizon MDPs, the extension to sequential settings mainly involves applying the rejection-sampling procedure at each decision step. This leads to the so-called curse of horizon; see e.g., [5]

Given these connections to existing work, together with the omission of relevant discussions and comparisons, the novelty and the usefulness of the proposed approach remain unclear.

References

[1] Wang et al. (2018). Quantile-Optimal Treatment Regimes.

[2] Chandak et al. (2021). Universal Off-Policy Evaluation.

[3] Huang et al. (2022). Off-Policy Risk Assessment for Markov Decision Processes.

[4] Thams et al. (2023). Statistical Testing under Distributional Shifts.

[5] Liu et al. (2018). Breaking the curse of horizon infinite-horizon off-policy estimation.

Questions for authors

Please refer to weaknesses.

1 comment
AuthorsOpenReview ↗

Relation to quantile and distributional OPE: what is new, and comparisons with its finite-sample methods

Thank you for the careful summary. We agree with your formulation: the task is quantile off-policy evaluation of a modified reward, for a target policy built from the behavior policy. The revision says so in the introduction and in Section 3.

Literature. Section 2 now discusses quantile and distributional off-policy evaluation [1–3] and Hong et al. (2025), rejection sampling under distribution shift [4] and the curse of horizon [5]. Appendix F tabulates, for each method, the information it needs and the guarantee it gives. We also credit the best-of-n ratio identity (Beirami et al. 2025; Gui et al. 2024), per-state queues with rejection (Mandel et al. 2016), weight clipping for conformal prediction (Wang and Goel 2026) and concurrent work.

What is new. To our knowledge this is the first method with finite-sample predictive coverage for sample-and-select policies from sampler access alone. Its contribution is a sampler-only realization of the required correction, together with a rank-based certificate that makes finite-sample clipping possible:

  1. The density ratio is replaced by a competitor draw. The importance-weighted methods [1–3] evaluate action probabilities of both policies, and the resampling framework of [4] assumes an available distribution ratio. For best-of-MM over continuous actions the target probability has no closed form. Completion keeps a logged action when the selection rule picks it among fresh candidates, which gives exact samples and unbiased bounded weights from a sampler alone (Theorem 1).
  2. The certificate comes from the candidate ranks (Lemma 1, Theorem 3). The rank of a logged action among fresh competitors is uniform for every task, so the clipped mass of the weights is bounded by a quantity computed from (M,R,ϵ,H)(M, R, \epsilon, H) before seeing data. Generic clipped importance weighting has no such certificate; it must estimate or assume it.
  3. The curse of horizon is quantified for this problem (Theorem 4): a worst-case lower bound for every valid procedure, whose exponent the certified rule attains as more competitors are scored; and it is removed when states recur (Theorem 5).

Empirical comparison (Table 3, Appendix D.4). We implemented the finite-sample band of UnO [2], the importance-sampling CDF band of OPRA [3], PAC rejection sampling (Park et al. 2022), the weighted conformal rule used by off-policy conformal methods (Taufiq et al. 2022; Foffano et al. 2023), and the importance-weighted quantile of [3]. Where exact ratios exist (50,000 trajectories, best-of-two; coverage / loss relative to the optimal correction):

MethodH=10H = 10H=15H = 15H=20H = 20
Weighted conformal rule, exact ratios91.8% / 1.007no boundno bound
PAC rejection sampling, exact ratios98.3% / 1.433 (202 of 300 datasets)no boundno bound
UnO band, exact ratios99.9% / 5.859 (25 of 300)no boundno bound
OPRA IS-CDF band, exact ratiosno boundno boundno bound
Certified rule (ours, no densities)90.5% / 1.00192.2% / 1.01196.6% / 1.138

Every finite-sample baseline, even with exact ratios, returns no bound at 15 and 20 steps; the UnO band needs about 45–80 times more data than our rule. Two further comparisons:

  • The UnO, OPRA and PAC bounds are stated per calibration set. In a matched comparison with the high-confidence version of our rule, the calculated episode requirement of PAC rejection sampling is 11–398 times larger at 10 to 20 steps (Table 16).
  • The importance-weighted quantile of [3] has no finite-sample guarantee, and it is runnable for this policy class only because completion supplies its weights. On MuJoCo, 31% of its calibration sets at 15 steps (10,000 episodes) give a bound whose test coverage is below 88%, against 0% for our rule.

In short: with sampler access only, completion gives finite-sample predictive coverage, and its certified rule returns useful bounds where the finite-sample constructions evaluated in Table 3 return none.

We would welcome your assessment of whether these results address your concerns.

Reviewer_VphWOpenReview ↗
Rating
1(−1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies Best-of-M policy completion in offline RL, which samples M actions at each step, and chooses the highest scoring action. The authors proposes a method that stochastically chooses this best-of-M policy or the behavior policy, and further prove that the retained count follows a binomial distribution Binomial(n,C−H)Binomial (n, C^{-H}), where n is the number of episodes, and H is the number of steps. Finally, the authors complement the theory with empirical experiments.

Critical strengths

Theorem 1 shows an interesting result that the retained count of the proposed algorithm follows a binomial distribution, which is intersting and easy to interpret. I do not read the whole proofs, but the high-level proof sketch looks good to me.

Critical weaknesses
  1. Both the theory and experiments show that the method does not scale to long horizon (H) environments. From the theoretical side, the retained probability decays exponentially with H. From the experiment side, the authors only choose H=2,3,5. I think the authors would strengthen the paper significantly by discussing the exponential dependence on H. For example, the authors can show a problem lower bound.

  2. Some parts of the papers are a bit hand-wavy. (1) The contribution section does not show much useful information. The authors can be more specific by refering to the specific theorem and discuss about exact experiments. (2) In Line 128, the authors write "such as the discounted reward". What is the exact model setting, discounted or un-discounted? The authors should state settings explicitly in the problem setup.

Questions for authors

See Weakness 1. I will increase my score if the authors can fully resolve that weakness during the rebuttal.

2 comments
AuthorsOpenReview ↗

Horizon dependence: an exponentially smaller data requirement, a lower bound, and experiments at 10-20 steps

Thank you for the constructive review and for stating what would change your assessment. The revision resolves Weakness 1 in full: a new rule that reduces the data requirement exponentially, the lower bound you asked for, and experiments at 10, 15 and 20 steps.

W1. Exponential dependence on the horizon.

Why the submitted rules needed so much data. The two rules in the original submission either kept whole trajectories, losing a fraction 1−M−H1 - M^{-H} of the data, or reserved the worst-case weight MHM^H. Both need on the order of MHM^H logged trajectories.

A rule that needs far less (Section 5.2, Lemma 1, Theorem 3). The rank of a logged action among RR fresh competitors is uniform on {0,…,R}\lbrace 0, \dots, R \rbrace for every task. So the distribution of the trajectory weights is dominated by a reference distribution that depends only on (M,R,ϵ,H)(M, R, \epsilon, H). We use it to cap large weights and to certify, before seeing data, how much probability the cap can remove; the calibration level is tightened by exactly that amount. The rule stays valid in finite samples and its data requirement grows like exp⁡(κH)\exp(\kappa H) with κ≈0.2\kappa \approx 0.2 for best-of-two, against log⁡2≈0.69\log 2 \approx 0.69 before.

A lower bound, as you suggested (Theorem 4). We construct two problems that differ only on trajectories that are likely under the target policy and rare under the behavior policy. Any procedure that is valid in one and returns an informative bound in the other needs at least exp⁡(κMH−O(H))\exp(\kappa_M H - O(\sqrt{H})) logged trajectories, where κM=log⁡M−(M−1)/M\kappa_M = \log M - (M-1)/M. So an exponential cost is unavoidable in the worst case, and the certified rule is optimal in the exponent: it has this exponent up to a term (M−1)2/R(M-1)^2/R that vanishes as more competitors are scored.

Requirements for returning an informative 90% bound with probability 0.95 in the benign problem of Theorem 4, best-of-two (Table 6; the first and last columns are necessary conditions, the middle one is sufficient):

HHevery valid procedure ≥\gecertified rule (64 competitors)submitted rules ≥\ge
10661,0478,756
152484,948280,000
2088621,4309.0 million

Experiments at longer horizons (Figure 1, Table 1). On HalfCheetah, Hopper and Walker2d with the same logs: at 10 steps with 2,000 episodes the certified rule returns a bound in all 324 runs and the submitted rules in none; at 15 steps it returns bounds from 10,000 episodes and at 20 steps from 40,000, where the submitted rules return none with 120,000. With 120,000 episodes its coverage is 91.0% and 93.8% and its pinball loss is 0.3% and 3.6% above calibration on target-policy data.

When the exponential disappears (Section 5.4, Theorem 5). The hard instance needs states that never recur. If the state is finite and Markov, completion can be applied to single transitions and the accepted transitions stitched into exact target trajectories; MHM^H is replaced by MM times a state-occupancy ratio. In a six-state synthetic problem, 2,000 logged episodes (2,000⋅H2{,}000 \cdot H transitions) give 89.8–90.4% coverage for every horizon HH from 5 to 200.

W2. Precision. (1) Each contribution now names its theorem, table or figure. (2) Section 3 states the setting explicitly: the outcome is the discounted return YH=∑t=0H−1γtRtY_H = \sum_{t=0}^{H-1} \gamma^t R_t with a fixed γ∈(0,1]\gamma \in (0, 1]; the experiments use γ=0.99\gamma = 0.99, and γ=1\gamma = 1 gives the undiscounted case.

We would welcome your assessment of whether these results address your concerns.

I thank the authors for a new lower bound. However, after reading the revised manuscript, I agree with Reviewer eQbz the revision has huge writing issues: e.g., Table 4 says "where to find what" that "maps a reader’s questions to results". A lot of texts read like defensive writing, which reinforces my impression that the authors simply ask an AI model to answer whatever the reviewers ask. It upsets me that reviewers seem to interact with an AI not real humans. Considering this, I decrease my score from 2 to 1.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision: a certified rule for longer horizons, a lower bound, and a usefulness guarantee

Summary of the revision

We thank the reviewers. The revision resolves each weakness the reviews identified with new theory and new experiments. The candidate-completion construction, the title and the original Theorems 1 and 2 are retained; the revision adds certified calibration and its supporting analysis, and the text was reorganized around one question: how far can calibration from a sampler go as the horizon grows?

  1. A certified rule for longer horizons (Lemma 1, Theorem 3). The rank of a logged action among fresh competitors is uniform whatever the task. With ties broken at random, this gives a reference distribution for the trajectory weights that is known before any data are seen, and with it a certified bound on the mass removed by clipping large weights. The resulting rule is valid in finite samples and returns bounds at horizons where the submitted rules return none (Figure 1, Table 1).
  2. A lower bound (Theorem 4). In the worst case, every valid procedure that returns an informative bound needs a number of logged trajectories that is exponential in the horizon; the certified rule has the same exponent as more competitors are scored.
  3. Recurring states (Theorem 5). When the state is finite and Markov, stitching completed transitions replaces the exponential factor by a state-occupancy ratio.
  4. Validity to usefulness (Theorem 6, Table 2). The loss of the calibrated bound is at most the predictor's own error plus a calibration term, for both the original rule and the certified rule; a quantile-trained predictor lowers the loss by 19% on average (Table 2) and by 14–26% at long horizons (Table 10).
  5. Positioning and comparisons. The task is stated as quantile off-policy evaluation; Section 2 and Appendix F relate it to distributional off-policy evaluation; Table 3 compares with finite-sample constructions from that literature.

The main text has 10 pages. Appendix A is a one-page guide that points to the result behind each of these items. All new results and all main-text tables use signed corrections (the earlier optional clip at zero is removed); the tables kept from the original submission in Appendix E say where they still use it.

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

Related papers

Discussion (0)

Sign in to comment.