📊 statistics

On the Complexity of Offline Reinforcement Learning with $Q^\star$ -Approximation and Partial Coverage

This paper provides a negative answer to the sufficiency of $Q^\star$ -realizability and Bellman completeness for sample-efficient offline RL under partial coverage by establishing an information-theoretic lower bound, and introduces a general decision-estimation framework that unifies and improves existing results by decomposing complexity into decision and value estimation components.

Original authors: Haolin Liu, Braham Snyder, Chen-Yu Wei

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haolin Liu, Braham Snyder, Chen-Yu Wei

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Learning from a Library, Not a Playground

Imagine you want to learn how to play a complex video game, but you are not allowed to play it yourself. Instead, you are given a massive library of videos showing other people playing the game. This is called Offline Reinforcement Learning (RL).

The problem is that the videos in the library are incomplete. They don’t show every possible move or every possible situation in the game. This is called Partial Coverage. You have to figure out the best strategy based only on the clips you have, without being able to test your ideas in the actual game.

Most existing theories assumed that if you had a good enough "map" of the game’s value (how good each move is), you could figure out the best strategy. This paper argues that that assumption is wrong. Just knowing the value of moves isn’t enough if you haven’t seen enough of the game to know which moves are safe to pick.

The Core Problem: The "Safe Bet" Dilemma

The authors ask a specific question: If we have a perfect map of the best possible scores (Q⋆-realizability) and our map is mathematically consistent (Bellman completeness), can we still learn efficiently from incomplete data?

Their answer is: No.

They prove this with a mathematical "lower bound" (a proof of impossibility). Here is the analogy:

Imagine you are in a dark room with two doors, Door A and Door B.

Behind Door A is a treasure chest worth $100.
Behind Door B is a trap that costs you $100.
However, you only have a blurry photo of the room. The photo shows that one of the doors leads to treasure, but it doesn’t clearly show which one.
You also know that if you pick the wrong door, you lose everything.

Even if you have a perfect mathematical model of the room’s layout, if your photo (the data) doesn’t clearly distinguish between Door A and Door B, you cannot safely choose a door. You might pick the trap. The paper shows that in many "offline" scenarios, the data is too blurry to distinguish the safe path from the dangerous one, no matter how good your math is.

The Solution: Splitting the Problem into Two Parts

Since the old way of thinking didn’t work, the authors created a new framework. They split the difficulty of learning into two separate challenges:

Estimation Error (The "Blurry Photo" Problem): How well can we guess the value of each move based on the limited data?
Decision Complexity (The "Safe Bet" Problem): Given our blurry guesses, how hard is it to pick a policy (a set of rules for playing) that won’t fail catastrophically?

They call their new tool Ordec (Offline Robust Decision-Estimation Coefficient). Think of Ordec as a "Risk Manager." It doesn’t just look for the highest possible score; it looks for the strategy that performs well even in the worst-case scenario allowed by the blurry data.

How It Works: The "Pessimistic" Game

The authors propose an algorithm called E2D.OR (Estimation-to-Decision). Here is how it works in plain English:

The Confidence Set: First, the algorithm looks at all the possible "maps" of the game that are consistent with the video clips it has seen. It creates a list of "plausible worlds."
The Game: The algorithm plays a mental game against an "Adversary."
- The Adversary tries to pick the most confusing world from the list of plausible worlds to trick the learner.
- The Learner tries to pick a strategy that works well in all those confusing worlds.
The Penalty: If a world in the list requires the learner to make moves that were never seen in the video clips, the Adversary is penalized. This prevents the algorithm from worrying about impossible scenarios.

This approach is different from older methods that just picked the "worst-case" map and played optimally against it. The authors show that their new method is more robust and makes safer decisions.

Key Improvements Over Previous Work

The paper claims several improvements over previous research:

Better Sample Efficiency: Previous methods required a huge amount of data (scaling with $\epsilon^{-4}$ ) to learn safely. This new method requires much less data (scaling with $\epsilon^{-2}$ ). In simple terms, you need fewer video clips to learn the same lesson.
No Need for "Value Gaps": Older methods assumed that the best move was clearly better than the second-best move (a large "gap"). This new method works even if the best move is only slightly better than the others, which is more realistic in complex games.
Works for Continuous Actions: It handles games where you can move smoothly (like steering a car) rather than just pressing discrete buttons (like Left/Right).
First Analysis of CQL: The paper provides the first theoretical proof that Conservative Q-Learning (CQL), a popular practical algorithm, works well under these conditions. CQL is a real-world algorithm used in robotics and AI, and this paper finally explains why it works mathematically.

Summary

The Problem: Learning from incomplete data is hard because you can’t distinguish safe moves from dangerous ones just by looking at values.
The Insight: You need to separate "guessing values" from "making safe decisions."
The Tool: Ordec, a new measure that balances estimation error with decision safety.
The Result: A new algorithm that learns faster, needs less data, and works in more realistic scenarios than previous methods.

In short, the paper says: "Don’t just try to guess the best score. Try to find the strategy that is robust against the uncertainty of your incomplete data."

Technical Summary: On the Complexity of Offline Reinforcement Learning with Q⋆-Approximation and Partial Coverage

