Stochastic Games

Definition

Stochastic games are multi-agent sequential decision problems where the current state, the agents’ joint action, and a transition kernel determine a probability distribution over next states. Each agent has its own payoff or cost objective over the resulting trajectory.

Why It Matters

They are the game-theoretic ancestor of modern Markov games in MARL. They make explicit which parts of a multi-agent learning problem are the stationary environment model, which parts are strategic objectives, and which parts come from agents learning or adapting on top of that model.

Formalism / Key Objects

• In Fink’s discounted finite formulation, each state i has per-player action sets J_h(i). A joint action j=(j_1,...,j_n) induces transition probabilities P_{ijk} and player-specific stage costs C_{hij}.
• A stationary mixed strategy gives each player h and state i a probability distribution x^h(i) over actions in J_h(i).
• The expected discounted cost vector for player h under stationary profile x satisfies:

$$e_{hi}(x)=\sum _j\prod _m{x}_{j_m}^m(i)\left[C_{hij}+{\alpha }_h\sum _k{P}_{ijk}{e}_{hk}(x)\right].$$

• An equilibrium stationary profile is one where no player can reduce its expected discounted cost by changing its own state-wise mixed strategy while the other players’ stationary strategies remain fixed.
• Discounted Stochastic Game Equilibrium records Fink’s contraction-plus-Kakutani proof that such equilibria exist in finite discounted n-person stochastic games.

Connections

• Fink1964 - Equilibrium in a Stochastic n-Person Game provides a compact existence theorem for finite discounted n-person stochastic games.
• Multi-Agent Non-Stationarity uses Markov-game structure as the stationary baseline, then studies how concurrent policy updates make each agent’s induced environment move.
• Constrained Markov Potential Games add coupled constraints and potential-game structure to Markov games in order to recover tractable feasible Nash-policy learning.
• Cooperative Multi-Agent Reinforcement Learning often specializes stochastic games to shared rewards, centralized training, decentralized execution, and empirical benchmark regimes.
• Mean-Field Reinforcement Learning approximates very large stochastic games through a representative agent and a population distribution.
• Constrained Markov Decision Processes are the single-agent constrained analogue; stochastic games restore strategic dependence among multiple decision makers.

Common Confusions

• A stochastic game can be stationary even when a learning algorithm operating in it faces non-stationarity from changing opponent policies.
• “Markov game” is often the modern RL term for similar state-action-transition structure, while “stochastic game” is the older game-theory term.
• Cooperative MARL removes conflicting rewards only in special cases; stochastic games in general allow each agent to have a different payoff or cost.
• Equilibrium existence does not by itself give an efficient learning algorithm or a guarantee that independent learners will converge.

Key Sources

• Fink1964 - Equilibrium in a Stochastic n-Person Game
• Papoudakis2019 - Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning
• Alatur2024 - Provably Learning Nash Policies in Constrained Markov Potential Games
• Gu2022 - Multi-Agent Constrained Policy Optimisation
• Jusup2024 - Safe Model-Based Multi-Agent Mean-Field Reinforcement Learning