Paper deep dive
Active Reward Machine Inference From Raw State Trajectories
Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 93%
Last extracted: 4/10/2026, 4:04:12 AM
Summary
The paper introduces a framework for learning reward machines (RMs) and labeling functions directly from raw state and policy trajectories, eliminating the need for predefined symbolic knowledge or reward observations. It formulates the inference as a SAT problem and provides theoretical bounds on the trajectory length required for successful learning, demonstrating the approach with grid world examples.
Entities (5)
Relation Signals (3)
SAT Problem → infers → Reward Machine
confidence 95% · We present in this section how to extend this framework... to learn a RM model
Labeling Function → maps → State
confidence 95% · a labeling function... associates an atomic proposition of a RM to each state of an MDP.
Reward Machine → captures → Task Memory
confidence 90% · Reward machines are automaton-like structures that capture the memory required to accomplish a multi-stage task.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2604.07480v1
- Canonical: https://arxiv.org/abs/2604.07480v1
Trouble viewing inline? Open PDF directly →
Full Text
56,944 characters extracted from source content.
Expand or collapse full text
11institutetext: Robotics Department, University of Michigan, Ann Arbor, MI 22institutetext: Independent Researcher 33institutetext: Electrical Engineering and Computer Science Department, University of Michigan, Ann Arbor, MI Active Reward Machine Inference From Raw State Trajectories Mohamad Louai Shehab Antoine Aspeel Necmiye Ozay Abstract 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. 1 Introduction Multi-stage tasks are ubiquitous in robotics applications, as real-world objectives are rarely achieved through a single atomic action but instead require the coordinated execution of sequential and interdependent subtasks [33, 8, 23]. These robots have to operate under temporally extended objectives in which task success depends on satisfying intermediate goals in a specific order, motivating the use of hierarchical and modular task representations [3]. Reward machines provide a principled and expressive formalism for representing such multi-stage task structure by encoding task progress as a finite-state automaton whose transitions are triggered by high-level events or propositions observed during execution [34, 35, 12, 16, 7]. While Reward Machines (RMs) offer a powerful framework for structured task execution, their utility is often bottlenecked by the requirement for human experts to manually specify the underlying automaton. In complex, real-world environments, defining the exact logical transitions and propositional triggers for a task is not only labor-intensive but also prone to specification errors that can lead to unintended robotic behaviors [2]. Consequently, there is a growing imperative to develop algorithms capable of learning RMs directly from experience [35, 38, 32]. This automated RM inference allows a robot to autonomously discover the latent logical structure of a task, identifying the “hidden” stages that define successful execution without explicit human oversight. Existing literature on learning reward machines generally falls into three categories: those assuming ground-truth labels for states or rewards to find consistent automata [5, 37, 22, 21, 1], those utilizing active learning or L∗L^* oracles to query membership and conjectures [4, 39, 25], and those combining automata synthesis with reinforcement learning in interactive environments [18, 19, 17]. While some approaches rely on observing demonstrations [12, 6], they are often restricted to single-stage tasks where the RM serves primarily for reward shaping rather than complex temporal logic. Other works learn reward machines for multi-staged tasks purely from demonstrations [32]. A critical bottleneck in these works is the reliance on a predefined labeling function that maps low-level states to high-level propositions. Recent efforts have begun addressing labeling function ambiguity by accounting for noise and uncertainty in label assignments [24, 27, 36]; however, they still assume the existence of a noisy labeling function. In contrast, our framework is the first to learn both the labeling function and the reward machine from scratch using only state-based traces, eliminating the need for any prior symbolic knowledge or predefined event detectors. Notation: For a finite set X, we denote by |X||X| its cardinality. The set of all probability distributions over X is denoted by Δ(X) (X). The set of all finite sequences with elements in X is denoted by X∗X^*. For two sets X and Y, their Cartesian product is X×YX× Y, and the Cartesian power of X of order n is denoted by XnX^n. The set of real numbers is denoted by ℝR. Logical conjunction and disjunction are denoted by ∧ and ∨ , respectively. The expectation operator is denoted by E. 2 Preliminaries 2.1 Markov decision processes and reward machines A Markov Decision Process (MDP) is a tuple ℳ=(,,,μ0,γ,r),M=(S,A,P, _0,γ,r), where S is the finite set of states, A is the finite set of actions, :×→Δ()P:S×A→ (S) is the Markovian transition kernel, μ0∈Δ() _0∈ (S) is the initial state distribution, γ∈[0,1)γ∈[0,1) is the discount factor, and r:×→ℝr:S×A×S is the reward function. We refer to a MDP without the reward r as an MDP model, and denote it by ℳ∖rM r. A Reward Machine (RM) is a tuple ℛ=(,uI,AP,δ,δ),R=(U,u_I,AP, _u, _r), where U is the finite set of nodes, uI∈u_I is the initial node, APAP is the set of atomic propositions (also called input alphabet), δ:×AP→ _u:U×AP is the (deterministic) transition function, and δ:×AP→ℝ _r:U×AP is the output function. A reward machine without its output function is named a reward machine model. We extend the definition of the transition function to define δ∗:×(AP)∗→ _u^*:U×(AP)^* as δ∗(u,l0,⋯,lk)=δ(⋯(δ(δ(u,l0),l1),⋯,lk) _u^*(u,l_0,·s,l_k)= _u(·s( _u( _u(u,l_0),l_1),·s,l_k). Finally, a labeling function (compatible with an MDP ℳM and a RM ℛR) is a function L:→APL:S which associates an atomic proposition of a RM to each state of an MDP. It is common to introduce the notion of labeled MDP as a pair formed by an MDP and a compatible labeling function. However, in the problem we are interested in, both the RM and the labeling function are unknown. Consequently, it will make our notation simpler to consider a labeled RM instead. Formally, a labeled RM refers to a pair composed by a reward machine and a (compatible) labeling function ℛL=(ℛ,,L)R_L=(R,S,L). A labeled RM model is a labeled RM without its output function δ _r and is denoted by G. In the next section, we show how a compatible labeling function allows to “connect” an MDP model with a RM. 2.2 Product MDP An MDP model ℳ∖rM r together with a reward machine ℛR and a compatible labeling function L allow to define a product MDP ℳProd=(′,′,′,μ0′,γ′,r′),M_Prod=(S ,A ,P , _0 ,γ ,r ), where ′=×S =S×U, ′=A =A, ′(s′,u′|s,u,a)=(s′|s,a)(u′=δu(u,L(s′)))P (s ,u |s,u,a)=P(s |s,a)1(u = _u(u,L(s ))), γ′=γ =γ, μ0′∈Δ(×) _0 ∈ (S×U) with μ0′(s,u)=μ0(s)(u=uI) _0 (s,u)= _0(s)1(u=u_I) and r′(s,u,a,s′,u′)=δ(u,L(s′))r (s,u,a,s ,u )= _r(u,L(s )), where (p)1(p) is one if p is true and zero otherwise. To make the notation compact, we denote the product state by s¯=(s,u) s=(s,u). A trajectory of the product MDP ℳProdM_Prod is a sequence (s¯∅,a∅,s¯0,a0,s¯1,a1,⋯)( s_ ,a_ , s_0,a_0, s_1,a_1,·s), where s¯∅=(∅,uI) s_ =( ,u_I) and a∅=∅a_ = . An initial state s0s_0 is sampled from μ0 _0. The introduction of s¯∅ s_ and a∅a_ at the start of the trajectory is to ensure that s0s_0 induces a transition in the reward machine. The reward machine thus transitions to u0=δu(uI,L(s0))u_0= _u(u_I,L(s_0)). The agent then takes action a0a_0 and transitions to s1s_1. Similarly, the reward machine transitions to u1=δu(u0,L(s1))u_1= _u(u_0,L(s_1)). The same procedure continues infinitely. We consider the product policy πProd:DomProd→Δ() _Prod:Dom_Prod→ (A) where DomProd⊆×Dom_Prod ×U is the set of accessible (s,u)(s,u) pairs in the product MDP. This policy is a function that describes an agent’s behavior by specifying an action distribution at each state. We consider the Maximum Entropy Reinforcement Learning (MaxEntRL) objective given by: JMaxEnt(π;r′)=μ0π[∑t=0∞γt(r′(s¯t,at,s¯t+1)+λℋ(π(.|s¯t)))],J_MaxEnt(π;r )=E^π_ _0[Σ _t=0^∞γ^t (r ( s_t,a_t, s_t+1)+ (π(.| s_t)) )], (1) where λ>0λ>0 is a regularization parameter, and ℋ(π(.|s¯))=−∑a∈π(a|s¯)log(π(a|s¯))H(π(.| s))=-Σ _a π(a| s) (π(a| s)) is the entropy of the policy π. The expectation is with respect to the probability distribution ℙμ0πP^π_ _0, the induced distribution over infinite trajectories following π, μ0 _0, and the Markovian transition kernel ′P [40]. The optimal policy πProd∗ _Prod^*, corresponding to a reward function r′r , is the maximizer of (1), i.e., πProd∗=argmaxπJMaxEnt(π;r′). _Prod^*= _πJ_MaxEnt(π;r ). (2) As shown in [40], the maximizer is unique and this policy is well defined. 3 Problem Statement We investigate the problem of learning a reward machine that makes a policy optimal, without assuming that the rewards, the machine nodes, or the atomic propositions are observed. This problem is ill-posed since several reward machines could make a policy optimal. To write this problem formally, we first introduce the notion of history policy (which captures the information available for solving this learning problem), and then the notion of policy equivalence (which characterizes equivalent solutions of this learning problem). 3.1 History Policy and Reward Machine Equivalence Consider an MDP model, a RM, and a compatible labeling function. As shown in Section 2.2, this allows to define the product MDP and the corresponding optimal product policy. The history policy, denoted πh:Domh→Δ() _h:Dom_h→ (A) is defined as πh(a|s,τ)=πProd(a|s,δu⋆(uI,L(τ))). _h(a|s,τ)= _Prod(a|s, _u (u_I,L(τ))). (3) The domain Domh⊆×∗Dom_h ×S^* is the largest set for which the right-hand side of (3) is well defined. In (3), τ∈∗τ ^* is a trajectory of states leading up to the current state s∈s . While πProd _Prod, δu _u, and L are not known, the history policy πh _h is assumed to be available111While we make this assumption for simplicity, in practice, instead of πh _h, one has access to state-action trajectories of an agent implementing πh _h. Then, πh _h can be estimated by a sample average. A discussion on the effects of such estimation can be found in [32].. In that sense, the history policy serves as a state-only representation of the product policy, capturing the agent’s behavior through the sequence of observable MDP states. We say that the product policy πProd _Prod induces πh _h. The history policy can take an arbitrarily long trajectory τ as argument. In contrast, we define the depth-l restriction of the history policy, denoted as πhl _h^l, by restricting its domain to trajectories of length at most l, i.e., the domain of πhl _h^l is Domh∩(×∪j=1lj)Dom_h∩ (S× _j=1^lS^j ). As mentioned before, the inverse reinforcement learning problem we are interested in can have multiple solutions. This is captured by the following definition. Definition 1 Two labeled reward machines are policy-equivalent with respect to an MDP model if the optimal product policies for each of the labeled reward machines induce the same history policy. Among all the labeled reward machines that are policy equivalent with respect to an MDP model, we define a minimal reward machine as one with the fewest number of nodes. 3.2 Formal problem statement We now have all the ingredients to formalize the problems we are interested in. For an MDP model and labeled RM, consider the induced optimal history policy. Knowing the MDP model and (a depth-l∗l^* restriction of) the history policy, is it possible to recover a labeled RM that is policy equivalent to the true one? This research question can be divided in the following: (P1) Does there always exist a depth l∗l^* such that, given the MDP model ℳM, an upper bound umaxu_max on the number of nodes of the underlying reward machine and the depth-l∗l^* restriction πhl _h^l of the true history policy, it is possible to learn a labeled reward machine that is policy-equivalent to the underlying one? (P2) If l∗l^* in problem (P1) exists, find a minimal labeled reward machine that is policy-equivalent to the underlying one. 4 Methodology The problem of learning a reward machine (RM) directly from policies when the labels are known has previously been addressed in [31] with a two step process: 1) a Boolean Satisfiability (SAT) problem [14, 9] to learn a RM model; 2) a structured IRL problem that uses the product of the labeled RM model from step 1 and the MDP to recover the reward function. We present in this section how to extend this framework, and in particular step 1, to the more general and challenging setting in which the labeling function is unknown and must be learned jointly with the reward machine model. 4.1 Learning a Labeled Reward Machine The unknown quantities that we aim to learn are the RM transition function δ _u, the labeling function L, and the output function δ _r. Learning δ _u, and L corresponds to the generalization of step 1 of the process described above. Learning an output function, i.e., a reward function for the product, consistent with a policy corresponds to step 2 and has been addressed in prior works [13, 31]. Therefore, this paper focuses on inferring δ _u and L. In this section, we present a SAT problem allowing to learn δ _u and L, i.e., a labeled reward machine model denoted G. Without loss of generality, let us write =1,…,||S=\1,…,|S|\, =1,…,||U=\1,…,|U|\, AP=1,…,|AP|AP=\1,…,|AP|\, and consider uI=1u_I=1 and L(1)=1L(1)=1. The transition function δ _u and the labeling function L are encoded by binary values as follows: bjpi=1if δ(i,p)=j,0otherwise, and pk=1if L(k)=p,0otherwise,b_jpi= cases1&if _u(i,p)=j,\\ 0&otherwise, cases\ \ and \ \ L_pk= cases1&if L(k)=p,\\ 0&otherwise, cases (4) where i,j=1,…,||i,j=1,…,|U|, p=1,…,|AP|p=1,…,|AP|, and k=1,…,||k=1,…,|S|. The core constraints in the SAT formulation arise from negative examples, which follow from the following lemma. Lemma 1 Let τ,τ′∈∗τ,τ ^* be two state trajectories. If πh(a|s,τ)≠πh(a|s,τ′) _h(a|s,τ)≠ _h(a|s,τ ) for some (s,a)∈×(s,a) ×A, then δ∗(uI,L(τ))≠δ(uI,L(τ′)) _u^*(u_I,L(τ))≠ _u(u_I,L(τ )). Proof It follows directly from the definition of the history policy (equation (3)). A pair of state trajectories τ,τ′\τ,τ \ that satisfies the assumption of Lemma 1 is called a negative example, meaning the atomic proposition trajectories L(τ)L(τ) and L(τ′)L(τ ) should lead to different reward machine nodes starting at uIu_I. The following set collects all negative examples of length at most l: ℰl−=τ,τ′|πhl(a|s,τ)≠πhl(a|s,τ′) for some (s,a)∈×.E^-_l= \\τ,τ \\; |\; _h^l(a|s,τ)≠ _h^l(a|s,τ ) for some (s,a) ×A \. (5) Note that τ and τ′τ may have different lengths (both not larger than l). For each pair τ,τ′∈ℰl−\τ,τ \ ^-_l, Lemma 1 imposes some constraints on δ _u and L. To write these constraints via our binary encoding we need to introduce some notation. First, let us define the binary matrices (Bp)ji=bjpi(B_p)_ji=b_jpi and note that they satisfy (Bp)ji=1(B_p)_ji=1 if and only if δ(i,p)=j _u(i,p)=j. In words, BpB_p represents the transitions in the RM for a given atomic proposition p. Next, for a state k∈k , consider the matrix Mk=(B1∧⋆1,k)∨⋯∨(B|AP|∧⋆|AP|,k),M_k=(B_1 L_1,k)\; \;·s\; \;(B_|AP| L_|AP|,k), (6) where ∧⋆ denotes point-wise conjunction between a Boolean matrix and a Boolean scalar. This binary matrix satisfies (Mk)ji=1(M_k)_ji=1 if and only if δ(i,L(k))=j _u(i,L(k))=j. In words, MkM_k represents the transitions in the RM for a given MDP state k. Finally, for a state trajectory τ=(k1,…,kt)∈tτ=(k_1,…,k_t) ^t, consider the binary vector vτ=MktMkt−1…Mk1[10⋯0]⊤,v_τ=M_k_tM_k_t-1… M_k_1 bmatrix1&0&·s&0 bmatrix , which satisfies (vτ)i=1(v_τ)_i=1 if and only if δ∗(uI,L(τ))=iδ^*(u_I,L(τ))=i (let us remind that we assumed uI=1u_I=1). Here, vτv_τ represents the node at which the RM will be after emitting the labels of the state trajectory τ. For a pair of negative examples τ,τ′∈ℰl−\τ,τ \ ^-_l, the condition δ∗(uI,L(τ))≠δ∗(uI,L(τ′)) _u^*(u_I,L(τ))≠ _u^*(u_I,L(τ )) given by Lemma 1 can be written vτ≠vτ′v_τ≠ v_τ . Overall, the SAT problem that encodes the learning of δ _u and L is the following: Problem 1 For a fixed l, find bjpib_jpi and pkL_pk for i,j=1,…,||i,j=1,…,|U|, p=1,…,|AP|p=1,…,|AP|, and k=1,…,||k=1,…,|S| such that: ∑jbjpi _jb_jpi =1 =1 (δ is a function) ( _u is a function) (7a) ∑pk _pL_pk =1 =1 (L is a function) (L is a function) (7b) 1,1 _1,1 =1 =1 (Anchoring: L(1)=1) (Anchoring: L(1)=1) (7c) ∀τ,τ′∈ℰl−:vτ ∀\τ,τ \ _l^-:\ v_τ ≠vτ′ ≠ v_τ (Compatibility with negative examples) (Compatibility with negative examples) (7d) bjpi=1⇒bjpj b_jpi=1 b_jpj =1 =1 (Non-stuttering, optional constraint) (Non-stuttering, optional constraint) (7e) where each constraint must hold for all free indices. Constraints (7a) and (7b) ensure that δ _u and L are well defined, respectively. Constraint (7c) removes some solutions which are equivalent up to permutation. Constraint (7d) enforces the conditions given by Lemma 1. Finally, constraint (7e) allows to enforce some prior knowledge on the reward machine, when such information exits. More precisely, it enforces ∀i,j,p:δ(i,p)=j⇒δ(j,p)=j∀ i,j,p: _u(i,p)=j _u(j,p)=j which holds if the underlying task is multi-stage and duration-insensitive (i.e., stutter-invariant). This constraint prevents repeated self-transitions under the same proposition and enables trace compression [22, 32]. Note that in Problem 1, it is enough to know an upper bound umaxu_max on |||U|. The same is true for |AP||AP|, but one can always choose |AP|=|||AP|=|S|. Indeed, if there are more atomic propositions than states, one can consider only the atomic propositions in L()L(S) whose cardinality is at most |||S|. Next, we present the main theoretical result of this section. Proposition 4.1 below specifies the required l∗l^* from Section 3.2. Proposition 1: Sufficient Depth Given an MDP model, an upper bound umaxu_max on the number of nodes of the underlying reward machine and the depth-l∗l^* restriction πhl∗ _h^l^* of some history policy πh _h, where l∗=||umax2l^*=|S|u_max^2, Problem 1 is satisfiable with l=l∗l=l^* if and only if it is satisfiable for all l>l∗l>l^*. 4.2 Proof of Proposition 4.1 In order to prove Proposition 4.1, let us first introduce the notion of synchronized labeled reward machine model. It allows to run two labeled reward machine models in parallel. It will be used to compare the ground truth labeled reward machine with the learned one. Definition 2 Let 1=(1,uI1,AP1,δ1,,L1),2=(2,uI2,AP2,δ2,,L2)G_1=(U_1,u_I^1,AP^1, _u^1,S,L^1),\ G_2=(U_2,u_I^2,AP^2, _u^2,S,L^2) be two labeled reward machine models with the domains of L1L^1 and L2L^2 being a same set S. The synchronized labeled reward machine model is the labeled reward machine model defined as follows: sync ^sync =(sync,uIsync,APsync,δsync,,Lsync) =(U^sync,u_I^sync,AP^sync, _u^sync,S,L^sync) sync ^sync =1×2, =U_1×U_2, uIsync u_I^sync =(uI1,uI2), =(u_I^1,u_I^2), APsync ^sync =AP1×AP2 =AP^1×AP^2 δsync((u1,u2),(l1,l2)) _u^sync((u^1,u^2),(l^1,l^2)) =(δ1(u1,l1),δ2(u2,l2)) =( _u^1(u^1,l^1), _u^2(u^2,l^2)) Lsync(s) L^sync(s) =(L1(s),L2(s)). =(L^1(s),L^2(s)). The following definition introduces cycles in a product MDP. The core of the proof relies on removing cycles in the synchronized product MDP model. Definition 3 Let ℳ∖rM r be an MDP model and G be a (compatible) labeled reward machine model. Let ℳProdM_Prod be the corresponding product MDP model. Given a state trajectory τ=(s1,s2,⋯,st)∈∗τ=(s_1,s_2,·s,s_t) ^*, we say that a subsequence si:js_i:j of τ is a cycle in ℳProdM_Prod if si=sjs_i=s_j and δu∗(uI,L(s:i))=δu∗(uI,L(s:j)) _u^*(u_I,L(s_:i))= _u^*(u_I,L(s_:j)). Proof(of Proposition 4.1) We will refer to Problem 1 with a given l by SATlSAT_l. Let j>l∗j>l^* be a natural number. First, let us prove the “if” direction. Assume that SATjSAT_j has a solution. Then, it satisfies constraint (7d) for all τ,τ′∈ℰj−\τ,τ \ ^-_j. But since l∗<jl^*<j, ℰl∗−⊆ℰj−E^-_l^* ^-_j. Since removing constraints can not make a solution infeasible, the solution of SATjSAT_j is also a solution of SATl∗SAT_l^*. Second, let us prove the “only if” direction. By contradiction, assume that SATl∗SAT_l^* has a solution which is not a solution to SATjSAT_j. This solution defines functions δ δ_u and L L through the binary encoding (4). Since this is not a solution to SATjSAT_j, there exists a pair of negative examples τ,τ′∈ℰj−\τ,τ \ ^-_j which does not satisfy condition (7d). That is, τ,τ′τ,τ satisfy πh(a|s,τ)≠πh(a|s,τ′) _h(a|s,τ)≠ _h(a|s,τ ) (8) for some (s,a)∈×(s,a) ×A, and δ^(uI,L^(τ))=δ^(uI,L^(τ′)). δ_u(u_I, L(τ))= δ_u(u_I, L(τ )). (9) Denote by syncG^sync the synchronized product between the true labeled reward machine model =(,uI,AP,δ,,L)G=(U,u_I,AP, _u,S,L) and the learned one G. Consider the product MDP model ℳprod,mM_prod,m obtained from the MDP model and the synchronized labeled RM model. A state in ℳprod,mM_prod,m is a tuple (s,u,u^)∈×^(s,u, u) ×U× U, which shows that ℳprod,mM_prod,m contains |||||^|≤||umax2=l∗|S||U|| U|≤|S|u_max^2=l^* states. Now, consider the trajectory τ¯ τ (resp. τ¯′ τ ) obtained by removing cycles of τ (resp. τ′τ ) in ℳprod,mM_prod,m. Since ℳprod,mM_prod,m has at most l∗l^* states, this can be repeated until |τ¯|≤l∗| τ|≤ l^* (resp. |τ¯′|≤l∗| τ |≤ l^*). Since only cycles have been removed, the corresponding nodes in the synchronized labeled RM model stay unchanged, i.e., δsync,∗(uIsync,Lsync(τ))=δsync,∗(uIsync,Lsync(τ¯)),δ^sync,*_u(u_I^sync,L^sync(τ))=δ^sync,*_u(u_I^sync,L^sync( τ)), and similarly for τ′τ . By definition of the synchronized labeled RM model, this gives δ∗(uI,L(τ)) δ^*_u(u_I,L(τ)) =δ∗(uI,L(τ¯)), =δ^*_u(u_I,L( τ)), (10) δ^∗(uI,L^(τ)) δ^*_u(u_I, L(τ)) =δ^∗(uI,L^(τ¯)), = δ^*_u(u_I, L( τ)), (11) and similarly for τ′τ . It follows from (10) and (3) that πh(a|s,τ)=πh(a|s,τ¯) _h(a|s,τ)= _h(a|s, τ), and similarly for τ′τ . Consequently, (8) implies πh(a|s,τ¯)≠πh(a|s,τ¯′) _h(a|s, τ)≠ _h(a|s, τ ). That is, the pair τ¯,τ¯′\ τ, τ \ is a negative example, i.e., τ¯,τ¯′∈ℰl∗−\ τ, τ \ ^-_l^*. In addition, it follows from (11) and (9) that δ^(uI,L^(τ¯))=δ^(uI,L^(τ¯′)) δ_u(u_I, L( τ))= δ_u(u_I, L( τ )). Overall, we have shown that the pair τ¯,τ¯′∈ℰl∗−\ τ, τ \ ^-_l^* contradicts Lemma 1 which is encoded as constraint (7d). Therefore, the solution to SATl∗SAT_l^* does not satisfy constraint (7d), a contradiction. 4.3 Active Extension of the History Policy One major bottleneck for solving Problem 1 comes from encoding all the negative examples in (7d) given a depth-l restriction of the history policy. Since the number of state trajectories for a standard stochastic MDP grows exponentially in the depth, representing (or storing) the history policy becomes increasingly infeasible, even for moderate depths and small state spaces. However, our key observation is that exhausting all the possible paths of the history policy is not necessary to shrink the solution set. We formalize this observation as follows. Observation 1: Not All Trajectories are Created Equal Suppose that we solved the SAT problem with a depth-l restriction of the history policy, which is less than the sufficient depth l∗l^*, and obtained a solution set of candidate labeled reward machine models. Let τ be a length (l+k)(l+k) state trajectory, for any k≥1k≥ 1, and let τ:l _:l be the first l states in τ. Finally, let δ,L _u,L be a ground truth transition function and labeling function respectively. If δ∗(uI,L(τ))=δ∗(uI,L(τ:l))δ^*_u(u_I,L(τ))=δ^*_u(u_I,L( _:l)), then τ will not reduce the candidate solution set, as it cannot introduce any new negative examples. While we do not know δ _u or L, the above observation aims at highlighting that many paths in the history policy are redundant when it comes to shrinking the candidate solution set. Hence, this motivates designing an active extension algorithm, which reduces the memory and computation requirements of fully extending the history policy. Our strategy adopts a volume-removal approach to active learning, where queries are selected to significantly reduce the number of hypotheses consistent with current observations. Similar volume-reduction techniques have proven effective in preference-based reward learning [28, 11, 10, 15]. In our setting, we query trajectory extensions (histories) that are expected to most rapidly eliminate candidate labeled reward machine models consistent with the current depth history policy. For a given depth l<l∗l<l^*, let the set of feasible solutions of Problem 1 be denoted feasible=i^i=1NP_feasible=\ G_i\_i=1^N, where N is the total number of feasible solutions. This depth l represents the burn-in cost in order to obtain a reasonably sized solution set. The key idea is to search for state trajectory pairs τ,τ′\τ,τ \ for which half of the labeled reward machine models in the solution set end up in the same node, and the other half does not. If any pair τ,τ′\τ,τ \ turns out to be an actual negative example when querying the extended ground truth history policy, then we have eliminated half of the reward machines in the solution set by just adding a single negative example. To formalize this, let B be the query budget, which represents the maximum number of state trajectory pairs that we can query the history policy by. Our active learning algorithm runs as follows: Algorithm 1: Active Extension Algorithm 1. Initialize: Start with an empty candidate set =∅.C= . 2. Subsample: Sample a subset of the feasible SAT solutions active≜^ii=1NactiveP_active \ G_i\_i=1^N_active. 3. Generate Candidates: For each ^i=(^,u^I,APi,δ^i,,L^i)∈active G_i=( U, u_I,AP^i, δ_u^i,S, L^i) _active, sample a random target node utarget∈^u_target∈ U and use randomized DFS [26] to find trajectory pairs τ,τ′\τ,τ \ of length l+1l+1 ending in the same MDP state such that δ^i,∗(u^I,L^i(τ))=δ^i,∗(u^I,L^i(τ′))=utarget δ_u^i,*( u_I, L^i(τ))= δ_u^i,*( u_I, L^i(τ ))=u_target. Add these pairs to C. 4. Evaluate Quality: For each τ,τ′∈\τ,τ \ , for each labeled reward machine model ^i∈active G_i _active with transition function δ^i δ_u^i and labeling function L^i L^i, let ui=δ^i(uI,L^i(τ)),ui′=δ^i(uI,L^i(τ′)),u_i= δ_u^i(u_I, L^i(τ)),u_i = δ_u^i(u_I, L^i(τ )), and define the quality of τ,τ′\τ,τ \ to be: quality(τ,τ′)=min∑i=1Nactive(ui=ui′),∑i=1Nactive(ui≠ui′), quality(τ,τ )= \ _i=1^N_active1(u_i=u_i ), _i=1^N_active1(u_i≠ u_i ) \, (12) which counts how many models in activeP_active predict a node collapse (ui=ui′u_i=u_i ) versus a node separation (ui≠ui′u_i≠ u_i ) when traversed with τ,τ′.\τ,τ \. 5. Query: Sort the trajectory pairs based on the quality metric and query the history policy for the top B pairs. If ∃s∗,a∗∃ s^*,a^* such that πh(a∗|s∗,τ)≠πh(a∗|s∗,τ′) _h(a^*|s^*,τ)≠ _h(a^*|s^*,τ ), add τ,τ′\τ,τ \ to the set of negative examples. 6. Refine: Resolve the SAT problem incrementally with the new negative examples and update the feasible solution set feasibleP_feasible. 7. Iterate/Terminate: If the feasible solution set has converged to a single model up-to-renaming, terminate; otherwise, increment l=l+1l=l+1 and return to Step 2. We note that the quality measure for a trajectory pair, quality(τ,τ′) quality(τ,τ ), is maximized when the pair bisects the candidate solution set. Also, given that exhaustive enumeration of all possible paths in Step 3 is computationally prohibitive, we employ a randomized Depth First Search (DFS) algorithm [26] with an upper bound on the size of C222In our experiments, we set ||≤10,000.|C|≤ 10,000.. This allows the exploration of deeper paths within the history policy tree than exhaustive search allows. Another algorithmic optimization we employ is re-solving the SAT problem incrementally by simply adding the newly discovered negative examples to the existing SAT instance. This allows us to increment the depth in Step 7 of the algorithm without resolving with the exhaustive history policy (essentially the starting burn-in depth is fixed). We evaluate the empirical performance of this active approach in the experiments section. 5 Experiments To evaluate the effectiveness of our proposed framework, we consider a grid world navigation environment (Figure 2(a)). Each cell in this 4×44× 4 grid structure represents an MDP state. During navigation, the robot occasionally slips into neighboring cells upon taking a step along one of the 4 cardinal directions. We consider two tasks: pick_n_drop and patrolABCD. Figures 1(a) and 2(a) show the color-coded ground-truth labeling function. For example, the blue cell in Figure 1(a) denotes the pickup location and the red cells in Figure 2(a) represents proposition AA. These labels (A,B,C, etc.A,B,C, etc.) could in principle denote an area that has certain properties (cold/hot), or contains landmarks (coffee/mail). It is important to emphasize that the labeling of these cells is hidden from our algorithm. (a) (b) 44668810101212141416161818202010010^010110^110210^210310^310410^412Depth# of SolutionsNactive=50N_active=50Nactive=100N_active=100Random (c) 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. 5.1 Task 1: pick_n_drop The robot’s objective is to perform a standard warehouse automation task: visit the pickup location (bottom right, Figure 1(a)) and then the drop-off location (top left, Figure 1(a)) in a cyclic manner while avoiding passing through a danger zone (the 44 states colored yellow in the bottom middle, Figure 1(a)). The corresponding ground-truth reward machine is shown in Figure 1(b). Above each edge between two nodes, there is a tuple showing the label initiating the transition and the corresponding reward value. Critically, our learning algorithm does not have access to the reward machine transitions or the underlying warehouse arrangement. It operates solely on raw state trajectories extracted from the expert’s patrolling policy. Using a depth-9 expert history policy, our algorithm returns 1212 solutions and successfully recovers the ground-truth reward machine. It correctly assigns distinct labels to the pickup, drop-off and avoid locations while grouping all remaining states under a common label. These solutions differ only by renaming, which does not change the task specification, making them equivalent to the ground truth. To evaluate the performance of our active extension algorithm, we start with a burn-in depth of l=3l=3. Due to the sparsity of negative examples at this depth, the number of feasible labeled reward machine models (i.e. feasible solutions to Problem 1) exceeds 150K150K. We only keep 10K10K of these solutions. We run our active extension algorithm with Nactive=50,100N_active=\50,100\ and a budget =250 B=250. We compare our active extension algorithm against a baseline that randomly generates feasible state trajectory pairs and queries the history policy. Results in Figure 1(c) show the mean solution count across 15 independent trials. With Nactive=100N_active=100, our active extension algorithm converges to the ground-truth solution set in 100%100\% of the trials by depth 1212. Running our algorithm with Nactive=50N_active=50 also performed well (stabilizing at the ground truth solution by depth 1818), while the random baseline failed to find any restrictive constraints even as far as depth 20.333We note that any depth beyond 1010 is practically infeasible to solve using the full restriction of the history policy, highlighting the computational significance of our algorithm. 5.2 Task 2: patrolABCD The robot’s objective here is to patrol the rooms in the order A→B→C→DA (Figure 2(a)). The task is encoded by the ground truth reward machine shown in Figure 2(b). By using the depth-99 restriction of the expert’s history policy, we recover the ground truth labeled reward machine model and the clustering of grid cells into their respective propositions up-to-renaming (this amounts to a total of 36 solutions444There is 66 possible node naming permutations of the labeled reward machine model and 66 naming permutations of the labeling assignments given that the label of the first state is anchored (Equation 7c), thus we have 6×6=366× 6=36 total renaming solutions.). As shown in Table 1, this results in |ℰ9−|≈414M|E^-_9|≈ 414M, meaning that we have over 414M414M negative examples. In our experiments, we group these negative examples by their terminal state and sample 50005000 of these negative examples at random from each group. We also test our framework on a tetris variant of the room structures (Figure 2(c)), to which the results remain unchanged. That is, our algorithm perfectly recovers the labeling function up to renaming. (a) (b) (c) Figure 2: (a) The room grid world. (b) The patrol reward machine. (c) The Tetris rooms grid world. For our active learning algorithm, we initialize the process with a burn-in depth of l=6l=6. At this depth, the history policy consists of 68956895 unique branches, and solving SATl=6SAT_l=6 yields a hypothesis space of 11521152 distinct solutions. We constrain the negative example query budget to =250 B=250 per depth increment. We examine two sub-sampling sizes, Nactive∈100,200N_active∈\100,200\. Figure 3(a) shows the mean solution count across 3030 independent trials. The blue curve represents the solution count when using the full depth-l restriction of the history policy, for 6≤l≤136≤ l≤ 13. Both Nactive=100N_active=100 and Nactive=200N_active=200 exhibit similar performance, achieving faster convergence to the ground truth solution set than the random sampling baseline. Specifically, with Nactive=200N_active=200, 96.6%96.6\% of trials converge to the ground-truth solution set (up-to-renaming) by depth 1313, while 83.3%83.3\% converge at the same depth with Nactive=100N_active=100. In contrast, the random sampling baseline still averages 378.0378.0 candidate solutions and exhibits a standard deviation nearly two orders of magnitude larger than that of our active extension method. 6677889910101111121213134004008008001,2001,20036Depth# of SolutionsSolution CountFull πh _hNactive=200N_active=200Nactive=100N_active=100Random6677889910101111121213134004008008001,2001,20036Depth# of SolutionsSolution CountFull πh _hNactive=200N_active=200Nactive=100N_active=100Random (a) 66778899101011111212131310K1M100MDepthNumber of TrajectoriesBranching ComplexityFull πh _hActive - =250 B=250 (b) Figure 3: (a): Reduction in solution set size vs depth. (b): Growth of the number of trajectories vs depth. Beyond exact recovery, we show in Table 1 the efficiency gains of the active extension algorithm as compared to the full depth restriction history policy (exhaustive). The latter quickly hits a memory bottleneck, requiring approximately 24.7624.76 GB to store over 414414 M negative examples at depth 99. This is due to the exponential growth in the number of state trajectories depicted in Figure 3(b). In contrast, the active method selectively queries the environment and maintains only 10.310.3 K branches and 0.2920.292 M negative examples even at depth 1313, reducing the memory required for negative examples to just 0.1470.147 GB, effectively reducing the memory requirement for negative examples by two orders of magnitude. Method Depth (l) |τ||τ| |ℰl−||E^-_l| size (|τ|) size (|ℰl−||E^-_l|) 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. |ℰl−||E^-_l| is the number of negative examples. size (|τ|) is the memory required to store the trajectories. size (|ℰl−||E^-_l|) is the memory required to store the negative examples. The active extension algorithm also yields significant runtime improvements. As shown in Table 2, the exhaustive baseline is dominated by SAT solving, with a mean SAT time exceeding 71007100 seconds, despite terminating at depth 99. In contrast, the active method substantially reduces the SAT burden to 2417.122417.12 seconds on average while scaling to a deeper horizon (l=13l=13). Overall, the active extension achieves a mean total runtime of 3544.763544.76 seconds, nearly a 2×2× speedup over the exhaustive baseline, while still recovering the full ground-truth solution set. These results demonstrate that active extension alleviates both memory and computational bottlenecks, which lays the groundwork for scalable reward machine inference from raw state trajectories. Method Mean Discovery Time (s) Mean SAT Time (s) Total Time (s) Max Depth Sols Active Extension 1127.64±186.111127.64± 186.11 2417.12±6.162417.12± 6.16 3544.76±188.713544.76± 188.71 13 36 Exhaustive 26.80 7158.73±1640.397158.73± 1640.39 7185.53±1640.397185.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 23502350 s spent solving SAT with the depth-66 policy. 6 Discussion and conclusion In this paper, we studied reward machine inference in an information-scarce setting where only raw state trajectories and a depth-limited history policy are available, without observing rewards, labels, or automaton nodes. We introduced a SAT-based formulation that jointly infers the reward machine transition structure and a labeling function, and established a sufficient depth condition under which additional history does not further constrain feasibility. Building on this, we proposed an active extension strategy that selectively queries informative trajectory pairs to reduce the hypothesis space efficiently, yielding substantial memory and runtime gains while still recovering the ground-truth solution set up to renaming whenever this is possible with the exhaustive version. We emphasize that the present framework should be viewed as a foundational step, establishing the identifiability and algorithmic backbone of the problem, rather than a complete end-to-end practical solution. Because the current formulation assumes a discrete state-action space and access to the history policy induced by the optimal product policy, important questions remain regarding robustness to finite data and scalability to richer robotic domains. Nevertheless, the framework suggests several concrete directions for improving applicability: the history policy could be estimated from state-action trajectories using statistical extensions robust to estimation error as is done in known labeling function case [32], while selective querying could substantially reduce the computational burden where exhaustive expansion is infeasible. Furthermore, extending the framework beyond the tabular setting will likely involve learning labeling functions directly from perceptual representations, potentially leveraging pre-trained models [20]. A remaining limitation, however, is that the current termination criterion requires finding solutions up to renaming, which may be unnecessarily restrictive in practice. In general, it might be possible to terminate, even earlier that the sufficient depth, if all the candidate labeled reward machine models are policy-equivalent. Integrating such an equivalence-testing procedure into the active extension process while preserving the framework’s computational advantages represents a promising path for future research. More broadly, our work fits within a larger question of why memory is needed in sequential decision-making. Arguably, there are two primary sources of such memory requirements. The first is partial observation or epistemic uncertainty, where memory is needed to construct a sufficient information state for decision-making. The second is task structure, where successful behavior depends on remembering progress through a temporally extended objective, as in our setting. Our contribution is aimed at uncovering this second form of memory structure, represented as a reward machine and labeling function, directly from policy data. A natural next step, therefore, is to relate the present framework to the literature on information states [29] and learning Partially Observed Markov Decision Processes [30], with the broader goal of developing a unified understanding of memory requirements in robot decision-making. credits 6.0.1 Acknowledgements This work is supported in part by ONR CLEVR-AI MURI (#N00014- 21-1-2431). Antoine thanks his son Mathéo for giving him the time to finish this article. LLMs (ChatGPT, Gemini) have been used to polish parts of the writing of this paper. The output of the LLM is then thoroughly examined by the authors to maintain consistency and accuracy. References [1] A. Abate, Y. Almulla, J. Fox, D. Hyland, and M. Wooldridge (2023) Learning task automata for reinforcement learning using hidden markov models. In ECAI 2023, p. 3–10. Cited by: §1. [2] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané (2016) Concrete problems in AI safety. arXiv preprint arXiv:1606.06565. Cited by: §1. [3] J. Andreas, D. Klein, and S. Levine (2017) Modular multitask reinforcement learning with policy sketches. In Proceedings of the 34th International Conference on Machine Learning, Cited by: §1. [4] D. Angluin (1987) Learning regular sets from queries and counterexamples. Information and computation 75 (2), p. 87–106. Cited by: §1. [5] B. Araki, K. Vodrahalli, T. Leech, C. Vasile, M. D. Donahue, and D. L. Rus (2019) Learning to plan with logical automata. Robotics: Science and Systems Foundation. Cited by: §1. [6] M. Baert, S. Leroux, and P. Simoens (2024) Reward machine inference for robotic manipulation. arXiv preprint arXiv:2412.10096. Cited by: §1. [7] M. Baert, E. Malomgré, S. Leroux, and P. Simoens (2025) Reward machine inference for robotic manipulation. In IBRL @ RLC 2025, Cited by: §1. [8] A. G. Barto and S. Mahadevan (2003) Recent advances in hierarchical reinforcement learning. Discrete Event Dynamic Systems 13 (1–2), p. 41–77. Cited by: §1. [9] A. Biere, M. J. Heule, H. van Maaren, and T. Walsh (2009) Handbook of satisfiability. Vol. 185, IOS press. Cited by: §4. [10] E. Biyik, M. Palan, N. C. Landolfi, and D. Sadigh (2020-30 Oct–01 Nov) Asking easy questions: a user-friendly approach to active reward learning. In Proceedings of the 3rd Conference on Robot Learning, L. P. Kaelbling, D. Kragic, and K. Sugiura (Eds.), Proceedings of Machine Learning Research, Vol. 100, p. 1177–1194. External Links: Link Cited by: §4.3. [11] E. Biyik and D. Sadigh (2018-29–31 Oct) Batch active preference-based learning of reward functions. In Proceedings of The 2nd Conference on Robot Learning, A. Billard, A. Dragan, J. Peters, and J. Morimoto (Eds.), Proceedings of Machine Learning Research, Vol. 87, p. 519–528. External Links: Link Cited by: §4.3. [12] A. Camacho, J. Varley, A. Zeng, D. Jain, A. Iscen, and D. Kalashnikov (2021) Reward machines for vision-based robotic manipulation. In 2021 IEEE International Conference on Robotics and Automation (ICRA), p. 14284–14290. Cited by: §1, §1. [13] H. Cao, S. Cohen, and L. Szpruch (2021) Identifiability in inverse reinforcement learning. Advances in Neural Information Processing Systems 34. Cited by: §4.1. [14] S. A. Cook (1971) The complexity of theorem-proving procedures. Proceedings of the third annual ACM symposium on Theory of computing, p. 151–158. Cited by: §4. [15] S. Dasgupta (2004) Analysis of a greedy active learning strategy. In Advances in Neural Information Processing Systems 17 (NeurIPS 2004), p. 337–344. Cited by: §4.3. [16] D. DeFazio, Y. Hayamizu, and S. Zhang (2024) Learning quadruped locomotion policies using logical rules. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 34, p. 142–150. Cited by: §1. [17] D. Furelos-Blanco, M. Law, A. Russo, K. Broda, and A. Jonsson (2020) Induction of subgoal automata for reinforcement learning. In AAAI, Vol. 34. Cited by: §1. [18] H. Hasanbeig, N. Y. Jeppu, A. Abate, T. Melham, and D. Kroening (2024) Symbolic task inference in deep reinforcement learning. Journal of Artificial Intelligence Research 80, p. 1099–1137. Cited by: §1. [19] M. Hasanbeig, N. Y. Jeppu, A. Abate, T. Melham, and D. Kroening (2021) DeepSynth: automata synthesis for automatic task segmentation in deep reinforcement learning. In AAAI, Vol. 35, p. 7647–7656. Cited by: §1. [20] K. He, X. Zhang, S. Ren, and J. Sun (2016) Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 770–778. Cited by: §6. [21] J. Hu, Y. Paliwal, H. Kim, Y. Wang, and Z. Xu (2024) Reinforcement learning with predefined and inferred reward machines in stochastic games. Neurocomputing 599, p. 128170. Cited by: §1. [22] R. T. Icarte, T. Q. Klassen, R. Valenzano, M. P. Castro, E. Waldie, and S. A. McIlraith (2023) Learning reward machines: a study in partially observable reinforcement learning. Artificial Intelligence 323, p. 103989. Cited by: §1, §4.1. [23] H. Kress-Gazit, G. Fainekos, and G. J. Pappas (2018) Synthesis for robots: guarantees and feedback for robot behavior. Annual Review of Control, Robotics, and Autonomous Systems 1, p. 211–236. Cited by: §1. [24] A. Li, Z. Chen, T. Klassen, P. Vaezipoor, R. Toro Icarte, and S. McIlraith (2024) Reward machines for deep rl in noisy and uncertain environments. Advances in Neural Information Processing Systems 37, p. 110341–110368. Cited by: §1. [25] F. Memarian, Z. Xu, B. Wu, M. Wen, and U. Topcu (2020) Active task-inference-guided deep inverse reinforcement learning. In 2020 59th IEEE Conference on Decision and Control (CDC), p. 1932–1938. Cited by: §1. [26] R. Motwani and P. Raghavan (1996) Randomized algorithms. ACM Computing Surveys (CSUR) 28 (1), p. 33–37. Cited by: item 3, §4.3. [27] R. Parac, L. Nodari, L. Ardon, D. Furelos-Blanco, F. Cerutti, and A. Russo (2024) Learning robust reward machines from noisy labels. arXiv preprint arXiv:2408.14871. Cited by: §1. [28] D. Sadigh, A. D. Dragan, S. S. Sastry, and S. A. Seshia (2017-07) Active preference-based learning of reward functions. In RSS, External Links: Document Cited by: §4.3. [29] B. Sakcak, K. G. Timperi, V. Weinstein, and S. M. LaValle (2024) A mathematical characterization of minimally sufficient robot brains. The International Journal of Robotics Research 43 (9), p. 1342–1362. Cited by: §6. [30] S. Shaw, T. Manderson, C. Kessens, and N. Roy (2026) Toward learning pomdps beyond full-rank actions and state observability. arXiv preprint arXiv:2601.18930. Cited by: §6. [31] M. L. Shehab, A. Aspeel, N. Arechiga, A. Best, and N. Ozay (2024) Learning true objectives: linear algebraic characterizations of identifiability in inverse reinforcement learning. In L4DC, p. 1266–1277. Cited by: §4.1, §4. [32] M. L. Shehab, A. Aspeel, and N. Ozay (2025) Learning reward machines from partially observed policies. Transactions on Machine Learning Research. External Links: ISSN 2835-8856 Cited by: §1, §1, §4.1, §6, footnote 1. [33] R. S. Sutton and A. G. Barto (1998) Reinforcement learning: an introduction. MIT Press. Cited by: §1. [34] R. Toro Icarte, T. Klassen, R. Valenzano, and S. A. McIlraith (2018) Reward machines: exploiting reward function structure in reinforcement learning. In Advances in Neural Information Processing Systems, Cited by: §1. [35] R. Toro Icarte and S. A. McIlraith (2019) Learning reward machines for partially observable reinforcement learning. In Advances in Neural Information Processing Systems, Cited by: §1, §1. [36] C. K. Verginis, C. Koprulu, S. Chinchali, and U. Topcu (2024) Joint learning of reward machines and policies in environments with partially known semantics. Artificial Intelligence 333, p. 104146. Cited by: §1. [37] Z. Xu, I. Gavran, Y. Ahmad, R. Majumdar, D. Neider, U. Topcu, and B. Wu (2020) Joint inference of reward machines and policies for reinforcement learning. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 30, p. 590–598. Cited by: §1. [38] Z. Xu, A. Gawel, K. Muller, M. Yan, D. Juan, and Y. Hu (2020) Deep reward machine learning. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Cited by: §1. [39] Z. Xu, B. Wu, A. Ojha, D. Neider, and U. Topcu (2021) Active finite reward automaton inference and reinforcement learning using queries and counterexamples. In Machine Learning and Knowledge Extraction, A. Holzinger, P. Kieseberg, A. M. Tjoa, and E. Weippl (Eds.), Cham. Cited by: §1. [40] B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey (2008) Maximum entropy inverse reinforcement learning.. In AAAI, Vol. 8. Cited by: §2.2, §2.2.