Appendix

Our goal in this section is twofold. To avoid excessive repetition of notation and proof arguments, we purposefully leavethis sectionnot self-contained and only outline these adjustments needed. We refer an interested reader to the work of Auer et al.[18] for the full and detailedproof. Instead of aiming to find a black-box reduction to the classical problem, we therefore investigate in detail the proof of theΩ KTlower bound for the classical MAB due to Auer et al.[18, 14 Theorem 5.1] and observe that their argument goes through for our MA-MAB problem as well. Instead of repeating their proof, we survey the key steps of their proof in which they assume the algorithm tobedeterministically pulling anarmandhighlight whytheargument holdsevenwhen thisisnotthecase.