Value Functions for Temporal Logic: Optimal Policies and Safety Filters

Oswin So, William Sharpless, Sylvia Herbert, Chuchu Fan · 2026

Read Value Functions for Temporal Logic: Optimal Policies and Safety Filters by Oswin So, William Sharpless, Sylvia Herbert, Chuchu Fan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-01051.txt.

Introduction

Oswin So, William Sharpless, Sylvia Herbert, and Chuchu Fan study value functions for temporal logic tasks in control, where policies must satisfy time-based specifications. Bellman equations for simple reach and avoid problems are well studied, but in undiscounted infinite-horizon settings a policy that greedily maximizes value can defer task completion forever. That can happen even when the value function is optimal. The problem is sharpest for reach-avoid and Until specifications.

Building on a decomposition of the temporal logic value function into a graph of simpler value functions, the authors construct non-Markovian policies based on state history that avoid that pathology. They prove optimality for nested Until, Globally, and combined specifications under a quantitative robustness score, and show the Q function can serve as a safety filter for complex tasks.

Catalog record

CREATOROswin So, William Sharpless, Sylvia Herbert, Chuchu Fan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.01051

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Value Functions for Temporal Logic: Optimal Policies and Safety Filters Oswin So, William Sharpless, Sylvia Herbert, Chuchu Fan Abstract While Bellman equations for basic reach, avoid, and reach-avoid problems are well studied, the relationship between value optimality and policy optimality becomes subtle in the undiscounted infinite-horizon setting, particularly for more complicated tasks. Greedily maximizing the Q-function can produce policies that indefinitely defer task completion for reach-avoid problems, or equivalently, Until specifications, even when the value function is optimal. Building upon recent results decomposing the value function for temporal logic (TL) into a graph of constituent value functions, we construct non-Markovian policies based on state history that avoid this pathology and prove their optimality with respect to the quantitative robustness score for nested Until, Globally, and Globally-Until specifications. We further show how the Q function can serve as a safety filter for complex TL specifications, extending prior results beyond simple avoid or reach-avoid tasks. \declaretheoremstyle [bodyfont=]normalstyle \declaretheorem [name=Theorem]thm \declaretheorem [name=Lemma]lemma \declaretheorem [name=Definition]defi \declaretheorem [name=Problem]problem \declaretheorem [name=Example,style=normalstyle]example \declaretheorem [name=Counterexample,style=normalstyle]counterexample \declaretheorem [name=Proposition]prop \declaretheorem [name=Corollary]coroll \declaretheorem [name=Remark,style=normalstyle]rmk \declaretheorem [name=Note,numbered=no,style=normalstyle]note \declaretheorem [name=Assumption]assmp I Introduction and Related Work The value function is central to optimal control and reinforcement learning (RL), encoding the optimal objective over action sequences. While it can be computed via dynamic programming (DP), this quickly becomes intractable in high dimensions. Instead, RL leverages the Bellman equation (BE), a recursive characterization of the value that enables approximation without grid-based DP. The associated Q-function further allows optimal policies to be obtained via single-step maximization. This framework is typically applied when objectives are defined by temporal sums of rewards (or costs), as in Markov Decision Processes (MDPs). While this approach has been successful, the additive combination of rewards and costs in RL can be difficult; the optimal trajectory may incur significant cost so long as it obtains high reward, leading practitioners to iteratively tune hyperparameters until desirable performance is observed. To overcome this limitation, values based on temporal maxima and minima have been introduced from the field of Hamilton-Jacobi reachability (HJR) [ 15 , 8 ] . In recent years, several works have integrated the max-min BE of HJR into RL frameworks to design safe and performant algorithms [ 9 , 12 , 10 , 20 ] . Fig. 1 : Hardware rollouts from a Crazyflie drone using an unsafe task policy , the task policy filtered for safety , and the task policy filtered for the specification . Filtering for safety maintains safety but violates the specification. Our proposed safety filter for TL specifications guarantees the specification is satisfied. HJR characterizes values for basic safety and liveness tasks, called the reach, avoid and reach-avoid problems [ 3 ] . Notably, the objectives of these values are equivalent to the quantitative semantics of basic predicates in Temporal Logic (TL) [ 16 , 6 , 7 , 4 ] , namely eventually ( \mathsf{F} ), always ( \mathsf{G} ), and until ( \mathsf{U} ) [ 5 ] . TL itself is merely a specification language but offers an attractive way to automatically translate and reduce complex task specifications into values for RL. Recently, it was demonstrated that HJR and the HJ-RL algorithms can be extended to broader classes of TL via algebraic decomposition of the value into a graph of values [ 18 , 19 ] . This was first considered in [ 18 ] , where the dual-objective values, called the reach-reach ( \mathsf{F}\land\mathsf{F} ) and reach-always-avoid ( \mathsf{F}\land\mathsf{G} ) problems, proved to decompose into coupled sets of BEs, and later extended to a broad class of TL specifications in [ 19 ] . These methods scale the approximation of the value in high-dimension and model free settings to complex task specifications. However, a novel challenge arises in these settings: simple single-step maximization of the corresponding Q function does not necessarily yield the optimal action sequence for infinite-horizon trajectories (see Ex. III ), a fundamentally non-Markovian problem [ 18 ] . While decomposition allows one to solve the value for infinite trajectories, it remains to show when the optimal inputs must “switch” from single-step maximization of the current value to a constituent value in the graph, corresponding to the remaining unsatisfied and infinite-horizon specifications. In [ 18 ] , a Markovian policy is derived with an efficient state-augmentation that tracks relevant quantitative semantics and yields the optimal switching condition. However, this approach is derived in the dual-objectives and is difficult to generalize to complex formulae, particularly those that include reach-avoid-loop specifications ( \mathsf{GU} ). In this work, we propose a generalization of the value and Q-function to state histories to compute non-Markovian policies optimal with respect to any state history. This approach extends to the broad class of TL specifications for which the value may be decomposed [ 19 ] . Moreover, this approach offers the novel ability to synthesize safety filters for a user-defined nominal policy that (1) guarantee specification satisfaction in a least-restrictive manner and (2) do so in a manner that is optimal given the prior sub-optimal path of the nominal policy. In this work, the optimality of the policy over histories and the guarantee of satisfaction are made possible by augmenting the system with a temporal state (Def. III-A ). For completeness, we re-derive the policies in [ 18 ] for the Until predicate via the novel framework and we show the approach proposed in this work extends to the larger class of formulae defined in Def. II-B . Ultimately, this work offers a practical approach to generate an optimal policy for the value of a broad class of TL formulae, and demonstrates the result may be used to filter a nominal policy to ensure complex task satisfaction. The contributions of this work are as follows: 1. We generalize the optimal value function and Q function (Def. II-B ) and optimal policy (Def. II-B ) for state histories to handle the non-Markovian nature of the problem. 2. For a broad class of TL formulae (Def. II-B ), we use this framework to construct a compositional optimal policy for the associated robustness metric (Thms. III-B - VI ). 3. Using the Q function over (sub-optimal) history yields a least-restrictive safety filter for a nominal policy to ensure satisfaction (Thms. VII , VII ). II Preliminaries II-A Problem Setting and Notation We consider a discrete-time system x_{t+1}=f(x_{t},a_{t}) with state x_{t}\in\mathcal{X}\subseteq\mathbb{R}^{n} and action a_{t}\in\mathcal{A}\subseteq\mathbb{R}^{m} . Let x_{0:t}\in\mathcal{X}^{t+1} and a_{0:t}\in\mathcal{A}^{t+1} denote state and action trajectories of length t+1 , and use x_{t}=x_{t:t}\in\mathcal{X} and a_{t}=a_{t:t}\in\mathcal{A} for brevity. Let \mathcal{X}^{+}\coloneqq\bigcup_{t=1}^{\infty}\mathcal{X}^{t} be the set of all finite-length state trajectories. For a (non-Markovian) policy \pi:\mathcal{X}^{+}\to\mathcal{A} , we say that the infinite trajectory x^{\pi}_{0:\infty} is generated by \pi from x_{0:t}\in\mathcal{X}^{+} if x^{\pi}_{0:t}=x_{0:t} and x^{\pi}_{k+1}=f(x^{\pi}_{k},\pi(x^{\pi}_{0:k})) for all k\geq t . In general, we use the word ‘‘policy’’ to refer to a non-Markovian policy (dependent on history), and specify when it is Markovian 1 1 1 One can always augment the state with the (infinite-dimensional) history to make the policy Markovian. dHowever, this would be inefficient and we avoid this to distinguish the proposed Markovian approach . We use Linear Temporal Logic (LTL) [ 2 ] specifications augmented with quantitative semantics via the robustness score [ 6 ] from Signal Temporal Logic (STL)

Read the complete text