PaperlayerView exact revision on arXiv

Source-linked AI summary

Independent Reinforcement Learning in Discounted Markov Games

Asrin Efe Yorulmaz, Ugur Aydin, Tamer Basar

arXiv:2609.00504v1cs.GTcs.AIcs.LGeess.SYmath.OC

TL;DR

Computing equilibria in discounted general-sum Markov games is challenging because strategic interactions affect future state distributions, especially when agents learn independently with limited coordination. This paper develops layered optimistic mirror descent and shows sub-exponential convergence alongside a matching complexity barrier: under ETH for PPAD, inverse-polynomially accurate coarse correlated equilibria cannot generally be computed in polynomial time.

  • Problem

    Equilibrium computation in Markov games must handle both strategic fixed points and the intertemporal effects of actions on future state distributions.

    Source: §1 · p. 2

  • Method

    The paper uses layered optimistic mirror descent with increasing step sizes, extending it to full-feedback and partial-feedback learning by controlling changing history-occupancy weights.

    Source: §3 · p. 8, §7 · p. 20

  • Results

    Under ETH for PPAD, no polynomial-time algorithm computes inverse-polynomially accurate sparse CCEs for fixed-discount discounted general-sum Markov games, while the proposed algorithm achieves quasi-polynomial-time, sub-exponential convergence guarantees.

    Source: §1 · p. 4, §7 · p. 20

  • Takeaways & Limitations

    Radically uncoupled learning can converge to coarse correlated equilibria in unrestricted discounted general-sum Markov games, but polynomial-time computation remains ruled out under the stated complexity assumption.

    Source: §1 · p. 4, §7 · p. 20

    A gap remains between the paper’s quasi-polynomial upper bounds and computational lower bounds, leaving the precise complexity of sparse CCE computation open.

    Source: §7 · p. 21

Abstract

from arXiv · show

In this work, we study radically uncoupled learning in discounted general-sum Markov games. Assuming ``$\mathsf{ETH}$ for $\mathsf{PPAD}$", we show that, for every fixed discount factor, there is no polynomial-time algorithm for computing inverse-polynomially accurate coarse correlated equilibria in discounted general-sum Markov games when players learn independently in decentralized settings. Complementing this hardness result, we provide what appears to be the first \emph{radically uncoupled} algorithm with sub-exponential convergence guarantees to coarse correlated equilibria in discounted general-sum Markov games without imposing any structural restrictions on the game. Our algorithm is a \emph{layered} variant of optimistic mirror descent with an increasing step-size schedule tailored to the multi-agent setting. Finally, we develop both full-feedback and partial feedback versions of the aforementioned algorithm and establish sub-exponential convergence guarantees for each case.

1 Introduction

The paper studies approximate coarse correlated equilibrium computation in discounted general-sum Markov games under radically uncoupled learning, where agents use only local feedback without communication or shared randomness. It develops layered optimistic mirror-descent methods with quasi-polynomial guarantees and proves complementary computational hardness under ETH for PPAD.

Problem setting

  • Markov games combine equilibrium computation with intertemporal dynamics, because policies affect both immediate rewards and future state distributions.Unlike normal-form games, unilateral deviations change future-state distributions; unlike single-agent MDPs, policy values depend on other players’ policies.Source: §1 · pp. 1–2

Decentralized information

  • Radically uncoupled learning forbids observing opponents’ policies, losses, value functions, or random bits, so each player updates from local feedback alone.These restrictions eliminate communication, shared randomness, policy revelation, and correlation devices while avoiding centralized coordination overhead.Source: §1 · p. 2

Challenges and prior work

  • General-sum Markov games obstruct direct no-regret arguments because deviations induce unknown, time-varying comparison distributions over future states.Existing decentralized methods often rely on coordination or common randomness and therefore do not provide online regret guarantees for independently played product policies [Jin et al., 2023, Song et al., 2022, Mao and Ba¸sar, 2023, Daskalakis et al., 2023].Source: §1 · p. 3

Finite-horizon algorithms

  • The paper introduces layered smoothed-entropy optimistic online mirror descent with increasing step sizes, obtaining finite-horizon CCE guarantees against history-dependent deviations.Under unknown models and a reachability condition, it also proves a high-probability finite-horizon guarantee with the same exponential-in-horizon dependence up to polynomial factors.Source: §1 · p. 4

