Reward Machines for Deep RL in Noisy and Uncertain Environments

Authors: andrew c li
zizhao  chen
toryn q klassen
pashootan  vaezipoor
georgian  io
rodrigo  toro
sheila a mcilraith
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:38:41

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, they critically rely on a ground-truth interpretation of the domain-specific vocabulary that forms the building blocks of the reward function—such ground-truth interpretations are elusive in the real world due in part to partial observability and noisy sensing. 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.

Main paper: 
 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 as propositional variables, formal languages like Linear Temporal Logic (LTL) [45] capture complex temporal patterns-such as the objectives of an agent-by composing variables via temporal operators and logical connectives. These languages provide well-defined semantics while enabling semantics-preserving transformations to normal-form representations such as automata, which can expose the discrete structure underlying an objective to a 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 garner significant improvements in sample efficiency (e.g., [53, 55, 18] ). Importantly, Reward Machines (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 and that can be deployed without a ground-truth labelling function. We show how preexisting abstraction models-uncertain estimators of abstract, task-relevant features that may manifest as pretrained neural networks, sensors, heuristics, or otherwise-can be brought to bear to improve learning efficiency.(3) We theoretically and experimentally evaluate our proposed RL algorithms. Theoretically, we discover a 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. 
background: 
 Notation. Given a set of random variables, X, ∆X is the set of distributions over X; (•) denotes a particular distribution; and for a categorical distribution w ∈ ∆X and some x ∈ X, we denote w[x] as the probability of x under w. We use x i:j as a shorthand for the sequence x i , . . . , x j .POMDPs. A Partially Observable Markov Decision Process (POMDP) ⟨S, O, A, P, R, ω, µ⟩ [3] is defined by the state space S, observation space O, action space A, reward function R, transition distribution P : S × A → ∆S, observation distribution ω : S → ∆O, and initial state distribution µ ∈ ∆S. An episode begins with an initial state s 1 ∼ µ(•) and at each timestep t ≥ 1, the agent observes an observation o t ∼ ω(s t ), performs an action a t ∈ A, transitions to the next state s t+1 ∼ P (s t , a t ), and receives reward r t = R(s t , a t , s t+1 ). Denote the agent's observation-action history at time t by h t = (o 1 , a 1 , . . . , o t-1 , a t-1 , o t ) and the set of all possible histories as H. A fully observable Markov Decision Process (MDP) serves as an important special case where the observation at each time t is o t = s t .Reward Machines. A Reward Machine (RM) [53] is a formal automaton representation of a non-Markovian reward function that captures temporally extended behaviours. Formally, an RM R = ⟨U, u 1 , F, AP, δ u , δ r ⟩, where U is a finite set of states, u 1 ∈ 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, δ u : U × 2 AP → (U ∪ F ) is the state-transition function, and δ r : U × 2 AP → 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 an RM captures the high-level structure of a non-Markovian reward function, concrete rewards in an environment are determined with the help of a labelling function L : S × A × S → 2 AP , a mapping that abstracts state transitions (s t-1 , a t-1 , s t ) in the environment to the subset of propositions that hold for that transition. To obtain rewards, the sequence of environment states and actions s 1 , a 1 , . . . , s t , a t , s t+1 are labelled with propositional evaluations σ 1:t , where σ i = L(s i , a i , s i+1 ) ∈ 2 AP . A sequence of transitions in the RM are then followed based on σ 1:t to produce the reward sequence r 1:t . In an MDP environment, rewards specified by an RM are Markovian over an extended state space S × U ; hence, there is an optimal policy of the form π(a t |s t , u t ) where u t ∈ U is the RM state at time t [53] . During execution, u t can be recursively updated given u t-1 by querying L after each environment transition.3 Problem Framework 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 preexisting knowledge over how a set of high-level features Z are grounded within the environment. Abstraction models are easier to obtain than 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 the real world, they might manifest as pretrained foundation models [46, 37, 4, 14] , sensors [16] , task-specific classifiers [20] , or so on.We refer to the tuple P = ⟨E, R, L, M⟩ as a Noisy Reward Machine Environment (depicted in Figure 1 ). Given P, our goal is to obtain a policy π(a t |h t , z 1:t ) based on observations and outputs from the abstraction model up to time t that maximizes the expected discounted return E π [ ∞ t=0 γ t r t ] for some discount factor γ ∈ (0, 1]. In this work, we assume π is trained via RL, and we assume that the ground-truth rewards r i are observable during training only. Notably, the trained policy π can be deployed without access to the ground-truth labelling function L. 
running example: 
 The Gold Mining Problem (Figure 2 ) serves as a running example of a Noisy RM Environment. A mining robot operates in a grid with a non-Markovian goal: dig up at least one chunk of gold ( ) and deliver it to the depot ( ). The environment is an MDP where the robot observes its current grid position and its actions include moving in the cardinal directions and digging. A labelling function L associates the propositions AP = { , } 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.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 as to whether a cell contains gold, which is captured by an u (0) u (1) u (2) ⟨o/w, 0⟩ ⟨ ∧ ¬ , 0⟩ ⟨ , 0⟩ ⟨o/w, 0⟩ ⟨ , 1⟩ Figure 2:The Gold Mining Problem is a Noisy RM Environment where the agent's interpretation of the vocabulary is uncertain. Left: The four rightmost cells yield gold ( ) while two cells in the second column yield iron pyrite, which has no value. The agent cannot reliably distinguish between the two metals-cells are labelled with the probability the agent believes it yields gold. Right: The RM emits a (non-Markovian) reward of 1 for collecting gold and delivering it to the depot ( ).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 it could learn an optimal Markovian policy π(a t |s t , u t ) with a relatively simple form (u t is easily computed with access to L). Intuitively, such a policy should collect gold while in RM state u (0) and head to the depot while in RM state u (1) . Unfortunately, when the agent does not have access to L, we cannot directly learn a policy with the simpler Markovian form above. In the following sections, we 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 a Noisy RM Environment? (2) How does the abstraction model M affect the problem? (3) How does not observing the labelling function L affect the problem? We provide proofs for all theorems in Appendix A.Observe that uncertainty in the labelling function is only relevant insofar as it informs the agent's knowledge of the current RM state u t since rewards from an RM R are Markovian over extended states (s t , u t ) ∈ S × U . Our first result is that a Noisy RM Environment ⟨E, R, L, M⟩ can be reformulated into an equivalent POMDP with state space S × U and observation space O (Theorem 4.1). Here, we say two problems are equivalent if there is a bijection between policies for either problem such that the policies have equal expected discounted return and behave identically given the same history h t . Thus, optimal behaviour in a Noisy RM Environment can be reduced to solving a POMDP. One may notice that the abstraction model M doesn't appear in the POMDP reformulation at 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 a Noisy RM Environment ⟨E, R, L, M⟩, and P ′ be a Noisy RM Environment ⟨E, R, L, M ′ ⟩. Then P and P ′ are equivalent.We also contrast our proposed framework, where the agent does not have direct access to L, 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 4.3). û1 = u 1 . For t > 1, predict ût = δ u (û t-1 , M(h t )).A weakness of this approach is that it does not represent the uncertainty in its prediction. Furthermore, since RM state predictions are updated recursively, an error when predicting ût will propagate to all future predictions (û t+1 , ût+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 → 2 AP . For a history h t , M takes the current grid position s t and predicts is true if it believes there is at least a 50% chance it yields gold when it performs a digging action. We assume the agent can always predict correctly. Observing Figure 2 , we see that M agrees with L in all cases except at 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. 
independent belief updating (ibu): 
 In order to capture the uncertainty in the belief over the RM state u t , one may instead wish to model a probability distribution ũt ∈ ∆U . Given an abstraction model of the form M : H → ∆(2 AP ) that Table 1 : 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 ABSTRACTION TARGET CONSISTENT CONSISTENT MODULE MODEL (MDPS) (POMDPS) NAIVE H → 2 AP L(st-1, at-1, st) ✓ ✗ IBU H → ∆(2 AP ) L(st-1, at-1, st) ✓ ✗ TDM H → ∆U ut ✓ ✓predicts probabilities over possible propositional evaluations L(s t-1 , a t-1 , s t ), an enticing approach is to derive ũt by probabilistically weighing all possible RM states at time t -1 according to the previous belief ũt-1 along with all possible evaluations of L(s t-1 , a t-1 , s t ) according to M. Method 2 (IBU) Given M : H → ∆(2 AP ), predict a distribution over RM states ũt ∈ ∆U as follows. Set ũ1 [u 1 ] = 1 and ũ1 [u] = 0 for u ∈ U \ {u 1 }. For t > 1, set ũt [u] = σ∈2 AP ,u ′ ∈U 1[δ u (u ′ , σ) = u] • ũt-1 [u ′ ] • M(h t )[σ]On the surface, IBU may appear to solve the error propagation issue of the Naive approach by softening a discrete belief into a probabilistic one. Surprisingly, updating beliefs ũt 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 are linked, rather than independent. Since the computation of ũt aggregates t queries to M, noise in the outputs of M can dramatically amplify if the correlation between these noisy outputs is not considered. This is best illustrated by an example. Example 5.2 The mining agent now considers a probability distribution over propositional assignments of { , }. We assume the agent always perfectly determines and applies its belief of locations yielding gold; e.g., digging in the cell the agent believes has gold with 0.3 probability yields the distribution (∅ : 0.7, { } : 0.3, { } : 0, { , } : 0). Consider a trajectory where the agent digs at this cell multiple times. After mining once, IBU updates the RM state belief ũt to reflect a 0.3 probability of having obtained gold. After mining twice, this increases to 0.51 and in general, the belief reflects a 1 -0.7 k probability after mining k times. In reality, mining more than once at 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.Example 5.2 demonstrates a challenge when aggregating multiple predictions from a noisy classifierthe 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, 61] , 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 an abstraction model M : H → ∆U designed to directly predict a distribution over RM states given the history. Such an abstraction model might manifest as a meta-classifier 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 a dataset of histories h t and their associated (ground-truth) RM states u t . Given an abstraction model M : H → ∆U , TDM simply returns the output of M. Method 3 (TDM) Given an abstraction model of the form M : H → ∆U predict M(h t ) directly.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, with our conclusions summarized in Table 1 . We consider how accurately an inference module models its target distribution Pr(u t |h t ). This largely depends on the veracity of the abstraction model M, but nonetheless, it is desirable that the inference module precisely recovers Pr(u t |h t ) under an ideal abstraction model M * . If this is possible, then we say that an inference module is consistent. Definition 5.3 (Consistency) Consider an inference module f : Z + → ∆U . f is consistent if there exists some M * : H → Z such that for every history h t ∈ H, running f on h t using M * as the abstraction model results in the belief Pr(u t |h t ).In the case that E is an MDP, Naive, IBU, and TDM are all consistent since there exists an abstraction model that can recover the labelling function L (for Naive and IBU) and u t (for TDM) with certainty. However, in the general case when E is a 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 a belief over RM states. We examine whether these methods are robust to uncertainty in the outputs of abstraction models, and whether they offer advantages over end-to-end RL algorithms that do not attempt to exploit task structure. Our experimental settings involve challenges that arise when scaling to complex, real-world environments: temporally extended reasoning, partial observability, high-dimensional observations, and sparse rewards.Our environments include the Gold Mining Problem as a toy environment, along with two MiniGrid [9] environments with image observations and a MuJoCo robotics environment (Figure 3 ). Full details on the environments are provided in Appendix B.Traffic Light is a partially observable MiniGrid where the agent must drive along a road to 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 a delayed penalty if it runs the red light. The agent only has a forward-facing camera and it can drive forwards, backwards, wait, or make a U-turn. We encode this task with an RM (Figure 7 ) with propositions for running a red 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 be uncertain about the evaluation of the red light proposition.Kitchen is a partially observable MiniGrid where a cleaning agent starts in the foyer of a home and is tasked with cleaning the kitchen before leaving. There are 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 to begin with). However, the agent doesn't know how clean the kitchen is until it enters it. For each chore, a proposition represents whether that chore is "done" (e.g. the dishes are clean) in the current state of the environment-thus, the propositional evaluations are unknown to the agent until it enters the kitchen. The RM for this task (omitted due to its size) uses the automaton state to encode the subset of chores that are currently done and gives a reward of 1 for leaving the house once the kitchen is clean. 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 it 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 a set of 18 possible colours in each episode, so to reliably solve the task, the agent must learn the correct associations of colour names to their RGB values.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 an upper bound on performance, we compare against an Oracle agent that has access to the labelling function. In the toy Gold Mining Problem, policies are trained using Q-learning [52] with linear function approximation [41] . In all other domains, policies are neural networks trained with PPO [48] , and the Memory-only policy is Recurrent PPO [25] , a popular state-of-the-art deep RL method for general POMDPs.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 it 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 in 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 L and ground-truth RM states. To obtain abstraction models, we train classifiers on their respective target labels and we select optimal hyperparameters according to a grid search. 1 We note that all abstraction models are trained on equivalent data, 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 a classifier trained to predict propositional evaluations (Figure 6 ). 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.We report RL learning curves for each method and environment in Figure 4 . The key results are:(R1) TDM performs well in 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. (R2): RL makes little progress on any domain when the task structure is not exploited. Specifically, 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 or 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 a discussion).We now highlight the most notable qualitative behaviours that were observed. For a 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 to 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 is similar to Example 5.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).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 a test set of 100 fixed trajectories generated by a random policy (following the same distribution as the data used to train the abstraction models). Since each inference module aims to capture a belief, we evaluate them according to the log-likelihood of the true RM state under the belief, averaging over the predictions at all timesteps. To avoid log 0 when Naive makes an incorrect prediction, we lower bound all log-likelihoods at ln 0.01.(R4): TDM is more accurate when predicting a belief over RM states compared to Naive or IBU on all domains.As an additional experiment, we assess whether GPT-4o can serve as an effective zero-shot abstraction model in the Traffic Light domain. We render RGB images of the environment and use GPT-4o to evaluate propositions described through text. With this abstraction model, we evaluate Naive and IBU on the test set from Section 6.5. We baseline these against the inference modules from Section 6.5 that use abstraction models trained via supervised learning, as well as abstraction models with randomly initialized weights. Results and further details are provided in Figure 8 of the Appendix.(R5): GPT-4o is an effective zero-shot abstraction model for Naive and IBU. As an abstraction model, GPT-4o is nearly as effective as a custom model trained from ground-truth data, and is significantly more effective than a randomly initialized neural network. 
related work: 
 Many recent works leverage structured task specifications such as RMs or Linear Temporal Logic (LTL) in deep RL. However, the vast majority of these works assume access to the ground-truth labelling function when acting, e.g. [59, 30, 34, 39, 18] . We note a few works that learn policies that do not rely on a labelling function for execution. Kuo et al. [33] solve LTL tasks by encoding them with a recurrent policy. Andreas et al. [2] and Oh et al. [44] learn modular subpolicies and termination conditions, avoiding the need for a 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 [43] empirically show that current RM algorithms are brittle to noise in the labelling function but do not offer a solution. Tuli et al. [57] teach an agent to follow LTL instructions in partially observable text-based games using the Naive method, but only consider propositions that are observable to the agent. Umili et al. [58] use RMs in visual environments with a method similar to IBU, while Hatanaka et al. [24] update a belief over LTL 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 a partially observed state. The closest work by Toro Icarte et al. [54] applies RMs to POMDPs but only considers propositions defined as a function of observations.LTL has long been used for specification in motion planning [31] , 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. [13] propose an approach assuming that propositions in a state occur probabilistically in an i.i.d. manner. Ghasemi et al. [19] , Verginis et al. [61] , Hashimoto et al. [23] , and Cai et al. [6] consider a setting where propositions are initially unknown but can be inferred through interactions. 
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 of the task, as exposed by the Reward Machine, while exploiting prior knowledge through the use of abstraction modelspreexisting models that noisily ground high-level features into the environment. Through theory and experiments, we show the pitfalls of naively aggregating outputs from a noisy abstraction model, while simultaneously demonstrating how abstraction models that are aware of temporally correlated predictions can mitigate this issue. 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 to ameliorate the impact of uncertain interpretations of symbols, which can lead to dangerous outcomes. We note that our proposed methods elucidate the internal decision-making process of RL agents within a formal framework, potentially providing enhanced interpretability. A limitation of TDM, our best-performing method, is that it 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 (some RM transitions might very rarely be observed), so deploying TDM could lead to poor outcomes.Our experiments show the promise of leveraging pretrained foundation models (e.g., GPT-4o) as general-purpose abstraction models in a 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. A 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-rewards given by the RM under the ground-truth evaluation of propositions-during training. ũt (u) = σ∈2 AP ,u ′ ∈U 1[δ u (u ′ , σ) = u] • ũt-1 (u ′ ) • M(h t )[σ] = σ∈2 AP 1[δ u (u t-1 , σ) = u] • M(h t )[σ] = 1[δ u (u t-1 , L(s t-1 , a t-1 , s t )) = u] = 1[u t = u]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 a strictly probabilistic nature.Consider a POMDP with two states, s (0) and s (1) , where the initial state is equally likely to be s (0) or s (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. 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) , s (0) , . . .) or (s (1) , s (1) , . . .).Let there be a single proposition A that holds when the agent is currently in state s (0) . Let the RM R have two states: an initial state u (0) that transitions to the state u (1) when the proposition A holds. The ground-truth RM state belief is given by Pr(u t = u (1) |h t ) = 0.5 for all timesteps t ≥ 2. This belief cannot be captured by Naive under any abstraction model, thus, Naive is not consistent.Proposition A.5 IBU is not necessarily consistent in general POMDP environments E.Proof. Suppose for a contradiction that IBU is consistent and therefore, produces ũt = Pr(u t |h t ) for some M * .Consider the same POMDP as in Proposition A.4, with one small change. Now, while in any state s (i) the observation emitted is o with 0.5 probability or o (i) (revealing the state) with 0.5 probability. Consider a history h t with the observation sequence o, o (1) . After seeing the observation o, it must be the case that ũ2 assigns 0.5 probability to both u (0) and u (1) , as before. Then after seeing the observation o (1) , it becomes certain that the persistent state is s (1) , and therefore P∇(u t |h t ) assigns probability 1 to u (0) . However, regardless of how M * (h t ) is assigned, it is impossible to achieve this belief for ũ3 . This is since ũ2 [u (1) ] = 0.5 but there are no RM transitions out of u (1) , so ũ3 [u (1) ] ≥ 0.5. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: We do not release data or models. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or 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? 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? 
 
 Appendix: The Gold Mining Problem is described in Example 3.2. We also introduce a small (Markovian) penalty of 0.02 each time the agent selects a movement action to incentivize the agent towards shorter solutions.Policy models. The Oracle baseline learns a Q-value for each (location, RM state, action) combination without memory or function approximation. The Memory only baseline and all the proposed methods are conditioned on 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 a tractable alternative to representing the entire history without neural network encoders.All approaches except Oracle use a linear decomposition of Q-values to allow for generalization and to reduce the number of estimated Q-values. Naive, IBU, and TDM use the following approximation.Q(location, ũ, memory 1:6 , action)= u∈U ũ(u) • Q 1 (u) + Q 2 (location, u, action) + 1 6 6 i=1 Q 3 (location, u, memory i , action)The Memory only baseline use the following approximation.Q(location, memory 1:6 , action) = Q 1 (location, action) + 1 66 i=1 Q 2 (location, memory i , action)Hyperparameters. All methods use a learning rate of 0.01, a discount factor of 0.99, and a random action probability of ϵ = 0.2.Evaluation details. All methods are trained for 1M steps, and the policy is evaluated every 10K steps without ϵ-greedy actions. Since the evaluation policy and the environment are deterministic, each evaluation step records the return from a single episode.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 is initialized such that each chore needs cleaning with 2 3 probability, and a chore can be completed by visiting that square. The agent can observe tasks that are completed when inside the kitchen. There is one proposition per chore marking whether that chore is done (regardless of whether the agent can observe this) and a 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 it so the agent must do so purposefully.EQUATIONu (4) ⟨package, 1⟩ 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 a policy network. The observation encoder takes in the current environment observation o t as well as a belief over RM states (when applicable) and produces an encoding. This encoding is fed to a 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-unit hidden layers and produces a 64-dimensional encoding.We use a single GRU layer with a 64-dimensional history encoding. The actor and critic both use two 64-dimensional hidden layers. The abstraction models use a separate, but identically structured observation encoder and GRU layer. The history encoding is fed to a single, linear output layer.The atomic propositions in the Colour Matching domain are {a, b, c, d}, where a 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, a negative reward of -0.2 is issued, but this penalty is not applied if the agent visits the same pillar multiple times in succession. A reward of 1 is given for visiting the target pillar, and then for subsequently going to the portal. We do not show the RM due to the excessive number of edges. Network architectures. The policy and grounding model networks are similar to those in the previous experiments. The policy uses an observation encoder with two 256-unit hidden layers and a 128-unit output layer. This is fed to a single GRU layer with a hidden size of 128. The actor has one encoding layer with hidden size 128, followed by linear layers to predict a mean and standard deviation for continuous actions. The critic has two 128-unit hidden layers.The abstraction models for Naive and IBU are MLPs with five 128-unit hidden layers (the environment is 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-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. Gold MiningThe agent typically digs at a nearby cell containing iron pyrite and immediately heads to the depot.There is a cell that the agent believes yields gold with 0.6 probability 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 the agent heads to the depot.The agent repeatedly digs at the same locations within the same episode before heading to the depot.Under IBU, the chance of obtaining gold on each step is assumed to be independent (even when digging at the same square). Hence, the agent repeatedly digs in the same place, even though digging more than once in any location has no utility.The agent mines at several squares to maximize the chance of obtaining gold before heading to the depot.Under TDM, we include the assumption that the belief of having obtained gold does not increase on repeated digs at the same square.The agent drives through the intersection in reverse (including when the traffic 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.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 a 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 to IBU.The agent learns the correct behaviour of entering the kitchen and completing the remaining tasks.Interestingly, the agent's initial belief over RM states is not 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 a 1 3 probability. This incentivizes the agent to enter the kitchen, allowing it to observe which tasks still need to be completed.The agent wanders around outside the kitchen and fails to complete the chores.While outside the kitchen, the agent predicts on each timestep a 1 3 probability for each chore that it started in a "done" state. As it treats this chance as independent on each timestep, the chance that each chore was done at some point up to time t is predicted to be 1 -( 2 3 ) t . By wandering around outside the kitchen for long enough, the agent believes that all chores are completed with close to probability 1, giving it no incentive to enter the kitchen.The agent learns the correct behaviour of entering the kitchen and completing the remaining tasks.TDM correctly models the initial belief over RM states reflecting that each chore has an independent 1 3 chance of being done before the agent has entered the kitchen. This incentivizes the agent to enter the kitchen and complete all chores that may still need to be completed. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 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 to 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. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).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. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

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

3. Some writing suggestions:
- 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.
- Make it clear about the problem setting. In particular, is the abstraction of model given as a part of the problem?
- 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?    
- Line 222 "Given an abstraction model of the form M : H → ∆U predict M(h_t) directly." what does this mean?
questions: 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?

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

3. In three of the domains, IBU is even worse than naive that do not consider stochasticity? Could authors explains why this is happening?
limitations: 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.
paper_summary: paper_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:
- Proposing framework for using RMs in deep RL in partially observable environments.
- Theoretical analysis identifying pitfalls in naive approaches.
- Experimental results demonstrating improved performance under noisy conditions.
- Discussing limitations and proposing future work for general-purpose models and relaxing ground truth reward assumptions.
strength_weakness: strength_weakness: - It is unclear how well the methods perform without ground-truth RMs, raising questions about additional effort required for new environments.
- 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.
- 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.
questions: 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.

The 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

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


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

The relations of RM, noisy RM environment and the evaluating environment is not clear to me. The evaluating environments are just simple POMDP environment.
questions: 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?

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

How 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: limitations: See weakness
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: I feel that the authors have adequately addressed the limitations and potential impact of their work.

Comments: title: Thanks
Response
Re: sM3w Optimality & Response to abstraction model problem or method (Part 2)
Re: sM3w Optimality & Response to abstraction model problem or method (Part 1)
Optimality
Response to abstraction model problem or method
comment: These clarifications will be insightful to readers and we will certainly make sure they are included. Thank you again for your positive and constructive review. We greatly appreciate it.
We're happy to hear that we've managed to alleviate most of your concerns. Thanks again for the review, and if there are any outstanding concerns that we can address, please let us know.
Thanks again for your constructive comments. We completely agree that the broader contextualization with respect to foundation models and the clarification of the role of abstraction models are an improvement. We will ensure these key points are included in the final paper.
We will be sure to include these explanations in the paper and we thank you once again for the productive discussion. Please let us know if you have any final questions or concerns that we can address.
Thanks for the clarification. Now I am more clear about optimality, but I still believe those terms are not precisely defined in the paper. For example, line 160 is not a definition, just a notation. The authors need to include some explanations like the rebuttal shows. I have raised my evaluation accordingly.
Thank you for the response. The additional clarifications are much appreciated, and I would encourage the authors to include them in some form in the appendix of the paper.
Thank you for your response. Most of my concerns have been addressed. I will raise my score.
Dear Reviewer qw5f, does the author's response change your assessment or do you still have concerns? It would be helpful to raise them now while we can still ask the authors for more clarification.
Thanks Reviewer sM3w for actively engaging with the authors to discuss your concerns -- I appreciate it and I'm sure the authors do too! Please let me and the authors know if you still have concerns following the discussion.
> I still don't understand what make a distribution $P(u_t | h_t)$ optimal? Or are you saying an optimal belief state is the distribution that deterministically predict the ground truth RM state?

Related to [4], you cannot always deterministically predict the true RM state from the history in a POMDP environment — multiple different rollouts of environment states $s_1, …, s_t$ (yielding different RM states) can result in the same history $h_t = (o_1,...,o_t)$. The optimal RM state belief simply marginalizes over all possible rollouts of states given the history to infer the RM state distribution, i.e. in finite-state POMDPs

$$P(u_t | h_t ) = \sum_{s_{1:t} \in S^t}  P(u_t | s_{1:t}) P(s_{1:t} | h_t)$$


Here, $P(u_t | s_{1:t})$ is deterministic — it is the RM state given the sequence of states (under the true labelling function), while $P(s_{1:t} | h_t)$ depends on the POMDP transition function and observation probabilities. As you can imagine, exact computation of this belief is typically infeasible and we must instead resort to approximate inference of the RM state.

If we restrict ourselves to fully observable environments, then indeed the ground-truth RM state is deterministic given the history. In this case, the optimal belief deterministically predicts the ground-truth RM state $u_t$ as you said.

### Re: sM3w Response to abstraction model problem or method

> in section 6, the three methods are directly compared, although they belongs to different problems

Yes, in comparing Naive, IBU, and TDM, we are considering three Noisy RM Environments where (only) the abstraction models differ. This is the disadvantage of including $\mathcal{M}$ as part of the problem setting, but per our original response, it is also important to frame the agent’s uncertainty over the vocabulary as part of the problem. [2] and [3] ensure us that this comparison is still meaningful — the space of possible behaviours and the objective remain the same in all three cases.

> does the Memory-only method uses the feature from the abstraction model?

Memory-only does not observe outputs from the abstraction model since it represents solving the task end to end without knowledge of the RM or propositions (per Theorem 4.1). We’ve run a baseline on MiniGrid that’s more along the lines of what you’re suggesting: Recurrent PPO that also observes (noisily) predicted propositions. On Traffic Light, it makes no improvement over “Memory only”. On Kitchen, it marginally outperforms Naive but is worse than TDM. This agrees with our claims that under noisy abstraction models, Naive and IBU can be detrimental, but TDM consistently performs well.   

> what conclusion do we want to draw from these comparison? The authors listed 3 questions in line 239, but I don't see any of these being addressed through the experiments.

We conclude the following regarding the three experimental questions:
- Naive and IBU are sometimes effective for RL. TDM reliably outperforms Recurrent PPO (Fig 3), demonstrating the importance of leveraging RM structure.
- Naive and IBU can be brittle when abstraction models are noisy due to partial observability, limited training data, or generalization error. This can lead to unintended or unsafe outcomes when training with RL.
- TDM models the RM state belief more accurately than Naive, IBU (Fig 4) when abstraction models are trained from equivalent data (per our original rebuttal).

These are referenced in our results but we can state them more directly. 

> Also, it would be better to mention some real-world cases when different forms abstraction exists.

Our experiments show that a dataset of trajectories labelled with propositional values can be used to train abstraction models for TDM, Naive, and IBU, with TDM being the most effective.

In some cases, different modelling assumptions can also be used to obtain different abstraction models for the same domain. For a (non-real-world) example, in Gold Mining, Naive, IBU, and TDM all leverage the same belief about where gold can be found but make different assumptions to predict an RM state belief (Sections 5.1-5.3).
Thanks for following up with further questions.  We appreciate the considerable effort this takes and we are committed to resolving your outstanding issues to ensure the paper is clear. 

We elected to address your two official comments in one (split) response. 

We preface our answers to your questions with four critical points that, based on your questions, we conjecture may assist in resolving your questions. 

[1] **The abstraction model does not affect what optimal behaviour is.** This is a consequence of [2] and [3] below. However, it can impact the difficulty of *identifying* and *learning* the optimal behaviour. 

[2] **The abstraction model $\mathcal{M}$ does not affect the set of behaviours the agent can perform.** Recall that we are interested in policies of the form $\pi(a_t | h_t, z_{1:t})$ (line 104), where $z_i = \mathcal{M}(h_i)$ and $h_t$ is the history of observations and actions up to time $t$. This is actually no more expressive than policies of the form $\pi(a_t | h_t)$ (i.e. Recurrent PPO) since $z_{1:t}$ is a deterministic function of $h_t$. Thus, the set of behaviours under consideration in our problem setting is precisely the set of history-based policies (i.e. policies $\pi : H \to \Delta A$), and is independent of $\mathcal{M}$. 

[3] **The objective (the expected discounted return) is independent of $\mathcal{M}$.** Recall that rewards are given by the RM $\mathcal{R}$ interpreted under the (hidden) labelling function $\mathcal{L}$. Thus, for any behaviour, we can determine its expected discounted return independent of $\mathcal{M}$.

[4] **For most problems, there exists no abstraction model that can recover the propositions or RM state with certainty.** This is because our framework allows the environment to be *partially observable*, with propositions and RM states depending on the (hidden) POMDP state. However, abstraction models are functions of the observable history $h_t$.

### Re: sM3w Optimality

> Imagine a environment of just one step. Either move left or move right. The agent does not know which one will give a reward of +1. The best it can do is random guess. Is random guess the optimal behavior?

Why does the agent not know the optimal action?

If it’s because the optimal action depends on the initial state (which is randomized), and the agent can’t distinguish the initial state given the initial observation, then yes, guessing is an optimal behaviour. There is no better policy given the observation history.

However, if in every episode the same action (say, “left”) is always better, and the agent does not initially know this (as is typical in RL), the optimal behaviour is to always go “left”. There exists a policy that does this and it maximizes expected return. 

> How could the choice of $\mathcal{M}$ not affecting optimal behavior? 

Please see [1,2,3]. To be clear, given any policy $\pi(a_t | h_t, z_{1:t})$ for an arbitrary abstraction model $\mathcal{M}$, there is a corresponding policy $\pi’(a_t | h_t)$ that encodes the same behaviour as $\pi$. Intuitively, this is because the abstraction model outputs $z_{1:t}$ are a function of $h_t$ and therefore the equivalent computation can be performed directly via the policy $\pi’$. This guarantees that the maximum expected discounted return is the same for any abstraction model $\mathcal{M}$, as stated in Theorem 4.2. What Theorem 4.2 does *not* state is how easy or hard it is to learn this optimal policy. 

Much of our analysis in these points is used to prove Theorems 4.1-4.3 in the paper, but we would be happy to make it more visible in the main paper if the reviewer thinks it would clarify the setting.

> an ideal $\mathcal{M}$ that deterministically predicts RM state u recovers the MDP

Generally, abstraction models are fundamentally unable to recover propositional values or RM states with certainty (per [4]). However, in the special case of a fully observable environment, we agree that such an abstraction model exists (Lemma A.2 in the Appendix).
Thank you for the additional clarifications and the thoughtful response to my concerns. I appreciate the detailed explanations regarding the potential "leakage" of ground-truth information and the role of abstraction models in your experiments.

I also commend your efforts to incorporate further discussion on foundational models, including the additional experiments with vision-language models. It's clear that you’ve put significant thought into expanding the practical relevance of your work, which is commendable.

Given the thoughtful revisions and effective responses to key concerns, the paper's quality has been notably improved. Theoretical solidity, added clarity, and broader contextualization have strengthened the work.

I have therefore upgraded my rating from "Weak Accept" to "Accept."
I am still confused by the optimal behavior. Imagine a environment of just one step. Either move left or move right. The agent does not know which one will give a reward of +1. The best it can do is random guess. Is random guess the optimal behavior? 

I also couldn't understand Theorem 4.2. How could the choice of $\mathcal{M}$ not affecting optimal behavior? An arbitrarily bad \mathcal{M} provides zero information, while an ideal $\mathcal{M}$ that deterministically predicts RM state u recovers the MDP.

In terms of optimal belief, line 160 is just a notation. I still don't understand what make a distribution $P(u_t \mid h_t)$ optimal? Or are you saying an optimal belief state is the distribution that deterministically predict the ground truth RM state $u$?
Thanks for the clarification. As the author pointed out, the abstraction model belongs to the problem rather than the method. So Section 5 is about three methods proposed for three different problems settings, but in many discussion, the authors seem to be drawing comparison between them. Also, in section 6, the three methods are directly compared, although they belongs to different problems. Also, does the Memory-only method uses the feature from the abstraction model? If it do not assume access to RM structure, like RM state space, it should at least directly takes abstraction model output as input to draw fair comparison. 

Also, what conclusion do we want to draw from these comparison? The authors listed 3 questions in line 239, but I don't see any of these being addressed through the experiments.

I really think this paper could benefit from a clearer statement of the problem, and rephrase its discussion and analysis.

Also, it would be better to mention some real-world cases when different forms abstraction exists.