Learning with Incomplete Context: Linear Contextual Bandits with Pretrained Imputation
This addresses the challenge of incomplete data in contextual bandits for applications like recommendation systems, though it is incremental by building on existing imputation and bandit methods.
The paper tackles the problem of online decision-making with partially observed contexts by incorporating pretrained models for imputation, achieving near-optimal performance with regret guarantees that decompose into standard bandit terms plus a component reflecting model quality.
The rise of large-scale pretrained models has made it feasible to generate predictive or synthetic features at low cost, raising the question of how to incorporate such surrogate predictions into downstream decision-making. We study this problem in the setting of online linear contextual bandits, where contexts may be complex, nonstationary, and only partially observed. In addition to bandit data, we assume access to an auxiliary dataset containing fully observed contexts--common in practice since such data are collected without adaptive interventions. We propose PULSE-UCB, an algorithm that leverages pretrained models trained on the auxiliary data to impute missing features during online decision-making. We establish regret guarantees that decompose into a standard bandit term plus an additional component reflecting pretrained model quality. In the i.i.d. context case with Hölder-smooth missing features, PULSE-UCB achieves near-optimal performance, supported by matching lower bounds. Our results quantify how uncertainty in predicted contexts affects decision quality and how much historical data is needed to improve downstream learning.