Discounted-game guarantees

  • For discounted games, horizon truncation and error bounds yield quasi-polynomial-time and quasi-polynomial-sample algorithms for inverse-polynomially accurate sparse discounted CCEs under full and partial feedback.The guarantees cover both finite-horizon and infinite-horizon discounted Markov games.Source: §1 · p. 4

Computational hardness

  • Assuming ETH for PPAD, for every fixed rational discount factor and polynomial support bound, some inverse-polynomial accuracy requires superpolynomial time for sparse approximate CCE computation.This lower bound applies to both finite-horizon and infinite-horizon discounted general-sum Markov games with independent decentralized learning.Source: §1 · p. 4

2 Preliminaries and Notations

This section establishes notation and formalizes finite-horizon, discounted, and truncated Markov games. It also defines policy classes, feedback and value-function conventions, discounted regret and CCE, and truncation error.

2.1 Notations

  • Basic notation fixes finite sets, probability simplices, action probabilities, natural logarithms, and binary-string input representations.Source: §2.1 · p. 4

2.2 Undiscounted Finite-horizon Markov games

  • An undiscounted finite-horizon Markov game has layered states, finite player action sets, transition kernels, and costs in [0, 1], with both general and Markov policy representations.The maximum action-set size is denoted Amax; Markov policies induce product action distributions at each state.Source: §2.2 · p. 5

2.3 Discounted Markov games

  • The finite- and infinite-horizon discounted games use deterministic initial states, finite action sets, transition kernels, bounded costs, general or nonstationary Markov policies, and discounted values defining regret and CCE.The infinite-horizon case uses a stationary transition kernel and cost function, while the policy convention permits nonstationary Markov policies.Source: §2.3 · p. 7

2.4 Truncated Markov Games

  • Truncated Markov games retain the original game through layer L, extend an L-step profile with uniform reference play, and quantify the discounted tail by τL, ¯H(γ) ≤ γ^L/(1−γ).The extension plays the truncated profile for the first L layers and the reference policy afterward.Source: §2.4 · p. 8

3 Main Algorithm and Results for Episodic Markov Games

The section develops layered optimistic mirror descent for episodic general-sum Markov games, addressing unknown, time-varying history-occupancy weights through layer-dependent learning rates. It establishes approximate CCE guarantees under full feedback and extends them to partial feedback using exploration and blocked Q-function estimation under reachability.

3 Main Algorithm and Results for Episodic Markov Games

  • Markov-game regret is weighted by deviation-induced history occupancies, whose unknown and time-varying drift must be controlled alongside online learning.The analysis rewrites regret into local weighted terms and uses the no-regret-to-CCE connection for empirical play.Source: §3 · p. 8

3.1 Episodic Markov games under full-feedback

  • Under full feedback, Layered OOMD combines smoothed entropy with increasing layer-wise step sizes so earlier policies move slowly while later layers adapt faster, yielding an approximate CCE guarantee.The schedule is designed specifically to manage occupancy-weight drift, unlike increasing-rate schemes motivated by exploration; the proof controls weighted regret, policy movement, and Q-function variation.Source: §3.1 · pp. 9–10

3.2 Episodic Markov games under partial feedback

  • Under partial feedback, blocked policy updates, an action-exploration floor, and trajectory-based Q-estimation extend the guarantee to (κ, ζ)-reachable games, with exponential horizon dependence and additional polynomial exploration and estimation overhead.The exploration floor supports state-action coverage, while comparator smoothing controls the resulting error; the empirical distribution is an ε-approximate CCE with probability at least 1 − δ.Source: §3.2 · pp. 11, 13

4 Approximating Equilibrium Discounted Markov Games

The section transfers finite-horizon regret guarantees to discounted Markov games by truncating the discounted horizon and controlling the geometric tail. This yields sub-exponential or quasi-polynomial convergence guarantees for both full-feedback and partial-feedback learning.

4.1 A transfer principle

  • Choosing the effective horizon L_ε = min{H̄, H_γ^ε} makes H_γ^ε = O(log(1/ε)) for fixed γ < 1, yielding quasi-polynomial rather than horizon-exponential discounted-game bounds.The truncated discounted game is solved with the finite-horizon algorithms after replacing the original horizon by the effective discounted horizon.Source: §4 · p. 13, §4.1 · p. 15

