Research map / Multi-agent systems and games / Games and equilibria
Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics
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 a communication-free independent learning algorithm for partially observable Markov potential games with decoupled dynamics, approximating the POMG by a finite-window superstate Markov game to reach approximate Nash equilibria with quasi-polynomial complexity.
Problem
Learning approximate Nash equilibria in partially observable Markov games (POMGs) is hard: prior methods rely on centralization or information sharing and scale exponentially in the number of players.
Approach
Exploit decoupled state transitions and observations with a stagewise potential reward structure, under filter stability, to approximate the POMG by a finite-window superstate Markov game that is near-potential, then run independent soft policy iteration on it.
Key results
- Approximate NE of the superstate Markov game induces a (epsilon + 2 eps_rho^m)-approximate NE of the POMG (Proposition on NE approximation).
- Algorithm reaches an epsilon-approximate NE of the POMG with sample and computational complexity quasi-polynomial in (kappa N H A O / (beta eps)), with window m logarithmic in 1/eps.
- Simulations in a dynamic transmission game and a cooperative gridworld show convergence and improving equilibrium approximation as window length m grows.
Limitations
- Superstate concentrability coefficient kappa is assumed bounded but not quantified and can grow exponentially in window length m in the worst case.
- Requires filter stability and decoupled transition/observation dynamics with stagewise potential rewards, a restricted subclass of POMGs.
- Assumes uniform lower bound on observation probabilities (beta).
Experimental setup
Benchmarks: dynamic transmission game cooperative gridworld
Metrics: approximate Nash equilibrium gap convergence
Builds on: Markov potential games independent learning POMDP finite-window approximation under filter stability Dec-POMDP information sharing
Closest papers by meaning
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.89)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.89)
- Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning (ICLR 2024 · similarity 0.88)
- Learning Nash Equilibrium of Markov Potential Games with a Shared Constraint via Primal-Dual Optimization (AAAI 2025 · similarity 0.88)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.88)
- Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.