acceptodds
Under review as a conference paper at ICLR 2027

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 primary-outcome acquisitions over 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 policies over actions, ASB incurs 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 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.

Primary area:
learning theory
Keywords:
contextual bandits, costly feedback, primary-outcome acquisition, post-surrogate acquisition

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_uEFxOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies contextual bandits where a free surrogate is observed after action selection and before deciding whether to acquire a costly primary outcome. ASB combines policy-comparison relevance with estimated surrogate-conditioned residual RMS, augmented inverse-propensity feedback, and a hard acquisition budget. The paper characterizes optimal PRE/POST variance under a proportional-allocation feasibility condition, separates the two information orders in regret, and proves a worst-case budget-dependent regret guarantee. Synthetic mechanism studies and a retrospective KuaiRec benchmark evaluate the design.

Critical strengths
  1. A meaningful information-order question with a principled acquisition rule. Policy relevance times surrogate-conditioned residual uncertainty is intuitive. Theorem 1 characterizes PRE/POST variance and strict improvement under its stated feasibility assumptions; Theorem 2 shows a bounded-versus-Omega(T/B) regret separation even when the surrogate's marginal law is identical across possible optimal actions. This identifies value in post-action information beyond predicting which action is better.
  2. Careful learning and acquisition under a hard budget. The support floor, interval accounting and stopped-process argument address the difficulty that budget exhaustion can invalidate unbiased feedback. The best-in-class guarantee accommodates misspecified models, and its worst-case budget dependence has a lower bound. These are useful contributions even though stronger benefits from learning accurate residual models remain unquantified.
Critical weaknesses
  1. The benchmarks provide limited evidence of the need to learn from the acquired outcomes. On all 64×512 released synthetic world/context pairs, the recommendation-only plurality rule argmax_a sum_pi 1{pi(x)=a} chooses the optimal action with zero errors or ties (minimum winning margin 68). Its mapping is represented in the policy class and it needs no outcomes or surrogates. This does not invalidate the matched acquisition ablations: the full component rerun gives ASB 550.70±4.80 SE versus relevance-only 650.25±5.57. It does limit what they show about an unresolved decision problem. On KuaiRec, plurality gives cumulative regret 49.43 versus ASB means 327.59–696.83 across budgets. This is a different action learner using the same 7,055 offline fitting labels, not an acquisition-only comparison or a claim of no prior supervision. It also does not dominate terminal value: at the 24% budget ASB reaches .365476 versus plurality's .364400. The operational distinction between a free play-duration threshold and a costly watch ratio needs justification.
  2. The benefit of the learned surrogate allocation is less fully established than the information-order separation. Residual-RMS allocation and augmentation have close precedents in the cited Active Statistical Inference and Ao et al. work; contextual regret and hard-budget integration remain distinct. Proposition 10 controls model-error effects at a fixed learner state but does not give an error-versus-acquisition-budget rate or a regret comparison between separately evolving learners. Theorem 3 likewise has no explicit surrogate-quality improvement. Its ASB exploration floor does not attain the separate constant-regret POST construction, and the experimental adaptive learning rates/restarts are not the analyzed fixed-eta instantiation. These limit the guarantees' scope; they do not contradict the stated theorems.
Questions for authors
  1. Benchmark and policy representation: Can you include the recommendation-only baseline, distinguish cumulative regret from terminal value, and test the acquisition benefit with a policy class whose consensus does not reveal the optimum? Since uniform expert initialization changes the induced action distribution when one behavioral cluster is overrepresented, how sensitive are the conclusions to distinct but nearly identical policies? Exact duplicates can be deduplicated; the issue is robustness to the prior induced by the policy collection, not a theorem contradiction.
  2. Learned models and analyzed algorithm: Which bridge/residual fitting choices produce the gains, and what evidence connects their acquisition cost and accuracy to policy regret? Can you clarify the guarantee for the adaptive-rate/restart implementation, or compare it with the analyzed schedule?
  3. Practical budget choices: What makes watch ratio costly when the play-duration threshold is free? Please account for the 7,055 offline labels and 346-label initialization. How sensitive are the results to the three post-initialization intervals, their lengths and the residual-uncertainty interval allocation? Reporting final-fill acquisition frequency would help interpret how much the adaptive score determines the final budget use.
Reviewer_YAP8OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper presents the Audited Surrogate Bandit (ASB), where a context X_t is shown, action A_t is taken as in a standard contextual bandit), but the player is allowed to see a cheap (free) surrogate reward, and based on this, can decide to see the true reward Y_t but with a budget (They can get B total reward sample out of the T round of play).

The setting is one where they have a finite set of deterministic policies. There are weights for each of the policies that are updated (second order exponential weights update); these weighted policies (along with an epsilon-greedy uniform “smoothing” line 4 in Algo 1) decides action; determines based on surrogate observation whether to expend reward budget of B, and update based on reward.

They have several theoretical results, some of which were hard to parse, and others were more transparent (details below).

Critical strengths

I think this is a nice formulation, and the regret results in section 5 are interesting. For bandit problems, I really look for a matching lower bound, and the expected budget version here is nice. The regret results also provide good intuition on the (T/B) dependence.

Critical weaknesses

Based on my reading, I think that there might be significant LLM use for this paper (which is fine, as this has been disclosed). However, I feel that it has not been sufficiently humanized because of which I am unable to parse some parts (and even other parts required a lot of time). The hardest for me is Section 3.1: “Pre-surrogate acquisition level and post-surrogate refinement”. What is the fitted bridge (“After observing S_t, it evaluates the fitted bridge …”). This does not seem to be defined earlier, and this term is used several times in the paper. I tried to read Appendix B to try to understand this better, but it was extremely hard for me to parse. There is no intuition on the method for budget allocation.

Also, it is unclear to me what the message in Section 3.2 is.

Questions for authors

Overall this paper would benefit from another pass, where more description and intuition is added. Proof sketches are needed, without which I am unable to follow significant pieces. Also, what parts of the proofs are novel and what are standard? I am willing to reconsider my score based on the response by the authors.

2 comments
AuthorsOpenReview ↗

Follow-up on the revised manuscript

Thank you again for your detailed comments. Following our two earlier responses, we have uploaded the revised manuscript with updates to

  • Sections 3.1, 3.2: Introduction of the fitted bridge hth_t, explanation of the two-step acquisition rule (3.1), and discussion of how the variance of Gt,πG_{t,\pi} motivates its two components (3.2).
  • Section 5.1: An outline of the regret proof, including how the acquisition probability lower bound for policy-relevant outcomes controls inverse-probability terms.
  • Opening of Appendix B: An overview of how the hard-budget rule reserves budget for the minimum acquisition probability and controls the remaining spending over time.

If you have a chance to take another look, we would appreciate your thoughts.

Thank you for the clarifications. I will make sure to take your response into account during the reviewer deliberations.

Reviewer_aXVdOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The author(s) studies the contextual bandit problem with costly outcome observations and post-action surrogate. The authors proposes Audited Surrogate Bandit (ASB), which combines decision relevance and residual uncertainty to allocate a hard budget of primary-outcome acquisitions. The ASB method incurs O [\sqrt{KT \log N {1+\sqrt{T/B}}] regret relative to the best policy in a finite class of N policies over K actions, where B is the primary-outcome acquisition budget over TT rounds. pSynthetic experiments and a KuaiRec benchmark illustrate the benefits of the proposed algorithm.

Critical strengths
  1. The paper is well written. The problem considered in the paper is interesting. and clearly motivates the use of post-action information for measurement allocation.

  2. The paper provides clean end-to-end regret bounds for a hard-budget constraint, togetther with lower bounds and a clear separation showing superior performance over pre-surrogate acquisition policies.

  3. The authors tested ASB on KuaiRec recommendation data and compared it with relevance-only acquisition under different budgets. They found that the mean-regret gap first increased and then decreased as the budget grew.

Critical weaknesses
  1. The theoretical regret bounds are stated for a finite class of NN deterministic policies. Can you please discuss how these guarantees translate to infinite, parametric, or function-approximation-based policy classes (e.g., neural contextual bandits)?

  2. When the budget is very smal, how much does the minimum required chance of collecting measurements limit the post-surrogate method? Does this requirement increase regret when measurements are very expensive?

  3. The results on real-world data do not show whether the method works well with different policy types, different data, or real-world online systems.

Questions for authors

Please see the weaknesses noted above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.