Temporal-Causal Inference for Reinforcement Learning via Automata Learning

I. INTRODUCTION

• Hidden temporal causes can make identical observed states call for different decisions, so a memoryless policy over the observed state need not be optimal.The cause is a sequence of genetic modifications that is not directly observable from symptoms alone.Source: §I · p. 1
• In the therapy example, TCIRL learns the gene-site sequence that triggers Phase 2 and symptoms decline, while standard Q-learning remains in Phase 1.The example's cause sequence is G1, G2, G1, G4; the medicine also has a harm-related timing constraint.Source: §I · p. 2
• TCIRL maintains a hypothesis DFA for the temporal cause and refines it with counterexample-driven SAT synthesis when an episode contradicts the hypothesis.The synthesis step returns a minimal DFA consistent with prior observations.Source: §I · p. 2
• Under the stated marker assumption, the hypothesis converges almost surely to the correct cause DFA, and the agent converges to an optimal policy.The markers are phase-exclusive, may be stochastic, and every wrong hypothesis must be exposed by a reachable episode.Source: §I · p. 2
• In both domains, TCIRL recovers the cause DFA and matches the full-information baseline, although triggering the cause helps in therapy and harms in traffic.The two domains are the genetic therapy gridworld and traffic signal environment.Source: §I · p. 2

II. BACKGROUND

• LTLf expresses temporal patterns over finite label traces, and its formulas can be compiled into DFAs that monitor whether a pattern has occurred.The logic includes sequencing, eventuality, and persistence constraints.Source: §II · p. 2
• A labeled NMDP has history-dependent transitions, Markovian rewards, and labels on transitions; attainable label sequences arise from positive-probability trajectories.The paper focuses on cases where a single regular temporal condition summarizes the relevant past.Source: §II · p. 2
• In the two-phase model, satisfying the cause formula switches dynamics permanently from P1 to P2, while the agent observes the state but not the active phase.The reward remains Markovian; the cause formula is the source of dependence on the past.Source: §II · p. 3
• Extension closure captures an irreversible cause: once the formula is satisfied, every continuation remains satisfying.This property allows a successor-closed DFA to recognize the cause language.Source: §II · p. 3
• A DFA for the cause language is the finite-memory structure that tracks label history and the active phase.Multiple successor-closed DFAs may recognize the same cause language; the paper denotes the minimum state count by nφc.Source: §II · p. 3

III. METHOD

• TCIRL jointly learns a policy and infers the hidden cause DFA from episode data.Once the cause monitor is correct, the problem reduces to a standard product-MDP construction.Source: §III · p. 3
• The central challenge is identifying the monitor from partial stochastic evidence gathered during reinforcement learning.The method uses stochastic markers as indirect evidence about whether the cause has occurred.Source: §III · p. 3
• The method proceeds through a hypothesis-induced product MDP, marker-based counterexample detection, SAT-based hypothesis synthesis, and an overall training procedure with convergence guarantees.Source: §III · p. 3

A. Problem Setting

• The hypothesis DFA tracks the inferred phase, and its product MDP combines the base state with the automaton state while retaining the original Markovian reward.If the hypothesis agrees with the cause on attainable sequences, the product MDP matches the NMDP dynamics on reachable states.Source: A. Problem Setting · p. 3

B. Marker Assumption

• Each completed episode supplies a label sequence that TCIRL uses both to run the hypothesis and check marker evidence against its phase predictions.Source: B. Marker Assumption · p. 3
• Phase-exclusive markers xr and xa certify that the cause has not yet fired or has fired, respectively, but identifying them requires domain knowledge about phase-dependent dynamics.In genetic therapy, symptom increase is xr and spontaneous recovery is xa.Source: B. Marker Assumption · p. 3
• Marker soundness prevents evidence from contradicting the true phase, while completeness guarantees an attainable extension that exposes each phase.Source: B. Marker Assumption · p. 3
• Markers may be probabilistic; the assumption requires a reachable witness to expose every incorrect hypothesis, not a marker in every episode.Source: B. Marker Assumption · p. 3

C. Counterexample Detection

• An episode is a counterexample when the DFA accepts a prefix followed by rejection-marker evidence, or rejects a prefix followed by acceptance-marker evidence.TCIRL checks this consistency as it runs the DFA over the episode and retains detected counterexamples.Source: C. Counterexample Detection · p. 4

D. SAT-Based Cause DFA Synthesis

• After a counterexample, TCIRL re-synthesizes a minimal DFA consistent with the accumulated marker evidence by testing SAT constraints for increasing state counts.The search terminates at a finite state count no greater than nφc.Source: D. SAT-Based Cause DFA Synthesis · p. 4
• The synthesis formula encodes deterministic total transitions, runs over observed counterexample prefixes, successor-closed acceptance, one absorbing accepting state, and consistency with certified positive and negative prefixes.Source: D. SAT-Based Cause DFA Synthesis · p. 4
• The SAT constraints are satisfiable exactly when an n-state DFA fits the accumulated evidence, and a satisfying assignment reconstructs its transition table and accepting states.The constraints exploit extension-closure, which allows minimal successor-closed DFAs to use a single absorbing accepting state.Source: D. SAT-Based Cause DFA Synthesis · p. 4

E. Training Procedure

• The agent performs ε-greedy Q-learning using the base state and current hypothesis state as the product-MDP input.Source: E. Training Procedure · p. 4
• Completed-episode label sequences enter the counterexample set only when they contradict the current DFA according to marker evidence.Source: E. Training Procedure · p. 4
• After each counterexample, TCIRL recomputes the smallest consistent DFA and resets the Q-table to optimistic initialization if the hypothesis changes.The reset avoids carrying over values learned under incompatible automaton semantics.Source: E. Training Procedure · p. 4

F. Theoretical Guarantees

• With ε > 0 and episode length at least m, every m-attainable label sequence is observed infinitely often almost surely.The proof uses the finite maximum m* of shortest counterexample lengths across wrong DFAs with at most nφc states.Source: F. Theoretical Guarantees · p. 5
• Under Assumptions 1 and 2, ε-greedy exploration, and episode length at least m*, the hypothesis stabilizes almost surely and classifies every attainable label sequence correctly.Theorem 1's equivalence is restricted to attainable sequences.Source: F. Theoretical Guarantees · p. 5
• Only finitely many hypothesis revisions can occur because each counterexample changes a bounded-size minimal DFA, and any remaining error would eventually produce an observed witness.Source: F. Theoretical Guarantees · p. 5
• TCIRL's greedy policy achieves the NMDP's optimal value when standard Q-learning assumptions hold after the final hypothesis update.Theorem 2 also states almost-sure convergence to the optimal Q-function of the final-hypothesis product MDP.Source: F. Theoretical Guarantees · p. 5
• Once the final hypothesis matches the cause on reachable trajectories, its product MDP has the NMDP's reachable dynamics, linking Q-learning convergence to NMDP optimality.Source: F. Theoretical Guarantees · p. 5

• The genetic therapy and traffic signal scenarios test hidden causes with beneficial and harmful phase transitions, respectively.Source: §IV · p. 5
• Five methods are compared: TCIRL, Q-learning with known or unknown cause, and DQN with four- or three-frame histories.Q-learning with known cause provides a full-information upper bound for tabular methods; the three-frame DQN history is insufficient for the cause formulas.Source: §IV · p. 5
• Performance is summarized by interquartile mean with bootstrap 95% confidence intervals across 50 training seeds, with policies evaluated on 50 greedy episodes.Evaluation uses a fixed set of evaluation seeds.Source: §IV · p. 5

A. Case Study 1

• The genetic therapy cause requires a particular gene-site sequence, with G3 a distractor and medicine affecting dynamics but not the cause.The soundness marker is a symptom increase possible only in Phase 1; the acceptance marker is a stochastic recovery possible only in Phase 2.Source: A. Case Study 1 · p. 5
• In genetic therapy, TCIRL’s training reward closely matches known-cause Q-learning and four-frame DQN, while three-frame DQN and unknown-cause Q-learning fail to learn an effective policy.Figure 3 reports average reward per training step.Source: A. Case Study 1 · p. 6, Figure 3 · p. 6
• Only TCIRL, four-frame DQN, and known-cause Q-learning consistently modify genes to trigger the cured state; smaller-history DQN and unknown-cause Q-learning do not learn that strategy.Figure 4 tracks symptom levels during evaluation; unknown-cause Q-learning instead prioritizes immediate medication rewards.Source: A. Case Study 1 · p. 6, Figure 4 · p. 6

B. Case Study 2

• In traffic control, the cause is three consecutive hold-advance cycles, and entering Phase 2 increases congestion, so the optimal policy must avoid that transition.The soundness and acceptance markers are, respectively, multiple departures from the last queue and multiple arrivals at the first queue.Source: B. Case Study 2 · p. 6
• In traffic control, TCIRL’s reward convergence approaches known-cause Q-learning, and both maintain lower evaluation queue levels than the other approaches.The training reward and evaluation queue comparisons are shown in Figures 5 and 6.Source: B. Case Study 2 · pp. 6–7, Figure 5 · p. 6, Figure 6 · p. 6

C. Cause Activation Analysis

• TCIRL triggers the cause in every genetic-therapy evaluation episode, matching known-cause Q-learning; in traffic control, higher reward is associated with fewer trajectories reaching Phase 2.Figure 7 reports the fraction of evaluation trajectories that trigger the cause formula.Source: C. Cause Activation Analysis · p. 7
• Cumulative re-inferences plateau early in both domains, with the hypothesis typically identified within the first 10% of training steps.Figure 8 shows cumulative re-inferences during training.Source: C. Cause Activation Analysis · p. 7, Figure 8 · p. 7

V. RELATED WORK

• Unlike prior methods that learn a predictive generative model or assume the temporal specification is known, TCIRL infers only the before/after-cause monitor and leaves value estimation to model-free Q-learning.The narrower target supports exact SAT-based inference and guarantees absent from the cited RDP learning work.Source: §V · p. 7
• Unlike reward-machine methods, TCIRL monitors transition dynamics using stochastic phase-exclusive markers, and it omits counterfactual updates because automaton-state changes can alter the transition kernel and bias Bellman targets.Source: §V · p. 7
• TCIRL’s prefix-level supervision can certify rejecting prefixes and later accepting prefixes within a trace, but may leave an uncertified band between them.This is richer than passive accepted/rejected-word learning but less complete than observing an output at every prefix.Source: §V · p. 8
• TCIRL uses finite-trace LTL and DFA monitoring for hidden transition dynamics, with convergence guarantees under the marker assumption; its use of “causal” is narrower than interventionist causal modeling.Source: §V · p. 8

• Under marker soundness and completeness, TCIRL’s hypothesis converges almost surely to the correct cause language and its policy to an optimal one.The framework uses sparse stochastic effect signals and two atomic marker propositions to provide certified counterexample information for SAT-based synthesis.Source: §VI · p. 8
• In a genetic therapy gridworld with a five-state cause and beneficial trigger and a traffic pipeline with a seven-state cause and harmful trigger, TCIRL recovers the true automaton and matches the full-information baseline.Source: §VI · p. 8
• The marker assumption requires domain expertise to identify phase-exclusive observable events, and the structural constraints cover one-shot causation rather than cyclic patterns.Future directions include automatic marker discovery and cause automata for general regular temporal patterns.Source: §VI · p. 8