Synthesizing Reward Functions from Temporal Logic

34 concepts28 papers1 proposal

Reinforcement learning (RL) relies heavily on the reward function to guide an agent toward a desired behavior. However, manual reward engineering is notoriously brittle. If a designer manually weights competing objectives—such as speed versus safety—the agent often finds unintended loopholes, a phenomenon known as reward hacking. Furthermore, complex tasks often require remembering history (e.g., "visit region A, then B, but only if C never happened"), violating the Markov property that standard RL algorithms depend on.

To solve this, a prominent research direction replaces handcrafted scalar rewards with formal task specifications written in temporal logic. Instead of guessing numerical weights, designers write mathematically precise rules. The core insight of this field is that these formal logical specifications can be automatically compiled into structured reward functions, providing mathematical guarantees that maximizing the reward perfectly aligns with satisfying the task.

From Binary Logic to Continuous Gradients: Robustness Degrees

If we simply give an agent a reward of $+1$ for satisfying a logical formula and $0$ otherwise, the reward signal is incredibly sparse. An agent might wander randomly for millions of steps without ever accidentally completing a complex sequence, receiving no feedback to learn from.

To build a smooth gradient for optimization, researchers translate temporal logic into a continuous metric called a robustness degree. Instead of a binary true/false, the robustness degree quantifies how well a trajectory satisfies a formula, or how close it came to violating it.

Xiao Li et al. demonstrated this in Reinforcement Learning With Temporal Logic Rewards by introducing Truncated Linear Temporal Logic (TLTL). By using the robustness degree as a reward signal, the logical structure inherently manages the trade-offs between competing objectives (like reaching a goal while avoiding obstacles) without requiring manual weight tuning. In subsequent work, Xiao Li et al. showed that this continuous margin provides a rich gradient that allows policy search methods to solve multi-step sequences reliably (A Policy Search Method For Temporal Logic Specified Reinforcement Learning Tasks).

This idea scales to even more complex properties. For instance, Tzu-Han Hsu et al. developed HypRL to handle multi-agent hyperproperties expressed in HyperLTL, using quantitative robustness scores to automatically balance inter-agent dependencies (HypRL: Reinforcement Learning of Control Policies for Hyperproperties). Similarly, the authors of Expressive Temporal Specifications for Reward Monitoring demonstrated that automatically synthesized dense rewards from quantitative temporal logic significantly accelerate training on long-horizon tasks compared to handcrafted alternatives.

Tracking History via Automata and Reward Machines

While robustness degrees provide smooth local gradients, they do not fully solve the problem of history-dependent (non-Markovian) tasks. If an agent's optimal action depends on what it did ten steps ago, a standard RL agent will struggle because its state representation only captures the immediate present.

The solution is to compile temporal logic specifications into finite-state automata or Reward Machines (RMs). An automaton acts as a high-level blueprint or flowchart that runs alongside the environment, tracking the logical state of the task.

[ Environment State ] ---> [ Logic Monitor / Automaton State ]
         |                                    |
         v                                    v
[ Low-Level Action ] <--- [ Dense Internal Reward / Policy ]

Daniel Kroening et al. formalized this in their Logically-Constrained Reinforcement Learning (LCRL) framework, where reward functions are automatically generated from the accepting conditions and state transitions of an LTL-derived automaton (Towards Verifiable and Safe Model-Free Reinforcement Learning). This ensures that the agent is explicitly incentivized to progress through the logical stages of a task.

To make these structures even more expressive, Mateo Perez et al. introduced $\omega$-regular reward machines, which utilize nondeterministic automata to let agents choose between multiple valid paths to satisfy an infinite-horizon logical property while optimizing secondary scalar rewards (Omega-Regular Reward Machines). In Mungojerrie: Linear-Time Objectives in Model-Free Reinforcement Learning, the authors provided an automated toolchain to compile LTL into $\omega$-automata, bridging the gap between formal verification and model-free RL.

Furthermore, Osbert Bastani et al. proved that by introducing uniform discounting to temporal operators, complex LTL specifications can be systematically reduced to finite-state reward machines, enabling theoretically sound, finite-memory optimal policies (Policy Synthesis and Reinforcement Learning for Discounted LTL). This automaton-driven reward shaping is also highly effective in multi-agent settings; Chenyang Zhu et al. showed that translating global temporal goals into decentralized individual reward machines transforms sparse multi-agent environments into dense, manageable learning problems (Decomposing Temporal Equilibrium Strategy for Coordinated Distributed Multi-Agent Reinforcement Learning).

Grounding and Learning the Symbolic Structure

How do we obtain these logical specifications or map them to the real world? One approach is to learn the reward machine's parameters or structure directly. Weichao Zhou et al. proposed Symbolic Reward Machines (SRMs), where the high-level logic is fixed as an automaton, but the exact numerical rewards assigned to transitions are treated as free variables learned from expert demonstrations via hierarchical Bayesian inverse RL (A Hierarchical Bayesian Approach to Inverse Reinforcement Learning with Symbolic Reward Machines).

Alternatively, runtime monitors can act as external "restraining bolts." Giuseppe De Giacomo et al. developed a framework where a separate monitoring component evaluates high-level symbolic features against predefined temporal rules, feeding auxiliary rewards to the agent without requiring the agent's low-level networks to explicitly understand the symbols (Restraining Bolts for Reinforcement Learning Agents). This concept of runtime verification integration is exemplified by RMLGym, a framework by Francesco Belardinelli et al. that connects OpenAI Gym to the Runtime Monitoring Language to automate reward design (RMLGym: a Formal Reward Machine Framework for Reinforcement Learning).

In data-driven control, Milad Kazemi explores how path-dependent reward functions derived from LTL allow model-free agents to satisfy safety properties even in dynamical systems with unknown models (Data-driven Approaches for Formal Synthesis of Dynamical Systems). To optimize training efficiency, Yash Shukla et al. showed that these high-level logical blueprints can be used for dynamic task sampling, guiding agents through sub-goals without human-assigned weights (Logical Specifications-guided Dynamic Task Sampling for Reinforcement Learning Agents).

Scaling to Language and Foundation Models

The ultimate promise of logic-based reward synthesis is bridging the gap between human intent (often expressed in natural language) and verifiable execution. For instance, in text-based games, Mathieu Tuli et al. introduced LTL-GATA, which uses LTL formulas to internally track the state of natural language instructions, providing auxiliary rewards that prevent agents from entering dead-end states (Learning to Follow Instructions in Text-Based Games).

To automate the creation of these logical structures, Shayan Meshkat Alsadat et al. used Large Language Models (LLMs) to extract domain knowledge from text, combined with a SAT solver to synthesize the most compact, observation-consistent reward machine (Using Large Language Models to Automate and Expedite Reinforcement Learning with Reward Machine). Similarly, Jinbang Huang et al. leveraged LLMs to generate symbolic PDDL domains that serve as automated, step-by-step reward functions to train planning agents (Plan2Evolve: LLM Self-Evolution for Improved Planning Capability via Automated Domain Generation).

Finally, looking toward the future of autonomous systems, Florent Delgrange proposes Foundation World Models (FWMs), arguing that synthesizing reward functions directly from formal logical or programmatic specifications like LTL is essential for building agents that are "correct-by-design" and capable of safe adaptation beyond static environments (Foundation World Models for Agents that Learn, Verify, and Adapt Reliably Beyond Static Environments).

Key Foundational Work

A Policy Search Method For Temporal Logic Specified Reinforcement Learning Tasks (2017) — contributed 2 concept elements to this direction.
Reinforcement Learning With Temporal Logic Rewards (2016) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_logic_based_reward_synthesis_8362bcfc,
  title = {logic-based reward synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logic-based-reward-synthesis/rdr_8362bcfcc6a141e9b327c50eed2c9760},
  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_logic_based_reward_synthesis_8362bcfc_v1,
  title = {logic-based reward synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logic-based-reward-synthesis/rdr_8362bcfcc6a141e9b327c50eed2c9760/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake