Proceedings

Topological Value Iteration Algorithm for Markov Decision Processes

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1860-1864.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Value Iteration is an inefficient algorithm for Markov decision processes (MDPs) because it puts the majority of its effort into backing up the entire state space, which turns out to be unnecessary in many cases. In order to overcome this problem, many approaches have been proposed. Among them, LAO*, LRTDP and HDP are state-of-the-art ones. All of these use reachability analysis and heuristics to avoid some unnecessary backups. However, none of these approaches fully exploit the graphical features of the MDPs or use these features to yield the best backup sequence of the state space. We introduce an algorithm named Topological Value Iteration (TVI) that can circumvent the problem of unnecessary backups by detecting the structure of MDPs and backing up states based on topological sequences. We prove that the backup sequenceValue Iteration is an inefficient algorithm for Markov decision processes (MDPs) because it puts the majority of its effort into backing up the entire state space, which turns out to be unnecessary in many cases. In order to overcome this problem, many approaches have been proposed. Among them, LAO*, LRTDP and HDP are state-of-the-art ones. All of these use reachability analysis and heuristics to avoid some unnecessary backups. However, none of these approaches fully exploit the graphical features of the MDPs or use these features to yield the best backup sequence of the state space. We introduce an algorithm named Topological Value Iteration (TVI) that can circumvent the problem of unnecessary backups by detecting the structure of MDPs and backing up states based on topological sequences. We prove that the backup sequence TVI applies is optimal. Our experimental results show that TVI outperforms VI, LAO*, LRTDP and HDP on our benchmark MDPs. TVI applies is optimal. Our experimental results show that TVI outperforms VI, LAO*, LRTDP and HDP on our benchmark MDPs.

  1. Topological Value Iteration TVI(MDP M , δ) 1 . scc(M ) 2 . for i ← 1 to cpntnum;
  2. S ← the set of states s where s.id = cpntnum
  3. vi(S, δ) vi(S: a set of states, δ) 5 . while (true) 6 . for each state s ∈ S 7 . V (s) = min a∈A(s) [
  4. C(s) + γ s ∈S T a (s |s)V (s )] 8 . if (Bellman error is less than δ)
  5. return scc(MDP M ) (Kosaraju's algorithm)
  6. construct G cr from M by removing action nodes 11. construct the reverse graph G cr of G cr 12. size ← number of states in G cr 13. for s ← 1 to size 14. s.id ← -1 15. // postR and postI are two arrays of length size 16. cnt ← 1, cpntnum ← 1 17. for s ← 1 to size 18. if (s.id = -1)
  7. df s(G , s) 20. for s ← 1 to size 21. postR[s] ← postI[s] 22. cnt ← 1, cpntnum ← 1 23. for s ← 1 to size 24. s.id ← -1 25. for s ← 1 to size 26. if (s.id = -1)
  8. return (cpntnum, G cr ) dfs(Graph G, s) 30. s.id ← cpntnum 31. for each successor s of s 32. if (s .id = -1)
  9. [Barto, Bradke, & Singh, 1995] Barto, A.; Bradke, S.; and Singh, S. 1995. Learning to act using real-time dynamic programming. JAI 72:81-138.
  10. [Bellman, 1957] Bellman, R. 1957. Dynamic Programming. Princeton, NJ: Princeton University Press.
  11. [Bonet & Geffner, 2003a] Bonet, B., and Geffner, H. 2003a. Faster heuristic search algorithms for planning with uncertainty and full feedback. In Gottlob, G., ed., Proc. of IJCAI-03, 1233-1238. IJCAI
  12. [Bonet & Geffner, 2003b] Bonet, B., and Geffner, H. 2003b. La- beled RTDP: Improving the convergence of real-time dynamic programming. In Giunchiglia, E.; Muscettola, N.; and Nau, D., eds., Proc. 13th ICAPS, 12-21. Trento, Italy: AAAI Press.
  13. [Boutilier, Dean, & Hanks, 1999] Boutilier, C.; Dean, T.; and Hanks, S. 1999. Decision-theoretic planning: Structural assump- tions and computational leverage. JAIR 11:1-94.
  14. [Cormen et al., 2001] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001.
  15. [Feng & Hansen, 2002] Feng, Z., and Hansen, E. A. 2002. Sym- bolic heuristic search for factored Markov decision processes. In Proc. of AAAI-05.
  16. [Feng, Hansen, & Zilberstein, 2003] Feng, Z.; Hansen, E. A.; and Zilberstein, S. 2003. Symbolic generalization for on-line plan- ning. In Proc. of UAI-03, 209-216.
  17. [Ferguson & Stentz, 2004] Ferguson, D., and Stentz, A. 2004. Fo- cussed dynamic programming: Extensive comparative results. Technical Report CMU-RI-TR-04-13, Carnegie Mellon Univer- sity, Pittsburgh, PA.
  18. [Guestrin et al., 2003] Guestrin, C.; Koller, D.; Parr, R.; and Venkataraman, S. 2003. Efficient solution algorithms for fac- tored MDPs. JAIR 19:399-468.
  19. [Hansen & Zilberstein, 2001] Hansen, E., and Zilberstein, S. 2001. LAO*: A heuristic search algorithm that finds solutions with loops. JAI 129:35-62.
  20. [Hoey et al., 1999] Hoey, J.; St-Aubin, R.; Hu, A.; and Boutilier, C. 1999. SPUDD: Stochastic planning using decision diagrams. In Proc. of UAI-99, 279-288.
  21. [Howard, 1960] Howard, R. 1960. Dynamic Programming and Markov Processes. Cambridge, Massachusetts: MIT Press.
  22. [Littman, Dean, & Kaelbling, 1995] Littman, M. L.; Dean, T.; and Kaelbling, L. P. 1995. On the complexity of solving Markov decision problems. In Proc. of UAI-95, 394-402.
  23. [McMahan & Gordon, 2005] McMahan, H. B., and Gordon, G. J. 2005. Fast exact planning in Markov decision processes. In Proc. of ICAPS-05.
  24. [Patrascu et al., 2002] Patrascu, R.; Poupart, P.; Schuurmans, D.; Boutilier, C.; and Guestrin, C. 2002. Greedy linear value- approximation for factored Markov decision processes. In Proc. of AAAI-02, 285-291.
  25. [Poupart et al., 2002] Poupart, P.; Boutilier, C.; Patrascu, R.; and Schuurmans, D. 2002. Piecewise linear value function approxi- mation for factored MDPs. In Proc. of AAAI-02, 292-299.
  26. [Puterman, 1994] Puterman, M. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley, New York.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards