An Analysis of Stochastic Shortest Path Problems
By Dimitri P. Bertsekas, John N. Tsitsiklis. 1991
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.
Subfields: Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Algorithms & Complexity
- John N. Tsitsiklis
- Thomas Unterthiner
- Angelia Nedić
- Asuman E. Ozdaglar
- Christoforos N. Hadjicostis
- Shreyas Sundaram
- José M. F. Moura
- Anders Rantzer
Citations in the corpus
- Learning Parameterized Skills (2012, neutral): “This result is similar to the more general problem of Stochastic Shortest Paths (SSP) [8] — the main difference being that SSPs require MDPs with finite state spaces.”
- RUDDER: Return Decomposition for Delayed Rewards (2018, methodology): “ contraction mapping with respect to a weighted sup-norm has been proved in Tseng, 1990, in Lemma 3 with equation (13) and text thereafter [111]. Also Proposition 1 in Bertsekas and Tsitsiklis, 1991, [10], Theorems 3 and 4(b) & 4(c) in Tsitsiklis, 1994, [112], and Proposition 2.2 on pages 23-24 ”
- Primal-dual algorithms for discounted Markov decision processes (2015, unknown): “c(1) = [ 1 2 ] c(2) = [ 3 4 ]”
- Asynchronous Stochastic Approximation and Q-Learning (1994, background): “It is then known [BT, BT1 ] that there exists a vector v > 0 such that T is a contraction with respect to the norm 1 . II,.”
- Automated Verification Techniques for Probabilistic Systems (2011, background): “From the results presented in [17,16] (since the problem of finding minimum reachability probabilities is a special case of the stochastic shortest path problem), the equations above have a unique solution.”