acceptodds
Under review as a conference paper at ICLR 2027

The Cost of Evaluating Policy Updates under Censored Feedback

Abstract

A policy can appear more accurate simply because its failures are less likely to be observed. We study how to decide whether a proposed policy actually improves expected reward when some rewards are missing. An audit reveals one missing reward, but the corresponding outcome must first be generated. Evaluation therefore has two costs: producing outcomes and inspecting them. For finitely many actions and rewards in [0,1], we characterize the smallest worst-case estimation error under both budgets. The optimal allocation gives more audits to influential actions, subject to how often their outcomes are available. For actions with too few observations, it reduces reliance on the sampled rewards and includes the remaining uncertainty in the error bound. We also account for estimating missingness and for evaluating a sequence of proposed updates. Experiments in a controlled environment and on fixed Qwen-generated GSM8K responses show when additional evidence resolves more decisions, and why that need not improve the final policy.

Primary area:
learning theory
Keywords:
censored feedback, policy evaluation, optimal experimental design, minimax estimation, partial identification, sequential decision making

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_xB5rOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the problem of evaluating policy updates under censored feedback, where reward visibility may depend on the reward itself. The authors consider two resource constraints: the cost of generating outcomes and the cost of auditing missing rewards. They characterize the uncertainty in policy improvement and propose a capped audit allocation with shrinkage to balance estimation variance and worst-case bias. The paper establishes minimax estimation guarantees and extends the analysis to sequential policy updates. Experiments on a controlled environment and fixed LLM-generated responses illustrate the tradeoffs between evaluation cost, decision resolution, and final policy quality.

Critical strengths
  1. The motivation is interesting. The theoretical analysis is well structured. The result that the same allocation is optimal across confidence scales is appealing.

  2. The paper provides a detailed treatment of estimation uncertainty and sequential policy evaluation. The distinction between reliable update decisions and final policy quality is important. The experiments investigate multiple budget settings.

Critical weaknesses
  1. The main experiments do not clearly demonstrate the additional value of the proposed allocation and shrinkage. In particular, removing shrinkage does not change the policy decisions in the reported learning trajectories. Moreover, the improvement over uniform allocation is modest, especially in terms of final policy quality. The benefits of shrinkage become substantial mainly in constructed scarce-arrival settings, where uniform allocation with shrinkage can also achieve similar performance.

  2. The theoretical optimality results assume a fixed behavior policy during evaluation. It remains unclear whether this restriction is essential where the evaluator may actively control the action distribution.

  3. The LLM experiment relies on fixed, pre-generated responses and artificially imposed reward-dependent missingness. The proposed validation procedure also requires more interactions and audits than the complete-feedback proposal reference, without improving final policy quality. The practical benefit of the additional evaluation costs remains unclear.

Questions for authors
  1. Can the authors clarify the individual practical contributions of capped allocation and shrinkage?

  2. Why is the behavior policy assumed to be fixed during evaluation? If the evaluator can actively adjust the action distribution, how would this affect the proposed method?

  3. Under what practical conditions would the additional evaluation costs be justified?

3 comments
AuthorsOpenReview ↗

Author Response (Part 1/3)

Thank you for highlighting the theoretical structure and the distinction between reliable update decisions and final policy quality. We address each weakness together with its corresponding question, combining the mechanism, evidence and practical implications in three sections.

W1 & Q1. Practical contributions of capped allocation and shrinkage

Capped allocation improves audit efficiency under moderate scarcity, while midpoint shrinkage improves resolution when influential outcomes are extremely scarce. Allocation directs audits toward missing rewards with greater influence on the candidate comparison, subject to how many outcomes each action supplies. Shrinkage reduces reliance on poorly sampled contributions by pulling their estimates toward the reward range's midpoint. The confidence radius includes the resulting worst-case bias and sampling uncertainty.

Theorem 3 connects these operations: one capped allocation minimizes their combined criterion at every confidence scale, while the retained weights change with that scale. When auditing improves on the no-audit bound, every action whose coefficient is reduced has reached its availability cap.

Table 5 evaluates identical frozen candidates using the same preliminary data and validation budgets. One action is sampled with probability η/K\eta/K, where KK is the action count; every action is made rare in turn. The paired analysis over 30 seeds separates the two contributions:

ComparisonControlled resolutionGSM8K resolution
Moderate scarcity, η=10−2\eta=10^{-2}: uniform + shrinkage to capped + shrinkage33.7% to 50.7%; gain 17.0 pp [9.0, 25.1]20.0% to 85.6%; gain 65.6 pp [54.0, 77.1]
Severe scarcity, η=10−4\eta=10^{-4}: capped without shrinkage to capped + shrinkage6.9% to 30.9%; gain 24.1 pp [13.8, 34.4]1.1% to 20.0%; gain 18.9 pp [9.3, 28.5]

Gains are percentage points, with 95% paired intervals after averaging action rotations within each seed. At severe scarcity, uniform + shrinkage resolves 28.7% and 20.0%, compared with 30.9% and 20.0% for capped + shrinkage; clipping + shrinkage gives 30.9% and 18.9%. This experiment makes one action extremely rare while keeping the others equally sampled. Both capped and uniform methods reduce reliance on that rare contribution through shrinkage, which supplies the main resolution gain in this regime. At moderate scarcity, directing audits according to influence produces the larger allocation gains shown above (Appendix D.3).

In the main learning runs, validation uses the retained policy, fixed within each episode. Removing shrinkage leaves the reported decisions unchanged. The learner retains the incumbent after both rejection (an interval entirely below zero) and an unresolved decision (an interval containing zero). For the same proposals and acceptance decisions, resolving additional rejections therefore increases resolution without changing the retained policy path. Final reward changes through accepted updates and their effects on later proposals. On GSM8K, the two stronger prompts have accuracies 43.0% and 42.5%, so redistributing probability between them changes final quality little.

W2 & Q2. Fixed behavior within evaluation and active choice before evaluation

The evaluator can choose the behavior distribution before each validation episode and retain the finite-sample guarantee. Treating that distribution as given also covers interaction streams supplied by a deployed policy or fixed logging policy. Under stationary action-conditional reward and visibility laws, holding the distribution fixed makes fresh interactions conditionally independent and identically distributed, supporting the Bernstein bounds and allocation analysis.

Active control changes how the interaction budget supplies outcomes. In the known-feedback design, let dad_a be the candidate's change in action probability, pap_a the missing-reward probability, ρa\rho_a the behavior probability, and TT the interaction limit. Action aa supplies an expected TρapaT\rho_ap_a missing outcomes. For NN planned audits, define H=∑a∣da∣paH=\sum_a|d_a|p_a. The proportional allocation na=N∣da∣pa/Hn_a=N|d_a|p_a/H is feasible when it fits every supply cap. Equation (83), Appendix B.3.4, expresses this condition as

\frac{H}{\max_{a\in\mathcal I}(|d_a|/\rho_a)}, \qquad \mathcal I=\{a:|d_a|p_a>0\}.$$ Here $H>0$ and behavior has positive probability on the relevant actions. The factor $p_a$ cancels from each action's feasibility inequality, so $|d_a|/\rho_a$ identifies the mismatch between the proposed change and outcome collection. Missingness still enters through $H$ and the total available supply. Choosing behavior proportional to $|d_a|$ equalizes these ratios and makes the proportional allocation feasible when $N/T\le H/\sum_a|d_a|$. The capped design handles the remaining limits when behavior is constrained or the interaction supply is insufficient.
AuthorsOpenReview ↗

Author Response (Part 2/3)

We test this principle on the same 60 first candidates, 30 per task, with common preliminary data and setting-4 validation limits. The chosen behavior mixes 5% uniform exploration with 95% allocated in proportion to the candidate's absolute probability changes:

+0.95\frac{|d_a|}{\sum_i|d_i|}.$$ | Validation behavior | Controlled resolution | GSM8K resolution | |---|---:|---:| | One action severely rare, rotated across actions | 31.1% | 18.9% | | Uniform | 50.0% | 93.3% | | Chosen using the candidate | 53.3% | 93.3% | The main gain here comes from correcting the skewed behavior in the first row. At setting 4 ($T=320{,}000$, $B=20{,}480$), uniform behavior already satisfies the cap-feasibility condition for all tested candidates in both tasks, including all three GSM8K actions. Uniform and candidate-aligned behavior therefore give the same planned audit allocation, although their realized samples differ, and each resolves 28/30 GSM8K candidates (93.3%). Each choice is fixed before fresh validation. Conditioning on the previous history gives the guarantee for the chosen design; allocating error probabilities across episodes preserves the sequence guarantee. Updating behavior using outcomes within the same episode requires the corresponding probability weights and a sequential concentration argument (Appendix E.4). **W3 & Q3. Evaluation cost, deployment value and expert judgments** **Early stopping reduces validation interactions by 70.7% in controlled learning and 30.2% on GSM8K under the same error allowance; prediction-assisted evaluation further raises GSM8K resolution from 38.3% to 47.5%.** Table 7 compares methods with a 0.05 error allowance per learning run: 0.01 for preliminary estimation and 0.005 for each of eight evaluations. Four planned checks occur at $T/8,T/4,T/2,T$, with error shares assigned before sampling. The predictive method fits a reward predictor using independent preliminary audit labels and corrects its predictions with inverse-probability-weighted validation residuals. Its empirical Bernstein interval accounts for residual uncertainty. All 1,536 controlled-task and 384 GSM8K training labels are charged. Total cost is $C_{10}=I+10A$, where $I$ counts all interactions and $A$ all paid audits. Setting-4 results are: | Evaluator | Controlled resolution | Controlled cost, millions | GSM8K resolution | GSM8K cost, millions | |---|---:|---:|---:|---:| | Capped, terminal | 84.2% | 3.839 | 38.3% | 4.122 | | Capped, four looks | 84.2% | 1.284 | 38.3% | 2.886 | | Uniform, four looks | 80.8% | 1.464 | 32.1% | 3.295 | | Predictive, four looks | 85.0% | 1.325 | 47.5% | 2.652 | Four-look capped evaluation preserves the terminal method's decisions on these runs. Predictive four-look evaluation reduces GSM8K total cost by 35.7% relative to terminal capped evaluation while improving resolution. Costs include preliminary data, predictor fitting, proposals and validation (Appendix E.2). Independent validation is useful when intermediate policies serve users, adverse releases have consequential costs, or candidates come from prompt edits, model checkpoints or external retrieval systems. It tests the candidate's reward change directly and bounds the probability of incorrect decisions across adaptive releases for any candidate fixed before fresh validation. We also test spending the original total allowance on larger proposal batches (Table 6). All methods use 40 proposal steps and eight deployment opportunities per run. Setting-4 means and counts across 30 seeds are: | Task | Use of allowance | Cost, millions | Final reward | Accepted nonpositive changes | |---|---|---:|---:|---| | Controlled | Interval validation | 3.838 | 0.7355 | 0/240 | | Controlled | Larger proposals, complete audits | 3.838 | 0.7587 | 0/240 | | Controlled | Larger proposals, 4% audits with weighting | 3.837 | 0.7587 | 0/240 | | GSM8K | Interval validation | 4.122 | 0.4245 | 0/240 | | GSM8K | Larger proposals, complete audits | 4.121 | 0.4266 | 0/240 | | GSM8K | Larger proposals, 4% audits with weighting | 4.121 | 0.4267 | 0/240 | The complete-feedback batches average about 63,800 fully observed outcomes per step in controlled learning and 18,900 on GSM8K, versus 128 in the original proposals. Averaging more outcomes reduces gradient sampling noise in these stationary tabular tasks, consistent with the zero observed adverse deployments. At setting 3, the matched-expenditure 4%-audit proposal learner accepts five strict decreases in 240 GSM8K groups; complete proposals and interval validation accept zero. The 4% rule independently inspects each missing proposal reward with probability 0.04 and applies inverse-probability correction.
AuthorsOpenReview ↗

Author Response (Part 3/3)

At the original batch size, complete proposal feedback accepts 157/1,200 nonpositive single-step changes in controlled learning and 394/1,200 on GSM8K. With five-step deployment, it accepts 4/240 and 35/240 strict decreases. Under a common loss per adverse five-step release, the observed extra evidence costs imply break-even losses of 28.69 million and 3.51 million interaction-cost units per release, respectively. Substituting the measured four-look capped costs gives 9.54 million and 2.45 million under the same reference and loss assumption. A deployment can insert its own exposure and loss estimates into this calculation (Appendix E.1; Table 7).

GSM8K uses controlled reward-dependent reveal rates on fixed Qwen2.5-0.5B-Instruct responses, counting replay draws and requests for hidden correctness labels. TREC-COVID adds naturally incomplete expert judgments (Section 6.6; Appendix E.5). Experts assessed whether biomedical articles answered specified topics. Reward is one for a fully relevant judgment and zero for other assessed grades. Across three fixed retrieval systems, 1,517 of 5,044 distinct topic–article pairs were judged initially, 894 first judged later, and 2,633 remain unjudged. Later judgments have fully relevant rates of 17.7%–23.7%, compared with 33.3%–37.4% initially. Historical follow-up narrows the full-population BM25R2-to-T5R3 gain range from [-0.402, 0.423] to [-0.307, 0.343].

