Zero-Shot Instruction Following in RL via Structured LTL Representations

arXiv:2602.14344 · cs.LG, cs.AI · Submitted 2026-08-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Zero-Shot Instruction Following in RL via Structured LTL Representations".

Jane: The paper was written by Mathias Jackermeier, Mattia Giuri, Jacques Cloete and Alessandro Abate from University of Oxford and Oxford Robotics Institute, University of Oxford.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title and Authors: Tom: Welcome back, everyone. Today we’re looking at a paper that’s been making the rounds in the reinforcement learning community, and it’s called "Zero-Shot Instruction Following in RL via Structured LTL Representations."

Jane: And Tom, I have to say, the title alone tells you this isn’t your average RL paper. It’s about teaching agents to follow instructions they’ve never seen before, using something called linear temporal logic, or LTL.

Tom: Right, and the authors are Mathias Jackermeier, Mattia Giuri, Jacques Cloete, and Alessandro Abate, out of Oxford. These folks have been pushing on this idea of using formal logic as a way to give robots and agents really precise, unambiguous tasks.

Jane: And that’s the key, isn’t it? Instead of saying "go to the red zone" in natural language, which can be fuzzy, you write it in LTL, which is like a mathematical language that says exactly what has to happen, in what order, and for how long.

Tom: Exactly. And the "zero-shot" part is the magic. The agent is trained on a bunch of tasks, and then at test time, you hand it a brand new LTL formula it has never seen, and it has to figure out how to satisfy it without any additional training.

Jane: That’s like teaching someone to cook by showing them a few recipes, and then asking them to cook a dish they’ve never heard of, just by reading the recipe. The agent has to understand the structure of the instructions, not just memorize them.

Tom: And that’s where the "structured" part of the title comes in. The authors aren’t just throwing the whole formula at the agent. They’re breaking it down into these sequences of Boolean formulae, which are like smaller sub-goals, and they’re giving the agent a way to reason about those sub-goals in order.

Jane: So it’s not just about following orders, it’s about understanding the logic behind the orders. That’s a huge step for making AI agents that can actually be useful in the real world, where tasks are rarely simple and often require planning ahead.

Tom: And we’re going to get into exactly how they do that in a minute. But first, I want to say, this paper feels like it’s addressing one of the biggest bottlenecks in RL, which is getting agents to generalize beyond their training data.

Jane: Absolutely. And the fact that they’re using formal logic, which is precise and verifiable, makes this approach really appealing for safety-critical applications. You know exactly what the agent is supposed to do, and you can check if it did it.

Tom: So, stick around. We’re going to break down the method, the results, and what this means for the future of AI. This is going to be a good one.

Paper Summary: Jane: So Tom, we’ve set the stage. Now let’s talk about what this paper actually does, and I think the core idea is really elegant. They’re using the structure of LTL formulas to build a map for the agent.

Tom: A map, I like that. So, they take an LTL instruction, like "eventually reach the green zone and avoid the red zone," and they convert it into something called a Büchi automaton. Think of it as a flowchart of all the possible ways to complete the task.

Jane: And the flowchart has states, and you move between states based on what’s true in the environment. But here’s the clever part. Instead of just telling the agent "you are in state three," they extract from that flowchart a sequence of Boolean formulae that describe what needs to happen to make progress.

Tom: Right, so it’s not just "do this," it’s "here’s the logical condition that will move you to the next step, and here’s what you need to avoid." And they do this for every step along the way, so the agent has a clear, structured view of the whole task.

Jane: And this is where the "structured" part really shines. The agent isn’t just seeing a list of raw facts. It’s seeing logical relationships. For example, it might see a formula like "a AND NOT b," which tells it that it needs to make 'a' true while making sure 'b' stays false.

Tom: And that’s a big deal because in complex environments, multiple things can be true at the same time. You might be in the green zone while holding a crate, and the agent needs to understand how those facts interact. The old methods, they just listed all the possible combinations, which gets out of hand really fast.

Jane: Exactly. The paper shows that their method, which they call StructLTL, handles this combinatorial explosion much better. They tested it in a warehouse environment where you have to move crates and vases between regions, and the tasks get really complicated, like "pick up a crate, but don’t put it down until you reach region B."

Tom: And the results are pretty impressive. They’re getting success rates above ninety-five percent on many of these complex tasks, while the previous state-of-the-art methods are struggling, sometimes dropping to fifty percent or sixty percent.

Jane: And it’s not just about success. It’s about efficiency. Their agent completes tasks in fewer steps because it can look ahead. It’s not just blindly going for the first sub-goal; it’s considering how that affects the future steps.

Tom: That’s the "non-myopic" part. The agent is planning, not just reacting. And that’s a huge leap forward for this kind of multi-task learning.

Jane: So, they’ve built a better map, and they’ve given the agent a way to read that map intelligently. That’s the summary in a nutshell.

Tom: And next, we need to talk about the specific improvements they made to make this work. Because it’s one thing to have the idea, and another to make it actually learn.

Improvements Suggested: Tom: Alright Jane, so we know they’ve got this great idea. But what are the actual technical improvements that make StructLTL work so well? Because the paper is full of clever engineering.

Jane: Right, and the first big one is how they encode those Boolean formulae. They don’t just treat them as a string of characters. They use a hierarchical encoder that respects the logic. So, a formula like "a AND b OR c" is broken down into its clauses, and each clause is encoded separately, then combined.

Tom: It’s like understanding a sentence by first understanding the words, then the phrases, and then the whole sentence. They’re preserving the logical structure, which lets the agent generalize. If it learns how to achieve "a" and how to achieve "b," it has a much better chance of understanding "a AND b."

Jane: And that’s a huge improvement over the previous method, DeepLTL, which just treated tasks as a flat list of assignments. That method struggles when you have many propositions that can be true at once, because the number of combinations explodes.

Tom: But the second improvement is what I think is really cool. They added a temporal attention mechanism. So, the agent isn’t just looking at the current sub-goal. It’s looking at the whole sequence and attending to future sub-goals to inform its current decision.

Jane: And that’s the difference between a myopic agent and a planner. The paper gives a great example. Imagine you need to achieve "a" and then "b." If you just focus on "a," you might do something that makes "b" impossible. But if you can see "b" coming up, you’ll make a different choice for "a."

Tom: Exactly. And they implemented this with a scaled dot-product attention mechanism, which is the same kind of thing used in transformers. But they added a clever twist called ALiBi, which biases the attention to focus more on nearby steps. So it’s not just "attend to everything equally," it’s "attend to the future, but remember that the immediate next step is usually the most important."

Jane: And they also handle those tricky epsilon transitions in the automaton. Those are like non-deterministic choices, where the agent can decide which path to take. They added special actions for those, so the agent can actively choose which route through the flowchart to follow.

Tom: And then, at test time, they use the learned value function to pick the best path. So, if there are multiple ways to satisfy the LTL formula, the agent picks the one it thinks it can complete most successfully.

Jane: It’s a full package. The hierarchical encoder gives it a better understanding of the logic, the attention mechanism gives it foresight, and the value function helps it make smart choices.

Tom: And the ablation studies in the paper show that each of these pieces matters. If you take away the hierarchical encoder, performance drops. If you take away the attention, it drops. They really did their homework.

Jane: So, it’s not just one big idea. It’s a combination of well-engineered improvements that all work together. And that’s why it’s so effective.

Tom: And that’s why we need to talk about what this means for the future. This isn’t just a lab curiosity. This could change how we build AI systems.

Conclusion: Jane: Well Tom, we’ve covered a lot of ground on "Zero-Shot Instruction Following in RL via Structured LTL Representations." And I think the big takeaway is that by giving the agent a structured, logical map of the task, you unlock a level of generalization that was previously out of reach.

Tom: Absolutely. The results speak for themselves. Over ninety-five percent success on complex warehouse tasks where the old methods were struggling. And the agent is more efficient too, completing tasks in fewer steps because it can plan ahead.

Jane: And the implications go beyond just these test environments. This approach of using formal logic to structure tasks could be huge for real-world robotics. Imagine a warehouse robot that can be given a new task in LTL, like "move all the blue crates to the loading dock, but don’t cross the yellow line," and it just does it, without any retraining.

Tom: Or even in safety-critical systems, where you need to be absolutely sure the AI understands the rules. LTL gives you that guarantee. You can verify that the agent’s behavior matches the specification.

Jane: And the authors mention that future work could look at combining this with visual input, where the agent learns the mapping from raw images to those logical propositions. That would make it even more applicable to the real world.

Tom: Right, and there’s also the idea of using hindsight experience replay to make training even more sample-efficient. So, there’s a lot of room to build on this foundation.

Jane: It’s a really solid piece of work. The authors have clearly thought deeply about the problem, and they’ve delivered a method that is both theoretically sound and practically effective.

Tom: So, with that, we’re going to say goodbye to this paper. It’s been a fascinating discussion, and I think this is one of those papers that will be cited for years to come.

Jane: Thanks for joining us, everyone. We’ll be back soon with the next paper. Until then, keep exploring.

Tom: Take care, everyone.

Mathias Jackermeier, Mattia Giuri, Jacques Cloete, Alessandro Abate

University of Oxford · Oxford Robotics Institute, University of Oxford

cs.LG, cs.AI

Submitted: 2026-08-16

Updated: 2026-08-18

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 76/100

The gist: The paper introduces StructLTL, a novel approach for training generalist policies to follow linear temporal logic (LTL) instructions in multi-task reinforcement learning, enabling zero-shot execution

Key concepts

Linear Temporal Logic (LTL)
A mathematical language used to express precise requirements for AI agents. Instead of vague natural language, LTL defines exactly what must happen, in what order and for how long, ensuring unambiguous task fulfillment.
Zero-Shot Instruction Following
The ability an AI agent has to perform a brand new task or instruction it has never encountered before. It does this by understanding the underlying structure of the logic, not just by memorizing specific training examples.
Structured LTL (StructLTL)
A method that breaks down complex LTL formulas into sequences of smaller Boolean sub-goals. This allows the agent to logically reason about how these sub-goals interact, avoiding the combinatorial complexity of traditional methods.

Terminology

Summary

The paper introduces StructLTL, a novel approach for training generalist policies to follow linear temporal logic (LTL) instructions in multi-task reinforcement learning, enabling zero-shot execution of novel tasks not seen during training.

The authors study instruction following in multi-task RL where an agent must zero-shot execute novel tasks. They adopt LTL as a formal language for specifying structured, temporally extended tasks, noting that while existing approaches successfully train generalist policies, they often struggle to effectively capture the rich logical and temporal structure inherent in LTL specifications. The paper argues that formal specifications offer advantages over natural language: "they facilitate the training process by enabling the automatic construction of task-specific reward functions, they explicitly expose task structure via their compositional syntax, and they are grounded in well-defined semantics."

The paper makes four main contributions:

  1. Representing LTL instructions as sequences of Boolean formulae constructed from transitions in the corresponding Büchi automaton. The authors state: we propose representing LTL instructions as sequences of Boolean formulae constructed from transitions in the corresponding Büchi automaton.

  2. A structured representation learning approach based on a hierarchical neural architecture coupled with a temporal attention mechanism to embed these sequences of formulae.

  3. A novel environment with complex logical structure (the Warehouse environment) that allows us to systematically study the effectiveness of our approach across challenging LTL specifications.

  4. An extensive empirical evaluation demonstrating that our method achieves state-of-the-art results and significantly outperforms existing approaches across a wide range of tasks.

Given an LDBA Bφ and state q, the method identifies behaviour leading to satisfying the LTL instruction by enumerating accepting runs via depth-first search. For each accepting run ρi, the method constructs a sequence of Boolean formula pairs (βi+, βi−) where:

  • βi+ is only true for the assignments that transition from qi to qi+1

  • βi− captures the assignments that must be avoided in order to avoid transitioning to other states

The authors use the Quine-McCluskey algorithm to compute minimal DNF representations, noting that Boolean formulae can be much more succinct than explicitly enumerating sets of assignments.

The policy architecture processes formula sequences hierarchically:

  • Embedding Boolean formulae: Formulae in DNF are processed hierarchically—propositions have trainable embeddings, negated propositions pass through a learned linear projection, literals in a clause are aggregated via a permutation-invariant DeepSets encoder, and clause embeddings are aggregated again at the disjunction level.

  • Temporal attention mechanism: In order to produce optimal behaviour, the policy may need to consider future subgoals rather than myopically focusing only on the first step. The method uses single-head scaled dot-product attention with the first step as query, augmented with ALiBi (linear bias) to preserve sequential information.

  • Handling ε-transitions: These are represented with a special token βε and handled by augmenting the action space with designated ε-actions.

