finite Upper bound for UCB1multi-armed bandits 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.

*

*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?

*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?

*What is that $\times$ symbol for in Equation (12) when calculating the expected value of $T_i(n)$?

*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.
 A: *

*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. 


*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).


*Equation (12)


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


*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)
