Zero-Violation Regret for Cooperative Markov Games with Coupled Instantaneous Hard Constraints

Safety-critical multi-agent systems require agents to learn coordinated behaviors while avoiding unsafe actions throughout learning. Existing safe reinforcement learning theory has established zero-violation guarantees for single-agent Markov decision processes with instantaneous hard constraints, while much of safe multi-agent reinforcement learning focuses on cumulative constraints, policy optimization, or shielding. We study a stricter setting: cooperative Markov games with unknown dynamics and coupled instantaneous hard constraints, where a joint action must be safe at every time step of every episode. This setting introduces challenges absent from the single-agent case: actions that are locally safe for individual agents may be unsafe jointly, unsafe joint actions can affect future feasible regions, and naive reductions to single-agent safe RL suffer exponential dependence on the number of agents. We propose a graph-structured safe learning algorithm that constructs conservative multi-agent safety certificates and explores optimistically only within certified safe joint subgraphs. Under structured coupling assumptions, the algorithm guarantees zero constraint violation with high probability and achieves sublinear regret against the optimal safe joint policy, with complexity depending on local interaction structure rather than the full joint action space.