\( \newcommand{\argmax}{\operatorname{arg\,max}\limits} \) \( \newcommand{\P}[1]{\mathbf{P} \left(#1\right)} \) \( \newcommand{\E}{\mathbf{E}} \) \( \newcommand{\R}{\mathbb{R}} \) \( \newcommand{\set}[1]{\left\{#1\right\}} \) \( \newcommand{\floor}[1]{\left \lfloor {#1} \right\rfloor} \) \( \newcommand{\ceil}[1]{\left \lceil {#1} \right\rceil} \) \( \newcommand{\logp}{\log_{+}\!} \) \( \let\epsilon\varepsilon\)

Anytime OCUCB

The anytime OCUCB is yet another algorithm designed for minimising the regret in finite-armed bandits with subgaussian noise. You can download the preprint here. For the notation used in this page see “finite-armed bandit notation”. We will assume a $1$-subgaussian noise model so the reward in round $t$ is $X_t = \mu_{I_t} + \text{noise}$ where $\text{noise}$ is $1$-subgaussian.

The algorithm is similar to UCB, but with a carefully tuned confidence parameter that adapts in a near-optimal way to the unknown environment parameters. In the first $K$ rounds the algorithm chooses $I_t = t$ and subsequently
\begin{align*}
I_t = \argmax_i \hat \mu_i(t-1) + \sqrt{\frac{2\eta \log B_i(T-1)}{T_i(t-1)}}
\end{align*}
where $\eta > 1$ is some tuneable parameter and
\begin{align*}
B_i(t-1) = t \log (t) \left(\sum_{j=1}^K \min\set{T_i(t-1), T_j(t-1)^{\frac{1}{2}} T_i(t-1)^{\frac{1}{2}}}\right)^{-1}
\end{align*}
This algorithm looks complicated, but we will shortly see it is quite intuitive. First though, the regret guarantee is
\begin{align*}
R_\mu(n) \leq C_\eta \sum_{i:\Delta_i > 0} \left(\Delta_i + \frac{1}{\Delta_i} \log\left(\frac{n\Delta_i^2 \log(n)}{k_i}\right)\right)
\end{align*}
where $C_\eta > 0$ is some constant that depends only on $\eta$ and $k_i = \sum_{j=1}^K \min\set{1, \Delta_i / \Delta_j}$.
Finally it is also possible to show that
\begin{align*}
\limsup_{n\to\infty} R_\mu(n) / \log(n) \leq \sum_{i:\Delta_i > 0} \frac{2\eta}{\Delta_i}
\end{align*}
which is just a factor of $\eta$ away from the optimal asymptotic rate.

So why is this bound intuitive? Assume the noise model is a standard Gaussian and let $\mu \in [0,1]^K$ be a fixed mean payoff vector. Let $i$ be some suboptimal arm and $\mu’ \in \R^K$ be given by $\mu’_j = \mu_j$ for $j \neq i$ and $\mu’_i = \mu_i + 2\Delta_i$, which is chosen so that arm $i$ is optimal for mean vector $\mu’$. Then $\Delta’_j = \mu’_i – \mu’_j \approx \max\{\Delta_i, \Delta_j\}$.
Now suppose that $\E[T_i(n)] \leq \Delta_i^{-2} \log(1/\delta) / 2$ for some $\delta \in (0,1)$, then the algorithm cannot statistically tell the difference between $\mu$ and $\mu’$ with a failure probability smaller than $\delta$. From this it can be shown (see the paper) that if $\delta \geq C k_i \log(n) / (n \Delta_i^2)$, then letting $\mathbb{P}’$ be the measure on outcomes when the algorithm operates in environment $\mu’$ leads to
\begin{align*}
R_{\mu’}(n)
&\geq \frac{n\Delta_i}{2} \mathbb{P}’\left\{T_i(n) < n/2\right\} \geq \frac{n\Delta_i \delta}{4} \\ &\geq \frac{C k_i \log(n)}{4\Delta_i} = \frac{C}{4}\sum_{j=1}^K \frac{\min\set{1, \Delta_i/\Delta_j} \log(n)}{\Delta_i} \\ &= \frac{C}{4}\sum_{j=1}^K \frac{1}{\max\set{\Delta_i, \Delta_j}} \log(n) \approx \frac{C}{4}\sum_{j : \Delta_j > 0} \frac{1}{\Delta’_j} \log(n)
\end{align*}
Unless $C$ is very small, then last quantity is bigger than we would like, since this is already achievable by UCB. This justifies that $\delta$ should be $O\left(\frac{k_i \log(n)}{n\Delta_i^2}\right)$.

Of course the algorithm doesn’t know $\Delta$ or which arm is optimal. The trick is to notice that arms $j$ with $\Delta_j \leq \Delta_i$ will be played about as often as $i$ and arms $j$ with $\Delta_j > \Delta_j$ will be played about as much as arm $i$ until $T_j(t-1) \approx \Delta_j^{-2}$. Then at the critical region when $T_i(t-1) \approx \Delta_i^{-2}$ we have
\begin{align*}
\sum_{j=1}^K \min\set{T_i(t-1), T_j(t-1)^{\frac{1}{2}} T_i(t-1)^{\frac{1}{2}}}
\approx \sum_{j=1}^K \min\set{\Delta_i^{-2}, \Delta_j^{-1} \Delta_i^{-1}}
= \frac{k_i}{\Delta_i^{2}}
\end{align*}
Then by making the approximation $t \log(t) \approx n \log(n)$ we have
\begin{align*}
1/B_i(t-1) \approx \frac{k_i}{n\Delta_i^2 \log(n)}
\end{align*}
which except for the logarithmic term is close to the optimal value.