A separate replay samples eventually assessed articles within each topic and system, providing a known gain of 0.0508. At the evaluated budget (T=4,096T=4{,}096, B=512B=512) and per-comparison error allowance 0.05/90.05/9, the mean interval radius is 0.072, larger than the true gain, so most intervals still include zero. Terminal capped evaluation resolves the positive gain in 3/30 seeds and leaves the other 27 unresolved, using a mean of 424.7 paid requests that consult 316.9 distinct later judgments. All 1,080 replay intervals cover their targets, with zero incorrect sign decisions. This experiment measures requests for archived expert labels and distinguishes the full return set from the assessed population.

Reviewer_4fUoOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks how to certify that a policy update improves expected reward when rewards are missing not at random, under separate budgets for producing outcomes and auditing missing rewards. For finite action sets, it derives the identification interval, matching audit bounds for the sign test, and a capped Neyman allocation with midpoint shrinkage that is minimax-optimal up to constants. Experiments use a simulator and frozen Qwen2.5-0.5B GSM8K outputs with imposed missingness.

Critical strengths
  • The paper addresses an important policy evaluation problem under censored feedback, explicitly accounting for both outcome generation and audit costs.
  • The paper establishes identification bounds, characterizes audit complexity, and derives an optimal capped allocation with shrinkage under limited budgets. It also extends the statistical guarantees to sequential policy updates.
  • The experiments provide detailed cost comparisons and useful ablations. They also highlight important findings, including the benefits of shrinkage under scarce observations and the fact that higher decision resolution does not necessarily improve final policy quality.
Critical weaknesses
  • The experiments do not match the motivating setting. The paper is motivated by settings where verifying rewards is hard or expensive. The LM experiment instead uses Qwen2.5-0.5B-Instruct on GSM8K, where every problem has a numerical ground truth and a missing reward can be recovered by checking the answer at almost no cost. Missingness is imposed artificially on frozen outputs of a small model, so the experiments do not show that the method is needed when verification is genuinely costly.
  • The optimal allocation gives no practical gain over simpler rules. In most settings, capped allocation and uniform allocation with shrinkage reach nearly identical final policy quality. Removing shrinkage does not change the learning decisions, and a simpler clipped-uncapped allocation performs almost as well in the scarce-arrival setting. The paper never identifies a regime where the optimal allocation matters.
  • The method costs orders of magnitude more than the baselines for the same result. On GSM8K it uses 2.59M interactions and 153,000 audits to reach 0.425 accuracy; complete proposal feedback reaches 0.426 with 5,120 interactions and 2,300 audits, over 500× fewer interactions and 66× fewer audits. In the controlled task it blocks 394 non-improving updates that complete proposal feedback accepts, with no argument that this is worth the cost. There is no comparison with cheaper alternatives under the same guarantee, such as sequential testing or prediction-powered estimators.
  • The sample-complexity theory is never checked against the experiments. Theorem 2 ties audit cost to the improvement gap and problem difficulty. The experiments report neither, and a large fraction of update decisions remain unresolved despite large budgets, so one cannot tell whether the cost is intrinsic to hard decisions or comes from conservative intervals and fixed budgets.
Questions for authors
  1. What is new in the capped allocation and midpoint shrinkage relative to classical optimal allocation and minimax estimation? Is optimality of one allocation across confidence levels a new result?
  2. How does the method extend to large or structured action spaces where action-specific quantities must be estimated, and what happens to the guarantees then?
  3. Are there results with naturally missing rewards and genuinely costly verification?
  4. What are the improvement gaps of the evaluated updates, and how does observed audit use compare with the Theorem 2 bounds? Are unresolved decisions mainly small-gap ones?
  5. How does the method compare with simpler allocation and sequential evaluation methods at matched guarantees and cost?
  6. Which guarantees still hold if the censoring mechanism changes as the policy evolves?
6 comments
AuthorsOpenReview ↗

Author Response (Part 1/4)

Thank you for the detailed review and for recognizing the value of accounting for both outcome-generation and audit costs. The revision adds expert-judgment replay, comparisons with sequential and prediction-assisted evaluation, and analyses of candidate gaps, calibration uncertainty and changing visibility. We have also clarified the experimental discussion in Sections 6.2–6.6. Closely related weaknesses and questions are answered together below.

W1 & Q3. Naturally missing rewards and expert verification

TREC-COVID tests evaluation using naturally incomplete, archived judgments produced by biomedical experts. It complements GSM8K, which isolates reward-dependent visibility in a fixed response pool. We compare three first-round retrieval systems, BM25R2, T5R1 and T5R3, over the original 30 topics. A fully relevant expert judgment receives reward one; other assessed grades receive zero.

Their combined top-100 results contain 5,044 distinct topic–article pairs: 1,517 judged initially, 894 first judged later, and 2,633 still unjudged. Later-assessed articles have fully relevant rates of 17.7%–23.7%, compared with 33.3%–37.4% among initially assessed articles. Thus the labels available early present a different view of system quality from the follow-up labels.

On the full return set, the 52.2% of pairs without archived judgments retain their possible reward contributions. Historical follow-up narrows the BM25R2-to-T5R3 improvement range from [-0.402, 0.423] to [-0.307, 0.343], reducing its width by 21.2%. All three full-set comparisons still span zero, identifying the remaining uncertainty in these rankings.

For a replay with known reward truth, we sample eventually assessed articles within each topic and system; their union contains 2,411 pairs. The BM25R2-to-T5R3 gain in this population is γ=0.0508\gamma=0.0508. Each evaluator shares a 0.05 error allowance across nine switch–budget pairs per seed, giving δj=0.05/9≈0.0056\delta_j=0.05/9\approx0.0056. The archive provides 894 follow-up judgments, and our largest evaluated budget is T=4,096T=4{,}096 interactions and B=512B=512 audits. At this budget, the mean interval radius is 0.072 against a gain of 0.0508, so the lower endpoint usually remains below zero. Terminal capped evaluation identifies the positive gain in 3/30 seeds, using a mean of 424.7 paid draws that consult 316.9 distinct follow-up judgments; the other 27 intervals include zero and retain the incumbent. All 1,080 replay intervals cover their targets, with zero incorrect sign decisions (Section 6.6; Appendix E.5).

W2. Separate contributions of allocation and shrinkage

Capped allocation improves resolution at moderate scarcity, and shrinkage provides the larger improvement at severe scarcity. In the frozen-candidate study, one action is sampled with probability η/K\eta/K, where KK is the action count. Each comparison holds the candidate, preliminary observations and resource limits fixed. Table 5 and the paired seed analysis give:

