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

The paper asks whether approximate equilibrium computation is feasible under radically uncoupled learning in discounted general-sum Markov games. It develops layered OOMD for independent self-play with full and partial feedback, while proving quasi-polynomial upper bounds and conditional polynomial-time hardness. The results identify a sub-exponential algorithmic guarantee alongside a PPAD-based barrier to polynomial-time computation.

  • Problem

    The paper studies whether radically uncoupled learning can compute approximate CCEs efficiently in discounted general-sum Markov games despite decentralized information and deviation-induced dynamic state distributions.

  • Method

    The paper introduces a layered optimistic mirror-descent algorithm with smoothed entropy and increasing layer-wise step sizes, with full-feedback and partial-feedback implementations.

  • Results

    Under “ETH for PPAD,” no polynomial-time algorithm computes sparse inverse-polynomially accurate CCEs for every fixed rational discount factor, while the proposed method achieves quasi-polynomial guarantees and sub-exponential convergence.

  • Takeaways & Limitations

    Radically uncoupled online self-play is provably convergent without structural game assumptions, but its discounted CCE computation has a gap between quasi-polynomial algorithms and conditional hardness bounds.

  • Takeaways & Limitations

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

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 radically uncoupled learning for approximate CCE computation in discounted general-sum Markov games, where decentralization and dynamic strategic interactions complicate no-regret analysis. It develops layered OOMD guarantees and establishes complementary computational upper and lower bounds.

  • Motivation: Markov games combine equilibrium computation with intertemporal dynamics because actions affect both immediate costs and future state distributions.Players’ values depend on opponents’ policies, while unilateral deviations can change later strategic interactions.
  • Problem setting: Radically uncoupled learning forbids players from observing one another’s policies, losses, value functions, or random bits.The setting requires each player to compute and estimate updates using only locally available information.
  • Technical challenge: Independent learning in general-sum Markov games is less understood because deviation-induced state distributions are time-varying, unknown, and jointly determined by policies and transitions.This obstructs direct transfer of normal-form no-regret arguments.
  • Related work: Existing decentralized CCE methods rely on coordination, post-processing, or shared-history sampling and do not provide the radically uncoupled online-regret objective.These methods can compute equilibrium policies but require mechanisms absent from independent online learning.
  • Contributions: The paper introduces a layered smoothed-entropy OOMD algorithm with increasing step sizes and transfers finite-horizon guarantees to discounted games.The discounted results yield quasi-polynomial-time and quasi-polynomial-sample guarantees for sparse discounted CCEs under full and partial feedback.
  • Computational complexity: Under “ETH for PPAD,” no polynomial-time algorithm computes sparse inverse-polynomially accurate CCEs for every fixed rational discount factor.This lower bound applies to finite- and infinite-horizon discounted general-sum Markov games.

2 Preliminaries and Notations

The preliminaries define finite- and infinite-horizon Markov games, policy classes, repeated interaction, feedback models, discounted values, regret, and CCEs. They distinguish history-dependent policies from nonstationary Markov policies and formalize empirical distributions over generated profiles.

  • Game model: A Markov game specifies states, finite player action sets, transition kernels depending on joint actions, and player-specific costs in [0,1].Finite-horizon games use layer-indexed state spaces and kernels; infinite-horizon games use a stationary state space and transition kernel.
  • Policies: A non-Markov policy maps complete histories to action distributions, whereas a Markov policy maps the current state and layer to an action distribution.In the infinite-horizon setting, the paper’s Markov policies are nonstationary across time.
  • Interaction and feedback: Players repeatedly select product Markov policies, interact with the environment for T episodes, and observe feedback determined by the information model.Full feedback reveals exact Q-vectors, while partial feedback reveals only each player’s own trajectory information.
  • Distributional policies: A distributional policy samples a policy profile first and then executes the sampled profile; the empirical distribution averages point masses over the iterates.This empirical distribution is the object used to define equilibrium and connect regret to CCE.
  • Discounted equilibrium notions: The framework defines discounted costs, general-policy regret, and approximate CCE over distributions of policy profiles for finite or infinite horizons.Discounted values use the discount factor γ and may be truncated at a finite horizon.

