TGPO: Temporal Grounded Policy Optimization for Signal Temporal Logic Tasks

## Abstract

Abstract Learning control policies for complex, long-horizon tasks is a central challenge in robotics and autonomous systems. Signal Temporal Logic (STL) offers a powerful and expressive language for specifying such tasks, but its non-Markovian nature and inherent sparse reward make it difficult to be solved via standard Reinforcement Learning (RL) algorithms. Prior RL approaches focus only on limited STL fragments or use STL robustness scores as sparse terminal rewards. In this paper, we propose TGPO, Temporal Grounded Policy Optimization, to solve general STL tasks. TGPO decomposes STL into timed subgoals and invariant constraints and provides a hierarchical framework to tackle the problem. The high-level component of TGPO proposes concrete time allocations for these subgoals, and the low-level time-conditioned policy learns to achieve the sequenced subgoals using a dense, stage-wise reward signal. During inference, we sample various time allocations and select the most promising assignment for the policy network to rollout the solution trajectory. To foster efficient policy learning for complex STL with multiple subgoals, we leverage the learned critic to guide the high-level temporal search via Metropolis-Hastings sampling, focusing exploration on temporally feasible solutions. We conduct experiments on five environments, ranging from low-dimensional navigation to manipulation, drone, and quadrupedal locomotion. Under a wide range of STL tasks, TGPO significantly outperforms state-of-the-art baselines (especially for high-dimensional and long-horizon cases), with an average of 31.6% improvement in task success rate compared to the best baseline. The code will be available at https://github.com/mengyuest/TGPO

## 1 Introduction

Signal Temporal Logic (STL) is a powerful framework for specifying tasks with temporal and spatial constraints in real-world robotic applications. However, designing controllers to satisfy these specifications is difficult, especially for systems with complex dynamics and a long task horizon. While Reinforcement Learning (RL) excels in handling these dynamical systems, directly deploying RL for STL specifications poses significant challenges. The history-dependent nature of STL breaks the Markovian assumption for the common RL algorithms. Furthermore, the reward based on the STL satisfaction is extremely sparse for long-horizon tasks, making RL struggle to learn effectively.

Existing model-free RL approaches for STL tasks typically leverage state augmentation with reward shaping. $\tau$-MDP (Aksaray et al., 2016) encodes histories explicitly in the augmented spaces and F-MDP (Venkataraman et al., 2020) designs flags to bookkeep the satisfaction of STL subformulas. However, these techniques only work on limited STL fragments with up to two temporal layers. While model-based RL (Kapoor et al., 2020; He et al., 2024) has fewer restrictions on the STL formulas, learning the system (latent space) dynamics can be challenging, and the estimation error accumulates over long horizons. Additionally, the planning often relies on Monte Carlo Tree Search or sampling action sequences, which may not be tractable for high-dimensional systems.

We argue that the primary barrier for RL to efficiently solve STL tasks is the difficulty of designing a dense, stage-wise reward function. This challenge stems directly from the unspecified temporal variables governing the “reach”-type tasks in STL formulas, which prevents a direct decomposition of STL into a sequence of executable subgoals. For example, for an STL $F_{[0,160]}A\land F_{[0,160]}B$ (“Eventually reach $A$ and eventually reach $B$ within the time interval $[0,160]$”), the time assignments for reaching $A$ and reaching $B$ determine the order of visiting these regions. If we can ground the variables into concrete values (e.g., reach $A$ at 35, and reach $B$ at 120), the problem can be cast into a sequence of goal-reaching problems, which is much easier to solve by RL.

Inspired by this observation, we propose a hierarchical RL framework to solve STL tasks by iteratively conducting Temporal Grounding and Policy Optimization (TGPO). The high-level component assigns values for the time variables to form the sequenced subgoals, and the low-level time-conditioned policy learns to achieve the task guided by the dense, stage-wise rewards derived from these subgoals. To efficiently bind values for multiple time variables, we carry out a high-level temporal search with a critic that predicts STL satisfaction. A Metropolis–Hastings sampling is used to guide exploration toward more “promising” time allocations. During inference, we sample time variable assignments and evaluate them using the critic. The most promising schedule is then executed by the low-level policy to generate the final solution trajectory for the STL specification.

We conduct extensive experiments over five simulation environments, ranging from 2D linear dynamics to 29D Ant navigation tasks. Compared to other baselines, TGPO^* (with Bayesian time variable sampling) achieves the highest overall task success rate. The performance gains are significant, especially in high-dimensional systems and long-horizon tasks. Furthermore, our time-conditioned design offers key benefits: our critic offers interpretability by identifying promising temporal plans, and the policy can generate diverse, multi-modal behaviors to satisfy a single STL specification.

Our main contributions are summarized as follows: (1) Hierarchical RL-STL framework: To the best of our knowledge, we are the first to develop a hierarchical model-free RL algorithm capable of solving general, nested STL tasks over long horizons. (2) Critic-guided Bayesian sampling: We introduce a critic-guided temporal grounding mechanism that, together with STL decomposition, yields subgoals and invariant constraints. This mechanism constructs an augmented MDP with dense, stage-wise rewards and thus overcomes the sparse reward challenges that have hindered existing RL approaches. (3) Interpretability: By explicitly grounding subgoals and invariant constraints in the STL structure using critic-guided Bayesian sampling, our approach offers a more interpretable learning process, where progress can be directly traced to logical task components. (4) Complex dynamics and reproducibility: TGPO demonstrates strong performance over other baselines and fits for complex dynamics, which supports the effectiveness of the design. All the code (the algorithm, the simulations and STL tasks) will be open-sourced to advance STL planning.

## 2 Related work

### 2.1 Signal Temporal Logic tasks

Signal Temporal Logic (STL) offers a powerful framework for specifying robotics tasks (Donzé, 2013). Unlike Linear Temporal Logic (LTL), STL operates over continuous signals with time intervals and lacks an automaton representation, making it challenging to conduct planning  (Finucane et al., 2010). Traditional approaches for STL include sampling-based methods (Vasile et al., 2017; Karlsson et al., 2020; Linard et al., 2023; Sewlia et al., 2023), Mixed-integer Programming (Sun et al., 2022; Kurtz & Lin, 2022) and trajectory optimization (Leung et al., 2023). More recently, learning-based methods emerged, such as differentiable policy learning (Liu et al., 2021; 2023; Meng & Fan, 2023), imitation learning (Puranic et al., 2021; Leung & Pavone, 2022; Meng & Fan, 2024; 2025), and reinforcement learning (RL) (Liao, 2020).

### 2.2 Reinforcement learning for temporal logic tasks

Temporal logic RL has been extensively studied in Linear Temporal Logic (LTL) and some Signal Temporal Logic (STL) fragments (Liao, 2020), where the key challenge is designing suitable rewards. For LTL, existing methods (Sadigh et al., 2014; Li et al., 2017; Hasanbeig et al., 2018; 2020) typically convert the formula into Limit-Deterministic Büchi Automata (LDBA) (Sickert et al., 2016) or reward machines (Icarte et al., 2018), while LTL2Action (Vaezipoor et al., 2021) uses progression (Bacchus & Kabanza, 2000) to assign dense reward, and SpectRL (Jothimurugan et al., 2019) devises a composable specification language for complex objectives. In contrast, STL poses additional challenges due to its explicit time constraints and real-value predicates. Early approaches augment the state space via temporal abstractions using history segments (Aksaray et al., 2016; Ikemoto & Ushio, 2022) or flags (Venkataraman et al., 2020; Wang et al., 2024), while bounded horizon nominal robustness (BHNR) (Balakrishnan & Deshmukh, 2019) offers intermediate reward approximations. Recent work uses model-based learning to solve STL tasks with evolutionary strategies (Kapoor et al., 2020) and Monte-Carlo Tree Search in value function space (He et al., 2024). However, most of these methods are restricted to STL structures and systems (limited temporal nesting, fixed-size time windows, or grid-like environments). Instead, our method can handle more general STLs and efficiently designs augmented states along with dense, stage-wise rewards.

## 3 Preliminaries

### 3.1 Signal Temporal Logic (STL)

Consider a discrete-time system $x_{t+1}=f(x_{t},u_{t})$ where $x_{t}\in\mathcal{X}\subseteq\mathbb{R}^{n}$ and $u_{t}\in\mathcal{U}\subseteq\mathbb{R}^{m}$ denote the state and control at time $t$. Starting from an initial state $x_{0}$, a signal $\sigma=x_{0},...,x_{T}$ is generated via controls $u_{0},...,u_{T-1}$. STL specifies properties via the following rules (Donzé et al., 2013):

$$ $\phi::=\top\ |\ \mu(x)\geq 0\ |\ \neg\phi\ |\ \phi_{1}\land\phi_{2}\ |\ \phi_{1}U_{[a,b]}\phi_{2}.$ (1) $$

Here the boolean-type operators split by “$|$” are the building blocks to compose an STL: $\top$ means “true”, $\mu$ denotes a predicate function $\mathbb{R}^{n}\to\mathbb{R}$, and $\neg$, $\land$, $U$, [a,b] are “negation”, “conjuction”, “until” and the time interval from $a$ to $b$.
Other operators are “disjunction”: $\phi_{1}\lor\phi_{2}=\neg(\neg\phi_{1}\land\neg\phi_{2})$, “eventually”: $F_{[a,b]}\phi=\top U_{[a,b]}\phi$ and “always”: $G_{[a,b]}\phi=\neg F_{[a,b]}\neg\phi$. We denote $\sigma,t\models\phi$ if the signal $\sigma$ from time $t$ satisfies the STL formula (the evaluation of $\phi$ returns True). In particular, we simply write $\sigma\models\phi$ if the signal is evaluated from $t=0$.
For operators $\top,\mu\geq 0,\neg,\land$ and $\lor$, the evaluation checks for the signal state at time $t$. As for temporal operators (Maler & Nickovic, 2004): $\sigma,t\models F_{[a,b]}\phi\Leftrightarrow\,\,\exists t^{\prime}\in[t+a,t+b],\,\sigma,t^{\prime}\models\phi$; and $\sigma,t\models G_{[a,b]}\phi\Leftrightarrow\,\,\forall t^{\prime}\in[t+a,t+b],\,\sigma,t^{\prime}\models\phi$; and $\sigma,t\models\phi_{1}U_{[a,b]}\phi_{2}\Leftrightarrow\exists t^{\prime}\in[t+a,t+b],\sigma,t^{\prime}\models\phi_{2},\forall t^{\prime\prime}\in[0,t^{\prime}],\sigma,t^{\prime\prime}\models\phi_{1}$. In plain words, $\phi_{1}U_{[a,b]}\phi_{2}$ means “$\phi_{1}$ holds until $\phi_{2}$ happens in $[a,b]$.” Robustness score (Donzé & Maler, 2010) $\rho(\sigma,t,\phi)$ measures how well a signal $\sigma$ satisfies $\phi$. We have $\rho\geq 0\text{ iff }\sigma,t\models\phi$. The score $\rho$ is:

