# Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations

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

## Key facts

- Cited by 10 papers in the map (data through 14 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.

## Placed in

- Offline RL and imitation learning from data / [Inverse reinforcement learning](https://mlsanity.com/offlinerl/inverse-reinforcement-learning/)

## Builds on (most cited first, 30 of 33)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [A Divergence Minimization Perspective on Imitation Learning Methods](https://mlsanity.com/paper/1911.02256/) (2019)
- [AlgaeDICE: Policy Gradient from Arbitrary Experience](https://mlsanity.com/paper/1912.02074/) (2019)
- [Imitation Learning via Off-Policy Distribution Matching](https://mlsanity.com/paper/1912.05032/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Socially Aware Motion Planning with Deep Reinforcement Learning](https://mlsanity.com/paper/1703.08862/) (2017)
- [Reinforcement Learning via Fenchel-Rockafellar Duality](https://mlsanity.com/paper/2001.01866/) (2020)
- [Safe Imitation Learning via Fast Bayesian Reward Inference from Preferences](https://mlsanity.com/paper/2002.09089/) (2020)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Model-Free Imitation Learning with Policy Optimization](https://mlsanity.com/paper/1605.08478/) (2016)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Logistic Q-Learning](https://mlsanity.com/paper/2010.11151/) (2020)
- [On Computation and Generalization of Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2001.02792/) (2020)
- [Bayesian Robust Optimization for Imitation Learning](https://mlsanity.com/paper/2007.12315/) (2020)
- [On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator](https://mlsanity.com/paper/1901.03674/) (2019)
- [Efficient Planning in Large MDPs with Weak Linear Function Approximation](https://mlsanity.com/paper/2007.06184/) (2020)
- [Linear Programming for Large-Scale Markov Decision Problems](https://mlsanity.com/paper/1402.6763/) (2014)
- [The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems](https://mlsanity.com/paper/1507.01562/) (2015)
- [Scalable Bilinear π Learning Using State and Action Features](https://mlsanity.com/paper/1804.10328/) (2018)
- [A Reduction from Reinforcement Learning to No-Regret Online Learning](https://mlsanity.com/paper/1911.05873/) (2019)
- [A Linearly Relaxed Approximate Linear Program for Markov Decision Processes](https://mlsanity.com/paper/1704.02544/) (2017)
- [On the Correctness and Sample Complexity of Inverse Reinforcement Learning](https://mlsanity.com/paper/1906.00422/) (2019)
- [Faster saddle-point optimization for solving large-scale Markov decision processes](https://mlsanity.com/paper/1909.10904/) (2019)
- [Generative Adversarial Imitation Learning with Neural Networks: Global Optimality and Convergence Rate](https://mlsanity.com/paper/2003.03709/) (2020)

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

- [Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2210.01808/) (2022)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP](https://mlsanity.com/paper/2207.06147/) (2022)
- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Operator Splitting for Convex Constrained Markov Decision Processes](https://mlsanity.com/paper/2412.14002/) (2024)
- [Apprenticeship learning with prior beliefs using inverse optimization](https://mlsanity.com/paper/2505.21639/) (2025)
- [Analysis of approximate linear programming solution to Markov decision problem with log barrier function](https://mlsanity.com/paper/2509.19800/) (2025)
- [Cross apprenticeship learning framework: Properties and solution approaches](https://mlsanity.com/paper/2209.02424/) (2022)
- [Lifted Bellman Linear Programming for Offline Reinforcement Learning](https://mlsanity.com/paper/2609.24489/) (2026)

## 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.