Thompson sampling is asymptotically optimal in general environments. (Leike, J., Lattimore, T., Orseau, L. & Hutter, M. (2016). Proceedings of the Thirty-Second Uncertainty in Artificial Intelligence Conference)

http://auai.org/uai2016/proceedings/papers/20.pdf