Summary
Sometimes a system changes over time in ways you cannot directly see, which makes it hard for a learning agent to make good choices. In this paper, the authors study situations where a hidden time pattern causes an irreversible switch in how things behave, but the agent only sees some basic information. They create a method called TCIRL that learns both a strategy for acting and figures out the hidden time pattern at the same time. Their approach uses a tool called a deterministic finite automaton to keep track of the phases and refines it as new information comes in. Tests show that their method can identify the hidden changes almost perfectly and perform as well as if the agent had full information about the system.
reinforcement learningnon-Markovian processphase transitiondeterministic finite automatontemporal patternpolicy learningautomata learningSAT-based synthesishidden cause inferencegridworld
Authors
Jan Corazza, Daniil Kaminskyi, Simon Lutz, Patrick Nossol, Hadi Partovi Aria, Zhe Xu, Daniel Neider
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 recognizing the true cause language on all attainable label sequences, 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.