Training uses goal-conditioned RL with PPO, assigning "+1 reward for successfully satisfying formulae βi+ and −1 for satisfying βi−. A curriculum learning approach is employed with increasingly challenging sequences of Boolean formulae."

At test time, the trained value function selects the formula sequence: ζ∗ = arg maxζi Vπ(s, ζi), corresponding to the path through the automaton with the highest likelihood of success.

The method is evaluated in ZoneEnv (a high-dimensional robotic navigation environment) and the newly introduced Warehouse environment (featuring hybrid action spaces and complex logical specifications).

Key findings include:

  • StructLTL consistently achieves high success rates in finite-horizon tasks, with more than 95% in most cases, including complex tasks requiring compositional reasoning.

  • Significant outperformance of baselines on complex tasks φ12–φ16 where baseline methods struggle.

  • Better sample efficiency compared to baselines.

  • Superior performance on infinite-horizon tasks, completing more accepting cycles in the LDBA for all but one formula.

The paper notes: whereas our approach represents complex combinations of atomic propositions via succinct Boolean formulae, DeepLTL struggles to handle the combinatorial explosion of assignments.

Ablation studies demonstrate that both the hierarchical DNF encoder and the temporal attention mechanism significantly impact performance. The hierarchical encoding is superior to flat token-based encodings, and the attention mechanism performs better than the alternatives (myopic baseline and GRU encoding). Additional analysis shows StructLTL is robust to increasing numbers of possible assignments, while DeepLTL's performance degrades.

The authors identify promising directions including hindsight experience replay to improve the sample efficiency, applying the approach to real-world robotic domains where the labelling function may be unknown, and jointly learning the labelling function from visual or sensory input, or leveraging pre-trained foundation models as high-level event detectors.

Improvements for AI systems

Based on the paper, here are the specific improvements I can make to an AI system and what the improved system can do:

Improvement: Replace myopic, unstructured task encodings (e.g., single atomic propositions or flat assignment sets) with sequences of Boolean formulae derived from Büchi automaton transitions. Use Quine-McCluskey minimization to produce succinct DNF formulae.

What the improved system can do:

  • Zero-shot execute novel LTL tasks not seen during training, including tasks requiring compositional reasoning (e.g., a ∧ ¬b, c ∨ d).

  • Handle environments where multiple propositions hold simultaneously (e.g., carrying a crate in region A), avoiding combinatorial explosion of assignment sets.

  • Generalize from simple tasks (e.g., reach red) to complex ones (e.g., pick up crate, don't drop until in region B) without retraining.

Improvement: Replace flat token-sequence encoders (e.g., GRU/LSTM) with a two-level DeepSets architecture: first aggregate literals within a clause, then aggregate clauses within the disjunction. Use learned embeddings per proposition and a projection layer for negations.

Improvement: Add a single-head scaled dot-product attention mechanism where the first step's embedding is the query, attending to all future subgoals. Apply ALiBi (linear penalty increasing with distance) to bias attention toward nearby steps.

Improvement: At test time, use the trained value function to select the most promising accepting run (sequence of Boolean formulae) from the current LDBA state, rather than random or heuristic selection.

Improvement: Train on a curriculum of increasingly complex Boolean formula sequences (single-step → multi-step → reach-stay with avoid conditions), with stage progression based on rolling success rates.

The improved AI system can:

  • Zero-shot execute arbitrary LTL instructions (finite- and infinite-horizon) in high-dimensional, continuous-action environments.

  • Compositionally generalize from simple to complex tasks by exploiting logical structure (conjunctions, disjunctions, negations) rather than memorizing assignments.

  • Plan ahead using attention over future subgoals, reducing myopic behavior and improving efficiency.

  • Handle complex environments where multiple propositions co-occur, without manual observation reduction or environment-specific assumptions.

  • Outperform state-of-the-art baselines (LTL2Action, DeepLTL) by 10–40% in success rate and 15–30% in efficiency across diverse tasks, while maintaining robustness to task complexity.

Sources

Related papers