Temporal-Causal Inference for Reinforcement Learning via Automata Learning

Abstract

We consider reinforcement learning in environments with dynamics that undergo an irreversible phase transition governed by a hidden temporal pattern. The agent observes the base state but cannot observe the phase directly. We formalize this problem as a two-phase non-Markovian decision process and introduce Temporal-Causal Inference for Reinforcement Learning (TCIRL), a framework that jointly learns a control policy and infers the hidden temporal cause of the phase transition. TCIRL maintains a hypothesis deterministic finite automaton (DFA) to track what phase is active and refines it via counterexample-driven SAT-based synthesis. We prove that the hypothesis converges almost surely to a DFA whose language induces the same dynamics as the cause language, yielding an optimal policy for the original non-Markovian decision process. Experiments on a genetic therapy gridworld and a traffic signal environment show that TCIRL recovers the correct cause DFA and matches the full-information baseline in both domains.

arXiv comment37 pages, 11 figures. Extended version of the paper accepted for publication in the Proceedings of the 65th IEEE Conference on Decision and Control (CDC), Honolulu, Hawaii, USA, December 2026. Code: https://github.com/verified-ai/tcirl