Investigation of progress and application related to Multi-Armed Bandit algorithms

Research Article
Open access

Investigation of progress and application related to Multi-Armed Bandit algorithms

Zizhuo Liu 1*
  • 1 Northeastern University    
  • *corresponding author liu.zizh@northeastern.edu
Published on 7 February 2024 | https://doi.org/10.54254/2755-2721/37/20230496
ACE Vol.37
ISSN (Print): 2755-273X
ISSN (Online): 2755-2721
ISBN (Print): 978-1-83558-299-2
ISBN (Online): 978-1-83558-300-5

Abstract

This paper discusses four Multi-armed Bandit algorithms: Explore-then-Commit (ETC), Epsilon-Greedy, Upper Confidence Bound (UCB), and Thompson Sampling algorithm. ETC algorithm aims to spend the majority of rounds on the best arm, but it can lead to a suboptimal outcome if the environment changes rapidly. The Epsilon-Greedy algorithm is designed to explore and exploit simultaneously, while it often tries sub-optimal arm even after the algorithm finds the best arm. Thus, the Epsilon-Greedy algorithm performs well when the environment continuously changes. UCB algorithm is one of the most used Multi-armed Bandit algorithms because it can rapidly narrow the potential optimal decisions in a wide range of scenarios; however, the algorithm can be influenced by some specific pattern of reward distribution or noise presenting in the environment. Thompson Sampling algorithm is also one of the most common algorithms in the Multi-armed Bandit algorithm due to its simplicity, effectiveness, and adaptability to various reward distributions. The Thompson Sampling algorithm performs well in multiple scenarios because it explores and exploits simultaneously, but its variance is greater than the three algorithms mentioned above. Today, Multi-armed bandit algorithms are widely used in advertisement, health care, and website and app optimization. Finally, the Multi-armed Bandit algorithms are rapidly replacing the traditional algorithms; in the future, the advanced Multi-armed Bandit algorithm, contextual Multi-armed Bandit algorithm, will gradually replace the old one.

Keywords:

Multi-Armed Bandit, ETC, UCB, Thompson Sampling, Epsilon-Greedy

Liu,Z. (2024). Investigation of progress and application related to Multi-Armed Bandit algorithms. Applied and Computational Engineering,37,155-159.
Export citation

References

[1]. Vermorel J Mohri M 2005 Multi-armed bandit algorithms and empirical evaluation European conference on machine learning. Berlin, Heidelberg: Springer Berlin Heidelberg 437-448

[2]. Kuleshov V Precup D 2014 Algorithms for multi-armed bandit problems arXiv preprint arXiv:1402.6028

[3]. Slivkins A 2019 Introduction to multi-armed bandits Foundations and Trends® in Machine Learning 12(1-2): 1-286.

[4]. Nie G Agarwal M Umrawal A K et al 2022 An explore-then-commit algorithm for submodular maximization under full-bandit feedback Uncertainty in Artificial Intelligence. PMLR, 1541-1551

[5]. Kuang N L Leung C H C 2019 Performance effectiveness of multimedia information search using the epsilon-greedy algorithm 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA) IEEE 929-936

[6]. Garivier A Moulines E 2011 On upper-confidence bound policies for switching bandit problems International Conference on Algorithmic Learning Theory. Berlin, Heidelberg: Springer Berlin Heidelberg 174-188

[7]. Russo D J Van Roy B Kazerouni A et al 2018 A tutorial on thompson sampling Foundations and Trends® in Machine Learning 11(1): 1-96

[8]. Auer P Cesa-Bianchi N & Fischer P 2002 Finite-time Analysis of the Multiarmed Bandit Problem Machine Learning 47, 235–256 https://doi.org/10.1023/A:1013689704352

[9]. Thompson W R 1933 On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika 25(3/4) 285–294

[10]. Aman A 2021 Thompson sampling in social media marketing Towards Data Science https://towardsdatascience.com/thompson-sampling-in-social-media-marketing-97d1892b125f

[11]. Li W et al 2010 Exploitation and exploration in a performance based contextual advertising system Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining https://doi.org/10.1145/1835804.1835811

[12]. Qiu Y Wang J Jin Z et al 2022 Pose-guided matching based on deep learning for assessing quality of action on rehabilitation training Biomedical Signal Processing and Control 72: 103323

[13]. Al-Shayea Q K 2011 Artificial neural networks in medical diagnosis International Journal of Computer Science Issues 8(2): 150-154

Cite this article

Liu,Z. (2024). Investigation of progress and application related to Multi-Armed Bandit algorithms. Applied and Computational Engineering,37,155-159.

Data availability

The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.

Disclaimer/Publisher's Note

The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

About volume

Volume title: Proceedings of the 2023 International Conference on Machine Learning and Automation

ISBN：978-1-83558-299-2(Print) / 978-1-83558-300-5(Online)
Editor：Mustafa İSTANBULLU
Conference website: https://2023.confmla.org/
Conference date: 18 October 2023
Series: Applied and Computational Engineering
Volume number: Vol.37
ISSN：2755-2721(Print) / 2755-273X(Online)

© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See Open access policy for details).

References

[1]. Vermorel J Mohri M 2005 Multi-armed bandit algorithms and empirical evaluation European conference on machine learning. Berlin, Heidelberg: Springer Berlin Heidelberg 437-448

[2]. Kuleshov V Precup D 2014 Algorithms for multi-armed bandit problems arXiv preprint arXiv:1402.6028

[3]. Slivkins A 2019 Introduction to multi-armed bandits Foundations and Trends® in Machine Learning 12(1-2): 1-286.

[4]. Nie G Agarwal M Umrawal A K et al 2022 An explore-then-commit algorithm for submodular maximization under full-bandit feedback Uncertainty in Artificial Intelligence. PMLR, 1541-1551

[5]. Kuang N L Leung C H C 2019 Performance effectiveness of multimedia information search using the epsilon-greedy algorithm 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA) IEEE 929-936

[6]. Garivier A Moulines E 2011 On upper-confidence bound policies for switching bandit problems International Conference on Algorithmic Learning Theory. Berlin, Heidelberg: Springer Berlin Heidelberg 174-188

[7]. Russo D J Van Roy B Kazerouni A et al 2018 A tutorial on thompson sampling Foundations and Trends® in Machine Learning 11(1): 1-96

[8]. Auer P Cesa-Bianchi N & Fischer P 2002 Finite-time Analysis of the Multiarmed Bandit Problem Machine Learning 47, 235–256 https://doi.org/10.1023/A:1013689704352

[9]. Thompson W R 1933 On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika 25(3/4) 285–294

[10]. Aman A 2021 Thompson sampling in social media marketing Towards Data Science https://towardsdatascience.com/thompson-sampling-in-social-media-marketing-97d1892b125f

[11]. Li W et al 2010 Exploitation and exploration in a performance based contextual advertising system Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining https://doi.org/10.1145/1835804.1835811

[12]. Qiu Y Wang J Jin Z et al 2022 Pose-guided matching based on deep learning for assessing quality of action on rehabilitation training Biomedical Signal Processing and Control 72: 103323

[13]. Al-Shayea Q K 2011 Artificial neural networks in medical diagnosis International Journal of Computer Science Issues 8(2): 150-154

For authors
Guide for authors Policies for authors Aims and scope Subscription Open access policy
For editors
Policies for editors Editorial board
For reviewers
Policies for reviewers Privacy policy

Cookies are used by this site.
Copyright © 2024 EWA Publishing, its licensors, and contributors. All rights reserved, including text and data mining, AI training, and similar technologies.