Erratum: The ADAPT algorithm presented in this paper DOES NOT have a
PAC guarantee as claimed. The authors regret the erroneous claim, and
thank Gergely Neu for bringing it to their attention. The LUCB
algorithm (Kalyanakrishnan, Tewari, Auer, and Stone, 2012) was
conceived to be a provably-correct and provably-efficient replacement
for ADAPT.