# Reward Imputation with Sketching for Contextual Batched Bandits

arXiv: https://arxiv.org/abs/2210.06719 · HTML: https://mlsanity.com/paper/2210.06719/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 36 references that are in the map.
- First posted on arXiv 13 Oct 2022.

## Builds on (most cited first, 17 of 17)

- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Inference for Batched Bandits](https://mlsanity.com/paper/2002.03217/) (2020)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Impact of Representation Learning in Linear Bandits](https://mlsanity.com/paper/2010.06531/) (2020)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2002.00287/) (2020)
- [A Reinforcement Learning System to Encourage Physical Activity in Diabetes Patients](https://mlsanity.com/paper/1605.04070/) (2016)
- [Improved Algorithm on Online Clustering of Bandits](https://mlsanity.com/paper/1902.09162/) (2019)
- [Balanced Linear Contextual Bandits](https://mlsanity.com/paper/1812.06227/) (2018)
- [Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2008.11918/) (2020)
- [Batched Neural Bandits](https://mlsanity.com/paper/2102.13028/) (2021)
- [Online learning with kernel losses](https://mlsanity.com/paper/1802.09732/) (2018)
- [Online Batch Decision-Making with High-Dimensional Covariates](https://mlsanity.com/paper/2002.09438/) (2020)

## Built on by (most cited first, 5 of 5)

- [KuaiLive: A Real-time Interactive Dataset for Live Streaming Recommendation](https://mlsanity.com/paper/2508.05633/) (2025)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Revisiting Clustering of Neural Bandits: Selective Reinitialization for Mitigating Loss of Plasticity](https://mlsanity.com/paper/2506.12389/) (2025)
- [Enhancing Bandit Algorithms with LLMs for Time-varying User Preferences in Streaming Recommendations](https://mlsanity.com/paper/2602.08067/) (2026)
- [Fast Second-Order Online Kernel Learning through Incremental Matrix Sketching and Decomposition](https://mlsanity.com/paper/2410.11188/) (2024)

## Abstract (arXiv)

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.