- 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
-
The motivation is interesting. The theoretical analysis is well structured. The result that the same allocation is optimal across confidence scales is appealing.
-
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
-
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.
-
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.
-
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
-
Can the authors clarify the individual practical contributions of capped allocation and shrinkage?
-
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?
-
Under what practical conditions would the additional evaluation costs be justified?
3 comments
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.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 (, ) and per-comparison error allowance , 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.
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, where K is the action count; every action is made rare in turn. The paired analysis over 30 seeds separates the two contributions:
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 da be the candidate's change in action probability, pa the missing-reward probability, ρa the behavior probability, and T the interaction limit. Action a supplies an expected Tρapa missing outcomes. For N planned audits, define H=∑a∣da∣pa. The proportional allocation na=N∣da∣pa/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.