# On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 7 of its 21 references that are in the map.
- First posted on arXiv 3 Jan 2025.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

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

- [Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods](https://mlsanity.com/paper/1910.09457/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Deep Reinforcement Learning for Page-wise Recommendations](https://mlsanity.com/paper/1805.02343/) (2018)
- [Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning](https://mlsanity.com/paper/1909.05850/) (2019)
- [Off-Policy Deep Reinforcement Learning by Bootstrapping the Covariate Shift](https://mlsanity.com/paper/1901.09455/) (2019)
- [Q-Learning in Regularized Mean-field Games](https://mlsanity.com/paper/2003.12151/) (2020)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)

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

- [A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory](https://mlsanity.com/paper/2508.07746/) (2025)

## Abstract (arXiv)

This article reviews the recent advances on the statistical foundation of reinforcement learning (RL) in the offline and low-adaptive settings. We will start by arguing why offline RL is the appropriate model for almost any real-life ML problems, even if they have nothing to do with the recent AI breakthroughs that use RL. Then we will zoom into two fundamental problems of offline RL: offline policy evaluation (OPE) and offline policy learning (OPL). It may be surprising to people that tight bounds for these problems were not known even for tabular and linear cases until recently. We delineate the differences between worst-case minimax bounds and instance-dependent bounds. We also cover key algorithmic ideas and proof techniques behind near-optimal instance-dependent methods in OPE and OPL. Finally, we discuss the limitations of offline RL and review a burgeoning problem of low-adaptive exploration which addresses these limitations by providing a sweet middle ground between offline and online RL.