{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T02:20:30Z","timestamp":1785550830125,"version":"3.56.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T00:00:00Z","timestamp":1576540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["ECCS-1847393, DMS-1839346"],"award-info":[{"award-number":["ECCS-1847393, DMS-1839346"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>We present an efficient algorithm for model-free episodic reinforcement learning on large (potentially continuous) state-action spaces. Our algorithm is based on a novel Q-learning policy with adaptive data-driven discretization. The central idea is to maintain a finer partition of the state-action space in regions which are frequently visited in historical trajectories, and have higher payoff estimates. We demonstrate how our adaptive partitions take advantage of the shape of the optimal Q-function and the joint space, without sacrificing the worst-case performance. In particular, we recover the regret guarantees of prior algorithms for continuous state-action spaces, which additionally require either an optimal discretization as input, and\/or access to a simulation oracle. Moreover, experiments demonstrate how our algorithm automatically adapts to the underlying structure of the problem, resulting in much better performance compared both to heuristics and Q-learning with uniform discretization.<\/jats:p>","DOI":"10.1145\/3366703","type":"journal-article","created":{"date-parts":[[2019,12,18]],"date-time":"2019-12-18T13:21:11Z","timestamp":1576675271000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces"],"prefix":"10.1145","volume":"3","author":[{"given":"Sean R.","family":"Sinclair","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siddhartha","family":"Banerjee","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christina Lee","family":"Yu","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,12,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Advances in Neural Information Processing Systems 21","author":"Auer Peter"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning -","volume":"70","author":"Azar Mohammad Gheshlaghi","year":"2017"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Luce Brotcorne Gilbert Laporte and Frederic Semet. 2003. Ambulance location and relocation models. European journal of operational research Vol. 147 3 (2003) 451--463.  Luce Brotcorne Gilbert Laporte and Frederic Semet. 2003. Ambulance location and relocation models. European journal of operational research Vol. 147 3 (2003) 451--463.","DOI":"10.1016\/S0377-2217(02)00364-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000024"},{"key":"e_1_2_1_5_1","unstructured":"S\u00e9bastien Bubeck Gilles Stoltz Csaba Szepesv\u00e1ri and R\u00e9mi Munos. 2009. Online optimization in X-armed bandits. In Advances in Neural Information Processing Systems. 201--208.  S\u00e9bastien Bubeck Gilles Stoltz Csaba Szepesv\u00e1ri and R\u00e9mi Munos. 2009. Online optimization in X-armed bandits. In Advances in Neural Information Processing Systems. 201--208."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3309697.3331516"},{"key":"e_1_2_1_7_1","unstructured":"Kefan Dong Yuanhao Wang Xiaoyu Chen and Liwei Wang. 2019. Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP. arXiv preprint arXiv:1901.09311 (2019).  Kefan Dong Yuanhao Wang Xiaoyu Chen and Liwei Wang. 2019. Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP. arXiv preprint arXiv:1901.09311 (2019)."},{"key":"e_1_2_1_8_1","unstructured":"Simon S Du Yuping Luo Ruosong Wang and Hanrui Zhang. 2019. Provably Efficient $ Q $-learning with Function Approximation via Distribution Shift Error Checking Oracle. arXiv preprint arXiv:1906.06321 (2019).  Simon S Du Yuping Luo Ruosong Wang and Hanrui Zhang. 2019. Provably Efficient $ Q $-learning with Function Approximation via Distribution Shift Error Checking Oracle. arXiv preprint arXiv:1906.06321 (2019)."},{"key":"e_1_2_1_9_1","volume-title":"International statistical review","author":"Gibbs Alison L","year":"2002"},{"key":"e_1_2_1_10_1","volume-title":"NeurIPS 2018 32nd Conference on Neural Information Processing Systems.","volume":"4873","author":"Jin","year":"2018"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3041838.3041877"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299873"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (Proceedings of Machine Learning Research), , Francis Bach and David Blei (Eds.)","volume":"37","author":"Lakshmanan K.","year":"2015"},{"key":"e_1_2_1_14_1","unstructured":"Tor Lattimore and Csaba Szepesv\u00e1ri. 2018. Bandit algorithms. preprint (2018).  Tor Lattimore and Csaba Szepesv\u00e1ri. 2018. Bandit algorithms. preprint (2018)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3005745.3005750"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1110069108"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-012-1064-y"},{"key":"e_1_2_1_18_1","volume-title":"Advances in Neural Information Processing Systems 25","author":"Ortner Ronald"},{"key":"e_1_2_1_19_1","volume-title":"Advances in Neural Information Processing Systems 27","author":"Osband Ian"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Martin L. Puterman. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming 1st ed.). John Wiley & Sons Inc. New York NY USA.  Martin L. Puterman. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming 1st ed.). John Wiley & Sons Inc. New York NY USA.","DOI":"10.1002\/9780470316887"},{"key":"e_1_2_1_21_1","volume-title":"Advances in Neural Information Processing Systems 31","author":"Shah Devavrat"},{"key":"e_1_2_1_22_1","unstructured":"Max Simchowitz and Kevin Jamieson. 2019. Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs. arxiv: cs.LG\/1905.03814  Max Simchowitz and Kevin Jamieson. 2019. Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs. arxiv: cs.LG\/1905.03814"},{"key":"e_1_2_1_23_1","first-page":"2533","article-title":"Contextual Bandits with Similarity Information","volume":"15","author":"Slivkins Aleksandrs","year":"2015","journal-title":"Journal of machine learning research : JMLR."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Aleksandrs Slivkins. 2019. Introduction to Multi-Armed Bandits. arxiv: cs.LG\/1904.07272  Aleksandrs Slivkins. 2019. Introduction to Multi-Armed Bandits. arxiv: cs.LG\/1904.07272","DOI":"10.1561\/9781680836219"},{"key":"e_1_2_1_25_1","unstructured":"Zhao Song and Wen Sun. 2019. Efficient Model-free Reinforcement Learning in Metric Spaces . arXiv:1905.00475 [cs stat] (May 2019). http:\/\/arxiv.org\/abs\/1905.00475 arXiv: 1905.00475.  Zhao Song and Wen Sun. 2019. Efficient Model-free Reinforcement Learning in Metric Spaces . arXiv:1905.00475 [cs stat] (May 2019). http:\/\/arxiv.org\/abs\/1905.00475 arXiv: 1905.00475."},{"key":"e_1_2_1_26_1","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction .MIT press.  Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction .MIT press."},{"key":"e_1_2_1_27_1","unstructured":"Tianyu Wang Weicheng Ye Dawei Geng and Cynthia Rudin. 2019. Towards Practical Lipschitz Stochastic Bandits . arXiv e-prints Article arXiv:1901.09277 (Jan 2019) bibinfonumpagesarXiv:1901.09277 pages.arxiv: stat.ML\/1901.09277  Tianyu Wang Weicheng Ye Dawei Geng and Cynthia Rudin. 2019. Towards Practical Lipschitz Stochastic Bandits . arXiv e-prints Article arXiv:1901.09277 (Jan 2019) bibinfonumpagesarXiv:1901.09277 pages.arxiv: stat.ML\/1901.09277"},{"key":"e_1_2_1_28_1","unstructured":"Nirandika Wanigasekara and Christina Lee Yu. 2019. Nonparametric Contextual Bandits in an Unknown Metric Space. arxiv: cs.LG\/1908.01228  Nirandika Wanigasekara and Christina Lee Yu. 2019. Nonparametric Contextual Bandits in an Unknown Metric Space. arxiv: cs.LG\/1908.01228"},{"key":"e_1_2_1_29_1","unstructured":"Christopher John Cornish Hellaby Watkins. 1989. Learning from delayed rewards. (1989).  Christopher John Cornish Hellaby Watkins. 1989. Learning from delayed rewards. (1989)."},{"key":"e_1_2_1_30_1","volume-title":"Sample-Optimal Parametric Q-Learning Using Linearly Additive Features. In International Conference on Machine Learning. 6995--7004","author":"Yang Lin","year":"2019"},{"key":"e_1_2_1_31_1","unstructured":"Lin F Yang Chengzhuo Ni and Mengdi Wang. 2019. Learning to Control in Metric Space with Optimal Regret. arXiv preprint arXiv:1905.01576 (2019).  Lin F Yang Chengzhuo Ni and Mengdi Wang. 2019. Learning to Control in Metric Space with Optimal Regret. arXiv preprint arXiv:1905.01576 (2019)."},{"key":"e_1_2_1_32_1","unstructured":"Lin F. Yang and Mengdi Wang. 2019 b. Reinforcement Leaning in Feature Space: Matrix Bandit Kernels and Regret Bound . arXiv:1905.10389 [cs stat] (May 2019). http:\/\/arxiv.org\/abs\/1905.10389 arXiv: 1905.10389.  Lin F. Yang and Mengdi Wang. 2019 b. Reinforcement Leaning in Feature Space: Matrix Bandit Kernels and Regret Bound . arXiv:1905.10389 [cs stat] (May 2019). http:\/\/arxiv.org\/abs\/1905.10389 arXiv: 1905.10389."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366703","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3366703","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3366703","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:39Z","timestamp":1750203879000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366703"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,17]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,12,17]]}},"alternative-id":["10.1145\/3366703"],"URL":"https:\/\/doi.org\/10.1145\/3366703","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,17]]},"assertion":[{"value":"2019-12-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}