TY - JOUR
T1 - A cost–based analysis for risk–averse explore–then–commit finite–time bandits
AU - Yekkehkhany, Ali
AU - Arian, Ebrahim
AU - Nagi, Rakesh
AU - Shomorony, Ilan
N1 - Funding Information:
The authors would like to thank the anonymous reviewers for their constructive comments and suggestions that improved the quality and rigor of the article.
Publisher Copyright:
© Copyright © 2021 “IISE”.
PY - 2021
Y1 - 2021
N2 - 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 (Formula presented.) for the minimum number of experiments that should be done to guarantee upper bound er 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 (Formula presented.) with an associated confidence level, where ne is the number of explorations of each arm.
AB - 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 (Formula presented.) for the minimum number of experiments that should be done to guarantee upper bound er 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 (Formula presented.) with an associated confidence level, where ne is the number of explorations of each arm.
KW - Explore–then–commit bandits
KW - finite–time bandits
KW - risk–averse bandits
UR - http://www.scopus.com/inward/record.url?scp=85103879574&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103879574&partnerID=8YFLogxK
U2 - 10.1080/24725854.2021.1882014
DO - 10.1080/24725854.2021.1882014
M3 - Article
AN - SCOPUS:85103879574
SN - 2472-5854
VL - 53
SP - 1094
EP - 1108
JO - IIE Transactions (Institute of Industrial Engineers)
JF - IIE Transactions (Institute of Industrial Engineers)
IS - 10
ER -