Reward Machines for Deep RL in Noisy and Uncertain Environments
Authors: Andrew C Li
Zizhao Chen
Toryn Q. Klassen
Pashootan Vaezipoor
Rodrigo Toro Icarte
Sheila A. McIlraith
Venue: NeurIPS 2024 poster (2024)
Keywords: Reward Machines
LTL
Linear Temporal Logic
Automata
RL
Reinforcement Learning
Formal Language
Primary area: reinforcement_learning
TL;DR: We investigate the use of Reward Machines in deep RL under an uncertain interpretation of the domain-specific vocabulary.

Abstract: Reward Machines provide an automaton-inspired structure for specifying instructions, safety constraints, and other temporally extended reward-worthy behaviour. By exposing the underlying structure of a reward function, they enable the decomposition of an RL task, leading to impressive gains in sample efficiency. Although Reward Machines and similar formal specifications have a rich history of application towards sequential decision-making problems, prior frameworks have traditionally ignored ambiguity and uncertainty when interpreting the domain-specific vocabulary forming the building blocks of the reward function. Such uncertainty critically arises in many real-world settings due to factors like partial observability or noisy sensors. In this work, we explore the use of Reward Machines for Deep RL in noisy and uncertain environments. We characterize this problem as a POMDP and propose a suite of RL algorithms that exploit task structure under uncertain interpretation of the domain-specific vocabulary. Through theory and experiments, we expose pitfalls in naive approaches to this problem while simultaneously demonstrating how task structure can be successfully leveraged under noisy interpretations of the vocabulary.

Reward Machines for Deep RL in Noisy and Uncertain Environments
Andrew C.
Zizhao Chen' Cornell University
Toryn Q. Klassen University of Toronto Vector Institute
University of Toronto Vector Institute
Pashootan Vaezipoor
Rodrigo Toro Icarte
Sheila A. Mcllraith University of Toronto Vector Institute
Georgian.io Vector Institute
Pontificia Universidad Católica de Chile Centro Nacional de Inteligencia Artificial
Abstract
Reward Machines provide an automaton-inspires structure for specifying instruc- tions, safety constraints, and other temporally extended reward-worthy behaviour. By exposing the underlying structure reward function, they enable the decom- position of an RL task, leading impressive gains in sample efficiency. Although Reward Machines and similar formal specifications have a rich history ap- plication towards sequential decision-making problems, prior frameworks have traditionally ignored ambiguity and uncertainty when interpreting the domain- specific vocabulary forming the building blocks of the reward function. Such uncertainty critically arises in many real-world settings due to factors like partial observability noisy sensors. In this work, we explore the of Reward Machines for Deep RL in noisy and uncertain environments. We characterize this problem POMDP and propose suite of RI. algorithms that exploit task structure under uncertain interpretation of the domain-specific vocabulary. Through theory and experiments, we expose pitfalls in naive approaches this problem while simultaneously demonstrating how task structure can be successfully leveraged under noisy interpretations of the vocabulary.
Code and videos are available at bttts::/ggithbe wttp:ttww..mmm//ddeee.1111111//. sowarddmaachines-oliss eonvonerroneneenneettt
Introduction
Formal languages, including programming languages such as Python and C, have long been used for objective specification in sequential decision making. Using a vocabulary of domain-specific properties, expressed propositional variables, formal languages like Linear Temporal Logic (LTL) [4 capture complex temporal patterns- as the objectives of an agent-by composing variables via temporal operators and logical connectives. These languages provide well-defined semantics while enabling semantics- preeetcci- transformations to normal-form representations such as automata, which expose the discrete structure underlying an objective decision-making agent. One such representation is the increasingly popular Reward Machine, which combines expression of rich temporally extended (non-Markovian) objectives via automata with algorithmic techniques such as automated reward shaping, task decomposition, and counterfactual learning updates to gamerr
WWor done while at the University of Toronto. Also affiliated with the Schwartz Reisman Institute for Technology and Society. Correspondence andrevli@ca. toronto. edu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Importantly, Reward Machines can be specified directly, constructed via translation from any regular language (including variants of I.TL.,, synthesized from high-level planning specifications, or learned from data 77] For these reasons, formal languages, and in particular, Reward Machines, have been adopted across a diversity
significant improvements in sample efficiency (e.g., [52 54 18
of domains, ranging from motion planning (30 15
50] and robotic manipulation [8] |6 31 to, more
recently, general deep Reinforcement Learning RR)) problems [e.g..
34
35
37
52
53
21 64 29
61 32 22
62,
63
17 46
28
49
59
66
I0
38 18
48
65
58
55
Importantly, formal language frameworks for deep RL require an interpretation of the domain- -peccicc vocabulary grounded in the RL environment. This is captured by a labelling function, mapping from environment states to the truth or falsity of abstract propostions that constitute the building blocks of objective specifications. However, practical real-world environments are often partially observable and rely on high-dimensional sensor data such as images. As result, labelling functions are, by necessity, noisy and uncertain, compromising the application of formal languages such as Reward Machines or L.TL for objective specification. Consider an autonomous vehicle, whose desired behaviour at intersection can be formally specified using temporal logic [5] 39] In the real world, key determinations-whethee a pedestrian is crossing, the colour of the light, the intent of other vehicles, and so on-must be made based on noisy obstructed LiDAR and camera sensors, and may therefore be noisy or uncertain themselves. To address this problem, while benefiting from the advantages of Reward Machines, we make the following contributions.
(1) We propose a deep RL framework for Reward Machines in settings where the evaluation of domain-specific vocabulary is uncertain, characterizing the RL problem in terms of a POMDP. To our knowledge, this is the first deep RL. framework for Reward Machines that broadly supports the imperfect detection of propositions, allowing us to extend Reward Machines to general partially observable environments.
(2) We propose and analyze a suite of RL algorithms that exploit Reward Machine structure under noisy and uncertain interpretations of the vocabulary. We show how preexisting abstraction models- noisy estimators of abstract, task-relevant features that may manifest as pretrained neural networks, sensors, heuristics, or otherwise can be brought to bear improve learning efficiency.
(3) We theoretically and experimentally evaluate our proposed RI. algorithms. Theoretically, we discover pitfall of naively leveraging standard abstraction models namely. that errors from repeated queries of a model are correlated rather than i.i.d. We show that this can have serious ramifications, including unintended or dangerous outcomes, and demonstrate how this issue can be mitigated. Experimentally, we consider a variety of challenging domains involving partial observability and high-dimensional observations. Results show that our algorithms successfully leverage task structure to improve sample efficiency and total reward under uncertain interpretations of the vocabulary.
2 Background
Notation. Given set of random variables, X, AX is the set of distributions over X; (-) denotes particular distribution; and for a categorical distribution Ø E AX and some x E X, we denote G[œ] as the probability of z under w. We use Tı.j as a shorthand for the sequence F;, JT..
POMDPs. A Partially Observable Markov Decision Process (POMDP) (S. A, w. B is defined by the state space S, observation space O action space A. reward function R. transition distribution P: S x A + AS, observation distribution w : + AO, and initial state distribution E AS. An episode begins with an initial state 81 ~ n(()) and at each timestep 1 2 1, the agent observes an observation o ~ ((x)). performs an action a E A, transitions to the next state 8141 P(st, a,), and receives reward r2- R(5t, azs St+1) ). Denote the agent's observation-action history at time t by ht = (0), .......,,,-1,. a;-1, 0r) and the set of all possible histories as H. A fully observable Markov Decision Process (MDP) serves observation at each time t is 0t St-
important special case where the
Reward Machines. A Reward Machine (RM) 52 is formal automaton representation of a Mar-Marnovian reward function that captures temporally extended behaviours. Formally, an RM R = (U, u1, F,AP, 5,),,, where U is finite set of states, #1 E U is the initial state, F is a finite set of terminal states (disjoint from U), AP is a finite set of atomic propositions representing the occurrence of salient events in the environment, d U 2 AP + (U UUP F)) is the state-transition
2

---

function, and 6, U x 2AP - R is the state-reward function. Each transition in an RM is labelled with a scalar reward along with a propositional logic formula over AP, while accepting states represent task termination.
Labelling Function.
While RM captures the high-level structure of non-Markovian reward function, concrete rewards in an environment are determined with the help of labelling function C: S A S + 24P,, a mapping that abstracts state transitions ( 1,-1, Sx) in the environment to the subset of propositions that hold for that transition. To obtain rewards, the sequence of environment states and actions $1, 01...... St, at, $(41 are labelled with propositional evaluations 01: where o; [(s,, Og 8;-1) E 2AP.. A sequence of transitions in the RM are then followed based on o1 to produce the reward sequence f14. In an MDP environment, rewards specified by an RM are Markovian over an extended state space S x U: hence, there is an optimal policy of the form T (ag) 18,, we) where Uy E U is the RM state at time [52]. During execution, u4 can be recursively updated given u by querying L after each environment transition.
3 Problem Framework
3.1 Formalization
Agent
We formalize the problem of solving an RM task under an uncertain interpretation of the vocab- ulary. Consider an agent acting in a POMDP environment (without the reward function) & (S, O, A, P. w. uu). We define rewards ri based on an RM R (U, u1, F, AP, 8u, 6.) inter- preted under a ground-truth labelling function C: S Ax S + 2AP as described in Section 2
Rlward Machine
Abstraction Modil
Croundiiaas expesatooe
Ocservation
Action
Lubelling Function
Environment
DO
An important aspect of our framework is that L is not made accessible to the agent. Instead, we make the weaker assumption that the agent can query an abstraction model .M H - Z. Here, M captures the agent's 's preexisting knowl- edge over how set of high-level features Z are grounded within the environment. Abstraction models are easier to obtain than ground-truth labelling functions for several reasons: they take as input observable histories H rather than states S, they can map to any feature space Z, and crucially, we allow their outcomes to be incorrect or uncertain. Note that the definition of abstraction models is quite general-in in the real world, they might manifest as pretrained foundation models 14]. sensors [6]. task-specific classifiers 20). or so on.
The Noisy Reward Machine Environment framework. Blue elements highlight differences with respect to a standard RL framework. Dashed lines (----) ) indicate that element is required during training but not deployment.
Figure 1:
45 36
Noisy Reward Machine Environment (depicted in Figure I. Given P, our goal is to obtain a policy (aal/he =1:e) based on observations and outputs from the abstraction model up to time & that maximizes the expected discounted return Ex,, 12 7'r.] for some discount factor 7 E (0, I]. In this work, we assume x is trained via RL, and we assume that the ground-trute truth rewards r; are observable during training only. Notably, the trained policy и can be deployed without access to the ground-trum truth labelling function L.
We refer to the tuple P (E, R. M)
3.2 Running Example
The Gold Mining Problem (Figure 2 serves as running example of Noisy RM Environment. A mining robot operates in a grid with a Mar-oaion goal: dig up at least one chunk of gold ( and deliver it to the depot ). The environment is MDP where the robot observes its current grid position and its actions include moving in the cardinal directions and digging. A labelling function L with grid states and actions as follows: holds when the robot digs in the rightmost row, and holds when the robot is at the bottom-left cell.
associates the propositions AP
However, the robot does not have access to L and cannot reliably distinguish gold from iron pyrite. Thus, it cannot ascertain whether it has obtained gold during the course of an episode. Luckily, the robot can make an educated guess to whether cell contains gold, which is captured by an
3

---

0.8
0.8
(0)
2111)
2222)
0
0.6
0
0.8
0
0.8
(o/w, 0)
(o/w.0)
Figure 2: The Gold Mining Problem is Noisy RM Environment where the agent's interpretation of the vocabulary is uncertain. Leftt: The four rightmost cells yield gold second column yield iron pyrite, which has no value. The agent cannot reliably distinguish between the two metals-celle are labelled with the probability the agent believes it yields gold. Right: The RM emits a monn-Maroovian) reward of for collecting gold and delivering the depot
while two cells in the
abstraction model M : H + [0, 1] mapping the robot's current position (while ignoring the rest of the history) to its belief that the cell contains gold.
Note that if the agent could observe L. then could learn an optimal Markovian policy x(a (st uz) with relatively simple form (u, is easily computed with access to C). Intuitively, such a policy should collect gold while in RM state u and head to the depot while in RM state u()), Unfortunately, when the agent does not have access to C. we cannot directly learn a policy with the simpler Markovian form above. In the following sections, show how the agent's noisy belief captured by the abstraction model M can be leveraged to simplify the learning problem.
Noisy RM Environments as POMDPs
We start with an analysis of the Noisy RM Environment framework, contrasting it with a standard RM framework. We ask: (1) What is the optimal behaviour in Noisy RM Environment? (2) How does the abstraction model M affect the problem? (3) How does not observing the ground-trute labelling funetion L affect the problem? We provide proofs for all theorems in Appendix A
Observe that uncertainty in the propositional values is only relevant insofar as influences the agent's belief about the current RM state ti, since rewards from an RM R are Markovian over extended states (&t, we) E U. Our first result is that a Noisy RM Environment (E, R. L, M) can be reformulated into equivalent POMDP with state space S x U and observation space O (Theorem 4.1. Here, we say two problems are equivalent if there is bijection between policies for either problem such that the policies have equal expected discounted return and behave identically given the same history h-- Thus, optimal behaviour in a Noisy RM Environment can be reduced to solving a POMDP.
Theorem 4.1 Noisy RM Environment (E, R., L,M) is equivalent to a POMDP over state space S U and observation space O.
One may notice that the abstraction model M doesn't 't appear in the POMDP reformulation all. We later show that an appropriate choice of M can improve policy learning in practice, but this choice ultimately does not change the optimal behaviour of the agent (Theorem 4.2).
Theorem 4.2 (Does the choice of M affect optimal behaviour?) Let P be Noisy RM Environment (E, R. C, M)) and P' be a Noisy RM Environment (E, R, C, M'). Then P and P' are equivalent.
We also contrast our proposed framework, where the agent does not have direct access to C, with prior RM frameworks where the agent does. We show that this difference does not affect the optimal behaviour in MDP environments, but can affect the optimal behaviour in POMDPs (Theorem
Theorem 4.3 (Does observing L affect optimal behaviour?) Let P be a Noisy RM Environment (E, R, L, M)). Consider a problem P' that is identical to P except that the agent at time t additionally observes L(st. 04, S1+1) after taking action a, in state st. If & is an MDP, then P and P' are equivalent. If is a POMDP, P and P' may be -oniequivl..nt.

