We have two Bernoulli distributions with success probabilities $\mu\_1$ and $\mu\_2$. We sample $n$ times from distribution 1 and the sequence we get is $X\_1, \ldots, X\_n$. Let 


$
\hat{kl}\_s = \sum\_{t=1}^s \ln\frac{\mu\_1 X\_t + (1-\mu\_1)(1-X\_t)}{\mu\_2 X\_t + (1-\mu\_2)(1 - X\_t)},
$


represent the empirical estimate of KL-divergence between the two probability distributions. Then the following property holds: For any event $A$ in the $\sigma$-algebra generated by $X\_1, \ldots, X\_n$ the following change of measure identity holds:


\begin{equation}
P\_2(A) = E\_1\left[ I\_A \exp(-\hat{kl}\_n) \right],
\end{equation}


where the subscript $2$ in $P\_2$ implies that the probability is based on the distribution 2. Similarly for the expectation. $I$ represents the indicator function. How to prove the above identity?



How to derive this change of measure identity in multi-armed bandits?
Shishir, this is quite elementary: write the probability $P\_2(\omega)$ of any individual bit sequence $\omega$ as $P\_1(\omega) f(\omega)$ where by definition, $f(\omega)=\exp(-\hat{kl}\_n)$. Finally, sum over $\omega \in A$.


