Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
read the original abstract
We consider the offline reinforcement learning problem, where the aim is to learn a decision making policy from logged data. Offline RL -- particularly when coupled with (value) function approximation to allow for generalization in large or continuous state spaces -- is becoming increasingly relevant in practice, because it avoids costly and time-consuming online data collection and is well suited to safety-critical domains. Existing sample complexity guarantees for offline value function approximation methods typically require both (1) distributional assumptions (i.e., good coverage) and (2) representational assumptions (i.e., ability to represent some or all $Q$-value functions) stronger than what is required for supervised learning. However, the necessity of these conditions and the fundamental limits of offline RL are not well understood in spite of decades of research. This led Chen and Jiang (2019) to conjecture that concentrability (the most standard notion of coverage) and realizability (the weakest representation condition) alone are not sufficient for sample-efficient offline RL. We resolve this conjecture in the positive by proving that in general, even if both concentrability and realizability are satisfied, any algorithm requires sample complexity polynomial in the size of the state space to learn a non-trivial policy. Our results show that sample-efficient offline reinforcement learning requires either restrictive coverage conditions or representation conditions that go beyond supervised learning, and highlight a phenomenon called over-coverage which serves as a fundamental barrier for offline value function approximation methods. A consequence of our results for reinforcement learning with linear function approximation is that the separation between online and offline RL can be arbitrarily large, even in constant dimension.
This paper has not been read by Pith yet.
Forward citations
Cited by 6 Pith papers
-
Fitted $Q$ Evaluation Without Bellman Completeness via Stationary Weighting
Stationary-weighted FQE achieves finite-sample linear convergence to the projected Bellman fixed point without Bellman completeness by reweighting regressions to the target stationary norm.
-
Bellman Calibration for $V$-Learning in Offline Reinforcement Learning
Bellman calibration supplies a new reliability criterion and post-hoc recalibration method for value functions in offline RL, with finite-sample guarantees at one-dimensional nonparametric rates that avoid Bellman com...
-
Inverse Reinforcement Learning with Just Classification and a Few Regressions
GenPQR recovers normalized rewards in maximum-entropy IRL by estimating the policy with classification and the soft Q-function with regression, providing modular finite-sample guarantees under general function approximation.
-
When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?
Proposes OPAC for trajectory-level offline RL achieving 𝓣O(H^{2}√(C_sa(π*)/n)) bounds with matching lower bound, plus conditions for tractability in generalized nonlinear outcome settings.
-
On the Role of Language Representations in Auto-Bidding: Findings and Implications
SemBid injects LLM-encoded Task, History, and Strategy semantics as tokens into offline bidding trajectories and uses self-attention to outperform numerical-only baselines in performance, constraint satisfaction, and ...
-
Stationary Reweighting Yields Local Convergence of Soft Fitted Q-Iteration
Stationary reweighting of soft fitted Q-iteration yields finite-sample local linear convergence to the projected fixed point under approximate realizability and controlled weighting error, even without Bellman completeness.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.