3 Main Algorithm and Results for Episodic Markov Games

The episodic analysis addresses unknown, time-varying history-occupancy weights with layered OOMD, then extends the guarantees to partial feedback through exploration and value estimation. The resulting empirical policy distribution achieves approximate CCE guarantees, with partial feedback adding polynomial overhead.

  • Challenge: Markov-game regret is weighted by deviation-induced history distributions, which can shift as policies change.The learner must control unknown occupancy-weight drift alongside online-learning dynamics.
  • Full-feedback algorithm: Layered OOMD independently updates each player’s local policy using state-action values from the previous product Markov profile.The method uses a smoothed-entropy regularizer and an increasing layer-wise step-size schedule.
  • Step-size design: Earlier layers use smaller learning rates while later layers use larger rates to limit downstream occupancy drift and permit faster adaptation.The schedule is designed specifically to manage hidden history-occupancy drift, unlike learning-rate schedules aimed at exploration.
  • Full-feedback guarantee: After T episodes, the empirical distribution generated by Algorithm 1 is an ε-approximate CCE against history-dependent deviations.The proof decomposes regret into local weighted terms, controls weight and Q-function movement, and equalizes resulting orders through the layer-wise schedule.
  • Partial-feedback guarantee: Partial feedback preserves the full-feedback guarantee’s exponential dependence on horizon length while adding polynomial overhead for exploration and value estimation.Reachability and an exploration floor ensure state-action pairs are sampled sufficiently often for Q-function estimation.
  • Error decomposition: The partial-feedback regret bound separates OOMD error, Q-function estimation error, comparator smoothing cost, and estimated-Q variation.Parameter choices make the four terms at most ε/4 each before applying the high-probability estimation guarantee.

4 Approximating Equilibrium Discounted Markov Games

The section transfers finite-horizon regret guarantees to discounted Markov games by truncating the horizon and controlling the discounted tail. This yields sub-exponential, quasi-polynomial guarantees for sparse discounted CCEs under full and partial feedback.

  • Transfer principle: Discounted guarantees extend finite-horizon regret bounds to both finite- and infinite-horizon Markov games.The transfer requires a finite-horizon guarantee on a truncated discounted game and applies independently of the feedback model.
  • Transfer principle: Truncation runs the finite-horizon algorithm on the first L discounted layers and bounds the remaining layers as a tail error.Geometric decay of future layers makes the finite approximation sufficient for controlling the original discounted objective.
  • Transfer principle: Theorem 3 shows that averaging the extended learned policies gives an (εalg + τL,H(γ))-approximate discounted CCE.The result applies to product Markov profiles generated on the truncated game and deviations over the target horizon.
  • Complexity guarantees: For every fixed γ < 1, Hγ,ε = O(log(1/ε)), making the discounted-game bounds quasi-polynomial in 1/ε rather than exponential in the original horizon.The effective discounted horizon replaces the original horizon in the finite-horizon regret exponents.

5 Computational Lower Bound for Discounted Markov Games

