# Misspecified Linear Bandits

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2017.

## Built on by (most cited first, 30 of 42)

- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles](https://mlsanity.com/paper/2102.13240/) (2021)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [On component interactions in two-stage recommender systems](https://mlsanity.com/paper/2106.14979/) (2021)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Online Clustering of Bandits with Misspecified User Models](https://mlsanity.com/paper/2310.02717/) (2023)
- [Online Markov Decision Processes with Aggregate Bandit Feedback](https://mlsanity.com/paper/2102.00490/) (2021)
- [On the Model-Misspecification in Reinforcement Learning](https://mlsanity.com/paper/2306.10694/) (2023)
- [Large Language Model-Enhanced Multi-Armed Bandits](https://mlsanity.com/paper/2502.01118/) (2025)
- [Improved Algorithms for Misspecified Linear Markov Decision Processes](https://mlsanity.com/paper/2109.05546/) (2021)
- [On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits](https://mlsanity.com/paper/2303.09390/) (2023)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [Optimistic Task Inference for Behavior Foundation Models](https://mlsanity.com/paper/2510.20264/) (2025)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [Dealing with Expert Bias in Collective Decision-Making](https://mlsanity.com/paper/2106.13539/) (2021)
- [Robust Contextual Linear Bandits](https://mlsanity.com/paper/2210.14483/) (2022)
- [Robust Causal Bandits for Linear Models](https://mlsanity.com/paper/2310.19794/) (2023)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)
- [Linear Bandits with Partially Observable Features](https://mlsanity.com/paper/2502.06142/) (2025)
- [Turning Bias into Bugs: Bandit-Guided Style Manipulation Attacks on LLM Judges](https://mlsanity.com/paper/2605.26156/) (2026)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [No-Regret Linear Bandits beyond Realizability](https://mlsanity.com/paper/2302.13252/) (2023)
- [CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption](https://mlsanity.com/paper/2309.16563/) (2023)

## Abstract (arXiv)

We consider the problem of online learning in misspecified linear stochastic multi-armed bandit problems. Regret guarantees for state-of-the-art linear bandit algorithms such as Optimism in the Face of Uncertainty Linear bandit (OFUL) hold under the assumption that the arms expected rewards are perfectly linear in their features. It is, however, of interest to investigate the impact of potential misspecification in linear bandit models, where the expected rewards are perturbed away from the linear subspace determined by the arms features. Although OFUL has recently been shown to be robust to relatively small deviations from linearity, we show that any linear bandit algorithm that enjoys optimal regret performance in the perfectly linear setting (e.g., OFUL) must suffer linear regret under a sparse additive perturbation of the linear model. In an attempt to overcome this negative result, we define a natural class of bandit models characterized by a non-sparse deviation from linearity. We argue that the OFUL algorithm can fail to achieve sublinear regret even under models that have non-sparse deviation.We finally develop a novel bandit algorithm, comprising a hypothesis test for linearity followed by a decision to use either the OFUL or Upper Confidence Bound (UCB) algorithm. For perfectly linear bandit models, the algorithm provably exhibits OFULs favorable regret performance, while for misspecified models satisfying the non-sparse deviation property, the algorithm avoids the linear regret phenomenon and falls back on UCBs sublinear regret scaling. Numerical experiments on synthetic data, and on recommendation data from the public Yahoo! Learning to Rank Challenge dataset, empirically support our findings.