{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T05:37:00Z","timestamp":1791437820148,"version":"4.3.3"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585161","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"363-376","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimistic MLE: A Generic Model-Based Algorithm for Partially Observable Sequential Decision Making"],"prefix":"10.1145","author":[{"given":"Qinghua","family":"Liu","sequence":"first","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Praneeth","family":"Netrapalli","sequence":"additional","affiliation":[{"name":"Google Research, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Csaba","family":"Szepesvari","sequence":"additional","affiliation":[{"name":"DeepMind, UK \/ University of Alberta, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chi","family":"Jin","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Ilge Akkaya Marcin Andrychowicz Maciek Chociej Mateusz Litwin Bob McGrew Arthur Petron Alex Paino Matthias Plappert Glenn Powell and Raphael Ribas. 2019. Solving Rubik\u2019s cube with a robot hand. arXiv preprint arXiv:1910.07113. \t\t\t\t  Ilge Akkaya Marcin Andrychowicz Maciek Chociej Mateusz Litwin Bob McGrew Arthur Petron Alex Paino Matthias Plappert Glenn Powell and Raphael Ribas. 2019. Solving Rubik\u2019s cube with a robot hand. arXiv preprint arXiv:1910.07113."},{"key":"e_1_3_2_1_2_1","volume-title":"International Conference on Machine Learning. 263\u2013272","author":"Azar Mohammad Gheshlaghi","year":"2017","unstructured":"Mohammad Gheshlaghi Azar , Ian Osband , and R\u00e9mi Munos . 2017 . Minimax regret bounds for reinforcement learning . In International Conference on Machine Learning. 263\u2013272 . Mohammad Gheshlaghi Azar, Ian Osband, and R\u00e9mi Munos. 2017. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning. 263\u2013272."},{"key":"e_1_3_2_1_3_1","volume-title":"Conference on Learning Theory. 193\u2013256","author":"Azizzadenesheli Kamyar","year":"2016","unstructured":"Kamyar Azizzadenesheli , Alessandro Lazaric , and Animashree Anandkumar . 2016 . Reinforcement learning of POMDPs using spectral methods . In Conference on Learning Theory. 193\u2013256 . Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. 2016. Reinforcement learning of POMDPs using spectral methods. In Conference on Learning Theory. 193\u2013256."},{"key":"e_1_3_2_1_4_1","volume-title":"Superhuman AI for multiplayer poker. Science, 365, 6456","author":"Brown Noam","year":"2019","unstructured":"Noam Brown and Tuomas Sandholm . 2019. Superhuman AI for multiplayer poker. Science, 365, 6456 ( 2019 ), 885\u2013890. Noam Brown and Tuomas Sandholm. 2019. Superhuman AI for multiplayer poker. Science, 365, 6456 (2019), 885\u2013890."},{"key":"e_1_3_2_1_5_1","volume-title":"International Conference on Machine Learning. 2485\u20132522","author":"Cai Qi","year":"2022","unstructured":"Qi Cai , Zhuoran Yang , and Zhaoran Wang . 2022 . Reinforcement learning from partial observation: Linear function approximation with provable sample efficiency . In International Conference on Machine Learning. 2485\u20132522 . Qi Cai, Zhuoran Yang, and Zhaoran Wang. 2022. Reinforcement learning from partial observation: Linear function approximation with provable sample efficiency. In International Conference on Machine Learning. 2485\u20132522."},{"key":"e_1_3_2_1_6_1","volume-title":"A Joseph Hoane Jr, and Feng-hsiung Hsu","author":"Campbell Murray","year":"2002","unstructured":"Murray Campbell , A Joseph Hoane Jr, and Feng-hsiung Hsu . 2002 . Deep blue. Artificial intelligence, 134, 1-2 (2002), 57\u201383. Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. 2002. Deep blue. Artificial intelligence, 134, 1-2 (2002), 57\u201383."},{"key":"e_1_3_2_1_7_1","unstructured":"Fan Chen Yu Bai and Song Mei. 2022. Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms. arXiv preprint arXiv:2209.14990. \t\t\t\t  Fan Chen Yu Bai and Song Mei. 2022. Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms. arXiv preprint arXiv:2209.14990."},{"key":"e_1_3_2_1_8_1","volume-title":"International Conference on Machine Learning. 2826\u20132836","author":"Du Simon","year":"2021","unstructured":"Simon Du , Sham Kakade , Jason Lee , Shachar Lovett , Gaurav Mahajan , Wen Sun , and Ruosong Wang . 2021 . Bilinear classes: A structural framework for provable generalization in RL . In International Conference on Machine Learning. 2826\u20132836 . Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. 2021. Bilinear classes: A structural framework for provable generalization in RL. In International Conference on Machine Learning. 2826\u20132836."},{"key":"e_1_3_2_1_9_1","unstructured":"Yonathan Efroni Chi Jin Akshay Krishnamurthy and Sobhan Miryoosefi. 2022. Provable reinforcement learning with a short-term memory. arXiv preprint arXiv:2202.03983. \t\t\t\t  Yonathan Efroni Chi Jin Akshay Krishnamurthy and Sobhan Miryoosefi. 2022. Provable reinforcement learning with a short-term memory. arXiv preprint arXiv:2202.03983."},{"key":"e_1_3_2_1_10_1","unstructured":"Dylan J Foster Sham M Kakade Jian Qian and Alexander Rakhlin. 2021. The Statistical Complexity of Interactive Decision Making. arXiv preprint arXiv:2112.13487. \t\t\t\t  Dylan J Foster Sham M Kakade Jian Qian and Alexander Rakhlin. 2021. The Statistical Complexity of Interactive Decision Making. arXiv preprint arXiv:2112.13487."},{"key":"e_1_3_2_1_11_1","volume-title":"Empirical Processes in M-estimation. 6","author":"Geer Sara A","unstructured":"Sara A Geer , Sara van de Geer , and D Williams . 2000. Empirical Processes in M-estimation. 6 , Cambridge University Press . Sara A Geer, Sara van de Geer, and D Williams. 2000. Empirical Processes in M-estimation. 6, Cambridge University Press."},{"key":"e_1_3_2_1_12_1","unstructured":"Noah Golowich Ankur Moitra and Dhruv Rohatgi. 2022. Learning in Observable POMDPs without Computationally Intractable Oracles. arXiv preprint arXiv:2206.03446. \t\t\t\t  Noah Golowich Ankur Moitra and Dhruv Rohatgi. 2022. Learning in Observable POMDPs without Computationally Intractable Oracles. arXiv preprint arXiv:2206.03446."},{"key":"e_1_3_2_1_13_1","unstructured":"Noah Golowich Ankur Moitra and Dhruv Rohatgi. 2022. Planning in Observable POMDPs in Quasipolynomial Time. arXiv preprint arXiv:2201.04735. \t\t\t\t  Noah Golowich Ankur Moitra and Dhruv Rohatgi. 2022. Planning in Observable POMDPs in Quasipolynomial Time. arXiv preprint arXiv:2201.04735."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0933-3657(99)00042-1"},{"key":"e_1_3_2_1_15_1","unstructured":"Herbert Jaeger. 1998. Discrete-time discrete-valued observable operator models: a tutorial. GMD-Forschungszentrum Informationstechnik Darmstadt Germany. \t\t\t\t  Herbert Jaeger. 1998. Discrete-time discrete-valued observable operator models: a tutorial. GMD-Forschungszentrum Informationstechnik Darmstadt Germany."},{"key":"e_1_3_2_1_16_1","volume-title":"International Conference on Machine Learning. 1704\u20131713","author":"Jiang Nan","year":"2017","unstructured":"Nan Jiang , Akshay Krishnamurthy , Alekh Agarwal , John Langford , and Robert E Schapire . 2017 . Contextual decision processes with low Bellman rank are PAC-learnable . In International Conference on Machine Learning. 1704\u20131713 . Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. 2017. Contextual decision processes with low Bellman rank are PAC-learnable. In International Conference on Machine Learning. 1704\u20131713."},{"key":"e_1_3_2_1_17_1","volume-title":"Is Q-learning provably efficient? Advances in neural information processing systems, 31","author":"Jin Chi","year":"2018","unstructured":"Chi Jin , Zeyuan Allen-Zhu , Sebastien Bubeck , and Michael I Jordan . 2018. Is Q-learning provably efficient? Advances in neural information processing systems, 31 ( 2018 ). Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. 2018. Is Q-learning provably efficient? Advances in neural information processing systems, 31 (2018)."},{"key":"e_1_3_2_1_18_1","unstructured":"Chi Jin Sham M Kakade Akshay Krishnamurthy and Qinghua Liu. 2020. Sample-Efficient Reinforcement Learning of Undercomplete POMDPs. NeurIPS. \t\t\t\t  Chi Jin Sham M Kakade Akshay Krishnamurthy and Qinghua Liu. 2020. Sample-Efficient Reinforcement Learning of Undercomplete POMDPs. NeurIPS."},{"key":"e_1_3_2_1_19_1","volume-title":"Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34","author":"Jin Chi","year":"2021","unstructured":"Chi Jin , Qinghua Liu , and Sobhan Miryoosefi . 2021. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34 ( 2021 ). Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. 2021. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34 (2021)."},{"key":"e_1_3_2_1_20_1","volume-title":"Conference on Learning Theory. 2137\u20132143","author":"Jin Chi","year":"2020","unstructured":"Chi Jin , Zhuoran Yang , Zhaoran Wang , and Michael I Jordan . 2020 . Provably efficient reinforcement learning with linear function approximation . In Conference on Learning Theory. 2137\u20132143 . Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. 2020. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory. 2137\u20132143."},{"key":"e_1_3_2_1_21_1","first-page":"740","article-title":"Efficient reinforcement learning in factored MDPs","volume":"16","author":"Kearns Michael","year":"1999","unstructured":"Michael Kearns and Daphne Koller . 1999 . Efficient reinforcement learning in factored MDPs . In IJCAI. 16 , 740 \u2013 747 . Michael Kearns and Daphne Koller. 1999. Efficient reinforcement learning in factored MDPs. In IJCAI. 16, 740\u2013747.","journal-title":"IJCAI."},{"key":"e_1_3_2_1_22_1","volume-title":"PAC reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29","author":"Krishnamurthy Akshay","year":"2016","unstructured":"Akshay Krishnamurthy , Alekh Agarwal , and John Langford . 2016. PAC reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29 ( 2016 ). Akshay Krishnamurthy, Alekh Agarwal, and John Langford. 2016. PAC reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29 (2016)."},{"key":"e_1_3_2_1_23_1","volume-title":"Bandit algorithms","author":"Lattimore Tor","unstructured":"Tor Lattimore and Csaba Szepesv\u00e1ri . 2020. Bandit algorithms . Cambridge University Press . Tor Lattimore and Csaba Szepesv\u00e1ri. 2020. Bandit algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Jesse Levinson Jake Askeland Jan Becker Jennifer Dolson David Held Soeren Kammel J Zico Kolter Dirk Langer Oliver Pink and Vaughan Pratt. 2011. Towards fully autonomous driving: Systems and algorithms. In 2011 IEEE intelligent vehicles symposium (IV). 163\u2013168. \t\t\t\t  Jesse Levinson Jake Askeland Jan Becker Jennifer Dolson David Held Soeren Kammel J Zico Kolter Dirk Langer Oliver Pink and Vaughan Pratt. 2011. Towards fully autonomous driving: Systems and algorithms. In 2011 IEEE intelligent vehicles symposium (IV). 163\u2013168.","DOI":"10.1109\/IVS.2011.5940562"},{"key":"e_1_3_2_1_25_1","volume-title":"Predictive representations of state. Advances in neural information processing systems, 14","author":"Littman Michael","year":"2001","unstructured":"Michael Littman and Richard S Sutton . 2001. Predictive representations of state. Advances in neural information processing systems, 14 ( 2001 ). Michael Littman and Richard S Sutton. 2001. Predictive representations of state. Advances in neural information processing systems, 14 (2001)."},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of Thirty Fifth Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"5220","author":"Liu Qinghua","year":"2022","unstructured":"Qinghua Liu , Alan Chung , Csaba Szepesvari , and Chi Jin . 2022 . When Is Partially Observable Reinforcement Learning Not Scary ? In Proceedings of Thirty Fifth Conference on Learning Theory (Proceedings of Machine Learning Research , Vol. 178). PMLR, 5175\u2013 5220 . https:\/\/proceedings.mlr.press\/v178\/liu22f.html Qinghua Liu, Alan Chung, Csaba Szepesvari, and Chi Jin. 2022. When Is Partially Observable Reinforcement Learning Not Scary? In Proceedings of Thirty Fifth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 178). PMLR, 5175\u20135220. https:\/\/proceedings.mlr.press\/v178\/liu22f.html"},{"key":"e_1_3_2_1_27_1","unstructured":"Volodymyr Mnih Koray Kavukcuoglu David Silver Alex Graves Ioannis Antonoglou Daan Wierstra and Martin Riedmiller. 2013. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602. \t\t\t\t  Volodymyr Mnih Koray Kavukcuoglu David Silver Alex Graves Ioannis Antonoglou Daan Wierstra and Martin Riedmiller. 2013. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060645"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347480"},{"key":"e_1_3_2_1_30_1","volume-title":"The complexity of Markov decision processes. Mathematics of operations research, 12, 3","author":"Papadimitriou Christos H","year":"1987","unstructured":"Christos H Papadimitriou and John N Tsitsiklis . 1987. The complexity of Markov decision processes. Mathematics of operations research, 12, 3 ( 1987 ), 441\u2013450. Christos H Papadimitriou and John N Tsitsiklis. 1987. The complexity of Markov decision processes. Mathematics of operations research, 12, 3 (1987), 441\u2013450."},{"key":"e_1_3_2_1_31_1","unstructured":"Daniel Russo and Benjamin Van Roy. 2013. Eluder Dimension and the Sample Complexity of Optimistic Exploration.. In NIPS. 2256\u20132264. \t\t\t\t  Daniel Russo and Benjamin Van Roy. 2013. Eluder Dimension and the Sample Complexity of Optimistic Exploration.. In NIPS. 2256\u20132264."},{"key":"e_1_3_2_1_32_1","volume-title":"Mastering the game of go without human knowledge. nature, 550, 7676","author":"Silver David","year":"2017","unstructured":"David Silver , Julian Schrittwieser , Karen Simonyan , Ioannis Antonoglou , Aja Huang , Arthur Guez , Thomas Hubert , Lucas Baker , Matthew Lai , and Adrian Bolton . 2017. Mastering the game of go without human knowledge. nature, 550, 7676 ( 2017 ), 354\u2013359. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, and Adrian Bolton. 2017. Mastering the game of go without human knowledge. nature, 550, 7676 (2017), 354\u2013359."},{"key":"e_1_3_2_1_33_1","unstructured":"Satinder Singh Michael James and Matthew Rudary. 2012. Predictive state representations: A new theory for modeling dynamical systems. arXiv preprint arXiv:1207.4167. \t\t\t\t  Satinder Singh Michael James and Matthew Rudary. 2012. Predictive state representations: A new theory for modeling dynamical systems. arXiv preprint arXiv:1207.4167."},{"key":"e_1_3_2_1_34_1","volume-title":"Conference on learning theory. 2898\u20132933","author":"Sun Wen","year":"2019","unstructured":"Wen Sun , Nan Jiang , Akshay Krishnamurthy , Alekh Agarwal , and John Langford . 2019 . Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches . In Conference on learning theory. 2898\u20132933 . Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. 2019. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory. 2898\u20132933."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2005.1469949"},{"key":"e_1_3_2_1_36_1","unstructured":"Masatoshi Uehara Ayush Sekhari Jason D Lee Nathan Kallus and Wen Sun. 2022. Provably efficient reinforcement learning in partially observable dynamical systems. arXiv preprint arXiv:2206.12020. \t\t\t\t  Masatoshi Uehara Ayush Sekhari Jason D Lee Nathan Kallus and Wen Sun. 2022. Provably efficient reinforcement learning in partially observable dynamical systems. arXiv preprint arXiv:2206.12020."},{"key":"e_1_3_2_1_37_1","volume-title":"Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575, 7782","author":"Vinyals Oriol","year":"2019","unstructured":"Oriol Vinyals , Igor Babuschkin , Wojciech M Czarnecki , Michael Mathieu , Andrew Dudzik , Junyoung Chung , David H Choi , Richard Powell , Timo Ewalds , and Petko Georgiev . 2019. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575, 7782 ( 2019 ), 350\u2013354. Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michael Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, and Petko Georgiev. 2019. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575, 7782 (2019), 350\u2013354."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382559.2382563"},{"key":"e_1_3_2_1_39_1","volume-title":"International Conference on Machine Learning. 10746\u201310756","author":"Yang Lin","year":"2020","unstructured":"Lin Yang and Mengdi Wang . 2020 . Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound . In International Conference on Machine Learning. 10746\u201310756 . Lin Yang and Mengdi Wang. 2020. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning. 10746\u201310756."},{"key":"e_1_3_2_1_40_1","unstructured":"Wenhao Zhan Masatoshi Uehara Wen Sun and Jason D Lee. 2022. PAC Reinforcement Learning for Predictive State Representations. arXiv preprint arXiv:2207.05738. \t\t\t\t  Wenhao Zhan Masatoshi Uehara Wen Sun and Jason D Lee. 2022. PAC Reinforcement Learning for Predictive State Representations. arXiv preprint arXiv:2207.05738."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585161","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:00Z","timestamp":1750178820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":40,"alternative-id":["10.1145\/3564246.3585161","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585161","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}