# Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 25 of its 53 references that are in the map.
- First posted on arXiv 16 Feb 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Model Predictive Path Integral Control using Covariance Variable Importance Sampling](https://mlsanity.com/paper/1509.01149/) (2015)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Active Learning for Nonlinear System Identification with Guarantees](https://mlsanity.com/paper/2006.10277/) (2020)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [An Online Learning Approach to Model Predictive Control](https://mlsanity.com/paper/1902.08967/) (2019)
- [Provably Efficient Algorithms for Multi-Objective Competitive RL](https://mlsanity.com/paper/2102.03192/) (2021)
- [Cautious Reinforcement Learning via Distributional Risk in the Dual Domain](https://mlsanity.com/paper/2002.12475/) (2020)
- [Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning](https://mlsanity.com/paper/1612.02516/) (2016)
- [PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Exploration](https://mlsanity.com/paper/2107.07410/) (2021)
- [Apprenticeship Learning via Frank-Wolfe](https://mlsanity.com/paper/1911.01679/) (2019)

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

- [Constraint-Aware Influence Estimation in Deep Constrained Learning](https://mlsanity.com/paper/2607.23388/) (2026)
- [A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance](https://mlsanity.com/paper/2505.04494/) (2025)

## Abstract (arXiv)

We study the Constrained Convex Markov Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure, subject to a convex constraint. Designing algorithms for a constrained convex MDP faces several challenges, including (1) handling the large state space, (2) managing the exploration/exploitation tradeoff, and (3) solving the constrained optimization where the objective and the constraint are both nonlinear functions of the visitation measure. In this work, we present a model-based algorithm, Variational Primal-Dual Policy Optimization (VPDPO), in which Lagrangian and Fenchel duality are implemented to reformulate the original constrained problem into an unconstrained primal-dual optimization. Moreover, the primal variables are updated by model-based value iteration following the principle of Optimism in the Face of Uncertainty (OFU), while the dual variables are updated by gradient ascent. Moreover, by embedding the visitation measure into a finite-dimensional space, we can handle large state spaces by incorporating function approximation. Two notable examples are (1) Kernelized Nonlinear Regulators and (2) Low-rank MDPs. We prove that with an optimistic planning oracle, our algorithm achieves sublinear regret and constraint violation in both cases and can attain the globally optimal policy of the original constrained problem.