lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits

Introduction

The best arm problem has a long history dating back to the ’50s with the work of . In the fixed confidence setting, the last decade has seen a flurry of activity providing new upper and lower bounds. In 2002, the successive elimination procedure of was shown to find the best arm with order $\sum_{i\neq i^{*}}\Delta_{i}^{-2}\log(n\Delta_{i}^{-2})$ samples, where $\Delta_{i}=\mu_{i^{*}}-\mu_{i}$, coming within a logarithmic factor of the lower bound of $\sum_{i\neq i^{*}}\Delta_{i}^{-2}$, shown in 2004 in . A similar bound was also obtained using a procedure known as LUCB1 that was originally designed for finding the $m$-best arms . Recently, proposed a procedure called PRISM which succeeds with $\sum_{i}\Delta_{i}^{-2}\log\log\left(\sum_{j}\Delta_{j}^{-2}\right)$ or $\sum_{i}\Delta_{i}^{-2}\log\left(\Delta_{i}^{-2}\right)$ samples depending on the parameterization of the algorithm, improving the result of by at least a factor of $\log(n)$. The best sample complexity result for the fixed confidence setting comes from a procedure similar to PRISM, called exponential-gap elimination , which guarantees identification of the best arm with high probability using order $\sum_{i}\Delta_{i}^{-2}\log\log\Delta_{i}^{-2}$ samples, coming within a doubly logarithmic factor of the lower bound of . While the authors of conjecture that the $\log\log$ term cannot be avoided, it remained unclear as to whether the upper bound of or the lower bound of was loose.

almost surely. Here is the basic intuition behind the lower bound. Consider the two-arm problem and let $\Delta$ be the difference between the means. In this case, it is reasonable to sample both arms equally and consider the sum of differences of the samples, which is a random walk with drift $\Delta$. The deterministic drift crosses the LIL bound (for a zero-mean walk) when $t\,\Delta=\sqrt{2t\log\log t}$. Solving this equation for $t$ yields $t\approx 2\Delta^{-2}\log\log\Delta^{-2}$. This intuition will be formalized in the next section.

The LIL also motivates a novel approach to the best arm problem. Specifically, the LIL suggests a natural scaling for confidence bounds on empirical means, and we follow this intuition to develop a new algorithm for the best-arm problem. The algorithm is an Upper Confidence Bound (UCB) procedure based on a finite sample version of the LIL. The new algorithm, called lil’UCB, is described in Figure 1. By explicitly accounting for the $\log\log$ factor in the confidence bound and using a novel stopping criterion, our analysis of lil’UCB avoids taking naive union bounds over time, as encountered in some UCB algorithms , as well as the wasteful “doubling trick” often employed in algorithms that proceed in epochs, such as the PRISM and exponential-gap elimination procedures . Also, in some analyses of best arm algorithms the upper confidence bounds of each arm are designed to hold with high probability for all arms uniformly, incurring a $\log(n)$ term in the confidence bound as a result of the necessary union bound over the $n$ arms . However, our stopping time allows for a tighter analysis so that arms with larger gaps are allowed larger confidence bounds than those arms with smaller gaps where higher confidence is required. Like exponential-gap elimination, lil’UCB is order optimal in terms of sample complexity.

One of the main motivations for this work was to develop an algorithm that exhibits great practical performance in addition to optimal sample complexity. While the sample complexity of exponential-gap elimination is optimal up to constants, and PRISM up to small $\log\log$ factors, the empirical performance of these methods is rather disappointing, even when compared to non-sequential sampling. Both PRISM and exponential-gap elimination employ median elimination as a subroutine. Median elimination is used to find an arm that is within $\varepsilon>0$ of the largest, and has sample complexity within a constant factor of optimal for this subproblem. However, the constant factors tend to be quite large, and repeated applications of median elimination within PRISM and exponential-gap elimination are extremely wasteful. On the contrary, lil’UCB does not invoke wasteful subroutines. As we will show, in addition to having the best theoretical sample complexities bounds known to date, lil’UCB exhibits superior performance in practice with respect to state-of-the-art algorithms.