The section establishes computational lower bounds for sparse discounted CCE computation by reducing hard bimatrix-game equilibrium problems to discounted Markov games. Under ETH for PPAD, polynomial-time algorithms are ruled out for fixed discount factors and polynomial support bounds.

  • Lower-bound formulation: The lower-bound search problem asks for a finite sequence of product Markov profiles whose uniform empirical distribution is an approximate discounted CCE.This formulation relaxes radically uncoupled online learning because centralized algorithms with full game access are also permitted.
  • Reduction: A polynomial-time construction maps any bimatrix game to a finite-horizon Markov game such that computing its CCE yields a Nash equilibrium of the original game.The reduction is polynomial-time and is stated for a two-player Markov game with a designated horizon.
  • Reduction: A finite-horizon Markov game can be extended to an infinite-horizon discounted game so that an approximate discounted CCE induces an approximate CCE for the original finite-horizon game.The extension is obtained by forcing absorption after the designated horizon and is computable in polynomial time.
  • Complexity assumption: Under ETH for PPAD, every algorithm for ε⋆-approximate Nash equilibrium in two-player n × n bimatrix games requires time n^(log^(1-o(1)) n).This hardness consequence supplies the source problem for the Markov-game reduction.
  • Hardness result: For every fixed rational γ ∈ (0, 1) and support exponent C > 0, Theorem 5 gives an inverse-polynomial accuracy level for which polynomial-time sparse discounted CCE computation is impossible.The theorem applies to constructed finite- and infinite-horizon discounted general-sum Markov games under ETH for PPAD.
  • Hardness result: The finite-horizon corollary likewise rules out polynomial-time algorithms outputting at most N^Cfh product Markov profiles with discounted CCE gap at most N^-Kfh.The guarantee is against all history-dependent deviations.

6 Numerical Results

The experiments evaluate independent learning under full and partial feedback on four finite-horizon games, plus a discounted linear-quadratic benchmark. The CCE gap decreases in all four games under both feedback models, while the benchmark’s value error decreases rapidly.

  • Finite-horizon episodic Markov games: Four finite-horizon games are evaluated under both full-feedback and independently sampled partial feedback.The games are a battle-of-the-sexes chain, routing/congestion, public goods, and transition trap.
  • Finite-horizon episodic Markov games: Full-feedback uses T = 1000, while partial feedback uses K = 1000 blocks of B = 500 episodes.The partial-feedback evaluation therefore covers 25,000 episodes, with gaps evaluated every 50 evaluation units.
  • Finite-horizon episodic Markov games: The CCE gap decreases in all four games under both feedback models.Figure 1 reports deterministic full-feedback behavior and the mean across 20 partial-feedback runs with one empirical standard deviation shaded.
  • Discounted linear-quadratic benchmark: The discounted benchmark is a two-player, two-state zero-sum linear-quadratic game with a closed-form infinite-horizon saddle-point solution.The action interval is discretized while retaining the closed-form saddle-point actions in the grid.
  • Discounted linear-quadratic benchmark: The value error relative to the closed-form solution decreases rapidly in the discounted linear-quadratic benchmark.The simulation uses T = 1000, H = 20, and γ = 0.90.

7 Conclusion

The paper concludes that discounted general-sum Markov-game CCE computation is polynomial-time hard under ETH for PPAD, while layered OOMD gives quasi-polynomial-time radically uncoupled online self-play without structural game assumptions. It also identifies a gap between the upper and lower bounds and several directions for narrowing it.

  • Conclusion: Under ETH for PPAD, no polynomial-time algorithm computes CCEs in discounted general-sum Markov games.This is the paper’s computational hardness result.
  • Conclusion: Layered OOMD provides a quasi-polynomial-time radically uncoupled online self-play algorithm without structural assumptions on the game.The paper describes it as the first provably convergent algorithm in this setting with a sub-exponential convergence guarantee.
  • Conclusion: The layered OOMD algorithm extends to partial feedback while retaining similar convergence guarantees.This complements the full-feedback result under the same radically uncoupled information structure.
  • Open problems: A gap remains between the paper’s quasi-polynomial upper bounds and its computational lower bounds.The precise complexity of computing sparse CCEs in discounted Markov games remains open.
  • Open problems: Future work includes restricting players to Markov policies and characterizing information models weaker than shared randomness.The paper specifically asks whether these settings permit polynomial-time radically uncoupled online learning.

B.7 Proof of Theorem 1

