Research map / Reinforcement learning / Offline RL

On the Complexity of Offline Reinforcement Learning with Q*-Approximation and Partial Coverage

NeurIPS 2026 · Reinforcement learning › Offline RL · approach: Offline RL sample complexity theory

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 Q*-realizability, partial coverage and Bellman completeness are insufficient for offline RL via an information-theoretic lower bound, and proposes an offline robust decision-estimation framework (Ordec, E2D.OR) decomposing suboptimality into decision complexity and estimation error.

Problem

Offline RL under Q*-approximation and partial coverage: whether Q*-realizability and Bellman completeness suffice for sample-efficient learning, and what structure is needed beyond them.

Approach

Introduces an offline robust decision-estimation coefficient (Ordec) that is a minimax game between a policy distribution and models in the Q*-induced confidence set, with discrepancy measured under each candidate model's own optimal policy, decomposing suboptimality into decision complexity plus estimation error.

Key results

• Lower bound: n >= Omega((1/eps) min{sqrt|S|, 1/Delta^2}) samples are required under Q*-realizability, partial coverage and Bellman completeness.
• Under regularization, Ordec-based analysis gives the first 1/eps^2 sample complexity for soft Q-learning under partial coverage, improving the prior 1/eps^4.
• Low Bellman rank becomes offline-learnable only with double policy sampling and policy feature coverage, which the paper shows are necessary.

Surprising findings

• Value-centric pessimism (minimizing f(s1) over the confidence set) can be highly suboptimal compared with policy-centric robust decisions, with a constant-order gap in the example.
• Under standard data and coverage definitions, low Bellman rank is insufficient for offline learnability even with bounded decision complexity.

Limitations

• Ordec serves mainly to identify learnable regimes; no matching lower bound shows tightness.
• Exactly solving the minimax algorithm is computationally difficult; only an actor-critic approximation is suggested.

Experimental setup

Metrics: sample complexity suboptimality bound

Baselines: CQL value-centric pessimism

Builds on: model-free DEC E2D CQL value-gap offline RL analysis

Closest papers by meaning

• On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling and Beyond (NeurIPS 2023 · similarity 0.93)
• Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian (ICLR 2023 · similarity 0.92)
• Conservative Q-Learning for Offline Reinforcement Learning (NeurIPS 2020 · similarity 0.92)
• On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples (AAAI 2023 · similarity 0.92)
• A Perspective of Q-value Estimation on Offline-to-Online Reinforcement Learning (AAAI 2024 · similarity 0.91)
• Exclusively Penalized Q-learning for Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.90)