Research map / Reinforcement learning / Policy gradient and actor-critic

Solving Zero-Sum Markov Games with Continuous State via Spectral Dynamic Embedding

NeurIPS 2024 · Reinforcement learning › Policy gradient and actor-critic · approach: Variance-reduced policy gradients · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SDEPO, a natural policy gradient method for two-player zero-sum stochastic Markov games with continuous state and finite action spaces, using spectral dynamic embedding (random/Nyström features) for least-squares Q evaluation, with an O~(1/((1-γ)^3 ε)) last-iterate convergence guarantee and a neural practical variant SDEPO-NN.

Problem

Finding epsilon-optimal Nash equilibria in two-player zero-sum Markov games with continuous state spaces, where tabular methods do not apply and prior function-approximation methods have suboptimal sample complexity or ignore known dynamics.

Approach

Exploit a Gaussian transition model to decompose the transition kernel via Bochner/Mercer spectral embeddings, truncate them to finite random or Nyström features, and run least-squares policy evaluation plus KL-regularized natural policy gradient for both players.

Key results

• Theory: SDEPO achieves O~(1/((1-γ)^3 ε)) iteration complexity to an ε-optimal one-sided Nash equilibrium, independent of state-space cardinality.
• In the simple zero-sum Markov game, SDEPO with random and Nyström features converges within about 60 of 120 iterations and outperforms discretized OFTRL.
• In simple push with σ=0.1, SDEPO-NNnys wins 95.38% against NPG-NN (vs 5.16% reverse), showing the benefit of spectral embedding.

Measured effects reported in the paper

Limitations

• Requires known (Gaussian-noise) system dynamics f and knowledge of the opponent's strategy
• Assumes finite action space for the theory; continuous action case handled only by a heuristic neural variant without guarantees
• Convergence bound has polynomial dependence on constants such as Υ1, Υ2 and kernel bounds

Experimental setup

Datasets: randomly generated zero-sum Markov game simple push (adapted multi-agent environment)

Benchmarks: random zero-sum Markov game (1D continuous state, 5 actions) simple push (adapted)

Metrics: duality gap / convergence of policy winning rate

Baselines: OFTRL NPG-NN

Builds on: Ren et al. spectral dynamic embedding natural policy gradient OFTRL Perolat et al. error propagation framework SAC

Closest papers by meaning

• Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.90)
• A Natural Actor-Critic Framework for Zero-Sum Markov Games (ICML 2022 · similarity 0.90)
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence (NeurIPS 2022 · similarity 0.90)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.89)
• Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence (ICML 2022 · similarity 0.89)
• Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games (NeurIPS 2019 · similarity 0.89)