I am a beginner at MAB. One thing that puzzles me these days:
The regret of the UCB policy (and Thompson Sampling with no prior) for stochastic bandit is $\sqrt{KT\ln T}$, but the regret of the EXP3 policy for adversarial bandit is $\sqrt{KT\ln K}$, where $T$ is the length of time horizon and $K$ is the number of arms.

It puzzles me because the adversarial setting appears to be more challenging, but why is the regret actually a bit smaller? I wonder if the reason is that the regrets in the two settings are defined slightly differently. (?)

If we apply the EXP3 policy in the stochastic setting, the regret should be $\sqrt{KT\ln K}$ as well? Because it is the case for every sample path.


1 Answer 1


Under stochastic settings, the regret bound of EPX3 is indeed $O(\sqrt{KT\ln K})$. The reason UCB has a higher upper bound than EXP3 is due to the design of the UCB algorithm. MOSS (a variant of UCB) achieves a regret upper bound of $O(\sqrt{KT})$, and the regret upper bound of TS with Gaussian prior is $O(\sqrt{KT\ln K})$.

However, in practice, due to the greedy nature of UCB and TS, experimental performance often surpasses that of EXP3.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.