ComparisonControlled resolutionGSM8K resolution
Capped vs. uniform allocation, both with shrinkage, at moderate scarcity η=10−2\eta=10^{-2}50.7% vs. 33.7%; gain 17.0 pp [9.0, 25.1]85.6% vs. 20.0%; gain 65.6 pp [54.0, 77.1]
Shrinkage vs. full retained weights, both with capped allocation, at severe scarcity η=10−4\eta=10^{-4}30.9% vs. 6.9%; gain 24.1 pp [13.8, 34.4]20.0% vs. 1.1%; gain 18.9 pp [9.3, 28.5]

Intervals are 95% paired intervals over 30 seeds, with action rotations averaged within each seed. The original learning trajectories are mostly well sampled, so removing shrinkage leaves their decisions unchanged. Under severe scarcity, shrinkage reduces mean radii from 0.137 to 0.040 and from 0.311 to 0.135, respectively, by limiting reliance on the poorly sampled contribution.

Capped allocation also redistributes audit allowance left unused by post-hoc clipping. In Table 5's single-rare-action design (η=10−4\eta=10^{-4}), clipping leaves mean expected allowances of 1,107 audits in controlled learning and 6,645 on GSM8K unallocated. Clipped and capped resolution is 30.9% vs. 30.9% and 18.9% vs. 20.0%, respectively. Reconstructing these interval designs shows that the uncapped actions' sampling uncertainty is already smaller, on average, than the preliminary calibration allowance. Reallocation refines those actions while leaving the calibration allowance and the rare action's outcome supply unchanged. The remaining calibration and shrinkage-bias terms therefore explain the small radius change, from 0.136 to 0.135 on GSM8K. When multiple influential actions reach availability caps and uncapped actions still have substantial sampling uncertainty, redistribution via λ\lambda reduces that uncertainty (Theorem 3; Appendix D.3).

AuthorsOpenReview ↗

Author Response (Part 2/4)

W3 & Q5. Lower evaluation cost under the same guarantee, and the value of validation

Under the same 0.05 sequence-level error allowance and resource ceilings, four planned checks reduce capped validation interactions by 70.7% in controlled learning and 30.2% on GSM8K. They preserve the terminal method's decisions. Prediction-assisted evaluation separately raises GSM8K resolution from 38.3% to 47.5%.

We allocate 0.01 to preliminary estimation and 0.005 to each of eight evaluations. Four-look methods check at T/8,T/4,T/2,TT/8,T/4,T/2,T, where TT is the maximum validation horizon, with error shares fixed before sampling. The predictive method fits a reward predictor using independent preliminary audit labels and corrects its errors with inverse-probability-weighted validation residuals. Its interval uses an empirical Bernstein bound. All 1,536 predictor-training labels in controlled learning and 384 on GSM8K are charged.

Total cost is C10=I+10AC_{10}=I+10A, where II includes all interactions and AA includes all paid audits. The six two-sided evaluators at setting 4 are shown below; Appendix E.2 also reports an acceptance-only evaluator. Costs are in millions.

EvaluatorControlled resolutionControlled costGSM8K resolutionGSM8K cost
Capped, terminal84.2%3.83938.3%4.122
Capped, four looks84.2%1.28438.3%2.886
Uniform, terminal80.8%3.87233.8%4.121
Uniform, four looks80.8%1.46432.1%3.295
Predictive, terminal85.0%3.84147.5%4.121
Predictive, four looks85.0%1.32547.5%2.652

The predictive four-look method combines 47.5% GSM8K resolution with cost 2.652 million, compared with 38.3% and 4.122 million for terminal capped evaluation. All realized costs include calibration, predictor fitting, proposals and validation. This comparison uses fresh validation streams; the original trajectory results remain separately reported.

We also test spending the original total allowance on larger proposal batches without validation (Appendix E.1, Table 6). At setting 4, complete-feedback proposals reach rewards 0.7587 and 0.4266, compared with 0.7355 and 0.4245 for interval screening; both approaches accept zero nonpositive changes across 240 five-step opportunities per task. These stationary tabular tasks use the same policy-gradient update, but the matched-expenditure complete-feedback batches average about 63,800 fully observed outcomes per step in controlled learning and 18,900 on GSM8K, versus 128 in the original proposals. Averaging more outcomes reduces gradient sampling noise and is consistent with the zero observed adverse updates. At setting 3, the matched-expenditure 4%-audit proposal arm accepts five strict decreases on GSM8K, while complete proposals and interval screening accept zero. For candidates produced by prompt edits, finetuning or retrieval-system switches, independent validation directly tests the resulting reward change. It provides a finite-sample (1−δ)(1-\delta) guarantee on decision correctness across adaptive updates for any candidate fixed before its fresh validation sample.

At the original proposal batch size (Table 4), the low-cost complete-proposal reference accepts 157/1,200 nonpositive single-step changes in controlled learning and 394/1,200 on GSM8K, or 4/240 and 35/240 strict decreases under five-step deployment. Relative to this low-cost reference, the observed extra validation expenditure breaks even at losses of 28.69 million and 3.51 million interaction-cost units per adverse release, respectively, assuming a common loss per adverse five-step release. These conditional thresholds let a deployment insert its own exposure and loss estimates.

AuthorsOpenReview ↗

Author Response (Part 3/4)

W4 & Q4. Why updates remain unresolved, and how audit use follows Theorem 2

Candidate-level diagnostics link unresolved decisions to small reward changes and show a median calibration share above 80% of the radius in both tasks. On GSM8K, unresolved candidates have a median absolute change of 0.06 percentage points, compared with 0.63 for resolved candidates at similar audit counts. Preliminary estimation contributes a median 83.3% of the full radius in controlled learning and 80.1% on GSM8K.

To connect these observations to the theory, let DD be the true reward change, γ=∣D∣\gamma=|D| its magnitude, dad_a the change in action probability, and pap_a the missingness probability. Then H=∑a∣da∣paH=\sum_a|d_a|p_a measures the influence of missing rewards. Table 8 reconstructs every setting-4 five-step candidate, including rejected and unresolved ones. Numerical columns are candidate-level medians; γ/H\gamma/H is computed for each candidate before taking its median.

Task and decisionCandidatesγ\gammaHHγ/H\gamma/HPaid validation audits
Controlled, resolved2050.024960.097990.481818,340
Controlled, unresolved350.008240.346520.031819,322
GSM8K, resolved1010.006340.050090.136719,198
GSM8K, unresolved1390.000600.050900.016919,085

