# Multi-armed Bandit :a lower bound for the expected sample size from an inferior population

I am reading Asymptotically efficient adaptive allocation rules to study the multi-armed bandit problem, and have a question.

The question is about the proof of Theorem 2.

THEOREM 2. Assume that $$I(\theta, \lambda)$$ satisfies (1.6) and (1.7) and that $$\Theta$$ satisfies (1.9). Fix $$j\in \{1, \dots, k\}$$, and define $$\Theta_j$$ and $$\Theta_j^*$$ by (2.1). Let $$\varphi$$ be any rule such that for every $$\theta \in \Theta_j^*$$, as $$n\to \infty$$ $$\sum_{i\neq j}E_\theta T_n(i) = o(n^a)$$ where $$T_n(i)$$, defined in (1.2), is the number of times that the rule $$\varphi$$ samples from $$\Pi_i$$ up to stage $$n$$. Then for every $$\theta \in \Theta_j$$ and every $$\epsilon > 0$$, $$\lim\limits_{n\to \infty}P_\theta\{T_n(j) \geq (1-\epsilon)(\log{n})/I(\theta_j, \theta^*)\}=1,$$ where $$\theta^*$$ is defined in (1.4), and hence $$\liminf\limits_{n\to\infty}E_\theta T_n(j)/\log{n}\geq 1/I(\theta_j, \theta^*).$$

The proof starts as follows:

Proof. To fix the ideas let $$j=1$$, $$\theta \in \Theta_1$$, and $$\theta^*=\theta_2$$. Then $$\mu(\theta_2)>\mu(\theta_1)$$ and $$\mu(\theta_2)\geq \mu(\theta_1)$$ for $$3\leq i\leq k$$. Fix any $$0<\delta <1$$. In view of (1.6), (1.7), and (1.9), we can choose $$\lambda \in \Theta$$ such that $$\mu(\lambda)>\mu(\theta_2) \text{ and } |I(\theta_1, \lambda)-I(\theta_1, \theta_2)|<\delta I(\theta_1, \theta_2).$$ Define the new parameter vector $$\gamma=(\lambda, \theta_2, \dots, \theta_k)$$. Then $$\gamma\in\Theta_1^*$$, so by (2.2) $$E_\gamma(n-T_n(1))=\sum_{h\neq 1}E_\gamma(T_n(h))=o(n^a)$$ with $$0, and therefore $$(n-O(\log{n}))P_\gamma\{T_n(1)<(1-\delta)(\log{n})/I(\theta_1, \lambda)\}\leq E_\gamma(n-T_n(1))=o(n^a)$$ ...

What I do not understand is the last inequality. How is this derived?

\begin{align} E_\gamma(n-T_n(1)) &= \int_\Omega (n-T_n(1))\\ &\geq \int_{\{T_n(1)<(1-\delta)(\log{n})/I(\theta_1, \lambda)\}}(n-T_n(1))\\ &\geq \int_{\{T_n(1)<(1-\delta)(\log{n})/I(\theta_1, \lambda)\}}(n-(1-\delta)(\log{n})/I(\theta_1, \lambda))\\ &\geq (n-(1-\delta)(\log{n})/I(\theta_1, \lambda))P_\gamma\{T_n(1)<(1-\delta)(\log{n})/I(\theta_1, \lambda)\} \end{align}