[2510.09908] Learning with Incomplete Context: Linear Contextual Bandits with Pretrained Imputation

Statistics > Machine Learning arXiv:2510.09908 (stat) [Submitted on 10 Oct 2025 (v1), last revised 1 Apr 2026 (this version, v3)] Title:Learning with Incomplete Context: Linear Contextual Bandits with Pretrained Imputation Authors:Hao Yan, Heyan Zhang, Yongyi Guo View a PDF of the paper titled Learning with Incomplete Context: Linear Contextual Bandits with Pretrained Imputation, by Hao Yan and 2 other authors View PDF HTML (experimental) Abstract: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 predi...