Source-linked AI summary
LTL2Action: Generalizing LTL Instructions for Multi-Task RL
Pashootan Vaezipoor, Andrew Li, Rodrigo Toro Icarte, Sheila McIlraith
TL;DR
Deep RL instruction-following can demand large, environment-specific training sets pairing natural-language instructions with rewards. This paper uses LTL progression and neural instruction encodings, with environment-agnostic pretraining, and reports robust generalization across procedurally generated task sets, outperforming a prevalent myopic approach.
Problem
Natural-language instruction-following approaches require large, environment-specific training sets of instructions paired with reward functions.
Source: §1 · p. 1Method
The approach trains RL agents to follow LTL instructions using neural encodings and semantics-preserving progression, and pretrains the LTL module in an environment-agnostic scheme.
Source: §1 · pp. 1–2, §3.3 · p. 4Results
Experiments on discrete and continuous domains demonstrated robust generalization across procedurally generated task sets, outperforming a prevalent myopic approach.
Source: §8 · p. 9Takeaways & Limitations
The experiments show zero-shot generalization to new instructions significantly larger than those seen in training.
Source: §6 · p. 8For LTL formulas that cannot be verified or falsified in finite time, the described reward function provides no meaningful reward signal.
Source: §3.2 · p. 3
Abstract
from arXiv · showhide
We address the problem of teaching a deep reinforcement learning (RL) agent to follow instructions in multi-task environments. Instructions are expressed in a well-known formal language -- linear temporal logic (LTL) -- and can specify a diversity of complex, temporally extended behaviours, including conditionals and alternative realizations. Our proposed learning approach exploits the compositional syntax and the semantics of LTL, enabling our RL agent to learn task-conditioned policies that generalize to new instructions, not observed during training. To reduce the overhead of learning LTL semantics, we introduce an environment-agnostic LTL pretraining scheme which improves sample-efficiency in downstream environments. Experiments on discrete and continuous domains target combinatorial task sets of up to $\sim10^{39}$ unique tasks and demonstrate the strength of our approach in learning to solve (unseen) tasks, given LTL instructions.
1. Introduction
Natural-language instruction-following can require large, environment-specific sets of instructions and rewards. The paper uses LTL and progression to train RL policies for temporally extended tasks, with an environment-agnostic pretraining scheme to reduce the cost of learning LTL semantics.
1. Introduction
- Natural-language instruction following requires large, environment-specific training sets pairing instructions with reward functions.Prior deep RL policies can generalize to unseen instructions given enough training data, but the approaches do not scale well.Source: §1 · p. 1
- Structured languages offer unambiguous semantics and compositional syntax for generating training data, but myopic methods can combine individually optimal subtasks into a suboptimal whole.The paper calls these methods myopic approaches.Source: §1 · p. 1
- LTL progression lets the agent track which parts of an instruction remain, supporting non-myopic learning while preserving optimality guarantees and generalization to unseen instructions.LTL combines temporal modalities and logical connectives over domain-specific propositions to express sequences, partial orders, and safety constraints.Source: §1 · p. 1
- The deep RL approach encodes LTL instructions with an LSTM, GRU, or GNN and introduces environment-agnostic pretraining to reduce the overhead of learning LTL semantics.The approach is evaluated in discrete and continuous domains.Source: §1 · pp. 1–2
- The reported contributions include higher reward from progression-based instruction encodings than a myopic approach, better GNN generalization than LSTM or GRU, and improved downstream sample efficiency from pretraining.The paper also reports theoretical advantages over existing LTL-instruction RL methods (Kuo et al., 2020; Leon et al., 2020).Source: §1 · p. 2
2. Reinforcement Learning
The section introduces reinforcement learning as learning policies through interaction with an environment, typically modeled as an MDP. The objective is to maximize expected discounted return.
2. Reinforcement Learning
- An MDP is defined by states, terminal states, actions, transition probabilities, rewards, a discount factor, and an initial-state distribution.The agent learns a policy to maximize expected discounted return.Source: §2 · p. 2
- In each episode, the agent observes a state, selects an action, receives a reward and next state, and repeats until termination.The initial state is sampled from the initial-state distribution.Source: §2 · p. 2
- The policy objective is to maximize expected discounted return from any state and time step.Source: §2 · p. 2
3. Multitask Learning with LTL
The section presents LTL instructions over detectable event propositions and uses progression to make instruction-conditioned RL Markovian in an augmented Taskable MDP. Its optimal stationary policy preserves the expected discounted return of the corresponding history-dependent policy.
3. Multitask Learning with LTL
- The task-learning setup uses detectable event propositions as a shared vocabulary and samples an LTL instruction for each episode.Instructions compose temporally extended occurrences of events.Source: §3 · p. 2, §3.3 · p. 3
3.1. Linear Temporal Logic (LTL)
- LTL combines propositions with next and until operators, allowing instructions to specify sequences, alternative goals, conjunctions, and safety constraints.Examples include reaching red and then green, reaching red or green, and avoiding blue.Source: §3.1 · pp. 2–3
3.2. From LTL Instructions to Rewards
- A labelling function maps states and actions to proposition truth values; the reward is 1 for satisfaction, −1 for falsification, and 0 otherwise.The episode ends when the instruction is satisfied or falsified.Source: §3.2 · p. 3
- The reward provides a non-zero signal only when an instruction can be verified or falsified in finite time; sequence-dependent rewards may also make learning partially observable.For some formulas, such as □♦G, the described reward gives no meaningful signal.Source: §3.2 · p. 3
3.3. Instructing RL Agents using LTL
- Progressing an LTL instruction after each step tracks what remains and makes the reward Markovian by augmenting the environment state with the current task.Progression rewards the agent when the instruction becomes true or false.Source: §3.3 · pp. 3–4
- An optimal stationary policy in the Taskable MDP achieves the same expected discounted return as an optimal history-dependent policy in the original environment.The equivalence holds for each state and instruction in the specified task set.Source: §3.3 · p. 4
3.4. Discussion and Bibliographical Remarks
- In the toy MiniGrid, the myopic policy succeeds on 50% of tasks, while the proposed approach obtains maximum reward.The tasks require visiting blue then red or blue then green, and doors lock upon entry.Source: Figure 1 · p. 4, §3.4 · p. 4
- Myopic approaches optimize the next subtask without accounting for later requirements, while learning a full state-and-instruction policy is harder; experiments did not show the expected myopic generalization advantage.The discussion contrasts proposition-conditioned myopic policies with policies conditioned on the state and full LTL instruction.Source: §3.4 · pp. 4–5
4. Model Architecture
The architecture progresses LTL instructions as propositions are detected, then combines their encoding with environment observations to choose actions. A compositional graph encoder represents formulas, and environment-agnostic pretraining transfers learned formula encodings to downstream tasks.
4. Model Architecture
- The modular agent receives an observation and LTL instruction, progresses the instruction from event-detector signals, and uses the resulting task with the observation to choose actions.The architecture has environment, LTL, and RL modules; the RL module emits actions from their encoded inputs.Source: §4 · p. 5
4.1. LTL Module
- R-GCN encodes each formula as a parse-tree graph with four edge types and propagates messages bottom-up; the root embedding represents the formula.Self-loops preserve information from each node’s prior representation, while distinct edge types use distinct weights.Source: §4.1 · p. 5
4.2. Pretraining the LTL Module
- Because LTL semantics are environment-agnostic, the LTL module can be pretrained on a target formula set and distribution, then transferred to that downstream Taskable MDP.LTLBootcamp is a single-state MDP without a reward function; its task is to progress sampled formulas by setting one proposition true per step.Source: §4.2 · pp. 5–6
5. Experiments
The experiments test progression, architecture, pretraining, task-size generalization, and continuous control across discrete LetterWorld and continuous ZoneEnv. Progression-based methods and GNN encoders show stronger generalization than the non-progression GRU and myopic baselines, while pretraining accelerates learning.
5.1.1. ENVIRONMENTS
- Experiments cover a 7 × 7 LetterWorld grid and continuous ZoneEnv, where the robot reaches or avoids colored zones according to the task.LetterWorld has 12 propositions; ZoneEnv randomly positions the robot and zones at episode start.Source: §5.1.1 · pp. 6–7
5.1.2. TASKS
- Procedurally generated tasks include partially ordered proposition sequences and avoidance constraints; their task sets exceed 5 × 10^39 and 970 million unique tasks, respectively.Avoidance propositions change as different parts of a task are solved.Source: §5.1.2 · p. 7
5.1.3. OUR METHODS AND BASELINES
- Three PPO variants use LTL progression with GNN, GRU, or LSTM encoders, and baselines include No LTL, non-progression GRU, and Myopic methods.The study evaluates i.i.d. tasks from a large distribution and upward generalization to larger tasks guaranteed to be unseen; formulas reach 75 training tokens and 210 tokens in upward tests.Source: §5.1 · p. 6, §5.1.3 · p. 7, §5.1.2 · p. 7
5.2. Results
- On LetterWorld, LTL progression significantly improved generalization, GNN encoded formulas better than GRU and LSTM, and the initially fast Myopic baseline was eventually outperformed by all proposed methods.Figure 3 reports discounted return over training, averaged over 30 seeds with 90% confidence intervals.Source: Figure 3 · p. 7, §5.2 · pp. 7–8
- Pretraining the LTL module accelerated learning for both GNN and GRU encoders on LetterWorld.Figure 4 compares pretrained and non-pretrained encoders with the Myopic baseline using discounted return over training.Source: Figure 4 · p. 7, §5.2 · p. 8
- On ZoneEnv avoidance tasks, both GNN architectures solved almost all tasks, while Myopic and GRU without progression failed to solve many within the timeout.Pretraining resulted in faster convergence in this continuous-control environment.Source: Figure 5 · p. 8, §5.2 · p. 8
6. Discussion
The experiments find that full LTL instructions and LTL progression improve solutions and generalization, while architecture affects encoding quality and speed. The work assumes noise-free event labels and primarily studies new formulas over a fixed proposition set.
6. Discussion
- LTL progression improves learning and generalization, and the approach zero-shot generalizes to instructions significantly larger than those seen in training.The experiments also report that full task instructions converge to better solutions than myopic methods and that pretraining LTL semantics improves downstream learning.Source: §6 · p. 8
- GNNs appear to encode LTL's compositional syntax more effectively, while GRUs are roughly 2 to 3× more wall-clock efficient because GNNs require abstract syntax trees.The reported architecture comparison identifies a trade-off between generalization and wall-clock efficiency.Source: §6 · p. 8
- The approach assumes access to a noise-free labelling function, leaving open whether that function can be learned and how agents can handle resulting uncertainty.The function identifies high-level domain features.Source: §6 · pp. 8–9
- The study investigates new formulas over a fixed proposition set; preliminary experiments suggest alternative proposition features can support unseen objects and propositions, but further investigation is needed.The proposed extension replaces one-hot proposition encodings with other feature representations.Source: §6 · p. 9
7. Related Work
Prior formal-language approaches often focus on single tasks or sequential subtasks, while this work targets multitask generalization by learning over full LTL tasks. It uses LTL progression and pretraining to improve learning efficiency.
7. Related Work
- Most prior LTL or related formal-language methods target a single fixed task; Toro Icarte et al. (2018a) address multiple tasks but cannot generalize to unseen tasks and may require exponentially many policies.The policy count may be exponential in the length of the largest formula.Source: §7 · p. 9
- Unlike approaches that decompose large tasks into sequential subtasks, this work considers full LTL tasks in a multitask setting with a new task sampled each episode.The paper notes that sequential decomposition often performs suboptimally on the full task.Source: §7 · p. 9
- The approach uses LTL progression for standard Markovian learning and pretrains the LTL module; unlike Kuo et al. (2020), its formula encoding supports environment-independent pretraining.Kuo et al. (2020) compose neural networks to mirror formula structure, which the paper describes as environment-dependent.Source: §7 · p. 9
- Other task-specification representations include programs, policy sketches, and natural language, and natural-language instructions can be translated automatically into LTL.The passage lists examples of translation methods by Dzifcak et al. (2009), Brunello et al. (2019), and Wang et al. (2020).Source: §7 · p. 9
8. Conclusion
The paper presents neural LTL encodings and progression as an approach to multitask RL, using LTL's compositional syntax to generate training data automatically. Experiments in discrete and continuous domains show robust generalization across procedurally generated tasks and outperform a prevalent myopic approach.
8. Conclusion
- Experiments in discrete and continuous domains show robust generalization across procedurally generated task sets and outperform a prevalent myopic approach.The approach trains RL agents to follow temporally extended instructions expressed in LTL, whose compositional syntax supports automatic generation of massive training data.Source: §8 · p. 9
- LTL is used for synthesis and verification, robot tasking, and human-robot interaction, and the authors say their contributions could be adapted to other structured languages.The cited applications include robot tasking and human-robot interaction.Source: §8 · p. 9
A. Proof of Theorem 3.1
Theorem 3.1 states that optimal stationary policies in the Taskable MDP match the expected discounted return of optimal non-stationary policies in the original MDP for each task. The proof relies on equivalent reward sequences and matching trace distributions.
A. Proof of Theorem 3.1
- Optimal policies in the Taskable MDP achieve the same expected discounted return as optimal non-stationary policies in the original MDP for every state and task.The Taskable MDP is constructed from an MDP without a reward, a finite set of propositional symbols, an action-state labelling function, a finite set of LTL formulas, and a task distribution.Source: A. Proof of Theorem 3.1 · p. 13
- The proof uses LTL progression correctness to establish identical reward at every time step, then matches policies by preserving trace distributions.The argument maps policies between the two MDPs and uses the stationary-policy guarantee for the Taskable MDP.Source: A. Proof of Theorem 3.1 · p. 13
B. Experimental Details
- The experimental-details section introduces further information on task generation and hyperparameters.The available passage ends before specifying those details.Source: B. Experimental Details · p. 13
B.1. LTL Task Generation
The task spaces are generated recursively from a context-free grammar and define different temporal constraints: ordered sequences for Partially-Ordered Tasks and changing avoidance requirements for Avoidance Tasks.
B.1. LTL Task Generation
- Partially-Ordered Tasks require every proposition in each of k sequences to occur in order, while allowing the sequences to be solved simultaneously.These tasks cannot be falsified, but finding a shortest solution is often computationally intractable because of the exponential number of possible solutions.Source: §B.1 · p. 13
- LetterWorld Partially-Ordered tasks sampled 1–4 conjuncts and sequence depths of 1–5, with terms comprising one proposition 75% of the time or a disjunction 25% of the time.For larger-formula tests, depth was 15 with 2–4 conjuncts, or 12 conjuncts with depth 3–5.Source: §B.1 · p. 13
- Avoidance Tasks add propositions that must be avoided, with the propositions to avoid changing as different parts of the task are solved.The task spaces are described recursively using production rules of a context-free grammar; ¬ and U denote not and until.Source: §B.1 · pp. 13–14
- Avoidance tasks used 1–2 conjuncts and sequence depths of 1–3 in LetterWorld; larger-formula tests used depth 6 with one conjunct or depth 2 with three.ZoneEnv used one conjunct and depths of 1–2 because longer tasks suffered from sparse reward; repeated propositions were disallowed to ensure formulas were solvable.Source: §B.1 · p. 14
B.2. Network Architectures
The experiments use shared PPO actor–critic designs with environment-specific observation modules and compare LTL encoders of similar size. The GNN uses iterative message passing, while the GRU and LSTM encode formulas recurrently.
B.2. Network Architectures
- LetterWorld and ZoneEnv shared PPO actor and critic networks, while LTLBootcamp used single-layer actor and critic networks without hidden layers.The pretraining networks were kept separate from downstream actor and critic models to encourage a self-sufficient LTL encoding.Source: §B.2 · p. 14
- The environment module encoded observations with a three-layer CNN in LetterWorld and a two-layer fully connected network in ZoneEnv; LTLBootcamp had none.For continuous actions, the actor parameterized a Gaussian distribution through separate linear layers for its mean and standard deviation.Source: §B.2 · p. 14
- LTL formulas were encoded with roughly 10^4-parameter architectures: an R-GCN GNN, a bidirectional GRU, or a bidirectional LSTM.The GNN used eight message-passing steps and 32-dimensional node embeddings; the recurrent alternatives used two layers and 16-dimensional hidden states.Source: §B.2 · p. 14
- GNN embeddings aggregate information only from formula nodes within eight edges of the root, though this was not observed to hinder the experiments.Progression generally reduces formula size as task parts are solved, and immediately relevant information tends to lie closer to the root.Source: §B.2 · p. 14
B.3. PPO Hyperparameters
- GNN training took approximately 26 hours in LetterWorld and 24 hours in ZoneEnv for 20 million frames; GRU formula encoding was usually 2–3× more wall-clock efficient.Gradients for partially observable baselines were backpropagated through only the last four timesteps, with no observed improvement from increasing that number.Source: §B.3 · p. 15
C.1. Generalization to Unseen Objects
The paper tests whether its framework generalizes to unseen propositions and reports pretraining learning curves for GNN and GRU encoders. It reports generalization beyond the training letters and faster learning by the GNN in LTLBootcamp.
C.1. Generalization to Unseen Objects
- The unseen-object experiment used fixed random normalized 3D vectors for letters, encoding each proposition identically in the grid and its LTL formula.The evaluation retained the training formulas' structure while substituting unseen letters.Source: §C.1 · p. 15
- Compared with random action selection, the framework generalizes well to Avoidance tasks over unseen letters.Agents trained on formulas over 12 fixed letters were evaluated on formulas using six seen and six unseen letters, or 12 unseen letters; Table 5 reports mean return over five seeds and 1,000 episodes per seed.Source: §C.1 · p. 15, Table 5 · p. 15
C.2. Pretraining Learning Curves
- In LTLBootcamp pretraining, the GNN learned significantly faster than the GRU, although Partially-Ordered tasks remained extremely challenging to solve optimally.Figure 6 plots discounted return over training, averaged across 30 seeds with 90% confidence intervals; this environment is for pretraining, not evaluation benchmarking.Source: §C.2 · p. 15, Figure 6 · p. 16