Research map / Learning theory and algorithms / Submodular and game algorithms
Approximate State Abstraction for Markov Games
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.
Extends approximate state abstraction from single-agent MDPs to two-player zero-sum Markov games and derives duality-gap bounds for minimax-Q and other similarity criteria, tested on Markov Soccer.
Problem
Computing equilibria in two-player zero-sum Markov games becomes hard as the state space grows, and state abstraction in multi-player settings may yield equilibria far from those of the ground game.
Approach
Extends approximate state abstraction (Abel et al.) to TZMGs by aggregating states whose minimax Q-values are within epsilon, and bounds the duality gap of the abstract-game Nash equilibrium when evaluated in the ground game (bound 12ε/(1-γ)^3), plus extensions to model, Boltzmann, and multinomial similarity criteria.
Key results
- Ground Markov Soccer has 760 states; the number of abstract states decreases almost linearly in epsilon, reaching 1 at epsilon=2.0.
- Duality gap of abstract-game policies (evaluated in ground game) approximates the ground gap only when epsilon is below about 0.6; larger epsilon gives significantly worse gaps due to deadlocks.
- Theorem bounds GAP(pi_GA*) <= 12ε/(1-γ)^3 for the minimax-Q abstraction.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase ε for Q*-based state abstraction | Markov Soccer · Markov Soccer | number of abstract states: 760 at ε=0.0 -> 1 at ε=2.0 | Helped |
| Use Q*-based state abstraction with ε less than 0.6 | Minimax Q-learning in Markov Soccer · Markov Soccer | duality gap | No clear effect |
| Use Q*-based state abstraction with larger ε | Minimax Q-learning in Markov Soccer · Markov Soccer | duality gap | Hurt |
Surprising findings
- Abstract-game policies with larger epsilon often repeat actions without progress, creating deadlocks that inflate the duality gap.
Limitations
- Experiments only on a small 1 vs 1 Markov Soccer grid game
- Abstraction discovery algorithms are left open; the abstraction relies on first solving the ground game
- Duality gap is approximated via Q-learning rather than computed exactly
Experimental setup
Datasets: Markov Soccer (self-constructed 4x5 grid game)
Benchmarks: Markov Soccer
Metrics: duality gap number of abstract states
Baselines: ground game minimax Q-learning
Builds on: Abel et al. approximate state abstraction for MDPs minimax Q-learning Markov soccer
Closest papers by meaning
- Towards General Function Approximation in Zero-Sum Markov Games (ICLR 2022 · similarity 0.89)
- Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games (ICML 2024 · similarity 0.89)
- Policy Optimization for Markov Games: Unified Framework and Faster Convergence (NeurIPS 2022 · similarity 0.89)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.88)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.88)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.87)
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.