An Analysis of Stochastic Shortest Path Problems

We consider a stochastic version of the classical shortest path problem whereby for each node of a graph, we must choose a probability distribution over the set of successor nodes so as to reach a certain destination node with minimum expected cost. The costs of transition between successive nodes can be positive as well as negative. We prove natural generalizations of the standard results for the deterministic shortest path problem, and we extend the corresponding theory for undiscounted finite state Markovian decision problems by removing the usual restriction that costs are either all nonnegative or all nonpositive.

• Publication year

  1991

• Venue

  Mathematics of Operations Research

• Publication date

  1991-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1287/moor.16.3.580
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Solving H-horizon, stationary Markov decision problems in time proportional to log(H)

  1990cited by this paper
• Parallel and distributed computation

  1989cited by this paper
• Dynamic Programming: Deterministic and Stochastic Models

  1987cited by this paper
• Negative Dynamic Programming

  1984cited by this paper
• Optimization Over Time

  1982cited by this paper
• Introduction to stochastic control

  1972influential reference
• Finite State Markovian Decision Processes

  1970cited by this paper
• Discrete Dynamic Programming with Sensitive Discount Optimality Criteria

  1969influential reference
• Optimal control theory

  1967cited by this paper
• CONTRACTION MAPPINGS IN THE THEORY UNDERLYING DYNAMIC PROGRAMMING

  1967cited by this paper
• Positive dynamic programming

  1967cited by this paper
• On Stefan’s Problem and Optimal Stopping Rules for Markov Processes

  1966cited by this paper
• Optimal Pursuit Strategies in Discrete-State Probabilistic Systems

  1962cited by this paper

• Large-Language-Model-Guided State Estimation for Partially Observable Task and Motion Planning

  2026cites this paper
• Preference-based probabilistic planning with partially-ordered temporal goals

  2026cites this paper
• Multiplicative Rewards in Markovian Models

  2025cites this paper
• Compromis entre sécurité et efficacité : Garanties formelles pour les MDP orientés but

  2025cites this paper
• Lexicographic Multi-Objective Stochastic Shortest Path with Mixed Max-Sum Costs

  2025cites this paper
• Sound Value Iteration for Simple Stochastic Games

  2025cites this paper
• Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems

  2025cites this paper
• Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs

  2025cites this paper
• Uncertain Machine Ethics Planning

  2025cites this paper
• Stochastic Shortest Path with Sparse Adversarial Costs

  2025cites this paper
• Robust Shortest Path with Incremental Information Revelation

  2025cites this paper
• Reinforcement Learning with Anticipation: A Hierarchical Approach for Long-Horizon Tasks

  2025cites this paper
• Road traffic estimation and distribution-based route selection

  2025cites this paper
• On Exact Solutions to the Linear Bellman Equation

  2025cites this paper
• Approximation Algorithms for Observer Aware MDPs

  2024cites this paper
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path

  2024influential citation
• Survey of Computerized Adaptive Testing: A Machine Learning Perspective

  2024cites this paper
• Risk-averse optimization of total rewards in Markovian models using deviation measures

  2024influential citation
• Demonic variance and a non-determinism score for Markov decision processes

  2024cites this paper
• Efficient Constraint Generation for Stochastic Shortest Path Problems

  2024cites this paper
• First Passage Percolation with Queried Hints

  2024cites this paper
• Dynamic vessel schedule recovery strategy of liner shipping with uncertainties: An event-triggered model predictive control solution

  2024cites this paper
• Risk-averse Total-reward MDPs with ERM and EVaR

  2024cites this paper
• Merge-and-Shrink Heuristics for SSPs with Prune Transformations

  2024cites this paper
• Iterative algorithms for solving one-sided partially observable stochastic shortest path games

  2024cites this paper
• Preference-Based Planning in Stochastic Environments: From Partially-Ordered Temporal Goals to Most Preferred Policies

  2024cites this paper
• Heuristic Search for Linear Positive Systems

  2024cites this paper
• Applying Ethical Decision Making on Space Missions

  2024cites this paper
• Finding Optimal Deterministic Policies for Constrained Stochastic Shortest Path Problems

  2024cites this paper
• Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning

  2024cites this paper
• Pessimistic Iterative Planning with RNNs for Robust POMDPs

  2024cites this paper
• Hierarchical Planning and Learning for Robots in Stochastic Settings Using Zero-Shot Option Invention

  2024cites this paper
• Online Resource Allocation in Episodic Markov Decision Processes

  2023cites this paper
• Distance Weighted Supervised Learning for Offline Interaction Data

  2023cites this paper
• Semi-Autonomous Systems with Contextual Competence Awareness

  2023cites this paper
• A Novel All-Pairs Shortest Path Algorithm ∗

  2023cites this paper
• Strategy Synthesis in Markov Decision Processes Under Limited Sampling Access

  2023cites this paper
• Positivity-hardness results on Markov decision processes

  2023cites this paper
• Dynamic Project Expediting: A Stochastic Shortest-Path Approach

  2023cites this paper
• Online Reinforcement Learning with Uncertain Episode Lengths

  2023cites this paper
• Heuristic Search for Multi-Objective Probabilistic Planning

  2023cites this paper
• Monotone Causality in Opportunistically Stochastic Shortest Path Problems

  2023influential citation
