The algorithm of fig:exp-algo works in the adversarial setting. We first show that it also applies to the probabilistic setting (and this is why we require the above measurability discussion). The proof is quite similar to Lemma 4.3 of [1]} and can be found at proof:adversarial-to-probabilistic.