The proof establishes full-feedback regret guarantees by applying smoothed-entropy optimistic mirror descent across histories and layers, then converting the resulting regret bound into an approximate CCE guarantee. The analysis also controls policy variation, smoothing error, and history-dependent comparators.

  • Regret analysis: The proof applies the OOMD regret bound separately to every history and layer, then sums the resulting guarantees.The smoothed entropy regularizer supplies bounded Bregman diameter and strong convexity.
  • Regret analysis: Choosing λi = 1/|Ai| gives ρi = 2 and Bi = 2 log(|Ai| + 1).These parameter values are substituted into the regret analysis.
  • CCE conversion: The proof converts the bounded regret guarantee into an ε-CCE guarantee using the standard no-regret-to-CCE equivalence.The empirical distribution of product policies is the object receiving the equilibrium guarantee.
  • Comparator smoothing: History-dependent comparator policies are replaced by smoothed versions, with the resulting approximation error accounted for in the regret bound.The smoothing comparison enables guarantees against general history-dependent policies.

C.4 Proof of Theorem 2

The partial-feedback proof establishes a high-probability block-level regret guarantee from uniformly accurate Q-function estimates and transfers it to the repeated trajectory sequence. Because each block policy is repeated equally often, the resulting empirical distribution is an ε-approximate CCE.

  • High-probability guarantee: With probability at least 1 − δ, the partial-feedback guarantee holds simultaneously for every player.The result is obtained after selecting the block, episode, smoothing, and estimation parameters for ε and δ.
  • Block estimation: During each block, the policy is fixed and the B trajectories are conditionally independent, enabling Q-function estimation under reachability and action-probability floors.These conditions provide uniform lower bounds on observing state–action pairs.
  • Trajectory transfer: The block-level guarantee transfers to Nε = KεBε actual episodes because each block policy is played exactly Bε times.The empirical distributions over block policies and trajectory episodes are therefore identical.
  • CCE conclusion: The empirical distribution over the repeated block policies is an ε-approximate CCE.This follows from the transferred regret bound and equal repetition of each block policy.

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

The proofs transfer finite-horizon regret guarantees to discounted games by truncating the discounted horizon and controlling the geometrically decaying tail. This yields discounted CCE guarantees from empirical distributions of joint policies.

  • Truncation: Discounting permits truncation because future layers contribute a geometrically decaying tail.The finite-horizon and infinite-horizon discounted models are handled under a fixed γ ∈(0, 1).
  • Truncation: The truncation σ[L] preserves the first L decision rules and therefore the trajectory distribution through layer L.This lets the proof compare the original and truncated policy profiles on their common initial layers.
  • Policy extension: Extending an L-step product Markov profile preserves the relevant first-L behavior, while nonnegative costs make ignoring later layers a lower bound.The argument connects finite-horizon deviations with their extended discounted counterparts.
  • Regret transfer: The finite-horizon regret guarantee bounds the truncated-game regret uniformly over deviations, enabling the discounted comparison.The bound is stated simultaneously for all players and uniformly over μ_i.
  • CCE conclusion: The discounted CCE conclusion follows by applying the standard no-regret-to-CCE equivalence to the empirical distribution of joint policies.The same conclusion is obtained for the empirical distribution over extended block policies.

D.2 Proof of the partial-feedback case

The partial-feedback proof applies the finite-horizon guarantee to a discounted truncated game, under a reachability condition, and then controls truncation and episode complexity.

  • Partial-feedback guarantee: Theorem 2 is applied to the truncated game G[Lε] under the (κ, ζ̄ε,L)-reachability condition.The truncated game's costs remain in [0, 1], satisfying the theorem's cost-range requirement.
  • Partial-feedback guarantee: With probability at least 1 −δ, the partial-feedback regret bound holds simultaneously for every player.The result is transferred to the discounted setting through the extended block policies.
  • CCE conclusion: The discounted CCE statement follows from the standard no-regret-to-CCE equivalence applied to the empirical distribution over extended block policies.This connects the partial-feedback regret guarantee to discounted CCE.
  • Truncation depth: The truncation depth satisfies Lε = O(L̄H,ε), where L̄H,ε := min{H̄, log(1/ε)}.For infinite horizons, the convention is L∞,ε = log(1/ε).

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

The proof verifies that Algorithms 1 and 2 generate admissible Markov policies and solve the sparse discounted-CCE problem through the established regret and CCE guarantees.

  • Algorithm 1: Algorithm 1 produces policies in Πmarkov,Lε and uses a fixed product Markov continuation through ExtLε.Thus each extended policy belongs to the required policy class.
  • Correctness: Algorithm 1 satisfies both requirements of Definition 8 and solves (Tε, ε)-DiscSparseMarkovCCEgen.The proof combines policy-class validity with the discounted CCE requirement.
  • Algorithm 2: Algorithm 2 repeats each block policy throughout its block, so every episode-level policy remains in Πmarkov,H̄.Corollary 2 then supplies the corresponding discounted CCE guarantee.
  • Reduction: The reduction constructs a finite-horizon Markov game from a bimatrix game using alternating singleton and action-pair state layers.Odd layers encode local mixed strategies and costs, while transitions are deterministic.
  • Reduction: An ε⋆/4-approximate T-sparse CCE with T < exp(cF ε⋆^2H) yields an ε⋆-approximate Nash equilibrium of the source bimatrix game.The extracted equilibrium appears at some odd layer h ∈OH.

E.4 Embedding into a fixed-discount game

The embedding converts a finite-horizon game into a fixed-discount game by adding an absorbing state and rescaling costs. It preserves equilibrium structure while keeping the encoding size polynomially related to the source game.

  • Construction: The embedding adds an absorbing state ⊥ after horizon H, where all future costs are zero.The first H layers exactly emulate the original finite-horizon game.
  • Value preservation: Choosing α := γ^(H−1) and rescaling costs makes discounted values equal α times the original H-horizon values.The construction is polynomial-time because it adds one state and rescales finite entries.
  • Equilibrium preservation: An ε-approximate discounted CCE maps to an (ε/α)-approximate CCE of the original finite-horizon game.This holds for sparse lists of infinite-horizon Markov policies after truncating them to H layers.
  • Deviation preservation: Every H-step deviation can be extended beyond the absorbing layer without changing discounted value, so deviation suprema coincide.Post-H costs are zero, which supports the equivalence between infinite-horizon and H-step deviations.
  • Encoding size: The source game itself has size polynomially related to its n actions: n ≤|cM| ≤(n + 2)^qsrc.The payoff normalization changes bit complexity by only an absolute additive amount.
  • Encoding size: For fixed rational γ and H ≤ BH log(n + 2), the embedded game satisfies n ≤|eFH,γ(cM)| ≤(n + 2)^d0.Here d0 := max{4, qsrc + 2}.

F.1 Implementation and evaluation protocol

The evaluation uses four finite-horizon games under identical game specifications, varying only the feedback available to players, alongside a discounted two-player zero-sum Markov-game benchmark. The benchmark is analyzed through Bellman-Isaacs equations and a numerically selected feasible saddle-point solution.

  • Finite-horizon experiments: Both finite-horizon experiments use the same four games and differ only in the feedback available to players.
  • Finite-horizon game suite: The finite-horizon suite includes two-player binary-action games with horizons two or three, layered state spaces, congestion, routing, contribution, and shortcut-versus-safety trade-offs.The routing games model congestion or increased danger from shortcut choices, while the contribution game uses the number of contributors to determine transitions.
  • Finite-horizon game suite: Transitions and costs are specified layer by layer, including action-dependent probabilities, congestion penalties, state-dependent base costs, and terminal-state costs.The finite-horizon games use explicit transition probabilities and cost formulas for each state layer and action profile.
  • Discounted benchmark: The discounted benchmark is a two-player, two-state, zero-sum Markov game with bounded continuous actions, quadratic raw costs, affine transition probabilities, and discount factor γ.Player 0 minimizes the raw cost, while player 1 chooses the opposing action within [−U, U].
  • Discounted benchmark: The benchmark computes values by reducing the Bellman-Isaacs saddle-point conditions to a scalar quadratic in ∆, solving it numerically, and retaining the feasible root whose actions lie in [−U, U].The value difference is defined as ∆ = V1 − V0, and feasibility is checked against the action bounds before recovering V0.
Loading 2609.00504v1…