# ROMAX: Certifiably Robust Deep Multiagent Reinforcement Learning via Convex Relaxation

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 46 references that are in the map.
- First posted on arXiv 14 Sep 2021.

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

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [On First-Order Meta-Learning Algorithms](https://mlsanity.com/paper/1803.02999/) (2018)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Population Based Training of Neural Networks](https://mlsanity.com/paper/1711.09846/) (2017)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/1709.04326/) (2017)
- [Adversarial Policies: Attacking Deep Reinforcement Learning](https://mlsanity.com/paper/1905.10615/) (2019)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Emergent Complexity via Multi-Agent Competition](https://mlsanity.com/paper/1710.03748/) (2017)
- [Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments](https://mlsanity.com/paper/1710.03641/) (2017)
- [A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity](https://mlsanity.com/paper/1707.09183/) (2017)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Probabilistic Recursive Reasoning for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1901.09207/) (2019)
- [Stable Opponent Shaping in Differentiable Games](https://mlsanity.com/paper/1811.08469/) (2018)
- [Certified Adversarial Robustness for Deep Reinforcement Learning](https://mlsanity.com/paper/1910.12908/) (2019)
- [DiCE: The Infinitely Differentiable Monte-Carlo Estimator](https://mlsanity.com/paper/1802.05098/) (2018)
- [A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00382/) (2020)
- [Learning Nash Equilibrium for General-Sum Markov Games from Batch Data](https://mlsanity.com/paper/1606.08718/) (2016)
- [Balancing Two-Player Stochastic Games with Soft Q-Learning](https://mlsanity.com/paper/1802.03216/) (2018)
- [Decentralized Adaptive Control for Collaborative Manipulation of Rigid Bodies](https://mlsanity.com/paper/2005.03153/) (2020)

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

- [Robust Multi-Agent Reinforcement Learning with State Uncertainty](https://mlsanity.com/paper/2307.16212/) (2023)
- [Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes](https://mlsanity.com/paper/2501.00200/) (2024)
- [What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?](https://mlsanity.com/paper/2212.02705/) (2022)
- [RoMFAC: A robust mean-field actor-critic reinforcement learning against adversarial perturbations on states](https://mlsanity.com/paper/2205.07229/) (2022)
- [Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification](https://mlsanity.com/paper/2512.11087/) (2025)
- [Sparse Adversarial Attack in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2205.09362/) (2022)
- [Robust Multi-Agent Reinforcement Learning by Mutual Information Regularization](https://mlsanity.com/paper/2310.09833/) (2023)
- [Game-Theoretical Perspectives on Active Equilibria: A Preferred Solution Concept over Nash Equilibria](https://mlsanity.com/paper/2210.16175/) (2022)
- [Multi-Agent Reinforcement Learning: Methods, Applications, Visionary Prospects, and Challenges](https://mlsanity.com/paper/2305.10091/) (2023)
- [Robust Multi-agent Communication via Multi-view Message Certification](https://mlsanity.com/paper/2305.13936/) (2023)
- [Wasserstein Distributionally Robust Control Barrier Function using Conditional Value-at-Risk with Differentiable Convex Programming](https://mlsanity.com/paper/2309.08700/) (2023)
- [Distributionally Safe Reinforcement Learning under Model Uncertainty: A Single-Level Approach by Differentiable Convex Programming](https://mlsanity.com/paper/2310.02459/) (2023)
- [Robustness to Multi-Modal Environment Uncertainty in MARL using Curriculum Learning](https://mlsanity.com/paper/2310.08746/) (2023)
- [Towards Fault Tolerance in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.00534/) (2024)
- [Empirical Study on Robustness and Resilience in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2510.11824/) (2025)
- [Noisy Zero-Shot Coordination: Breaking The Common Knowledge Assumption In Zero-Shot Coordination Games](https://mlsanity.com/paper/2411.04976/) (2024)
- [SAJA: A State-Action Joint Attack Framework on Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/2510.13262/) (2025)

## Abstract (arXiv)

In a multirobot system, a number of cyber-physical attacks (e.g., communication hijack, observation perturbations) can challenge the robustness of agents. This robustness issue worsens in multiagent reinforcement learning because there exists the non-stationarity of the environment caused by simultaneously learning agents whose changing policies affect the transition and reward functions. In this paper, we propose a minimax MARL approach to infer the worst-case policy update of other agents. As the minimax formulation is computationally intractable to solve, we apply the convex relaxation of neural networks to solve the inner minimization problem. Such convex relaxation enables robustness in interacting with peer agents that may have significantly different behaviors and also achieves a certified bound of the original optimization problem. We evaluate our approach on multiple mixed cooperative-competitive tasks and show that our method outperforms the previous state of the art approaches on this topic.