# Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrability

arXiv: https://arxiv.org/abs/2302.03770 · HTML: https://mlsanity.com/paper/2302.03770/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion and flow policies for offline RL, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 29 of its 47 references that are in the map.
- First posted on arXiv 7 Feb 2023.

## Placed in

- Offline RL and imitation learning from data / [Diffusion and flow policies for offline RL](https://mlsanity.com/offlinerl/diffusion-and-flow-policies-for-offline-rl/)

## Builds on (most cited first, 29 of 29)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [VIP: Towards Universal Visual Reward and Representation via Value-Implicit Pre-Training](https://mlsanity.com/paper/2210.00030/) (2022)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Learning Latent Plans from Play](https://mlsanity.com/paper/1903.01973/) (2019)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research](https://mlsanity.com/paper/1802.09464/) (2018)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [AlgaeDICE: Policy Gradient from Arbitrary Experience](https://mlsanity.com/paper/1912.02074/) (2019)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Actionable Models: Unsupervised Offline Reinforcement Learning of Robotic Skills](https://mlsanity.com/paper/2104.07749/) (2021)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimation](https://mlsanity.com/paper/2106.10783/) (2021)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Adversarially Trained Actor Critic for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02446/) (2022)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Rethinking Goal-conditioned Supervised Learning and Its Connection to Offline RL](https://mlsanity.com/paper/2202.04478/) (2022)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [Batch Policy Learning in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2007.11771/) (2020)
- [How Far I'll Go: Offline Goal-Conditioned Reinforcement Learning via f-Advantage Regression](https://mlsanity.com/paper/2206.03023/) (2022)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Approximate Policy Iteration Schemes: A Comparison](https://mlsanity.com/paper/1405.2878/) (2014)
- [A Kernel Loss for Solving the Bellman Equation](https://mlsanity.com/paper/1905.10506/) (2019)
- [Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian](https://mlsanity.com/paper/2211.00716/) (2022)
- [On Value Functions and the Agent-Environment Boundary](https://mlsanity.com/paper/1905.13341/) (2019)

## Built on by (most cited first, 5 of 5)

- [Efficient Prompt Caching via Embedding Similarity](https://mlsanity.com/paper/2402.01173/) (2024)
- [On Representation Complexity of Model-based and Model-free Reinforcement Learning](https://mlsanity.com/paper/2310.01706/) (2023)
- [SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignment](https://mlsanity.com/paper/2505.21395/) (2025)
- [How to Provably Improve Return Conditioned Supervised Learning?](https://mlsanity.com/paper/2506.08463/) (2025)
- [World Models in Pieces: Structural Certification for General Agents](https://mlsanity.com/paper/2606.24842/) (2026)

## Abstract (arXiv)

Goal-conditioned reinforcement learning (GCRL) refers to learning general-purpose skills that aim to reach diverse goals. In particular, offline GCRL only requires purely pre-collected datasets to perform training tasks without additional interactions with the environment. Although offline GCRL has become increasingly prevalent and many previous works have demonstrated its empirical success, the theoretical understanding of efficient offline GCRL algorithms is not well established, especially when the state space is huge and the offline dataset only covers the policy we aim to learn. In this paper, we provide a rigorous theoretical analysis of an existing empirically successful offline GCRL algorithm. We prove that under slight modification, this algorithm enjoys an widetildeO(poly(1/ε)) sample complexity (where ε is the desired suboptimality of the learned policy) with general function approximation thanks to the property of (semi-)strong convexity of the objective functions. We only require nearly minimal assumptions on the dataset (single-policy concentrability) and the function class (realizability). Moreover, this algorithm consists of two uninterleaved optimization steps, which we refer to as V-learning and policy learning, and is computationally stable since it does not involve minimax optimization. We also empirically validate our theory by showing that the modified algorithm outperforms the previous algorithm in various real-world environments. To the best of our knowledge, this is the first algorithm that is both provably efficient with general function approximation and single-policy concentrability, and empirically successful without requiring solving minimax optimization problems.