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

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper establishes the first regret lower bound for decentralized multi-agent stochastic shortest path (Dec-MASSP) problems under linear function approximation. Using novel symmetry-based arguments and carefully constructed hard-to-learn instances, the authors prove an Ω(√K) regret lower bound over K episodes, matching the existing upper bound in K up to constants and poly-logarithmic factors.

Problem¶

Prior work (MACCM, [23]) provided the only regret guarantee for Dec-MASSPs—an upper bound of Õ(B*^1.5 · d · √(nK/c_min))—but no lower bounds existed, leaving open whether decentralized multi-agent SSP learning is fundamentally harder than the single-agent case and whether the existing algorithm is optimal. Four technical obstacles blocked extending single-agent lower bound techniques: (i) exponentially large global state-action space (2^n states for n agents), (ii) coupled costs and dynamics across agents, (iii) intractable multi-agent value functions, and (iv) KL divergence with exponentially many terms.

Method¶

The authors construct a family of hard-to-learn LM-MASSP instances on a minimal two-node network {s, g} with n agents and global state space of size 2^n. Feature design: They introduce a novel per-agent feature map φ_i(s'i | s_i, a_i) ∈ R^d that encodes node-occupation counts and action alignment with the unknown parameter θ, producing valid transition distributions (Lemma 1). State partitioning: The exponential state space is partitioned by "type" r (number of agents at node s), reducing value function analysis from 2^n states to n+1 types. Optimal policy characterization: Using mathematical induction on r and a monotonicity lemma (Lemma 3/4), they show the optimal policy always selects action a_θ (aligning each action component with sgn(θ_i,p)), and the value function V(s) = V_r depends only on the state type r (Theorem 1). Information-theoretic lower bound: Regret is lower-bounded via misalignment counts N · Δ²/[δ(d−1)²] · E[N^−]. Setting Δ = Δ}(θ); truncated sums handle unbounded terms. KL divergence between path distributions under θ vs. flipped-coordinate θ^j is bounded by exploiting instance symmetry (Lemma 7): KL(P^π_θ ∥ P^π_{θ^j}) ≤ 3 · 2^{2n = (d−1)√δ / [2^{n+5} · √(KV_1)] and using V_1 ≥ B/n yields the final bound.

Key Contributions¶

First Ω(√K) regret lower bound for any decentralized learning algorithm in LM-MASSPs, matching the known upper bound in K.
Novel feature construction for linearly parameterized transition probabilities in MASSP instances, handling exponential state-action spaces and serving as a design template for broader Dec-MARL applications.
Structural characterization of optimal policies: type-r state partitioning and value function monotonicity (Theorem 1), enabling tractable lower bound analysis despite exponential state space.
Symmetry-based KL divergence bounding (Lemma 7) to handle the exponential number of terms in multi-agent settings.
Recovery of the single-agent lower bound [14] as the n=1 special case.

Results¶

Main lower bound (Theorem 2): For any Dec-MARL algorithm π and n ≥ 1, there exists an instance θ ∈ Θ such that E[R(K)] ≥ d · √(δ · K · B/n) / 2^{n+9}, for K > n(d−1)² · δ / [2^{10} · B · (1−2δ)/(1+n+n²)].
Matches the upper bound of [23] (Õ(B*^1.5 · d · √(nK/c_min))) in K up to constants and poly-log factors; closes the open question on K-optimality.
Recovers the single-agent lower bound Ω(dB*√K) from [14] at n=1 (matching the corresponding upper bound).
Purely theoretical—no empirical benchmarks; the hard instances are existence results, not practically observable worst cases.

Limitations¶

Lower bound is an existence result: Theorem 2 does not identify which specific instance is hardest for a given algorithm, complicating empirical validation.
Constructed instances may not reflect practical MASSP scenarios (uniform cost, two-node topology, linear features with specific structure).
Does not formally establish a separation between Dec-MASSP and single-agent SSP regret—whether MASSPs are provably harder than single-agent SSPs in general remains open.
Results restricted to linear function approximation; extension to non-linear approximations is an open problem.
Effect of specific communication protocols (beyond the communication-agnostic framework) on regret is not analyzed.
Only one competing algorithm (MACCM [23]) exists in this setting, making runtime comparisons infeasible.

Relevance to Agentic AI / LLM Agents¶

This paper provides fundamental theoretical grounding for decentralized multi-agent systems—the same coordination setting that underlies multi-agent LLM frameworks where agents cannot or do not share private information (costs, observations). The Ω(√K) lower bound clarifies what no decentralized learning algorithm can improve upon, establishing a complexity floor relevant to any multi-agent deployment regardless of whether agents are classical RL or LLM-based. The novel state-partitioning and symmetry-based analysis techniques may inform the design of scalable coordination protocols and benchmarks for multi-agent LLM systems operating in shared stochastic environments. However, the connection is primarily foundational—this work addresses theoretical MARL rather than practical LLM-agent architectures directly.