Bandits via Additive Quantized Representations

Contextual bandits require balancing nonlinear reward modeling with online efficiency. Tree ensembles capture nonlinearities but require periodic retraining and large replay buffers. Linear models update efficiently per observation with $O(1)$ memory, but are fundamentally restricted to linear reward structures. We propose Residual Quantization (RQ) as a representation layer to bridge this gap. An offline-trained RQ codebook maps continuous contexts into discrete centroid assignments across $\ell$ levels, set dynamically through a shadow mechanism. This enables a spectrum of additive bandit algorithms that achieve nonlinear expressivity with strictly bounded memory. Across 13 datasets, RQ variants beat their non-RQ counterparts on 11 of 13 datasets, often by wide margins, while matching doubling-retrain XGBoost and neural baselines at up to $1000\times$ less memory.