We thank the reviewer for insightful feedback, valuable suggestions, and drawing attention to important aspects of our work. We provided detailed responses below and will revise the manuscript accordingly upon acceptance.

Q1:

The starting point of reward machine research is the construction of automata from LTL formulas specified as RL tasks [RM1]. Early work focused on the co-safe fragment of LTL [RM1] and LTL over finite traces (LTLf) [RM2], for which a deterministic finite automaton (DFA) can be constructed. These DFAs were later termed reward machines (RMs), as their accepting states can be used to assign positive rewards. Approaches targeting general LTL specifications instead use limit-deterministic Büchi automata (LDBAs). While structurally similar to RMs, LDBAs differ in their acceptance condition, which is based on infinite visitation of accepting states (suitable for continuous tasks), and thus require a distinct discounting scheme for correctness and convergence. In this work, we focus on making automaton-based reward signals differentiable, including those from DFAs and therefore RMs. When dealing with LDBAs, our approach additionally handles non-deterministic transitions and infinite visitation objectives. Importantly, our method can be immediately applied, without modification, to any RM constructed from co-safe LTL or LTLf) formulas using the atomic propositions defined in Section 2. As a result, our approach can directly accelerate learning with RMs. Furthermore, all existing techniques used with RMs, such as reward shaping [RM3], can also be integrated into differentiable RL. We note that while reward shaping does not affect the optimality of policies, it may lead to incorrect estimates of satisfaction probabilities. We hope our response provides sufficient explanation.

[RM1] Icarte et al. "Teaching multiple tasks to an RL agent using LTL." AAMAS. 2018.

[RM2] Camacho et al. "LTL and beyond: Formal languages for reward function specification in reinforcement learning." IJCAI. 2019.

[RM3] Icarte et al. "Reward machines: Exploiting reward function structure in reinforcement learning." JAIR. 2022.

Q2:

By Theorem 1, the sum of discounted discrete LTL rewards approaches the actual satisfaction probabilities as $\gamma \to 1$, thereby adhering to hard safety constraints. The introduction of "softness" in the labels may introduce some slack, but this can be upper-bounded. We show that the maximum discrepancy between the discrete and differentiable values can be upper-bounded for a given tolerance parameter, as formalized in the theorem below.

Theorem 2: Let $\varsigma$ be the tolerance on the signal bounds of atomic propositions, and let $p$ be the probability associated with $\varsigma$ (i.e., $p := \text{Pr}(\varsigma > 0) = h(\varsigma)$) as in (3). Let $G^\text{disc.}$ and $G^\text{diff.}$ denote the returns obtained via discrete and differentiable rewards, respectively. Then the maximum discrepancy between them is upper bounded as:

$$|G^\text{disc.}(\sigma)-G^\text{diff.}(\sigma)| < \frac{1}{1+\frac{1-\beta}{(1-p)^{|\mathtt{A}|}}} = \frac{1}{1+\frac{1-\beta}{(1-h(\varsigma))^{|\mathtt{A}|}}}$$

where $\beta$ is the discount factor for accepting states, as defined in (8). By linearity of expectation, this result immediately extends to the expected return (values) in stochastic environments; i.e, the upper bound above holds for $|\mathbb{E}[G^\text{disc.}(\sigma)]-\mathbb{E}[G^\text{diff.}(\sigma)]|$ where expectations are over trajectories drawn under any given policy.

Please see Proof of Theorem 2 above under response to Reviewer ynyM.

Now, given Theorem 2, we can capture the safety constraints via differentiable rewards with an approximation error that can be tuned by the tolerance parameter $\varsigma$ or the activation function $h$. For instance, using a hard sigmoid $h(x) = \max(0, \min(1,(\alpha x+1)/2))$ yields $p = 1$ when $\varsigma = 1/\alpha$, thus achieving equivalence. This introduces a trade-off between tolerance (hence the size of the the differentiable region) and the approximation error. We hope our response sufficiently addresses your concerns.

Q3:

Yes. We modeled the stochasticity of the environments through an initial state distribution ($p_0$ in MDPs, Section 3), since differentiable simulators typically have only deterministic step functions. Stochasticity can also be introduced by manually adding noise to the actuation signals, which can be integrated in a differentiable manner using the reparameterization trick as the reviewer pointed out. Our approach is capable of handling such environments, as our results hold in expectation over stochastic trajectories (Theorem 1, 2). In practice, we believe that as long as the noise isn't excessively high—which would pose a general challenge for RL—our differentiable approach will still lead to improved efficiency. We hope our response answers your question.

W1:

Due to the space limit, unfortunately, we had to move many details to Appendix. We include them below for your convenience.

Differentiable RL. Differentiable simulators enable gradient-based optimization by analytically or automatically computing gradients of states and rewards with respect to actions. These simulators can be represented as differentiable transition functions $s_{t+1} = f(s_t, a_t)$, where $s_t$ and $a_t$ represent the state and action at time step $t$, respectively, and $s_{t+1}$ is the next state at time step $t+1$. In the context of RL, a common choice for the differentiable loss function is the negative of the return, defined as the sum of discounted rewards: $\mathcal{L} = -G_H(\sigma) = - \sum_{t=0}^H \gamma_t r_t$, where $H$ is the time horizon, $\sigma = s_0s_1\dots$ is the trajectory, $r_t$ is the reward at time step $t$, and $\gamma_t$ is the discount factor applied at that step. The backward pass then computes the gradients as follows:

$$\frac{\partial G_H}{\partial s_t} = \frac{\partial G_H}{\partial s_{t+1}} \frac{\partial f}{\partial s_t}, \qquad \frac{\partial G_H}{\partial a_t} = \frac{\partial G_H}{\partial s_{t+1}} \frac{\partial f}{\partial a_t}.$$

By chaining these gradients, the optimization updates propagate effectively throughout trajectories.In policy gradient RL over a finite horizon $H$, the goal is to find optimal parameters $\psi^\star = \mathrm{arg}\max_\psi J(\psi)$, such that $J(\psi) = \mathbb{E}$ G_H(\sigma) $$ where expectation is over random trajectory drawn from the Markov chain induced by a policy $\pi$ parameterized by $\psi$. If a differentiable model is available, optimization can leverage first-order gradients: \nabla_\psi^{ 1 } J(\psi) = \mathbb{E} \nabla_\psi G_H(\sigma) $$, or employ model-free zeroth-order gradients via the policy gradient theorem: \nabla_\psi^{ 0 } J(\psi) = \mathbb{E} G_H(\sigma) \sum_{t=0}^{H-1} \nabla_\psi \log \pi_\psi(a_t|s_t) $.$ Both gradients can be approximated through Monte Carlo sampling: \hat{\nabla_\psi}{ 1 } J(\psi) = \frac{1}{N} \sum_{i=1}^N \nabla_\psi G_H(\sigma^{(i)}) and \hat{\nabla_\psi}^{ 0 } J(\psi) = \frac{1}{N} \sum_{i=1}^NG_H(\sigma^{(i)}) \sum_{t=0}^{H-1} \nabla_\psi \log \pi_\psi(a^{(i)}_t|s^{(i)}_t) respectively.

LDBA Updates. Please see the LDBA Updates paragraph under Q2 in our response to Reviewer ynyM; (also see the supp. file for details of LDBAs).

Rewarding and Discounting. Visiting an accepting state requires a separate discount factor $\beta$ to ensure the correctness of the objective, namely, making the sum of discounted rewards accurately reflect the satisfaction probability. The core idea is to structure the rewards so that the cumulative reward from repeatedly visiting an accepting state converges to 1. For example, suppose an accepting state is visited repeatedly and a reward of $1 - \beta$ is provided at each time step. Then, the cumulative return is given by: $G = (1-\beta) + \beta(1-\beta) + \beta^2(1-\beta) + \dots = 1$. On the other hand, as long as accepting states are visited repeatedly, visits to non-accepting states do not violate the acceptance condition and thus should be disregarded. Since non-accepting states have no associated rewards, one might initially consider omitting discounting altogether in these states. However, doing so prevents convergence. Therefore, non-accepting states must still be discounted slightly, using a discount factor $\gamma$ that is significantly closer to 1 than $\beta$. We hope our response provides sufficient clarification.

W2:

Please see our detailed response to Q2. We hope it provides satisfactory explanation.

W3:

We believe our extended discussion in W1 addresses this concern as well.

W4:

Classic reward schemes are typically handcrafted for specific tasks and therefore cannot be directly analyzed in relation to general LTL formulas. That said, automatically deriving rewards from LTL specifications is significantly easier than manually designing classic rewards, which often requires detailed knowledge of system dynamics and balancing trade-offs between competing objectives.

W5:

Our discussion regarding stochasticity under Q3. We hope it provides sufficient explanation.

L1 and L2:

Please see our response to Q1 and Q2.

L3:

The choice of the activation function $h$ in $g$, along with its hyperparameters, can influence the performance of learning from LTL specifications. We intend to perform these experiments as much as possible and include the results in the manuscript before the camera-ready version upon acceptance.

We are grateful to the reviewer for their thoughtful feedback, constructive suggestions, and for drawing attention to important issues in our work. Below, we provide detailed responses and clarifications addressing the raised questions and concerns. We will update our manuscript upon acceptance accordingly.

Q1:

That is correct, the more frequently the accepting states of the LDBA are visited, the more rewards are accumulated. In our approach, the expected return (i.e., the cumulative discounted rewards) is proven to converge to the actual satisfaction probability in the limit as $\gamma \to 1$, given a sufficiently large horizon. That said, very long-horizon tasks typically require a discount factor $\gamma$ extremely close to 1. For example, a horizon of $H = 10000$ might necessitate $\gamma = 0.999999$ to maintain meaningful credit assignment over the trajectory. However, using such a high discount factor can significantly slow down convergence. In practice, smaller discount factors often lead to more efficient learning. The downside is that a smaller $\gamma$ places more emphasis on immediate rewards, increasing the risk of overlooking optimal policies that yield rewards later in the trajectory, such as those involving reaching a target state after many steps with higher certainty. We hope this response provides sufficient clarification.

Q2:

Yes, we still consider the satisfaction of the acceptance condition of LDBAs. One can interpret probabilistic LDBA updates as executions triggered by probabilistically superimposed trajectories. Theorem 1 still holds, but with an approximation error that can be controlled by a tolerance parameter and the choice of activation function. We formally state this as a theorem below:

Theorem 2: Let $\varsigma$ be the tolerance on the signal bounds of atomic propositions, and let $p$ be the probability associated with $\varsigma$ (i.e., $p := \text{Pr}(\varsigma > 0) = h(\varsigma)$) as in (3). Let $G^\text{disc.}$ and $G^\text{diff.}$ denote the returns obtained via discrete and differentiable rewards, respectively. Then the maximum discrepancy between them is upper bounded as:

$$|G^\text{disc.}(\sigma)-G^\text{diff.}(\sigma)| < \frac{1}{1+\frac{1-\beta}{(1-p)^{|\mathtt{A}|}}} = \frac{1}{1+\frac{1-\beta}{(1-h(\varsigma))^{|\mathtt{A}|}}}$$

where $\beta$ is the discount factor for accepting states, as defined in (8). By linearity of expectation, this result immediately extends to the expected return (values) in stochastic environments; i.e, the upper bound above holds for $|\mathbb{E}[G^\text{disc.}(\sigma)]-\mathbb{E}[G^\text{diff.}(\sigma)]|$ where expectations are over trajectories drawn under any given policy.

Proof: The maximum discrepancy between $G^\text{disc.}$ and $G^\text{diff.}$ occurs when all probabilistic transitions associated with soft labels yield positive differentiable rewards while their corresponding discrete rewards are zero (or vice versa). For a given tolerance $\varsigma$, the probability of incorrectly evaluating all atomic propositions under soft labels is $\rho := (1-p)^{|\mathtt{A}|}$, where $\mathtt{A}$ denotes the set of all atomic propositions defined in the LTL grammar. In this worst-case scenario, the differentiable return for a trajectory $\sigma$, where all such transitions lead to accepting states, is:

$$G^\text{diff.}(\sigma) \leq \sum_t^\infty \rho(1-\rho)^t\beta^t = \frac{\rho}{1-(1-\rho)\beta} = \frac{\rho}{(1-\beta)+ \rho\beta} = \frac{1}{1+\frac{1-\beta}{\rho}} = \frac{1}{1+\frac{1-\beta}{(1-p)^{|\mathtt{A}|}}}.$$

Since $G^\text{disc.} = 0$, this expression provides the upper bound on the maximum discrepancy.

Given Theorem 2, we can capture the Büchi acceptance condition via differentiable rewards with an approximation error that can be tuned by the tolerance parameter $\varsigma$ or the activation function $h$. For instance, using a hard sigmoid $h(x) = \max(0, \min(1,(\alpha x+1)/2))$ yields $p = 1$ when $\varsigma = 1/\alpha$, thus achieving equivalence. This introduces a trade-off between tolerance (hence the size of the the differentiable region) and the approximation error. We hope this provides a satisfactory explanation.

Q3:

Thank you for pointing this out. Here, $\psi$ denotes the set of trainable parameters, typically corresponding to the weights of the actor and critic networks in RL algorithms. We will make sure to explain this in detail in our paper.

Q4:

With the ablation studies, our goal is to highlight our core contribution: making learning for LTL specifications feasible through differentiable LTL rewards, which would otherwise be infeasible. As the reviewer pointed out, it is not possible to fully decouple the effects of environment dynamics from those of the task specification. However, these ablation studies demonstrate that there is no inherent limitation in the environments themselves that prevents learning from discrete rewards. They show that while learning with discrete rewards is possible for simple task specifications, it becomes dramatically more difficult as the complexity of the specification increases to include more challenging LTL properties. This underscores the necessity of using differentiable rewards for learning complex LTL tasks. We hope this response provides sufficient clarification.

W1:

Thank you for bringing these articles to our attention. We will add these references.

W2:

Visiting an accepting state requires a separate discount factor to ensure the correctness of the objective, namely, making the sum of discounted rewards accurately reflect the satisfaction probability. The core idea is to structure the rewards so that the cumulative reward from repeatedly visiting an accepting state converges to 1. For example, suppose an accepting state is visited repeatedly and a reward of $1 - \beta$ is provided at each time step. Then, the cumulative return is given by: $G = (1-\beta) + \beta(1-\beta) + \beta^2(1-\beta) + \dots = 1$. On the other hand, as long as accepting states are visited repeatedly, visits to non-accepting states do not violate the acceptance condition and thus should be disregarded. Since non-accepting states have no associated rewards, one might initially consider omitting discounting altogether in these states. However, doing so prevents convergence. Therefore, non-accepting states must still be discounted slightly, using a discount factor $\gamma$ that is significantly closer to 1 than $\beta$.

Due to the simultaneous execution of probabilistic transitions triggered by soft labels, the automaton occupies a superposition of states at any given timestep, represented by the vector $\mathbf{q}$. Because different automaton states require different discounting behaviors, we compute a superimposed discount factor, as specified by the function $\mathfrak{D}$, to account for this state-dependent discounting. We hope this response provides sufficient clarification.

W3:

The shaded areas in the rightmost plot of Figure 3 represent the standard deviation of the gradients. We observe that the gradient associated with differentiable rewards is significantly lower than that associated with discrete rewards, particularly around $5.0m/s^2$. We hope this helps.

W4:

Thank you for this suggestion. We would like to note that our primary objective in this work is to develop differentiable automaton-based rewards. Thus, our contribution can be measured by the improvement in learning efficiency achieved when transitioning from discrete to differentiable rewards, which is why we compare our approach directly to the discrete version. Our framework can easily be applied to any automaton-based reward method (such as reward machines), and similar comparisons can be performed between the standard discrete rewards and the differentiable rewards obtained via the soft labels introduced in our work. Upon acceptance, we will incorporate more discrete LTL algorithms, analyze the acceleration gained through differentiability via the soft labels we introduce, and include a comparative evaluation.

W5:

Thank you for pointing this out. It is, unfortunately, typically not feasible to compute satisfaction probabilities for continuous (infinite-horizon) tasks, such as safety, in highly nonlinear systems. However, we can employ a formal metric that indicates whether the system's progress complies with the specification, similar to the robustness score used in the online monitoring of STL specifications. We plan to include such results upon acceptance.

We thank the reviewer for insightful comments, helpful suggestions, and pointing out the important issues regarding our paper. We answered and explained the questions and weaknesses below. We will update our manuscript upon acceptance accordingly.

Q1:

Learning from sparse rewards in high-dimensional settings is generally a challenging problem, primarily due to the extensive exploration required. In our paper, we demonstrate that our differentiable reward approach can significantly mitigate this issue. For example, as shown in Figure 3 for the Ant environment with a 37-dimensional state space, our method substantially improves learning efficiency. While learning from discrete LTL rewards in even higher-dimensional state spaces may potentially require billions of time steps, we believe that our differentiable approach can substantially alleviate this burden. We hope this answers your question.

Q2:

We modeled the stochasticity of the environments through an initial state distribution ($p_0$ in MDPs, as described in Section 3), since differentiable simulators typically have only deterministic step functions ($f$). Stochasticity can also be introduced by manually adding noise to the actuation signals, which can be integrated in a differentiable manner using the reparameterization trick. Our approach is capable of handling such environments, as our results hold in expectation over stochastic trajectories (Theorem 1). In practice, we believe that as long as the noise is not excessively high—which would pose a general challenge for RL—our differentiable approach will still lead to improved efficiency. We hope this addresses your question.

Q3:

STL additionally allows for the specification of real-time constraints; however, this comes at the significant cost of losing the compact memory mechanism provided by LTL. Specifically, evaluating STL satisfaction or robustness requires access to the full trajectory, as these metrics can only be computed after the trajectory ends. This necessitates storing entire trajectory histories, which directly violates the Markovian assumption fundamental to value-based RL techniques. Unlike LTL, this issue cannot be resolved by augmenting the state space with a compact memory representation derived from automata. There are two common approaches to address this challenge. The first is to augment the state space with the full trajectory history, but this leads to prohibitively large and impractical state spaces. For instance, with a horizon of $H = 1024$ used in our experiments, the state space for the Ant environment would be of size $1024 \times 37 = 37{,}888$. The second approach involves applying policy optimization over the action history using backpropagation through time (BPTT). However, due to the well-known exploding and vanishing gradient problems, gradients quickly deteriorate and become unreliable beyond roughly 100 time steps. This issue is further exacerbated in stochastic environments, where optimization becomes ineffective even over a small number of steps. Using intermediate STL robustness scores, an approach sometimes adopted to address the sparse reward problem in practice, does not resolve this hard non-Markovian problem of STL specifications. In fact, optimizing for the sum of such intermediate rewards can lead to incorrect RL objectives, as it does not necessarily correspond to maximizing the satisfaction of the STL specification. We hope our response provides sufficient information and clarification.

Q4:

The starting point of reward machine research is the construction of automata from LTL formulas specified as RL tasks [RM1]. Early work focused on the co-safe fragment of LTL [RM1] and LTL over finite traces (LTLf) [RM2], for which a deterministic finite automaton (DFA) can be constructed. These DFAs were later termed reward machines (RMs), as their accepting states can be used to assign positive rewards. Approaches targeting general LTL specifications instead use limit-deterministic Büchi automata (LDBAs). While structurally similar to RMs, LDBAs differ in their acceptance condition, which is based on infinite visitation of accepting states (suitable for continuous tasks), and thus require a distinct discounting scheme for correctness and convergence. In this work, we focus on making automaton-based reward signals differentiable, including those from DFAs and therefore RMs. When dealing with LDBAs, our approach additionally handles non-deterministic transitions and infinite visitation objectives. Importantly, our method can be immediately applied, without modification, to any RM constructed from co-safe LTL or LTLf) formulas using the atomic propositions defined in Section 2. As a result, our approach can directly accelerate learning with RMs. Furthermore, all existing techniques used with RMs, such as reward shaping [RM3], can also be integrated into differentiable RL. We note that while reward shaping does not affect the optimality of policies, it may lead to incorrect estimates of satisfaction probabilities. We hope this reponse provides sufficient clarification.

[RM1] Icarte et al. "Teaching multiple tasks to an RL agent using LTL." AAMAS. 2018.

[RM2] Camacho et al. "LTL and beyond: Formal languages for reward function specification in reinforcement learning." IJCAI. 2019.

[RM3] Icarte et al. "Reward machines: Exploiting reward function structure in reinforcement learning." JAIR. 2022.

W1: Existing Work

Due to space limitations, we had to condense the related work section, which may have obscured some important details. We include our extended discussion below for your convenience and will update our paper to include more details.

