Decomposing Temporal Logic Specifications for Reinforcement Learning

This direction is split into other directions: automata-based task representation. Its last version stays readable and citable here.

Version 1 of 1143 papers163 conceptsfrozen 2026-10-04

Reinforcement Learning (RL) excels at discovering optimal behaviors through trial and error, but it notoriously struggles with "long-horizon" tasks. If an agent must perform a specific sequence of ten actions to receive a single reward, the probability of stumbling upon that sequence by chance is vanishingly small. This is the "sparse reward" problem.

To solve this, a growing body of research integrates formal logic—specifically Linear Temporal Logic (LTL) and Signal Temporal Logic (STL)—with RL. The core intuition is to treat a complex mission not as a single goal, but as a structured sequence of milestones. By decomposing a high-level specification into a formal graph, researchers can guide agents through complex tasks with mathematical precision.

The Logic as a Roadmap

Standard RL rewards are often "black boxes"—a scalar value that tells the agent that it did something good, but not why or what comes next. In contrast, Alessandro Abate, Hosein Hasanbeig, and Daniel Kroening propose Logically-Constrained Reinforcement Learning (LCRL), which uses LTL to automatically design reward functions.

LTL allows us to write rules like "Eventually reach $A$, and once $A$ is reached, always avoid $B$ until $C$ is satisfied." These rules are mathematically translated into a Finite State Automaton (FSA)—a flowchart where nodes represent stages of task progress and edges represent the conditions (subgoals) required to move between them.

As Yash Shukla and Alvaro Velasquez describe in Automaton-Guided Curriculum Generation for Reinforcement Learning Agents, this automaton acts as a high-level mission map. Instead of wandering aimlessly, the agent's state is augmented with its current position in the automaton. This "product state space" ensures the agent always knows which logical milestone it is currently pursuing.

Decomposing Complexity into Reach-Avoid Tasks

The power of this approach lies in decomposition. A daunting mission is broken down into a series of "reach-avoid" sub-problems. For each transition in the automaton, the agent simply needs to learn how to reach the next logical state while avoiding "failure" states.

Kishor Jothimurugan and Rajeev Alur formalize this in the DIRL framework (Compositional Reinforcement Learning from Logical Specifications). They interleave a Dijkstra-style search over the automaton with neural network policy training. This allows the system to scale linearly with task complexity: to solve a longer task, you don't need a exponentially larger brain; you just need to traverse more edges in the graph.

Similarly, Zijian Guo and Wenchao Li argue in One Subgoal at a Time that by conditioning the policy only on the immediate next subgoal, the agent becomes immune to the length of the overall task. This modularity is what enables zero-shot generalization: if an agent has learned the "skills" to reach $A$ and reach $B$, it can immediately satisfy a new LTL instruction like "reach $B$ then $A$" without any additional training.

Skill Composition and Reward Machines

If the automaton is the map, "skills" are the engine. Xiao Li and Calin Belta demonstrate in Automata-Guided Hierarchical Reinforcement Learning for Skill Composition how these logical structures can "stitch" learned skills together.

This concept is further refined by Devon Jarvis through Skill Machines, which map LTL states to specific logical sub-tasks. By learning a library of atomic propositions (e.g., "is near door," "is holding key"), the agent can use the automaton to compose these atoms into complex behaviors. Mathias Jackermeier extends this in DeepLTL by using Graph Neural Networks to encode the transitions of the automaton, allowing the agent to reason about simultaneous events and infinite-horizon objectives (like "patrol these three rooms forever").

Why It Works: The Information Bottleneck

A key reason these systems generalize better than standard deep RL is the separation of concerns. Borja G. León and Murray Shanahan describe this as an "information bottleneck" in In a Nutshell, the Human Asked for This.

By forcing the agent to receive its goals through a symbolic module (the automaton), the agent's representation of the environment is decoupled from the specific logic of the current task. The symbolic layer handles the "high-level" temporal dependencies (what to do next), while the RL policy handles the "low-level" motor control (how to move).

Beyond Success: Safety and Failure

Because these frameworks are rooted in formal methods, they offer more than just performance; they offer guarantees. Pushpak Jagtap and Majid Zamani use Control Barrier Certificates to provide formal probability bounds on task satisfaction.

Even when a task is impossible, logic-guided RL can "fail gracefully." Makai Mann and Kevin Leahy show in Learning Minimally-Violating Continuous Control that by decomposing missions into sub-tasks, an agent can identify which parts of a specification are infeasible and satisfy as much of the mission as possible while minimizing violations.

In summary, the research direction moves away from treating RL as a "black box" optimizer and toward a neuro-symbolic hierarchy. By using formal logic to decompose complex missions into a structured graph of subgoals, we gain agents that are easier to train, safer to deploy, and capable of following complex instructions they have never seen before.

Papers in this version

Showing 60 of 143 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_decomposing_temporal_logic_specification_54126c98,
  title = {Decomposing Temporal Logic Specifications for Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decomposing-temporal-logic-specifications-for-reinforcement-learning/rdr_54126c984cfc4202891317a979272b59},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_decomposing_temporal_logic_specification_54126c98_v1,
  title = {Decomposing Temporal Logic Specifications for Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decomposing-temporal-logic-specifications-for-reinforcement-learning/rdr_54126c984cfc4202891317a979272b59/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}