标题： 去中心化多智能体随机最短路径问题的遗憾下界 显示英文标题

标题： Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems

摘要： 多智能体系统（MAS）在诸如群体机器人和交通路由等应用中至关重要，其中智能体必须以去中心化的方式协调以实现共同目标。 随机最短路径（SSP）问题为在这些环境中建模去中心化控制提供了自然的框架。 虽然在单智能体设置中学习问题已被广泛研究，但去中心化的多智能体变体仍基本未被探索。 在本工作中，我们朝着解决这一差距迈出了一步。 我们在线性函数近似下研究去中心化的多智能体 SSP（Dec-MASSPs），其中转移动态和成本使用线性模型表示。 应用新颖的基于对称性的论证，我们确定了最优策略的结构。 我们的主要贡献是基于为任意数量的智能体构造难以学习的实例，这是该设置下的第一个遗憾下界，$n$。 我们的遗憾下界为 $\Omega(\sqrt{K})$，在 $K$个回合中，突显了 Dec-MASSPs 中固有的学习难度。 这些见解明确了去中心化控制的学习复杂性，并可进一步指导多智能体系统中高效学习算法的设计。 显示英文摘要

摘要： 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 $\Omega(\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.