Paper deep dive
Budgeted Multi-Source Counterfactual Annotation for Off-Policy Evaluation
Biao Xiang, Ali Eshragh, Yuexing Li, Kai Wang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 10/9/2026, 8:08:13 AM
Summary
This paper addresses the problem of budgeted acquisition of counterfactual annotations for Off-Policy Evaluation (OPE) in contextual bandits. It formulates an integer allocation problem to minimize estimator variance by selecting which context-action pairs to annotate and which sources (e.g., domain experts, LLMs) to use, given source-specific costs and error profiles. The authors derive a first-annotation threshold and characterize four regimes of annotation value. They propose a majorization-minimization algorithm with dynamic-programming subroutines to solve the coupled multi-source allocation problem. Experiments on synthetic clinical and education bandits demonstrate that their method reduces mean squared error by 20.58% and 10.77% respectively compared to no annotation.
Entities (8)
Relation Signals (6)
Majorization-Minimization Algorithm → solves → Budgeted Multi-Source Counterfactual Annotation
confidence 93% · we develop a majorization-minimization algorithm with dynamic-programming subroutines that monotonically improves the objective
Large Language Models → issourcefor → Counterfactual Annotation
confidence 92% · practical sources, including domain experts and large language models (LLMs), may be costly, biased, or noisy
Domain Experts → issourcefor → Counterfactual Annotation
confidence 92% · practical sources, including domain experts and large language models (LLMs)
Majorization-Minimization Algorithm → optimizes → Mean Squared Error
confidence 90% · reduces fixed-profile mean squared error (MSE) by 20.58% and 10.77%
Off-Policy Evaluation → uses → Counterfactual Annotation
confidence 90% · Counterfactual annotations can add evidence about unobserved actions... incorporated into OPE estimators
DM+-IS Estimator → incorporates → Counterfactual Annotation
confidence 88% · we leverage the idea of the DM+-IS estimator [2] by incorporating annotations only in the reward estimate
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Off-policy evaluation (OPE) estimates the value of a target policy from logged data, but limited behavior-policy coverage can force high-variance reweighting or reward-model extrapolation. Counterfactual annotations can add evidence about unobserved actions, yet practical sources, including domain experts and large language models (LLMs), may be costly, biased, or noisy. We study budgeted acquisition of such annotations for contextual-bandit OPE. Given source-specific costs and error profiles, we formulate an integer allocation problem over context-action pairs and annotation sources to minimize the component of estimator variance that depends on the annotation plan. We characterize when annotations are valuable through a first-annotation threshold and local annotation-value regimes. For the coupled multi-source problem, we develop a majorization-minimization algorithm with dynamic-programming subroutines that monotonically improves the objective. Experiments in synthetic clinical and LLM-annotated education bandits show that our allocation method reduces fixed-profile mean squared error (MSE) by 20.58% and 10.77%, respectively, relative to no annotation.
Tags
Links
- Source: https://arxiv.org/abs/2610.10974v1
- Canonical: https://arxiv.org/abs/2610.10974v1
Trouble viewing inline? Open PDF directly →
Full Text
206,557 characters extracted from source content.
Expand or collapse full text
Budgeted Multi-Source Counterfactual Annotation for Off-Policy Evaluation Biao Xiang †thanks: Corresponding author. Email: bqx5053@psu.edu Ali Eshragh †thanks: Equal supervision. Affiliation: Johns Hopkins Carey Business School, Washington, DC Affiliation: International Computer Science Institute, Berkeley, CA Yuexing Li Kai Wang [0.1em] Pennsylvania State University State College PA Affiliation: Georgia Institute of Technology, Atlanta, GA Abstract Off-policy evaluation (OPE) estimates the value of a target policy from logged data, but limited behavior-policy coverage can force high-variance reweighting or reward-model extrapolation. Counterfactual annotations can add evidence about unobserved actions, yet practical sources, including domain experts and large language models (LLMs), may be costly, biased, or noisy. We study budgeted acquisition of such annotations for contextual-bandit OPE. Given source-specific costs and error profiles, we formulate an integer allocation problem over context-action pairs and annotation sources to minimize the component of estimator variance that depends on the annotation plan. We characterize when annotations are valuable through a first-annotation threshold and local annotation-value regimes. For the coupled multi-source problem, we develop a majorization-minimization algorithm with dynamic-programming subroutines that monotonically improves the objective. Experiments in synthetic clinical and LLM-annotated education bandits show that our allocation method reduces fixed-profile mean squared error (MSE) by 20.58%20.58\% and 10.77%10.77\%, respectively, relative to no annotation. 1 Introduction Off-policy evaluation (OPE) estimates the value of a target policy from data collected by a different behavior policy. It is especially important when online evaluation is expensive, disruptive, or risky, as in healthcare and education. In contextual bandits, logged data reveal rewards only for actions selected by the behavior policy. When the target policy assigns probability to actions that are poorly covered in the logged data, evaluation can depend on high-variance reweighting, reward-model extrapolation, or both. Counterfactual annotations offer a practical way to add evidence about unobserved actions without deploying the target policy. For example, a clinician may assess what would likely have happened under an alternative treatment, or an automated tutor may estimate a student’s response under a different instructional activity. Recent work has shown how such annotations can be incorporated into OPE estimators [1, 2]. However, a key practical question remains: when annotations are costly and imperfect, which ones should be collected? This question matters because annotation sources vary in cost and reliability. Domain experts may be accurate but expensive, while large language models (LLMs) may scale cheaply yet make systematic errors on particular context-action pairs. In the counterfactual-annotated estimator we study, such errors do not introduce bias into the policy-value estimate but affect variance through the reward model. Annotation value therefore depends jointly on source quality, cost, factual coverage, and how strongly the target policy weights the annotated action. We formulate counterfactual-annotation acquisition as a budget-constrained allocation problem: given estimates of each source’s cost, bias, and variability, choose which context-action pairs to annotate and which sources to query so as to minimize the part of the estimation error that depends on the annotation plan. The problem is discrete because annotations are acquired one at a time, and coupled because annotations for different actions in the same context jointly shape the reward model used for evaluation. These challenges require both a statistical understanding of when annotations are valuable and an optimization method for allocating them under budget. To address them, we make three contributions: (I) Annotation-value regimes. We derive a first-annotation threshold and a four-regime characterization of when annotations help immediately, help only up to a finite amount, help only after acquiring a sufficiently large batch, or do not help locally. (I) Budgeted allocation algorithm. We show that the allocation problem is coupled, nonconvex, and not generally submodular, and develop a majorization-minimization (M) algorithm with dynamic-programming subroutines that monotonically improves the original objective. (I) Empirical validation. Across synthetic and LLM-annotated bandit environments, we compare against greedy allocation and certified solver benchmarks, quantify profile-estimation sensitivity, and validate the final OPE estimator using finite pilots and independent evaluation samples. 2 Related Work Off-policy evaluation (OPE) estimates the value of a target policy from data generated by a behavior policy. Core estimators include importance sampling and per-decision variants [19], direct-method estimators that learn reward, value, or transition models [25, 26], and doubly robust (DR) estimators that combine model estimates with importance-weighted corrections [11, 12, 7]. Variance reduction and reliability have been further studied through data-efficient DR estimators [24, 13], representation-based OPE [27], empirical benchmarking [28], and confidence or estimator-selection methods [23, 22, 14, 17]. Our work builds on this OPE foundation, but addresses the acquisition stage: which counterfactual annotations to collect before applying the estimator. A related stream augments logged data with counterfactual or auxiliary information. Structural-causal methods construct counterfactual trajectories [10, 18]; semi-offline OPE reweights human counterfactual annotations to preserve the logged context distribution [1]; and CANDOR incorporates imperfect annotations into DR contextual-bandit estimators, particularly through the reward model [2]. Auxiliary-data methods such as trajectory augmentation, PERRY, and APRIL use generated trajectories or LLM-derived predictions for inference and policy evaluation [9, 15, 16, 4]. These works study how to use auxiliary information once available; we study how to allocate a finite annotation budget across heterogeneous sources. Our problem is also related to budgeted data acquisition: active learning and optimal design choose measurements under resource constraints [21, 20], while multiple-logger OPE combines logged data from different behavior policies [8]. Our setting differs because the acquired data are counterfactual rewards used in a DR reward model, rather than supervised labels or additional logged actions. Thus, annotation value is not standalone informativeness; it is defined by how the annotation changes the resulting OPE estimator’s variance under the target and behavior policies. 3 Problem Formulation We study off-policy evaluation with counterfactual annotations in a contextual bandit with finite context space S and action space A. We use separate factual datasets for reward-model fitting and OPE: fit=(s~j,a~j,r~j)j=1MD_fit=\( s_j, a_j, r_j)\_j=1^M and ope=(si,ai,ri)i=1ND_ope=\(s_i,a_i,r_i)\_i=1^N. For each record in either dataset, the context s∈s is drawn from a distribution d0d_0, the action a∈a is chosen by a behavior policy πb(⋅|s) _b(·|s), and the reward r is drawn from the reward distribution R(s,a)R(s,a). We write μr(s,a)=[r|s,a] _r(s,a)=E[r|s,a] and σr2(s,a)=Var(r|s,a) _r^2(s,a)=Var(r|s,a) for the true mean and variance of rewards for context-action pair (s,a)(s,a). In addition to the logged data, annotations may be obtained from K independent sources. For each pair (s,a)(s,a) and source k∈=1,…,Kk =\1,…,K\, let nk(s,a)n_k(s,a) be the number of collected annotations, and let gk,j∼Gk(s,a)g_k,j G_k(s,a), j=1,…,nk(s,a)j=1,…,n_k(s,a), denote independent annotation draws from that source. Denote [gk,j|s,a]=μr(s,a)+εgk(s,a)E[g_k,j|s,a]= _r(s,a)+ _g_k(s,a) and Var(gk,j|s,a)=σr2(s,a)+Δgk(s,a)Var(g_k,j|s,a)= _r^2(s,a)+ _g_k(s,a), where εgk _g_k denotes annotation bias and Δgk _g_k denotes excess annotation variance for source k. The fitting data and acquired annotations are independent of the OPE evaluation sample. Because annotations may be biased, we leverage the idea of the DM+-ISDM^+-IS estimator [2] by incorporating annotations only in the reward estimate, rather than treating them as factual rewards in the importance-sampling correction. For each pair (s,a)(s,a), let nf(s,a)=∑j=1Ms~j=s,a~j=an_f(s,a)= _j=1^M 1\ s_j=s, a_j=a\ denote the number of fitting observations for that pair in fitD_fit, and let N(s,a)=nf(s,a)+∑k=1Knk(s,a)N(s,a)=n_f(s,a)+ _k=1^Kn_k(s,a) denote the total number of factual and annotated reward observations available for that pair. We define the annotation-augmented reward estimate, for N(s,a)>0N(s,a)>0, as r^+(s,a)=∑j=1Ms~j=s,a~j=ar~j+∑k=1K∑j=1nk(s,a)gk,jN(s,a). r^+(s,a)= _j=1^M 1\ s_j=s, a_j=a\ r_j+ _k=1^K _j=1^n_k(s,a)g_k,jN(s,a). For N(s,a)=0N(s,a)=0, use a fixed default r0(s,a)r_0(s,a), this case is treated separately in Appendix B.8. Thus, for a target policy πe _e with standard common support, i.e., πb(a|s)>0 _b(a|s)>0 whenever πe(a|s)>0 _e(a|s)>0 for all s∈,a∈s ,a , the DM+-ISDM^+-IS estimator is: v^DM+-IS(πe)=1N∑i=1N[r^+(si,πe)+πe(ai|si)πb(ai|si)(ri−r^+(si,ai))], v^DM^+-IS( _e)= 1N _i=1^N [ r^+(s_i, _e)+ _e(a_i|s_i) _b(a_i|s_i) (r_i- r^+(s_i,a_i) ) ], (1) where r^+(s,πe)=∑a∈πe(a|s)r^+(s,a) r^+(s, _e)= _a _e(a|s) r^+(s,a) is the estimated value of πe _e at context s. Our goal is to minimize the mean squared error (MSE) of v^DM+-IS(πe) v^DM^+-IS( _e) by choosing n, i.e., how many annotations should be queried from each source for each context-action pair. 4 Objective Function and Budget-Constrained Allocation To express how allocation affects MSE, we define reward-model bias and variance for N(s,a)>0N(s,a)>0 as B(s,a,) B(s,a;n) =∑knk(s,a)εgk(s,a)N(s,a), = _kn_k(s,a) _g_k(s,a)N(s,a), W(s,a,) W(s,a;n) =nf(s,a)σr2(s,a)+∑knk(s,a)[σr2(s,a)+Δgk(s,a)]N(s,a)2. = n_f(s,a) _r^2(s,a)+ _kn_k(s,a) [ _r^2(s,a)+ _g_k(s,a) ]N(s,a)^2. For N(s,a)=0N(s,a)=0, set B(s,a,)=r0(s,a)−μr(s,a)B(s,a;n)=r_0(s,a)- _r(s,a) and W(s,a,)=0W(s,a;n)=0. Write ℬs()=∑aπe(a∣s)B(s,a,)B_s(n)= _a _e(a s)B(s,a;n), η(s,a)=1−πb(a∣s)η(s,a)=1- _b(a s), α1(s,a)=d0(s)πe(a∣s)2/πb(a∣s) _1(s,a)=d_0(s) _e(a s)^2/ _b(a s), and α3(s,a)=η(s,a)α1(s,a) _3(s,a)=η(s,a) _1(s,a), with α1=α3=0 _1= _3=0 when πe(a∣s)=0 _e(a s)=0. The following result isolates the part of OPE error controlled by the annotation plan. Theorem 1 (Unbiasedness and allocation-dependent MSE). Under the independent-sample design above, known behavior propensities, common support, and finite second moments, fix the factual counts and a feasible allocation n. The estimator in (1) is unbiased, and MSE()=C0+J()N,MSE(n)=C_0+ J(n)N, where C0C_0 is allocation-invariant and J() J(n) =J1()−J2()+J3(), =J_1(n)-J_2(n)+J_3(n), (2) J1() J_1(n) =∑s,aα1(s,a)B(s,a,)2, = _s,a _1(s,a)B(s,a;n)^2, J2() J_2(n) =∑sd0(s)ℬs()2, = _sd_0(s)B_s(n)^2, J3() J_3(n) =∑s,aα3(s,a)W(s,a,). = _s,a _3(s,a)W(s,a;n). Although the OPE estimator remains unbiased, annotation bias affects its variance through J1−J2J_1-J_2, alongside reward-model variance J3J_3. Because C0C_0 is allocation-invariant, minimizing J exactly minimizes fixed-profile MSE. For reporting, we distinguish J from scaled total MSE, ():=NC0+J()=NMSE()V(n):=NC_0+J(n)=NMSE(n). The unbiasedness result extends Mandyam et al. [2] to multiple sources; Appendix A gives the proof and C0C_0. Let ck>0c_k>0 be the cost of obtaining one annotation from source k, and let κ>0κ>0 be the total annotation budget. To focus on how the budget should be distributed across sources and context-action pairs, we consider the setting where each factual sample receives at most one counterfactual annotation. Let Ns:=∑a∈nf(s,a)N_s:= _a n_f(s,a) denote the number of factual samples with context s. The resulting budget-constrained allocation problem is min _n J() J(n) (3) s.t. .t. ∑s∈∑a∈∑k∈cknk(s,a)≤κ, _s _a _k c_kn_k(s,a)≤κ, ∑a∈∑k∈nk(s,a)≤Ns,∀s∈, _a _k n_k(s,a)≤ N_s, ∀ s , ∑k∈nk(s,a)≤Ns−nf(s,a),∀s∈,a∈, _k n_k(s,a)≤ N_s-n_f(s,a), ∀ s ,\;a , nk(s,a)∈ℤ≥0,∀s∈,a∈,k∈. n_k(s,a) _≥ 0, ∀ s ,\;a ,\;k . Write ℱF for the feasible set in (3). The first constraint enforces the budget; the second and third encode the one-annotation protocol and can be relaxed if repeated annotations are allowed. In practice, source profiles are estimated from an independent pilot, so we compare allocations selected under estimated and true profiles. Let θ and θ θ denote the true and estimated source profiles, and let ⋆∈argmin∈ℱJ(,θ)n ∈ _n J(n;θ). For a feasible allocation n computed using θ θ, write J(^,θ^)≤min∈ℱJ(,θ^)+ξalgJ( n; θ)≤ _n J(n; θ)+ _alg, where ξalg≥0 _alg≥ 0 is its optimization error. Let δε,δΔ _ , _ denote the uniform errors in estimated biases and excess variances, βmax _ bound annotation and default-model bias magnitudes, and A1,A2A_1,A_2 be the sensitivity constants defined in Appendix A.4. The following result translates profile-estimation and optimization errors into excess OPE MSE. Theorem 2 (Effect of source-profile estimation on MSE). Under Theorem 1’s assumptions, conditional on the independent pilot and with fixed factual reward moments and policy probabilities, MSE(^)−MSE(⋆)≤2A1δε(2βmax+δε)+2A2δΔ+ξalgN.MSE( n)-MSE(n )≤ 2A_1 _ (2 _ + _ )+2A_2 _ + _algN. (4) The guarantee allows estimated profiles to change which sources or pairs receive annotations while controlling the resulting MSE loss. As profile errors vanish, the bound reduces to ξalg/N _alg/N, distinguishing the gains from better source-profile estimates from those obtained by improving the allocation solver. We examine these two effects in §7; Appendix A.4 gives the proof. 5 Annotation Value: Thresholds, Regimes, and Multi-Source Benefits Before solving problem (3), we examine when counterfactual annotations are statistically valuable. We first study a single context-action pair and source to derive the first-annotation threshold (§5.1) and four regimes of annotation value (§5.2). These results motivate source selection and bias cancellation (§5.3), followed by an analysis of cross-action coupling in the full allocation problem (§5.4). 5.1 Local Single-Source Objective and First-Annotation Threshold To gain actionable insight, we first focus on a single context-action pair (s,a)(s,a) with nf(s,a)>0n_f(s,a)>0 and α1(s,a)>0 _1(s,a)>0, and a single annotation source g. The case nf(s,a)=0n_f(s,a)=0 is discussed in Appendix B.8. For ease of notation, we suppress the dependence on (s,a)(s,a) throughout and write nf:=nf(s,a)n_f:=n_f(s,a), ε:=εg(s,a) := _g(s,a), Δ:=Δg(s,a) := _g(s,a), σ2:=σr2(s,a)σ^2:= _r^2(s,a), σg2:=σ2+Δ _g^2:=σ^2+ , η:=η(s,a)η:=η(s,a), and αi:=αi(s,a) _i:= _i(s,a) for i=1,3i=1,3. For n annotations, the (s,a)(s,a) terms of J1+J3J_1+J_3 give the local objective ϕ(n):=α1n2ε2+α3(nfσ2+nσg2)(nf+n)2.φ(n):= _1n^2 ^2+ _3 (n_fσ^2+n _g^2 )(n_f+n)^2. (5) We omit J2J_2 here because it couples actions within the same context, and revisit its effect in §5.4. By isolating this local scenario, we derive a threshold condition under which adding the first annotation does not increase the local objective (5). Theorem 3 (First Annotation Threshold). The first annotation, corresponding to the transition n=0n=0 to n=1n=1, does not increase the local objective (5) if and only if ε2(s,a)≤η(s,a)((nf(s,a)+1)σ2(s,a)nf(s,a)−Δ(s,a)), ^2(s,a)≤η(s,a)\! ( (n_f(s,a)+1)σ^2(s,a)n_f(s,a)- (s,a) ), (6) where η(s,a)=1−πb(a∣s)η(s,a)=1- _b(a s). In particular, if Δ(s,a)≥(nf(s,a)+1)σ2/nf(s,a) (s,a)≥(n_f(s,a)+1)σ^2/n_f(s,a), then δϕ(0)>0δφ(0)>0 for every (s,a) with ε(s,a)≠0 (s,a)≠ 0. The threshold explains why the same source can be useful at one pair but not another: its bias is judged against the variance reduction available at that pair. Greater factual coverage lowers the factor (nf+1)/nf(n_f+1)/n_f, while greater excess variance reduces the remaining variance benefit; both make the first annotation harder to justify. Appendix B.3 gives the proof. 5.2 Four Regimes of Annotation Value The first-annotation threshold compares only ϕ(1)φ(1) with ϕ(0)φ(0). To understand how annotation value evolves as more annotations are added, we now characterize the behavior of the local objective ϕ(n)φ(n) over all annotation counts. Although n is integer-valued in the allocation problem, treating it as continuous reveals the marginal structure of ϕ(n)φ(n). Differentiating (5) gives ϕ′(n)=(n+)/(nf+n)3φ (n)=( a\,n+ b)/(n_f+n)^3, where :=2α1ε2nf−α3σg2 a:=2 _1 ^2n_f- _3 _g^2 and :=α3nf(Δ−σ2) b:= _3n_f( -σ^2). Thus, the sign of ϕ′(n)φ (n) is determined by the affine term n+ an+ b, yielding four possible regimes. Theorem 4 (Four Regimes of Annotation Value). In all cases, ϕ(n)→α1ε2φ(n)→ _1 ^2 as n→∞n→∞. When ==0 a= b=0, ϕφ is constant; otherwise, it falls into four regimes: (I) If ≥0 a≥ 0 and ≥0 b≥ 0, then ϕφ is increasing, so annotations are locally harmful. (I) If >0 a>0 and <0 b<0, then ϕφ decreases and then increases, with unique continuous minimizer n∗=ηnf(σ2−Δ)/(2ε2nf−ησg2)n^*=η n_f(σ^2- )/(2 ^2n_f-η _g^2). (I) If ≤0 a≤ 0 and ≤0 b≤ 0, then ϕφ is decreasing, so each annotation locally reduces the objective. (IV) If <0 a<0 and >0 b>0, then ϕφ first increases and then decreases, with unique continuous maximizer n¯=ηnf(Δ−σ2)/(ησg2−2ε2nf) n=η n_f( -σ^2)/(η _g^2-2 ^2n_f). In this regime, a strict improvement over no annotation is possible if and only if ε2<ησ2/nf ^2<ησ^2/n_f. Regime (I) favors a finite count, so spending the entire available budget on one pair can be counterproductive. In Regime (IV), a sufficiently large batch improves on no annotation only if the limiting bias contribution satisfies α1ε2<ϕ(0) _1 ^2<φ(0) (IVa); otherwise, n=0n=0 remains best (IVb). Table 1 translates these distinctions into local allocation decisions, subject to the available budget and capacities; Appendix B.4 gives the proof. Table 1: Conditions and local allocation decisions for η>0η>0, excluding the constant-objective case. Regime Excess variance Bias condition Best local action I Δ≥σ2 ≥σ^2 ε2≥ησg22nf ^2≥ η _g^22n_f no annotations (n=0)(n=0) I Δ<σ2 <σ^2 ε2>ησg22nf ^2> η _g^22n_f compare ⌊n∗⌋,⌈n∗⌉ n^* , n^* , capped by feasibility I Δ≤σ2 ≤σ^2 ε2≤ησg22nf ^2≤ η _g^22n_f add as many as feasible IV Δ>σ2 >σ^2 a: ε2<ησ2nf ^2< ησ^2n_f large batch needed to improve over n=0n=0 Δ>σ2 >σ^2 b: ησ2nf≤ε2<ησg22nf ησ^2n_f≤ ^2< η _g^22n_f no annotations (n=0)(n=0) 5.3 Source Selection and Bias Cancellation The local regimes reveal how access to multiple sources can improve allocation. Because every single-source plan remains feasible under the same budget and capacities, the multi-source optimum is no worse than the best single-source optimum. To identify where source selection can help, we apply the first-annotation threshold (6) to source k: εgk(s,a)2≤η(s,a)((nf(s,a)+1)σr2(s,a)nf(s,a)−Δgk(s,a)). _g_k(s,a)^2\;≤\;η(s,a)\! ( (n_f(s,a)+1)\, _r^2(s,a)n_f(s,a)- _g_k(s,a) ). (7) Because factual coverage and source quality vary across pairs, condition (7) can hold for different sources at different pairs. Sources can also complement one another within a pair. At a fixed total annotation count, mixing two sources with opposite-signed biases can reduce the magnitude of the reward-model bias B(s,a,)=∑knk(s,a)εgk(s,a)/N(s,a)B(s,a;n)= _kn_k(s,a) _g_k(s,a)/N(s,a) below that obtained from either source alone. The allocation must balance this reduction against source variances and costs. When one source performs well across pairs and mixing offers little bias cancellation, gains over the best single source can be modest. 5.4 From Local Thresholds to the Full Allocation Problem The benefits of source selection and mixing must be evaluated through the full objective, which includes cross-action coupling through J2J_2. For α3>0 _3>0 and zero aggregate reward-model bias in context s, including J2J_2 changes the first-annotation threshold to ε2≤(nf+1)σ2/nf−Δ ^2≤(n_f+1)σ^2/n_f- , removing the factor η from Theorem 3 and permitting larger admissible bias when the right-hand side is positive. More generally, the marginal effect of J2J_2 depends on the effective biases of all actions in the same context, while source mixing can reduce B(s,a,)B(s,a;n) via bias cancellation but reshapes ℬs()B_s(n). Together with the shared budget, this coupling motivates the joint allocation method in §6. 6 Budget-Constrained Multi-Source Allocation We now solve the multi-source allocation problem (3). Proposition 1 formalizes why the local rules from §5 cannot be applied independently: the problem has cross-action coupling, nonconvexity, and integer constraints. Proposition 1 (Structure of the allocation objective). The objective J()J(n) in problem (3) is nonnegative and bounded over all feasible allocations. Moreover, there exist valid instances for which: (I) J is non-separable across actions within the same context. (I) The continuous relaxation of J is neither convex nor concave. (I) J is neither submodular nor supermodular over annotation allocations. An annotation’s full value depends on the other allocations in its context, so independent pairwise decisions need not produce a good joint allocation. We use majorization-minimization (M) [29] to replace the cross-action coupling by a locally tight upper surrogate while retaining the exact per-pair bias-variance structure. Feasible surrogate-improving updates then guarantee monotone descent. Appendices C and D.2 give the structural proofs and descent analysis, respectively. 6.1 Majorization-Minimization Surrogate We optimize the objective J using an iterative M scheme. Starting from a feasible allocation (0)n^(0) (zero or a greedy allocation), each M iteration constructs an upper bound around (t)n^(t) and seeks a feasible update that improves this surrogate. The term −J2-J_2 is the only part of J that couples actions within the same context through ℬs()2B_s(n)^2. We majorize this coupling term, turning it into an affine function of ℬs()B_s(n) while leaving J1J_1 and J3J_3 unchanged. The following proposition shows that this replacement yields an upper bound that is exact at the current allocation. Proposition 2 (Tight majorization of J). Fix a feasible allocation (t)n^(t) at iteration t and let ℬs(t):=ℬs((t))B_s^(t):=B_s(n^(t)). Define J~full(,(t))=J1()+J3()+∑s∈d0(s)[(ℬs(t))2−2ℬs(t)ℬs()]. J_full(n;n^(t))=J_1(n)+J_3(n)+ _s d_0(s) [(B_s^(t))^2-2B_s^(t)B_s(n) ]. Then J~full J_full is a tight upper bound on J: J~full(,(t))−J()=∑s∈d0(s)(ℬs()−ℬs(t))2≥0. J_full(n;n^(t))-J(n)= _s d_0(s) (B_s(n)-B_s^(t) )^2≥ 0. In particular, J~full((t),(t))=J((t)) J_full(n^(t);n^(t))=J(n^(t)). Tightness at the current allocation ensures that a feasible update improving the surrogate cannot increase J. For computation, we drop the allocation-independent constant ∑sd0(s)(ℬs(t))2 _sd_0(s)(B_s^(t))^2, obtaining the equivalent surrogate J~(,(t))=J1()+J3()−2∑s∈d0(s)ℬs(t)ℬs(). J(n;n^(t))=J_1(n)+J_3(n)-2 _s d_0(s)B_s^(t)B_s(n). (8) Substituting ℬs()=∑aπe(a|s)B(s,a,)B_s(n)= _a _e(a|s)B(s,a;n) into (8) shows that J~ J is additively separable in (s,a)(s,a). Each iteration therefore searches for an improving allocation using these separable costs under the original constraints, preserving descent in J. Appendix D.2 gives the majorization proof. 6.2 Solving the Surrogate Allocation Problem We now describe the computational step at a fixed M iteration t. We write J~(,(t))=∑s,aJ~s,a(t)(s,a) J(n;n^(t))= _s,a J_s,a^(t)(n_s,a), where J~s,a(t) J_s,a^(t) denotes the summand of J~ J specific to the context-action pair (s,a)(s,a), and s,a:=(n1(s,a),…,nK(s,a))n_s,a:=(n_1(s,a),…,n_K(s,a)) is the source-count vector. The remaining challenge is to handle the shared budget and capacity constraints. Let C():=∑s,a,kcknk(s,a)C(n):= _s,a,kc_kn_k(s,a) denote the total annotation cost. For a fixed multiplier λ≥0λ≥ 0, we minimize the penalized surrogate J~(,(t))+λC() J(n;n^(t))+λ C(n), while retaining the per-context and context-action capacity constraints. Thus, the penalized problem decomposes by context. For each context-action pair (s,a)(s,a) and each feasible annotation count m∈0,…,Ns−nf(s,a)m∈\0,…,N_s-n_f(s,a)\, define Hs,a(t,λ)(m):=min∈ℤ+K: 1⊤=mJ~s,a(t)()+λ∑k=1Kckzk.H_s,a^(t,λ)(m):= _z _+^K:\,1 z=m \ J_s,a^(t)(z)+λ _k=1^Kc_kz_k \. Here, =(z1,…,zK)z=(z_1,…,z_K) specifies how the m annotations for (s,a)(s,a) are split across sources, and the local surrogate is evaluated with N(s,a)=nf(s,a)+mN(s,a)=n_f(s,a)+m. Thus, Hs,a(t,λ)(m)H_s,a^(t,λ)(m) is the best penalized surrogate value among all source mixtures that assign exactly m annotations to (s,a)(s,a). Exact enumeration over all source-count vectors z yields a certified solution for Hs,a(t,λ)(m)H_s,a^(t,λ)(m), but the cost grows combinatorially with K. We instead obtain approximate values Hs,a♯(m,λ)H _s,a(m,λ) by pairwise-exchange local search, which reallocates one annotation between sources at a time to reduce the penalized surrogate while keeping m fixed. Proposition 9 in Appendix D.3 bounds the resulting approximation error. Given Hs,a(t,λ)(m)H_s,a^(t,λ)(m), it remains to choose how many annotations each context-action pair receives within context s. Let ms,a:=∑k=1Knk(s,a)m_s,a:= _k=1^Kn_k(s,a) denote the total number of annotations assigned to (s,a)(s,a), aggregated over sources. For each context, the remaining problem is min∑a∈ms,aa∈Hs,a(t,λ)(ms,a)s.t.∑a∈ms,a≤Ns,ms,a∈0,…,Ns−nf(s,a),∀a∈. _\m_s,a\_a _a H_s,a^(t,λ)(m_s,a) .t. _a m_s,a≤ N_s, m_s,a∈\0,…,N_s-n_f(s,a)\,~∀ a . We solve the aggregation by dynamic programming (DP), using H♯H in place of H and allowing unused context capacity. DP is exact for these tables; the source mixtures remain approximate. We search over λ by bisection. Each trial value of λ returns a candidate allocation from the penalized problem above, computed by local source search followed by DP across actions within each context. Among the candidates satisfying C()≤κC(n)≤κ, together with the current allocation (t)n^(t), we select the one with the smallest surrogate value J~(⋅,(t)) J(·;n^(t)). Because (t)n^(t) is included as a fallback, the selected update (t+1)n^(t+1) satisfies J~((t+1),(t))≤J~((t),(t)) J(n^(t+1);n^(t))≤ J(n^(t);n^(t)) and hence J((t+1))≤J((t))J(n^(t+1))≤ J(n^(t)). We assess allocation quality by benchmarking against exact solvers. The evaluation of the empirical optimality gaps is detailed in §7. We next bound the computational cost of an M update. Proposition 3 (Runtime per M update). Let TBisT_Bis denote the total number of multiplier trials and let Tswap≥1T_swap≥ 1 bound the number of annotation reassignments per local search. One M update costs (TBis||||(K2NmaxTswap+Nmax2))O\! (T_Bis\,|S|\,|A|\,(K^2N_ \,T_swap+N_ ^2) ), where Nmax:=maxsNs≥1N_ := _sN_s≥ 1. The terms K2NmaxTswapK^2N_ T_swap and Nmax2N_ ^2 correspond to local source search and DP aggregation, respectively. With the other parameters fixed, the runtime bound grows linearly with the number of context-action pairs. Appendices D.7 and D.1 give the proof and pseudocode. 7 Numerical Experiments We evaluate 1) how source quality affects annotation value, 2) how M compares with greedy and solver benchmarks, and 3) how profile-estimation error affects final OPE performance. For comparisons with fixed source profiles, we report scaled total MSE of the estimator (1), ()=NMSE()=NC0+J()V(n)=N\,MSE(n)=NC_0+J(n). Full experimental details are deferred to Appendix E. 7.1 Annotation Value and Synthetic Validation We construct a synthetic clinical bandit with 100100 contexts, 55 actions, M=1,000M=1,000 fitting records, and budget κ=10,000κ=10,000. Detailed environment settings are in Appendix E.1. To illustrate the four regimes in Theorem 4, we construct four sources combining low or high bias with low or high excess variance (Table 2). For each source k and pair (s,a)(s,a), we independently draw bias and excess variance from normal distributions parameterized by εk _k and Δk _k, respectively. Table 2: Configuration of annotation sources. Source ID Type Bias (εk _k) Excess Variance (Δk _k) Cost (ckc_k) 1 Low Bias Low Variance 2.0 6.0 20.0 2 Low Bias High Variance 2.0 48.0 5.0 3 High Bias Low Variance 5.0 3.0 10.0 4 High Bias High Variance 5.0 48.0 1.0 We activate one source at a time and randomly allocate increasing numbers of its annotations to examine how scaled MSE changes. We average over 100100 independently sampled environments. Figure 1 matches the predicted regimes: Source 1 decreases monotonically (Regime I), Source 2 first increases and then decreases (Regime IV), Source 3 decreases and then increases (Regime I), and Source 4 increases monotonically (Regime I). The decomposition shows how variance reduction (J3J_3) competes with bias accumulation (J1J_1) and correction (J2J_2). Figure 1: Scaled mean squared error (MSE) V and the allocation-dependent components J1J_1, J2J_2, and J3J_3 versus the number of annotations for the four annotation sources in Table 2. Shaded bands show ±1± 1 standard deviation over 100100 environments. We next examine how the set of available annotation sources affects allocation quality. We evaluate all 2K−1=152^K-1=15 nonempty source subsets sub⊆1,2,3,4K_sub \1,2,3,4\ from Table 2. For multi-source subsets, we run the proposed M algorithm in §6 restricted to the active sources. For single-source subsets, we use a uniformly random allocation (assigning annotations uniformly across eligible logged samples and counterfactual actions until the budget or per-sample capacity is reached) as a non-optimized baseline; the corresponding optimized single-source results are reported in Appendix E.1.2. All runs use the same environment, factual data, and budget κ=10,000κ=10,000. Figure 2 shows that the four-source setting achieves the lowest scaled MSE among the evaluated subsets, illustrating the potential benefit of source selection and mixing discussed in §5.3. With fixed source profiles, the four-source M allocation reduces scaled MSE from ()=84.23V(0)=84.23 to 66.9066.90, corresponding to a 20.58%20.58\% MSE reduction relative to no annotation. Full convergence traces are provided in Appendix E.1.3. Figure 2: Scaled mean squared error (MSE) ()V(n) for each active source subset. Bars are grouped by the number of available sources; the dashed line is the no-annotation baseline ()=84.23V(0)=84.23. 7.2 Baselines and Solver Benchmarks To compare allocation methods with realistic annotation sources, we also construct a semi-synthetic education bandit from 6.16.1 million ASSISTments student–problem interactions [5]. Contexts are ||=100|S|=100 K-means clusters of student answer history and affect features, including past correct rate, hint usage, and detector confidences for frustration, confusion, concentration, and boredom. Actions are the ||=10|A|=10 problem_type×original combinations. Following the feature-prediction approach of APRIL [4], each LLM predicts the student’s first-response time t, which is converted to reward through R(s,a,t)=Rmax⋅PIRT(s,a)⋅TimeEff(t,t~a)R(s,a,t)=R_ · P_IRT(s,a)·TimeEff(t, t_a). Here, Rmax=30R_ =30 and PIRT(s,a)=σ(θs−ba)P_IRT(s,a)=σ( _s-b_a) is a one-parameter logistic item response theory (IRT) model [3], with context-level ability θs _s and action difficulty bab_a. The factor TimeEff(t,t~a)=max0.3, 1−0.4|log10(t/t~a)|TimeEff(t, t_a)= \0.3,\,1-0.4| _10(t/ t_a)|\ discounts responses that are much faster or slower than action a’s empirical median response time t~a t_a. We use Gemini-2.5-Flash, GPT-4o-mini, and Claude-Haiku-4.5 as annotation sources, collecting 2020 predictions per source and (s,a)(s,a) to estimate εgk(s,a) _g_k(s,a) and Δgk(s,a) _g_k(s,a). Appendix E.2 details the data processing, reward construction, LLM prompts, and M algorithm results. For the baselines, Greedy (max-gain) repeatedly selects the feasible annotation with largest positive marginal gain, while Greedy (cost-aware) uses gain per unit cost. We compare these methods with zero-initialized M and M initialized from the better greedy allocation on the ASSISTments, original synthetic, and I/IV-focused synthetic environments. The I/IV-focused environment tests allocation with locally harmful or initially harmful sources, for which single-annotation gains can be uninformative. Within each environment, all methods use the same budget, capacities, source costs, and source profiles. Table 3: Scaled MSE of allocations from M and greedy baselines. Setting No ann. Greedy (cost-aware) Greedy (max-gain) M M (greedy init) ASSISTments 88.608 79.198 79.707 79.062 79.062 Original synthetic 84.234 69.275 67.078 66.901 66.8075 I/IV-focused synthetic 84.234 72.644 71.718 70.663 70.720 Table 3 shows that M or greedy-initialized M achieves the lowest MSE in each environment, with reductions of 10.77%10.77\%, 20.68%20.68\%, and 16.11%16.11\% relative to no annotation. On the I/IV-focused instance, M improves on both greedy baselines, illustrating the value of jointly allocating annotations beyond single-step gains. To assess how close these allocations are to a global optimum, we construct 3030 small instances with 55 contexts, 33 actions, and 2525 logged samples. For each instance, we enumerate the feasible context-level choices and use Gurobi to solve the resulting multiple-choice knapsack mixed-integer linear program to certified global optimality. Table 4 shows that greedy-initialized M has the lowest mean optimality gap. On the full Synthetic and ASSISTments instances, it reaches within 0.2807%0.2807\% and 0.0050%0.0050\% of the Gurobi lower bounds, respectively (Appendix E.3). Table 4: Relative MSE gap to the certified small-instance optima. Method Mean gap (%) Std. gap (%) Median gap (%) Max gap (%) Greedy (max-gain) 0.30 0.30 0.23 0.98 Greedy (cost-aware) 3.67 3.12 3.37 17.38 M 0.31 0.27 0.26 1.08 M (greedy init.) 0.05 0.07 0.02 0.26 7.3 Robustness to Finite-Pilot Profile Estimation The preceding comparisons use fixed source profiles; we now test whether the gains persist when profiles are estimated from finite pilots. Across 3030 pilot replications, factual moments are estimated from 2020 pilot rewards per pair and annotation moments from 2020 pilot draws per source–pair. The pilot, reward-model fitting data, acquired annotations, and OPE evaluation data are mutually independent. After selecting an allocation, we evaluate DM+-IS using 5050 independent final estimates per pilot replication. Greedy-initialized M performs best, reducing empirical OPE MSE by 19.13%19.13\% on Synthetic and 8.47%8.47\% on ASSISTments relative to no annotation. As a complementary sensitivity check, we perform 3030 within-pair bootstraps of the 2020 observed LLM predictions and rerun M after re-estimating every source profile. On ASSISTments, the resulting mean reference-profile scaled-MSE reduction is 10.765%10.765\%, compared with 10.774%10.774\% using the original profiles, with a standard deviation of only 0.00380.0038 percentage points. The bootstrap indicates stable allocation quality under resampling of the observed LLM outputs, complementing the gains in final OPE MSE measured with independent evaluation data. Full protocols and baseline results are reported in Appendices E.4 and E.5. 8 Conclusion We formulated budgeted counterfactual annotation for contextual-bandit off-policy evaluation as an integer allocation problem minimizing the MSE of the DM+-ISDM^+-IS estimator. The objective separates effective annotation bias, cross-action bias correction, and reward/annotation variance, explaining why annotation sources are not interchangeable. For a single context-action pair and source, we derived a first-annotation threshold and four annotation-value regimes. For multiple sources, we established cross-action coupling, nonconvexity, and lack of submodularity, and developed a majorization-minimization algorithm with dynamic-programming subroutines that monotonically improves the objective. These results guide the purchase and allocation of counterfactual annotations under a limited budget to improve policy evaluation. Limitations and future work. Our framework is limited to contextual bandits and uses known or estimated source profiles (εgk,Δgk)( _g_k, _g_k). The ASSISTments experiment uses real LLM annotations in a semi-synthetic environment. Future work includes sequential Markov decision processes, online estimation of source profiles, and human annotations in fully real-world experiments. Acknowledgments and Disclosure of Funding The authors thank Aishwarya Mandyam for introducing the original problem that motivated this line of work. This work was supported in part by the Johns Hopkins Carey Business School. This work was supported by NSF IIS-2403240, NSF IIS-2552007, NIH R01HL184139, and Schmidt Sciences AI2050 Fellowship. The authors declare no competing interests. References [1] Shengpu Tang and Jenna Wiens. Counterfactual-augmented importance sampling for semi-offline policy evaluation. In Advances in Neural Information Processing Systems, volume 36, 2023. [2] Aishwarya Mandyam, Shengpu Tang, Jiayu Yao, Jenna Wiens, and Barbara E. Engelhardt. CANDOR: Counterfactual annotated doubly robust off-policy evaluation. arXiv preprint arXiv:2412.08052, 2024. [3] Maria Orlando Edelen and Bryce B. Reeve. Applying item response theory (IRT) modeling to questionnaire development, evaluation, and refinement. Quality of Life Research, 16(Suppl. 1):5–18, 2007. [4] Aishwarya Mandyam, Kalyani Limaye, Barbara E. Engelhardt, and Emily Alsentzer. APRIL: Annotations for policy evaluation with reliable inference from LLMs. In Machine Learning for Health, volume 297 of Proceedings of Machine Learning Research, 2025. [5] Mingyu Feng, Neil T. Heffernan, and Kenneth R. Koedinger. Addressing the assessment challenge with an online system that tutors as it assesses. User Modeling and User-Adapted Interaction, 19(3):243–266, 2009. [6] Yutao Wang, Neil T. Heffernan, and Cristina Heffernan. Towards better affect detectors: Effect of missing skills, class features and common wrong answers. In Proceedings of the Fifth International Conference on Learning Analytics and Knowledge, pages 31–35. ACM, 2015. [7] Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 652–661. PMLR, 2016. [8] Aman Agarwal, Soumya Basu, Tobias Schnabel, and Thorsten Joachims. Effective evaluation using logged bandit feedback from multiple loggers. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 687–696, 2017. [9] Anastasios N. Angelopoulos, Stephen Bates, Clara Fannjiang, Michael I. Jordan, and Tijana Zrnic. Prediction-powered inference. Science, 382(6671):669–674, 2023. [10] Lars Buesing, Théophane Weber, Yori Zwols, Sébastien Racanière, Arthur Guez, Jean-Baptiste Lespiau, and Nicolas Heess. Woulda, coulda, shoulda: Counterfactually-guided policy search. In International Conference on Learning Representations, 2019. [11] Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning, pages 1097–1104, 2011. [12] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485–511, 2014. [13] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1447–1456. PMLR, 2018. [14] Daniele Foffano, Alessio Russo, and Alexandre Proutière. Conformal off-policy evaluation in Markov decision processes. In Proceedings of the 62nd IEEE Conference on Decision and Control, pages 3087–3094. IEEE, 2023. [15] Ge Gao, Qitong Gao, Xi Yang, Song Ju, Miroslav Pajić, and Min Chi. On trajectory augmentations for off-policy evaluation. In International Conference on Learning Representations, 2024. [16] Aishwarya Mandyam, Jason Meng, Ge Gao, Jiankai Sun, Mac Schwager, Barbara E. Engelhardt, and Emma Brunskill. PERRY: Policy evaluation with confidence intervals using auxiliary data. arXiv preprint arXiv:2507.20068, 2025. [17] Allen Nie, Yash Chandak, Christina J. Yuan, Anirudhan Badrinath, Yannis Flet-Berliac, and Emma Brunskill. OPERA: Automatic offline policy evaluation with re-weighted aggregates of multiple estimators. In Advances in Neural Information Processing Systems, volume 37, 2024. [18] Michael Oberst and David Sontag. Counterfactual off-policy evaluation with Gumbel-Max structural causal models. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4881–4890. PMLR, 2019. [19] Doina Precup, Richard S. Sutton, and Satinder Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the 17th International Conference on Machine Learning, pages 759–766, 2000. [20] Friedrich Pukelsheim. Optimal Design of Experiments. Society for Industrial and Applied Mathematics, 2006. [21] Burr Settles. Active learning literature survey. Computer Sciences Technical Report 1648, University of Wisconsin–Madison, 2009. [22] Muhammad Faaiz Taufiq, Jean-François Ton, Rob Cornish, Yee Whye Teh, and Arnaud Doucet. Conformal off-policy prediction in contextual bandits. In Advances in Neural Information Processing Systems, volume 35, pages 31512–31524, 2022. [23] Philip S. Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off-policy evaluation. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 3000–3006, 2015. [24] Philip S. Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2139–2148. PMLR, 2016. [25] Alina Beygelzimer and John Langford. The offset tree for learning with partial labels. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 129–138, 2009. [26] Hoang M. Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3703–3712. PMLR, 2019. [27] Yao Liu, Omer Gottesman, Aniruddh Raghu, Matthieu Komorowski, Aldo A. Faisal, Finale Doshi-Velez, and Emma Brunskill. Representation balancing MDPs for off-policy policy evaluation. In Advances in Neural Information Processing Systems, volume 31, pages 2649–2658, 2018. [28] Cameron Voloshin, Hoang M. Le, Nan Jiang, and Yisong Yue. Empirical study of off-policy policy evaluation for reinforcement learning. In Advances in Neural Information Processing Systems, Datasets and Benchmarks Track, 2021. [29] David R. Hunter and Kenneth Lange. A tutorial on M algorithms. The American Statistician, 58(1):30–37, 2004. Appendix A Derivations for the Objective Function This appendix provides the full, step-by-step derivations for the explicit forms of the variance decomposition described in the main text. Throughout the appendices, we interpret πe(a|s)/πb(a|s) _e(a|s)/ _b(a|s) and πe(a|s)2/πb(a|s) _e(a|s)^2/ _b(a|s) as zero whenever πe(a|s)=0 _e(a|s)=0, consistent with the coefficient convention preceding (2). Recall that variance of the DM+-ISDM^+-IS estimator is decomposed as: NVar(v^DM+-IS(πe)) NVar ( v^DM^+-IS( _e) ) =Vars∼d0(v(πe|s)) =Var_s d_0(v( _e|s)) +s∼d0[a∼πb(⋅|s)[ρ(s,a)2σr2(s,a)]] +E_s d_0 [E_a _b(·|s) [ρ(s,a)^2 _r^2(s,a) ] ] +s∼d0[a∼πb(⋅|s)[ρ(s,a)2ε^r^+(s,a)2]−ε^r^+πe(s)2] +E_s d_0 [E_a _b(·|s) [ρ(s,a)^2 _ r^+(s,a)^2 ]- _ r^+ _e(s)^2 ] +s∼d0[a∼πb(⋅|s)[(ρ(s,a)2−πe(a|s)2πb(a|s))×Var(r^+(s,a))]] +E_s d_0 [E_a _b(·|s) [ (ρ(s,a)^2- _e(a|s)^2 _b(a|s) )×Var_D ( r^+(s,a) ) ] ] The total variance is decomposed as follows: NVar(v^DM+-IS(πe))=T1+T2+T3+T4NVar ( v^DM^+-IS( _e) )=T_1+T_2+T_3+T_4 where T1T_1 and T2T_2 can be seen as constant with respect to n. We focus on deriving the explicit forms of T3T_3 and T4T_4. In addition, as proved in [2], v^DM+-IS(πe) v^DM^+-IS( _e) remain unbiased even the annotations are biased. Thus, MSE()=0+Var(v^DM+-IS(πe))=C0+J()N,MSE(n)=0+Var ( v^DM^+-IS( _e) )=C_0+ J(n)N, where C0=Vars∼d0(v(πe|s))+s∼d0[a∼πb(⋅|s)[ρ(s,a)2σr2(s,a)]]NC_0= Var_s d_0(v( _e|s))+E_s d_0 [E_a _b(·|s) [ρ(s,a)^2 _r^2(s,a) ] ]N. A.1 Term 3 The third term is given by: T3=s∼d0[a∼πb(⋅|s)[ρ(s,a)2ε^r^+(s,a)2]−ε^r^+πe(s)2]T_3=E_s d_0 [E_a _b(·|s) [ρ(s,a)^2 _ r^+(s,a)^2 ]- _ r^+ _e(s)^2 ] (9) First, we derive the bias ε^r^+(s,a) _ r^+(s,a) for a pair with N(s,a)>0N(s,a)>0. We begin by calculating the expectation [r^+(s,a)]E_D[ r^+(s,a)]: [r^+(s,a)] _D[ r^+(s,a)] =1N(s,a)(∑i=1nf(s,a)[ri]+∑k=1K∑j=1nk(s,a)[gk,j]) = 1N(s,a) ( _i=1^n_f(s,a)E[r_i]+ _k=1^K _j=1^n_k(s,a)E[g_k,j] ) =1N(s,a)(nf(s,a)μr(s,a)+∑k=1Knk(s,a)(μr(s,a)+εgk(s,a))) = 1N(s,a) (n_f(s,a) _r(s,a)+ _k=1^Kn_k(s,a)( _r(s,a)+ _g_k(s,a)) ) =1N(s,a)(nf(s,a)μr(s,a)+∑k=1Knk(s,a)μr(s,a)+∑k=1Knk(s,a)εgk(s,a)) = 1N(s,a) (n_f(s,a) _r(s,a)+ _k=1^Kn_k(s,a) _r(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a) ) =1N(s,a)((nf(s,a)+∑k=1Knk(s,a))μr(s,a)+∑k=1Knk(s,a)εgk(s,a)) = 1N(s,a) ( (n_f(s,a)+ _k=1^Kn_k(s,a) ) _r(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a) ) =1N(s,a)(N(s,a)μr(s,a)+∑k=1Knk(s,a)εgk(s,a)) = 1N(s,a) (N(s,a) _r(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a) ) =μr(s,a)+∑k=1Knk(s,a)εgk(s,a)N(s,a). = _r(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a)N(s,a). The bias term ε^r^+(s,a) _ r^+(s,a) is defined as: ε^r^+(s,a) _ r^+(s,a) :=[r^+(s,a)]−μr(s,a) :=E_D[ r^+(s,a)]- _r(s,a) =(μr(s,a)+∑k=1Knk(s,a)εgk(s,a)N(s,a))−μr(s,a) = ( _r(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a)N(s,a) )- _r(s,a) =∑k=1Knk(s,a)εgk(s,a)N(s,a) = _k=1^Kn_k(s,a) _g_k(s,a)N(s,a) (10) If N(s,a)=0N(s,a)=0, the fixed default instead gives ε^r^+(s,a)=r0(s,a)−μr(s,a) _ r^+(s,a)=r_0(s,a)- _r(s,a). Thus ε^r^+(s,a)=B(s,a,) _ r^+(s,a)=B(s,a;n) in both cases, using the definition preceding (2). Next, we derive ε^r^+πe(s) _ r^+ _e(s) by expanding the expectation over the target policy πe _e: ε^r^+πe(s) _ r^+ _e(s) :=a∼πe(⋅|s)[ε^r^+(s,a)] :=E_a _e(·|s)[ _ r^+(s,a)] =∑a∈πe(a|s)ε^r^+(s,a) = _a _e(a|s) _ r^+(s,a) =∑a∈πe(a|s)B(s,a,) = _a _e(a|s)B(s,a;n) (11) Substituting these bias expressions into (9) gives T3 T_3 =∑s∈d0(s)(a∼πb(⋅|s)[ρ(s,a)2ε^r^+(s,a)2]−(ε^r^+πe(s))2) = _s d_0(s) (E_a _b(·|s) [ρ(s,a)^2 _ r^+(s,a)^2 ]- ( _ r^+ _e(s) )^2 ) =∑s∈d0(s)(∑a∈πb(a|s)ρ(s,a)2B(s,a,)2−(∑a∈πe(a|s)B(s,a,))2) = _s d_0(s) ( _a _b(a|s)ρ(s,a)^2B(s,a;n)^2- ( _a _e(a|s)B(s,a;n) )^2 ) (12) We simplify the importance sampling weight term πb(a|s)ρ(s,a)2 _b(a|s)ρ(s,a)^2: πb(a|s)ρ(s,a)2 _b(a|s)ρ(s,a)^2 =πb(a|s)(πe(a|s)πb(a|s))2=πe(a|s)2πb(a|s) = _b(a|s) ( _e(a|s) _b(a|s) )^2= _e(a|s)^2 _b(a|s) Substituting this back into (12): T3 T_3 =∑s∈d0(s)[∑a∈πe(a|s)2πb(a|s)B(s,a;)2 = _s d_0(s) [ _a _e(a|s)^2 _b(a|s)B(s,a;n)^2 −(∑a∈πe(a|s)B(s,a;))2] - ( _a _e(a|s)B(s,a;n) )^2 ] (13) A.2 Term 4 The fourth term is given by: T4=s∼d0[a∼πb(⋅|s)[(ρ(s,a)2−πe(a|s)2πb(a|s))Var(r^+(s,a))]]T_4=E_s d_0 [E_a _b(·|s) [ (ρ(s,a)^2- _e(a|s)^2 _b(a|s) )Var_D ( r^+(s,a) ) ] ] (14) First, for N(s,a)>0N(s,a)>0, we calculate the reward-model variance Var(r^+(s,a))Var_D ( r^+(s,a) ). Using the independence of samples: Var(r^+(s,a)) _D ( r^+(s,a) ) =Var(1N(s,a)(∑i=1nf(s,a)ri+∑k=1K∑j=1nk(s,a)gk,j)) =Var_D ( 1N(s,a) ( _i=1^n_f(s,a)r_i+ _k=1^K _j=1^n_k(s,a)g_k,j ) ) =1N(s,a)2(∑i=1nf(s,a)Var(ri)+∑k=1K∑j=1nk(s,a)Var(gk,j)) = 1N(s,a)^2 ( _i=1^n_f(s,a)Var(r_i)+ _k=1^K _j=1^n_k(s,a)Var(g_k,j) ) =1N(s,a)2(nf(s,a)σr2(s,a)+∑k=1Knk(s,a)(σr2(s,a)+Δgk(s,a))) = 1N(s,a)^2 (n_f(s,a) _r^2(s,a)+ _k=1^Kn_k(s,a)( _r^2(s,a)+ _g_k(s,a)) ) =1N(s,a)2(nf(s,a)σr2(s,a)+∑k=1Knk(s,a)σr2(s,a)+∑k=1Knk(s,a)Δgk(s,a)) = 1N(s,a)^2 (n_f(s,a) _r^2(s,a)+ _k=1^Kn_k(s,a) _r^2(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a) ) =1N(s,a)2((nf(s,a)+∑k=1Knk(s,a))σr2(s,a)+∑k=1Knk(s,a)Δgk(s,a)) = 1N(s,a)^2 ( (n_f(s,a)+ _k=1^Kn_k(s,a) ) _r^2(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a) ) =1N(s,a)2(N(s,a)σr2(s,a)+∑k=1Knk(s,a)Δgk(s,a)) = 1N(s,a)^2 (N(s,a) _r^2(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a) ) =σr2(s,a)N(s,a)+∑k=1Knk(s,a)Δgk(s,a)N(s,a)2 = _r^2(s,a)N(s,a)+ _k=1^Kn_k(s,a) _g_k(s,a)N(s,a)^2 (15) For N(s,a)=0N(s,a)=0, the fixed default has variance zero, so Var(r^+(s,a))=W(s,a,)Var_D( r^+(s,a))=W(s,a;n) in both cases. Next, we substitute this variance into (14) and expand the expectations, evaluating divisions by πb(a|s) _b(a|s) only on its positive support: T4 T_4 =∑s∈d0(s)∑a:πb(a|s)>0πb(a|s)[(ρ(s,a)2−πe(a|s)2πb(a|s))Var(r^+(s,a))] = _s d_0(s) _a: _b(a|s)>0 _b(a|s) [ (ρ(s,a)^2- _e(a|s)^2 _b(a|s) )Var_D ( r^+(s,a) ) ] =∑s∈d0(s)∑a:πb(a|s)>0[(πb(a|s)ρ(s,a)2−πb(a|s)πb(a|s)πe(a|s)2)Var(r^+(s,a))] = _s d_0(s) _a: _b(a|s)>0 [ ( _b(a|s)ρ(s,a)^2- _b(a|s) _b(a|s) _e(a|s)^2 )Var_D ( r^+(s,a) ) ] =∑s∈d0(s)∑a:πb(a|s)>0[(πb(a|s)πe(a|s)2πb(a|s)2−πe(a|s)2)Var(r^+(s,a))] = _s d_0(s) _a: _b(a|s)>0 [ ( _b(a|s) _e(a|s)^2 _b(a|s)^2- _e(a|s)^2 )Var_D ( r^+(s,a) ) ] =∑s∈d0(s)∑a∈(πe(a|s)2πb(a|s)−πe(a|s)2)W(s,a,) = _s d_0(s) _a ( _e(a|s)^2 _b(a|s)- _e(a|s)^2 )W(s,a;n) (16) A.3 Objective Function Let =nj(s,a)s∈,a∈,j∈n=\n_j(s,a)\_s ,a ,j denotes the set of decision variables. Combining (13) and (16), the objective function is: J() J(n) =∑s∈d0(s)[∑a∈πe(a|s)2πb(a|s)B(s,a;)2 = _s d_0(s) [ _a _e(a|s)^2 _b(a|s)B(s,a;n)^2 −(∑a∈πe(a|s)B(s,a,))2 - ( _a _e(a|s)B(s,a;n) )^2 +∑a∈(πe(a|s)2πb(a|s)−πe(a|s)2)W(s,a;)]. + _a ( _e(a|s)^2 _b(a|s)- _e(a|s)^2 )W(s,a;n) ]. A.4 Theoretical bound for source-profile estimation error The MSE decomposition above depends on source biases εgk _g_k and excess variances Δgk _g_k, which must often be estimated from pilot annotations. We first bound the resulting perturbation of J uniformly over feasible allocations, then translate this bound into the MSE guarantee in Theorem 2. Appendices E.4 and E.5 complement this analysis with finite-pilot evaluation and within-pair resampling. Write x=(s,a)∈:=×x=(s,a) :=S×A, and define fx:=nf(s,a),mx():=∑k=1Knk(s,a),Nx():=fx+mx().f_x:=n_f(s,a), m_x(n):= _k=1^Kn_k(s,a), N_x(n):=f_x+m_x(n). Let θ:=(εgk(x),Δgk(x))x,kθ:= \ ( _g_k(x), _g_k(x) ) \_x,k and θ^:=(ε^gk(x),Δ^gk(x))x,k θ:= \ ( _g_k(x), _g_k(x) ) \_x,k denote the true and estimated source profiles, respectively. Define the uniform estimation errors δε:=maxx,k|ε^gk(x)−εgk(x)|,δΔ:=maxx,k|Δ^gk(x)−Δgk(x)|. _ := _x,k | _g_k(x)- _g_k(x) |, _ := _x,k | _g_k(x)- _g_k(x) |. To include the zero-factual-coverage case of Appendix B.8, define Bx(,θ):=∑k=1Knk(x)εgk(x)Nx(),Nx()>0,r0(x)−μr(x),Nx()=0.B_x(n;θ):= cases _k=1^Kn_k(x) _g_k(x)N_x(n),&N_x(n)>0,\\[12.0pt] r_0(x)- _r(x),&N_x(n)=0. cases The same default r0(x)r_0(x) is used under θ and θ θ. Let βmax:=maxmaxx,k|εgk(x)|,maxx:fx=0|r0(x)−μr(x)|. _ := \ _x,k| _g_k(x)|,\, _x:f_x=0|r_0(x)- _r(x)| \. If factual rewards, source annotations, and the default value all lie in [0,R][0,R], then βmax≤R _ ≤ R. We next define two sensitivity constants. First, A1:=∑s∈∑a∈α1(s,a).A_1:= _s _a _1(s,a). For the excess-variance term, let MxM_x denote the maximum number of annotations that can feasibly be assigned to pair x. Define γx:=max0≤m≤Mxm∈ℤm(fx+m)2,fx+m>0,0,fx=m=0. _x:= _ subarrayc0≤ m≤ M_x\\ m subarray cases m(f_x+m)^2,&f_x+m>0,\\[8.0pt] 0,&f_x=m=0. cases (17) Define A2:=∑x∈α3(x)γx.A_2:= _x _3(x) _x. Lemma 1 (Uniform perturbation of the allocation objective). For every feasible allocation ∈ℱn , |J(,θ^)−J(,θ)|≤Φ(δε,δΔ), |J(n; θ)-J(n;θ) |≤ ( _ , _ ), (18) where Φ(δε,δΔ):=A1δε(2βmax+δε)+A2δΔ. ( _ , _ ):=A_1 _ (2 _ + _ )+A_2 _ . Proof. Fix an allocation n, and define Ux():=Bx(,θ^)−Bx(,θ).U_x(n):=B_x(n; θ)-B_x(n;θ). If Nx()>0N_x(n)>0, then Ux()=∑knk(x)(ε^gk(x)−εgk(x))Nx(),U_x(n)= _kn_k(x) ( _g_k(x)- _g_k(x) )N_x(n), and hence |Ux()|≤mx()Nx()δε≤δε.|U_x(n)|≤ m_x(n)N_x(n) _ ≤ _ . (19) If Nx()=0N_x(n)=0, the same default is used under both parameter sets, so Ux()=0U_x(n)=0. Moreover, |Bx(,θ)|≤βmax.|B_x(n;θ)|≤ _ . For each context s, define Ms:=d0(s)[diag(πe(a∣s)2πb(a∣s))a∈−e(s)e(s)⊤],M_s:=d_0(s) [diag ( _e(a s)^2 _b(a s) )_a - π_e(s) π_e(s) ], where e(s):=(πe(a∣s))a∈ π_e(s):=( _e(a s))_a . For any z∈ℝ||z ^|A|, z⊤Msz z M_sz =d0(s)[∑aπe(a∣s)2πb(a∣s)za2−(∑aπe(a∣s)za)2] =d_0(s) [ _a _e(a s)^2 _b(a s)z_a^2- ( _a _e(a s)z_a )^2 ] =d0(s)Vara∼πb(⋅∣s)[πe(a∣s)πb(a∣s)za]≥0. =d_0(s)Var_a _b(· s) [ _e(a s) _b(a s)z_a ]≥ 0. Therefore, Ms⪰0M_s 0. Let s:=(Bs,a(,θ))a∈,s:=(Us,a())a∈. B_s:= (B_s,a(n;θ) )_a , U_s:= (U_s,a(n) )_a . The combined bias term satisfies J1(,θ)−J2(,θ)=∑s⊤Mss.J_1(n;θ)-J_2(n;θ)= _s B_s M_s B_s. Using the seminorm induced by Mss\M_s\_s, |[J1(,θ^)−J2(,θ^)]−[J1(,θ)−J2(,θ)]| | [J_1(n; θ)-J_2(n; θ) ]- [J_1(n;θ)-J_2(n;θ) ] | (20) ≤2(∑s⊤Mss)1/2(∑s⊤Mss)1/2+∑s⊤Mss. ≤ 2 ( _s B_s M_s B_s )^1/2 ( _s U_s M_s U_s )^1/2+ _s U_s M_s U_s. Because the rank-one term subtracted in MsM_s is nonnegative, ∑s⊤Mss≤∑s,aα1(s,a)Bs,a2≤A1βmax2, _s B_s M_s B_s≤ _s,a _1(s,a)B_s,a^2≤ A_1 _ ^2, (21) and, using (19), ∑s⊤Mss≤∑s,aα1(s,a)Us,a2≤A1δε2. _s U_s M_s U_s≤ _s,a _1(s,a)U_s,a^2≤ A_1 _ ^2. (22) Substituting (21)–(22) into (20) gives |[J1(,θ^)−J2(,θ^)]−[J1(,θ)−J2(,θ)]|≤A1δε(2βmax+δε). | [J_1(n; θ)-J_2(n; θ) ]- [J_1(n;θ)-J_2(n;θ) ] |≤ A_1 _ (2 _ + _ ). (23) For the excess-variance term, |J3(,θ^)−J3(,θ)| |J_3(n; θ)-J_3(n;θ) | ≤∑xα3(x)∑knk(x)|Δ^gk(x)−Δgk(x)|Nx()2 ≤ _x _3(x) _kn_k(x) | _g_k(x)- _g_k(x) |N_x(n)^2 (24) ≤δΔ∑xα3(x)mx()(fx+mx())2 ≤ _ _x _3(x) m_x(n)(f_x+m_x(n))^2 ≤A2δΔ, ≤ A_2 _ , where the ratio is defined as zero when fx=mx=0f_x=m_x=0, and the last inequality follows from (17). Combining (23) and (24) proves (18). ∎ Let ⋆∈argmin∈ℱJ(,θ)n ∈ _n J(n;θ) be an optimal allocation under the population profiles. Let n be the allocation returned by Algorithm 1 using θ θ, and suppose that J(^,θ^)≤min∈ℱJ(,θ^)+ξalg,J( n; θ)≤ _n J(n; θ)+ _alg, (25) where ξalg≥0 _alg≥ 0 denotes the algorithmic suboptimality on the estimated objective. Theorem 2 (Effect of source-profile estimation on MSE). Under the assumptions of Theorem 1, assume that the pilot/allocation sample, the reward-model and annotation sample, and the OPE evaluation sample are independent. Conditional on the pilot, with factual counts, factual reward moments, and policy probabilities fixed, source-profile estimation introduces no additional OPE bias, and MSE(^)−MSE(⋆)≤2A1δε(2βmax+δε)+2A2δΔ+ξalgN.MSE( n)-MSE(n )≤ 2A_1 _ (2 _ + _ )+2A_2 _ + _algN. Proof. Let ^⋆∈argmin∈ℱJ(,θ^). n^\, ∈ _n J(n; θ). By adding and subtracting the estimated-objective values, J(^,θ)−J(⋆,θ) J( n;θ)-J(n ;θ) =[J(^,θ)−J(^,θ^)]+[J(^,θ^)−J(^⋆,θ^)] = [J( n;θ)-J( n; θ) ]+ [J( n; θ)-J( n^\, ; θ) ] +[J(^⋆,θ^)−J(⋆,θ^)]+[J(⋆,θ^)−J(⋆,θ)]. + [J( n^\, ; θ)-J(n ; θ) ]+ [J(n ; θ)-J(n ;θ) ]. By Lemma 1, the first and fourth terms are each at most Φ(δε,δΔ) ( _ , _ ). By (25), the second term is at most ξalg _alg, and the third term is nonpositive by the optimality of ^⋆ n^\, for the estimated objective. Hence, J(^,θ)−J(⋆,θ)≤2Φ(δε,δΔ)+ξalg.J( n;θ)-J(n ;θ)≤ 2 ( _ , _ )+ _alg. (26) Using Φ(δε,δΔ)=A1δε(2βmax+δε)+A2δΔ, ( _ , _ )=A_1 _ (2 _ + _ )+A_2 _ , this becomes J(^,θ)−J(⋆,θ)≤2A1δε(2βmax+δε)+2A2δΔ+ξalg.J( n;θ)-J(n ;θ)≤ 2A_1 _ (2 _ + _ )+2A_2 _ + _alg. (27) Under the stated data separation, DM+-IS is unbiased conditional on the pilot-selected allocation. Theorem 1 therefore gives MSE()=C0+J(,θ)N.MSE(n)=C_0+ J(n;θ)N. Subtracting the MSE at ⋆n and applying (27) proves (4). ∎ Appendix B Threshold for Valuable Annotation for a single annotation source In this appendix, we analyze, for a single annotation source, under what conditions adding counterfactual annotations improves or degrades the estimator variance. We begin with the simplest case (within a single context-action pair), then extend to actions within a single context, and finally consider arbitrary context-action pairs. B.1 Setup and Notation We consider a single annotation source (K=1K=1) and suppress the source index. For a fixed context-action pair (s,a)(s,a), let nf:=nf(s,a)n_f:=n_f(s,a), ε:=εg(s,a) := _g(s,a), Δ:=Δg(s,a) := _g(s,a), σ2:=σr2(s,a)σ^2:= _r^2(s,a), and n denote the number of annotations. We assume nf>0n_f>0 and α1>0 _1>0 for the analysis below; the case nf=0n_f=0 is treated in Appendix B.8. The total sample size is N:=nf+nN:=n_f+n. Define the total annotation variance as σg2:=σ2+Δ _g^2:=σ^2+ , and the policy-dependent ratio: η(s,a):=α3(s,a)α1(s,a)=πe(a|s)2πb(a|s)−πe(a|s)2πe(a|s)2πb(a|s)=1−πb(a|s).η(s,a):= _3(s,a) _1(s,a)= _e(a|s)^2 _b(a|s)- _e(a|s)^2 _e(a|s)^2 _b(a|s)=1- _b(a|s). (28) This ratio satisfies 0≤η(s,a)<10≤η(s,a)<1 under the common support assumption πb(a|s)>0 _b(a|s)>0, and measures how much the behavior policy under-covers action a: small πb(a|s) _b(a|s) yields η close to 1. B.2 Bias Threshold for a Single Context-Action Pair Ignoring the cross-action bias correction term (J2J_2) (since J2J_2 couples all actions together, we will analysis it later in B.6), the contribution of a single (s,a)(s,a) to the objective is: ϕ(n):=α1n2ε2N2+α3(σ2N+nΔN2)=α1n2ε2+α3(nfσ2+nσg2)N2.φ(n):= _1 n^2 ^2N^2+ _3 ( σ^2N+ n N^2 )= _1n^2 ^2+ _3 (n_fσ^2+n _g^2 )N^2. (29) Lemma 2 (Marginal Change for a single (s,a)). The marginal change in the local objective when increasing the annotation count from n to n+1n+1 is: δϕ(n) δφ(n) :=ϕ(n+1)−ϕ(n) :=φ(n+1)-φ(n) (30) =α1ε2nf((2n+1)N+n)+α3σg2(nf2−n(n+1))−α3nfσ2(2N+1)N2(N+1)2, = _1 ^2n_f ((2n+1)N+n )+ _3 _g^2 (n_f^2-n(n+1) )- _3n_fσ^2(2N+1)N^2(N+1)^2, where N=nf+nN=n_f+n. Proof. Write ϕ(n)=P(n)N2φ(n)= P(n)N^2 where P(n)=α1n2ε2+α3nfσ2+α3nσg2P(n)= _1n^2 ^2+ _3n_fσ^2+ _3n _g^2. Then: δϕ(n)=P(n+1)⋅N2−P(n)⋅(N+1)2N2(N+1)2.δφ(n)= P(n+1)· N^2-P(n)·(N+1)^2N^2(N+1)^2. (31) We decompose P(n+1)=P(n)+α1(2n+1)ε2+α3σg2P(n+1)=P(n)+ _1(2n+1) ^2+ _3 _g^2 and expand the numerator: P(n+1)N2−P(n)(N+1)2 P(n+1)N^2-P(n)(N+1)^2 =[P(n)+α1(2n+1)ε2+α3σg2]N2−P(n)(N+1)2 = [P(n)+ _1(2n+1) ^2+ _3 _g^2 ]N^2-P(n)(N+1)^2 =P(n)[N2−(N+1)2]+[α1(2n+1)ε2+α3σg2]N2 =P(n) [N^2-(N+1)^2 ]+ [ _1(2n+1) ^2+ _3 _g^2 ]N^2 =−P(n)(2N+1)+[α1(2n+1)ε2+α3σg2]N2. =-P(n)(2N+1)+ [ _1(2n+1) ^2+ _3 _g^2 ]N^2. (32) We evaluate each component in (32) separately. For the first term: −P(n)(2N+1)=−α1n2ε2(2N+1)−α3nfσ2(2N+1)−α3nσg2(2N+1).-P(n)(2N+1)=- _1n^2 ^2(2N+1)- _3n_fσ^2(2N+1)- _3n _g^2(2N+1). (33) For the second term: [α1(2n+1)ε2+α3σg2]N2=α1(2n+1)ε2N2+α3σg2N2. [ _1(2n+1) ^2+ _3 _g^2 ]N^2= _1(2n+1) ^2N^2+ _3 _g^2N^2. (34) Collecting α1ε2 _1 ^2 terms we get α1ε2[(2n+1)N2−n2(2N+1)] _1 ^2 [(2n+1)N^2-n^2(2N+1) ]. We use the factorization (2n+1)N2−n2(2N+1)=[(2n+1)N+n][N−n]=nf[(2n+1)N+n](2n+1)N^2-n^2(2N+1)= [(2n+1)N+n ] [N-n ]=n_f [(2n+1)N+n ], which follows from the difference-of-products identity with N−n=nfN-n=n_f. Collecting α3σg2 _3 _g^2 terms: α3σg2[N2−n(2N+1)]=α3σg2[nf2−n(n+1)], _3 _g^2 [N^2-n(2N+1) ]= _3 _g^2 [n_f^2-n(n+1) ], (35) where we expanded N2−n(2N+1)=(nf+n)2−2n(nf+n)−n=nf2+2nnf+n2−2nnf−2n2−n=nf2−n2−nN^2-n(2N+1)=(n_f+n)^2-2n(n_f+n)-n=n_f^2+2n_f+n^2-2n_f-2n^2-n=n_f^2-n^2-n. The remaining term is −α3nfσ2(2N+1)- _3n_fσ^2(2N+1). Substitute (33) – (35) back into (31) yields Eq. (30). ∎ B.3 Proof of Theorem 3 (First Annotation Threshold) Theorem 3. With η(s,a)η(s,a) in (28), the first annotation (n=0→1n=0→ 1) does not increase the local objective (29), i.e., δϕ(0)≤0δφ(0)≤ 0, if and only if ε2(s,a)≤η(s,a)((nf(s,a)+1)σ2(s,a)nf(s,a)−Δ(s,a)). ^2(s,a)≤η(s,a)\! ( (n_f(s,a)+1)σ^2(s,a)n_f(s,a)- (s,a) ). (36) Equality in (36) leaves the local objective unchanged, whereas strict inequality gives a strict decrease. In particular, if Δ(s,a)≥(nf(s,a)+1)σ2/nf(s,a) (s,a)≥(n_f(s,a)+1)σ^2/n_f(s,a), then δϕ(0)>0δφ(0)>0 for every (s,a) with ε(s,a)≠0 (s,a)≠ 0. Proof. Substituting n=0n=0 and N=nfN=n_f into Eq. (30): δϕ(0) δφ(0) =α1ε2nf⋅nf+α3σg2⋅nf2−α3nfσ2(2nf+1)nf2(nf+1)2 = _1 ^2n_f· n_f+ _3 _g^2· n_f^2- _3n_fσ^2(2n_f+1)n_f^2(n_f+1)^2 =nf[α1ε2nf+α3nfσg2−α3(2nf+1)σ2]nf2(nf+1)2 = n_f [ _1 ^2n_f+ _3n_f _g^2- _3(2n_f+1)σ^2 ]n_f^2(n_f+1)^2 =α1ε2nf+α3[nf(σ2+Δ)−(2nf+1)σ2]nf(nf+1)2 = _1 ^2n_f+ _3 [n_f(σ^2+ )-(2n_f+1)σ^2 ]n_f(n_f+1)^2 =α1ε2nf+α3[nfΔ−(nf+1)σ2]nf(nf+1)2. = _1 ^2n_f+ _3 [n_f -(n_f+1)σ^2 ]n_f(n_f+1)^2. (37) Because nf>0n_f>0 and α1>0 _1>0, the condition δϕ(0)≤0δφ(0)≤ 0 is equivalent to α1ε2nf _1 ^2n_f ≤α3[(nf+1)σ2−nfΔ], ≤ _3 [(n_f+1)σ^2-n_f ], ε2 ^2 ≤α3α1((nf+1)σ2nf−Δ)=η(s,a)((nf+1)σ2nf−Δ). ≤ _3 _1 ( (n_f+1)σ^2n_f- )=η(s,a) ( (n_f+1)σ^2n_f- ). The same equivalence holds with either equality or strict inequality throughout. When Δ≥(nf+1)σ2/nf ≥(n_f+1)σ^2/n_f and ε≠0 ≠ 0, the right-hand side is nonpositive while ε2>0 ^2>0, so (37) gives δϕ(0)>0δφ(0)>0. ∎ B.4 Proof of Theorem 4 (Four Regimes of Annotation Value) Lemma 3 (Continuous Critical Point n∗n^*). Treating n as a continuous variable, the derivative of ϕφ is: ϕ′(n)=(2α1ε2nf−α3σg2)n+α3nf(Δ−σ2)(nf+n)3.φ (n)= (2 _1 ^2n_f- _3 _g^2)\,n+ _3n_f( -σ^2)(n_f+n)^3. (38) If 2α1ε2nf≠α3σg22 _1 ^2n_f≠ _3 _g^2, the only possible critical point is n∗=α3nf(σ2−Δ)2α1ε2nf−α3σg2=ηnf(σ2−Δ)2ε2nf−ησg2.n^*= _3n_f(σ^2- )2 _1 ^2n_f- _3 _g^2= η\,n_f(σ^2- )2 ^2n_f-η\, _g^2. (39) It is an interior critical point exactly when n∗>0n^*>0. If 2α1ε2nf=α3σg22 _1 ^2n_f= _3 _g^2, there is no interior critical point unless α3(Δ−σ2)=0 _3( -σ^2)=0, in which case ϕφ is constant. Furthermore, ϕ(n)→α1ε2φ(n)→ _1 ^2 as n→∞n→∞. Proof. From Eq. (29), ϕ(n)=P(n)/N2φ(n)=P(n)/N^2 where P(n)=α1n2ε2+α3nfσ2+α3nσg2P(n)= _1n^2 ^2+ _3n_fσ^2+ _3n _g^2 and N=nf+nN=n_f+n. By the quotient rule: ϕ′(n) φ (n) =P′(n)N2−P(n)⋅2N4=P′(n)N−2P(n)N3, = P (n)N^2-P(n)· 2NN^4= P (n)N-2P(n)N^3, (40) where P′(n)=2α1nε2+α3σg2P (n)=2 _1n ^2+ _3 _g^2. Expanding the numerator: (2α1nε2+α3σg2)(nf+n)−2(α1n2ε2+α3nfσ2+α3nσg2) (2 _1n ^2+ _3 _g^2)(n_f+n)-2( _1n^2 ^2+ _3n_fσ^2+ _3n _g^2) =2α1nε2nf+2α1n2ε2+α3σg2nf+α3σg2n−2α1n2ε2−2α3nfσ2−2α3nσg2 =2 _1n ^2n_f+2 _1n^2 ^2+ _3 _g^2n_f+ _3 _g^2n-2 _1n^2 ^2-2 _3n_fσ^2-2 _3n _g^2 =2α1ε2nfn+α3nf(σg2−2σ2)−α3σg2n =2 _1 ^2n_f\,n+ _3n_f( _g^2-2σ^2)- _3 _g^2n =(2α1ε2nf−α3σg2)n+α3nf(Δ−σ2), =(2 _1 ^2n_f- _3 _g^2)\,n+ _3n_f( -σ^2), (41) where we used σg2−2σ2=Δ−σ2 _g^2-2σ^2= -σ^2. When its slope is nonzero, setting the numerator to zero yields Eq. (39), with an interior solution exactly when n∗>0n^*>0. When the slope is zero, the numerator is the constant α3nf(Δ−σ2) _3n_f( -σ^2), so the derivative either never vanishes or is identically zero. For the limit, divide numerator and denominator of ϕ(n)φ(n) by n2n^2: ϕ(n)=α1ε2+α3nfσ2/n2+α3σg2/n(nf/n+1)2→n→∞α1ε2.∎φ(n)= _1 ^2+ _3n_fσ^2/n^2+ _3 _g^2/n(n_f/n+1)^2 n→∞ _1 ^2. Define the slope and intercept of the numerator in Eq. (38) as: :=2α1ε2nf−α3σg2,:=α3nf(Δ−σ2). a:=2 _1 ^2n_f- _3 _g^2, b:= _3n_f( -σ^2). (42) Theorem 4 (Four Regimes of Annotation Value). In all cases, ϕ(n)→α1ε2φ(n)→ _1 ^2 as n→∞n→∞. When ==0 a= b=0, ϕφ is constant; otherwise, it falls into four regimes: (I) If ≥0 a≥ 0 and ≥0 b≥ 0, then ϕφ is increasing, so annotations are locally harmful. (I) If >0 a>0 and <0 b<0, then ϕφ decreases and then increases, with unique continuous minimizer n∗=ηnf(σ2−Δ)/(2ε2nf−ησg2)n^*=η n_f(σ^2- )/(2 ^2n_f-η _g^2). (I) If ≤0 a≤ 0 and ≤0 b≤ 0, then ϕφ is decreasing, so each additional annotation locally reduces the objective. (IV) If <0 a<0 and >0 b>0, then ϕφ first increases and then decreases, with unique continuous maximizer n¯=ηnf(Δ−σ2)/(ησg2−2ε2nf) n=η n_f( -σ^2)/(η _g^2-2 ^2n_f). In this regime, a strict improvement over no annotation is possible if and only if ε2<ησ2/nf ^2<ησ^2/n_f. Proof. The numerator of ϕ′(n)φ (n) is n+ an+ b, and the denominator (nf+n)3>0(n_f+n)^3>0 for all n≥0n≥ 0. Hence sign(ϕ′(n))=sign(n+)sign(φ (n))=sign( an+ b) for n>0n>0. If ==0 a= b=0, then ϕ′(n)=0φ (n)=0 for every n≥0n≥ 0, so ϕ(n)=ϕ(0)=α1ε2φ(n)=φ(0)= _1 ^2 throughout. When η=0η=0, we have α3=0 _3=0 and ϕ(n)=α1ε2n2/(nf+n)2φ(n)= _1 ^2n^2/(n_f+n)^2; thus ε≠0 ≠ 0 gives Regime (I), while ε=0 =0 gives the constant zero objective, regardless of Δ . For η>0η>0, equivalently α3>0 _3>0, we translate the four sign patterns into the source conditions in Table 1, excluding the constant case. Regime (I): ≥0 a≥ 0 and ≥0 b≥ 0 (not both zero). Then n+>0 an+ b>0 for all n>0n>0, so ϕ′(n)>0φ (n)>0. The condition ≥0 b≥ 0 is Δ≥σ2 ≥σ^2. The condition ≥0 a≥ 0 is 2α1ε2nf≥α3σg22 _1 ^2n_f≥ _3 _g^2, which gives ε2≥α3σg22α1nf=ησg22nf ^2≥ _3 _g^22 _1n_f= η _g^22n_f. Regime (I): >0 a>0 and <0 b<0. The affine function n+ an+ b starts negative at n=0n=0 and increases, crossing zero at n∗=−/>0n^*=- b/ a>0. For n<n∗n<n^*, ϕ′(n)<0φ (n)<0 (decreasing); for n>n∗n>n^*, ϕ′(n)>0φ (n)>0 (increasing). The condition <0 b<0 is Δ<σ2 <σ^2. The condition >0 a>0 gives ε2>ησg22nf ^2> η _g^22n_f. Regime (I): ≤0,≤0 a≤ 0, b≤ 0 (not both zero) gives n+≤0 an+ b≤ 0 for all n>0n>0, with strict inequality whenever at least one of , a, b is strictly negative. The conditions are Δ≤σ2 ≤σ^2 and ε2≤ησg2/(2nf) ^2≤η _g^2/(2n_f), with at least one inequality strict. In particular, Δ=σ2 =σ^2 is included when ε2<ησ2/nf ^2<ησ^2/n_f; equality in both conditions gives the constant case already treated. Regime (IV): The sign transition is reversed: >0 b>0 gives ϕ′(0+)>0φ (0^+)>0, and <0 a<0 forces a sign change at the maximizer n¯=−/>0 n=- b/ a>0 stated in the theorem. For the sub-case analysis, we examine ϕ(n)−ϕ(0)φ(n)-φ(0). The function increases up to n¯ n, then decreases toward α1ε2 _1 ^2. Sub-case (IVa): α1ε2<ϕ(0) _1 ^2<φ(0). Because limn→∞ϕ(n)<ϕ(0) _n→∞φ(n)<φ(0), there is a finite T>n¯T> n with ϕ(T)<ϕ(0)φ(T)<φ(0). The intermediate value theorem on [n¯,T][ n,T], together with ϕ(n¯)>ϕ(0)φ( n)>φ(0) and strict decrease after n¯ n, gives a unique break-even count nbe>n¯n_be> n satisfying ϕ(nbe)=ϕ(0)φ(n_be)=φ(0). Consequently, ϕ(n)<ϕ(0)φ(n)<φ(0) exactly when n>nben>n_be; under a finite capacity, this improvement is attainable only if such a count is feasible. Sub-case (IVb): α1ε2≥ϕ(0) _1 ^2≥φ(0). We show ϕ(n)≥ϕ(0)φ(n)≥φ(0) for all n≥0n≥ 0. Since ϕφ is increasing on (0,n¯)(0, n), we have ϕ(n)>ϕ(0)φ(n)>φ(0) for n∈(0,n¯]n∈(0, n]. On (n¯,∞)( n,∞), ϕφ is strictly decreasing toward α1ε2≥ϕ(0) _1 ^2≥φ(0). Thus ϕ(n)>α1ε2≥ϕ(0)φ(n)> _1 ^2≥φ(0) for every n>n¯n> n, proving the claim, including the boundary case α1ε2=ϕ(0) _1 ^2=φ(0). The sub-case condition α1ε2≶ϕ(0)=α3σ2/nf _1 ^2 φ(0)= _3σ^2/n_f translates to ε2≶ησ2/nf ^2 ησ^2/n_f. ∎ Integer counts in Regime (I). For the local problem with feasible counts n∈0,…,Un∈\0,…,U\, where U is a nonnegative integer, it suffices to compare ϕφ at min⌊n∗⌋,U \ n^* ,U\ and min⌈n∗⌉,U \ n^* ,U\. If n∗≤Un^*≤ U, monotonicity on each side of n∗n^* implies that every feasible integer has an objective value at least as large as that at ⌊n∗⌋ n^* or ⌈n∗⌉ n^* . If n∗>Un^*>U, ϕφ decreases throughout [0,U][0,U], so both capped candidates equal the optimum U. When the candidates coincide, including U=0U=0 or integer n∗n^*, only one evaluation is needed; if their objective values tie, either is optimal. B.5 Asymptotic Behavior and Bias Floor Corollary 1 (Diminishing Marginal Returns). In all regimes, the marginal effect of annotation vanishes asymptotically: |ϕ′(n)|=|n+|(nf+n)3=O(1n2)as n→∞.|φ (n)|= | a\,n+ b|(n_f+n)^3=O\! ( 1n^2 ) n→∞. (43) In Regime (I), annotations beyond n∗n^* increase ϕφ, with marginal cost of magnitude O(1/n2)O(1/n^2). In Regime (I), and in Regime (IV) beyond the maximizer n¯ n, annotations decrease ϕφ, with marginal benefit of magnitude O(1/n2)O(1/n^2). The discrete marginal change δϕ(n)=ϕ(n+1)−ϕ(n)δφ(n)=φ(n+1)-φ(n) also has magnitude O(1/n2)O(1/n^2). Proof. For n≥1n≥ 1, |n+|≤(||+||)n| an+ b|≤(| a|+| b|)n and (nf+n)3≥n3(n_f+n)^3≥ n^3, so |ϕ′(n)|≤(||+||)/n2|φ (n)|≤(| a|+| b|)/n^2. The signs follow from Theorem 4: ϕ′>0φ >0 after the minimum in Regime (I), whereas ϕ′<0φ <0 throughout Regime (I) and after the maximum in Regime (IV). For integer n≥1n≥ 1, the mean value theorem gives δϕ(n)=ϕ′(ξn)δφ(n)=φ ( _n) for some ξn∈(n,n+1) _n∈(n,n+1), yielding the same bound on its magnitude. ∎ Corollary 2 (Irreducible Bias Floor). Regardless of regime, limn→∞ϕ(n)=α1ε2 _n→∞φ(n)= _1 ^2. The asymptotic reduction relative to no annotation is ϕ(0)−α1ε2=α1nf[ησ2−nfε2].φ(0)- _1 ^2= _1n_f [η\,σ^2-n_f ^2 ]. (44) This quantity is positive if and only if ε2<ησ2nf ^2< η\,σ^2n_f, which is exactly the condition separating sub-cases (IVa) from (IVb). The condition holds throughout the nonconstant Regime (I), including the boundary Δ=σ2 =σ^2. In Regime (I), the asymptotic floor may exceed ϕ(0)φ(0) when ε is large; however, the local optimum ϕ(n∗)φ(n^*) always satisfies ϕ(n∗)<ϕ(0)φ(n^*)<φ(0) since ϕ′(0+)<0φ (0^+)<0 guarantees initial descent. Proof. The limit and the formula follow from Lemma 3. Regime (I) requires η>0η>0, because η=0η=0 gives either Regime (I) or the constant case. If Δ<σ2 <σ^2, then ε2≤ησg2/(2nf)<ησ2/nf ^2≤η _g^2/(2n_f)<ησ^2/n_f. If Δ=σ2 =σ^2, then =0 b=0 and the nonconstant Regime (I) requires <0 a<0, which gives ε2<ησ2/nf ^2<ησ^2/n_f directly. In the excluded constant case, ϕ(0)=α1ε2φ(0)= _1 ^2, so the asymptotic reduction is zero. For Regime (I): <0 b<0 implies ϕ′(0+)=/nf3<0φ (0^+)= b/n_f^3<0, so ϕφ is initially decreasing. Since n∗n^* is the unique minimum of ϕφ on (0,∞)(0,∞), continuity gives ϕ(n∗)<ϕ(ϵ)<ϕ(0)φ(n^*)<φ(ε)<φ(0) for sufficiently small ϵ>0ε>0. ∎ B.6 Cross-Action Coupling within a Context When multiple actions are annotated within the same context, the marginal value of an annotation also depends on how it changes the aggregate bias in J2J_2. We compute this correction to identify when it strengthens or weakens the local benefit derived above. Lemma 4 (Marginal change including J2J_2). Consider adding one annotation (from n to n+1n+1) for action a at context s. The total marginal change in the objective, including the bias correction term J2J_2, is: δJ(n)=δϕ(n)−δJ2(n),δ J(n)=δφ(n)-δ J_2(n), (45) where δϕ(n)δφ(n) is the local change from Lemma 2 and: δJ2(n)=d0(s)[2ℬs⋅πe(a|s)nfεN(N+1)+(πe(a|s)nfεN(N+1))2],δ J_2(n)=d_0(s) [2B_s· _e(a|s) n_f N(N+1)+ ( _e(a|s) n_f N(N+1) )^2 ], (46) with ℬs:=∑a′∈πe(a′|s)B(s,a′,)B_s:= _a _e(a |s)B(s,a ;n) being the current weighted bias accumulation, including default-model biases at pairs with N(s,a′)=0N(s,a )=0. Proof. The bias accumulation for context s changes from ℬsB_s to ℬs′=ℬs+πe(a|s)δB(s,a)B_s =B_s+ _e(a|s)\,δ B(s,a), where: δB(s,a) δ B(s,a) :=(n+1)εN+1−nεN=ε(n+1)N−n(N+1)N(N+1)=nfεN(N+1). := (n+1) N+1- n N= (n+1)N-n(N+1)N(N+1)= n_f N(N+1). (47) Therefore: δJ2(n) δ J_2(n) =d0(s)[(ℬs′)2−ℬs2]=d0(s)[2ℬs⋅πe(a|s)δB+(πe(a|s)δB)2]. =d_0(s) [(B_s )^2-B_s^2 ]=d_0(s) [2B_s· _e(a|s)\,δ B+ ( _e(a|s)\,δ B )^2 ]. (48) Since −J2-J_2 appears in the objective, the total change is δJ=δϕ−δJ2δ J=δφ-δ J_2. ∎ Remark 1 (Sign of δJ2δ J_2). The quadratic term in (46) is non-negative, but the linear term 2d0(s)ℬsπe(a|s)nfε/[N(N+1)]2d_0(s)B_s\, _e(a|s)\,n_f /[N(N+1)] has the sign of ℬs⋅εB_s· . Therefore δJ(n)δ J(n) may be either smaller or larger than δϕ(n)δφ(n) depending on whether the new bias correlates with or opposes the existing aggregate bias ℬsB_s. This is exactly why allocation decisions cannot be made independently across actions. Theorem 5 (Threshold including bias correction). Assume α3>0 _3>0. If the aggregate bias before the first annotation for action a is ℬs(0)=0B_s^(0)=0, then this annotation does not increase the objective (δJ(0)≤0δ J(0)≤ 0) if and only if ε2≤(nf+1)σ2nf−Δ. ^2\;≤\; (n_f+1)σ^2n_f- . (49) Equality in (49) gives δJ(0)=0δ J(0)=0, whereas strict inequality gives δJ(0)<0δ J(0)<0. When the right-hand side of (49) is positive, including J2J_2 multiplies the allowable squared bias from Theorem 3 by 1/η>11/η>1. For general ℬs(0)≠0B_s^(0)≠ 0, the threshold becomes α3ε2≤α3[(nf+1)σ2−nfΔ]nf+2d0(s)ℬs(0)πe(a|s)(nf+1)ε, _3\, ^2\;≤\; _3 [(n_f+1)σ^2-n_f ]n_f+2d_0(s)\,B_s^(0)\, _e(a|s)\,(n_f+1)\, , (50) which couples the allowable bias of action a to the existing aggregate bias of context s. Proof. The condition δJ(0)≤0δ J(0)≤ 0 is equivalent to δϕ(0)≤δJ2(0)δφ(0)≤δ J_2(0). At n=0n=0, N=nfN=n_f and the increment δB(s,a)=ε/(nf+1)δ B(s,a)= /(n_f+1) (Eq. 47). Substituting δϕ(0)δφ(0) from Eq. (37) and δJ2(0)δ J_2(0) from Eq. (48): α1ε2nf+α3(nfΔ−(nf+1)σ2)nf(nf+1)2≤d0(s) 2ℬs(0)πe(a|s)εnf+1+d0(s)πe(a|s)2ε2(nf+1)2. _1 ^2n_f+ _3(n_f -(n_f+1)σ^2)n_f(n_f+1)^2≤ d_0(s)\,2B_s^(0) _e(a|s)\, n_f+1+ d_0(s)\, _e(a|s)^2\, ^2(n_f+1)^2. (51) Multiplying both sides by (nf+1)2(n_f+1)^2 and rearranging, we collect ε2 ^2 terms: (α1−d0(s)πe(a|s)2)ε2≤α3((nf+1)σ2−nfΔ)nf+2d0(s)ℬs(0)πe(a|s)(nf+1)ε. ( _1-d_0(s) _e(a|s)^2 ) ^2≤ _3 ((n_f+1)σ^2-n_f )n_f+2d_0(s)\,B_s^(0)\, _e(a|s)\,(n_f+1)\, . (52) The key identity is: α1−d0(s)πe(a|s)2=d0(s)πe(a|s)2(1πb(a|s)−1)=α3. _1-d_0(s) _e(a|s)^2=d_0(s) _e(a|s)^2\! ( 1 _b(a|s)-1 )= _3. (53) Substitute Eq. (53) into LHS of Eq. (52) yields Eq. (50). Setting ℬs(0)=0B_s^(0)=0 and dividing by α3>0 _3>0 gives Eq. (49). All transformations preserve equality and strict inequality, proving the corresponding statements for δJ(0)=0δ J(0)=0 and δJ(0)<0δ J(0)<0. ∎ B.7 Extension to Arbitrary Context-Action Pairs In (2), each aggregate bias ℬsB_s depends only on allocations within context s. Thus the objective is additive across contexts: J()=∑s∈Js(s)J(n)= _s J_s(n_s), where s:=nk(s,a):a∈,k∈n_s:=\n_k(s,a):a ,\ k \ and JsJ_s contains that context’s terms. The shared budget in (3) nevertheless couples the feasible choices across contexts. The four regimes in Theorem 4 and the diminishing marginal effects in Corollary 1 describe the local objective ϕφ, which omits J2J_2. They do not directly characterize the coupled context objective JsJ_s. For a single annotation with other allocations held fixed, Theorem 5 gives the full first-annotation condition through the current aggregate bias. Joint allocation must therefore account for both within-context bias coupling and the shared budget, as in §6. B.8 The Case nf(s,a)=0n_f(s,a)=0 When nf(s,a)=0n_f(s,a)=0, the fitting data contain no observations for the pair (s,a)(s,a). This can occur even when πb(a|s)>0 _b(a|s)>0, so an empty fitting cell does not by itself violate common support. The formulas in Theorem 4 require nf>0n_f>0. We treat this case separately. B.8.1 πb(a|s)>0 _b(a|s)>0 but nf(s,a)=0n_f(s,a)=0 We retain the single-source setting and consider pairs with α1>0 _1>0; if α1=0 _1=0, then α3=0 _3=0 and the local objective is identically zero. When no annotations have been acquired, N(s,a)=0N(s,a)=0 and we use the fixed default r^+(s,a)=r0(s,a) r^+(s,a)=r_0(s,a). Then ε^r^+(s,a)|N=0=r0(s,a)−μr(s,a),Var(r^+(s,a))|N=0=0. _ r^+(s,a) |_N=0=r_0(s,a)- _r(s,a), _D( r^+(s,a)) |_N=0=0. (54) The baseline local objective is: ϕ0:=α1(μr(s,a)−r0(s,a))2. _0:= _1 ( _r(s,a)-r_0(s,a) )^2. (55) For n≥1n≥ 1, N=nN=n and the local objective (Eq. 29) becomes: ϕ(n)=α1n2ε2+α3nσg2n2=α1ε2+α3σg2n,n≥1.φ(n)= _1n^2 ^2+ _3n _g^2n^2= _1 ^2+ _3 _g^2n, n≥ 1. (56) Substituting nf=0n_f=0 into Eq. (42) gives =−α3σg2≤0 a=- _3 _g^2≤ 0 and =0 b=0. The derivative ϕ′(n)=−α3σg2/n2≤0φ (n)=- _3 _g^2/n^2≤ 0 shows that the local objective is nonincreasing for n≥1n≥ 1, with strict decrease exactly when α3σg2>0 _3 _g^2>0. Proposition 4 (Properties When nf=0n_f=0 and πb(a|s)>0 _b(a|s)>0). For nf(s,a)=0n_f(s,a)=0 and α1>0 _1>0, the local objective has the following properties: 1. First Annotation Threshold The transition from n=0n=0 to n=1n=1 satisfies: δϕ(0→1):=ϕ(1)−ϕ0=α1[ε2−(μr−r0)2]+α3σg2.δφ(0→ 1):=φ(1)- _0= _1 [ ^2-( _r-r_0)^2 ]+ _3 _g^2. (57) This is positive (i.e., the first annotation is locally harmful) if and only if ε2>(μr−r0)2−ησg2. ^2>( _r-r_0)^2-η\, _g^2. (58) Equality in (58) leaves the local objective unchanged, and reversing the strict inequality gives a strict decrease. For an exact default r0=μr_0= _r, the first annotation is locally harmful if and only if ε2+ησg2>0 ^2+η _g^2>0. Conversely, if the default is poor ((μr−r0)2( _r-r_0)^2 large), the first annotation can be beneficial even with high bias. 2. Nonincreasing objective for n≥1n≥ 1: The marginal benefit of the (n+1)(n+1)-th annotation is −δϕ(n)=α3σg2n(n+1)=O(1n2).-δφ(n)= _3 _g^2n(n+1)=O\! ( 1n^2 ). (59) The decrease is strict if α3σg2>0 _3 _g^2>0; otherwise, ϕ(n)=α1ε2φ(n)= _1 ^2 for every n≥1n≥ 1. 3. Bias is never diluted: The bias of the reward estimator is ε^r^+(s,a)=ε _ r^+(s,a)= for all n≥1n≥ 1, independent of the annotation count. Without factual data, there is no unbiased component to attenuate the annotation bias. 4. Irreducible floor: For n≥1n≥ 1, the local objective is bounded below by α1ε2 _1 ^2, which cannot be reduced by increasing n. A net improvement over the baseline (ϕ(n)<ϕ0φ(n)< _0 for some n≥1n≥ 1) requires: ε2<(μr−r0)2. ^2<( _r-r_0)^2. (60) That is, the annotation bias must be strictly smaller in magnitude than the default model’s bias. Proof. (1) From Eqs. (56) and (55): δϕ(0→1) δφ(0→ 1) =ϕ(1)−ϕ0 =φ(1)- _0 =[α1ε2+α3σg2]−α1(μr−r0)2 = [ _1 ^2+ _3 _g^2 ]- _1( _r-r_0)^2 =α1[ε2−(μr−r0)2]+α3σg2. = _1 [ ^2-( _r-r_0)^2 ]+ _3 _g^2. Because α1>0 _1>0, the condition δϕ(0→1)>0δφ(0→ 1)>0 is equivalent to Eq. (58), with equality or the reversed strict inequality corresponding to zero or negative change, respectively. Substituting r0=μr_0= _r gives the exact-default statement. (2) From Eq. (56), δϕ(n)=α3σg2(1/(n+1)−1/n)=−α3σg2/(n(n+1))≤0δφ(n)= _3 _g^2(1/(n+1)-1/n)=- _3 _g^2/(n(n+1))≤ 0. The denominator is positive for n≥1n≥ 1, so the decrease is strict exactly when α3σg2>0 _3 _g^2>0, and its magnitude is at most α3σg2/n2 _3 _g^2/n^2. If α3σg2=0 _3 _g^2=0, Eq. (56) gives the stated constant value. (3) When nf=0n_f=0, B(s,a)=nεn=εB(s,a)= n n= for all n≥1n≥ 1. (4) Equation (56) gives ϕ(n)≥α1ε2φ(n)≥ _1 ^2 for every n≥1n≥ 1, with limn→∞ϕ(n)=α1ε2 _n→∞φ(n)= _1 ^2. If ϕ(n)<ϕ0φ(n)< _0 for a feasible n≥1n≥ 1, then α1ε2<ϕ0=α1(μr−r0)2 _1 ^2< _0= _1( _r-r_0)^2; dividing by α1>0 _1>0 proves the necessary condition (60). ∎ B.8.2 πb(a|s)=0 _b(a|s)=0 and nf(s,a)=0n_f(s,a)=0 When πb(a|s)=0 _b(a|s)=0, neither the fitting sample nor the evaluation sample contains observations of action a at context s. If also πe(a|s)=0 _e(a|s)=0, the pair contributes nothing to the estimator or J, and the zero-weight convention gives α1(s,a)=α3(s,a)=0 _1(s,a)= _3(s,a)=0. If πe(a|s)>0 _e(a|s)>0, common support fails; at a context with d0(s)>0d_0(s)>0, the importance-weighted correction cannot remove the reward-model error for that action. The unbiasedness guarantee and MSE decomposition in Theorem 1 therefore do not generally apply. This does not imply infinite variance: with one context, πb(a1|s)=1 _b(a_1|s)=1, and πe(a2|s)=1 _e(a_2|s)=1 for a1≠a2a_1≠ a_2, the estimator in (1) reduces to r^+(s,a2) r^+(s,a_2), which has finite variance under the stated moment assumptions but may be biased. Appendix C Properties of the Objective Function This appendix establishes the four structural properties of J()J(n) claimed in Proposition 1 of the main text. Nonnegativity and boundedness hold for every valid instance; the remaining properties are established by counterexamples. We organize the proof into four parts, summarized below: (I) J is non-negative and bounded over ℱF (Proposition 5); (I) J is non-separable across actions within the same context (Proposition 6); (I) the continuous relaxation of J is neither convex nor concave (Proposition 7); (IV) J is neither submodular nor supermodular over annotation allocations (Corollary 3). C.1 Decomposition and Notation We use B(s,a):=B(s,a,)B(s,a):=B(s,a;n) and W(s,a):=W(s,a,)W(s,a):=W(s,a;n) as defined before (2), including the default-model case N(s,a)=0N(s,a)=0. The objective decomposes as J()=J1()−J2()+J3(),J(n)\;=\;J_1(n)\;-\;J_2(n)\;+\;J_3(n), where the three components are: J1() J_1(n) =∑s∑aα1(s,a)B(s,a)2, = _s _a _1(s,a)\,B(s,a)^2, J2() J_2(n) =∑sd0(s)ℬs()2, = _sd_0(s)\,B_s(n)^2, J3() J_3(n) =∑s∑aα3(s,a)W(s,a). = _s _a _3(s,a)W(s,a). For a fixed context-action pair (s,a)(s,a), we define: N:=N(s,a)=nf+∑knk, N\;:=\;N(s,a)=n_f+ _kn_k, nf:=nf(s,a), n_f\;:=\;n_f(s,a), P:=∑k=1Knkεgk(s,a), P\;:=\; _k=1^Kn_k\, _g_k(s,a), QD:=∑k=1KnkΔgk(s,a), Q_D\;:=\; _k=1^Kn_k\, _g_k(s,a), B(s,a)=P/N(N>0), B(s,a)=P/N (N>0), σ2:=σr2(s,a), σ^2\;:=\; _r^2(s,a), α1(s,a):=d0(s)πe(a|s)2πb(a|s), _1(s,a)\;:=\;d_0(s)\, _e(a|s)^2 _b(a|s), α3(s,a)=(1−πb(a|s))α1(s,a). _3(s,a)= (1- _b(a|s) ) _1(s,a). For N>0N>0, W(s,a)=σ2/N+QD/N2W(s,a)=σ^2/N+Q_D/N^2; for N=0N=0, we use B(s,a)=r0(s,a)−μr(s,a)B(s,a)=r_0(s,a)- _r(s,a) and W(s,a)=0W(s,a)=0. The coefficients use the zero-weight convention α1=α3=0 _1= _3=0 when πe(a|s)=0 _e(a|s)=0. The context-level bias accumulation is ℬs():=∑a∈πe(a|s)B(s,a).B_s(n)\;:=\; _a _e(a|s)\,B(s,a). We write Ek:=εgk(s,a)E_k:= _g_k(s,a) and Dk:=Δgk(s,a)D_k:= _g_k(s,a) when (s,a)(s,a) is clear from context. The shorthand njn_j denotes the annotation count nj(s,a)n_j(s,a) from source j for the pair under consideration. We note the following elementary sign properties: • α1(s,a)≥0 _1(s,a)≥ 0, with strict positivity exactly when d0(s)>0d_0(s)>0 and πe(a|s)>0 _e(a|s)>0 under common support; • α3(s,a)=α1(s,a)−d0(s)πe(a|s)2=(1−πb(a|s))α1(s,a)≥0 _3(s,a)= _1(s,a)-d_0(s) _e(a|s)^2= (1- _b(a|s) ) _1(s,a)≥ 0, with equality exactly when α1(s,a)=0 _1(s,a)=0 or πb(a|s)=1 _b(a|s)=1. C.2 First and Second-Order Derivatives We compute all partial derivatives with respect to the annotation counts nk:=nk(s,a)n_k:=n_k(s,a). Since J1J_1 and J3J_3 decompose over individual (s,a)(s,a) pairs while J2J_2 decomposes over contexts, the analysis is organized accordingly. At N(s,a)=0N(s,a)=0, finite annotation changes are evaluated using the default definitions rather than the rational derivative formulas below. Lemma 5 (First-order partial derivatives). For a fixed (s,a)(s,a) pair with N(s,a)>0N(s,a)>0 and annotation source k∈k : ∂J1(s,a)∂nk ∂ J_1^(s,a)∂ n_k =2α1P(EkN−P)N3, = 2 _1\,P\,(E_kN-P)N^3, (61) ∂J2(s)∂nk(s,a) ∂ J_2^(s)∂ n_k(s,a) =2d0(s)ℬsπe(a|s)EkN−PN2, =2\,d_0(s)\,B_s\, _e(a|s)\, E_kN-PN^2, (62) ∂J3(s,a)∂nk ∂ J_3^(s,a)∂ n_k =α3N3((Dk−σ2)N−2QD). = _3N^3 ((D_k-σ^2)\,N-2\,Q_D ). (63) Proof. Eq. (61). Write J1(s,a)=α1(P/N)2J_1^(s,a)= _1\,(P/N)^2. Noting ∂P∂nk=Ek ∂ P∂ n_k=E_k and ∂N∂nk=1 ∂ N∂ n_k=1, the chain rule gives ∂nk(PN)=EkN−PN2, ∂ n_k\! ( PN )= E_k\,N-PN^2, hence ∂J1(s,a)∂nk=2α1⋅PN⋅EkN−PN2 ∂ J_1^(s,a)∂ n_k=2 _1· PN· E_kN-PN^2, yielding (61). Eq. (62). Since ℬs=∑a′πe(a′|s)B(s,a′)B_s= _a _e(a |s)\,B(s,a ) and only B(s,a)B(s,a) depends on nk(s,a)n_k(s,a): ∂ℬs∂nk(s,a)=πe(a|s)EkN−PN2. _s∂ n_k(s,a)= _e(a|s)\, E_kN-PN^2. Then ∂J2(s)∂nk(s,a)=2d0(s)ℬs⋅∂ℬs∂nk(s,a) ∂ J_2^(s)∂ n_k(s,a)=2\,d_0(s)\,B_s· _s∂ n_k(s,a) gives (62). Eq. (63). Writing J3(s,a)=α3σ2N−1+α3QDN−2J_3^(s,a)= _3\,σ^2N^-1+ _3\,Q_D\,N^-2 and differentiating: ∂J3(s,a)∂nk=α3(−σ2N2+DkN−2QDN3)=α3N3((Dk−σ2)N−2QD).∎ ∂ J_3^(s,a)∂ n_k= _3\! (- σ^2N^2+ D_k\,N-2\,Q_DN^3 )= _3N^3 ((D_k-σ^2)N-2Q_D ). Lemma 6 (Hessian entries). For a fixed context s, the following second-order partial derivatives hold when every pair being differentiated has positive total count. (i) J1(s,a)J_1^(s,a): same pair, sources k,lk,l. ∂2J1(s,a)∂nk∂nl=2α1N4(EkElN2−2(Ek+El)PN+3P2). ∂^2J_1^(s,a)∂ n_k\,∂ n_l= 2 _1N^4 (E_kE_l\,N^2-2(E_k+E_l)\,P\,N+3P^2 ). (64) (i) J2(s)J_2^(s): same action a, sources k,lk,l. ∂2J2(s)∂nk(s,a)∂nl(s,a)=2d0(s)[πe(a|s)2(EkN−P)(ElN−P)N4+ℬsπe(a|s)(2P−(Ek+El)N)N3]. ∂^2J_2^(s)∂ n_k(s,a)\,∂ n_l(s,a)=2\,d_0(s)\! [ _e(a|s)^2\,(E_kN-P)(E_lN-P)N^4+ B_s\, _e(a|s)\,(2P-(E_k+E_l)N)N^3 ]\!. (65) (i) J2(s)J_2^(s): different actions a≠a′a≠ a , sources k,lk,l. ∂2J2(s)∂nk(s,a)∂nl(s,a′)=2d0(s)πe(a|s)πe(a′|s)(EkNa−Pa)(ElNa′−Pa′)Na2Na′2, ∂^2J_2^(s)∂ n_k(s,a)\,∂ n_l(s,a )= 2\,d_0(s)\, _e(a|s)\, _e(a |s)\,(E_kN_a-P_a)(E_lN_a -P_a )N_a^2\,N_a ^2, (66) where Na:=N(s,a)N_a:=N(s,a), Pa:=P(s,a)P_a:=P(s,a), etc. (iv) J3(s,a)J_3^(s,a): same pair, sources k,lk,l. ∂2J3(s,a)∂nk∂nl=2α3N4((σ2−Dk−Dl)N+3QD). ∂^2J_3^(s,a)∂ n_k\,∂ n_l= 2 _3N^4 ((σ^2-D_k-D_l)\,N+3\,Q_D ). (67) Proof. All four identities follow from applying the quotient rule to the first-order expressions in Lemma 5. We detail each computation below. Part (i). Let u:=P/Nu:=P/N so that J1(s,a)=α1u2J_1^(s,a)= _1u^2. From Lemma 5, ∂u∂nk=(Ek−u)/N ∂ u∂ n_k=(E_k-u)/N. Differentiating: ∂2(α1u2)∂nk∂nl ∂^2( _1u^2)∂ n_k\,∂ n_l =2α1(∂u∂nk∂u∂nl+u∂2u∂nk∂nl). =2 _1\! ( ∂ u∂ n_k\, ∂ u∂ n_l+u\, ∂^2u∂ n_k\,∂ n_l ). We compute ∂2u∂nk∂nl=∂nl(Ek−uN)=−∂u∂nlN−(Ek−u)N2=2u−Ek−ElN2. ∂^2u∂ n_k\,∂ n_l= ∂ n_l\! ( E_k-uN )= - ∂ u∂ n_l\,N-(E_k-u)N^2= 2u-E_k-E_lN^2. Substituting and collecting terms with u=P/Nu=P/N: ∂2J1(s,a)∂nk∂nl ∂^2J_1^(s,a)∂ n_k\,∂ n_l =2α1N2[(Ek−u)(El−u)+u(2u−Ek−El)] = 2 _1N^2\! [(E_k-u)(E_l-u)+u(2u-E_k-E_l) ] =2α1N2[EkEl−2(Ek+El)u+3u2], = 2 _1N^2\! [E_kE_l-2(E_k+E_l)u+3u^2 ], which yields (64) after substituting u=P/Nu=P/N. Part (i). Differentiating (62) with respect to nl(s,a)n_l(s,a): ∂2J2(s)∂nk(s,a)∂nl(s,a)=2d0(s)[∂ℬs∂nl⋅πe(a|s)EkN−PN2+ℬs⋅πe(a|s)∂nl(EkN−PN2)]. ∂^2J_2^(s)∂ n_k(s,a)\,∂ n_l(s,a)=2\,d_0(s)\! [ _s∂ n_l\!·\! _e(a|s) E_kN-PN^2+B_s\!·\! _e(a|s) ∂ n_l\! ( E_kN-PN^2 ) ]. Using ∂ℬs∂nl(s,a)=πe(a|s)ElN−PN2 _s∂ n_l(s,a)= _e(a|s) E_lN-PN^2 from Lemma 5 and ∂nl(EkN−PN2)=2P−(Ek+El)N3, ∂ n_l\! ( E_kN-PN^2 )= 2P-(E_k+E_l)NN^3, (computed via the quotient rule) yields (65). Part (i). For a≠a′a≠ a , since B(s,a)B(s,a) depends only on nk(s,a)k\n_k(s,a)\_k and B(s,a′)B(s,a ) depends only on nk(s,a′)k\n_k(s,a )\_k, the term ℬs⋅∂nl(s,a′)(⋯)B_s· ∂ n_l(s,a )(·s) does not contribute a cross-action second derivative from the same factor. Only the product of first derivatives remains: ∂2J2(s)∂nk(s,a)∂nl(s,a′)=2d0(s)∂ℬs∂nk(s,a)∂ℬs∂nl(s,a′), ∂^2J_2^(s)∂ n_k(s,a)\,∂ n_l(s,a )=2\,d_0(s)\, _s∂ n_k(s,a)\, _s∂ n_l(s,a ), giving (66). Part (iv). Let Rk:=(Dk−σ2)N−2QDR_k:=(D_k-σ^2)N-2Q_D so that ∂J3(s,a)∂nk=α3Rk/N3 ∂ J_3^(s,a)∂ n_k= _3R_k/N^3. Then ∂Rk∂nl=(Dk−σ2)−2Dl ∂ R_k∂ n_l=(D_k-σ^2)-2D_l, and the quotient rule gives: ∂nl(RkN3) ∂ n_l\! ( R_kN^3 ) =(Dk−σ2−2Dl)N−3RkN4. = (D_k-σ^2-2D_l)\,N-3R_kN^4. Expanding 3Rk=3(Dk−σ2)N−6QD3R_k=3(D_k-σ^2)N-6Q_D and simplifying: (Dk−σ2−2Dl)N−3(Dk−σ2)N+6QD=2(σ2−Dk−Dl)N+6QD.∎(D_k-σ^2-2D_l)N-3(D_k-σ^2)N+6Q_D=2(σ^2-D_k-D_l)N+6Q_D. Hessian matrices in compact form. For a fixed (s,a)(s,a), define the vectors =(E1,…,EK)⊤e=(E_1,…,E_K) , =(D1,…,DK)⊤d=(D_1,…,D_K) , and =(1,…,1)⊤∈ℝK1=(1,…,1) ^K. The Hessian matrices 1,3∈ℝK×KH_1,H_3 ^K× K with respect to (n1,…,nK)(n_1,…,n_K) for the given (s,a)(s,a) pair are: 1 _1 =2α1N4(N2⊤−2NP(⊤+⊤)+3P2 11⊤), = 2 _1N^4\! (N^2\,ee -2NP\,(e1 +1e )+3P^2\,11 ), 3 _3 =2α3N4((σ2N+3QD) 11⊤−N(⊤+⊤)). = 2 _3N^4\! ((σ^2N+3Q_D)\,11 -N\,(d1 +1d ) ). Both are sums of rank-one and rank-two matrices; their spectral properties are parameter-dependent and analyzed in §C.3. C.3 Structural Properties We now prove the structural claims in Proposition 1. Proposition 5 (Non-negativity and boundedness). For every feasible allocation ∈ℱn , 0≤J()≤Jmax<∞.0\;≤\;J(n)\;≤\;J_ <∞. Proof. Lower bound. For J1−J2J_1-J_2: fix any context s and define xa:=B(s,a)x_a:=B(s,a), wa:=πe(a|s)w_a:= _e(a|s), and ca:=πb(a|s)c_a:= _b(a|s). In the following display, action sums run over a with ca>0c_a>0; common support gives wa=0w_a=0 on the omitted actions, so their contributions are zero. By the Cauchy–Schwarz inequality applied with weights (ca)( c_a) and (wacaxa)( w_a c_a\,x_a): (∑awaxa)2⏟=ℬs2=(∑aca⋅waxaca)2≤(∑aca)(∑awa2caxa2)=∑awa2caxa2, ( _aw_a\,x_a )^2_ =B_s^2= ( _a c_a· w_a\,x_a c_a )^2≤ ( _ac_a )\! ( _a w_a^2c_a\,x_a^2 )= _a w_a^2c_a\,x_a^2, where we used ∑aca=∑aπb(a|s)=1 _ac_a= _a _b(a|s)=1. Multiplying both sides by d0(s)d_0(s) and summing over s yields J2()≤J1()J_2(n)≤ J_1(n), hence J1−J2≥0J_1-J_2≥ 0. For J3J_3, pairs with N(s,a)=0N(s,a)=0 have W(s,a)=0W(s,a)=0 and contribute zero. For a pair with N(s,a)>0N(s,a)>0, combining the two terms in W(s,a)W(s,a) gives W(s,a)=σr2(s,a)N(s,a)+QD(s,a)N(s,a)2=σr2(s,a)N(s,a)+QD(s,a)N(s,a)2,W(s,a)= _r^2(s,a)N(s,a)+ Q_D(s,a)N(s,a)^2= _r^2(s,a)\,N(s,a)+Q_D(s,a)N(s,a)^2, and the numerator expands as σr2(s,a)nf(s,a)+∑k=1Knk(s,a)[σr2(s,a)+Δgk(s,a)]≥0, _r^2(s,a)\,n_f(s,a)+ _k=1^Kn_k(s,a)\, [ _r^2(s,a)+ _g_k(s,a) ]≥ 0, since σr2(s,a)≥0 _r^2(s,a)≥ 0, nf(s,a),nk(s,a)≥0n_f(s,a),\,n_k(s,a)≥ 0, and σr2(s,a)+Δgk(s,a)=Var(gk,j|s,a)≥0 _r^2(s,a)+ _g_k(s,a)=Var(g_k,j|s,a)≥ 0 for every k. The denominator is positive, so W(s,a)≥0W(s,a)≥ 0; together with α3(s,a)≥0 _3(s,a)≥ 0, this shows that every J3J_3 summand is nonnegative and hence J3≥0J_3≥ 0. Therefore J()=(J1−J2)+J3≥0J(n)=(J_1-J_2)+J_3≥ 0. Upper bound. Each count nk(s,a)n_k(s,a) is a nonnegative integer bounded by NsN_s, so ℱF is finite and contains the zero allocation. Common support and the zero-weight convention make all coefficients α1 _1 and α3 _3 finite. For positive total counts, N(s,a)≥1N(s,a)≥ 1, so finite reward and annotation moments give finite B(s,a)B(s,a) and W(s,a)W(s,a); for zero counts, the fixed finite defaults give finite B(s,a)B(s,a) and W(s,a)=0W(s,a)=0. Thus J()J(n) is finite for every ∈ℱn , and Jmax:=max∈ℱJ()<∞J_ := _n J(n)<∞. ∎ Proposition 6 (Non-separability across actions). There exist valid instances with a single context s and ||≥2|A|≥ 2 for which no functions faa∈\f_a\_a satisfy J()=∑a∈fa(nk(s,a)k∈).J(n)= _a f_a\! (\n_k(s,a)\_k ). Proof. We first identify the cross-action coupling in the continuous relaxation, then verify non-separability on feasible integer allocations. Since J1J_1 and J3J_3 decompose over individual (s,a)(s,a) pairs, they contribute zero to the cross-action derivative. The only contribution comes from −J2-J_2. By Lemma 6(i): ∂2J∂nk(s,a)∂nl(s,a′)=−2d0(s)πe(a|s)πe(a′|s)(EkNa−Pa)(ElNa′−Pa′)Na2Na′2. ∂^2J∂ n_k(s,a)\,∂ n_l(s,a )=- 2\,d_0(s)\, _e(a|s)\, _e(a |s)\,(E_k\,N_a-P_a)(E_l\,N_a -P_a )N_a^2\,N_a ^2. (68) For pairs with nf(s,a),nf(s,a′)>0n_f(s,a),n_f(s,a )>0, at =n=0 we have Pa=Pa′=0P_a=P_a =0, giving ∂2J∂nk(s,a)∂nl(s,a′)|==−2d0(s)πe(a|s)πe(a′|s)EkElnf(s,a)nf(s,a′), ∂^2J∂ n_k(s,a)\,∂ n_l(s,a ) |_n=0=- 2\,d_0(s)\, _e(a|s)\, _e(a |s)\,E_k\,E_ln_f(s,a)\,n_f(s,a ), which is non-zero whenever d0(s)>0d_0(s)>0, πe(a|s),πe(a′|s)>0 _e(a|s), _e(a |s)>0, and Ek,El≠0E_k,E_l≠ 0. For integer allocations, we choose one context, two actions, one source, and πb(ai|s)=πe(ai|s)=1/2 _b(a_i|s)= _e(a_i|s)=1/2 for i=1,2i=1,2. We set nf(s,ai)=1n_f(s,a_i)=1, εg1(s,ai)=1 _g_1(s,a_i)=1, σr2(s,ai)=1 _r^2(s,a_i)=1, Δg1(s,ai)=0 _g_1(s,a_i)=0, c1=1c_1=1, and κ=2κ=2. Then Ns=2N_s=2 and each action has annotation capacity one, so (0,0)(0,0), (1,0)(1,0), (0,1)(0,1), and (1,1)(1,1) are feasible annotation-count vectors. Writing J(x,y)J(x,y) for the objective at counts x and y on the two actions, substitution into (2) gives J(0,0)=12,J(1,0)=J(0,1)=716,J(1,1)=14.J(0,0)= 12, J(1,0)=J(0,1)= 716, J(1,1)= 14. Consequently, J(1,1)−J(1,0)−J(0,1)+J(0,0)=−1/8J(1,1)-J(1,0)-J(0,1)+J(0,0)=-1/8. Any additive per-action decomposition would make this difference zero, proving the claim. ∎ Proposition 7 (Non-convexity and non-concavity). There exist valid instances for which the continuous relaxation of J()J(n) is neither convex nor concave over feasible allocations. Proof. We show non-convexity and non-concavity by exhibiting a feasible direction along which a diagonal entry of the Hessian of the continuous relaxation takes opposite signs at two configurations. We construct an instance with one context s, two actions =a1,a2A=\a_1,a_2\, a single annotation source (K=1K=1), and πb(a1|s)=πb(a2|s)=1/2 _b(a_1|s)= _b(a_2|s)=1/2. Set πe(a1|s)=1 _e(a_1|s)=1 and πe(a2|s)=0 _e(a_2|s)=0, and fix n1(s,a2)=0n_1(s,a_2)=0, so the only decision variable is n:=n1(s,a1)n:=n_1(s,a_1). Write E:=εg1(s,a1),D:=Δg1(s,a1),σ2:=σr2(s,a1),nf:=nf(s,a1),N:=nf+n.E:= _g_1(s,a_1), D:= _g_1(s,a_1), σ^2:= _r^2(s,a_1), n_f:=n_f(s,a_1), N:=n_f+n. We choose a positive integer nfn_f, set nf(s,a2)=2nfn_f(s,a_2)=2n_f, c1=1c_1=1, and κ=2nfκ=2n_f; then Ns=3nfN_s=3n_f and the feasible interval along this direction is 0≤n≤2nf0≤ n≤ 2n_f. Under this configuration, only (s,a1)(s,a_1) contributes to the bias-related terms, and ℬs()=πe(a1|s)B(s,a1)=B(s,a1)B_s(n)= _e(a_1|s)\,B(s,a_1)=B(s,a_1). Using the identity α1(s,a1)−d0(s)πe(a1|s)2=α3(s,a1) _1(s,a_1)-d_0(s) _e(a_1|s)^2= _3(s,a_1) (Eq. (53)), the contribution of (s,a1)(s,a_1) to J1−J2J_1-J_2 collapses into α3(s,a1)B(s,a1)2 _3(s,a_1)\,B(s,a_1)^2. Thus, along this feasible direction, J(n)=α3[n2E2N2+σ2N+nDN2],α3:=α3(s,a1)>0.J(n)= _3\! [ n^2E^2N^2+ σ^2N+ nDN^2 ], _3:= _3(s,a_1)>0. Specializing the Hessian formulas of Lemma 6(i) and (iv) to K=1K=1 (so that the mixed partial reduces to the second derivative), the diagonal entry of the Hessian is J′(n)=2α3N4[E2nf(nf−2n)+(σ2−2D)N+3nD].J (n)= 2 _3N^4\! [E^2\,n_f(n_f-2n)+(σ^2-2D)\,N+3nD ]. (69) Non-concavity. Evaluating (69) at n=0n=0 (so N=nfN=n_f): J′(0)=2α3nf4[E2nf2+(σ2−2D)nf]=2α3(E2nf+σ2−2D)nf3.J (0)= 2 _3n_f^4\! [E^2n_f^2+(σ^2-2D)n_f ]= 2 _3 (E^2n_f+σ^2-2D )n_f^3. For α3>0 _3>0 and parameters with E2nf+σ2−2D>0E^2n_f+σ^2-2D>0 (e.g. E≠0E≠ 0 and 0≤D≤σ2/20≤ D≤σ^2/2), J′(0)>0J (0)>0. By continuity, J′(n)>0J (n)>0 at interior points of the feasible interval sufficiently close to zero, so J is not concave. Non-convexity. At n=nfn=n_f (so N=2nfN=2n_f): J′(nf)=2α3(2nf)4[−E2nf2+2(σ2−2D)nf+3nfD]=α3(−E2nf+2σ2−D)8nf3.J (n_f)= 2 _3(2n_f)^4\! [-E^2n_f^2+2(σ^2-2D)n_f+3n_fD ]= _3 (-E^2n_f+2σ^2-D )8\,n_f^3. Choosing the bias with E2>(2σ2−D)/nfE^2>(2σ^2-D)/n_f makes J′(nf)<0J (n_f)<0, so the Hessian is not positive semidefinite; J is not convex. Both regimes coexist on a single instance: pick any nf≥1n_f≥ 1, σ2>0σ^2>0, D with 0≤D≤σ2/20≤ D≤σ^2/2, and an E satisfying E2>(2σ2−D)/nfE^2>(2σ^2-D)/n_f. Then J′(0)>0J (0)>0 and J′(nf)<0J (n_f)<0 simultaneously, certifying that the continuous relaxation of J is neither convex nor concave. ∎ Corollary 3 (Neither submodular nor supermodular). There exist valid instances for which J()J(n), viewed as a function on the integer lattice ℤ+||||KZ_+^|S||A|K, is neither submodular nor supermodular, with both properties violated by feasible allocations. Proof. We test the defining lattice inequality on feasible integer allocations. Submodularity requires J()+J()≥J(∧)+J(∨)J(x)+J(y)≥ J(x )+J(x ), where ∧ and ∨ denote coordinate-wise minimum and maximum; supermodularity requires the reverse inequality. For distinct coordinates i,ji,j with unit vectors i,je_i,e_j, we define the mixed finite difference δijJ():=J(+i+j)−J(+i)−J(+j)+J(). _ijJ(n):=J(n+e_i+e_j)-J(n+e_i)-J(n+e_j)+J(n). Taking =+ix=n+e_i and =+jy=n+e_j shows that submodularity requires δijJ()≤0 _ijJ(n)≤ 0, whereas supermodularity requires δijJ()≥0 _ijJ(n)≥ 0. We construct one instance violating both requirements, with one context s, three actions a1,a2,a3a_1,a_2,a_3, and one source. For each action, we set πb(ai|s)=πe(ai|s)=1/3 _b(a_i|s)= _e(a_i|s)=1/3, nf(s,ai)=1n_f(s,a_i)=1, σr2(s,ai)=1 _r^2(s,a_i)=1, and Δg1(s,ai)=0 _g_1(s,a_i)=0. We write εi:=εg1(s,ai) _i:= _g_1(s,a_i) and choose (ε1,ε2,ε3)=(1,1,−1)( _1, _2, _3)=(1,1,-1). These moments can be realized by independent rewards taking values 11 and 33 with equal probability, with each annotation distributed as an independent reward draw plus the corresponding bias. We set c1=1c_1=1 and κ=2κ=2, giving Ns=3N_s=3 and per-action capacities Ns−nf(s,ai)=2N_s-n_f(s,a_i)=2. Thus 0, ie_i, je_j, and i+je_i+e_j are feasible for every i≠ji≠ j, where ie_i now denotes one annotation for action aia_i. The terms J1J_1 and J3J_3 are sums of per-action functions, so their mixed finite differences vanish. At the zero allocation, all reward-model biases are zero; adding one annotation for action aia_i gives B(s,ai)=εi/2B(s,a_i)= _i/2. Consequently, ℬs()=0B_s(0)=0, ℬs(i)=εi/6B_s(e_i)= _i/6, and ℬs(i+j)=(εi+εj)/6B_s(e_i+e_j)=( _i+ _j)/6. Only −J2=−ℬs2-J_2=-B_s^2 contributes to the mixed difference, yielding δijJ()=−(εi+εj)2−εi2−εj236=−εiεj18. _ijJ(0)=- ( _i+ _j)^2- _i^2- _j^236=- _i _j18. Hence δ12J()=−1/18<0 _12J(0)=-1/18<0 violates supermodularity, while δ13J()=1/18>0 _13J(0)=1/18>0 violates submodularity on the same instance. The same violations persist with additional sources by setting their annotation counts to zero. ∎ Appendix D Analysis of the Majorization-Minimization Algorithm This appendix provides the theoretical analysis of the proposed M framework. Throughout this section, we use the notation established in §C.1. In particular, ℬs():=∑a∈πe(a|s)B(s,a)B_s(n):= _a _e(a|s)B(s,a) denotes the context-level bias accumulation, with B and W defined in (2) and its preceding text, including the default-model case N(s,a)=0N(s,a)=0. We write ℱF for the full feasible set defined by all constraints in (3), and ℱ0F_0 for the feasible set with the budget constraint removed. D.1 Pseudocode of the Algorithms Algorithm 1 retains the best feasible allocation found at each majorization-minimization (M) iteration, while Algorithm 2 generates candidates by local source search and dynamic programming (DP). Both algorithms use factual fitting counts, reward moments, source profiles, policy probabilities, default rewards, and costs from the allocation problem; these fixed inputs are suppressed in subroutine calls. The M coefficients are ω1(s,a)=α1(s,a) _1(s,a)= _1(s,a), ω3(s,a)=α3(s,a) _3(s,a)= _3(s,a), and ω2(t)(s,a)=−2d0(s)ℬs((t))πe(a|s) _2^(t)(s,a)=-2d_0(s)B_s(n^(t)) _e(a|s). The local search and DP tables use the complete penalized cost ψs,a(t)(,λ):=J~s,a(t)()+λ∑kckzk _s,a^(t)(z;λ):= J_s,a^(t)(z)+λ _kc_kz_k, where J~s,a(t) J_s,a^(t) is the summand defined in §6.2. For each total count m, the subproblem solver records the largest remaining positive swap gain δs,a(m,λ) _s,a(m,λ), with zero assigned when no improving swap exists. These residuals certify the approximation error even when the swap cap is reached (Proposition 9). All ties in source selection, swaps, DP, and candidate ordering use a fixed index order, and the outer update retains the current allocation unless the surrogate strictly improves. Algorithm 1 Majorization-minimization (M) allocation with feasible-candidate retention 1: Fixed problem inputs above, budget κ, feasible (0)n^(0) (default 0), iteration limits Tmax,Tswap≥1T_ ,T_swap≥ 1, tolerances ϵ≥0ε≥ 0, ϵλ>0 _λ>0, initial multiplier λ0>0 _0>0. 2: Feasible allocation with objective no larger than J((0))J(n^(0)). 3: for t=0,1,…,Tmax−1t=0,1,…,T_ -1 do 4: Compute M coefficients (t) ω^(t) from (t)n^(t). 5: best←(t)n_best ^(t); t←∅Q_t← . 6: (0,0)←DP(0,(t),Tswap)(n_0, δ_0)← DP(0, ω^(t),T_swap). 7: If C(0)≤κC(n_0)≤κ, add (0,0,0)(0,n_0, δ_0) to tQ_t. 8: λlow←0 _low← 0; λhigh←λ0 _high← _0. 9: (high,high)←DP(λhigh,(t),Tswap)(n_high, δ_high)← DP( _high, ω^(t),T_swap). 10: while C(high)>κC(n_high)>κ do 11: λlow←λhigh _low← _high; λhigh←2λhigh _high← 2 _high. 12: (high,high)←DP(λhigh,(t),Tswap)(n_high, δ_high)← DP( _high, ω^(t),T_swap). 13: end while 14: Add (λhigh,high,high)( _high,n_high, δ_high) to tQ_t. 15: while λhigh−λlow>ϵλ _high- _low> _λ do 16: λmid←(λlow+λhigh)/2 _mid←( _low+ _high)/2. 17: (′,′)←DP(λmid,(t),Tswap)(n , δ )← DP( _mid, ω^(t),T_swap). 18: if C(′)>κC(n )>κ then 19: λlow←λmid _low← _mid. 20: else 21: λhigh←λmid _high← _mid. 22: Add (λmid,′,′)( _mid,n , δ ) to tQ_t. 23: end if 24: end while 25: for each (λ,′,′)∈t(λ,n , δ ) _t do 26: if J~(′,(t))<J~(best,(t)) J(n ;n^(t))< J(n_best;n^(t)) then 27: best←′n_best . 28: end if 29: end for 30: (t+1)←bestn^(t+1) _best. 31: if (t+1)=(t)n^(t+1)=n^(t) or J((t))−J((t+1))≤ϵJ(n^(t))-J(n^(t+1))≤ε then 32: break 33: end if 34: end for 35: return (t+1)n^(t+1) Algorithm 2 Capped source search and dynamic programming (DP) 1: Fixed problem inputs, multiplier λ≥0λ≥ 0, M coefficients (t) ω^(t), swap cap Tswap≥1T_swap≥ 1. 2: Capacity-feasible allocation ∈ℱ0n _0 and table of residual swap gains δ. 3: for each context s∈s do 4: for each action a∈a do 5: Ms,a←Ns−nf(s,a)M_s,a← N_s-n_f(s,a). 6: for m=0,…,Ms,am=0,…,M_s,a do 7: Initialize z with m annotations from the cheapest source. 8: if m>0m>0 and K>1K>1 then 9: for i=1,…,Tswapi=1,…,T_swap do 10: Choose (u,v)(u,v), u≠vu≠ v, zu≥1z_u≥ 1, maximizing g=ψs,a(t)(,λ)−ψs,a(t)(+v−u,λ)g= _s,a^(t)(z;λ)- _s,a^(t)(z+e_v-e_u;λ). 11: If g≤0g≤ 0, break. 12: ←+v−uz +e_v-e_u. 13: end for 14: end if 15: Store s,a♯[m]←n _s,a[m] and Hs,a♯[m]←ψs,a(t)(,λ)H _s,a[m]← _s,a^(t)(z;λ). 16: Store δs,a(m,λ) _s,a(m,λ) as the largest remaining positive swap gain (zero if none). 17: end for 18: end for 19: Order actions as a1,…,a||a_1,…,a_|A|; set D0(0)=0D_0(0)=0 and D0(w)=∞D_0(w)=∞ for w>0w>0. 20: for j=1,…,||j=1,…,|A| do 21: for w=0,…,Nsw=0,…,N_s do 22: Dj(w)←min0≤m≤minw,Ms,ajDj−1(w−m)+Hs,aj♯[m]D_j(w)← _0≤ m≤ \w,M_s,a_j\\D_j-1(w-m)+H _s,a_j[m]\. 23: Store a minimizing count mj(w)m_j(w). 24: end for 25: end for 26: w⋆∈argmin0≤w≤NsD||(w)w ∈ _0≤ w≤ N_sD_|A|(w); set w←w⋆w← w . 27: for j=||,…,1j=|A|,…,1 do 28: m←mj(w)m← m_j(w); s,aj←s,aj♯[m]n_s,a_j _s,a_j[m]; w←w−mw← w-m. 29: end for 30: end for 31: return ,n, δ. D.2 Surrogate Construction and Majorization Property The M framework replaces the non-convex objective J()J(n) with a locally tight upper bound. To remove the cross-action coupling, we majorize −J2()=−∑sd0(s)ℬs()2-J_2(n)=- _sd_0(s)\,B_s(n)^2 while retaining J1J_1 and J3J_3. We apply the tangent majorant of the concave scalar function h(x)=−x2h(x)=-x^2 at x=ℬs((t))x=B_s(n^(t)), giving an expression affine in ℬs()B_s(n). Lemma 7 (Valid Majorization). For any fixed feasible allocation (t)n^(t), the full surrogate J~full(,(t)) J_full(n;\,n^(t)) defined in Proposition 2 of §6.1 satisfies: (i) (Upper bound) J~full(,(t))≥J() J_full(n;\,n^(t))≥ J(n) for all ∈ℱn . (i) (Tangency) J~full((t),(t))=J((t)) J_full(n^(t);n^(t))=J(n^(t)). Moreover, the majorization gap admits the closed-form expression: J~full(,(t))−J()=∑s∈d0(s)(ℬs()−ℬs((t)))2. J_full(n;\,n^(t))-J(n)= _s d_0(s) (B_s(n)-B_s(n^(t)) )^2. (70) Proof. We fix (t)∈ℱn^(t) and any ∈ℱn . Because h(x)=−x2h(x)=-x^2 is concave, its tangent at any x0∈ℝx_0 gives a global upper bound: −x2≤−x02−2x0(x−x0)=x02−2x0x,∀x∈ℝ,-x^2\;≤\;-x_0^2-2x_0(x-x_0)\;=\;x_0^2-2x_0\,x, ∀\,x , with equality if and only if x=x0x=x_0. Substituting x=ℬs()x=B_s(n) and x0=ℬs((t))x_0=B_s(n^(t)), multiplying by the nonnegative weights d0(s)d_0(s), and summing over contexts gives −∑sd0(s)ℬs()2≤∑sd0(s)[ℬs((t))2−2ℬs((t))ℬs()].- _sd_0(s)\,B_s(n)^2\;≤\; _sd_0(s) [B_s(n^(t))^2-2\,B_s(n^(t))\,B_s(n) ]. The full surrogate (including the constant term) is: J~full(,(t))=J1()+∑sd0(s)[ℬs((t))2−2ℬs((t))ℬs()]+J3(). J_full(n;\,n^(t))=J_1(n)+ _sd_0(s) [B_s(n^(t))^2-2\,B_s(n^(t))\,B_s(n) ]+J_3(n). (71) Property (i) follows from −J2()≤J~full(,(t))−J1()−J3()-J_2(n)≤ J_full(n;\,n^(t))-J_1(n)-J_3(n). At =(t)n=n^(t), the summed linearized term in (71) equals ∑sd0(s)[(ℬs(t))2−2(ℬs(t))2]=−∑sd0(s)(ℬs(t))2=−J2((t)). _sd_0(s) [(B_s^(t))^2-2(B_s^(t))^2 ]=- _sd_0(s)(B_s^(t))^2=-J_2(n^(t)). Substitution into (71) gives J~full((t),(t))=J1((t))−J2((t))+J3((t))=J((t)) J_full(n^(t);n^(t))=J_1(n^(t))-J_2(n^(t))+J_3(n^(t))=J(n^(t)), proving property (i). For the gap formula, we compute: J~full(,(t))−J() J_full(n;\,n^(t))-J(n) =∑sd0(s)[ℬs((t))2−2ℬs((t))ℬs()+ℬs()2] = _sd_0(s) [B_s(n^(t))^2-2B_s(n^(t))B_s(n)+B_s(n)^2 ] =∑sd0(s)(ℬs()−ℬs((t)))2. = _sd_0(s) (B_s(n)-B_s(n^(t)) )^2. The optimization surrogate in (8) satisfies J~(,(t))=J~full(,(t))−J2((t)). J(n;n^(t))= J_full(n;n^(t))-J_2(n^(t)). Because J2((t))J_2(n^(t)) is independent of n, both surrogates have the same minimizers and give the same comparisons between allocations at fixed t. At the current allocation, however, J~((t),(t))=J((t))−J2((t)) J(n^(t);n^(t))=J(n^(t))-J_2(n^(t)). ∎ Proposition 8 (Monotone Descent under Surrogate-Improving Updates). Suppose at every iteration t≥0t≥ 0 the update (t+1)∈ℱn^(t+1) satisfies the surrogate-improvement condition J~((t+1),(t))≤J~((t),(t)). J\! (n^(t+1);\,n^(t) )\;≤\; J\! (n^(t);\,n^(t) ). (72) Then the original objective is monotonically non-increasing, J((t+1))≤J((t)),∀t≥0,J\! (n^(t+1) )\;≤\;J\! (n^(t) ), ∀\,t≥ 0, and the sequence J((t))\J(n^(t))\ converges. The fallback rule (t+1)←(t)n^(t+1) ^(t) used in Algorithm 1 ensures (72) regardless of how accurately the inner Lagrangian subproblem is solved; in particular, exact surrogate minimization is not required for descent of J. Proof. At fixed t, adding J2((t))J_2(n^(t)) to both sides of (72) gives the same improvement inequality for J~full J_full. Combining this inequality with the upper bound and tangency in Lemma 7 yields J((t+1)) J(n^(t+1)) ≤J~full((t+1),(t)) ≤ J_full(n^(t+1);n^(t)) ≤J~full((t),(t)) ≤ J_full(n^(t);n^(t)) =J((t)). =J(n^(t)). The fallback update satisfies (72) with equality. Proposition 5 gives J≥0J≥ 0, so the non-increasing objective sequence converges. ∎ Remark 2 (Reconciliation with Theorem 6). Proposition 8 only certifies monotonic descent of J along the iterates produced by Algorithm 1. It is independent of the suboptimality of (t+1)n^(t+1) relative to the exact constrained minimizer ^(t+1)=argminℱJ~(⋅,(t)) n^(t+1)= _F J(·;n^(t)). Theorem 6 subsequently bounds the gap to the global minimizer ∗n^* of J, and that bound naturally incorporates Inner-loop suboptimality (Proposition 10). The two results therefore play complementary roles: Proposition 8 guarantees algorithmic stability, while Theorem 6 quantifies how close each iterate may be to a global optimum. D.3 Local Source Search and Exact Count Aggregation At a fixed multiplier λ, separability allows us to search source mixtures independently and then aggregate their costs across actions. We bound the local-search error before propagating it through the exact DP aggregation. Lemma 8 (Separability of the Surrogate). The surrogate objective J~(,(t)) J(n;\,n^(t)) decomposes as: J~(,(t))=∑s∈∑a∈ϕs,a(t)(nk(s,a)k=1K). J(n;\,n^(t))= _s _a _s,a^(t)\! (\n_k(s,a)\_k=1^K ). Here ϕs,a(t)=J~s,a(t) _s,a^(t)= J_s,a^(t) is the local summand from §6.2 and depends only on the annotation counts for (s,a)(s,a). Proof. The terms J1J_1 and J3J_3 are already sums over individual (s,a)(s,a) pairs. The linearized −J2-J_2 contribution to the surrogate is: −2∑sd0(s)ℬs((t))∑aπe(a|s)B(s,a)=∑s∑aω2(t)(s,a)B(s,a),-2 _sd_0(s)\,B_s(n^(t))\! _a _e(a|s)\,B(s,a)= _s _a _2^(t)(s,a)\,B(s,a), where ω2(t)(s,a)=−2d0(s)ℬs((t))πe(a|s) _2^(t)(s,a)=-2\,d_0(s)\,B_s(n^(t))\, _e(a|s) is a constant with respect to n. Because each B(s,a)B(s,a) depends only on nk(s,a)k\n_k(s,a)\_k, the optimization surrogate J~ J is separable. ∎ Lemma 9 (Convexity of the Local Cost for Fixed Total Count). Fix an M iteration t, a pair (s,a)(s,a), a multiplier λ≥0λ≥ 0, and a total count m with N0:=nf(s,a)+m>0N_0:=n_f(s,a)+m>0. Holding N0N_0 constant, the complete local cost is ψs,a(t)(K,λ) _s,a^(t)(n_K;λ) =ω1N02(∑knkEk)2+ω2(t)N0∑knkEk = _1N_0^2 ( _kn_kE_k )^2+ _2^(t)N_0 _kn_kE_k (73) +ω3(σr2(s,a)N0+∑knkDkN02)+λ∑kcknk, + _3 ( _r^2(s,a)N_0+ _kn_kD_kN_0^2 )+λ _kc_kn_k, and is convex in K:=(n1,…,nK)⊤n_K:=(n_1,…,n_K) on the simplex K≥, 1⊤K=m\n_K 0,\ 1 n_K=m\. The coefficients ω1=α1(s,a) _1= _1(s,a), ω3=α3(s,a) _3= _3(s,a), and ω2(t)=−2d0(s)ℬs((t))πe(a|s) _2^(t)=-2d_0(s)B_s(n^(t)) _e(a|s) are fixed during this search. Proof. The Hessian of ψ with respect to Kn_K is ψ=2ω1N02⊤,=(E1,…,EK)⊤.H_ψ= 2 _1N_0^2\,e\,e , =(E_1,…,E_K) . For every direction ∈ℝKv ^K, ⊤ψ=2ω1(⊤)2/N02≥0v H_ψv=2 _1(e v)^2/N_0^2≥ 0 because ω1=α1(s,a)≥0 _1= _1(s,a)≥ 0. Thus the quadratic extension with fixed denominator is convex, as is its restriction to the simplex. Strict convexity is not required and need not hold because the Hessian has rank at most one. ∎ The term ω3σr2(s,a)/N0 _3 _r^2(s,a)/N_0 is constant across source mixtures at fixed m, but varies across counts and must be retained in Hs,a♯(m,λ)H _s,a(m,λ). For m=0m=0, the only source vector is 0, so Algorithm 2 stores its complete local cost without a swap search. If also nf(s,a)=0n_f(s,a)=0, that cost is ω1(r0−μr)2+ω2(t)(r0−μr) _1(r_0- _r)^2+ _2^(t)(r_0- _r), using the default bias and zero reward-model variance. Proposition 9 (Pairwise-Exchange Termination and Approximation Error). Fix t, (s,a)(s,a), m≥1m≥ 1, and λ≥0λ≥ 0. The source search in Algorithm 2 accepts at most minTswap,(m+K−1K−1)−1 \T_swap, m+K-1K-1-1\ swaps. For its output ♯n , let Hs,a♯(m,λ):=ψs,a(t)(♯,λ)H _s,a(m,λ):= _s,a^(t)(n ;λ) and define the residual gain δs,a(m,λ):=maxu,v∈nu♯≥1[ψs,a(t)(♯,λ)−ψs,a(t)(♯+v−u,λ)]+, _s,a(m,λ):= _ subarraycu,v \\ n_u ≥ 1 subarray [ _s,a^(t)(n ;λ)- _s,a^(t)(n +e_v-e_u;λ) ]_+, where [x]+:=maxx,0[x]_+:= \x,0\ and allowing u=vu=v includes a zero-gain move when K=1K=1. Relative to the exact fixed-count minimum Hs,a(t,λ)(m)H_s,a^(t,λ)(m), the output satisfies 0 0 ≤Hs,a♯(m,λ)−Hs,a(t,λ)(m)≤ηs,a(m)+mδs,a(m,λ), ≤ H _s,a(m,λ)-H_s,a^(t,λ)(m)≤ _s,a(m)+m\, _s,a(m,λ), (74) ηs,a(m) _s,a(m) :=α1(s,a)mΔEs,a 2(nf(s,a)+m)2,ΔEs,a:=maxkEk−minkEk. := _1(s,a)m E_s,a^\,2(n_f(s,a)+m)^2, E_s,a:= _kE_k- _kE_k. The output is swap-local if and only if δs,a(m,λ)=0 _s,a(m,λ)=0. With no swap cap, strict descent reaches such an output after at most (m+K−1K−1)−1 m+K-1K-1-1 accepted swaps. For m=0m=0, the local gap is zero, and we set ηs,a(0)=δs,a(0,λ)=0 _s,a(0)= _s,a(0,λ)=0. When nf(s,a)>0n_f(s,a)>0, ηs,a(m)≤α1(s,a)ΔEs,a 2/[4nf(s,a)] _s,a(m)≤ _1(s,a) E_s,a^\,2/[4n_f(s,a)] for every m. Proof. Finite termination. The integer simplex contains (m+K−1K−1) m+K-1K-1 configurations. Each accepted swap strictly decreases ψs,a(t)(⋅,λ) _s,a^(t)(·;λ), so it cannot revisit a configuration. Including the initial configuration gives at most (m+K−1K−1)−1 m+K-1K-1-1 accepted swaps, and the cap imposes the additional limit TswapT_swap. Without a cap, the search stops only when there is no positive swap gain; this is precisely δs,a(m,λ)=0 _s,a(m,λ)=0. For K=1K=1 there are no swaps, and the sole source mixture is optimal. Approximation error. With m≥1m≥ 1, the denominator N0=nf(s,a)+mN_0=n_f(s,a)+m is positive even if the factual count is zero. We write ψ(K)=ω1(⊤K)2/N02+⊤K+Cψ(n_K)= _1(e n_K)^2/N_0^2+L n_K+C, where =(E1,…,EK)⊤e=(E_1,…,E_K) and ,CL,C collect the fixed-count linear and constant terms in (73). Its Hessian is =2ω1⊤/N02⪰0H=2 _1ee /N_0^2 0. For any feasible swap u,v=v−ud_u,v=e_v-e_u, the residual definition and the exact quadratic expansion give −∇ψ(♯)⊤u,v≤δs,a(m,λ)+12u,v⊤u,v=δs,a(m,λ)+ω1(Ev−Eu)2N02.-∇ψ(n )^\! d_u,v≤ _s,a(m,λ)+ 12d_u,v Hd_u,v= _s,a(m,λ)+ _1(E_v-E_u)^2N_0^2. (75) Let ∗z^* be a global minimizer on the same integer simplex. Moving units from coordinates with nu♯>zu∗n_u >z_u^* to coordinates with nv♯<zv∗n_v <z_v^* gives ∗−♯=∑u,vquvu,vz^*-n = _u,vq_uvd_u,v, where quvq_uv are nonnegative integers and every donor has nu♯≥1n_u ≥ 1. The total moved mass is ∑u,vquv=12‖∗−♯‖1≤m _u,vq_uv= 12\|z^*-n \|_1≤ m. Convexity and (75) therefore yield ψ(♯)−ψ(∗) ψ(n )-ψ(z^*) ≤−∇ψ(♯)⊤(∗−♯) ≤-∇ψ(n ) (z^*-n ) ≤∑u,vquv(δs,a(m,λ)+ω1(Ev−Eu)2N02) ≤ _u,vq_uv ( _s,a(m,λ)+ _1(E_v-E_u)^2N_0^2 ) ≤mδs,a(m,λ)+ω1mΔEs,a 2N02. ≤ m\, _s,a(m,λ)+ _1m E_s,a^\,2N_0^2. The lower bound follows because ♯n is a feasible source mixture. Substituting ω1=α1(s,a) _1= _1(s,a) proves (74). For m=0m=0, the simplex is the singleton \0\, so the exact and stored costs coincide. Finally, (nf+m)2≥4nfm(n_f+m)^2≥ 4n_fm gives the uniform bound when nf>0n_f>0. The count-specific bound remains valid for nf=0n_f=0 and m≥1m≥ 1, where ηs,a(m)=α1(s,a)ΔEs,a 2/m _s,a(m)= _1(s,a) E_s,a^\,2/m. ∎ D.4 Lagrangian Relaxation Analysis The global budget constraint ∑s,a,kcknk(s,a)≤κ _s,a,kc_k\,n_k(s,a)≤κ couples the subproblems across contexts. We relax it via a Lagrange multiplier λ≥0λ≥ 0, yielding the dual function: q(λ)=min∈ℱ0J~(,(t))+λ(∑s,a,kcknk(s,a)−κ).q(λ)= _n _0 \ J(n;\,n^(t))+λ ( _s,a,kc_k\,n_k(s,a)-κ ) \. By Lemma 8, the Lagrangian problem decomposes over contexts. Algorithm 2 solves the count aggregation exactly for its supplied H♯H tables; the local approximation errors determine its gap to the exact Lagrangian minimum. The multiplier search always produces a feasible candidate in exact arithmetic. Indeed, ℱ0F_0 is finite, 0 is represented in every set of DP tables, and cmin:=minkck>0c_ := _kc_k>0. For fixed t, every nonzero allocation has cost at least cminc_ , so any λ>J~(,(t))−min∈ℱ0J~(,(t))cminλ> J(0;n^(t))- _n _0 J(n;n^(t))c_ makes the zero allocation strictly better than every nonzero allocation in the penalized objective. Thus doubling eventually returns 0, or terminates earlier at another budget-feasible candidate. Subsequent bisection is a finite candidate search, without a monotonicity guarantee for the costs returned by approximate local solves. Proposition 10 (Inner-loop suboptimality). Fix t and let ^(t+1)∈argmin∈ℱJ~(,(t)) n^(t+1)∈ _n J(n;n^(t)). Choose any recorded feasible trial (λ(t),cand(t),(t))∈t(λ^(t),n_cand^(t), δ^(t)) _t from Algorithm 1. To bound the aggregate local-search error, define EGreedy(t):=∑s,amax0≤m≤Ms,aηs,a(m)+mδs,a(m,λ(t)),E_Greedy^(t):= _s,a _0≤ m≤ M_s,a \ _s,a(m)+m\, _s,a(m,λ^(t)) \, where the maxima are over integer counts and Ms,a=Ns−nf(s,a)M_s,a=N_s-n_f(s,a). The actual outer update, including the current-allocation fallback, satisfies 0≤ΔLag(t) 0≤ _Lag^(t) :=J~((t+1),(t))−J~(^(t+1),(t)) := J(n^(t+1);n^(t))- J( n^(t+1);n^(t)) (76) ≤λ(t)(κ−C(cand(t)))+EGreedy(t). ≤λ^(t) (κ-C(n_cand^(t)) )+E_Greedy^(t). If all local residuals in that trial vanish and all factual counts are positive, then EGreedy(t)≤∑s,aα1(s,a)ΔEs,a 2/[4nf(s,a)]E_Greedy^(t)≤ _s,a _1(s,a) E_s,a^\,2/[4n_f(s,a)]. Proof. Feasibility of (t+1)n^(t+1) and optimality of ^(t+1) n^(t+1) give ΔLag(t)≥0 _Lag^(t)≥ 0. For the upper bound, fix the selected trial multiplier λ=λ(t)λ=λ^(t) and write L(,λ):=J~(,(t))+λC()L(n;λ):= J(n;n^(t))+λ C(n). First, Dj(w)D_j(w) in Algorithm 2 is the minimum stored cost for exactly w annotations across the first j actions. The initialization gives this interpretation for j=0j=0. For stage j, any feasible assignment uses some m≤minw,Ms,ajm≤ \w,M_s,a_j\ on action aja_j, leaving w−mw-m annotations for the first j−1j-1 actions. Minimizing over these choices proves the interpretation inductively and supplies valid backtracking counts. Selecting the best w≤Nsw≤ N_s enforces the context capacity inequality. Assembling the independent context solutions therefore minimizes the sum of stored costs over ℱ0F_0. Let ~λ∈argmin∈ℱ0L(,λ) n_λ∈ _n _0L(n;λ) and let m~s,a:=∑kn~λ,k(s,a) m_s,a:= _k n_λ,k(s,a) be its counts. By exact aggregation and Proposition 9, L(cand(t),λ) L(n_cand^(t);λ) ≤∑s,aHs,a♯(m~s,a,λ) ≤ _s,aH _s,a( m_s,a,λ) ≤∑s,a[Hs,a(t,λ)(m~s,a)+ηs,a(m~s,a)+m~s,aδs,a(m~s,a,λ)] ≤ _s,a [H_s,a^(t,λ)( m_s,a)+ _s,a( m_s,a)+ m_s,a _s,a( m_s,a,λ) ] ≤L(~λ,λ)+EGreedy(t). ≤ L( n_λ;λ)+E_Greedy^(t). The last inequality uses the fact that the exact fixed-count costs are no greater than the costs of the corresponding mixtures in ~λ n_λ. Because ^(t+1)∈ℱ⊆ℱ0 n^(t+1) _0, this gives L(cand(t),λ)≤L(~λ,λ)+EGreedy(t)≤L(^(t+1),λ)+EGreedy(t).L(n_cand^(t);λ)≤ L( n_λ;λ)+E_Greedy^(t)≤ L( n^(t+1);λ)+E_Greedy^(t). (77) The outer comparison ensures J~((t+1),(t))≤J~(cand(t),(t)) J(n^(t+1);n^(t))≤ J(n_cand^(t);n^(t)), even when the current allocation wins. Rearranging (77) and using C(^(t+1))≤κC( n^(t+1))≤κ yields ΔLag(t) _Lag^(t) ≤J~(cand(t),(t))−J~(^(t+1),(t)) ≤ J(n_cand^(t);n^(t))- J( n^(t+1);n^(t)) ≤λ[C(^(t+1))−C(cand(t))]+EGreedy(t) ≤λ [C( n^(t+1))-C(n_cand^(t)) ]+E_Greedy^(t) ≤λ[κ−C(cand(t))]+EGreedy(t). ≤λ [κ-C(n_cand^(t)) ]+E_Greedy^(t). If every residual is zero and every factual count is positive, the uniform local bound in Proposition 9 gives the stated bound on EGreedy(t)E_Greedy^(t). ∎ D.5 Per-Iteration Approximation Error We now combine the majorization and Lagrangian analyses to bound the optimality gap. Theorem 6 (Per-Iteration Approximation Error). Let ∗n^* denote any global minimizer of J()J(n) over ℱF, and use any recorded feasible trial and its error certificate from Proposition 10. The solution (t+1)n^(t+1) returned by one M iteration satisfies: J((t+1))−J(∗)≤∑s∈d0(s)(ℬs(∗)−ℬs((t)))2⏟M(t):majorization gap+λ(t)(κ−C(cand(t)))⏟Lagrangian relaxation gap+EGreedy(t)⏟inner greedy gap.J(n^(t+1))-J(n^*)\;≤\; _s d_0(s) (B_s(n^*)-B_s(n^(t)) )^2_ _M^(t)\;:\;majorization gap\;+\; λ^(t) (κ-C(n_cand^(t)) )_Lagrangian relaxation gap\;+\; E_Greedy^(t)_inner greedy gap. (78) The majorization gap is bounded uniformly by M(t)≤4βmax2G_M^(t)≤ 4 _ ^2, where βmax _ from Appendix A.4 bounds both annotation biases and default-model biases at zero factual counts. The greedy error certificate includes remaining swap gains when the local search stops at its cap. Proof. At fixed t, the constant difference between J~full J_full and J~ J leaves both the constrained minimizer ^(t+1) n^(t+1) and the value difference ΔLag(t) _Lag^(t) unchanged. Consequently, Lemma 7 and the definition of ΔLag(t) _Lag^(t) in Proposition 10 give J((t+1)) J(n^(t+1)) ≤J~full((t+1),(t)) ≤ J_full\! (n^(t+1);\,n^(t) ) (majorization) =J~full(^(t+1),(t))+ΔLag(t) = J_full\! ( n^(t+1);\,n^(t) )+ _Lag^(t) (definition of ΔLag(t) _Lag^(t)) ≤J~full(∗,(t))+ΔLag(t) ≤ J_full\! (n^*;\,n^(t) )+ _Lag^(t) (optimality of ^(t+1)). (optimality of $ n^(t+1)$). Subtracting J(∗)J(n^*) and applying the gap formula (70) yields J((t+1))−J(∗)≤∑s∈d0(s)(ℬs(∗)−ℬs((t)))2+ΔLag(t).J(n^(t+1))-J(n^*)≤ _s d_0(s) (B_s(n^*)-B_s(n^(t)) )^2+ _Lag^(t). The upper bound on ΔLag(t) _Lag^(t) from Proposition 10 then gives (78). For N(s,a)>0N(s,a)>0, the bias is a convex combination of zero factual bias and source biases, so |B(s,a)|≤βmax|B(s,a)|≤ _ . For N(s,a)=0N(s,a)=0, the definition of βmax _ also bounds the default bias. Because the target-policy probabilities sum to one, |ℬs|≤βmax|B_s|≤ _ , and hence |ℬs(∗)−ℬs((t))|≤2βmax|B_s(n^*)-B_s(n^(t))|≤ 2 _ . Summing the squared differences with weights d0(s)d_0(s), which also sum to one, gives M(t)≤4βmax2G_M^(t)≤ 4 _ ^2. ∎ D.6 Convergence Guarantees Corollary 4 (Finite Descent and Stopping Criteria). With fixed problem inputs and deterministic tie-breaking, Algorithm 1 has the following properties: (i) Every changed allocation strictly decreases J, and there are at most |ℱ|−1|F|-1 such updates. (i) If the outer iteration limit is removed and ϵ=0ε=0, the algorithm reaches an unchanged allocation in finitely many iterations. This allocation is a fixed point of the deterministic update rule. A positive tolerance or finite iteration limit may terminate before a fixed point is reached. (i) If an unchanged allocation (∞)n^(∞) is reached at iteration t⋆t_ , then J((∞))−J(∗) J(n^(∞))-J(n^*) ≤∑sd0(s)(ℬs(∗)−ℬs((∞)))2 ≤ _sd_0(s) (B_s(n^*)-B_s(n^(∞)) )^2 (79) +λ(t⋆)(κ−C(cand(t⋆)))+EGreedy(t⋆), +λ^(t_ ) (κ-C(n_cand^(t_ )) )+E_Greedy^(t_ ), using any feasible trial recorded at t⋆t_ . Proof. The best-candidate variable starts at (t)n^(t) and changes only on a strict surrogate improvement. Thus any changed allocation satisfies J~full((t+1),(t))<J~full((t),(t)) J_full(n^(t+1);n^(t))< J_full(n^(t);n^(t)), and the majorization chain in Proposition 8 gives strict descent of J. No changed allocation can therefore revisit a previous allocation in the finite set ℱF, proving (i). After at most |ℱ|−1|F|-1 changes, an update must leave the allocation unchanged. With fixed inputs, search parameters, and tie-breaking, repeating the update at that allocation returns the same result, proving (i). The practical stopping conditions can stop after a small strict improvement or at the iteration limit, neither of which implies an unchanged next update. At an unchanged update, (t⋆+1)=(t⋆)=(∞)n^(t_ +1)=n^(t_ )=n^(∞), so Theorem 6 gives (79), proving (i). ∎ D.7 Computational Complexity Proposition 11 (Total Computational Complexity). Let S=||S=|S|, A=||A=|A|, K=||K=|K|, Nmax=maxsNs≥1N_ = _sN_s≥ 1, and let Tswap≥1T_swap≥ 1 cap accepted swaps per local call. Let TMMT_M be the number of outer iterations and TBisT_Bis an upper bound on all subproblem calls per outer iteration, including the zero-multiplier trial, doubling, and bisection. The total complexity of Algorithm 1 is (TMM⋅TBis⋅S⋅A⋅(K2NmaxTswap+Nmax2)).O\! (T_M· T_Bis· S· A· (K^2\,N_ \,T_swap+N_ ^2 ) ). (80) For an iteration with d multiplier doublings and bracket width W>0W>0 before bisection, the number of subproblem calls is 2+d+max0,⌈log2(W/ϵλ)⌉2+d+ \0, _2(W/ _λ) \. The finite-state bound in Proposition 9 also limits the actual number of accepted swaps, regardless of the chosen cap. Proof. For a fixed pair and total count, source search accepts at most TswapT_swap swaps and needs at most one additional scan to certify the final residual. Each scan evaluates K(K−1)K(K-1) swaps in (K2)O(K^2) by maintaining the sums ∑knkEk _kn_kE_k, ∑knkDk _kn_kD_k, and ∑kcknk _kc_kn_k; each accepted swap updates these sums in constant time. Initialization and storing the source vector cost (K)O(K), so the full fixed-count cost is (K2Tswap)O(K^2T_swap) for Tswap≥1T_swap≥ 1. There are at most Nmax+1N_ +1 counts per pair, giving (ANmaxK2Tswap)O(AN_ K^2T_swap) per context when Nmax≥1N_ ≥ 1. The action-indexed DP has A(Ns+1)A(N_s+1) entries, each scanning at most Ns+1N_s+1 feasible counts, so aggregation costs (ANmax2)O(AN_ ^2) per context. Backtracking costs (AK)O(AK), and scanning the residual tables costs (ANmax)O(AN_ ), both within the preceding bounds. Candidate objective comparisons cost (SAK)O(SAK) per trial and are also dominated by the subproblem cost. Summing over contexts, all multiplier trials, and outer iterations proves (80). There are two initial trials, one at zero and one at λ0 _0, followed by d doubling trials. Each bisection trial halves the interval width, giving the stated remaining trial count. ∎ Appendix E Experimental Details and Additional Results Code and reproduction instructions are available at https://github.com/Lygist/Budgeted-Multi-Source-Counterfactual-Annotation-for-Off-Policy-Evaluation. The accompanying README provides detailed instructions on data preparation, configuration, and the execution pipeline. Computational resources. Local preprocessing, allocation, and OPE calculations used only the central processing unit (CPU) of a MacBook with an Apple M3 Pro chip; the codebase is also compatible with the standard Google Colab CPU environment. LLM annotations were obtained through hosted application programming interfaces (APIs) from Google, OpenAI, and Anthropic. Table 7 reports full-instance solver runtimes, with a one-hour limit for each Gurobi run. Theoretical runtime bounds are given in Proposition 3 and Appendix D.7. E.1 Synthetic Clinical Bandit E.1.1 Environment and source profiles We use 100100 contexts and 55 actions. For each context, πb(⋅∣s)∼Dirichlet(0.2) _b(· s) (0.21). The target policy retains a behavior-selected action with probability 0.90.9 and otherwise replaces it by a uniformly sampled alternative. The context distribution is sampled from a symmetric Dirichlet distribution. Pairwise reward means are independently drawn from 0.2Normal(−2,32)+0.8SkewNormal(ξ=5,ω=6,α=−2),0.2\,Normal(-2,3^2)+0.8\,SkewNormal(ξ=5,ω=6,α=-2), and reward variances from Uniform(20,50)Uniform(20,50). The fitting dataset contains M=1,000M=1,000 records. Source k has mean μr(s,a)+εk _r(s,a)+ _k, variance σr2(s,a)+Δk _r^2(s,a)+ _k, and cost ckc_k. The allocation budget is κ=10,000κ=10,000. E.1.2 Source Subset Comparison Under Consistent Optimization To isolate the effect of source availability from allocation strategy, we evaluate all nonempty subsets sub⊆1,2,3,4K_sub \1,2,3,4\ with M, including the single-source subsets evaluated under random allocation in Figure 2. Figure 3 shows the resulting scaled MSE values. Under consistent optimization, the qualitative conclusions of §7 are unchanged. Figure 3: Scaled mean squared error (MSE) ()V(n) for each active source subset under the proposed majorization-minimization (M) algorithm. Compared with Figure 2, the single-source bars (red) are now obtained by optimization rather than uniformly random allocation; the multi-source bars are unchanged. E.1.3 Convergence Trace on the Synthetic Bandit Figure 4 reports the convergence trace of the M algorithm on the synthetic clinical bandit, replayed across the source subsets that achieve successively lower scaled MSE values: 1,3\1,3\, 1,2,3\1,2,3\, and finally 1,2,3,4\1,2,3,4\. Scaled MSE drops sharply within the first M iteration of each subset and stabilizes within roughly 55–66 iterations, consistent with the monotone-descent property in Proposition 8. The annotation-count tuples annotated on the trajectory show that the optimizer concentrates the budget on the lowest-bias source (Source 1) at first and progressively allocates a small share to higher-variance, lower-cost sources as additional sources become available. Figure 4: Convergence trace of scaled mean squared error (MSE) ((t))V(n^(t)) across majorization-minimization (M) iterations on the synthetic clinical bandit. Different colors mark the active source subset; the tuple annotated at selected iterations records the allocation [n1,n2,n3,n4][n_1,n_2,n_3,n_4] across Sources 1–4 in Table 2. E.2 ASSISTments Semi-Synthetic Environment E.2.1 Dataset, Context Space, and Action Space The ASSISTments 2012–13 School Data with Affect [5] contains 6,123,2706,123,270 student–problem interactions from the ASSISTments online middle-school mathematics tutoring platform. Each row records: (i) student/problem identifiers, (i) first-response latency ms_first_response, (i) correctness of first attempt, hint count, and attempt count, (iv) problem metadata (problem_type, original indicator), and (v) four affect-detector confidences (frustration, confusion, concentration, boredom). We remove interactions with ms_first_response outside [1,000, 600,000][1,000,\;600,000] ms (<1<1 s likely auto-fill, >10>10 min likely idle), retaining 6,117,2796,117,279 rows (99.9%99.9\%), then sort by (user_id, start_time) so that past statistics use only strictly prior interactions. Context Space (||=100|S|=100) Each interaction is embedded as a 6-dimensional vector ϕcontext=[PastCorrect,PastHints,Frust,Conf,Conc,Bore], _context= [PastCorrect,\;PastHints,\;Frust,\;Conf,\;Conc,\;Bore ], where PastCorrectPastCorrect and PastHintsPastHints are expanding-mean correct rate and hint count over the student’s strictly prior problems (initialized to 0.50.5 and 00). Features are standardized; K-means with k=100k=100, ninit=10n_init=10 produces 100100 clusters. Centroids in the original scale are passed to the LLM as the context descriptor. Action Space (||=10|A|=10) We cross problem_type (6 values) with original (2 values), then retain the 1010 combinations with at least 100100 observed interactions. Table 5 lists the resulting actions and their empirical statistics used both in the reward function and in the LLM prompt. Table 5: Action space of the ASSISTments environment. ID Problem Type Original Median RT IQR (s) Correct Rate Count 0 algebra No 11.711.7 s [5.1,30.1][5.1,30.1] 0.3810.381 128,221128,221 1 algebra Yes 27.027.0 s [11.3,63.3][11.3,63.3] 0.6780.678 3,367,9803,367,980 2 choose_1 No 8.18.1 s [4.3,17.7][4.3,17.7] 0.8120.812 127,222127,222 3 choose_1 Yes 16.116.1 s [7.5,39.0][7.5,39.0] 0.7050.705 1,719,8821,719,882 4 choose_n No 11.211.2 s [5.1,19.4][5.1,19.4] 0.6000.600 295295 5 choose_n Yes 13.313.3 s [7.6,27.9][7.6,27.9] 0.7880.788 11,30011,300 6 fill_in_1 No 11.211.2 s [4.9,25.8][4.9,25.8] 0.3350.335 46,59046,590 7 fill_in_1 Yes 28.628.6 s [12.3,66.1][12.3,66.1] 0.6590.659 695,424695,424 8 open_response Yes 76.976.9 s [27.2,169.3][27.2,169.3] 0.5880.588 17,62917,629 9 rank Yes 51.151.1 s [25.4,104.7][25.4,104.7] 0.6600.660 2,7262,726 E.2.2 Reward Function Following the feature-prediction spirit of APRIL [4], we decompose the reward into a data-driven base and an LLM-predictable multiplier. With Rmax=30R_ =30: R(s,a,t)=Rmax⋅PIRT(s,a)⏟data-driven⋅TimeEff(t,t~a)⏟LLM-predictable.R(s,a,t)\;=\;R_ · P_IRT(s,a)_data-driven· TimeEff(t, t_a)_LLM-predictable. (81) IRT component. For context s with centroid correct rate psp_s and action a with overall correct rate qaq_a, set θs=logit(ps) _s=logit(p_s), ba=logit(1−qa)b_a=logit(1-q_a), and PIRT(s,a)=σ(θs−ba)P_IRT(s,a)=σ( _s-b_a), with ps,qap_s,q_a clipped to [0.02,0.98][0.02,0.98]. This is a Rasch (1-PL) model depending only on observed data. Across the 100×10100× 10 grid, PIRTP_IRT has range [0.03,0.98][0.03,0.98], mean 0.680.68, std 0.220.22—providing the primary reward variation. Time-efficiency component. Let t~a t_a be action a’s median response time in seconds. Define TimeEff(t,t~a)=max0.3, 1−α⋅|log10(t/t~a)|,α=0.4.TimeEff(t, t_a)\;=\; \! \0.3,\;1-α· | _10(t/ t_a) | \, α=0.4. This symmetric clamped-linear function is 1.01.0 at t=t~at= t_a, decays linearly in log-space, and floors at 0.30.3 for extreme mispredictions. This constructed discount encodes a preference for response times near the action-specific median, penalizing both unusually short and unusually long responses. Ground-truth reward. For each observed (s,a)(s,a) pair, the reference μr(s,a) _r(s,a) is computed by plugging the empirical median t~s,a t_s,a into Eq. (81). For the 54/100054/1000 pairs with fewer than 2020 observations, we fit a random forest on context centroids ++ action one-hot features to predict log10t~s,a _10 t_s,a (55-fold CV R2=0.89R^2=0.89) and fill the gap. The final μr _r grid has range [0.43,28.7][0.43,28.7], mean 20.0820.08, std 10.7710.77. Figure 5: Ground-Truth reward Left: distribution of Ground-Truth Rewards Middle: heatmap of factual context-action pair data Right: influence of Time-efficiency discount on the total reward E.2.3 LLM Prompt Design Each prompt is a batch of 1010 (s,a)(s,a) pairs sharing a common task description, action-reference table, and domain-knowledge preamble, followed by pair-specific student profiles and 88 bootstrap-sampled historical response times per pair. All per-pair information (ability-level label, centroid features, action statistics, historical samples) is precomputed once from the dataframe before any API call, keeping per-batch overhead below 11 ms and the mean prompt length at ∼3,500 \!3,500 characters. Figure 6 shows the template; curly-braced fields are populated from precomputed lookups. LLM Prompt: ASSISTments Response-Time Prediction You are an expert in educational data mining and intelligent tutoring systems. Your task: predict the response time in seconds for students solving math problems on the ASSISTments platform. “Response time” = seconds from when a problem appears until the student’s first action (submitting an answer or requesting a hint). [[ ## Action Reference (Problem Types) ## ]] ID Problem Type Orig. Median RT IQR (s) CR 0 algebra No 11.711.7s [5.1,30.1][5.1,30.1] 0.3810.381 1 algebra Yes 27.027.0s [11.3,63.3][11.3,63.3] 0.6780.678 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 9 rank Yes 51.151.1s [25.4,104.7][25.4,104.7] 0.6600.660 [[ ## Key Factors Affecting Response Time ## ]] 1. Student ability (past correct rate): higher performers respond faster; strugglers take longer or give up quickly. 2. Hint-seeking habit: students who frequently request hints pause longer before their first action. 3. Emotional context: frustration/confusion → longer; boredom → rush or disengage; concentration → moderate, productive. 4. Problem type: multiple choice fastest; open response and rank slowest; algebra and fill-in in between. 5. Original vs. scaffolding: scaffolding problems typically 3030–50%50\% faster than the original. 6. Interaction effects: struggling × hard → much longer than able × easy. [[ ## Historical Response Time Samples ## ]] For each pair below, we provide actual response times from similar students on similar problems. Use them to calibrate your prediction. [[ ## Student–Problem Pairs ## ]] --- Pair 1 (context_id: s, action_id: a) --- Student: ability_level, correct_rate=psp_s, avg_hints=hsh_s, Student: frustration=fsf_s, confusion=csc_s, concentration=ksk_s, boredom=bsb_s Problem: problem_type, original=orig, typical_median=t~a t_as Historical response times from similar cases: [t1t_1s, t2t_2s, ..., t8t_8s] … (9 more pairs in the same format) … [[ ## Prediction Task ## ]] For each pair, predict a single number: the response time in seconds. Consider all factors and the historical samples carefully. Output a JSON object conforming to the schema, with one entry per pair containing context_id, action_id, and predicted_response_time_seconds. Figure 6: Prompt template used for all three large language models (LLMs) on the ASSISTments environment. Bracketed headers [[ ## …## ]] follow the section-delimiter style of Mandyam et al. [4]; curly_braces denote per-pair fields populated from precomputed pandas lookups. Each batch contains 1010 pairs; 2020 independent queries at temperature 0.80.8 are issued per (s,a)(s,a). E.2.4 LLM Annotation Allocation by M We evaluate four LLM annotation sources: Gemini-2.5-Flash, GPT-4o-mini, GPT-o3-mini, and Claude-Haiku-4.5. For each of the 100×10100× 10 context-action pairs, each model produces 2020 first-response-time predictions at temperature 0.80.8, yielding 20,00020,000 predictions per model. We estimate each source’s bias as ε^k(s,a)=r¯k(s,a)−μr(s,a) _k(s,a)= r_k(s,a)- _r(s,a), where r¯k(s,a) r_k(s,a) is the mean of the 2020 predicted rewards and μr(s,a) _r(s,a) is the reference reward from the simulator. We estimate prediction variability by σ^k(s,a) σ_k(s,a), the standard deviation of the 2020 predicted rewards. Table 6 summarizes these estimates and the API costs. GPT-4o-mini has the lowest mean absolute bias and cost, while GPT-o3-mini costs about 78×78× more without improving the reported quality summaries, consistent with the feature-prediction findings of APRIL [4]. Table 6: LLM annotation quality on ASSISTments. Bias and variability are computed after converting predicted response times to rewards. The cost column reports the total API cost for the 20,00020,000 predictions used to estimate each model’s empirical bias and variability; the allocation experiment uses the corresponding per-prediction cost. Source mean|ε^k|mean| _k| median|ε^k|median| _k| meanσ^kmean σ_k Total API cost Gemini-2.5-Flash 1.091.09 0.770.77 0.530.53 $1.141.14 GPT-4o-mini 0.830.83 0.570.57 0.440.44 $0.48\$0.48 GPT-o3-mini 0.960.96 0.620.62 0.550.55 $37.2637.26 Claude-Haiku-4.5 0.860.86 0.560.56 0.280.28 $8.118.11 We generate 6,0006,000 logged samples from the ASSISTments simulator, with pair-specific reward variances σr2(s,a)∼Uniform(30,60) _r^2(s,a) (30,60). Based on the source diagnostics in Table 6, we run the M-based allocation algorithm with the three lower-cost sources, excluding GPT-o3-mini, under budget κ=$0.50κ=\$0.50. The algorithm decides to purchase 6,0006,000 annotations and reduces the variance objective from J()=88.61J(0)=88.61 to 79.0679.06, a 10.77%10.77\% reduction. Mirroring the synthetic experiment, we evaluate every non-empty LLM source subset (excluding the high-cost GPT-o3-mini, which Table 6 shows offers no quality advantage) under two protocols for the single source baseline: a uniformly random allocation and the proposed M algorithm. Figure 7 reports the random-allocation baseline. Single-source subsets yield variance objectives in the range 80.7980.79–83.7283.72, while every multi-source subset drops below 8080. Figure 7: Variance objective J()J(n) for each active LLM source subset under uniformly random allocation. Bars are grouped by the number of available sources; the dashed line is the no-annotation baseline J()=88.61J(0)=88.61. Figure 8 repeats the comparison under consistent M optimization. The single-source bars improve to 79.3279.32–80.8280.82, narrowing the gap to multi-source results. The three-source configuration Gemini,Claude,GPT-4o-mini\Gemini,Claude,GPT-4o-mini\ remains the global optimum at J=79.06J=79.06, a 10.77%10.77\% reduction over J()=88.61J(0)=88.61. Figure 8: Variance objective J()J(n) for each active LLM source subset under the proposed M algorithm To illustrate the dynamics of the M algorithm under realistic LLM annotation profiles, Figure 9 shows the convergence trace on ASSISTments. The objective decreases monotonically from 88.6188.61 to 79.0679.06. Figure 9: Convergence trace of J((t))J(n^(t)) across M iterations on ASSISTments. The tuple at each highlighted iteration denotes the optimal allocation across [Gemini-2.5-Flash, Claude-Haiku-4.5, GPT-4o-mini]. The algorithm heavily favors GPT-4o-mini due to its low empirical bias and high cost-efficiency, while utilizing Claude-Haiku-4.5 more conservatively because of its higher API cost. E.3 Exact-Solver Benchmarks and Runtime To complement the certified small-instance optima in Table 4, we warm-started Gurobi on the full Synthetic and ASSISTments instances with the best heuristic solution and imposed a one-hour time limit. The runs did not certify global optimality within that limit, so we compare the methods against the valid lower bounds available at termination. Let L be the scaled-MSE lower bound available at termination and zA=(A)z_A=V(n_A) the scaled MSE returned by method A. The table reports 100(zA−L)/zA100(z_A-L)/z_A. The heuristic runtimes exclude the Gurobi computation used to obtain L. Table 7: Solver benchmarks and runtimes for the Synthetic and ASSISTments environments. Dataset Method Gap to Gurobi lower bound Runtime (s) Synthetic Greedy (max-gain) 0.6863% 0.0314 Synthetic Greedy (cost-aware) 3.9843% 0.0562 Synthetic M 1.0474% 8.2390 Synthetic M (greedy init.) 0.2807% 5.2657 Synthetic Gurobi incumbent 0.1258% 3600.6957 ASSISTments Greedy (max-gain) 0.8216% 1.0222 ASSISTments Greedy (cost-aware) 0.1769% 3.5662 ASSISTments M 0.0050% 857.6975 ASSISTments M (greedy init.) 0.0050% 521.8667 ASSISTments Gurobi incumbent 0.0047% 3604.0060 Table 4 shows greedy-initialized M has a 0.05%0.05\% mean gap and a 0.26%0.26\% maximum gap to the certified optima on the small instances. On the full instances, Table 7 shows that it reaches within 0.2807%0.2807\% and 0.0050%0.0050\% of the Gurobi lower bounds in 5.35.3 and 522522 seconds, respectively. These comparisons show small empirical gaps to the available exact and lower-bound benchmarks. E.4 End-to-End Evaluation with Finite Pilots The solver benchmarks assess optimization quality for fixed profiles; we next evaluate final OPE performance when allocations are selected using finite-pilot estimates. For each of 3030 pilot replications, factual moments are estimated from 2020 pilot rewards per pair and annotation moments from 2020 pilot draws per source–pair. The pilot is separate from subsequent fitting rewards, acquired annotation realizations, and OPE outcomes. Fitting-data context–action counts determine the capacities. Each allocator receives the same pilot estimates and constraints. For the optimized single-source baseline, we optimize each source separately and use the pilot objective to select the predicted best source. Thus, this baseline does not select its source using final OPE outcomes. After fixing an allocation, we generated 5050 independent reward and annotation realizations from the distributions used in each environment and evaluated DM+-IS on independent OPE datasets (N=1,000N=1,000 for Synthetic and N=6,000N=6,000 for ASSISTments). In ASSISTments, the annotation realizations are drawn from empirical source models fitted to the observed LLM predictions. Within each pilot replication, empirical MSE is the average squared deviation of the 5050 final value estimates from the environment’s true policy value. Table 8 reports the mean across pilot replications of the relative MSE reduction versus the corresponding no-annotation baseline. Table 8: Mean relative reduction in empirical mean squared error (MSE) over 3030 pilot replications. For each pilot, MSE is estimated from 5050 independent final off-policy value estimates. Method Synthetic ASSISTments Best optimized single source 17.86% 8.30% Greedy (max-gain) 18.43% 7.86% Greedy (cost-aware) 14.39% 8.46% M 18.67% 8.46% M (greedy init.) 19.13% 8.47% Table 8 shows greedy-initialized M reduces empirical MSE by 19.13%19.13\% on Synthetic and 8.47%8.47\% on ASSISTments relative to no annotation. Thus, the allocation gains persist in these experiments after finite-sample profile estimation and evaluation of the final OPE estimator. E.5 Within-pair bootstrap As a complementary check, we assess sensitivity to resampling the LLM outputs used to estimate source profiles. For each of 3030 bootstrap replications, we resample the 2020 observed predictions within each source–pair, re-estimate its moments, and rerun M. We evaluate the resulting allocation using reference profiles estimated from all 2020 original predictions per source–pair. The average reference-profile MSE reduction is 10.765%10.765\%, compared with 10.774%10.774\% using the original profiles. The standard deviation is 0.00380.0038 percentage points, and the mean difference is 0.0090.009 percentage points. This measures conditional sensitivity to resampling the observed outputs. Because evaluation uses the same empirical source reference, it is not held-out validation of the population LLM distribution and does not measure uncertainty in the simulator’s factual reward reference. Appendix F Broader Impacts and Asset Use F.1 Broader Impacts Budgeted counterfactual annotation can improve the efficiency of policy evaluation before deployment. In healthcare and education, unreliable annotations or violations of the evaluation assumptions may nevertheless yield inaccurate policy comparisons with consequences for treatment or instruction. Application-specific validation, including assessment of subgroup outcomes, is therefore important before deployment. F.2 Existing Data and Model Services The ASSISTments 2012–13 School Data with Affect [5, 6] are provided by Neil T. Heffernan and the ASSISTments team at Worcester Polytechnic Institute through the official dataset release. The ASSISTments data-use conditions require users to report and delete any inadvertently discovered personally identifiable information and prohibit using that information. Our experiments use existing records, with no participant recruitment, crowdsourcing, or interventions. The annotation sources are Google’s Gemini-2.5-Flash, OpenAI’s GPT-4o-mini, and Anthropic’s Claude-Haiku-4.5. Hosted access is subject to the Google APIs Terms of Service and Gemini API Additional Terms of Service, the OpenAI Services Agreement, and the Anthropic Commercial Terms of Service, respectively. NeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? Answer: [Yes] Justification: The claims in the abstract and introduction match the theoretical results proved in Appendices A–D and the experimental results in Section 7. Guidelines: • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 2. Limitations Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The Conclusion discusses the contextual-bandit scope, reliance on known or estimated source profiles, and semi-synthetic ASSISTments environment. Sensitivity to estimated profiles is analyzed in Appendix A.4 and evaluated in Section 7.3. Guidelines: • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate “Limitations” section in their paper. • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory assumptions and proofs Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: Assumptions accompany the theoretical statements, and their derivations and proofs are provided in Appendices A–D. Guidelines: • The answer [N/A] means that the paper does not include theoretical results. • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 4. Experimental result reproducibility Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Section 7 and Appendix E describe the environments, reward functions, large language model (LLM) prompts, and evaluation protocols; code and reproduction instructions are available at the GitHub repository link in Appendix E. Guidelines: • The answer [N/A] means that the paper does not include experiments. • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provide a GitHub repository containing all code, public data sources, data preprocessing scripts, and a detailed README to reproduce the experiments. See details in Appendix E. Guidelines: • The answer [N/A] means that paper does not include experiments requiring code. • Please see the NeurIPS code and data submission guidelines (https://neurips.c/public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.c/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental setting/details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results? Answer: [Yes] Justification: Section 7 and Appendix E describe the synthetic and semi-synthetic environments, preprocessing, source-profile estimation, and separation of pilot, fitting, and evaluation samples. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 7. Experiment statistical significance Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: We report the mean and standard deviation across 100 independent environment initializations(e.g., shaded bands in Figure 1). We also provide bootstraps experiment to test the robustness of the algorithm in Section 7.3. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates). • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments compute resources Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Appendix E identifies the local hardware and hosted LLM services, and Table 7 reports full-instance solver runtimes. Memory, runtimes for the remaining experiments, and total project compute are not reported. Guidelines: • The answer [N/A] means that the paper does not include experiments. • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper). 9. Code of ethics Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.c/public/EthicsGuidelines? Answer: [Yes] Justification: The research conforms to the NeurIPS Code of Ethics. Guidelines: • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics. • If the authors answer [No] , they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: Appendix F.1 discusses the benefit of more efficient policy evaluation, potential consequences of inaccurate policy comparisons, and the need for application-specific validation. Guidelines: • The answer [N/A] means that there is no societal impact of the work performed. • If the authors answer [N/A] or [No] , they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)? Answer: [N/A] Justification: The contribution is an allocation method using existing data and hosted LLMs; we do not release a pretrained generative model or a newly collected student dataset. Guidelines: • The answer [N/A] means that the paper poses no such risks. • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Appendix F.2 identifies the ASSISTments release and creators, links its data-use conditions, and identifies the LLM providers and applicable service terms. Guidelines: • The answer [N/A] means that the paper does not use existing assets. • The authors should cite the original paper that produced the code package or dataset. • The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., C-BY 4.0) should be included for each asset. • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset’s creators. 13. New assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: The code and detailed instructions are in our repository at [repository URL]. Guidelines: • The answer [N/A] means that the paper does not release new assets. • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [N/A] Justification: We use synthetic data and secondary analysis of existing ASSISTments records, with no participant recruitment, crowdsourcing, or interventions (Appendix F.2). Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [N/A] Justification: The experiments use synthetic data and secondary analysis of the public ASSISTments release, with no new participant recruitment or interventions (Appendix F.2). Guidelines: • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 16. Declaration of LLM usage Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required. Answer: [Yes] Justification: Section 7.2 and Appendix E.2 describe the LLM annotation sources, response-time prediction task, prompts, and conversion of predictions to rewards. Guidelines: • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.