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.

本文解决了两人零和马尔可夫博弈（TZMGs）中由于状态数量增加导致均衡计算困难的问题。通过将多个不同状态视为一个状态的方式进行状态抽象，提出了一种新颖的方法，并通过推导对偶间隙界限来评估状态抽象游戏的均衡解。实验结果显示，该方法在马尔可夫足球游戏中有效计算了均衡策略，具有重要的应用潜力。

马尔可夫博弈的近似状态抽象