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.
Paper
Similar papers
Peer review
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.
Strengths
I do not have any major complaints with this paper. It is well-motivated, well-reasoned, and well-communicated. I particularly appreciate the inclusion of a concrete running example as a way to elucidate the theoretical points made. The empirical experiments are also very thorough, consisting of multiple runs, multiple baselines, and a wide variety of environments.
Weaknesses
If there is a quibble to be made, it is that the paper could benefit from slightly more analysis on the differences between environments. It’s notable that the TDM approach is only one that approximates oracle performance across all 4 environments, but in some environments it is one of many that do so. Is this because those environments are generally less challenging or does some other explanation present itself? I’m slightly surprised that the baselines seem competitive in the color matching environment, in particular, since it is the only non-tabular environment. If the authors have any insight on this issue, it could be nice to include it.
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?
Rating
8
Confidence
4
Soundness
4
Presentation
4
Contribution
3
Limitations
I feel that the authors have adequately addressed the limitations and potential impact of their work.
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.
Strengths
The paper introduces a novel way of handling noisy and uncertain environments by modeling them as POMDPs. This perspective is particularly effective in real-world applications where the accurate reward and stationary environment are not always possible. The automatic design of reward machines is a valuable tool in reinforcement learning, especially in contexts where defining reward functions manually is difficult, such as with LLMs.
Weaknesses
Do the author assume the form of the abstraction model (e.g., classifier or regression model) is known, which might limit its applicability in more complex or less understood environments. In Golden Mining, the modeling of belief as binary might require domain-specific knowledge, which could be a limitation. This simplification might not be suitable for all environments, particularly those requiring more nuanced belief representations. How about the design of the abstraction model in other environments? 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
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.
Rating
5
Confidence
2
Soundness
2
Presentation
2
Contribution
3
Limitations
See weakness
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.
Strengths
Originality: - The combination of RMs with deep RL algorithms to handle noisy and uncertain environments is innovative. - The paper provides rigorous mathematical definitions and theoretical insights into the limitations of naive approaches and Independent Belief Updates (IBU). Quality: - The submission is technically sound with well-supported claims through both theoretical analysis and experimental results. - The experiments are comprehensive, spanning toy environments to more realistic tasks, showing the scalability and applicability of the methods. Clarity: - The paper is generally well-written and organized. - The explanation of theoretical concepts using the Gold Mining Problem is clear and effective. Significance: - The results demonstrate significant improvements in RL performance and sample efficiency in noisy environments. - The experimental evaluation shows the potential for real-world applications.
Weaknesses
- It is unclear how well the methods perform without ground-truth RMs, raising questions about additional effort required for new environments. - 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
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)?
Rating
7
Confidence
3
Soundness
2
Presentation
4
Contribution
3
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.
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.
Strengths
1. The discussion of reward machine under uncertain interpretation of the domain-specific vocabulary is somewhat novel. 2. The paper discusses three possible abstraction models that predicts deterministic proposition, stochastic proposition, and stochastic RM state respectively. 3. The paper provides theoretical analysis on the consistency of these three different abstraction models.
Weaknesses
1. I think this paper could be improved by clearer presentation. The formulation of Noisy Reward Machine Environment is confusing. Especially, the abstraction model is included as part of the environment or part of the problem setting, however, the proposed methods considers different types of abstraction models. Should the abstraction model be the method or the problem? 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
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?
Rating
5
Confidence
3
Soundness
2
Presentation
2
Contribution
2
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.
Response to abstraction model problem or method
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.
Optimality
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$?
Re: sM3w Optimality & Response to abstraction model problem or method (Part 1)
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).
Re: sM3w Optimality & Response to abstraction model problem or method (Part 2)
> 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 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.
Response
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.
Thanks
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.
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."
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.
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.
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.
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.
Decision
Accept (poster)