Robust Reward Machine Learning and Execution in Noisy Environments

AI summary

Overview

Research area: Reinforcement learning (RL), specifically reward machines (RMs), neuro-symbolic AI, and inductive logic programming (ILP) applied to learning under noisy observations.

Technical level: Advanced. The paper assumes familiarity with Markov decision processes, non-Markovian reward formalisms, finite-state machines, Bayesian belief updating, and answer-set/ILP learning (ILASP), plus deep RL with PPO.

Scope: The paper introduces Prob-IRM, a method that learns reward machines from noisy proposition traces with inductive logic programming and interleaves that learning with neural policy optimisation in both discrete and continuous environments.

What This Paper Is About

Reward machines express non-Markovian reward functions as small finite-state machines over high-level propositional events, but existing methods for learning them assume a perfect "labelling function" that detects those events flawlessly. In real deployments, event detection comes from sensors or AI models and is frequently wrong, and a single misdetected event can cause an incorrect reward machine to be learned. The paper's goal is a method that both learns and exploits reward machines when the labelling function is noisy, without falling back on hand-engineered machines.

Key Contributions

1. Prob-IRM, a method for learning and exploiting RMs under noisy labelling. The paper presents what it describes as the first method that directly learns and exploits reward machines when the labelling function is noisy. The agent's belief about event occurrences is modelled as a Bayesian posterior conditioned on sensor outputs, and noisy proposition histories become training examples for ILASP, which learns an RM that maximises coverage of low-uncertainty histories.

2. A complete ILASP encoding for learning RMs from noisy traces. The paper gives the full encoding for the noisy RM-learning task and identifies explicitly which parts change relative to learning from noise-free traces in the earlier work of Furelos-Blanco et al. (2021).

3. Enhanced generality and scalability over the authors' prior work (Parac et al., 2024). The earlier version used tabular action-value functions, which required discretising beliefs over RM states and restricted the method to discrete state spaces. Prob-IRM instead approximates policies with neural networks trained using Proximal Policy Optimisation (PPO), enabling continuous domains and improved robustness. The architecture was also modified to allow parallel trace collection, which the authors report significantly improves scalability.

4. Extensive evaluation and ablation study. Prob-IRM is evaluated on tasks with discrete and continuous state spaces and sparse non-Markovian rewards, with an in-depth ablation of design choices, against baselines using handcrafted RMs and a fully neural Recurrent PPO baseline.

The paper also contributes a formalisation of the noisy event-detection setting and a discussion of RM exploitation, including a probabilistic reward-shaping formulation derived from posterior beliefs over traces.

Main Findings

• Comparable to oracle-style baselines: Across diverse noise configurations, Prob-IRM performs comparably to baselines that are given handcrafted reward machines, despite operating only with noisy labels. The specific performance figures, noise levels and confidence intervals are not reported in the excerpt of the paper available here.
• Outperforms the neural history-encoding baseline: Prob-IRM outperforms Recurrent PPO, the fully neural baseline that encodes history with a recurrent network rather than an explicit machine.
• Works beyond discrete state spaces: Unlike the prior tabular version of the method, Prob-IRM operates in continuous state spaces as well as discrete ones, as a result of the switch to PPO-trained neural policies.
• Relearning is triggered by belief, not by fixed schedules: A new RM is learned whenever the RL agent produces a trace that is not believed to be accepted by the current RM, so RM learning and policy optimisation are interleaved rather than staged.
• Beliefs serve two purposes: The belief over RM states is used both to decide when to relearn the RM and to supply additional guiding rewards through probabilistic reward shaping, which the paper presents as a way to accelerate policy learning.
• Task and domain scale used for illustration: The worked example is the OfficeWorld domain, a 12 × 9 grid with state space {0,…,11} × {0,…,8} and four actions (up, down, left, right). The Coffee task requires visiting the coffee machine and then the office, with a reward of 1 for completing the task and 0 otherwise.
• Not reported in the provided content: benchmark dataset sizes, exact labelling-noise rates tested, wall-clock or sample-complexity numbers, and the quantitative ablation results.

Methodology in Plain English

The setting is a labelled Markov decision process in which the agent must solve a task whose reward depends on the whole history, not just the current state. A reward machine compresses that history into a small set of machine states, so standard RL can be applied to the augmented state. The twist is that the propositions feeding the machine are observed through an imperfect detector.

Prob-IRM handles this in three interlocking pieces. First, instead of treating a detected event as fact, the agent maintains a Bayesian belief about which events actually occurred, conditioned on what the sensors reported. Second, those beliefs are turned into training examples for ILASP, an inductive logic programming system that can learn from noisy examples. The learning objective prefers reward machines that explain the histories the agent is most confident about, so uncertain traces do not corrupt the learned machine; this is the "maximises coverage of low-uncertainty histories" idea. Third, the learned machine is not used blindly. The agent tracks a belief distribution over which machine state it is in, and this distribution does two jobs: it signals when the current machine no longer explains the agent's behaviour, prompting a relearn, and it produces an extra shaping reward that guides exploration.

Policy learning uses neural networks trained with PPO rather than a tabular action-value table, which is what makes continuous environments feasible and what allows traces to be collected in parallel. The whole loop alternates between improving the policy under the current machine and learning a new machine when the evidence demands it. Baselines are handcrafted reward machines (representing the ideal case) and Recurrent PPO (representing a purely neural approach with no symbolic structure).

Why This Matters

The paper attacks an assumption that quietly underpins most reward-machine work: that high-level events can be detected perfectly. In any deployment where propositions come from sensors, classifiers, or language models, that assumption fails, and errors propagate into a wrong reward machine and therefore a wrong policy. Prob-IRM shows that symbolic task structure can still be recovered and exploited when the perception layer is unreliable, which is a step toward deploying interpretable, structured RL outside simulation.

Real-world applications:

• Robotics with imperfect perception: household or warehouse robots whose object detectors occasionally miss or hallucinate objects, where the task specification is a sequence of high-level events.
• Agents that rely on learned event detectors or language models: settings where task-relevant events are inferred from noisy model outputs rather than read directly from the environment state.
• Process and workflow monitoring: business or industrial processes where the "events" are logged by sensors and logs and the reward depends on the order in which they occur.
• Assistive and instruction-following agents: agents that must satisfy ordered instructions while their understanding of which instruction step has been completed is itself uncertain.

Industry relevance: the method keeps the task specification in an interpretable, inspectable form (a finite-state machine) while tolerating an unreliable perception stack, which matters for safety review and debugging in industrial RL. The move from tabular to PPO-based policies and the parallel trace collection also make the approach compatible with standard deep RL infrastructure.

Future Directions

• Scaling the symbolic learning step: ILASP-based learning from noisy traces is the computational bottleneck; extending the encoding and the example-selection strategy to larger proposition sets and longer horizons is a natural next step.
• Learning the noise model instead of assuming it: the method conditions on sensor outputs through a belief model; how that noise model is obtained and how sensitive the approach is to its misspecification remains an open question.
• Guarantees under noise: the paper frames its results empirically; formal characterisations of when the learned machine is correct, or how error scales with noise level, are not established.
• Broader evaluation against real perception noise: the reported evaluation uses injected labelling noise across discrete and continuous environments; testing on physical sensor streams or learned event detectors would strengthen the case for real-world deployment.

Target Audience

Researchers and graduate students in reinforcement learning and neuro-symbolic AI who work on reward machines, temporal-logic or automata-based task specification, and learning from noisy or uncertain examples. It is also relevant to practitioners in robotics and industrial RL who have a structured task specification but an unreliable perception layer, and to ILP researchers interested in learning finite-state structures from uncertain data. Readers without background in reward machines, Markov decision processes and inductive logic programming will find the formalism demanding.

Authors’ abstract

Background: Reward machines (RMs) represent non-Markovian reward functions as finite-state machines over high-level propositional events. Traditionally, these events are generated by a deterministic labelling function that maps environment states to proposition sets. However, real-world labelling functions are inherently noisy. Objectives: Design and implement a method that learns RMs in the presence of noisy labelling functions and exploits them for policy learning in both discrete and continuous environments. Methods: We propose Prob-IRM, a method that learns RMs from noisy proposition histories using inductive logic programming (ILP) and exploits them for policy learning. Noisy proposition histories are represented as training examples for ILP, which learns an RM that maximises coverage of low-uncertainty histories. RM learning is interleaved with policy optimisation. Prob-IRM uses a belief over RM states to determine when to relearn the RM and to provide additional guiding rewards. Results: Prob-IRM is evaluated on environments with discrete and continuous state spaces under varying levels of labelling noise. Prob-IRM performs comparably to baselines using handcrafted RMs and outperforms approaches that use recurrent neural networks to encode history, despite operating with noisy labels. Conclusions: Prob-IRM represents a step towards deploying reward machines in noisy, real-world environments.