0
$\begingroup$

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<a<\delta$, 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?

$\endgroup$
0
$\begingroup$

It is just a restriction of the integral domain:

\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}

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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