Competing with automata-based expert sequences

Mehryar Mohri, Scott Yang

Research output: Contribution to conferencePaperpeer-review


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 ∞-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.

Original languageEnglish (US)
Number of pages9
StatePublished - 2018
Event21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018 - Playa Blanca, Lanzarote, Canary Islands, Spain
Duration: Apr 9 2018Apr 11 2018


Conference21st International Conference on Artificial Intelligence and Statistics, AISTATS 2018
CityPlaya Blanca, Lanzarote, Canary Islands

ASJC Scopus subject areas

  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Competing with automata-based expert sequences'. Together they form a unique fingerprint.

Cite this