# Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees

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

## Key facts

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

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networks](https://mlsanity.com/paper/1312.6211/) (2013)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Self-Supervised Representation Learning: Introduction, Advances and Challenges](https://mlsanity.com/paper/2110.09327/) (2021)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach](https://mlsanity.com/paper/2202.00063/) (2022)
- [A Survey on Practical Applications of Multi-Armed and Contextual Bandits](https://mlsanity.com/paper/1904.10040/) (2019)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Online Model Selection for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2011.09750/) (2020)
- [Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits](https://mlsanity.com/paper/2006.02612/) (2020)
- [An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits](https://mlsanity.com/paper/2010.12247/) (2020)
- [Regret Balancing for Bandit and RL Model Selection](https://mlsanity.com/paper/2006.05491/) (2020)
- [Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection](https://mlsanity.com/paper/2110.14798/) (2021)
- [Self-Supervised Contextual Bandits in Computer Vision](https://mlsanity.com/paper/2003.08485/) (2020)

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

- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [State Representations as Incentives for Reinforcement Learning Agents: A Sim2Real Analysis on Robotic Grasping](https://mlsanity.com/paper/2309.11984/) (2023)
- [Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oracle](https://mlsanity.com/paper/2301.12571/) (2023)
- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Infrequent Exploration in Linear Bandits](https://mlsanity.com/paper/2510.26000/) (2025)

## Abstract (arXiv)

We study the problem of representation learning in stochastic contextual linear bandits. While the primary concern in this domain is usually to find realizable representations (i.e., those that allow predicting the reward function at any context-action pair exactly), it has been recently shown that representations with certain spectral properties (called HLS) may be more effective for the exploration-exploitation task, enabling LinUCB to achieve constant (i.e., horizon-independent) regret. In this paper, we propose BanditSRL, a representation learning algorithm that combines a novel constrained optimization problem to learn a realizable representation with good spectral properties with a generalized likelihood ratio test to exploit the recovered representation and avoid excessive exploration. We prove that BanditSRL can be paired with any no-regret algorithm and achieve constant regret whenever an HLS representation is available. Furthermore, BanditSRL can be easily combined with deep neural networks and we show how regularizing towards HLS representations is beneficial in standard benchmarks.