cs.AIApr 2, 2026

Efficient Constraint Generation for Stochastic Shortest Path Problems

Authors: Johannes Schmalz, Felipe Trevizan

Organizations: Australian National University, Australia · Saarland University, Germany

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Stochastic Shortest Path problems (SSPs) are traditionally solved by computing each state's cost-to-go by applying Bellman backups. A Bellman backup updates a state's cost-to-go by iterating through every applicable action, computing the cost-to-go after applying each one, and selecting a minimal action's cost-to-go. State-of-the-art algorithms use heuristic functions; these give an initial estimate of costs-to-go, and lets the algorithm apply Bellman backups only to promising states, determined by low estimated costs-to-go. However, each Bellman backup still considers all applicable actions, even if the heuristic tells us that some of these actions are too expensive, with the effect that such algorithms waste time on unhelpful actions. To address this gap we present a technique that uses the heuristic to avoid expensive actions, by reframing heuristic search in terms of linear programming and introducing an efficient implementation of constraint generation for SSPs. We present CG-iLAO*, a new algorithm that adapts iLAO* with our novel technique, and considers only 40% of iLAO*'s actions on many problems, and as few as 1% on some. Consequently, CG-iLAO* computes on average 3.5x fewer costs-to-go for actions than the state-of-the-art iLAO* and LRTDP, enabling it to solve problems faster an average of 2.8x and 3.7x faster, respectively.

More in this topic

Markov Decision Processes

Markov decision processes model sequential choices under uncertainty, linking actions, state transitions, and rewards to planning and reinforcement learning.

See all 157 papers

Explore similar work

CardsList
Apr 17, 2026

Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model

We study the sample complexity of learning an εε-optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with SS states, AA actions, minimum cost cmin⁡c_{\min}, and maximum expected cost of the optimal policy over all states B⋆B_{\star}, where any algorithm requires at least Ω(SAB⋆3/(cmin⁡ε2))Ω(SAB_{\star}^3/(c_{\min}ε^2)) samples to return an εε-optimal policy with high probability. Surprisingly, this implies that whenever cmin⁡=0c_{\min} = 0 an SSP problem may not be learnable, thus revealing that learning in SSPs is strictly harder than in the finite-horizon and discounted settings. We complement this lower bound with an algorithm that matches it, up to logarithmic factors, in the general case, and an algorithm that matches it up to logarithmic factors even when cmin⁡=0c_{\min} = 0, but only under the condition that the optimal policy has a bounded hitting time to the goal state.

Jean Tarbouriech, Matteo Pirotta, Michal Valko +1

Facebook AI Research Paris & Inria Lille · Facebook AI Research Paris · DeepMind Paris

Markov Decision ProcessesPolicy LearningSample-Efficient RL
AskPDF
May 7, 2026

Multiagent Stochastic Shortest Path Problem

We introduce and study the multi-agent stochastic shortest path (MSSP) problem, in which kk agents strive to reach a target state, aiming to minimize the expected time to reach the target by any agent. We analyze the computational and strategy-complexity of the problem in both autonomous and coordinated settings, and we design efficient strategy-synthesis algorithms. The algorithms are experimentally evaluated on instances of increasing size against natural baselines.

Martin Jonáš, Antonín Kučera, Vojtěch Kůr +2

Faculty of Informatics, Masaryk University, Czechia

Multi-Agent System OptimizationMulti-Agent CoordinationMulti-Agent Planning
AskPDF
Jun 4, 2026

Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics

Bidirectional heuristic search can potentially reduce search effort for problems amenable to backward search. Therein, it is well-known that front-to-front heuristics can reduce the number of node expansions, but their overhead is so high that overall runtime almost always increases. We propose BiXDFBnB, a bidirectional depth-first branch-and-bound algorithm that adapts the Single-Frontier Bidirectional Search (SFBDS) framework - originally developed for shortest-path (MIN) problems - to the Generalized Longest Simple Path (GLSP) setting. Because SFBDS inherently operates on paired states, front-to-front (F2F) heuristic evaluation arises naturally and avoids the overhead typically associated with bidirectional frontier management. We show that this adaptation can be successfully applied to maximization (MAX) problems while efficiently handling overlapping constraints. BiXDFBnB is applied to several types of longest-path problems: Longest Simple Path (LSP), Snakes, and Coil-in-the-Box (CIB). Empirical evaluation shows that the new algorithm frequently reduces the number of node expansions and, in some cases, also improves overall runtime.

Tzur Shubi, Ariel Felner, Solomon Eyal Shimony +1

Stein Faculty of Computer and Information Science, Ben-Gurion University of the Negev, Israel

Branch and BoundTree SearchCombinatorial Optimization
AskPDF