$$ $\begin{cases}&\rho(\sigma,t,\top)=1,\quad\quad\quad\rho(\sigma,t,\mu)=\mu(\sigma(t)),\quad\quad\quad\rho(\sigma,t,\neg\phi)=-\rho(\sigma,t,\phi),\\ &\rho(\sigma,t,\phi_{1}\land\phi_{2})=\min\{\rho(\sigma,t,\phi_{1}),\rho(\sigma,t,\phi_{2})\},\\ &\rho(\sigma,t,F_{[a,b]}\phi)=\sup\limits_{r\in[a,b]}\rho(\sigma,t+r,\phi),\quad\quad\rho(\sigma,t,G_{[a,b]}\phi)=\inf\limits_{r\in[a,b]}\rho(\sigma,t+r,\phi),\\ &\rho(\sigma,t,\phi_{1}U_{[a,b]}\phi_{2})=\sup\limits_{t^{\prime}\in[t+a,t+b]}\min\left\{\rho(\sigma,t^{\prime},\phi_{2}),\inf\limits_{t^{\prime\prime}\in[t,t^{\prime}]}\rho(\sigma,t^{\prime\prime},\phi_{1})\right\}.\end{cases}$ (2) $$

### 3.2 Markov Decision Process

A Markov Decision Process (MDP) is defined by the tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma)$ where: $\mathcal{S}$ and $\mathcal{A}$ represent the sets of states and actions, respectively, $P:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to[0,1]$ is the probabilistic transition function where $P(s^{\prime}|s,a)$ denotes the probability of the next state $s^{\prime}$ given current state $s$ and action $a$, $R:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$ is the reward function, and $\gamma\in[0,1)$ is the discount factor. The agent decision is made by a policy $\pi:\mathcal{S}\to\mathcal{A}$ which maps states to a probability distribution over actions. The objective is to find an optimal policy $\pi^{*}$ that maximizes the expected discounted cumulative reward from a starting state $s_{0}$: $\mathop{\mathbb{E}}_{\pi}\left[\sum\limits_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t})\big|s_{0}\right]$ with $a_{t}\sim\pi(\cdot|s_{t})$ and $s_{t+1}\sim P(\cdot|s_{t},a_{t})$.

### 3.3 Problem formulation

