为零和马尔可夫博弈设计状态抽象，降低计算复杂度并保证解的近似精度。
Approximate State Abstraction for Markov Games
- 通过合并相似状态简化博弈模型，降低求解难度。
- 推导出对偶间隙上界，量化抽象后解与原解的距离。
- 在马尔可夫足球场景验证，可高效求得近似均衡策略。
本文针对双人零和马尔可夫博弈（TZMGs）引入状态抽象方法，其中玩家收益由环境状态及各自动作决定，状态转移遵循马尔可夫过程。例如足球等游戏中，动作价值随比赛状态动态变化，需用马尔可夫博弈建模。当状态数增加时，求解均衡变得困难。为此，本文采用状态抽象技术，将多个不同状态合并为单一状态以减少状态数量。已有研究多关注马尔可夫决策过程中的最优策略，但在多人博弈中，抽象后的博弈可能产生与原始博弈不同的均衡解。为此，本文推导了对偶间隙的上界，用于衡量抽象博弈均衡解与原博弈均衡解之间的距离。最后，通过在马尔可夫足球（Markov Soccer）数据集上的实验，计算均衡策略并分析结果，验证了该方法的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。