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?


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

  • $\begingroup$ Can one come up with this without knowing the proof? If I wanted to prove this without the known proof why would I come up with this made up event? $\endgroup$ – Shishir Pandey Nov 5 '16 at 6:31
  • $\begingroup$ I do not understand what you mean by "this". Could you clarify? $\endgroup$ – Qinshi Wang Nov 6 '16 at 6:02
  • $\begingroup$ "This" is the event C_n. One can go through the proof and understand how the result follows. But when Lai and Robbins were proving it for the first time why did they come up with this event? Why would one think that such an event will help prove the lower bound? $\endgroup$ – Shishir Pandey Nov 8 '16 at 2:13
  • $\begingroup$ In my opinion, it is just about writing style. They did not mention C_n comes from A_n and B_n and wrote directly about C_n. Technically, to bound C_n is as effective as to bound B_n. $\endgroup$ – Qinshi Wang Nov 10 '16 at 6:42

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.