arXiv:2509.23157cs.GTcs.LG2025-09

证明了多智能体博弈中策略可收敛至均衡,为算法设计提供理论支撑。

Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective

  • 从拓扑视角分析策略更新路径,提出收敛条件
  • 所有有限状态马尔可夫博弈均有有限长度收敛路径
  • 适合研究多智能体强化学习理论的学者参考

在博弈论与多智能体强化学习(MARL)中,各智能体选择策略、与环境及其他智能体交互,并根据获得的收益更新自身策略。这一过程生成一个联合策略序列 $(s^t)_{t \≥ 0}$,其中 $s^t$ 表示时间步 $t$ 时所有智能体的策略组合。广泛采用的‘赢留输变’原则规定:若当前策略为最优回应,则保持不变。该原则在联合策略达到均衡时表现出固定点性质。在此原则下生成的策略序列称为满足路径(satisficing path),最早由[40]引入,并在[39]中拓展至 $N$-人博弈场景。一个基本问题是:在何种条件下,任意初始联合策略 $s$ 都存在一条有限长度的满足路径 $(s^t)_{0 \≤ t \≤ T}$,使得 $s^0=s$ 且 $s^T$ 为均衡?本文建立了该性质的充分条件,证明了任意有限状态马尔可夫博弈及任意 $N$-人博弈均保证从任一初始策略出发,存在有限长度的满足路径收敛至某个均衡。这些结果为 MARL 算法的设计提供了更强的理论基础。

原文摘要 · Abstract (English)

In game theory and multi-agent reinforcement learning (MARL), each agent selects a strategy, interacts with the environment and other agents, and subsequently updates its strategy based on the received payoff. This process generates a sequence of joint strategies $(s^t)_{t \geq 0}$, where $s^t$ represents the strategy profile of all agents at time step $t$. A widely adopted principle in MARL algorithms is "win-stay, lose-shift", which dictates that an agent retains its current strategy if it achieves the best response. This principle exhibits a fixed-point property when the joint strategy has become an equilibrium. The sequence of joint strategies under this principle is referred to as a satisficing path, a concept first introduced in [40] and explored in the context of $N$-player games in [39]. A fundamental question arises regarding this principle: Under what conditions does every initial joint strategy $s$ admit a finite-length satisficing path $(s^t)_{0 \leq t \leq T}$ where $s^0=s$ and $s^T$ is an equilibrium? This paper establishes a sufficient condition for such a property, and demonstrates that any finite-state Markov game, as well as any $N$-player game, guarantees the existence of a finite-length satisficing path from an arbitrary initial strategy to some equilibrium. These results provide a stronger theoretical foundation for the design of MARL algorithms.

多智能体博弈论收敛性强化学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。