A recommendation platform that wants to learn which option is best must get some people to try options that look worse right now. When the people acting are self-interested, they ignore any recommendation they suspect is an experiment. The theory of incentivized exploration shows that a platform can still explore without paying anyone. It does this by mixing exploratory recommendations into a stream that is accurate on average, so that following the recommendation stays the best bet for each user. The platform "spends" the information advantage it has built up over users. There is a catch at the start of learning. A new platform knows nothing users don't, so it has no advantage to spend. Every existing guarantee therefore assumes an initial warm-up phase in which data is gathered with no incentive constraint, through paid trials, subsidies, or altruistic early adopters, and these warm-ups can be long.
This note proposes that the warm-up can often be replaced by data the platform already holds from related past tasks: other markets, other product categories, other patient subpopulations. Users do not see this data. If it predicts the new task's rewards, it gives the platform an information advantage at round one, a "borrowed surplus" that can hide exploration from the first user onward. The difficulty is that borrowed knowledge can be wrong, as when tasks are dissimilar, and incentive guarantees are notoriously fragile to wrong beliefs. The research question is how much exploration past tasks can safely buy, and how to spend it so that compliance survives disagreement about how similar the tasks are.
Core Claim
The standard compliance requirement, Bayesian incentive compatibility (BIC), says that a user who knows the prior and the platform's recommendation policy, but not its data, should prefer the recommended action to every alternative. Today this is checked only against data from the current task. We extend the platform's private information to include a source-task dataset $S$. The condition becomes
$$\mathbb{E}_{\mu}\big[R(a) - R(a') \,\big|\, \pi(S, H_t) = a\big] \ge 0 \quad \text{for all actions } a, a',$$
where $\mu$ is a joint prior over source and target rewards, $H_t$ is the target-task history at round $t$ (empty at $t=1$), $\pi$ is the recommendation policy, and $R$ is the target reward. Under a hierarchical prior in which a similarity parameter $\rho$ governs how strongly $S$ predicts target rewards, the expected gap between the action $S$ favors and the others is strictly positive at $t=1$ whenever $\rho$ is bounded away from zero. That positive gap is a budget for hidden exploration that exists before any target data.
The new ingredient is robustness to $\rho$. Users may not share the platform's belief about task similarity, and at $\rho = 0$ the borrowed surplus vanishes. We therefore require the condition to hold for every $\rho$ in an agreed set $[\rho_{\min}, \rho_{\max}]$. Our main conjecture is that the exploration probability affordable at round one scales with the surplus evaluated at $\rho_{\min}$. This yields a clean statement: past tasks shorten the unconstrained warm-up exactly to the extent that users agree they are informative. We expect the shortening to be zero if users grant no similarity, and in favorable regimes we expect the warm-up to be eliminated entirely.
Relation to Prior Work
Several papers supply the incentive mechanism and also motivate the gap, because they leave the warm-up untouched. Mansour et al. convert any bandit algorithm into a BIC one at a constant-factor regret cost, but they need an initial surplus. The random-routing analysis of Dai et al. shows that exploration can be hidden with probability up to a surplus-determined threshold. We reuse that pooling device and change where the surplus comes from.
Four results show that posterior sampling becomes compliant once enough seed data exists. Hu et al. require this in combinatorial settings, Sellke after $\tilde{O}(d^4/\epsilon^2)$ dispersed samples in linear settings, and Kalvit et al. after a warm-up of spectral diversity $\Omega(1/\epsilon^2)$. Li et al. give a two-stage design whose hidden cold-start phase grows as $O(K^3/\epsilon^2)$ in the number of arms $K$. In all four papers the seed data must come from outside the incentive constraint. We ask whether it can come from other tasks instead.
Schiffer et al. remove exponential burn-in by exploiting the curvature of a ball-shaped action set. Our route is orthogonal, since it uses side information rather than geometry, and it applies to finite arm sets where their argument does not.
Two papers constrain the design. Sellke proves that compliance can hold at round one and fail at round two under correlated beliefs. A prior built from past tasks is a correlated prior, so we must check compliance at every round, not just at the start. Wang et al. show that when users know more than the platform, payments never stop. This tells us not to oversell borrowed surplus when users hold private context, and we restrict to settings without that gap.
From cold-start Bayesian optimization we borrow the robustness machinery. Dai et al. weight past-task models adaptively so that dissimilar tasks cannot prevent convergence. Qu et al. decay an expert prior mean over iterations. Hvarfner et al. choose initial queries by information value instead of space-filling. None of these models user compliance. Our contribution is to make their weights and decay subject to a per-round incentive check, and to use information value to decide which exploratory arm to hide inside the budget. Feurer et al. and Sharaf & Daumé III show that meta-features of past tasks predict good starting choices. That is evidence the borrowed signal is often real, but neither paper treats it as an incentive resource.
Research Program
The theoretical part fixes a Gaussian hierarchical model. Target arm means equal $\rho$ times the matching source means plus independent noise, and $\rho$ has a prior on $[\rho_{\min}, \rho_{\max}]$. In this model the round-one surplus has a closed form. We will derive the largest hiding probability $\gamma_1$ that keeps the condition above for all $\rho$ in the set. We will then prove that a policy which recomputes $\gamma_t$ from the joint posterior each round stays compliant. This directly answers Sellke's instability result, because compliance is enforced round by round rather than inherited. Finally, we will bound the number of target rounds before ordinary posterior sampling becomes compliant on its own. We expect this bound to be the existing seed requirement minus an effective sample count contributed by $S$, measured as source sample size times $\rho_{\min}^2$. That form comes from Gaussian conjugacy, where a source observation acts like a target observation down-weighted by squared correlation.
The algorithmic part builds three things: a robust weighting of past tasks in the style of Dai et al.; the per-round surplus computation, done exactly for Gaussian models and by Monte Carlo otherwise; and a choice rule that spends the hiding probability on the arm with the highest expected information gain about target rewards.
Baselines
The naive reference point is the standard-of-care rule that always recommends the a priori best arm. It never explores, so it is trivially compliant. Any method must beat its long-run regret while matching its zero violation rate.
The strongest existing method on finite arms with covariates is the two-stage mechanism of Li et al., which is the only cited work that reports a number on our main benchmark. On PharmGKB warfarin dosing, it reports a weighted risk score of 0.291 against 0.20 for the medium-dose standard of care, with extreme errors held to 2%. The file does not state the direction of the score, so we will recompute both under their stated protocol before claiming improvement. We run it with the same patients, arm set and compliance tolerance $\epsilon$. It is granted its full unconstrained cold-start stage, and that stage's length and cost are reported as a cost.
The second strong baseline is a combination of the cited seed-then-sample approaches Hu et al. and Kalvit et al.. It collects the required warm-up with paid exploration and then switches to posterior sampling.
Two ablations isolate our ingredients. In the first, the identical hierarchical posterior feeds plain posterior sampling with no robust surplus check, which isolates the per-round check. In the second, the surplus check is computed at the platform's point estimate of $\rho$ instead of at $\rho_{\min}$, which isolates robustness to similarity disagreement.
All methods share the same data splits, the same posterior model class and the same hyperparameter-tuning budget per method, chosen on held-out source tasks only. Beating a baseline means equal or lower compliance-violation rate, together with strictly fewer unconstrained or paid rounds or lower regret at equal violation rate.
Why not just…?
Why not just pay users during the warm-up? Payments are often unavailable. Bahar et al. formalize clinical settings where inducing patients into untested treatments breaches fiduciary duty. Where payments are allowed, they are a cost we can count. We report the payment total the seed-then-sample baseline needs and the fraction our method removes, so the trade-off is explicit rather than assumed.
Why not just treat past-task data as seed samples and run Thompson sampling? This is the real threat, and it is our first ablation. Under a correct hierarchical prior, plain posterior sampling conditioned on $S$ might already be compliant from round one, and our contribution would shrink to a characterization of when that happens. We expect it to fail in two places: when $\rho$ is moderate, so that source data shrinks but does not concentrate the target posterior, and when users' similarity belief is below the platform's. The violation rate of the ablation, measured exactly in simulation under $\rho_{\min}$, settles this. If it is near zero across regimes, we will reframe the work as the effective-sample-size theorem alone.
Why not just use a Sobol or random warm-up and then turn on a compliant policy? Space-filling points ignore user utility, so users would reject them unless paid. Hvarfner et al. also show such designs calibrate models poorly in high dimensions. We include this as a paid-warm-up variant and compare regret and payments.
Why not just plug in a fixed expert or transferred prior? Dai et al. and Qu et al. show that fixed priors get stuck under negative transfer. In our setting the failure is worse: an overconfident prior manufactures a surplus that does not exist, so users are misled. Our adversarial-source experiments test exactly this.
Proposed Experiments
The first testbed is synthetic Gaussian linear bandits in the style of Schiffer et al., using finite arm sets so their geometric bootstrap does not apply. We control the true $\rho$, $\rho_{\min}$, source sample size and dimension. Because the prior is known in simulation, compliance can be checked exactly. The decisive check is whether the measured warm-up reduction tracks source size times $\rho_{\min}^2$, and whether it falls to zero when $\rho_{\min} = 0$.
The second testbed is PharmGKB warfarin dosing (5,528 patients, three dose arms), split into covariate-defined subpopulations that serve alternately as source and target. We report risk score, extreme-error rate, compliance-violation rate under the fitted prior, and unconstrained rounds used, compared against the Li et al. number above.
The third testbed is the 300 OpenML binary classification datasets converted to contextual bandits, following Sharaf & Daumé III. Each target dataset uses the others as sources, with meta-feature similarity as in Feurer et al.. That paper reports relative reward of 1.0 on over 40% of datasets versus about 30% for the best classical heuristics. We compare at matched compliance, noting that their method imposes no compliance constraint.
The negative-transfer stress test deliberately pairs dissimilar tasks: random OpenML pairs, and mismatched warfarin subgroups. It passes if our violation rate stays within $\epsilon$ while the point-estimate ablation exceeds it.
References
- Bayesian Incentive-Compatible Bandit Exploration
- Incentive-Aware Recommender Systems in Two-Sided Markets
- Incentivizing Combinatorial Bandit Exploration
- Incentivizing Exploration with Linear Contexts and Combinatorial Actions
- Incentivized Exploration via Filtered Posterior Sampling
- Incentivized Exploration with Stochastic Covariates: A Two-Stage Mechanism Design for Recommender System
- Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts
- Incentivizing Exploration in Linear Contextual Bandits under Information Gap
- On Provably Robust Meta-Bayesian Optimization
- Incorporating Expert Priors into Bayesian Optimization via Dynamic Mean Decay
- Informed Initialization for Bayesian Optimization and Active Learning
- Initializing Bayesian Hyperparameter Optimization via Meta-Learning
- Meta-Learning for Contextual Bandit Exploration
- Fiduciary Bandits