Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Bandits via Additive Quantized Representations

NeurIPS 2026 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Oracle-efficient contextual bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Repurposes residual quantization codebooks (trained offline by k-means) as a fixed-memory nonlinear representation for contextual bandits, with gradient-boosted per-level learners and shadow-based depth promotion.

Problem

Contextual bandits need nonlinear reward modeling with online efficiency and bounded memory; tree/neural methods require retraining on growing replay buffers while linear bandits cannot model nonlinear rewards.

Approach

Use an offline-trained residual quantization codebook to map contexts to discrete centroid codes across levels, and fit per-level bandit learners (count/sum, diagonal linear, or full LinTS) to residual pseudo-targets in a gradient-boosting-style cascade, with a shadow model that decides online whether to add depth.

Key results

• RQ variants beat their non-RQ counterparts on 11 of 13 datasets (LinTS-RQ 10W/1L/2T vs LinTS; SGD-RQ 12W/1L vs SGD-LinTS; TS-RQ 11W/2L vs TS).
• LinTS-RQ vs Doubling-XGB is 7W/4L/2T while using 620 KB vs XGB's 1.1 GB replay buffer at T=5M on higgs.
• LinTS-RQ beats TabNet-LinTS on 11 of 13 datasets (11W/2L).

Surprising findings

• SGD-LinTS performs worse than context-free TS on datasets with low effective rank (skin_segmentation, miniboone).
• LinTS-RQ degrades on year_prediction even at depth 1 due to data sparsity (N/(bKd^2)=0.04).

Limitations

• LinTS-RQ fails when data per parameter is insufficient (N/(bKd^2) small), e.g., year_prediction.
• Linear variants use squared loss for binary rewards.
• Codebook is trained by unsupervised k-means and requires an offline unlabeled holdout; may degrade in cold-start settings.

Experimental setup

Datasets: higgs susy covertype skin_segmentation miniboone hepmass year_prediction kddcup99

Benchmarks: 13 OpenML/UCI tabular datasets as supervised-to-bandit conversions

Metrics: normalized regret rate win/loss/tie with 95% CIs over 30 seeds memory

Baselines: TS SGD-LinTS LinTS Doubling-XGB Doubling-NeuralCB TabNet-LinTS

Builds on: LinTS LinUCB XGBoost TabNet Freedman's inequality

Closest papers by meaning

• Beyond task diversity: provable representation transfer for sequential multitask linear bandits (NeurIPS 2024 · similarity 0.88)
• Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees (NeurIPS 2022 · similarity 0.88)
• Impact of Representation Learning in Linear Bandits (ICLR 2021 · similarity 0.87)
• Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.86)
• Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Bandits (ICML 2024 · similarity 0.86)
• Diffusion Models Meet Contextual Bandits (NeurIPS 2025 · similarity 0.86)