PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Markov Equilibrium in Stochastic Games

Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang

arXiv:2204.03991v1cs.LGcs.GT

TL;DR

The paper studies whether approximate stationary Markov CCEs can be computed and learned efficiently in general-sum stochastic games. It proves PPAD-hardness for constant-approximation stationary equilibria even in two-player, 1/2-discounted turn-based games, and provides a decentralized algorithm for learning nonstationary Markov CCEs with polynomial complexity.

  • Problem

    The paper addresses the unresolved computational and learning complexity of stationary Markov CCEs in general-sum stochastic games.

    Source: §1 · pp. 2–3

  • Method

    The paper uses reductions from generalized circuit problems and develops SPoCMAR for decentralized learning of nonstationary Markov CCEs with shared randomness.

    Source: §1 · p. 3

  • Results

    Stationary Markov CCE computation is PPAD-hard to approximate within a constant for perfect CCEs, and for stationary CCEs assuming the PCP for PPAD conjecture.

    Source: §1 · p. 3, §3 · p. 8

  • Takeaways & Limitations

    Efficient stationary Markov CCE computation is ruled out under the stated hardness results, while nonstationary Markov CCE learning can avoid exponential dependence on the number of agents.

    Source: §1 · p. 3

    The stationary CCE hardness result relies on the PCP for PPAD conjecture.

    Source: §5.1 · p. 16

Abstract

from arXiv · show

We show that computing approximate stationary Markov coarse correlated equilibria (CCE) in general-sum stochastic games is computationally intractable, even when there are two players, the game is turn-based, the discount factor is an absolute constant, and the approximation is an absolute constant. Our intractability results stand in sharp contrast to normal-form games where exact CCEs are efficiently computable. A fortiori, our results imply that there are no efficient algorithms for learning stationary Markov CCE policies in multi-agent reinforcement learning (MARL), even when the interaction is two-player and turn-based, and both the discount factor and the desired approximation of the learned policies is an absolute constant. In turn, these results stand in sharp contrast to single-agent reinforcement learning (RL) where near-optimal stationary Markov policies can be efficiently learned. Complementing our intractability results for stationary Markov CCEs, we provide a decentralized algorithm (assuming shared randomness among players) for learning a nonstationary Markov CCE policy with polynomial time and sample complexity in all problem parameters. Previous work for learning Markov CCE policies all required exponential time and sample complexity in the number of players.

1 Introduction

The paper studies equilibrium computation and learning in stochastic games, focusing on the previously unresolved complexity of stationary Markov CCEs. It proves stationary CCE computation is hard while providing an efficient decentralized method for learning nonstationary Markov CCEs.

1 Introduction

  • Stochastic games generalize Markov decision processes to multiple agents, with rewards and transitions depending on states and joint actions.They model settings including games, autonomous driving, and economic-policy evaluation.Source: §1 · p. 2
  • Normal-form games admit efficient computation of correlated and coarse correlated equilibria, but equilibrium computation and learning become more intricate in multi-step stochastic games.Stochastic games allow history-dependent strategic behavior, motivating Markov and stationary policy classes.Source: §1 · p. 2
  • Stationary Markov CCE computation was previously unresolved in stochastic games, whereas approximate nonstationary Markov CCEs can be computed efficiently by backward induction.Prior learning methods for nonstationary CCEs either cannot output Markov equilibria or require exponentially many samples in the number of agents.Source: §1 · pp. 2–3
  • The paper establishes intractability for computing stationary Markov CCEs in 2-player discounted general-sum stochastic games, including constant-approximation hardness for perfect CCEs and conjecturally for stationary CCEs.The perfect CCE result is unconditional, while the stationary CCE result assumes the PCP for PPAD conjecture.Source: §1 · p. 3
  • The paper introduces SPoCMAR, a learning algorithm for nonstationary Markov CCEs whose sample complexity is linear in the number of agents.SPoCMAR can be implemented decentrally when agents share common randomness.Source: §1 · p. 3

2 Problem Formulation & Preliminaries