• Hierarchical Motion Planning Under Probabilistic Temporal Tasks and Safe-Return Constraints

  2023cites this paper
• Minimax weight learning for absorbing MDPs

  2023cites this paper
• A Practitioner's Guide to MDP Model Checking Algorithms

  2023cites this paper
• Reachability Games and Friends: A Journey Through the Lens of Memory and Complexity (Invited Talk)

  2023cites this paper
• Tackling Stackelberg Network Interdiction against a Boundedly Rational Adversary

  2023cites this paper
• A Fully Polynomial Time Approximation Scheme for Constrained MDPs Under Local Transitions

  2023cites this paper
• ROSARL: Reward-Only Safe Reinforcement Learning

  2023cites this paper
• Uncertainty-Aware Planning for Heterogeneous Robot Teams using Dynamic Topological Graphs and Mixed-Integer Programming

  2023cites this paper
• Recent Trends in Task and Motion Planning for Robotics: A Survey

  2023cites this paper
• Anytime-Constrained Reinforcement Learning

  2023cites this paper
• Cartesian Abstractions and Saturated Cost Partitioning in Probabilistic Planning

  2023cites this paper
• Forward-PECVaR Algorithm: Exact Evaluation for CVaR SSPs

  2023influential citation
• Posterior sampling-based online learning for the stochastic shortest path model

  2023influential citation
• A Theory of Merge-and-Shrink for Stochastic Shortest Path Problems

  2023cites this paper
• Entropic Risk for Turn-Based Stochastic Games

  2023cites this paper
• Should sports professionals consider their adversary’s strategy? A case study of match play in golf

  2023influential citation
• On the Statistical Benefits of Temporal Difference Learning

  2023cites this paper
• Real-time safest route identification: Examining the trade-off between safest and fastest routes

  2023cites this paper
• Uncertain Machine Ethical Decisions Using Hypothetical Retrospection

  2023cites this paper
• Bi-Objective Lexicographic Optimization in Markov Decision Processes with Related Objectives

  2023cites this paper
• Mixture Model for Contextual Route Choice in Multimodal Transportation Systems

  2023cites this paper
• A Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions

  2022influential citation
• DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs

  2022cites this paper
• A Novel Faster All-Pair Shortest Path Algorithm Based on the Matrix Multiplication for GPUs

  2022cites this paper
• On the Learning and Learnability of Quasimetrics

  2022cites this paper
• Cost Partitioning Heuristics for Stochastic Shortest Path Problems

  2022cites this paper
• Stochastic Route Planning for Electric Vehicles

  2022cites this paper
• Stochastic Policies in Morally Constrained (C-)SSPs

  2022cites this paper
• Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)

  2022cites this paper
• Recursive Reinforcement Learning

  2022cites this paper
• Convex duality for stochastic shortest path problems in known and unknown environments

  2022influential citation
• Dynamic Regret of Online Markov Decision Processes

  2022cites this paper
• On the Learning and Learnablity of Quasimetrics

  2022cites this paper
• Turning Mathematics Problems into Games: Reinforcement Learning and Gröbner bases together solve Integer Feasibility Problems

  2022cites this paper
• Exploration. Exploitation, and Engagement in Multi-Armed Bandits with Abandonment

  2022influential citation
• Multiagent, Multitarget Path Planning in Markov Decision Processes

  2022influential citation
• An anytime algorithm for constrained stochastic shortest path problems with deterministic policies

  2022cites this paper
• Heuristic Search for SSPs with Lexicographic Preferences over Multiple Costs

  2022cites this paper
• Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality

  2022cites this paper
• Bayesian Reinforcement Learning for Single-Episode Missions in Partially Unknown Environments

  2022cites this paper
• Reinforcement Learning and Stochastic Optimization

  2022cites this paper
• Testes Adaptativos Computadorizados como um Processo de Decisão Markoviano: equilíbrio ótimo entre eficiência e precisão

  2022cites this paper
• Road traffic estimation and distribution-based route selection

  2022cites this paper
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path

  2022cites this paper
• Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings

  2022influential citation
• Lane-level route planning for autonomous vehicles

  2022cites this paper
• Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Path

  2022cites this paper
• Optimal decisions in stochastic graphs with uncorrelated and correlated edge weights

  2022cites this paper
• Partial Consistency for Stabilizing Undiscounted Reinforcement Learning

  2022cites this paper
• Iterative Depth-First Search for Fully Observable Non-Deterministic Planning

  2022cites this paper
• The variance-penalized stochastic shortest path problem

  2022influential citation
• Probabilistic Planning with Partially Ordered Preferences over Temporal Goals

  2022cites this paper
• Undiscounted Recursive Path Choice Models: Convergence Properties and Algorithms

  2022cites this paper
• Congestion-Aware Policy Synthesis for Multirobot Systems

  2022cites this paper
• On the Convergence of Monte Carlo UCB for Random-Length Episodic MDPs

  2022cites this paper
• On probability-raising causality in Markov decision processes

  2022influential citation
• Multi-Task Option Learning and Discovery for Stochastic Path Planning

  2022cites this paper
• A Fully Polynomial Time Approximation Scheme for Fixed-Horizon Constrained Stochastic Shortest Path Problem under Local Transitions

  2022cites this paper