Is a Markov decision process a special case?

A single-agent version removes the strategic interaction with other decision makers.

Must every transition be random?

No. Deterministic transitions can be represented by probabilities zero and one.

Does every stochastic game have the same solution method?

No. Available guarantees and methods depend on assumptions such as rewards, information, horizon, and game structure.

AI Glossary / Graphs and symbolic AI / Intermediate

Stochastic games

Definition

Stochastic games are models of sequential interaction in which several players choose actions, receive rewards, and influence probabilistic transitions between states. A player's best choice can depend both on what other players do now and on how the joint action changes future opportunities. They extend single-agent decision models to settings with strategic interaction.

What it means

The state describes the current situation, such as available capacity or the position of a shared resource. Each player has available actions, and the combination of their choices determines immediate rewards and a distribution over the next state.
The players' objectives may align, conflict, or overlap only partly. A zero-sum game makes one player's gain another's loss, while a general-sum game need not. The model also needs a time horizon or a rule for valuing future rewards. Random transitions and strategic choices are separate ingredients: uncertainty alone does not make a single-agent process a multiplayer game.

How it works

Specify the players, states, actions, reward functions, and transition probabilities. For each state and joint action, the transition probabilities must form a valid distribution over next states. Define how rewards accumulate, for example through a finite horizon or discounted sum.
A policy describes how a player chooses actions from available information. In a fully observed Markov formulation, current-state policies are an important class, but the appropriate strategy space and solution concept depend on the game. Evaluating a joint action includes its immediate reward and expected continuation value. Solving the game additionally requires reasoning about the other players' incentives; merely averaging random outcomes does not settle that strategic problem.

Three practical examples

A shared-resource simulation can model several autonomous agents whose usage choices affect congestion.
A multiplayer game environment can include probabilistic movement or resource changes influenced by several players.
A multi-agent learning experiment can study cooperation and competition when each agent's actions change the others' future rewards.

Think of it this way

Think of several teams using a shared facility. Their choices affect what they receive today and whether the facility remains easy to use tomorrow. The analogy is limited because a stochastic game requires explicit states, actions, probabilities, and reward definitions; ordinary descriptions of competition do not automatically supply a complete mathematical model.

Worked example

Consider an original two-agent simulation with two states: free capacity and congested capacity. At the current free state, each agent chooses considerate use C or aggressive use A. Define immediate reward pairs as follows: C,C gives (1,1); C,A gives (0,4); A,C gives (4,0); and A,A gives (3,3).
The probability that the next state is free is 0.9 after C,C, 0.5 after either mixed pair, and 0.2 after A,A. The remaining probability leads to congestion. Each row therefore assigns total probability one.
For a single decision calculation, stipulate that each agent's continuation value is 10 in the free state and 2 in the congested state. These are supplied estimates for this example, not values obtained by solving the whole game. Use discount factor 0.9.
Under C,C, each agent's estimated total is 1 + 0.9 × (0.9 × 10 + 0.1 × 2). The expected continuation is 9.2, so the result is 1 + 8.28 = 9.28.
Under A,A, each estimate is 3 + 0.9 × (0.2 × 10 + 0.8 × 2). The expected continuation is 3.6, giving 3 + 3.24 = 6.24. Although mutual aggressive use gives a larger immediate reward, its worse transition prospects reduce this estimated total.
If the second agent chooses C while the first chooses A, the first agent obtains 4 + 0.9 × (0.5 × 10 + 0.5 × 2) = 9.4. The considerate agent obtains 0 + 5.4 = 5.4.
Thus the attractive joint outcome C,C does not by itself remove the incentive to deviate in this one-step calculation: 9.4 exceeds 9.28. The example separates a joint-benefit comparison from an individual-incentive comparison. It does not establish a stationary equilibrium, because that would require a complete model at both states and continuation values consistent with the resulting policies.

Illustrative case study

In a fictional multi-agent laboratory, researchers simulate two controllers sharing a limited processing resource. They vary how current usage affects future capacity and compare joint reward with each controller's individual reward.
When a cooperative-looking outcome proves unstable, they inspect the incentives rather than blaming random transitions alone. They also test whether the state variables capture the relevant history. This fictional case illustrates model analysis.

Common misconceptions and mistakes

Stochastic games are not simply repeated independent lotteries. Actions can alter the next state and therefore future choices. They are also not necessarily zero-sum, and a high combined reward does not automatically imply that every player will choose the corresponding actions.
Do not import an equilibrium guarantee from one restricted game class into all multi-agent settings. Do not mistake estimated continuation values for a solved game. Finally, uncertainty about other players' policies is different from the environment's transition randomness, even when both affect observed outcomes.

Business use

The framework can help teams reason about automated systems that interact through shared resources or competing objectives. It makes clear why optimizing each component in isolation may not produce the desired combined behavior.
Before using such a model, define whose rewards are represented and how they relate to the real objective. Inspect incentives, transition assumptions, and information available to each agent. Evaluate both individual and joint outcomes. A model that rewards short-term resource capture may teach agents behavior the system owner did not intend.

Check your understanding

Why does the example not prove that considerate use will be chosen just because its joint estimated reward is higher?

Answer: A player can have an individual incentive to deviate. Joint desirability and strategic stability are different properties.

Related terms

Markov decision process
Joint action
Transition probability
Zero-sum games
Markov game
Multi-agent reinforcement learning
Discounted reward
Nash equilibrium
Zero-sum game

Learn next

Next, replace the aggressive player's mixed-pair reward of four with three. Its one-step estimate becomes 8.4 instead of 9.4, below 9.28. Explain how this changes that particular deviation comparison while leaving the full game's unresolved continuation-policy question intact.

Sources

Primary source: Lloyd Shapley, Stochastic Games, 1953, original paper: https://cs.siu.edu/~hexmoor/classes/CS539-F10/Shapley.pdf . The paper introduces state transitions controlled jointly by players and studies a specific two-player zero-sum setting. Littman, Markov Games as a Framework for Multi-Agent Reinforcement Learning, general formulation: https://courses.cs.duke.edu/cps296.3/spring07/littman94markov.pdf . The resource example is original.

Previous: Stochastic edit Next: Stochastic gradient descent