Lower Bound

Before introducing the lil’UCB algorithm, we show that the $\log\log$ factor in the sample complexity is necessary for best-arm identification. It suffices to consider a two armed bandit problem with a gap $\Delta$. If a lower bound on the gap is unknown, then the $\log\log$ factor is necessary, as shown by the following result of .

Proof Consider a reduction of the best arm problem with $n=2$ in which the value of one arm is known. In this case, the only strategy available is to sample the other arm some number of times to determine if it is less than or greater than the known value. We have reduced the problem precisely to that studied by Farrell in , restated below.

In brief, the result of Farrell follows by studying the form of a known optimal test, termed a generalized sequential probability ratio test, which compares the running empirical mean of $X$ after $t$ samples against a series of thresholds. In the limit as $t$ increases, if the thresholds are not at least $\sqrt{(2/t)\log\log(t)}$ then the LIL implies the procedure will fail with probability approaching 1/2 for small values of $\mu$. Setting the thresholds to be just greater than $\sqrt{(2/t)\log\log(t)}$, in the limit, one can show the expected number of samples must scale as $\Delta^{-2}\log\log{\Delta^{-2}}$.

The proof in is quite involved; to make this paper more self-contained we provide a short argument for a slightly simpler result than above in Appendix A.

Procedure

This section introduces lil’UCB. The procedure operates by sampling the arm with the largest upper confidence bound; the confidence bounds are defined to account for the implications of the LIL. The procedure terminates when an arm has been sampled more than a constant fraction of the total number of samples. Fig. 1 details the algorithm and Theorem 2 quantifies performance. In what follows, let $X_{i,s}$, $s=1,2,\dots$ denote independent samples from arm $i$ and let $T_{i}(t)$ denote the number of times arm $i$ has been sampled up to time $t$. Define $\widehat{\mu}_{i,T_{i}(t)}:=\frac{1}{T_{i}(t)}\sum_{s=1}^{T_{i}(t)}X_{i,s}$ to be the empirical mean of the $T_{i}(t)$ samples from arm $i$ up to time $t$.

where $c>0$ is a constant that appears in the analysis that makes the $\log\log$ term well defined for all $\Delta_{i}\in(0,1]$. Our main result is the following.

For any $\varepsilon,\beta>0$, $\delta\in(0,\log(1+\varepsilon)/e)$The range on $\delta$ is restricted to guarantee that $\log(\frac{\log((1+\varepsilon)t)}{\delta})$ is well defined. This makes the analysis cleaner but in practice one can allow the full range of $\delta$ by using $\log(\frac{\log((1+\varepsilon)t+2)}{\delta})$ instead and obtain the same theoretical guarantees. and

with probability at least $1-\sqrt{\rho\delta}-\frac{4\rho\delta}{1-\rho\delta}$, lil’ UCB stops after at most $c_{1}\mathbf{H}_{1}\log(1/\delta)+c_{3}\mathbf{H}_{3}$ samples and outputs the optimal arm where $\rho=\frac{2+\varepsilon}{\varepsilon}\left(\frac{1}{\log(1+\varepsilon)}\right)^{1+\varepsilon}$ and $c_{1},c_{3}>0$ are constants that depend only on $\varepsilon,\beta$.

Note that regardless of the choice of $\varepsilon,\beta$ the algorithm obtains the optimal query complexity of $\mathbf{H}_{1}\log(1/\delta)+\mathbf{H}_{3}$ up to constant factors. However, in practice some settings of $\varepsilon,\beta$ perform better than others. We observe from the bounds in the proof that the optimal choice for the exploration constant is $\beta\approx 1.66$ but we suggest using $\beta=1$ and $a=\left(\frac{\beta+2}{\beta}\right)^{2}$. The optimal value for $\varepsilon$ is less evident as it depends on $\delta$ but we suggest using $\varepsilon=0.01$. If one is willing to forego theoretical guarantees, we recommend taking a more aggressive setting with $\varepsilon=0$, $\beta=0.5$, and $a=1+10/n$ which is motivated by simulation results presented later. We prove the theorem via two lemmas, one for the total number of samples and one for the correctness of the algorithm. In the lemmas we give precise constants.

Proof of Theorem 2

Before stating the two main lemmas that imply the result, we first present a finite form of the law of iterated logarithm. This finite LIL bound is necessary for our analysis and may also prove useful for other applications.

Proof We denote $S_{t}=\sum_{s=1}^{t}X_{s}$, and $\psi(x)=\sqrt{2\sigma^{2}x\log\left(\frac{\log(x)}{\delta}\right)}$. We also define by induction the sequence of integers $(u_{k})$ as follows: $u_{0}=1$, $u_{k+1}=\lceil(1+\varepsilon)u_{k}\rceil$.

Step 1: Control of $S_{u_{k}},k\geq 1$. The following inequalities hold true thanks to an union bound together with Chernoff’s bound, the fact that $u_{k}\geq(1+\varepsilon)^{k}$, and a simple sum-integral comparison:

Step 2: Control of $S_{t},t\in(u_{k},u_{k+1})$. Recall that Hoeffding’s maximal inequalityIt is an easy exercise to verify that Azuma-Hoeffding holds for martingale differences with sub-Gaussian increments, which implies Hoeffding’s maximal inequality for sub-Gaussian distributions. states that for any $m\geq 1$ and $x>0$ one has

This implies that the following inequalities hold true (by using trivial manipulations on the sequence $(u_{k})$):

Step 3: By putting together the results of Step 1 and Step 2 we obtain that with probability at least $1-\frac{2+\varepsilon}{\varepsilon}\left(\frac{\delta}{\log(1+\varepsilon)}\right)^{1+\varepsilon}$, one has for any $k\geq 0$ and any $t\in\{u_{k}+1,\ldots,u_{k+1}\}$,

Without loss of generality we assume that $\mu_{1}>\mu_{2}\geq\ldots\geq\mu_{n}$. To shorten notation we denote

The following events will be useful in the analysis:

Let $\gamma=2(2+\beta)^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)$ and $\rho=\frac{2+\varepsilon}{\varepsilon}\left(\frac{1}{\log(1+\varepsilon)}\right)^{1+\varepsilon}$. With probability at least $1-2\rho\delta$ one has for any $t\geq 1$,

Proof We decompose the proof in two steps.

Step 1. Let $i>1$. Assuming that $\mathcal{E}_{1}(\delta)$ and $\mathcal{E}_{i}(\omega)$ hold true and that $I_{t}=i$ one has

which implies $(2+\beta)U(T_{i}(t),\min(\omega,\delta))\geq\Delta_{i}$. Thus using (2) with $c=\frac{\Delta_{i}^{2}}{2(2+\beta)^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)}$ one obtains that if $\mathcal{E}_{1}(\delta)$ and $\mathcal{E}_{i}(\omega)$ hold true and $I_{t}=i$ then

where $\gamma=2(2+\beta)^{2}(1+\sqrt{\varepsilon})^{2}(1+\varepsilon)$, and $\tau_{i}=\frac{\gamma}{\Delta_{i}^{2}}\log\left(\frac{2\log(\gamma(1+\varepsilon)/\Delta_{i}^{2})}{\delta}\right)$.

Since $T_{i}(t)$ only increases when $I_{t}$ is played the above argument shows that the following inequality is true for any time $t\geq 1$:

Step 2. We define the following random variable:

Putting together (6) and (7) with $x=4e\|a\|_{1}\log(1/(\rho\delta))$ one obtains

Let $\rho=\frac{2+\varepsilon}{\varepsilon}\left(\frac{1}{\log(1+\varepsilon)}\right)^{1+\varepsilon}$. If

then for all $i=2,\dots n$ and $t=1,2,\dots$,

with probability at least $1-\sqrt{\rho\delta}-\frac{2\rho\delta}{1-\rho\delta}$.

Proof We decompose the proof in two steps.

Step 1. Let $i>j$. Assuming that $\mathcal{E}_{i}(\omega)$ and $\mathcal{E}_{j}(\delta)$ hold true and that $I_{t}=i$ one has

which implies $(2+\beta)U(T_{i}(t),\min(\omega,\delta))\geq\beta U(T_{j}(t),\delta)$. Thus using (3) with $c=\left(\frac{\beta}{2+\beta}\right)^{2}$ one obtains that if $\mathcal{E}_{i}(\omega)$ and $\mathcal{E}_{j}(\delta)$ hold true and $I_{t}=i$ then

Similarly to Step 1 in the proof of Lemma 2 we use the fact that $T_{i}(t)$ only increases when $I_{t}$ is played and the above argument to obtain the following inequality for any time $t\geq 1$:

Step 2. Using (8) with $\omega=\delta^{i-1}$ we see that

Let $\delta^{\prime}=\rho\delta$. Note that by a simple Hoeffding’s inequality and a union bound one has

and thus we obtain with the above calculations

Treating $\varepsilon$ and factors of $\log\log(\beta)$ as constants, Lemma 2 says that the total number of times the suboptimal arms are sampled does not exceed $(\beta+2)^{2}\left(c_{1}\mathbf{H}_{1}\log(1/\delta)+c_{3}\mathbf{H}_{3}\right)$. Lemma 3 states that only the optimal arm will meet the stopping condition with $a=c_{a}\left(\frac{2+\beta}{\beta}\right)^{2}$. Combining these results, we observe that the total number of times all the arms are sampled does not exceed $(\beta+2)^{2}\left(c_{1}\mathbf{H}_{1}\log(1/\delta)+c_{3}\mathbf{H}_{3}\right)\left(1+c_{a}\left(\frac{2+\beta}{\beta}\right)^{2}\right)$, completing the proof of the theorem. We also observe using the approximation $c_{a}=1$, the optimal choice of $\beta\approx 1.66$.

Implementation and Simulations

In this section we investigate how the state of the art methods for solving the best arm problem behave in practice. Before describing each of the algorithms in the comparison, we briefly describe a LIL-based stopping criterion that can be applied to any of the algorithms.

LIL Stopping (LS) : For any algorithm and $i\in[n]$, after the $t$-th time we have that the $i$-th arm has been sampled $T_{i}(t)$ times and accumulated a mean $\widehat{\mu}_{i,T_{i}(t)}$. We can apply Lemma 1 (with a union bound) so that with probability at least $1-\frac{2+\varepsilon}{\varepsilon}\left(\frac{\delta}{\log(1+\varepsilon)}\right)^{1+\varepsilon}$

for all $t\geq 1$ and all $i\in[n]$. We may then conclude that if $\widehat{i}:=\arg\max_{i\in[n]}\widehat{\mu}_{i,T_{i}(t)}$ and $\widehat{\mu}_{\widehat{i},T_{\widehat{i}}(t)}-B_{\widehat{i},T_{\widehat{i}}(t)}\geq\widehat{\mu}_{j,T_{j}(t)}+B_{j,T_{j}(t)}$ then with high probability we have that $\widehat{i}=i_{*}$.

The LIL stopping condition is somewhat naive but often quite effective in practice for smaller size problems when $\log(n)$ is negligible. To implement the strategy for any fixed confidence algorithm, simply run the algorithm with $\delta/2$ in place of $\delta$ and assign the other $\delta/2$ confidence to the LIL stopping criterion. The algorithms compared were:

Nonadaptive + LS : Draw a random permutation of $[n]$ and sample the arms in an order defined by cycling through the permutation until the LIL stopping criterion is met.

Exponential-Gap Elimination (+LS) : This procedure proceeds in stages where at each stage, median elimination is used to find a $\varepsilon$-optimal arm whose mean is guaranteed (with large probability) to be within a specified $\varepsilon>0$ of the mean of the best arm, and then arms are discarded if their empirical mean is sufficiently below the empirical mean of the $\varepsilon$-optimal arm. The algorithm terminates when there is only one arm that has not yet been discarded (or when the LIL stopping criterion is met).

Successive Elimination : This procedure proceeds in the same spirit as Exponential-Gap Elimination except the landmark arm is equal to $\widehat{i}:=\arg\max_{i\in[n]}\widehat{\mu}_{i,T_{i}(t)}$. One observes that the algorithm’s usual stopping condition and the LIL stopping criterion are one in the same.

lil’UCB (+LS) : The procedure of Figure 1 is run with $\varepsilon=0.01$, $\beta=1$, $a=(2+\beta)^{2}/\beta^{2}=9$, and $\delta=\left(\frac{\nu\varepsilon}{5(2+\varepsilon)}\right)^{1/(1+\varepsilon)}$ for input confidence $\nu$. The algorithm terminates according to Fig. 1 or when the LIL stopping criterion is met.

lil’UCB Heuristic : The procedure of Figure 1 is run with $\varepsilon=0$, $\beta=1/2$, $a=1+10/n$, and $\delta=\nu/5$ for input confidence $\nu$. These parameter settings do not satisfy the conditions of Theorem 2, and thus there is no guarantee that this algorithm will find the best arm. However, as the experiments show, this algorithm performs exceptionally well in practice and therefore we recommend this lil’UCB algorithm in practice. The algorithm terminates according to Fig. 1.

UCB1 + LS : This is the classical UCB procedure that samples the arm

at each time $t$ and terminates when the LIL stopping criterion is met.

We did not compare to PRISM of because the algorithm and its empirical performance are very similar to Exponential-Gap Elimination so its inclusion in the comparison would provide very little added value. We remark that the first three algorithms require $O(1)$ amortized computation per time step, the lil’UCB algorithms require $O(\log(n))$ computation per time step using smart data structuresTo see this, note that the sufficient statistic for lil’UCB for deciding the next arm to sample depends only on $\widehat{\mu}_{i,T_{i}(t)}$ and $T_{i}(t)$ which only changes for an arm if that particular arm is pulled. Thus, it suffices to maintain an ordered list of the upper confidence bounds in which deleting, updating, and reinserting the arm requires just $O(log(n))$ computation. Contrast this with a UCB procedure in which the upper confidence bounds depend explicitly on $t$ so that the sufficient statistics for pulling the next arm changes for all arms after each pull, requiring $\Omega(n)$ computation per time step., and UCB1 requires $O(n)$ computation per time step. Due to the poor computational scaling of UCB1 with respect to the problem size $n$, UCB1 was not run on all problem sizes due to practical time constraints.

Three problem scenarios were considered over a variety problem sizes (number of arms). The “1-sparse” scenario sets $\mu_{1}=1/4$ and $\mu_{i}=0$ for all $i=2,\dots,n$ resulting in a hardness of $\mathbf{H}_{1}=4n$. The “$\alpha=0.3$” and “$\alpha=0.6$” scenarios consider $n+1$ arms with $\mu_{0}=1$ and $\mu_{i}=1-(i/n)^{\alpha}$ for all $i=1,\dots,n$ with respective hardnesses of $\mathbf{H}_{1}\approx 3/2n$ and $\mathbf{H}_{1}\approx 6n^{1.2}$. That is, the $\alpha=0.3$ case should be about as hard as the sparse case with increasing problem size while the $\alpha=0.6$ is considerably more challenging and grows super linearly with the problem size. See for an in-depth study of the $\alpha$ parameterization. All experiments were run with input confidence $\delta=0.1$. All realizations of the arms were Gaussian random variables with mean $\mu_{i}$ and variance $1/4$The variance was chosen such that the analyses of algorithms that assumed realizations were in $$and used Hoeffding’s inequality were still valid using sub-Gaussian tail bounds with scale parameter$1/2$..

Each algorithm terminates at some finite time with high probability so we first consider the relative stopping times of each of the algorithms in Figure 2. Each algorithm was run on each problem scenario and problem size 40 times. The first observation is that Exponential-Gap Elimination (+LS) appears to barely perform better than uniform sampling with the LIL stopping criterion. This confirms our suspicion that the constants in median elimination are just too large to make this algorithm practically relevant. It should not come as a great surprise that successive elimination performs so well because even though it is suboptimal in the problem parameters, its constants are small leading to a practical algorithm. The lil’UCB+LS and UCB1+LS algorithms seem to behave comparably and lead the pack of algorithms with theoretical algorithms. The LIL stopping criterion seems to have a large impact on performance of the regular lil’UCB algorithm, but it had no impact on the lil’UCB Heuristic variant (not plotted). While lil’UCB Heuristic has no theoretical guarantees of outputting the best arm, we remark that over the course of all of our tens of thousands of experiments, the algorithm never failed to terminate with the best arm.

In reality, one cannot always wait for an algorithm to run until it terminates on its own so we now explore how the algorithms perform if the algorithm must output an arm at every time step before termination (this is similar to the setting studied in ). For each algorithm, at each time we output the arm with the highest empirical mean. Because the procedure for outputting the arm is the same across algorithms, measuring how often this output arm is the best arm is a measure of how much information is being gathered by the algorithm’s sampling procedure. Clearly in the beginning, the probability that a sub-optimal arm is output by any algorithm is very close to 1. However, as time increases we know that this probability of error should decrease to at least the desired input confidence, and likely, to zero. Figure 3 shows the “anytime” performance of the algorithms for the three scenarios and unlike the empirical stopping times of the algorithms, we now observe large differences between the algorithms. Each experiment was repeated 5000 times. Again we see essentially no difference between nonadaptive sampling and the exponential-gap procedure. While in the stopping time plots of Figure 2 successive elimination appears neck-and-neck with the UCB algorithms, we observe in Figure 3 that the UCB algorithms are collecting sufficient information to output the best arm at least twice as fast as successive elimination. This tells us that the stopping conditions for the UCB algorithms are still too conservative in practice which motivates the use of the lil’UCB Heuristic algorithm which appears to perform very strongly across all metrics.

References

Appendix A Condensed Proof of Lower Bound

In the following we show a weaker result than what is shown in ; nonetheless, it shows the $\log\log$ term is necessary.

We rely on two intuitive facts, each which justified more formally in .

The form of an optimal test is a generalized sequential probability ratio test (GSPRT), which continues sampling while

and stops otherwise, declaring $\Delta>0$ if $\sum_{j=1}^{t}X_{j}\geq B_{t}$, and $\Delta<0$ if $\sum_{j=1}^{t}X_{j}\leq-B_{t}$ where $B_{t}>0$ is non-decreasing in $t$. This is made formal in .

The argument proceeds as follows. If (9) is holds, then the error probability is $1/2$. So we can focus on threshold sequences satisfying $\lim_{t\rightarrow\infty}\frac{B_{t}}{\sqrt{2t\log\log t}}\geq(1+\varepsilon)$ for some $\varepsilon>0$. In other words, for all $t>t_{1}$ some $\varepsilon>0$, some sufficiently large $t_{1}$

Let $S_{t}^{(\Delta)}=\sum_{j=1}^{t}X_{j}$ for $X_{j}\overset{iid}{\sim}\mathcal{N}(\Delta,1)$. Without loss of generality, assume $\Delta>0$. Additionally, suppose $\Delta$ is sufficiently small, such that both $t_{0}(\Delta)>t_{1}(\varepsilon)$ and $\Delta\leq\varepsilon$ (in the following steps we consider the limit as $\Delta\rightarrow 0$). We have

where (A) holds when $\varepsilon\geq\Delta$ and (11) holds by removing the conditioning, and then by increasing the number of terms in the intersection. To see that (A) holds, note that $\frac{2\log\log t}{t}\geq\left(\frac{2\Delta}{\varepsilon}\right)^{2}$ for all $t\leq t_{0}(\Delta)$, which is easily verified when $\varepsilon\geq\Delta$ since

Taking the limit as $\Delta\rightarrow 0$, for any $\varepsilon>0$, gives

which follows from (11), as the first term is non-zero for any $\Delta$ (including $\Delta=0$) since $t_{1}(\varepsilon)<\infty$ and $B_{t}>0$, and the second term is non-zero by the LIL for any $\varepsilon>0$. Note that a finite bound on the second term can be obtained as in Section 2.