UCBoost: A Boosting Approach to Tame Complexity and Optimality for Stochastic Bandits

1 Introduction

Multi-armed bandits, introduced by Thompson [1933], have been used as quintessential models for sequential decision making. In the classical setting, at each time, a decision maker must choose an arm from a set of K arms with unknown probability distributions. Choosing an arm i at time t reveals a random reward Xi(t) drawn from the probability distribution of arm i. The goal is to find policies that minimize the expected regret due to uncertainty about arms' distributions over a given time horizon T. Lai and Robbins [1985], followed by Burnetas and Katehakis [1996], have provided an asymptotically lower bound on the expected regret.

Upper confidence bounds (UCB) based algorithms are an important class of bandit algorithms. The most celebrated UCB-type algorithm is UCB1 proposed by Auer et al. [2002], which enjoys simple computations per round as well as O(log T) regret guarantee. Variants of UCB1, such as UCBV proposed by Audibert et al. [2009] and MOSS proposed by Audibert and Bubeck [2010], have been studied and shown improvements on the regret guarantees. However, the regret guarantees of these algorithms have unbounded gaps to the lower bound. Recently, Maillard et al. [2011] and Garivier and Capp´e [2011] have proposed a UCB algorithm based on the Kullback-Leibler divergence, kl-UCB, and proven it to be asymptotically optimal when all arms follow a Bernoulli distribution, i.e., they reach the lower bound by Lai and Robbins [1985]. They have generalized the algorithm to KL-UCB [Capp´e et al., 2013], which is asymptotically optimal under general distributions with bounded supports.

However, these UCB algorithms exhibit a complexityoptimality dilemma in the real world applications that are computationally sensitive. On one hand, the UCB1 algorithm enjoys closed-form updates per round while its regret gap to the lower bound can be unbounded. On the other hand, the kl-UCB algorithm is asymptotically optimal but it needs to solve a convex optimization problem for each arm at each round. Though there are many standard optimization tools to solve the convex optimization problem numerically, there is no regret guarantee for the implemented kl-UCB with arbitrary numerical accuracy. Practitioners usually set a sufficient accuracy (for example, 10-5 ) so that the behaviors of the implemented kl-UCB converge to the theory. However, this means that the computational cost per round by kl-UCB can be out of budget for applications with a large number of arms. The complexity-optimality dilemma is because there is currently no available algorithm that can trade-off between complexity and optimality.

Such a dilemma occurs in a number of applications with a large K. For example, in an online recommendation system [Li et al., 2010; Buccapatnam et al., 2017], the algorithm needs to recommend an item from hundreds of thousands of items to a customer within a second. Another example is the use of bandit algorithms as a meta-algorithm for other machine learning problems, e.g., using bandits for classifier boosting [Busa-Fekete and K´egl, 2010]. The number of data points and features can be large.

Another scenario that the dilemma appears is in realtime applications such as robotic systems [Matikainen et al., 2013], 2D planning [Laskey et al., 2015] and portfolio optimization [Moeini et al., 2016]. In these applications, a delayed decision may turn out to be catastrophic.

Capp´e et al. [2013] proposed the open problem of finding a low-complexity optimal UCB algorithm, which has remained open till now. In this work, we make the following contributions to this open problem. (Table 1 summarizes the main results.)

• We propose a generic UCB algorithm. By plugging a semi-distance function, one can obtain a specific UCB algorithm with regret guarantee (Theorem 1). As a byproduct, we propose two new UCB algorithms that are alternatives to UCB1 (Corollary 1 and 2).
• We propose a boosting algorithm, UCBoost, which can obtain a strong (i.e., with regret guarantee close to the lower bound) UCB algorithm from a set of weak (i.e., with regret guarantee far away from the lower bound) generic UCB algorithms (Theorem 2). By boosting a finite number of weak generic UCB algorithms, we find a UCBoost algorithm that enjoys the same complexity as UCB1 as well as a regret guarantee that is 1/e-close to the kl-UCB algorithm (Corollary 3) 1 . That is to say, such a UCBoost algorithm is low-complexity and nearoptimal under the Bernoulli case.
• We propose an approximation-based UCBoost algorithm, UCBoost(ϵ), that enjoys ϵ-optimal regret guarantee under the Bernoulli case and O(log(1/ϵ)) computational complexity for each arm at each round for any ϵ > 0 (Theorem 3). This algorithm provides a nontrivial trade-off between complexity and optimality.

Related Work. There are other asymptotically optimal algorithms, such as Thompson Sampling [Agrawal and Goyal, 2012], Bayes-UCB [Kaufmann et al., 2012] and DMED [Honda and Takemura, 2010]. However, the computations involved in these algorithms become non-trivial in non-Bernoulli cases. First, Bayesian methods, including Thompson Sampling, Information Directed Sampling [Russo and Van Roy, 2014; Liu et al., 2017] and Bayes-UCB, require updating and sampling from the posterior distribution, which is computationally difficult for models other than exponential families [Korda et al., 2013]. Second, the computational complexity of DMED policy is larger than UCB policies because the computation involved in DMED is formulated as a univariate convex optimization problem. In contrast, our algorithms are computationally efficient in general bounded support models and don't need the knowledge of prior information on the distributions of the arms.

Our work is also related to DMED-M proposed by Honda and Takemura [2012]. DMED-M uses the first d empirical moments to construct a lower bound of the objective function involved in DMED. As d goes to infinity, the lower bound converges to the objective function and DMED-M

1 Note that e is the natural number

converges to DMED while the computational complexity increases. However, DMED-M has no explicit form when d > 4 and there is no guarantee on the regret gap to the optimality for any finite d. Unlike DEMD-M, our UCBoost algorithms can provide guarantees on the complexity and regret performance for arbitrary ϵ, which offers a controlled tradeoff between complexity and optimality.

Agarwal et al. [2017] proposed a boosting technique to obtain a strong bandit algorithm from the existing algorithms, that is adaptive to the environment. However, our boosting technique is specifically designed for stochastic setting and hence allows us to obtain near-optimal algorithms that have better regret gurantees than those obtained using the boosting technique by Agarwal et al. [2017].

2 Preliminaries

We consider a stochastic bandit problem with finitely many arms indexed by a ∈ K ≜ {1, . . . , K}, where K is a positive integer. Each arm a is associated with an unknown probability distribution va over the bounded support 2 Θ = [0, 1]. At each time step t = 1, 2, . . . , the agent chooses an action At according to past observations (possibly using some independent randomization) and receives a reward XAt,NAt (t) independently drawn from the distribution vAt , where Na(t) ≜ ∑ts=1 1{As = a} denotes the number of times that arm a was chosen up to time t. Note that the agent can only observe the reward XAt,NAt (t) at time t. Let ¯Xa(t) be the empirical mean of arm a based on the observations up to time t.

For each arm a, we denote by µa the expectation of its associated probability distribution va. Let a∗ be any optimal arm, that is a∗ ∈ argmaxa∈K µa. We write µ∗ as a shorthand notation for the largest expectation µa∗ and denote the gap of the expected reward of arm a to µ∗ as ∆a = µ∗ - µa. The performance of a policy π is evaluated through the standard notion of expected regret, defined at time horizon T as

The goal of the agent is to minimize the expected regret.

Now, we introduce the concept of semi-distance functions, which measure the distance between two expectations of random variables over Θ, and show several related properties.

Definition 1. (Candidate semi-distance) A function d : Θ× Θ → R is said to be a candidate semi-distance function if 1. d(p, p) ≤ 0, ∀p ∈ Θ;

1. d(p, q) ≤ d(p, q′ ), ∀p ≤ q ≤ q′ ∈ Θ;
2. d(p, q) ≥ d(p′ , q), ∀p ≤ p′ ≤ q ∈ Θ.

2 If the supports are bounded in another interval, rescale to [0,1].

Clearly, a candidate semi-distance function satisfies the monotone properties 3 of a distance function. However, it does not need to be non-negative and symmetric.

Definition 2. (Semi-distance) A function d : Θ×Θ → R is said to be a semi-distance function if it is a candidate semidistance function such that d(p, q) ≥ 0, ∀p, q ∈ Θ.

A semi-distance function satisfies the non-negative condition, and is stronger than a candidate semi-distance function. The following lemma reveals a simple way to obtain a semidistance function from a candidate semi-distance function.

Lemma 1. If d1 : Θ×Θ → R is a candidate semi-distance function and d2 : Θ × Θ → R is a semi-distance function, then max(d1, d2) is a semi-distance function.

Remark 1. In particular, d ≡ 0 is a semi-distance function. So one can easily obtain a semi-distance function from a candidate semi-distance function.

As discussed in Remark 1, a semi-distance function may not distinguish two different distributions. So we introduce the following strong notion of semi-distance functions.

Definition 3. (Strong semi-distance) A function d : Θ×Θ→ R is said to be a strong semi-distance function if it is a semidistance function such that d(p, q) = 0 if and only if p = q.

One can obtain a strong semi-distance function from a candidate semi-distance function as shown in Lemma 2.

Lemma 2. If d1 : Θ×Θ → R is a candidate semi-distance function and d2 : Θ × Θ → R is a strong semi-distance function, then max(d1, d2) is a strong semi-distance function.

A typical strong semi-distance function is the KullbackLeibler divergence between two Bernoulli distributions,

In this work, we are interested in semi-distance functions that are dominated by the KL divergence as mentioned above.

Definition 4. (kl-dominated) A function d : Θ×Θ → R is said to be kl-dominated if d(p, q) ≤ dkl(p, q), ∀p, q ∈ Θ.

Consider a set of candidate semi-distance functions. A formal definition of feasible set is presented in Definition 5.

Definition 5. (Feasible set) A set D of functions fromΘ×Θ to R is said to be feasible if maxd∈D d is a kl-dominated and strong semi-distance function.

The following proposition shows a sufficient condition for a set to be feasible.

Proposition 1. A set D of kl-dominated and candidate semidistance functions from Θ×Θ to R is feasible if ∃d ∈ D such that d is a strong semi-distance function.

Note that we only need one of the functions to be a strong semi-distance function in order to have a feasible set. This allows us to consider some useful candidate semi-distance functions in our boosting approach.

3 The monotone properties are equivalent to the triangle inequality in one-dimensional case.

Algorithm 1 The generic UCB algorithm

Require: semi-distance function d Initialization: t from 1 to K, play arm At = t. for t from K + 1 to T do Play arm At = argmaxa∈Kmax{q ∈ Θ : Na(t - 1)d( ¯Xa(t - 1), q) ≤ log(t) + c log(log(t))} end for

3 Boosting

We first present a generic form of UCB algorithm, which can generate a class of UCB algorithms. We then provide a boosting technique to obtain a good UCBoost algorithm based on these UCB algorithms.

3.1 The Generic UCB Algorithm

Algorithm 1 presents a generic form of UCB algorithm, which only uses the empirical means. The instantiation of the UCB algorithm requires a semi-distance function. Given a semi-distance function d, UCB(d) algorithm finds upper confidence bounds {ua(t)}a∈K such that the distance d( ¯Xa(t - 1), ua(t)) is at most the exploration bonus ((log(t)+c log(log(t)))/Na(t-1)) for any arm a. Note that c is a constant to be determined. In other words, ua(t) is the solution of the following optimization problem P1(d),

where p ∈ Θ is the empirical mean and δ > 0 is the exploration bonus. The computational complexity of the UCB(d) algorithm depends on the complexity of solving the problem P1(d). The following result shows that the regret of the UCB(d) algorithm depends on the semi-distance function d.

Theorem1. If d : Θ×Θ→R is a strong semi-distance function and is also kl-dominated, then the regret of the UCB(d) algorithm when c = 3 satisfies:

Theorem 1 is a generalization of the regret gurantee of klUCB proposed by Garivier and Capp´e [2011], which is recovered by UCB(dkl). Recall that dkl is the KL divergence between two Bernoulli distributions. Note that Theorem 1 holds for general distributions over the support Θ. If the reward distributions are Bernoulli, the kl-UCB algorithm is asymptotically optimal in the sense that the regret of kl-UCB matches the lower bound provided by Lai and Robbins [1985]:

However, there is no closed-form solution to the problem P1(dkl). Practical implementation of kl-UCB needs to solve P1(dkl) via numerical methods with high accuracy, which means that the computational complexity is non-trivial.

In addition to the KL divergence function dkl, we can find other kl-dominated and strong semi-distance functions such that the complexity of solving P1(d) is O(1). Then we can obtain some low-complexity UCB algorithms with possibly

Algorithm 2 UCBoost

Require: candidate semi-distance function set D

Initialization: t from 1 to K, play arm At = t.

for t from K + 1 to T do

weak regret performance. For example, consider the l2 distance function, dsq(p, q) = 2(p - q)2 . It is clear that dsq is a kl-dominated and strong semi-distance function. Note that UCB(dsq) recovers the traditional UCB1 [Auer et al., 2002].

Now, we introduce two alternative functions to the function dsq: biquadratic distance function and Hellinger distance function. The biquadratic distance function is dbq(p, q) = 2(p - q)2 + 49 (p - q)4 . The Hellinger distance function 4 is dh(p, q) = (√p - √q)2 + (√1 - p - √1 - q)2 . As shown in Lemma 3 and Lemma 4, they are kl-dominated and strong semi-distance functions and the solutions of the corresponding P1(d) have closed forms.

Lemma 3. The biquadratic distance function dbq is a kldominated and strong semi-distance function. The solution

Lemma 4. The Hellinger distance function dh is a kldominated and strong semi-distance function. The solution of P1(dh) is q∗ =

where 1{·} is the indicator function.

The following result follows from Theorem 1 and Lemma 3. Note that UCB(dbq) enjoys the same complexity of UCB1 and better regret guarantee than UCB1.

Corollary 1. If c = 3, then the regret of UCB(dbq) satisfies

The following result follows from Theorem 1 and Lemma 4. Note that UCB(dh) enjoys the same complexity of UCB1. In terms of regret guarantees, no one dominates the other.

Corollary 2. If c = 3, then the regret of UCB(dh) satisfies

3.2 The UCBoost Algorithm

The generic UCB algorithm provides a way of generating UCB algorithms from semi-distance functions. Among the class of semi-distance functions, some have closed-form solutions of the corresponding problems P1(d). Thus, the corresponding algorithm UCB(d) enjoys O(1) computational complexity for each arm in each round. However, these UCB(d)

4 Actually, dh is 2 times the square of the Hellinger distance.

algorithms are weak in the sense that the regret guarantees of these UCB(d) algorithms are worse than that of kl-UCB. Moreover, the decision maker does not know which weak UCB(d) is better when the information {µa}a∈K is unknown. A natural question is: is there a boosting technique that one can use to obtain a stronger UCB algorithm from these weak UCB algorithms? The following regret result of Algorithm 2 offers a positive answer.

Theorem 2. If D is a feasible set, then the regret of UCBoost(D) when c = 3 satisfies:

The UCBoost algorithm works as the following. Given a feasible set D of candidate semi-distance functions, UCBoost(D) algorithm queries the upper confidence bound of each weak UCB(d) once and takes the minimum as the upper confidence bound. Suppose that for any d ∈ D, UCB(d) enjoys O(1) computational complexity for each arm in each round. Then, UCBoost(D) enjoys O(|D|) computational complexity for each arm in each round, where |D| is the cardinality of set D. Theorem 2 shows that UCBoost(D) has a regret guarantee that is no worse than any UCB(d) such that d ∈ D. Hence, the UCBoost algorithm can obtain a stronger UCB algorithm from some weak UCB algorithms. Moreover, the following remark shows that the ensemble does not deteriorate the regret performance.

Remark 2. If D1 and D2 are feasible sets, and D1 ⊂ D2, then the regret guarantee of UCBoost(D2) is no worse than that of UCBoost(D1).

By Theorem 2, UCBoost({dbq, dh}) enjoys the same complexity as UCB1, UCB(dbq) and UCB(dh), and has a no worse regret guarantee. However, the gap between the regret guarantee of UCBoost({dbq, dh}) and that of kl-UCB may still be large since dbq and dh are bounded while dkl is unbounded. To address this problem, we are ready to introduce a candidate semi-distance function that is kl-dominated and unbounded. The candidate semi-distance function is a lower bound of the KL divergence function dkl, dlb(p, q) = p log(p) + (1 - p) log ( 1-p 1-q ) .

Lemma 5. The function dlb is a kl-dominated and candidate semi-distance function. The solution of P1(dlb) is

By Lemma 3-5, Proposition 1 and Theorem 2, we have the following result.

Corollary 3. If D = {dbq, dh, dlb}, then the regret of UCBoost(D) when c = 3 satisfies:

Note that dkl(µa, µ∗ ) - 1/e ≤ max d∈D d(µa, µ∗ ) ≤ dkl(µa, µ∗ )

for any a ∈ K such that µa < µ∗ . Thus, we have that

Although dlb is not a strong semi-distance function, the set D = {dbq, dh, dlb} is still feasible by Proposition 1. The advantage of introducing dlb is that its tightness to dkl improves the regret guarantee of the algorithm. To be specific, the gap between dlb(µa, µ∗ ) and dkl(µa, µ∗ ) is µa log(1/µ∗ ), which is uniformly bounded by 1/e since µa < µ∗ . Note that e is the natural number. Hence, UCBoost({dbq, dh, dlb}) achieves near-optimal regret performance with low complexity.

3.3 The UCBoost(ϵ) Algorithm

