mlsanityData to 7 Oct 2026

Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations

arXiv 2112.14004 ↗First posted 28 Dec 2021cs.LG cs.AI math.OCcited by 9

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

Abstract (arXiv)

We consider large-scale Markov decision processes with an unknown cost function and address the problem of learning a policy from a finite set of expert demonstrations. We assume that the learner is not allowed to interact with the expert and has no access to reinforcement signal of any kind. Existing inverse reinforcement learning methods come with strong theoretical guarantees, but are computationally expensive, while state-of-the-art policy optimization algorithms achieve significant empirical success, but are hampered by limited theoretical understanding. To bridge the gap between theory and practice, we introduce a novel bilinear saddle-point framework using Lagrangian duality. The proposed primal-dual viewpoint allows us to develop a model-free provably efficient algorithm through the lens of stochastic convex optimization. The method enjoys the advantages of simplicity of implementation, low memory requirements, and computational and sample complexities independent of the number of states. We further present an equivalent no-regret online-learning interpretation.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Placed in Inverse reinforcement learning, one of 13 directions in Offline RL and imitation learning from data. Builds on 33 of its 81 references that are in the map. First posted on arXiv 28 Dec 2021.

Builds on

33 of 81 references.

Closest ancestors · 1

Same direction, newest first

  1. 2019On the Correctness and Sample Complexity of Inverse Reinforcement Learning2 Jun

Other references · 32

  1. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 11,979
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2016Generative Adversarial Imitation Learningcited by 1,576
  4. 2019Introduction to Online Convex Optimizationcited by 793
  5. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  6. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  7. 2019A Divergence Minimization Perspective on Imitation Learning Methodscited by 188
  8. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  9. 2019Imitation Learning via Off-Policy Distribution Matchingcited by 182
  10. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  11. 2017Socially Aware Motion Planning with Deep Reinforcement Learningcited by 128
  12. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
20 more
  1. 2020Safe Imitation Learning via Fast Bayesian Reward Inference from Preferencescited by 73
  2. 2019Reinforcement Learning with Convex Constraintscited by 57
  3. 2016Model-Free Imitation Learning with Policy Optimizationcited by 52
  4. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  5. 2019Variance Reduction for Matrix Gamescited by 37
  6. 2020Logistic Q-Learningcited by 34
  7. 2020Bayesian Robust Optimization for Imitation Learningcited by 28
  8. 2020On Computation and Generalization of Generative Adversarial Imitation Learningcited by 27
  9. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  10. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  11. 2014Linear Programming for Large-Scale Markov Decision Problemscited by 12
  12. 2015The Alternating Descent Conditional Gradient Method for Sparse Inverse Problemscited by 11
  13. 2018Scalable Bilinear π Learning Using State and Action Featurescited by 10
  14. 2019A Reduction from Reinforcement Learning to No-Regret Online Learningcited by 10
  15. 2017A Linearly Relaxed Approximate Linear Program for Markov Decision Processescited by 9
  16. 2019Faster saddle-point optimization for solving large-scale Markov decision processescited by 8
  17. 2020Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Ratecited by 7
  18. 2017From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programmingcited by 4
  19. 2016Performance guarantees for model-based Approximate Dynamic Programming in continuous spacescited by 3
  20. 2014Linear conic optimization for inverse optimal controlcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 0; 2024: 0; 2025: 3; 2026: 1.

9 papers.

  1. 2022Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guaranteescited by 42
  2. 2022Proximal Point Imitation Learningcited by 25
  3. 2022Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimizationcited by 8
  4. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  5. 2025IL-SOAR : Imitation Learning with Soft Optimistic Actor cRiticcited by 5
  6. 2025Analysis of approximate linear programming solution to Markov decision problem with log barrier functioncited by 1
  7. 2022Cross apprenticeship learning framework: Properties and solution approachescited by 0
  8. 2025Apprenticeship learning with prior beliefs using inverse optimizationcited by 0
  9. 2026Lifted Bellman Linear Programming for Offline Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021Stochastic convex optimization for provably efficient apprenticeship learning
  2. 2025Inverse Reinforcement Learning via Convex Optimization
  3. 2026Fast Rates for Inverse Reinforcement Learning
  4. 2025Offline Reinforcement Learning via Inverse Optimization
  5. 2026Inverse Reinforcement Learning without an Optimal Demonstrator: A Feasible Reward Set Approach
  6. 2024How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approach
  7. 2023A Novel Variational Lower Bound for Inverse Reinforcement Learning
  8. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs