Research map / Multi-agent systems and games / Cooperative multi-agent RL
Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves the first regret lower bound for decentralized multi-agent stochastic shortest path (SSP) with linear mixture MDPs, showing Omega(sqrt(K)) regret is unavoidable, matching the known upper bound up to log factors.
Problem
Regret of learning in decentralized multi-agent stochastic shortest path problems with linear function approximation (LM-MASSP); prior work only had upper bounds.
Approach
Constructs a family of two-node hard-to-learn LM-MASSP instances parameterized by agent-action sign vectors, shows the optimal value is monotone in the number of agents at the initial node, and uses information-theoretic (KL/Pinsker) arguments to get a sqrt(K) regret lower bound that holds for any decentralized algorithm, with no assumption on information sharing.
Key results
- Establishes an Omega(sqrt(K)) regret lower bound for decentralized LM-MASSP, matching the sqrt(K) upper bound of MACCM up to poly-log factors.
- Recovers the single-agent two-node SSP lower bound of Min et al. when n=1.
Limitations
- Only exact linear function approximation is considered; model misspecification is not analyzed.
- Lower bound constructed only with two-node instances; extension to more nodes is not proven.
- No empirical validation; the lower bound is existential and not checked against algorithms.
Experimental setup
Metrics: regret scaling in K
Baselines: MACCM
Builds on: Min et al. single-agent SSP lower bound MACCM (Trivedi et al. 2023) linear mixture MDP
Closest papers by meaning
- Near-optimal Regret Bounds for Stochastic Shortest Path (ICML 2020 · similarity 0.89)
- Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret (NeurIPS 2021 · similarity 0.89)
- Minimax Regret for Stochastic Shortest Path (NeurIPS 2021 · similarity 0.88)
- Decentralized Multi-Agent Linear Bandits with Safety Constraints (AAAI 2021 · similarity 0.88)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.86)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.