The stochastic multi-armed bandit problem is a well-known model for studying the explorationexploitation trade-off. It has significant possible applications in adaptive clinical trials, which allow for dynamic changes in the treatment allocation probabilities of patients. However, most bandit learning algorithms are designed with the goal of minimizing the expected regret. While this approach is useful in many areas, in clinical trials, it can be sensitive to outlier data, especially when the sample size is small. In this paper, we define and study a new robustness criterion for bandit problems. Specifically, we consider optimizing a function of the distribution of returns as a regret measure. This provides practitioners more flexibility to define an appropriate regret measure. The learning algorithm we propose to solve this type of problem is a modification of the BESA algorithm [Baransi et al., 2014], which considers a more general version of regret. We present a regret bound for our approach and evaluate it empirically both on synthetic problems as well as on a dataset from the clinical trial literature. Our approach compares favorably to a suite of standard bandit algorithms. Finally, we provide a web application where users can create their desired synthetic bandit environment and compare the performance of different bandit algorithms online.
The multi-armed bandit is a standard model for researchers to investigate the exploration-exploitation trade-off, see e.g [Baransi et al., 2014; Auer et al., 2002; Sani et al., 2012a; Chapelle and Li, 2011; Sutton and Barto, 1998]. One of the main advantage of multi-armed bandit problems is its simplicity that allows for a higher level of theoretical studies.
The multi-armed bandit problem consists of a set of arms, each of which generates a stochastic reward from a fixed but unknown distribution associated to it. Consider a series of mulitple arm pulls (or steps) t = 1; :::; T and selecting a specific arm a 2 A at each step i.e. a(t) = at. The standard goal hossein.aboutalebi@mail.mcgill.ca in the multi-armed bandit setting is to find the arm ? which has the maximum expected reward ? (or equivalently, minimum expected regret). The expected regret after T steps RT is defined as the sum of the expected difference between the mean reward under fatg and the reward expected under the optimal arm ?:
RT = E " T
X( ? at )
# t=1
While this objective is very popular, there are practical applications, for example in medical research and AI safety [Garcıa and Ferna´ndez, 2015] where maximizing expected value is not sufficient, and it would be better to have an algorithm sensitive also to the variability of the outcomes of a given arm. For example, consider multi-arm clinical trials where the objective is to find the most promising treatment among a pool of available treatments. Due to heterogeneity in patients’ treatment responses, considering only the expected mean may not be of interest [Austin, 2011]. Specifically, as the mean is usually sensitive to outliers and does not provide information about the dispersion of individual responses, the expected reward has only limited value in achieving a clinical trial’s objective. Due to these problems, previous contributions like [Sani et al., 2012a] try to include the variance of rewards in the regret definition and develop algorithms to solve this slightly enhanced problem. While these modified approaches try to consider variablity in the response of arms, they induce new problems due to the fact that the variance is not necessarily a good measure of variablity for a distribution. This is because the variance equally penalizes responses that are above or below the mean response. Other articles like [Galichet et al., 2013] try to use the conditional value at risk to define a better regret definition. Though the conditional value at risk may address the problem we faced with including variance, it may not reflect the amount of variablity we could observe for a distribution over its entire domain. All in all, the consistency of treatments among patients is essential, with the ideal treatment usually defined as the one which has a high positive response rate while showing low variability in response among patients. Thus, the idea of consistency and saftey seems to some extent subjective and problem dependant. As a result, it might be necessary to develop an algorithm which can work with an arbitrary definition of consistency for a distribution.
This kind of system design which allows the separation of different parts of a system (here regret function and learning algorithm) has already been explored in modular programming. In modular programming, we emphasize on splitting the entire system into independant modules which at the end, the composite of these modules builds our system. This design trick is necessary when we are dealing with the change of customer demands and we require our system to adapt with the new demands. Here, we follow the same paradigm by making regret definition independent of the learning algorithm. As a result, we allow more flexibility in defining the regret function which is capable of incorporating problem specific demands.
Finally, we achieve the aforementioned goals by extending one of the recent algorithms in the bandit literature called BESA (Best Empirical Sampled Average) [Baransi et al., 2014]. One of the main advantage of BESA compared to other existing bandit algorithms is that it does not involve many hyper-parameters. This is especially useful when one does not have any prior knowledge or has insufficient prior knowledge about the different arms in the beginning. Also, this feature makes it easier to introduce modular design by using McDiarmid’s Lemma [El-Yaniv and Pechyony, 2009].
Key contributions: We provide a modular definition of regret called safety-aware regret which allows higher flexibility in defining the risk for multi-armed bandit problems. We propose a new algorithm called BESA+ which solves this category of problems. We show the upper-bounds of its safetyaware regret for two-armed and multi-armed bandits. For the experiment parts, we compare our model with some of the notable earlier research works and show that BESA+ has a satisfying performance. For the last experiment, we depict the performance of our algorithm on a real clinical dataset and illustrate that it is capable of solving the problem with user-defined safety-aware regret. Finally, for the first time as far as we know, we provide a web application which allows users to create their own custom environment and compare our algorithm with other works.
We consider the standard bandit setting with action (arm) set A, where each action a 2 A is characterized by a reward distribution 'a. The distribution for action a has mean a and variance a2. Let Xa;i 'a denote the i-th reward sampled from the distribution of action a. All actions and samples are independent. The bandit problem is described as an iterative game where, on each step (round) t, the player (an algorithm) selects action (arm) at and observes sample Xa;Na;t , where Na;t = Pts=1 Ifas = ag denotes the number of samples observed for action a up to time t (inclusively). A policy is a distribution over A. In general, stochastic distributions are necessary during the learning stage, in order to identify the best arm. We discuss the exact notion of “best” below.
We define IS (m; j) as the set obtained by sub-sampling without replacement j elements form the set S of size m. Let Xa;t denote the history of observations (records) obtained from action (arm) a up to time t (inclusively), such that jXa;tj = Na;t. The notation Xa;t(I) indicates the set of subsamples from Xa;t, where sub-sample I f1; 2; : : : ; Na;tg.
The multi-armed bandit was first presented in the seminal work of Robbins [Robbins, 1985]. It has been shown that under certain conditions [Burnetas and Katehakis, 1996; Lai and Robbins, 1985], a policy can have logarithmic cumulative regret: lim inf t!1
Rt log(t) >
X a: a< ? ?
a Kinf (ra; r?) where Kinf (ra; r?) is the Kullback-Leibler divergence between the reward distributions of the respective arms. Policies for which this bound holds are called admissible.
Several algorithms have been shown to produce admissible policies, including UCB1 [Auer et al., 2002], Thompson sampling [Chapelle and Li, 2011; Agrawal and Goyal, 2013] and BESA [Baransi et al., 2014]. However, theoretical bounds are not always matched by empirical results. For example, it has been shown in [Kuleshov and Precup, 2014] that two algorithms which do not produce admissible policies, "-greedy and Boltzmann exploration [Sutton and Barto, 1998], behave better than UCB1 on certain problems. Both BESA and Thompson sampling were shown to have comparable performance with Softmax and "-greedy.
While the expected regret is a natural and popular measure of performance which allows the development of theoretical results, recently, some papers have explored other definitions for regret. For example, [Sani et al., 2012b] consider a linear combination of variance and mean as the definition of regret for a learning algorithm A:
MdV t(A) = bt2(A) bt(A) (1) where t is the estimate of the average of observed rewards b up to time step t and t is a biased estimate of the variance of b rewards up to time step t. The regret is then defined as: Rt(A) = MdV t(A)
MdV ?;t(A); where ? is the optimal arm. According to [Maillard, 2013], however, this definition is going to penalize the algorithm if it switches between optimal arms. Instead, in [Maillard, 2013], the authors devise a new definition of regret which controls the lower tail of the reward distribution. However, the algorithm to solve the corresponding objective function seems time-consuming, and the optimization to be performed may be intricate. Finally, in [Galichet et al., 2013], the authors use the notion of conditional value at risk in order to define the regret.
Unlike previous works, we now give a formal definition of class of functions which can be used as a separate module inside our learning algorithm module to measure the regret. We call these class of functions ”safety value functions”.
In the following section, we try to formally define these functions. Assume we have k arms (jAj = k) with reward distributions '1; '2; : : : ; 'k.
Definition 0.1. safety value function: Let D denotes the set of all possible reward distributions for a given interval. The safety value function v : D ! R provides a score for a given distribution.
The optimal arm ? under this value function is defined as ? 2 arg max(v('a))
a2A
The regret corresponding to the safety value function up to time T is defined as:
RT;v = E " T
X(v('?) t=1 v('at )) # We call (3), safety-aware regret.
When the context is clear, we usually drop the subscript v and use only RT for the ease of notation.
Definition 0.2. Well-behaved safety value function: Given a reward distribution 'a over the interval [0; 1], a safety value function v for this distribution is called well-behaved if there exists an unbiased estimator v of v such that for any set of b observation fx1; x2; : : : ; xng sampled from 'a, and for some constant we have: sup jvb(x1; : : : ; xi; : : : ; xn) xi b v(x1; : : : ; xi; : : : ; xn)j < b b If (4) holds for any reward distribution ' over the interval [0; 1], we call the safety value function v, a well-behaved safety value function.
Example 1: For a given arm a which has reward distribution limited to interval [0; 1], consider the safety value function a a2 which measures the balance between the mean and the variance of the reward distribution of arm a. is a hyper-parameter constant for adjusting the balance between variance and the mean. This is a well-behaved safety function if we use the following estimator for computing empirical mean and variance: ba;t
2 ba;t = = 1 Na;t
X ra;i Na;t i=1
1 Na;t 1
Na;t X(ra;i i=1 ba;t) 2 where ra;i is the ith reward obtained from pulling arm a. It should be clear that the unbiased estimator ba;t ba2;t satisfies (4).
Other types of well-behaved safety function can be defined as a function of standard deviation or conditional value at risk similar to the previous example. In the next section, we are going to develop an algorithm which can optimize the safetyaware regret.
In order to optimize the safety-aware regret, we build on the BESA algorithm, which we will now briefly review. As discussed in [Baransi et al., 2014], BESA is a non-parametric (2) (3) n (4) (5) (6) (without hyperparameter) approach for finding the optimal arm according to the expected mean regret criterion. Consider a two-armed bandit with actions a and ? ,where ? > a, and assume that Na;t < N?;t at time step t. In order to select the next arm for time step t + 1, BESA first sub-samples s? = I?(N?;t; Na;t) from the observation history (records) of the arm ? and similarly sub-sample sa = Ia(Na;t; Na;t) = Xa;t from the records of arm a. If bsa > bs? , BESA chooses arm a, otherwise it chooses arm ?.
The main reason behind the sub-sampling is that it gives a similar opportunity to both arms. Consequently, the effect of having a small sample size, which may cause bias in the estimates diminishes. When there are more than two arms, BESA runs a tournament algorithm on the arms [Baransi et al., 2014].
Finally, it is worth mentioning that the proof of the regret bound of BESA uses a non-trivial lemma for which authors did not provide any formal proof. In this paper, we will avoid using this lemma to prove the soundness of our proposed algorithm for a more general regret family. Also, we extend the proof for the multi-armed case which was not provided in the [Baransi et al., 2014].
We are now ready to outline our proposed approach, which we call BESA+. As in [Baransi et al., 2014], we focus on the two-arm bandit. For more than two arms, a tournament can be set up in our case as well.
Input: Safety aware value function v and its estimate v b Parameters: current time step t, actions a and b. Initially Na;0 = 0; Nb;0 = 0 1: if Na;t 1 = 0 _ Na;t 1 < log(t) then 2: at = a 3: else if Nb;t 1 = 0 _ Nb;t 1 < log(t) then 4: at = b
6: 7: 8: 9: nt 1 = minfNa;t 1; Nb;t 1g Ia;t 1 Ia(Na;t 1; nt 1) Ib;t 1 Ib(Nb;t 1; nt 1) Calculate v~a;t = vb(Xa;t 1(Ia;t 1)) and v~b;t vb(Xb;t 1(Ib;t 1)) 10: at = arg maxi2fa;bg v~i;t (break ties by choosing arm with fewer tries) 11: end if 12: return at =
If there is a strong belief that one arm should be better than the other then instead of using factor log(t) in Algorithm BESA+, one can use log(t) factor (where 0 < < 1 and is constant) to reduce the final regret.
The first major difference between BESA+ and BESA is the use of the safety-aware value function instead of the simple regret. A second important change is that BESA+ selects the arm which has been tried less up to time step t if the arm has been chosen less than log(t) times up to t. Essentially, this change in the algorithm is negligible in terms of establishing the total expected regret, as we cannot achieve any better bound than log(T ) which is shown in Robbins’ lemma [Lai and Robbins, 1985]. This tweak also turns out to be vital in proving that the expected regret of the BESA+ algorithm is bounded by log(T ) (a result which we present shortly).
To better understand why this modification is necessary, consider a two arms scenario. The first arm gives a deterministic reward of r 2 [0; 0:5) and the second arm has a uniform distribution in the interval [0,1] with the expected reward of 0.5. If we are only interested in the expected reward ( ), the algorithm should ultimately favor the second arm. On the other hand, there exists a probability of r that the BESA algorithm is going to constantly choose the first arm if the second arm gives a value less than r on its first pull. In contrast, BESA+ evades this problem by letting the second arm be selected enough times such that it eventually becomes distinguishable from the first arm.
We are now ready to state the main theoretical result of our proposed algorithm.
Theorem 0.1. Let v be a well-behaved safety value function. Assume A = fa; ?g be a two-armed bandit with bounded rewards 2 [0; 1], and the value gap = v? va. Given the value , the expected safety-aware regret of the Algorithm BESA+ up to time T is upper bounded as follows: RT 6 ; log(T ) + ; (7) ; are constants which are dependent where in (7), ; ; on the value of ; .
Proof. Due to the page limit, we could not include all the proof. Here, we just provide a short overview of the proof. The proof mainly consists of two parts. The first part of our proof is similar to [Baransi et al., 2014] but instead we have used McDiarmid’s Lemma [El-Yaniv and Pechyony, 2009] [Tolstikhin, 2017]. For the second part of the proof, unlike [Baransi et al., 2014], we have avoided using the unproven lemma in their work and instead tried to compute the upper bound directly by exploiting the log trick in our algorithm (this trick has been further elaborated in the first experiment). Interested reader can visit here to see the full proof. Theorem 0.2. Let v be a well-behaved safety value function. Assume A = fa1; : : : ; ak 1; ?g be a k-armed bandit with bounded rewards 2 [0; 1]. Without loss of generality, consider the optimal arm is ? and the value gap for arm a; ? is a = v? va. Also consider max = maxa2A a. Given the value , the expected safety-aware regret of the Algorithm BESA+ up to time T is upper bounded as follows: RT 6 maxdlog ke [ a b a; log(T ) + b a; ] + k b maxn (8) where in (8), ; are constants which are dependent on the value of ; . Moreover, a is defined:
b ba = arga2mAax a; log(T ) + a; for T > n.
Proof. We Know that the arm ? has to play at most dlog ke matches (games) in order to win the round. If it losses any of these dlog ke games, we know that at that round we will see a regret. This regret should be less than or equal to max.
In the following,We use notation 1 a?;i to denote the indicator for the event of a? losing the ith match (1 6 i 6 dlog ke).
T k RT = X X As discussed in the previous section, BESA+ has some advantages over BESA. We illustrate the example we discussed in the previous section through the results in Figures 1-3, for r 2 f0:2; 0:3; 0:4g. Each experiment has been repeated 200 times. Note that while BESA has an almost a linear regret behavior, BESA+ can learn the optimal arm within the given time horizon and its expected accumulated regret is upper bounded by a log function. It is also easy to notice that BESA+ has a faster convergence rate compared with BESA. As r gets closer to 0:5, the problem becomes harder. This phenomenon is a direct illustration of our theoretical result. 8000 10000 BESA BESA+ 400 steps 600 800 1000 MARAB Algorithm BESA+ 2000
As discussed in [Galichet et al., 2013], in some situations, we need to limit the exploration of risky arms. Examples include financial investment where inverters may tend to choose riskaverse kind of strategy. Using conditional value at risk as a risk measure is one of the approaches to achieve this goal. Informally, conditional value at risk level is defined as the expected values of the quantiles of reward distribution where the probability of the occurrence of values inside this quantile is less than or equal to . More formally:
CV aR = E[XjX < v ] (10) where in (10), v = arg max fP(X < ) 6 g. To estimate (10), we have used the estimation measure introduced by [Chen, 2007]. This estimation is also employed in [Galichet et al., 2013] work to derive their MARAB algorithm. Here, we have used this estimation for the Conditional value at risk safety value function which is the regret measure for this problem. Our environment consists of 20 arms where each arm reward distribution is the truncated Gaussian mixture consisting of four Gaussian distribution with equal probability. The reward of arms are restricted to the interval [0; 1]. To make the environment more complex, the mean and standard deviation of arms are sampled uniformly from the interval [0; 1] and [0:5; 1] respectively. The experiments are carried out for = 10%. For MARAB algorithm, we have used grid search and set the value C = 1. The figures 4, 5 depict the results of the run for ten experiments. It is noticeable that in both figures BESA+ has a lower variance in experiments. 0 200 400 600 800
1000 steps Next, we evaluated the performance of BESA+ with the regret definition provided by [Sani et al., 2012a]. Here, we used the same 20 arms Gaussian mixture environment described in the previous section. We evaluated the experiments with = 1 which is the trade off factor between variance and the mean. The results of this experiment is depicted in figures 6, 7. The hyper-parameters used here for algorithms MV-LCB and ExpExp are based on what [Sani et al., 2012a] suggests using. Again, we can see that BESA+ has a relatively small variance over 10 experiments.
Finally, we examined the performance of BESA+ against other methods (BESA, UCB1 , Thompson sampling, MVLCB, and ExpExp) based on a real clinical dataset. This dataset includes the survival times of patients who were suffering from lung cancer [Ripley et al., 2013]. Two different kinds of treatments (standard treatment and test treatment) were applied to them and the results are based on the number of days the patient survived after receiving one of the treatments. For the purpose of illustration and simplicity, we assumed non-informative censoring and equal follow-up times in both treatment groups. As the experiment has already been conducted, to apply bandit algorithms, each time a treatment is selected by a bandit algorithm, we sampled uniformly from the recorded results of the patients whom received that selected treatment and used the survival time as the reward signal. Figure 8 shows the distribution of treatment 1 and 2. We categorized the survival time into ten categories (category 1 showing the minimum survival time). It is interesting to notice that while treatment 2 has a higher mean than treatment 1 due to the effect of outliers, it has a higher level of variance compared to treatment 1. From figure 8 it is easy to deduce that treatment 1 has a more consistent behavior than treatment 2 and a higher number of patients who received treatment 2 died early. That is why treatment 1 may be preferred over treatment 2 if we use the safety value function described in Example 1. In this regard, by setting = 1, treatment 1 has less expected mean-variance regret than treatment 2, and it should be ultimately favored by the learning algorithm. Figure 9 illustrates the performance of different bandit algorithms. It is easy to notice that BESA+ has relatively better performance than all the other ones.
As discussed earlier, for this project, we have developed a web application simulator for bandit problem where users can create their customized environment and run experiments online. Usually, research works provide limited experiments to testify their method. We tried to overcome this problem by developing this web application where the user can select number of arms and change their reward distribution. Then the web application will send the input to the web-server and show the results to the user by providing regret figures and additional figures describing the way algorithms have chosen arms over time. This software can be used as a benchmark for future bandit research and it is open sourced for future steps
In this paper, we developed a modular safety-aware regret definition which can be used to define the function of interest as a safety measure. We also modified the BESA algorithm and equipped it with new features to solve modular safetyaware regret bandit problems. We then computed the asymptotic regret of BESA+ and showed that it can perform like an admissible policy if the safety value function satisfies a mild assumption. Finally, we depicted the performance of BESA+ on the regret definition of previous works and showed that it can have better performance in most cases.
It is still interesting to investigate whether we can find better bounds for BESA+ algorithm with modular safety-aware regret definition. Another interesting path would be to research if we can define similar safety-aware regret definition for broader reinforcement learning problems including MDP environments.
We would like to thank Audrey Durand for her comments and insight on this project. We also thank department of family medicine of McGill University and CIHR for their generous support during this project.