Thompson Sampling for Adversarial Bit Prediction

Yuval Lewi, Haim Kaplan, Yishay Mansour

We study the Thompson sampling algorithm in an adversarial setting, specifically, for adversarial bit prediction. We characterize the bit sequences with the smallest and largest ex…