Abstract
Due to the multitude of potential courses of action, communication robots designed to satisfy the users facing them must take appropriate action more rapidly. In practice however, user requests often change while these robots are determining the most appropriate actions for these users. Therefore, it is difficult for robots to derive an appropriate course of action. This issue has been formalized as the “multi-armed bandit (MAB) problem.” The MAB problem points to an environment featuring multiple levers (arms) where pulling an arm has a certain probability of yielding a reward; the issue is to determine how to select the levers to pull to maximize the rewards gained. To solve this problem, we considered a new MAB problem algorithm using self-organizing maps that is adaptable to stationary and non-stationary environments. For this paper, numerous experiments were conducted considering a stochastic MAB problem in both stationary and non-stationary environments. As a result, we determined that the proposed algorithm demonstrated equivalent or improved capability in stationary environments with numerous arms and consistently strong effectiveness in a non-stationary environment compared to the existing UCB1, UCB1-Tuned, and Thompson Sampling algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Robbins, H.: Some aspects of the sequential design of experiments. Bull. Am. Math. Soc. 58(5), 527–535 (1952)
Sutton, R.S., Barto, A.G.: Introduction to Reinforcement Learning. MIT Press, Cambridge (1998)
Xu, M., Qin, T., Liu, T.Y.: Estimation bias in multi-armed bandit algorithms for search advertising. Adv. Neural Inf. Process. Syst. 26 (2013)
Schwartz, E.M., Bradlow, E.T., Fader, P.S.: Customer acquisition via display advertising using multi-armed bandit experiments. Market. Sci. 36(4), 500–522 (2017)
Combes, R., Jiang, C., Srikant, R.: Bandits with budgets: regret lower bounds and optimal algorithms. In: Proceedings of ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 245–257. ACM, Portland (2015)
Gasparini, M., Nuara, A., Trovò, F., Gatti, N., Restelli, M.: Targeting optimization for internet advertising by learning from logged bandit feedback. In: Proceedings of International Joint Conference on Neural Networks. IEEE, Rio (2018)
Li, L., Chu, W., Langford, J., Schapire, R.E.: A contextual-bandit approach to personalized news article recommendation. In: Proceedings of the 19th International Conference on World Wide Web, Raleigh, North Carolina, pp. 661–670, (2010)
Meshram, R., Gopalan, A., Manjunath, D.: Optimal recommendation to users that react: online learning for a class of POMDPs. In: Proceedings of 55th Conference on Decision and Control, pp. 7210–7215. IEEE, Las Vegas (2016)
Balakrishnan, A., Bouneffouf, D., Mattei, N., Rossi, F.: Using contextual bandits with behavioral constraints for constrained online movie recommendation. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, Stockholm, Sweden, pp. 5802–5804 (2018)
Wang, Q., Li, T., Iyengar, S.S., Shwartz, L., Grabarnik, G.Y.: Online IT Ticket automation recommendation using hierarchical multi-armed bandit algorithms. In: Proceedings of the 2018 SIAM International Conference on Data Mining, San Diego, CA, USA, pp. 657–665 (2018)
Korein, M., Veloso, M.: Multi-armed bandit algorithms for spare time planning of a mobile service robot. In: Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems, Stockholm, Sweden, pp. 2195–2197 (2018)
Eppner, C., Brock, O.: Visual detection of opportunities to exploit contact in grasping using contextual multi-armed bandits. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Vancouver, Canada, pp. 273–278 (2017)
Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47(2–3), 235–256 (2002)
Thompson, W.R.: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25, 285–294 (1933)
Garivier, A., Moulines, E.: On upperconfidence bound policies for non-stationary bandit problems. Algorithmic Learn. Theor., 174–188 (2011)
Larkin, L., Richard, D., Joshua, R.: Multi-armed bandit strategies for non-stationary reward distributions and delayed feedback processes. arXiv preprint arXiv:1902.08593 (2019)
Kohonen, T.: Self-organizing Maps. Springer, Heidelberg (1995). https://doi.org/10.1007/978-3-642-56927-2
Li, T., Sun, G., Yang, C., Liang, K., Ma, S., Huang, L.: Using self-organizing map for coastal water quality classification: towards a better understanding of patterns and processes. Sci. Total Environ. 628–629(1), 1446–1459 (2018)
Belkhiri, L., Mouni, L., Tiri, A., Narany, T.S., Nouibet, R.: Spatial analysis of groundwater quality using self-organizing maps. Groundwater Sustain. Dev. 7, 121–132 (2018)
Camara-Turull, X., Fernández-Izquierdo, M.Á., Sorrosal-Forradellas, M.T.: Analysing capital structure of spanish chemical companies using self-organizing maps. Kybernetes 46(6), 947–965 (2017)
Kaufmann, E., Korda, N., Munos, R.: Thompson sampling: an asymptotically optimal finite-time analysis. Algorithmic Learn. Theor., 199–213 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Manome, N., Shinohara, S., Suzuki, K., Tomonaga, K., Mitsuyoshi, S. (2019). A Multi-armed Bandit Algorithm Available in Stationary or Non-stationary Environments Using Self-organizing Maps. In: Tetko, I., Kůrková, V., Karpov, P., Theis, F. (eds) Artificial Neural Networks and Machine Learning – ICANN 2019: Theoretical Neural Computation. ICANN 2019. Lecture Notes in Computer Science(), vol 11727. Springer, Cham. https://doi.org/10.1007/978-3-030-30487-4_41
Download citation
DOI: https://doi.org/10.1007/978-3-030-30487-4_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30486-7
Online ISBN: 978-3-030-30487-4
eBook Packages: Computer ScienceComputer Science (R0)