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

Ali Yekkehkhany, Ebrahim Arian, Rakesh Nagi and Ilan Shomorony

IISE Transactions, 2021, vol. 53, issue 10, 1094-1108

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 (1∈r) 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 1ne with an associated confidence level, where ne is the number of explorations of each arm.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2021.1882014 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:53:y:2021:i:10:p:1094-1108

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2021.1882014

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().