# On The Statistical Complexity of Offline Decision-Making

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 62 references that are in the map.
- First posted on arXiv 10 Jan 2025.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Deep Reinforcement Learning for Dialogue Generation](https://mlsanity.com/paper/1606.01541/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (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)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [On the Theory of Transfer Learning: The Importance of Task Diversity](https://mlsanity.com/paper/2006.11650/) (2020)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [On the Value of Target Data in Transfer Learning](https://mlsanity.com/paper/2002.04747/) (2020)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Off-Policy Policy Gradient with State Distribution Correction](https://mlsanity.com/paper/1904.08473/) (2019)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Active Learning for Cost-Sensitive Classification](https://mlsanity.com/paper/1703.01014/) (2017)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond](https://mlsanity.com/paper/2401.03301/) (2024)
- [Efficient Online Learning with Offline Datasets for Infinite Horizon MDPs: A Bayesian Approach](https://mlsanity.com/paper/2310.11531/) (2023)

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

- [Online Optimization for Offline Safe Reinforcement Learning](https://mlsanity.com/paper/2510.22027/) (2025)
- [Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings](https://mlsanity.com/paper/2601.06505/) (2026)

## Abstract (arXiv)

We study the statistical complexity of offline decision-making with function approximation, establishing (near) minimax-optimal rates for stochastic contextual bandits and Markov decision processes. The performance limits are captured by the pseudo-dimension of the (value) function class and a new characterization of the behavior policy that strictly subsumes all the previous notions of data coverage in the offline decision-making literature. In addition, we seek to understand the benefits of using offline data in online decision-making and show nearly minimax-optimal rates in a wide range of regimes.