Unifying the Stochastic and the Adversarial Bandits with Knapsack

1 Introduction

Sequential decision making is a fundamental task faced by any agent interacting with the environment, and the optimal (or near optimal) behavior has been studied in in a number of settings [Auer et al., 2002; Puterman, 2014; Rangi et al., 2018c; 2018b; 2018a]. Multi-Armed Bandit (MAB) is a sequential decision making problem under uncertainty that is based on balancing the trade-off between exploration and exploitation, i.e. "the conflict between taking actions whose benefits will be seen later and taking actions which yield immediate rewards." A common feature in various applications of MAB is that the resources consumed during the decision making process are limited. For instance, scientists experimenting with alternative medical treatments may be limited by the number of patients participating in the study as well as by the cost of the material used in the treatments. Similarly, in web advertisements, a website experimenting with displaying advertisements is constrained by the number of users who visit the site as well as by the advertisers' budgets. A retailer engaging in price experimentation faces inventory limits along with a limited number of consumers. A model which incorporates a budget constraint on these supply limits is Bandits with Knapsack (BwK). This can be seen as a game between a player and an adversary (or environment) that evolves for T rounds, and the player is constrained by a budget B on the resources consumed during the decision making process. At each round t ≤ T, the player performs an action i from a set of K actions, pays a cost for this action i from the budget B and receives a reward in [0, 1] for this action. The game terminates when the player runs out of the budget, therefore T is dependent on B and the player's strategy. The reward and the cost can vary from application to application. For example, in web advertisement, the reward is the click through rate and the cost is the space occupied by the advertisement on the web page. In medical trials, the reward is the success rate of the medicine and the cost corresponds to the cost of the material used.

The BwK problem can be classified into two categories: stochastic BwK and adversarial BwK. In stochastic BwK, the reward and the cost of the actions are independent and identically distributed (i.i.d) sequences over T rounds drawn from fixed unknown distributions. In adversarial BwK, the sequence of the rewards and the costs associated with each action over T rounds is assigned by an oblivious adversary before the game starts. The objective of the player is to minimize the expected regret in these settings.

The stochastic BwK setting has been extensively studied in the literature [Tran-Thanh et al., 2010; 2012a; Ding et al., 2013; Badanidiyuru et al., 2013; Agrawal and Devanur, 2014; Tran-Thanh et al., 2012b; Agrawal and Devanur, 2016; Xia et al., 2016; Sankararaman and Slivkins, 2018; Rangi and Franceschetti, 2018a]. However, limited attention has been received by the adversarial BwK setting [Immorlica et al., 2018; Zhou and Tomlin, 2018]. It has been shown that the competitive ratio, defined as the ratio of the expected rewards corresponding to best fixed distribution over actions and the expected rewards of any learning algorithm, is at least Ω(log(B)) [Immorlica et al., 2018]. Thus, the difference between the expected rewards corresponding to the best fixed distribution over the actions and the expected rewards of the learning algorithm, is at least Ω(B). The work in [Zhou and Tomlin, 2018], assumes that the rewards are greater than the costs at each round t for every action i, and reduces the problem to an adversarial MAB setting [Auer et al., 2002]. This assumption is somewhat uncommon in the literature and does not have physical meaning in many applications. For example, in a medical trial, the success rate (i.e., the reward) and the cost of the material (i.e., the cost) cannot be compared with each other. Likewise, in web advertisement, the comparison of the click through rate (i.e., the reward) and the space occupied by the advertisement on the web page (i.e., the cost) has no meaning. Thus, determining the feasibility of sub-linear regret bounds in the adversarial BwK setting, and the designing an algorithm without constraints on the rewards and the costs remain important open problems.

An additional open problem is to provide an algorithm that is satisfactory for both stochastic and adversarial BwK settings simultaneously. In many real-world situations, there is no information about the stochastic or the adversarial nature of the problem. Thus, the deployed algorithm has to be able to performwell in both the cases. Finally, the literature of the BwK problem typically assumes that the costs are bounded by a constant independent of the budget B, and it is unknown whether the state-of-the-art regret bounds hold for the case of large costs (i.e., when costs are comparable to the budget B).

In this framework, the contribution of our work is three fold. First, we study the adversarial BwK setting in terms of a new definition of expected regret defined as the difference between the total expected rewards per unit cost corresponding the best fixed action (instead of best fixed distribution over actions) and the total expected rewards per unit cost of the learning algorithm. We establish that, unlike in [Immorlica et al., 2018], sub-linear regret bounds of O(√B) are feasible for this new notion of regret in BwK setting. We propose a new algorithm EXP3.BwK and show that its expected regret is O(√BK logK). We also prove that the expected regret for any learning algorithm is at least Ω(√KB) in the adversarial BwK setting, and establish that EXP3.BwK is order optimal. Additionally, this analysis is carried out without the assumption on the rewards and the costs previously used in [Zhou and Tomlin, 2018]. Second, we unify the stochastic and the adversarial settings by proposing EXP3++.BwK. This algorithm incurs an expected regret of O(√BK logK) and O(log2 (B)) in the adversarial and the stochastic BwK settings respectively. In the stochastic BwK setting, the regret bound has an additional factor of log(B) in comparison to the optimal expected regret i.e. O(log(B)). Thus, EXP3++.BwK exhibits an almost optimal behavior in both the stochastic and the adversarial settings simultaneously. We also study the performance of another algorithm EXP3++.LwK for a generic online learning setting where the player's feedback can be viewed as a time-varying graph Gt at round t and a directed edge k → j in Gt indicates that choosing action k at round t also reveals the reward and the cost of action j at round t. Finally, we show that if the maximum cost is bounded above by Bα, where α ∈ [0, 1], then the expected regret in the adversarial BwK setup scales at least linearly with the maximum cost, namely it is Ω(Bα). Thus, for α > 1/2, it is impossible to achieve a regret bound of O(√B), which is feasible for small costs. The proofs of all the results are available online [Rangi et al., 2018d].

1.1 RelatedWork

In the MAB literature, the problem of finding one algorithm for both the stochastic and the adversarial setting has been referred as "Best of Both Worlds" [Bubeck and Slivkins, 2012; Auer and Chiang, 2016; Seldin and Slivkins, 2014; Seldin and Lugosi, 2017; Lykouris et al., 2018]. Initial works on this problem reduced it to a detection problem, where the algorithms initially assume the rewards are stochastic, and perform an irreversible switch to EXP3.P if the beginning of the game is estimated to exhibit an adversarial or non-stochastic behavior [Bubeck and Slivkins, 2012; Auer and Chiang, 2016]. Unlike the algorithms in [Bubeck and Slivkins, 2012; Auer and Chiang, 2016], EXP3++ starts by assuming that the rewards exhibit a non-stochastic behavior and adapts itself as it encounters stochastic behavior on rewards [Seldin and Slivkins, 2014; Seldin and Lugosi, 2017]. The algorithm guarantees an expected regret of O(log2 (T)) and O(√T) in the stochastic and the adversarial MAB settings respectively. The problem of stochastic bandits corrupted with adversarial samples has also been studied in the regime of small corruptions [Lykouris et al., 2018]. The work provides the regret analysis of the algorithm in terms of the corruption in the rewards, and shows that the decay in performance is order optimal in this corruption.

The "Best of Both Worlds" problem has not been studied in the BwK setting. This setting is more complex in comparison to the MAB setting as the adversary can choose both the rewards and the costs associated with the actions. Additionally, the adversary can dynamically choose to corrupt the rewards or the costs at each step which can lead to stochastic environment based on the cumulative effects of the corruptions.

2 ProblemFormulation

A player has a total budget B to perform actions. At each round t, the player performs an action it ∈ [K], pays the cost ct(it) and receives the reward rt(it), where ct(i) ∈ [cmin, cmax] is the cost of action i and rt(i) ∈ [0, 1] is the reward of action i. Note that cmax = 1 which is also a common assumption in the literature, and we will investigate the case with larger costs in Section 5. The objective of a player is to design a learning algorithm A such that

where τ(A) is the number of rounds feasible in the budget B using algorithm A. The optimization problem in (1) is a knapsack problem, and is known to be NP-hard [Kellerer et al., 2004]. Given that at each round t, the reward and the cost of all the actions are known and fixed i.e. rt(i) = r(i) and ct(i) = c(i), the best fixed action i∗ is the action with the highest efficiency, namely

where efficiency e(i) = r(i)/c(i) for an action i ∈ [K]. This choice of best fixed action is referred as a greedy algorithm AG and satisfies the following [Kellerer et al., 2004]

