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

We study budget-constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. We adopt the standard realizability assumption: conditioned on the observed context, rewards and costs are drawn independently from fixed distributions whose expectations belong to known function classes. We focus on the continuing setting, in which the algorithm operates over the entire horizon even after the budget for cumulative cost is exhausted. In this setting, the objective is to simultaneously control regret and the violation of the budget constraint. Building on the seminal $\mathsf{SquareCB}$ framework of Foster et al. [2018], we propose a simple and modular framework that leverages online regression oracles to reduce the constrained problem to a standard unconstrained contextual bandit problem with adaptively defined surrogate reward functions. In contrast to prior works, which focus on stochastic contexts, our reduction yields improved guarantees for more general adversarial contexts, together with an efficient algorithm with a compact and transparent analysis.

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector $p$. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known $p$, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order $\sqrt{n/T \, \lVert p \rVert_{1/2}}$, whereas active sampling with allocation $q_j \propto p_j^{2/3}$ achieves the tight rate $\sqrt{n/T} \, \lVert p \rVert_{2/3}$. The resulting improvement can be as large as $Θ(k^{1/4})$, where $k$ is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When $p$ is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-$p$ active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Robust reinforcement learning typically assumes that feedback sources are either globally trustworthy or corrupted within a fixed global budget. We identify a more subtle failure mode that escapes this dichotomy, which we call \emph{Contextual Sycophancy}. In this failure, evaluators are truthful in benign contexts but systematically biased in critical ones, so that no single evaluator is reliable everywhere and the corrupt evaluators may form a \emph{majority} in the contexts that matter. Our first result is an information-theoretic lower bound. We exhibit two problem instances that induce \emph{identical} social-feedback distributions yet have disjoint optimal actions, proving that \emph{any} algorithm relying on social feedback alone (including any robust aggregator, regardless of breakdown point) incurs $Ω(T)$ latent regret. This shows that breaking contextual sycophancy is impossible without having some information. We then show that a sparse stream of ground-truth audits, available with probability $p_{\mathrm{aud}}$, is sufficient. We propose \ESA, which learns a per-evaluator contextual \emph{trust boundary} from audits and re-weights feedback accordingly, and we prove a high-probability latent-regret bound of $\tilde{\mathcal{O}}\!\big(\sqrt{T\,d_{VC}/p_{\mathrm{aud}}} + d\sqrt{T} + ε_{\mathrm{tol}}T\big)$, where $d_{VC}$ is the complexity of the adversary's bias strategy. The audit-dependence $1/\sqrt{p_{\mathrm{aud}}}$ matches the information-theoretic necessity of audits. Empirically, \ESA\ recovers the ground truth when $80\%$ of the social layer is adversarial, a regime in which median- and mean-based robust baselines fail.