Active Reward Machine Inference From Raw State Trajectories
Authors: Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay
Organizations: Robotics Department, University of Michigan, Ann Arbor, MI · Independent Researcher · Electrical Engineering and Computer Science Department, University of Michigan, Ann Arbor, MI
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.
Figures & tables
Figure 1: (a) The warehouse grid world. (b) The pick and drop reward machine. (c) Solution count at increasing depths. The shaded area represents ± one standard deviation. Negative region is cut-off.
Figure 2: (a) The room grid world. (b) The patrol reward machine. (c) The Tetris rooms grid world.
Figure 3: (a): Reduction in solution set size vs depth. (b): Growth of the number of trajectories vs depth.
Method
Depth ( l )
∣τ∣
∣El−∣
size (| τ |)
size ( ∣El−∣ )
Exhaustive
9
382K
414M
0.3Gb
24.76Gb
Active Extension
13
10.3K
0.292M
0.046Gb
0.147Gb
Table 1: Memory Requirements for exhaustive vs. active search. ∣τ∣ is the total number of trajectories. ∣El−∣ is the number of negative examples. size (| τ |) is the memory required to store the trajectories. size ( ∣El−∣ ) is the memory required to store the negative examples.
Method
Mean Discovery Time (s)
Mean SAT Time (s)
Total Time (s)
Max Depth
Sols
Active Extension
1127.64±186.11
2417.12±6.16
3544.76±188.71
13
36
Exhaustive
26.80
7158.73±1640.39
7185.53±1640.39
9
36
Table 2: Computation requirements for active extension vs. exhaustive Baseline. Mean Discovery Time (s) refers to the time spent finding the negative example set. Mean SAT Time (s) refers to the time spent solving a SAT problem instance. Results are over 10 separate trials. The mean SAT time for active extension includes 2350 s spent solving SAT with the depth- 6 policy.
We present Pareto Q-Learning with Reward Machines (PQLRM), a multi-objective reinforcement learning algorithm for tasks whose reward structure is specified by a set of reward machines (RMs). PQLRM combines Pareto Q-Learning (PQL), which maintains sets of vector-valued Q-estimates to approximate the Pareto front, with enhancements from Q-Learning with Reward Machines (QRM), which exploits the factored automaton structure of the reward signal. This yields a multi-policy algorithm that remains sample-efficient under non-Markovian, RM-encoded rewards. Experimental trials show that PQLRM converges faster than a naive PQL baseline applied to the cross-product MDP and can synthesize Pareto-optimal policies that QRM cannot.
Linköping University, Sweden · Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStal, F-59000 Lille, France · Univ. Toulouse, INRAE-MIAT, Toulouse, France
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
Does a reinforcement-learning agent that earns reward learn its task's hidden state? We study this question with hidden finite automata that the agent partially controls. Because each automaton is known, we can normalize reward by the best achievable return and probe the network for the true state at every step. Together the two measurements separate failures that reward alone conflates. An agent can encode too little of a state its network could hold, or encode the state and still control poorly. Weak on-policy RL matches random play while the state probe stays at chance. State learning depends on the optimizer, the training budget, and the task's structure. Permutation automata provide a warning before training: no input symbol maps two distinct states to the same successor. On a stratified held-out set, 86 of 103 permutation automata fail the state probe, and the classification is stable across probe read-outs and recovery thresholds. Most of these failures come with weak reward. High reward without the state occurs but is rare. Non-permutation automata can also fail. Oracle-normalized reward alone therefore does not establish that the task's state was learned.