The paper formalizes discounted stochastic games, Markov policy classes, equilibrium notions, learning access, turn-based structure, and the complexity framework used for its results.

2.1 Stochastic games

  • A discounted stochastic game specifies finite states and actions, player rewards, transition probabilities, a discount factor, and an initial-state distribution.Stationary policies map states to action distributions, while nonstationary policies may also depend on the step count.Source: §2.1 · p. 4
  • Joint Markov policies prescribe distributions over joint actions at each state, and trajectories generate discounted value functions for each player.Nonstationary policies use step-indexed value functions because their action distributions vary over time.Source: §2.1 · pp. 4–5
  • The formulation truncates infinite nonstationary policies to finitely many steps and uses fixed continuation behavior after the truncation horizon.This preserves only a small discounted approximation loss from later steps.Source: §2.1 · pp. 4–5, §2.2 · p. 6

2.2 Equilibrium notions

  • Approximate stationary, nonstationary, and perfect CCEs are defined through players’ gains from best-response deviations, with perfect notions requiring the condition state by state.In turn-based games, CCE and Nash equilibrium notions coincide because product policies suffice without loss of generality.Source: §2.2 · pp. 5–6
  • The corresponding Nash equilibria are the product-policy versions of these CCE notions, and perfect Markov Nash equilibria exist in discounted stochastic games.Best responses to Markov policies can be taken Markovian and deterministic because they reduce to single-agent MDP problems.Source: §2.2 · p. 6

2.3 The PAC-RL model for stochastic games

  • The PAC-RL model gives agents unknown transitions, rewards, and initial-state distributions, with access only to trajectories generated by selected joint policies.Efficient learning requires exploration, and discounted trajectories are truncated after H proportional to log(1/ε)/(1−γ).Source: §2.3 · p. 7

2.4 Turn-based stochastic games

  • Turn-based games have one controlling player per state whose action determines rewards and transitions, making CCE and Nash notions equivalent for stationary and nonstationary policies.The action dependence is represented through the controller’s action rather than the full joint action profile.Source: §2.4 · p. 7

2.5 PPAD and the generalized circuit problem

  • Equilibrium computation belongs to TFNP because equilibria exist and candidate policies can be efficiently verified.The hardness proofs use PPAD and the PPAD-complete generalized circuit problem as the reduction source.Source: §2.5 · pp. 7–8

3 PPAD-hardness results for stationary equilibria

The paper proves PPAD-hardness for stationary equilibria in two-player, 1/2-discounted turn-based stochastic games and explains the generalized-circuit reduction behind these results.

3 PPAD-hardness results for stationary equilibria

  • For some constant ε, computing ε-perfect NE—and therefore ε-perfect CCE—in 2-player, 1/2-discounted turn-based stochastic games is PPAD-hard.In turn-based games, stationary Nash and coarse correlated equilibria coincide.Source: §3 · p. 8
  • For constants ε,c>0, computing c/S-stationary NE and c/S-stationary CCE is PPAD-hard in 2-player, 1/2-discounted turn-based stochastic games.These bounds address non-perfect stationary notions that do not require equilibrium conditions at every state.Source: §3 · p. 8
  • Assuming the PCP for PPAD conjecture, computing ε-stationary NE and ε-stationary CCE is PPAD-hard in the same game class.The conjectural step relies on hardness of generalized circuits with positive δ.Source: §3 · p. 8, §3.1 · p. 8

3.1 Proof overview for Theorems 3.1 and 3.2

  • The reduction maps generalized-circuit gates to constant-size game gadgets whose stationary equilibrium probabilities approximately satisfy the corresponding gate constraints.Gadgets are connected to mirror the circuit structure, allowing an equilibrium to decode a satisfying circuit assignment.Source: §3.1 · pp. 8–9
  • To obtain two-player hardness, the construction transforms the circuit into one with a valid coloring that prevents reward conflicts across gadgets.The resulting 2-player game preserves the property that equilibrium policies yield approximately satisfying circuit assignments.Source: §3.1 · p. 9
  • The proof route passes through perfect well-supported Nash equilibria in stage games before reaching perfect Nash equilibria in stochastic games.The full lower-bound proofs are supplied later in the paper.Source: §3.1 · p. 9

