TL;DR
This paper introduces a novel method for computing suboptimality bounds in stochastic shortest path problems (SSPs), even when not all policies guarantee reaching a goal state. By leveraging the Bellman residual and a concept called "uniform improvability," the authors provide a way to quantify the error in approximate solutions, which is crucial for practical applications where optimal policies are hard to find.
What Problem Does This Paper Address?
Stochastic shortest path problems (SSPs) are fundamental to planning under uncertainty, aiming to find a policy that minimizes the expected cost to reach a goal state. While dynamic programming (DP) is a standard solution method, its convergence guarantees and the ability to bound the error of approximate solutions are often weaker than in discounted Markov decision processes (MDPs). Specifically, in SSPs, the DP operator isn't always a contraction, meaning standard techniques for bounding suboptimality (like those used in discounted MDPs) don't directly apply. This is particularly problematic when some policies might never reach the goal state, making their expected cost infinite. The paper tackles the challenge of providing meaningful suboptimality bounds in these more general, and more realistic, SSP settings.
Methods
The core of the paper's contribution lies in extending suboptimality bounding techniques to SSPs where not all policies are proper (i.e., guarantee reaching the goal). The authors build upon existing results by Bertsekas and Tsitsiklis, which relate suboptimality to the Bellman residual and bounds on the expected number of steps to reach the terminal state.
Key methodological contributions include:
- Uniform Improvability: They introduce the concept of a "uniformly improvable value function" (J) where the Bellman equation (TJ < J) holds. This property is crucial because it guarantees that a greedy policy derived from J will be proper (guarantees reaching the goal).
- Bounding Expected Steps: For uniformly improvable value functions, they derive a method to compute an upper bound on the expected number of steps to reach the terminal state. This bound, denoted N(i), is derived using the minimum transition costs into and out of the terminal state.
- Connecting Bellman Residual to Suboptimality: By combining the bounds on expected steps with the Bellman residual (||TJ - J||), they establish suboptimality bounds of the form ||J* - J|| ≤ ||TJ - J|| * N, where N is the maximum of these step bounds. This is a generalization of the well-known bound for discounted MDPs.
- Behavioral Contraction: They show that the DP operator behaves like an m-stage contraction operator on the subspace of uniformly improvable value functions, even if it's not a contraction on the entire space. This theoretical insight underpins the possibility of bounding convergence rates and suboptimality.
Datasets
Not discussed in the paper. The paper uses a small gridworld example for illustration, which is a standard benchmark in AI planning literature.
Key Insights and Ideas
- Uniform Improvability is Key: The concept of a uniformly improvable value function is the linchpin that allows for suboptimality bounds in the general SSP case. It bridges the gap between non-contractive operators and the need for error bounds.
- Proper Policies from Greedy Actions: A direct consequence of uniform improvability is that greedy policies derived from such value functions are guaranteed to be proper. This is a significant theoretical result for policy generation.
- Generalizing Discounted MDP Bounds: The paper successfully generalizes the suboptimality bounds from discounted MDPs to SSPs, showing that the Bellman residual, combined with bounds on the expected time to termination, provides a unified framework.
- Practical Implications for POMDPs: The work has implications for partially observable Markov decision processes (POMDPs), suggesting that even for undiscounted POMDPs (which are generally undecidable for e-optimal policies), the SSP formulation might allow for decidability and practical approximation.
Key Results
- Theorem 2: A greedy policy derived from a uniformly improvable value function (TJ < J) is proper and its value function is no worse than the original value function (Jµ ≤ J).
- Theorem 5: For SSPs with positive transition costs (except to the terminal state), an upper bound N(i) on the expected number of steps to reach the terminal state is derived as N(i) = (J(i) - a) / b + 1, where 'a' and 'b' are minimum transition costs.
- Suboptimality Bound: The paper establishes suboptimality bounds of the form ||J* - J|| ≤ ||TJ - J|| * N, where N is an upper bound on the expected number of steps to reach the terminal state. This bound is applicable even when not all policies are proper, provided the value function is uniformly improvable.
- Gridworld Example: The paper demonstrates the effectiveness of their approach on a gridworld navigation example, showing how suboptimality bounds decrease as value iteration or policy iteration progresses, and how these bounds can be state-dependent.
Limitations and Future Work
- Practicality of Bounds in General Case: While the paper shows that suboptimality bounds are possible in the general case (zero or negative transition costs), the derived bounds are described as "much too loose to be practical." This suggests that finding tighter bounds in these scenarios remains an open problem.
- Computational Complexity: The paper mentions that for partially observable SSPs, the number of belief states can grow exponentially, making exact solutions intractable. While suboptimality bounds are helpful, computing them efficiently in such complex scenarios is still a challenge.
- Future Work: The authors explicitly state that future work will focus on developing more practical approaches to computing tight suboptimality bounds in the general case where transition costs can be zero or negative.
Summary updated