A Proof of Proposition

In this appendix we prove Proposition 1 from Section 4. Proposition 1. We next derive two lemmas that will be used in the proofs of our theorems. Hence we select the most under-sampled action if we take!1 in Algorithm 1. Lemma 2. Let s be a state that we visit m times. The proof follows from Lemma 1. The proof is by induction.