An Analysis of Stochastic Shortest Path Problems

DOI10.1287/moor.16.3.580zbMath0751.90077OpenAlexW2081287319MaRDI QIDQ3986758

Dimitri P. Bertsekas, John N. Tsitsiklis

Publication date: 27 June 1992

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.16.3.580

zbMATH Keywords

Bellman equationsuccessive approximationpolicy iterationoptimal stationary policystochastic shortest path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic programming (90C15) Markov and semi-Markov decision processes (90C40)

Related Items (71)

Stability Estimation of Transient Markov Decision Processes ⋮ Distance oracles for time-dependent networks ⋮ Policy iteration type algorithms for recurrent state Markov decision processes ⋮ A Semantics for Every GSPN ⋮ Probabilistic causes in Markov chains ⋮ Performance analysis of probabilistic timed automata using digital clocks ⋮ Dynamic shortest path problems: hybrid routing policies considering network disruptions ⋮ PH-graphs for analyzing shortest path problems with correlated traveling times ⋮ On an exact method for the constrained shortest path problem ⋮ The stochastic shortest-path problem for Markov chains with infinite state space with applications to nearest-neighbor lattice chains ⋮ Computing transience bounds of emergency call centers: a hierarchical timed Petri net approach ⋮ Anonymous Stochastic Routing ⋮ A game-based abstraction-refinement framework for Markov decision processes ⋮ A Tutorial on Interactive Markov Chains ⋮ Markov Reward Models and Markov Decision Processes in Discrete and Continuous Time: Performance Evaluation and Optimization ⋮ Symblicit algorithms for mean-payoff and shortest path in monotonic Markov decision processes ⋮ On the convergence of reinforcement learning with Monte Carlo exploring starts ⋮ Q-learning and policy iteration algorithms for stochastic shortest path problems ⋮ Error bounds for stochastic shortest path problems ⋮ An approach to the distributionally robust shortest path problem ⋮ Symbolic Minimum Expected Time Controller Synthesis for Probabilistic Timed Automata ⋮ The stochastic shortest path problem: a polyhedral combinatorics perspective ⋮ Regular Policies in Abstract Dynamic Programming ⋮ Competence-aware systems ⋮ An anytime algorithm for constrained stochastic shortest path problems with deterministic policies ⋮ Stochastic shortest path problems with associative accumulative criteria ⋮ On probability-raising causality in Markov decision processes ⋮ Optimal stopping with a probabilistic constraint ⋮ Foundations of probability-raising causality in Markov decision processes ⋮ Real-time dynamic programming for Markov decision processes with imprecise probabilities ⋮ A simple ant colony optimizer for stochastic shortest path problems ⋮ Relax-and-split method for nonconvex inverse problems ⋮ Efficient solutions to factored MDPs with imprecise transition probabilities ⋮ Using mathematical programming to solve factored Markov decision processes with imprecise probabilities ⋮ Depth-based short-sighted stochastic shortest path problems ⋮ Risk-sensitive multiagent decision-theoretic planning based on MDP and one-switch utility functions ⋮ Optimal threshold probability in undiscounted Markov decision processes with a target set. ⋮ PageRank optimization by edge selection ⋮ Percentile queries in multi-dimensional Markov decision processes ⋮ On the complexity of time-dependent shortest paths ⋮ An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem ⋮ Maximizing the Conditional Expected Reward for Reaching the Goal ⋮ Model Checking Exact Cost for Attack Scenarios ⋮ Concurrent reachability games ⋮ Symbolic optimal expected time reachability computation and controller synthesis for probabilistic timed automata ⋮ Robust path choice in networks with failures ⋮ Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games ⋮ Teaching randomized learners with feedback ⋮ SPAR: Stochastic Programming with Adversarial Recourse ⋮ On terminating Markov decision processes with a risk-averse objective function ⋮ An analysis of transient Markov decision processes ⋮ Proximal algorithms and temporal difference methods for solving fixed point problems ⋮ Optimal search from multiple distributions with infinite horizon ⋮ Nearly Optimal Verifiable Data Streaming ⋮ Computation tree measurement language (CTML) ⋮ Perseverance and suspense in tug-of-war ⋮ Robust Adaptive Routing Under Uncertainty ⋮ Wasserstein distributionally robust shortest path problem ⋮ Reaching Your Goal Optimally by Playing at Random with No Memory ⋮ Optimization of a peer-to-peer system for efficient content replication ⋮ A directed hypergraph model for random time dependent shortest paths ⋮ On the fastest finite Markov processes ⋮ Maximum-Stopping-Value Policies in Finite Markov Population Decision Chains ⋮ On Convergence of Value Iteration for a Class of Total Cost Markov Decision Processes ⋮ Robust shortest path planning and semicontractive dynamic programming ⋮ Multiply Accelerated Value Iteration for NonSymmetric Affine Fixed Point Problems and Application to Markov Decision Processes ⋮ Optimal decisions in stochastic graphs with uncorrelated and correlated edge weights ⋮ A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times ⋮ Computational Methods for Risk-Averse Undiscounted Transient Markov Models ⋮ An application of Lemke's method to a class of Markov decision problems ⋮ Dynamic shortest path in stochastic dynamic networks: Ship routing problem

This page was built for publication: An Analysis of Stochastic Shortest Path Problems