Automata Learning

Definition

Automata learning infers a finite automaton from evidence such as positive and negative traces, membership/equivalence queries, or observed interaction data.

Why It Matters

Learned automata can expose temporal task structure in a compact, inspectable form. In RL, that structure can turn history-dependent rewards into product-state planning problems and guide exploration.

Formalism / Key Objects

• A deterministic finite automaton is typically written

$$A=(Q,\Sigma ,\delta ,q_0,F),$$

with states Q, alphabet Sigma, transition function delta, initial state q_0, and accepting states F.

• Passive algorithms such as RPNI infer a DFA consistent with positive and negative trace sets.
• Active algorithms such as L* use membership and equivalence queries.
• In DARP, confidence-weighted refinement attaches a score

$$c(q)=\frac{|P_q|+\lambda |N_q|}{|P_q|+|N_q|+\beta }$$

to automaton states and revises low-confidence or inconsistent regions online.

• Dynamic Automaton Refinement records the DARP-specific update rule, exploration bonus, and product-MDP maintenance scheme.
• In LHRM, the learner induces the root transition function of a hierarchical Reward Machines model from goal, dead-end, and incomplete label traces using ILASP, while previously learned lower-height RMs may be available as callable components.

Connections

• Directly supports Non-Markovian Reinforcement Learning when task automata are not supplied by a human designer.
• Reward Machines are an important RL-facing target representation for learned automata.
• Toro Icarte2022 - Reward Machines highlights that learning RMs from traces often assumes a correct labeling function, making event-detector learning a separate hard problem.
• Complements Linear Temporal Logic: LTL can be compiled into automata, while automata learning tries to infer automata from traces.
• Automata-Theoretic Logic supplies the semantic background for treating an inferred automaton as a language recognizer or monitor.
• Related to Invariant Synthesis as another route from examples/counterexamples toward symbolic structure.
• In Alinejad2026 - Dynamic Automaton Refinement and Planning for Non-Markovian RL, learned automata are used to maintain a product MDP for planning.
• In Furelos-Blanco2023 - Hierarchies of Reward Machines, learned HRMs reuse lower-level machines and policies rather than learning every task as a flat automaton.
• Dynamic Automaton Refinement is the focused annex for the confidence-weighted online refinement construction.
• Hierarchical Reward Machine Semantics records the HRM-specific call-stack semantics and flat-equivalence result.

Common Confusions

• Learning an automaton from traces does not guarantee the inferred automaton is the true task structure unless the evidence is sufficient and assumptions hold.
• Passive inference avoids query overhead but can miss valid behavior absent from the data.
• Active inference can identify structure with stronger interaction assumptions, but those queries may be unrealistic in deployed RL settings.

Key Sources

• Toro Icarte2022 - Reward Machines
• Alinejad2026 - Dynamic Automaton Refinement and Planning for Non-Markovian RL
• Furelos-Blanco2023 - Hierarchies of Reward Machines
• Dynamic Automaton Refinement