[Proof of Theorem ]
We first state without proof a crucial lemma from [1]} which we will use in our analysis.
[[1]}]

Let \(_t(\, \cdot \, ) = (\, \cdot \, | A_1,X_1,\dots ,A_{t-1},X_{t-1})\)  be the probability measure conditioned on the history up to time \(t-1\)  and \(G_{is} = _t(E_i^c(t) | T_{i,t} = s)\) , where \(E_i(t)\)  is any specified event for arm \(i\)  at time \(t\) . Then
\([T_{i,n}] \le \sum _{s=0}^{n-1} {\frac{1}{G_{1s}} - 1} + \sum _{s=0}^{n-1} {G_{is} > \frac{1}{n}} + 1.\) 
