next up previous
Next: Learning an Optimal Policy: Up: Finding a Policy Given Previous: Enhancement to Value Iteration

Computational Complexity

Value iteration works by producing successive approximations of the optimal value function. Each iteration can be performed in tex2html_wrap_inline2018 steps, or faster if there is sparsity in the transition function. However, the number of iterations required can grow exponentially in the discount factor [27]; as the discount factor approaches 1, the decisions must be based on results that happen farther and farther into the future. In practice, policy iteration converges in fewer iterations than value iteration, although the per-iteration costs of tex2html_wrap_inline2020 can be prohibitive. There is no known tight worst-case bound available for policy iteration [66]. Modified policy iteration [91] seeks a trade-off between cheap and effective iterations and is preferred by some practictioners [96].

Linear programming [105] is an extremely general problem, and MDPs can be solved by general-purpose linear-programming packages [35, 34, 46]. An advantage of this approach is that commercial-quality linear-programming packages are available, although the time and space requirements can still be quite high. From a theoretic perspective, linear programming is the only known algorithm that can solve MDPs in polynomial time, although the theoretically efficient algorithms have not been shown to be efficient in practice.

Leslie Pack Kaelbling
Wed May 1 13:19:13 EDT 1996