New coding method makes online learning faster and more memory efficient
Bandits via Additive Quantized Representations
Machine Learning
Summary
Contextual bandits help computers learn to make decisions based on changing information but often need complex models that use lots of memory and time. The authors propose a new method called Residual Quantization (RQ) that turns continuous data into simpler coded pieces, allowing fast updates with much less memory. Their method keeps the power to understand complex patterns better than simpler models but without the heavy resource cost of more complicated techniques. Tests on many datasets show RQ beats similar methods and matches strong baselines while using far less memory.
What this means in practice
- •For online advertising teams: Build recommendation engines that update user preferences rapidly without needing large memory or retraining.$Commercial implications: Enables more efficient ad targeting systems that adapt quickly with low resource use, improving performance and cost-effectiveness.
- •For industrial control system developers: Implement adaptive control algorithms that adjust to nonlinear environments with limited onboard memory.
Authors
Ami Tavory, Noam Touitou, Tal Sarig, Frank Cheng, Ido Guy
Abstract
Contextual bandits require balancing nonlinear reward modeling with online efficiency. Tree ensembles and neural methods 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 multiple 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 using up to 1000 times less memory.