🤖 AI

Value Functions for Temporal Logic: Optimal Policies and Safety Filters

This paper addresses the limitation of greedy Q-function maximization in undiscounted infinite-horizon temporal logic tasks by constructing non-Markovian policies based on state history to ensure optimality for nested specifications and demonstrating how Q-functions can serve as safety filters for complex temporal logic requirements.

Original authors: Oswin So, William Sharpless, Sylvia Herbert, Chuchu Fan

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Oswin So, William Sharpless, Sylvia Herbert, Chuchu Fan

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 (or a drone) how to navigate a complex world to complete a very specific, multi-step mission. The mission isn't just "go from A to B." It's a complicated set of rules like: "Go to the kitchen, but don't touch the stove until you have the key, then loop around the living room forever, and make sure you never bump into the walls."

This paper tackles a tricky problem in robotics and AI: How do you make sure the robot actually follows these complex rules without getting stuck or taking shortcuts that look good on paper but fail in reality?

Here is the breakdown of their solution using simple analogies.

The Problem: The "Procrastinating Robot"

In the world of AI, robots usually learn by trying to maximize a "score" (called a Value Function). Think of this score like a video game high score.

The Trap: Sometimes, a robot can get a perfect score without actually finishing the game.
The Analogy: Imagine a game where you get points for "eventually reaching the treasure." A greedy robot might think, "If I just stand here forever, I haven't failed yet, so I still have a chance to get the treasure later." It keeps deferring the task indefinitely. It looks like it's doing well (the score is high), but it never actually moves.
The Paper's Insight: The authors found that for complex, long-term rules (called Temporal Logic), simply telling the robot to "pick the move that gives the best immediate score" doesn't work. The robot needs to remember its history, not just its current location.

The Solution: The "Time-Traveling Map"

To fix this, the authors created a new way of thinking about the robot's "map" (Value Function).

History is Key: Instead of just looking at where the robot is right now, the new method looks at the robot's entire journey so far. It's like a GPS that doesn't just say "You are here," but says, "You are here, you started at the garage 5 minutes ago, and you haven't picked up the key yet."
The "Witness" Timer: They introduced a concept called a "witness time." Imagine a countdown timer that starts when the robot begins its mission. The robot knows exactly how long it has to complete a specific step before the "score" starts dropping. This forces the robot to stop procrastinating and actually finish the task.
Breaking it Down: Complex rules are like a giant puzzle. The authors showed how to break a huge, scary rule (like "Loop forever while avoiding walls") into smaller, manageable pieces (like "Go to the door," then "Open the door," then "Loop"). They solve the small pieces first and stitch them together into a master plan.

The "Safety Filter" (The Guardian Angel)

One of the most practical parts of the paper is the Safety Filter.

The Scenario: Imagine you have a robot that is already programmed to do a job (a "nominal policy"), but it's a bit clumsy or doesn't know the complex rules.
The Filter: The authors built a "guardian angel" layer that sits between the robot's brain and its motors.
- If the robot tries to make a move that satisfies the complex rules, the guardian lets it go.
- If the robot tries to make a move that would break the rules (like crashing into a wall or forgetting to get the key), the guardian steps in and forces a different move.
The Result: The robot can still try to do its job, but it is guaranteed to follow the complex rules. It's like a parent letting a child drive a car, but with a magical steering wheel that only turns when it's safe and legal to do so.

Real-World Tests

The authors didn't just write theory; they tested it:

Two Robots in a Grid: They made two robots work together in a grid world. One had to get a key to open a door for the other. They showed that without their special filter, the robots would get stuck in a deadlock or fail to coordinate. With the filter, they successfully completed the complex mission.
A Flying Drone: They tested this on a real drone (a Crazyflie). The drone had to fly to a "worksite," loop around to pick up items, and avoid obstacles.
- Without the filter: The drone crashed or got stuck.
- With a "Safety Only" filter: The drone stayed safe (didn't crash) but failed to complete the mission (didn't get the items).
- With their "Complex Rule" filter: The drone stayed safe and successfully completed the entire complex mission.

Summary

In short, this paper gives robots a better way to understand "to-do lists" that stretch into the infinite future. It stops them from procrastinating, breaks big goals into small steps, and adds a safety net that ensures they follow the rules even if their original plan was flawed. It turns a robot that might "cheat" by doing nothing into one that reliably completes the job.

Technical Summary: Value Functions for Temporal Logic: Optimal Policies and Safety Filters

