Robust Reward Machine Learning and Execution in Noisy Environments

Roko Parac; Lorenzo Nodari; Daniel Furelos-Blanco; Leo Ardon; Federico Cerutti; Alessandra Russo

cs.AIOct 31, 2026

Robust Reward Machine Learning and Execution in Noisy Environments

Authors: Roko Parac, Lorenzo Nodari, Daniel Furelos-Blanco, Leo Ardon, Federico Cerutti, Alessandra Russo

Organizations: Imperial College London, United Kingdom · University of Brescia, Italy

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.

Figures & tables

Panel of Figure 2 — Figure 2. Overview of the RM learning pipeline. Traces are sampled from noisy traces and from an existing RM, converted into ILASP examples, and used together with background knowledge and a hypothesis space to learn a new RM. Flow diagram of the RM learning pipeline. A dashed box labelled Given contains a stack of noisy traces and an existing RM. An arrow labelled sample leads from the noisy traces to a stack of grounded traces, and another arrow labelled sample leads from the existing RM to RM traces. Grounded traces and RM traces both feed a stack of examples. The examples, a background box and a hypothesis space box all feed into ILASP, which outputs an RM.

Panel of Figure 3 — Figure 3. Reward machine for the VisitABCD task used in Example 4.2 . The agent must go to locations $A$ , $B$ , $C$ and $D$ in order. This RM accounts for co-location: $A$ may appear with $B$ , and $C$ may appear with $D$ . A reward machine drawn as a left-to-right chain of five states u0, u1, u2, u3 and the accepting state uA. The edges along the chain are labelled A and not B with reward 0, B with reward 0, C and not D with reward 0, and D with reward 1. Two curved shortcut edges skip a state: from u0 to u2 labelled A and B with reward 0, and from u2 to uA labelled C and D with reward 1.

Panel of Figure 4 — Figure 4. Overview of the Prob-IRM algorithm that interleaves RM learning and exploitation from noisy traces. At each timestep, the agent takes action $a_{t}$ and observes the next state $s_{t+1}$ and termination information $\tau_{t+1}$ . The agent computes the noisy label $\widetilde{\mathcal{L}}_{t+1}$ from the transition $\langle s_{t},a_{t},s_{t+1}\rangle$ . The noisy label and current RM are used to determine the RM state belief $\tilde{u}_{t+1}$ ( Section 5.1 ) and RM reward $\tilde{\delta}^{r}_{t+1}$ ( Section 5.2 ). The episode trace $\tilde{\lambda}_{t+1}$ is updated with the noisy label. At episode termination, the trace is stored and we determine whether to relearn the RM using the final RM state belief ( Section 6.1 ). If relearning is triggered, grounded traces are sampled from the noisy traces ( Section 4.1.1 ) and from the current RM ( Section 4.1.2 ). These traces are provided to ILASP to learn a new RM. Flow diagram of the Prob-IRM loop. The environment sends the next state and termination information to the agent, and the agent sends an action back. The agent exchanges the noisy label with the RM and receives the RM state belief and RM reward. The noisy label, termination information and belief are appended to the noisy trace of the episode. A decision node asks whether the episode terminated; if yes, the trace is added to a stack of noisy traces and a second decision node asks whether the RM should be relearned, based on the RM state belief. If yes, ILASP is called with traces sampled from the noisy traces and from the current RM, and the updated RM replaces the current one.

Panel of Figure 5 — Figure 5. Visualisation of the WaterWorld domain Toro Icarte et al., 2018 . The agent is depicted by the white ball. A square arena containing twelve coloured balls (two each of red, green, blue, magenta, cyan and yellow), each with an arrow indicating its direction of motion, and one white ball representing the agent.

Hyperparameter	Value	Search Range
Environment
Max. episode length
OfficeWorld ( Coffee , CoffeeMail )	500	N/A
OfficeWorld ( VisitABCD )	1,000	N/A
WaterWorld (all)	150	N/A
PPO

Table 1. Hyperparameter values. Search ranges show values tested during random search; N/A indicates fixed values.

Panel of Figure 6 — Figure 6. Learning curves for Coffee across different sensor confidence levels. Four panels of learning curves for the Coffee task, one per method: Perfect RM, Prob-IRM, ISA and Recurrent PPO. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. Prob-IRM reaches returns close to the Perfect RM baseline at all three confidence levels, ISA performs well only without noise, and Recurrent PPO does not solve the task consistently.

Panel of Figure 7 — Figure 7. Learning curves for CoffeeMail across different sensor confidence levels. Four panels of learning curves for the CoffeeMail task, one per method: Perfect RM, Prob-IRM, ISA and Recurrent PPO. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. Prob-IRM is comparable to the Perfect RM baseline across noise levels, ISA performs well only without noise, and Recurrent PPO does not solve the task.

Panel of Figure 8 — Figure 8. Learning curves for VisitABCD across different sensor confidence levels. Four panels of learning curves for the VisitABCD task, one per method: Perfect RM, Prob-IRM, ISA and Recurrent PPO. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. Prob-IRM solves the task at confidence 1.0 and 0.9 and degrades at 0.8, ISA fails to converge under noise, and Recurrent PPO does not solve the task.

Panel of Figure 9 — Figure 9. Learning curves for RGB across different sensor confidence levels. Four panels of learning curves for the RGB task, one per method: Perfect RM, Prob-IRM, ISA and Recurrent PPO. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. Prob-IRM converges close to the Perfect RM baseline at all noise levels, Recurrent PPO converges more slowly, and ISA degrades under noise.

Panel of Figure 10 — Figure 10. Learning curves for RG-B across different sensor confidence levels. Four panels of learning curves for the RG-B task, one per method: Perfect RM, Prob-IRM, ISA and Recurrent PPO. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. Prob-IRM matches the Perfect RM baseline, Recurrent PPO converges more slowly, and ISA degrades under noise.

Panel of Figure 11 — Figure 11. Learning curves for RGBC across different sensor confidence levels. Four panels of learning curves for the RGBC task, one per method: Perfect RM, Prob-IRM, ISA and Recurrent PPO. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. Prob-IRM solves the task at all noise levels, while ISA and Recurrent PPO fail to make progress.

Panel of Figure 12 — Figure 12. Prob-IRM learning curves for Coffee with and without probabilistic reward shaping. Two panels of Prob-IRM learning curves for the Coffee task, without and with probabilistic reward shaping. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. Both variants reach similar final returns; with reward shaping the curves rise faster.

Panel of Figure 13 — Figure 13. Learning curves and exploited RMs for Coffee in the noise-all setting. Two rows, each pairing a learning-curve plot with the reward machine that was exploited, for the Coffee task with all sensors noisy. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. The top row shows the Perfect RM baseline with the handcrafted four-state reward machine for the Coffee task, where returns decrease as sensor confidence decreases. The bottom row shows Prob-IRM with its learned reward machine, which has the same four states but a simpler edge from u0 to u1 labelled coffee and not decoration and no direct edge from u0 to the accepting state; its returns are close to 1 at all confidence levels.

Sensor		$A$	$B$	$C$	$D$	☕	🖂	$o$	$\ast$
F1 Score	Min.	0.60	0.70	0.80	0.70	0.87	0.80	0.60	0.40
	Max.	1.00	1.00	1.00	1.00	1.00	1.00	0.90	0.80
	Avg.	0.84	0.90	0.89	0.92	0.94	0.95	0.72	0.59
	Std. Dev.	0.14	0.10	0.07	0.10	0.05	0.07	0.10	0.14

Table 2. F1 scores for each sensor in the pre-trained sensor model ablation (10 runs).

Figure 14. Learning curves for Coffee with a pre-trained noise model. One plot of average return (0 to 1) against training iterations for the Coffee task with pre-trained classifiers as sensors, with one curve for the Perfect RM baseline and one for Prob-IRM; lines show the mean and shaded bands the standard deviation. Both curves level off between 0.8 and 0.9, with Prob-IRM slightly below the Perfect RM baseline.

