Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems
Authors: Utkarsh U. Chavan
Prashant Trivedi
Nandyala Hemachandra
Venue: NeurIPS 2025 poster ()
Keywords: Lower Bounds
Decentralized MARL
Stochastic Shortest Path
Reinforcement Learning
Feature Design
Primary area: reinforcement_learning
TL;DR: First 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 $\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.

Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems
Utkarsh U. Chavan
Prashant Trivedi
Department of Mechanical Engineering Indian Institute Technology Bombay
Computer Science and Information Systems
BITS Pilani, Pilani Campus
Mumbai India 400076
Rajasthan 333031 titb .ul.pppooo pt@gmail...... com
utkarrshuclavvnn0ggmae..cccc com
Nandyala Hemachandra
Industrial Engineering and Operations Research Indian Institute of Technology Bombay Mumbai India 400076 nh@iitb. ac in
Abstract
Multi-agent systems (MAS) are central applications such as swarm robotics and traffic routing, where agents must coordinate in a decentralized manner to achieve 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 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-band -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 hard-to- learn instances for any number of agents, n. Our regret lower bound of 2( ((vK), 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-agen, systems.
Introduction
The Stochastic Shortest Path (SSP) problem is foundational model for goal-oriented decision- making under uncertainty, extending classical shortest path formulations by incorporating stochastic transitions and random costs [6, 4]. In an SSP, an agent sequentially selects actions in a probabilistic environment with the objective of reaching a designated terminal state while minimizing the expected cumulative cost. By explicitly modeling uncertainty in outcomes, SSP serves core abstraction in many areas, including robotics, automated planning and reinforcement learning. While planning in fully known SSPs is well understood [5], the focus has increasingly shifted to the learning setting, where the agent must learn the optimal policy through interaction with the environment. The quality of learning algorithms is typically measured using the notion of regret, which quantifies the difference between the cost incurred by following a learning algorithm and the optimal policy [11, 3, 2].
Given its broad applicability, the problem of learning optimal policies in tabular SSP environments has garnered significant attention, leading algorithms with nearioptimal regret guarantees [20, 18. 21, 7]. However, in many real-worke applications, the state and action spaces are humongous, making tabular
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

approaches computationally infeasible. To overcome this, recent works have assumed linear structure in the cost function or transition dynamics [25. 14. 24]. These approaches have led algorithms that achieve sublinear regret in SSPs with either known or unknown cost settings, along with tight upper and lower bounds on regret [20, 18, 7, 14, 24], making the single-agent SSP well understood.
Despite significant progress in single agent SSPs, many real-worid applications such as robotics, traffic routing, and distributed control naturally involve multiple agents interacting in a shared environment [9, 16, 1, 13]. These multi-agent systems are often decentralized, meaning agents cannot or choose not to share private information (e.g., their actions or incurred costs). However, they can exchange certain parameters (e.g., cost or transition parameter estimates) over predefined communication graph. Motivated by this, [23] introduced the decentralized (Dec-MASSP) problem with linear function approximations of transition dynamics and costs. They propose learning algorithm and report sub-linear regret upper bound of ((Br1.5d / where n is the number of agents, K is the number of episodes, di is the individual feature dimension, B" is the maximum expected cost-to-go, to-go, and Cuin > 0 is lower bound per-period cost. While it provides the first regret guarantees for Dec-MASSPs, optimality of their algorithm remains open leading us to central question:
aggett stochastic shortest path
What are the fundamental limits of learning in Dec-MASSPs with linear function approximations?
To address this question, we establish tight regret lower bounds for the decentralized MASSP setting by constructing hard-to-learn instances. Extending single-agent SSP lower bound techniques [14, 18] to decentralized MASSPs presents several key challenges, which we overcome using novel methods.
(i) Exponential state-action space. Even with just two nodes in the network, the global state space grows as 2" with the number of agents n, which complicates both instance construction and lower bound analysis. To address this in the linear setting, introduce novel feature design for the transition probabilities specific to our MASSP instances. These features lead to a valid transition probability distribution and can serve a foundational approach for feature design in other decentralized multi-agent reinforcement learning (MARL) applications.
(ii) Coupled costs and dynamics. In the MASSP setting, both transition probabilities and cost functions are inherently coupled across agents, depending on the global state-action space. To construct bard-to-learn instances and establish meaningful regret lower bound, we first demonstrate that it suffices to restrict the analysis to uniform cost. We derive closed-fone expressions for the transition probabilities using our novel feature design. This explicit formulation allows us identify the structure of optimal actions, making our approach both tractable and novel.
(iii) Intractable value functions. Unlike the single-agent setting with two nodes [14], where closed-form expression for the optimal value of the non-goal state can be exactly derived, obtaining similar expressions for the many non-goal states in multi-agent systems is significantly challenging due to exponentially many states. To address this, we observe that this huge state space can be partitioned based on the number of agents present at each node. This key insight allows us to establish a monotonicity property of the value function, which in turn is sufficient to derive regret lower bounds without requiring its explicit closed-form.
(iv) Bounding KL divergence. A standard approach for deriving regret lower bound relies on coommation-thorette techniques, particularly bounding the Kullback-Leible (KL) divergence be- tween two distributions. In the SSP setting [14], the KI. divergence reduces to just two analytically tractable terms. However, in the MASSP setting, the KI. divergence involves an exponential number of terms, making exact analysis intractable. To overcome this, we exploit the non-negativity of the KL divergence and leverage the symmetry in our problem instances, which allows us to bound the KL divergence efficiently depending on the number of agents present at each node.
Building on the challenges outlined above and the novel methods we use to address them, we now summarize the major contributions of our work.
We establish the first 12( ((VK) regret lower bound for decentralized MASSPs under linear function approximation, which matches the previously reported upper bound up to constant and poly-logarithnic factors [23], thereby providing a precise characterization of the fundamental limits of learning these settings. Notably, our result also recovers the lower bound of [14] as special case of 1, which matches the corresponding upper bound in K.
Regret lower bounds:

---

Design of hard-to-learn MASSP instances: The above regret bound is based on proposed family of decentralized MASSP instances with linearly parameterized costs and transitions that are provably hard-to-learn. As scalability with n is key factor in evaluating the efficiency of MARL, algorithms, our increasingly hard-to-learn instances (with respect to n) are suitable to assess the performances of such algorithms.
First analysis of instances with exponential state-action space: the first to handle exponential state and action space in MASSP settings. These lower bounds are based on the identification of optimal policies and value functions in two-node MASSPs. These optimal policies have the same values for all states with identical number of agents at each node.
Our lower bound analysis is
1.1 Related work
Stochastic shortest path (SSP) problems and learning in tabular setting. The stochastic shortest path (SSP) problem is a classical framework introduced in early work by [8]. [6] later extended deterministic shortest path theory to stochastic environments, formalizing the SSP setting within dynamic programming. More recently, the focus has shifted toward learning in SSPs under unknown dynamics, in the tabular settings. Authors in [20] introduced Upper Confidence SSP (UC-SSP), the
first no-regret algorithm for tabular SSPs, with regret Ö(DS / //AK///miiii where D is the expected hitting time and Cuin the minimum per-period cost, S and A denote the cardinality of state and action space and K' is the number of episodes. Follow-up up work by [18] improved this bound by removing the Cmin dependence and gave lower bound of 2 ( AAK), where B" captures the maximum optimal cost-to- to--to--g go-go, showing near-optimality. [21] further refined SSP learning through Exploration Bonus for SSP (EB-SSP), model-based based algorithm with regret Ö(B* /LLB*AAAA /SAK), that doesn't 't require prior knowledge 8 [7] introduced a Miiiimax-optimee algorithm under stochastic costs with matching bounds by reducing the SSP finite-horizon MDP.
Function approximation in SSPs. To address scalability beyond the tabular regime, recent efforts have explored SSPs under linear function approximation. [24] designed model-free algorithm with sub-linear regret and computationally efficient under minimal assumptions, using stationary policies. Parallelly, [14] proposed two algorithms, each based on Hoeffding-tyre and Bernstien- type sets. The Bernstien-type confidence set based algorithm has a better regret upper bound of OdB" /K/Cmin) Additionally, the paper provides a lower bound Q(dB" /K) in this setting.
Decentralized multi-agent SSP. The extension of SSP learning to decentralized multi-agen sys- tems is still in its early stages. Authors [23] introduced the MASSP framework with linearly parameterized costs and transitions, and proposed MACCM- decentralized learning algorithm, reporting regret upper bound of Ö(B=1.5d ///...dd///// InK/Cmin), where is the number of agents. However, their work does not establish any lower bounds, leaving open the fundamental questions regarding inherent difficulty and optimal regret rates for decentralized MASSP learning. We close this gap by establishing the first regret lower bounds for decentralized MASSPs (with any number of agents, n) under linear transition kernel.
Table summarizes the relevant results.
2
Preliminaries and problem formulation
In this section, we introduce the Multi-Agent Stochastic Shortest Path (MASSP) problem, and also present the formal setup and notations that underpin the decentralized learning framework.
2.1 Notations and preliminaries
A MASSP problem is defined by the tuple IV,NPP.AA A), where V = {U1, u2,... R is the set of nodes and A' {1, ...... n. the set of agents. Each agent occupies exactly one node at in the global state space = > so |S| = q= We assume that all agents start at the same node s and aim to reach the common goal node y, resulting in initial and goal states 8in = (s....,s) 8) and = (g) (g.....9) . respectively. Each agent i E N has a finite action space Ar at every node, leading to a joint action (aI,..., on) A A X ... x An. Once an action is taken in the state s, the system evolves
any given time, leading to a global system state = ($1, $2....... sn)
3

---

Reference
Setting
Upper Bound
Lower Bound
[20]
Ö(DS MOOS/ADKjOR
[18]
Ò SK)
((BR)AAK)
[7] when B"
O(B'VSAR O(K
[7] when B²
9 ((VB-SAK) R(dB'
[14]
O(dB' /K/Cmia Cminn
[24)
Ö(dB" VaB K/Cmin + 3 /Cmin)
[23]
$
Ö(BLL5 dv /nK/Coiu))
LVKB*/0
This work
$
Ω
2n
Table I: Comparison of related work in SSP learning and decentralized multi-agent SSPs, Here and A denote the number of states and actions, respectively; K is the number of episodes; Cmin > 0 a lower bound on the minimum per-period cost to an agent; 3 is the SSP diameter, defined as the maximum (over all states) of the expected cost to reach goal under the optimal policy; D is the expected hitting time defined, as the maximum over all states, of the minimum (over policies of) expected time to reach goal state starting from this state. Symbols: tabular SSP (no function approximation), = linear mixture SSP (with linear function approximation), & = decentralized MA-SSP (with linear function approximation).
to next state s' according to a Markovian transition kernel IP(- s,a)) and each agent E N incurs an instantaneous cost (s,5a) E [Cmin; 1), where Cmin >> 0.
The cost function (s, a) captures complex dependencies of individual costs both the positions and actions of all agents, For example, the cost can be modeled by taking (s a) 22 ()) (s where (s, a) 25=1 [ayy=at } is the congestion (number of agents choosing the same action) and K2(s, a) encodes the cost due to private efficiency and all other complex dependencies (except congestion). The global cost is defined as the average of individual costs: c(s, a) Σ (s.a).
A stationary Markov deterministic policy is a mapping S - A. Given the stationary Markovian dynamics I' and cost c, an optimal policy lies in the class HMD of Markov determinístic policies [17]. We further focus on the class of proper policies 1I, S. 1MMD. i.e., the policies for which each agent reaches the goal node, from any initial state with probability one [20, 21, 7, 14). Given any proper policy x E II. the value function (or cost-to-go function) is defined as / V*((s)
E E c(s", m(s))) s² =s where the expectation is over all sample paths due to interaction of policy and transition kernel P. T (s) is the random time reach the goal state g under policy starting at s. The objective is to find a policy that minimizes the expected cumulative global cost from the initial state Sini to the goal state g. The optimal value function with the corresponding optimal policy xt is thus
(s) min (T((s)
(1)
We further define the diameter of MASSP as B maxes (s)
2.2 Problem formulation
When transition kernel IP and cost c(..)) are known, the objective of MASSP problem is find an optimal policy in the space of proper policies, as in Equation (1), However, in the learning setting with unknown transition kernel IP or cost c(.,), agents must actively explore learn an optimal policy. Though the goal is to minimize the cumulative global cost to reach g. agents in our setup act independently and lack knowledge of others' actions or costs. A natural solution is employ a central controller that aggregates signals from all agents to coordinate learning [26]. However, such centralization poses several challenges: (i) poor scalability with the number of agents due to increased communication overhead [12] (ii) vulnerability to single-point failures and adversarial attacks [27], and (iii) privacy concerns, as agents may be unwilling to reveal their individual costs. These limitations motivate decentralized learning, where the agents do not explicitly share the actions

---

or private costs among themselves via a central controller. This setting falls within the purview of Decentralized Multi-Agent Reinforcement Learning (Dec-MARL).
To make decentralized learning tractable, prior works (e.g.. [27,2_] adopt linear cost approximations c(s, (sb(s, a), w), where (5,s, a) Rnd is known feature map, and Red is unknown parameter, with nd << [|] This allows agents to coordinate via shared parameter estimates rather than raw cost values. Given the large state-action space, we also assume linear model of transitions, commonly used in recent literature. [14, 23]
Assumption 1. For every (s,a, a's') unknown parameter 8 E Rnd with d 2 2 such that P(s' a) = (ó(s'|s, a), 8).
) E S x A x S, there exists known features @(s'|s, a) E IRnd and
We design the features d(s'(s. specific to our setting in the next section. We refer to this setting as the Linear Mixture Multi-Agent Stochastic Shortest Path (LM-MASSP).
Algorithm. Analogous to [10, 15], define general (possibly randomized) Dec-MARL algorithm as a sequence of deterministic functions æ = [x =t=1 where at each time step f, the algorithm specifies a policy x' (.' m,))) Here n.. H (AA:) maps the history observed by agent i to a distribution over its action space A, from which the agent samples its action. Each history Hi consists of the agent's past observations- own actions and rewards, along with any information may have received from other agents in the network. To maintain generality, we do not impose any specific communication protocol; thus, our analysis and results hold for broad range of settings, from full information sharing to completely communication free (Note that in communication free system, our lower bounds are trivial since the global optimal policy cannot be learned [27]).
Performance criteria. Let (s aath)) denote the state-action pair encountered at step of episode k under given algorithm æ and model parameter f. Let h2 represent the (random) length of episode k. The expected cumulative regret after episodes is defined as
Ea Ea, E.,,
K V*
The above regret measures the difference between the total expected cost by following the algorithm i instead of (unknown) optimal policy. A desirable algorithm achieves sublinear regret in K, indicating that it eventually learns an optimal policy. In the setting described above, [23] propose an algorithm with expected cumulative regret Õ (VK). However, the optimality of this algorithm has not yet been established raising questions such as: Are better learning algorithms possible in this setting? If so, in what aspects can they improve compared to the existing one? To answer these questions, it is essential to derive tight regret lower bounds. Hence, we construct hard-to-leare instances with tractable optimal policies and analyze the regret of any algorithm. Following [2], we consider deterministic algorithms, though similar analysis extends to randomized algorithms, only the expense of notational overhead.
Our approach
In this section, we construct family of provably hard instances for LM-MASSP. These are designed so that the optimal policy is analytically tractable, where any deviation leads to measurable regret.
3.1 Construction of hard-to-learn LM-MASSP instances
We consider a minimal yet expressive network with only two nodes: V= {s, g} with n agents. This induces global state space S = {s.g]" of size [S] 2n, where any agent can either be or g. We fix the initial state as Sinit = (s, s,..., s) and the goal state as g = (g.g.....5 .g). We assume that once an agent reaches node g. it is impossible go back node Each agent [m] has the same action set A,, 11 111 for some d 2. Consequently, the global action space is AA = {-1, (dd(d-1) with |A| 2n(d-1) We parameterize transition probabilities according to Assumption 1. Next, define features o(s' (s,a), which may be of independent interest to the MARL community, as offers practical guidance for designing valid feature representations! We represent the concatenation of
'While there are many possible ways to design features, any valid feature construction must satisfy the conditions specified in Lemma below.
5

---

vectors z and by (a. v).
(di
,..., (1 an)
if # g and x.= if Vi E [n]
Øss' as
Ond,
s; g. s = for any E [n]
1)
ifs - 8, s =
(3)
where for every agent i E A the feature map (5(() 8c, a,) is defined as follows
(-a
if s; s
n-2"
if 8; 8, 8. g
(4)
122
if 9, 8 g.
In the above, r denotes the number of agents at node in the current global state S. The parameters 8 and A are chosen such that 5 E 2) and A <2- It=+n? (details are available in the next section). Furthermore, the transition model is parameterized by vector E Rnd the form
Let the set of all such 0 be O. Thus, |0] 2n(d-1), For any [n] and p E [d- 1], we denote the pth component of a, and fg as di.p and pp respectively. These parameters along with the features (-I.,.) .) define the transition probabilities as in Assumption 1. Observe that the first case in Eqn (3) captures general transitions, the second captures disallowed transitions and the third corresponds to the only certain transition.
0 (01, 1, 02 1......... p,, 1)T, where each 0
A
n(d-1j m(d-1)
Instances. With the above construction, we define hard-to-learn LM-MASSP instances by varying key problem parameters while maintaining analytical tractability of the optimal policy. In particular, we define each instance by fixed tuple (n, 6, A, 0) as defined above.
Lemma 1. For any instance (n, A, A), features defined in Equations (3) and (4) yield valid transition probabilities, i.e.,
1. We have, (0(5') |s, a),0) 2 AA (s) and Eves a), 1 (s, E A.
2. For any (s,a) E S x A. if transition to some s' E S is impossible, we have (Ø(s' |s, a), a),6, 8) = 0; on the other hand, if the transition is certain, then (6(s'|s,,))))))))) a).
The detailed proof of this lemma is given in Appendix C.I. Analysis of a general SSP instance is complicated due to trade-offs between policies that quickly reach the goal state (minimizing time) and those that take longer but cost-efficient [20]. These make optimal policies, in general, intractable. To avoid this, we adopt a uniform cost structure i.e., V a, c(s, a) = V & g and c(g, a) = 0. Thus, that minimizes the expected time reach goal and depends only
the optimal policy is the transition dynamics. Note that the above cost structure is not merely hypothetical; in our instance design, for all [n]. a E A, and s + g, we define K K'(s (s.a)) and set K* K'(g,a (g.a) O.
3.2 Transition probabilities
Using above features and the transition model in Assumption 1, we now derive general expression for transition probabilities for any instance (n,, 6, A, 0) in the lemma below. We partition the state space S based on the number of agents at node Let S, be the subset of state space with r agents at node i.c., (s11 .,, $2...., sn) E S Σiex (s,=s)
r.. For any E {0]U[n]. we say that state s is of type if E S,.. Clearly, UP S S and S,, ns,, 1 for any rı r2- Thus, SS ........
r)
., Sn)) |ss a) > O, for some a E A} as the of all states that are reachable from in the next step. Also let (s) be the set of all states of type r that are reachable in the next step from s, i.e. S,(s) = S, S(s).
partitions S. Further, for any s, we define S(s)= = {s' E S PP''
Lemma 2. For given state s E S 8. let I denote the set of agents at node s. Consider transition A. Let T C I be the of agents moving from to g. Define r [Z] r' II \ T and T' = N \ T. Then, under our proposed feature construction and
to s' E S(s) under joint action
Assumption 1 on the instances. we have
P(s'|s,a) r' (r 2r
r n 2
A
(r 2r')
n 2
71

---

d-1
2A
Σ VEINT
(ssg((ar.) & sgn(Or.p)3 - Σ (r. + sgn(Or.))3] IET
nld
p=1
Corollary 1. Following Lemma 2, if each agent i E N selects its action according to Di,j = sgn(0cs) y [d-1], the resulting transition probability is independent of and T, and it only depends on r and r'. We denote the corresponding global action by ag and resulting transition probabilities by pr.y"
We observe the following property regarding behavior of pr,y" with r and r'. This helps us identify optimal policies (Theorem 1) as well as derive regret lower bounds (Theorem 2).
Lemma 3. For every T E [n 11. the following holds: (a) for r' E =!0..... L 13. we have (T"")) < Prr and (b) for E { +l...., we have (** P (2)
Why do we expect tight lower bounds for these instances? In Theorem we will establish that, for any instance (n, 6, A, f), the optimal policy selects action ag in every state. Now consider sub-optimal policy that differs from ag in only one non-goal state and exactly at one component of global action. Due to the small A 2 2),,, the transition probability (from Lemma 2) for any (s, s') under this sub-optimal policy is nearly identical to that under optimal policy, implying the value of such sub-optimal policy is only slightly worse. There are (2" 1) nnd- such policies. Similarly, consider any sub-optimal policy that differs from the optimal at exactly one state but in two different components of global action. Again, due small A, we can expect the transition probabilities to differ slightly and the value functions for various states to be only marginally worse. At each state, there are ("(d-1)) such optimoptmal policies. Thus, there are ("(d-1) x (2" - 1) such policies. We can similarly obtain that the number of policies differing from optimal in any two states at any one component of global action is even higher (²";-1 x rndd - 1) x n(d - 1). So many near-optimal policies make learning the optimal policy extremely challenging for any algorithm.
4 Theoretical results
We now present main theoretical findings. Our goals are twofold: (i) characterize the structure of optimal policies and value functions in our LM-MASSP instances and (ii) to establish a tight regret lower bound for any decentralized learning algorithm in this setting. Intuitively, any state with less agents at the initial node a is expected to be closer to the goal state than any other state with more agents 8. Thus, it desirable have the state with less agents cumulative cost-to-ge go. Such monotonicity allows us to reason about the value function at coarser level depending on the number of agents at node s. Leveraging this structure, we characterize the optimal policy and value function in the following theorem.
have relatively lower
Theorem (Structure of the optimal value and policy). For any instance (n, 6, A)
(a) the policy that selects action ag (as given in Corollary 1) in every state s E S is optimal.
(b) the optimal value is same for all states of same type, i.e., for every r E [m], we have, V*(s) = V,"
for every E Sr, where Vi² depends only on r. We define Vi- 0.
(c) the optimal value function is strictly increasing with r, i.e. 0 = Vo Vi < V B².
The detailed proof is deferred to Appendix A. The theorem reveals that our instances admit a simple optimal policy depending only on parameter 0. Despite exponential state space, the optimal value function is fully characterized by its type. We emphasize that this result is critical, enabling our regret analysis and may be of independent interest in broader classes of symmetric decentralized multi-agent settings.
We now present our main result: regret lower bound for decentralized learning in LM-MASSPs. It matches the upper bound of [14] (for n 1) and reported upper bound in [23] for a general n in number of episodes, K.
Theorem 2 (Lower bound on regret). Let π be any decentralized learning algoritium. For every 1, (2/5, 1/2), and A < 2- 1-25 (14x4t3) there exists LM-MASSP instance (0 e Q) such
7

---

that, after K> B. (
15d-1 episodes, the expected cumulative regret incurred by satisfies
Ee [R(K)] d d.vo K BB-Bn
(29)
20+9
The proof is provided in Appendix B. This theorem highlights that with strong structure and symmetry in the instances, any decentralized learning algorithm suffers from fundamental information bottlenecks, and no learning algorithm can escape the fundamental Q v K) regret. Moreover, our lower bound recovers the previously established single-agent result [14] as a special case
1. Remark 1. The exponential decay of regret lower bound with may not be misinterpreted as weakening of the bound with increasing n. To analyze regret scaling with n, one must fix parameters (6, A, 0). Since A 2- (1n==2)) 1-26 ), inherently fixes the range n. For any valid instance, there (""""110
exist exponentially many near-optimal policies (see discussion after Lemma 3). In these instances, as n increases within this range, more suboptimal policies get closer to optimal, making learning significantly harder. The corresponding decay of the lower bound reflects the increased difficulty.
Outline of proofs
5.1 Proof sketch of Theorem 1
Proof. We use the Mathematical induction on the number of agents at node in any s E S. All the claims trivially hold for
So, we consider r as the base case.
Base case (r = 1). For any state E Si, the only reachable next state is either 8 or g. For any action E A, value of the policy Ta that always selects action at is given by (**(s) I-F(sia.a] Using Lemma 2, one observes that the self-transition probability P(s|s, a) is minimized at a = ag. This establishes the first claim. The above arguments hold for every s E S₁ and using corollary 1, the value is same for every state in Sj. This completes the second claim. The third claim holds as V/" > 0.
Inductive Step. Assume the three claims of the theorem hold for all {1, kJ. We now show they also hold for r = ++ 1, in the same order. Consider any state Sx41- To prove the first claim, we evaluate the value (s² under policy Ta that always takes action s and optimal action ag other reachable states. By the inductive hypothesis, values and optimal actions are known for all states in S Since all states reachable from lie in this set, i... (o (,)s S U the value (**(s) is given by
VT (s) = + P(s
+ E P(slss,aVV,, (E
(5)
Using the inductive hypothesis and Lemma we show that (** is minimized when as Sk+1, proving the first claim. The second claim follows directly from Corollary and Eqn (5). For the third claim, we Lemma 3 along with the following result (see appendix C.5).
Lemma 4. Let r E [n- 1]. Suppose that for every r' {0, 10.1...., 1
}}. we have ("+))'+ ()) and for every r' E [1_t1]111111 + 1, ,,...,r), r., we have (1t") > (F) Further, if V= Vi > Vo8 then Vi+ Vi-
This proves the final claim for r + 1. By induction, the claim holds for all r = {0, 1o..,....... (.....n). n).
5.2 Proof sketch of Theorem 2
Proof. Consider instances (n, 6, A, where n 2 1, 12/5,1/2) and A 2- 1-26
1+++n2 are
fixed, while 9 varies across instances with corresponding optimal policy тद as described in Theorem
1. Let s' and a' be the global state and action at time f, respectively. The expected regret of an algorithm æ in the first episode is
Eg , [R]] (T v (s²)
8

---

(x)) (nD() (V*(22- ( Butwa(stt ( .a)) V=
(6)
where in the second step add and subtract the expectation of optimal Q-function [19] and use its definition. We emphasize that unlike the value of a state under any Markov stationary policy, the value of any intermediate state s for any learning algorithm depends, in general, the past history till t. This implies that the V= (s²) above is not independent of the history for any fixed s². The first expectation in Eqn (6) suggests a recurrence. Using definition of Q"² and Lemma 2,
Ea (attn ( a') (s)) = Barr
ad') v=
x2 g
24
d-1
Σ
1 fssgn(at * sgn(Or.p)) v=o(st)
n(d - 1)
pml
We further lower bound the above using the following lemma (see appendix C.6).
Lemma 5. For any of our instances, V (s.a) E x Er (P(s")s, P(s a (s)
Further, unrolling the relationship in Eqn (6) recursively over all time steps h in the first episode and applying the third claim in Theorem to lower bound V (s') for each non-goal state s', we get
2AV1
Σ Eg, x [R]] 2 rd 1)
Bg,
ΣV
1fs * goal} ((sgn(a * sgn(Or
(7)
LiEZ,
where In denotes the set of agents at node s at time step h. Extending this over all the K episodes, the lower bound can be expressed as
n d-1 No. (0)
Ro.- (R(K)
2AV 2 nld - 1)
E
1ΣΣ j=1
(8)
g} (ssgn(at,) * sgn(0.,))} for each [m]. E [d - 1]. It is important to note that we cannot use the standard Pinsker's inequality here to bound the regret, as (6) can be unbounded for example, in case of trivial algorithms. To handle this, define the truncated sums up to a predefined T as N, = ΣT 1ss * g). N = max;e[n] N; and T
where (0) E 1(s
NT, (0) Ei= 1 * 9} 1 (sgn((of,) # sgm(O..g) } for any agent i [m]] and j [d 1]. Thus, the regret upto K episodes can be further lower bounded
2AV1
Es.- [R(K)] 2 n(d 1) Eg
ΣΣ NT.
For every 0 = (0), 1, 02, 1..,, On, 1) θ and j E [d - 1J. let 03 = (0,, 1, 02 I..., O, 1), where ...
for every E [mi], 02 is identical to 0g except at the jth coordinate, where 0',5 -0 Thus, we have
2AV
n ΣΣΣ
2 En [[(K)] DE5
Ea (NT,(N))) Bor IN., (00)
(10)
nld 1)
2AV
[s [N. + Es (NT, Eoi S. IN,,, (0)]) (11)
n(d 1)
00. i=1 1=1
The first step also uses the fact that Vi* is independent of 0 and the last step follows since N; = NT, (0) + NT, (0)) for any i E [n), j E [d-1] 1] along with noting that the map 0 - 0 is bijective for any j E [d 1]. To simplify the first expectation, we generalize Lemma C.2 in [18] as follows
Lemma 6. For any instance (n, 8, A, 0), algorithm n, and T 2 2KV1, we have [,,, KV. for any i [n].

---

This bounds the first term in Equ (11). The remaining terms capture the difference in expectations under different model parameters. Applying the Pinsker's 's inequality (Lemma E.3 in [14]. we get
2AV7 nt( Bge
KV TV
log 2
Σ Ee.[(R(K)] BE0
2
KL(PFIPP
(12)
In the above, P3 represents the distribution over T'- length state sample paths due to interaction of algorithm π and the transition dynamics described by parameter 0. Bounding KL divergence in the multi-agent setting is challenging due to exponential number of next states and actions. Since existing techniques [11], [14]) do not directly apply, we leverage symmetries in our instances to derive an appropriate upper bound the KL divergence.
Lemma 7. For any instance (n, 5, A, 8) and algorithm n, for any j E [d - 1}, we have.
A
KL P
S 3 2
o(d - 1)² Eg, [N
(64)
The proof of this lemma is deferred to Appendix C.8. Using Lemma 7, Bo.n [N IN
and
(d-1)vā
picking A = A
in Eqn (12) we get
VRV
(d-1) V8 KV
d Vo VKV 2
d. V. /KB-/n 2n+9
Σ BE
Ea [R(K)]
(13)
2
where the last inequality holds due to the result V/- 2 B* /n (see C.11) for any of our instances. Since this is lower bound on the average of expected regret over + there must exist at least one instance
0 E θ for which the lower bound in Eqn (13) holds. Finally, to ensure that the chosen A = A is nid
valid, i... A < 2 2 1-28 ). we obtain the following sufficient condition K
210.
This completes the proof.
Discussion
This work takes a first step towards closing the gap in our understanding of Dec-MASSPs under linear function approximations. We establish the first regret lower bounds for this setting, obtained by carefully constructed hard-to-learn instances whose complexity scales with the number of agents. By leveraging symmetry-bane arguments, we identify the structure optimal policies and their values. Our 12( (K) regret lower bound over K episodes underscores the fundamental difficulty of decentralized learning in stochastic environments. These findings deepen the theoretical under- standing of decentralized control and can provide a foundation for designing more efficient and scalable algorithms in MARL. It is important to recognize that our instances, created for the purpose of establishing fundamental limits of learning in the broad MASSP setting, may not be ubiquitous in practice. We also remark that, depending the application. it may be possible to exploit specific information to design learning algorithms (but limited to the particular class of application) with sub-v K regret. We also note that our lower bound theorem is an existence result i.e., Theorem doesn't 't help identify which of the exponentially many instances is hard-enough for a given algorithm hence, complicating empirical validations. Furthermore, due to lack of multiple algorithms this setting, run-time comparison be an interesting direction to pursue when more algorithms are available in the future.
the constructed hard instances is currently infeasible but would
The design of our MASSP instances is based on linear function approximations [14, 24, 23]; thus, an important extension of this work is to obtain suitable regret lower bounds with non-linear function approximations. It would also be interesting to investigate how both the regret upper and lower bounds behave under model mis- muis-seccificatins.. Furthermore, in order to have widely applicable results, we did not restrict to specific communication protocol among the learning agents. Yet, managed to close the gap in number of episodes, K. This calls for a study investigating the effect of various levels of communication among the agents.
An important open direction is to formally understand the increased complexity of decentralized MASSPs compared to single-agent SSPs. In particular, demonstrating a separation where the regret lower bound for a Dec-MASSP instance exceeds the upper bound for single-agent settings would establish fundamental hardness of MASSPs over single-agent SSPs.
10

---

Acknowledgments and Disclosure of Funding
The authors would like express their sincere gratitude their institutes for providing the necessary resources. They are grateful to the Reviewers and the Area Chair whose valuable feedback and constructive suggestions have greatly helped improve the quality of this work. Utkarsh acknowledges support from the NeurlPS Foundation for the Travel Award and from IIT Bombay-FedEx ALFA for the partial travel support. He also thanks his home Department of Mechanical Engineering at IIT Bombay for allowing him the flexibility of spending his final undergrad year at the Department of IEOR IIT Bombay as well as accepting this work as his undergraduate thesis. He also acknowledges the Teaching Assistantships provided by IIT Bombay in his final year. A portion of this work was carried out while Prashant was a Postdoctoral Scholar at the University of Central Florida, USA, under the mentorship of Dr. Amrit Singh Bedi. Prashant would like thank him for providing the flexibility to work on this problem.
References
[1] Gianluca Antonelli. Interconnected dynamic systems: An overview on distributed control. IEEE Control Systems Magazine, 33(1):76 88, 2013.
[2] Peter Auer, Nicolo Gesa-Bianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, -7,
[3] Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. Advances in neural information processing systems, 19, 2006.
[4] Dimitri Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific, 2012.
[5] Dimitri P Bertsekas. Nonlinear Programming. Athena scientific, 3rd edition, 1997.
[6] Dimitri P. Bertsekas and John N. Tsitsiklis. An analysis of stochastic shortest path problems. Math. Oper. Res., 16(3):580-555) 595, August 1991.
[7] Alon Cohen, Yonathan Efroni, Yishay Mansour, and Aviv Rosenberg. Minimax regret for stochastic shortest path. Advances Neural Information Processing Systems, 01-28350-283611 2021.
[8] James Eaton and Lofti Zadeh. Optimal pursuit strategies in discrete-state probabilistic systems. Journal of Basic Engineering, 84(1):23-29, 03 1962.
[9] Jennifer Gielis, Ajay Shankar, and Amanda Prorok. A critical review of communications in multi-robot systems. Current Robotics Reports, 3, 08 2022.
[10] Osband lan, Van Roy Benjamin, and Russo Daniel. (More) efficient reinforcement learning via posterior sampling. In Proceedings of the 27th International Conference Neural Information Processing Systems - Volume 2, NIPS' 13, page 3003-3011, Red Hook, NY, USA, 2013. Curran Associates Inc.
[11] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning, Journal of Machine Learning Research, 11(4), 2010.
[12] Jingchen Li, Yusen Yang, Ziming He, Huarui Wu, Haobin Shi, and Wenbai Chen. Cournot policy model: Rethinking centralized training in multi-agent reinforcement learning. Information Sciences, 677:120983, 2024.
[13] Kai Lin, Chensi Li, Yihui Li, Claudio Savaglio, and Giancarlo Fortino. Distributed learning for vehicle routing decision in software defined internet of vehicles. IEEE Transactions Intelligent Transportation Systems, 22(6)33730-374) 2021.
[14] Yifei Min, Jiafan He, Tianhao Wang, and Quanquan Gu. Learning stochastic shortest path with linear function approximation. In International Conference on Machine Learning, pages 15584-15629. PMLR, 2022.

---

[15] Ian Osband and Benjamin Van Roy. On lower bounds for regret in reinforcement learning. arXiv preprint arXiv: 1608.6688.22 2016.
[16] Jun Ota. Multi-agent robot systems as distributed autonomous systems. Advances Engineering Informatics, 20(1):59-70, January 2006.
[17] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[18] Aviv Rosenberg, Alon Cohen, Yishay Mansour, and Haim Kaplan. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pages 8210- 8219. PMLR, 2020.
[19] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[20] Jean Tarbouriech, Evrard Garcelon, Michal Valko, Matteo Pirotta, and Alessandro Lazaric. No-regret exploration in goal-oriented reinforcement learning. In International Conference Machine Learning, pages
PMLR, 2020.
[21] Jean Tarbouriech, Runlong Zhou, Simon S Du, Matteo Pirotta, Michal Valko, and Alessandro Lazaric. Stochastic shortest path: Minimax, parameter-free and towards horizon-free regret. Advances in Neural Information Processing Systems, 34:6843-6855, 2021.
[22] Prashant Trivedi and Nandyala Hemachandra. Multi-agent natural actor-critic reinforcement learning algorithms. Dynamic Games and Applications, Special Issue on Multi-agent Dynamic Decision Making and Learning, edited by Konstantin Avrachenkov, Vivek S. Borkar and U. Jayakrishnan Nair, pages 1-31, 2022.
[23] Prashant Trivedi and Nandyala Hemachandra. Multi-agent congestion cost minimization with linear function approximations. In International Conference Artificial Intelligence and Statistics, pages 761 1-7633, PMLR, 2023.
[24] Daniel Vial, Advait Parulekar, Sanjay Shakkottai, and Srikant, Regret bounds for stochastic shortest path problems with linear function approximation. In International Conference Machine Learning, pages 22203-22233. PMLR, 2022.
[25] Lin Yang and Mengdi Wang. Samplc-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[26] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021.
[27] Kaiqing Zhang. Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference Machine Learning, pages 5872-5881. PMLR, 2018.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims are demonstrated in the key results Lemmas and Theorems, with explanations next to them.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The assumptions given in the paper give the limitations of this work. Further, future work direction in the conclusions describe another limitation of this work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
We have provided the assumptions used in this work, that are used in main the results.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: The experimental results are not provided, since we are providing the regret lower bounds, that require construction of hard-to-lcamt instance.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. ccppp.ccpppullc///eecccc/ hew.diiciggiie...eeeee /CodeSubmia (isoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our work is theoretical, and hence there are no computational experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is theoretical, thus does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that NeurIPS Code of Ethics https://neuripp: https://waarrrs..ccppppccc/cccee hctppp/bcccc/tthccccseeeeellllll
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: All the points mentioned in the NeurlPS Code Ethics are taken into consid- eration.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Applications of decentralized MASSP are mentioned in introduction with positive societal impacts because of better resource utilization.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is no release of data models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: There is code, data, models, etc. involved.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There is no asset, code, data, models, etc. involved in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does neither involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does involve research with human subjects, thus no approvals are required.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
18

---

Appendix
In this appendix, we provide additional notation, definitions, and proofs the theorems and interme- diate results that support the main findings presented in the paper.
More details of proofs of Theorem 1 and Theorem 2 are in Appendix A and Appendix B respectively, Also, proofs of some other intermediate results, used in Appendices A and B, are in Appendix C.
We first recall the intermediate results that Theorem 2.
to prove the main results, ie., Theorem 1 and
Lemma 1. For any instance (n, 8, A, 0), features defined in Equations (3) and (4) yield valid transition probabilities, i.e.,
( (s.a) E x A. 2. For any as,a)= S A. if transition some s' S is impossible, we have (Ø(s' |s, a), 0: on the other hand, if the transition is certain, then ( =1
1. We have, (é(s'(s, (o(s')s,a), a), 2 AA as,), and Eses(o(s')
Lemma 2. For given state s E S \gg let I denote the set of agents at node Consider transition
to s' E S(s) under joint action a E A. Let T C I be the set of agents moving from 8 to g. Define
[Z, r' II TI and 'T' N \ T. Then, under our proposed feature construction and Assumption 1 on the instances, we have
P(s'(s,a) r' (r 26
n
A
+
(r (r-2r')
22r)
n1 22-21
n n.27
n
d-1
2A
Σ VEINT
1sggn(ar,)) & sgn(O:,p)) E ((sgn((ae)) + sgn(Or.p))
nld
p=1
LET
Corollary 1. Following Lemma 2, if each agent i E N selects its action according to aijj = sgn(Brg) YjE [d-1], the resulting transition probability is independent of and T, and it only depends on and r'. We denote the corresponding global action by as and resulting transition probabilities by pi..'
Lemma For every T E - 1I, the following holds: (a) for r' E 1O.....LE1... 13. we have (**)) Pr < Prr and for E {( +I...,, we have (*t M Pr
A Proof of Theorem 1
Theorem (Structure of the optimal value and policy). For any instance (n, 5, A,
(a) the policy that selects action as (as given in Corollary 1) in every state E S is optimal.
(b) the optimal value is same for all states of same type, i.e., for every r E [n], we have, (*)s)= = V
for every E Sy, where Vi depends only r. We define Vi- = 0.
(c) the optimal value function is strictly increasing with r, i.e., 0 Vo V
V B
Proof. The simplest ease when all the agents are at the goal node, i.e., r = 0, i.e. s E Sg. Note that in this case [Sp] 1, that is when r = 0, there is only one state g = (g. 9, ........11 g).
For this case, all the actions at goal node are optimal, this because no matter what action taken at the goal state g, the cost is same i.c., O. Moreover, the next state is certainly g (by construction of features). Hence, particular, the action ag is also optimal. Hence the claim (a) of the theorem holds.
Next, since S = 1, the claim (b) also holds trivially. That is, (*(s) Vo¹ 0 for all Su- Finally, the claim (c) also follows by assumption, as Vir 0 B".
Now, we begin to prove the theorem for the interesting states, i.e., states in which at least one agent at the node s. We will prove all the claims of this theorem using the principle of Mathematical induction on the type of states I....,n.. n. To this end, first consider the base case of 1.
19

---

Base case, r = 1. For any state E S1, we first find the optimal action in this state. Note that for this state, there are only two possible next global states, itself and the global goal state g. This may seem very similar to the single agent problem.
Suppose s, a) denotes the transition probability from to for any A. To determine the optimal action at this state, we consider any policy that takes action a E A in the state and the optimal action other states that are reachable from s, Note that, above we argued that the action ag is optimal at g and hence the value of this policy at s can be expressed as
V (s) = P(s|s.a) a) (1 + (s)) (1 P(s)s.a) a)) (1+
(14)
Simplifying the above expression using Vo we have
v (s) = - P()
(15)
Thus, the optimal action at s is the one that minimizes (s) i.e., minimizes P(s]s, a). We now use the following corollary of Lemma 2; the proof of Corollary 2 is given in Appendix C.10.
Corollary 2. For any non-goal state s E S of type the self-transition probability under action is
P(s = n 2 2
r(1-6) n- A.A
+
2A
ΣΣ
((sgn(os.)) # sgn(O:.p)) (16) VEI
d-1
n(d - 1)
This is minimized when ag and the resulting probability only depends on
Using the above, we have that ag is optimal action in this state. Notice, we chose E S1 arbitrarily. Hence the above holds for all states in Sj. This proves claim (a) of the theorem for the base case of r
Now from Corollary 1, we have that
P(s)s,a")= = Pi.1: E
(17)
where pi,, is the probability that is independent of state itself, rather only depends on the number of agents 8. Thus, from Equation (15), have that (*()) Vi", V Si. This implies that value is same for all states in Sj. Thus claim (b) of the theorem also holds for the base case.
Finally, we have that V I-Pls s.ao] 0 Vi This completes claim (c) of the theorem for the base case. Thus, all three claims of Theorem hold for the base case.
Inductive Step. Next, let us assume that all three claims of the theorem hold for 1: = 1,2.....? for any < n We will prove that the claims hold for k 1. In particular, we assume that for all E (1....,7). it holds that
1. The optimal action a" = for any state in Sa.
This implies from Corollary that, the transition probabilities from any s Se any s' E S(s) can be expressed as pk.e. for any 1e' E {0, 1, 2,..,, k) under the optimal policy.
2. Vg (s) Vg for all s E Sk
3. V/ 1
We will now show that all the three claims hold for k ++
Consider any E S, We again want to know the optimal action in this state. The optimal action in all the other states that are reachable from are known. Hence, we consider any policy na that takes a E A at this state and optimal actions at all other states that are reachable from here. The value of this policy can be expressed follows
V (s)
(18)
= Σ
+ V*(s)) + P(sls,a)(1 + P(gls,a) (s)) (1
(19)
(FE)
20

---

= + P( (s) + P(gls.a) +
Σ Σ
VV)
(20)
(1
We will simplify the last term in the above equation using Lemma 2 as follows.
Σ
Σ
aVs
(=
Σ
+ +
+
n n-r-1
A -
(r + 1-+1-22)
n.
n22+1
y (x)
2A
Σ VEINT
1 (sggn(As.p) + sgn(Oi.p)
Σ
{sgn(ar.p) & sgn(Ot.p))) V3
n(d -
p=1
IET
(21)
p' + (r 11-1-100 2r')0
n - ----1 1 A
+ (r [r+1-1 (1+1-229)
r (++1 1) rd
n n
n2*
2A
Σ Σ
Σ
Hlsg((rt.)) + sgn(Or.p))
n2d - 1)
p=1s'E8,111)
iEZNT
1 (sgn(or.p)) + sgn(Ot,p)) )
Σ 1ET
V3
(22)
The Equation (22) follows by observing that for fixed r', the inner summation over s' in the first line is just the sum of (s)) = (*+t) terms of same value.
In the below, we alternatively represent the summation over sets In T and T as an appropriate summation over I and in the next step, we take the (*) factor inside and take the summation two terms:
Σ
Σ PV)
(r 1-2'6
n-r-1 A (r ( 211)= (r+11)
1
n.2r
m22+1
2A
Σ Σ
d-1
HiEIITT ((sgn(a;,)) + sgn(Oi,))
rld
p= p=1r'ES,(1)) tex
1fi T) 1177--111s0 (sgn((ar.p) # sgn(Or.p))
Vi
(23)
Σ
pl + (r + 1 - 2r
n n-r-1
A (r (r+1-1 ( 221) (++1) 1
Vi
n 2"
n1
n
r"'
d-1
2A
ΣΣΣ Σ
((iEInTT 1 1(ggn(ai.)) # sgn(Or.p)
(2d - 1)
p=1 1E (1)
1(i T)1 # sgn(0r.p)
Vi (24)
r' + (r 1 28'
n r
( -22))
A
(r+1
Vi
n 2"
m2
n
r'
21

---

d-1
2A
(11) 1(sgn(ar,)) + sgn(O.p))
re(d 1)
p=1 iEZ
+ (
1 (sgn(arr)) & sgn(Orw)) Vç..
(25)
In the last step, we identified that for every agent E II for a fixed r' the number of states in S, (s) in which the agent i stays at node itself are (r_1) and those in which it transits to node g are (,5).
In the immediate below step, use the following property: for any function f()) and natural number m, we have Eae(m] f(a) = Eagim) f(a) + Eue(m/ f(1 + m - a). In our case, f is the terms
inside the summations over p. i of Equation (25), is r' and m is r. In the next few steps, we simplify the expression using properties of binomial coefficients:
P(s'(s,a\Vz
r' (1
(r + 1 2r')0 n n-r-1
A
(r +1 1(++1-22)
(++11) V
(r 1)
n 2"
n2r+1 n
("'
A
d-1
((--1) - (+)) 1 (sgn((aip) 7 sgu(Or.p)} Vi3
n(d 1)
((++---11) -1--))))(+p)))) (++1-+))
1 (sgg((arp) # sgn(Os.p) } 17 V
1=
(26)
(r + 1 27')0
n n-r-1
A
(r + 1- 1++11))) (++1) V
+ n
n-2"
m21+1
rd
ΣΣΣ ((-1)- (P)) 1(sgn(ai.)) + sgn(Or.p)) V,,
(0)
r () -(sgn(ai.)) + (gipp: Vitt--
(27)
(r+1 2r')6
n - r -
A
2+1) (r 1 ( (r pd
Vi2
n n n2r+1
n
ΣΣΣ ((-1)-
(2-()) (+)) (sgg((ar,)) + sgn((r,))) (V2 - Vini-
n(d - 1) ilizr
(28)
Observe that the term inside the summation is always non negative since when r' > r/2 the binomial difference (x=-,) (5) 2 0 as well as V 2 Vi+i- while for r' S r/2, (p-") (2)
< 0 as
well as V/3 S V* -- due to property of Binomial coefficients and the Induction assumption on monotonicity of V* Note that the above argument is for E [r].
To minimize (s)(s), need to minimize P(s)s,a) a) as well (can be seen by rearranging Equation (20) along with the fact that V* (g) = O as it will appear in denominator as 1 - (P(sss.))) a)).
Clearly, the action ag minimizes P(s(s.a) a) as well as makes the sum of non-negative terms the minimum i.c., O. Hence, it minimizes (s). Hence this action ag is the optimal action at s. Note we had chosen E S,+1 arbitratily. Hence, the above arguments hold for any E S, This proves claim (a) of the theorem for r + 1.
Again, by Corollary 1, for any E S and any s' E (p), we have P(s'|s, an) = 1i41, for any r' E [r] U (0).
22

---

Thus, using = in Equation (19), we have (s()) = V for any s E S,+1. This proves the claim (b) for + 1.
Using the induction assumption combined with the above results, Lemma 3 and the following lemma we have V > Vi,, completing the claim (c) for r ++1
Lemma 4. Les r E [n- - 1]. Suppose that for every r' E (0.1,...; L we have (7t (*+) < ()) and for every r' E - +,...., we have (** Pi > (P) Further, if
Vi V >->>... > Ví > Vo = 0, then V > V
The proof of Lemma 4 is given in Appendix C.5. Thus, by induction, all the three claims of theorem hold. Note that V = 3 as it is the maximum optimal value over all states.
B Proof of Theorem 2
Theorem 2 (Lower bound on regret), Let π be any decentralized learning algorithm. For every 2 1, 8 E (2/5, 1/2), and A < 2 ( 1-26 (tntnz), there exists an LM-MASSP instance (f E 2) such episodes, the expected cumulative regret incurred by satisfies
n(d 1)d-1)2-
that, after K >
B
1-26
1-ntn
d. d.vo. VK. / 2n
E (R(K) 2
(29)
Proof. The proof builds on techniques used in the single-agent SSP setting by [14] and the two- state RL setting in [11]. However, extending these ideas the Multi-Agent SSP (MASSP) setting introduces several technical challenges. These include: designing novel features, constructing instances that generalize any number of agents while admitting tractable optimal policy, the intractability of expressing the optimal value function in closed form due to exponential growth of the state space, and deriving tight upper bounds on the KI. divergence. Some of these challenges are addressed in Theorem 1, while the remaining ones are tackled in the below analysis.
We construct and analyze hard to learn instances based on the discussion in Section In Theorem we characterized the optimal policy. Recall that for our instances, the cost of any global action in any non-goal state is equal to I and that in goal state equal (see discussion at the end of Section 3.1).
Consider any instance parameters (n 2 1,8 E (2/5, A < 2-
1-26 "Inntx=) We want to analyze regret of any algorithm π for instances that are defined by fixed parameters (n,, 6, A) and all 0 E O.
Consider any instance E O. Let лh denote the optimal policy for this instance as in Theorem 1. Suppose in episode k, agents take actions according to æ. Let, s" represent the global state and a' the global action at time Note that as we are analyzing any algorithm, is important to track the time any state is reached and the history till then. Then, the expected regret for this instance the e episode is:
step at which
Es xx [Ri] V (**)) V=O (s²2
(30)
= V (s²) - ExiNT(S)) 1Q (ss),a))==)))))))))))))))) Eai > (5², a²)] Va (s²)
(31)
In the above, we add and subtract E. wi((s) 1Q (s² aaa))a)) Now using the definitions of VT(()) and Q=ò (-.-) and rearranging the terms we have:
Ee. [Ri] = ( ( i a²) + Ea at [s²
Eat [c(s' a²) + EswN(( at)) a1) [V
/ (s
+ Egg ~ ( aaa)] V (s!)
(32)
Egii 2 P(le .2) [V*((()) y (=2)) + Ext 1Q (st, aaa)) ud (s*) (33)
In the above expression, there appears to be recursive relation for the first term however, it is unclear how to deal with the remaining terms. To this end, we expand the second term below using the definition of Q" (...) = Q and V*(+) V
Eg, ( 1Q"(s (s', .a (*((") Ea Ea lc(ss aa') + Ba a () v*'))) (34)
23

---

Above, we use the definition of (*(..)) and then expand the expectation as
Next, we use the cost c(s.a) 1, A (s.a) E E A
Battar (s' aa)) (Q" (*t)
+ B -V(
(35)
Beiwa(st)
1 P+ a'') + Σ P(s aa)) - (-+)t)
(36)
To simplify above, we use the general transition probability expression from Lemma 2 with s (s, S, ",..,,.,.)).
s), i..., r = n, and then rearrange
F Fa' (Q" aaa) [²)] - (s')
1- 5
2A
=Eg'Na(s!) 1
A
{gnn (s) + sgn(0u,p33 v2(
2n-1
n(d=
P(s"'s" a')))((s)) - v(6') (37)
1 8
- 2) (-((t) + Σ p v' v-(stt)
Egtwa(tt)
1+
2
,24421
d-1
+ (g(wx(()))
2A
lfsgn(ai.p) + ((tp)) -
(38)
ald= - 1)
i=1 p=1
Egl )
+ 1ss (s*) + Σ a')V"' - v-(st))
24
+ ((()))
(sgn(at))) + sgn(O.,))\*'(5))
(39)
a(d-1)
i=1
The last step follows from transition probability expression in Lemma 2. Now, expand V=(s!) and simplify
En (Q")) (a)) -v*
= (()))
1 P
((')((")"""")v((())
+ Σ p( (a") - (1 ,(s"'s',"'''v'' (('))((s')
d-1
+
Σ P(s ("")""a""\V'(07))
+ (
2A
(a)n(a).)) # sgnn(
n(d- 1)
2
(40)
Σ (P((211s ( ('6'""
Bg (x+)
n d-1
2A
(sgn(at.)) + sgn(0 sgn(Ot,p))v*(())
(41)
re(d
1)
p=1
Next, we have the following lemma (proof in Appendix C.6)
Lemma 5. For any of our instances, & (s,a) E S x A Er (P(s'(s,a) P('')s.a))\V''''>> 20 0.
24

---

Using the above lemma, we have the following bound:
n d-1
2A
Ba) (Q"" v*(ss) 2 E. ((s))(s))
1 (sgn((at.)) # sgn(8s.p)
n(d
(42)
Using Equations (30), (42) and (33), we have that [Ri] = (*(s') VTa (s')
(43)
2 Egin~ )()
P(,lrt at)
( Vs()))
2A
d-1
1 1s + { + sgn(Orp))\V'(s
+ Ba'
m(d-11
(44)
This introduces recursive structure in the regret: the difference time is written in terms of the expectation of the same difference at time 2, plus another term. Although s is deterministic, s² is stochastic due transitions under и. Taking any sample path of length H (i.e., global goal is reached at step H), and unrolling the recursion across all steps (similar to the analysis between Equations (30) and (44)), we obtain
H
2A
(=('s))('(s'))) E1
11s + goall (sgn(())) + s)
n(dd
h=1
iET, p=1
(45)
where 1n represents the random set of all agents at node s in global state s and where the expectation taken with respect to trajectory induced in the first episode due to the interaction kernel Po. Note that in Equation (44), we have the summation over all agents in [n] since I [n] as s = Sint and, this I, differs for different times based on sample paths. To fully convince why I, occurs in the above expression, we encourage the reader to try carrying out the steps between Equations (30) and (44) for the second time step and then observe the pattern for arbitrary h.
and transition
Now, observe that as per our model, once an agent reaches the goal node, it remains there for the rest of the episode. For all by construction, making the indicator term 1ss" * goal) = O. This allows us to safely extend the summation to infinity without altering its value. Specifically, we apply the following identity:
in this episode, the global state is thought to be the goal state,
Σ r =
Σ
1 <
(46)
where 7 and xg are random variables. Using this, we get
2A
VT((') - 2 (s 2 E
(st * goal) (sgnlal; # Vg
(d
iET p=1
(47)
Using the fact that (x) 2 V for any E S'g, we have that
2AV* Eg. [R1] n(d - 1) E
Σ Σ
1ss # goal)[[sgn((c)) sgn(Or,p))
(48)
iE,, p=1
Now, the total expected regret over K episodes is
21V1 (R(K)) nid - 1)
20 ΣΣ>
Eg,
1 118 + goal) + sgn(Or.p))
(49)
Lt=l MelieL. p=1
25

---

We get rid of the random set L by introducing an indicator as below, where sf denotes the 1th index of state s² i.e. node which agent is present at t:
2AVÍ nld
Es, [R(K]] 2
B0.
Σ (=l
1(
+ 9)
Σ 1ss # (sg()1 # sgn(0s.))
iE(m)
(50)
2AV' nld 1)
ΣΣ i=1 p=1
1 1ss + ()gnaag(()),)) # sgn(Os,p))
(51)
where the simplification follows since 1 (( # 9} (ss # goal] = 1 1(s + g) for any E [n] and t N.
For any E [nj. let N₂ be the random variable capturing total number of time steps over K episodes in which agent stays node s,
N = Σ 1 و
(52)
Further, for any agent E [x] and j E [d- 11, let (0) be the (random) number of times in the entire duration of K episodes that the agent chose jth component of action as not the same as that of the optimal action for that instance while being at node Formally, it is given by
DC
(0)
Σ (s + (sgn + sgn(
(53)
t=1
Using the above notations, have Equation (51) rewritten
Ea,- [R(K) 2
2AV1 n(d 1) Eg,
ΣΣ |E|m j=1
Ni.
(54)
To use the standard Pinsker's inequality, we need (0) to be bounded almost surely which doesn't hold (for example, in poorly designed or trivial algorithms) similar to the single agent SSP [14, 7]. Hence, we use the capping trick introduced by [7] and also used by [14]. In this trick, we cap the learning process predetermined T.
For any E [r]]. we define the following:
N = Σ 165 + g).
(55)
and for any E [n]] and j E [d - 1],
T
N (0) = Σ
1(s g} 1 1ssgn(at,) + sgn(Os;))
(56)
Thus,
N max N
(57)
denotes the truncated length over the K episodes.
If the learning process (i.e. 1 episode) ends before this T, the agents are taken to continue to remain in the goal state g. In this case, the summations for the actual process and the capped process are the same. On the other hand, when K episodes end beyond T. we have possibly truncated sum. Due to the neg-tiiay of indicator functions, the summations for the capped process lower bounds the actual sum.
26

---

For any i E [n), we observe that (since any component of action, which is either +1 or -1, has to match corresponding sign of 0 or (5) for any j E [d 1].
N = No. (0) + NN, (8)
(58)
where for every 0 0.00 E o for j E [d 1] represents the vector that only differs from 0 only the jth index of every in 0 (01, 1, 02 1, ..... On 1). where each 0g mld- mld-1j> mid-1]
Note that since any component can take only one of the two values m(d-1)) 1) m(d-1) the differing components are exactly negative of each other. Thus, we can further lower bound Equation (54) as:
24V n(d 1)
E [
Σ iE(m] j=1
(O)
(59)
Notice that for any j E (d
11.0 + map is bijective. This allows us to write the following
2A
2
EA [R(K]]
2
Ba. [NT,, (0)) + Eos IN (00)
(60)
n(d
AEB
BE8
sE/n]
2AV
d-1
E (N, (0) [NN, N., [0)]
(61)
n(d 1)
DEG j=1
2AVT
ΣΣΣ BEB iE j=1
Ea [N.] Eo (NT, (0) EØs [0]]
(62)
n(d -1
The Equation (61) follows from Equation (58) and noticing that Vi 1-pi. only depends on
(n, 6, A) i.e., the same for all 0 E θ in this analysis. Also, Equation (62) is due to the fact that for any j E [d [d-1], IJ. for any function f-),, we have Eoee f(0') Loge f()). To deal with the first
expectation in the above equation we use the following lemma (proof Appendix C.7)
Lemma 6. For any instance (n, 8, A, 0), algorithm n, and T 2 2K we have Eg [N,] 2 KV for any i [n].
For the remaining terms, we use Lemma E.3 from [14] which is a standard result using Pinskers' inequality. We re-iterate the lemma here.
Lemma E.3 in [14]. If f ST [0, DJ then, Er, (f(s)) - Er, (f(s)) S DV
log(2)
(T.(PP|
2
Using Lemma 6 and Lemma E.3 from [14] in Equation (62), we obtain
2 Σ Ro,- (R(K)] 800
2AV'
ΣΣΣ
KV (T (VV//4-(T//og)//22 (P. iE
(63)
rld 1)
where PT and Pg. are the distributions over T-length state sample paths generated due to the interaction between π and the transition kernels IG and Pa respectively. Next, to bound the KL-divergence term appearing in Equation (63), have the following lemma (proof in Appendix C.8)
Lemma 7. For any instance (n,, 5, A. 0) and algorithm ग. for any j E [d - 1]. we have,
KL P PT
I 33.22 2
Eg,[[N-] [N
(64)
5(d 1)2
Using above, we get the following
2 Σ Eg. [R(K)
2AV*
ΣΣΣ
KV /4
T
3.22n
A
Eg [N-]
n(d - 1)
/2
8(d 1)2
BEE
sE[n j=1
(65)
27

---

2 ΣEΣ n(d 1)
2
KV1/4-(TV33
vō(d 1) V
Ea IN
11
BED se|n| j=1
(66)
2AV1 nld 1)
KV (TV3/2 2
.TT]
(67)
Vō(d
1EA sE|n| 1=1
2
ΣΣΣ DEM
KV -V7/44(2KV)))) 3/2 Vo 1)
2
(68)
n(d 1)
where in the last second step we used the fact that - < 'I' and in the last step, we use T 2KV1. Further, notice that the term inside the bracket is independent of f, and j. Thus, we have
2".A
Σ ES [R(K]] 2 AVT |0] O
KVi (2KV)) 3/2 3322
(69)
vo(d 1)
Rearranging and using the fact that v3 < 2 we get
1
AKVT A (KV)))8 2
B [R(K)] 2 VT
(70)
Vold - 1)
AEO
Now choosing
(d (d-1)v8
A
(71)
2n+5 VKV*'
we have that
1
(d (d-1)V8
KV
(KV 2n42
(d - 1)V8
2
Be.- [R(K)] 2 Vi*
2 VKV
4
vo(d-1)
2n+5 KK
AE
(72)
(d - 1) 2n+7
KVV (d -
1) K V
VI
(73)
2n+8
1) Vo. VKV
(74)
2
d V0 VKV
(75)
2n+9
d Vo V KB*/n
(76)
2
where in the last second line, any natural number d 2 2 which holds for our instances. The final step follows from the result V > B* /n (details in Appendix C.I Since the average over entire set is lower bounded by the RHS, there must exist some parameter in the set for which the RHS is definitely a valid lower bound.
that Vi 1 and in the last line, use d - 1 2 d/2 for
Now, what remains to check is that the A chosen above is valid. Hence, we need to ensure that
(d 1)V8
1 28
<2
(77)
2 VVV
1 + n2
Thus, we need
(d - 1)3.0 8
K
(78)
1-28 2. I+n+nz
210 Vi'
The condition in the theorem ensures the above because Vi* >> B" /n
K n (d - 1)2 8
(d - 1)2 6
(79)
210 B
1-26 1+n+n=
210 Vi
1-25 1+a+n
So the lower bound valid and it gives a bound on the number of episodes as well. This completes the proof.
28

---

C Proof of Intermediate Lemmas
C.1 Proof of Lemma
Lemma 1. For any instance (n, 6, A, 0), features defined in Equations (3) and (4) yield valid transition probabilities, i.e.,
1. We have, (o(s'(s, a), 0) 2 O' (s, (s,,,s"), and E a). = AL (s,a) E S x A. 2. For any as,a)= S A. if transition some s' S is impossible, we have (ø(s' (s a), 0: on the other hand, if the transition is certain, then (o(s')ssa),.
Proof. For any instance (n, 8, A.,), f), we prove the lemma through partitions of the set of all global transitions (s, a') E x A S.
Fix any action a E A. We consider various transitions and argue that the analysis below for this fixed action holds for any action.
When =
All the agents are at the goal node. Using the features, we have, for s' (this corresponds to third case in Equation (3)),
P(ggg gig.a a) (o(glg,a)00) = ((0nd-1, 1), (01, 1,..,,..,00 0n, 1))
(80)
Again, using the features, for any s' + g (this corresponds to the second case in Equation (3)), we have,
P(s'lg. gig. a) = (ø(s'lg, (iss'ggaa.. a)
(Ond, (01, 1,...,,... Gn. 1))
0
(81)
Thus, for the fixed a, for any s' E S, from above Equations (81) and (80), have (ó(s' gg, a), 2 0.
Also using Equations (81) and (80) we have
(0(s'lg. a), = a) Σ
Σ (la"'g.a),,) = =100= s'ES((g
(82)
E'ES
Hence, the first part of the lemma proved for this case.
Now, recall from the construction of instances as given in Section 3.1, the impossible transitions in this case from g to any s' and the only certain transition is from g g. Hence, Equations (80) and (81) ensure that the second part of the lemma is also satisfied for this case.
When gg
These represent the most general transitions. For any such s, let I (ú ....... in be the set of be the set of all agents that are at
all agents that are at node s in state s. Let J node y in state s. We partition the state space here based on
Consider the set all states in S which at least one the agents in J is not at node g. We represent this set S(s). Recall that these are the states not reachable from While all the other states that are reachable from s are denoted by S(s).
Using the features, for any s' E S(s) (this corresponds to the second part of the second case in Equation (3)), we have
P(('(ss,) (((ss(ssa))
(Ondi (0,, 1, ..., On. 1))
= 0
(83)
29

---

These are the only impossible transitions and there's no certain transition for s. Thus second part of the lemma holds.
For any s' E (s), we derive the expression of transition probability in closed form in Appendix C.2. Here, we will just show that second condition of the lemma is also satisfied.
From Equation (83) we have
P(s'ss.a)=
Σ
a(s'ss,a + Σ
a(s'ss,a)=
Σ P(s'|s,a)
(84)
N'ES
3'E((s)
s'ES(s)
r'S(()
Using Assumption and features Equation (3), we have
Σ IP (s.)
Σ (1bs'' s, (0,, 1..., 0n, 1))
(85)
ESE((s
rES())
Σ
(,)(())...........)..).....)).)) 8n); (al........ an)); (01, 1,..,,............ 1....,00.. 1)) (86)
S'E(())
Σ ((01(s)
si, sn an)) I... On. 1))
(87)
('S(()
Σ S'ES(s) 1=1
Σ (6.(s) | s1 a.), (0,,
(88)
In the above, Equation (86) is obtained by explicitly expanding the joint state, action, and next- state tuples into their individual components. In Equation (87) we further break down the joint feature vector into concatenation of per-agent feature vectors (s(s} | 8; a;) according to features corresponding to first case in Equation (3). Finally, in Equation (88) we use linearity of the inner product.
In the next step, we split the summation into two disjoint sets of agents, based on the nodes they are currently located at. This helps us exploit the properties of nested sums for further simplification.
Σ PPs' s,a) s'ES(s)
Σ ((E
Σ
( st, ai), (0t, 1))
(89)
Σ
Σ iET
(ol 8/, (1,0,), 1)) + Σ (og az)) 1))
(90)
5')(())
JEJ
Σ
Σ
(0i( 8i, ai) (0s, 1)) + Σ Σ
(55(0s)) (5, (0,, (91)
iEZ (x)(ss
JEJ sE(()))
Σ
Σ
(di(s) | st, (0,,
iET
Σ JEJ
Σ
(o,ss)) 84, az), (0), 1)) S,
(92)
LESS
where in the Equation (92) we fully unroll the nested sum, making it explicit that we are summing over the Cartesian product of each agent's next state space (S) = {s. gf if I and S {g} i E J). It emphasizes that even though the local inner product depends only on particular agent fixed in the outer sum, it is repeated across all combinations of other agents' next states.
Since for any j E J, we have s/ = g. the transition is certain. Moreover, [Z| r, and also note that for each fixed i E I, the term (o(s/ | 8;, a;), (0,, 1)) does not depend on the values of other agents' next states in Similarly, for each the next states of any agents in Z. This allows us to factor out these terms from the inner sums. We now refine the expression from Equation (92) by leveraging this structure as follows:
J, the corresponding inner product term is independent of
Σ IPs' 8,4)= Σ (2 3'E
Σ (0() 8i, as), (0., 1))} + Σ {2" (o(s)) | 185,4,), (O,, 1))}
SEI
JEJ
(93)
30

---

Now, substituting the feature representations defined in Equation (4), we have
Σ
P(s'
s,a) =
Σ
2-
((06-1, n. n.2 (0,,
x'ES())
EE
+
Σ
2"
(106-1; n2 2 00;
1
JEJ
+
T1
12
IEZ
JEJ
T
T2
Now, what remains is to verify that all remaining individual transition probabilities are all non-negative ie., for all E S(s), we have
P'(s s.a) O. Recall for any of our instance, n 2 1, (2/5, 1/2), A < Itatnz and 0 E Ô. Suppose is of type r E [n]] For any r' E [r] U (0). we analyze the non-negativity the transition probability as follows.
(94)
For any s' (s), we let T {1, 12,...,, b- C I represent the of agents that transit from node 8 to node g during the global transition s to s'. Those who continue to stay at node constitute the set I TT' First, observe that
2 2- (1 26)
2-n
A
(95)
1 1 n + n12
where the second inequality holds because 1 - 25 < 25 for E (2/5, and 1 + + n² 2 3 for all 1.
Next, using r S n, we get
5
8 8>3.2"14 A > 3.2 A
3A > 0. 2-
(96)
Observe that the above inequality is equivalent to
(-0.5m)(1 -25) + 0.5n n 2r-1
3A 0,
(97)
Moreover, since 0 S r' and S n, and 8 E (2/5, 1/2), it follows that -0.5r 2 -0.5n, and hence
(r' - 0.5r) - 25) + 0.5n
3A 0.
(98)
-1
Expanding and rearranging, we have
((1 28) + r(8 0.5) 0.5n
3A >
(99)
n 2r
Since r' Sr S n, we note that A 2r') 2
A. Hence, we have
r + (r 25
n ー r
2" (r-2r)) - 24 > 0.
(100)
n n 21
Now, note that each indicator
1 (ssgn(ai.p)
# sgnn( (0.,))) takes values in 0, 1, so
Σ
(asgn(at.)) # sgn(Or,p))
Σ
1 (sgn(aa (t,p)) # sgn(Or,p)) 2 -(r r')
(101)
SEZNT
TET
2 -T
(102)
2 n
(103)
31

---

I be the set of agents transiting from node to node g in Using above results (Equations (100) and (103)) and the expression for general transition probability (from Lemma 2) we obtain
P(s'(s,a)
r' + (r 2r')6
T1 -
A (r 2r')
(r-2r')
2
2
20
Σ
1 (sggn(at,)) + sgn(Or,p) Σ IET
(s.g((r.)))) * sgn(Or,p)
n(d - 1) p=1 LiEZNT'
(104)
O.
(105)
This shows that the constructed probability remains strictly positive for all feasible transitions. Thus, all transition probabilities P(s' ssa)) are non-negative under the proposed construction. Thus the first condition is also satisfied.
This completes the proof that the transition model and proposed feature design defines a valid probability distribution on any instance as defined in Section 3.1.
C.2 Proof of Lemma
Lemma 2. For given state S \g, let I denote the set of agents at node Consider transition
so E S(s) under joint action a E A. Let T S I be the set of agents moving from s to g. Define [7. r' I TI and T' N \ T. Then, under our proposed feature construction and Assumption I on the instances, we have
P(s'(s,a) r' + (r 2r'
A (r -2rr) n
n 2
n.
2"
d-1
2A
Σ iEInT'
1 {sgn((aip) & sgn(Or.p) - Σ 1 {sgn(ar.p) & sgn(Or.p)) IET
(ld 1) p=1
Proof. Consider any state s E \ {g} such that the agents in I := fir .2.....;7! are at node
and the remaining agents in J == {11, J2, Jn-r) are already at the node g. For any next state s' E Sss), let T = {41, 22....,4--1 the next state. Others in I that stay at node 8 form the set I T'. Then, s E S, and E S,,, where 2 2 r' 2 0 and n 2 1.
From Assumption 1, the transition probability given by F(s'|s.a) a) = (ō(s'(s, (s,a), (cb ((51, .e..., (s1, (3....,,)),, (a), a2,..., (2,)).,,,)),, 02, 1,..,,0,0..
(106)
On, 1))
(107)
(0i(s) (0:. 1)) + EEINT
Σ
(o g. 0. (0,,
Σ TET
(dela 18, 1,,)), (0), 1)),
JET
(108)
where the last inequality follows by decomposing the agents across sets I n ITT J, and T.
Now, using the feature definition from Equation (4), we compute the transition probability as follows:
P(s'
Σ
ajj
1 1- 5 (0 1)
2r
+ Σ
(
(44-1. n 2
(0).1)
(109)
IE
JEJ
8
+ Σ
at n. 21
(0.,, 1)
IET
Σ
1-6
+ ( (-a,, 04)
Σ
1
+
Σ
(ac, B2) +
(110)
n 2n
n- 2
2r
IEZNTT
JEJ
LET
1-6
8
=y.
a; 0.)
(r r²)
(ae, 0t) (111)
n 2
n
2
iEINT?
TET
32

---

1' + (r- -2r
(-ai, 0z)
(or, 0z)
(112)
n. 2-221
n.
iEZNT
LET
r' + +r (r--22 -2r")8
n2 -
Di. Oi. +
Dt Or.
(113)
n. 22-2-1
Y1 2.
IEINI p=1
LET p=1
r' + (r (r--2-10 2r')8
---r
2r
2"
Σ
d-1
A
=SS(((a)))==gn(t.n))))) 1 1ssgn(ar.)) + sgn(0t,p))
n(d - 1)
EENN p=1
d-1
A
ΣΣ n(dd p=1
((sgn(arp)) sgn(Or.p)) 1 (sgn((rr,) & sgn(Or,))3)) (114)
1)
where in Equation (111) we use the cardinality of sets I ZNT', IT and I. Equation (114) follows from the fact that for any i E [n], a, (-1,1)d-1, and 0, E m(d-I]) m(d-I) Taking the summation over p inside,
d-1
-A
a) r' + (r-r2r'0'
n. 2"
2"
Σ iETNT
A
{ 1d-1-2 2
Σ
d-1
1 (fsgn(ar,) (at.)) + sgn((r.p) }
n(d - 1)
p=1
d-1
A
d 1 2
Σ
(sgn((r).) & sgn(0r.p)3
(115)
n(d 1)
p=1
+' + (r 26
--
+ 12
n. 2"
n(d 1) {r'(d-1) 1) Σ Σ
A
1 (sgn(ar.p) # sgn(Bip))}
iEINT
+
A
{
(r-r') (d (d- - (sgn(ar..) # sgn(Or.p)3
(116)
nld 11)
1ET p=1
r' + (r (r- -2r')8
n1
n. 21
n. 2"
d-1
+ a(d - 1) {(r 2r') (d-
A
- -d-1)) nld -))
24
Σ Σ
1 (sgn((ar.p) + sgn((i.p))
iEZNT' p=1
2A
(sgn((rr,)) * (gn())p)))
(117)
n(d 1)
LET p=1
1' + (r- (0--2"1) 25')0 )0
n (r 27')
n. 2-
n. 2"
2A
Σ
(sgn((i.p) + (gn(Oi.)))
1sssnn(arp)) # sgn(Or.p))
(ld
IEINT
(118)
where Equation (116) is obtained by using the cardinality of the set I T'. Finally, we simplify Equation (117) to obtain the final expression given in Equation (118). This completes the proof.
33

---

C.3 Proof of Corollary 1
Corollary Following Lemma 2, if each agent i E N selects its action according to Qi.j sgn(0r,) 4 j E [d - 11, the resulting transition probability is independent of and T, and it only depends on and r'. We denote the corresponding global action by ag and resulting transition probabilities by pr.
Proof.
Putting ag. all indicators in the final equation from Lemma 2 proof vanish leaving probability only function of r and r' for given instance.
P(s||s,a))
r' + +r 2r')0
n
A pr.
(r 22')
(119)
n 2-
n 2
n
C.4 Proof of Lemma 3
Lemma For every [n 11, the following holds: (a) for r'
1.......1111 we have
("))) < Prr and for r' E +[ + .,..., , r, we have (*t P (r)
Proof. Consider any E [n - 1]
Part (a) For any r' E (0, 1 For our instances, we have
1)
1- 28
28
(120)
2 + + +
2n (1 + + (5
Rearranging the above terms, we have
( n²
26
+ n m++1
<
(121)
8
2
1>> p² 8
Since < r S n, follows that
+ n
+
+ + and therefore
8
1 26
A 8
+r++1
(122)
2
Moreover, using the fact that
r+1 2r+1
2 2n
for our range of r. we obtain
A
2 +r ++-+11 1) < <(++1) 1). 1 28
(123)
n
21
Rewriting the left-hand side, we get
2
A
1- 28
+ (r (1+1) 1)
< (r + 1).
(124)
8
n
n1 2
Next, we use the inequality r'(r 2r')= s / which holds for all 0
S
r'
< ++
to deduce
0.5 0.5
A
(r 2r') + (r 1)
< 0.
(125)
n. 2r
Now, since 0
[
r+1 J. we have that
2r' - (1+1)
< 0.
(126)
2
Also, since 0 O''''r Srr n, and 8 E (2/5, 1/2), we have that
0.5m + (1 - 2r) - 0.5r) > 0.5m + (1 26)(-0)5r)
(127)
> 0.5m + (1 - 28)(-0)5m)
(128)
34

---

= n 0 0.
(129)
Using Equations (125), (126) and (129), we have
2r (r + (r' - 0.5r) 25) + 0.5n
A rr + -+(r++)))(++))
8 0.5
< 0.
2
2
2
(130)
After appropriate rearrangement of terms in Equation (130), obtain
11 ( (r' (r'+ (r + 1 2r')6
A
+
(r
(1+1-2r')
+
n.22
212
(r+1-r))
(r 22
n2 -
+
A
(r- (r-r))
(r
(131)
n 2"-21
n.2"
The above inequality is equivalent to
+ 1 - pf Pr+1.r < Pr.
(132)
which in turn implies
(++1) r'
P < (+) Pr.r"
(133)
where used the expression of transition probabilities P,+1, and pr, from Lemma 2. This completes the proof of part (a). We now proceed to the second case, where > |.
Part (b): Now consider the case where r 2 r' the parameters satisfy
r+
Again, recall that for any of our instances,
1 2 (n2 + 2n2 + n + 1)' with 12/5,
35
(134)
The inequality follows because ó (2/5, 1/2) and hence we have 1 -22 < 30 Now, using the above inequality, we have as n 2 1 that
0.5 8
(n² + n + 1)
n 28 0.5
+
(135)
28 - 0.5
Rearranging the above terms we have
2nd 0.5n + - 0.5 A (n² + 1).
(136)
Using the fact that n² + n + 1 n n 2 r + 1 for r S get
0.5n n + 2nó 0.5 0.5 > (r² - 1).2
(137)
Rearranging the terms, have
(-n 015) 25) + 0.5n > A (p2 (r--++1) 1). 2" > A -r+1.2
(138)
Again using r, we get
(-r 0.5) 26) + 0.5n
(1² - --1)
(139)
n-
Further since 2 r' > r+1
we have pr' - 22 >
- Using this along with d E (2/5, 1/2)
we get
(r' - 015) 220) + 0.5n
A
(1 2f > 0
(140)
2"
n
Therefore
(r' - 0.5r) - -26) + 0.5m
(1-25 20
+ (1 (1
0.5(r
> 0 (141)
n 2"
2"
35

---

Simplifying this further, we get (r' - 0.5r) 26) + 0.5n
A (r 2r') (r + 1)
( n
10-0.5 0.5 2"
A
(142)
2
n
n
Noting that r' > |'21] implies
2r' (r+-()+1) 2 1/2. Hence, from the above inequality we get
2
2r'- (r +++1) (r' 0.5r) 26) + 0.5n
A
0 (6-02
0.5
A
(r(r-22r) (r+
+
>
2
71 2n
7
2
n
(143)
Simplifying this further, we have
(1+ (r' 0.5r)( - 26) + 0.5m)
0 0.5
1) A
+ +1
+
+
(r
+
(r 2r')
n n.2"
n1 2
n
> (r+1-r") ( (r'- ( 0.5r) 26) + 0.5m
A
+ (r 1 r))
)
[r
2r')
(144)
2-2r-1
The above can be further simplified as
11 (r' 0.5r)( 28) + 8- 0.5 + 0.5m
A
(r + 1 1-22")
+
n222
n1
> (++1-r)) (('' 0.5r) ((''-0.5r)(11 - 28) + 0.5m
-
A
(r 2n'))
(145)
n 222-1
n
Therefore, we finally have
(r+ ( (r+ 20")6
n-r-1 +
+ -
(r (r+ + (12--)r))
n.
122+1
> (r+1-r)-
r'+ (r 2r')8
n-r + - (r (r-)"))
(146)
2r
n-
The above inequality is equivalent to
r+1
Po+tir > Prss:
(147)
r+ 1 rd
which in turn implics
(*+1) Pitt, >
(r) Pr.e.
(148)
where used the transition probabilities P1+1,' and pr,y from Lemma 2. This completes the proof.
C.5 Proof of Lemma 4
Lemma 4. Letr E In - 1]. Suppose that for every 1' E (0, we have (*+) Pitt, < (2) and for every r' E f1rt1] l....,r,. r), we have )P (2) Further, if
> " >.......
V > Ve 0, then V V
Proof.
Using the lemma hypothesis for every r' E {0, 1, I, there exist constants 8p, > 0 such
that
r +
(3)
(5)
Der 8ry's V r' E f0. 1,
r r+1] 13. and (149)
Pr+1.
r'
(r+1 1 )iew
rl 1o
1
Pew + Spors V v {(
r+
+ 1,..... r 1.r).
(150)
2
36

---

Recall that from any state of type + 1, there are (c*') reachable states of type r' for r' e {0, 1, 1.....,+
r + 13. Suppose ag is the action taken in this state, the sum of transition probabilities over
the above mentioned states must add up to 1. Thus,
Pi+
(151)
r'
r+1
(*++)
Piito + (r+1) 1)
1r
1 P7+1,411
(152)
rl
r=1 J+1
(H)rr
(c)) (e))+ttbrr))) +
(r+1)
Pr.y Sau-drrr
6ryrr)
+ Σ
r (r+1)
Pi+1.+t1
(153)
J+1
( Pii
(r+1) Bege
Pri
Ps+1r+1
Pr
r r+}
+1 |+1
~= |+1
(154)
This implies
(w) (pr)
DDir
Po+1,4+1
8 Sype
Sppr' +1 1
(155)
J+1
0Srish
(156)
++1
where, the last equation follows because Eosr's (r),, = 1. This can be interpreted as the sum of transition probabilities over all possible next states from a state of type r under action ag.
Next, recall that V22 is given by
(7) (1)
V
1+ Σ -=
Pfr V
(157)
Using this we have that
r+1
V2+1 1 +
+
D
(158)
rd
r==0
(r+1
(r+1)
1 V++++ +
Pr
Pr
V2
(159)
rd
r'
+1
((")
= =1+p' Pr V+++ +
Σ
Pr |
)nyr) - V/3
r==0
(()
Piar + )om) ) vi
+
(160)
1-1
1 + + Vi+1+ + Σ
Py V
8rgn V +
Sp Vi
(161)
r0=0
r J+1
[+1
V + V.*
Σ
6y
V +
Σ
8p Vi
(162)
r=00
r= ++1
J+1
37

---

> Pitt.t1V + +V²
8n V 1411
Oy V
(163)
15 ++
P=0
M= +1
- V Vp-
Örg
V Vitli
(164)
= |+1
= -Pit1r+1 V + V 1 14 > -1++1++1 V++1 V P++1,++V V
(165)
(166)
where in (162), we the definition of V. from the Equation (157). (165) follows from Equation (156). (163) and (166) we utilize the monotonicity assumption V with respect to r.
Thus, combining above with the fact that for our instances for any E [n- - 1] and 1r-1, 1, we have that
V P Pr+1 V + V2" Pr+1,++1 V2
(167)
This implies that
(1 - 1 > 0
Vi+1 V
(168)
This completes the proof.
O
C.6 Proof of Lemma 5
Lemma 5, For any of our instances, V ( A Er (P(s"|s,a) (('s'ss""') 2
E
Proof. For the statement trivially holds. For any E S, for any E [n] and any A, have,
Σ (P((''ss.a) P(s'sss (v)
Σ
Σ
PPs' s,a)saaaaa))) P(s (' (\)
(169)
The above follows as there is only one state of type 0 i.e., g and V*(g) = Also, all the other states reachable from (apart from itself) lie in (s)) For other states that are not reachable, the probability is O.
Using the transition probability obtained in Lemma 2 (along with the notation I, T that varies with individual transitions) and Theorem 1, the above can be further written as
Σ TP(5'ls
(170)
Σ
24 nld
Σ
Σ iEZnT
(ssgn(ar.) # sgn(Or.p))
(1
Σ Hsgn((rr,) & sgn((en))) v (171) TET
2A
Σ
V Σ
Σ
Σ
1(sgn(ar,p) # sgn (0.p)
n(d - 1)
1=1
(s) iiinT
(sgn((rt.)) sgn(Or.p))
(172)
In the inner difference of summation of indicators, for any fixed p E [d 1] we observe that for any agent i [r]] the indicator has positive coefficient if the agent stays at node itself, whereas it has
38

---

negative sign if the agent transits to node g. Hence, we write the following along with swapping the summations:
Eir(''s ()) - P(s")s,a') s'
(173)
2A
Σ Σ
[1(4] =} - - = g}]
(sgn(aa))))))) & sgn(O
n(d - 1)
p=l
iEI (1)
(174)
2A
(sgn(aa.)) + sgn(Oip)}
Σ
(1{54 - 8f 116 - 9}) (175)
n(d -1
p=1
iEz
s'ES,1(8)
24
d-1
((-
p' )
Σ
(sgg((r.p)) + sgn(Orp))
(176)
n(d - 11
p=1
FE
The final steps follows from calculating how many states of type r' that are reachable from s are possible with the particular agent at node node in the next state. Simplifying this further, we have that
Σ x'
Usssssss a))saa))))))_) - ((s'|ss ss, "ls.aa")) (5)
(177)
24
2r' -r
1 (sgg((ar.)) & sgn(0r,p))
(178)
n(d - 1) y==l
r
p=1 IEI
24
d-1
2r' r V
[lsgn(ar.p) + sgn(Br.p)
(179)
1) p=1==1 i=1
where, the second equation follows by re-arranging the order of summations. Now, using the fact that for any function ʃ. >ae(m)] f(a)= = 1 [/ ((a) + Lae(m| s'm + - a)]. we have
Σ (s) - P(s''s s a VV (s') x'
(180)
24
[(sgn(ar.)) + (gn(D:.p)
(181)
nld
2r
(1)
2(r - r') - ( rr
r r- --r) [-)
Vi
+ V
2
rl)
pupp
(182)
d-1
V 27' - r (r)
2r
1 (sgn(ai..)) F sgn(Oi.p))
V
nld 1) p=1 ==1
r'
pmpp'
(183)
d-1 æ
2r r
(sgn(as.p) * sgn(Or.p))
Σ (V V:rp))
(184)
nid
r
2 O.
(185)
where the last step holds because V 2 Vi when r' 2 r/2 and vice-versa due to third claim in Theorem 1. This completes the proof.
C.7 Proof of Lemma 6
Lemma 6. For any instance (n, 5, A, 0), algorithm n, and T 2 2KV1, we have Ea,, KV for any i [n).
39

---

Proof. Recall the capped process for any agent from Theorem 2 proof. If capped process for agent i [n] finishes before T. then N, N, Else, number of visits to node g for that agent less than K due to which N, 2 T K. Therefore, we have for any E [n]]
K
Bg. [N 2 [ K, N.J E0, Σ
min (
(186)
In the above, is the random variable representing the number of time steps in episode & that the agent i stayed at node s when the global policy being followed was и. Since T 2 2K V/', and Vi 2 1, we have T/ K - 1 Vi". Using this, from Equation (186), observe that the statement of lemma holds for any algorithm æ for any agent i, 1.k 2 Vi" with probability at least 1 1/4. So,
suffices to prove that for any म, the probability that N 2 V/2" is at least 1/4.
Firstly, we note from the proof of Theorem that V n-1+2(6+4) > 2 since
2n
2(6 + A)
(187)
2n
2n
- 1
2(0 + 2 " '+n-n" n
(188)
2n
2n
2 + 1-26
n1 -
(189)
2n
2n
[1+46)
(190)
2n
2n
1/2
(191)
Above, the first inequality arises because A < 1-28
I+n+x= for our instances, the second inequality holds because n 2 and the final step is due to < 1/2.
Next, we state the following lemma whose proof is available in Appendix C.9.
Lemma 8. Take any agent E [m] currently at node 8. Then under any global action a E A, the probability that agent i stays in node 8 in the next step is lower bounded by 1/2. Formally, if is such that s; s, then Expg P[s'|s, [s,a] a) >> 1/2 for any E A.
Now, we observe that, we can express PIN,, 2 2] PH((s 82 ,,,..,, || VVLE [[>]]], st [init]] i.e., starting at initial state, the probability of observing a [x] length sequence with agent always at node s. Let the set of all states s with 9, be S(i). We further evaluate the LHS below
E
Pls
[01]
(192)
(0l (
Σ
Pis s 1-111
P(s
[=] s(i) | {s', .....,. [m] ((1)
|=]
(193)
Σ
Pls ....., s [11- P[|sa] s()) s s(i)
(194)
(8) (8) (11-SSSS(
Σ
P !| 111 (1/2)
(195)
(196)
2 F(s E S(1) (1/2) [=] > (1/2)*
(197)
Thus, we obtain, P[N 2 2x > (1/2)*. Further, we use 1 > 2n
61A
př,1 pi,o 1/V; obtain,
a
P[N 2 x|
> (1 - 1/V1)²
(198)
40

---

Putting = V/2 and using that V/r > 2, PIN 2 Vr] > 1/4, noting that for any a 2 2, we have 1 1/4.
C.8 Proof of Lemma
Lemma 7. For any instance (n, 6, A, 0) and algorithm for any j [d 1}. we have,
KL ( P
3. 2
Eg [N
(64)
3(d 1)2
Proof. We let the 1-length tuple consisting of the sequence of states from first 8th time step be denoted by 8, E Sxt, i.e., times cross product of state space. Recall that s represents the state at time t.
By chain rule of KL divergence for any O, and j [d - 1].
T- 1
KL((PaIPT.)
KL. KL (s ++
|5 |. (s [s:)]
(199)
where,
KL [ |5:
|PP) (s:+)
P. (s + (5.)
= Σ P (S:)
Σ
1o (s (5c) In
(200)
P (s++1 (s.)
SeSX
st+lES
p. (s = s5t)
Σ (S.).
(g = s: In
(201)
P (st+1 s' s/15e)
F'ES
P (5)-))))
(s = s.a" als:-1)
SES
5 11, 5, a² = a) pa (s++1 = s 5/ = 8, a'
p (s
Σ P = S 8 = s. aa) In EES
(202)
In the above, we just use the laws conditional divergences and conditional probabilities. Notice that in the above, for any fixed (s, as, the inner summation (last line) is itself KL-divergenee for fixed parameters from outer summations. We will simplify this inner KL term now.
PT (s t+1 s' 15, ssa' a)
PTstt = -s = =saa' aa) In
P7 (st+1 = 5t,5 = =s =a
ES
P (s*+++1 = s'1s² = =s,a" a) Po (sl+1 = s'(s' = -s a)
Σ (g = s'1s" ssa a) In s'ES
(203)
where the above equation holds due to Markovian Transitions. We'll upper bound the inner KL for any (s,a) A.
For any probability distributions A, B, due to non-negativity of KL(.II-), we have (L(AI|B < KT((A) KT.(BI|A) Thus,
Po (s = s'1s" = =, a)
Σ ( =s'ss" =saa' aa) In
(st+1 s'1st = s, a' = a)
N'ES
p (s++1 = s'|s¹ 8,
S
P (stt1 = s'1ss ssa' = -l
Irt (s++1 = s'|s" = a = a)
3'ES
Tor (s = 5'1s" = =sa"
+
px (s1+1 s'|s² s, a' a) In
(204)
py (s++1 = s'(s' s. a. =
S'
41

---

Σ
Po (s =s'ss" =,a' =a) -P (s"
ss =s =a]
Py (s s'1ss = "s a)
x In
(205)
80 (s = -s|s" = 8, = a)
= Σ
1 (s(tt) = ss'ss' = s. = a) po: +1 = 8 8'1s" = s, = a)]
S'ES
po (s = 801 st = s, a' = a) - po (sl+1 = 5 = =sa' a)
x In 1+
(206)
p (s s'1st s, a)
Since In(1 + 2) < x for any x E R, from above, we have:
po (sl+1 = s'1s" = s,a = a)
pg (s = s'ss* = s,a' =a)
Pr. (st+1 = s'1ss s, a' a)
S'ES
Po (s s'1st s s, =a) py (s 8 | s.a' = =a]
(207)
pe (st+1 = ss = =saa = a)
YES
max a. ((0('') 1s, a), 00,,0-003 01))
2A
2
/
2 ming,yy 0: (sr+1 = 5/1s² = ssa' = a) S 2n
A
d -
2n-1
(208)
In the last step, we upper bound every term in the summation by taking the maximum for the numerator and minimum for the denominator. The 2n appears due to there being maximum of 2" such terms for any s E S. Hence, the 2 appears. Note that the difference 0 0-0' is nd- dimensional and has non-zero components only at (j+ (i-d)) )th index and are equal to 2 0.,, where {0, 1, 1,...,.... n 1). The inner throughout or mdd-1)- Either
product maximizes when each component produces either 2A
mid-1
way, the maximum that the numerator can be is { can verify from general transition probability equation in Lemma 2 that it would be minimum when s' = = Smit and a = ag-
2
[d-1]
For the minimum of the denominator, one
Since 2/5 8 < 1/2 and A 2 2-
"itn+ we have A 2-
1-28
25 Thus
.3.
(s = =s'ss' = =saa' = a)
Σ
(s ++ = s'(ss" =s =a) In
Pr. B:
(st+1 s''ss" =saa' aa
E'ES
412
28
2"
(209)
(d - 1)
3 2-
A
3. 22n
(210)
old - 1)2
Hence, from Equations (203) and (210) we have
(s ++1 = 5 1,, = 5, = a)
Fo ( = 5' 5115 = =saa' = =a) In
ps (s(+1 = 5 1, = =s,a² = a)
SE
p (st+1 = 5'1s² a'
PJ (6 = s'1ss s,a' =a) In
p (sl+1 8' 8'15² = s, a = a)
SEES
(211)
A
3. 2.
(212)
5(d 1)2
Further, note that we must consider only those cases where s' f g since otherwise s*+1 with probability 1 for both instances @ and Hi and corresponding In terms are all O. Using this and Equation (212) in Equation (202)
KLIPT (s (+1
1 P (s (s2+1
[B:)
(5
Σ
P = s,a' = aa a/(,.1)
R-1ESKI
SEA
42

---

Pg (5
= 8 St-1..5 = s,a" a
Σ po (s =s'ss;-1,s² ssa' =a) -In
(213)
Pi (sl+1 =s 1 5, a
A
Σ
PD (S
P8 = s, a - -))
(214)
8(d 1)2
- 1-1-
xES,aE
A 2
P # g)
3
2
(215)
5(d
1)2
Using above result in Equation (199), we have
KL Pg
KL KL (s (s
1P 80 (s
[s:)]
(216)
3. 2
( +g)
(217)
8(d 1)²
A
22n
(s (s' # g)
(218)
8(d
1)2
2
22
Eg [N]]
(219)
3(d - 1)2
where, the final step follows from the definition of N- This completes the proof.
C.9 Proof of Lemma
Lemma 8. Take any agent E [n] currently at node Then under any global action E A, the probability that agent i stays in node in the next step is lower bounded by 1/2. Formally, if is such that 8; = 8, then Ex Pis'ls, a) >> 1/2 for any a E A.
Proof. Similar Equation (90), for any E [m]. and such that s; s, then for any A we have
Pi's s,a)
(220)
y' VESWI==S
Σ
Σ VEI
(01 | s/ si,aa)) (0,, + Σ
(5) sy, (0,,1))
(221)
jEJ
Σ
((aa n 2 (0; +
1-8
Σ
(0.(1) s a;,a;), 1)) + n2
(222)
n 2"
1 1-8
Σ
02, 0:) +
Σ
( 8i, as), (b,, 1)) + n. 2"
(223)
n1 2
iEZ(()
2" (107, 0;) +
1 2
(r - 1)
Σ
(0r(s) st, a.) (0,, 1)) + -
12 72-8 r
n
2
- 2"
{)())
(224)
1
2r-1
72 - r +
2" 2" (--07 0:)
+
(r
1)
(225)
2
n1 (2r-1)
1)
2n
2" a-a 0:) +
1-8
n
(226)
2n
In Equation (222), we use the features from Equations (3) and (4). In the next step, simplify the dot product. To obtain Equation (224), observe that there are 2n-1 next states in which agent i
43

---

stays at node s. To simplify the middle summation, we observe that for any agent E I (d), it will appear in half of the next states of interest in node and half times in node g. In of the steps, we only rearrange terms and simplify.
Note that the ahove probability is minimized when optimal action a" is taken, and hence (-a, A Thus,
P(s' ssa)
2
Σ
Pis'
|s,a")
(227)
A
1
1
n1
2
(228)
2n
A +
-
8
72 1
2
(229)
11
2n
1 + 20
6 - 68
3n 3
(230)
6n
6n
6n
3n + 2 46
(231)
6n
1/2
(232)
In the above, we use our restriction on A and
C.10 Proof of Corollary 2
Corollary 2. For any non-goal state s E Sr of type r, the self-transition probability under action a is
a( = r(1 8)
+
n-r
24
ΣΣ
d-1
1 {sgn((rr.) & sgn(Or,)))
(16)
n. 2
n n. 2
n
nld
VEI p=1
This is minimized when a = ag and the resulting probability only depends on r.
Proof. Putting r' in the equation from Lemma and using
T gives the desired expression:
a) r(1 ((1-)) 8)
2A
Σ
Σ 1 (sgn(ar.))) + sgn(O:,p)) (233)
- n.."
((d
PE[d- IET
Fixing any E S' {g), fixes the first terms. Only the summation over indicators varies for various actions Since the indicator function can least be 0, the minimum probability for the above transition for any s E S is achieved when for each agent E I. the signs of each component of its action a, matches with respective components of 0,. This definitely happens ag.
C.11 Proof for V B*
By standard evaluation argument,
r-1
===1+pp; -r V2"
Σ
Pr.p Pi Vi
(234)
p=
< <1 <1+p Pf, V2 -P.r
(235)
1
+ V - Vi_ <
(236)
1 1- ph.r
Thus,
V - V カ-1 < 1
(237)
Pinn
V V n- <
V
(238)
Ph-1In-11
44

---

2
VT
(239)
22.2
1
VT Vo
(240)
PÍ
Adding the above inequalities,
V VO
72
VV = B
(241)
P
Pi.1
i=1
The second inequality above is due to př, being the maximum over all p.g (Using the Equation in Corollary 2, it's easy to show that p7,r decreases with r for our instances). Observe that the final equality in Equation (241) holds for 1.
45


Reviews:
[{"review_id": "pvyQY1I6uA", "reviewer": "Reviewer_Z1Bz", "summary": "This paper characterizes the theoretical lower bound on the regret of the decentralized stochastic shortest path learning problem, which is a crucial problem in path planning. The authors consider decentralized learning in multi-agent state and action spaces. There are three major contributions: (1) designing a class of hard-to-learn MASSP problems and theoretical characterization of the optimal policy and value functions; (2) leveraging that class of problems, a tight lower bound is proposed; (3) Some technical intermediate results on the exponential state-action space would be valuable for future MASSP studies. Overall, the paper appears to be the first work to propose tight lower bounds for MASSP problems, and therefore is a valuable contribution to the field.", "questions": "This work considers multi-agent cases, so would the derived lower bound recover existing lower bound results for the single-agent shortest path problem? If so, I believe the constructed hard-to-learn example will also have an impact on the single-agent case. \n\nThe constructed lower bound relies on the strong assumption that the optimal policy can be easily found. However, for the general case where the optimal policy is hard to find, would the lower bound still be tight? \n\nThe constructed lower bound in Theorem 2 depends on B^*, but the reported lower bound of this work in Table 1 has no dependency on B^*. Why is B^* missing in the last line of Table 1? \n\nWhat is the technical challenge when extending the proposed technique to random policies? \n\nThe constructed regret lower bound seems to rely on the assumption that the value function can be estimated accurately. In practice, it may not be the case. So, how does the value function approximation error affect the regret? \n\nIn many theoretical RL papers, we assume all states and actions should have some probability mass in the transition dynamics to avoid the poor exploration issue. Do we need similar assumptions in this work? I believe so, because otherwise the denominator in equation (15) can be zero when we have deterministic transition dynamics.", "limitations": "Yes, the authors provide some discussion about the limitations, such as only considering linear feature spaces instead of nonlinear feature spaces. However, the reviewer believes that there are two additional limitations to the current manuscript. Having some discussion about them will significantly improve the impact of this work.\n\nNo experiment comparing the actual computation time of different algorithms for solving those hard-to-learn examples. The result would be more convincing if a plot could be provided for visualizing that the lower bound regret is indeed tight and valid, compared to the existing algorithms’ regrets. \n\nIn many real-world planning problems, we need to consider road capacity and other types of constraints. The current formulation has no practical constraints. So, looking ahead, a natural question is how constraint satisfaction affects the computational lower bound? Some discussion on this in future work would be exciting and make the work more impactful for real-world constraint-aware shortest-path problems.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \nThe high-level two-step strategy of proving the theoretical lower-bound result is technically sound and original. \n\nThe constructed worst-case MDP is interesting. It can motivate more research on characterizing which class of linear MDP would have an even tighter lower bound than the one proposed in this paper, and therefore can be an impactful contribution for helping the readers understand the interplay between linear MDP structure and computational complexity of learning the optimal policy. \n\nThe linear MDP approach generalizes prior works on tabular MDP, with compact and efficient feature representation. \n\nThe four technical challenges of the multi-agent shortest path problem are clearly discussed on page 2. The paper employs various strategies to address these challenges.\n\n\nWeaknesses: \nAssumption 1 can be made more informative. In general, the theoretical lower bound of computational complexity relies on the specific information provided for the algorithm. However, the current version of Assumption 1 only specifies the linear MDP setup. A more informative assumption should also include information on how decentralized learning is implemented. What information can different agents share while learning? \n\nSome technical details are unclear. For example, this paper motivates the problem by discussing the shortest path over a graph, which typically includes a set of nodes and a set of edges; however, the paper only introduces the node set. Moreover, it is unclear whether the paper considers a discrete or continuous state space. In other words, do we allow state or action to only take discrete values, or can they take continuous values? \n\nThere is a concern that some technical proofs may have a logic gap, and therefore, it questions the quality and credibility of the proofs. In the equation (45) of Lemma 5’s proof in the supplementary material, why can we aggressively take the sum of h from h = 1 to h = infinity? \nThis part seems not very clearly explained, and it may be a bold step. Technically, I’m not sure whether it’s correct. \n\nThere appears to be no discussion about how frequently the constructed MDP would be encountered in practical applications. If it never happens, then the impact of those constructed examples is low. \n\nThe technical details are hard to follow, and limited intuition is shared behind the derivation of proofs. So, it is hard to fully justify the technical correctness of the proposed idea. For example, it would greatly improve the readability if the authors could explain how the binomial coefficients help construct the lower bound. \n\nMany typos. For example, line 28, “recent works has”; line 252, “its desirable to”; line 320, “upto”, etc.", "was_revised": true, "final_justification": "I appreciate the reviewer’s detailed follow-up discussion. I agree with the authors that empirically comparing an algorithm’s actual computational complexity to its theoretical lower bound can be challenging. Nevertheless, if space permits in the camera-ready version, I recommend including a discussion of these challenges and possibly noting this as an avenue for future work. A clear gap between empirical performance and the theoretical lower bound would call into question the theoretical claim that “the derived regret bound is tight.” More broadly, I believe empirical validation of theoretical bounds is valuable, as it provides a practical check on the reasonableness of the assumptions underlying the analysis. Such validation ultimately brings theoretical work closer to practical problems and increases its potential impact on actual algorithm design. Given the explanation and the challenges described by the authors, I am raising my score to borderline accept.", "rebuttal": "*We sincerely thank the reviewer for their thoughtful comments and valuable feedback on our submission. We provide clarifications below on the questions raised.*\n\n**Single agent case:**  Yes, our lower bound results and hard-instance construction readily recover the single-agent case studied by Min et al. (2022). While this connection is noted in lines 272–273, it was not made explicit. We will clarify it in the final version and provide the relevant details.\n\n**Role of optimal policy:** The lower bound does not depend on the ability to find the optimal policy. It reflects the fundamental learning hardness in LM-MASSP setting which we show by constructing the hard-to-learn instances based on proposed feature design (Equations 3 and 4). We show that for any algorithm, there exists a hard-to-learn instance for which the regret is at least the stated bound (the bound need not hold for all the instances). So, we do not make any assumption on how easily the optimal policy can be found. Thus, our lower bounds remain tight irrespective of the whether the optimal policy is hard to find or not. \n\n**Absence of $B^*$ in Table 1:** We appreciate this observation. Table 1 highlights the leading-order dependence on the number of episodes $K$, which is the primary focus in characterizing regret scaling. Constants and instance-dependent terms such as $n,d$, and  $B^*$ are omitted for clarity, but they do appear explicitly in the formal statements (e.g., Theorem 2). We will consider including them in the table in final version.\n\n**Randomized policies:** Extending our results to randomized policies is a valuable direction and aligns with standard theoretical frameworks. As noted in lines 181–182, such an extension is conceptually straightforward and primarily introduces notational overhead. \n\nFor example, in the deterministic case, expressions like $\\pi(s^t)$ (e.g., in Equation 219) directly specify the action taken in state $s^t$. Thus, $\\mathbb{P}(g|s,\\pi(s^t))$ is well-defined. In the randomized setting, we instead would need to define\n\n$$\n\\mathbb{P}(g|s, \\pi(s^t)) = \\sum_{a\\in\\mathcal{A}} \\mathbb{P}(g|s, a) \\cdot \\pi(s^t,a),\n$$\nwhere $\\pi(s^t,a)$ denotes the probability of selecting action $a$ in state $s^t$ as specified by the randomized algorithm.\n\nMoreover, by Yao’s minimax principle (Cohen et. al. (2020)), the expected regret of the best randomized algorithm on the worst-case instance is lower bounded by that of the best deterministic algorithm on a randomized instance. Hence, our lower bound results naturally extend to randomized policies as well.\n\n**Role of value function approximation:** Our lower bound analysis does not rely on value function approximation. Instead, we construct hard instances within the LM-MASSP class that yield tight regret lower bounds without explicit approximation. Key to our approach is the monotonicity of the optimal value function with respect to the number of agents at the initial state (Theorem 1) which allows us to bypass approximation entirely. In settings where such structure is absent, approximation errors may become significant and impact regret. Analyzing how these errors scale with the number of episodes is an important direction for future work.\n\n**Equation (15):** Our feature design ensures that the denominator in Equation (15) will not be zero, since for $r=1$ we have $\\mathbb{P}(s|s,a) \\neq 1$. Thus, the associated transition probabilities are strictly between 0 and 1, ensuring the expression is well-defined.\n\n**Regarding exploration assumptions:** These are indeed important when designing algorithms and analyzing their upper bounds. However, our focus is on lower bounds, where we construct hard instances to show that, for any algorithm regardless of its level of exploration (e.g. greedy to fully exploratory), the regret lower bound still holds. As a result, we do not require exploration assumption.\n\nNext, we address the **weaknesses and limitations** raised in the review.\n\n**Assumption 1 and information sharing:** We intentionally avoid assuming a specific communication structure to ensure broad applicability. As a result, our lower bounds hold across fully decentralized, partially connected, and centralized settings, capturing fundamental performance limits. Exploring how different communication levels affect instance hardness or refine the bounds (beyond the $K$ dependence) is a promising direction for future work.\n\n**Discrete state and action space:** We clarify in Section 2.1 (lines 121–129) that both state and action spaces are discrete and finite, and our analysis is based entirely on this setting. Extending the results to continuous spaces is an interesting future direction.\n\n**Equation (44):** We thank the reviewer for their time and for carefully examining the technical details. We would be happy to discuss any concerns regarding the correctness of the proofs in greater depth.  Specifically we respond to the concerns about the missing details between Equation (44) and (45) in Appendix B. First note that Equation (44) is not the part of Lemma 5, rather it is part of the proof of Theorem 2. Recall that\n\n$\\mathbb{E}_{\\theta,\\pi} [R_1]$ \n\n$= V^{\\pi}(\\textbf{s}^1) - V^{\\pi^*_{\\theta}} (\\textbf{s}^1) $\n\n$\\geq \\mathbb{E}_{\\textbf{a}^1 \\sim \\pi(\\textbf{s}^1), \\textbf{s}^2 \\sim \\mathbb{P}(.|\\textbf{s}^1,\\textbf{a}^1)} [ V^{\\pi}(\\textbf{s}^2) - V^*(\\textbf{s}^2) ]$ \n\n$\\quad +\\mathbb{E}_{\\textbf{a}^1 \\sim \\pi(\\textbf{s}^1)} [ \\frac{2 \\Delta}{n(d-1)}$\n\n$\\quad \\times \\sum_{i=1}^n \\sum_{p=1}^{d-1} \\mathbb{1}[\\{\\textbf{s}^1 \\neq \\text{goal}\\} ] \\mathbb{1} [\\{sgn(a_{i,p}^1) \\neq sgn(\\theta_{i,p})\\}] V^*(\\textbf{s}^1) ]$. \n\nThis introduces a recursive structure in the regret: the difference at time 1 is written in terms of the same difference at time 2 plus another term that depends on $s^1$.  Although $\\textbf{s}^1$ is deterministic, $\\textbf{s}^2$ is stochastic due to transitions under $\\pi$ and $P_{\\theta}$. Fixing a sample path of length $H$ (i.e., goal is reached at step $H$), and unrolling the recursion across all steps, we obtain\n\n$V^{\\pi}(\\textbf{s}^1) - V^{\\pi^*_{\\theta}}(\\textbf{s}^1)$\n \n$\\geq E_{1} (\\sum_{h=1}^H \\frac{2\\Delta}{n(d-1)} \\times \\sum_{i=1}^n \\sum_{p=1}^{d-1} \\mathbb{1} (\\{\\textbf{s}^h \\neq \\text{goal} \\} ) \\mathbb{1} (\\{sgn(a^h_{i,p}) \\neq sgn(\\theta_{i,p})\\}) V^*(\\textbf{s}^h) $,\n\nwhere the expectation is over all sample paths in episode 1.\n\nNow observe that, as per our model, once an agent reaches the goal node, it remains there for the rest of the episode. This allows us to safely extend the summation to infinity without altering its value. For all $h>H$, the state is specified (by convention) to be goal for that episode i.e., $s^{h,k} = goal$, making the indicator term $\\mathbb{1} (\\{\\textbf{s}^h \\neq \\text{goal} \\})  = 0$. Specifically, we apply the following identity:\n\n$\\mathbb{E} \\left[ \\sum_{t=1}^{\\tau} x_t \\right] =  \\mathbb{E} \\left[  \\sum_{t=1}^{\\infty} x_t \\mathbb{1}(\\{t\\leq \\tau \\}) \\right] = \\sum_{t=1}^{\\infty} \\mathbb{E} \\left[  x_t \\mathbb{1}(\\{t\\leq \\tau \\}) \\right]$\n\nwhere $\\tau$ and $x_t$ are random variables. Using this we get\n \n$V^{\\pi}(\\textbf{s}^1) - V^{\\pi^*_{\\theta}}(\\textbf{s}^1)$\n\n$\\geq E_{1} (\\sum_{h=1}^{\\infty} \\frac{2\\Delta}{n(d-1)} \\sum_{i=1}^n \\sum_{p=1}^{d-1} \\mathbb{1} (\\{\\textbf{s}^h \\neq \\text{goal} \\}) \\mathbb{1} (\\{sgn(a^h_{i,p}) \\neq sgn(\\theta_{i,p})\\})  V^*(\\textbf{s}^h))$\n\nNow using V^* $(s^h) \\geq V^*_1$ we get Equation (45).\n\n**Occurance of the instances:** \nThank you for raising this important point. Our goal is to establish fundamental lower bounds by constructing hard-to-learn instances that illustrate worst-case limitations in MASSP problems. These instances are not meant to reflect typical real-world MDPs but to capture theoretical hardness, as is standard in prior work (e.g., Min et al., 2022; Trivedi & Hemachandra, 2023). Exploring how such hard instances or their variants manifest in practical settings is indeed a valuable future direction.\n\n**Binomial coefficients:** While the binomial coefficients were not explicitly introduced, they arise naturally from the combinatorial structure of the two-node instance. For example, in Lemma 3, they quantify the number of ways in which r+1-r' out of r+1 agents move from the initial node to the goal node. Importantly, Lemma 3 is a key technical insight that underpins our proof strategy. It plays a central role in establishing Lemma 4 (supporting the monotonicity claim in Theorem 1) and Lemma 8 (see page 46), which is used to prove Lemma 6 and ultimately Theorem 2.\n\n**Typos:** Thank you for pointing these. We will take care of these and others, if any. \n\n**Lower Bound Visualization:** The lower bounds are existential in nature, i.e., they assert that no algorithm can perform better than a certain regret scaling in the worst case. Unlike upper bounds, they do not correspond to a specific algorithm or instance. In our setting, identifying the hard instance (among the exponentially many possibilities) for any fixed algorithm is itself non-trivial. Simulating or plotting regret curves against the lower bound would require checking all $2^{n(d-1)}$ instances, which is computationally infeasible. Moreover, lower bounds are not algorithm-specific; they hold universally across all possible algorithms. Even in classical single-agent SSP settings, despite the availability of many algorithms such plots are not shown, for the same reason.\n\n**Future work on constraint aware SSP:** We agree that this is a valuable and interesting future direction, and we will include a brief discussion on it in the final version under future work.\n\n*We hope these clarifications address the reviewer’s concerns. We would be grateful if the reviewer could consider increasing their score in light of these clarifications and the contributions of our work. We would also be happy to engage in further discussion during the  reviewer-author discussion period to clarify any additional questions or suggestions.*"}, {"review_id": "xZN23yHvk7", "reviewer": "Reviewer_jnXP", "summary": "This paper studies the fundamental learning limits in decentralized multi-agent stochastic shortest path (Dec-MASSP) problems with linear function approximation—a setting relevant to areas like swarm robotics and traffic routing, but still theoretically underexplored. While single-agent SSPs have been well explored in the existing literature, extending regret bounds to decentralized multi-agent cases poses major challenges due to exponential state-action spaces and coupled dynamics.\n\nTo this end, the paper establishes the first ever regret lower bound for Dec-MASSPs, proving a bound of Ω(√K) over K episodes. This matches known upper bounds and recovers the single-agent case when the number of agents is one, providing a tight characterization of the problem's learning complexity. Their analysis is based on a technically novel construction of hard-to-learn problem instances with linearly parameterized dynamics and costs.\n\nTo overcome key technical barriers, the paper designs feature representations that yield valid transitions, simplify value function analysis using state partitioning and monotonicity, and bound KL divergence via symmetry in agent distributions. These techniques enable valid analysis despite the exponential state space. Overall, the paper closes a critical gap in theory and offers a foundation for evaluating and designing scalable learning algorithms in decentralized multi-agent systems.", "questions": "1. The setting is fully decentralized learning without communication. I wonder how limited communication might affect the regret bounds and instance hardness? Or am I missing something here?\n\n\n2. Just curious but I wonder what might happen if we allow some model misspecification? The model assumes exact linear approximation. How sensitive are the lower bounds or constructions to small model misspecifications?", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n**Quality**\n\n1. Technically rigorous: The paper presents a careful and comprehensive construction of hard instances for Dec-MASSP, supported by well-structured theoretical arguments and inductive proofs.\n\n2. Tight lower bound: The regret lower bound matches the known upper bounds up to poly-log factors, demonstrating tightness and validating the authors' analytical framework.\n\n3. The authors skillfully handle several complex issues — exponential state space, coupled agent dynamics, and KL divergence — using symmetry and feature design to make the analysis doable.\n\n**Clarity**\n\n1. Well-motivated research topic: The paper clearly identifies the knowledge gap in decentralized SSPs with function approximation and motivates the need for lower bounds.\n\n2. Each section is logically laid out, with clear transitions from the problem setup to methodology, theory, and discussion.\nNotions like state-type partitions, the monotonicity of value functions, and symmetry-based analysis are introduced and explained in a way that highlights their intuitive appeal and theoretical usefulness.\n\n3. A very clear proof sketch: This is a hard paper. But the proof sketch makes it easier for the readers to follow. The proof sketches are clear, well-motivated, and the full proofs (relegated to appendices) build on and extend techniques from prior work thoughtfully.\n\n\n**Significance**\n\nI think this paper fills in an important gap in the research direction of SSP and multi-agent RL.\n\n1. This is the first known regret lower bound in the decentralized SSP setting with linear function approximation, establishing a benchmark for future algorithms in this research area. The paper recovers the classical single-agent bounds as a special case, and thus provides a generalization of prior SSP results to the decentralized setting.\n\n2. Importantly, the paper provides a critical insight for understanding the complexity of decentralized MARL. Specifically, the paper reveals that increasing the number of agents increases the density of near-optimal policies, making learning fundamentally harder.\n\n\n**Originality**\n\n1. The hard instances are new and cleverly designed to yield analytical tractability despite exponential state-action space.\n\n2. Novel technique challenges: The use of symmetry to simplify the KL divergence analysis and characterize optimal actions is a clever extension of classical information-theoretic techniques to a more complex setting.\n\n3. First result in the field: The tight lower bound for any number of agents in Dec-MASSP with linear approximation is a good contribution in MARL theory.\n\n\n**Weaknesses (Minor and Contextual)**\n\nI do not detect any major technical weakness in the paper. Following are just some minor comments.\n\n**Quality**\n\nAs a purely theoretical work, the use of very specialized assumptions (e.g., uniform cost, linear transition features, parameter restrictions on $\\delta$) may limit the practicability of the lower bounds beyond the theory.\n\n**Significance**\n\nThe impact is currently limited to linear function approximation. While the paper acknowledges this, broader significance will depend on whether similar bounds can be extended to more general function classes (e.g., neural networks).\n\n**Overall**, I deem this as a high-quality and technically sound contribution that meaningfully contributes to our understanding of decentralized stochastic shortest path. Its careful lower bound construction and insights into the hardness of multi-agent learning problems position it as a strong candidate for acceptance, particularly in theory-focused tracks or venues.", "was_revised": true, "final_justification": "I thank the authors for their response to my questions.\nOverall, I think this is a very good paper. \nI definitely vote for an accept.", "rebuttal": "*We thank Reviewer for their detailed and constructive feedback. We greatly appreciate the positive assessment and the high confidence in our work. Your thoughtful comments have helped us improve both the clarity and completeness of the paper. Below, we respond to each of your points.*\n\n**Limited communication:** Thank you for the thoughtful question. We intentionally do not assume any specific communication structure among agents in order to keep our results general. As such, the lower bounds we derive are valid under any communication among agents, including fully decentralized, partially connected, or even centralized settings. This generality allows our results to serve as fundamental performance limits across a broad range of scenarios. That said, studying how different levels of communication might affect instance hardness or improve lower bounds (in factors other than $K$) is indeed a compelling  future direction, and we appreciate the suggestion.\n\n**Model misspecification:** Thank you for the insightful question. Our work, like prior literature Min et. al. (2022), Zhang et. al. (2018) assumes exact linear function approximation (LFA) and focuses on the LM-MASSP setting. The impact of model misspecification is largely unexplored in this context. While we cannot currently comment on the tightness of our bounds under misspecification, it is a promising future direction. Notably, the existing upper bounds also assume exact LFA and would require similar re-evaluation.\n\n*We hope that our clarifications and improvements adequately address your concerns. We would be happy to further engage during the author–reviewer discussion phase to elaborate on any remaining issues. Given the significance of the contributions and the enhancements made in response to your feedback, we kindly ask you to consider increasing your score if you feel it is appropriate.*"}, {"review_id": "WlqkSZEVXp", "reviewer": "Reviewer_YLTg", "summary": "The paper examines a regret lower bound for a class of multi-agent stochastic shortest path problems. The general model assumes that $n$ agents are either in the starting or the goal state, and a linearly defined transition function stochastically allows this transition based on an action which is a binary vector of dimensionality $d$ over $\\{-1,1\\}$. This implies that the optimal policy is given by letting each agent select the action minimizing the likelihood of staying in the starting state. Though the cost is uniform for each action, the transition function is dependent on how many agents are still in the starting state. \nThe authors prove two main theorems for their setting: The first basically shows that the optimal policy should constantly select the action for each agent which is maximizing the likelihood of transitioning to the goal. Furthermore, due to the homogenous and independent behaviour of agents, states having the same number of agents positioned on the starting state share the same values. Furthermore, as agents may eventually transit to the goal, the cumulated expected future cost decreases.\nIn the second theorem, the authors compute a lower bound for the expected regret based on this optimal behaviour.", "questions": "Q1. Your main claim seems to be Theorem 2, presenting the lower bound. What are the assumptions on the algorithm $\\pi$ that is lower bounded? There are some hints in the proofs, but even from the sketch in Section 5, it remains unclear why the algorithm cannot estimate the transition likelihood of actions any quicker.\n\nQ2. To what extent are LM-MASSP problems indicative of general MASSP problems as defined in the related work? \n\nQ3. Could your results easily be extended to a larger number of nodes beyond start and goal?", "limitations": "The authors describe the main assumptions of their model and stress that the linear transition function is a limiting factor.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper examines whether, in decentralized multi-agent stochastic shortest path problems with linear cost and transition functions, the already proposed methods might already have an optimal complexity. This is interesting as it answers the question of how well-known algorithms are performing compared to optimal policies and if further research in this direction is required.\nThe idea of finding instances of this problem setting where the optimal policy can be derived and then showing that no algorithm can achieve faster convergence towards the optimal policy also seems feasible.\n\nA drawback of the paper is that it rarely tries to give any intuition behind the assumptions, the design of the problem, or even about the assumption on the actual algorithms, which are lower bounded in the end. Thus, trying to get behind the setting requires a lot of time, and it feels that the authors could have made it far easier for the reader to get an understanding of what is proposed in the paper. \n\nAnother drawback of the paper is that the contribution feels somewhat limited as the setting is rather specific. Thus, it is unclear why the proposed setting is indicative of the broader settings from the related work.\nThough the authors define a problem that allows deriving a lower bound, the authors do not advertise the practical relevance of the setting. Also, it is not clear to what extent the results are transferable to a larger set of MASSP problems. Thus, the results may not be interesting to the broader machine learning community.\n\nTo conclude, the paper examines a very complicated setting from a theoretical point of view by finding and analyzing an instance that allows tractable results. Concerns are that the paper is hard to follow due to a lack of providing intuitions and that the assumptions required to derive  the results are too restrictive to raise attention in the broader machine learning community.", "was_revised": true, "final_justification": "The authors adequately addressed my concerns in their rebuttal. Thus, I raised my score and recommend accepting this paper.", "rebuttal": "*We sincerely thank the reviewer for their thoughtful comments and feedback. We are encouraged by their engagement with our work and provide clarifications below to address the points raised.*\n\n**Q1: Assumptions on algorithm $\\pi$:** Thank you for the question. Our goal is to characterize the fundamental limits of LM-MASSPs, and as such, we make no assumptions on the algorithm. Our lower bound is universal in the sense that it applies to any algorithm, including those that estimate transition dynamics. Theorem 2 is proven using information-theoretic techniques to show that no algorithm can reliably distinguish between carefully constructed, hard-to-learn instances better than $O(\\sqrt{K})$ in number of episodes. We elaborate on this intuition in the paragraph titled \"Why do we expect tight lower bounds for these instances?\" on page 6. We also emphasize that our only structural assumption is the linear function approximation. No additional assumptions about the learning algorithm are required for the lower bound to hold.\n\n**Q2: LM-MASSP vs. MASSP:** We focus on LM-MASSP to stay consistent with prior work on regret upper bounds, which also assumes linear function approximation (Trivedi and Hemachandra 2023). LM-MASSP are representative of MASSP as far as linear function approximations are concerned. To emphasize this linear function approximation assumption and its role we explicitly refer to the setting as LM-MASSP.\n\n**Q3: Extension to three or more nodes:** We construct hard-to-learn instances using a two-node setup and establish valid regret lower bounds. Despite the minimal structure, the state space grows exponentially with the number of agents, making the problem highly non-trivial. A key contribution of our work is demonstrating that this simple setup suffices to capture the core difficulty of decentralized learning and to derive tight lower bounds. \nWhile we focus on two nodes for clarity and tractability, we do not rule out the possibility of extending the construction to three or more nodes. Such extensions would introduce additional technical challenges, particularly in identifying suitable hard instances and characterizing the optimal policy and value function while preserving the lower bound structure. We expect the regret lower bound to scale similarly with $K$, with possible changes only to constant factors. We leave this as a promising direction for future work.\n\nWe will now address the points raised in the **Strengths And Weaknesses** section of the review. \n\n**Intuition/restrictiveness of assumption:** We emphasize that the *only* assumption made throughout our work is the linear function approximation of the transition dynamics, a standard and widely adopted assumption in both single-agent and multi-agent RL literature (e.g., Min et al., (2022); Zhang et al., (2018)). \n\nThroughout the paper, we provide supporting intuition and background to motivate our approach. For instance, in constructing hard-to-learn instances and establishing the tightness of the regret lower bound, we highlight that these instances are designed to admit exponentially many near-optimal policies which are indistinguishable making the learning fundamentally hard and leading to $O(\\sqrt{K})$ regret scaling (see lines 238–246). Additionally, we outline the key proof steps with underlying intuition, which resulted in the technical lemmas. We will expand on these aspects further in the final version.\n\n**Contributions of the paper:** We provided an itemized summary of our contributions on page 2. To reiterate, our key contributions include: (i) identifying a suitable class of hard-to-learn instances, (ii) carefully designing the feature representations, (iii) uncovering structural properties of the optimal value function, and (iv) rigorously proving the regret lower bounds. Each of these steps involved substantial technical challenges, which we addressed in detail. We hope the reviewer recognizes the depth and significance of our contributions. \n\n**Practical relevance of the setting:** The Stochastic Shortest Path (SSP) problem is a foundational and widely applicable model in the MDP literature. As noted in Neuro-Dynamic Programming (Bertsekas & Tsitsiklis, 1996), many MDPs can be cast as SSP problems. Moreover, real-world applications such as board games (e.g., Go, with random play durations) are naturally modeled as SSPs. The learning version of SSPs has received recent attention (Tarbouriech et al., 2019; Cohen et al., 2020).\n\nA more realistic extension is the multi-agent SSP (MASSP) framework, which captures practical scenarios such as multiple vehicles sharing a road network, leading to congestion effects. These settings, where independently acting agents share costs or information, introduce additional complexity. While Trivedi & Hemachandra (2023) propose an algorithm for MASSP and provide upper bounds on regret, the fundamental lower bounds remained unaddressed.\n\nOur work fills this gap by constructing a carefully designed 2-node hard-to-learn MASSP instance and establishing that no multi-agent algorithm can achieve regret better than $O(\\sqrt{K})$ under linear transition assumptions. This construction extends the 2-node hard instance used in single-agent SSP lower bounds (Min et al., 2022) to the multi-agent setting.\n\nWe believe our results offer meaningful insights into the fundamental limits of learning in MASSP under linear assumptions and may inspire future lower bound analyses in other multi-agent settings. We welcome further feedback to clarify any aspect of our contributions or their relevance.\n\n*We hope our responses adequately address your concerns and help clarify the key contributions and technical depth of our work. If you find the clarifications convincing, we kindly ask you to consider raising your score. We would also be happy to engage further during the author–reviewer discussion phase to elaborate on any remaining questions.*"}, {"review_id": "QfgopFMwRg", "reviewer": "Reviewer_MLjP", "summary": "The authors study decentralized multi-agent SSPs (Dec-MASSPs) under linear function approximation, where the transition dynamics and costs are represented using linear models.\nTheir 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.\nI find this work very interesting!", "questions": "Page 1:\nCan you please expand the discussion on SSP so that a non-expert can better relate to the problem you are studying?\n\nPage 2:\nCan you please elaborate on (iii)?\nI think that this explanation is very handwavy :)\n\nPage 3:\nCan you please elaborate on the caption of Table 1?\n\nIs there any related work from the field of computational complexity?\n\nPage 5:\nIn Equation (2), why is there a negative term?\nWhy are you subtracting $K \\cdot V^*(s_{\\rm init})$?\n\nPage 6:\nLine 238:\nThis explanation is nice but I am a bit confused.\nWhy are there exponentially many policies that differ in just two components of the global action in a single state, etc.?\n\nPage 7:\nI do not understand Equation (6).\nWhy do you need to sum over all $r$?\n\nPage 8:\nCan you please explain how use Pinsker's inequality to bound the regret?\n\nWhy is $N_{i, j}(\\theta)$ unbounded?\n\nPage 9:\nCan you please expand the future work paragraph? :)", "limitations": "None.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\nThe problem studied is central in decentralized RL.\n\nWeaknesses:\nSee Questions.", "was_revised": true, "final_justification": "The authors have effectively addressed my comments and concerns.", "rebuttal": "*We thank Reviewer for their detailed and constructive feedback. We greatly appreciate the positive assessment of our work. Your thoughtful comments have helped us improve both the clarity and completeness of the paper. Below, we respond to each of your points.*\n\n**Page 1: Discussion on SSP for non-experts:** Sure we will add some more discussion on SSP for the non-expert.\n\n**Page 2: elaboration of (iii):** Unlike the single-agent case with two nodes (Min et al. (2022)), where a closed-form expression for optimal value function can be derived exactly for the two states, extending this to the multi-agent setting is significantly more challenging due to the exponential growth of the state space. While we initially attempted to derive a closed-form expression for the optimal value function, it turned out to be complex to work with analytically. A key insight that enabled progress was partitioning the state space based on the number of agents at each node. This structure helped us establishing the  monotonicity property of the optimal value function with respect to the number of agents at node $s$. This property played a central role in our lower bound analysis and allowed us to proceed without requiring an explicit optimal value function. The details are provided in Theorem 1 and proof of Lemma 5.\n\n**Page 3: caption of Table 1** Sure, we will add more details in the table to make it self-contained. For example, we will consider including the role of $n, d$ and $B^*$ in the table in final version. We are not aware of any related work in the field of computational complexity for the MASSP settings. We would appreciate it if you could point out any aspects we may have missed in this regard.\n\n**Page 5: regret definition, equation (2):** This term arises naturally from the definition of regret in the cost setting (Bandit Algorithms. Tor Lattimore and Csaba Szepesvari). We aim to study the expected cumulative cost an algorithm incurs in excess to that of the optimal policy over $K$ episodes, and its scaling with $K$. In the regret definition (Equation 2) $V^*(s_{init})$\n\ndenotes the expected cost per episode under the optimal policy. Therefore, the total expected cost of the optimal policy over $K$ episodes is $K \\cdot V^*  (s_{init})$.\n\n**Page 6: line 238, exponentially many near-optimal policies:** We agree that this point could have been made more explicitly. Our intent was to highlight that the number of policies differing from the optimal one in the specified manner grows faster than exponentially in $n$, the number of agents. Specifically, there are $2^n - 1$ non-goal states where a policy may deviate from the optimal. In each such state, there are  $n(d-1)$ components of the global action, and a deviation at any two of these components yields a different policy of this kind. This results in $(2^n-1) \\times \\binom{n(d-1)}{2}$ such policies, which scales as $n^2 \\times 2^n$ in number of agents, $n$. Thus, the number of such policies grows super-exponentially with $n$.\n\n**Page 7: equation (6), summation over $r'$ :** Please note that the summation is over $r'$ not $r$. We recall $r$ is the number of agents at node $s$ in global state $\\textbf{\\textit{s}}$, whereas $r'$ is a running index representing the similar number for the reachable states from $s$. The summation over $r'$ is used to take care of all the possible types of next states. The goal state and the current state are explicitly included in the equation (6), while the double summation ensures that all other reachable states are also considered. Specifically, the outer summation over all $r'$ captures all other reachable state types, and for each fixed $r'$, the inner summation over all $\\textbf{\\textit{s}}' \\in \\mathcal{S}_{r'}(\\textbf{\\textit{s}})$ ensures that every state of type $r'$ that is reachable from $\\textbf{\\textit{s}}$ is also included in the summation. This structure guarantees completeness in covering all valid successor states in the transition dynamics.\n\n**Page 8: Pinsker's inequality:** Lemma E.3 (on page 25) is directly borrowed from the related work of Min et al.(2022), where it is obtained using Pinsker’s inequality. In our work, we apply Pinsker’s inequality to bound the KL divergence between probability distributions over sample paths of two closely related instances, denoted by $\\theta$ and $\\theta^j$, as defined in lines 323–324. Further details of this KL divergence and its role in the proof can be found on page 25.\n\n**Regarding unboundness of $N_{i,j}(\\theta)$:** While it is not always unbounded, we must account for the possibility of it being unbounded as shown below. In the proof of Theorem 2, we consider an arbitrary decentralized learning algorithm and it is possible that such an algorithm selects actions for which $sgn(a^t_{i,j}) \\neq sgn(\\theta_{i,j})$ for some $(i,j)$ and for all $t$ (e.g., this can occur in trivial or poorly designed algorithms). Furthermore, certain sample paths may not terminate, for instance, the trajectory  $s_{init}, s_{init}, s_{init}, ...$ which would lead to unbounded $N_{i,j}(\\theta)$. To maintain generality and correctness, we carefully consider such cases in our analysis by defining $N^-_{i,j}(\\theta)$, \n\na truncated version of $N_{i,j}(\\theta)$.\n\nWe also note that similar techniques to apply Pinsker's inequality and handling the unboundedness of the analogous quantity have been applied in the single-agent setting in Min et al. (2022).\n\n**Page 9: future work paragraph:** Sure, we will add a few more things like capacitated SSP, and multi-commodity problems which posses additional learning challenges.\n\n*We hope our responses have addressed your concerns and clarified the key contributions. We would be glad to engage further during the discussion phase if needed. Given the significance of the results and the improvements made, we would appreciate it if you could consider raising your score.*"}]

Author rebuttal:

Meta-review: This paper studies the theoretical foundations of decentralized multi-agent stochastic shortest path problems with linear function approximation. Its main contribution is a regret lower bound in this setting, established through carefully constructed hard-to-learn instances.

The strengths of the paper lie in its novelty and technical depth. Establishing a lower bound for decentralized multi-agent SSPs represents a meaningful theoretical advance for decentralized reinforcement learning. The feature design, monotonicity arguments, and treatment of exponential state-action spaces form the key technical contributions, and the work highlights the inherent difficulty of decentralized learning.

The weaknesses concern presentation, assumptions, and broader impact. Several assumptions (such as linear models and a decentralized setup without communication details) require clarification, and parts of the proofs are difficult to follow. The relevance of the constructed hard instances to real-world decentralized systems is not entirely convincing, limiting practical significance. One reviewer also noted the lack of empirical validation, such as runtime comparisons. While the rebuttal addressed some technical points (e.g., randomized policies and exploration assumptions), it did not fully resolve concerns about applicability.

Overall, the paper makes a theoretical contribution that helps characterize fundamental limits in decentralized multi-agent learning. However, it is narrowly scoped, heavily assumption-driven, and at times difficult to interpret without additional intuition. Its value lies primarily in advancing theoretical understanding rather than practical impact.
Decision: Accept (poster)