Consider a discrete-time system with state space $\mathcal{X}$, control space $\mathcal{U}$ and the initial state set $\mathcal{X}_{0}$. Given an STL formula $\phi$ defined in Eq. [1](https://arxiv.org/html/2510.00225v1#S3.E1), our objective is to first formulate an MDP $(\mathcal{S},\mathcal{A},P,R,\gamma)$ and then learn a policy: $\pi:\mathcal{S}\to\mathcal{A}$ to maximize the satisfaction probability, $\max\limits_{\pi}\mathop{\mathbb{P}}\limits_{x_{0}\in\mathcal{X}_{0}}(\sigma\models\phi)$.

Remarks.
It is tempting to treat the control system state $\mathcal{X}$ as the MDP state $\mathcal{S}$, and the control input $\mathcal{U}$ as the actions $\mathcal{A}$. However, for STL tasks, the policy also depends on the history(^1^11E.g., if an STL task is to “Eventually reach region A and then reach B”, the policy needs to “remember” whether it has already visited the region A in order to proceed to reach B.), making the problem non-Markovian. Thus, we need to augment the state to keep history data. Besides, the satisfaction of an STL is checked over the full trajectory, making it difficult to define dense rewards (unlike LTL, where stage-wise rewards (Camacho et al., 2017; Vaezipoor et al., 2021) can be defined). Thus, we need to design dense rewards under the augmented state space to learn efficiently.

## 4 Methodology

We propose TGPO, Temporal Grounded Policy Optimization, to address the problem considered. The entire framework is illustrated in Fig. [1](https://arxiv.org/html/2510.00225v1#S4.F1), and we explain each component in detail below.

Figure: Figure 1: Framework: STL decomposition and critic-guided temporal grounding yield subgoals and invariant constraints that guide an augmented MDP with dense rewards for policy optimization.
Refer to caption: x1.png

### 4.1 STL subgoal decomposition

Our method of decomposing STL into subgoals with invariant constraints is inspired by Kapoor et al. (2024); Liu et al. (2025). The essence is to first translate the STL into a set of subtasks, where each subtask has a checker $\mu$ on the trace $\sigma$ and belongs to one of the following types:

- •
Reachability task: achieve $\mu(\sigma(\tau))\geq 0$ at a time instant $\tau$, denoted as $\operatorname{Reach}(\mu,\tau)$.
- •
Invariance task: keep $\mu(\sigma(\tau))\geq 0$ for all time $\tau$ in an interval $W$, denoted as $\operatorname{Inv}(\mu,W)$.

For basic STL formulas, the time instants and the time intervals can be concrete values or variables: e.g., the formula $G_{[a,b]}\mu$ can be written as $\operatorname{Inv}(\mu,[a,b])$ with concrete $[a,b]$, whereas the formula $F_{[a,b]}\mu$ can be written as $\operatorname{Reach}(\mu,\tau)$ with the time variable $\tau\in[a,b]$,
and $\mu_{1}U_{[a,b]}\mu_{2}$ can be written as $\{\operatorname{Reach}(\mu_{2},\tau),\operatorname{Inv}(\mu_{1},[a,\tau])\}$ with the time variable $\tau\in[a,b]$.
For a nested STL, we follow a top-down approach to “flatten” it into reachability and invariance tasks governed by time variables. We denote $\operatorname{Reach}(\phi,\tau)$ for $\rho(\sigma,\tau,\phi)\geq 0$ and use $\operatorname{Inv}(\phi,W)$ to represent $\rho(\sigma,\tau,\phi)\geq 0,\forall\tau\in W$.
For any STL $\phi$ we can write it as $\operatorname{Reach}(\phi,0)$ and then we rewrite with tasks using its subformulas. The subformula will always carry time variables from its ancestor operators, and we repeat the process until all the tasks are represented as atomic propositions (APs) corresponding to $\mu$ or its negation $\neg\mu$. For example, for $\phi=F_{[a,b]}\phi_{0}\land G_{[c,d]}\neg\mu_{0}$ where $\phi_{0}=\mu_{1}\land G_{[a_{2},b_{2}]}\mu_{2}\land F_{[a_{3},b_{3}]}\mu_{3}$ is a subformula, we can represent $\phi$ as $\{\operatorname{Reach}(\phi_{0},\tau),\operatorname{Inv}(\neg\mu_{0},[c,d])\}$ with domain $\{\tau\in[a,b]\}$, then we can pass $\tau$ into $\phi_{0}$ to represent the STL as $\{\operatorname{Reach}(\mu_{1},\tau),\operatorname{Inv}(\mu_{2},[\tau+a_{2},\tau+b_{2}]),\operatorname{Reach}(\mu_{3},\tau+\tau^{\prime}),\operatorname{Inv}(\neg\mu_{0},[c,d])\}$ with domains $\{\tau\in[a,b],\tau^{\prime}\in[a_{3},b_{3}]\}$. An illustration of the decomposition is depicted in Fig. [2](https://arxiv.org/html/2510.00225v1#S4.F2).
In this work, we do not consider disjunctions or temporal structures of the form “$G(F\ldots)$.” Such STLs can be represented by introducing additional binary variables to select the disjunction branch and more time variables for each instant in the time domain of the $G$ operator.

From the reachability and invariance tasks, we further denote subgoals (reach or stay) as tasks that are either a reachability task (e.g., Subgoal 1 in Fig. [2](https://arxiv.org/html/2510.00225v1#S4.F2)) or an invariance task (e.g., Subgoal 2 in Fig. [2](https://arxiv.org/html/2510.00225v1#S4.F2)) with atomic proposition $\mu$ (we assume all the APs are for reaching certain regions). The remaining invariance tasks associated with negation of APs (e.g., $\operatorname{Inv}(\neg\mu_{0},[c,d])$) are treated as invariant constraints (avoidance).
Through this decomposition, a complex STL formula $\phi$ reduces to $N_{g}$ subgoals $\phi^{g}_{i}$ with $\operatorname{Reach}(\mu^{g}_{i},\tau_{i})$ or $\operatorname{Inv}(\mu^{g}_{i},W_{i})$, $i\in\Theta_{g}:=\{1,\cdots,N_{g}\}$ and $N_{c}$ invariant constraints $\phi^{c}_{j}$ with $\operatorname{Inv}(\neg\mu^{c}_{j},W_{j})$, $j\in\Theta_{c}:=\{1,\cdots,N_{c}\}$. Each subgoal / constraint has a starting time and an ending time $[\underline{t},\bar{t}]$ which is $[\tau,\tau]$ (or $W$). Denote all the time variables in this STL as $\mathbf{t}$. Next, we will show how this decomposition guides our state augmentation and reward shaping.

Figure: Figure 2: STL decomposition of $\phi=F_{[a,b]}(\mu_{1}\land G_{[a_{2},b_{2}]}\mu_{2}\land F_{[a_{3},b_{3}]}\mu_{3})\land G_{[c,d]}\neg\mu_{0}$.

### 4.2 Temporal grounded state augmentation and reward design

Given a concrete time variables assignment $\mathbf{t}$, the problem is now structured as reaching a sequence of subgoals sorted by their starting time with invariant constraints satisfied during execution. For brevity, we assume the subgoal indices are already sorted. We augment our state as:

$$ $s=(x,\tau,p_{prev},p,r,\chi)$ (3) $$

Here $x\in\mathbb{R}^{n}$ stands for the original state, $\tau\in\{0,1,\cdots,T\}$ represents the time index, $p\in\{0,1,\cdots,N_{g}\}$ represents the progress index and $p_{prev}$ records the previous progress, $r$ records the certificate to proceed to the next subgoal, $\chi\in\{0,1\}^{N_{c}}$ maintains the satisfaction status for the invariant constraints. For the $k$-th subgoal (or invariant constraint), denote the starting time $\underline{t}^{g}_{k}$ (or $\underline{t}^{c}_{k}$) and the ending time $\bar{t}^{g}_{k}$ (or $\bar{t}^{c}_{k}$). The augmented state transition can be written as:

$$ $\begin{cases}x^{\prime}=f(x,u),\quad\tau^{\prime}=\tau+1,\quad p_{prev}^{\prime}=p,\quad r^{\prime}=h(r,x^{\prime},\tau^{\prime},p^{\prime}),\quad p^{\prime}=p+\mathbbm{1}(r^{\prime}=2)\\ \chi^{\prime}_{k}=\chi_{k}\times\mathbbm{1}(\neg(\underline{t}^{c}_{k}\leq\tau^{\prime}\leq\bar{t}^{c}_{k}\land\neg\mu^{c}_{k}(x^{\prime})<0))\quad k=0,1,...,N_{c}\\ \end{cases}$ (4) $$

where:

$$ $h(r,x^{\prime},\tau^{\prime},p^{\prime})=\begin{cases}0,\quad\text{if }r=2\\ 1,\quad\text{if }\underline{t}^{g}_{{p^{\prime}}}\neq\bar{t}^{g}_{{p^{\prime}}}\land\tau^{\prime}=\underline{t}^{g}_{{p^{\prime}}}\land\mu^{g}_{{p^{\prime}}}(x^{\prime})\geq 0\\ 2,\quad\text{if }(r=1\lor\underline{t}^{g}_{{p^{\prime}}}=\bar{t}^{g}_{{p^{\prime}}})\land(\tau^{\prime}=\bar{t}^{g}_{{p^{\prime}}}\land\mu^{g}_{{p^{\prime}}}(x^{\prime})\geq 0)\\ r,\quad\text{otherwise}\\ \end{cases}$ (5) $$

The variable $r$ acts as a certificate (or flag) that keeps track of whether the reach-and-stay ($FG$) condition has been satisfied. It encodes the progress toward establishing that the predicate holds both at the entry time and the exit time of the required interval. To guide the agent to achieve these subgoals in a proper time window while satisfying the invariant constraints, we design the reward:

$$ $R(s)=\lambda_{1}R_{dist}+\lambda_{2}R_{progress}+\lambda_{3}R_{success}+\lambda_{4}R_{inv}$ (6) $$

where $R_{dist}=\mu^{g}_{p}(x)$ is a distance-based reward shaping to encourage the agent to reach the current subgoal (and stay at the current subgoal within the time window $[\underline{t}_{p}^{g},\bar{t}_{p}^{g}]$), $R_{progress}=\mathbbm{1}(p^{prev}\neq p)$ encourages the agent to achieve more subgoals, $R_{success}=\mathbbm{1}(p=N_{g}\land\chi=\mathbf{1})$ encourages the agent to finish all subgoals without violating any invariant constraints, and $\quad R_{inv}=\mathbbm{1}(\chi_{k}=0)$ penalizes for violating invariant constraints. The robustness score is also used at the final time step to encourage the agent to satisfy the STL. In this way, the agent is incentivized to reach all the subgoals while obeying the invariant constraints. We use Proximal Policy Optimization (PPO) (Schulman et al., 2017) to train the agent. The policy network and the critic receive the augmented state and the time variable assignment as the input, and output the action and the critic value correspondingly. At the beginning of each training epoch, we sample the time variables and collect episodes to update the network parameters. During inference, we sample time variables and use the trained critic to find the most effective assignment. The most naive way to sample these time variables will be randomly sampling from their feasible intervals, but we will present a better solution in the following section.

### 4.3 Critic-guided Bayesian Time Allocation

The key challenge in our framework is efficiently searching for time variable assignments. A naive uniform sampling strategy might waste huge effort on assignments that lead to infeasible or low-reward trajectories. To address this, we propose a Bayesian sampling strategy to find promising time assignments. We do not need to learn an extra surrogate function, as the value function learned by the PPO agent already provides a powerful heuristic. We employ a Metropolis-Hastings (MH) algorithm to sample time variables from $\exp(V_{\psi}(s_{0},\mathbf{t}))$ for initial state $s_{0}$. The MH performs a guided random walk over the discrete time variable space and prefers to stay in regions that yield high critic values. To mitigate the risk of the sampler converging to a local optima and the fact that the initial critic might not be accurate, we adopt a hybrid approach: In each epoch, we use an MH sampler to obtain a ratio $\eta_{\text{mcmc}}$ of the time variables and sample a ratio $\eta_{\text{uniform}}$ through uniform sampling. To further leverage knowledge across training epochs, we maintain a replay buffer containing the top $\eta_{\text{elite}}$ ratio of “elite” time variable assignments that yield the highest STL robustness scores. This combination creates a robust and efficient mechanism for discovering effective temporal plans. The full training procedure is detailed in Algo. [1](https://arxiv.org/html/2510.00225v1#alg1), and the ablation study for each component is shown in Sec. [5.4](https://arxiv.org/html/2510.00225v1#S5.SS4).

Figure: Algorithm 1 TGPO with Hybrid Time Variable Sampling

## 5 Experiments

### 5.1 Implementation details

Baselines. We consider the following approaches. RNN: Train RL with a recurrent neural network (RNN) to handle history and use the STL robustness score as the rewards. CEM: Cross-Entropy Method (De Boer et al., 2005) that optimizes the policy network with the STL robustness score as the fitness score. Grad: A gradient-based method (Meng & Fan, 2023) that trains the policy with a differentiable STL robustness score. $\tau$-MDP: An RL method (Aksaray et al., 2016) which augments the state space with a trajectory segment to handle history data.
F-MDP: An RL approach (Venkataraman et al., 2020) that augments the state space with flags. We denote our base algorithm as TGPO and the enhanced version with Bayesian time sampling as TGPO^*.

Figure: (a) Linear
Refer to caption: x2.png

Benchmarks. We evaluate TGPO across five environments shown in Fig. [3](https://arxiv.org/html/2510.00225v1#S5.F3) with varying dynamics and dimensionality:
(1) Linear: A 2D point-mass linear system.
(2) Unicycle: A non-holonomic 4D system for a wheeled robot.
(3) Franka Panda: A 7-DoF robot arm.
(4) Quadrotor: A 12D, full dynamic model of a quadrotor.
(5) Ant: a 29D quadruped robot for locomotion tasks. The agent starts from an initial set, and we specify the regions that the agent needs to reach, stay, or avoid using STL. For each benchmark, we designed 10 STL tasks of varying difficulty. Five of these STLs are two-layered (e.g., $F_{[0,T]}G_{[0,5]}(\text{Reach A})$), solvable by all the methods. The rest are multi-layer STLs with deeper nesting, which cannot be solved by F-MDP. Details can be found in App. [A.7](https://arxiv.org/html/2510.00225v1#A1.SS7).

Training and evaluation.
For the main comparisons, the task horizon is fixed at $T$=100 except for “Ant” ($T$=200). We trained each model with 7 random seeds to ensure statistical significance. All the methods are implemented in JAX (Bradbury et al., 2018) and trained with 512 parallel environments for 1000$\sim$4000 epochs. All experiments were conducted on Amazon Web Services (AWS) g6e.2xlarge instances. A single experiment (a specific set of environment, method, STL, and random seed) took 5 to 90 minutes, depending on the environment and method complexity.
In the testing stage, we sample $512$ initial states. For each initial state, each baseline is given 10 attempts to generate the solution, and the trajectory with the highest STL robustness score is selected. For our approach, we attempt to select the best time assignment only once, based on the critic value, and then roll out the trajectory (we avoid the use of the STL score as feedback to choose the trajectory). The Success rate is the average performance over all the initial states and the STLs. We also measured Training time, as shown in App. [A.5](https://arxiv.org/html/2510.00225v1#A1.SS5), which is the time to train each model (averaged over STLs).

### 5.2 Main results

Figure: Figure 4: Main comparison. Our method has higher task success rate compared to other baselines.
Refer to caption: x6.png

Figure: Figure 5: Main comparison for the STL success rate evaluation along the training process.
Refer to caption: x7.png

As shown in Fig. [4](https://arxiv.org/html/2510.00225v1#S5.F4) (top row), TGPO achieves the leading performance in most benchmarks, and with Bayesian time variable sampling, TGPO^* achieves the highest overall success rate across all benchmarks, indicating the strong empirical performance. Our advantage becomes clearer as the system dimension and the planning difficulty increase, especially in “Quadrotor” and “Ant”, where most of the baselines achieve less than 10% success rate, whereas TGPO^* can achieve 86.46% and 61.57% success rate, respectively. Under “Linear” system, the best baseline $\tau$-MDP (84.11%) performs competitively compared to TGPO^* (87.53%), but $\tau$-MDP’s performance drops drastically on the other benchmarks. The “Grad” method is a strong baseline on “Franka Panda”, however, its success rate decreases by a large margin on “Quadrotor” due to its complex nonlinear dynamics, and it cannot work at all on “Ant”, which is likely caused by the discrepancy between the simulator’s approximated gradients and the true non-differentiable dynamics. These findings showcase TGPO’s strong performance and great adaptation to high-dimensional and non-differentiable environments. If we look at different types of STLs (Fig. [4](https://arxiv.org/html/2510.00225v1#S5.F4), bottom row), on low-dimensional cases (“Linear” and “Unicycle”), most baselines work well under the simple STL tasks (“two-layer STLs”) but they struggle on the harder STLs (“multi-layer STLs”, note that F-MDP can only handle “two-layer STLs”). Whereas our approaches (both TGPO and TGPO^*) excel at working on these complex STLs and perform consistently well. This shows our approach’s strength in handling complex STLs. In Fig. [5](https://arxiv.org/html/2510.00225v1#S5.F5), we show the task success rate in training. Our approach can achieve a high task success rate eventually, whereas other baselines show plateauing early in the training.

### 5.3 Solving STL with Different horizon-lengths

Figure: Figure 6: Solving STL in “Linear” environment over varied task horizons. Our method performs the best and maintains high success rate in long horizons where the RL baselines performance degrades.
Refer to caption: x8.png

Beyond system complexity and task difficulty, our methods also show resilient adaptivity for long-horizon tasks. Here, we consider only the two-level STLs and we scale the task horizon to different lengths (50, 200, 300, 800 and 1000). As shown in Fig. [6](https://arxiv.org/html/2510.00225v1#S5.F6), our methods (TGPO and TGPO^*) keep a high success rate over varied time lengths, whereas for RL methods $\tau$-MDP, F-MDP and RNN, which are strong baselines for shorter horizons ($T$=50 and 100), experience a huge drop in success rate as the horizon increases. It is interesting that CEM and Grad can maintain their performance as the horizon expands 10 times, which may be attributed to their trajectory optimization formulation.

### 5.4 Ablation studies

**Table 1: Ablation studies for TGPO on the linear dynamics environment.**
| Method | Rand. | Bay. | Elite | Test(%) |
| --- | --- | --- | --- | --- |
| Ours | ✓ |  |  | 80.33 $\pm$ 8.84 |
| OursBay |  | ✓ |  | 53.79 $\pm$ 7.99 |
| OursElite |  |  | ✓ | 61.49 $\pm$ 10.02 |
| OursmixBay | ✓ | ✓ |  | 81.18 $\pm$ 9.72 |
| OursmixElite | ✓ |  | ✓ | 86.62 $\pm$ 8.67 |
| OursBayElite |  | ✓ | ✓ | 81.04 $\pm$ 11.00 |
| Ours^* | ✓ | ✓ | ✓ | 88.99 $\pm$ 9.60 |

We conduct a thorough ablation study under “Linear” (all 10 STLs) for the analysis. We first study different sampling strategies. As shown in Tbl. [1(a)](https://arxiv.org/html/2510.00225v1#S5.T1.st1), our base model with random sampling (Ours) can already achieve 80.33% success rate ($\pm$ indicates the standard deviation over 7 random seeds). However, naively using Bayesian sampling (OursBay) or Elite variable replay buffer (OursElite) will hurt the performance, likely due to the myopic exploration at the beginning of the training, which restricts the agent from seeking more promising assignments. Hence, we mix the two sources of the time variables together and witness certain improvement (OursmixBay, OursmixElite, and OursBayElite) compared to Ours. Finally, by combining all these together, Ours^* achieves the best performance.

In Tbl. [1(b)](https://arxiv.org/html/2510.00225v1#S5.T1.st2) we study how state augmentation and reward shaping foster an efficient multi-stage RL. For the reward design, we consider to just using parts of the reward terms introduced before, and the results (the first 4 rows) show that, just using STL robustness score will only result in 11.73% success rate, whereas by gradually adding invariance penalty, progress reward and the distance reward, the performance will get improved (the most improvement comes from using the distance reward term) and finally becomes 88.99% for Ours^*. Regarding the state augmentation, removing the flags in the augmented state will result in a 41.48% drop in success rate, and if further removing the time index counter, the performance will drop to 11.43%. The combined findings validate our design.

### 5.5 Visualization for interpretability and multi-modal behavior

Figure: Figure 7: Critic value visualization and simulation for the ant environment under STL $F_{[0,160]}(A_{1})\land F_{[0,160]}(A_{2})\land G_{[0,200]}\neg B$. From the two feasible regions on the critic heatmap, we can see that the corresponding conditioned policy generates two behaviors to fulfill the task specification.
Refer to caption: x9.png

TGPO can generate diverse behaviors to fulfill the STL specifications, which can also be reflected from the critic values. We consider an example under the Ant environment for the STL task $F_{[0,160]}(A_{1})\land F_{[0,160]}(A_{2})\land G_{[0,200]}\neg B$. The ant starts from the lower left, and there is an obstacle in the middle of the scene. The time variables here correspond to “Reach $A_{1}$” (the cyan region in the scene) and “Reach $A_{2}$” (green). After the training, we plot the critic value heatmap across different time variable assignments for the initial state. As shown in Fig. [7](https://arxiv.org/html/2510.00225v1#S5.F7), the lower-left L-shape region is in low critic value as it is dynamically infeasible to reach the first subgoal in a short time (0$\leq\tau\leq$40). The diagonal line region also receives low critic value, because the two subgoal regions cannot be visited in such a short time. The diagonal line splits the promising time variable regions (yellow) into two parts, from which we can generate two different ways to fulfill the STL task (as shown from the time-elapsed simulation plot on the right). This shows that we can leverage the time variables as the condition to generate multi-modal solutions to solve the STL problem.

### 5.6 Limitations

While our method achieves strong empirical performance, it lacks formal guarantees on convergence to a global optimum. TGPO is effective on STLs with conjunctions and temporal operators, but it might not efficiently handle STLs with disjunctions or infinite-horizon task requirements like “Always-Eventually (G(F))”. In our paper, we have tested TGPO with 5 time variables; its scalability towards more complex STLs remains an open question. We aim to address these in future work.

## 6 Conclusion

In this paper, we introduce Temporal Grounded Policy Optimization (TGPO), a novel reinforcement learning framework for solving long-horizon Signal Temporal Logic tasks. By using STL decomposition, time variable sampling, state augmentation and reward design, TGPO can effectively handle general and complex STL tasks. Our experiments demonstrate that TGPO significantly outperforms existing baselines across various robotic environments and STL formulas. Future work will focus on extending TGPO to handle a broader class of STL formulas and improving its scalability.

## References

- Aksaray et al. (2016)
Derya Aksaray, Austin Jones, Zhaodan Kong, Mac Schwager, and Calin Belta.
Q-learning for robust satisfaction of signal temporal logic specifications.
In *2016 IEEE 55th Conference on Decision and Control (CDC)*, pp. 6565–6570. IEEE, 2016.
- Bacchus & Kabanza (2000)
Fahiem Bacchus and Froduald Kabanza.
Using temporal logics to express search control knowledge for planning.
*Artificial intelligence*, 116(1-2):123–191, 2000.
- Balakrishnan & Deshmukh (2019)
Anand Balakrishnan and Jyotirmoy V Deshmukh.
Structured reward shaping using signal temporal logic specifications.
In *2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, pp. 3481–3486. IEEE, 2019.
- Bradbury et al. (2018)
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, et al.
Jax: Composable transformations of python+ numpy programs, version 0.3. 13, 2018, 2018.
- Camacho et al. (2017)
Alberto Camacho, Oscar Chen, Scott Sanner, and Sheila A McIlraith.
Decision-making with non-markovian rewards: From ltl to automata-based reward shaping.
In *Proceedings of the Multi-disciplinary Conference on Reinforcement Learning and Decision Making (RLDM)*, pp. 279–283, 2017.
- Chib & Greenberg (1995)
Siddhartha Chib and Edward Greenberg.
Understanding the metropolis-hastings algorithm.
*The american statistician*, 49(4):327–335, 1995.
- De Boer et al. (2005)
Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Y Rubinstein.
A tutorial on the cross-entropy method.
*Annals of operations research*, 134(1):19–67, 2005.
- Donzé (2013)
Alexandre Donzé.
On signal temporal logic.
In *Runtime Verification: 4th International Conference, RV 2013, Rennes, France, September 24-27, 2013. Proceedings 4*, pp. 382–383. Springer, 2013.
- Donzé & Maler (2010)
Alexandre Donzé and Oded Maler.
Robust satisfaction of temporal logic over real-valued signals.
*Formal Modeling and Analysis of Timed Systems*, pp.  92, 2010.
- Donzé et al. (2013)
Alexandre Donzé, Thomas Ferrere, and Oded Maler.
Efficient robust monitoring for stl.
In *Computer Aided Verification: 25th International Conference, CAV 2013*, pp. 264–279. Springer, 2013.
- Finucane et al. (2010)
Cameron Finucane, Gangyuan Jing, and Hadas Kress-Gazit.
Ltlmop: Experimenting with language, temporal logic and robot control.
In *2010 IEEE/RSJ International Conference on Intelligent Robots and Systems*, pp. 1988–1993. IEEE, 2010.
- Freeman et al. (2021)
C Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem.
Brax–a differentiable physics engine for large scale rigid body simulation.
*arXiv preprint arXiv:2106.13281*, 2021.
- Hasanbeig et al. (2018)
Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening.
Logically-constrained reinforcement learning.
*arXiv preprint arXiv:1801.08099*, 2018.
- Hasanbeig et al. (2020)
Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate.
Deep reinforcement learning with temporal logics.
In *Formal Modeling and Analysis of Timed Systems: 18th International Conference, FORMATS 2020, Vienna, Austria, September 1–3, 2020, Proceedings 18*, pp. 1–22. Springer, 2020.
- He et al. (2024)
Yiting He, Peiran Liu, and Yiding Ji.
Scalable signal temporal logic guided reinforcement learning via value function space optimization.
*arXiv preprint arXiv:2408.01923*, 2024.
- Icarte et al. (2018)
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila McIlraith.
Using reward machines for high-level task specification and decomposition in reinforcement learning.
In *International Conference on Machine Learning*, pp. 2107–2116. PMLR, 2018.
- Ikemoto & Ushio (2022)
Junya Ikemoto and Toshimitsu Ushio.
Deep reinforcement learning under signal temporal logic constraints using lagrangian relaxation.
*IEEE Access*, 10:114814–114828, 2022.
- Jothimurugan et al. (2019)
Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani.
A composable specification language for reinforcement learning tasks.
*Advances in Neural Information Processing Systems*, 32, 2019.
- Kapoor et al. (2020)
Parv Kapoor, Anand Balakrishnan, and Jyotirmoy V Deshmukh.
Model-based reinforcement learning from signal temporal logic specifications.
*arXiv preprint arXiv:2011.04950*, 2020.
- Kapoor et al. (2024)
Parv Kapoor, Eunsuk Kang, and Rômulo Meira-Góes.
Safe planning through incremental decomposition of signal temporal logic specifications.
In *NASA Formal Methods Symposium*, pp. 377–396. Springer, 2024.
- Karlsson et al. (2020)
Jesper Karlsson, Fernando S Barbosa, and Jana Tumova.
Sampling-based motion planning with temporal logic missions and spatial preferences.
*IFAC-PapersOnLine*, 53(2):15537–15543, 2020.
- Kurtz & Lin (2022)
Vincent Kurtz and Hai Lin.
Mixed-integer programming for signal temporal logic with fewer binary variables.
*IEEE Control Systems Letters*, 6:2635–2640, 2022.
- Leung & Pavone (2022)
Karen Leung and Marco Pavone.
Semi-supervised trajectory-feedback controller synthesis for signal temporal logic specifications.
In *2022 American Control Conference (ACC)*, pp. 178–185. IEEE, 2022.
- Leung et al. (2023)
Karen Leung, Nikos Aréchiga, and Marco Pavone.
Backpropagation through signal temporal logic specifications: Infusing logical structure into gradient-based methods.
*The International Journal of Robotics Research*, 42(6):356–370, 2023.
- Li et al. (2017)
Xiao Li, Cristian-Ioan Vasile, and Calin Belta.
Reinforcement learning with temporal logic rewards.
In *2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, pp. 3834–3839. IEEE, 2017.
- Liao (2020)
Hsuan-Cheng Liao.
A survey of reinforcement learning with temporal logic rewards.
*preprint*, 2020.
- Linard et al. (2023)
Alexis Linard, Ilaria Torre, Ermanno Bartoli, Alex Sleat, Iolanda Leite, and Jana Tumova.
Real-time rrt* with signal temporal logic preferences.
In *2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, pp. 8621–8627. IEEE, 2023.
- Liu et al. (2025)
Ruijia Liu, Ancheng Hou, Xiao Yu, and Xiang Yin.
Zero-shot trajectory planning for signal temporal logic tasks.
*arXiv preprint arXiv:2501.13457*, 2025.
- Liu et al. (2021)
Wenliang Liu, Noushin Mehdipour, and Calin Belta.
Recurrent neural network controllers for signal temporal logic specifications subject to safety constraints.
*IEEE Control Systems Letters*, 6:91–96, 2021.
- Liu et al. (2023)
Wenliang Liu, Wei Xiao, and Calin Belta.
Learning robust and correct controllers from signal temporal logic specifications using barriernet.
In *2023 62nd IEEE Conference on Decision and Control (CDC)*, pp. 7049–7054. IEEE, 2023.
- Maler & Nickovic (2004)
Oded Maler and Dejan Nickovic.
Monitoring temporal properties of continuous signals.
*Formal Techniques, ModellingandAnalysis of Timed and Fault-Tolerant Systems*, pp. 152, 2004.
- Meng & Fan (2023)
Yue Meng and Chuchu Fan.
Signal temporal logic neural predictive control.
*IEEE Robotics and Automation Letters*, 8(11):7719–7726, 2023.
- Meng & Fan (2024)
Yue Meng and Chuchu Fan.
Diverse controllable diffusion policy with signal temporal logic.
*IEEE Robotics and Automation Letters*, 2024.
- Meng & Fan (2025)
Yue Meng and Chuchu Fan.
Telograf: Temporal logic planning via graph-encoded flow matching.
In *Forty-second International Conference on Machine Learning*, 2025.
- Pant et al. (2017)
Yash Vardhan Pant, Houssam Abbas, and Rahul Mangharam.
Smooth operator: Control using the smooth robustness of temporal logic.
In *2017 IEEE Conference on Control Technology and Applications (CCTA)*, pp. 1235–1240. IEEE, 2017.
- Puranic et al. (2021)
Aniruddh Puranic, Jyotirmoy Deshmukh, and Stefanos Nikolaidis.
Learning from demonstrations using signal temporal logic.
In *Conference on Robot Learning*, pp. 2228–2242. PMLR, 2021.
- Sadigh et al. (2014)
Dorsa Sadigh, Eric S Kim, Samuel Coogan, S Shankar Sastry, and Sanjit A Seshia.
A learning based approach to control synthesis of markov decision processes for linear temporal logic specifications.
In *53rd IEEE Conference on Decision and Control*, pp. 1091–1096. IEEE, 2014.
- Salimans et al. (2017)
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever.
Evolution strategies as a scalable alternative to reinforcement learning.
*arXiv preprint arXiv:1703.03864*, 2017.
- Schulman et al. (2017)
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
*arXiv preprint arXiv:1707.06347*, 2017.
- Sewlia et al. (2023)
Mayank Sewlia, Christos K Verginis, and Dimos V Dimarogonas.
Cooperative sampling-based motion planning under signal temporal logic specifications.
In *2023 American Control Conference (ACC)*, pp. 2697–2702. IEEE, 2023.
- Sickert et al. (2016)
Salomon Sickert, Javier Esparza, Stefan Jaax, and Jan Křetínskỳ.
Limit-deterministic büchi automata for linear temporal logic.
In *International Conference on Computer Aided Verification*, pp. 312–332. Springer, 2016.
- Sun et al. (2022)
Dawei Sun, Jingkai Chen, Sayan Mitra, and Chuchu Fan.
Multi-agent motion planning from signal temporal logic specifications.
*IEEE Robotics and Automation Letters*, 7(2):3451–3458, 2022.
- Tayebi & McGilvray (2006)
Abdelhamid Tayebi and Stephen McGilvray.
Attitude stabilization of a vtol quadrotor aircraft.
*IEEE Transactions on control systems technology*, 14(3):562–571, 2006.
- Vaezipoor et al. (2021)
Pashootan Vaezipoor, Andrew C Li, Rodrigo A Toro Icarte, and Sheila A Mcilraith.
Ltl2action: Generalizing ltl instructions for multi-task rl.
In *International Conference on Machine Learning*, pp. 10497–10508. PMLR, 2021.
- Vasile et al. (2017)
Cristian-Ioan Vasile, Vasumathi Raman, and Sertac Karaman.
Sampling-based synthesis of maximally-satisfying controllers for temporal logic specifications.
In *2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, pp. 3840–3847. IEEE, 2017.
- Venkataraman et al. (2020)
Harish Venkataraman, Derya Aksaray, and Peter Seiler.
Tractable reinforcement learning of signal temporal logic objectives.
In *Learning for Dynamics and Control*, pp. 308–317. PMLR, 2020.
- Wang et al. (2024)
Siqi Wang, Xunyuan Yin, Shaoyuan Li, and Xiang Yin.
Tractable reinforcement learning for signal temporal logic tasks with counterfactual experience replay.
*IEEE Control Systems Letters*, 2024.

## Appendix A Appendix

### A.1 Algorithm hyperparameters

All the main hyperparameters used during training are shown in Table [2](https://arxiv.org/html/2510.00225v1#A1.T2).

**Table 2: Hyperparameters assignments used for training TGPO^*.**
| Hyperparameter | Linear; Unicycle; FrankaPanda; Quadrotor; Ant |
| --- | --- |
| Network hidden units | (512, 512, 512) |
| Optimizer | Adam |
| Learning rate | $3\times 10^{-4}$ |
| Weight decay | $0.1$ |
| Grad norm clip | $0.5$ |
| Random seeds | 1007,1008,1009,1010,1011,1012,1013 |
| Batch size | 512 |
| Epochs | 1000 (L, U); 2000 (F, A); 4000(Q) |
| Time steps $T$ | 100 (L, U, F, Q); 200 (A) |
| Time duration $\Delta t$ | 0.2 (L, U); 0.05 (F, A); 0.1 (Q) |
| Distance reward $\lambda_{1}$ | 0.5 |
| Progress reward $\lambda_{2}$ | 20.0 |
| Success reward $\lambda_{3}$ | 20.0 |
| Invariance penalty $\lambda_{4}$ | -3.0 (L, F, Q); -3.5 (U); -1.5 (A) |
| Number of MCMC steps $N_{MCMC}$ | 500 |
| Number of warmup steps $N_{warmup}$ | 200 |
| Number of MCMC chains $M_{MCMC}$ | 512 |
| Ratio of Randomly-sampled time variables $\eta_{mcmc}$ | 0.5 |
| Ratio of MCMC-sampled time variables $\eta_{uniform}$ | 0.4 |
| Ratio of Elite time variables $\eta_{elite}$ | 0.1 |
| Elite buffer size $|\mathcal{B}|$ | 512 |

### A.2 Simulation environment details

In this paper, we conduct experiments on five simulation environments (Linear, Unicycle, Franka Panda, Quadrotor, and Ant). The first four environments were implemented in plain JAX code by writing out the system dynamics, whereas the last one was adopted from the Mujoco JAX implementation. Detailed implementations are listed as follows.

#### A.2.1 Linear

We use a single-integrator dynamics model. The 2D state $(x,y)^{T}$ represents the 2D coordinates on a xy-plane, and the 2D control input $(v,w)^{T}$ reflects the velocities in these two directions. The system dynamics is described as:

$$ $\begin{cases}x_{t+1}=x_{t}+v_{t}\Delta t\\ y_{t+1}=y_{t}+w_{t}\Delta t\\ \end{cases}$ (7) $$

We set the time step duration $\Delta t=0.2s$.

#### A.2.2 Unicycle

We use a car-like dynamics model. The 4D state $(x,y,\theta,v)^{T}$ represents the 2D coordinates on the xy-plane, the heading angle of the robot and the velocity of the robot, respectively. The 2D input $(\omega,a)^{T}$ represents the angular velocity and the acceleration. The system dynamics can be described as:

$$ $\begin{cases}x_{t+1}=x_{t}+v_{t}\cos(\theta_{t})\Delta t\\ y_{t+1}=y_{t}+v_{t}\sin(\theta_{t})\Delta t\\ \theta_{t+1}=\theta_{t}+\omega_{t}\Delta t\\ v_{t+1}=v_{t}+a_{t}\Delta t\\ \end{cases}$ (8) $$

We set the time step duration $\Delta t=0.2s$. The control actuation is limited at $[-1rad/s,+1rad/s]\times[-4m/s^{2},+4m/s^{2}]$. The scene layout is $[-5m,+5m]\times[-5m,+5m]$ on the xy-plane.

#### A.2.3 Franka Panda

We use a 7 DoF Franka Panda robot arm model to conduct the simulation. The 7D state $(\theta_{1},\theta_{2},...,\theta_{7})^{T}$ represents the angle for all the joints where $\theta_{7}$ is for the end-effector joint. The 7D control input $(\omega_{1},\omega_{2},...,\omega_{7})^{T}$ represents the angular velocity for all the joints. The dynamics follows a simple single-integrator case: $\theta_{i,t+1}=\theta_{i,t}+\omega_{i,t}\Delta t,\text{ for }i=1,2,...,7$. We set the time step duration $\Delta t=0.05s$.

#### A.2.4 Quadrotor

We use a full quadrotor dynamics model (Tayebi & McGilvray, 2006) to conduct the simulation. The 12D state $(x,y,z,v_{x},v_{y},v_{z},\phi,\theta,\psi,\omega_{x},\omega_{y},\omega_{z})^{T}$ represents the 3D coordinate $\mathbf{p}=(x,y,z)^{T}$, the velocity vector $\mathbf{v}=(v_{x},v_{y},v_{z})^{T}$, the orientation vector $\bm{\Theta}=(\phi,\theta,\psi)^{T}$, and the angular velocity $\bm{\omega}=(\omega_{x},\omega_{y},\omega_{z})^{T}$, respectively. The 4D control input $(f_{1},f_{2},f_{3},f_{4})^{T}$ represents the lifting force from the four motors. The full dynamics are:

$$ $\begin{cases}\mathbf{p}_{t+1}=\mathbf{p}_{t}+\mathbf{v}_{t}\Delta t\\ \mathbf{v}_{t+1}=\mathbf{v}_{t}+(g\mathbf{e}_{3}-\frac{T}{m}R_{z}(\psi)R_{y}(\theta)R_{x}(\phi)\mathbf{e}_{3})\Delta t\\ \bm{\Theta}_{t+1}=\bm{\Theta}_{t}+\bm{\omega}_{t}\Delta t\\ \bm{\omega}_{t+1}=\bm{\omega}_{t}+I^{-1}(\bm{\tau}-\bm{\omega}_{t}\times(I\bm{\omega}_{t}))\Delta t\end{cases}$ (9) $$

with the rotation matrices $R_{x}(\phi)=\begin{bmatrix}1&0&0\\
0&\cos(\phi)&-\sin(\phi)\\
0&\sin(\phi)&\cos(\phi)\end{bmatrix}$,
$R_{y}(\theta)=\begin{bmatrix}\cos(\theta)&0&\sin(\theta)\\
0&1&0\\
-\sin(\theta)&0&\cos(\theta)\end{bmatrix}$,
and $R_{z}(\psi)=\begin{bmatrix}\cos(\psi)&-\sin(\psi)&0\\
\sin(\psi)&\cos(\psi)&0\\
0&0&1\\
\end{bmatrix}$ and $T$ and $\bm{\tau}$ are the total thrust and the torques derived from the motor input $u$ with the Coriolis effect considered to the angular velocity vector. We set the time step duration $\Delta t=0.10s$, adapt the gravity coefficient $g=9.81m/s^{2}$ with the corresponding gravity vector $\mathbf{e}_{3}=(0,0,1)^{T}$, set the total mass of the quadrotor $m=0.2kg$ and set the diagonal line of the quadrotor inertia matrix $I$ as $(0.01kg\cdot m^{2},0.01kg\cdot m^{2},0.02kg\cdot m^{2})^{T}$.

#### A.2.5 Ant

In this case, the agent is a 8-DoF quadruped robot with the complex dynamics implemented in Brax (Freeman et al., 2021). The observation space is 29-dimension (3-dimension for xyz coordinates, 4-dimension for the torso orientation (in Quaternion representation), 3-dimension velocity vector and 3-dimension angular velocity for the torso, 8-dimension for the joints’ angles and another 8-dimension for the joints’ angular velocities). The original control input is 8-dimension for the torques applied to each of the 8 joints. To ease the RL training, we first train a goal-reaching policy, enabling the ant to learn and move to a specified target location. Then, for the baselines and our methods, the problem becomes planning the waypoints so that the ant can satisfy the STL tasks specified.

### A.3 Baseline implementation details

#### A.3.1 CEM

We use the Cross Entropy Method baseline mentioned in (Meng & Fan, 2023), which belongs to the evolutionary search algorithm mentioned in (Salimans et al., 2017). We denote the initial neural network policy parameters as $\theta^{(0)}$. At $j$-th iteration, we draw $N$ samples $\theta_{1},...\theta_{N}$ from $\mathcal{N}(\theta^{(j)},{\sigma^{(j)}}^{2})$ where $\sigma^{(j)}$ is the preset standard deviation, then we rollout the trajectories and compute their robustness score. We pick the top-$K$ candidates parameters $\theta_{E_{1}},...\theta_{E_{k}}$. Then we update the estimate for the neural network parameters $\theta^{(j+1)}=\frac{1}{k}\sum\limits_{i=1}^{k}\theta_{E_{i}}$ and $\sigma^{(j+1)}=\sqrt{\frac{1}{k-1}\sum\limits_{i=1}^{k}(\theta_{E_{i}}-\theta^{(j+1)})^{2}}$. We repeat this process for $L$ iterations to get the final parameters. We set the size for the elite pool to be $K=32$ and set the population sample size to be $N=512$. The number of iteration steps $L$ is the same as our method ($L=1000$ for “Linear” and “Unicycle”, $L=2000$ for “Franka Panda” and “Ant”, and $L=4000$ for “Quadrotor”.)

#### A.3.2 τ \tau -MDP

$\tau$-MDP is an RL method introduced in (Aksaray et al., 2016) to solve STL tasks under the discrete state space. The original method appends history to the state space, and uses Q-learning to solve short-horizon tasks with 2-layer STL specifications. Here, we extend it to handle general STL formulas by augmenting the entire trajectory into the state space with STL robustness score as the terminal reward to guide the agent to satisfy STL tasks. We also changed the RL backbone from Q-learning to PPO for better scalability to longer-horizon tasks (The original Q-learning tabular formulation will not work on continuous space for $T=100$).

#### A.3.3 F F -MDP

$F$-MDP is an improved RL method introduced in (Venkataraman et al., 2020) to solve STL tasks under the discrete state space more efficiently. This approach considers the 2-layer STL specifications, and introduces a flag for each of the subformulas in the STL. They defined the state transition rules and reward mechanism for “F” and “G”-based subformulas based on these flags and show that the Q-learning under this augmentation can learn more efficiently than the Q-learning under $\tau$-MDP (Aksaray et al., 2016). We re-implemented $F$-MDP in PPO for our comparison.

#### A.3.4 RNN

In this case, similar to (Liu et al., 2021), we use an RNN to encode the history data and then use the robustness score as the final reward to guide the agent to satisfy the tasks. The issue of this implementation is that it is much more time-consuming compared to the other baselines.

#### A.3.5 Grad

In this case, similar to (Leung & Pavone, 2022) and (Meng & Fan, 2023), we use a neural network policy to roll out the trajectory (in a deterministic manner, rather than sampling from the learned Gaussian distribution). At each time step, the network receives the state (and the time index) and generates the action, which is then sent to the environment to derive the next state. We repeat this process $T$ times to roll out the full trajectory, which preserves the gradient through the differentiable system dynamics. We use the approximated robustness score mentioned in (Pant et al., 2017) to ensure the score is differentiable. We then conduct backpropagation-through-time (BPTT) to update the neural network parameters.

### A.4 Temporal sampling algorithm details

The Metropolis-Hastings algorithm (Chib & Greenberg, 1995) is a Markov Chain Monte Carlo (MCMC) method for sampling from a probability distribution, commonly used when directly sampling from the distribution is hard. In our approach TGPO^*, we use a discrete version of the M-H algorithm to sample time variables $\mathbf{t}$ that are likely to yield high critic values $V_{\psi}(s_{0},\mathbf{t})$, where $s_{0}$ is the initial state. We use $\exp(V_{\psi}(s_{0},\mathbf{t}))$ as a proxy for the unnormalized probability of the promising temporal variables. The algorithm proceeds by starting with an initial set of temporal variables $\mathbf{t}_{0}$ and iteratively proposing to move on grids to a new set $\mathbf{t}^{\prime}$ based on a proposal distribution $g(\mathbf{t}^{\prime}|\mathbf{t})$. The move is then accepted or rejected based on the acceptance ratio $\alpha$, which compares the critic value exponentials of the new and the current variables. The process is detailed in Algorithm. [2](https://arxiv.org/html/2510.00225v1#alg2).

Figure: Algorithm 2 Metropolis-Hastings for time variable sampling (with multiple chains and warm-up)

In our approach, we set $N_{mcmc}=500$, $N_{warmup}=200$, $M_{chain}=512$ and pick the time variable from each $S_{i}$ with the highest critic value to form the time variable set $\mathbf{T}_{mcmc}$ used in Alg. [1](https://arxiv.org/html/2510.00225v1#alg1). For the proposal distribution $g(\mathbf{t}^{\prime}|\mathbf{t})$, we use a uniform distribution over the local neighborhood of the current temporal variables $\mathbf{t}$: we first uniformly sample an index $j$ from the dimensions of $\mathbf{t}$ and then uniformly sample a move direction $\Delta\in\{-1,+1\}$. The proposed new set of variables $\mathbf{t}^{\prime}$ is generated by applying this change to the selected index but also ensure that the new value $\mathbf{t}^{\prime}$ is within the valid range (otherwise we keep $\mathbf{t}$ unchanged).

### A.5 Training time comparison

Figure: Figure 8: Comparison for training time. For each method under each environment, the result is averaged over 10 STLs and 7 random seeds. TGPO’s training time is on par with leading baselines.
Refer to caption: x10.png

As shown in Fig. [8](https://arxiv.org/html/2510.00225v1#A1.F8), TGPO and TGPO^* have a similar runtime compared to $\tau$-MDP, $F$-MDP and Grad baselines, whereas the CEM baseline is normally 20.8%$\sim$35.8% higher than TGPO^*. The most time-consuming baseline is RNN, where TGPO^* is 1.96X$\sim$6.11X faster in training speed. This shows that our approach is as scalable as other top RL baselines in training time, but our method can achieve higher task success rate.

### A.6 Correlation between the Critic and the STL robustness score

Figure: (a) STL-01
Refer to caption: x11.png

Figure: (a) STL-01
Refer to caption: x21.png

To validate that our learned critic in TGPO can really reflect the “promising” time variables that lead to STL satisfaction, in the “Linear” environment, for the TGPO algorithm, we randomly sample 4096 points from the pretrained critic and rollout the corresponding trajectories to generate the STL robustness score. We plot the (critic value, STL score) scatter plot, together with the cumulative STL success rate curve for samples with a critic value greater than x. As shown in Fig. [9](https://arxiv.org/html/2510.00225v1#A1.F9) (for seed=1007) and Fig. [10](https://arxiv.org/html/2510.00225v1#A1.F10) (for seed=1008) from the blue scatter plots, whenever the critic value (left) is higher, the STL score is more likely to be higher, and hence more likely to satisfy STL. If we look at the orange curve, as the Critic value x increases, in most cases the probability for the corresponding traces satisfying the STL score is monotonously increasing or plateau at 100%, which indicates that our critic is learned correctly (note that if the critic is not learned well, it could learn for some time variables that bring in high critic value but result in low STL scores, like STL-09 in Fig. [10](https://arxiv.org/html/2510.00225v1#A1.F10)) and can be used to find “promising” time variable assignments.

### A.7 STL Task details

Under each simulation environment, we make 10 STL formulas in two different categories (“two-level” and “multi-level”). Here we only consider predicates related with “Reach”, “Stay”, “Avoid” certain objects in the scene. They are listed as follows.

#### A.7.1 STLs in “Linear” environment

Figure: (a) STL-01
Refer to caption: x31.png

STL-01 (Two-layer):  $F_{[5:7]}(F_{[50:85]}(A)\land G_{[0:90]}(\neg B_{5})\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

STL-02 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land G_{[60:80]}(C)\land G_{[0:90]}(\neg B_{5})\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

STL-03 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land F_{[40:60]}(C)\land G_{[70:80]}(D)\land G_{[0:90]}(\neg B_{5})\land G_{[0:90]}(\neg B_{0})\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

STL-04 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land F_{[40:50]}(C)\land F_{[70:80]}(F)\land G_{[50:60]}(D)\land G_{[0:90]}(\neg B)\land G_{[0:90]}(\neg E)\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

STL-05 (Two-layer):  $F_{[5:10]}(F_{[0:30]}(A)\land F_{[30:50]}(C)\land F_{[70:80]}(F)\land F_{[75:88]}(H)\land G_{[50:60]}(D)\land G_{[0:90]}(\neg B)\land G_{[0:90]}(\neg E)\land G_{[0:90]}(\neg G)\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

Figure: (a) STL-06
Refer to caption: x36.png

STL-06 (Multi-layer):  $F_{[10:90]}(A)\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})$

STL-07 (Multi-layer):  $F_{[0:90]}(A_{1})\land F_{[40:80]}(A_{2})\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})$

STL-08 (Multi-layer):  $F_{[0:90]}(A_{1})\land F_{[40:80]}(A_{2}\land F_{[10:20]}(G_{[0:10]}(A_{3})))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})$

STL-09 (Multi-layer):  $F_{[5:20]}(A_{1}\land F_{[10:20]}(G_{[0:5]}(A_{2})\land F_{[10:30]}(G_{[0:5]}(A_{3}))\land F_{[10:30]}(G_{[0:10]}(A_{4}))))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})\land G_{[0:100]}(\neg B_{6})\land G_{[0:100]}(\neg B_{7})\land G_{[0:100]}(\neg B_{8})\land G_{[0:100]}(\neg B_{9})$

STL-10 (Multi-layer):  $(\neg D_{1})U_{[0:100]}(K_{1})\land(\neg D_{2})U_{[0:100]}(K_{2})\land(\neg D_{3})U_{[0:100]}(K_{3})\land F_{[80:90]}(G_{[0:5]}(G))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})$

#### A.7.2 STLs in “Unicycle” environment

Figure: (a) STL-01
Refer to caption: x41.png

STL-01 (Two-layer):  $F_{[5:7]}(F_{[50:85]}(A)\land G_{[0:90]}(\neg B_{5})\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

STL-02 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land G_{[60:80]}(C)\land G_{[0:90]}(\neg B_{5})\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

STL-03 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land F_{[40:60]}(C)\land G_{[70:80]}(D)\land G_{[0:90]}(\neg B_{5})\land G_{[0:90]}(\neg B_{0})\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

STL-04 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land F_{[40:50]}(C)\land F_{[70:80]}(F)\land G_{[50:60]}(D)\land G_{[0:90]}(\neg B)\land G_{[0:90]}(\neg E)\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

STL-05 (Two-layer):  $F_{[5:10]}(F_{[0:30]}(A)\land F_{[30:50]}(C)\land F_{[70:80]}(F)\land F_{[75:88]}(H)\land G_{[50:60]}(D)\land G_{[0:90]}(\neg B)\land G_{[0:90]}(\neg E)\land G_{[0:90]}(\neg G)\land G_{[0:90]}(\neg B_{1})\land G_{[0:90]}(\neg B_{2})\land G_{[0:90]}(\neg B_{3})\land G_{[0:90]}(\neg B_{4}))$

Figure: (a) STL-06
Refer to caption: x46.png

STL-06 (Multi-layer):  $F_{[10:90]}(A)\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})$

STL-07 (Multi-layer):  $F_{[0:90]}(A_{1})\land F_{[40:80]}(A_{2})\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})$

STL-08 (Multi-layer):  $F_{[0:90]}(A_{1})\land F_{[40:80]}(A_{2}\land F_{[10:20]}(G_{[0:10]}(A_{3})))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})$

STL-09 (Multi-layer):  $F_{[5:20]}(A_{1}\land F_{[10:20]}(G_{[0:5]}(A_{2})\land F_{[10:30]}(G_{[0:5]}(A_{3}))\land F_{[10:30]}(G_{[0:10]}(A_{4}))))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})\land G_{[0:100]}(\neg B_{6})\land G_{[0:100]}(\neg B_{7})\land G_{[0:100]}(\neg B_{8})\land G_{[0:100]}(\neg B_{9})$

STL-10 (Multi-layer):  $(\neg D_{1})U_{[0:100]}(K_{1})\land(\neg D_{2})U_{[0:100]}(K_{2})\land(\neg D_{3})U_{[0:100]}(K_{3})\land F_{[80:90]}(G_{[0:5]}(G))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg B_{5})$

#### A.7.3 STLs in “Franka Panda” environment

Figure: Figure 15: Scene for Franka Panda: STL task 01
Refer to caption: x51.png

STL-01 (Two-layer):  $F_{[5:7]}(F_{[50:85]}(A)\land G_{[0:90]}(\neg B_{5})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 16: Scene for Franka Panda: STL task 02
Refer to caption: x52.png

STL-02 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land G_{[60:80]}(C)\land G_{[0:90]}(\neg B_{5})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 17: Scene for Franka Panda: STL task 03
Refer to caption: x53.png

STL-03 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land F_{[40:60]}(C)\land G_{[70:80]}(D)\land G_{[0:90]}(\neg B_{5})\land G_{[0:90]}(\neg B_{0})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 18: Scene for Franka Panda: STL task 04
Refer to caption: x54.png

STL-04 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land F_{[40:50]}(C)\land F_{[70:80]}(F)\land G_{[50:60]}(D)\land G_{[0:90]}(\neg B)\land G_{[0:90]}(\neg E)\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 19: Scene for Franka Panda: STL task 05
Refer to caption: x55.png

STL-05 (Two-layer):  $F_{[5:10]}(F_{[0:30]}(A)\land F_{[30:50]}(C)\land F_{[70:80]}(F)\land F_{[75:88]}(H)\land G_{[50:60]}(D)\land G_{[0:90]}(\neg B)\land G_{[0:90]}(\neg E)\land G_{[0:90]}(\neg G)\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 20: Scene for Franka Panda: STL task 06
Refer to caption: x56.png

STL-06 (Multi-layer):  $F_{[10:90]}(A)\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

Figure: Figure 21: Scene for Franka Panda: STL task 07
Refer to caption: x57.png

STL-07 (Multi-layer):  $F_{[0:90]}(A_{1})\land F_{[40:80]}(A_{2})\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

Figure: Figure 22: Scene for Franka Panda: STL task 08
Refer to caption: x58.png

STL-08 (Multi-layer):  $F_{[0:90]}(A_{1})\land F_{[40:60]}(A_{2}\land F_{[15:30]}(G_{[0:5]}(A_{3})))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

Figure: Figure 23: Scene for Franka Panda: STL task 09
Refer to caption: x59.png

STL-09 (Multi-layer):  $F_{[25:30]}(A_{1}\land F_{[20:28]}(G_{[0:5]}(A_{2})\land F_{[10:30]}(G_{[0:5]}(A_{3}))\land F_{[10:30]}(G_{[0:10]}(A_{4}))))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{6})\land G_{[0:100]}(\neg B_{7})\land G_{[0:100]}(\neg B_{8})\land G_{[0:100]}(\neg B_{9})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

Figure: Figure 24: Scene for Franka Panda: STL task 10
Refer to caption: x60.png

STL-10 (Multi-layer):  $(\neg D_{1})U_{[0:100]}(K_{1})\land(\neg D_{2})U_{[0:100]}(K_{2})\land(\neg D_{3})U_{[0:100]}(K_{3})\land F_{[80:90]}(G_{[0:5]}(G))\land G_{[0:100]}(\neg B_{5})\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{2})\land G_{[0:100]}(\neg B_{3})\land G_{[0:100]}(\neg B_{4})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

#### A.7.4 STLs in “Quadrotor” environment

Figure: Figure 25: Scene for Quadrotor: STL task 01
Refer to caption: x61.png

STL-01 (Two-layer):  $F_{[5:7]}(F_{[50:85]}(A)\land G_{[0:90]}(\neg B_{5})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 26: Scene for Quadrotor: STL task 02
Refer to caption: x62.png

STL-02 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land G_{[60:80]}(C)\land G_{[0:90]}(\neg B_{5})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 27: Scene for Quadrotor: STL task 03
Refer to caption: x63.png

STL-03 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land F_{[40:60]}(C)\land G_{[70:80]}(D)\land G_{[0:90]}(\neg B_{5})\land G_{[0:90]}(\neg B_{0})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 28: Scene for Quadrotor: STL task 04
Refer to caption: x64.png

STL-04 (Two-layer):  $F_{[5:10]}(F_{[0:50]}(A)\land F_{[40:50]}(C)\land F_{[70:80]}(F)\land G_{[50:60]}(D)\land G_{[0:90]}(\neg B)\land G_{[0:90]}(\neg E)\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 29: Scene for Quadrotor: STL task 05
Refer to caption: x65.png

STL-05 (Two-layer):  $F_{[5:10]}(F_{[0:30]}(A)\land F_{[30:50]}(C)\land F_{[70:80]}(F)\land F_{[75:88]}(H)\land G_{[50:60]}(D)\land G_{[0:90]}(\neg B)\land G_{[0:90]}(\neg E)\land G_{[0:90]}(\neg G)\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6}))$

Figure: Figure 30: Scene for Quadrotor: STL task 06
Refer to caption: x66.png

STL-06 (Multi-layer):  $F_{[10:90]}(A)\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

Figure: Figure 31: Scene for Quadrotor: STL task 07
Refer to caption: x67.png

STL-07 (Multi-layer):  $F_{[0:90]}(A_{1})\land F_{[40:80]}(A_{2})\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

Figure: Figure 32: Scene for Quadrotor: STL task 08
Refer to caption: x68.png

STL-08 (Multi-layer):  $F_{[0:90]}(A_{1})\land F_{[40:60]}(A_{2}\land F_{[15:30]}(G_{[0:5]}(A_{3})))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

Figure: Figure 33: Scene for Quadrotor: STL task 09
Refer to caption: x69.png

STL-09 (Multi-layer):  $F_{[25:30]}(A_{1}\land F_{[20:28]}(G_{[0:5]}(A_{2})\land F_{[10:30]}(G_{[0:5]}(A_{3}))\land F_{[10:30]}(G_{[0:10]}(A_{4}))))\land G_{[0:100]}(\neg B_{1})\land G_{[0:100]}(\neg B_{6})\land G_{[0:100]}(\neg B_{7})\land G_{[0:100]}(\neg B_{8})\land G_{[0:100]}(\neg B_{9})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

Figure: Figure 34: Scene for Quadrotor: STL task 10
Refer to caption: x70.png

STL-10 (Multi-layer):  $(\neg D_{1})U_{[0:100]}(K_{1})\land(\neg D_{2})U_{[0:100]}(K_{2})\land(\neg D_{3})U_{[0:100]}(K_{3})\land F_{[80:90]}(G_{[0:5]}(G))\land G_{[0:100]}(\neg B_{5})\land G_{[0:100]}(\neg W_{1})\land G_{[0:100]}(\neg W_{2})\land G_{[0:100]}(\neg W_{3})\land G_{[0:100]}(\neg W_{4})\land G_{[0:100]}(\neg W_{5})\land G_{[0:100]}(\neg W_{6})$

#### A.7.5 STLs in “Ant” environment

Figure: (a) STL-01
Refer to caption: x71.png

STL-01 (Two-layer):  $F_{[10:14]}(F_{[100:170]}(A)\land G_{[0:180]}(\neg B_{5})\land G_{[0:180]}(\neg B_{1})\land G_{[0:180]}(\neg B_{2})\land G_{[0:180]}(\neg B_{3})\land G_{[0:180]}(\neg B_{4}))$

STL-02 (Two-layer):  $F_{[10:20]}(F_{[0:100]}(A)\land G_{[120:160]}(C)\land G_{[0:180]}(\neg B_{5})\land G_{[0:180]}(\neg B_{1})\land G_{[0:180]}(\neg B_{2})\land G_{[0:180]}(\neg B_{3})\land G_{[0:180]}(\neg B_{4}))$

STL-03 (Two-layer):  $F_{[10:20]}(F_{[0:100]}(A)\land F_{[80:120]}(C)\land G_{[140:160]}(D)\land G_{[0:180]}(\neg B_{5})\land G_{[0:180]}(\neg B_{0})\land G_{[0:180]}(\neg B_{1})\land G_{[0:180]}(\neg B_{2})\land G_{[0:180]}(\neg B_{3})\land G_{[0:180]}(\neg B_{4}))$

STL-04 (Two-layer):  $F_{[10:20]}(F_{[0:100]}(A)\land F_{[80:100]}(C)\land F_{[140:160]}(F)\land G_{[100:120]}(D)\land G_{[0:180]}(\neg B)\land G_{[0:180]}(\neg E)\land G_{[0:180]}(\neg B_{1})\land G_{[0:180]}(\neg B_{2})\land G_{[0:180]}(\neg B_{3})\land G_{[0:180]}(\neg B_{4}))$

STL-05 (Two-layer):  $F_{[10:20]}(F_{[0:60]}(A)\land F_{[60:100]}(C)\land F_{[140:160]}(F)\land F_{[150:176]}(H)\land G_{[100:120]}(D)\land G_{[0:180]}(\neg B)\land G_{[0:180]}(\neg E)\land G_{[0:180]}(\neg G)\land G_{[0:180]}(\neg B_{1})\land G_{[0:180]}(\neg B_{2})\land G_{[0:180]}(\neg B_{3})\land G_{[0:180]}(\neg B_{4}))$

Figure: (a) STL-06
Refer to caption: x76.png

STL-06 (Multi-layer):  $F_{[20:180]}(A)\land G_{[0:200]}(\neg B_{1})\land G_{[0:200]}(\neg B_{2})\land G_{[0:200]}(\neg B_{3})\land G_{[0:200]}(\neg B_{4})\land G_{[0:200]}(\neg B_{5})$

STL-07 (Multi-layer):  $F_{[0:180]}(A_{1})\land F_{[80:160]}(A_{2})\land G_{[0:200]}(\neg B_{1})\land G_{[0:200]}(\neg B_{2})\land G_{[0:200]}(\neg B_{3})\land G_{[0:200]}(\neg B_{4})\land G_{[0:200]}(\neg B_{5})$

STL-08 (Multi-layer):  $F_{[0:180]}(A_{1})\land F_{[80:160]}(A_{2}\land F_{[20:40]}(G_{[0:20]}(A_{3})))\land G_{[0:200]}(\neg B_{1})\land G_{[0:200]}(\neg B_{2})\land G_{[0:200]}(\neg B_{3})\land G_{[0:200]}(\neg B_{4})\land G_{[0:200]}(\neg B_{5})$

STL-09 (Multi-layer):  $F_{[10:40]}(A_{1}\land F_{[20:40]}(G_{[0:10]}(A_{2})\land F_{[20:60]}(G_{[0:10]}(A_{3}))\land F_{[20:60]}(G_{[0:20]}(A_{4}))))\land G_{[0:200]}(\neg B_{1})\land G_{[0:200]}(\neg B_{2})\land G_{[0:200]}(\neg B_{3})\land G_{[0:200]}(\neg B_{4})\land G_{[0:200]}(\neg B_{5})\land G_{[0:200]}(\neg B_{6})\land G_{[0:200]}(\neg B_{7})\land G_{[0:200]}(\neg B_{8})\land G_{[0:200]}(\neg B_{9})$

STL-10 (Multi-layer):  $(\neg D_{1})U_{[0:200]}(K_{1})\land(\neg D_{2})U_{[0:200]}(K_{2})\land(\neg D_{3})U_{[0:200]}(K_{3})\land F_{[160:180]}(G_{[0:10]}(G))\land G_{[0:200]}(\neg B_{1})\land G_{[0:200]}(\neg B_{2})\land G_{[0:200]}(\neg B_{3})\land G_{[0:200]}(\neg B_{4})\land G_{[0:200]}(\neg B_{5})$

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: How are the STLs designed?

What are the guidelines used for this designing?

Are there any practical scenarios where these STLs have been applied in real applications?
soundness: 2
strengths: This work presents a new reinforcement learning method for motion planning to achieve sequenced subgoals given time assignments. The formulation of several RL components including state space and reward function seems to be new.

This work proposes a new method for time domain planning in STL that is capable of sampling promising future timesteps for subgoal planning.

Experiments in five simulated environments demonstrate improved performance over some baseline methods.
summary: This paper presents a new reinforcement learning method to learn control policies for some types of STL specifications. The proposed method consists of first sampling time assignments for decomposed subgoals and then learn policies to achieve these subgoals conditioned on the time assignments.
weaknesses: Although the paper claims to solve *general* STLs, in fact the proposed method cannot be applied to some important STLs at the moment.
- Line 197, it is assumed that the type of invariance task after translation only contains *interval* for time variable. This makes modelling and learning for STL that involves infinite time impractical. Although this is mentioned in the limitation section, It should be clearly described at the introduction of STLs.
- This paper cannot handle STLs like G(F …) as mentioned in Line 212. In fact, many liveness properties of the STL cannot be handled by the current method. These kinds of temporal logic are quite important in some domain like maintenance tasks or repeated tasks that require the agent conduct task periodically.
Therefore, the current paper overclaims what types of STL the proposed method can handle. The paper is supposed to have a clear explanation on what the specific STLs are they are targeting, give a formal definition on what these STLs are and what common properties they have in common, how they are related to other types of STLs that the method cannot handle.

The proposed reward function lacks a direct link with respect to the original STL task. It is unclear under this combination of rewards, how the optimal policy behaves in the original STL task. Ideally, the conversion from STL task to RL task should be formulated in a way that both optimization tasks share the same optimal solutions. Similar to LTL2Action, it would be better to provide analysis showing that the optimal policy under the proposed rewards also guarantees the satisfaction of the original STL.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. See weaknesses 1 and 2
2. In what sense is the time-allocation method Bayesian?
The Metropolis–Hastings sampling uses the critic as a heuristic energy function, but it’s unclear whether this constitutes a Bayesian inference procedure or simply a guided stochastic search.
soundness: 3
strengths: Strengths
1. Solid statistical analysis and thorough results section.
The empirical evaluation is broad, well-structured, and uses multiple seeds, metrics, and ablation studies. The inclusion of both low- and high-dimensional systems helps demonstrate scalability.
2. The use of the learned value function to guide time allocation search is interesting 
3. The writing is clear for the most part (see weakness 1)
summary: The paper proposes Temporal Grounded Policy Optimization (TGPO), a hierarchical reinforcement learning framework for solving control problems specified using Signal Temporal Logic (STL). STL enables rich task specifications with temporal and spatial constraints, but its non-Markovian structure and sparse reward signals make it difficult to handle with standard RL algorithms.  TGPO decomposes STL formulas into subgoals with invariant constraints, and introduces a two-level architecture: a high-level “temporal grounding” component assigns time variables to each subgoal, while a low-level time-conditioned policy learns to satisfy them using dense, stage-wise rewards. The framework includes a critic-guided Bayesian time allocation step using Metropolis–Hastings sampling, which focuses exploration on promising temporal schedules.
Experiments across five environments (2D navigation, unicycle, Franka Panda, quadrotor, and Ant) show that TGPO and its Bayesian variant (TGPO*) outperform several baselines—τ-MDP, F-MDP, RNN, Grad, and CEM—particularly on complex, high-dimensional, and long-horizon STL tasks.
weaknesses: 1. In sec. 4.1 the authors say “Our method of decomposing STL into subgoals with invariant constraints is inspired by Kapoor et al. (2024); Liu et al. (2025).”  From a clarity standpoint, it is unclear to what extent the proposed method for decomposition into subgoals differs from these prior works.  Can the authors elaborate on this?
2. The shaped reward defined in eq. 6 seems specific to locomotion-type problems.  It’s unclear how this would generalize to other domains.

---

confidence: 3
contribution: 3
initial_rating: 2
presentation: 2
questions: - **Q1.** See W2. What does $\mathbb{P}_{x_0\in\mathcal{X}_0}$ formally mean in the problem statement? Do we assume a distribution over the initial states? Is the objective maximization over success rates or average robustness score?
- **Q2.** See W3. Can you provide pseudocode for STL decomposition? What are the inputs and outputs? How are nested formulas formally divided? How are the time variables determined; for example, for $G_{[0,200]} F_{[0,10]} a$, where the number of time variables can vary, or for $F_{[0,100]} a \vee F_{[0,100]} b$, where one time variable might be sufficient?
- **Q3.** What are your thoughts regarding W4?
- **Q4.** See W6. Why isn't an ordering of subgoals sufficient?
- **Q5.** See W7. What are your thoughts on such a nonstationary environment? Why do you think your procedure transfers knowledge efficiently across MDPs?
- **Q6.** See W8. Does maximizing the return maximize the STL success rate or the robustness score? Is it an admissible heuristic?
- **Q7.** See W9. For example, assuming deep RL converges to an optimal policy that maximizes return, is the time-variable assignment procedure complete; i.e., if there is a feasible assignment, will the procedure eventually propose such an assignment? How fast could that be, given W4?
- **Q8.** See W9. Could you provide pseudocode for time-variable assignment with MH sampling? Also, why do you think the critic provides a good heuristic for MH sampling given that the MDPs are changing?
- **Q9.** I think some of the STL formulas used in the experiments should be discussed in the main paper. Could you provide a general description of the STL formulas? 
- **Q10.** In the figures in the experiments section, are training steps the same as environment steps?
- **Q11.** Could you compare the dimensionality of your augmented state space with history-stacked state spaces?
- **Q12.** Regarding Figure 6, did you use the same STL formulas with the same time intervals? Could you provide similar figures for different environments where the intervals are also scaled accordingly?
soundness: 2
strengths: To the best of my knowledge, the proposed approach is a novel way to address the sparsity and non-Markovian nature of STL rewards, an important problem in STL learning that existing methods do not sufficiently handle, especially for long-horizon tasks with complex STL formulas. In addition, the proposed approach is compared against a sufficiently representative set of baselines.
summary: This paper presents a reinforcement learning (RL) approach for learning from signal temporal logic (STL) to make learning more feasible for long-horizon tasks. The novel model-free approach divides and flattens complex STL formulas and searches for time-variable actualizations via Metropolis-Hastings (MH) sampling to enable efficient learning. The proposed method is compared with a range of existing approaches across several environments. I believe the idea is original and shows promise for improving over existing methods for STL learning. However, the paper still needs substantial work; specifically, a more thorough technical analysis and a systematic description of the proposed approach, as well as clearer explanations and presentation of the experimental results.
weaknesses: - **W1.** (Minor) Eq. (2) can be visually improved.
- **W2.** The problem statement is quite vague and somewhat confusing. I think a more comprehensive and consistent notation can be used. Also, constructing an augmented MDP should be part of the solution rather than the objective. Lastly, the probability-maximization statement with respect to the initial state is also ambiguous.
- **W3.** The STL decomposition is not systematically or algorithmically explained (Algorithm 1 is very high level) and is presented primarily through intuition and examples.
- **W4.** The number of different time-variable assignments can grow exponentially with the number of subgoals, which can be further complicated for nested and/or disjunctive formulas.
- **W5.** I think observed (continuous) time should be part of the augmented state space rather than the discrete step number, as STL is defined for continuous signals.
- **W6.** Exact time-variable assignments do not seem realistic; as I understand it, they represent the exact time at which a certain state must be reached.
- **W7.** It seems that a new MDP is constructed for every new assignment, which can technically impede RL.
- **W8.** The formal connection between the dense rewards and STL satisfaction is not established or discussed.
- **W9.** The authors do not provide sufficient technical analysis of the time-variable assignment procedure.
- **W10.** The flow and clarity of the experiments section can be improved.