mlsanityData to 7 Oct 2026

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

arXiv 2302.03770 ↗First posted 7 Feb 2023cs.LG cs.AIcited by 5

On the map: Offline RL and imitation learning from data → Diffusion and flow policies for offline RL

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.

Key facts. Cited by 5 papers in the map (data through 7 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.

Builds on

29 of 47 references.

Closest ancestors · 2

Same direction, newest first

  1. 2022How Far I'll Go: Offline Goal-Conditioned Reinforcement Learning via f-Advantage Regression7 Jun
  2. 2022Rethinking Goal-conditioned Supervised Learning and Its Connection to Offline RL9 Feb

Other references · 27

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2022VIP: Towards Universal Visual Reward and Representation via Value-Implicit Pre-Trainingcited by 384
  3. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  4. 2019Learning Latent Plans from Playcited by 310
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  7. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  8. 2018Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Researchcited by 256
  9. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  10. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  11. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  12. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
15 more
  1. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  2. 2021Actionable Models: Unsupervised Offline Reinforcement Learning of Robotic Skillscited by 125
  3. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  4. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimationcited by 121
  5. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learningcited by 111
  6. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  7. 2020Batch Value-function Approximation with Only Realizabilitycited by 103
  8. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  9. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 82
  10. 2020Batch Policy Learning in Average Reward Markov Decision Processescited by 69
  11. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  12. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  13. 2019A Kernel Loss for Solving the Bellman Equationcited by 37
  14. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  15. 2019On Value Functions and the Agent-Environment Boundarycited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 1; 2025: 2; 2026: 1.

5 papers.

  1. 2024Efficient Prompt Caching via Embedding Similaritycited by 9
  2. 2023On Representation Complexity of Model-based and Model-free Reinforcement Learningcited by 6
  3. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  4. 2025How to Provably Improve Return Conditioned Supervised Learning?cited by 1
  5. 2026World Models in Pieces: Structural Certification for General Agentscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024OGBench: Benchmarking Offline Goal-Conditioned RL
  2. 2026Beyond Success Rates: Trainability and Extractability for Offline GCRL
  3. 2026Efficient Hierarchical Implicit Flow Q-learning for Offline Goal-conditioned Reinforcement Learning
  4. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  5. 2023What is Essential for Unseen Goal Generalization of Offline Goal-conditioned RL?
  6. 2026Adaptive Coarse-to-Fine Subgoal Refinement for Long-Horizon Offline Goal-Conditioned Reinforcement Learning
  7. 2020MOReL : Model-Based Offline Reinforcement Learning
  8. 2023SMORE: Score Models for Offline Goal-Conditioned Reinforcement Learning