{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T12:14:58Z","timestamp":1680437698051},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"BSF","award":["2006261"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,3]]},"abstract":"\n We present algorithms for finding optimal strategies for discounted, infinite-horizon, Determinsitc Markov Decision Processes (DMDPs). Our fastest algorithm has a worst-case running time of\n O<\/jats:italic>\n (\n mn<\/jats:italic>\n ), improving the recent bound of\n O<\/jats:italic>\n (\n mn<\/jats:italic>\n 2<\/jats:sup>\n ) obtained by Andersson and Vorbyov [2006]. We also present a randomized\n O<\/jats:italic>\n (\n m<\/jats:italic>\n 1\/2<\/jats:sup>\n n<\/jats:italic>\n 2<\/jats:sup>\n )-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving an\n O<\/jats:italic>\n (\n mn<\/jats:italic>\n 2<\/jats:sup>\n )-time algorithm that can be obtained using ideas of Papadimitriou and Tsitsiklis [1987].\n <\/jats:p>","DOI":"10.1145\/1721837.1721849","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"page":"1-25","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Discounted deterministic Markov decision processes and discounted all-pairs shortest paths"],"prefix":"10.1145","volume":"6","author":[{"given":"Omid","family":"Madani","sequence":"first","affiliation":[{"name":"SRI International, Menlo Park, CA"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"AT&T Labs - Research, Florham Park, NJ"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2010,4,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aho A. Hopcroft J. and Ullman J. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley. Aho A. Hopcroft J. and Ullman J. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley."},{"key":"e_1_2_1_2_1","unstructured":"Andersson D. and Vorobyov S. 2006. Fast algorithms for monotonic discounted linear programs with two variables per inequality. Tech. rep. NI06019-LAA Isaac Newton Institute for Mathematical Sciences Cambridge UK. Andersson D. and Vorobyov S. 2006. Fast algorithms for monotonic discounted linear programs with two variables per inequality. Tech. rep. NI06019-LAA Isaac Newton Institute for Mathematical Sciences Cambridge UK."},{"key":"e_1_2_1_3_1","volume-title":"Dynamic Programming","author":"Bellman R.","unstructured":"Bellman , R. 1957. Dynamic Programming . Princeton University Press . Bellman, R. 1957. Dynamic Programming. Princeton University Press."},{"key":"e_1_2_1_4_1","volume-title":"Dynamic Programming and Optimal Control","author":"Bertsekas D.","unstructured":"Bertsekas , D. 2001. Dynamic Programming and Optimal Control , 2 nd Ed. Athena Scientific . Bertsekas, D. 2001. Dynamic Programming and Optimal Control, 2nd Ed. Athena Scientific.","edition":"2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.041"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Blum L. Cucker F. Shub M. and Smale S. 1997. Complexity and Real Computation. Springer. Blum L. Cucker F. Shub M. and Smale S. 1997. Complexity and Real Computation. Springer.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791256325"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"e_1_2_1_9_1","unstructured":"Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms 2nd Ed. The MIT Press. Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms 2nd Ed. The MIT Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027084.1027085"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.10.1.98"},{"key":"e_1_2_1_12_1","volume-title":"Finite State Markov Decision Processes","author":"Derman C.","unstructured":"Derman , C. 1972. Finite State Markov Decision Processes . Academic Press . Derman, C. 1972. Finite State Markov Decision Processes. Academic Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768705"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX). 1--13","author":"Georgiadis L.","unstructured":"Georgiadis , L. , Goldberg , A. , Tarjan , R. , and Werneck , R . 2009. An experimental study of minimum mean cycle algorithms . In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX). 1--13 . Georgiadis, L., Goldberg, A., Tarjan, R., and Werneck, R. 2009. An experimental study of minimum mean cycle algorithms. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX). 1--13."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(88)90012-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-0175-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251876"},{"key":"e_1_2_1_19_1","volume-title":"Dynamic Programming and Markov Processes","author":"Howard R.","unstructured":"Howard , R. 1960. Dynamic Programming and Markov Processes . MIT Press . Howard, R. 1960. Dynamic Programming and Markov Processes. MIT Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90011-0"},{"key":"e_1_2_1_22_1","first-page":"191","article-title":"A polynomial time algorithm in linear programming","volume":"20","author":"Khachiyan L.","year":"1979","unstructured":"Khachiyan , L. 1979 . A polynomial time algorithm in linear programming . Soviet Math. Dokl. 20 , 191 -- 194 . Khachiyan, L. 1979. A polynomial time algorithm in linear programming. Soviet Math. Dokl. 20, 191--194.","journal-title":"Soviet Math. Dokl."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence (UAI). 394--402","author":"Littman M.","unstructured":"Littman , M. , Dean , T. , and Kaelbling , L . 1995. On the complexity of solving markov decision problems . In Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence (UAI). 394--402 . Littman, M., Dean, T., and Kaelbling, L. 1995. On the complexity of solving markov decision problems. In Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence (UAI). 394--402."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1035"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 273--278","author":"Madani O.","year":"2002","unstructured":"Madani , O. 2002 a. On policy iteration as a Newton's method and polynomial policy iteration algorithms . In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 273--278 . Madani, O. 2002a. On policy iteration as a Newton's method and polynomial policy iteration algorithms. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 273--278."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI). 311--318","author":"Madani O.","year":"2002","unstructured":"Madani , O. 2002 b. Polynomial value iteration algorithms for detrerminstic MDPs . In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI). 311--318 . Madani, O. 2002b. Polynomial value iteration algorithms for detrerminstic MDPs. In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI). 311--318."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI). 401--408","author":"Mansour Y.","unstructured":"Mansour , Y. , and Singh , S . 1999. On the complexity of policy iteration . In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI). 401--408 . Mansour, Y., and Singh, S. 1999. On the complexity of policy iteration. In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI). 401--408."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.2.188"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 6th International Conference on Machine Learning (ICML). 278--287","author":"Ng A.","unstructured":"Ng , A. , Harada , D. , and Russell , S . 1999. Policy invariance under reward transformations: Theory and application to reward shaping . In Proceedings of the 6th International Conference on Machine Learning (ICML). 278--287 . Ng, A., Harada, D., and Russell, S. 1999. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the 6th International Conference on Machine Learning (ICML). 278--287."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.441"},{"key":"e_1_2_1_33_1","volume-title":"Markov Decision Processes","author":"Puterman M.","unstructured":"Puterman , M. 1994. Markov Decision Processes . Wiley . Puterman, M. 1994. Markov Decision Processes. Wiley."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.39.10.1953"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220006"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0149"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210206"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00188-3"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721837.1721849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T06:44:50Z","timestamp":1672296290000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721849"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721837.1721849"],"URL":"http:\/\/dx.doi.org\/10.1145\/1721837.1721849","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":["Mathematics (miscellaneous)"],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2008-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}