{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:56:57Z","timestamp":1760241417178,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2018,2,28]],"date-time":"2018-02-28T00:00:00Z","timestamp":1519776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we propose an information-theoretic exploration strategy for stochastic, discrete multi-armed bandits that achieves optimal regret. Our strategy is based on the value of information criterion. This criterion measures the trade-off between policy information and obtainable rewards. High amounts of policy information are associated with exploration-dominant searches of the space and yield high rewards. Low amounts of policy information favor the exploitation of existing knowledge. Information, in this criterion, is quantified by a parameter that can be varied during search. We demonstrate that a simulated-annealing-like update of this parameter, with a sufficiently fast cooling schedule, leads to a regret that is logarithmic with respect to the number of arm pulls.<\/jats:p>","DOI":"10.3390\/e20030155","type":"journal-article","created":{"date-parts":[[2018,2,28]],"date-time":"2018-02-28T12:54:12Z","timestamp":1519822452000},"page":"155","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["An Analysis of the Value of Information When Exploring Stochastic, Discrete Multi-Armed Bandits"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7755-5886","authenticated-orcid":false,"given":"Isaac","family":"Sledge","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Florida, Gainesville, FL 32611, USA"},{"name":"Computational NeuroEngineering Laboratory (CNEL), University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9","family":"Pr\u00edncipe","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Florida, Gainesville, FL 32611, USA"},{"name":"Computational NeuroEngineering Laboratory (CNEL), University of Florida, Gainesville, FL 32611, USA"},{"name":"Department of Biomedical Engineering, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,2,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Sutton, R.S., and Barto, A.G. (1998). Reinforcement Learning: An Introduction, MIT Press.","DOI":"10.1109\/TNN.1998.712192"},{"key":"ref_2","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_3","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1090\/S0002-9904-1952-09620-8","article-title":"Some aspects of the sequential design of experiments","volume":"58","author":"Robbins","year":"1952","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000024","article-title":"Regret analysis of stochastic and non-stochastic multi-armed bandit problems","volume":"5","author":"Bubeck","year":"2012","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_5","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_6","first-page":"397","article-title":"Using confidence bounds for exploration-exploitation trade-offs","volume":"3","author":"Auer","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s10998-010-3055-6","article-title":"UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem","volume":"61","author":"Auer","year":"2010","journal-title":"Period. Math. Hung."},{"key":"ref_8","unstructured":"Garivier, A., and Capp\u00e9, O. (2011, January 24). The KL-UCB algorithm for bounded stochastic bandits and beyond. Proceedings of the Conference on Learning Theory (COLT), Budapest, Hungary."},{"key":"ref_9","first-page":"1516","article-title":"Kullback\u2013Leibler upper confidence bounds for optimal sequential allocation","volume":"41","author":"Garivier","year":"2013","journal-title":"Ann. Stat."},{"key":"ref_10","first-page":"1","article-title":"Analysis of Thompson sampling for the multi-armed bandit problem","volume":"23","author":"Agarwal","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/s10994-011-5257-4","article-title":"An asymptotically optimal policy for finite support models in the multiarmed bandit problem","volume":"85","author":"Honda","year":"2011","journal-title":"Mach. Learn."},{"key":"ref_12","first-page":"3721","article-title":"Non-asymptotic analysis if a new bandit algorithm for semi-bounded rewards","volume":"16","author":"Honda","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1023\/A:1013689704352","article-title":"Finite-time analysis of the multi-armed bandit problem","volume":"47","author":"Auer","year":"2002","journal-title":"Mach. Learn."},{"key":"ref_14","unstructured":"McMahan, H.B., and Streeter, M. (2009, January 18\u201321). Tight bounds for multi-armed bandits with expert advice. Proceedings of the Conference on Learning Theory (COLT), Montreal, QC, Canada."},{"key":"ref_15","first-page":"3","article-title":"On value of information","volume":"5","author":"Stratonovich","year":"1965","journal-title":"Izv. USSR Acad. Sci. Tech. Cybern."},{"key":"ref_16","first-page":"3","article-title":"Value of information when an estimated random variable is hidden","volume":"6","author":"Stratonovich","year":"1966","journal-title":"Izv. USSR Acad. Sci. Tech. Cybern."},{"key":"ref_17","unstructured":"Sledge, I.J., and Pr\u00edncipe, J.C. (2017). Analysis of agent expertise in Ms. Pac-Man using value-of-information-based policies. IEEE Trans. Comput. Intell. Artif. Intell. Games."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Sledge, I.J., and Pr\u00edncipe, J.C. (arxiv, 2017). Partitioning relational matrices of similarities or dissimilarities using the value of information, arxiv.","DOI":"10.1109\/ICASSP.2018.8462453"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Sledge, I.J., Emigh, M.S., and Pr\u00edncipe, J.C. (arxiv, 2018). Guided policy exploration for Markov decision processes using an uncertainty-based value-of-information criterion, arxiv.","DOI":"10.1109\/TNNLS.2018.2812709"},{"key":"ref_20","unstructured":"Cesa-Bianchi, N., and Fischer, P. (1998, January 24\u201327). Finite-time regret bounds for the multi-armed bandit problem. Proceedings of the International Conference on Machine Learning (ICML), San Francisco, CA, USA."},{"key":"ref_21","unstructured":"Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (2017). Boltzmann exploration done right. Advances in Neural Information Processing Systems (NIPS), MIT Press."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539701398375","article-title":"The nonstochastic multi-armed bandit problem","volume":"32","author":"Auer","year":"2002","journal-title":"SIAM J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1613\/jair.301","article-title":"Reinforcement learning: A survey","volume":"4","author":"Kaelbling","year":"1996","journal-title":"J. Artif. Intell. Res."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Salganicoff, M., and Ungar, L.H. (1995, January 9\u201312). Active exploration and learning in real-valued spaces using multi-armed bandit allocation indices. Proceedings of the International Conference on Machine Learning (ICML), Tahoe City, CA, USA.","DOI":"10.1016\/B978-1-55860-377-6.50066-9"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Strehl, A.L., Mesterharm, C., Littman, M.L., and Hirsh, H. (2006, January 25\u201329). Experience-efficient learning in associative bandit problems. Proceedings of the International Conference on Machine Learning (ICML), Pittsburgh, PA, USA.","DOI":"10.1145\/1143844.1143956"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Madani, O., Lizotte, S.J., and Greiner, R. (2004, January 1\u20134). The budgeted multi-armed bandit problem. Proceedings of the Conference on Learning Theory (COLT), Banff, AB, Canada.","DOI":"10.1007\/978-3-540-27819-1_46"},{"key":"ref_27","unstructured":"Saul, L.K., Weiss, Y., and Bottou, L. (2008). Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems (NIPS), MIT Press."},{"key":"ref_28","unstructured":"Koller, D., Schuurmans, D., Bengio, Y., and Bottou, L. (2008). Algorithms for infinitely many-armed bandits. Advances in Neural Information Processing Systems (NIPS), MIT Press."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1876","DOI":"10.1016\/j.tcs.2010.12.059","article-title":"Pure exploration in finitely-armed and continuous-armed bandits","volume":"412","author":"Bubeck","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Gama, J., Camacho, R., Brazdil, P.B., Jorge, A.M., and Torgo, L. (2005). Multi-armed bandit algorithms and empirical evaluation. Machine Learning: ECML, Springer.","DOI":"10.1007\/11564096"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Even-Dar, E., Mannor, S., and Mansour, Y. (2002, January 8\u201310). PAC bounds for multi-armed bandit and Markov decision processes. Proceedings of the Conference on Learning Theory (COLT), Sydney, Australia.","DOI":"10.1007\/3-540-45435-7_18"},{"key":"ref_32","first-page":"623","article-title":"The sample complexity of exploration in the multi-armed bandit problem","volume":"5","author":"Mannor","year":"2004","journal-title":"J. Mach. Learn. Res."},{"key":"ref_33","unstructured":"Platt, J.C., Koller, D., Singer, Y., and Roweis, S.T. (2008). The epoch-greedy algorithm for multi-armed bandits. Advances in Neural Information Processing Systems (NIPS), MIT Press."},{"key":"ref_34","unstructured":"Srinivas, S., Krause, A., Seeger, M., and Kakade, S.M. (2010, January 21\u201324). Gaussian process optimization in the bandit setting: No regret and experimental design. Proceedings of the International Conference on Machine Learning (ICML), Haifa, Israel."},{"key":"ref_35","unstructured":"Shawe-Taylor, J., Zemel, R.S., Bartlett, P.L., Pereira, F., and Weinberger, K.Q. (2011). Contextual Gaussian process bandit optimization. Advances in Neural Information Processing Systems (NIPS), MIT Press."},{"key":"ref_36","unstructured":"Beygelzimer, A., Langford, J., Li, L., Reyzin, L., and Schapire, R.E. (2011, January 11\u201313). Contextual bandit algorithms with supervised learning guarantees. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), Ft. Lauderdale, FL, USA."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Sledge, I.J., and Pr\u00edncipe, J.C. (2017, January 5\u20139). Balancing exploration and exploitation in reinforcement learning using a value of information criterion. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), New Orleans, LA, USA.","DOI":"10.1109\/ICASSP.2017.7952670"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1109\/TSMC.1974.5408453","article-title":"Learning automata\u2014A survey","volume":"4","author":"Narendra","year":"1974","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1109\/TSMC.1985.6313407","article-title":"A new approach to the design of reinforcement schemes for learning automata","volume":"15","author":"Thathachar","year":"1985","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1876","DOI":"10.1016\/j.tcs.2009.01.016","article-title":"Exploration-exploitation tradeoff using variance estimates in multi-armed bandits","volume":"410","author":"Audibert","year":"2009","journal-title":"Theor. Comput. Sci."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/3\/155\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:56:56Z","timestamp":1760194616000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/3\/155"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,28]]},"references-count":40,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2018,3]]}},"alternative-id":["e20030155"],"URL":"https:\/\/doi.org\/10.3390\/e20030155","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2018,2,28]]}}}