# Pessimism for Offline Linear Contextual Bandits using ℓp Confidence Sets

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 47 references that are in the map.
- First posted on arXiv 21 May 2022.

## Builds on (most cited first, 30 of 36)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction](https://mlsanity.com/paper/1906.00949/) (2019)
- [Behavior Regularized Offline Reinforcement Learning](https://mlsanity.com/paper/1911.11361/) (2019)
- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [MOReL : Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2005.05951/) (2020)
- [A Survey of Autonomous Driving: Common Practices and Emerging Technologies](https://mlsanity.com/paper/1906.05113/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialog](https://mlsanity.com/paper/1907.00456/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Adversarially Trained Actor Critic for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02446/) (2022)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Provably Good Batch Reinforcement Learning Without Great Exploration](https://mlsanity.com/paper/2007.08202/) (2020)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL](https://mlsanity.com/paper/2012.08005/) (2020)

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

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Bandits](https://mlsanity.com/paper/2306.07923/) (2023)
- [Importance-Weighted Offline Learning Done Right](https://mlsanity.com/paper/2309.15771/) (2023)
- [Differentially Private Reward Estimation with Preference Feedback](https://mlsanity.com/paper/2310.19733/) (2023)
- [Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage](https://mlsanity.com/paper/2302.02392/) (2023)
- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits](https://mlsanity.com/paper/2502.06051/) (2025)
- [Multi-Task Off-Policy Learning from Bandit Feedback](https://mlsanity.com/paper/2212.04720/) (2022)
- [Hybrid Preference Optimization for Alignment: Provably Faster Convergence Rates by Combining Offline Preferences with Online Exploration](https://mlsanity.com/paper/2412.10616/) (2024)
- [Balancing optimism and pessimism in offline-to-online learning](https://mlsanity.com/paper/2502.08259/) (2025)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Unified Off-Policy Learning to Rank: a Reinforcement Learning Perspective](https://mlsanity.com/paper/2306.07528/) (2023)
- [Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysis](https://mlsanity.com/paper/2505.13768/) (2025)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)
- [Hybrid Combinatorial Multi-armed Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2512.21925/) (2025)
- [Group-Sensitive Offline Contextual Bandits](https://mlsanity.com/paper/2510.27123/) (2025)
- [Unlearning Offline Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2605.00638/) (2026)
- [Offline-to-Online Learning in Linear Bandits](https://mlsanity.com/paper/2606.04305/) (2026)

## Abstract (arXiv)

We present a family hatπp≥ 1 of pessimistic learning rules for offline learning of linear contextual bandits, relying on confidence sets with respect to different ℓp norms, where hatπ2 corresponds to Bellman-consistent pessimism (BCP), while hatπ_∞ is a novel generalization of lower confidence bound (LCB) to the linear setting. We show that the novel hatπ_∞ learning rule is, in a sense, adaptively optimal, as it achieves the minimax performance (up to log factors) against all ℓq-constrained problems, and as such it strictly dominates all other predictors in the family, including hatπ2.