In this paper, we study multi-armed bandit problems in explore-then-commit setting. In our proposed explore-then-commit setting, the goal is to identify the best arm after a pure experimentation (exploration) phase and exploit it once or for a given finite number of times. We identify that although the arm with the highest expected reward is the most desirable objective for infinite exploitations, it is not necessarily the one that is most probable to have the highest reward in a single or finite-time exploitations. Alternatively, we advocate the idea of risk-aversion where the objective is to compete against the arm with the best risk-return trade-off. Then, we propose two algorithms whose objectives are to select the arm that is most probable to reward the most. Using a new notion of finite-time exploitation regret, we find an upper bound for the minimum number of experiments before commitment, to guarantee an upper bound for the regret. As compared to existing risk-averse bandit algorithms, our algorithms do not rely on hyper-parameters, resulting in a more robust behavior in practice, which is verified by the numerical evaluation.
Explore-then-commit is a class of multi-armed bandit problems that has two consecutive phases named as exploration (experimentation) and commitment. The decision maker can arbitrarily explore each arm in the experimentation phase; however, he she needs to commit to one selected arm in the commitment phase. There are several studies on explore-then-commit bandits in the literature as follows. @cite_8 studied the optimal number of explorations when cost is incurred in both phases. @cite_27 designed an explore-then-commit algorithm for the case where there is a limited space to record the arm reward statistics. @cite_19 studied explore-then-commit policy under the assumption that the employed policy must split explorations into a number of batches. None of these works have addressed the risk-averse issue on explore-then-commit bandits. In the following, we present an overview on risk-averse bandits.
@cite_19 @cite_27 @cite_8
2762385100 2777439363
Motivated by practical applications, chiefly clinical trials, we study the regret achievable for stochastic bandits under the constraint that the employed policy must split trials into a small number of batches. We propose a simple policy, and show that a very small number of batches gives close to minimax optimal regret bounds. As a byproduct, we derive optimal policies with low switching cost for stochastic bandits. We consider the stochastic bandit problem in the sublinear space setting, where one cannot record the win-loss record for all @math arms. We give an algorithm using @math words of space with regret [ i=1 ^ K 1 T ] where @math is the gap between the best arm and arm @math and @math is the gap between the best and the second-best arms. If the rewards are bounded away from @math and @math , this is within an @math factor of the optimum regret possible without space constraints.