Actually it's not UCB-1. UCB-1 solves the stochastic bandit problem, where you assume the arms have fixed but unknown expected reward. He's talking about the ad

Actually it's not UCB-1. UCB-1 solves the stochastic bandit problem, where you assume the arms have fixed but unknown expected reward. He's talking about the adversarial setting, where you make no assumptions about the distribution of the rewards of the arms. They can even be set by an adversary that is trying to make you perform badly. Remarkably you can derive results here, though the "catch" is you are measuring performance against choosing a fixed arm for every play. (It's actually a bit more complex than that, but that's a reasonable simplification for direct comparison to the stochastic bandit.) The standard algorithm in the adversarial setting is Exp3: http://cseweb.ucsd.edu/~yfreund/papers/bandits.pdf http://cseweb.ucsd.edu/~yfreund/papers/bandits.pdf Otherwise I agree for the most part with what you've said. Edit: In response to the parent edit, I should note that I know of no Bayesian algorithm for the adversarial setting. Thompson sampling is assuming a stochastic problem. I think a Bayesian algorithm would be possible, but the details elude me.