Finite-Time Logarithmic Bayes Regret Upper Bounds

Alexia Atsidakou, Branislav Kveton, Sumeet Katariya +2

We derive the first finite-time logarithmic Bayes regret upper bounds for Bayesian bandits. In a multi-armed bandit, we obtain $O(c_{\Delta }\log n)$ and $O(c_h{\log }^{2}n)$ upper bounds for…