Reward Machines for Deep RL in Noisy and Uncertain Environments

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.

is there an account for why TDM performance is substantially better on than the baselines on some environments, but not on others?

This 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:

1. 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.
2. In other cases, an inaccurate RM state belief can still lead to a reasonable policy.

To elaborate, we can consider each environment.

Traffic Light

Recall 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.

Naive 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.

Kitchen

The 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.

IBU 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).

Interestingly, 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.

Colour Matching

Recall 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$.

This 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.

In 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.

To 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.

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.

What are the constraints of the abstraction model?

Our 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.

We 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:

1. 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.
2. 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.

the modeling of belief as binary might require domain-specific knowledge

You are correct if you are stating that our propositions must be binary. Other formal languages with more expressive vocabularies have also been considered.

• In Signal Temporal Logic [4], the vocabulary is a continuous-valued signal that can represent values such as distances and velocities.
• Sun et al [6] consider programs as a specification with a rich set of domain-specific primitives.
• Tuli et al [5] consider Linear Temporal Logic over open-ended entity relations described in natural language e.g. (“potato”, “is”, “chopped”).

Our 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.

Most of the compared methods in the paper are proposed by the authors themselves.

We 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.

• 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.
• 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.
• 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.
• 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]).

How about the interpretability or visualization of the learned model?

We 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.

The paper primarily uses Proximal Policy Optimization (PPO) for experiments.

We 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.

The relations of RM, noisy RM environment and the evaluating environment is not clear to me

Unfortunately, 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.

[1] Fainekos et al. "Temporal logic motion planning for dynamic robots." Automatica, 2009.

[2] Doherty et al. "A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems." Autonomous Agents and Multi-Agent Systems 2009.

[3] Camacho et al. "Reward machines for vision-based robotic manipulation." ICRA, 2021.

[4] Aksaray et al. "Q-learning for robust satisfaction of signal temporal logic specifications." IEEE Conference on Decision and Control, 2016.

[5] Tuli et al. "Learning to follow instructions in text-based games." NeurIPS, 2022.

[6] Umili et al. "Visual reward machines." Neural-Symbolic Learning and Reasoning, 2022.

[7] Ghasemi et al. "Task-oriented active perception and planning in environments with partially known semantics." ICML, 2020.

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.

… 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? …

Indeed, 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].

The 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.

This 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.

We 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.

The discussion on foundational models is mentioned early on but is missing from the experiments, discussion, and conclusion.

An RM framework that incorporates foundation models is an important and exciting direction. We are happy to include a further discussion on this topic.

We’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”.

We 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.

Line 32 mentions numerous references without distinguishing their importance

We 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.

[1] Fainekos et al. "Temporal logic motion planning for dynamic robots." Automatica, 2009.

[2] Doherty et al. "A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems." Autonomous Agents and Multi-Agent Systems, 2009.

[3] Camacho et al. "Reward machines for vision-based robotic manipulation." ICRA, 2021.

[4] Xu & Topcu. "Transfer of temporal logic formulas in reinforcement learning." IJCAI, 2019.

[5] Vaezipoor et al. "Ltl2action: Generalizing ltl instructions for multi-task rl." ICML, 2021.

Thank you for your constructive review. We take seriously the issues you raised regarding clarity and will revise the manuscript accordingly.

Should the abstraction model be the method or the problem?

The 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.

Regarding 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.)

Could authors provide … a definition of optimality …

Thanks 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.

The 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.

We'll clarify both of these concepts in the paper.

Where do the ground truth labels come from? Especially, Naive, IBU, and TDM …

We 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.

Naive 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).

In three of the domains, IBU is even worse than naive … Could authors explains why this is happening?

Naive 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.

Example 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.

In 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.

Some writing suggestions

Very good suggestions. Thank you.

• We will include an algorithm box describing how we combine RL with abstraction models (see the global response pdf).
• 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.

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

To 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.

The related work section elaborates upon the novelty of our framework in comparison to previous works.

Limitations

Agreed. These were explicitly acknowledged as limitations in the paper.