Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear qπ-Realizability and Concentrability
On the map: Offline RL and imitation learning from data → Offline RL algorithms
Abstract (arXiv)
We consider offline reinforcement learning (RL) in H-horizon Markov decision processes (MDPs) under the linear qπ-realizability assumption, where the action-value function of every policy is linear with respect to a given d-dimensional feature function. The hope in this setting is that learning a good policy will be possible without requiring a sample size that scales with the number of states in the MDP. Foster et al. [2021] have shown this to be impossible even under textitconcentrability, a data coverage assumption where a coefficient Cconc bounds the extent to which the state-action distribution of any policy can veer off the data distribution. However, the data in this previous work was in the form of a sequence of individual transitions. This leaves open the question of whether the negative result mentioned could be overcome if the data was composed of sequences of full trajectories. In this work we answer this question positively by proving that with trajectory data, a dataset of size poly(d,H,Cconc)/ε2 is sufficient for deriving an ε-optimal policy, regardless of the size of the state space. The main tool that makes this result possible is due to Weisz et al. [2023], who demonstrate that linear MDPs can be used to approximate linearly qπ-realizable MDPs. The connection to trajectory data is that the linear MDP approximation relies on "skipping" over certain states. The associated estimation problems are thus easy when working with trajectory data, while they remain nontrivial when working with individual transitions. The question of computational efficiency under our assumptions remains open.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 13 of its 21 references that are in the map. First posted on arXiv 27 May 2024.
Builds on
13 of 21 references.
Closest ancestors · 6
Same direction, newest first
- 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data25 Mar
- 2022ARMOR: A Model-based Framework for Improving Arbitrary Baseline Policies with Offline Data8 Nov
- 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
- 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
- 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
- 2020Batch Value-function Approximation with Only Realizability11 Aug
Other references · 7
- 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
- 2019Provably Efficient Exploration in Policy Optimizationcited by 203
- 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
- 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
- 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
- 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 24
- 2023Online RL in Linearly qπ-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignorecited by 2
Built on by
Citing papers per year: 2025: 3.
3 papers.
- 2025Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPscited by 5
- 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
- 2025Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear qπ-Realizability and Concentrabilitycited by 0
- 2025Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear qπ-Realizability and Concentrability3 Oct 2025
- 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory11 Aug 2025
- 2025Inverse Q-Learning Done Right: Offline Imitation Learning in Qπ-Realizable MDPs26 May 2025
Similar, not cited
Close in wording, no citation either way
- 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?
- 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
- 2023Harnessing Mixed Offline Reinforcement Learning Datasets via Trajectory Weighting
- 2023Beyond Uniform Sampling: Offline Reinforcement Learning with Imbalanced Datasets
- 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data
- 2021Nearly Horizon-Free Offline Reinforcement Learning
- 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
- 2023Offline Reinforcement Learning with Additional Covering Distributions