Robust Constrained Markov Games: Multi-Agent Decision-Making under Model Uncertainty and Constraints

Ningkang Chang, Chenyu Xu, Ziying Jia, Yue Wang, Sihong He
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1003-1033, 2026.

Abstract

Multi-agent decision-making under both uncertainty and constraints is a central challenge in safety-critical domains such as autonomous driving, where agents must coordinate in uncertain environments while ensuring feasibility with respect to safety and resource limits. However, there is limited theoretical and practical work that addresses this challenge. Therefore, we introduce a Robust Constrained {Markov} Game (RCMG), the first multi-agent framework that simultaneously captures adversarial transition uncertainty and cost constraints. We further propose a solution concept, the Robust and Feasible {Nash} Equilibrium (RFNE), and a principled relaxation that yields a tractable surrogate upper bound to the intractable problem of computing an exact RFNE. This surrogate enables both a fixed-point existence proof via {Kakutani}’s theorem and a decentralized algorithm that alternates robust dynamic programming with Lagrangian dual updates. In settings where the relaxation is tight, the method provably recovers an exact RFNE. A grid-world experiment illustrates consistency with the theoretical results and highlights the viability of RCMGs as a foundation for reliable multi-agent decision-making under uncertainty and constraints.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-chang26a, title = {Robust Constrained {Markov} Games: Multi-Agent Decision-Making under Model Uncertainty and Constraints}, author = {Chang, Ningkang and Xu, Chenyu and Jia, Ziying and Wang, Yue and He, Sihong}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1003--1033}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/chang26a/chang26a.pdf}, url = {https://proceedings.mlr.press/v337/chang26a.html}, abstract = {Multi-agent decision-making under both uncertainty and constraints is a central challenge in safety-critical domains such as autonomous driving, where agents must coordinate in uncertain environments while ensuring feasibility with respect to safety and resource limits. However, there is limited theoretical and practical work that addresses this challenge. Therefore, we introduce a Robust Constrained {Markov} Game (RCMG), the first multi-agent framework that simultaneously captures adversarial transition uncertainty and cost constraints. We further propose a solution concept, the Robust and Feasible {Nash} Equilibrium (RFNE), and a principled relaxation that yields a tractable surrogate upper bound to the intractable problem of computing an exact RFNE. This surrogate enables both a fixed-point existence proof via {Kakutani}’s theorem and a decentralized algorithm that alternates robust dynamic programming with Lagrangian dual updates. In settings where the relaxation is tight, the method provably recovers an exact RFNE. A grid-world experiment illustrates consistency with the theoretical results and highlights the viability of RCMGs as a foundation for reliable multi-agent decision-making under uncertainty and constraints.} }
Endnote
%0 Conference Paper %T Robust Constrained Markov Games: Multi-Agent Decision-Making under Model Uncertainty and Constraints %A Ningkang Chang %A Chenyu Xu %A Ziying Jia %A Yue Wang %A Sihong He %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-chang26a %I PMLR %P 1003--1033 %U https://proceedings.mlr.press/v337/chang26a.html %V 337 %X Multi-agent decision-making under both uncertainty and constraints is a central challenge in safety-critical domains such as autonomous driving, where agents must coordinate in uncertain environments while ensuring feasibility with respect to safety and resource limits. However, there is limited theoretical and practical work that addresses this challenge. Therefore, we introduce a Robust Constrained {Markov} Game (RCMG), the first multi-agent framework that simultaneously captures adversarial transition uncertainty and cost constraints. We further propose a solution concept, the Robust and Feasible {Nash} Equilibrium (RFNE), and a principled relaxation that yields a tractable surrogate upper bound to the intractable problem of computing an exact RFNE. This surrogate enables both a fixed-point existence proof via {Kakutani}’s theorem and a decentralized algorithm that alternates robust dynamic programming with Lagrangian dual updates. In settings where the relaxation is tight, the method provably recovers an exact RFNE. A grid-world experiment illustrates consistency with the theoretical results and highlights the viability of RCMGs as a foundation for reliable multi-agent decision-making under uncertainty and constraints.
APA
Chang, N., Xu, C., Jia, Z., Wang, Y. & He, S.. (2026). Robust Constrained Markov Games: Multi-Agent Decision-Making under Model Uncertainty and Constraints. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1003-1033 Available from https://proceedings.mlr.press/v337/chang26a.html.

Related Material