{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:12:00Z","timestamp":1760137920753,"version":"build-2065373602"},"reference-count":60,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T00:00:00Z","timestamp":1646006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Reinforcement learning with sparse rewards is still an open challenge. Classic methods rely on getting feedback via extrinsic rewards to train the agent, and in situations where this occurs very rarely the agent learns slowly or cannot learn at all. Similarly, if the agent receives also rewards that create suboptimal modes of the objective function, it will likely prematurely stop exploring. More recent methods add auxiliary intrinsic rewards to encourage exploration. However, auxiliary rewards lead to a non-stationary target for the Q-function. In this paper, we present a novel approach that (1) plans exploration actions far into the future by using a long-term visitation count, and (2) decouples exploration and exploitation by learning a separate function assessing the exploration value of the actions. Contrary to existing methods that use models of reward and dynamics, our approach is off-policy and model-free. We further propose new tabular environments for benchmarking exploration in reinforcement learning. Empirical results on classic and novel benchmarks show that the proposed approach outperforms existing methods in environments with sparse rewards, especially in the presence of rewards that create suboptimal modes of the objective function. Results also suggest that our approach scales gracefully with the size of the environment.<\/jats:p>","DOI":"10.3390\/a15030081","type":"journal-article","created":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T20:09:57Z","timestamp":1646078997000},"page":"81","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Long-Term Visitation Value for Deep Exploration in Sparse-Reward Reinforcement Learning"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3886-8131","authenticated-orcid":false,"given":"Simone","family":"Parisi","sequence":"first","affiliation":[{"name":"Meta AI Research, 4720 Forbes Avenue, Pittsburgh, PA 15213, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7193-923X","authenticated-orcid":false,"given":"Davide","family":"Tateo","sequence":"additional","affiliation":[{"name":"Department of Informatics, Technische Universit\u00e4t Darmstadt, Hochschulstr. 10, 64289 Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maximilian","family":"Hensel","sequence":"additional","affiliation":[{"name":"Department of Informatics, Technische Universit\u00e4t Darmstadt, Hochschulstr. 10, 64289 Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"D\u2019Eramo","sequence":"additional","affiliation":[{"name":"Department of Informatics, Technische Universit\u00e4t Darmstadt, Hochschulstr. 10, 64289 Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5266-8091","authenticated-orcid":false,"given":"Jan","family":"Peters","sequence":"additional","affiliation":[{"name":"Department of Informatics, Technische Universit\u00e4t Darmstadt, Hochschulstr. 10, 64289 Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joni","family":"Pajarinen","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Automation, Aalto University, Tietotekniikantalo, Konemiehentie 2, 02150 Espoo, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,28]]},"reference":[{"key":"ref_1","unstructured":"Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. (2013, January 5). Playing Atari With Deep Reinforcement Learning. Proceedings of the NIPS Workshop on Deep Learning, Lake Tahoe, CA, USA."},{"key":"ref_2","unstructured":"Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv."},{"key":"ref_3","unstructured":"Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., and Graepel, T. (2017). Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv."},{"key":"ref_4","first-page":"1","article-title":"Deep Exploration via Randomized Value Functions","volume":"20","author":"Osband","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"ref_5","unstructured":"Lillicrap, T.P., Hunt, J.J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2016, January 2). Continuous control with deep reinforcement learning. Proceedings of the International Conference on Learning Representations (ICLR), San Juan, Puerto Rico."},{"key":"ref_6","unstructured":"Kakade, S. (2003). On the Sample Complexity of Reinforcement Learning. [Ph.D. Thesis, University College London]."},{"key":"ref_7","unstructured":"Szepesvari, C. (2010). Algorithms for Reinforcement Learning, Morgan & Claypool Publishers."},{"key":"ref_8","unstructured":"Osband, I., Van Roy, B., and Wen, Z. (2016, January 19). Generalization and Exploration via Randomized Value Functions. Proceedings of the International Conference on Machine Learning (ICML), New York, NY, USA."},{"key":"ref_9","unstructured":"Osband, I., Blundell, C., Pritzel, A., and Van Roy, B. (2016, January 5). Deep exploration via bootstrapped DQN. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Barcelona, Spain."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1023\/A:1017984413808","article-title":"Near-optimal reinforcement learning in polynomial time","volume":"49","author":"Kearns","year":"2002","journal-title":"Mach. Learn."},{"key":"ref_11","first-page":"213","article-title":"R-MAX\u2014A general polynomial time algorithm for near-optimal reinforcement learning","volume":"3","author":"Brafman","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"ref_12","first-page":"1563","article-title":"Near-optimal regret bounds for reinforcement learning","volume":"11","author":"Jaksch","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s10994-012-5322-7","article-title":"TEXPLORE: Real-time sample-efficient reinforcement learning for robots","volume":"90","author":"Hester","year":"2013","journal-title":"Mach. Learn."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Strehl, A.L., Li, L., Wiewiora, E., Langford, J., and Littman, M.L. (2006, January 25). PAC model-free reinforcement learning. Proceedings of the International Conference on Machine Learning (ICML), Pittsburgh, PA, USA.","DOI":"10.1145\/1143844.1143955"},{"key":"ref_15","unstructured":"Bellemare, M.G., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. (2016, January 5). Unifying count-based exploration and intrinsic motivation. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Barcelona, Spain."},{"key":"ref_16","unstructured":"Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M.I. (2018, January 3). Is Q-learning provably efficient?. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Montreal, QC, Canada."},{"key":"ref_17","unstructured":"Dong, K., Wang, Y., Chen, X., and Wang, L. (2020, January 26). Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP. Proceedings of the International Conference on Learning Representation (ICLR), Virtual."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kolter, J.Z., and Ng, A.Y. (2009, January 24). Near-Bayesian exploration in polynomial time. Proceedings of the International Conference on Machine Learning (ICML), Montreal, QC, Canada.","DOI":"10.1145\/1553374.1553441"},{"key":"ref_19","unstructured":"Houthooft, R., Chen, X., Duan, Y., Schulman, J., De Turck, F., and Abbeel, P. (2016, January 5). VIME: Variational information maximizing exploration. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Barcelona, Spain."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Pathak, D., Agrawal, P., Efros, A.A., and Darrell, T. (2017, January 6). Curiosity-driven Exploration by Self-supervised Prediction. Proceedings of the International Conference on Machine Learning (ICML), Sydney, NSW, Australia.","DOI":"10.1109\/CVPRW.2017.70"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Puterman, M.L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley-Interscience.","DOI":"10.1002\/9780470316887"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00992698","article-title":"Q-learning","volume":"8","author":"Watkins","year":"1992","journal-title":"Mach. Learn."},{"key":"ref_23","unstructured":"Strens, M. (2000, January 29). A Bayesian framework for reinforcement learning. Proceedings of the International Conference on Machine Learning (ICML), Stanford, CA, USA."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Poupart, P., Vlassis, N., Hoey, J., and Regan, K. (2006, January 25). An analytic solution to discrete Bayesian reinforcement learning. Proceedings of the International Conference on Machine Learning (ICML), Pittsburgh, PA, USA.","DOI":"10.1145\/1143844.1143932"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1016\/0196-8858(85)90002-8","article-title":"Asymptotically Efficient Adaptive Allocation Rules","volume":"6","author":"Lai","year":"1985","journal-title":"Adv. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Auer, P., and Ortner, R. (2007, January 3). Logarithmic online regret bounds for undiscounted reinforcement learning. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Vancouver, BC, Canada.","DOI":"10.7551\/mitpress\/7503.003.0011"},{"key":"ref_27","unstructured":"Dann, C., and Brunskill, E. (2015, January 7). Sample complexity of episodic fixed-horizon reinforcement learning. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Montreal, QC, Canada."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1023\/A:1013689704352","article-title":"Finite-time analysis of the multiarmed bandit problem","volume":"47","author":"Auer","year":"2002","journal-title":"Mach. Learn."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1006\/ceps.1999.1020","article-title":"Intrinsic and extrinsic motivations: Classic definitions and new directions","volume":"25","author":"Ryan","year":"2000","journal-title":"Contemp. Educ. Psychol."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1309","DOI":"10.1016\/j.jcss.2007.08.009","article-title":"An analysis of model-based interval estimation for Markov decision processes","volume":"74","author":"Strehl","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_31","unstructured":"Raileanu, R., and Rockt\u00e4schel, T. (2020, January 26). RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environments. Proceedings of the International Conference on Learning Representations (ICLR), Virtual."},{"key":"ref_32","unstructured":"Stadie, B.C., Levine, S., and Abbeel, P. (2015, January 7). Incentivizing exploration in reinforcement learning with deep predictive models. Proceedings of the NIPS Workshop on Deep Reinforcement Learning, Montreal, QC, Canada."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Schmidhuber, J. (1991, January 25). A Possibility for lmplementing Curiosity and Boredom in Model-Building Neural Controllers. Proceedings of the International Conference on Simulation of Adaptive Behavior (SAB), Paris, France.","DOI":"10.7551\/mitpress\/3115.003.0030"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1080\/09540090600768658","article-title":"Developmental robotics, optimal artificial curiosity, creativity, music, and the fine arts","volume":"18","author":"Schmidhuber","year":"2006","journal-title":"Connect. Sci."},{"key":"ref_35","unstructured":"Pathak, D., Gandhi, D., and Gupta, A. (2019, January 9). Self-Supervised Exploration via Disagreement. Proceedings of the International Conference on Machine Learning (ICML), Long Beach, CA, USA."},{"key":"ref_36","unstructured":"Burda, Y., Edwards, H., Storkey, A., and Klimov, O. (2019, January 6). Exploration by random network distillation. Proceedings of the International Conference on Learning Representations (ICLR), New Orleans, LA, USA."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1093\/biomet\/25.3-4.285","article-title":"On the likelihood that one unknown probability exceeds another in view of the evidence of two samples","volume":"25","author":"Thompson","year":"1933","journal-title":"Biometrika"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Kaufmann, E., Korda, N., and Munos, R. (2012, January 29). Thompson sampling: An asymptotically optimal finite-time analysis. Proceedings of the International Conference on Algorithmic Learning Theory (ALT), Lyon, France.","DOI":"10.1007\/978-3-642-34106-9_18"},{"key":"ref_39","unstructured":"Agrawal, S., and Goyal, N. (2013, January 29). Further Optimal Regret Bounds for Thompson Sampling. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), Scottsdale, AZ, USA."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1002\/asmb.874","article-title":"A modern Bayesian look at the multi-armed bandit","volume":"26","author":"Scott","year":"2010","journal-title":"Appl. Stoch. Model. Bus. Ind."},{"key":"ref_41","unstructured":"Chapelle, O., and Li, L. (2011, January 12). An empirical evaluation of Thompson sampling. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Granada, Spain."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1287\/moor.2014.0650","article-title":"Learning to optimize via posterior sampling","volume":"39","author":"Russo","year":"2014","journal-title":"Math. Oper. Res."},{"key":"ref_43","unstructured":"Russo, D., Tse, D., and Van Roy, B. (2017). Time-sensitive bandit learning and satisficing thompson sampling. arXiv."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000070","article-title":"A tutorial on Thompson sampling","volume":"11","author":"Russo","year":"2018","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_45","unstructured":"Osband, I., Russo, D., and Van Roy, B. (2013, January 5). (More) efficient reinforcement learning via posterior sampling. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Lake Tahoe, CA, USA."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"D\u2019Eramo, C., Cini, A., and Restelli, M. (2019, January 14). Exploiting Action-Value Uncertainty to Drive Exploration in Reinforcement Learning. Proceedings of the International Joint Conference on Neural Networks (IJCNN), Budapest, Hungary.","DOI":"10.1109\/IJCNN.2019.8852326"},{"key":"ref_47","unstructured":"Fortunato, M., Azar, M.G., Piot, B., Menick, J., Osband, I., Graves, A., Mnih, V., Munos, R., Hassabis, D., and Pietquin, O. (2017, January 24). Noisy networks for exploration. Proceedings of the International Conference on Learning Representations (ICLR), Toulon, France."},{"key":"ref_48","unstructured":"Plappert, M., Houthooft, R., Dhariwal, P., Sidor, S., Chen, R.Y., Chen, X., Asfour, T., Abbeel, P., and Andrychowicz, M. (2018, January 3). Parameter Space Noise for Exploration. Proceedings of the International Conference on Learning Representations (ICLR), Vancouver, BC, Canada."},{"key":"ref_49","unstructured":"Gal, Y., and Ghahramani, Z. (2016, January 19). Dropout as a Bayesian approximation: Representing model uncertainty in deep learning. Proceedings of the International Conference on Machine learning (ICML), New York, NY, USA."},{"key":"ref_50","unstructured":"Osband, I. (2016, January 5). Risk versus uncertainty in deep learning: Bayes, bootstrap and the dangers of dropout. Proceedings of the NIPS Workshop on Bayesian Deep Learning, Barcelona, Spain."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Efron, B. (1982). The Jackknife, the Bootstrap and Other Resampling Plans, SIAM.","DOI":"10.1137\/1.9781611970319"},{"key":"ref_52","unstructured":"Osband, I., Aslanides, J., and Cassirer, A. (2018, January 3). Randomized prior functions for deep reinforcement learning. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Montreal, QC, Canada."},{"key":"ref_53","unstructured":"Van Hasselt, H. (2010, January 6). Double Q-learning. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Vancouver, BC, Canada."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"D\u2019Eramo, C., Nuara, A., Pirotta, M., and Restelli, M. (2017, January 20). Estimating the maximum expected value in continuous reinforcement learning problems. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), Fort Lauderdale, FL, USA.","DOI":"10.1609\/aaai.v31i1.10887"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Tateo, D., D\u2019Eramo, C., Nuara, A., Restelli, M., and Bonarini, A. (2017, January 27). Exploiting structure and uncertainty of Bellman updates in Markov decision processes. Proceedings of the Symposium Series on Computational Intelligence (SSCI), Honolulu, HI, USA.","DOI":"10.1109\/SSCI.2017.8280923"},{"key":"ref_56","unstructured":"Sutton, R.S., and Barto, A.G. (2018). Reinforcement Learning: An Introduction, The MIT Press."},{"key":"ref_57","unstructured":"Tang, H., Houthooft, R., Foote, D., Stooke, A., Chen, O.X., Duan, Y., Schulman, J., DeTurck, F., and Abbeel, P. (2017, January 24). #Exploration: A study of count-based exploration for deep reinforcement learning. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Long Beach, CA, USA."},{"key":"ref_58","unstructured":"Ostrovski, G., Bellemare, M.G., van den Oord, A., and Munos, R. (2017, January 6). Count-based exploration with neural density models. Proceedings of the International Conference on Machine Learning (ICML), Sydney, NSW, Australia."},{"key":"ref_59","unstructured":"Asadi, K., and Littman, M.L. (2017, January 6). An alternative softmax operator for reinforcement learning. Proceedings of the International Conference on Machine Learning (ICML), Sydney, NSW, Australia."},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Sutton, R.S. (1990). Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. Machine Learning, Elsevier.","DOI":"10.1016\/B978-1-55860-141-3.50030-4"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/81\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:29:22Z","timestamp":1760135362000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/81"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,28]]},"references-count":60,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["a15030081"],"URL":"https:\/\/doi.org\/10.3390\/a15030081","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,2,28]]}}}