First, we show an approximation of the KL divergence function dkl. Then we design a UCBoost algorithm based on the approximation, which enjoys low complexity and regret guarantee that is arbitrarily close to that of kl-UCB.

Recall that p ∈ Θ and δ > 0 are the inputs of the problem P1(dkl). Given any approximation error ϵ > 0, let η = ϵ 1+ϵ and qk = 1 - (1 - η)k ∈ Θ for any k ≥ 0. Then there exist τ1(p) = ⌈ log(1-p) log(1-η) ⌉ and τ2(p) = ⌈ log(1-exp(-ϵ/p)) log(1-η) ⌉ such that p ≤ qk ≤ exp(-ϵ/p) if τ1(p) ≤ k ≤ τ2(p). For each τ1(p) ≤ k ≤ τ2(p), we construct a step function, dks (p, q) = dkl(p, qk)1{q > qk}. These step functions can approximate the function dkl on the interval [p, exp(-ϵ/p)]. Then we use dlb to approximate dkl on the interval [exp(-ϵ/p), 1]. The following result shows that the step function dks (p, q) is a kldominated and semi-distance function.

Lemma 6. For each k ≥ τ1(p), the step function dks (p, q) is a kl-dominated and semi-distance function. The solution of P1(dks ) is q∗ = q1{δ<dkl(p,qk)} k .

Let D(p) = {dsq, dlb, dτ1(p) s , dτ1(p)+1 s , . . . , dτ2(p) s }. Then the following result shows that the envelope maxd∈D(p) d is an ϵ-approximation of the function dkl on the interval [p, 1].

Lemma 6 and Proposition 2 allow us to bound the regret of the UCBoost algorithm based on the approximation, which is shown in the following result.

Theorem 3. Given any ϵ > 0, let D = {dsq, dlb} ∪ {dks : k ≥ 0}. The regret of UCBoost(D) with c = 3 that restricts D to D(p) for each arm with empirical mean p, satisfies

The complexity for each arm per round is O(log( 1ϵ )).

We denote the algorithm described in Theorem 3 as UCBoost(ϵ) for shorthand. The UCBoost(ϵ) algorithm offers an efficient way to trade regret performance with complexity.

Remark 3. The practical implementation of kl-UCB needs numerical methods for searching the q∗ of P1(dkl) with some sufficiently small error ϵ. For example, the bisection search can find a solution q′ such that |q′ - q∗ | ≤ ϵ with O(log( 1ϵ )) iterations. However, there is no regret guarantee of the implemented kl-UCB when ϵ is arbitrary. Our UCBoost(ϵ) algorithm fills this gap and bridges computational complexity to regret performance. Moreover, the empirical performance of the implemented kl-UCB when ϵ is relatively large, becomes unreliable. This is because the gap |dkl(p, q∗ ) - dkl(p, q′ )| is unbounded even though |q′ - q∗ | is bounded. On the contrary, our approximation method guarantees bounded KL divergence gap, thus allowing reliable regret performance.

4 Numerical Results

In this section, we support our results by numerical experiments that compare our algorithms with the baseline algorithms in three scenarios. All the algorithms are run exactly as described in the previous sections. For implementation of kl-UCB, we use the MATLAB code in py/maBandits package developed by Capp´e et al. [2012]. All the other algorithms are also implemented using MATLAB for fairness. Note that we choose c = 0 in the experiments as suggested by Garivier and Capp´e [2011]. All the results are obtained from 10, 000 independent runs of the algorithms.

Bernoulli Scenario 1. We first consider the basic scenario with Bernoulli rewards. There are K = 9 arms with expectations µi = i/10 for each arm i. The average regret of various algorithms as a function of time is shown in Figure 1a.

First, UCB(dbq) performs as expected, though it is slightly better than UCB1. However, UCB(dh) performs worse than UCB1 in this scenario. The reason is that the regret guarantee of UCB(dh) under this scenario is worse than that of UCB1.

Second, the performance of UCBoost({dbq, dh, dlb}) is between that of UCB1 and kl-UCB. UCBoost({dbq, dh, dlb}) outperforms UCB(dh) and UCB(dbq) as expected, which demonstrates the power of boosting. The candidate semidistance function dlb plays an important role in improving the regret performance.

Third, UCBoost(ϵ) algorithm fills the gap between UCBoost({dbq, dh, dlb}) and kl-UCB with moderate ϵ. As ϵ decreases, UCBoost(ϵ) approaches to kl-UCB, which verifies our result in Theorem 3. When ϵ = 0.01, UCBoost(ϵ) matches the regret of kl-UCB. Note that the numerical method for kl-UCB, such as Newton method and bisection search, usually needs the accuracy to be at least 10-5 . Otherwise, the regret performance of kl-UCB becomes unreliable. Compared to kl-UCB, UCBoost(ϵ) can achieve the same regret performance with less complexity by efficiently bounding the KL divergence gap.

Bernoulli Scenario 2. We consider a more difficult scenario of Bernoulli rewards, where the expectations are very low. This scenario has been considered by Garivier and Capp´e [2011] to model the situations like online recommendations and online advertising. For example, in Yahoo! Front Page Today experiments [Li et al., 2010], the rewards are the click through rates of the news and articles. The rewards are binary and the average click through rates are very low. In this scenario, we consider ten arms, with µ1 = µ2 = µ3 = 0.01, µ4 = µ5 = µ6 = 0.02, µ7 = µ8 = µ9 = 0.05 and µ10 = 0.1. Figure 1b shows the average regret of various algorithms as a function of time.

First, the performance of UCB(dbq) is the same as UCB1. This is because the term∆4a vanishes for all suboptimal arms in this scenario. So the improvement of UCB(dbq) over UCB1 vanishes as well. However, UCB(dh) outperforms UCB1

because the Hellinger distance between µa and µ∗ is much larger than the l2 distance in this scenario. So UCB(dh) enjoys better regret performance than UCB1 in this scenario.

Second, UCBoost({dbq, dh, dlb}) performs as expected and is between UCB1 and kl-UCB. Although the gap between UCB1 and kl-UCB becomes larger when compared to Bernoulli scenario 1, the gap between UCBoost({dbq, dh, dlb}) and kl-UCB remains. This verifies our result in Corollary 3 that the gap between the constants in the regret guarantees is bounded by 1/e. This result also demonstrates the power of boosting in that UCBoost({dbq, dh, dlb}) performs no worse than UCB(dh) and UCB(dbq) in all cases.

Third, UCBoost(ϵ) algorithm fills the gap between UCBoost({dbq, dh, dlb}) and kl-UCB, which is consistent with the results in Bernoulli scenario 1. The regret of UCBoost(ϵ) matches with that of kl-UCB when ϵ = 0.001. Compared to the results in Bernoulli scenario 1, we need more accurate approximation for UCBoost when the expectations are lower. However, this accuracy is moderate compared to the requirements in numerical methods for kl-UCB.

Beta Scenario. Our results in the previous sections hold for any distributions with bounded support. In this scenario, we consider K = 9 arms with Beta distributions. More precisely, each arm 1 ≤ i ≤ 9 is associated with Beta(αi,βi) distribution such that αi = i and βi = 2. Note that the expectation of Beta(αi,βi) is αi/(αi + βi). The regret results shown in Figure 1c are consistent with that of Bernoulli scenario 1.

Computational time. We obtain the average running time for each arm per round by measuring the total computational time of 10, 000 independent runs of each algorithms in each scenario. Note that kl-UCB is implemented by the py/maBandits package developed by Capp´e et al. [2012], which sets accuracy to 10-5 for the Newton method. The average computational time results are shown in Table 2. The average running time of UCBoost(ϵ) that matches the regret of kl-UCB is no more than 1% of the time of kl-UCB.

5 Conclusion

In this work, we introduce the generic UCB algorithm and provide the regret guarantee for any UCB algorithm generated by a kl-dominated strong semi-distance function. Then, we propose a boosting framework, UCBoost, to boost any set of generic UCB algorithms. We find a specific finite set D, such that UCBoost(D) enjoys O(1) complexity for each arm per round as well as regret guarantee that is 1/e-close to the kl-UCB algorithm. Finally, we propose an approximationbased UCBoost algorithm, UCBoost(ϵ), that enjoys regret guarantee ϵ-close to that of kl-UCB as well as O(log(1/ϵ)) complexity for each arm per round. This algorithm bridges the regret guarantee to the computational complexity, thus offering an efficient trade-off between regret performance and complexity for practitioners. By experiments, we show that UCBoost(ϵ) can achieve the same regret performance as standard kl-UCB with only 1% computational cost of kl-UCB.

Acknowledgments

This work has been supported in part by grants from the Army Research Office W911NF-14-1-0368 and MURI W911NF12-1-0385, and grants from the Office of Naval Research N00014-17-1-2417 and N00014-15-1-2166.