The Surrogate Is Not the Reward: Post-Surrogate Primary-Outcome Acquisition in Contextual Bandits

• Acquisition value depends both on how much an outcome matters to unresolved policy comparisons and on the residual uncertainty remaining after the surrogate.When policies choose the same action, or little residual variation remains, the outcome provides little help distinguishing them.Source: §1 · pp. 1–2
• ASB acquires exactly B primary outcomes on every path while learning a policy, using decision relevance before the surrogate and estimated residual uncertainty afterward.The method is evaluated for a finite class of N policies over K actions.Source: §1 · p. 2
• Post-surrogate acquisition can achieve bounded regret, while pre-surrogate acquisition incurs Ω(T/B) worst-case regret even when the surrogate does not reveal the better action.The comparison uses the same acquisition budget.Source: §1 · p. 2
• Synthetic experiments find higher regret when either decision relevance or post-surrogate residual-RMS refinement is removed; on KuaiRec, the gap from relevance-only acquisition first widens and then narrows as budget grows.Source: §1 · p. 2
• Related work studies prediction-guided acquisition, costly feedback, and intermediate or post-action feedback, while ASB uses the current surrogate to decide whether to acquire the same round’s primary outcome.Regret and subsequent policy learning remain tied to that primary outcome.Source: §1 · p. 2

• After observing context X_t, the learner selects action A_t, observes surrogate S_t for free, and then decides whether to acquire Y_t.Y_t is observed only when the acquisition indicator Q_t equals one.Source: §2 · pp. 2–3
• The conditional mean r⋆(x, a) defines primary-outcome value, and cumulative regret compares each chosen action with the best action in that round’s context.Source: §2 · p. 3
• The learner minimizes cumulative regret subject to acquiring at most B primary outcomes on every path over T rounds.B is the primary-outcome acquisition budget.Source: §2 · p. 3

3.1 One round of ASB

• ASB combines a policy mixture and exploration to select an action, then computes how relevant that action is to current policy comparisons.The decision-relevance score is the largest comparison coefficient magnitude across policies.Source: §3.1 · p. 3
• It sets a pre-surrogate acquisition level from decision relevance and refines it after observing the surrogate using a learned RMS residual score.The refinement redistributes the initial level according to residual RMS while retaining its fitted conditional mean.Source: §3.1 · p. 3
• The augmented feedback preserves the primary-outcome conditional mean, allowing policy-comparison evidence to remain unbiased for the primary-outcome value difference.The policy weights are updated using a second-order exponential-weights rule.Source: §3.1 · p. 4

3.2 Acquisition structure: decision relevance and residual RMS

• Decision relevance sets the pre-surrogate allocation shape, while post-surrogate acquisition favors surrogate values with larger learned residual RMS scores.The resulting rule can depend on the surrogate while preserving the comparison evidence’s conditional mean.Source: §3.2 · p. 5

4 Primary-Outcome Acquisition Before and After the Surrogate: Allocation and Regret

• The section isolates whether allowing acquisition to depend on the current surrogate changes allocation efficiency and attainable regret rates.PRE rules decide before observing the surrogate; POST rules may use it.Source: §4 · p. 5

4.1 Acquisition Timing for a Policy Comparison

• Post-surrogate acquisition strictly lowers minimum comparison variance when the surrogate adds information about residual uncertainty at states relevant to the policy comparison.The estimator remains unbiased for the same primary-outcome value difference under either timing rule.Source: §4.1 · p. 6

4.2 Regret-Rate Separation

• For B=o(T), pre-surrogate strategies incur Ω(T/B) worst-case regret, whereas a post-surrogate strategy achieves bounded regret even though the surrogate does not reveal the optimal action.The separation also holds for the original pathwise hard-budget problem.Source: §4.2 · p. 7

5.1 ASB Regret under the Hard Budget

