Nash equilibrium in RL

When several agents learn at once, what does it even mean to be 'done'? A Nash equilibrium is the standard answer: a set of strategies, one per agent, such that no single agent can do better by changing its own strategy while everyone else keeps theirs fixed. It is a state of mutual no-regret — everybody is simultaneously playing their best response to everybody else, so nobody has a unilateral reason to move.

In a Markov game this replaces the single-agent notion of an optimal policy. Each agent's policy must be a best response to the others' policies in the sense of expected return; written out, agent i's equilibrium policy earns at least as much as any alternative policy would, given the fixed policies of the rest. John Nash proved such an equilibrium always exists (in mixed strategies) for finite games, which is what makes it a usable target for learning.

Two honest caveats keep this from being a magic bullet. Equilibria are often not unique — a game can have many, and learners may land on a poor one — and a Nash equilibrium is about stability, not about being good: agents can be stuck in a mutually bad outcome (the prisoner's dilemma is exactly this). Computing or even approximating Nash equilibria is also hard in general, which is why much of MARL settles for weaker, learnable notions.