A. Badanidiyuru, J. Langford, and A. Slivkins. (2014)cite arxiv:1402.6779Comment: This is the full version of a paper in COLT 2014. Version history: (V2) Added some details to one of the proofs, (v3) a big revision following comments from COLT reviewers (but no new results).