Automata Learning from Preference and Equivalence Queries
This addresses a foundational problem in automata learning with potential applications in reinforcement learning, though it is an incremental variant of an existing paradigm.
The paper tackles the problem of learning finite automata by replacing membership queries with preference queries, and introduces the REMAP algorithm which guarantees correct inference of the minimal automaton with polynomial query complexity under exact equivalence queries and achieves PAC-identification with sampling-based queries.
Active automata learning from membership and equivalence queries is a foundational problem with numerous applications. We propose a novel variant of the active automata learning problem: actively learn finite automata using preference queries -- i.e., queries about the relative position of two sequences in a total order -- instead of membership queries. Our solution is REMAP, a novel algorithm which leverages a symbolic observation table along with unification and constraint solving to navigate a space of symbolic hypotheses (each representing a set of automata), and uses satisfiability-solving to construct a concrete automaton from a symbolic hypothesis. REMAP is guaranteed to correctly infer the minimal automaton with polynomial query complexity under exact equivalence queries, and achieves PAC-identification ($\varepsilon$-approximate, with high probability) of the minimal automaton using sampling-based equivalence queries. Our empirical evaluations of REMAP on the task of learning reward machines for two reinforcement learning domains indicate REMAP scales to large automata and is effective at learning correct automata from consistent teachers, under both exact and sampling-based equivalence queries.