Research map / Reinforcement learning / Offline RL
Worst-Case Offline Reinforcement Learning with Arbitrary Data Support
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.
Proposes worst-case offline RL, which replaces the conventional policy value with a worst-case value over environments indistinguishable from the data, and a model-free minimax method (WMRL) achieving O(ε^-2) sample complexity without any data-support or concentrability assumptions.
Problem
Offline RL is ill-posed when the data does not cover the visitation distribution of target policies (violating concentrability), so the conventional policy value cannot be estimated or optimized.
Approach
Replace the policy value with a worst-case value over all MDPs consistent with the data distribution; this equals offline RL in a truncated environment that is absorbing outside the data support. A regularized Lagrangian saddle-point formulation with a lower-clipped weight and an IPM-based policy extraction then yields a minimax algorithm with no hyperparameters beyond the function classes.
Key results
- Establishes a sample complexity bound of O(eps^-2) for worst-case offline RL with no data-support assumptions, under finite function classes (Corollary 6.3).
- The bound improves on prior results: Zhan et al. (2022) O(eps^-6) and Chen and Jiang (2022) O(eps^-2) with action-gap dependence, under single-policy realizability and concentrability.
- Worst-case value equals the conventional value on concentrable policies (Corollary 4.1), so the method generalizes standard offline RL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the conventional policy value with worst-case policy value | Offline RL · Arbitrary data support | sample complexity guarantee: O(ϵ−6) -> O(ϵ−2) | Helped |
| Use WMRL instead of Zhan et al. (2022) | Offline RL · Single-policy realizability and single-policy concentrability | sample complexity bound: ϵ−6(1 − γ)−4ln(N/δ) -> ϵ−2(1 − γ)−4ln(N/δ) | Helped |
| Remove concentrability and action-value-gap assumptions | WMRL · Worst-case offline RL | assumption strength | Helped |
| Use worst-case policy value rather than conventional policy value | Offline RL · Policies outside the data support | performance guarantee | Helped |
Surprising findings
- Small function approximation error in the unregularized Lagrangian saddle point can collapse the saddle point to zero (Corollary 5.1), motivating value-function regularization.
Limitations
- Analysis is for finite state and action spaces; extension to continuous spaces leaves truncated concentrability coefficients not unconditionally finite.
- Bound carries an implicit extra (1-gamma)^-2 factor in the worst case.
- No empirical experiments are reported.
Experimental setup
Metrics: sample complexity bound
Baselines: Zhan et al. (2022) Chen and Jiang (2022) Ozdaglar et al. (2023) Uehara et al. (2023)
Builds on: Lagrangian LP formulation of RL (Nachum et al., 2019) pessimism in the face of uncertainty (Liu et al., 2020) Uehara et al. (2023) regularized value function Zhan et al. (2022)
Closest papers by meaning
- Towards Instance-Optimal Offline Reinforcement Learning with Pessimism (NeurIPS 2021 · similarity 0.93)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.91)
- Online Optimization for Offline Safe Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
- Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.91)
- A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · similarity 0.91)
- A Unified Principle of Pessimism for Offline Reinforcement Learning under Model Mismatch (NeurIPS 2024 · similarity 0.90)
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.