Competing With Strategies
This work addresses a theoretical challenge in online learning for researchers, though it appears incremental as it builds on standard regret frameworks with new strategy sets.
The paper tackles the problem of online learning with regret defined relative to sets of strategies, demonstrating the existence of regret-minimization methods that compete with various strategies like autoregressive algorithms and regularized least squares, and in some cases deriving efficient algorithms.
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.