Machine Learning Department
School of Computer Science, Carnegie Mellon University
On Fixed Convex Combinations of No-Regret Learners
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.
Research was completed while visiting Carnegie Mellon University.
Author a student at the University of Karlsruhe, Germany, at publication.