The Surrogate Is Not the Reward: Post-Surrogate Primary-Outcome Acquisition in Contextual Bandits
Abstract
We study contextual bandits in which a surrogate is observed after the action but before the learner decides whether to acquire the primary outcome that defines action value and regret. The value of acquiring the primary outcome depends on both decision relevance (how much the current outcome matters for comparing policies) and the residual uncertainty after observing the surrogate. The Audited Surrogate Bandit (ASB) learns a contextual policy while allocating a budget of B primary-outcome acquisitions over T rounds. ASB sets a pre-surrogate acquisition level from current decision relevance and, after observing the surrogate, redistributes that level using an estimate of that residual uncertainty. For a finite class of N policies over K actions, ASB incurs Õ[√(KTlog N){1+√(T/B)}] regret relative to the best policy in the class. In a two-action family where the surrogate does not reveal the better action, a learner that observes the surrogate before deciding whether to acquire can achieve bounded regret, whereas any learner that must decide before seeing the surrogate incurs Ω(T/B) worst-case regret under the same budget. Synthetic experiments show that both acquisition factors matter: ASB has lower regret than variants using only decision relevance or only residual uncertainty. On a KuaiRec benchmark of user-video interactions, the regret gap relative to relevance-only acquisition widens and then narrows as the budget grows.
Related
- Set Membership Estimation for Stochastic Linear Contextual Bandits
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
- Diversified Multinomial Logit Contextual Bandits
- Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
- Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
BibTeX
@misc{lee2026surrogate,
title = {{The Surrogate Is Not the Reward: Post-Surrogate Primary-Outcome Acquisition in Contextual Bandits}},
author = {Kyungbok Lee and Michael R. Kosorok},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06610},
eprint = {2610.06610},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06610},
}
RIS
TY - UNPB
TI - The Surrogate Is Not the Reward: Post-Surrogate Primary-Outcome Acquisition in Contextual Bandits
AU - Kyungbok Lee
AU - Michael R. Kosorok
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06610
UR - https://arxiv.org/abs/2610.06610
AB - We study contextual bandits in which a surrogate is observed after the action but before the learner decides whether to acquire the primary outcome that defines action value and regret. The value of acquiring the primary outcome depends on both decision relevance (how much the current outcome matters for comparing policies) and the residual uncertainty after observing the surrogate. The Audited Surrogate Bandit (ASB) learns a contextual policy while allocating a budget of B primary-outcome acquisitions over T rounds. ASB sets a pre-surrogate acquisition level from current decision relevance and, after observing the surrogate, redistributes that level using an estimate of that residual uncertainty. For a finite class of N policies over K actions, ASB incurs Õ[√(KTlog N){1+√(T/B)}] regret relative to the best policy in the class. In a two-action family where the surrogate does not reveal the better action, a learner that observes the surrogate before deciding whether to acquire can achieve bounded regret, whereas any learner that must decide before seeing the surrogate incurs Ω(T/B) worst-case regret under the same budget. Synthetic experiments show that both acquisition factors matter: ASB has lower regret than variants using only decision relevance or only residual uncertainty. On a KuaiRec benchmark of user-video interactions, the regret gap relative to relevance-only acquisition widens and then narrows as the budget grows.
ER -