Figure 15. Learning curves for VisitABCD tasks with varying sequence lengths (80% sensor confidence). One plot of average return (0 to 1) against training iterations for Prob-IRM on visitation tasks of increasing length, with one curve per task (one to five locations); lines show the mean and shaded bands the standard deviation. Tasks with up to three locations converge to returns near 1, the four-location task converges lower with high variance, and the five-location task stays far below the others.

Figure 16. Learning curves for Coffee ( noise-all , 80% confidence) comparing thresholding at 0.7 and 0.9 with belief updating (dashed line). One plot of average return (0 to 1) against training iterations for the Coffee task, with a curve for a threshold of 0.7, a curve for a threshold of 0.9 and a dashed curve for belief updating without a threshold; lines show the mean and shaded bands the standard deviation. Belief updating and the 0.7 threshold reach returns above 0.9, while the 0.9 threshold remains substantially lower and unstable.

Panel of Figure 17 — Figure 17. Prob-IRM learning curves for different values of the cross-entropy threshold $\beta$ . Five panels of Prob-IRM learning curves, one per value of the cross-entropy threshold (0, 0.5, 1, 1.5 and 2). Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. The curves are similar across threshold values.

Panel of Figure 18 — Figure 18. Prob-IRM learning curves for different example penalty budgets in CoffeeMail . Five panels of Prob-IRM learning curves, one per example penalty budget (100, 200, 500, 1,000 and 10,000). Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. The lowest budgets give lower and noisier returns than the higher budgets.

Panel of Figure 19 — Figure 19. Prob-IRM learning curves for Coffee when class-based weight rebalancing is enabled and disabled. Two panels of Prob-IRM learning curves for the Coffee task, with and without class-based weight rebalancing. Each panel plots average return (vertical axis, 0 to 1) against training iterations (horizontal axis), with one curve per sensor confidence level (1.0, 0.9 and 0.8); lines show the mean and shaded bands the standard deviation over runs. With rebalancing the curves converge faster and more stably.

Figure 20. Prob-IRM learning curves for RGBC under 80% sensor confidence with ( $w_{t_{o}}=0.25$ ) and without ( $w_{t_{o}}=0$ ) example generation from previous RMs. One plot of average return (0 to 1) against training iterations for the RGBC task at 80 percent sensor confidence, with one curve for a trace origin multiplier of 0.25 and one for a multiplier of 0; lines show the mean and shaded bands the standard deviation. The curve with multiplier 0.25 rises markedly faster; both approach returns near 1 by the end of training.

Domain	Noise	Min.	Median	Max.	Average	Std. Dev.
Coffee	80%	<0.01%	<0.01%	<0.01%	<0.01%	<0.01%
[0.5pt/5pt]	90%	<0.01%	<0.01%	<0.01%	<0.01%	<0.01%
[0.5pt/5pt]	100%	<0.01%	<0.01%	<0.01%	<0.01%	<0.01%
[0.5pt/5pt] CoffeeMail	80%	0.05%	0.10%	0.96%	0.31%	0.31%
[0.5pt/5pt]	90%	0.01%	0.05%	0.96%	0.21%	0.34%
[0.5pt/5pt]	100%	<0.01%	0.01%	0.05%	0.02%	0.01%

Table 3. ILASP runtime as a percentage of total training time across tasks and sensor confidence levels.

Panel of Figure 21 — Figure 21. Simplified OfficeWorld task (Visit $A$ or $B$ ) demonstrating cyclic relearning. The perfect RM accepts both propositions, but Prob-IRM alternates between $\mathcal{RM}_{1}$ (accepts only $A$ ) and $\mathcal{RM}_{2}$ (accepts only $B$ ) when the edge cost exceeds the example penalty. Four panels. (a) A one-row grid of three cells: A on the left, the agent in the middle and B on the right. (b) The perfect reward machine, with two edges from the initial state u0 to the accepting state uA, labelled A with reward 1 and B with reward 1. (c) The learned reward machine RM1, with a single edge from u0 to uA labelled A with reward 1. (d) The learned reward machine RM2, with a single edge from u0 to uA labelled B with reward 1.

#	RM learned	Penalty of $\mathtt{ex1}$	Penalty of $\mathtt{ex2}$	Number of traces generating $\mathtt{ex1}$	Number of traces generating $\mathtt{ex2}$	Additional traces needed to trigger relearning
1	$\mathcal{RM}_{1}$	$\frac{1}{1}\times 10=10$	—	1	0	1
2	$\mathcal{RM}_{2}$	$\frac{1}{3}\times 10\approx 3$	$\frac{2}{3}\times 10\approx 7$	1	2	2
3	$\mathcal{RM}_{1}$	$\frac{3}{5}\times 10=6$	$\frac{2}{5}\times 10=4$	3	2	2
4	$\mathcal{RM}_{2}$	$\frac{3}{7}\times 10\approx 4$	$\frac{4}{7}\times 10\approx 6$	3	4	2
5	$\mathcal{RM}_{1}$	$\frac{5}{9}\times 10\approx 6$	$\frac{4}{9}\times 10\approx 4$	5	4	2
6	$\mathcal{RM}_{2}$	$\frac{5}{12}\times 10\approx 4$	$\frac{7}{12}\times 10\approx 6$	5	7	3

Table 4. Example penalties and examples required for RM learning iterations in the cycling scenario. Column “Additional traces needed to trigger relearning” captures the number of new traces collected between iterations

i-1

and

i

;

Y

is a variable representing the number of

\mathtt{ex2}

-generating traces at iteration

2n-1

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description
Reinforcement Learning and (Noisy) Labelled MDPs ( Sections 2.1 and 3 )
$\mathcal{S}$	Set of MDP states
$s_{0}$	Initial MDP state
$\mathcal{A}$	Set of actions
$h$	State-action history
$p$	Probability transition function

Appendix

Table 5. Summary of mathematical notation.

Non-Markovian RL

See all 15 papers

Active Reward Machine Inference From Raw State Trajectories
Apr 8, 2026Mohamad Louai Shehab, Antoine Aspeel, Necmiye OzayAutomata Learning
Robotics Department, University of Michigan, Ann Arbor, MI · Independent Researcher · Electrical Engineering and Computer Science Department, University of Michigan, Ann Arbor, MI
Reinforcement Learning with Symbolic Reward Machines
Mar 3, 2026Thomas Krug, Daniel NeiderReward Machines Non-Markovian RL
TU Dortmund University · Research Center Trustworthy Data Science and Security
RM-VLM: From Natural-Language Task Descriptions to Vision-Grounded Reward Machines
Nov 5, 2026Roko Parac, Christos Ziakas, Leo Ardon +1Reward Machines Reinforcement Learning
Imperial College London, London, United Kingdom

Apr 8, 2026J/K move · Enter open · S save

Active Reward Machine Inference From Raw State Trajectories

Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

Robotics Department, University of Michigan, Ann Arbor, MI · Independent Researcher · Electrical Engineering and Computer Science Department, University of Michigan, Ann Arbor, MI

Automata Learning

Open paper AskPDF arXiv

Reward machines are automaton-like structures that capture the memory required to accomplish a multi-stage task. When combined with reinforcement learning or optimal control methods, they can be used to synthesize robot policies to achieve such tasks. However, specifying a reward machine by hand, including a labeling function capturing high-level features that the decisions are based on, can be a daunting task. This paper deals with the problem of learning reward machines directly from raw state and policy information. As opposed to existing works, we assume no access to observations of rewards, labels, or machine nodes, and show what trajectory data is sufficient for learning the reward machine in this information-scarce regime. We then extend the result to an active learning setting where we incrementally query trajectory extensions to improve data (and indirectly computational) efficiency. Results are demonstrated with several grid world examples.

Abstract

Non-Markovian RL

Explore similar work

Active Reward Machine Inference From Raw State Trajectories

Reinforcement Learning with Symbolic Reward Machines

RM-VLM: From Natural-Language Task Descriptions to Vision-Grounded Reward Machines