Research map / Reinforcement learning / MDPs and planning
Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^\pi$-Realizability and Concentrability
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that with full-length trajectory data, offline RL under linear q^pi-realizability and concentrability admits a statistically efficient learner (poly(d,H,C)/eps^2 trajectories) independent of state-space size, via skipping low-range states to obtain linear MDPs; computational efficiency left open.
Problem
Whether offline RL under linear q^pi-realizability plus concentrability can find an eps-optimal policy with sample size independent of the state space when data are full trajectories rather than individual transitions (prior work proved a lower bound for transition data).
Approach
Use the observation that linearly q^pi-realizable MDPs become linear MDPs after skipping low-range states; with trajectory data, a learner can simulate skipping mechanisms (guessing the skip structure G over all candidates), rejects guesses yielding loose q-estimates, and outputs a greedy policy over selected least-squares parameters, which is statistically efficient.
Key results
- Sample complexity n = tilde Theta(C^4 H^7 d^4 / eps^2) full trajectories suffices for eps-optimal policy under linear q^pi-realizability, concentrability, and trajectory data, independent of state-space size.
- Requires approximation error misspec = tilde O(eps^2/(C^2 H^5 d^2)).
- Table comparison shows prior lower bounds for transition data and exponential lower bounds for restricted settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use full-length trajectory data rather than individual transition data | Offline RL with linear q^π-realizability and concentrability · Policy optimization | sample complexity: n = \tilde Θ(\conc^4 H^7 d^4/\eps^2) | Helped |
Surprising findings
- Trajectory data overcomes the poly-sample lower bound known for individual-transition offline data under the same assumptions.
Limitations
- No computationally efficient implementation known; the optimization is not computationally efficient.
- Statistical rate optimality unknown.
- Assumptions (linear q^pi-realizability, single-policy trajectory data, concentrability) are strong; mixtures of behavior policies not covered.
Experimental setup
Metrics: sample complexity suboptimality v*(s1) - v^pi(s1)
Builds on: Eleanor linear MDP approximation of linear q^pi-realizable MDPs
Closest papers by meaning
- What are the Statistical Limits of Offline RL with Linear Function Approximation? (ICLR 2021 · similarity 0.89)
- Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.87)
- Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs (NeurIPS 2024 · similarity 0.87)
- Model-based Reinforcement Learning for Confounded POMDPs (ICML 2024 · similarity 0.86)
- On the Complexity of Offline Reinforcement Learning with Q*-Approximation and Partial Coverage (NeurIPS 2026 · similarity 0.86)
- Worst-Case Offline Reinforcement Learning with Arbitrary Data Support (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.