无需通信的多智能体学习，高效逼近纳什均衡
Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics
- 基于有限历史窗口的独立策略，避免集中信息共享
- 在部分可观测环境下实现近似纳什均衡收敛
- 适合大规模多智能体系统，计算复杂度接近多项式
我们研究部分可观测马尔可夫博弈（POMG）中的纳什均衡学习，即智能体无法完全观测环境状态。以往方法依赖中心化或信息共享，样本与计算复杂度随智能体数量呈指数增长。本文聚焦具有独立状态转移的子类，假设底层可观测马尔可夫博弈为马尔可夫势博弈。提出一种独立学习算法：各智能体仅依赖自身动作与观测，不进行通信，仍能共同收敛至近似纳什均衡。由于部分可观测性，最优策略通常依赖完整的历史记录。在滤波稳定性假设下，我们证明使用有限历史窗口的策略即可提供充分近似保证，从而将原POMG近似为近势博弈，实现对底层POMG的独立纳什均衡学习，其样本与计算复杂度为拟多项式级。
原文摘要 · Abstract (English)
We study Nash equilibrium learning in partially observable Markov games (POMGs), a multi-agent reinforcement learning framework in which agents cannot fully observe the underlying state. Prior work in this setting relies on centralization or information sharing, and suffers from sample and computational complexity that scales exponentially in the number of players. We focus on a subclass of POMGs with independent state transitions, where agents remain coupled through their rewards, and assume that the underlying fully observed Markov game is a Markov potential game. For this class, we present an independent learning algorithm in which players, observing only their own actions and observations and without communication, jointly converge to an approximate Nash equilibrium. Due to partial observability, optimal policies may in general depend on the full action-observation history. Under a filter stability assumption, we show that policies based on finite history windows provide sufficient approximation guarantees. This enables us to approximate the POMG by a surrogate Markov game that is near-potential, leading to quasi-polynomial sample and computational complexity for independent Nash equilibrium learning in the underlying POMG.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。