where G(A) = E[∑τ(A) t=1 rt(it)] is the expected reward of A, and A∗ is the optimal solution of (1). Intuitively, the best fixed action i∗ returns the maximum rewards per unit cost. Since the total cost spent is at most B, G(AG) is at most e(i∗ ) · B.

We define the expected regret in both stochastic and adversarial settings with respect to the best fixed optimal action based on the efficiency according to AG. In the stochastic setting, for all t and i ∈ [K], the sequence of rewards rt(i) is i.i.d with mean µ(i) and the sequence of cost ct(i) is i.i.d with mean ρ(i). However, the expected reward µ(i) and expected cost ρ(i) can be correlated. Thus, the efficiency of an action i is e(i) = µ(i)/ρ(i) in stochastic setting, and the expected regret of an algorithm A with respect to best fixed action, given by AG, is defined as

where i∗ = argmaxi∈[K] e(i), and T(i) is the number of rounds of action i feasible in the budget B. Thus, the best fixed action i∗ returns maximum expected rewards per unit expected cost. The regret, defined in (4), is previously studied in the literature of stochastic BwK setting as well, and the performance guarantees are presented in terms of ∆(i) = e(i∗ ) - e(i) [Ding et al., 2013; Tran-Thanh et al., 2012b; Rangi and Franceschetti, 2018a].

In the adversarial setting, rt(i) and ct(i) are chosen by an adversary. Unlike the efficiency in the stochastic setting, the efficiency of an action i is time varying, and is denoted by et(i) = rt(i)/ct(i) at round t. Since the reward per unit cost varies across t, the best fixed action in the hindsight is defined as

The action i∗ maximizes the total rewards per unit cost across T(i∗ ) rounds, and T(i∗ ) takes into account the total budget utilized while performing i∗ repeatedly. Since cmax = 1, the maximum rewards achievable in adversarial setting is at most ∑T (i∗ ) t=1 et(i∗ ). Therefore, the expected regret in this setting is defined as

For ct(i) = 1, action i∗ reduces to the best fixed action over B rounds in MAB setup, and the regret in (6) reduces to the regret in adversarial MAB setting [Auer et al., 2002].

3 Adversarial Bandits with Knapsack

In this section, we propose an order optimal algorithm EXP3.BwK for the adversarial BwK setting, and show that sub-linear regret guarantees are feasible in this setting.

EXP3.BwK is presented in Algorithm 1. At each round t, EXP3.BwK selects an action it = i with probability pt(i), pays the cost ct(it) from the remaining budget Br, and receives the reward rt(it). If the budget Br is insufficient, i.e. ct(it) > Br, then the algorithm terminates without attempting to find other feasible actions which can be performed using the remaining budget Br. Since cmax = 1, Br at the termination round is at most unity, and the number of rounds feasible with this remaining budget is at most 1/cmin, which is independent of B.

In EXP3.BwK, the empirical estimate ˆ et(i) of efficiency (defined in Algorithm 1) of action i is the observed efficiency et(i) = rt(i)/ct(i) scaled with the probability pt(i). This empirical estimate is used to maintain the set of timevarying weights {wt(i)}Ki=1 for all actions. The difference in wt(i) and wt-1(i) is controlled by exp (γcminˆ et(i)/K) as γcminˆ et(i)/K less than unity. Thus, wt(i) is proportional to the cumulative estimated efficiency of action i observed until round t i.e wt(i) ∝ exp (∑t-1 n=1 ˆ en(i)).

The sampling probability pt(i) is dependent on the timevarying weight wt(i) and the exploration constant γ/K. The weight wt(i) favors the selection of an action with higher cumulative estimated efficiencies until round t. In other words, it favors the action which may yield immediate rewards, and is responsible for the exploitation in the algorithm. On the other hand, the exploration constant γ/K ensures that the player is always exploring with a positive probability in search of the optimal action i∗ . This balances the trade-off between exploration and exploitation.

In EXP3.BwK, we exploit the idea of efficiency measure et(i) for tracking the contributions of each action i ∈ [K]. The use of this measure is motivated from the greedy algorithmAG, and its performance guarantees with respect to the optimal solution (see (3)). The advantages of using this measure are two folds. First, it eliminates the need of the assumption that at each round, the reward is greater than the cost for each action [Zhou and Tomlin, 2018]. Second, it can track rewards of the algorithm A irrespective of the measure or scale of the rewards and the costs of the actions. For example, in a recommendation system, the space (i.e. the cost) of the item and the click rate (i.e. the reward) of the item are not comparable on same scale. However, the returns can be tracked using the efficiency measure et(i). An alternate choice of efficiency measure can be rt(i) - ct(i) for tracking the contributions of different actions. However, this can only be used if both the rewards and the costs can be compared on a linear scale, which is not true in many practical applications.

The following theorem shows that the expected regret of EXP3.BwK is sub-linear in the budget B.

Algorithm 1 EXP3.BwK

end while

Theorem 1. For γ = √cminK log(K)/B(e -1), the expected regret, as defined in (6), of EXP3.BwK is at most

where E denotes EXP3.BwK.

The following theorem provides the lower bound on the expected regret of any learning algorithm in the adversarial BwK setting.

Theorem 2. There exists an adversary such that for any player's learning algorithm A, the expected regret of the algorithm A is at least Ω(√KB/cmin).

Combining Theorem 1 and Theorem 2, it follows that the expected regret of EXP3.BwK is order optimal in the budget B and has an additional factor of 1/cmin. Additionally, unlike [Immorlica et al., 2018], Theorem 1 and Theorem 2 establish that it is feasible to attain sub-linear regret bounds with respect to the best fixed action based on the efficiency for BwK with single constraint (1). The order optimality of EXP3.BwK also highlights an important feature of an alternate class of algorithms in the adversarial BwK setup. Consider a new class of algorithms G which looks for an alternative action to perform after the algorithm is unable to pay the cost, i.e. ct(it) > Br, in order to utilize the remaining budget efficiently. Since EXP3.BwK terminates if it is unable to pay ct(it), EXP3.BwK does not belong to G, and is still order optimal in the budget B. Therefore, the expected regret of the algorithms in this new class G will have same dependency on B as that of EXP3.BwK. Additionally, the difference between the expected regret of EXP3.BwK and the algorithms in G will be at most 1/cmin, a constant independent of B. The algorithms in G faces an additional challenge of designing an appropriate criterion for the termination of the algorithm because the costs are assigned by the adversary.

The ideas developed in EXP3.BwK form the basis for designing an algorithm that achieves almost optimal performance guarantees in both the stochastic and the adversarial BwK settings simultaneously.

4 One Practical Algorithm for Both Stochastic and Adversarial BwK

In this section, we propose EXP3++.BwK, and show that it achieves almost optimal performance guarantees in both the stochastic and the adversarial BwK settings simultaneously.

Before discussing EXP3++.BwK, let us briefly focus on the fundamental difference between the optimal algorithms in the stochastic and the adversarial settings. In the stochastic setting, the algorithms focus on exploration in the initial stage until reliable estimates of the expected rewards µ(i) and expected costs ρ(i) are achieved. Then, the algorithms shift their focus on exploitation by choosing actions which yield immediate rewards, and perform exploration only with a small probability. For instance, in UCB type of algorithms, the probability of exploration or choosing sub-optimal actions decays as O(1/t2 ) with round t [Tran-Thanh et al., 2012a; Ding et al., 2013; Rangi and Franceschetti, 2018a]. In greedy algorithms, the probability of exploration is exactly zero after a fixed round (or time instance), and the algorithm chooses the best action based on its knowledge at this time instance [Tran-Thanh et al., 2010; 2012b]. On the contrary, in the adversarial setting, the algorithms are always exploring, and looking for the actions with high returns [Auer et al., 2002; Rangi and Franceschetti, 2018b]. For instance, in EXP3.BwK, the exploration constant γ/K does not change with round t, and is dependent only on the total number of rounds i.e. Θ(B) in the BwK setup. Intuitively, an algorithm that is optimal in both these settings needs to efficiently adapt its exploration phase based on the nature of the observations while balancing the exploration and exploitation trade-off.

EXP3++.BwK is presented in Algorithm 2. It is built upon the ideas of the efficiencies in the stochastic and the adversarial BwK settings. Like EXP3.BwK, at each round t, EXP3++.BwK selects an action it = i with sampling probability ˜ pt(i), pays the cost ct(it) from the remaining budget Br, and receives reward rt(it). The algorithm terminates if it is unable to pay the cost ct(it) at any round t, namely ct(it) > Br.

The sampling probability ˜ pt(i) is dependent on two time varying parameters: the exploration parameter ϵt(i) and the exploitation parameter pt(i). Unlike EXP3.BwK, exploration parameter ϵt(i) is time-varying, and helps to efficiently adapt the exploration phase of the algorithm based on the stochastic or non-stochastic nature of the past observations. It is a function of UCBt(i), LCBt(i) and ˆ∆t(i) (see Algorithm 2). At each round t, EXP3++.BwK maintains an Upper Confidence Bound UCBt(i) and a Lower Confidence Bound LCBt(i) on the stochastic efficiency e(i) = µ(i)/ρ(i) of action i, where

Algorithm 2 EXP3++.BwK

Initialization: For all i ∈ [K], w1(i) = 1, ˆ e1(i) = 0, ¯ e1(i) = 0, N1(i) = 1 δ1(i) > 0; t = 1, γt = 0.5cmin√log(K)/tK; Br = B; Perform each action once and update for all i ∈ [K], ¯ e1(i) = r1(i)/c1(i), Br = Br - ∑i∈[K] c1(i) and t = K + 1.

λ ≤ cmin and Nt(i) is the number of times action i has been selected until round t. These UCB and LCB on the stochastic efficiency are used to estimate the gap ∆(i). At round t, the estimate ˆ∆t(i) of ∆(i) is defined as

It can been shown that for all i ∈ [K], we have

with high probability as t → ∞ in the stochastic BwK setting [Rangi et al., 2018d]. Thus, ˆ∆t(i) is a reliable estimate of ∆(i), and helps to adapt the exploration of the algorithm via ϵt(i). In the stochastic BwK setup, combining the fact that ∆(i∗ ) = 0 and (12) holds, the exploration parameter ϵt(i∗ ) of the optimal action i∗ tends to zero, and favors its selection. On the other hand, the exploitation parameter pt(i) is computed based on the empirical estimate ˆ et(i) of efficiency until round t. Similar to EXP3.BwK, this favors the selection of an action with higher cumulative estimated efficiency ∑t-1 n=1 ˆ et-1(i) or lower cumulative estimated inefficiency ∑t-1 n=1 ˆ ℓt-1(i). In conclusion, the sampling probability ˜ pt(i) is dependent on both the estimates of the efficiencies ¯ et(i) and ˆ et(i) where ¯ et(i) and ˆ et(i) are crucial in the stochastic BwK and the adversarial BwK settings respectively. ¯ et(i) controls the exploration through ϵt(i), and ˆ et(i) controls the exploitation through pt(i).

The following theorem provides the performance guarantees of EXP3++.BwK in the stochastic BwK setting.

Theorem 3. In the stochastic BwK setting, for α = 3 and β = 256/c2min , the expected regret of EXP3++.BwK is at most

where F denotes the algorithm EXP3++.BwK, and M is a constant.

The optimal regret guarantees in the stochastic BwK setting are O(log(B/cmin))[Tran-Thanh et al., 2012a; Ding et al., 2013; Rangi and Franceschetti, 2018a]. Using Theorem 3, EXP3++.BwK has an additional factor of log(B/cmin) in comparison to the optimal regret bounds in the literature. This additional factor is also common in the literature of the "Best of Both Worlds" problem in MAB setting [Seldin and Slivkins, 2014; Lykouris et al., 2018].

The following theorem provides the performance guarantees of EXP3++.BwK in the adversarial BwK setting.

Theorem 4. In the adversarial BwK setting, the expected regret of EXP3++.BwK is at most

Thus, like EXP3.BwK, EXP3++.BwK is order optimal in the adversarial BwK setting. In conclusion, using Theorem 3 and Theorem 4, EXP3++.BwK is order optimal in the adversarial BwK setting, and is almost optimal with an additional factor of log(B/cmin) in the stochastic BwK setting.

Now, we extend these ideas beyond the MAB setting to a general online learning setting, where the player's feedback can be viewed as a time-varying graph Gt at round t [Alon et al., 2015; Rangi and Franceschetti, 2018b]. At round t, a directed edge k → j in Gt indicates that choosing action k also reveals the reward and the cost of action j. Thus, St(i) = {j : i → j is a directed edge in Gt} is the set of observable actions if i is performed. In MAB setting, St(i) = {i}. EXP3++.BwK can be modified to design a new algorithm EXP3++.LwK for this general online learning with Knapsack setting, which has not been addressed previously in the literature. The key difference is the estimation of the two efficiencies ˆ et(i) and ¯ et(i), and is presented in the following equations:

Likewise, Nt(i) = ∑tn=1 1(i ∈ Sn(in)) and ˆ ℓt(i) = 1(i ∈ St(it))/cmin ∑j:j→i ˜ pj,t - ˆ et(i). The following theorem provides the performance guarantees of EXP3++.LwK in the adversarial online learning Knapsack setting.

Theorem5. In the adversarial online learning Knapsack setting, the expected regret of EXP3++.LwK is at most

where L denotes EXP3++.LwK, T = B/cmin, mas(Gt) is the size of the maximal acyclic graph in Gt, and b > 0 is a constant dependent on K and cmin.

In the stochastic online learning Knapsack setting, the expected regret of EXP3++.LwK is O(log2 (B/cmin)), and these guarantees are similar to the ones presented in Theorem 3. Now, the following theorem provides a lower bound on the expected regret in the online learning Knapsack setting.

Theorem 6. For a sequence of feedback graphs G1, . . . ,GT with independence sequence number β(G1:T ) > 1, there exists an adversary such that for any learning algorithm A, the expected regret of the algorithm A is at least Ω(√β(G1:T )B/cmin).

Using Theorem 5 and 6, EXP3++.LwK is order optimal in two special cases of adversarial online learning: MAB and symmetric PI setting, i.e. the feedback graph Gt = G is fixed and un-directed. In MAB setting β(G1:T ) = mas(Gt) = K, Theorem 6 recovers the lower bound in Theorem 2, and establishes that the algorithm is order optimal. Likewise, in symmetric PI setting β(G1:T ) = mas(Gt) which implies the algorithm is order optimal. Note that any state-of-art algorithms in adversarial online learning setting are order optimal for these two special cases only [Alon et al., 2015; Rangi and Franceschetti, 2018a], and the key challenges for closing this gap are highlighted in [Alon et al., 2015].

5 BwKwith Unbounded Cost

In the previous sections, we have shown that the sub-linear regret is achievable in the BwK and the online learning Knapsack settings for cmax = 1. We now explore the regime of varying cmax, and develop important insights about the achievable regret in this scenario. Following theorem presents the scaling of the lower bound on the expected regret with respect to cmax in the adversarial BwK setup.

Theorem 7. Suppose that cmax = Bα. For any learning algorithmA, there exists an adversary such that the expected regret of the algorithm is at least Ω(Bα).

In the literature of BwK, the cost is always considered to be bounded above by a constant independent of B. Theorem 7 instead considers that the cost is bounded by a function of the budget B. It shows that the lower bound on the expected regret scales at least linearly with the maximum cost cmax in the adversarial BwK setup, and similar results hold for online learning Knapsack setting as well. If α > 1/2, then it is impossible to achieve a regret bound of O(√B), which is order optimal in cases with small cmax.

In the adversarial BwK setup, the adversary can penalize the player in two ways. First, the adversary can control the reward of an action at any round. Second, the adversary can control the cost of an action, which is analogous to penalizing the player on the number of rounds T. For α > 1/2, the penalty on the number of rounds T becomes significant, and the minimum achievable regret is no longer Ω(√B). In this setting with α > 1/2, the design of algorithms which achieve regret of O(Bα) is left as a future work.

6 Conclusion

The study of BwK has been mostly focused on the stochastic regime. In this work, we considered the adversarial regime and proposed the order optimal algorithm EXP3.BwK for this setting. We also proposed the algorithm EXP3++.BwK, which achieves an expected regret of O(√KB log(K)) and O(log2 (B)) in the adversarial and stochastic settings respectively. Thus, the algorithm is order optimal in the adversarial regime, and has an additional factor of log(B) in the stochastic regime. It is the first algorithm that provides almost optimal performance guarantees in both stochastic and adversary BwK settings simultaneously. Using the ideas from EXP3++.BwK, a new algorithm EXP3++.LwK was designed for a general online learning setting, and its performance guarantees were provided.

All the results in the literature of BwK assume that the maximum cost is bounded by a constant independent of B. We have shown that if the cost is O(Bα), then the expected regret is at least Ω(Bα). This setting is of particular interest when α > 1/2 because the expected regret of O(√B), which is achievable in the setting where cost is bounded by a constant, becomes unachievable. Hence, there is a need to study this BwK setting, and design optimal algorithms whose expected regret is O(Bα), which is left as a future work.