Mean-based algorithms: A lower bound and regret

Julius Durmann, Amelie Kleber

Mean-based algorithms are online learning algorithms that assign low probability to actions with low average rewards. Recent research shows that they converge to serially undominat…