{"ID":2845449,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.04594","arxiv_id":"2511.04594","title":"Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems","abstract":"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.","short_abstract":"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 probl...","url_abs":"https://arxiv.org/abs/2511.04594","url_pdf":"https://arxiv.org/pdf/2511.04594v2","authors":"[\"Utkarsh U. Chavan\",\"Prashant Trivedi\",\"Nandyala Hemachandra\"]","published":"2025-11-06T17:49:33Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.MA\"]","methods":"[]","has_code":false}