Let \(\Delta _K\)  denote the \(K\) -dimensional simplex and \(\operatorname{kl}(\delta , 1-\delta )\)  be the KL-divergence between two Bernoulli distributions with parameters \(\delta \)  and \(1-\delta \) . Finally, define the set of alternative bandit problems \(\operatorname{Alt}({\mu })= \lbrace \lambda \in {R}^K: G_{\varepsilon }({\mu }) \ne G_{\varepsilon }(\lambda )\rbrace \) .
Using the change-of-measure trick developed by [1]} and later popularized by [2]}for Best Arm Identification problems, we derive the following lower bound on the sample complexity in our special setting:
