{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T03:27:08Z","timestamp":1777865228086,"version":"3.51.4"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031959752","type":"print"},{"value":"9783031959769","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-95976-9_8","type":"book-chapter","created":{"date-parts":[[2025,6,28]],"date-time":"2025-06-28T03:53:44Z","timestamp":1751082824000},"page":"119-136","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Efficiency of\u00a0Algebraic Simplex Algorithms for\u00a0Solving MDPs"],"prefix":"10.1007","author":[{"given":"Dibyangshu","family":"Mukherjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shivaram","family":"Kalyanakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,29]]},"reference":[{"key":"8_CR1","unstructured":"Andersson, D., Vorobyov, S.: Fast Algorithms for Monotonic Discounted Linear Programs with Two Variables per Inequality. Preprint NI06019-LAA, Isaac Newton Institute for Mathematical Sciences, Cambridge, UK (2006)"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Ashutosh, K., Consul, S., Dedhia, B., Khirwadkar, P., Shah, S., Kalyanakrishnan, S.: Lower bounds for policy iteration on multi-action MDPs. In: 59th IEEE Conference on Decision and Control, CDC 2020, pp. 1744\u20131749. IEEE (2020)","DOI":"10.1109\/CDC42340.2020.9303956"},{"key":"8_CR3","volume-title":"Dynamic Programming","author":"R Bellman","year":"1957","unstructured":"Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957)"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Blackwell, D.: Discrete dynamic programming. Ann. Math. Stat. 719\u2013726 (1962)","DOI":"10.1214\/aoms\/1177704593"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-39206-1_24","volume-title":"Automata, Languages, and Programming","author":"T Brunsch","year":"2013","unstructured":"Brunsch, T., R\u00f6glin, H.: Finding short paths on polytopes by the shadow vertex algorithm. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 279\u2013290. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39206-1_24"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Improved deterministic algorithms for linear programming in low dimensions. ACM Trans. Algorithms 14(3), 30:1\u201330:10 (2018)","DOI":"10.1145\/3155312"},{"issue":"2","key":"8_CR7","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"KL Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2), 488\u2013499 (1995)","journal-title":"J. ACM"},{"key":"8_CR8","unstructured":"Dadashi, R., Bellemare, M.G., Ta\u00efga, A.A., Roux, N.L., Schuurmans, D.: The value function polytope in reinforcement learning. In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, USA, pp. 1486\u20131495. PMLR (2019)"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press (1963)","DOI":"10.7249\/R366"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1007\/s10107-022-01848-x","volume":"199","author":"Y Disser","year":"2023","unstructured":"Disser, Y., Friedmann, O., Hopp, A.V.: An exponential lower bound for Zadeh\u2019s pivot rule. Math. Program. 199(1), 865\u2013936 (2023)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"8_CR11","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10107-016-1089-0","volume":"164","author":"F Eisenbrand","year":"2017","unstructured":"Eisenbrand, F., Vempala, S.S.: Geometric random edge. Math. Program. 164(1\u20132), 325\u2013339 (2017)","journal-title":"Math. Program."},{"issue":"3","key":"8_CR12","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1002\/rsa.10034","volume":"20","author":"B G\u00e4rtner","year":"2002","unstructured":"G\u00e4rtner, B.: The random-facet simplex algorithm on combinatorial cubes. Random Struct. Algorithms 20(3), 353\u2013381 (2002)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/05062370X","volume":"21","author":"B G\u00e4rtner","year":"2007","unstructured":"G\u00e4rtner, B., Kaibel, V.: Two new bounds on the random-edge simplex algorithm. SIAM J. Discret. Math. 21(1), 178\u2013190 (2007)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"8_CR14","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0166-218X(79)90004-0","volume":"1","author":"D Goldfarb","year":"1979","unstructured":"Goldfarb, D., Sit, W.Y.: Worst case behavior of the steepest edge simplex method. Discret. Appl. Math. 1(4), 277\u2013285 (1979)","journal-title":"Discret. Appl. Math."},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kalyanakrishnan, S.: Improved strong worst-case upper bounds for MDP planning. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 1788\u20131794. ijcai.org (2017)","DOI":"10.24963\/ijcai.2017\/248"},{"key":"8_CR16","unstructured":"Howard, R.A.: Dynamic Programming and Markov Processes. MIT Press (1960)"},{"issue":"4","key":"8_CR17","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0012-365X(73)90171-4","volume":"4","author":"R Jeroslow","year":"1973","unstructured":"Jeroslow, R.: The simplex algorithm with the pivot rule of maximizing criterion improvement. Discret. Math. 4(4), 367\u2013377 (1973)","journal-title":"Discret. Math."},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Kalai, G.: A subexponential randomized simplex algorithm (extended abstract). In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 475\u2013482. ACM (1992)","DOI":"10.1145\/129712.129759"},{"key":"8_CR19","unstructured":"Kalyanakrishnan, S., Mall, U., Goyal, R.: Batch-switching policy iteration. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, pp. 3147\u20133153. IJCAI\/AAAI Press (2016)"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Kalyanakrishnan, S., Misra, N., Gopalan, A.: Randomised procedures for initialising and switching actions in policy iteration. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp. 3145\u20133151. AAAI Press (2016)","DOI":"10.1609\/aaai.v30i1.10408"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp. 302\u2013311. ACM (1984)","DOI":"10.1145\/800057.808695"},{"issue":"1","key":"8_CR22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"LG Khachiyan","year":"1980","unstructured":"Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20(1), 53\u201372 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"3","key":"8_CR23","first-page":"159","volume":"3","author":"V Klee","year":"1972","unstructured":"Klee, V., Minty, G.J.: How good is the simplex algorithm. Inequalities 3(3), 159\u2013175 (1972)","journal-title":"Inequalities"},{"key":"8_CR24","unstructured":"Littman, M.L., Dean, T.L., Kaelbling, L.P.: On the complexity of solving Markov decision problems. In: UAI 1995: Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence, pp. 394\u2013402. Morgan Kaufmann (1995)"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"Madani, O., Thorup, M., Zwick, U.: Discounted deterministic Markov decision processes and discounted all-pairs shortest paths. ACM Trans. Algorithms 6(2), 33:1\u201333:25 (2010)","DOI":"10.1145\/1721837.1721849"},{"key":"8_CR26","unstructured":"Mansour, Y., Singh, S.: On the complexity of policy iteration. In: UAI 1999: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pp. 401\u2013408. Morgan Kaufmann (1999)"},{"issue":"4\/5","key":"8_CR27","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/BF01940877","volume":"16","author":"J Matousek","year":"1996","unstructured":"Matousek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16(4\/5), 498\u2013516 (1996)","journal-title":"Algorithmica"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Mausam, Kolobov, A.: Planning with Markov Decision Processes: An AI Perspective. Morgan & Claypool (2012)","DOI":"10.1007\/978-3-031-01559-5"},{"issue":"1","key":"8_CR29","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31(1), 114\u2013127 (1984)","journal-title":"J. ACM"},{"issue":"3","key":"8_CR30","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1287\/moor.12.3.441","volume":"12","author":"CH Papadimitriou","year":"1987","unstructured":"Papadimitriou, C.H., Tsitsiklis, J.N.: The complexity of Markov decision processes. Math. Oper. Res. 12(3), 441\u2013450 (1987)","journal-title":"Math. Oper. Res."},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"Post, I., Ye, Y.: The simplex method is strongly polynomial for deterministic Markov decision processes. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, pp. 1465\u20131473. SIAM (2013)","DOI":"10.1137\/1.9781611973105.105"},{"key":"8_CR32","doi-asserted-by":"crossref","unstructured":"Puterman, M.L.: Markov Decision Processes. Wiley (1994)","DOI":"10.1002\/9780470316887"},{"key":"8_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/11496915_17","volume-title":"Integer Programming and Combinatorial Optimization","author":"I Schurr","year":"2005","unstructured":"Schurr, I., Szab\u00f3, T.: Jumping doesn\u2019t help in abstract cubes. In: J\u00fcnger, M., Kaibel, V. (eds.) IPCO 2005. LNCS, vol. 3509, pp. 225\u2013235. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11496915_17"},{"issue":"10","key":"8_CR34","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"LS Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Natl. Acad. Sci. 39(10), 1095\u20131100 (1953)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"8_CR35","doi-asserted-by":"crossref","unstructured":"Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press (1998)","DOI":"10.1109\/TNN.1998.712192"},{"key":"8_CR36","doi-asserted-by":"crossref","unstructured":"Szab\u00f3, T., Welzl, E.: Unique sink orientations of cubes. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, pp. 547\u2013555. IEEE Computer Society (2001)","DOI":"10.1109\/SFCS.2001.959931"},{"key":"8_CR37","doi-asserted-by":"crossref","unstructured":"Wu, Y., Loera, J.A.D.: Geometric policy iteration for Markov decision processes. In: KDD 2022: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2070\u20132078. ACM (2022)","DOI":"10.1145\/3534678.3539478"},{"issue":"4","key":"8_CR38","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1287\/moor.1110.0516","volume":"36","author":"Y Ye","year":"2011","unstructured":"Ye, Y.: The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Math. Oper. Res. 36(4), 593\u2013603 (2011)","journal-title":"Math. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-95976-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T05:59:32Z","timestamp":1777528772000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-95976-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031959752","9783031959769"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-95976-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"29 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Melbourne, VIC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 November 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/cpaior2025","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}