首个针对去中心化多智能体随机最短路径问题的后悔下界研究
Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems
- 基于对称性分析，揭示去中心化策略的最优结构
- 证明了任意智能体数量下后悔率至少为Ω(√K)，在K轮中难以优化
- 为多智能体协同学习算法设计提供理论指导
多智能体系统（MAS）在群体机器人和交通调度等场景中至关重要，要求智能体以去中心化方式协作达成共同目标。随机最短路径（SSP）为建模此类去中心化控制提供了自然框架。尽管单智能体情形下的学习问题已被广泛研究，但去中心化多智能体版本仍基本未被探索。本文研究在线性函数近似下的去中心化多智能体随机最短路径问题（Dec-MASSPs），其中转移动态和代价由线性模型表示。通过新颖的对称性论证，我们揭示了最优策略的结构。主要贡献是首次在任意智能体数量n下构造出难以学习的实例，并建立了关于总轮数K的后悔下界Ω(√K)。该结果凸显了去中心化多智能体学习的固有难度，有助于理解其学习复杂性，并指导高效学习算法的设计。
原文摘要 · Abstract (English)
Multi-agent systems (MAS) are central to applications such as swarm robotics and traffic routing, where agents must coordinate in a decentralized manner to achieve a common objective. Stochastic Shortest Path (SSP) problems provide a natural framework for modeling decentralized control in such settings. While the problem of learning in SSP has been extensively studied in single-agent settings, the decentralized multi-agent variant remains largely unexplored. In this work, we take a step towards addressing that gap. We study decentralized multi-agent SSPs (Dec-MASSPs) under linear function approximation, where the transition dynamics and costs are represented using linear models. Applying novel symmetry-based arguments, we identify the structure of optimal policies. Our main contribution is the first regret lower bound for this setting based on the construction of hard-to-learn instances for any number of agents, $n$. Our regret lower bound of $Ω(\sqrt{K})$, over $K$ episodes, highlights the inherent learning difficulty in Dec-MASSPs. These insights clarify the learning complexity of decentralized control and can further guide the design of efficient learning algorithms in multi-agent systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。