Mean-based algorithms: A lower bound and regret

Julius Durmann, Amelie Kleber

Mean-based algorithms are a class of online learning algorithms that assign low probability to actions with low average rewards. Recent work indicates these algorithms converge fav…