Equilibria as Learning Targets

Single-agent RL has an unambiguous target: the optimal policy. Multi-agent learning has no such thing, because "optimal" depends on what everyone else does. Game theory supplies candidate solution concepts, and each is a different answer to what the algorithm should be trying to reach.

The concepts and what they assume

Nash equilibrium is a joint policy where no agent can improve by unilaterally deviating. It exists in mixed strategies for finite games, and that is nearly all the good news. It is not generally unique, so the concept does not select an outcome; computing one is intractable in general; and it says nothing about how agents would reach it, which is the question a learning algorithm is asking.

Correlated equilibrium allows a shared signal that agents condition on, which enlarges the set and, crucially, is reachable by simple no-regret learning dynamics. This makes it a far more natural target for learning: run a no-regret algorithm per agent and the empirical joint distribution converges to the correlated equilibrium set.

Coarse correlated equilibrium relaxes further and is what standard no-regret dynamics actually reach, which is why it appears in learning-theoretic analyses more than in classical game theory.

Pareto optimality asks that no agent can improve without another losing, and it is not an equilibrium concept at all: it says nothing about stability, and many Pareto-optimal outcomes are not self-enforcing. In cooperative settings it is usually closer to what the designer wants than Nash is.

Where structure decides the answer

Two-player zero-sum games are the well-behaved case. The minimax value is unique, all equilibria have the same value, and self-play with no-regret dynamics converges. This is why the striking results in the field are in this class: the theory supports what the algorithms do.

General-sum games lose all of that. Multiple equilibria with different payoffs mean an algorithm can converge to a bad one, and equilibrium selection becomes the problem rather than equilibrium computation.

Cooperative games with identical rewards are formally a single-agent problem with a factored action space, so the equilibrium question largely dissolves and the difficulty moves entirely to credit assignment and coordination.

When it breaks

Convergence to equilibrium may not be desirable. In a general-sum game the equilibrium can be worse for everyone than an achievable non-equilibrium outcome, the prisoner's dilemma being the standard illustration. An algorithm that reliably converges to Nash has reliably reached a bad outcome.

Empirical convergence is usually to a cycle. Independent learners in general-sum games commonly cycle rather than converge, and reporting the final iterate hides this. The time-averaged policy is the object with the theoretical guarantee, not the last one, and evaluating the last iterate is a frequent mismatch between theory and practice.

Deep RL has no equilibrium guarantees. Nearly all convergence results assume tabular representations or specific game classes, and function approximation voids them. Deep multi-agent RL results are empirical claims about specific environments, and the theory is invoked as motivation rather than as support.

The reward specification defines the game. Whether the situation is zero-sum, cooperative or mixed is a modelling choice made when rewards are written, and a designer who intended cooperation but created scarcity has specified a competitive game and will get competitive behaviour regardless of intent.