4.2 Full-feedback and Partial-feedback consequences

  • Theorem 3 is instantiated in Corollaries 1 and 2 to provide discounted CCE guarantees for the full-feedback and partial-feedback algorithms.The partial-feedback guarantee assumes the truncated discounted game is (κ, ζ̄_ε,L_ε)-reachable and provides an ε-approximate discounted CCE with probability at least 1 − δ.Source: §4 · p. 14, §4.2 · pp. 15–16

4.1 A transfer principle

  • Discounting permits finite-horizon truncation: controlling the first L layers and bounding the geometric tail transfers finite-horizon regret to an (ε_alg + τ_L, H̄(γ))-approximate discounted CCE.The construction uses sparse distributions over finite-horizon product-policy prefixes with a fixed reference continuation beyond truncation.Source: §4.1 · p. 14

5 Computational Lower Bound for Discounted Markov Games

This section establishes computational lower bounds for discounted Markov-game CCE computation under the ETH for PPAD. Polynomial-time hardness is obtained by reducing bimatrix Nash-equilibrium computation to finite- and infinite-horizon discounted Markov games, extending the result to the radically uncoupled learning setting.

Lower-bound framework

  • Under the ETH for PPAD, polynomial-time computation of sparse discounted CCEs is unlikely for general-sum discounted Markov games, complementing the paper’s quasi-polynomial upper bounds.The search problem asks for a finite sequence of product Markov profiles whose uniform empirical distribution is an approximate discounted CCE; any lower bound for this relaxation also applies to radically uncoupled learning.Source: §5 · pp. 16–18

Reduction from bimatrix games

  • A polynomial-time reduction maps any bimatrix game to a finite-horizon Markov game whose CCE computation implies Nash-equilibrium computation.The construction is polynomial-time and uses a predesignated horizon length.Source: §5 · p. 17

Discounted extension

  • An absorbing-state extension converts finite-horizon games into infinite-horizon γ-discounted games while preserving approximate CCEs up to an ε/γ^(H−1) accuracy factor.The extension and the correspondence are computable in polynomial time.Source: §5 · p. 17

Main hardness theorem

  • Assuming ETH for PPAD, there is a universal constant ε⋆ > 0 such that every algorithm computing an ε⋆-approximate Nash equilibrium for every two-player n × n bimatrix game requires n^log^(1−o(1)) n time.Source: §5 · p. 17

Finite-horizon corollary

  • In finite-horizon discounted Markov games, no polynomial-time algorithm can output at most N^Cfh product Markov profiles with CCE gap at most N^−Kfh against all history-dependent deviations.This corollary holds for a constant discount factor γ ∈ (0,1) under the ETH for PPAD.Source: §5 · p. 19

6 Numerical Results

The numerical results evaluate the proposed independent learning dynamics under full and partial feedback on four finite-horizon Markov games, and test discounted truncation on a linear-quadratic benchmark with a closed-form solution. CCE gaps decrease under both feedback models, while the benchmark approximation error decreases rapidly.

6.1 Finite-horizon episodic Markov games

  • The finite-horizon experiments use a battle-of-the-sexes chain, routing/congestion game, three-player public-goods game, and transition-trap game, each with every state having occupancy probability at least 0.05 under every product Markov profile.Thus, all four games are (0.05, ζ)-reachable for every ζ ∈(0, 1].Source: §6.1 · p. 19
  • CCE gaps decrease in all four finite-horizon Markov games under both full-feedback and independently sampled partial-feedback dynamics.Figure 1 reports deterministic full-feedback behavior and means over 20 partial-feedback runs with empirical standard-deviation bands, supporting Theorems 1 and 2.Source: §6.1 · p. 20, Figure 1 · p. 20

6.2 Discounted linear-quadratic benchmark

  • The two-state zero-sum discounted linear-quadratic benchmark shows that the finite-approximation error decreases rapidly against a closed-form infinite-horizon discounted saddle-point solution.The simulation discretizes the action interval while retaining the closed-form saddle-point actions in the grid.Source: §6.2 · p. 20

7 Conclusion … B.6 Weighted value-difference decomposition

The paper establishes hardness for CCE computation while presenting radically uncoupled layered OOMD with quasi-polynomial, sub-exponential convergence, including under partial feedback. Its convergence analysis develops smoothed-entropy and OOMD bounds, then controls policy, occupancy, Q-value, and value differences across layers.