4 A Nearly Decentralized MARL Algorithm

The section presents SPoCMAR, a nearly decentralized algorithm for learning nonstationary Markov CCEs in general-sum stochastic games. It combines bandit learning, optimistic exploration, and policy covers to achieve polynomial complexity, with an implementation requiring shared randomness but no communication.

4 A Nearly Decentralized MARL Algorithm

  • The infinite-horizon discounted learning problem is reduced to a finite-horizon undiscounted problem with H := log 1/ϵ divided by 1−γ, preserving nonstationary equilibria up to additive error ϵ.The reduction uses γ^H ≤ϵ and supports comparison with prior finite-horizon episodic learning work.Source: §4 · pp. 9–10, §4.3 · p. 11

4.1 Preliminaries for adversarial bandit routine

  • Adversarial bandit instances provide the statewise learning routine, using high-probability regret guarantees and polynomial time per step.Each player updates a bandit instance when the relevant state is encountered, based on observed action and loss information.Source: §4.1 · p. 10, §4.2 · p. 11

4.2 The SPoCMAR algorithm

  • The algorithm combines statewise adversarial bandits, Rmax-style optimistic rewards, and a policy cover that preserves exploratory policies learned at earlier stages.Stages search for policies that visit each state-step pair with probability at least p, then use visitation estimates to decide whether further exploration is needed.Source: §4.2 · p. 11

4.3 Guarantee for SPoCMAR

  • SPoCMAR outputs an ϵ-nonstationary CCE with probability at least 1 −δ and polynomial sample and computational complexity in the relevant game parameters, including the number of players.The guarantee applies first to finite-horizon general-sum stochastic games and extends to γ-discounted games through the finite-horizon reduction.Source: §4.3 · pp. 11, 13

4.4 Proof overview for Theorem 4.2

  • The proof constructs an optimistic intermediate game that grants maximum future rewards at insufficiently visited state-step pairs, then transfers the CCE guarantee to the true game when those pairs are rarely visited.No-regret learning establishes the guarantee in the intermediate game, while optimism and the termination criterion control the difference from the true game.Source: §4.4 · p. 13

4.5 Implementing SPoCMAR in a decentralized manner

  • SPoCMAR can be decentralized with common randomness: agents observe their own trajectories, communicate nothing, and jointly sample the output policy using O(H3S2K log(SK)) random bits.The decentralized implementation relies on shared random indexing of stored actions and local bandit, value, and visitation computations.Source: §4.5 · pp. 13–14

5 Proofs for Section 3

This section develops the PPAD-hardness reduction from generalized circuits to approximate equilibria in two-player turn-based discounted stochastic games. It constructs and composes constant-size gadgets and valid-coloring assignments to establish hardness for approximate stationary equilibria, including CCEs and stationary NEs.

5 Proofs for Section 3

  • The proof reduces solving ǫ-GCircuit or (ǫ, δ)-GCircuit to computing corresponding equilibria in a two-player turn-based stochastic game.The construction proceeds through equilibrium reductions, gate gadgets, and a composition of those gadgets; policies are stationary Markov unless stated otherwise.Source: §5 · pp. 14–15

5.1 Additional preliminaries for PPAD

  • For hardness proofs, every generalized-circuit node may be made the output of a gate by adding a gate enforcing value 1±ǫ, without invalidating solutions.The resulting circuit remains valid, and Brouwer’s fixed point theorem guarantees it has a solution.Source: §5.1 · p. 15
  • The section relies on the fact that ǫ-GCircuit is PPAD-complete for a constant ǫ, while PPAD-hardness of (ǫ, δ)-GCircuit remains conjectural [BPR15].The cited conjecture posits constants ǫ, δ for which EOTL reduces to (ǫ, δ)-GCircuit.Source: §5.1 · p. 16