Problem Setting and Motivation
The paper addresses the theoretical foundations of offline reinforcement learning (RL) under two specific conditions: $Q^\star$ -approximation (where the optimal Q-function is realizable within a function class) and partial coverage (where the offline dataset does not cover the entire state-action space). While $Q^\pi$ -realizability has been well-characterized, the sample efficiency of offline RL under $Q^\star$ -realizability and partial coverage remains an open question. Specifically, it is unknown whether $Q^\star$ -realizability combined with Bellman completeness is sufficient for sample-efficient learning in this regime. The authors aim to resolve this by establishing information-theoretic limits and providing a unified framework that identifies the structural conditions necessary for learnability.

Methodology: Decision-Estimation Decomposition
The core methodological contribution is a decomposition of the offline RL complexity into two distinct components: decision complexity and value estimation error. This framework is inspired by the Decision-Estimation Coefficient (DEC) used in online RL but is adapted for the offline setting.

Confidence Set Construction: The offline data induces a confidence set $\mathcal{F}_{\text{conf}}$ of plausible optimal Q-functions. This set induces a set of plausible models $\mathcal{M}_{\text{conf}} = \{M : Q^\star_M \in \mathcal{F}_{\text{conf}}\}$ .
Offline Robust DEC (Ordec): The authors define a new complexity measure, $\text{Ordec}$ , which quantifies the difficulty of making robust decisions from the confidence set. It is defined as a minimax game between a policy player and a model player:
$\text{Ordec}^{\text{OD}}_\gamma(\mathcal{F}_{\text{conf}}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{\text{conf}}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in \mathcal{F}_{\text{conf}}} D_{\pi_M}(f \| M) \right]$
Here, the policy player chooses a mixture policy $\rho$ to minimize suboptimality, while the model player chooses a model $M$ from the confidence set to maximize the gap, penalized by a discrepancy term $D$ that measures statistical inconsistency with the confidence set. Crucially, the discrepancy is measured under the candidate model’s own optimal policy $\pi_M$ , rather than the learner’s policy, to account for partial coverage.
Algorithm (E2D.OR): The proposed algorithm, Offline Robust Estimation-to-Decision (E2D.OR), solves the minimax problem defined by Ordec to output a mixture policy $\hat{\rho}$ .

Key Contributions and Results

Information-Theoretic Lower Bound:
The authors prove that $Q^\star$ -realizability, partial coverage, and Bellman completeness are not sufficient for sample-efficient offline RL. They construct a family of MDPs where these assumptions hold, yet any algorithm requires $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$ samples to achieve $\epsilon$ -optimality, where $\Delta$ is the value gap. This demonstrates that the difficulty arises not just from estimating $Q^\star$ , but from the decision-making process under ambiguity.
Upper Bound via Decomposition:
The paper establishes that the suboptimality of the E2D.OR algorithm is bounded by the sum of the decision complexity (Ordec) and the estimation error:
$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq \text{Ordec}^{\text{OD}}_\gamma(\mathcal{F}_{\text{conf}}) + \gamma \max_{f \in \mathcal{F}_{\text{conf}}} D_{\pi^\star}(f \| M^\star)$
This modular decomposition allows the authors to analyze conditions that bound each term separately.
Bounding Decision Complexity:
The authors identify three settings where Ordec is bounded:
- Value Gap: In the unregularized case, if the true Q-function has a value gap $\Delta_{Q^\star}$ , Ordec scales with $\Delta_{Q^\star}^{-2}$ . This improves upon prior work (Chen and Jiang, 2022) by adapting to the true gap without requiring prior knowledge or online interaction.
- Curved Decision Boundary: For linear function approximation with curved decision boundaries, Ordec is bounded even without strict value gaps, addressing concerns about the practicality of gap assumptions in continuous action spaces.
- Regularization: In regularized MDPs (e.g., with KL regularization), Ordec is bounded due to the strong convexity of the regularizer. This yields the first $\epsilon^{-2}$ sample complexity bound for soft Q-learning under partial coverage, improving the $\epsilon^{-4}$ bound of Uehara et al. (2023).
Bounding Estimation Error:
The authors provide conditions for controlling the estimation error term:
- Bellman Completeness: Under standard Bellman completeness, the estimation error is controlled, providing the first sample complexity analysis for Conservative Q-Learning (CQL) in the general function approximation setting.
- Weight Realizability: Recovers existing results where density ratios are realizable.
- Low Bellman Rank: The paper provides the first characterization of offline learnability for low-Bellman-rank MDPs. It shows that standard coverage assumptions are insufficient; instead, double policy sampling and policy feature coverage are necessary and sufficient conditions for efficient estimation in this regime.

Significance and Claims
The paper claims to provide a comprehensive understanding of offline RL under $Q^\star$ -approximation and partial coverage. By introducing the Ordec framework, it unifies and improves upon existing results, specifically:

It resolves the open question of sufficiency by proving a negative result for Bellman completeness alone.
It improves sample complexity bounds for regularized settings (from $\epsilon^{-4}$ to $\epsilon^{-2}$ ).
It removes the need for online interaction or known gap values in value-gap settings.
It extends learnability to new regimes, such as curved decision boundaries and low-Bellman-rank MDPs with specific data assumptions.
It provides the first theoretical analysis of CQL under general function approximation.

The authors note limitations, including the computational difficulty of exactly solving the minimax Ordec objective and the lack of a matching lower bound for the Ordec complexity measure itself.