# The Stochastic Shortest Path Problem : A polyhedral combinatorics perspective

arXiv: https://arxiv.org/abs/1702.03186 · HTML: https://mlsanity.com/paper/1702.03186/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2017.

## Built on by (most cited first, 7 of 7)

- [Adversarial Intrinsic Motivation for Reinforcement Learning](https://mlsanity.com/paper/2105.13345/) (2021)
- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [On the Learning and Learnability of Quasimetrics](https://mlsanity.com/paper/2206.15478/) (2022)
- [Reductive MDPs: A Perspective Beyond Temporal Horizons](https://mlsanity.com/paper/2205.07338/) (2022)
- [Convergent Reinforcement Learning Algorithms for Stochastic Shortest Path Problem](https://mlsanity.com/paper/2508.13963/) (2025)
- [Bayesian learning for the stochastic shortest path problem](https://mlsanity.com/paper/2606.04845/) (2026)

## Abstract (arXiv)

In this paper, we give a new framework for the stochastic shortest path problem in finite state and action spaces. Our framework generalizes both the frameworks proposed by Bertsekas and Tsitsikli and by Bertsekas and Yu. We prove that the problem is well-defined and (weakly) polynomial when (i) there is a way to reach the target state from any initial state and (ii) there is no transition cycle of negative costs (a generalization of negative cost cycles). These assumptions generalize the standard assumptions for the deterministic shortest path problem and our framework encapsulates the latter problem (in contrast with prior works). In this new setting, we can show that (a) one can restrict to deterministic and stationary policies, (b) the problem is still (weakly) polynomial through linear programming, (c) Value Iteration and Policy Iteration converge, and (d) we can extend Dijkstra's algorithm.