Machine Learning Department
School of Computer Science, Carnegie Mellon University


On Fixed Convex Combinations of No-Regret Learners

Jan-P. Calliess

September 2008


Keywords: Machine learning, no-regret algorithm, external regret, affine regret, online convex problem, online decision program, computational learning theory, online learning

No-regret algorithms are powerful tools for learning in online convex problems that have received increased attention in recent years. Considering affine and external regret, we investigate what happens when a set of no-regret learners (voters) merge their respective strategies in each learning iteration to a single, common one in form of a convex combination. We show that an agent who executes this merged decision in each iteration of the online learning process and each time feeds back a reward function to the voters that is a correspondingly weighted version of its own reward, incurs sublinear regret itself. As a by-product, we obtain a simple method that allows us to construct new no-regret algorithms out of known ones.

14 pages

Research was completed while visiting Carnegie Mellon University.
Author a student at the University of Karlsruhe, Germany, at publication.

SCS Technical Report Collection
School of Computer Science homepage

This page maintained by