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
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.
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.
Figure 4. Overview of the Prob-IRM algorithm that interleaves RM learning and exploitation from noisy traces. At each timestep, the agent takes action at and observes the next state st+1 and termination information τt+1 . The agent computes the noisy label Lt+1 from the transition ⟨st,at,st+1⟩ . The noisy label and current RM are used to determine the RM state belief u~t+1 ( Section 5.1 ) and RM reward δ~t+1r ( Section 5.2 ). The episode trace λ~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.
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.
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.
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.
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.
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.
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.
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.
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.
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
∗
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.
Figure 17. Prob-IRM learning curves for different values of the cross-entropy threshold β . 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.
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.
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 ( wto=0.25 ) and without ( wto=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.
Figure 21. Simplified OfficeWorld task (Visit A or B ) demonstrating cyclic relearning. The perfect RM accepts both propositions, but Prob-IRM alternates between RM1 (accepts only A ) and RM2 (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 ex1
Penalty of ex2
Number of traces generating ex1
Number of traces generating ex2
Additional traces needed to trigger relearning
1
RM1
11×10=10
—
1
0
1
2
RM2
31×10≈3
32×10≈7
1
2
2
3
RM1
53×10=6
52×10=4
3
2
2
4
RM2
73×10≈4
74×10≈6
3
4
2
5
RM1
95×10≈6
94×10≈4
5
4
2
6
RM2
125×10≈4
127×10≈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 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 )
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.
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
Reward Machines (RMs) are an established mechanism in Reinforcement Learning (RL) to represent and learn sparse, temporally extended tasks with non-Markovian rewards. RMs rely on high-level information in the form of labels that are emitted by the environment alongside the observation. However, this concept requires manual user input for each environment and task. The user has to create a suitable labeling function that computes the labels. These limitations lead to poor applicability in widely adopted RL frameworks. We propose Symbolic Reward Machines (SRMs) together with the learning algorithms QSRM and LSRM to overcome the limitations of RMs. SRMs consume only the standard output of the environment and process the observation directly through guards that are represented by symbolic formulas. In our evaluation, our SRM methods outperform the baseline RL approaches and generate the same results as the existing RM methods. At the same time, our methods adhere to the widely used environment definition and provide interpretable representations of the task to the user.
Thomas Krug, Daniel Neider
TU Dortmund University · Research Center Trustworthy Data Science and Security
Reward machines (RMs) have been proposed as a reward formulation in reinforcement learning (RL) to capture non-Markovian tasks where credit assignment depends on history. By representing reward functions as automata, RMs expose the task's temporal structure and allow such rewards to be handled within a Markovian framework. However, they assume a labelling function, a proposition-grounding oracle for observations, which must be manually engineered for each environment, limiting their wider applicability. In this work, we address this limitation by proposing RM-VLM, a novel approach in which a large language model (LLM) generates an RM from a natural-language task description, and a vision-language model (VLM) acts as the labelling function, grounding the RM's propositions over image-based observations during RM-guided policy learning. A VLM-based value function estimator is used to assess the agent's progress towards each RM transition and derive a dense reward signal. We evaluate RM-VLM on three domains covering non-Markovian grid-world navigation, robotic manipulation, and 3D object collection. Our experimental results show that RM-VLM consistently achieves higher task success rates than existing VLM-based reward methods across all tested domains.