---

Method
In this section, consider how train policies that do not require the ground-truth labelling func- tion L act. Given Theorem 4.1 in principle we can apply any deep RL approach suitable for POMDPs, such as recurrent policy that condi- tions on past actions and observations. However, such a learning algorithm may be inefficient as it doesn't It exploit the known RM structure at all. Motivated by the observation that the RM state ue is critical for decision making, instead pro- pose a class of policies that decouple inference the RM state Ue (treated
Input: Inference module f: Z 7 AU.
Abstraction model M H Z,
Initialize policy π x AU AA. for each episode do
Observe 01
h1 < (01)
for each time / 2,,
Uy f(
Exccute action on I(- h2 uz). Get reward r; and observation o++1-
unknown random variable) and decision making into two separate modules (Algorithm(]) )
Update π using RL.
h441 + h + (at, 0t+1)
The inference module models belief ü, AU of the current RM state over the course of an episode with the help of an abstraction model M. More precisely, the inference module is function f: Z + AU mapping the history of outputs from the abstraction model to belief over RM states. The inference objective is to recover the (policy-independent) distribution Pr(ue]/e), marginalized over all possible state trajectories T = ($), al....,,........................ St-1, 1,,
Algorithm 1: On-policy RL that decouples RM state inference using an abstraction model M and decision making.
Pr(ue(he)
Pr(ue)T))(T ho)dT
Here (T)) is deterministic-it is the RM state given the trajectory (under the ground-truth labelling functioo)-while the probability density function p(T, (h,) depends on the POMDP transition function and observation probabilities. The decision massinnnmaking module a policy т T(ae (h, in) that then leverages the inferred belief it Below, describe three inference modules that leverage different forms of abstraction models M : H - Z to predict ūt
5.1 Naive
Suppose that in lieu of the ground-truth labelling function L, we have a noisy estimator of L that predicts propositional evaluations based on the observation history. This is captured via an abstraction model of the form M H + 24P that makes discrete (and potentially incorrect) predictions about the propositions (( ( 8t) that hold at time L, given the history ht Then, we can recursively model a discrete prediction of the RM state ûn U (which can be seen belief over U with full probability mass on úe) using outputs of M in place of L.
Method 1 (Naive) Given M H 2AP, predict discrete RM state 0e U follows. Set à = M1. For t > 1, predict ûe =
weakness of this approach is that it does represent the uncertainty in its prediction. Furthermore, since RM state predictions are updated recursively, an eтror when predicting ù, will propagate to all future predictions (u++1, dc.2....).
Example 5.1 Returning to the running example, suppose the agent uses its belief of locations yielding gold to derive an abstraction model M H + 2AAP For a history h,, M takes the current grid position 8, and predicts is true if it believes there is at least a 50% chance it yields gold when performs a digging action. We assume the agent can always predict A correctly. Observing Figure 2 see that M agrees with L in all cases except one cell where there is actually iron pyrite (that the agent believes has gold with 0.6 probability). Given a trajectory where the agent mines at this cell, Naive would erroneously assume gold was obtained.
5.2 Independent Belief Updating (IBU)
In order to capture the uncertainty in the belief over the RM state wt, one may instead wish model probability distribution ü, AV. Given abstraction model of the form M H + A22 that
5

---

Table I: Comparison of inference modules. For each, we highlight its prerequisite abstraction model, the target feature the abstraction model aims to predict, and its consistency in MDPs and POMDPs.
INFERENCE MODULE
ABSTRACTION MODEL
TARGET
CONSISTENT (MDPs)
CONSISTENT (POMDPS)
NAIVE IBU
H 2AP H + A(2AP)
11- 1(
X
TDM
AU
U
predicts probabilities over possible propositional evaluations ((st-1, (t-1, enticing approach to derive üe by probabilistically weighing all possible RM states time / according to the
previous belief ū along with all possible evaluations of [(s ax-1, st) according to M.
Method 2 (IBU) Given M H - A(2AA), predict a distribution over RM states ūn E AU as {un}. For f 1, set
follows. Set ūn [wn] 1 and ūn ju] for
üg [x]]
Σ
10,("', = u] u M(h))lo)
0 E'EU
On the surface, IBU may appear to solve the error propagation issue of the Naive approach by softening discrete belief into probabilistic one. Surprisingly, updating beliefs üe in this manner can still result in a belief that quickly diverges from reality with increasing t. This is because IBU fails to consider that propositional evaluations ūy aggregates queries to M, noise in the outputs of M can dramatically amplify the correlation between these noisy outputs is not considered. This is best illustrated by example.
linked, rather than independent. Since the computation of
Example 5.2 The mining agent now considers a probability distribution over propositional assign- We assume the agent always perfectly determines and applies its belief of
ments of locations yielding gold; e.g., digging in the cell the agent believes has gold with 0.3 probability yields the distribution (0 0.7, } 0.3,
0). Consider a trajectory where the agent digs at this cell multiple times. After mining once, IBU updates the RM state belief ü, to reflect 0.3 probability of having obtained gold. After mining twice, this increases to 0,51 and in general, the belief reflects 1 0.7* probability after mining & times. In reality, mining more than once this square should not increase the probability beyond 0.3 since all evaluations of at that cell are linked they are all true, or they are all false.
:0
5.3 Temporal Dependency Modelling (TDM)
Example 5.2 demonstraasss a challenge when aggregating multiple predictions from a noisy classifier- the noise may be correlated between evaluations. One solution in the Gold Mining Problem is to update the RM state belief only the first time the agent digs at any particular square, accounting for the fact that all evaluations of in that state yield the same result. Indeed, this type of solution is used by many approaches in tabular MDPs with noisy propositional evaluations [19 66), but this solution does not scale to infinite state spaces where propositional evaluations may be arbitrarily linked between "similar" pairs of states.
We instead consider an inference module that uses abstraction model M H. - AU designed to directly predict a distribution over RM states given the history. Such an abstraction model might manifest meta-classifie that aggregates outputs from another model but corrects for the correlation in these outputs. Another way to obtain M is to train a recurrent neural network [27 end-to-end given dataset of histories h, and their associated (ground-truth) RM states u4 Given an abstraction model M H + AU, TDM simply returns the output of M.
Method 3 (TDM) Given an abstraction model of the form M: - AU predict M(he) directly.
5.4
Comparison of Inference Modules
At first glance, it may seem challenging to compare different inference modules since they may operate under different abstraction models. Our goal is to elucidate the relatives advantages of each approach to better inform its use. We begin by considering a theoretical property of inference modules,

---

Figure 3: Traffic Light (top left) and Kitchen (bottom left), are MiniGrids with image observations, where key propositions partially observable. Colour Matching (right) is MuJoCo robotics environment where the agent must identify colour names by their RGB values to solve a task.
with our conclusions summarized in Table We consider how accurately an inference module models its target distribution Pr(w,]he) [4).. This largely depends the veracity of the abstraction model M, but nonetheless, is desirable that the inference module precisely recovers Pr(ue(hx) under an ideal abstraction model M If this is possible, then say that an inference module is consistent.
Definition 5.3 (Consistency) Consider an inference module f Z - AU. f is consistent if there exists some M + Z such that for every history he running on h2 using M as the abstraction model results in the belief Pr(u, h2).
In the case that & is MDP, Naive, IBU, and TDM all consistent since there exists abstraction model that can recover the ground-truth labelling function L (for Naive and IBU) and (for TDM) with certainty. However, in the general case when is POMDP, only TDM remains consistent. Proofs and counterexamples are provided in Appendix A
Experiments
Our experiments assess the approaches in Section 5 in terms of RL sample efficiency and final total return, as well as accuracy in predicting belief over RM states. We examine whether these methods robust to uncertainty in the outputs of abstraction models, and whether they offer advantages end-to-end RL algorithms that do not attempt to exploit task structure. Our experimental settings involve challenges that arise when scaling complex, real-world environments: temporally extended reasoning, partial observability, high-dimensional observations, and sparse rewards.
6.1 Environments
Our environments include the Gold Mining Problem toy environment, along with two MiniGrid [ environments with image observations and a MuJoCo robotics environment (Figure 3 Full details the environments provided in Appendix B
Traffic Light is partially observable MiniGrid where the agent must drive along road pick up a package and then return home. A traffic light along the road cycles between green, yellow, and red at stochastic intervals and the agent receives delayed penalty it runs the red light. The agent only has forward-facing camera and it can drive forwards, backwards, wait, make a U-turn. We encode this task with an (Figure 7) with propositions for running a light, collecting the package, and returning home. Crucially, the agent does not observe the light colour when entering the intersection in reverse, causing the agent to uncertain about the evaluation of the red light proposition.
Kitchen is partially observable MiniGrid where a cleaning agent starts in the foyer of home and is tasked with cleaning the kitchen before leaving, There three chores: the agent must make sure the dishes are washed, the stove is wiped, and the trash is emptied, but not every chore necessarily requires action from the agent (e.g. there might be no dirty dishes begin with). However, the agent doesn't 't know how clean the kitchen is until it enters it. For each chore, proposition represents whether that chore is "done" (e.g. the dishes are clean) in the current state of the environment-thhss the propositional evaluations are unknown to the agent until it enters the kitchen. The RM for this task (omitted due its size) uses the automaton state encode the subset of chores that are currently done and gives reward of for leaving the house once the kitchen is clean.
7

---

Gold Mining
Traffic Light
Kitchen
Colour Matching
2.0
200
0.8
0.5
1.5
1.5
Retum
0.4
1.0
0.5
0.5
0.0
-0.2
0.0
Steps (millions)
Steps (millions)
Steps (million)
Steps (milions)
Oracle
Memory only
TDM
IBU
Naive
Figure 4: RL curves averaged over 8 runs (shaded regions show standard error). TDM performs well all domains, the absence of the ground-truth labelling function, while Recurrent PPO fails.
In Colour Matching, the agent controls a robot car while observing LiDAR and RGB observations of nearby objects. The agent observes an instruction with the name of a colour (e.g. "blue") and must touch only that pillar and then enter the portal. Propositions for each pillar evaluate whether the agent is touching it. The colours of the pillars (and in the instruction) are randomized from set of 18 possible colours in each episode, so to reliably solve the task, the agent must learn the correct associations of colour names their RGB values.
6.2 Baselines
We consider the methods Naive, IBU, and TDM from Section 5 that use the abstraction models described below. For RL experiments, we baseline against a Memory-only method for general POMDPs that does not exploit the RM structure. As upper bound on performance, against an Oracle agent that has access to the ground-truth labelling function. the toy Gold Mining Problem, policies are trained using Q-learning (5I) with linear function approximation 40). In all other domains, policies are neural networks trained with PPO 47, and the Memory-only policy is Recurrent PPO 25). popular state-of-the-ar deep RI method for general POMDPs.
compare
6.3 Abstraction Models
In the Gold Mining Problem, we consider toy abstraction models based on the probabilities in Figure 2 as described in the running examples. TDM is equivalent to IBU except only updates the RM state belief when digging for the first time at the current cell.
In all other domains, abstractions models are neural networks trained via supervised learning. We collect training datasets comprising 2K episodes in each domain (equalling 103K interactions in Traffic Light, 397K interactions Kitchen, and 3.7M interactions in Colour Matching), along with validation and test datasets of 100 episodes each. This data is generated by a random policy and labelled with propositional evaluations from and ground-trute -tuth RM states. To obtain abstraction models, we train classifiers on their respective target labels and we select optimal hyperparameters We note that all abstraction models are trained on equivalent data,
according to a grid search] [ ensuring a fair comparison between different inference modules. To verify that abstraction models are indeed noisy, we use the test set to evaluate the precision and recall of classifier trained to predict propositional evaluations (Figure (). We find that key propositions towards decision making, such as running a red light in Traffic Light, or whether the chores are done in Kitchen, are uncertain.
6.4 Results: Reinforcement Learning
We report RL learning curves for each method and environment in Figure The key results are: (R1) TDM performs well all domains. Using only a noisy abstraction model, TDM achieves similar sample efficiency and final performance to the Oracle agent that has access to the ground truth.
For RL training on Traffic Light and Kitchen, we continue to finetune the abstraction models using data collected by the policy- this is to verify that partial observability is difficult to handle even with virtually unlimited data and no distributional shift.
8

---

Gold Mining
Traffic Light
Kitchen
Colour Matching
-0.2
Log likelhhodd
-0.5
-.5
-0.8
-0.4
-1.0
0.6
-1.0
2.5
-3.0
-1.4
TDM
Naive
IBU
Figure 5: Accuracy of inference modules measured by log- likelihood (higher better) of the true RM state, averaged over 8 runs with lines showing standard error. TDM predicts the R.M state belief more accurately than Naive and IBU.
(R2): RL makes little progress on any domain when the task structure is not exploited. Specifi- cally, Memory only (recurrent PPO in the deep RL environments) fails since it does not leverage the temporal and logical structure afforded by the RM.
(R3): The performance of Naive and IBU depends on the specific environment. When the simplifying assumptions made by Naive IBU are reasonable, these approaches can perform well. However, the use of these approaches under noisy abstraction models can also lead to dangerous or unintended outcomes (see Appendix [B.5 for discussion).
We now highlight the most notable qualitative behaviours that were observed. For more in-depth discussion, refer to Appendix B.5 In Gold Mining, Naive often digs at the nearby cell believed to yield gold with 0.6 probability (but in actuality yielding iron pyrite) before immediately heading to the depot, and IBU repeatedly digs at the same cell increase its belief of having obtained gold. On the other hand, TDM adopts a robust strategy of mining at multiple different cells to maximize its chance of having obtained gold. In Traffic Light. Naive often runs the red light by driving in reverse to get through the intersection faster. This shortcoming stems from its inability to represent uncertainty about running the red light. In Kitchen, IBU often stays in the foyer without ever entering the kitchen. Despite this, the RM state belief erroneously reflects that all chores have a high probability of being done. This similar Example -.2 each chore is initially "clean" with some small probability, and this is compounded over time by the incorrect independence assumption. In reality, the state of the chore is linked between timesteps (and doesn't change unless the agent intervenes).
6.5 Results: RM State Belief Inference
We compare the inference modules Naive, IBU, and TDM in terms of their predictive accuracy of the RM state (Figure 5). We evaluate each approach on test set of 100 fixed trajectories generated by a random policy (following the same distribution the data used to train the abstraction models), Since each inference module aims to capture belief, we evaluate them according to the log-likelihood of the true RM state under the belief, averaging when Naive makes an incorrect prediction, we lower bound all log- ligeeiiooosods at 0.01.
the predictions at all timesteps. To avoid log 0
(R4): TDM is more accurate when predicting a belief over RM states compared to Naive or IBU on all domains.
6.6 Results: Vision-Language Models as Zero-Shot Abstraction Models
As an additional experiment, assess whether GPT-4o serve as effective zero-shot abstraction model in the Traffic Light domain. We render RGB images of the environment and use GPT-40 to evaluate propositions described through text. With this abstraction model, we evaluate Naive and IBU on the test set from Section 6.3 We baseline these against the inference modules from Section 6.3 that abstraction models trained via supervised learning, well abstraction models with randomly initialized weights. Results and further details are provided in Figure & of the Appendix.
(R5): GPT-4o is an effective zero-shot abstraction model for Naive and IBU. As abstraction model, GPT-4o is nearly as effective as custom model trained from ground-truth data, and is significantly more effective than randomly initialized neural network.

---

7
Related Work
Many recent works leverage structured task specifications such as RMs or Linear Temporal Logic (I.TI.) in deep RI. However, the vast majority of these works do not consider the effects of error or uncertainty in the labelling function. We note a few works that explicitly avoid the assumption of an oracle labelling function. Kuo et al. [32] solve LTL tasks by encoding them with recurrent policy, Andreas et al. [2] and Oh et al. [43] learn modular subpolicies and termination conditions, avoiding the need for labelling function, but these approaches are restricted to simple sequential tasks.
Some recent works have considered applying formal languages to deep RL under a noisy evaluation of propositions. Nodari and Cerutti [42] empirically show that current RM algorithms are brittle to noise the labelling function but do not offer a solution. Tuli al. [66] teach an agent to follow L.T. instructions in partially observable text-based games using the Naive method, but only consider propositions that are observable to the agent. Umili et al. (57) use RMs in visual environments with a method similar to IBU, while Hatanaka et al. [24] update a belief over L.TL. formulas using IBU, but only update the belief at certain time intervals. While these last three works offer solutions that tackle noise for a specific setting, they do not consider the efficacy of these methods more generally. Hence, we believe our framework and the insights from this paper will provide a useful contribution.
Despite the large corpus of prior work in fully observable settings, RMs and LTL have rarely been considered for general partially observable deep RL problems. We believe this is due to the difficulty of working with an uncertain labelling function when propositions are defined over partially observed state. The closest work by Toro learte al. 5 applies RMs to POMDPs but only considers propositions defined as function of observations.
LTL has long been used for specification in motion planning 33 and some works consider an uncertain labelling function or partial observability. However, solutions nearly always depend on a small, tabular state space, while we focus on solutions that scale to infinite state spaces. Ding et al. [3] propose an approach assuming that propositions in a state occur probabilisticaly in an i.i.d. manner. Ghasemi al. [99, Verginis et al. 660, Hashimoto et al. [23], and Cai et al. [6] consider a setting where propositions are initially unknown but can be inferred through interactions.
8 Conclusion
This work introduces a framework for Reinforcement Learning with Reward Machines where the interpretation or perception of the domain-specific vocabulary is uncertain. We propose a suite of algorithms that allow an RL agent to leverage the structure the task, as exposed by the Reward Machine, while exploiting prior knowledge through the use of abstraction models- preexisting models that noisily ground high-level features into environment. Through theory and experiments, show the pitfalls of naively aggregating outputs from noisy abstraction model, while simultaneously demonstrating how abstraction models that are aware of temporally correlated predictions can mitigate this issuc. Ultimately, our techniques successfully leverage task structure to improve sample efficiency while scaling to environments with large state spaces and partial observability.
On the topic of societal impact, our work aims ameliorate the impact of uncertain interpretations of symbols, which can lead to dangerous outcomes. We note that our proposed methods elucidate process of RL agents within a formal framework, potentially providing enhanced interpretability. A limitation of TDM, our best-performing method, is that it relies task-specifi abstraction model (to predict the state in the specific RM). For some real-world tasks, might not be possible to get enough training data to learn accurate abstraction models (some RM transitions might very rarely be observed), so deploying TDM could lead to poor outcomes.
the internal
Our experiments show the promise of leveraging pretrained foundation models (e.g., GPT-4o) as general-purpose abstraction models in Reward Machine framework. Two of our proposed methods, Naive and IBU, can employ such models directly in many settings where text or image descriptions of the environment are available. further investigation on the integration of Reward Machines and foundation models is left to future work. Another promising direction is to relax the assumption of access to ground-truth rewards-reward given by the RM under the ground- truth evaluation of propositions-durin training.
10

---

Acknowledgements
We gratefully acknowledge funding from the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canada CIFAR AI Chairs Program, and Microsoft Research. The second-to- last author also acknowledges funding from the National Center for Artificial Intelligence CENIA FB210017 (Basal ANID) and Fondecyt grant 1230762. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute for Artificial Intelligence (https: http://veetoonnnnttee as/partnershipa/ Finally, we thank the Schwartz Reisman Institute for Technology and Society for providing a rich multi-disciplinary research environment.
An earlier of this work 33 appeared in the NeurlPS 2022 Deep RI. Workshop.
References
[1] Derya Aksaray, Austin Jones, Zhaodan Kong, Mac Schwager, and Calin Belta. Q-learning for Robust Satisfaction Signal Temporal Logic Specifications. In Proceedings of the 55th IEEE Conference Decision and Control (CDC), pages
IEEE, 2016.
[2] Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages
[3] Karl Johan Aström. Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10(1):174-2090 1965.
[4] Bowen Baker, 1lge Akkaya, Peter Zhokov, Joost Huizinga, Jie Tang, Adrien Ecoffet, Brandon Houghton, Raul Sampedro, and Jeff Clune. Video pretraining (VPT): Learning to act by watching unlabeled online videos. Advances in Neural Information Processing Systems, 35: 24639-24654, 2022.
[5] Maxime Bouton, Jesper Karlsson, Alireza Nakhaei, Kikuo Fujimura, Mykel Kochenderfer, and Jana Tumova. Reinforcement learning with probabilistic guarantees for autonomous driving. arXiv preprint arXiv: 2019.
[6] Mingyu Cai, Shaoping Xiao, Baoluo Li, Zhiliang Li, and Zhen Kan. Reinforcement learn- ing based temporal logic control with maximum probabilistic satisfaction. In 202/ IEEE International Conference on Robotics and Automation (ICRA), pages 806-812 IEEE, 2021.
[7] Alberto Camacho, Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcllraith. I.TI. and beyond: Formal languages for reward function specification in reinforcement learning. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 6065-6073, 2019.
[8] Alberto Camacho, Jacob Varley, Andy Zeng, Deepali Jain, Atil Iscen, and Dmitry Kalashnikov. Reward machines for vision-bar based robotic manipulation. Proceedings of the 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 14284-14290, 2021.
[9] Maxime Chevalier-Bii -Biisver,, Bolun Dai, Mark Towers, Rodrigo de Lazcano, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry. Minigrid Miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. arXiv preprint arXiv:abs/2306, 13831, 2023.
[10] Jan Corazza, Ivan Gavran, and Daniel Neider. Reinforcement learning with stochastic reward machines. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 6439, 2022.
[11] Giuseppe De Giacomo, Marco Favorito, Luca locchi, Fabio Patrizi, and Alessandro Ronea. Temporal logic monitoring rewards via transducers. In Proceedings of the 17th International Conference on Knowledge Representation and Reasoning (KR), pages 860-870, 2020.
[12] David DeFazio and Shiqi Zhang. Learning quadruped locomotion policies with reward machines. arXiv preprint arXiv:2107.10966 2021.

---

[13] Xu Chu Dennis Ding, Stephen L Smith, Calin Belta, and Daniela Rus. LTL control in uncertain environments with probabilistic satisfaction guarantees. IFAC Proceedings Volumes, 44(1): 3515-3520, 2011.
[14] Yuqing Du, Ksenia Konyushkova, Misha Denil, Akhil Raju, Jessica Landon, Felix Hill, Nando de Freitas, and Serkan Cabi. Vision-language models as success detectors, arXiv preprini arXiv:2303.07280, 2023.
[15] Georgios E Fainekos, Antoine Girard, Hadas Kress-Gazit, and George J Pappas. Temporal logic motion planning for dynamic robots. Automatica, 45(2):343-355) 2009.
[16] Cameron Finucane, Gangyuan Jing, and Hadas language, temporal logic and robot control. In 2010 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1988-1993 IEEE, 2010.
LTLMoP: Experimenting with
[17] Daniel Furelos-Blanco, Mark Law, Alessandra Russo, Krysia Broda, and Anders Jonsson. Induction of subgoal automata for reinforcement learning. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAT), pages 3890-3897, 2020.
[18] Daniel Purelos-Blance Mark Law, Anders Jonsson, Krysia Broda, and Alessandra Russo. Hierarchies of reward machines. In International Conference on Machine Learning, pages 10494-10541. PMLR, 2023.
[19] Mahsa Ghasemi, Erdem Arinc Bulgur, and Ufuk Topcu. Task-oriented active perception and planning in environments with partially known semantics. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
[20] Prasoon Goyal, Scott Niekum, and Raymond Mooney. Using natural language for reward shaping in reinforcement learning. arXiv preprint arXiv: 0903:::990.0000 0903002000, 2019.
[21] Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Logically-constrained reinforcement learning. arXiv preprint arXiv: 1oXi::8800.0009 2018.
[22] Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate. Deep Reinforcement Learning with temporal logics. In Proceedings of the 18th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS), pages 1-22, 2020.
[23] Kazumune Hashimoto, Natsuko Tsumagari, and Toshimitsu Ushio Collaborative rover-copter path planning and exploration with temporal logic specifications based on Bayesian update under uncertain environments. ACM Transactions on Cyber-Physice Systems (TCPS), 6(2):
1-24, 2022.
[24] Wataru Hatanaka, Ryota Yamashina, and Takamitsu Matsubara. Reinforcement learning of action and query policies with LTL. instructions under uncertain event detector. IEEE Robotics and Automation Letters, 2023.
[25] Matthew Hausknecht and Peter Stone. Deep recurrent Q-learning for partially observable MDPs. In 2015 AAAI Fall Symposium series, 2015.
[26] Keliang He, Morteza Lahijanian, Lydia Kavraki, and Moshe Y Vardi. Towards manipulation planning with temporal logic specifications. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 346-352. IEEE, 2015.
[27] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
[28] Yugian Jiang, Suda Bharadwaj. Bo Wu, Rishi Shah, Ufuk Topcu, and Peter Stone. Temporal- logic-based reward shaping for continuing reinforcement learning tasks. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 7995-8003, 2021.
[29] Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani. A composable specification language for reinforcement learning tasks. In Proceedings of the 33dd Conference on Advances Neural Information Processing Systems (NeurIPS), volume 32, pages 13041-13051. 2019.
12

---

[30] Hadas Gazit, Georgios E Fainekos, and George Pappas. Temporal-logic-bssed reactive mission and motion planning. IEEE Transactions on Robotics, 25(6):1370-1381, 2009.
[31] Lars Kunze, Mihai Emanuel Dolha, and Michael Beetz. Logic programming with simulation- based temporal projection for everyday robot object manipulation. In 2011 IEEE/RSJ Interna- lional Conference on Intelligent Robots and Systems, pages 3172-3178. IEEE, 2011.
[32] Yen-Ling Kuo, Boris Katz, and Andrei Barbu. Encoding formulas as deep networks: Rein- forcement learning for zero-shot execution of LTL formulas. In 2020 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pages 5604-5610. IEEE, 2020.
[33] Andrew C Li, Zizhao Chen, Pashootan Vaezipoor, Toryn Q. Klassen, Rodrigo Toro Icarte, and Sheila A. Mcllraith. Noisy symbolic abstractions for deep RL: A case study with reward machines. In Deep Reinforcement Learning Workshop NeurlPS 2022, 2022. URL https
//openreview net wtt.///orrrmdddd/PPPr...
[34] Xiao Li, Cristian loan Vasile, and Calin Belta. Reinforcement learning with temporal logic rewards. In Proceedings of the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3834-3839, 2017.
[35] Xiao Li, Yao Ma, and Calin Belta. A policy search method for temporal logic specified reinforcement learning tasks. In Proceedings of the 2018 Annual American Control Conference (ACC), pages 240-245. IEEE, 2018
[36] Shalev Lifshitz, Keiran Paster, Harris Chan, Jimmy Ba, and Sheila Mcllraith. STEVE-1: A generative model for text-to-behavior Minecraft. arXiv preprint arXiv:2306.0099 2023.
[37] Michael L Littman, Ufuk Topcu, Jie Fu, Charles Isbell, Min Wen, and James MaGGlashan. Environment-ing Eavironment-indeeendenn task specifications via GLTL. arXiv preprint 1rXhv:1704.0434/ 2017.
[38] Jason Xinyu Liu, Ankit Shah, Eric Rosen, George Konidaris, and Stefanie Tellex. Skill transfer for lemporally-extendee task specifications. arXiv preprint arXiv:2206.05090 2022.
[39] Sebastian Maierhofer, Paul Moosbrugger, and Matthias Althoff. Formalization of intersection traffic rules in temporal logic. In 2022 IEEE Intelligent Vehicles Symposium (IV), pages 144. IEEE, 2022.
[40] Francisco S Melo and M Isabel Ribeiro. Q-learning with linear function approximation. In International Conference on Computational Learning Theory, pages 308-322. Springer, 2007.
[41] Cyrus Neary, Zhe Xu, Bo Wu, and Ufuk Topcu. Reward machines for cooperative multi-agent reinforcement learning. Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 934-942, 2021.
[42] Lorenzo Nodari and Federico Cerutti. Assessing the robustness of intelligence-driven reinforce- ment learning. In 2023 IEEE International Workshop on Technologies for Defense and Security (TechDefense), pages 439-443, IEEE, 2023.
[43] Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmect Kohli. Zero-shot Task Generalization with Multi-Task Deep Reinforcement Learning. In International Conference on Machine Learning, pages 2661-2670. PMLR, 2017.
[44] Amir Pnueli. The temporal logic of programs. In 18th Annual Symposium on Foundations of Computer Science (sfes 1977), pages 46-57. IEEE, 1977.
[45] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pages 7748-8765. PMLR, 2021.
[46] Gavin Rens and Jean-François Raskin. Learning non-Markovian Reward Models MDPs. arXiv preprint arXiv:2001.09299 2020.
13

---

[47] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.0634, 2017.
[48] Ameesh Shah, Cameron Voloshin, Chenxi Yang, Abhinav Verma, Swarat Chaudhuri, and Sanjit A Seshia. Deep policy optimization with temporal logic constraints. arXiv preprint arXiv:2404. / 1578, 2024.
[49] Ankit Shah, Shen Li, and Julie Shah. Planning with Uncertain Specifications (PUnS), IEEE Robotics and Automation Letters, 5(2):3114 3421, 2020.
[50] Xiaowu Sun and Yasser Shoukry. Neurosymbolic motion and task planning for linear temporal logic tasks. IEEE Transactions Robotics, 2024.
[51] Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. MIT press, second edition, 2018.
[52] Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In Proceedings of the 35th International Conference Machine Learning (ICML), pages 2107-2116, 2018.
[53] Rodrigo Toro Icarte Ethan Waldie, Toryn Q. Klassen, Rick Valenzano, Margarita P. Castro, and Sheila Mcllraith. Learning reward machines for partially observable reinforcement learning. In Proceedings of the 33nd Conference Advances in Neural Information Processing Systems (NeurIPS), pages 15497-15508, 2019.
[54] Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. Mcllraith. Reward machines: Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73:173-7177 173-208, 2022.
[55] Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, Margarita P. Castro, Ethan Waldie, and Sheila A. Mcllraith. Learning reward machines: A study in partially observable reinforce- ment learning. Artificial Intelligence, 323: 103989, 2023. doi:
URL https: org/ 10. 1016/j artint. 2023. 103989
[56] Mathicu Tuli, Andrew C. Li, Pashootan Vaczipoor. Toryn Q. Klassen, Scott Sanner, and Sheila A. Mcllraith. Learning to follow instructions text-based games. In Proceedings of the 36rd Conference on Advances in Neural Information Processing Systems (NeurIPS), 2022.
[57] Elena Umili, Francesco Argenziano, Aymeric Barbin, Roberto Capobianco, et al. Visual reward machines. In Proceedings of the 17th International Workshop on Neural-Symbolic Learning and Reasoning, La Certosa di Pontignano, Siena, Italy, pages 3-5, 2023.
[58] Pashootan Vaezipoor, Andrew Li, Rodrigo Toro Icarte, and Sheila Mcllraith. LTL2Action: Generalizing LTL instructions for multi-task RL. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 10497-10508, 2021.
[59] Alvaro Velasquez, Andre Beckus, Taylor Dohmen, Ashutosh Trivedi, Noah Topper, and George Atia. Learning probabilistic reward machines from non-Markovian stochastic reward processes. arXiv preprint 1rXiv:abs//107.044600 2021.
[60] Christos Verginis, Cevahir Koprulu, Sandeep Chinchali, and Ufuk Topeu. Joint learning of reward machines and policies environments with partially known semantics. arXiv preprint ar0iv:2204.1 /833, 2022.
[61] Zhe Xu and Ufuk Topcu. Transfer of temporal logic formulas in reinforcement learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 4010-4018, 2019.
[62] Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topeu, and Bo Wu. Joint inference of reward machines and policies for reinforcement learning. In Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS), volume 30, pages 590-598, 2020.
14

---

[63] Zhe Xu, Bo Wu, Aditya Ojha, Daniel Neider, and Ufuk Topcu. Active finite reward automaton inference and reinforcement learning using queries and counterexamples. International Cross-Domain Conference for Machine Learning and Knowledge Extraction, pages 115-135. Springer, 2021.
[64] Lim Zun Yuan, Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening. Modular deep reinforcement learning with temporal logic specifications. arXiv preprint arXiv:1909. 11591, 2019.
[65] Hao Zhang, Hao Wang, and Zhen Kan. Exploiting transformer in sparse reward reinforcement learning for interpretable temporal logic motion planning. IEEE Robotics and Automation Letters, 2023.
[66] Xuejing Zheng, Chao Yu, and Minjie Zhang. Lifelong reinforcement learning with temporal logic formulas and reward machines. Knowledge Showledge-Based Based Systems. 257:109650,, 2022.
15

---

A Additional Definitions and Theorems
Theorem 4.1 A Noisy RM Environment (E, R,,,R,,M, is equivalent POMDP over state space S x U and observation space O.
Proof. The POMDP K (8", O','','''' R', w/, ,1),, where S' = 0, A.
P' ('((S+1,, (++1) (st, uz), az) P(s az) [[ōu at u[+1] R' ('((,, uz), az (Se+1, u++1)) = (m4, L(st, 04, S1+1)), w' w (8t, ux)) = (()) pl(s, u) = pus) w1]
equivalent to the Noisy RM Environment (E, R. C, M) in the following sense. For any pol- icy Taaslhe. #14) in the noisy RM environment we can obtain an equivalent policy x' r'(a,lha t (aglht, Malli, M(h M(h:)) for that achieves the same expected discounted return and vice- versa. To see why the reverse direction is true, we note that 21:1 -M(h))..... M(h,) (ima),...,,,(hy is function of ht for a fixed abstraction model M. These policies behave identically given the same history hi
Theorem 4.2 (Does the choice of M affect optimal behaviour?) Let P be Noisy RM Environment (E, R, C, M), and Pe be a Noisy RM Environment (E, R, M'). Then P and P' are equivalent.
Proof. Consider any policy T (uelhe, =1.e) for P and notice that the sequence of outputs from the abstraction model . is a function of the history hes ic. 21:t = f(1)). Thus, valid policy in P is T' (at |,, ) (a,l/e, f(e)) (where zi are the outputs from the abstraction model M' but do not affect the policy T'). Similarly, a policy for P' can be used to obtain policy for P that is
identical. Thus, P and Pl are equivalent.
Theorem 4.3 (Does observing L affect optimal behaviour?) Let P be a Noisy RM Environment (E, R. L, M). Consider a problem P' that is identical to P except that the agent at time / additionally observes L(st. O4, S1+1) after taking action a, in state st. If E is an MDP, then P and P' are equivalent. If is a POMDP, P and P' may be non-equivalent.
Proof. Consider that & is MDP. At time t. denote the sequence of outputs from the labelling function up to time t by 01:-1, where a; = L(s,, as $;-1) = [(o,, a, 0++1) (we assume 8 o since E is an MDP). Consider policy T' T'(a, he, 21:1, 01.--1) for P' that conditions information (including the outputs of the labelling function) up to time l. However, since & is fully observable, the labelling function outputs Fıa can be represented
all observable
function of the history hy, i.e. 01 = s(h)). Then the policy π (ag [he, z1ze) = n' (axl [4, #1 ((h)) for P is identical to x'. Similarly, given a policy it [aae 21:r) for P. we can obtain an identical policy n' (a (he, 21st 11z)) T (ar 21.e) for P'.
Note that if E is POMDP, this is not true, since the outputs of the labelling function 014-1 (which is a function of the history of states and actions) cannot be determined from the history of observations and actions. For explicit counterexample, consider that & is two-state POMDP with states (()) and (1) where the initial state is equally like to be !0)) or (1), and that state persists for the remainder of the episode regardless of the agent's actions. The agent receives a single, uninformative observation o regardless of the state. Let there be two actions (0) and (1),, where a reward of is
received for taking action (i)) in state (()) (a reward of 0 is received otherwise). Let there be single proposition A that holds for transition (st, út, 8(+1) ) if 8, g()) For the Noisy RM Environment P (where the agent cannot observe L),, the optimal policy receives no information about the current state and has no better strategy than to randomly guess between (0)) and a(1) at each timestep. In p (where the agent enabling a strategy that receives a reward of I on each step. There is no identical policy in P that achieves this, thus the problems are not equivalent.
observe L), the agent can deduce the state based on whether A holds not,
Proposition A.1 TDM is consistent.
16

---

Proof. This is immediate because the belief Pr(2ul/e) is a function of h4 Thus, choose (hs) Pr(ue (b4) and we are done.
Lemma A.2 If is fully observable, then there exist abstraction models M₁ : H + 2AP M2 H + A(2AP), and M3 H 7 AU such that Mi(h,) = L(s--1, a,-1, St), M2(h;)][((+--,) at-1, 11)1 = 1, and Ma(hy) [ue] for all he E H. In other words, MI, M2 recover the ground-truth labelling function L and Mg recovers the RM state at time 1 with certainty.
Proof. Since & is an MDP, we assume states 9t and observations or are interchangeable. The desired statements immediately result from the fact that the labelling function [(5 1e-1, 8t) and ut deterministic functions of the history h4-
Proposition A.3 If & is fully observable, then Naive and IBU are consistent.
Proof. Choose the abstraction models MI, MM and M3 as in Lemma A.2 Running Naive with M precisely mirrors the procedure for computing RM states u, with the ground counnd-ruthhha labelling function f. and therefore recovers 4e with certainty.
For IBU with M2, we perform simple proof by induction. At any time t, we propose that the predicted belief ūn assigns full probability the ground-truth RM state u4. At time 1, this true by the initialization of the algorithm. At time & > 1, we have
(u(
E
( (i-(()))M(ba)oo 18 ul -u).
0E2AR W'EU
Σ 1( = -
rE2AP
[0 (u:-1 L(s ((-15))))1,, u|
1 Jug = ul
Proposition A.4 Naive is not necessarily consistent in general POMDP environments E.
Proof. This result stems from the fact that Naive cannot model an RM state belief of strictly probabilistic nature.
Consider POMDP with two states, (0) and (1),, where the initial state is equally likely to be s( or s(1), and that state persists for the remainder of the episode regardless of the agent's actions. The agent receives single, uninformative observation o regardless of the state. Thus, the agent always observes the same sequence of observations (o, o.... and the sequence of states is equally likely to be either (s(0), ((.))...) or (())),)))...))
Let there be a single proposition that holds when the agent currently in state (0) Let the RM R. have two states; an initial state (0) that transitions to the state (1) when the proposition A holds.
The ground-trut -ruth RM state belief is given by Pr(u, = zf() (h,) 0.5 for all timesteps 2 2. This
belief cannot be captured by Naive under any abstraction model, thus, Naive is not consistent. 0
Proposition A.5 IBU is not necessarily consistent in general POMDP environments E.
Proof. Suppose for contradiction that IBU is consistent and therefore, produces in = Pr(ue(ba) for some M
Consider the same POMDP as in Proposition A.4 with one small change. Now, while in any state g( the observation emitted with 0.5 probability or of (revealing the state) with 0.5 probability. Consider a history h, with the observation sequence o, (1), After seeing the observation o, must be the case that 0e assigns 0.5 probability to both (0)) and (!!), before. Then after seeing the
observation (4)) it becomes certain that the persistent state is ((1), and therefore PV(u,hhe assigns
probability to n! However, regardless of how M (ht) is assigned, it is impossible to achieve
17

---

Traffic Light
Kitchen
Colour Matching
1.0
Precision & Recall
0.4
0.2
0.0
red
package
home
diehen
slove
trash
1st
2nd
3rd
Propositional Symbol
Precision
Recall
Figure 6: Precision and recall of a classifier trained to predict occurrences of propositions. Key propositions in each domain uncertain. Values are averaged over training runs, with lines showing standard error.
this belief for üg. This is since üz uz(u!") 0.5 but there are no RM transitions out of u(1), so üg (s[ 2 0.5.
B
Experimental Details
B.1 Gold Mining Experiments
The Gold Mining Problem is described in Example 3.2 penalty of 0.02 each time the agent selects movement action incentivize the agent towards shorter solutions.
We also introduce a small (Markovian)
Policy models. The Oracle baseline learns Q-value for each (location, RM state, action) combination without memory or function approximation. The Memory only baseline and all the proposed methods conditioned six additional binary features corresponding to each square with gold or iron pyrite (i.e. where the agent places non-zero probability of that indicates whether the agent has previously mined at that location. We use this as tractable alternative representing the entire history without neural network encoders.
All approaches except Oracle use linear decomposition of Q-values to allow for generalization and reduce the number estimated Q-values. Naive, IBU, and TDM use the following approximation.
Qlocatioo, û, memorry.6 action)
Σ (((()) [Q1(u) + Qz(location, u, action) +
(locationn u, memory; action)]
6
NEU
The Memory only bascline use the following approximation.
Qlocatioo, memory action) Q (location, action)
Q2(location, memory,, memeorytion,mmmory, action)
Hyperparameters. All methods use a learning rate of 0.01, discount factor of 0.99, and a random action probability of 0.2.
18

---

Evaluation details. All methods are trained for 1M steps, and the policy is evaluated every 10K steps without e-greedy actions. Since the evaluation policy and the environment are deterministic, each evaluation step records the return from single episode.
B.2 MiniGrid Experiments
In the Traffic Light domain, the task is described by the RM in Figure 7 There are propositions corresponding to reaching the squares with the package, the home, and for crossing a red light. The light colour cycles between green, yellow, and red, where the duration of the green and red lights are randomly sampled. The yellow light always lasts a single timestep and serves to warn the agent of the red light.
The RM for the Kitchen domain (not shown) has 9 states, encoding all possible subsets of the completed chores plus one additional terminal state that is reached upon leaving the house. The episode initialized such that each chore needs cleaning with & probability, and a chore can be completed by visiting that square. The agent can observe tasks that are completed when inside the kitchen. There one proposition per chore marking whether that chore is done (regardless of whether the agent can observe this) and proposition for leaving the house through the foyer. We implement a small cost of -0.05 for opening the kitchen door and performing each task, making so the agent must do so purposefully.
(package,
(home, 1)
u(1)
u(4)
fred, 0}
(red, 0)
(home, -1)
(package,
(222)
(3)
Figure 7: An RM for Traffic Light. The goal is to pick up the package and return home (each stage gives reward of 1). If the agent crosses red light, it gets a delayed penalty upon returning home. To simplify formulas on edge transitions, we assume all propositions occur mutually exclusively, and if no transition condition is satisfied, the RM remains in the same state, receiving 0 reward.
Network architectures: A policy is composed of an observation encoder followed by policy network. The observation encoder takes in the current environment observation as well as belief over RM states (when applicable) and produces an encoding. This encoding is fed to GRU layer to produce an encoding of the history. The policy network takes the history encoding and feeds it to an actor and critic network, which predicts an action distribution and value estimate, respectively. We use ReLU activations everywhere except within the critic, which use Tanh activations. The observation encoder consists of two 64-umit hidden layers and produces a 64 -4-dimensional encoding. We use single GRU layer with a 64-dimensional history encoding. The actor and critic both use two 64-diimnsionnl hidden layers. The abstraction models use separate, but identically structured observation encoder and GRU layer. The history encoding is fed to single, linear output layer.
B.3 Colour Matching Experiment
The atomic propositions in the Colour Matching domain are {a, b, c, d}. where means the agent is currently in range of the target pillar, and b and c mean the agent is in range of the second and third pillars, respectively. The order of the three pillars is specified at the beginning of the episode via an index vector, where each index corresponds to one of the 18 possible colours.
The RM for this task has 6 states and encodes two pieces of information: whether the target pillar was ever reached, and the last pillar the agent visited. Each time the agent visits an incorrect pillar, negative reward of -0.2 is issued, but this penalty is not applied if the agent visits the same pillar multiple times in succession. subsequently going to the portal. We do not show the RM due to the excessive number of edges.
reward is given for visiting the target pillar, and then for
19

---

Traffic Light
Log- Log-likellhood
-2
44
Naivo
TDM (BL)
(GPT4)
Nalve (Random) [Randion)
(CPT4)
Figure 8: (Left:) Accuracy of various inference modules measured by log-likelihood (higher is better) when predicting RM states given trajectories generated by random policy. (SL:) abstraction model is trained via supervised learning from ground-truth data. (GPT4:) abstraction model is zero-shot GPT-4o. (Random:) abstraction model is neural network with random weights. (Right:) An RGB rendering
the Traffic Light MiniGrid environment used to query GPT-4o. GPT-4o given the prompt: "The red triangle is contained in cell of this grid. What is the color of the cell? Answer in a single word." Note that the light colour is only visible when entering the intersection in the forward direction.
Table 2: Hyperparameters for deep RL experiments
PPO hyperparameters
Traffic Light
Kitchen
Colour Matching
Env. steps per update
32768
32768
32000
Number of epochs
8
Minibatch size
2048
2048
8000
Discount factor (?)
0.97
0,99
0,999
Learning rate
3 x 10
3 10
3 X 10
GAE-À
0.95
0.95
0.95
Entropy coefficient
0.01
0.01
0.001
Value loss coefficient
0.5
0.5
0.5
Gradient Clipping
0.5
0.5
PPO Clipping (E)
0.2
0.2
0.2
L.TTM Backpropagation Steps
4
Abstraction model hyperparameters
Env. steps per update
32768
32768
32000
Number of epochs
8
8
Minibatch size
2048
2048
8000
Learning rate
10-4
10
10
LSTM Backpropagation Steps
4
Network architectures. The policy and grounding model networks are similar to those in the previous experiments. The policy uses observation encoder with two 256-unit hidden layers and a 128-unit output layer. This is fed to a single GRU layer with hidden size of 128. The actor has one encoding layer with hidden size 128, followed by linear layers predict mean and standard deviation for continuous actions. The critic has two 128-unit hidden layers.
The abstraction models for Naive and IBU are MI.ss with five 128-unit hidden layers (the environment nearly fully observable and encoding the history is not necessary for predicting the labelling function). The abstraction model for TDM first predicts evaluations of propositions at each step, and then aggregates the history of these predictions with history of observations, before predicting the RM state belief. We find this approach to work well with a limited dataset as it can also exploit labels corresponding to the evaluations of individual propositions. The network architecture is as follows. An observation encoder first produces a 128 128-dimensional embedding using three 128-unit hidden layers. This is fed to a decoder that predicts propositional probabilities using one 128-unit hidden layer. The observation embedding and the outputs of this decoder are both fed through 2 GRU layers with hidden size 128, and finally, another decoder uses the memory from the GRU layers to predict the RM state belief.
20

---

B.4 PPO Training Details
We report all hyperparameter settings for the Deep RL experiments in Table Experiments were conducted on a compute cluster. Each run occupied 1 GPU, 16 CPU workers, and 12G of RAM. Runs lasted approximately 18 hours for Colour Matching, and hours for Traffic Light and Kitchen. The Gold Mining experiments took negligible time and were run personal computer. The total runtime for these experiments is estimated at 1100 GPU hours. Prior experiments that did not make into the paper accounted for at least 1000 GPU hours. We used the implementation of PPO found here under an MIT license: https://gitin //hi://ggbb......... com hotp://////wwleee////oooooo
B.5 Agent Behaviours
Table provides a detailed description and explanation of the behaviours we observed for Naive, IBU, and TDM in our experiments in the Gold Mining, Traffic Light, and Kitchen environments.
In the Colour Matching environment, Naive, IBU, and TDM all learn an effective policy in the RL setting, but it is important note that only TDM is effective at accurately modelling belief over RM states given trajectories from a random policy (see Figure (5). We believe this is since the RL setting provides leeway for the agent to act in manner that mitigates the errors of the inference module. In particular, the inference modules are most uncertain when the agent stays near the distance threshold for which pillar is considered "reached". However, the RL agent address this by moving closer to the pillar and reducing this uncertainty.
21

---

Table 3: Behaviours observed in experiments.
Method
Description of behaviour
Explanation
Gold Mining
Naive
The agent typically digs at a nearby cell containing iron pyrite and immediately heads to the depot.
There a cell that the agent helieves yields gold with 0.6 prob- ability but is actually iron pyrite. Under the Naive approach, digging at this location makes the agent believe with certainty that gold has been obtained so agent heads the depot.
IBU
The agent repeatedly digs at the same locations within the same episode before heading the depot.
Under IBU, the chance of obtaining gold on cach step is as- sumed to be independent (even when digging the same square). Hence, agent repeatedly digs in the same place, even though digging more than once any location has no utility.
TDM
The agent mines several squares to maximize the chance of obtaining gold before heading the depot.
Under TDM, we include the assumption that the belief of having obtained gold does increase repeated digs at the same square.
Traffic Light
Naive
The agent drives through the intersec- tion in reverse (including when the traf- fic light is red) to pick up the package.
When crossing the intersection in reverse, the agent cannot see the light colour and has to guess. The chance of the light being red tends to be less than 50%, hence the agent predicts that it has not violated the red light.
IBU
The agent faces the intersection and waits until the light is green to proceed, successfully solving the task.
IBU is able to capture the uncertainty in whether red light violation has occurred when crossing the intersection in reverse (as further evidenced by Figure 5 Thus, IBU successfully learns to avoid the dangerous behaviour of driving through the intersection in reverse.
TDM
Similar to IBU.
Similar IBU.
Kitchen
Naive
The agent learns the correct hehaviour entering the kitchen and completing the remaining tasks.
Interestingly, the agent's initial belief RM states accurate. While outside the kitchen, the agent cannot tell whether each task was initialized in a "done" state or not-it predicts all tasks are not done since each starts as "done" with only á probability. This incentivizes the agent to enter the kitchen, allowing observe which tasks still need be completed.
IBU
The agent wanders around outside the kitchen and fails to complete the chores.
While outside the kitchen, the agent predicts on each timestep a I probability for each chore that it started in a "done" state. As this chance as independent that each chore was done at some point up time is predicted to be 1 ( By wandering around outside the kitchen for long enough, the agent believes that all chores are completed with close probability 1, giving incentive to enter the kitchen.
each timestep. the chance
TDM
The agent learns the correct bchaviour of entering the kitchen and completing the remaining tasks.
TDM correctly models the initial belicf over RM states reflecting that each chore has an independent 3 chance of being done before the agent has entered the kitchen. This incentivizes the agent to enter kitchen and complete all chores that may still need to be completed.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The POMDP framework is described in sections and the algorithms in
section | the thcoretical analysis in sections and 5.4 and the experiments in section 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
See the conclusion for some discussion of limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification: See Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our algorithms are described in detail in Section 5 and their specific imple- mentations and training details are detailed in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [Yes]
Justification:
Code and instructions are provided as supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
cesssnnnoiccyyl for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.ccppullc//uuuii wwwtc//ggue////eeeeceoocc CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Standard error is indicated in the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section B.4
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that NeurIPS Code of Ethics https: http::///errisioeee http://ccc..ccc..tccccccc.d..ee.
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
The potential breaches of the code of ethics do apply this work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See the conclusion.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
26

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release data models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: See Section B.4
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whworee.wthhhe....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
27

---

Answer:
[NA]
Justification: No assets are introduced.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: There were such experiments research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: There were such participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "1YKPfH5uV3", "reviewer": "Reviewer_sM3w", "summary": "This paper investigates the use of Reward Machines in Deep Reinforcement Learning (RL) for handling noisy and uncertain environments. It frames the problem as a Partially Observable Markov Decision Process (POMDP) and proposes a set of RL algorithms leverage the task structure under uncertain interpretation  of domain-specific vocabulary. The theoretical analysis reveals the limitations of naive approaches, while experimental results demonstrate that the proposed algorithms successfully leverage task structure to improve performance under noisy interpretations. The findings provide a general framework for exploiting Reward Machines in partially observable environments.", "questions": "1. Could authors provide a clear definition of the problem (if abstraction of model is part of the problem) and also provide a definition of optimality under the definition of the problem?\n\n2. In the experiments, abstractions models are represented by neural networks. Where do the ground truth labels come from? Especially, Naive, IBU, and TDM have different prediction objective. So they use different training data and labels?\n\n3. In three of the domains, IBU is even worse than naive that do not consider stochasticity? Could authors explains why this is happening?", "limitations": "TDM, the best-performing method, relies on a task-specific abstraction model (to predict the state in the specific RM). For some real-world tasks, it might not be possible to get enough training data to learn accurate abstraction models.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The discussion of reward machine under uncertain interpretation of the domain-specific vocabulary is somewhat novel.\n\n2. The paper discusses three possible abstraction models that predicts deterministic proposition, stochastic proposition, and stochastic RM state respectively.\n\n3. The paper provides theoretical analysis on the consistency of these three different abstraction models.", "weaknesses": "1. I think this paper could be improved by clearer presentation. The formulation of Noisy Reward Machine Environment is confusing. Especially, the abstraction model is included as part of the environment or part of the problem setting, however, the proposed methods considers different types of abstraction models. Should the abstraction model be the method or the problem?\n\n2. The paper claims as the first to consider reward machines under environment uncertainty. However, its discussion and theoretical analysis does not go much beyond the POMDP and brief state updating in the existing literature. For example, its result can be seamlessly handled by including RM state U as part of the POMDP state.\n\n3. Some writing suggestions:\n- In the introduction, the authors used term \"new RL framework\", but up to Section 5, there is no RL. The three methods being discussed are abstraction models. The authors didn't talk much about how the abstraction models can be combined with RL.\n- Make it clear about the problem setting. In particular, is the abstraction of model given as a part of the problem?\n- The author used term \"optimal behavior\", \"optimal brief\". These term should be clearly defined. What are the optimal behavior? Optimal assuming accessing to label function L? What is optimal state brief?    \n- Line 222 \"Given an abstraction model of the form M : H → ∆U predict M(h_t) directly.\" what does this mean?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive review. We take seriously the issues you raised regarding clarity and will revise the manuscript accordingly.\n\n> **Should the abstraction model be the method or the problem?**\n\nThe abstraction model is part of the problem. It captures the agent’s uncertain prior over how high-level features are grounded in the environment. The fact that this uncertainty arises and is not easily resolved in many real-world domains motivates our work. Thus, we include this uncertainty as an element of the problem rather than something within our freedom to affect. In terms of the Gold Mining example, we argue that the agent’s uncertainty of where gold can be found should be stated in the problem, not the solution. Thanks for raising this point of potential confusion — we will include this justification when introducing our framework.\n\nRegarding your concern that the proposed methods require different types of abstraction models, Theorem 4.2 establishes that, under any choice of abstraction model, the problems are equivalent (i.e, per the definition in the paper, that for each pair of problems, there is a bijection between policies of equal value.)\n\n> **Could authors provide … a definition of optimality …**\n\nThanks for pointing out that *optimal behaviour* is potentially ambiguous. In this work, it refers to the behaviour that maximizes expected discounted return in the Noisy RM environment. Rewards are defined by the RM interpreted under the labelling function, $\\mathcal{L}$, and we do not assume the agent can query $\\mathcal{L}$ when executing.\n\nThe *optimal RM state belief* is defined as the distribution $P(u_t | h_t)$ (line 160). It is closely related to a POMDP belief state distribution, $P(s_t | h_t)$. As such, the optimal RM state belief can be viewed as inferring the ground-truth RM state from histories (which depends on $\\mathcal{L}$), marginalized over all possible state trajectories, while Naive, IBU, and TDM approximate this optimal belief. \n\nWe'll clarify both of these concepts in the paper.\n\n> **Where do the ground truth labels come from? Especially, Naive, IBU, and TDM …**\n\nWe obtained offline datasets to train the abstraction models as follows. We generated full episodes from a random policy and annotated each timestep with the ground-truth propositional evaluations $\\sigma_t \\in 2^\\mathcal{AP}$ and RM state $u_t \\in U$ obtained via a manually constructed labelling function.\n\nNaive and IBU were trained to predict $\\sigma_t$ given $h_t$, while TDM was trained to predict $u_t$ given $h_t$. The abstraction models were trained from the same set of trajectories, ensuring a fair comparison between Naive, IBU, and TDM (even though the target labels were different).\n\n> **In three of the domains, IBU is even worse than naive … Could authors explains why this is happening?**\n\nNaive and IBU are flawed in different ways when predicting a belief over RM states — it should not be concluded that one is generally better than the other. The key flaw with IBU is that when a proposition is uncertain, IBU ignores the dependence of that proposition across timesteps. \n\nExample 5.2 illustrates this. When the agent mines repeatedly at the same state, the outcomes are linked — either there is gold at every time, or at none of the times. By assuming independence, IBU incorrectly assigns non-zero probability to cases that cannot occur, such as the first “mine” action yielding gold but not the second one. Unfortunately, this can mislead the agent into undesirable behaviours such as mining at the same location over and over, to maximize the perceived probability of obtaining gold.\n\nIn the Kitchen task, the agent initially cannot observe the state of the kitchen. Consider an episode where the agent never enters the kitchen. Then at each step $t$, the agent (correctly) believes there is a small chance the dishes are already clean. However, IBU ignores the dependence between these events — in reality, the dishes are either clean at every step or at none of the steps. Similar to Gold Mining, IBU will erroneously reflect that all chores are complete with probability approaching 1, even when the agent never enters the kitchen.\n\n> **Some writing suggestions**\n\nVery good suggestions. Thank you.\n- We will include an algorithm box describing how we combine RL with abstraction models (see the global response pdf).\n- To your question, in the description of TDM (line 222), the output $\\mathcal{M}(h_t)$ of the abstraction model has the required form (a distribution over RM states) to be used directly as the output of the inference module. We will clarify this and also add a description of an instantiation of TDM where an RNN directly predicts a distribution over RM states given the history.\n\n> **The paper claims as the first to consider reward machines under environment uncertainty ... [the] result can be seamlessly handled by including RM state U as part of the POMDP state**\n\nTo clarify, we provide the first scalable deep RL framework for RMs (and related formal languages) under noisy determination of propositions. We respectfully disagree that our results follow seamlessly from viewing the RM state as part of the POMDP state. Characterizing the problem as a POMDP relates it to established concepts and supports theoretical analysis. However, this insight alone does not yield an effective RL solution because it neglects to exploit the rich reward function structure provided by the RM. This is reflected in the poor performance of the generic “Memory only” baseline (Recurrent PPO). Our proposed methods are so effective because they exploit the structure of our specific POMDP formulation. \n\nThe related work section elaborates upon the novelty of our framework in comparison to previous works.\n\n#### **Limitations**\nAgreed.  These were explicitly acknowledged as limitations in the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jOmNHO0jCQ", "reviewer": "Reviewer_ed91", "summary": "The paper proposes the use of Reward Machines (RMs) in deep reinforcement learning (RL) for noisy and uncertain environments, characterizing these settings as Partially Observable Markov Decision Processes (POMDPs). The contributions include:\n- Proposing framework for using RMs in deep RL in partially observable environments.\n- Theoretical analysis identifying pitfalls in naive approaches.\n- Experimental results demonstrating improved performance under noisy conditions.\n- Discussing limitations and proposing future work for general-purpose models and relaxing ground truth reward assumptions.", "questions": "The proposed technique makes build a model for a reward machine either from data or via pretrained foundational labeling functions. making such GT data available to a policy would likely increase training performance: By providing useful features of the environment instead of raw observations, the difficulty of the task the neural network has to solve is reduced. But this is already given by the No-Free-Lunch-Theorem.\n\nThe evaluations show the policies trained with the newly proposed methods to perform better, but to what extend could this be explained by 'leaking' information of the ground thought RM to the policy during training? Can we actually make predictions on whether this is an improvement when no GT RM data is available (as such leaks can no longer occur)?", "limitations": "The paper mentions addresses some limitations, such as the need for ground-truth rewards during training. However, could be extended by further discussion on the practical challenges of implementing these methods in real-world scenarios.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "Originality:\n- The combination of RMs with deep RL algorithms to handle noisy and uncertain environments is innovative.\n- The paper provides rigorous mathematical definitions and theoretical insights into the limitations of naive approaches and Independent Belief Updates (IBU).\n\nQuality:\n- The submission is technically sound with well-supported claims through both theoretical analysis and experimental results.\n- The experiments are comprehensive, spanning toy environments to more realistic tasks, showing the scalability and applicability of the methods.\n\nClarity:\n- The paper is generally well-written and organized.\n- The explanation of theoretical concepts using the Gold Mining Problem is clear and effective.\n\nSignificance:\n- The results demonstrate significant improvements in RL performance and sample efficiency in noisy environments.\n- The experimental evaluation shows the potential for real-world applications.", "weaknesses": "- It is unclear how well the methods perform without ground-truth RMs, raising questions about additional effort required for new environments.\n- The discussion on foundational models is mentioned early on but is missing from the experiments, discussion, and conclusion, leaving the practical setting for these methods unclear.\n- Line 32 mentions numerous references without distinguishing their importance. This should be extended to provide (even if just brief one-sentence) summaries of the mentioned works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive evaluation and for recognizing that this work addresses an innovative problem, introduces rigorous definitions and insights, and presents well-supported claims in a clear and organized manner. We address your main questions and concerns below.\n\n> **… to what extent could [evaluations] be explained by 'leaking' information of the ground truth RM to the policy during training? Can we actually make predictions on whether this is an improvement when no GT RM data is available? …** \n\nIndeed, an abstraction model serves to identify salient features of the problem such as the ground-truth propositional evaluations or RM states. You are correct that exposing such features can allow for significant performance benefits. This is one of the merits of RMs (and similar formal specifications) — they leverage this prior information in a systematic way to yield greater sample efficiency and interpretability. In fact, a number of real-world applications already depend on these types of methods, e.g. [1-3]. \n\nThe last part of your question is also important: what happens when abstraction models are unable to “leak” these relevant features? Firstly, an abstraction model that provides no signal at all is entirely noise (i.e. the model outputs are independent of the features, such as a neural network with random weights). In such cases, we hypothesize that exploiting the reward function structure is nearly impossible since we have no information regarding the semantics of the propositional symbols.\n\nThis paper relaxes a strong assumption inherent in many RL works leveraging formal languages for reward function specification, including works on Reward Machines, and various temporal logics (e.g. Metric Interval Temporal Logic [4], Linear Temporal Logic [5]). These approaches are often predicated on a \"perfect\" labelling function, an oracle that returns ground-truth features for any environment transition. In contrast, abstraction models are significantly easier to obtain — they can be noisy, can model arbitrary features (not just propositions), and depend only on the observable history (not states). This allows us to better handle practical concerns such as ambiguity in the intended interpretation of propositions, noisy sensors, and partial observability. As you noted, foundation models fit into our framework too and bringing to bear such models presents an exciting direction for this field. For these reasons, we consider our work a step towards making RMs more widely applicable in the real world. \n\nWe understand your concern that we may “leak” too much ground-truth information through the abstraction models in our experiments. However, Figure 5 in the Appendix shows that these abstraction models are in fact quite noisy — they have poor precision and recall when predicting the most important propositions (e.g. running a red light in Traffic Light, or the completion of chores in Kitchen) under a random policy. Also note that in our partially observable domains, the abstraction models cannot capture the ground-truth labelling function or RM state even with infinite data. We fundamentally restrict abstraction models to depend only on observable histories, while ground-truth propositional values and RM states are functions of state.\n\n> **The discussion on foundational models is mentioned early on but is missing from the experiments, discussion, and conclusion.**\n\nAn RM framework that incorporates foundation models is an important and exciting direction. We are happy to include a further discussion on this topic.\n\nWe’ve conducted additional experiments using vision-language models in the Traffic Light MiniGrid domain, showing that GPT4o can serve as an effective zero-shot abstraction model (see global response). We consider the task of predicting RM state beliefs from a dataset of randomly generated trajectories, like in the original Figure 4, and we directly prompt the VLM to list the coloured grid squares it can see from the agent’s image observation. We will discuss these capabilities in a subsection of “Experiments”. \n\nWe will also discuss the limitations of current foundation models. Namely, we find that only GPT4o effectively understands MiniGrid observations, while smaller models (GPT4o-mini, CLIP) fail. There is also no easy way to implement TDM, the most robust type of abstraction model, using current VLMs.\n\n> **Line 32 mentions numerous references without distinguishing their importance**\n\nWe originally included the list of references on line 32 to convey the depth of literature on formal specifications (particularly those based on LTL or automata) in deep RL. This helps establish that we are working on an important problem of broad interest to the research community. Nonetheless, your point is well taken and we are happy to provide short contrastive descriptions of these works in an extended related works section.\n\n[1] Fainekos et al. \"Temporal logic motion planning for dynamic robots.\" Automatica, 2009.\n\n[2] Doherty et al. \"A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems.\" Autonomous Agents and Multi-Agent Systems, 2009.\n\n[3] Camacho et al. \"Reward machines for vision-based robotic manipulation.\" ICRA, 2021.\n\n[4] Xu & Topcu. \"Transfer of temporal logic formulas in reinforcement learning.\" IJCAI, 2019.\n\n[5] Vaezipoor et al. \"Ltl2action: Generalizing ltl instructions for multi-task rl.\" ICML, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9h9PbnYkEQ", "reviewer": "Reviewer_qw5f", "summary": "This paper focuses on the automatic design of reward machines in reinforcement learning, which holds potential for interpreting instructions, enforcing safety constraints, and more. It is particularly relevant in the real world, especially in the era of large language models (LLMs), where defining reward functions is often challenging. The authors propose to formulate noisy and uncertain environments as Partially Observable Markov Decision Processes (POMDPs), a straightforward approach. Their experiments demonstrate the efficiency of their method. The solution seems broadly applicable across many fields as it doesn't require a ground-truth interpretation of domain-specific vocabulary.", "questions": "What are the constraints of the abstraction model? Or just an arbitrary model. Is its form assumed to be known, such as a classifier or a regression model?\n\nGiven that most of the compared methods are proposed in the paper, it is unclear if other RL methods have the potential to solve the discussed noisy reward setting effectively.\n\nHow about the interpretability or visualization of the learned model? Could you provide examples of the learned belief or the output of the abstraction model with respect to observations and agent actions? It would be better for the reader to understand.", "limitations": "See weakness", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper introduces a novel way of handling noisy and uncertain environments by modeling them as POMDPs. This perspective is particularly effective in real-world applications where the accurate reward and stationary environment are not always possible.\n   \nThe automatic design of reward machines is a valuable tool in reinforcement learning, especially in contexts where defining reward functions manually is difficult, such as with LLMs.", "weaknesses": "Do the author assume the form of the abstraction model (e.g., classifier or regression model) is known, which might limit its applicability in more complex or less understood environments. In Golden Mining, the modeling of belief as binary might require domain-specific knowledge, which could be a limitation. This simplification might not be suitable for all environments, particularly those requiring more nuanced belief representations. How about the design of the abstraction model in other environments?\n\nMost of the compared methods in the paper are proposed by the authors themselves. This raises questions about whether other existing RL methods could address the noisy and uncertainty environment effectively. A broader comparison with existing methods is necessary to establish the general effectiveness of the proposed approach.\n\n\nThe paper primarily uses Proximal Policy Optimization (PPO) for experiments. It would be beneficial to compare the proposed methods across different RL algorithms to demonstrate consistent improvements and broader applicability.\n\nThe relations of RM, noisy RM environment and the evaluating environment is not clear to me. The evaluating environments are just simple POMDP environment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review. First, we’d like to clarify that our focus is not the “automatic design of Reward Machines” (we assume the RMs are specified by a human). Rather, the work is about whether we can effectively follow task specifications (expressed via RMs) even when the vocabulary cannot be interpreted with certainty. We hope our response further clarifies the work and raises your evaluation.\n\n> **What are the constraints of the abstraction model?**\n\nOur framework allows for abstraction models to be quite general. Abstraction models represent the agent’s uncertain interpretation of high-level salient features, and critically, we allow these features to be arbitrary. \n\nWe later focus on three classes of methods (Naive, IBU, TDM) requiring specific types of abstraction models. These abstraction models predict a specific feature (propositional values or RM states) given histories. We agree that requiring specific models is a limitation, but there are two reasons this work is significant nonetheless:\n\n1. Our work is motivated by the large body of work leveraging RMs or related formal languages in deep RL (see line 32). **The vast majority of these are built on a far stricter requirement that the agent can observe the labelling function — an oracle providing exact propositional evaluations**. Abstraction models significantly relax the labelling function — they can be noisy, they can output arbitrary features, and they depend only on the observable history rather than states.\n2. **Formal specifications like RMs have already been applied to important real-world problems despite the limitations you mention** (e.g. [1-3]), and they are often more data efficient and easily interpreted compared to end-to-end data-driven approaches.\n\n> **the modeling of belief as binary might require domain-specific knowledge**\n\nYou are correct if you are stating that our propositions must be binary. Other formal languages with more expressive vocabularies have also been considered.\n- In Signal Temporal Logic [4], the vocabulary is a continuous-valued signal that can represent values such as distances and velocities.\n- Sun et al [6] consider programs as a specification with a rich set of domain-specific primitives. \n- Tuli et al [5] consider Linear Temporal Logic over open-ended entity relations described in natural language e.g. (“potato”, “is”, “chopped”).\n\nOur work is motivated by the general observation that agents may incorrectly interpret or evaluate their vocabularies, which is relevant to other forms of task specification as well.\n\n> **Most of the compared methods in the paper are proposed by the authors themselves.**\n\nWe understand the concern that our experiments mainly use our own methods. **However, we are proposing a novel problem setting and there are few existing approaches that can suitably be applied.** We believe our paper is comprehensive in discussing the relevant literature — for each class of approach, we either include a direct experimental comparison or explain why it is not suitable to our problem.\n- We show our problem can be reduced to a POMDP and compare against Recurrent PPO, a state-of-the-art method for general large POMDPs.\n- There is a broad literature leveraging formal languages in deep RL. These often rely on access to the labelling function and we include the “Oracle” baseline as a performance upper bound.\n- Some applications have used ideas like Naive or IBU to handle noisy inputs (e.g. [5,6]) but these are treated as an implementation trick rather than a general solution for partial observability. We identify the pitfalls of applying such approaches more generally.\n- Many works have considered the noisy detection of propositions in tabular MDPs. Their methods require marginalization over the entire state space which is infeasible in most deep RL environments (e.g. [7]).\n\n> **How about the interpretability or visualization of the learned model?**\n\nWe agree that this would be insightful and have already prepared videos of the trained agents. We will ensure these are released in the final version.\n\n> **The paper primarily uses Proximal Policy Optimization (PPO) for experiments.**\n\nWe mainly use PPO throughout our experiments as it’s arguably the most popular deep RL algorithm. Nonetheless, the rigorous theory and conceptual examples (as recognized by the other reviewers) supporting our results are independent of the specific policy learning scheme. \n\n> **The relations of RM, noisy RM environment and the evaluating environment is not clear to me**\n\nUnfortunately, we were not completely sure what you meant by this. If you’re asking how our experimental domains depend on RMs (and why they are not just simple MDPs or POMDPs), note that an RM specifies a temporally extended, non-Markovian pattern. For example, in Colour Matching, the agent must touch the correct pillar before entering the portal. A normal RL agent that only considers its position cannot reliably solve this without considering past information (namely, whether the correct pillar was touched yet). The RM state conveniently encodes this salient information, but the RM state cannot be computed with certainty in our noisy problem setting.\n\n[1] Fainekos et al. \"Temporal logic motion planning for dynamic robots.\" Automatica, 2009.\n\n[2] Doherty et al. \"A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems.\" Autonomous Agents and Multi-Agent Systems 2009.\n\n[3] Camacho et al. \"Reward machines for vision-based robotic manipulation.\" ICRA, 2021.\n\n[4] Aksaray et al. \"Q-learning for robust satisfaction of signal temporal logic specifications.\" IEEE Conference on Decision and Control, 2016.\n\n[5] Tuli et al. \"Learning to follow instructions in text-based games.\" NeurIPS, 2022.\n\n[6] Umili et al. \"Visual reward machines.\" Neural-Symbolic Learning and Reasoning, 2022.\n\n[7] Ghasemi et al. \"Task-oriented active perception and planning in environments with partially known semantics.\" ICML, 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Nte4MZxdWh", "reviewer": "Reviewer_pete", "summary": "The authors present an extension of the general “Reward Machine” framework to partially observable reinforcement learning environments. In particular, they consider cases where an agent does not have direct access to a labeling function which maps from state transitions to the relevant propositions needed to update the Reward Machine state. They propose a model that learns to directly predict the Reward Machine state from the agent’s trajectory and motivate their approach with both theoretical and experimental results.", "questions": "See above: is there an account for why TDM performance is substantially better on than the baselines on some environments, but not on others?", "limitations": "I feel that the authors have adequately addressed the limitations and potential impact of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I do not have any major complaints with this paper. It is well-motivated, well-reasoned, and well-communicated. I particularly appreciate the inclusion of a concrete running example as a way to elucidate the theoretical points made. The empirical experiments are also very thorough, consisting of multiple runs, multiple baselines, and a wide variety of environments.", "weaknesses": "If there is a quibble to be made, it is that the paper could benefit from slightly more analysis on the differences between environments. It’s notable that the TDM approach is only one that approximates oracle performance across all 4 environments, but in some environments it is one of many that do so. Is this because those environments are generally less challenging or does some other explanation present itself? I’m slightly surprised that the baselines seem competitive in the color matching environment, in particular, since it is the only non-tabular environment. If the authors have any insight on this issue, it could be nice to include it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for the strong endorsement of our work. We are glad that you recognize its merits across all the major criteria. Please see our response to your feedback and questions below.\n\n> **is there an account for why TDM performance is substantially better on than the baselines on some environments, but not on others?**\n\nThis is a great question and something we will certainly spend more time discussing in the paper. As you noted, TDM is the only method that consistently performs well, but Naive and IBU *occasionally* match the performance. We believe there are two reasons this occurs:\n\n1. In some environments, the simplifying assumptions made by Naive or IBU are reasonable. Thus, the predicted RM state belief may be close to the ground truth RM state belief. \n2. In other cases, an inaccurate RM state belief can still lead to a reasonable policy. \n\nTo elaborate, we can consider each environment.\n\n**Traffic Light**\n\nRecall the main challenge is that the agent can only see the colour of the light when facing it. TDM and IBU both avoid the pitfall of driving backwards through the light because they can model the *chance* the agent may have run a red light. In fact, Figure 4 shows that IBU and TDM predict similarly accurate beliefs under random trajectories — this implies we are in case 1 and indeed IBU learns a reasonable policy on Traffic Light. \n\nNaive doesn’t model the difference between driving through a green light and driving backwards through an unknown light colour (as the probability of the light being red is less than 0.5) and falls into the trap.\n\n**Kitchen**\n\nThe correct initial belief should reflect that each chore (independently) has a ⅓ chance of being done (recall some chores may randomly start in the “done” state). This belief should not change until the agent enters the kitchen and observes the true state of all the chores.\n\nIBU fails here by gradually increasing its belief that chores are done over time without entering the kitchen (our response to Q3 from Reviewer sM3w includes a brief explanation of this). This is problematic since IBU conflates two behaviours into the same belief: completing all the remaining chores by entering the kitchen, and only wandering outside the kitchen (which incurs less cost and time to perform than the former, and is preferred by the agent). \n\nInterestingly, Naive also models an incorrect belief but still manages to learn a reasonable policy. Before entering the kitchen, its belief inaccurately reflects that none of the chores are done (as they each have below 0.5 probability). Entering the kitchen allows it to deduce with certainty which chores have been done and which still need to be done. Thus, we are in case 2: Naive models the initial belief incorrectly, but this leads to the same reaction as if it had the correct belief — entering the kitchen.\n\n**Colour Matching**\n\nRecall that the propositions relate to “reaching” certain pillars, which we take to mean the agent is within $d$ distance of the pillar. Unlike in MiniGrid, it is theoretically possible for abstraction models to capture the labelling function perfectly since this environment is an MDP. However, given that our abstraction models were only trained on limited datasets, we noticed that they were often uncertain about propositional values when the distance to a pillar was *approximately* $d$. \n\nThis case commonly arises under a random policy, and only TDM captures this uncertainty well. Naive discretely predicts the proposition is either true or false. IBU captures the uncertainty on the first step near the distance threshold $d$, but in MuJoCo, the agent tends to stay near this threshold for several steps. This causes IBU to compound this uncertainty, resulting in a belief that the proposition had occurred with very high probability. These results are reflected in Figure 4. \n\nIn the RL setting, the policy has quite a bit of leeway to correct for such errors. We observed that the agent tends to go much closer than distance $d$ to the pillar, resulting in a more certain belief. However, we are not sure if this is intentional or simply a side effect of the agent’s momentum towards the pillar while trying to solve the task *quickly*. \n\nTo summarize, only TDM appears to reliably perform well, matching our theoretical understanding since it is the only *consistent* method in POMDPs. Naive and IBU can sometimes perform well, but it depends heavily on the specific task.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to the reviewers for their time and for their detailed and informative reviews. Reviewers found “the combination of RMs with deep RL algorithms to handle noisy and uncertain environments [to be] innovative” (ed91), noting that the work was “broadly applicable across many fields as it doesn't require a ground-truth interpretation of domain-specific vocabulary” (qw5f). Reviewers praised the inclusion of “rigorous mathematical definitions and theoretical insights” (ed91), and recognized our experimentation as “very thorough” (pete). 

Reviewers raised a number of good points. In the individual reviews that follow, we have addressed the major questions raised by reviewers, together with additional comments. We are confident that we can address all feedback in the final paper. In two instances, we were uncertain whether we had correctly interpreted reviewer comments. If we have not adequately addressed a question in the review, please raise this during the discussion period. We appreciate reviewers’ engagement with the material and are keen to answer reviewer questions. 

Some of the main points are summarized below. 

1. [**A subset of reviewers suggested improvements to the presentation.**]

Reviewer sM3w identified details relating to our framework that were unclear. We will make the following changes to improve readability for the broader NeurIPS audience:

- We’ll include an architectural diagram (global pdf, Fig. 1) to clarify the elements of our framework including which elements are available during training and execution.
- We’ll include an algorithm box (global pdf, Fig. 2) that provides a more precise description of how we incorporate abstraction models into RL.

Reviewers sM3w, qw5f, and pete suggested further elaboration of the experimental results. We will provide a more detailed explanation of the experimental outcomes in line with our answers to reviewer questions. We have also prepared videos of the trained agents to be released with the final version. 

2. [**Further discussion of foundation models.**]

Reviewer ed91 requested further discussion on the possibility of foundation models as abstraction models. We agree that this adds to the paper, and have conducted some preliminary experiments using GPT-4o as a zero-shot abstraction model. 

We considered the Traffic Light MiniGrid domain, where we rendered RGB images of the environment and prompted GPT-4o to detect if the agent was standing on a coloured grid cell (representing a propositional occurrence). We found that GPT-4o could determine propositional values to predict accurate RM state beliefs with our methods, achieving performance close to a model trained on ground-truth data, and significantly outperforming a random abstraction model (global pdf, Fig. 3). 

We will further discuss the limitations of current foundation models. In particular, these models provide no easy way to implement TDM (which had the most robust performance in our experiments), and only the largest available vision-language models were able to interpret the MiniGrid images correctly. 

3. [**Dependence on domain knowledge and/or ground-truth features.**]

Reviewer qw5f mentioned that our noisy RM framework requires domain knowledge to specify propositions and abstraction models, and Reviewer ed91 noted that abstraction models can potentially leak relevant features to the learning algorithm, particularly when trained on ground-truth data. 

We acknowledge that these are weaknesses, but it’s important to understand why our work is significant nonetheless. RMs and related formal languages are so effective for specifying reward functions because they expose a task’s logical and temporal structure over an abstract vocabulary. There is a rich literature that leverages these specifications to synthesize controllers with provable guarantees when an environment model is available, but they can also significantly improve the performance and interpretability of deep RL algorithms in the absence of such a model. 

Up until now, works leveraging these specifications largely depended on the availability of “perfect” labelling functions that identify ground-truth features for any environment transition. Our work relaxes this strong assumption by instead relying on abstraction models, which can be noisy. As shown above, foundation models are a promising way of implementing abstraction models in new environments, and they will likely be noisy. We consider our work an important step towards making RMs more widely applicable in the real world.

Meta-review: This paper investigates the use of Reward Machines in Deep Reinforcement Learning (RL) for handling noisy and uncertain environments. It frames the problem as a Partially Observable Markov Decision Process (POMDP) and proposes a set of RL algorithms leverage the task structure under uncertain interpretation of domain-specific vocabulary. The theoretical analysis reveals the limitations of naive approaches, while experimental results demonstrate that the proposed algorithms successfully leverage task structure to improve performance under noisy interpretations. The findings provide a general framework for exploiting Reward Machines in partially observable environments.

Stengths: the reward machine formalsim holds potential for interpreting instructions, enforcing safety constraints, and more. This paper extends its use to the partially-observable setting which is significant for real-world use of RL. Reviewers appreciated the theoretical and empirical analysis provided. The paper is clearly written.

Weaknesses: the method requires a ground-truth reward function and this can be seen as an immediate limitation. There was a concern about fairness of empirical comparisons but that concern has been addressed with discussion.

The paper was extensively discussed and all major concerns were addressed by the author. The authors should make all clarifications requested by the reviewers.
Decision: Accept (poster)