The stochastic shortest path problem: a polyhedral combinatorics perspective
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3126094 (Why is no real title available?)
- scientific article; zbMATH DE number 3148886 (Why is no real title available?)
- scientific article; zbMATH DE number 1786124 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- A New Complexity Result on Solving the Markov Decision Problem
- A Survey of Applications of Markov Decision Processes
- An Analysis of Stochastic Shortest Path Problems
- An Auction Algorithm for Shortest Paths
- An Intertemporal Capital Asset Pricing Model
- Approximate Dynamic Programming
- Dynamic programming and optimal control. Vol. 1.
- Dynamic programming and optimal control. Vol. 2
- Exponential lower bounds for policy iteration
- Linear Programming and Markov Decision Chains
- Linear programming and sequential decisions
- Markov decision processes with applications to finance.
- Mathematical problems for the next century
- Maximum matching and a polyhedron with 0,1-vertices
- Network flows. Theory, algorithms, and applications.
- On Linear Programming in a Markov Decision Problem
- On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
- Planning with Markov decision processes. An AI perspective
- Polynomial auction algorithms for shortest paths
- Réseaux stochastiques
- Stochastic Games
- Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
- The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
- The stochastic motion roadmap: a sampling framework for planning with Markov motion uncertainty
- The value iteration algorithm is not strongly polynomial for discounted dynamic programming
Cited in
(10)- Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function
- Variations on the stochastic shortest path problem
- Depth-based short-sighted stochastic shortest path problems
- The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms
- A multi-objective approach for PH-graphs with applications to stochastic shortest paths
- A fully polynomial time approximation scheme for the probability maximizing shortest path problem
- The stochastic shortest-path problem for Markov chains with infinite state space with applications to nearest-neighbor lattice chains
- Technical Note—A Note on the Stochastic Shortest Route Problem
- A note on detecting unbounded instances of the online shortest path problem
- Error bounds for stochastic shortest path problems
This page was built for publication: The stochastic shortest path problem: a polyhedral combinatorics perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2183321)