5.3 Reductions between notions of equilibria

  • For a turn-based stochastic game, Lemma 5.8 states that from a product stationary policy that is an ε-perfect NE or ε-NE, one can construct a policy in polynomial time.The lemma follows immediately from Lemmas 5.5 and 5.6, taking p = 1 because the game is turn-based.Source: §5.3 · p. 20

5.4 Implementing the gates with “stochastic game gadgets”

  • Each arithmetic gate is implemented by a constant-size turn-based stochastic-game gadget, and WSNE conditions imply that all or most states are approximately unimprovable.Under ǫ-PWSNE-SG all states are ǫ-unimprovable; under ǫ-WSNE-SG, a fraction 1−1/k are ǫ·k-unimprovable.Source: §5.4 · pp. 20–21
  • The G←(b||v) gadget forces π(v) = b when v is ǫ-unimprovable and ǫ < (1 −γ)/2.The gadget uses absorbing transitions and rewards b and 1 − b for the two actions.Source: §5.4 · p. 24
  • The G< gadget makes v3 respond to an ǫ-separated comparison between v1 and v2 whenever v3 and its helper node w are ǫ′-unimprovable and γ|β|ǫ −2γ2 > ǫ′.It yields 1 ± ǫ when π(v1) ≤ π(v2) − ǫ and 0 ± ǫ when π(v1) ≥ π(v2) + ǫ.Source: §5.4 · p. 25

5.5 Gluing gadgets via valid colorings

  • Valid colorings resolve conflicts caused by assigning all non-helper states to player V and all helper states to player W, enabling the circuit gadgets to embed in a two-player game.The construction introduces valid colorings so helper-state reward requirements do not disagree at shared states.Source: §5.5 · pp. 26–27
  • Lemma 5.12 gives a polynomial-time transformation to a validly colored circuit whose approximate assignments restrict to (133√ǫ)-approximate assignments of the original circuit.The transformed circuit extends the original while preserving approximate satisfiability under restriction.Source: §5.5 · p. 27
  • The gluing gadget extends a valid coloring while preserving gate validity, and any satisfying assignment keeps |π(a) −π(a′)| ≤66 · √ǫ.The construction uses O(1/√ǫ) added nodes and gates.Source: §5.5 · pp. 28–29
  • The gadget composition approximates each original G×,+ gate within 133√ǫ, while preserving all but a Cδ/√ǫ fraction of gates under approximate assignments.Each supplementary gate set has size O(1/√ǫ).Source: §5.5 · p. 29
  • An ǫ-assignment problem for validly colored generalized circuits reduces in polynomial time to ǫ′-PWSNE-SG in 2-player turn-based γ-discounted stochastic games, with γ = ǫ2 and ǫ′ = ǫ4.The analogous WSNE-SG reduction handles an (ǫ, 3δ)-assignment using ǫ′′ = ǫ′ · δ.Source: §5.5 · p. 30
  • Restricting an ǫ′-PWSNE-SG to circuit nodes yields an ǫ-approximate assignment, while an ǫ′′-WSNE-SG yields an ǫ-approximate assignment for at least a 1−3δ fraction of gates.The stochastic-game construction is two-player, turn-based, and uses binary actions; its rewards remain bounded by 1.Source: §5.5 · pp. 30–31
  • These reductions prove PPAD-hardness for computing approximate stationary equilibria in 2-player 1/2-discounted stochastic games, including c · ǫ16_0-perfect NE and c · ǫ18_0δ2_0-stationary NE.In turn-based games, stationary policies can be converted to product policies, so approximate CCE computation inherits the hardness result.Source: §5.5 · pp. 32–33

6 Proofs for Section 4

This section proves Theorem 4.2 by analyzing SPoCMAR through discounted-to-finite-horizon reductions, concentration and termination properties, and an intermediate restricted game. It establishes an approximate CCE guarantee in the restricted game and transfers it to the original game by controlling visits outside the restricted region.

6.1 Preliminaries for finite-horizon stochastic games

  • The proof of Theorem 4.2 proceeds through finite-horizon stochastic games after truncating the discounted game and scaling rewards by γ^(h−1), yielding a 2ε-CCE from an ε-CCE.The finite horizon is chosen so that γ^H ≤ ε, and trajectories from the discounted game can simulate the finite-horizon PAC-RL model.Source: §6 · p. 33, §6.1 · p. 34

6.2 Parameters & concentration inequalities

  • SPoCMAR terminates after at most SH stages, while its visitation and coverage estimates hold simultaneously with probability at least 1−δ under the stated concentration events.The visitation guarantee applies across stages and time steps; coverage follows from repeated visits and a Chernoff bound.Source: §6.2 · pp. 35–36

6.3 Intermediate game

  • The intermediate game G_bV preserves the original game on visited state-time pairs and sends other pairs to a rewarding absorbing sink, enabling value comparison with SPoCMAR’s estimates.Lemma 6.4 establishes the comparison with probability at least 1−2δ, using reverse induction and the coverage event.Source: §6.3 · p. 36
  • The analysis also invokes the no-regret guarantee for SPoCMAR’s bandit learners to bound the difference between the algorithm’s values and the intermediate game’s values.Lemma 6.5 provides this bound on an event occurring with probability at least 1−δ.Source: §6.3 · p. 38
  • SPoCMAR’s policy bπ is an approximate CCE in G_bV, with deviation gain at most H · (εreg + 2 · εval) under Ereg ∩ Eval.The argument combines the intermediate-game regret and value guarantees for states in bV with a performance-difference argument for states outside bV.Source: §6.3 · p. 40

6.4 Completion of proof of Theorem 4.2

  • The proof transfers the restricted-game guarantee to G by coupling trajectories and bounding the probability of visiting states outside bV under Evisitation.Lemma 6.7 supplies the visitation control, while the coupling compares rewards and values in G and G_bV.Source: §6.4 · pp. 41–43
  • With probability at least 1−4δ, SPoCMAR’s output policy bπ is an ε-(nonstationary) CCE of G.Lemma 6.8 bounds every player’s deviation by H · (εreg + 2 · εval) + 2H^2 · (pS + εtvd) ≤ ε, and the theorem follows after parameter choices.Source: §6.4 · pp. 42, 44

A Related Work

Prior work provides efficient equilibrium computation and learning in normal-form and two-player zero-sum stochastic games, but general-sum stochastic games remain substantially harder. Multi-agent RL approaches in general-sum settings achieve convergence only under restrictive assumptions or produce non-Markovian policies.

Equilibrium computation complexity in games

  • General-sum normal-form CCEs are efficiently computable by linear programming or no-regret learning, unlike Nash equilibria, which are PPAD-complete even for two players.Source: A Related Work · p. 50
  • For stochastic games, computing Markov perfect Nash equilibria in general-sum settings is PPAD-complete, with additional hardness results for pure-strategy and memoryless approximate equilibria.Source: A Related Work · p. 50

Multi-agent RL in stochastic games

  • Two-player zero-sum stochastic games have received extensive attention, including time- and sample-efficient algorithms for learning Markovian Nash equilibria.Source: A Related Work · p. 50
  • General-sum multi-agent RL methods include Q-learning variants with convergence under restrictive assumptions, while correlated Q-learning has shown empirical convergence in several stochastic games.Source: A Related Work · p. 50
  • V-learning methods learn nonstationary correlated or coarse correlated equilibria with tighter sample complexity than this work, but their output policies are not Markovian.Source: A Related Work · p. 50

B On the Gates Used in GCircuit

The construction implements the generalized-circuit gates omitted from the stated definition using the available gate set. These substitutions preserve approximate assignments, and the resulting ε-GCircuit problem remains PPAD-complete for a constant ε.

Gate implementations

C Adversarial bandit guarantees

The adversarial bandit analysis uses conditional-expectation identities and Azuma–Hoeffding concentration over an appropriate filtration. A union bound is then applied to the resulting difference sequences.

Guarantee derivation

Related papers

Loading 2204.03991v1…