  We study the problem of online learning with a notion of regret defined with
respect to a set of strategies. We develop tools for analyzing the minimax
rates and for deriving regret-minimization algorithms in this scenario. While
the standard methods for minimizing the usual notion of regret fail, through
our analysis we demonstrate existence of regret-minimization methods that
compete with such sets of strategies as: autoregressive algorithms, strategies
based on statistical models, regularized least squares, and follow the
regularized leader strategies. In several cases we also derive efficient
learning algorithms.
