mlsanityData to 14 Oct 2026

Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data

arXiv 2403.17091 ↗First posted 25 Mar 2024cs.LG cs.AI stat.MLcited by 11

On the map: Offline RL and imitation learning from data → Offline RL algorithms

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.

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.

Builds on

9 of 40 references.

Closest ancestors · 6

Same direction, newest first

  1. 2024Harnessing Density Ratios for Online Reinforcement Learning18 Jan
  2. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian1 Nov
  3. 2022The Role of Coverage in Online Reinforcement Learning9 Oct
  4. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  5. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency5 Feb
  6. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct

Other references · 3

  1. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 25
  2. 2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22
  3. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 18

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 5.

11 papers.

  1. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  2. 2025Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocolcited by 6
  3. 2025FOVA: Offline Federated Reinforcement Learning with Mixed-Quality Datacited by 5
  4. 2024Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear qπ-Realizability and Concentrabilitycited by 3
  5. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  6. 2026A Unifying View of Coverage in Linear Off-Policy Evaluationcited by 1
  7. 2026AdaGamma: State-Dependent Discounting for Temporal Adaptation in Reinforcement Learningcited by 1
  8. 2026TOUR: A Trajectory-Level Unlearning Benchmark for Offline Reinforcement Learningcited by 1
  9. 2025Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear qπ-Realizability and Concentrabilitycited by 0
  10. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coveragecited by 0
  11. 2026The Sample Complexity of Policy Learning with Mu-Resetscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  2. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  3. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  4. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  5. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps
  6. 2021Nearly Horizon-Free Offline Reinforcement Learning
  7. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
  8. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning