I've implemented in MATLAB the UCB algorithm for gaussian bandits with zero mean and unit variance (these means were themselves sampled from a gaussian prior of zero mean and unit variance). Now I want to plot the accumulated regret as a function of time against the Lai&Robbins bound.

The plot shows that the Lai&Robbins bound is above the other UCB regrets instead of being beneath them all and I'm trying to understand what I did wrong.

First, can I even use UCB with a normal distribution (as it's not bounded [0,1])? I also tried to scale it by giving it a mean of 0.5 and a small variance so the pdf won't get far off the [0,1] bounds but it still shows this pattern.

Second,Does the Lai-Robbins bound holds for this distribution or is it merely for Bernoulli distributions? If not,Is there another useful bound for this case?

The Lai-Robbins bound I used is this one:

$$\lim_{t\to \infty} L_t \ge \log t \sum_{a|\Delta_a>0} \frac{\Delta_a}{KL(R^a||R^{a^*})}$$

and the results I got for 10 arms are:

enter image description here

where the different graphs are for different c values(the UCB parameter).

  • $\begingroup$ Could you post a citation/more detail on which bound and algorithm you use and maybe a figure showing the discrepancy? I should have time for a more thorough answer tomorrow if someone else doesn't get to it first. The short answer is that there are (lower) bounds for the case you are considering (including ones developed by Lai & Robbins), but in general you can't just use results derived for a [0,1] bounded variable case (Reverdy's work might be helpful). $\endgroup$ – combo Aug 24 '17 at 0:00

tl;dr If you run the simulation longer things work as expected.

UCB definition

First off, let's be explicit about what we mean by a UCB algorithm. Since we have a small number of arms, we first select each arm once. Define $n_j(t)$ as the number of times arm $j$ has been selected over the first $t$ actions, $\hat{\mu}_j^t$ as the sample average for arm $j$. At iteration $t > N$, we select an action which maximizes the upper confidence bound, $$\hat{\mu}_j^t + \sqrt{\frac{c \log(t) }{n_j(t-1)}}.$$

The parameter $c$ controls how much the algorithm prioritizes exploration. A standard choice is $c=6$ (e.g. in these notes). In your experiments, you set $c = 1, \sqrt{2}, 2$.

Lower bound: Gaussian case

The lower bound is derived by using a bound on the expected number of times a suboptimal arm is selected. Specifically Lai and Robbins showed that for suboptimal $j$, $\mathbb{E}[n_j(t)] \ge \frac{\log(t)}{KL(p_j \| p_{j^*})} = \frac{\log(t)}{\Delta_j^2}$, where the last inequality holds for the standard Gaussian case. From this it's easy to get the gap dependent lower bound as $$\sum_{j \neq j^*} \mathbb{E}[n_j(t)] \Delta_j = \sum_{j \neq j^*} \frac{2}{\Delta_j} \log(t)$$

Simulations and Hypothesis

I've run simulations for the setting you describe (means from the standard normal, and standard normal measurement noise). Since $c=6$ shows up in the literature, I used somewhat different values ($c=2,3,6$) than you did. The cumulative regret over 1 million iterations averaged over 100 runs is plotted below:

Regret over 1,000,000 iterations

Two take-aways:

  1. Over a long time horizon, the lower bound is accurate. Note that even though $c=2$ is still below the lower bound, the gap is shrinking over time.

  2. Choosing overly small $c$ may lead to bad upper bounds on the regret, especially if the algorithm fails to distinguish between the best and second best arm.

This still leaves the question of why the bound is violated for small $t$, since the Lai & Robbins bound should hold not just at the limit as $t\to \infty$. I'll update my answer if I figure out what's going on there.

| cite | improve this answer | |
  • $\begingroup$ First, thanks a lot. Second, in the definition I use for UCB, the c parameter is outside the square root so the difference between us is smaller. Another fact which I just found is that the original article of Lai and Robbins (Asymptomatically Efficient Adaptive Allocation Rules) states that the log coefficient actually contains an o(1) unknown term so it might explain the gap you got and might also explain why most articles choose not to plot it against other curves. $\endgroup$ – Gabizon Aug 30 '17 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.