# Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data

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

## Key facts

- Cited by 11 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 9 of its 40 references that are in the map.
- First posted on arXiv 25 Mar 2024.

## Placed in

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

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

- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency](https://mlsanity.com/paper/2102.02981/) (2021)
- [Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian](https://mlsanity.com/paper/2211.00716/) (2022)
- [A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting](https://mlsanity.com/paper/2011.01075/) (2020)
- [Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL](https://mlsanity.com/paper/2304.05889/) (2023)
- [Reinforcement Learning in Low-Rank MDPs with Density Features](https://mlsanity.com/paper/2302.02252/) (2023)
- [Harnessing Density Ratios for Online Reinforcement Learning](https://mlsanity.com/paper/2401.09681/) (2024)

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

- [Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees](https://mlsanity.com/paper/2510.04088/) (2025)
- [Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol](https://mlsanity.com/paper/2502.08021/) (2025)
- [FOVA: Offline Federated Reinforcement Learning with Mixed-Quality Data](https://mlsanity.com/paper/2512.02350/) (2025)
- [Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear qπ-Realizability and Concentrability](https://mlsanity.com/paper/2405.16809/) (2024)
- [A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory](https://mlsanity.com/paper/2508.07746/) (2025)
- [A Unifying View of Coverage in Linear Off-Policy Evaluation](https://mlsanity.com/paper/2601.19030/) (2026)
- [AdaGamma: State-Dependent Discounting for Temporal Adaptation in Reinforcement Learning](https://mlsanity.com/paper/2605.06149/) (2026)
- [TOUR: A Trajectory-Level Unlearning Benchmark for Offline Reinforcement Learning](https://mlsanity.com/paper/2607.21111/) (2026)
- [Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear qπ-Realizability and Concentrability](https://mlsanity.com/paper/2510.03494/) (2025)
- [On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coverage](https://mlsanity.com/paper/2602.12107/) (2026)
- [The Sample Complexity of Policy Learning with Mu-Resets](https://mlsanity.com/paper/2608.07772/) (2026)

## Abstract (arXiv)

We revisit the problem of offline reinforcement learning with value function realizability but without Bellman completeness. Previous work by Xie and Jiang (2021) and Foster et al. (2022) left open the question whether a bounded concentrability coefficient along with trajectory-based offline data admits a polynomial sample complexity. In this work, we provide a negative answer to this question for the task of offline policy evaluation. In addition to addressing this question, we provide a rather complete picture for offline policy evaluation with only value function realizability. Our primary findings are threefold: 1) The sample complexity of offline policy evaluation is governed by the concentrability coefficient in an aggregated Markov Transition Model jointly determined by the function class and the offline data distribution, rather than that in the original MDP. This unifies and generalizes the ideas of Xie and Jiang (2021) and Foster et al. (2022), 2) The concentrability coefficient in the aggregated Markov Transition Model may grow exponentially with the horizon length, even when the concentrability coefficient in the original MDP is small and the offline data is admissible (i.e., the data distribution equals the occupancy measure of some policy), 3) Under value function realizability, there is a generic reduction that can convert any hard instance with admissible data to a hard instance with trajectory data, implying that trajectory data offers no extra benefits over admissible data. These three pieces jointly resolve the open problem, though each of them could be of independent interest.