Optimal Sequential Annotations for Off-Policy Evaluation

1 Introduction

• Rich text or image observations can encode sequential states and rewards, while LLM-as-a-judge labels have unknown trustworthiness and expert annotation is costly.Such data arise in settings including healthcare and social services, where notes may document underlying individual states.Source: §1 · p. 1
• The method treats ground-truth annotation as missing outcome data and optimizes annotation probabilities for variance-optimal sequential off-policy evaluation.The authors distinguish this functional-estimation objective from prediction-targeting active learning.Source: §1 · pp. 1–2
• The motivating nonprofit records longitudinal client interactions in casenotes, enabling evaluation of outreach effects on intermediate outcomes such as housing-application progress.The paper notes that successful housing placement is a rare terminal event and does not capture all forms of support.Source: §1 · p. 2
• At budgets of 40% and above, variance-optimal annotation reduces RMSE relative to random annotation by 34–65% for housing placement, 17–68% for progress, and 55–62% on LMArena.The comparisons are at equal label cost on the nonprofit casenotes and LMArena human-preference votes.Source: §1 · p. 2

2 Related Work

• The approach selects a validation set for OPE with missing rewards and optimizes annotation probabilities for asymptotic variance without distributional assumptions on LLM prediction errors.The authors note that common distributional conditions for non-standard measurement error may not apply to text or images.Source: §2 · p. 2
• Unlike single-time-step annotation work, including Zrnic and Candès (2024), this paper studies sequential OPE with missing rewards and optimizes annotation probabilities.The related work also notes that the joint reward-and-state setting approximates away state-revelation effects on efficient Q-function estimation.Source: §2 · pp. 2–3
• Unlike Nwankwo et al. (2026), which optimizes annotation for average treatment-effect estimation, this work targets sequential off-policy evaluation.Nwankwo et al. (2026) is described as obtaining a closed-form solution for its single-time-step setting.Source: §2 · p. 3
• Active learning generally targets prediction error, whereas this paper targets OPE error; the authors also identify batch annotation as more relevant to querying human annotators.The authors leave strengthening the cited batch-adaptive asymptotic inferential guarantees with modern technical tools for future work.Source: §2 · p. 3
• Prior work on surrogate terminal rewards uses uniform allocation, whereas this paper annotates stagewise rewards and optimizes gold-label sampling; behavior-policy design is a separate OPE variance strategy.The comparison with Sonabend-W et al. (2023) and behavior-policy design work distinguishes which rewards are ground-truthed from which actions are collected.Source: §2 · p. 3

3 Problem Setup

• The target is the value of a fixed evaluation policy, while historical actions are generated by a behavior policy in a full-information sequential MDP.The full trajectory includes states, actions, and rewards across the horizon.Source: §3 · p. 4
• The observed data include tabular states, actions, and noisy reward proxies; annotation reveals ground-truth rewards and may also reveal next states.The proxy may be text or images, and not every datapoint can receive ground-truth annotation.Source: §3 · p. 4
• The setup permits Markovian or history-dependent reward and transition laws, but assumes sequential ignorability with respect to the tabular state rather than rich observations.In the motivating setting, outreach frequency can be scheduled using tabular information alone.Source: §3 · p. 5
• Annotation decisions are made using the already observed prefix before newly revealed stage information, with positive annotation probabilities and bounded density ratios required by the stated overlap condition.The passage also states that action overlap can be replaced by weaker concentrability assumptions standard in offline reinforcement learning.Source: §3 · p. 6
• Forward-monotone annotation reveals each stage's reward and next state along a trajectory prefix, so a later stage cannot be annotated unless all earlier stages were annotated.At the terminal stage, annotation reveals the final reward.Source: §3 · pp. 6–7, Figure 2 · p. 7

4.1 Estimation under sequential annotation protocols.

• The sequential estimator adds inverse-annotation-weighted corrections to imputed scores; under annotation ignorability and true annotation probabilities, its increments telescope in expectation, reducing variance and yielding an unbiased estimate with oracle nuisances.The variance decomposition uses the martingale structure of forward-monotone annotation protocols.Source: §4.1 · p. 8
• Approximate projections preserve orthogonal estimation and unbiasedness without requiring consistency of earlier-stage predictions, although misspecification can make variance minimization suboptimal.The proposed surrogate-variance optimization has a guarantee: uniform criterion error δ adds at most 2δ to the ε bound on optimization shortfall.Source: §4.1 · p. 10

4.2 Batch-adaptive experiment scheme

• A batch-adaptive scheme uses an initial fully annotated pilot batch to estimate nuisance functions, then updates constrained annotation probabilities using preceding batches while targeting the pooled budget-optimal design.After collection, K-fold cross-fitting estimates nuisance functions outside each fold and evaluates them on held-out observations.Source: §4.2 · p. 12

4.3 Optimized allocation probabilities.

• The convex allocation problem minimizes annotation-dependent variance subject to the expected-label budget and forward monotonicity; its optimal stagewise annotation probability is proportional to the conditional standard deviation of that stage’s score contribution.For T = 2, Theorem 1 gives a closed-form solution under the stated feasibility condition.Source: §4.3 · p. 13
• When monotonicity binds, the optimal allocation uses pointwise truncation, with its first probability determined by a numerically solvable scalar boundary KKT fixed-point equation.The fixed-point equation is described as convex decreasing or concave increasing.Source: §4.3 · p. 13

4.4 Feasible batch-adaptive annotation.

• The two-batch implementation estimates nuisances on a pilot batch, then applies a plug-in allocation with a mixture correction so the pooled design targets the optimal prefix-label distribution.The adaptive allocation uses the T = 2 optimum.Source: §4.4 · p. 14

5 Analysis

• Both non-adaptive and batch-adaptive estimators are asymptotically normal when nuisance estimators satisfy the required convergence rates.Source: §5 · p. 14, §5.1 · p. 15, §5.2 · p. 16

5.1 Asymptotic normality under the non-adaptive experiment

• The non-adaptive experiment holds annotation probabilities fixed across batches, providing an oracle benchmark for the batch-adaptive estimator.Source: §5.1 · pp. 14–15

5.2 Asymptotic normality under the batch-adaptive experiment

• In the batch-adaptive experiment, each batch’s annotation probability is derived from data in previous batches at the same fold.Source: §5.2 · p. 15
• Asymptotic inference extends to simplified estimators, including reward-and-state annotation and the corrected estimator of Equation (5), with a small cost in suboptimal variance.Source: §5.2 · p. 16

6 Experiments

• Design signals proxy unknown conditional variance: first-batch residual regression, Bernoulli p(1−p), or always-observed silver-label disagreement; allocation sets λt ∝ ŝt under floor and prefix constraints.In the experiments, conditional variance estimates are replaced by nonnegative history-measurable signals.Source: §6 · p. 17
• When reward variance is similar across timesteps, trajectory-wise annotation reduces to a Neyman problem on summed increment variances; it is suboptimal for the original problem but reduces variance versus uniform allocation.This is presented as an alternative to forward-monotone annotation in the two-stage setting.Source: §6 · pp. 17–18

6.1 Simulated data

• At a 20% budget, adaptive allocation reduces DRL RMSE by 37–40%, raises coverage to 0.92 versus 0.83, and yields 15–35% narrower intervals than random sampling.At an 80% budget, the RMSE reduction decays to approximately 12%.Source: Figure 3 · p. 18, §6.1 · p. 19

6.2 Real-world data: casenotes from street outreach for homelessness services

• Casenote ground truth is unknown, so the cohort subsampling standard errors are optimistically small; a fitted simulator offers truth-relative checks, but its effect estimates are less credible.In that simulator, annotated-DRL intervals cover the true policy value at 0.89–0.96.Source: §6.2 · p. 20
• For Any Placement, DRL RMSE falls 34–65% at budgets of 50% and above; for Progress, it falls 17–32% at 40–60% and 45–68% at 70–80%.Placement interval width falls 16–18% at budgets up to 60%; Progress interval width falls 14–20% across budgets.Source: §6.2 · p. 20

6.3 Real-world data: sequential preferences in LMArena

• For equal exposure, adaptive annotation reduces RMSE against the full-annotation benchmark by 55–62% at every budget and interval width by 34% at a 30% budget.Figure 5 also reports full-annotation estimates of Φπb = 0.967, Φequal = 0.958 and Φtilt = 0.966.Source: Figure 5 · p. 21, §6.3 · p. 21

• Each weighted annotation increment has mean zero by iterated expectation.Source: §A.1 · p. 26
• At stage t, annotation is drawn given prior annotations and F_{t−1}, before new stage-t information, with probability λt(Ft−1).Source: §A.1 · p. 26
• The tower property completes the mean-zero argument.Source: §A.1 · p. 26

A.2 Proof of Proposition 2

• Sequential increments have conditional mean zero, so cross-time terms vanish and only diagonal variance terms remain.The same argument gives orthogonality for cross-terms of the projection increments.Source: §A.2 · pp. 26–27

A.3 Proof of Theorem 1

• Strict convexity makes the KKT conditions characterize the optimal solution.Source: §A.3 · p. 27
• The budget constraint binds because the objective decreases in both annotation variables, and convexity makes the KKT conditions sufficient.Source: §A.3 · p. 28
• For decreasing prefix probabilities, the proof bounds the variance expression using the probability constraint.The stated bound follows by substituting the inequality for consecutive prefix probabilities into part (i).Source: §A.3 · p. 28

B.1 Proofs of Theorem 2

• The proof combines a negligible empirical-process term, a normally convergent oracle term, and a negligible drift term to establish the asymptotic result.Source: §B.1 · pp. 29, 31, 34

B.1.1 Proofs of Technical Lemmas

• The technical lemmas decompose feasible-versus-oracle estimation error and reduce nuisance errors from V to Q.Source: §B.1 · pp. 29–30

B.1 Proofs of Theorem 2

• The empirical-process term is negligible because its conditional mean is zero and its conditional variance vanishes under the consistency conditions.Source: §B.1 · pp. 31, 34
• The oracle term converges in distribution to a normal distribution, while the drift term is negligible under the assumed product error rates.Source: §B.1 · pp. 34–35

B.1.1 Proofs of Technical Lemmas

• The oracle projection increment measures the information gained by revealing the stage-t reward and next state rather than their projections.Source: §B.1.1 · p. 37

B.2 Proof of Theorem 3

• The adaptive drift analysis requires an additional annotation product error-rate assumption when comparing realized outcomes with counterfactual outcomes.Source: §B.2 · pp. 45–46
• Under the stated convergence, boundedness, and overlap conditions, the batch-adaptive estimator is asymptotically normal.Source: §B.2 · p. 47
• At a limiting batch design, the pooled empirical variance consistently estimates the limiting variance.Source: §B.2 · p. 47

B.3 Auxiliary lemmas

• The weight-collapse lemma relates expectations weighted by sequential annotation indicators to the corresponding annotation probabilities.Source: §B.3 · p. 47

C.1 Simulated data

• In the simulation, the less common control arm has higher variance at both stages.Source: §C.1 · p. 48

C.2 Trajectory-wise versus stagewise annotation on the casenote data

• The stagewise and trajectory-wise designs are statistically indistinguishable: their RMSE ratios range from 1.00 to 1.15, with all paired-bootstrap 95% intervals covering one and interval widths within 2%.The ratios, in order for budgets 30–80%, are 1.00, 1.00, 1.07, 1.09, 1.15, and 1.00.Source: §C.2 · p. 48
• At low budgets, stagewise allocation forgoes a second label for about 20% of clients annotated at stage 1, increasing to 0.85 at an 80% budget.The reported ratio Λ1:2/λ1 rises from approximately 0.64 at low budgets to 0.85 at 80%.Source: §C.2 · p. 48
• Trajectory-wise allocation needs a signal that ranks clients, but stagewise allocation also needs stage-1 and stage-2 signals calibrated relative to each other.The within-window variance of LLM codes is not designed for that cross-stage calibration; in a simulator with one silver-label mechanism at both stages, stagewise RMSE is 0.80–0.99 of trajectory-wise RMSE, with its largest gain of 20% at a 50% budget.Source: §C.2 · p. 48

C.3 Simulator-grounded validation of the real-data protocols

• The simulator is a monthly outreach MDP with placement, progress, and service transitions modeled using multinomial logistic regressions on random Fourier features of state and action.Its state includes prior placement, progress, service, age–gender group, shelter, and contact information; outreach is binned by monthly contact count.Source: §C.3 · pp. 48–49
• The simulator reproduces aggregate cohort moments despite noisy predictions, including placement-improvement rates of 0.215 versus 0.225 and median stage contact counts of 21 versus 19.Stage rewards are somewhat higher and less dispersed in simulation: R1 mean 2.34, sd 1.03, versus 2.20, 1.16.Source: §C.3 · p. 49
• The evaluation uses 100 replications of 600 clients and compares RMSE against the true target-policy value, 95% interval coverage, and mean interval width across placement and progress tasks.The true policy value is evaluated under the model using 100,000 rollouts; Figure 7 displays the three metrics for the two protocols.Source: §C.3 · p. 49, Figure 7 · p. 50
• Because the behavior policy is known in the simulator, the experiment validates the annotation design, outcome models, and inference, but not propensity estimation.The pipeline uses the known behavior policy in place of an estimated propensity.Source: §C.3 · pp. 49–50
• Adaptive annotation reduces RMSE against the truth by 12–38% for placement and 37–60% for progress, with coverage close to nominal across budgets.Coverage is 0.92–0.96 for random and 0.91–0.92 for adaptive placement; for progress it is 0.91–0.95 and 0.92–0.94, respectively.Source: §C.3 · p. 50, Figure 7 · p. 50

C.4 LMArena experiment details

• The release contains 135,634 battles dated April 17–July 24, 2025; after removing 15 duplicate session/order records and excluding 7,068 sessions without a first vote, 108,304 eligible sessions remain.Of the 108,304 eligible sessions, 10,196 contain both first and second votes. Session identifiers determine the units; the release does not provide user identifiers, so distinct sessions cannot be guaranteed to come from distinct users.Source: §C.4 · p. 50
• The fitted state uses week and continuation status, with first reward withheld until annotation; this tabular representation omits other prompt and session history.When continuation is absent, the second-stage value is set to zero.Source: §C.4 · p. 51
• The intervention shifts probabilities among three open-weight/closed-model pair categories while retaining model-identity distributions within category and week.Behavior probabilities are empirical category frequencies by week, estimated on the original 64,886-session training partition and held fixed in the annotation experiment.Source: §C.4 · p. 51
• The allocation uses two-stage constrained probabilities with a 0.01 floor, second-stage cost Z1, and binary-link design signals; the stage-1 signal is a surrogate for conditional score variance.The surrogate affects efficiency but not validity; reward predictors use response metadata, reward-model scores, and a TF–IDF text score.Source: §C.4 · p. 51
• Each replication samples 21,685 sessions without replacement, and an initial uniform sample reveals all available votes with probability p = 0.3B.There are 1,000 replications at budget fractions B from 0.3 to 0.8.Source: §C.4 · p. 51
• Reported intervals give model-based 95% widths, but shared sampling variation means coverage against the same-session full-annotation benchmark does not establish coverage of population policy value.The reported evaluation includes interval widths, not a coverage guarantee.Source: §C.4 · p. 52, Table 1 · p. 52