Reward Imputation with Sketching for Contextual Batched Bandits
This work addresses the underutilization of feedback in contextual batched bandits, an incremental improvement for sequential decision-making systems.
The paper tackles the problem of partial-information feedback in contextual batched bandits by proposing SPUIR, which imputes unobserved rewards using sketching to approximate full-information feedback, achieving a sublinear regret bound and outperforming state-of-the-art baselines on synthetic, benchmark, and real-world datasets.
Contextual batched bandit (CBB) is a setting where a batch of rewards is observed from the environment at the end of each episode, but the rewards of the non-executed actions are unobserved, resulting in partial-information feedback. Existing approaches for CBB often ignore the rewards of the non-executed actions, leading to underutilization of feedback information. In this paper, we propose an efficient approach called Sketched Policy Updating with Imputed Rewards (SPUIR) that completes the unobserved rewards using sketching, which approximates the full-information feedbacks. We formulate reward imputation as an imputation regularized ridge regression problem that captures the feedback mechanisms of both executed and non-executed actions. To reduce time complexity, we solve the regression problem using randomized sketching. We prove that our approach achieves an instantaneous regret with controllable bias and smaller variance than approaches without reward imputation. Furthermore, our approach enjoys a sublinear regret bound against the optimal policy. We also present two extensions, a rate-scheduled version and a version for nonlinear rewards, making our approach more practical. Experimental results show that SPUIR outperforms state-of-the-art baselines on synthetic, public benchmark, and real-world datasets.