{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,8]],"date-time":"2023-09-08T10:37:10Z","timestamp":1694169430437},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>Can we solve finite-horizon Markov decision processes (FHMDPs) while raising low memory requirements? Such models find application in many cases where a decision-making agent needs to act in a probabilistic environment, from resource management to medicine to service provisioning. However, computing optimal policies such an agent should follow by dynamic programming value iteration raises either prohibitive space complexity, or, in reverse, non-scalable time complexity requirements. This scalability question has been largely neglected. In this paper, we propose SIFTER (Space Efficient Finite Horizon MDPs), a suite of algorithms that achieve a golden middle between space and time requirements. Our former algorithm raises space complexity growing with the square root of the horizon's length without a time-complexity overhead, while the latter's space requirements depend only logarithmically in horizon length with a corresponding logarithmic time complexity overhead. A thorough experimental study under diverse settings confirms that SIFTER algorithms achieve the predicted gains, while approximation techniques do not achieve the same combination of time efficiency, space efficiency, and result quality.<\/jats:p>","DOI":"10.14778\/3561261.3561269","type":"journal-article","created":{"date-parts":[[2022,11,16]],"date-time":"2022-11-16T15:32:50Z","timestamp":1668612770000},"page":"90-98","source":"Crossref","is-referenced-by-count":1,"title":["SIFTER"],"prefix":"10.14778","volume":"16","author":[{"given":"Konstantinos","family":"Skitsas","sequence":"first","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis G.","family":"Papageorgiou","sequence":"additional","affiliation":[{"name":"NTU Athens"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad Sadegh","family":"Talebi","sequence":"additional","affiliation":[{"name":"University of Copenhagen"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Verena","family":"Kantere","sequence":"additional","affiliation":[{"name":"NTU Athens"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael N.","family":"Katehakis","sequence":"additional","affiliation":[{"name":"Rutgers University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiotis","family":"Karras","sequence":"additional","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ICML (Proc. of Machine Learning Research","volume":"272","author":"Azar Mohammad Gheshlaghi","year":"2017","unstructured":"Mohammad Gheshlaghi Azar , Ian Osband , and R\u00e9mi Munos . 2017 . Minimax Regret Bounds for Reinforcement Learning . In ICML (Proc. of Machine Learning Research , Vol. 70). 263-- 272 . Mohammad Gheshlaghi Azar, Ian Osband, and R\u00e9mi Munos. 2017. Minimax Regret Bounds for Reinforcement Learning. In ICML (Proc. of Machine Learning Research, Vol. 70). 263--272."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-020-03706-5"},{"key":"e_1_2_1_3_1","first-page":"679","article-title":"A Markovian Decision Process","volume":"6","author":"Bellman Richard E.","year":"1957","unstructured":"Richard E. Bellman . 1957 . A Markovian Decision Process . Journal of Mathematics and Mechanics 6 , 5 (1957), 679 -- 684 . Richard E. Bellman. 1957. A Markovian Decision Process. Journal of Mathematics and Mechanics 6, 5 (1957), 679--684.","journal-title":"Journal of Mathematics and Mechanics"},{"key":"e_1_2_1_4_1","volume-title":"Dynamic programming and optimal control","author":"Bertsekas Dimitri P.","unstructured":"Dimitri P. Bertsekas . 2017. Dynamic programming and optimal control ( 4 th ed.). Vol. 1 . Athena Scientific . Dimitri P. Bertsekas. 2017. Dynamic programming and optimal control (4th ed.). Vol. 1. Athena Scientific.","edition":"4"},{"key":"e_1_2_1_5_1","volume-title":"ICML (Proc. of Machine Learning Research","volume":"1066","author":"Bourel Hippolyte","year":"2020","unstructured":"Hippolyte Bourel , Odalric Maillard , and Mohammad Sadegh Talebi . 2020 . Tightening Exploration in Upper Confidence Reinforcement Learning . In ICML (Proc. of Machine Learning Research , Vol. 119). 1056-- 1066 . Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. 2020. Tightening Exploration in Upper Confidence Reinforcement Learning. In ICML (Proc. of Machine Learning Research, Vol. 119). 1056--1066."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.1.222"},{"key":"e_1_2_1_7_1","volume-title":"Markov Decision Process Routing Games. In 8th Intl Conf. on Cyber-Physical Systems (ICCPS). 273--279","author":"Calderone Dan","unstructured":"Dan Calderone and S. Shankar Sastry . 2017 . Markov Decision Process Routing Games. In 8th Intl Conf. on Cyber-Physical Systems (ICCPS). 273--279 . Dan Calderone and S. Shankar Sastry. 2017. Markov Decision Process Routing Games. In 8th Intl Conf. on Cyber-Physical Systems (ICCPS). 273--279."},{"key":"e_1_2_1_8_1","volume-title":"Markov Decision Process (MDP) Framework for Optimizing Software on Mobile Phones. In 7th ACM Intl Conf. on Embedded Software (EMSOFT). 11--20","author":"Cheung Tang Lung","year":"2009","unstructured":"Tang Lung Cheung , Kari Okamoto , Frank Maker , Xin Liu , and Venkatesh Akella . 2009 . Markov Decision Process (MDP) Framework for Optimizing Software on Mobile Phones. In 7th ACM Intl Conf. on Embedded Software (EMSOFT). 11--20 . Tang Lung Cheung, Kari Okamoto, Frank Maker, Xin Liu, and Venkatesh Akella. 2009. Markov Decision Process (MDP) Framework for Optimizing Software on Mobile Phones. In 7th ACM Intl Conf. on Embedded Software (EMSOFT). 11--20."},{"key":"e_1_2_1_9_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). The MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press.","edition":"3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964818000529"},{"key":"e_1_2_1_11_1","volume-title":"Daniel S Weld Mausam, and Daniel S Weld","author":"Dai Peng","year":"2008","unstructured":"Peng Dai , Daniel S Weld Mausam, and Daniel S Weld . 2008 . Partitioned External-Memory Value Iteration.. In AAAI. 898--904. Peng Dai, Daniel S Weld Mausam, and Daniel S Weld. 2008. Partitioned External-Memory Value Iteration.. In AAAI. 898--904."},{"key":"e_1_2_1_12_1","volume-title":"External Memory Value Iteration. In 17th Intl Conf. on Automated Planning and Scheduling (ICAPS). 128--135","author":"Edelkamp Stefan","year":"2007","unstructured":"Stefan Edelkamp , Shahid Jabbar , and Blai Bonet . 2007 . External Memory Value Iteration. In 17th Intl Conf. on Automated Planning and Scheduling (ICAPS). 128--135 . Stefan Edelkamp, Shahid Jabbar, and Blai Bonet. 2007. External Memory Value Iteration. In 17th Intl Conf. on Automated Planning and Scheduling (ICAPS). 128--135."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2010.5706896"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artmed.2011.06.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1030.0022"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859902"},{"key":"e_1_2_1_17_1","unstructured":"Lodewijk Kallenberg. 2020. Lecture Notes Markov Decision Problems. https:\/\/www.math.leidenuniv.nl\/~kallenberg\/Lecture-notes-MDP.pdf  Lodewijk Kallenberg. 2020. Lecture Notes Markov Decision Problems. https:\/\/www.math.leidenuniv.nl\/~kallenberg\/Lecture-notes-MDP.pdf"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386124"},{"key":"e_1_2_1_19_1","unstructured":"Erwan Lecarpentier and Emmanuel Rachelson. 2019. Non-Stationary Markov Decision Processes a Worst-Case Approach using Model-Based Reinforcement Learning. In NeurIPS. 7214--7223.  Erwan Lecarpentier and Emmanuel Rachelson. 2019. Non-Stationary Markov Decision Processes a Worst-Case Approach using Model-Based Reinforcement Learning. In NeurIPS. 7214--7223."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0912"},{"key":"e_1_2_1_21_1","unstructured":"Yuxi Li. 2019. Reinforcement Learning Applications. arXiv:1908.06973 [cs.LG]  Yuxi Li. 2019. Reinforcement Learning Applications. arXiv:1908.06973 [cs.LG]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257928"},{"key":"e_1_2_1_23_1","volume-title":"L-opacity: Linkage-Aware Graph Anonymization. In EDBT. 583--594.","author":"Nobari Sadegh","year":"2014","unstructured":"Sadegh Nobari , Panagiotis Karras , HweeHwa Pang , and St\u00e9phane Bressan . 2014 . L-opacity: Linkage-Aware Graph Anonymization. In EDBT. 583--594. Sadegh Nobari, Panagiotis Karras, HweeHwa Pang, and St\u00e9phane Bressan. 2014. L-opacity: Linkage-Aware Graph Anonymization. In EDBT. 583--594."},{"key":"e_1_2_1_24_1","unstructured":"Ian Osband Daniel Russo and Benjamin Van Roy. 2013. (More) Efficient Reinforcement Learning via Posterior Sampling. In NeurIPS. 3003--3011.  Ian Osband Daniel Russo and Benjamin Van Roy. 2013. (More) Efficient Reinforcement Learning via Posterior Sampling. In NeurIPS. 3003--3011."},{"key":"e_1_2_1_25_1","volume-title":"Markov decision processes: discrete stochastic dynamic programming","author":"Puterman Martin L.","unstructured":"Martin L. Puterman . 2014. Markov decision processes: discrete stochastic dynamic programming . John Wiley & Sons . Martin L. Puterman. 2014. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.14.5.292"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.08.009"},{"key":"e_1_2_1_28_1","volume-title":"Algorithmic Learning Theory (Proc. of Machine Learning Research","volume":"805","author":"Talebi Mohammad Sadegh","year":"2018","unstructured":"Mohammad Sadegh Talebi and Odalric-Ambrym Maillard . 2018 . Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs . In Algorithmic Learning Theory (Proc. of Machine Learning Research , Vol. 83). 770-- 805 . Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. 2018. Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs. In Algorithmic Learning Theory (Proc. of Machine Learning Research, Vol. 83). 770--805."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236263"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3464389"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1993.181"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3561261.3561269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:21:41Z","timestamp":1672219301000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3561261.3561269"}},"subtitle":["space-efficient value iteration for finite-horizon MDPs"],"short-title":[],"issued":{"date-parts":[[2022,9]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.14778\/3561261.3561269"],"URL":"https:\/\/doi.org\/10.14778\/3561261.3561269","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,9]]}}}