CS Paper Radar

Expressive Power of WSTL Formulas for Learning to Rank

Ruya Karagulle, Gustavo A. Cardona, Necmiye Ozay, Cristian-Ioan Vasile

eess.SY ·submitted 2026-09-18 18:22 UTC · v1
published

Abstract

Weighted Signal Temporal Logic (WSTL) is increasingly used as a scoring function in learning-to-rank problems of trajectories with safety guarantees, where its weighted quantitative semantics serve as a parametrized utility function. Despite the growing interest, prior work only assumes the expressiveness of WSTL formulas and empirically demonstrates its utility in capturing diverse preferences. This work focuses on the correctness of this assumption and asks whether using WSTL formulas as scoring functions is theoretically justified. We formalize two concepts: first, rank-realizability, which asks whether all rankings of a given signal set are achievable by varying weights, and, second, rank-capacity, the maximum signal set size for which the formula is rank-realizable. We propose a Mixed-Integer Linear Program to decide rank-realizability, and derive constructive lower bounds for rank-capacity. Experiments on a robotic navigation task show that while a practical WSTL specification may fail to be rank-realizable on a set with similar trajectories, its rank-capacity exceeds the size of the trajectory set. Analysis of Boolean-equivalent formulas reveals that formula structure affects expressivity and that rank-capacity can be increased without altering qualitative semantics.

Comment
8 pages, 2 figures, 2 tables, accepted to IEEE CDC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

SparseMax-dSTL: Sound Robustness with Horizon-Independent Gradient Allocation for Temporal Logic Trajectory Optimization

eess.SY cs.LOcs.RO ·2026-10-16 ·Sai Sandeep Damera, Ryan Matheu, John S. Baras, Calin Belta
theory similarity 0.65
Abstract · 8 pages, 5 figures. This work has been submitted to the IEEE for possible publication

A gradient-based solver that enforces a Signal Temporal Logic (STL) specification uses a smooth approximation of its quantitative semantics, the robustness. In safety-critical trajectory optimization, this approximation must have two properties. First, it must be sound, that is, nonnegative only on trajectories that satisfy the specification. Second, at each temporal operator, the weight of its gradient on the violating samples must stay bounded away from zero, however long the horizon. The approximations in use, including the log-sum-exp, its sound variant, and the generalized-mean robustness, do not have both. We introduce lower approximations of the minimum and the maximum whose gradients are sparsemax projections, and we prove that the robustness built from them has both. It lies below the exact robustness and is therefore sound, and its error has a bound that is independent of the number of samples and known before optimization. The gradient of each approximation is exactly zero on every sample beyond a data-dependent threshold, so the weight on violating samples a gap beyond the others has a positive lower bound at every horizon. On a planar unicycle and on a seven-joint manipulator beside a person in simulation, the log-sum-exp approximation is positive on a violating trajectory. As the horizon of the manipulator's task grows from 10 to 80 s, the gradient weight of the sound variant on the violating samples falls from 0.22 to 0.04, while that of sparsemax stays at 1. In a constrained trajectory optimization of the unicycle, the constraint on the log-sum-exp robustness returns a violating trajectory, whereas the constraint on the sparsemax robustness returns a trajectory that satisfies the specification with the required margin.

0.20

RLVR$^{2}$: Reinforcement Learning with Verifiable Rubric-based Ranking

cs.LG cs.AI ·2026-09-20 ·Hao Li, Zhengkun Zhang, Gangqiang Hu, Zhen Zhang, Yude Gao +2 more
similarity 0.62
Abstract · Preprint

Reinforcement Learning with Verifiable Rewards (RLVR) is expanding from tasks with well-defined correctness signals, such as mathematics and code, toward multifaceted quality requirements specified by multi-dimensional rubrics. Since policy optimization consumes one scalar per rollout, rubric-based pipelines must map multiple criterion scores into a scalar reward. This aggregation is often treated as score scaling, but it implicitly determines how quality dimensions trade off during training. The prevailing practice, normalizing each criterion and taking a linear combination, assumes that cardinal score differences are comparable across criteria and that gains on one criterion compensate for failures on another; both assumptions are unreliable when criteria are semantically heterogeneous. We propose Reinforcement Learning with Verifiable Rubric-based Ranking (RLVR$^2$), a verifiable ranking paradigm for rubric-based RLVR. For each criterion, RLVR$^2$ converts rubric scores into criterion-specific within-group ordinal outcomes, recovers a latent utility from the resulting comparison matrix, and merges these utilities into one training signal. By retaining only within-group ordering and discarding raw score magnitudes, RLVR$^2$ avoids calibrating heterogeneous rubric scales. It further supports objective-preserving attribute adjustment: auxiliary attributes that correlate with observed rankings but are not training objectives can enter the estimation without expanding the rubric or rewarding them directly. Across three model scales and 16 benchmarks, RLVR$^2$ consistently outperforms representative rubric-based baselines, achieving the best overall performance on most benchmarks at every scale. Analysis shows it controls systematic effects tied to reasoning efficiency and response formatting while preserving the quality objective.

0.28

From LLM-Generated Specifications to Learned Quadruped Locomotion

cs.RO cs.AI ·2026-09-07 ·Merve Atasever, Keyan Azbijari, Cagan Bakirci, Alfredo Reina Corona, Tolga Izdas +3 more
similarity 0.60
Abstract

Quadruped robot locomotion policies are often trained using reinforcement learning, which in turn relies heavily on hand-crafted reward functions. Designing reward functions requires substantial manual engineering, and it is often unclear which local rewards will induce the desired global behavior. Shaped rewards from formal specifications in languages like Signal Temporal Logic (STL) can make rewards more interpretable, but writing STL specifications itself still requires domain expertise. We study whether large language models (LLMs) can fill this gap by generating Parametric Signal Temporal Logic (PSTL) specifications that are subsequently used for policy learning. Given a natural language locomotion objective and a constrained specification grammar, GPT-5.5 and Qwen 3.6 independently propose STL templates for command tracking, safety, and gait structure. We instantiate the parameters of the generated PSTL templates using expert trajectories and retain only specifications that are consistent with demonstrated expert behavior. The resulting specifications are then transformed into smooth, finite-history reward functions and used to train a quadruped locomotion policy with Proximal Policy Optimization (PPO) in MuJoCo XLA (MJX). We evaluate both \emph{gait-aware} and \emph{gait-agnostic} settings. The former specifies walking-trot, trot, and bound regimes, while the latter allows contact patterns to emerge from the task objective. We compare against hand-engineered rewards, Text2Reward-style LLM-generated reward code, and an expert-switching oracle. Gait-aware Qwen 3.6 specifications achieved 100\% survival and command success across all tested speeds (0.3--2.1 m/s) and matched the target gait at high speeds, whereas Text2Reward achieved 0\% for both metrics at $\geq 1.9$ m/s. Videos: https://stl-locomotion.github.io/

0.15

Video2STL: Grounding VLM-Generated Temporal Specifications for Robot Learning

cs.RO cs.AI ·2026-09-29 ·Merve Atasever, Keyan Azbijari, Cagan Bakirci, Bo-Ruei Huang, Tolga Izdas +4 more
similarity 0.60
Abstract

Video-based policy learning is particularly promising, as it illustrates target behaviors without requiring action annotations or embodiment-matched demonstrations. A central challenge is deciding what information should be transferred from the video to the robot. Existing approaches commonly convert visual observations into scalar similarity or value signals, or ask foundation models to directly generate reward code. These approaches can make the temporal structure of a task difficult to inspect, ground, and reuse. We present Video2STL, a framework that converts observation-only videos into parametric Signal Temporal Logic (STL) specifications and uses the resulting formal representation for robot learning. A vision-language model extracts an embodiment-independent semantic event trace and constructs a bank of symbolic temporal specifications. The model determines the task structure, while numerical predicate thresholds and temporal bounds are grounded from successful robot trajectories. For policy learning, we separate short- and long-timescale temporal information: short-horizon specifications provide dense rewards through rolling-window quantitative robustness, while a causal monitor over a retained long-horizon specification provides one-time progress rewards for valid temporal prefixes. The same representation supports cross-embodiment transfer from human or animal videos to robot control. Across four manipulation tasks, Video2STL achieves $85.8\%$ average success-once and $67.0\%$ success-at-end, compared with $81.5\%/59.5\%$ for native dense PPO and $65.0\%/42.3\%$ for Text2Reward; in quadruped locomotion, Qwen-3.8 and GPT-5.6-based Video2STL policies achieve $100\%$ success across velocities from $0.3$ to $2.1\,\mathrm{m/s}$ while remaining competitive in high-speed energy efficiency. Project webpage: \href{https://video2stl.github.io/}{video2stl}.

0.29

Differentiable Ternary Temporal Logic Semantics with Polynomial Surrogate Networks

eess.SY cs.RO ·2026-10-03 ·Ryan Matheu, Sai Sandeep Damera, John S. Baras, Calin Belta
similarity 0.60
Abstract · 9 pages, 6 figures

Temporal logic provides designers a formal reasoning tool for specifying complex spatio-temporal behaviors and tasks for autonomous systems. Many techniques exist for control synthesis according to temporal logic specifications, spanning a large variety of systems, including robotics. However, the vast majority of implementations are limited to Boolean temporal logics. Boolean temporal logic does not have an innate mechanism for quantifying abstention, rather verdicts are either definitively \textit{True} or \textit{False}. Recent work demonstrates that ternary logic is a capable formalism for reasoning about robotic behaviors, with the natural ability to classify uncertainty with the \textit{Unknown} literal. Ternary temporal logic is still in its infancy, with work limited to synthesis for linear systems and monitoring. This work proposes a probabilistic relaxation of ternary temporal logic that allows for value and gradient computation through the same network while retaining exact verdicts on actual data. The relaxed network can be used as an objective in gradient-based control synthesis for both offline and online robotic control applications. We demonstrate the utility of our framework with two robotic manipulator tasks, one offline and one online, involving intermediate checking and sequencing of subtasks to demonstrate the benefit of our approach in terms of correct and timely execution.

0.20

Satisfiability Modulo Theories for Robust Synthesis of Signal Temporal Logic Specifications

eess.SY cs.RO ·2026-11-17 ·Philip Smith, Kevin Leahy
similarity 0.59
Abstract · Submitted to American Control Conference

Signal Temporal Logic is a popular framework for describing a robotic system's goals. Once described using a temporal logic framework, synthesis turns the goals into actual steps for the robots to follow. Currently, the state of the art for sound and complete synthesis is using Mixed-Integer Linear Programming (MILP), which struggles on long time horizons and large environments, preventing the construction of guaranteed safe plans for long deployments. This paper introduces a new synthesis method using Satisfiability Modulo Theories (SMT) which scales better for long deployments and adapts to environmental changes more quickly. We do this by introducing an encoding method for STL into SMT constraints, and an encoding method for discrete-time dynamical systems modeled as a transition system. We then conduct an empirical comparison of our SMT based methods against the state of the art MILP based methods. Results show that for this class of problems, SMT is an effective encoding strategy that performs the best on long time horizon tasks.

0.24

Class-Conditional Conformal Prediction for Signal Temporal Logic Inference with Many Classes

cs.LG ·2026-10-09 ·Yixuan Wang, Danyang Li, Matthew Cleaveland, Roberto Tron, Mingyu Cai
similarity 0.59
Abstract

Signal Temporal Logic (STL) inference provides interpretable formulas for time series classification. For multiclass classification, however, accurate predictions do not necessarily ensure that the inferred formulas are satisfied consistently with the true class. We introduce the positive satisfaction rate and codeword satisfaction rate to quantify satisfaction of required formulas and consistency with the complete class codeword, respectively. We develop a two-stage procedure that first learns discriminative formulas using a margin-based objective and then refines predicate thresholds toward a small positive robustness target while fixing the formula structure and temporal intervals. Satisfaction and ranking penalties discourage violations of required formulas and loss of class separation. The decoding loss is used as a nonconformity score and calibrated separately for each class, providing finite-sample class-conditional coverage under intra-class exchangeability. Experiments on naval, synthetic, and robot manipulation trajectories demonstrate discrepancies between classification accuracy and formula satisfaction. The results further reveal a data-dependent tradeoff between robustness tightness and satisfaction, while class-conditional calibration mitigates undercoverage that can be hidden by pooled calibration.

0.25

Integer-Free Control Synthesis for Signal Temporal Logic via Ranked Implicants

eess.SY ·2026-10-14 ·Arash Bahari Kordabad, Mohammad H. Mamduhi, Sadegh Soudjani
theory similarity 0.59
Abstract · 7 pages, 2 figures

This paper proposes an integer-free method for control synthesis of nonlinear discrete-time systems under finite-horizon Signal Temporal Logic (STL) constraints. Instead of introducing integer variables, we consider the discrete choices of the specification in a ranked order and solve a standard nonlinear program for each selected choice until a satisfying trajectory is found. We first define implicants as sets of timed atomic constraints whose joint satisfaction is sufficient to satisfy the specification. A reference trajectory obtained from a smooth approximation of the STL robustness is used to rank these implicants. Fixing one implicant turns the problem into a standard nonlinear program with no auxiliary weights or bilinear terms. If the solution does not satisfy the specification, the next implicant will be considered. We prove soundness and completeness of our method relative to the nonlinear programming solver. Numerical evaluation on nonlinear multi-agent systems shows that our proposed method identifies satisfying trajectories where the exact continuous reformulation fails, and moreover, it is faster than a mixed-integer formulation of the same specification.

0.23