Problem Statement
While Bellman equations for basic reach, avoid, and reach-avoid problems are well-established, the relationship between value optimality and policy optimality becomes subtle in undiscounted infinite-horizon settings, particularly for complex Temporal Logic (TL) specifications. A critical pathology arises where greedily maximizing the Q-function can produce policies that indefinitely defer task completion for reach-avoid problems (equivalent to Until specifications), even when the value function itself is optimal. This occurs because the optimal action sequence for infinite trajectories is fundamentally non-Markovian; the optimal input may need to "switch" from maximizing the current value to a constituent value in a decomposition graph to satisfy remaining infinite-horizon specifications. Existing methods, such as state-augmentation for dual-objective problems, struggle to generalize to complex formulae involving nested Until, Globally, and Globally-Until specifications. Furthermore, there is a need for safety filters that guarantee the satisfaction of complex TL specifications, extending beyond simple avoidance or reach-avoid tasks.

Methodology
The authors propose a framework that generalizes value and Q-functions to state histories to handle the non-Markovian nature of the problem. The methodology relies on the algebraic decomposition of the value function for TL into a graph of constituent value functions.

Non-Markovian Value Functions: The paper defines optimal value functions $V^*$ and Q-functions $Q$ over state histories $x_{0:t}$ rather than just current states. This allows the policy to account for the history required to satisfy temporal constraints.
Time-Augmented Systems and Witness Times: To address the deferral issue in Until ( $U$ ) specifications, the authors introduce a time-augmented system with a timer. They define an "optimal witness time" $\sigma^*$ , which is the earliest time a trajectory achieves the optimal robustness score. This allows the construction of policies that switch from a finite-horizon greedy strategy (maximizing the Q-function within the witness time) to a suffix policy that satisfies the remaining sub-formula.
Compositional Policy Construction: The paper constructs optimal policies for a specific fragment of TL formulas (Definition 3), which includes:
- Propositional formulas.
- Until ( $p U \phi$ ), Next ( $X\phi$ ), and Globally ($Gp$) operators.
- Globally-Until ( $G(\bigvee p_i U r_i)$ ), which encodes Büchi acceptance criteria.
- Disjunctions and propositional conjunctions.
  The construction assumes the existence of optimal policies for sub-formulas (Assumption 2) and recursively combines them. For Globally-Until, the policy iteratively visits each Until component in sequence to ensure infinite visits to required state sets.
Safety Filtering: The authors demonstrate that the Q-function can serve as a safety filter. They define a failure set where the specification cannot be satisfied with non-negative robustness. A least-restrictive intervention scheme is proposed: if a nominal policy's action yields a non-negative Q-value (indicating future satisfiability), it is allowed; otherwise, the system switches to the action that maximizes the Q-function. Under specific assumptions (e.g., absence of unbounded Until operators), this filter guarantees specification satisfaction.

Key Contributions

Generalization of Value Functions: The paper generalizes the optimal value function and Q-function to state histories (Definition 1) and defines optimality over histories (Definition 2), addressing the non-Markovian nature of infinite-horizon TL problems.
Compositional Optimal Policies: For a broad class of TL formulas (Definition 3), the authors construct compositional optimal policies for the associated robustness metric (Theorems 1–8). This includes handling the deferral pathology in Until and Globally-Until specifications.
Least-Restrictive Safety Filters: The work shows that the Q-function over (potentially sub-optimal) histories yields a least-restrictive safety filter for a nominal policy (Theorems 9, 10). This filter guarantees specification satisfaction while respecting the prior path of the nominal policy, provided the formula meets certain structural constraints.

Results and Demonstrations
The paper validates the proposed framework through theoretical proofs and two hardware/software demonstrations:

Two-Agent GridWorld: The authors solve a 4-dimensional joint state-action problem with a complex specification involving time-bounded reach, safety, and liveness constraints. They demonstrate that the derived optimal policy ( $\pi_{spec}$ ) successfully guides the system to satisfy the specification. Furthermore, when used as a filter for "coffee" and "tea" nominal policies (which individually fail to satisfy the joint spec), the filter ensures the joint system satisfies the complex task, whereas a standard "safety-only" filter leads to deadlock and failure.
Single-Agent Drone: Using a Crazyflie drone, the authors demonstrate the policy in a navigation task with obstacles. The proposed TL filter successfully guides the drone to a worksite while satisfying complex temporal constraints (e.g., looping through specific zones, avoiding walls). In contrast, an unfiltered nominal policy or a filter based only on safety constraints results in the drone getting trapped or crashing.

Significance
The paper claims to offer a practical approach to generate optimal policies for the value of a broad class of TL formulas by extending recent decomposition results. Its primary significance lies in resolving the pathology where greedy Q-maximization fails for infinite-horizon tasks and in providing a mechanism to synthesize safety filters that guarantee complex task satisfaction, not just safety. By extending the scope of solvable formulas to include nested Until and Globally-Until specifications, the work bridges the gap between Hamilton-Jacobi reachability and Reinforcement Learning for complex, safety-critical temporal tasks.