# Tractable contextual bandits beyond realizability

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- First posted on arXiv 25 Oct 2020.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

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

- [Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits](https://mlsanity.com/paper/2106.02029/) (2021)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles](https://mlsanity.com/paper/2102.13240/) (2021)
- [On component interactions in two-stage recommender systems](https://mlsanity.com/paper/2106.14979/) (2021)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)
- [Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective](https://mlsanity.com/paper/2106.06483/) (2021)
- [Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions](https://mlsanity.com/paper/2601.15353/) (2026)
- [No-Regret Linear Bandits beyond Realizability](https://mlsanity.com/paper/2302.13252/) (2023)

## Abstract (arXiv)

Tractable contextual bandit algorithms often rely on the realizability assumption - i.e., that the true expected reward model belongs to a known class, such as linear functions. In this work, we present a tractable bandit algorithm that is not sensitive to the realizability assumption and computationally reduces to solving a constrained regression problem in every epoch. When realizability does not hold, our algorithm ensures the same guarantees on regret achieved by realizability-based algorithms under realizability, up to an additive term that accounts for the misspecification error. This extra term is proportional to T times a function of the mean squared error between the best model in the class and the true model, where T is the total number of time-steps. Our work sheds light on the bias-variance trade-off for tractable contextual bandits. This trade-off is not captured by algorithms that assume realizability, since under this assumption there exists an estimator in the class that attains zero bias.