Competing With Strategies


Wei Han, Alexander Rakhlin, Karthik Sridharan ;
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:966-992, 2013.


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.

Related Material