Error bounds for stochastic shortest path problems

For stochastic shortest path problems, error bounds for value iteration due to Bertsekas elegantly generalize the classic MacQueen–Porteus error bounds for discounted infinite‐horizon Markov decision problems, but incur prohibitive computational overhead. We derive bounds on these error bounds that can be computed with little or no overhead, making them useful in practice–especially so, since easily‐computed error bounds have not previously been available for this class of problems.