Provably Convergent Actor-Critic for MARL through Risk-aversion

Yizhou Zhang, Eric Mazumdar

This paper presents a significant theoretical and practical breakthrough in Multi-Agent Reinforcement Learning (MARL). By fundamentally changing how agent behavior is modeled, the authors prove that global convergence can be achieved in general-sum games—a problem long considered computationally intractable.

The Challenge of General-Sum Games

In single-agent reinforcement learning, the objective is straightforward: find an optimal policy that maximizes cumulative reward. In multi-agent settings, however, the "best" move depends inherently on the actions of others, shifting the objective toward finding an equilibrium.

General-sum Markov Games (MGs)—where agents' interests are neither perfectly aligned nor perfectly opposed—are notoriously difficult to solve. Finding a stationary Nash equilibrium in these games is classified as "PPAD-complete," a complexity class suggesting it is effectively impossible to compute for large-scale problems. Consequently, most existing MARL algorithms suffer from critical flaws: they lack convergence guarantees, only converge in highly specific game types (such as strictly zero-sum or fully cooperative games), or produce "non-stationary" policies that are too complex to deploy in practice.

Methodology: Risk-Averse Quantal Response Equilibria

To bridge this gap, the authors draw inspiration from behavioral game theory. Instead of assuming agents are perfectly rational and risk-neutral, they model them using Risk-Averse Quantal Response Equilibria (RQE). This framework relies on two core behavioral assumptions:

  1. Risk-Aversion: Agents act as if they are playing against an imaginary adversary who is actively trying to minimize their payoff, constrained by a penalty function.
  2. Bounded Rationality: Agents utilize "quantal responses" (often implemented via entropy regularization). This means they choose better actions with higher probability, but are not perfectly optimal.

The "Reverse" Actor-Critic Architecture

Standard actor-critic wisdom dictates that the critic (the value estimator) should update faster than the actor (the policy) to provide a stable learning signal. This paper flips that logic entirely.

Because the RQE framework turns the Bellman operator into a contraction mapping, the authors introduce a novel single-timescale algorithm featuring a faster actor and a slower critic. This "reverse" step-size logic allows the actor to quickly track the equilibrium of the current value estimates, while the critic slowly and stably converges to the true value of that equilibrium.

Key Insights and Theoretical Breakthroughs

  • Behavior as Regularization: The most profound insight of the paper is that making agents "human-like"—risk-averse and slightly irrational—actually regularizes the game. It renders the game monotone, which is the game-theoretic equivalent of a well-behaved convex optimization problem.
  • Independence from Game Structure: Unlike previous proofs that require a game to be strictly "zero-sum" or "potential," this convergence depends entirely on the agent's design (their specific levels of risk-aversion and entropy). This implies the method can be applied to any general-sum game, provided the agents are designed with these behavioral constraints.
  • The Contraction Property: The authors mathematically prove that the risk-adjusted Bellman operator is a contraction. This guarantees that iterative updates will eventually settle on a unique fixed point, establishing the first MARL algorithm with finite-sample global convergence guarantees to stationary equilibria in general-sum discounted MGs.

Experimental Validation

The algorithm was evaluated across three distinct environments to test its empirical stability and performance:

  1. Inspection Game: A classic normal-form game where an "Inspectee" chooses to comply or defect, and an "Inspector" chooses to audit or not.
  2. Gridworld Cooperation Game: A $5 \times 5$ grid social dilemma where agents must choose between a safe cooperative reward or a risky, higher reward for defecting.
  3. MPE Simple Tag: A predator-prey environment from the Multi-Particle Environments (MPE) suite, modified to test how adversaries learn to cooperate.

Results: In the Gridworld experiment, the risk-averse agents converged consistently across all 10 independent runs. In stark contrast, risk-neutral baselines were highly unstable, often failing to converge entirely or settling on sub-optimal "defect-defect" behaviors. Furthermore, in the MPE Simple Tag experiment, the Risk-Averse Actor-Critic outperformed popular baselines like MAPPO and MADDPG, achieving higher average rewards with significantly lower variance.

Limitations and Future Directions

While the algorithm is provably convergent, the authors acknowledge several areas for future refinement:

  • Sample Efficiency: The number of samples required to reach convergence remains a challenge for future optimization.
  • Function Approximation: The core convergence theory is developed for tabular settings. While the authors successfully utilized deep neural networks in their empirical experiments, a formal theoretical bridge for non-linear function approximation in this specific RQE context is still needed.
  • Independent Learning: The current framework requires agents to have some awareness of opponent policies in order to update their internal "adversary" model. Designing fully independent learning algorithms that do not explicitly require opponent policy tracking is a promising next step for the field.

Summary updated

Abstract

Learning stationary policies in infinite-horizon general-sum Markov games (MGs) remains a fundamental open problem in Multi-Agent Reinforcement Learning (MARL). While stationary strategies are preferred for their practicality, computing stationary forms of classic game-theoretic equilibria is computationally intractable—a stark contrast to the comparative ease of solving single-agent RL or zero-sum games. To bridge this gap, we study Risk-averse Quantal response Equilibria (RQE), a solution concept rooted in behavioral game theory that incorporates risk aversion and bounded rationality. We demonstrate that RQE possesses strong regularity conditions that make it uniquely amenable to learning in MGs. We propose a novel single-timescale Actor-Critic algorithm characterized by a faster actor and a slower critic. Leveraging the regularity of RQE, we prove that this approach achieves global convergence with finite-sample guarantees. We empirically validate our algorithm in several environments to demonstrate superior convergence properties compared to risk-neutral baselines.
BibTeX
@inproceedings{zhang2026provably,
  author = {Yizhou Zhang and Eric Mazumdar},
  title = {{Provably Convergent Actor-Critic for MARL through Risk-aversion}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=NpguYNGrG2},
}
Figure