# Approximate State Abstraction for Markov Games

arXiv: https://arxiv.org/abs/2412.15877 · HTML: https://mlsanity.com/paper/2412.15877/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 30 references that are in the map.
- First posted on arXiv 20 Dec 2024.

## Builds on (most cited first, 6 of 6)

- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Plannable Approximations to MDP Homomorphisms: Equivariance under Actions](https://mlsanity.com/paper/2002.11963/) (2020)
- [Solving Imperfect Information Games Using Decomposition](https://mlsanity.com/paper/1303.4441/) (2013)
- [Competitive Multi-agent Inverse Reinforcement Learning with Sub-optimal Demonstrations](https://mlsanity.com/paper/1801.02124/) (2018)

## Abstract (arXiv)

This paper introduces state abstraction for two-player zero-sum Markov games (TZMGs), where the payoffs for the two players are determined by the state representing the environment and their respective actions, with state transitions following Markov decision processes. For example, in games like soccer, the value of actions changes according to the state of play, and thus such games should be described as Markov games. In TZMGs, as the number of states increases, computing equilibria becomes more difficult. Therefore, we consider state abstraction, which reduces the number of states by treating multiple different states as a single state. There is a substantial body of research on finding optimal policies for Markov decision processes using state abstraction. However, in the multi-player setting, the game with state abstraction may yield different equilibrium solutions from those of the ground game. To evaluate the equilibrium solutions of the game with state abstraction, we derived bounds on the duality gap, which represents the distance from the equilibrium solutions of the ground game. Finally, we demonstrate our state abstraction with Markov Soccer, compute equilibrium policies, and examine the results.