Markov games

A Markov game is what you get when you take a Markov decision process — the standard single-agent model of states, actions, and rewards — and let several agents act at the same time. The state still evolves with the Markov property, meaning the next state depends only on the current state and the actions taken now, not on the full history. The one change is that the action driving the transition is the joint action of all the players, and each player carries its own reward function.

Concretely a Markov game is the tuple of a set of agents, a shared state space, one action set per agent, a transition rule giving the probability of the next state from the current state and the joint action, one reward function per agent, and a discount factor. When all agents share the same reward it is a cooperative (team) game; when two agents have exactly opposite rewards it is a zero-sum game; everything in between is general-sum. This single framework spans the whole field.

The reason Markov games are the right backbone is that they make the difficulty precise: a single agent cannot define 'optimal' by itself, because the best action depends on what the others do. So we replace the idea of an optimal policy with equilibrium concepts — most famously the Nash equilibrium — and many of the convergence guarantees we enjoy in single-agent RL weaken or disappear.