# How to derive this change of measure identity in multi-armed bandits?

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?

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