Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards
Wenlong Ji, Yihan Pan, Ruihao Zhu, Lihua Lei · 2025
Read Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards by Wenlong Ji, Yihan Pan, Ruihao Zhu, Lihua Lei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16658.txt.
Introduction
Wenlong Ji and co-authors bring machine learning forecasts into bandit decision problems in a 2025 paper. A bandit problem asks a learner to pick among options again and again, learning which pays best from sparse live results. In many real settings, rich side data exist before any live trial, and a trained model can turn that data into forecast rewards.
Those forecasts can be biased, since they rest on guessing beyond past data. The authors' algorithm blends the forecasts with live results through a confidence method that needs no prior knowledge of how the two relate. Proofs show it cuts total regret even when the forecasts point the wrong way on average. Tests on model choice and video recommendation backed the math.
Catalog record
| CREATOR | Wenlong Ji, Yihan Pan, Ruihao Zhu, Lihua Lei |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-16658
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards Wenlong Ji, Yihan Pan, Ruihao Zhu, Lihua Lei Abstract Multi-armed bandit (MAB) is a widely adopted framework for sequential decision-making under uncertainty. Traditional bandit algorithms rely solely on online data, which tends to be scarce as it must be gathered during the online phase when the arms are actively pulled. However, in many practical settings, rich auxiliary data, such as covariates of past users, is available prior to deploying any arms. We introduce a new setting for MAB where pre-trained machine learning (ML) models are applied to convert side information and historical data into surrogate rewards . A prominent feature of this setting is that the surrogate rewards may exhibit substantial bias, as true reward data is typically unavailable in the offline phase, forcing ML predictions to heavily rely on extrapolation. To address the issue, we propose the Machine Learning-Assisted Upper Confidence Bound (MLA-UCB) algorithm, which can be applied to any reward prediction model and any form of auxiliary data. When the predicted and true rewards are jointly Gaussian, it provably improves the cumulative regret, provided that the correlation is non-zero – even in cases where the mean surrogate reward completely misaligns with the true mean rewards. Notably, our method requires no prior knowledge of the covariance matrix between true and surrogate rewards. We compare MLA-UCB with the standard UCB on a range of numerical studies and show a sizable efficiency gain even when the size of the offline data and the correlation between predicted and true rewards are moderate. † † We thank Emma Brunskill, Emmanuel Candès, Edward Malthouse, Art Owen, Jann Spiess, and Stefan Wager for their helpful comments. L.L. and W.J. are grateful for the support of the National Science Foundation grant DMS-2338464. 1 Introduction The multi-armed bandit (MAB) framework is a widely adopted framework for sequential and interactive decision-making under incomplete information. In the MAB setting, a decision maker interacts with an unknown environment by sequentially selecting from a pre-specified set of actions (a.k.a. pulling arms). Each selected action yields a random reward from an action-dependent distribution that is unknown to the decision maker. A common objective is to choose actions to maximize cumulative rewards over time or to minimize cumulative regret, defined as the loss incurred from not always selecting the ex-post optimal action. For example, a pharmaceutical company could apply an MAB framework to more efficiently identify the most effective drugs and dosages in clinical trials villar2015multi ; aziz2021multi , while minimizing risk to participants. Similarly, online news vendors deploy MAB algorithms to continuously refine content recommendations and enhance user engagement in real time ( li2010acontextual ; coenen2019nyt ; su2024exploration ) . At the heart of the MAB problem lies the exploration-exploitation trade-off – the decision maker must explore different actions sufficiently to discover the most rewarding one, while also feeling the pull to exploit the current best arm to maximize immediate gains. Many algorithms have been developed to address the trade-off, typified by the upper confidence bound (UCB) algorithm ( auer2002finite ) and the Thompson sampling ( agrawal2012analysis ; russo2018tutorial ) , both of which provably achieve favorable regret bounds in the long run (e.g., lattimore2020bandit ). Despite the appealing theoretical guarantees, most existing algorithms operate solely in the online phase where the decision maker is actively pulling arms, without taking advantage of offline/historical data that is prevalent in practice. Although rewards are not directly observable in the offline phase before an arm is pulled, other variables may be informative about the reward distributions. To extract information, we can leverage machine learning algorithms, including pre-trained AI models like large language models (LLMs), to convert these offline variables into surrogate rewards . If ML-generated surrogate rewards are correlated with unrealized true rewards through the input to the ML model, they have the potential to reduce regret even in the early stage by increasing the effective number of pulls. For example, in a clinical trial where the primary endpoint takes time to measure, such as five-year survival, the researcher can predict the long-term outcome using patient data from other trials and use the ML predictions as the surrogate rewards. Similarly, an online retailer can feed consumer profiles into LLMs to simulate purchasing behavior under the current marketing strategy or recommendation system, thereby obtaining surrogate rewards. As ML-generated surrogate rewards are much less expensive to acquire, it is tempting to use them in place of the costly true rewards to guide arm ranking. For example, the decision maker can pick – or at least prioritize — the best arms based on the mean surrogate rewards for each arm computed solely on offline data. However, this approach is ineffective unless the mean surrogate rewards preserve the ranking of the true mean rewards, an assumption that is unrealistic in most applications. In fact, most MAB applications aim to test new treatments and interventions that do not appear in historical data, and thus ML-generated surrogate rewards must rely on extrapolation to unseen environments. To provide context, we describe how to apply ML algorithms to generate surrogate rewards in two scenarios. • (Surrogate rewards for parametrizable arms) When the arms correspond to new values of tuning parameters of a pricing or recommendation algorithm, and multiple values have been deployed in the past, a reward model can be fit jointly on user features and the parameter values using offline data. Such models enable extrapolation to generate arm-specific surrogate rewards for each unseen arm in the online phase. Nonetheless, the new values are often distant from the previous ones or even lie outside their convex hull. In such cases, the mean surrogate rewards may substantially misalign with the true mean rewards. • (One-size-fits-all surrogate rewards) When the arms cannot be naturally parametrized and no similar arm has been deployed before, a reward model can be trained solely on user features under the status quo treatment. Such models produce the same surrogate rewards for all arms in the online phase. By definition, it is unable to inform the ranking of arms. In either of the above scenarios, the ML-generated surrogate rewards are inaccurate and untrustworthy. On the other hand, if the true rewards are not statistically independent of input to the ML models (e.g., user features) that generate surrogate rewards, they are typically correlated with the surrogate rewards. Motivated by these practical considerations, we focus on the setting where the surrogate rewards are correlated with the true rewards, but their means may be arbitrarily misaligned. Importantly, we require the surrogate rewards to be computable for all experimental units – both offline and online – allowing joint observation of the surrogate and true rewards for online units. This joint observability is essential for debiasing the surrogate rewards and leveraging their correlation with the true rewards. We argue that this is not a restrictive assumption, as it clearly holds in both aforementioned scenarios. 1.1 Main Contributions We begin by introducing the setting of MAB with ML-generated surrogate rewards, which is relevant to a wide range of applications. In this new setting, we propose the Machine Learning-Assisted Upper Confidence Bound (MLA-UCB) algorithm that combine the online true rewards with ML-generated surrogate rewards for both offline and online units. MLA-UCB