# Leveraging Good Representations in Linear Contextual Bandits

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 43 references that are in the map.
- First posted on arXiv 8 Apr 2021.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (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)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [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)
- [OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits](https://mlsanity.com/paper/1905.10040/) (2019)
- [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)
- [Corralling Stochastic Bandit Algorithms](https://mlsanity.com/paper/2006.09255/) (2020)
- [Regret Balancing for Bandit and RL Model Selection](https://mlsanity.com/paper/2006.05491/) (2020)
- [The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates](https://mlsanity.com/paper/1803.00316/) (2018)
- [Stochastic Linear Contextual Bandits with Diverse Contexts](https://mlsanity.com/paper/2003.02681/) (2020)
- [Rate-adaptive model selection over a collection of black-box contextual bandit algorithms](https://mlsanity.com/paper/2006.03632/) (2020)

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

- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization](https://mlsanity.com/paper/2111.13807/) (2021)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection](https://mlsanity.com/paper/2110.14798/) (2021)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Model Selection in Batch Policy Optimization](https://mlsanity.com/paper/2112.12320/) (2021)
- [Active Coverage for PAC Reinforcement Learning](https://mlsanity.com/paper/2306.13601/) (2023)
- [Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricing](https://mlsanity.com/paper/2309.08634/) (2023)
- [Adaptive Regularization of Representation Rank as an Implicit Constraint of Bellman Equation](https://mlsanity.com/paper/2404.12754/) (2024)
- [On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits](https://mlsanity.com/paper/2303.09390/) (2023)
- [Feature and Parameter Selection in Stochastic Linear Bandits](https://mlsanity.com/paper/2106.05378/) (2021)
- [Universal and data-adaptive algorithms for model selection in linear contextual bandits](https://mlsanity.com/paper/2111.04688/) (2021)
- [Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees](https://mlsanity.com/paper/2210.13083/) (2022)
- [Linear Contextual Bandits with Hybrid Payoff: Revisited](https://mlsanity.com/paper/2406.10131/) (2024)
- [Achieving Constant Regret in Linear Markov Decision Processes](https://mlsanity.com/paper/2404.10745/) (2024)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [Efficient Algorithms for Logistic Contextual Slate Bandits with Bandit Feedback](https://mlsanity.com/paper/2506.13163/) (2025)
- [Provable and Practical In-Context Policy Optimization for Self-Improvement](https://mlsanity.com/paper/2603.01335/) (2026)
- [Logistic Bandits with tildeO(√dT) Regret without Context Diversity Assumptions](https://mlsanity.com/paper/2604.22161/) (2026)
- [Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oracle](https://mlsanity.com/paper/2301.12571/) (2023)
- [Ranking with Popularity Bias: User Welfare under Self-Amplification Dynamics](https://mlsanity.com/paper/2305.18333/) (2023)
- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Invariance-Based Dynamic Regret Minimization](https://mlsanity.com/paper/2603.03843/) (2026)
- [Personalized Alignment Revisited: The Necessity and Sufficiency of User Diversity](https://mlsanity.com/paper/2605.09119/) (2026)
- [Set Membership Estimation for Stochastic Linear Contextual Bandits](https://mlsanity.com/paper/2606.20022/) (2026)
- [Contextual Slate GLM Bandits with Limited Adaptivity](https://mlsanity.com/paper/2606.31449/) (2026)

## Abstract (arXiv)

The linear contextual bandit literature is mostly focused on the design of efficient learning algorithms for a given representation. However, a contextual bandit problem may admit multiple linear representations, each one with different characteristics that directly impact the regret of the learning algorithm. In particular, recent works showed that there exist "good" representations for which constant problem-dependent regret can be achieved. In this paper, we first provide a systematic analysis of the different definitions of "good" representations proposed in the literature. We then propose a novel selection algorithm able to adapt to the best representation in a set of M candidates. We show that the regret is indeed never worse than the regret obtained by running LinUCB on the best representation (up to a ln M factor). As a result, our algorithm achieves constant regret whenever a "good" representation is available in the set. Furthermore, we show that the algorithm may still achieve constant regret by implicitly constructing a "good" representation, even when none of the initial representations is "good". Finally, we empirically validate our theoretical findings in a number of standard contextual bandit problems.