mlsanityData to 14 Oct 2026

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

arXiv 2511.04594 ↗First posted 6 Nov 2025cs.LG cs.MAcited by 0

Not on the map. Why?

Abstract (arXiv)

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(√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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 13 of its 28 references that are in the map. First posted on arXiv 6 Nov 2025.

Builds on

13 of 28 references.

References · 13

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  3. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
  4. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  5. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 40
  6. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  7. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  8. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  9. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  10. 2022A Critical Review of Communications in Multi-Robot Systemscited by 16
  11. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  12. 2021Multi-agent Natural Actor-critic Reinforcement Learning Algorithmscited by 2
1 more
  1. 2023Multi-Agent Congestion Cost Minimization With Linear Function Approximationscited by 1

Built on by

Not cited yet.