# Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 115 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Reward Constrained Policy Optimization](https://mlsanity.com/paper/1805.11074/) (2018)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [A General Safety Framework for Learning-Based Control in Uncertain Robotic Systems](https://mlsanity.com/paper/1705.01292/) (2017)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [Provably Efficient Safe Exploration via Primal-Dual Policy Optimization](https://mlsanity.com/paper/2003.00534/) (2020)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs](https://mlsanity.com/paper/2106.02684/) (2021)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach](https://mlsanity.com/paper/2109.06332/) (2021)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [Constrained Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2001.09377/) (2020)
- [Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss](https://mlsanity.com/paper/2003.00660/) (2020)

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

- [Independent Learning in Constrained Markov Potential Games](https://mlsanity.com/paper/2402.17885/) (2024)
- [Safe Multi-Agent Reinforcement Learning with Bilevel Optimization in Autonomous Driving](https://mlsanity.com/paper/2405.18209/) (2024)
- [Discrete GCBF Proximal Policy Optimization for Multi-agent Safe Optimal Control](https://mlsanity.com/paper/2502.03640/) (2025)
- [Safe Multi-Agent Reinforcement Learning with Convergence to Generalized Nash Equilibrium](https://mlsanity.com/paper/2411.15036/) (2024)
- [Solving Multi-Agent Safe Optimal Control with Distributed Epigraph Form MARL](https://mlsanity.com/paper/2504.15425/) (2025)
- [Anytime-Constrained Equilibria in Polynomial Time](https://mlsanity.com/paper/2410.23637/) (2024)
- [Scalable Constrained Multi-Agent Reinforcement Learning via State Augmentation and Consensus for Separable Dynamics](https://mlsanity.com/paper/2605.30461/) (2026)
- [AttentionSwarm: Reinforcement Learning with Attention Control Barier Function for Crazyflie Drones in Dynamic Environments](https://mlsanity.com/paper/2503.07376/) (2025)
- [Feasibility-Aware Pessimistic Estimation: Toward Long-Horizon Safety in Offline RL](https://mlsanity.com/paper/2505.08179/) (2025)
- [Towards a Practical Understanding of Lagrangian Methods in Safe Reinforcement Learning](https://mlsanity.com/paper/2510.17564/) (2025)
- [Stable Reasoning, Unstable Responses: Mitigating LLM Deception via Stability Asymmetry](https://mlsanity.com/paper/2603.26846/) (2026)
- [Safe and Generalizable Hierarchical Multi-Agent RL via Constraint Manifold Control](https://mlsanity.com/paper/2606.24010/) (2026)
- [Learning to Harvest Without Collapse in a Regenerative Commons: A Lagrangian Framework](https://mlsanity.com/paper/2609.36478/) (2026)
- [VERA: Verifiable Feasibility Representations with Counterfactual Credit for Constrained Multi-Agent Control](https://mlsanity.com/paper/2609.38889/) (2026)

## Abstract (arXiv)

We examine online safe multi-agent reinforcement learning using constrained Markov games in which agents compete by maximizing their expected total rewards under a constraint on expected total utilities. Our focus is confined to an episodic two-player zero-sum constrained Markov game with independent transition functions that are unknown to agents, adversarial reward functions, and stochastic utility functions. For such a Markov game, we employ an approach based on the occupancy measure to formulate it as an online constrained saddle-point problem with an explicit constraint. We extend the Lagrange multiplier method in constrained optimization to handle the constraint by creating a generalized Lagrangian with minimax decision primal variables and a dual variable. Next, we develop an upper confidence reinforcement learning algorithm to solve this Lagrangian problem while balancing exploration and exploitation. Our algorithm updates the minimax decision primal variables via online mirror descent and the dual variable via projected gradient step and we prove that it enjoys sublinear rate  O((|X|+|Y|) L √T(|A|+|B|))) for both regret and constraint violation after playing T episodes of the game. Here, L is the horizon of each episode, (|X|,|A|) and (|Y|,|B|) are the state/action space sizes of the min-player and the max-player, respectively. To the best of our knowledge, we provide the first provably efficient online safe reinforcement learning algorithm in constrained Markov games.