• Up to logarithmic factors, ASB’s best-in-class regret is √(KT log N)(1 + √(T/B)) for N policies over K actions, with B hard-budget acquisitions.At B = T, the bound has the usual finite-policy contextual-bandit scale; the budget factor grows as B decreases.Source: §5.1 · p. 8
• The end-to-end guarantee does not require the fitted bridge, residual score, or surrogate law to be correct.Source: §5.1 · p. 8

5.2 Primary-Outcome Scarcity Lower Bound

• For a family with zero approximation gap, every learner retains the T/B budget dependence, up to logarithmic factors, even under an expected acquisition budget.The lower bound relaxes the pathwise hard budget; every pathwise-budget learner satisfies the relaxed constraint.Source: §5.2 · p. 8

6.1 Synthetic tests of acquisition structure

• With the same decision problem and exact budget, ASB has substantially lower cumulative regret than Relevance only, Residual only, Uniform, and Fixed-N.Decision relevance targets rounds that distinguish policies, while residual RMS prioritizes surrogate states by estimated remaining uncertainty.Source: §6 · p. 8, §6.1 · p. 9
• As residual-magnitude information in the surrogate increases, POST regret falls below PRE; they coincide when the surrogate carries no such information, despite not revealing the better action.Source: §6.1 · p. 9, Figure 1 · p. 9
• At fixed average residual information, placing more information in policy-disagreement contexts lowers regret; the middle information level yields the largest contrast and regret change.Source: §6.1 · pp. 9–10, Figure 1 · p. 9

6.2 KuaiRec acquisition benchmark

• At 4–8% budgets, both mean contrasts favor ASB most clearly, while differences are small at the lowest and upper evaluated budgets.Cumulative-regret gains need not persist in terminal policy value, whose contrast is near zero at some budgets.Source: Figure 2 · p. 10, §6.2 · p. 10
• At low budgets, initialization leaves few refinement rounds; toward the high end, abundant primary feedback narrows the contrasts.Source: §6.2 · p. 10

7 Discussion

• Selective measurement can bias an uncorrected update, so the augmented feedback preserves the primary target without requiring a correct bridge.The timing question then concerns whether observing the surrogate changes comparison variance or attainable regret.Source: §7 · p. 11
• Even with an expected acquisition budget, the lower bound gives a worst-case T/B penalty up to logarithmic factors.The discussion contrasts this scarcity limit with ASB’s pathwise hard-budget setting.Source: §7 · p. 11
• ASB must learn online which rounds merit measurement because acquired outcomes feed policy updates as well as bridge and residual fits.The discussion reports synthetic regret increases when either acquisition component is removed and a KuaiRec separation clearest at 4–8% budgets that narrows at higher budgets.Source: §7 · p. 11
• The formulation treats measurement as passive: acquiring the current primary outcome does not change future contexts or outcomes.The surrogate can still affect which primary outcomes are measured for future learning, while the primary outcome continues to define action value and regret.Source: §7 · p. 11

Generative AI disclosure

• The paper reports that generative AI assisted with editing, related-work discovery, experiment-code implementation, and proof-sketch checking; the authors reviewed the material and take responsibility for the final paper.Source: Generative AI disclosure · p. 11

A Theory of Primary-Outcome Acquisition Before and After the Surrogate

• The appendix proves the augmented-feedback identity, isolates the acquisition-dependent part of fixed-comparison variance, and establishes the two main theorems.Source: A Theory of Primary-Outcome… · p. 16

A.1 Conditional-Mean Preservation

• The augmented feedback has conditional expectation equal to the primary outcome’s conditional mean, preserving the primary target.ASB uses the identity only when acquisition probability is positive; deterministic full-acquisition rounds have probability one.Source: §A.1 · p. 16

A.2 Acquisition-Dependent Variance for a Fixed Policy Comparison

• For a fixed policy comparison, V(ρ) is the only acquisition-dependent part of the variance because the comparison mean and the other variance term do not depend on ρ.The derivation defines residual uncertainty through the conditional squared error of the bridge.Source: §A.2 · p. 16

