In the context of minimizing regret among $\varepsilon$-greedy strategies for a multi-armed bandit problem, a number of sources* present the following decay schedule with a claim that it has logarithmic asymptotic total regret:

$$ c > 0 \\[1ex] d = \min_{a \in \mathcal{A} \mid \Delta_a > 0} \Delta_a \\[1ex] \varepsilon_t = \min \, \biggl\{ 1, \frac{c \lvert \mathcal{A} \rvert}{d^2 t} \biggr\} $$

Here, $\Delta_a = \max_{a' \in \mathcal{A}} V(a') - V(a)$ is the value gap between action $a$ and the best value. That the schedule depends on these gaps of course means that it is not implementable without knowing the true value function, so it is not useful in practice.

I understand some parts of this presentation, but—critically—I haven’t been able to find any specification for the constant $c$. Surely $c$ cannot be an arbitrary positive constant, because then we could pick $c = d^2$ and the schedule would be easily implementable without knowing the true gap values.

It’s also surprising to me that scaling a simple hyperbolic schedule by a constant factor (namely, $c \lvert \mathcal{A} \rvert / d^2$) can change the asymptotic cumulative regret from linear to logarithmic. Why should I expect this to be the case?

* Some such sources:


Let's consider the multi-armed bandits with gaussian noise with fix variance $\sigma $. In that case, the regret of any consistent policy is lower bounded by $$R_T(\pi) \geq \sum_{i=1}^K\frac{\sigma^2\log{T}}{2\Delta_i} + o(\log{T})$$ "Consistent" means that we exclude stupid policy like the policy which always pull the first arm. Indeed, this policy may have 0 regret on any problem which have the first arm as best arm. However, on any other problem it would have linear regret : hence, it is not "consistent". This result is known as Lai and Robbins' lower bound. They have derived a similar result for the Bernoulli's case (which is in fact harder than the Gaussian case).

Few comments :

  1. The logarithmic rate is asymptotically impossible to beat as soon as we want to be consistent (= not extremely bad on some instances).
  2. A good asymptotic policy should try to recover this logarithmic rate with the smallest constant. It happens that some policies (e.g. KL-UCB, Bayes-UCB, Thomson Sampling) have an upper bound with this exact constant.
  3. $\frac{\sigma^2\log{T}}{2\Delta_i}$ regret means $\frac{\sigma^2\log{T}}{2\Delta_i^2}$ errors of size $\Delta_i$
  4. If your amount of exploration is smaller than $\frac{\sigma^2\log{T}}{2\Delta_i^2}$, then you will be suboptimal.
  5. If your amount of exploration is greater than $\frac{\sigma^2\log{T}}{2\Delta_i^2}$, then you will be suboptimal.
  6. As a rule of thumb (5) is better than (4). Indeed, not enough exploration can quickly means linear regret (too greedy). While too much exploration means "logarithmic rate with a large constant" (too conservative).

Now, if we go back to $\epsilon$-greedy, the best would be to tune one $\epsilon_{i,t}$ per arm $i$ and round $t$. We could tune $$\epsilon_{i,t} = \min \left\{1, \frac{\sigma^2}{2\Delta_i^2 t}\right\}$$ which would lead to exactly $\frac{\sigma^2\log{T}}{2\Delta_i^2}$ cumulative exploration. However, if you don't know $\Delta_i$ but have a rough idea of their minimum $d$, you may want to have a single tuning for all the arm $$\epsilon_t = \min \left\{1, \frac{\sigma^2|\mathcal{A}|}{2d^2 t}\right\}$$ ($\epsilon_{i,t}$ is the probability of selecting arm $i$, $\epsilon_t$ is the probability of selecting one arm at random. This is why there is a factor $\mathcal{A}$.)

This is your formula with $c=\frac{\sigma^2}{2}$. Indeed according to (6), it is better to have too much exploration on large $\Delta_i$ than too little on small one. This is why we take the minimum (which maximizes exploration). Note that I am not 100% sure about $c=\sigma^2/2$ (only 80% sure for theory, but anyway, in practice you may use a smaller value). The important thing is that it is a "reasonnable" number which scales with the variance, and if you "set" it equals to $d^2$ to avoid tuning, you will be in trouble if $d<<1$. In that case, at least one of the arm requires a lot of exploration that you will not provide, and you will suffer a (near-)linear regret rate.

To avoid this bad tuning effect, you may want to use policy which are adaptive to $\Delta_i$s like (KL-)UCB or Thomson sampling.

Ressource :

Tor Lattimore and Csaba Szepesvári's Book

Sébastien Bubeck's blog post about Lai and Robbins bound


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.