💻 computer science

Multiagent Stochastic Shortest Path Problem

This paper introduces the multi-agent stochastic shortest path problem, analyzes its computational and strategy complexity in autonomous and coordinated settings, and proposes efficient strategy-synthesis algorithms that are experimentally validated against natural baselines.

Original authors: Martin Jonáš, Antonín Kučera, Vojtěch Kůr, Jan Mačák, Vojtěch Řehák

Published 2026-05-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Martin Jonáš, Antonín Kučera, Vojtěch Kůr, Jan Mačák, Vojtěch Řehák

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to get a very urgent package to a hospital. You have a map of the city, but the traffic is unpredictable. Sometimes a road is clear, and sometimes it's a total jam. This is a classic "Stochastic Shortest Path" problem: finding the fastest route when the future is uncertain.

Now, imagine you don't just have one car, but a fleet of ten cars leaving the same warehouse at the same time. Your goal isn't to get every car to the hospital as fast as possible; your goal is to get at least one car there as quickly as possible. The first car to arrive delivers the package; the others can wait or be used later.

This paper introduces a new way to solve this "Multiagent Stochastic Shortest Path" (MSSP) problem. The authors ask: How should we direct these cars to minimize the time until the first one arrives?

Here is the breakdown of their findings, using simple analogies:

1. The Two Ways to Drive: The "Conductor" vs. The "Soloists"

The paper explores two different ways to manage the fleet:

The Coordinated Approach (The Conductor): Imagine a central control room (a conductor) that sees the whole city and tells every car exactly what to do at every moment. If Car A hits a jam, the conductor instantly tells Car B to take a different route.
- The Result: The authors found that while this is the most efficient way to drive, it gets incredibly hard to calculate as you add more cars. If you have 2 cars, it's easy. If you have 10, the math becomes so massive it's practically impossible to solve perfectly on a standard computer. They proved that the difficulty explodes exponentially with every new car added.
- The Good News: If the number of cars is fixed (e.g., you always have exactly 3 cars), you can solve it perfectly and quickly.
The Autonomous Approach (The Soloists): Imagine each car has its own GPS and makes decisions on its own, without talking to the others or a central brain. They don't know what the other cars are doing.
- The Result: This is much harder to solve mathematically. In fact, finding the perfect set of rules for these independent cars is a "nightmare" problem (technically called NP-hard). Even with just two cars, finding the absolute best strategy is computationally very difficult.
- The Catch: Sometimes, the cars need to "remember" things. For example, Car A might need to remember, "I took a left turn three blocks ago, so I should probably turn right now to avoid the other car." The paper shows that perfect strategies might need infinite memory, but "good enough" strategies only need a tiny bit of memory.

2. The "Price of Autonomy"

The authors calculated the "Price of Autonomy." This is a fancy way of asking: "How much slower is the soloist approach compared to the conductor approach?"

In some scenarios, the answer is "not much." The soloists do almost as well as the conductor.
In other scenarios, the answer is "a lot." The soloists might be significantly slower because they can't coordinate to avoid each other or cover different routes effectively.
The paper proves that this "price" can be arbitrarily large. In the worst cases, letting the cars drive themselves without coordination can be infinitely worse than having a conductor.

3. The Solution: "AUTOHIT" (The Smart Optimizer)

Since finding the perfect solution for independent cars is mathematically impossible to do quickly, the authors invented an algorithm called AUTOHIT.

How it works: Instead of trying to find the perfect answer (which is like trying to find the single highest peak in a massive, foggy mountain range), AUTOHIT uses a technique called "gradient descent." Imagine you are blindfolded on a hill and you want to get to the bottom. You feel the ground with your feet; if it slopes down, you take a step that way. You keep doing this until you can't go any lower.
The Twist: They turned the problem into a smooth, mathematical landscape where they can use powerful modern tools (like those used to train AI) to "slide" down to a very good solution.
The Trade-off: They admit this isn't a guarantee of the perfect solution (because the perfect one is too hard to find), but it finds a solution that is significantly better than the standard "do what the single car would do" approach.

4. The Experiments: Testing in a Virtual City

To test their ideas, they built a virtual city with grid-like streets. Some intersections had "traffic jams" (random delays). They sent fleets of cars (from 1 to 20 cars) through these cities.

The Baseline: They compared their new method against the "obvious" strategy: just tell every car to take the best route for a single car, ignoring the others.
The Result: AUTOHIT consistently beat the baseline. In some cases, it reduced the expected arrival time of the first car by nearly 20%.
Speed: The "Conductor" method (COORHIT) was too slow for large fleets (it timed out with just 4 cars on a big map). The "Soloist" method (AUTOHIT) was fast and scalable, handling 20 cars on large maps in under a minute.

Summary

The paper says:

Coordinating many agents to reach a target first is theoretically possible but computationally heavy as the group grows.
Letting agents act independently is mathematically very hard to optimize perfectly, but we can get very close to the best result using smart, modern optimization techniques.
Their new algorithm, AUTOHIT, is a practical tool that helps independent agents work together (without actually talking) to get the job done much faster than if they just acted alone.

In short: If you need to get a package there fast with a team of drivers, you should try to coordinate them. But if you can't, don't just let them drive randomly—use a smart algorithm to teach them how to drive independently in a way that still beats the odds.

Technical Summary: Multiagent Stochastic Shortest Path Problem

Problem Definition

The paper introduces and investigates the Multiagent Stochastic Shortest Path (MSSP) problem. In this setting, $k$ agents operate within a known, explicitly represented Markov Decision Process (MDP). The objective is to minimize the expected time until at least one agent reaches a designated target state. This contrasts with classical Stochastic Shortest Path (SSP) problems where a single agent minimizes its own expected path length.

The authors distinguish between two operational settings:

Coordinated MSSP: Agents are controlled by a central authority that issues joint actions based on the global state and shared memory.
Autonomous MSSP: Agents act independently, each following its own strategy based on its local history and memory, without coordination.

A motivating example provided is the urgent transport of blood by multiple vehicles; the goal is to minimize the expected arrival time of the first vehicle, rather than the average arrival time of all vehicles. The paper notes that solving the single-agent SSP problem independently for each agent (a natural baseline) is generally suboptimal and can, in specific cases, be the worst possible solution.

Methodology and Complexity Analysis

Theoretical Complexity

The authors analyze the computational and strategy complexity for both settings:

Coordinated MSSP:
- Complexity: The problem is shown to be PSPACE-hard. However, for a fixed number of agents $k$ , the problem is solvable in time polynomial in the size of the MDP $M$ , though exponential in $k$ .
- Strategy Type: An optimal coordinated strategy exists that is memoryless (decisions depend only on current positions) and deterministic.
- Algorithm: The authors propose COORHIT, which reduces the $k$ -agent problem to a single-agent SSP on a product MDP of size $|S|^k$ , solvable via standard Linear Programming (LP).
Autonomous MSSP:
- Complexity: The decision problem (determining if an expected time $\le B$ exists) is NP-hard, even for $k=2$ agents and even when restricted to memoryless profiles. Consequently, the problem is not fixed-parameter tractable in $k$ .
- Strategy Type: Optimal autonomous profiles may require finite memory of arbitrary size. However, for any $\epsilon > 0$ , an $\epsilon$ -optimal profile exists using finite-memory randomized strategies.
- Randomization: The paper proves that randomized profiles are strictly more powerful than deterministic ones for a fixed memory size.
- Reduction: The synthesis of finite-memory profiles is reducible to the synthesis of memoryless profiles in an expanded MDP, but the core problem remains NP-hard.

Algorithmic Solution: AUTOHIT

Given the NP-hardness of the autonomous setting, the authors design AUTOHIT, an efficient heuristic synthesis algorithm that sacrifices optimality guarantees for scalability.

Differentiable Programming: The core innovation is representing memoryless randomized strategies as vectors of real-valued parameters. Using the Softmax function, these parameters define action probabilities.
Objective Function: The expected time to reach the target is expressed as a differentiable function of these parameters. The authors derive a truncated infinite sum approximation, $E^{\langle \gamma \rangle}_\pi[M_{Hit}]$ , which is computable in polynomial time.
Optimization: AUTOHIT uses gradient descent (specifically the ADAM optimizer via PyTorch) to minimize this differentiable objective function.
Initialization: The algorithm can be initialized with random parameters or pre-computed strategies (e.g., derived from single-agent LP solutions).

Experimental Results

The authors evaluated their algorithms on randomly generated benchmarks resembling grid-like city maps with random traffic delays (congestion).

Coordinated vs. Autonomous:
- COORHIT scales poorly with the number of agents due to the exponential state space of the product MDP. It failed to terminate within 5 minutes for 4 agents on grids larger than size 3.
- AUTOHIT scales significantly better, handling up to 20 agents on grids with 250 states in under 85 seconds.
- Price of Autonomy: In cases where both algorithms terminated, the performance gap (Price of Autonomy) was small (average difference of 0.01 in expected time), suggesting that for these specific benchmarks, coordination offers limited additional benefit over well-tuned autonomous strategies.
Performance vs. Baselines:
- AUTOHIT consistently outperformed the natural baseline of independent optimal single-agent strategies (solved via LP).
- In some instances, AUTOHIT reduced the expected time to reach the target by nearly 20% compared to the baseline.
- Initializing AUTOHIT with a "randomized version" of the LP solution yielded slightly better results than purely random initialization.

Key Contributions

Problem Formulation: Formal definition of the MSSP problem, distinguishing between coordinated and autonomous settings, and identifying the objective as minimizing the expected time of the first arrival.
Complexity Characterization:
- Proved Coordinated MSSP is PSPACE-hard but fixed-parameter tractable in $k$ (with memoryless deterministic optimal strategies).
- Proved Autonomous MSSP is NP-hard even for $k=2$ and memoryless profiles, requiring finite-memory randomized strategies for $\epsilon$ -optimality.
- Demonstrated that the "Price of Autonomy" can be arbitrarily large.
Algorithmic Innovation: Development of AUTOHIT, a differentiable programming approach for synthesizing autonomous strategies. This approach bypasses the NP-hardness barrier by using gradient-based optimization on a differentiable approximation of the expected time.
Empirical Validation: Experimental evidence showing that AUTOHIT produces high-quality solutions that significantly outperform independent single-agent baselines and scales to agent counts where exact coordinated methods fail.

Significance and Claims

The paper claims that while the MSSP problem presents fundamental complexity barriers (PSPACE-hardness for coordination, NP-hardness for autonomy), efficient synthesis algorithms can still produce solutions that significantly outperform natural baselines.

The authors emphasize that their work initiates the study of MSSP. They highlight that despite the high computational complexity, the AUTOHIT algorithm successfully overcomes barriers in the more challenging autonomous setting. The results suggest that for time-critical delivery problems where items can be replicated (like the blood transport example), deploying multiple autonomous agents with synthesized strategies is a viable and effective approach, often yielding near-optimal performance without the need for expensive central coordination.

The paper concludes modestly, noting that while AUTOHIT is effective, the existence of similarly efficient algorithms for the coordinated setting (beyond the exponential blowup) and alternative approaches for even better synthesis remain open questions for future research.