# On the Complexity of Representation Learning in Contextual Linear Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 33 references that are in the map.
- First posted on arXiv 19 Dec 2022.

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

- [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)
- [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)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Exploration in Structured Reinforcement Learning](https://mlsanity.com/paper/1806.00775/) (2018)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [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)
- [Structure Adaptive Algorithms for Stochastic Bandits](https://mlsanity.com/paper/2007.00969/) (2020)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality](https://mlsanity.com/paper/2006.08754/) (2020)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [Feature and Parameter Selection in Stochastic Linear Bandits](https://mlsanity.com/paper/2106.05378/) (2021)
- [Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees](https://mlsanity.com/paper/2210.13083/) (2022)

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

- [Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oracle](https://mlsanity.com/paper/2301.12571/) (2023)
- [Personalized Alignment Revisited: The Necessity and Sufficiency of User Diversity](https://mlsanity.com/paper/2605.09119/) (2026)

## Abstract (arXiv)

In contextual linear bandits, the reward function is assumed to be a linear combination of an unknown reward vector and a given embedding of context-arm pairs. In practice, the embedding is often learned at the same time as the reward vector, thus leading to an online representation learning problem. Existing approaches to representation learning in contextual bandits are either very generic (e.g., model-selection techniques or algorithms for learning with arbitrary function classes) or specialized to particular structures (e.g., nested features or representations with certain spectral properties). As a result, the understanding of the cost of representation learning in contextual linear bandit is still limited. In this paper, we take a systematic approach to the problem and provide a comprehensive study through an instance-dependent perspective. We show that representation learning is fundamentally more complex than linear bandits (i.e., learning with a given representation). In particular, learning with a given set of representations is never simpler than learning with the worst realizable representation in the set, while we show cases where it can be arbitrarily harder. We complement this result with an extensive discussion of how it relates to existing literature and we illustrate positive instances where representation learning is as complex as learning with a fixed representation and where sub-logarithmic regret is achievable.