🤖 machine learning

Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version)

Original authors: Pierriccardo Olivieri, Fausto Lasca, Alessandro Gianola, Matteo Papini

Published 2026-02-09

📖 5 min read🧠 Deep dive

Original authors: Pierriccardo Olivieri, Fausto Lasca, Alessandro Gianola, Matteo Papini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to drive a car or move a box in a warehouse. In the world of Artificial Intelligence, this is called Reinforcement Learning. The robot learns by trying things and getting "rewards" (like a digital high-five) when it does something right, and "no rewards" when it does something wrong.

The big problem is telling the robot what "right" actually means.

The Old Way: The "Labeling" Bottleneck

Traditionally, to teach a robot a complex task, humans have to write very specific, rigid rules.

The Analogy: Imagine you are teaching a child to bake a cake. In the old method, you can't just say, "Make a cake." You have to hand the child a checklist of 50 specific ingredients and say, "If the flour is exactly 200 grams, check box A. If the sugar is 100 grams, check box B."
The Problem: If you want the robot to pick up a red box instead of a blue one, or move to a different spot, you often have to rewrite the entire checklist or build a new "translator" (called a labeling function) to explain the new rules. It's tedious, error-prone, and hard to reuse.

The New Way: "Do It for HER" (The Paper's Solution)

This paper proposes a new framework called LTLfMT. Let's break down what that means using a simple metaphor.

1. The Universal Translator (SMT Solvers)
Instead of forcing the human to build a custom translator for every single rule, this framework uses a "Universal Translator" (a mathematical tool called an SMT solver).

The Analogy: Instead of writing a new dictionary for every language you speak, you just speak naturally to a super-smart interpreter. You can say, "Pick up the box that weighs less than 10kg and has the ID 'H123'." The interpreter instantly understands the math and the logic without you needing to write code to check the weight or the ID.
The Benefit: You can describe complex tasks using natural logic (like "First do A, then do B, but never go near the red zone") without manually coding the details of how to measure distance or check IDs.

2. The "Time Travel" Logic
The framework uses a special kind of logic that understands time.

The Analogy: It's like giving the robot a script for a play. The script doesn't just say "Stand here." It says, "First, walk to the door. Then, wait for the bell. After that, open the door." The robot understands the sequence of events, not just a single snapshot.

The "Sparsity" Problem: The Silent Room

There is a catch. Because these logical rules are so precise, the robot often goes a long time without getting a "high-five."

The Analogy: Imagine playing a video game where you only get a point when you reach the very last level. If you die 100 times trying to get there, you get zero feedback. You don't know why you failed, so you don't know how to improve. This is called Reward Sparsity.

The Solution: "Hindsight" and "What-Ifs"

To fix the silence, the authors combine two clever tricks:

A. Hindsight Experience Replay (HER)

The Analogy: Imagine the robot fails to reach the "Red Box." Instead of just saying "Fail," the robot looks back and says, "Well, I did successfully reach the 'Blue Box' I was aiming for by accident. Let's pretend that was the goal I wanted all along."
How it helps: The robot learns from its mistakes by reinterpreting them as successes for different goals. It turns a failure into a learning opportunity.

B. Counterfactual Experiences (CRM)

The Analogy: This is like a "What-If" simulator. The robot thinks, "I was at the door, but what if I had turned left instead of right? I would have gotten a reward." It creates fake, imaginary scenarios to practice on.

The "Do It for HER" Combo:
The paper's main innovation is combining these two. They take the "What-If" scenarios (CRM) and apply the "Hindsight" trick (HER) to them.

The Result: The robot gets a massive amount of practice data. It learns not just from what it actually did, but from what it could have done, and it learns to treat those "could-have-beens" as valid goals.

What They Tested

They tested this on a virtual car parking task.

The Challenge: The car had to navigate to specific spots, avoid obstacles, and follow a sequence of steps.
The Outcome:
- The old methods (and the robot trying on its own) mostly failed or learned very slowly.
- The new method (combining the logical rules with the "Hindsight" and "What-If" tricks) learned much faster and could solve complex parking tasks that the others couldn't figure out at all.

Summary

This paper gives robots a better way to understand instructions. Instead of humans writing complex code to translate rules, the robot uses a universal math tool to understand logical sentences like "Go to X, then Y." To make sure the robot learns quickly despite getting few rewards, the authors teach it to learn from its failures by pretending those failures were actually successes for different goals. It's like giving the robot a time machine to practice different versions of reality so it can master the real one.

Technical Summary: Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning

Problem Statement

Reinforcement Learning (RL) relies on reward signals to guide agent behavior, yet reward engineering remains a heuristic and labor-intensive process. A significant challenge arises when tasks are inherently non-Markovian, requiring history-dependent rewards that standard Markovian reward functions cannot capture effectively. While Linear Temporal Logic with finite traces (LTLf) has been successfully employed to specify such tasks, it is limited to Boolean predicates. This restriction necessitates manual "labeling functions" to map continuous or heterogeneous state spaces (e.g., real-valued coordinates, object IDs, weights) to discrete propositional symbols. In complex real-world scenarios like robotics or business process management, this manual encoding is brittle, non-reusable, and fails to leverage the rich structure of continuous data. Furthermore, logic-based specifications often result in sparse rewards, making learning difficult without additional mechanisms like reward shaping or hindsight experience replay.

Methodology

The authors propose a framework utilizing Linear Temporal Logic Modulo Theories over finite traces (LTLfMT) to overcome the expressiveness limitations of LTLf.

1. Theoretical Framework: LTLfMT

Instead of Boolean atoms, LTLfMT employs first-order formulas interpreted over arbitrary theories (e.g., Non-Linear Real Arithmetic, relational databases).

Syntax: The framework defines a grammar where atomic propositions are replaced by first-order terms and predicates ( $\alpha$ ) involving variables, constants, and functions. These are combined via first-order logic ( $\lambda$ ) and then wrapped in temporal operators ( $\phi$ ) similar to standard LTLf.
Tractable Fragment: Recognizing that full LTLfMT is undecidable, the authors identify a specific fragment suitable for RL. They remove the "lookahead" operators ( $\bigcirc, \sim\bigcirc$ ) from the term layer, arguing that temporal constraints on data collection are unnecessary for reward specification. This leaves the decidability dependent solely on the underlying theory.
Translation to Automata: To enable standard RL, the authors propose a propositionalization strategy. A formula $\phi$ in the LTLfMT fragment is translated into a standard LTLf formula $\phi'$ by substituting first-order sub-formulas with distinct propositional letters. A Satisfiability Modulo Theories (SMT) solver acts as a universal labeling function, evaluating these sub-formulas at each time step to determine the truth values of the propositional letters.
Product MDP: The propositionalized formula is converted into a Deterministic Finite Automaton (DFA). This DFA is combined with the original environment to form a Product MDP, where the state space is the Cartesian product of the environment state and the automaton state. This transforms the non-Markovian reward problem into a Markovian one solvable by standard RL algorithms.

2. Addressing Reward Sparsity: CRM-HER

To tackle the sparsity inherent in logic-based goals, the paper combines two techniques within the Product MDP framework:

Counterfactual Experiences for Reward Machines (CRM): This technique generates artificial transitions by replacing the current DFA state with other reachable states in the automaton, effectively creating "what-if" scenarios to densify the reward signal.
Hindsight Experience Replay (HER): HER improves sample efficiency by relabeling failed trajectories with goals that were actually achieved during those episodes.
Integration: The authors adapt HER to the Product MDP by defining the "goal" as a specific state in the product space (a state triggering a transition to an accepting state). They propose a combined approach (CRM-HER) where HER is applied to both real trajectories and the counterfactual trajectories generated by CRM. This leverages the structured nature of first-order goals to automatically generate goal specifications without manual intervention.

Key Contributions

LTLfMT for Reward Specification: The paper introduces a framework that extends LTLf to LTLfMT, allowing reward specifications to be written directly over continuous and heterogeneous data domains using first-order theories, eliminating the need for manual labeling functions.
Identification of a Tractable Fragment: The authors define a specific fragment of LTLfMT that is free from decidability issues (assuming the underlying theory is decidable) and allows for efficient translation to automata via SMT solvers.
Unified CRM-HER Approach: The paper presents a novel method for combining Counterfactual Experiences and Hindsight Experience Replay within the context of logic-specified rewards, specifically tailored to the Product MDP structure derived from LTLfMT.
Empirical Validation: The framework is evaluated in continuous control environments (Parking and Reacher) using Non-Linear Real Arithmetic (NRA). The experiments demonstrate that the proposed approach, particularly the CRM-HER combination, outperforms baselines (standard DDPG, CRM-only, and HER-only) in tasks with complex, sparse goals.

Results

Experiments were conducted using Deep Deterministic Policy Gradients (DDPG) on a modified Parking environment and a Reacher environment.

Baseline Performance: Standard DDPG applied to the Product MDP struggled significantly, often failing to learn a successful policy in complex tasks (e.g., parking_1, parking_2) due to reward sparsity.
CRM vs. HER: CRM alone improved performance in tasks where the automaton structure was the primary bottleneck but offered limited benefits when the goal itself was difficult to discover. HER alone performed well in goal-discovery scenarios but did not fully leverage the automaton structure.
CRM-HER Superiority: The combined CRM-HER approach consistently achieved the best or near-best performance across all tasks. Notably, in the most complex tasks (parking_2), CRM-HER was the only method capable of learning a successful policy. The results suggest that the synergy between counterfactual reasoning (exploiting automaton structure) and hindsight experience (exploiting goal generalization) is fundamental to solving complex, sparse-reward tasks in continuous domains.

Significance and Claims

The paper claims that LTLfMT offers a more expressive and reusable alternative to LTLf for reward specification, particularly in domains with continuous or heterogeneous data. By shifting the complexity of encoding from manual labeling functions to off-the-shelf SMT solvers, the framework reduces human intervention and increases the speed of defining new tasks.

The authors emphasize that their approach naturally facilitates the application of HER in logic-based RL. Because the reward specification is based on first-order formulas, the variables used in the formula can directly serve as the basis for goal definitions in HER, avoiding the need for ad-hoc goal engineering. The paper concludes that this integration of symbolic logic, SMT solving, and modern RL techniques (CRM and HER) provides a robust pathway for specifying and learning complex, non-Markovian behaviors in continuous control settings, paving the way for future work in safety constraints and multi-task learning.