RL for TL. Initial attempts to combine LTL with RL relied on model-based approaches. These methods required precise knowledge of the transition structure of the underlying MDPs to precompute accepting components of a product MDP constructed using a Deterministic Rabin Automaton (DRA) based on LTL specifications. This approach transformed satisfying temporal logic constraints into reachability problems solvable via RL. Despite providing probably approximately correct (PAC) guarantees, the complexity and frequent unavailability of accurate transition models limit their applicability, especially in deep RL contexts. To address these limitations, model-free RL methods for LTL emerged, such as those proposed in [RM(1-3)] for co-safe LTL and LTLf, which directly generate rewards from the acceptance conditions of automata derived from LTL without explicit knowledge of transition dynamics. The introduction of LDBAs [79], simplifying model checking by utilizing simpler Büchi conditions instead of Rabin conditions, further facilitated structured reward design with improved correctness [28] and stronger convergence guarantees [29]. Researchers have also explored alternative temporal logics to generate informative reward signals. STL allows robustness scores to serve as rewards in finite-horizon tasks [56]. However, these scores typically depend on historical information, violating the Markov assumption and restricting their use in stochastic or value-based RL settings.

W2: Baseline/RM Comparison

Our objective in this work is to make automaton-based rewards differentiable. Therefore, our contribution can be measured by the acceleration in learning achieved by switching from discrete to differentiable rewards. This is why we compared our approach with the discrete version. Our framework can be readily applied to RMs, and a similar comparison can be made between standard discrete RM rewards and differentiable RM rewards obtained through the soft labels we introduce (e.g., by focusing on co-safe LTL or LTLf; also see our response to Q4). We will include such explicit comparisons upon acceptance.

W3: STL Comparison

Learning from STL rewards is generally not well-suited for the tasks with a horizon of $H = 1024$ considered in our paper (please see our response to Q3 as well), and therefore, we believe not suitable for direct comparison with LTL in our experiments. We hope our response provides clarification.

W4: Long-Horizon Control

We thank the reviewer for this comment. We will consider even longer horizons in our experiments as suggested. We also would like to emphasize that, in the environments we consider, only the forward movement objective, supported by carefully designed dense and intricate rewards, can be effectively solved by modern RL approaches. For example, the reward function used in the Ant environment is as complex as: reward = healthyreward*ifhealthy() + wforward*dx/dt - wcontrol*$||$action$||^2_2$ - wcontrol*$||$clip(Fcontact)$||^2_2$. General objectives without handcrafted rewards are difficult to learn for a horizon of $H = 1024$, the setting used in our experiments, even for state-of-the-art RL algorithms such as SAC and PPO, as demonstrated in our results.

W5: Determinism

Please see our response to Q2, where we also discuss how we can consider stochasticity in our setting.

W6: More Discrete Temporal Specifications

We thank the reviewer for this comment. We would like to note that, although differentiable simulators require the state space to be continuous, the positions and velocities can be highly nonlinear with respect to actions—often resembling discrete transitions—especially in contact-rich, legged-robot environments such as those used in our experiments. As a result, the The APs we use inherently exhibit highly nonlinear behavior with respect to actions. Additionally, any differentiable nonlinear function can be used for $g(s)$ in APs; however, the more nonlinear it is, the less reliable the gradients become. Nonetheless, this does not fundamentally affect our approach, as it is no different from having highly nonlinear transitions within the simulator itself.

Formatting Concern:

We will decrease the number of references.

We appreciate the reviewer’s thoughtful comments, constructive suggestions, and for highlighting key issues in our paper. We have addressed and clarified the questions and concerns as detailed below. We will update our manuscript upon acceptance accordingly.

Q1:

We can show that the maximum discrepancy between the discrete and differentiable values can be upper-bounded for a given tolerance parameter, as formalized in the theorem below. Since, by Theorem 1, the discrete values converge to the satisfaction probabilities, the bound is also valid in the limit for the actual satisfaction probabilities.

Theorem 2: Let $\varsigma$ be the tolerance on the signal bounds of atomic propositions, and let $p$ be the probability associated with $\varsigma$ (i.e., $p := \text{Pr}(\varsigma > 0) = h(\varsigma)$) as in (3). Let $G^\text{disc.}$ and $G^\text{diff.}$ denote the returns obtained via discrete and differentiable rewards, respectively. Then the maximum discrepancy between them is upper bounded as:

$$|G^\text{disc.}(\sigma)-G^\text{diff.}(\sigma)| < \frac{1}{1+\frac{1-\beta}{(1-p)^{|\mathtt{A}|}}} = \frac{1}{1+\frac{1-\beta}{(1-h(\varsigma))^{|\mathtt{A}|}}}$$

where $\beta$ is the discount factor for accepting states, as defined in (8). By linearity of expectation, this result immediately extends to the expected return (values) in stochastic environments; i.e, the upper bound above holds for $|\mathbb{E}[G^\text{disc.}(\sigma)]-\mathbb{E}[G^\text{diff.}(\sigma)]|$ where expectations are over trajectories drawn under any given policy.

Proof: The maximum discrepancy between $G^\text{disc.}$ and $G^\text{diff.}$ occurs when all probabilistic transitions associated with soft labels yield positive differentiable rewards while their corresponding discrete rewards are zero (or vice versa). For a given tolerance $\varsigma$, the probability of incorrectly evaluating all atomic propositions under soft labels is $\rho := (1-p)^{|\mathtt{A}|}$, where $\mathtt{A}$ denotes the set of all atomic propositions defined in the LTL grammar. In this worst-case scenario, the differentiable return for a trajectory $\sigma$, where all such transitions lead to accepting states, is:

$$G^\text{diff.}(\sigma) \leq \sum_t^\infty \rho(1-\rho)^t\beta^t = \frac{\rho}{1-(1-\rho)\beta} = \frac{\rho}{(1-\beta)+ \rho\beta} = \frac{1}{1+\frac{1-\beta}{\rho}} = \frac{1}{1+\frac{1-\beta}{(1-p)^{|\mathtt{A}|}}}.$$

Since $G^\text{disc.} = 0$, this expression provides the upper bound on the maximum discrepancy.

Q2:

We include definitions of $\sigma$ and its fragments ($\sigma[t]$, $\sigma[:t]$, $\sigma[t:]$) in the context of RL objective below (please see the supplementary material for more details):

RL Objective. In RL, a given policy $\pi:S^+\mapsto A$ is evaluated based on the expected cumulative reward (known as return) associated with the paths $\sigma := s_0s_1\dots$ (sequence of visited states) generated by the Markov chain (MC) $M_\pi$ induced by the policy $\pi$. We write $\sigma[t]$, $\sigma[:t]$, $\sigma[t:]$ for $s_t$, the prefix $s_0\dots s_t$ and the suffix $s_ts_{t+1}\dots$. For a given reward function $R: S^+ \mapsto \mathbb{R}$, a discount factor $\gamma \in (0, 1)$, and a horizon $H$, the return of a path $\sigma$ from time $t \in \mathbb{N}$, is defined as $G_{t:H}(\sigma) = \sum_{i=t}^{H} \gamma^{i} R(\sigma[:i])$. For simplicity, we denote the infinite-horizon return starting from $t = 0$ as $G_H(\sigma) := G_{0:H}(\sigma)$, and further drop the subscript to write $G(\sigma) := \lim_{H \to \infty} G_H(\sigma)$. We note that for Markovian reward functions ($R: S \mapsto \mathbb{R}$), memoryless policies ($\pi:S\mapsto A$) suffice. However, the tasks we consider require finite-memory policies (see the supplementary material). To address this, we reduce the problem of obtaining a finite-memory policy to that of learning a memoryless policy by augmenting the state space $S$ with memory states, as detailed in Section 4. The discount factor reduces the~value of future rewards to prioritize immediate ones: a reward received after $t$ steps contributes $\gamma^t R(\sigma[t])$ to the return. The objective in RL is to learn a policy that maximizes the expected return over trajectories.

We include an explanation of automaton updates with soft labels and $\varepsilon$-actions as follows:

LDBA Updates. In an LDBA, transitions triggered by labels are deterministic, so the current automaton state is represented by a discrete variable $q \in \mathbb{N}$. In our setting, however, the automaton observes all possible labels simultaneously, each with an associated probability. Consequently, the current state becomes a probability distribution over possible states, represented by a vector $\mathbf{q}$. Similarly, instead of taking a single $\varepsilon$-action (as in the discrete case, where it corresponds to a transition to a specific automaton state), our framework allows the agent to ``take a probability distribution'' over $\varepsilon$-actions. Each component of this action vector corresponds to a potential transition to a different automaton state. This probabilistic formulation captures uncertainty and enables smoothness and gradient-based learning.

Q3:

In the literature, it is established that the discrete reward formulation captures the Büchi acceptance condition in the limit as the discount factor $\gamma \to 1$. For finite-state MDPs, there always exists a sufficiently large discount factor $\gamma < 1$ for any given LTL specification. For infinite number of MDP states, though we do not have such guarantees in theory (i.e., $\gamma$ required could be arbitrarily close to $1$); there usually exists a practical discount factor. Our setting has these limitations as well, as our differentiable rewards are crafted based on these discrete rewards.

Now, given Theorem 2, we can similarly capture the Büchi acceptance condition via differentiable rewards with an approximation error that can be tuned by the tolerance parameter $\varsigma$ or the activation function $h$. For instance, using a hard sigmoid $h(x) = \max(0, \min(1,(\alpha x+1)/2))$ yields $p = 1$ when $\varsigma = 1/\alpha$, thus achieving equivalence. This introduces a trade-off between tolerance (hence the size of the the differentiable region) and the approximation error.

W1:

We provide a formal definition and explanation of finite-state machines below. (also see our response to Question 2 for a broader explanation). We also have a similar detailed explanation of finite-memory policies in the supplemantary file. Thank you for pointing this out, we understand the confusion and will update our paper accordingly.

A finite-memory policy for an MDP $M$ is defined as a tuple $\pi = (\mathfrak{M}, \mathfrak{m}_0, \mathfrak{T}, \mathfrak{a})$, where:

• $\mathfrak{M}$ is a finite set of modes (memory states);
• $\mathfrak{m}_0 \in \mathfrak{M}$ is the initial mode;
• $\mathfrak{T} : \mathfrak{M} \times S \times \mathfrak{M} \rightarrow [0,1]$ is a probabilistic mode transition function such that for any current mode $\mathfrak{m}$ and state $s$, the probabilities over next modes sum to 1, i.e., $\sum_{\mathfrak{m}' \in \mathfrak{M}} \mathfrak{T}(\mathfrak{m}' \mid \mathfrak{m}, s) = 1$;
• $\mathfrak{a} : \mathfrak{M} \times S \times A \rightarrow [0,1]$ is a probabilistic action selection function that assigns a probability to each action $a$ given the current mode $\mathfrak{m} \in \mathfrak{M}$ and state $s \in S$.

A finite-memory policy acts as a finite-state machine that updates its internal mode (memory state) as states are observed, and specifies a distribution over actions based on both the current state and mode. The action at each step is thus selected according not only the current state but also the current memory state of the policy. In contrast to standard definitions of finite-memory policies, which typically assume deterministic mode transitions, this definition permits probabilistic transitions between modes.

W2:

The symbol $\mathtt{M}$ denotes the mass matrix. Thank you for catching this oversight.

W3:

Thank you for pointing this out. Due to the space limitation, we had to move the path definitions and notations to supplementary material. We understand the confusion, and will make sure to include brief explanations in the paper. Please also see our response to Question 2.

W4:

This discrepancy appears to be a PDF rendering issue. We confirm that AP refers to atomic propositions and that $\mathtt{A}$ denotes the corresponding set.

W5:

We represent the $\varepsilon$-action being taken with an integer $q_{\epsilon}$, which denotes the automaton state reached via the $\varepsilon$-transition associated with that action. We also have a more detailed description of LDBAs and $\varepsilon$-transitons in the supplementary file. We could not explain in detail due to space limitations, but we understand this could be confusing and we will update the manuscript accordingly.

W6:

We included an intuitive explanations of LDBAs via soft labels in our response to Question 2. We hope this helps.

W7:

Thank you for catching this. It was a leftover sentence fragment.

W8:

We address this by introducing Theorem 2, which provides a formal approximation bound between discrete and differentiable rewards (please also see our response to Question 1). We hope this helps strengthen the formal justification of our core contribution.