mlsanityData to 7 Oct 2026

Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian

arXiv 2211.00716 ↗First posted 1 Nov 2022cs.LG cs.AI math.OCcited by 29

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

Offline reinforcement learning (RL), which refers to decision-making from a previously-collected dataset of interactions, has received significant attention over the past years. Much effort has focused on improving offline RL practicality by addressing the prevalent issue of partial data coverage through various forms of conservative policy learning. While the majority of algorithms do not have finite-sample guarantees, several provable conservative offline RL algorithms are designed and analyzed within the single-policy concentrability framework that handles partial coverage. Yet, in the nonlinear function approximation setting where confidence intervals are difficult to obtain, existing provable algorithms suffer from computational intractability, prohibitively strong assumptions, and suboptimal statistical rates. In this paper, we leverage the marginalized importance sampling (MIS) formulation of RL and present the first set of offline RL algorithms that are statistically optimal and practical under general function approximation and single-policy concentrability, bypassing the need for uncertainty quantification. We identify that the key to successfully solving the sample-based approximation of the MIS problem is ensuring that certain occupancy validity constraints are nearly satisfied. We enforce these constraints by a novel application of the augmented Lagrangian method and prove the following result: with the MIS formulation, augmented Lagrangian is enough for statistically optimal offline RL. In stark contrast to prior algorithms that induce additional conservatism through methods such as behavior regularization, our approach provably eliminates this need and reinterprets regularizers as "enforcers of occupancy validity" than "promoters of conservatism."

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 67 of its 101 references that are in the map. First posted on arXiv 1 Nov 2022.

Builds on

67 of 101 references.

Closest ancestors · 35

Same direction, newest first

  1. 2022Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief13 Oct
  2. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity11 Aug
  3. 2022On Gap-dependent Bounds for Offline Reinforcement Learning1 Jun
  4. 2022RAMBO-RL: Robust Adversarial Model-Based Offline Reinforcement Learning26 Apr
  5. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  6. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps25 Mar
  7. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  8. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  9. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
  10. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
  11. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
  12. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
23 more
  1. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  2. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  3. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  4. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimation21 Jun
  5. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  6. 2021A Minimalist Approach to Offline Reinforcement Learning12 Jun
  7. 2021Corruption-Robust Offline Reinforcement Learning11 Jun
  8. 2021Offline Reinforcement Learning as Anti-Exploration11 Jun
  9. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  10. 2021Offline Reinforcement Learning with Fisher Divergence Critic Regularization14 Mar
  11. 2021COMBO: Conservative Offline Model-Based Policy Optimization16 Feb
  12. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  13. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  14. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  15. 2020Batch Value-function Approximation with Only Realizability11 Aug
  16. 2020EMaQ: Expected-Max Q-Learning Operator for Simple Yet Effective Offline and Online RL21 Jul
  17. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  18. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  19. 2020MOPO: Model-based Offline Policy Optimization27 May
  20. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  21. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  22. 2020Keep Doing What Worked: Behavioral Modelling Priors for Offline Reinforcement Learning19 Feb
  23. 2019Behavior Regularized Offline Reinforcement Learning26 Nov

Other references · 32

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 833
  3. 2019Advantage-Weighted Regression: Simple and Scalable Off-Policy Reinforcement Learningcited by 750
  4. 2020AWAC: Accelerating Online Reinforcement Learning with Offline Datasetscited by 647
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2019Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialogcited by 283
  7. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 268
  8. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  9. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  10. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  11. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  12. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
20 more
  1. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  2. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  3. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  4. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  5. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  6. 2014Reinforcement and Imitation Learning via Interactive No-Regret Learningcited by 116
  7. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  8. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  9. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  10. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  11. 2020GradientDICE: Rethinking Generalized Offline Estimation of Stationary Valuescited by 70
  12. 2020Batch Policy Learning in Average Reward Markov Decision Processescited by 69
  13. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  14. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  15. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  16. 2014Approximate Policy Iteration Schemes: A Comparisoncited by 39
  17. 2019A Kernel Loss for Solving the Bellman Equationcited by 37
  18. 2020Review on Ranking and Selection: A New Perspectivecited by 28
  19. 2020Optimistic Exploration even with a Pessimistic Initialisationcited by 25
  20. 2019On Value Functions and the Agent-Environment Boundarycited by 19

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 13; 2024: 8; 2025: 4; 2026: 2.

29 papers.

Sort:

By area:

  1. 2024Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizercited by 109
  2. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  3. 2022Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequalitycited by 32
  4. 2023Beyond Uniform Sampling: Offline Reinforcement Learning with Imbalanced Datasetscited by 24
  5. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  6. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  7. 2023Oracle-Efficient Pessimism: Offline Policy Optimization in Contextual Banditscited by 14
  8. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  9. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  10. 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Datacited by 11
  11. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 9
  12. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
17 more
  1. 2023On Representation Complexity of Model-based and Model-free Reinforcement Learningcited by 6
  2. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  3. 2023Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrabilitycited by 5
  4. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  5. 2024Adversarially Trained Weighted Actor-Critic for Safe Offline Reinforcement Learningcited by 4
  6. 2024A Unified Linear Programming Framework for Offline Reward Learning from Human Demonstrations and Feedbackcited by 4
  7. 2024Q-Distribution guided Q-learning for offline reinforcement learning: Uncertainty penalized Q-value via consistency modelcited by 4
  8. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  9. 2024Offline RL via Feature-Occupancy Gradient Ascentcited by 2
  10. 2025Learning an Optimal Assortment Policy under Observational Datacited by 2
  11. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  12. 2023Offline Reinforcement Learning with Additional Covering Distributionscited by 1
  13. 2023Neural Network Approximation for Pessimistic Offline Reinforcement Learningcited by 1
  14. 2025Offline Constrained Reinforcement Learning under Partial Data Coveragecited by 1
  15. 2024MoMA: Model-based Mirror Ascent for Offline Reinforcement Learningcited by 0
  16. 2025Reachability Weighted Offline Goal-conditioned Resamplingcited by 0
  17. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coveragecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Fully Offline Reinforcement Learning
  2. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning
  3. 2023DOMAIN: MilDly COnservative Model-BAsed OfflINe Reinforcement Learning
  4. 2022Offline RL Policies Should be Trained to be Adaptive
  5. 2024Strategically Conservative Q-Learning
  6. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage
  7. 2026Bayesian Conservative Policy Optimization (BCPO): A Novel Uncertainty-Calibrated Offline Reinforcement Learning with Credible Lower Bounds
  8. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures