Multiagent Stochastic Shortest Path Problem

1 Introduction

Stochastic Shortest Path (SSP) is a fundamental optimization problem deeply studied in planning and control. The task is to navigate an agent to a target state in a given explicitly represented Markov decision process (MDP) at the minimum expected path length (the expected path length can also be interpreted as the expected time to reach a target). The SSP problem captures a variety of realistic scenarios, including car navigation, drone flying, game playing, etc.

In this work, we initiate the study of the Multiagent Stochastic Shortest Path (MSSP) problem, where k agents strive to reach a target so that the expected time of reaching the target by some agent is minimized. As in the classical SSP, we consider application scenarios where the MDP is known and represented explicitly (hence, there is no need to learn the MDP structure). As a simple example, consider the problem of urgent blood transport from a blood bank to a distant hospital by a car driving through a city. The current traffic density determines the probability distribution of the time required to cross individual sections of the road and can be modeled by an MDP whose size is proportional to the number of road sections. Hence, planning an optimal route for a single car is an instance of the SSP problem, and an optimal moving strategy σ can be quickly computed by existing algorithms. In order to increase the chance of timely delivery, multiple cars (from the same or different blood banks) can be dispatched simultaneously. Clearly, the aim is to minimize the expected time of the first arrival (the blood doses delivered by the cars arriving later can be stored for later use). A natural approach to solving this optimization problem is to compute the above strategy σ for each car, i.e., to solve the SSP problem independently for each car. However, this is not optimal in general, and in some cases it is even the worst possible solution. A simple illustrative example is given in Fig. 1.

More generally, MSSP models a class of time-critical delivery problems where the item can be replicated and sent across multiple paths to improve time performance and reliability. The primary research question considered in this work is "How to compute an optimal solution for a given MSSP instance?" In addition to designing efficient algorithms, we analyze the computational complexity of MSSP and determine the type of strategies required for optimal solutions.

In the above application scenario, the cars can be autonomous or coordinated by a central control room. When the agents are UAVs operating in a hostile environment, the coordination may be unachievable. Therefore, we consider the MSSP problem for both autonomous and coordinated agents.

Even if agent coordination is achievable, it can be expensive. Therefore, we also analyze the benefits of coordination for solving MSSP, i.e., the ratio between the best solutions achievable in the autonomous and coordinated settings.

Our Contribution. We start by analyzing the computational complexity of the MSSP problem and identifying the type of strategies required for optimal solutions.

For the Coordinated MSSP problem, we show that an optimal coordinated strategy for k agents in a given MDP M is computable in time polynomial in the size of M and exponential in k. For every fixed k, the problem is solvable in polynomial time, but the degree of the bounding polynomial grows linearly in k. Furthermore, an optimal strategy can be constructed so that it is memoryless (the decision depends only on the current positions of the agents) and deterministic (the choice of actions is uniquely determined in every step). We also show that the problem is PSPACE-hard, and hence the exponential blowup in k is unavoidable. More precisely, we prove it is PSPACE-hard to decide the existence of a coordinated strategy such that the expected time to reach a target by some agent is bounded by a given constant.

For the Autonomous MSSP problem, we show that an optimal autonomous strategy profile for k agents (i.e., a k-tuple of independent single-agent strategies) exists, but each agent may require memory to "remember" some information about the history of previous moves. We also prove that finite-memory randomized strategy profiles are sufficient for achieving ε-optimal solutions for an arbitrarily small ε > 0. Hence, for practical purposes, it suffices to consider only finite-memory randomized strategy profiles. Then, we show that the problem of deciding the existence of an autonomous strategy profile for k agents such that the expected time to reach a target by some agent is bounded by a given constant is NP-hard even for k = 2 and even if the class of admissible profiles is restricted to memoryless profiles. Hence, the Autonomous MSSP problem is not fixed-parameter tractable in k, and it is also conceptually harder (in particular, there is no apparent way of computing an ε-optimal profile for a given ε ≥ 0). Our algorithmic solution is based on the following:

(1) We show that for every memory size m, the problem of synthesizing the best randomized profile where every strategy in the profile uses at most m memory states is reducible to the problem of computing the best randomized memoryless profile. Hence, the algorithmic core of the problem is the synthesis of the best memoryless randomized profile (this problem is still NP-hard even for two agents, see above).

(2) In the next step, we show how to express the expected time to reach a target by some agent as a differentiable function of the parameters representing memoryless randomized profiles. This is the crucial step enabling the application of stateof-the-art techniques of differentiable programming, which is the core of our AUTOHIT algorithm. The efficiency of AUTOHIT is bought by the loss of optimality guarantees (this is unavoidable due to the NP-hardness of the problem).

In the experimental part of our paper, we evaluate our synthesis algorithms on instances of increasing size against natural baselines, and we compare the efficiency of solutions obtained in the coordinated and autonomous settings. The instances resemble city maps with a grid-like structure with random delays at certain locations. To avoid bias towards specific MDP classes, the instances are generated randomly.

RelatedWork. The SSP problemwas introduced in [Eaton and Zadeh, 1962] in the framework of pursuit-evasion games. The SSP problem is solvable efficiently by the standard MDP strategy synthesis techniques (i.e., value iteration, policy iteration, and linear programming) under some structural conditions [Puterman, 1994; Bertsekas and Tsitsiklis, 1991; de Alfaro, 1999]. The solution algorithms and their complexity depend also on the properties of the reward function (see, e.g., [Baier et al., 2018]). More recent works study SSP under some additional conditions on the probability distribution of the accumulated reward [Piribauer et al., 2022; Haase and Kiefer, 2015; Kˇret´ınsk´y and Meggendorfer, 2018; Ahmadi et al., 2021; Mannor and Tsitsiklis, 2011]. See also [Randour et al., 2015] for an overview. The SSP problem in an unknown environment has been studied in various variants, and the solution is mostly constructed by appropriate reinforcement learning techniques. A recent overview of these works is given in [Rosenberg, 2022].

Multi-agent problems related to SSP have been studied only recently. In [Nawaz and Ornik, 2023], an algorithm for minimizing the expected time of visiting all targets in a given set by a swarm of autonomous agents is proposed. A multi-agent extension of pursuit-evasion games is introduced in [Zhang et al., 2021]. The problem of minimizing the total time of reaching all targets by autonomous agents in an unknown environment is studied in [Trivedi and Hemachandra, 2023; Chavan et al., 2025]. Recent works also study multi-agent variants of infinite-horizon objectives (such as mean-payoff or steady-state objectives) in explicitly presented MDPs [Jon´aˇs et al., 2025; D´ıaz-Garc´ıa et al., 2023; Klaˇska et al., 2023]. Related objectives such as expected average reward have also been studied for decentralized POMDPs (see, e.g., [Jiang et al., 2017]). To the best of our knowledge, there are no previous works on MSSP.

2 Preliminaries

We assume familiarity with basic notions of probability theory and Markov chain theory. We use N to denote the set of all non-negative integers and N∞ to denote the set N ∪ {∞}. For a given finite or countably infinite set A, the set of all probability distributions over A is denoted by Dist(A). We say that µ ∈ Dist(A) is Dirac if µ(a) = 1 for some a ∈ A.

Markov Chains. A Markov chain is a pair C = (S,A) where S is a finite or countably infinite set of states and A : S × S → [0, 1] is a stochastic matrix such that ∑t∈S A(s, t) = 1 for every s ∈ S.

A path in C is a finite or infinite sequence of states. Infinite paths are called runs, where a run is also understood as a mapping ω : N → S. For each finite path w, we use Runw to denote the set of all runs starting with w. To every s ∈ S we associate the probability space (Runs, Fs, Probs) such that Fs is the σ-algebra generated by all Runw where w is a finite path initiated in s, and Probs is the unique probability measure satisfying Probs(Runw) = ∏n-1 i=0 A(si, si+1) for all finite paths w = s0, . . . , sn such that s0 = s.

Markov Decision Processes (MDPs). A Markov decision process (MDP) is a triple M = (S, Act, P) where S and Act are non-empty finite sets of states and actions, and P : S × Act × S → [0, 1] is a transition function. We require that, for all s ∈ S and a ∈ Act, the sum ∑t∈S P(s, a, t) is equal either to 0 or 1. In the latter case, we say that a is enabled in s. The set of all actions enabled in s is denoted by En(s). We require that En(s) ̸= ∅ for all s ∈ S. We say that t ∈ S is reachable from s ∈ S if there is a finite sequence s0, . . . , sn such that s0 = s, sn = t, and for every i < n there is ai ∈ Act such that P(si, ai, si+1) > 0.

Strategies and Strategy Profiles. Let M = (S, Act, P) be an MDP. Consider k ≥ 1 agents moving among the vertices of M by performing the actions of M. The agents are either autonomous or coordinated, i.e., each agent acts either independently or coordinates its decisions with the other agents, respectively (the coordination is usually implemented by a central controller instructing the agents).

We start by defining a coordinated strategy for k ≥ 1 agents. Let Mem be a non-empty set of memory states where some information about the history of the agents' previous moves is stored. A configuration is a tuple (s1, . . . , sk,m) where s1, . . . , sk ∈ S are the states currently visited by the agents and m ∈ Mem is the current memory state. We use Conf to denote the set of all configurations. A coordinated strategy for k ≥ 1 agents is a triple σ = (µ, next, update) where µ ∈ Mem is an initial memory state and

are functions defining the next actions taken by the agents and the associated memory update. We require that for all γ ∈ Conf and α ∈ Actk such that next(γ)(α) > 0, we have that the action αi is enabled in the underlying state si of the configuration γ for all i ∈ {1, . . . , k}.

Note that the choice of the next tuple of actions is randomized. The current memory state is updated according to the current configuration and the chosen tuple of actions. We say that σ is deterministic if next and update use only Dirac distributions. Furthermore, we say that σ is finite-memory if the underlying set Mem is finite, and memoryless if Mem is a singleton. Note that if σ is memoryless, then update is trivial and next can be seen as a function Sk → Dist(Actk ). Slightly abusing our notation, we formally define memoryless strategies as functions σ : Sk → Dist(Actk ), i.e., we avoid using the next and update functions completely.

An autonomous strategy profile for k agents is defined as a k-tuple π = (σ1, . . . , σk) where every σi is a coordinated strategy for one agent (see above). Since each σi controls only the agent i, the behaviour of each agent is completely autonomous. We use Conf i = S×Memi to denote the set of all configurations of agent i, where Memi is the set of memory states of σi. We say that π is finite-memory or memoryless if every Memi is finite or a singleton, respectively.

RandomVariableMHit. LetM = (S, Act, P) be anMDP, k ≥ 1 the number of agents, and let ιi ∈ S, Ti ⊆ S be the initial/target states of agent i for every i ∈ {1, . . . , k}.

Let σ = (µ, next, update) be a strategy for k agents, and let init = (ι1, . . . , ιk, µ) be the initial configuration. We define a Markov chain Mσ = (Conf , Aσ) where the stochastic matrix Aσ is defined as follows: for all γ, δ ∈ Conf such that γ = (s1, . . . , sk, n) and δ = (t1, . . . , tk,m), we put

Let MHit : Runinit → N∞ be a random variable over the runs in Mσ initiated in init such that MHit(ω) is either the least j ∈ N such that ω(j)i ∈ Ti for some i ∈ {1, . . . , k}, or ∞ if there is no such j. We use Eσ[MHit] to denote the expected value of MHit. Hence, if the agents are controlled by σ, the expected number of actions executed before some agent visits a target state is equal to Eσ[MHit].

Now consider an autonomous strategy profile π = (σ1, . . . , σk) for k agents. For every i ∈ {1, . . . , k}, let µi be the initial memory state of σi and initi = (ιi, µi) the initial configuration of agent i. Each σi determines a Markov chain Mσi and the probability space over Runiniti in the way described above. Let Probπ be the probability measure in the product probability space over the set Runinit1 × · · · × Runinitk of all multiruns. Slightly overloading our notation, we define a random variable MHit over the multiruns such that MHit(ω1, . . . , ωk) is either the least j ∈ N such that ωi(j) ∈ Ti ×Memi for some i ∈ {1, . . . , k}, or ∞ if there is no such j. We use Eπ[MHit] to denote the expected value of MHit. Hence, if the agents move according to the profile π, then Eπ[MHit] is the expected number of actions executed before some agent visits a target state.

Multiagent Stochastic Shortest Path (MSSP) Problem. In this work, we study the Coordinated MSSP and Autonomous MSSP problems. In both cases, a problem instance consists of

• an MDPM = (S, Act, P),
• an integer k ≥ 1 (the number of agents),
• initial/target states ιi ∈ S, Ti ⊆ S such that ιi ̸∈ Ti ̸= ∅ for every i ∈ {1, . . . , k}.

The task is to construct a coordinated strategy σ (in the case of Coordinated MSSP) or an autonomous strategy profile π (in the case of Autonomous MSSP) for k agents minimizing the expected value of MHit.

For a given ε ≥ 0, we say that σ∗ and π∗ are ε-optimal if Eσ∗[MHit] and Eπ∗[MHit] are ε-close to infσ Eσ[MHit] and infπ Eπ[MHit], where σ and π range over all coordinated strategies and autonomous strategy profiles for k agents, respectively. 0-optimal σ∗ and π∗ are called optimal.

Price of Autonomy. For every MSSP instance, the price of autonomy is defined as the ratio of infπ Eπ[MHit] to infσ Eσ[MHit]. Hence, the price of autonomy measures the benefits of coordination for a given MSSP instance, where a higher value means higher benefits.

3 The Complexity of MSSP

In this section, we analyze the computational/strategy complexity of the Coordinated and Autonomous MSSP problems.

Single-Agent Case. We begin by recalling known results about the single-agent case, i.e., the SSP problem (see, e.g., [Puterman, 1994]).

Let M = (S, Act, P) be an MDP, k = 1 the number of agents, ι ∈ S an initial state and T ⊆ S a set of target states such that ι ̸∈ T ̸= ∅. We have the following:

Figure 2: A linear program for computing an optimal strategy for a single agent.

Figure 3: A system of linear equations evaluating a given memoryless strategy σ for one agent.

• (a) There exists an optimal memoryless deterministic strategy for the agent computable in polynomial time by the LP of Fig. 2.
• (b) For a given memoryless strategy σ for one agent, we have that Eσ[MHit] is computable in polynomial time by solving the system of linear equations of Fig. 3.

More precisely, let SR be the maximal C ⊆ S satisfying the following conditions:

• if s ∈ C, then there is t ∈ T reachable from s,
• if s ∈ C ∖ T, then there is a ∈ En(s) such that t ∈ C for all t ∈ S where P (s, a, t) > 0.

Furthermore, for every s ∈ SR, we use EnR(s) to denote the set of all a ∈ En(s) such that P(s, a, t) > 0 implies t ∈ SR. If ι ̸∈ SR, then the expected time to reach a target state from the initial state is infinite for every strategy σ. Otherwise, let x∗s , s ∈ SR be the solution to the LP of Fig. 2, and let σ∗ be a memoryless deterministic strategy where σ∗ (s)(a) = 1 for an action a ∈ EnR(s) such that x∗s = 1+ ∑t∈SR P (s, a, t) · x∗t . Then σ∗ is optimal and Eσ∗ [MHit] = x∗ι .

The set Sσ used in the system of Fig. 3 is the maximal C ⊆ S such that

• if s ∈ C, then a state of T can be reached from s with positive probability in the Markov chain Mσ,
• if s ∈ C∖T, σ(s)(a)>0, and P(s, a, t)>0, then t ∈ C.

If ι ̸∈ Sσ, then Eσ[MHit] = ∞. Otherwise, Eσ[MHit] = y∗ ι , where y∗ s , s ∈ Sσ is the unique solution of the system of linear equations of Fig. 3.

Coordinated MSSP Problem. The problem of constructing an optimal coordinated strategy for k ≥ 1 agents is easily reducible to the SSP problem discussed above. For an MSSP instance M = (S, Act, P), k, ιi, Ti where i ∈ {1, . . . , k}, we construct an SSP instance consisting of an MDP M ′ = (Sk , Actk , P ′ ) where

the initial state is (ι1, . . . , ιk), and the target states are all (t1, . . . , tk) ∈ Sk such that ti ∈ Ti for some i ∈ {1, . . . , k}. There is a natural one-to-one correspondence between memoryless coordinated strategies for k agents in M and memoryless strategies for one agent inM ′ , and this correspondence preserves the expected value of MHit. Hence, an optimal coordinated strategy for k agents in M corresponds to an optimal strategy for one agent in M ′ computable by the LP of Fig. 2. Observe that the size of this LP is polynomial in the size of M and exponential in k. We obtain the following:

Theorem 1. For every MSSP instance, there exists an optimal memoryless deterministic coordinated strategy computable in time polynomial in the size of the MDPM and exponential in the number of agents k. For every fixed k, the strategy is computable in polynomial time.

In the following, the above-described algorithm for computing an optimal memoryless deterministic strategy for a given MSSP instance is referred to as COORHIT.

Now we show that the exponential blowup in k is unavoidable (assuming P ̸= PSPACE), because the Coordinated MSSP problem is PSPACE-hard. More precisely, we have the following:

Theorem 2. Let M, k, ιi, Ti where 1 ≤ i ≤ k be an MSSP instance and B a rational bound. The problem of whether there exists a coordinated strategy σ for k agents such that Eσ[MHit] ≤ B is PSPACE-hard.

A proof of Theorem 2 is non-trivial and can be found in [Jon´aˇs et al., 2026].

Autonomous MSSP Problem. We start by observing that optimal autonomous profiles exist and may require strategies with memory of arbitrarily large size.

The class of all autonomous strategy profiles is denoted by Π. Furthermore, for every n ≥ 1, we use Πn to denote the class of all profiles π = (σ1, . . . , σk) such that the underlying Memi of every σi contains at most n memory states. In particular, Π1 is the class of all memoryless profiles. Recall that π∗ is optimal if Eπ∗[MHit] = infπ∈ΠEπ[MHit]. Furthermore, we say that π∗ is Πn-optimal if π∗ ∈ Πn and Eπ∗[MHit] = infπ∈Πn Eπ[MHit]. Note that the existence of an optimal and a Πn-optimal profile is not immediately clear. It is established in the next theorem.

Theorem 3. For every MSSP instance, there exist an optimal profile and a Πn-optimal profile for every n ≥ 1.

The existence of an optimal profile is proven by repeatedly selecting converging subsequences of distributions occurring in an infinite sequence of profiles π1, π2, . . . such that limi→∞Eπi [MHit] = infπ′∈ΠEπ′ [MHit]. A similar technique is used to prove the existence of a Πn-optimal profile. The details are in [Jon´aˇs et al., 2026].

Now we show that optimal autonomous profiles may require strategies with memory of arbitrarily large size. However, for every ε > 0, there exists an ε-optimal profile with finite memory.

Theorem 4. For every n ≥ 1, there exist an instance of the Autonomous MSSP problem with two agents and a profile

π ∈ Πn+1 such that Eπ[MHit] < infπ′∈Πn Eπ′ [MHit]. Furthermore, for every instance of the Autonomous MSSP problem with k agents and every ε > 0, there exists an ε-optimal finite-memory profile.

Furthermore, in [Jon´aˇs et al., 2026] we show that randomized profiles are strictly more powerful than deterministic profiles when the agents use memory of a given size.

Now we analyze the computational complexity of Autonomous MSSP. The next theorem says that the problem of computing a profile π ∈ Πn for an MDP M minimizing Eπ[MHit] can be efficiently reduced to the problem of computing a memoryless profile ¯π minimizing E¯π[MHit] in an effectively constructible MDP ¯M.

Theorem 5. Let M = (S, Act, P) be an MDP, k ≥ 1, and Mem a set of memory states of size n ≥ 1. Then there is an MDP ¯M = (S×Mem, Act×Mem, ¯ P) such that

• for every profile π = (σ1, . . . , σk) for M where every σi is a strategy with memory Mem, there exists a memoryless profile ¯π = (¯σ1, . . . , ¯σk) for ¯M such that the Markov chains Mσi and ¯M¯σi are identical for every i ∈ {1, . . . , k},
• for every memoryless profile ¯π = (¯σ1, . . . , ¯σk) for ¯M, there exists a profile π = (σ1, . . . , σk) for M where every σi is a strategy with memory Mem such that the Markov chains ¯M¯σi and Mσi are identical for every i ∈ {1, . . . , k}.

Intuitively, the MDP ¯M is obtained from M by encoding the elements of Mem into the states of ¯M. Hence, instead of synthesizing a finite-memory profile for M, we may synthesize a memoryless profile ¯π for ¯M and then "translate" ¯π into a finite-memory profile for M so that E¯π[MHit] in ¯M is equal to Eπ[MHit] inM. In other words, the algorithmic core of the MSSP problem is the synthesis of memoryless profiles. Unfortunately, the synthesis problem is NP-hard even for two agents and memoryless profiles.

Theorem 6. Let M be an MDP and ιi, Ti where i ∈ {1, 2} initial/target states for two agents. Let B be a rational bound. The problem of whether there exists an autonomous strategy profile π for two agents such that Eπ[MHit] ≤ B is NP-hard. The problem is NP-hard even if the class of admissible profiles is restricted to memoryless profiles.

A proof is obtained by a non-trivial reduction from a variant of the Boolean satisfiability problem; see [Jon´aˇs et al., 2026]. Finally, we show that the price of autonomy can be arbitrarily large, even for two agents.

Theorem 7. For every B ∈ N, there exists an MSSP instance with two agents such that the price of autonomy is at least B.

4 Minimizing Eπ[MHit]

The results of the previous section show that the problem of computing an optimal coordinated strategy for a given MSSP instance is fixed-parameter tractable in the number of agents k. However, there is no straightforward algorithmic solution for the Autonomous MSSP. In this section, we address this challenge by designing AUTOHIT, an efficient profile synthesis algorithm for the Autonomous MSSP. We begin by summarizing the principal limitations.

Due to Theorems 4 and 5, we can safely restrict our attention to the synthesis of memoryless profiles. Since synthesizing optimal memoryless profiles is NP-hard even for two agents (see Theorem 6), it cannot be done efficiently unless P = NP. Hence, efficiency inevitably leads to losing optimality guarantees. Furthermore, the synthesis should not be limited to deterministic profiles because randomized profiles are strictly more powerful (see the remarks after Theorem 4). On the other hand, the synthesis may take advantage of the explicit MDP representation by analyzing and utilizing relevant structural properties of M. The design of AUTOHIT reflects these observations.

We start by designing an efficient evaluation procedure computing Eπ[MHit] for a given memoryless profile π. Note that a naive evaluation based on constructing a product Markov chain and solving the linear system of Fig. 3 is exponential in k. A more efficient procedure is given below.

For the rest of this section, we fix an MSSP instance consisting of an MDP M = (S, Act, P), k ≥ 1, and ιi ∈ S, Ti ⊆ S for every i ∈ {1, . . . , k}.

Evaluating Memoryless Profiles. Let π = (σ1, . . . , σk) be a memoryless profile. Recall that each σi is formally a function S → Dist(Act) and determines a Markov chain Mσi = (S,Ai). For the sake of clarity, we use Hiti to denote a random variable over the runs of Mσi such that Hiti(ω) is either the least j ∈ N such that ω(j) ∈ Ti, or ∞ if there is no such j. Since the agents are independent, we have that

For every i ∈ {1, . . . , k}, we fix a target state τi ∈ Ti and define a transition matrix ¯ Ai obtained from Ai by changing τi into a sink and modifying transitions ending in a state of Ti so that they end in τi. More precisely, we put

• ¯ Ai(s, t) = Ai(s, t) for all s, t ̸∈ Ti,
• ¯ Ai(s, τi) = ∑t∈Ti Ai(s, t) for all s ̸∈ Ti,
• ¯ Ai(s, t) = 0 for all s ̸∈ Ti and t ∈ Ti∖{τi},
• ¯ Ai(t, t) = 1, and ¯ Ai(t, s) = 0 for all t ∈ Ti and s ̸= t.

Then, for every ℓ ≥ 0, we have that Probιi [Hiti≤ℓ] = ¯ Aℓi (ιi, τi), where ¯ A0i is the identity matrix. Hence,

for all ℓ ≥ 1, and thus we obtain

Since (3) is an infinite sum, it is not algorithmically workable. Therefore, we also consider a truncated version of (3) where the range of ℓ is restricted to {1, . . . , γ} for a suitable constant γ ∈ N. Formally, we define

Note that E⟨γ⟩π[MHit] is computable in time polynomial in k, γ, and the size of M. Furthermore, we show that for every ε > 0, there is an efficiently computable γε such that Eπ[MHit] - E⟨γε⟩π[MHit] ≤ ε. Thus, the value of Eπ[MHit] can be efficiently ε-approximated by evaluating the righthand side of (4).

The constant γε is computed as follows. Recall that for every i ∈ {1, . . . , k}, the value of Eσi [Hiti] is computable in polynomial time by solving the system of linear equations of Fig. 3. For a given ϱ ∈ N, we put

Furthermore, let Xi = {1, . . . , k} ∖ {i}. Then

Note that (5) follows immediately from definitions and the fact that ¯ Aℓj (ιj, τj) ≥ ¯ Aϱj (ιj, τj) for all ℓ ≥ ϱ. Hence, γε can be set to the least ϱ such that the right-hand side of (5) is bounded by ε for some i ∈ {1, . . . , k}. Since the righthand side of (5) decreases exponentially in ϱ, the value of γε is small for most instances.

RepresentingMemoryless Profiles. Nowwe show how to represent memoryless strategies by vectors of real-valued parameters so that E⟨γ⟩π[MHit] becomes a differentiable function of these parameters.

Let i ∈ {1, . . . , k} be an agent index. For all s ∈ S and a ∈ En(s), we fix a fresh parameter (variable) Xi,s,a ranging over R. We use Pari to denote the vector of all Xi,s,a. Furthermore, for every s ∈ S, we use Pari,s to denote the vector of all Xi,s,a where a ∈ En(s).

Let SOFTMAX be the standard softmax function transforming a vector of real values into a probability distribution, i.e., a vector of the same dimension over (0, 1] whose sum is equal to one. The values of Pari represent a memoryless strategy σi such that σi(s)(a) = SOFTMAX(Pari,s)(a) for every a ∈ En(s). In other words, for every s ∈ S, the values of Pari,s are transformed into a probability distribution over En(s) using SOFTMAX. Note that σi can be seen as a function of Pari. We also use ¯ A¯ A¯ Ai and ¯ A¯ A¯ Aℓi to denote the matrices ¯ Ai and ¯ Aℓi determined by σi (see the previous paragraphs). Again, ¯ A¯ A¯ Ai and ¯ A¯ A¯ Aℓi are seen as functions of Pari. More concretely, for all s, t ∈ S, the element ¯ A¯ A¯ Aℓi (s, t) is a function of Pari involving SOFTMAX, multiplication, addition, and some constants. Note that ¯ A¯ A¯ Aℓi (s, t) is differentiable.

Let Par1, . . . , Park be parameters whose values represent a memoryless profile π = (σ1, . . . ,σk) in the way described above. We use E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] to denote the value of E⟨γ⟩π[MHit] for the profile π. Note that E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] is a differentiable function of Par1, . . . , Park.

AUTOHIT Algorithm. The AUTOHIT algorithm (Algorithm 1) is based on minimizing E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] by gradient descent from a suitable initial profile.

More precisely, AUTOHIT starts by invoking an abstract function INITPARAMS(M, k) initializing the parameters Par1, . . . , Park to values representing an initial profile π0 (line 4). In our experiments, π0 is either a random profile or a precomputed profile (in the latter case, π0 is computed by some efficient method based on analyzing the structure of M,

Algorithm 1 The AUTOHIT Synthesis Algorithm

• 1: Inputs: MDP M = (S, Act, P ), the number of agents k ≥ 1, ιi ∈ S, Ti ⊆ S for all i ∈ {1, . . . , k} 2: Outputs: A memoryless profile π for M and k agents Val such that Eπ[MHit] - ε ≤ Val ≤ Eπ[MHit] 3: Numerical hyperparameters: Steps, ε, γ 4: Par1, . . . , Park ← INITPARAMS(M, k) 5: for all index ∈ {1, . . . , Steps} do 6: grad ← ∇E⟨γ⟩π [MHit] E⟨γ⟩π[MHit] E⟨γ⟩π[MHit](Par1, . . . , Park) 7: Par1, . . . , Park ← OPTIMIZE(grad, Par1, . . . , Park) 8: Val ← EVALUATE(π, ε) 9: return π, Val

see Section 5). For the random profile π0, the value of each parameter Xi,s,a is sampled from the normal distribution with expected value 0 and variance 1.

The main optimization loop at lines 5-7 is terminated after Steps iterations, where Steps is a hyperparameter. In each step, the gradient of E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] at Par1, . . . , Park is computed (line 6) and then passed to a gradient-based optimizer that computes modified parameter values (line 7). Our implementation uses the PYTORCH library [Paszke et al., 2019] to compute the gradient, and OPTIMIZE(grad, Par1, . . . , Park) is implemented by the ADAM optimizer [Kingma and Ba, 2015]. At line 8, the value of Eπ[MHit] for the resulting profile π is computed up to the precision ε by the function EVALUATE(π, ε) whose implementation is described in the paragraph "Evaluating Memoryless Profiles" above.

5 Experiments

Our experimental evaluation aims to answer the following fundamental research questions: What is the quality of strategies and strategy profiles synthesized by our COORHIT and AUTOHIT algorithms? What is the efficiency and scalability of these algorithms? We also aim to compare the quality of solutions obtained in the coordinated and autonomous settings (i.e., estimate the price of autonomy).

Benchmarks. We designed a scalable family of benchmarks resembling cities with congestion at some crossroads. The benchmarks, parameterized by their length l and a "congestion factor" pc, consist of states sx,y for all 1≤x≤l, 1≤y≤5 and actions left, right, up, down. Each state is congested with probability pc (to avoid bias towards specific instances, the subset of congested states is determined randomly). In non-congested states, the actions work as expected, moving the agent left, right, up, and down, respectively. In congested states, the actions work as expected only with probability p ∈ [ 18 , 12 ] and with probability 1-p do not move the agent (i.e., they lead back to the same state). Thus, congested states model random delays at road segments. The goal is to reach the target state sl,3 from s1,3.

Setup. We used a Linux machine with AMD Ryzen 7 PRO 5750G CPU and 32 GB of RAM. All experiments were executed without using GPUs. Each execution has wall clock time limit of 5 minutes. In all experiments, the hyperparameters are set to Steps = 1000 and ε = 10-9 . The hyperparameter γ is set to the number of states of the MDP. This ensures that each simple path from the initial state to the target state is reflected in the objective function 1 E⟨γ⟩π[MHit] E⟨γ⟩π[MHit] E⟨γ⟩π[MHit]. A reproduction package is available as [Jon´aˇs et al., 2026].

Results for AUTOHIT. For each l ∈ {10, 20, 30, 40, 50}, we generated 10 random benchmarks with pc=0.2. Thus, we considered 50 benchmarks in total. As a baseline, we use the profile πLP consisting of the optimal single-agent strategies obtained by solving the LP of Fig. 2. We ran AUTOHIT for every k ∈ {1, 5, 10, 15, 20}. All AUTOHIT executions took less than 85 seconds of wall time, even for 20 agents and grids with l=50 containing 250 states and 890 actions.

We executed AUTOHIT with two initial parameter settings representing a random profile πRND and a precomputed profile πRLP, which is a "randomized version" of πLP. Note that since πLP is deterministic, it cannot be precisely translated into the parameter values due to the use of SOFTMAX. Instead, each parameter Xi,s,a representing πRLP is sampled from the normal distribution with the expected value equal to 10 or 0, depending on whether the strategy σi in the profile πLP selects the action a in s or not, respectively (the variance is 1). For each MSSP instance, we generate 5 randomly sampled versions of πRND and πRLP, and we use ValRND and ValRLP to denote the average Val returned by AUTOHIT for these 5 versions of πRND and πRLP, respectively. We compare ValRND and ValRLP against the baseline Base = EVALUATE(πLP, ε).

The results are presented in Fig. 4. The value ValRND is on average 97.5 % of Base and is even 81.9 % in some cases. For ValRLP, this improves to 96.0 % on average and 81.8 % in the best case. Hence, AUTOHIT computes strategy profiles that outperform the baseline, decreasing the expected value of MHit by almost 20 % in some cases. When initialized with πRLP, the profile computed by AUTOHIT outperforms the baseline in the vast majority of the benchmarks.

1 We also experimented with other values of γ, the results are available in [Jon´aˇs et al., 2026].

We also ran similar experiments with another precomputed initial profile πSP consisting of strategies following a graphtheoretic shortest path in the MDP. However, the quality of the resulting profiles computed by AUTOHIT tends to be worse than that for πRND and πRLP. We refer to [Jon´aˇs et al., 2026] for details.

Results for COORHIT. Our COORHIT implementation is based on Gurobi [Gurobi Optimization, LLC, 2024] LP solver. Since COORHIT does not scale so well in the number of agents, we use smaller grids. We generated 10 random benchmarks for each l between 3 and 10. To ensure that there are some congested crossroads on the shortest path, we used pc = 1. We ran the algorithms with 2, 3, and 4 agents.

The average runtimes of COORHIT and AUTOHIT (initialized with the πRLP profile) are shown in Fig. 5. Consistently with our theoretical results, AUTOHIT scales significantly better than COORHIT. For 4 agents, COORHIT did not terminate within 5 minutes for any grid with l>3. Hence, AUTOHIT is significantly more efficient than COORHIT.

In the cases where both algorithms terminated, the expected values of MHit for the resulting strategies and strategy profiles differed by 0.01 on average and at most by 0.08. This shows that the price of autonomy is rather low in the considered benchmarks.

6 Conclusions

Our initial study of the MSSP problem reveals the fundamental complexity barriers for designing efficient algorithmic solutions in both coordinated and autonomous setting. Our AUTOHIT algorithm successfully overcomes the barriers in the (more challenging) autonomous setting and produces high-quality solutions.

For our randomly generated benchmarks, AUTOHIT consistently improves the expected value of MHit over the baseline EπLP [MHit] where πLP is the profile consisting of optimal single-agent strategies. In some cases, this improvement is significant. This shows that despite the high computational complexity of the MSSP problem, there are efficient synthesis algorithms producing solutions outperforming the natural baseline EπLP [MHit].

The questions whether a similarly efficient synthesis algorithm exists also for the coordinated setting and whether alternative approaches can lead to even better synthesis algorithms certainly deserve an adequate research effort left for future work.

Acknowledgements

The work received funding from the Czech Science Foundation, grant No. 26-23441S.