Magical event in the proof of lower bound in multi-armed bandits

Question

The proof of lower bound on regret of a two-armed bandit introduces this magical event.

\begin{equation} C_n = \{ T_2(n) > \frac{1- \epsilon}{kl(\mu_2, \mu_2^\prime)} \ln n, \hat{kl}_{T_2(n)} \leq (1 - \frac{\epsilon}{2} ln(n))\}, \end{equation}

where $T_2(n)$ in the number of time arm 2 was played until time $n$, $\epsilon > 0$, $\hat{kl}_s$ is the empirical KL-divergence of $kl(\mu_2, \mu_2^\prime)$ and $kl(p, q) = p \ln \frac{p}{q} + (1-p) \ln \frac{1-p}{1-q}$. I have read this (or similar) proof in a number of papers but none of the papers tell how they came up with the event $C_n$. Could someone tell how was this event thought of?

Answer 1

Let $$A_n=\{T_2(n)>\frac{1-\epsilon}{kl(\mu_2, \mu'_2)}\ln(n)\}$$ and $$B_n=\{\hat{kl}_{T_2(n)}\le (1-\frac{\epsilon}{2})\ln(n)\}.$$ Then $C_n=A_n\cap B_n$. The actually effective part is $B_n$. In the common proof of lower bound, we first show $\mathbb{P}(C_n)=o(1)$ and then $\mathbb{P}(A_n)=o(1)$. To explain how we get the expression of $C_n$, we may understand the proof in another way. The proof of $\mathbb{P}(C_n)=o(1)$ does not depend on $A_n$. It just shows $\mathbb{P}(B_n)=o(1)$. We then derive $\mathbb{P}(A_n)=o(1)$ by showing $A_n$ is almost a subset event of $B_n$, i.e. $\mathbb{P}(A_n\cap B_n^c)=o(1)$.