A.3 Proof of the PRE/POST Variance Characterization

• The minimum PRE and POST variances are equal exactly when residual uncertainty after the surrogate has no conditional variation on states that matter to the comparison; otherwise POST is strictly better.The condition applies almost surely where the fixed comparison weight is nonzero.Source: §A.3 · p. 17

A.4 Regret-Rate Separation on a Common Family

• The POST strategy acquires informative St=1 rounds until it reaches B acquisitions or the horizon ends, yielding exactly B acquisitions on every path.Source: §A.4 · p. 19
• With ∆=1/4 and q=1/(2B), PRE has a T/(16B) bound, while POST has an O(1) bound when B ≥8 log T.For B=o(T) and B≥8 log T, the passages state that PRE learners have Ω(T/B) worst-case regret while the exact-B POST strategy has O(1) regret.Source: §A.4 · p. 19

B Hard-Budget Acquisition for ASB

• The hard-budget rule uses deterministic boundaries and interval accounting to allocate exactly B primary outcomes over the horizon.Its stochastic-round accounting is designed to avoid exhausting the remaining budget too early while preserving support for the regret analysis.Source: B Hard-Budget Acquisition for ASB · p. 20

B.1 Pre-surrogate budget allocation

• Before observing the surrogate, the allocator sets interval targets from the remaining budget, reserves acquisitions for support, and scales additional acquisition using decision relevance.The support floor is required whenever decision relevance is positive, independently of the fitted residual score.Source: §B.1 · pp. 20–21

B.2 Post-surrogate refinement and accounting

• After observing the surrogate, residual-RMS refinement is restricted by the remaining additional interval budget; once that budget is exhausted, the rule uses a constant allocation.Source: §B.2 · p. 22

C.1 Gain range and second-moment bounds

• Under support condition (21), the gain is bounded by Gbd = K/(2ε) + 1/α, and the cumulative mixture second moment satisfies DT ≤ 2KT + T/α.The per-round mixture second moment is bounded by K + 2dt.Source: §C.1 · p. 23

C.2 Fixed-rate regret bound

• For a fixed learning rate, policy regret is bounded by terms scaling as LT/η, η(KT + DT), and Gbd LT, simultaneously across policies.The bound applies under the support condition and the stated timing and conditional-independence assumptions.Source: §C.2 · pp. 24, 26

C.3 Hard-budget support verification

• For the theorem specialization of Algorithm 2, using Cinit = 0, a fixed regular interval partition with κ > 0, and ζ = δ/(2J), the analysis verifies (21) with α = B/{KT log(8T)}.Source: §C.3 · p. 26

C.4 Proof of the ASB regret guarantee

• ASB’s regret guarantee follows by combining the fixed-rate bound with support verification for its hard-budget acquisition rule.For B ≥ Cpace K LT, the support condition holds with probability at least 1 − δ/2; the proof then applies the fixed-rate analysis.Source: §C.4 · pp. 28–29

C.5 Regret guarantee with full-acquisition initialization

• Controlled full-acquisition initialization preserves the same regret rate as the main guarantee.The appendix notes that initialization acquisitions count toward budget B; the proposition considers a fixed initialization length parameter.Source: C ASB Regret Analysis · p. 23, §C.5 · p. 29
• With Cinit ≤ T/4 and B ≥ C0KLT, qj ≥ qinit; a sequential union bound gives (21) on all post-initialization rounds with probability at least 1−δ/2.Source: §C.5 · p. 30

C.6 Learned post-surrogate refinement in the regret bound

• If Proposition 10’s right-hand side is positive, learned post-surrogate refinement gives DT < Dpre_T, lowering the acquisition-dependent regret term when the support condition for Lemma 7 holds.Proposition 10 does not require the support condition or correct fitted models; support is needed to apply Lemma 7.Source: §C.6 · pp. 30–31

D Proof of the Primary-Outcome Scarcity Lower Bound

• The proof fixes a context sequence and uses a constant surrogate, then varies which action is optimal at each context.The environment family also includes contexts where all actions have equal primary-outcome means.Source: D Proof of the Primary-Outcome… · pp. 31–32
• The constructed policy class has zero approximation error along the fixed context sequence, so the lower bound isolates primary-outcome scarcity.Unused contexts can be added to reach N policies without changing the evaluated sequence.Source: D Proof of the Primary-Outcome… · p. 32
• A one-context comparison bounds how much play counts can differ between environments by the primary acquisitions at that context.The argument compares observation laws, applies Pinsker’s inequality, and averages across actions and contexts.Source: D Proof of the Primary-Outcome… · pp. 32–33
• The averaging argument yields at least one environment satisfying the lower bound under the stated budget and policy-class conditions.The proof also treats the cases log N / log K ≤ T and log N / log K > T.Source: D Proof of the Primary-Outcome… · p. 33

E One Fitting Specification for the Learned Components

• The finite-policy fitting specification estimates the conditional surrogate law from past surrogate observations, without primary outcomes.For finite supports, it uses smoothed empirical conditional frequencies.Source: E One Fitting Specification for the… · pp. 33–34

F A Linear Analogue of the Acquisition Roles

• A linear analogue replaces pre-surrogate decision relevance with leverage while retaining residual RMS for post-surrogate allocation.The appendix gives a budgeted linear construction and a regret bound separate from Algorithm 1.Source: F A Linear Analogue of the Acquisition… · p. 34

F.1 One linear construction

• The linear construction chooses actions and a leverage-based acquisition level before observing the surrogate, then adds a bounded residual component afterward.The current primary outcome is not used before the acquisition decision.Source: §F.1 · pp. 34–35

F.2 Regret bound for the linear construction

• Proposition 11 states that the linear learner satisfies the hard primary-outcome budget and gives a high-probability regret bound.The proof handles the budget stop and separately notes that for smaller B, the deterministic regret bound is absorbed by the displayed rate.Source: §F.2 · pp. 35, 37

G Experimental Details and Reproducibility

• The experimental-details appendix records the settings used in reported experiments, with further implementation specifics in supplementary code.The fitted methods begin with a fully acquired prefix, and reported hard-budget runs finish with exactly B acquisitions.Source: G Experimental Details and… · p. 37, §G.1 · p. 38

G.1 Common finite-policy implementation

• Budget-matched learned methods share a policy-learning schedule and common feedback, while adaptive methods use an exact-count budget manager.The implementation also fixes the refinement strength before observing the surrogate.Source: §G.1 · pp. 37–38

G.2 Controlled synthetic family

• The controlled synthetic family holds the primary law, contexts, and policy class fixed while varying the association between the surrogate and residual magnitude.Its variants compare relevance-only, residual-only, uniform, fixed, and exact residual-allocation references.Source: §G.2 · pp. 38–39

G.3 KuaiRec data-derived benchmark

• The KuaiRec benchmark uses five-video candidate sets and reveals whether play duration exceeds seven seconds before deciding whether to acquire watch ratio.It includes 22,417 rounds, five actions, and nine represented policies.Source: §G.3 · p. 39
• The fitted acquisition models are trained on a disjoint KuaiRec subset and held fixed; residual-model predictions have Spearman correlation 0.4387 with absolute bridge residuals across selectable cells.The positive association also holds within each surrogate stratum.Source: §G.3 · p. 39
• The benchmark’s plotted standard errors measure algorithmic randomization on its fixed table, not uncertainty for a future user population.At the 2% budget, the 346-round fully acquired prefix uses 77.2% of available acquisitions.Source: §G.3 · pp. 39–40

H Extended Related Work

• ASB treats the observed surrogate as acquisition-side information, while action value and regret remain defined by the primary outcome.The related-work discussion contrasts this role with surrogate-reward methods that incorporate proxy signals into reward prediction or policy learning.Source: H Extended Related Work · p. 40