Dynamic Automaton Refinement

Context

Alinejad2026 - Dynamic Automaton Refinement and Planning for Non-Markovian RL uses learned automata to represent history-dependent rewards. The key technical pattern is to refine a DFA online when new trajectories contradict or under-support the current automaton, while keeping the induced product MDP usable for planning.

Formal Statement

An NMRDP is represented as

$$M=(S,s_0,A,P,AP,L,R),$$

where R:(2^{AP})^* -> {0,1} maps proposition-label traces to binary outcomes.

The reward structure is encoded by a DFA

$$A_t=(Q_t,\Sigma ,{\delta }_t,q_0,F_t),\Sigma =2^{AP}.$$

For automaton state q, DARP defines confidence

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

where P_q and N_q count positive and negative traces through q, lambda weights negative evidence, and beta delays confidence saturation.

After an episode with trace w_t and observed outcome y_t=R(w_t), refinement is triggered when either the current automaton prediction disagrees with the observation or the trace visits a state with confidence below a threshold:

$$A_t(w_t)\ne y_t\text{or}\exists q\in {\mathrm{run}}_{A_t}(w_t):c(q)<{\theta }_{\min }.$$

When refinement is triggered, the next automaton is synthesized by RPNI over the updated positive and negative trace sets:

$$A_{t+1}=\mathrm{RPNI}(P_t\cup \{w_t:y_t=1\},N_t\cup \{w_t:y_t=0\}).$$

Derivation / Construction

• Use the learned DFA to form the product MDP M x A_t with state space S x Q_t.
• During action selection, add an exploration bonus that prefers rarely visited and low-confidence automaton regions:

$$\mathrm{bonus}(s,a)=\alpha \sqrt{\frac{\log t}{N(q_{\delta })}}\max \{1-c(q_{\delta }),0\},$$

where q_delta is the automaton state reached by the candidate transition.

• When A_t changes to A_{t+1}, identify affected automaton states by transition differences:

$$\Delta Q=\{q\in Q_t:\exists \sigma \in \Sigma ,{\delta }_t(q,\sigma )\ne {\delta }_{t+1}(q,\sigma )\}.$$

• Preserve Q-values for unaffected product states, average predecessor values for new-but-related regions, and initialize genuinely new regions conservatively.

Implications

• Confidence is doing two jobs: deciding when the automaton model is unreliable enough to revise, and deciding where exploration should search for missing temporal patterns.
• Product-MDP maintenance keeps the learned temporal abstraction coupled to planning, but it inherits state-space growth from both environment states and automaton states.
• The method is attractive for implicit task rules, but safety-critical use would need a clear policy for whether low-confidence regions should be explored, avoided, or shielded.

Links

• Source: Alinejad2026 - Dynamic Automaton Refinement and Planning for Non-Markovian RL
• Concepts: Automata Learning, Non-Markovian Reinforcement Learning, Safe Reinforcement Learning