When One Agent Isn't Enough

The world rarely holds still for one learner

Classic reinforcement learning tells a tidy story: a single agent acts in an environment, the world responds, and a reward guides learning. But look at the problems we actually care about — cars merging in traffic, players on a soccer field, bidders in an auction, warehouse robots threading past each other. In all of them, the 'environment' is partly made of other learners, each chasing its own goal. This is the realm of multi-agent reinforcement learning (MARL).

The shift is bigger than 'more agents'. The moment two learners share a world, each one's best move depends on what the others are doing — and what the others are doing keeps changing as they learn too. The ground beneath your feet is no longer fixed. That single fact reshapes almost everything, and it is why MARL is both fascinating and genuinely hard.

The formal picture: from MDPs to Markov games

Single-agent RL is built on the Markov Decision Process (MDP): states, actions, transitions, rewards. Multi-agent RL generalises this to a Markov game (also called a stochastic game). Now there are N agents. At each state, every agent picks an action; the environment moves to a new state based on the joint action of everyone; and each agent receives its own reward.

Two changes carry all the weight. First, the transition depends on the joint action, not one agent's action — so no single agent fully controls the outcome. Second, each agent has its own reward function, so their goals can align, clash, or anything in between. An ordinary MDP is just the special case of a Markov game with one agent.

\mathcal{P}\!\left(s' \mid s, a_1, \dots, a_n\right) \qquad r_i\!\left(s, a_1, \dots, a_n\right)

The two changes that make a Markov game: the transition and each agent's reward both depend on the joint action of all agents.

Three flavours: cooperate, compete, or both

How the agents' rewards relate to each other sorts MARL into three families. In cooperative MARL, everyone shares (or nearly shares) one reward — a rescue team, a fleet of delivery drones, a power grid balancing load. Success is collective; the challenge is coordination.

In competitive MARL, one agent's gain is another's loss — the zero-sum world of board games, fighting games, and pursuit-evasion. Here the opponent is actively trying to beat you, so improving means out-thinking a moving adversary. Most real systems live in the middle: mixed cooperative–competitive settings, like team sports (cooperate with teammates, compete with rivals) or markets (traders share infrastructure yet compete for profit).

Ask: do the agents share a reward? If yes → cooperative.
Do gains for one mean losses for another? If yes → competitive (often zero-sum).
Is it some of each, perhaps within teams? Then it's mixed — the most common and the hardest.

What does 'optimal' even mean now?

In single-agent RL there is a clean target: the optimal policy that maximises expected reward. With several self-interested learners that idea breaks. Your best policy depends on theirs, and theirs on yours. The standard substitute borrows from game theory: a Nash equilibrium — a set of policies where no single agent can do better by unilaterally changing its own policy while everyone else stays put.

A Nash equilibrium is a kind of mutual best-response: everyone is doing as well as they can, given what everyone else is doing. It is the bedrock concept of MARL — but it is also slippery. Equilibria can be many, can be hard to reach, and 'nobody can improve alone' does not always mean 'this is good for everyone'. We will unpack those troubles next.

J_i\!\left(\pi_i^{*}, \pi_{-i}^{*}\right) \;\ge\; J_i\!\left(\pi_i, \pi_{-i}^{*}\right) \quad \forall\, \pi_i,\ \forall\, i

A Nash equilibrium as mutual best-response: no agent can gain by changing its policy while the others hold theirs fixed.