Dynamic Automaton Refinement and Planning for Non-Markovian RL

Summary

This partial ingest is based on the extracted PDF text for the full five-page ICASSP paper. The paper proposes Dynamic Automaton Refinement and Planning (DARP), an RL framework for Non-Markovian Reinforcement Learning where the temporal reward/task automaton is incomplete, implicit, or evolving. DARP passively infers deterministic finite automata from trajectory labels, refines them online with confidence-weighted RPNI, adds exploration bonuses for low-confidence automaton regions, and updates the product MDP while preserving learned Q-values where possible.

Key Claims

• Many sequential RL tasks have rewards determined by histories or event sequences rather than the current state alone.
• Existing automata-guided RL methods often assume a known reward automaton or rely on expensive active queries; DARP instead refines a learned DFA during interaction.
• Confidence scores over automaton states identify unreliable regions where new traces should trigger refinement and where exploration should be directed.
• Incremental product-MDP updates and Q-value transfer reduce the cost of automaton revisions compared with rebuilding the planning problem from scratch.
• In the reported grid/resource domains, DARP discovers more valid task patterns and often reaches high success rates in fewer episodes than static RPNI, active grammatical inference, and HiPO baselines.

Methods / Formalism

• The paper models the environment as an NMRDP

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

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

• A reward function can be represented by a DFA

$$A=(Q,\Sigma ,\delta ,q_0,F),\Sigma =2^{AP},$$

where a trajectory receives reward iff the induced DFA run ends in an accepting state.

• DARP extends RPNI by assigning confidence to automaton state q:

$$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 premature confidence.

• After each episode, if the automaton prediction disagrees with the observed label or a trace visits a low-confidence state, the trace is added to the positive/negative set and RPNI synthesizes a revised DFA.
• Exploration receives a UCB-style bonus modulated by max(1-c(q_delta),0), directing search toward under-supported automaton states.
• Planning is performed on the product MDP M x A; when the automaton changes, DARP updates only affected product states and transfers Q-values for preserved regions.
• The focused formal payload is pulled out into Dynamic Automaton Refinement.

Evidence / Experiments

• Domains: Dungeon Quest, where the agent must discover valid item acquisition orderings, and Blind Craftsman, where the agent must learn resource-constrained production patterns.
• Baselines: static RPNI, active grammatical inference with L* queries, and HiPO.
• DARP reports higher pattern discovery from zero positive examples: 56.7% in Dungeon Quest and 73.3% in Blind Craftsman, compared with 0% for static RPNI/HiPO and lower rates for active grammatical inference.
• DARP reaches 90% success in fewer episodes in the reported Dungeon Quest setting and maintains better or comparable final success in the resource-constrained setting.
• Ablations indicate that confidence weighting, exploration bonuses, and Q-value transfer each contribute; removing them slows convergence or reduces pattern discovery.
• The Blind Craftsman results have high variance, so the paper’s empirical evidence supports promise rather than a settled robustness claim.

Connections

• Primary source for Non-Markovian Reinforcement Learning and Automata Learning in the current wiki.
• Complements Elsayed-Aly2024 - Distributional Probabilistic Model Checking because both use automata/products to make temporally structured decision problems tractable, but DARP learns the automaton from interaction rather than assuming a known specification.
• Connects to Linear Temporal Logic because automata encode temporal task structure over event traces.
• Connects to Safe Reinforcement Learning when invalid temporal sequences are safety or constraint violations rather than merely unrewarding behaviors.
• Connects to Continual Learning because the agent updates its task model online while trying to preserve useful learned policy information.
• The core refinement equations and product-MDP update pattern are summarized in Dynamic Automaton Refinement.

Open Questions

• The paper reports empirical improvements but leaves convergence and regret theory for future work.
• How robust is confidence-weighted refinement when observations are noisy, labels are delayed, or the true reward automaton is nonstationary rather than merely initially incomplete?
• Can the approach scale beyond finite symbolic labels and tabular/product-MDP planning into continuous state spaces?
• When should low-confidence automaton states trigger exploration versus conservative avoidance in safety-critical settings?

Citation

Alinejad, M., Wang, Y., and Atia, G. (2026). Dynamic Automaton Refinement and Planning for Non-Markovian RL. In ICASSP 2026 - IEEE International Conference on Acoustics, Speech and Signal Processing. DOI: 10.1109/ICASSP55912.2026.11461556.