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

• URL: http://arxiv.org/abs/2511.04594v1
• Date: Thu, 06 Nov 2025 17:49:33 GMT
• Title: Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems
• Authors: Utkarsh U. Chavan, Prashant Trivedi, Nandyala Hemachandra,
• Abstract summary: Shortest Path (SSP) problems provide a natural framework for modeling decentralized control in such settings.<n>We study decentralized multi-agent SSPs (Dec-MASSPs) under linear function approximation.<n>Applying novel symmetry-based arguments, we identify the structure of optimal policies.
• Score: 1.1575091540914677
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\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.

Related papers

• Structured Cooperative Multi-Agent Reinforcement Learning: a Bayesian Network Perspective [1.2515675707300356]
  We propose a systematic approach to leverage structures in the inter-agent couplings for efficient model-free reinforcement learning.<n>We derive a multi-agent policy gradient theorem based on the P-DTDE scheme and develop a scalable actor-critic algorithm.
  arXiv  Detail & Related papers  (2025-10-11T00:29:55Z)
• Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach [0.0]
  This paper presents a novel and more scalable alternative, namely the sequential-move centralized training for decentralized execution.<n>It further pushes the applicability of the Bellman's principle of optimality, raising three new properties.<n> Experiments on two- and many-agent domains confirm the superiority of our novel approach.
  arXiv  Detail & Related papers  (2024-08-23T15:01:37Z)
• MADiff: Offline Multi-agent Learning with Diffusion Models [79.18130544233794]
  MADiff is a diffusion-based multi-agent learning framework.<n>It works as both a decentralized policy and a centralized controller.<n>Our experiments demonstrate that MADiff outperforms baseline algorithms across various multi-agent learning tasks.
  arXiv  Detail & Related papers  (2023-05-27T02:14:09Z)
• Decentralized Cooperative Multi-Agent Reinforcement Learning with Exploration [35.75029940279768]
  We study multi-agent reinforcement learning in the most basic cooperative setting -- Markov teams. We propose an algorithm in which each agent independently runs a stage-based V-learning style algorithm. We show that the agents can learn an $epsilon$-approximate Nash equilibrium policy in at most $proptowidetildeO (1/epsilon4)$ episodes.
  arXiv  Detail & Related papers  (2021-10-12T02:45:12Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  Reinforcement learning (RL) has been widely investigated and shown to be a promising solution for decision-making and optimal control processes. We propose an adaptive ADMM (asI-ADMM) algorithm and apply it to decentralized RL with edge-computing-empowered IIoT networks. Experiment results show that our proposed algorithms outperform the state of the art in terms of communication costs and scalability, and can well adapt to complex IoT environments.
  arXiv  Detail & Related papers  (2021-06-30T16:49:07Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles. Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center. We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes. A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
  arXiv  Detail & Related papers  (2020-10-02T10:41:59Z)
• F2A2: Flexible Fully-decentralized Approximate Actor-critic for Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
  Decentralized multi-agent reinforcement learning algorithms are sometimes unpractical in complicated applications. We propose a flexible fully decentralized actor-critic MARL framework, which can handle large-scale general cooperative multi-agent setting. Our framework can achieve scalability and stability for large-scale environment and reduce information transmission.
  arXiv  Detail & Related papers  (2020-04-17T14:56:29Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)
• Regret Bounds for Decentralized Learning in Cooperative Multi-Agent Dynamical Systems [3.9599054392856488]
  quadratic analysis is challenging in Multi-Agent Reinforcement Learning (MARL) We propose a MARL algorithm based on the construction of an auxiliary single-agent LQ problem. We show that our algorithm provides a $tildeO(sqrtT)$ regret bound.
  arXiv  Detail & Related papers  (2020-01-27T23:37:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.