MLA-UCB Improves Multi-Armed Bandits with Generated Surrogates

The authors introduce `MLA-UCB`, a machine learning-assisted variant of the classic Multi-Armed Bandits framework that uses pre-trained ML models to produce surrogate rewards from offline side information. The paper proves regret improvements under joint Gaussian assumptions and provides extensions for batched feedback and non-Gaussian observations, while requiring no prior knowledge of the covariance between surrogate and true rewards.

`MLA-UCB` wraps any reward prediction model and augments the standard UCB exploration rule with confidence bounds that account for surrogate-target uncertainty. Key algorithmic properties include:

• •Applicability to any offline reward predictor and arbitrary auxiliary data sources
• •Provable cumulative regret improvement when predicted and true rewards are jointly Gaussian, even if surrogate means misalign with true means
• •No requirement for prior knowledge of the covariance matrix between surrogate and true rewards
• •A batched-feedback extension that handles multiple observations per pull and non-Gaussian rewards with computable confidence bounds

The paper derives bounds in the Gaussian case and computable confidence bounds for the batched, non-Gaussian setting. Empirical evaluation uses both synthetic Gaussian surrogates and ML-generated surrogates, plus real-world tests in language model selection and video recommendation showing consistent regret reductions with moderate offline sample sizes and modest surrogate-target correlations.

This work formalizes a common practical workflow: using offline ML models to warm-start online bandit problems. By giving a theoretically-grounded way to exploit biased ML predictions while controlling exploration, the paper connects counterfactual/offline learning ideas with classic sequential decision theory. The no-covariance requirement and batched extensions make the approach broadly applicable to production settings where full statistical characterization of predictors is unavailable. For practitioners, the result means safer, provable gains from using historical models to accelerate exploration in recommender systems, A/B testing, and model selection.

Validate MLA-UCB on larger-scale, nonstationary deployments and quantify sensitivity to surrogate bias and unmodeled heteroskedasticity. Practical adoption will hinge on easy-to-compute confidence terms and robustness to heavy-tailed reward noise.