Theorem 2 isolates direct access to missing rewards with ordinary feedback known. In that setting, at H=0.4H=0.4 and error allowance 0.05, halving the gap from 0.05 to 0.025 to 0.0125 raises mean stopping counts from 336 to 1,583 to 6,564 over 500 trials per gap. The hard-pair lower benchmarks are 10.60, 42.40 and 169.60. This experiment checks the predicted inverse-square dependence on the gap.

The learning pipeline additionally estimates feedback rates and pays for outcome generation. Its calibration term is (3/2)∑a∣da∣ea(3/2)\sum_a|d_a|e_a, where eae_a bounds each action's preliminary estimation error. The radius decomposition above identifies this term as the main source of width at setting 4. The 95th percentiles of absolute estimation error divided by radius are 0.126 and 0.157. Appendix E.3 reports both the direct-audit scaling test and this full-pipeline decomposition.

Q1. Contribution relative to classical allocation and minimax estimation

Yes. Theorem 3 proves that a single availability-capped allocation is optimal across all confidence scales for our joint bias–uncertainty criterion. Classical Neyman allocation minimizes sampling variance; bounded-range estimation and midpoint shrinkage build on optimal recovery. Our criterion jointly optimizes the audit allocation and retained weights under outcome-availability and audit-budget constraints.

Let ρa\rho_a be the behavior probability for action aa and TT the interaction limit. Its expected missing-outcome supply is TρapaT\rho_ap_a. The allocation is

na∗=min⁡{Tρapa,λ∣da∣pa},n_a^*=\min\{T\rho_ap_a,\lambda|d_a|p_a\},

where λ\lambda fills the usable audit allowance. This allocation is independent of the confidence scale; the retained weights adapt to that scale. When audits improve on the no-audit bound, every action whose coefficient is reduced has reached its availability cap. Theorem 4 connects the optimized criterion to minimax estimation error under the two budgets, up to universal constants. Sections 4 and 7 state the results and their relation to Neyman allocation, two-phase nonresponse sampling and Donoho's optimal-recovery framework.

Q2. Large or structured action spaces

Known classes can reduce the number of quantities requiring calibration. When actions in a class share the joint reward–visibility distribution, we pool their observations and sum their policy-change coefficients. The finite-action guarantee then applies to the classes.

Appendix E.4 expands 18 controlled actions into 72 and 288 equally mixed copies in 18 known classes, holding total calibration at 147,456 observations and validation budgets fixed. Separate estimates give mean radii of approximately 0.0255, 0.0489 and 0.0983; pooling keeps the radius near 0.0255. At 288 actions, pooling raises resolution from 0/30 to 17/30 candidates. Exact within-class equivalence supports the stated guarantee; approximate or learned classes require an additional bound on the error introduced by pooling.

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

This paper studies how to figure out whether a proposed policy improves expected reward when some rewards are missing. To determine what rewards are missing, the mechanism itself must depend on the reward itself. Missing rewards can be revealed through paid audits, but the corresponding outcomes must first be generated. Policy evaluation therefore involves two coupled resources: interactions to produce outcomes and audits to inspect missing rewards. The setting consists of (K) actions, each with a fixed joint distribution of bounded reward (R∈[0,1]R\in[0,1]) and visibility indicator (G). A policy specifies a probability distribution over these actions, and the objective is to estimate the expected reward difference between a current policy and a proposed replacement.

Their main theoretical contributions are: Proposition 1 characterizes the exact interval of possible policy improvements without audits, and Theorem 2 establishes upper and lower bounds on the number of audits needed to determine the sign of an improvement. They also propose Theorem 3, which minimizes a bias–uncertainty modulus across all confidence scales. Finally, Theorem 4 establishes worst-case estimation error optimality up to universal constants. I have not gone deep into the proofs of these theorems. Experiments use an 18-action simulator and 3,957 fixed Qwen2.5-0.5B responses to GSM8K, with synthetically imposed reward-dependent missingness. The authors report zero incorrect resolved decisions across 51,840 interval evaluations. This is mainly a theory paper with limited experiments to justify the theory.

Critical strengths

The main strengths of the paper are as follows:

  1. The main contribution is the theoretical treatment under coupled interaction and audit budgets. The allocation problem is not simply one of choosing which missing rewards to inspect. An action can be highly influential for the policy comparison but occur too rarely under the behavior policy to supply the desired number of auditable outcomes. Theorem 3 handles this through the availability constraint. The resulting allocation is proportional to the absolute influence coefficient until an availability cap becomes active.

  2. The paper also establishes that, in the nontrivial sampling regime, coordinates receiving partial shrinkage are those constrained by outcome availability. This shows that increasing the audit budget alone cannot resolve uncertainty when relevant outcomes are unavailable. Theorem 4 shows this result by relating the achievable error radius to a minimax lower bound, up to universal constants.

  3. The empirical presentation augments the theoretical findings of the paper. The authors separately account for preliminary calibration, proposal generation, validation interactions, and paid audits. They also report retained quality, decision resolution, and incorrect accepted updates.

Critical weaknesses

The main weaknesses of the paper are as follows:

  1. The paper demonstrates that high-confidence interval evaluation can avoid accepting nonpositive updates. However, its experiments do not establish when this protection is worth the additional exploration using evidence expenditure. Maybe an ablation study considering this can be useful.

  2. The paper cites Neyman (1934), Wright (2020), and Donoho (1994), and explicitly acknowledges that proportional allocation is classical. However, it does not sufficiently explain how its complete two-budget formulation relates to the broader literature on cost-optimal two-phase nonresponse sampling. More clarification is needed on this from the authors.

  3. There is a particular issue with the motivating failure mode. In the introduction, the authors discuss policies whose failures become less likely to be observed, drawing motivation from work on strategic behavior, deceptive models, and monitoring failures. However, the mathematical model assumes that the joint distribution of reward and visibility is fixed within each action. Policy optimization changes only the mixture over these fixed action-specific distributions. The model can therefore represent policies selecting actions with different reward and visibility profiles. It does not represent a model learning a new strategy for concealing failures within an action. Maybe I missed something here. Some clarification is required on how the model can actually learn new strategies.

  4. Across the 51,840 reported interval evaluations, the paper observes zero confidence-interval misses and zero incorrect resolved decisions. This might actually suggest that the confidence intervals may be conservative on the evaluated populations. Any idea why this is happening or possible?

Questions for authors

