UCB: where is delta and standard deviation?

Question

One of the most popular multi-armed bandit is the Upper Confidence Bound (UCB) line of algorithms (see references below).

My understanding is that we try to find the largest plausible estimate of the mean of arm $i$: $$\hat\mu_i(t-1) + \sqrt{\frac{2\sigma}{n_i(t-1)}\log\frac{1}{\delta}},$$ where $\hat\mu_i(t)$ is the average reward of arm $i$ until time $t$ and $n_i(t)$ is the number of times arm $i$ has been chosen.

The second term of the formula is the confidence tail. We assume that rewards are $\sigma^2$-subgaussian which (by definition) means we have the upper-bound $\text P(\hat\mu\geq\varepsilon)\leq\exp(-\frac{n\varepsilon^2}{2\sigma})$. By setting $\delta=\exp(-\frac{n\varepsilon^2}{2\sigma})$, we have that $\text P(\hat\mu\geq\sqrt{\frac{2\sigma}{n}\log\frac{1}{\delta}}) \leq \delta$.

In graphical terms, I believe (at each iteration) we want to find the arm that maximizes:

My question is two-fold:

1. Isn't this sensitive to the magnitude of the mean and deviation? What if I don't know the deviation $\sigma$ of my rewards? Most authors seem to assume $\sigma=1$, but this just seems wrong. In my particular case, UCB gives bad results because of this (I think). Should I just try different values instead of $\sigma$? Should I try somehow to estimate it? Likewise, I am not completely sure if my $\mu=0$ -- is this a problem?
2. Why do so many people replace $\frac{1}{\sigma}$ by something like $1/\delta=f(t)=1+t\log^2(t)$? I could not find this from the original paper (which I found hard to read) or any of the references.

I guess my question is: why do I see so many implementations like this?

formula = mu + np.sqrt(2*np.log(it)/n)

Why do $\sigma$ and $\delta$ disappear?

References:

1. A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit (2015)
2. Bandit Algorithms blog

Answer 1

1) It shouldn't necessarily be sensitive to the mean, but it will definitely be sensitive to the variance. Most authors do assume the reward distribution (or rather, the noise $X - \mathbb{E}[X]$) is 1-subgaussian, mostly for convenience. You'll need to adjust the algorithm if you believe your variance is higher than 1. See the UCB-Tuned algorithm on page 15 of your first reference. It shouldn't matter if your $\mu \neq 0$. If the means of all the reward distributions had to be 0, then bandits would be a useless construction.

2) The specific $1/\delta$ you mention is the constant that is asymptotically optimal. See chapter 8 of http://downloads.tor-lattimore.com/banditbook/book.pdf

To answer your last question: Tthe $\sigma$ disappears likely due to assuming $\sigma=1$. The $\delta$ disappears because you need to make some choice for $\delta$, in this case it looks like that would be part of the "it" expression.