I am referring to the paper Finite-time Analysis of the Multiarmed Bandit Problem paper.

The Theorem 1 in the paper is,

Theorem 1: For all $K > 1$, if policy UCB1 is run on $K$ machines having arbitrary reward distributions $P_1,...,P_K$ with support in $[0,1]$, then its expected regret after any number $n$ of plays is at most

$\Big[8 \sum_{i:\mu_i < \mu^{*}} \Big( \frac{\ln n}{\Delta_i} \Big)\Big] + \Big(1+ \frac{\pi^2}{3}\Big) \Big( \sum_{j=1}^{K} \Delta_j\Big)$

where $\mu_1,...,\mu_K$ are the expected values of $P_1,..., P_K$.

The UCB1 policy given in the paper is as follows,

Init: Play each machine once.

Loop: Play machine $j$ that maximizes $\bar{x}_j + \sqrt{\frac{2 \ln n}{n_j}}$, where $\bar{x}_j$ is the average reward obtained from machine $j$, $n_j$ is the number of times machines $j$ has been played so far, and $n$ is the overall number of plays done so far.

I am looking at the Proof of the Theorem 1 and trying to understand it. The proof is as follows.

Let $c_{t,s}= \sqrt{(2 \ln t)/s}$. $t$ is the total number of rounds and $s$ is a specific number of times an arm is played. For any arm $i$, we upper bound $T_i(n)$ on any sequence of plays, where $T_i(n)$ is the number of times arm $i$ has been played by policy $A$ in the first $n$ plays. More precisely, for each $t \geq 1$ we bound the indicator function of $I_t = i$ as follow. We define the random variables $I_1, I_2,\cdots$ where $I_t$ denotes the arm played at time $t$. Everything related to the optimal arm is associated with an $*$. Let $l$ be an arbitrary positive integer. \begin{equation} T_i(n) = 1+ \sum_{t=K+1}^{n} \{I_t =i\} (1) \tag{1} \end{equation} \begin{equation} \leq l +\sum_{t=K+1}^{n} \{I_t =i, T_i(t-1) \geq l\} \tag{2}\end{equation} \begin{equation} \leq l +\sum_{t=K+1}^{n} \{\bar{X}^{*}_{T^{*}(t-1)}+c_{t-1,T^{*}(t-1)} \leq \bar{X}_{i,T_{i}(t-1)}+c_{t-1,T_{i}(t-1)}, T_{i}(t-1) \geq l\} \tag{3}\end{equation} \begin{equation} \leq l +\sum_{t=K+1}^{n} \{\min_{0<s<t}\bar{X}^{*}_{s}+c_{t-1,s} \leq \max_{l \leq s_i < t} \bar{X}_{i,s_i}+c_{t-1,s_i} \} \tag{4}\end{equation} \begin{equation} \leq l + \sum_{t=1}^{\infty} \sum_{s=1}^{t-1} \sum_{s_i=l}^{t-1}\{\bar{X}^{*}_{s}+c_{t-1,s} \leq \bar{X}_{i,s_i}+c_{t-1,s_i}\} \tag{5}\end{equation} Now observe that $\bar{X}^{*}_{s}+c_{t-1,s} \leq \bar{X}_{i,s_i}+c_{t-1,s_i}$ implies that at least one of the following must hold \begin{equation} \bar{X}^{*}_{s} \leq \mu^{*} - c_{t,s} \tag{6}\end{equation} \begin{equation} \bar{X}_{i,s_i} \geq \mu_{i} - c_{t,s_i} \tag{7}\end{equation} \begin{equation} \mu^{*} < \mu_{i} + 2c_{t,s_i} \tag{8} \end{equation} Using Chernoff-Hoeffding bound we can say the following \begin{equation} P\{\bar{X}^{*}_{s} \leq \mu^{*} - c_{t,s}\} \leq e^{-4\ln t} = t^{-4} \tag{9}\end{equation} \begin{equation} P\{\bar{X}_{i,s_i} \geq \mu^{i} - c_{t,s_i}\} \leq e^{-4\ln t} = t^{-4} \tag{10}\end{equation} For $l=[(8 \ln n)/\Delta^{2}_i]$, (8) is false. In fact \begin{equation} \mu^{*}-\mu_i -2\sqrt{2(\ln t)/s_i} \geq \mu^{*}-\mu_i - \Delta_i = 0 \text{ for } s_i \geq (8 \ln n)/ \Delta^{2}_{i}. \tag{11} \end{equation} So we get, \begin{equation}E[T_i(n)] \leq [\frac{8 \ln n}{\Delta^{2}_{i}}] + \sum_{t=1}^{\infty} \sum_{s=1}^{t-1}\sum_{s_i=[(8 \ln n)/\Delta^{2}_i]}^{t-1} \times (P\{\bar{X}^{*}_{s} \leq \mu^{*} - c_{t,s}\}+P\{\bar{X}_{i,s_i} \geq \mu^{i} - c_{t,s_i}\}) \tag{12}\end{equation} \begin{equation}\leq [\frac{8 \ln n}{\Delta^{2}_{i}}]+ \sum_{t=1}^{\infty} \sum_{s=1}^{t-1}\sum_{s_i=1}^{t-1} 2 t^{-4} \tag{13}\end{equation} \begin{equation} \leq [\frac{8 \ln n}{\Delta^{2}_{i}}]+1+\frac{\pi^2}{3}\tag{14}\end{equation} which concludes the proof.

I would like to understand several things in this proof.

  1. How did the authors come up with the inequality in Equation (3). I don't understand how the mean reward of the optimal arm can be less than the mean reward of the $i$ arm?
  2. For Equarion (4) why are they selecting the $\min$ of the optimal arm while they are selecting the $\max$ of the $i$ arm? Why are the ranges different? What is the logic behind it?
  3. What is that $\times$ symbol for in Equation (12) when calculating the expected value of $T_i(n)$?
  4. How did authors go from Equation (13) to Equation (14) and get the $\pi$ values. Is there standard math theorem for it?

Thanks in advance for the help after going through the trouble to read thing long question.


1 Answer 1

  1. Inequality (3)

This inequality is due to the fact that we chose arm $i$ at time $t$, so it follows by construction of the algorithm. I think the confusion you have is that these are not the true means here, but the upper confidence bounds.

  1. Inequality (4)

The authors are looking for an event that occurs more frequently (but not too much so) than selecting a suboptimal arm. In this case, they compare the most pessimistic estimate for $\bar{X}^*$ up to time $t$ with the most optimistic estimate of arm $i$ between times $\ell$ and $t$ (note that in (2) they account for the first $\ell$ steps).

  1. Equation (12)

I believe $\times$ is just to emphasize that this is a continuation of the equation on the previous line.

  1. Equation (14)

Yes,the formula used is $$\sum_{t=1}^\infty t^{-2} = \frac{\pi^2}{6}$$ There's a separate question covering this identity and some proofs.

If we evaluate the sum, we get $$\sum_{t=1}^\infty \sum_{s=1}^{t-1} \sum_{s_i=1}^{t-1} 2t^{-4} \le \sum_{t=1}^\infty \sum_{s=1}^t \sum_{s_i=1}^t 2t^{-4} = \sum_{t=1}^\infty 2t^{-2} = 2\frac{\pi^2}{6} = \frac{\pi^2}{3} $$ Just a note that in the original paper, equation (14) does not have the ceiling operator (that's what the +1 is there for)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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