Here are the questions for the authors. If they are addressed, I am willing to raise my score.

  1. One concern is that the current comparisons establish that the interval method provides stronger decision protection at substantially higher cost, which might exhaust the fixed evidence budget. Can the authors compare the proposed evaluator against a baseline that uses the same total evidence cost, but allocates additional resources to proposal generation, proposal auditing, or larger proposal batches rather than validation?

  2. Some more discussion on technical novelty is required. How do Theorems 3 and 4 differ from classical cost-optimal nonresponse follow-up design (and the related works)?

  3. Going back to one of the weaknesses raised before, the confidence interval could be very conservative. A discussion on this is required as to why the paper observes zero confidence-interval misses.

  4. Theorem 4 establishes minimax optimality up to universal constants. Combining that with the reported upper and lower bounds with the relationship between (R_z) at different confidence scales yields a constant-factor separation between the theoretical bounds. Can the authors comment on this gap?

3 comments
AuthorsOpenReview ↗

Author Response (Part 1/3)

Thank you for recognizing the joint-budget formulation and the detailed cost accounting. We address your four questions together with the corresponding weaknesses, then explain the learning mechanism in W3. The revised manuscript includes matched-expenditure comparisons, early stopping, connections to two-phase sampling, and quantitative analyses of interval width and theoretical constants.

Q1 & W1. Allocating the same expenditure to proposals, and reducing validation cost

Spending the full allowance on larger proposal batches raises final reward at setting 4. At setting 3, the 4%-audit GSM8K learner accepts five strict decreases, while interval validation accepts zero. Four-look early stopping cuts validation interactions by 70.7% in the controlled task and 30.2% on GSM8K under the same sequence guarantee.

For both tasks and budget settings 3 and 4, each run has 40 proposal steps and eight five-step deployment opportunities. Thirty seeds give 240 opportunities per task and method. We measure total expenditure as C10=I+10AC_{10}=I+10A, where II counts all interactions and AA all paid inspections of missing rewards. Each proposal-only learner receives its allowance before sampling, with at most 400 units left unspent through batch rounding. We test complete proposal audits and independent 4% audits with inverse-probability correction. Setting-4 means are:

TaskUse of total allowanceCost, millionsFinal rewardAccepted nonpositive changes
ControlledCapped interval validation3.8380.73550/240
ControlledLarger proposals, complete audits3.8380.75870/240
ControlledLarger proposals, 4% audits with weighting3.8370.75870/240
GSM8KCapped interval validation4.1220.42450/240
GSM8KLarger proposals, complete audits4.1210.42660/240
GSM8KLarger proposals, 4% audits with weighting4.1210.42670/240

At setting 4, the complete-feedback proposal batches average about 63,800 outcomes per step in the controlled task and 18,900 on GSM8K, compared with the original 128. Averaging more outcomes reduces gradient sampling noise in these stationary finite-action tasks, consistent with the zero adverse releases observed at this budget. At setting 3, the matched-expenditure 4%-audit GSM8K learner accepts five strictly decreasing updates across 240 opportunities; complete proposal audits and interval validation each accept zero (Appendix E.1).

Independent validation supplies a probability bound on incorrect decisions across adaptive deployments. It applies to any candidate fixed before fresh evaluation, including prompt changes, model checkpoints and retrieval-system switches. Its practical value depends on the consequences of releasing an adverse update. At the original batch size and five-step deployment cadence, the low-cost complete-proposal reference accepts 4 strictly decreasing releases in the controlled task and 35 on GSM8K across 30 runs. Assuming equal loss per adverse release, the observed additional validation expenditure breaks even at losses of 28.69 million and 3.51 million interaction-cost units per release, respectively. Appendix E.1 provides the calculation so a deployment can use its own loss estimate.

For deployments requiring the 0.05 error bound across the learning run, four planned checks at T/8,T/4,T/2,TT/8,T/4,T/2,T reduce validation interactions by 70.7% in the controlled task and 30.2% on GSM8K. Here TT is the maximum interaction count for one evaluation, and each episode's error allowance is divided across the checks before sampling. Total costs fall from 3.839 to 1.284 million and from 4.122 to 2.886 million, including preliminary estimation, proposals and paid audits. Four-look and terminal capped evaluation make the same decisions on these setting-4 runs. Under the same low-cost complete-proposal reference and equal-loss assumption, early stopping reduces the break-even losses above to 9.54 million and 2.45 million interaction-cost units per adverse release, respectively (Appendices E.1–E.2, Table 7).

AuthorsOpenReview ↗

Author Response (Part 2/3)

Q2 & W2. Connection to two-phase nonresponse sampling and the contribution of Theorems 3–4

Two-phase follow-up provides the sampling structure; our results optimize bounded-reward estimation error under the outcome supply created by the first phase.

Section 7 now connects the framework to Hansen and Hurwitz (1946) and later nonresponse follow-up design, including Thompson et al. (2018). Interactions correspond to the first-phase sample, and audits follow up a probability subsample of missing rewards. If TT interactions select action aa with probability ρa\rho_a, and its reward is missing with probability pap_a, the expected supply available for follow-up is TρapaT\rho_ap_a. An expected audit allocation nan_a must fit that supply and the total audit budget NN.

The estimation target is the signed reward change between two policies. Let dad_a be the candidate's change in action probability and wa=dapaw_a=d_ap_a its missing-reward coefficient. For rewards in [0,1][0,1], shrinking a missing-reward estimate toward 1/21/2 retains an absolute coefficient va∈[0,∣wa∣]v_a\in[0,|w_a|]. The omitted weight introduces bounded bias, while the retained weight determines sampling uncertainty. At confidence scale z>0z>0, their combined criterion is

+z\sqrt{\sum_a v_a^2/n_a}, \qquad n_a\le T\rho_ap_a,\quad \sum_a n_a\le N.$$ Theorem 3 proves that the single capped allocation $n_a^*=\min\{T\rho_ap_a,\lambda|w_a|\}$ minimizes the optimized criterion for every confidence scale $z$, with $\lambda$ chosen to set the usable total allocation. Although the retained weights change with $z$, the allocation remains the same. In the theorem's nontrivial sampling regime, every reduced coefficient belongs to an action that has reached its supply cap. This identifies when collecting more interactions is needed to support an influential contribution. Classical proportional allocation minimizes sampling variance for unbiased estimators, including in two-phase nonresponse follow-up (Neyman, 1934; Hansen & Hurwitz, 1946; Wright, 2020). Theorem 3 proves that a single supply-capped allocation is simultaneously optimal across all confidence scales for the combined worst-case shrinkage-bias and sampling-noise criterion. It also shows that shrinkage is restricted to supply-capped actions in the nontrivial sampling regime. Theorem 4 connects this deterministic optimum to finite-sample upper bounds and minimax lower bounds under joint interaction and audit budgets, applying bounded-mean optimal recovery (Donoho, 1994) to the signed policy comparison. **Q3 & W4. Explaining the observed coverage and unresolved decisions** **The observed zero misses across 51,840 evaluations reflect intervals that combine simultaneous preliminary calibration across actions, sequence-wide error control, and worst-case variance bounds for $[0,1]$ rewards. Preliminary calibration's median share of the radius exceeds 80% in both tasks at setting 4 with five-step evaluation.** Appendix E.3 decomposes the radius and reconstructs the true reward change of each candidate. The error allowance 0.05 protects the entire adaptive run: 0.01 is assigned to simultaneous preliminary estimation across all actions, and each of eight validation episodes receives 0.005. The calibration contribution is $\frac32\sum_a|d_a|e_a$, where $e_a$ bounds the preliminary errors in action $a$'s visible-reward mean and missingness probability. Stable action-specific laws permit reuse of this preliminary sample. Of the original 51,840 interval evaluations, all cover their true changes and 11,304 exclude zero. For the setting-4 five-step candidates, let $D$ denote the true reward change and $\gamma=|D|$. The measured decomposition is: | Measurement | Controlled | GSM8K | |---|---:|---:| | Median calibration share of total radius | 83.3% | 80.1% | | 95th percentile of absolute estimation error / radius | 0.126 | 0.157 | | Median $\gamma$ among resolved candidates | 0.02496 | 0.00634 | | Median $\gamma$ among unresolved candidates | 0.00824 | 0.00060 | These measurements explain the margin between realized errors and interval widths. The bounds account for simultaneous calibration, the full adaptive sequence and bounded-reward sampling variation. Unresolved candidates have smaller typical reward changes, especially on GSM8K. Table 7 also evaluates a prediction-assisted estimator on fresh validation streams under the same error allowance. It fits a reward predictor on independent preliminary audit labels and corrects predictions using inverse-probability-weighted residuals. Four-look prediction-assisted evaluation raises GSM8K resolution from 38.3% to 47.5%, with total cost 2.652 million. All predictor-training labels are charged: 1,536 in the controlled task and 384 on GSM8K (Appendix E.2).
AuthorsOpenReview ↗

Author Response (Part 3/3)

Q4. The constant-factor separation in Theorem 4

The proved upper and lower error bounds differ by a factor bounded by approximately 8.69 at δ=0.005\delta=0.005, and by 18.86 uniformly for 0<δ≤1/40<\delta\le1/4.

The comparison holds at the same expected budgets (T,N)(T,N) with known ordinary feedback. Let rδ∗(T,N)r_\delta^*(T,N) be the smallest error radius valid with probability 1−δ1-\delta for every compatible hidden-reward law, and let Rz(T,N)\mathcal R_z(T,N) be the optimized criterion from Q2. The theorem uses scales zU=log⁡(4/δ)/2z_U=\sqrt{\log(4/\delta)/2} and zL=3kl⁡(1−δ,δ)/8z_L=\sqrt{3\operatorname{kl}(1-\delta,\delta)/8}, where kl⁡\operatorname{kl} is Bernoulli relative entropy, and establishes

\le r_\delta^*(T,N) \le\frac53\mathcal R_{z_U}(T,N).$$ Multiplying $z$ by a factor $c\ge1$ increases the optimized bias–uncertainty criterion by at most $c$. Therefore, $$\mathcal R_{z_U}(T,N) \le\max\{1,z_U/z_L\}\mathcal R_{z_L}(T,N), \qquad C_\delta=\frac{20}{3}\max\{1,z_U/z_L\}$$ bounds the multiplicative separation of the proof endpoints. At $\delta=0.005$, $z_U/z_L\approx1.304$, giving $C_\delta\approx8.69$. For $0<\delta\le1/4$, $\operatorname{kl}(1-\delta,\delta)\ge\log(4/\delta)/6$, giving $C_\delta\le(20/3)\sqrt8\approx18.86$. The factors have distinct sources. The lower argument's factor 4 combines a half-sized perturbation of hidden means with the separation needed for two error-radius intervals to be disjoint. The Bernoulli relative-entropy bound sets $z_L$. The upper factor $5/3$ comes from bounding the Bernstein range term by $2/3$ of the square-root sampling term using the optimal shrinkage relation. The remaining factor compares the two confidence scales. These constants quantify estimation-radius bounds at fixed budgets (Appendix E.3). **W3. Selection across fixed action profiles and changes within an action** **Policy learning can change overall failure visibility by shifting probability toward actions whose failures are less often observed.** Section 2.1 now makes this mechanism explicit. An action can combine a task strategy and an evidence rule. The main model fixes the joint reward–visibility law within each action during evaluation and learns the mixture over actions. In the GSM8K experiment, visible-only learning reaches 87.7% apparent accuracy and 21.6% actual accuracy by changing prompt-selection probabilities over fixed Qwen2.5-0.5B-Instruct responses with imposed reveal rates. This experiment isolates selection across existing reward–visibility profiles. Appendix E.4 separately tests changes within those profiles between evaluations. It keeps rewards fixed and moves each action's failure-reveal probability halfway toward one when the candidate increases that action's probability and toward zero otherwise ($\lambda=0.5$). Reusing the earlier calibration sample gives coverage on 2/30 controlled candidates and 0/30 GSM8K candidates; fresh calibration gives coverage on 30/30 in each task. The refresh uses an additional 147,456 and 24,576 ordinary observations, respectively. The sequence guarantee extends across such changes when fresh calibration and its subsequent validation sample the same current action-specific law, with an error share reserved for every refresh and evaluation. This separates learning the mixture of available strategies from re-estimating a strategy whose feedback law has changed.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response (Part 1/2)

We thank all three reviewers for recognizing the importance of evaluating policy updates under joint interaction and audit budgets. The revised manuscript clarifies the theoretical contribution, separates the roles of allocation and shrinkage, and adds comparisons and diagnostics addressing evaluation cost, expert verification and the scope of the guarantees.

1. Contribution and practical effects of allocation and shrinkage

The reviews requested a clearer distinction between classical allocation, the contribution of our theorems and the empirical effects of each component. Sections 4 and 7 now distinguish classical variance minimization for unbiased estimators from our joint optimization of bounded shrinkage bias and sampling uncertainty. Theorem 3 establishes that one availability-capped allocation is optimal across all confidence scales, with retained weights adapting to the scale. In its nontrivial sampling regime, every reduced coefficient belongs to an action at its availability cap. Theorem 4 connects the optimized criterion to minimax estimation error under both budgets.