7 Conclusion

  • Under “ETH for PPAD,” polynomial-time CCE computation is impossible, while layered OOMD gives quasi-polynomial online self-play with sub-exponential convergence under radically uncoupled information, including partial feedback.The algorithm imposes no structural assumptions on the game and is presented as the first provably convergent method in this setting with a sub-exponential guarantee.Source: §7 · p. 20

A Related Work

  • Optimistic FTRL and OMD variants improve the baseline e O(T −1/2) convergence rate to coarse correlated and correlated equilibria in normal-form games, with recent general-sum results approaching O(1/T).In Markov games, value-based methods have convergence guarantees only under game restrictions, while related decentralized results target weakly acyclic games or two-player zero-sum settings.Source: A Related Work · p. 28

B.1 Properties of smoothed entropy

  • The smoothed negative-entropy regularizer provides bounded Bregman divergence and 1/ρ_i-strong convexity in the ℓ1 norm.Its divergence is bounded by B_i = ρ_i log((1 + λ_i)/λ_i), and D_i(x,y) ≥ 1/(2ρ_i)||x−y||_1^2.Source: §B.1 · pp. 29–30

B.2 Properties of OOMD with smoothed entropy

  • The OOMD analysis derives a weighted regret inequality controlled by Bregman diameter, weight variation, and optimistic prediction error.The proof uses prox inequalities, cancellation of intermediate divergences, strong convexity, Young’s inequality, and summation by parts.Source: §B.2 · pp. 30–31

B.3 First order path of the played policies

  • The played policies have bounded first-order movement because both played and reference updates use a common base point and Q-functions bounded in [0,H].The resulting per-step policy variation satisfies ||x_{t+1}−x_t||_1 ≤ 3ρ_iHη_h.Source: §B.3 · p. 32

B.4 History occupancy variation

  • History-occupancy variation is controlled by decomposing kernel changes across layers, using ℓ1 contraction of stochastic kernels and product-distribution bounds.The argument compares the induced history distributions under a fixed comparator and changing opponents’ product policies, with a separate h = 1 case.Source: §B.4 · pp. 32–33

B.5 Variation bounds on the Q-values

  • Q-value variation decomposes into distribution-shift and future-value terms, yielding Δ_h ≤ 2H(H−h+1)Δ and in particular Δ_h ≤ 2H^2Δ.The bound follows by backward induction from Δ_{H+1}=0 and per-layer losses in [0,1].Source: §B.5 · p. 34

B.6 Weighted value-difference decomposition

  • The weighted value-difference decomposition introduces continuation losses under a comparator and telescopes their layerwise identities from the initial layer to zero terminal values.The continuation value W_h is defined over histories while player i follows the comparator and opponents follow π_t^{-i}.Source: §B.6 · p. 35

B.7 Proof of Theorem 1 … C.3 Regret with uniformly accurate estimates

The appendices establish the full-feedback regret-to-CCE guarantee and extend the analysis to estimated Q-values through comparator smoothing, uniform estimation, and an event-conditioned regret bound. The resulting partial-feedback analysis accounts explicitly for smoothing and Q-estimation errors.

B.7 Proof of Theorem 1

  • The full-feedback proof fixes the regularization parameters to obtain ρ_i = 2, ρ̄ = 2, and B_i = 2 log(|A_i| + 1) before combining the component bounds.The same parameter choices are reused in the estimated-Q analysis.Source: §B.7 · p. 37, §C.3 · p. 42
  • Theorem 1’s regret bound implies an ε-CCE guarantee for the empirical distribution via the standard no-regret-to-CCE equivalence.The proof identifies the left-hand side as player i’s regret and applies the equivalence to obtain the ε-CCE guarantee.Source: §B.7 · p. 37

C.1 Comparator smoothing

  • Comparator smoothing replaces arbitrary history-dependent policies with ζ-smoothed policies while controlling the resulting payoff loss.The proof compares policies layer by layer using Q-functions bounded in sup norm by H.Source: §C.1 · pp. 37–38

C.2 Uniform estimation of Q-values

  • Uniform Q-value estimation relies on independent trajectories within each block, reachability, and an action-probability floor to ensure sufficient observations for every state-action tuple.A union bound over all block, player, layer, state, and action tuples yields the uniform guarantee.Source: §C.2 · pp. 38–40

C Convergence Analysis of Algorithm 2

  • The convergence analysis extends the full-feedback argument to Algorithm 2 by conditioning its regret analysis on uniformly accurate estimated Q-functions.On the event Eξ, the estimated-Q analysis differs from the full-feedback case through estimation-error terms.Source: §C.3 · p. 40

C.3 Regret with uniformly accurate estimates

  • On Eξ, Proposition 2 bounds every player’s regret for Algorithm 2 despite using estimated Q-vectors.The analysis applies the mirror-descent bounds on the restricted simplex and separately controls policy-path and estimated-Q variation terms.Source: §C.3 · pp. 40–41
  • The partial-feedback regret bound includes a cumulative Q-estimation contribution of 2HKξ in addition to the comparator-smoothing error.The proof states that the smoothing comparison contributes 2ζH^2K, while Q-function estimation contributes 2HKξ.Source: §C.3 · pp. 40, 42

C.4 Proof of Theorem 2

The proof combines Lemma 14 and Proposition 2 on a high-probability event to establish the block-level guarantee for every player. Repeating each block policy across its episodes transfers this guarantee to actual trajectories and yields an ε-approximate CCE.

C.4 Proof of Theorem 2

  • Applying Lemma 14 with the specified parameters and Proposition 2 gives the required guarantee for every player with probability at least 1−δ.The argument conditions on the event E_ξε, which holds with probability at least 1−δ by the definition of B_ε.Source: §C.4 · pp. 42–43
  • Because each block repeats its product Markov policy for B_ε episodes, the block-level bound also holds over the N_ε = K_εB_ε actual trajectory episodes.The empirical distribution over trajectory policies equals the empirical distribution over block policies because every π_k is repeated exactly B_ε times.Source: §C.4 · p. 43
  • Consequently, the empirical distribution over the block policies is an ε-approximate CCE.The proof concludes by translating the repeated-block guarantee into the claimed equilibrium guarantee and accounting for the total episode count.Source: §C.4 · p. 43

D Proofs for the Approximation of Discounted Markov Games (Section 4) · D.1 Proofs for the full-feedback case

The appendix proves truncation lemmas for a unified discounted Markov-game model covering finite and infinite horizons, then establishes the full-feedback result by applying the finite-horizon guarantee to a truncated game. The resulting discounted CCE conclusion follows from the standard no-regret-to-CCE equivalence.

D Proofs for the Approximation of Discounted Markov Games (Section 4)

  • The truncation analysis fixes γ ∈ (0, 1) and treats finite-horizon and infinite-horizon discounted games within one unified model.The original horizon may be finite or infinite.Source: D Proofs for the Approximation of… · p. 43
  • Lemma 15 establishes the truncation relation for every policy profile, truncation level L, and player.The proof uses that the original and truncated profiles share their first L decision rules and therefore induce identical trajectories through layer L.Source: D Proofs for the Approximation of… · p. 43
  • Lemma 16 relates an L-step product Markov profile to its extension by comparing the first L decision rules and exploiting nonnegative costs.Ignoring layers after L can only decrease the relevant cost term.Source: D Proofs for the Approximation of… · p. 44
  • Theorem 3 follows by combining the truncation lemmas with the assumed finite-horizon regret guarantee, yielding a bound uniform over all comparator policies.The finite-horizon guarantee applies simultaneously to all players, after which the supremum over general policies is taken.Source: D Proofs for the Approximation of… · p. 44

D.1 Proofs for the full-feedback case

  • Algorithm 1 applies to the truncated game G[L_ε] because its costs remain in [0, 1], so Theorem 1 applies with horizon parameter L_ε.This is the finite-horizon step used in the full-feedback proof.Source: §D.1 · p. 44
  • Corollary 1 obtains discounted coarse correlated equilibrium from the truncated-game regret guarantee and the truncation-error bound.The CCE conclusion uses the standard no-regret-to-CCE equivalence applied to the empirical distribution of joint policies.Source: §D.1 · pp. 44–45
  • The full-feedback proof also derives the total episode bound by substituting the Theorem 1 estimate under λ_i = 1/|A_i| into T_ε.The derivation uses log(1/γ) ≥ 1 − γ and the ceiling inequality ⌈x⌉ ≤ 1 + x.Source: §D.1 · p. 45

D.2 Proof of the partial-feedback case · E Proofs for the Computational Lower Bounds (Section 5)

The partial-feedback proof transfers the finite-horizon guarantee to truncated discounted games, controls truncation and horizon parameters, and derives discounted coarse correlated equilibrium through no-regret equivalence. The lower-bound proofs begin by specifying binary encoding lengths for rational inputs.

D.2 Proof of the partial-feedback case

  • Theorem 2 applies to the truncated game G[L] under the stated (κ, ζ̄_ε,L)-reachability condition.Source: §D.2 · p. 45
  • The partial-feedback argument obtains a high-probability regret guarantee simultaneously for every player.Source: §D.2 · p. 45
  • Extended block policies have average regret at most ε/2 + τ_L,H̄(γ), with truncation error vanishing when L_ε = H̄ < ∞.Source: §D.2 · p. 46
  • The discounted CCE conclusion follows by applying the standard no-regret-to-CCE equivalence to the empirical distribution of extended block policies.Source: §D.2 · p. 46
  • The required effective horizon satisfies L_ε = O(L_H̄,ε), where L_H̄,ε := min{H̄, log(1/ε)} and L_∞,ε = log(1/ε).Source: §D.2 · p. 46
  • The proof concludes after bounding the number of bands and associated parameter expressions up to universal constants.Source: §D.2 · p. 46

E Proofs for the Computational Lower Bounds (Section 5)

E.1 Proof of Algorithms 1 and 2 solving the sparse discounted-CCE problem · E.2 Game size and encoding conventions · E.3 The logarithmic-horizon undiscounted Markov game

The appendix verifies that Algorithms 1 and 2 solve the sparse discounted-CCE problem, fixes game-size encoding conventions, and presents a logarithmic-horizon construction linking sparse CCEs to approximate Nash equilibria. The construction underlies the reduction by ensuring that sufficiently short sparse CCE sequences reveal an approximate Nash equilibrium in the source bimatrix game.

E.1 Proof of Algorithms 1 and 2 solving the sparse discounted-CCE problem

  • The proof establishes that Algorithm 1 satisfies the policy-class and discounted-CCE requirements, thereby solving (Tε, ε)-DiscSparseMarkovCCEgen.Its policies and extensions remain within the prescribed fixed product Markov-policy class.Source: §E.1 · p. 47
  • Algorithm 2 likewise yields an episode-level sequence solving (Nε, ε)-DiscSparseMarkovCCEgen with probability at least 1 − δ.The proof uses blockwise fixed policies and applies the corresponding CCE guarantee to the resulting episode sequence.Source: §E.1 · p. 47

E.2 Game size and encoding conventions

  • Game size is defined as the maximum of horizon, state, action, and transition-or-loss encoding parameters, yielding polynomial-bit descriptions for fixed player count.For infinite-horizon discounted games, the fixed discount factor contributes only a constant-factor change to the size measure.Source: §E.2 · pp. 47–48
  • Section 5 uses N as a common upper bound on game-size parameters and switches between loss and utility conventions without changing equilibria or game size.The source game for the reduction is identified with the construction from Rubinstein [2016].Source: §E.2 · p. 48

E.3 The logarithmic-horizon undiscounted Markov game

  • The finite-horizon game FH(M) encodes an n × n bimatrix game M using alternating singleton and joint-action state layers with deterministic transitions.Odd layers record the players’ joint action in the next state, while even layers reset to the next odd-layer singleton.Source: §E.3 · p. 48
  • In FH(M), costs equal 1/H times the corresponding bimatrix loss at odd layers and are zero at even layers, while local mixed strategies are read from odd-layer policies.The construction is computable in polynomial time.Source: §E.3 · p. 48
  • If T < exp(cF ε⋆^2 H), any ε⋆/4-approximate T-sparse CCE against non-Markov deviations contains an ε⋆-approximate Nash equilibrium of M at some odd layer.The guarantee provides the key extraction property of the logarithmic-horizon construction.Source: §E.3 · p. 48

E.4 Embedding into a fixed-discount game · F Details for the Numerical Experiments (Section 6)

The section embeds a finite-horizon Markov game into a fixed-discount infinite-horizon game, linking discounted CCE to Nash equilibrium and preserving approximation guarantees. It also establishes polynomial encoding-size bounds for the source game and its discounted embedding.

E.4 Embedding into a fixed-discount game

  • The construction extends FH(M) with an absorbing state and rescaled costs, so the first H layers emulate the finite-horizon game while later costs vanish.The embedding is computable in polynomial time and uses the scaling parameter α := γ^(H−1).Source: §E.4 · p. 49
  • For every policy profile, discounted value equals α times the original H-step value, and an ε-approximate discounted CCE induces an (ε/α)-approximate CCE in the finite-horizon game.The equivalence holds because arbitrary post-H extensions have the same value after entering the zero-cost absorbing state.Source: §E.4 · pp. 49–50
  • The source game c M from Rubinstein [2016] has polynomial size in the number n of pure actions per player: n ≤ |c M| ≤ (n + 2)^qsrc.This follows from polynomially bounded payoff encoding lengths for the scaled polymatrix and Alth¨ofer-game components, with constant-size payoff normalization overhead.Source: §E.4 · p. 50
  • The discounted embedding retains n actions per player, adds only the absorbing state, and has transition probabilities in {0, 1}, while discounted loss entries have polynomial bit complexity.Because γ is fixed, the encoding length of γ^k grows at most linearly in k, and H is logarithmic in n.Source: §E.4 · p. 51
  • The size bound combines the source-game encoding, the O(Hn^2) state-space contribution, and discounted-loss precision to obtain |eFγ(c M)| ≤ (n + 2)^d0.Together with the action-set lower bound |eFγ(c M)| ≥ n, this yields the claimed polynomial relation.Source: §E.4 · p. 51
  • For fixed rational γ and even H ≤ B_H log(n + 2), the discounted embedding satisfies n ≤ |eFH,γ(c M)| ≤ (n + 2)^d0 for sufficiently large n.Here d0 := max{4, qsrc + 2}, and the bound accounts for state, action, transition, and discounted-loss encoding sizes.Source: §E.4 · p. 51

F.1 Implementation and evaluation protocol … F.3.1 Closed-form saddle-point solution

The evaluation uses four fixed finite-horizon games under full- and partial-feedback variants, alongside a discounted two-state zero-sum LQ Markov game. For the LQ game, the saddle point reduces to solving a scalar quadratic and selecting the feasible root.

F.1 Implementation and evaluation protocol

  • Both finite-horizon experiments use the same four games, differing only in the feedback available to players.The transition and cost tables define the experimental games.Source: §F.1 · p. 52, §F.2 · p. 52

F.2 Finite-Horizon Episodic Games

  • The finite-horizon experiments therefore cover four explicitly specified episodic Markov games with varied player counts, horizons, transitions, and cost structures.The suite includes battle-of-the-sexes, routing/congestion, public-goods, and transition-trap games.Source: §F.1 · p. 52, §F.2.1 · p. 52, §F.2.2 · p. 52

F.2.1 Markov battle-of-the-sexes chain

  • The finite-horizon suite comprises a horizon-2 Markov battle-of-the-sexes chain with two players, two actions, and layered states.The initial state transitions to two intermediate states before deterministic termination.Source: §F.2.1 · p. 52

F.2.2 Routing/congestion game

  • The routing/congestion game is a horizon-3, two-player model where route choices affect congestion, transitions, and stage costs.Action 0 is an upper/fast route, action 1 a lower/safe route, and matching actions create congestion.Source: §F.2.2 · pp. 52–53

F.2.3 Three-player public-goods game

  • The three-player public-goods game has binary contribution actions, horizon 2, and transitions determined by the number of contributors.The contributor count is k(a) = a1 + a2 + a3, with distinct transition probabilities for k(a) ≥2 versus k(a) < 2.Source: §F.2.3 · p. 53

F.2.4 Transition-trap game

  • The transition-trap game is a horizon-3, two-player model in which shortcut choices lower immediate cost but increase dangerous-state and trap probabilities.Trap-state costs distinguish shortcut action 0 from safe action 1.Source: §F.2.4 · p. 53

F.3 Discounted LQ Markov Game

  • The discounted benchmark is a two-player, two-state, zero-sum Markov game with bounded continuous actions, quadratic costs, affine transitions, and discount factor γ.Player 0 minimizes the raw cost, and the numerical experiment transforms the raw zero-sum costs.Source: §F.3 · pp. 53–54

F.3.1 Closed-form saddle-point solution

  • The closed-form solution reduces the Bellman-Isaacs saddle-point conditions to a scalar quadratic in ∆, solved numerically using the feasible root with actions in [−U, U].The values are then recovered as V0 and V1 = V0 + ∆.Source: §F.3.1 · p. 54

Related papers

Loading 2609.00504v1…