Online Learning with Automata-based Expert Sequences
This work addresses online learning challenges for scenarios requiring structured expert sequences, but it appears incremental as it builds on existing frameworks like weighted-majority and k-shifting experts.
The authors tackled the problem of online learning with expert advice by defining regret relative to sequences accepted by a weighted automaton, covering problems like competing against k-shifting experts, and developed algorithms including automata-based extensions and efficient approximations using n-gram models, with results including extensive approximation studies and extensions to sleeping experts.
We consider a general framework of online learning with expert advice where regret is defined with respect to sequences of experts accepted by a weighted automaton. Our framework covers several problems previously studied, including competing against k-shifting experts. We give a series of algorithms for this problem, including an automata-based algorithm extending weighted-majority and more efficient algorithms based on the notion of failure transitions. We further present efficient algorithms based on an approximation of the competitor automaton, in particular n-gram models obtained by minimizing the \infty-Rényi divergence, and present an extensive study of the approximation properties of such models. Finally, we also extend our algorithms and results to the framework of sleeping experts.