Section 6.2 and Appendix D.3 explain the two components through frozen-candidate comparisons at common budgets. At moderate scarcity, capped allocation with shrinkage raises resolution over uniform acquisition with shrinkage from 33.7% to 50.7% in controlled learning and from 20.0% to 85.6% on GSM8K. Under severe scarcity, adding shrinkage to the same capped allocation raises resolution from 6.9% to 30.9% and from 1.1% to 20.0%, respectively (Table 5).

We also clarify why higher resolution need not change final reward: both rejected and unresolved candidates retain the incumbent policy. Certifying additional rejections can therefore increase resolution while preserving the retained policy path. Sections 6.2–6.3 connect final quality to accepted gains and subsequent proposals.

2. Evaluation cost, matched-expenditure alternatives and deployment value

The reviewers asked whether the validation expenditure would be better allocated to proposals, and whether cheaper evaluators can retain the same guarantee. Appendix E.1 now compares validation with larger proposal batches receiving the same total allowance before sampling. Cost is C10=I+10AC_{10}=I+10A, where II counts all interactions and AA all paid audits. Each run has 40 proposal steps and eight five-step deployment opportunities.

At setting 4, larger fully observed proposals improve final reward, and both complete-proposal learning and interval validation accept zero nonpositive changes across 240 opportunities per task. The complete-feedback batches average approximately 63,800 and 18,900 outcomes per step, compared with the original 128. Averaging these batches reduces gradient sampling noise in the stationary tasks. At setting 3, the matched-expenditure 4%-audit GSM8K proposal learner accepts five strict decreases; complete proposals and interval validation each accept zero (Table 6).

Section 6.5 and Appendix E.2 add sequential and prediction-assisted alternatives under the same 0.05 error allowance per learning run. Four planned checks reduce capped validation interactions by 70.7% in controlled learning and 30.2% on GSM8K, with the same decisions as terminal evaluation on these setting-4 runs. Total costs fall from 3.839 to 1.284 million and from 4.122 to 2.886 million. An independently trained predictor with residual correction raises GSM8K resolution from 38.3% to 47.5%, at total cost 2.652 million. All training labels are charged (Table 7).

Section 6.4 and Appendix E.1 also quantify deployment value relative to the original low-cost complete-proposal reference, which accepts 4/240 strict decreases in controlled learning and 35/240 on GSM8K. Assuming equal loss per adverse five-step release, the observed terminal-validation costs and adverse-release counts imply break-even losses of 28.69 million and 3.51 million interaction-cost units per adverse release. Substituting the four-look costs into the same calculation lowers these conditional thresholds to 9.54 million and 2.45 million. This calculation lets a deployment use its own loss estimates for candidates fixed before fresh validation.

AuthorsOpenReview ↗

General Response (Part 2/2)

3. Naturally missing rewards and expert verification

To address the request for naturally incomplete outcomes requiring expert judgment, we added TREC-COVID replay using archived expert assessments of biomedical relevance. Section 6.6 and Appendix E.5 present this study alongside GSM8K, which isolates reward-dependent visibility over fixed Qwen responses, and explain their respective roles.

Three retrieval systems return 5,044 distinct topic–article pairs: 1,517 judged initially, 894 first judged later and 2,633 still unjudged. Historical follow-up narrows the full-population BM25R2-to-T5R3 gain range from [-0.402, 0.423] to [-0.307, 0.343]. We separately evaluate randomized auditing on the eventually assessed population, where the true gain is 0.0508. With 4,096 interactions, 512 available audits and per-comparison error allowance 0.05/90.05/9, the mean radius is 0.072. Terminal capped evaluation resolves the positive gain in 3/30 seeds, leaving 27 unresolved. All 1,080 replay intervals cover their targets. These experiments count requests to archived expert judgments and distinguish the full returned collection from the population with known reward truth (Table 9).

4. Connecting theoretical complexity to observed gaps and interval widths

Questions about unresolved decisions and the zero interval misses across 51,840 original evaluations motivated the candidate-level analysis in Section 6.4 and Appendix E.3. We reconstruct every setting-4 five-step candidate and report its true change, missing-reward influence, audit use and radius decomposition.

On GSM8K, unresolved candidates have a median absolute change of 0.00060, compared with 0.00634 for resolved candidates at similar audit counts. Preliminary calibration contributes a median 83.3% of the radius in controlled learning and 80.1% on GSM8K. This decomposition explains the empirical margin between estimation errors and the bounds that protect the adaptive sequence (Table 8).

A separate experiment checks Theorem 2 in its direct-audit setting, with missing-reward influence fixed at 0.4 and error allowance 0.05. Halving the reward gap from 0.05 to 0.025 to 0.0125 raises mean stopping counts from 336 to 1,583 to 6,564 over 500 trials per gap. Appendix E.3 reports the lower benchmarks alongside these counts, testing the predicted inverse-square dependence. It also bounds the separation of Theorem 4's upper and lower error-bound endpoints by approximately 8.69 at error probability δ=0.005\delta=0.005, under the same expected interaction and audit budgets with known ordinary feedback.

5. Behavior choice, changing visibility and structured action spaces

The fixed-behavior assumption prompted questions about active data collection and changes in visibility. Section 2.1 explains that an action can combine a task strategy with an evidence rule. Changing the mixture of actions can change overall failure visibility while their conditional laws remain fixed.

Appendix E.4 tests behavior distributions chosen using the candidate before fresh validation. Fixing that choice within the episode preserves the conditional guarantee. When action-specific visibility changes between evaluations, fresh calibration and subsequent validation use the same current law, with error allowances assigned to each refresh and evaluation. Under the strongest tested visibility shift, refreshing calibration gives coverage on 30/30 candidates in each task; reusing the earlier sample covers 2/30 controlled candidates and 0/30 GSM8K candidates.

To examine calibration as the action space grows, the same appendix expands 18 action classes into 72 and 288 actions with identical conditional laws within each class. At fixed calibration expenditure, pooling maintains a mean radius near 0.0255. At 288 actions, separate estimation gives radius 0.0983 and resolves 0/30 candidates, while pooling resolves 17/30. The guarantee applies to the known classes by pooling observations and summing their policy-change coefficients.

6. Clearer problem statements, notation and experimental interpretation

We revised the abstract, introduction, formulation and experimental discussion to make the problem and mechanisms easier to follow. Section 4 introduces outcome supply and the bias–uncertainty tradeoff before the optimization formulas. Section 5 distinguishes the point estimate from its confidence radius and explains how preliminary calibration and fresh validation share the sequence-level error allowance.

Section 6.1 aligns baseline names with the figure legends and explains the cost accounting. Sections 6.2–6.3 separate decision resolution from retained quality. Sections 6.4–6.6 organize the added evidence around evaluation difficulty, lower-cost evaluation and expert follow-up, with detailed protocols and results in Appendices C–E.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.