A cost–based analysis for risk–averse explore–then–commit finite–time bandits

Abstract

In this article, a multi–armed bandit problem is studied in an explore–then–commit setting where the cost of pulling an arm in the experimentation (exploration) phase may not be negligible. Identifying the best arm after a pure experimentation phase to exploit it once or for a given finite number of times is the goal of the problem. Applications of this are prevalent in personalized health-care and financial investments where the frequency of exploitation is limited. In this setting, we observe that pulling the arm with the highest expected reward is not necessarily the most desirable objective for exploitation. Alternatively, we advocate the idea of risk aversion, where the objective is to compete against the arm with the best risk–return trade–off. Additionally, a trade–off between cost and regret should be considered in the case where pulling arms in the exploration phase incurs a cost. In the case that the exploration cost is not considered, we propose a class of hyper–parameter–free risk–averse algorithms, called OTE/FTE–MAB (One/Finite–Time Exploitation Multi–Armed Bandit), whose objectives are to select the arm that is most probable to reward the most in a single or finite–time exploitations. To analyze these algorithms, we define a new notion of finite–time exploitation regret for our setting of interest. We provide an upper bound of order ln $\left(\frac{1}{{\in }_r}\right)$ for the minimum number of experiments that should be done to guarantee upper bound e_r for regret. As compared with existing risk–averse bandit algorithms, our algorithms do not rely on hyper–parameters, resulting in a more robust behavior in practice. In the case that pulling an arm in the exploration phase has a cost, we propose the c–OTE–MAB algorithm for two–armed bandits that addresses the cost–regret trade–off, corresponding to exploration–exploitation trade–off, by minimizing a linear combination of cost and regret that is called cost– regret function, using a hyper–parameter. This algorithm determines an estimation of the optimal number of explorations whose cost–regret value approaches the minimum value of the cost–regret function at the rate $\frac{1}{\sqrt{n_e}}$ with an associated confidence level, where n_e is the number of explorations of each arm.

Keywords:

• Explore–then–commit bandits
• risk–averse bandits
• finite–time bandits

Acknowledgment

The authors would like to thank the anonymous reviewers for their constructive comments and suggestions that improved the quality and rigor of the article.

Additional information

Notes on contributors

Ali Yekkehkhany

Ali Yekkehkhany is a postdoctoral scholar with the Department of Industrial Engineering and Operations Research, University of California, Berkeley. He received his Ph.D. and M.Sc. degrees in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 2020 and 2017, respectively, and BSc degree in Electrical Engineering from Sharif University of Technology in 2014. His research interests include machine and reinforcement learning, queueing theory, and applied probability theory.

Ebrahim Arian

Ebrahim Arian received his MSc and BSc degrees from the Department of Industrial Engineering, Sharif University of Technology, Iran, in 2015 and 2013, respectively. He is currently a PhD student with the Department of Industrial Engineering at the University of Illinois at Urbana-Champaign. His research interests include optimization, algorithm, revenue management, pricing, and inventory management.

Rakesh Nagi

Rakesh Nagi is Donald Biggar Willett Professor of Engineering at the University of Illinois, Urbana-Champaign. He served as the Department Head of Industrial and Enterprise Systems Engineering (2013-2019). He also served as the Interim Director of the Illinois Applied Research Institute (2016 –2018). He is an affiliate faculty in Computer Science, Electrical and Computer Engineering, Coordinated Science Laboratory, and Computational Science and Engineering. Previously he served as the Chair (2006-2012) and Professor of Industrial and Systems Engineering at the University at Buffalo (SUNY) (1993-2013). He received his PhD (1991) and MS (1989) degrees in Mechanical Engineering from the University of Maryland at College Park, while he worked at the Institute for Systems Research and INRIA, France, and B.E. (1987) degree in Mechanical Engineering from University of Roorkee (now IIT-R), India. He has more than 200 journal and conference publications. Dr. Nagi's academic interests are in big graphs/data, social networks, analytics, high performance (GPU-accelerated) computing for discrete optimization and graph algorithms, production systems, applied/military operations research and data fusion using graph theoretic models.

Ilan Shomorony

Ilan Shomorony is an assistant professor of Electrical and Computer Engineering at the University of Illinois, Urbana-Champaign (UIUC), where he is a member of the Coordinated Science Laboratory. He obtained his PhD in Electrical and Computer Engineering from Cornell University in 2014 and was a postdoctoral scholar at UC Berkeley through the NSF Center for Science of Information (CSoI) until 2017. After that, he spent a year working as a researcher and data scientist at Human Longevity Inc., a personal genomics company. He received the NSF CAREER Award in 2021. His research interests include information theory, communications, and computational biology.