I am reading the multi-armed bandit survey by Bubeck and Bianchi. This question is for the lower bound section (2.3) of the survey. Let us define $kl(p, q) = p \log \frac{p}{q} + (1- p) \log \frac{1-p}{1-q}$.

  1. The authors consider a $2$ arm bandit problem with Bernoulli arms such that the expected rewards, $\mu_1, \mu_2$ of arm $1$ and arm $2$ respectively are such that $\mu_2 < \mu_1 < 1$, we will denote this problem by $\mathcal{B}_1(\mu_1, \mu_2)$ or simply $\mathcal{B}_1$. Then for $\epsilon > 0$, $\exists$ $\mu_2^\prime \in (\mu_1, 1)$ such that \begin{equation} kl(\mu_2, \mu_2^\prime) \leq (1 + \epsilon)kl(\mu_2, \mu_1). \end{equation} Authors consider another problem which has the arm $2$ replaced with the arm $2^\prime$ with success probability $\mu_2^\prime$, i.e. $\mathcal{B}_2(\mu_1, \mu_2^\prime)$. Authors claim that strategy or policy for picking and arm cannot distinguish between the two problems.

Question: Shouldn't the second problem be $\mathcal{B}(\mu_2, \mu_2^\prime)$. I can understand if the authors say that this problem is similar to the original problem $\mathcal{B}_1$. How is $\mathcal{B}_2$ similar to $\mathcal{B}_1$?


Your Answer

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

Browse other questions tagged or ask your own question.