{'fraction_non_alphanumeric': 0.03972014510994299, 'fraction_numerical': 0.010513067298437847, 'mean_word_length': 4.390063846767758, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
WFA-IRL: Inverse Reinforcement Learning of Autonomous Behaviors Encoded as Weighted Finite Automata

This paper presents a method for learning logical task specifications and cost functions from demonstrations. Constructing specifications by hand is challenging for complex objectives and constraints in autonomous systems. Instead, we consider demonstrated task executions, whose logic structure and transition costs need to be inferred by an autonomous agent. We employ a spectral learning approach to extract a weighted finite automaton (WFA), approximating the unknown task logic. Thereafter, we define a product between the WFA for high-level task guidance and a labeled Markov decision process for low-level control. An inverse reinforcement learning (IRL) problem is considered to learn a cost function by backpropagating the loss between agent and expert behaviors through the planning algorithm. Our proposed model, termed WFA-IRL, is capable of generalizing the execution of the inferred task specification in a suite of MiniGrid environments.


I. INTRODUCTION
Autonomous systems are expected to achieve reliable performance in increasingly complex environments with increasingly complex objectives. Yet, it is often challenging to design a mathematical formulation that captures all safety and liveness requirements across various operational conditions. Minimizing a misspecified cost function may lead to undesirable performance, regardless of the quality of the optimization algorithm. However, a domain expert is often able to demonstrate desirable or undesirable behavior that implicitly captures the task specifications. As a simple illustration, consider the navigation task in Fig. 1, requiring a door to be unlocked before reaching a goal state. Instead of encoding the task requirements as a cost function, an expert may provide several demonstrations of navigating to the goal, some of which require picking up the key whenever the door is locked. A reinforcement learning agent should infer the underlying logic sequence of the demonstrated task in order to learn the desired behavior.
Inverse reinforcement learning (IRL) [1]- [3] focuses on inferring the latent costs of expert demonstrations. Early works assume that the cost is linear in a set of state features and minimize the feature expectation difference between learned policy and demonstrations. [3] use dynamic programming to find a maximum entropy (MaxEnt) policy which maximizes the likelihood of the demonstrated actions. Later works [4], [5] introduce Gaussian process or deep neural networks to learn nonlinear cost functions. [6] builds a connection between MaxEnt IRL and adversarial learning   [9], where an agent has to pick up a key, open the door, and navigate to the goal. (Right) The trajectory can be decomposed into three segments, identified by hidden states αt. Transitions between the high-level states are triggered by events, such as picking up key (σ0), or opening door (σ1). and solves continuous control problems. Most IRL models, however, consider general cost formulations that do not explicitly capture sequencing and compositional requirements of the demonstrated task [7], [8]. Compared to a general cost formulation, this paper shows the logical structure of a complex task can be inferred from demonstrations. Exploiting the underlying task logic in planning ensures that the learned agent behavior mode matches the demonstrations.
Hierarchical reinforcement learning and options framework [10]- [13] are formulations that learn task decomposition and temporal abstraction. Options are high-level macro-actions consisting of primitive actions. [14] introduces a multi-level hierarchical model to discover options from demonstrations where option boundaries are inferred for trajectory segmentation. [15] uses an unsupervised encoderdecoder model to predict subtask segmentation and categorical latent encoding. [16] uses graph recurrent neural networks with relational features between objects for highlevel planning and low-level primitive dynamics prediction.
Formal methods have been applied in robotics to prove and guarantee different behavioral properties such as safety and correctness [17]- [20]. For example, linear temporal logic (LTL) [21] is used to specify safety and liveness objectives with temporal ordering constraints in control and reinforcement learning problems [20], [22]- [26]. Specification mining of LTL formulas can learn finite state automata from execution traces [27], [28]. LTL formulas can also be inferred from Bayesian inference [29] or from graph connectivity of directed acyclic graphs over atomic propositions [30]. In this work, we consider weighted finite automata (WFA) in which the transitions carry weights. Whereas classical automata determine whether a word is accepted or rejected, WFA can compute quantitative values as a function of the weighted transitions from the execution of words [31]. WFA offer the expressive power to model quantitative properties, such as resources, time or cost, of the demonstrated behavior. Under certain assumptions of the semiring on which the WFA is defined, it can be shown that WFA is expressively equivalant to weighted monadic second-order (MSO) logic [31], [32].
We introduce an IRL model that learns to infer highlevel task specifications and low-level control costs to imitate demonstrated behavior. Given a set of demonstrations, we use a spectral method to learn a WFA which encodes the task logic structure. The agent's interaction with the environment is modeled as a product between the learned WFA and a labeled Markov decision process (L-MDP). We propose a planning algorithm to search over the product space for a policy that satisfies task requirements encoded by the WFA. Since the true transition cost is not directly observable, we differentiate the error between the agent's policy and the demonstrated controls through the planning algorithm using a subgradient method introduced in [2], [33]. We demonstrate that our WFA-IRL method correctly classifies accepting and rejecting sequences and learns a cost function that generalizes the demonstrated behavior to new settings in several MiniGrid environments [9]. In summary, our contribution is to recognize that the logic structure of a demonstrated task can be learned as a weighted finite automaton and, in turn, can be integrated with differentiable task planning to learn generalizable behavior from demonstrations.

A. Agent and environment models
The agent's interaction with the environment is modeled as an L-MDP [34]. Definition 1. A labeled Markov decision process is a tuple {X , U, x 0 , f, c, AP, }, where X , U are finite sets of states and controls, x 0 ∈ X is an initial state, f : X × U → X is a deterministic transition function, and c : X × U → R ≥0 assigns a non-negative cost when control u ∈ U is applied at state x ∈ X . A finite set of atomic propositions AP provides logic statements that must be true or false (e.g., "the agent is 1 meter away from the closest obstacle" or "the agent possesses a key"). A labeling function : X × U → 2 AP assigns a set of atomic propositions that evaluate true for a given state transition.
We assume that the state x is fully observable and captures both endogenous variables for the agent, such as position and orientation, and exogenous variables, such as an environment containing objects of interest as illustrated in Fig. 1. The transition function f (x, u) specifies the change of state x when control u is executed, and c(x, u) assigns a nonnegative cost to this transition. The alphabet of the L-MDP is the set of labels Σ = 2 AP that can be assigned to the transitions. The labeling function σ = (x, u) provides the atomic propositions σ ∈ Σ which are satisfied during the transition f (x, u). The set of words on Σ is denoted by Σ * and consists of all strings σ 0:T = σ 0 . . . σ T for σ t ∈ Σ and T ∈ N. We assume that the transition f and labeling are known. However, the cost function c is unknown and needs to be inferred from expert demonstrations.

B. Expert model
The agent needs to execute a task, whose success is evaluated based on the word σ 0:T ∈ Σ * resulting from the agent's actions. We model the quality of the task execution by a function h : Σ * → R. An execution σ 0:T is deemed successful if h(σ 0:T ) ≥ ξ for a known performance threshold ξ, and unsuccessful otherwise. As argued in the introduction, defining the function h explicitly is challenging in many applications. Instead, we consider a training set D = (x n 0:Tn , u n 0:Tn , s n ) N n=1 of N demonstrations of the same task in different environment configurations provided by an expert. Each demonstration n contains the controls u n 0:Tn = u n 0 . . . u n Tn executed by the expert, the resulting agent-environment states x n 0:Tn = x n 0 . . . x n Tn , and the success level s n ∈ R of the execution, measured by h(σ n 0:Tn ), where σ n t = (x n t , u n t ) is the label encountered by the expert at time t. We assume that the expert knows the true task h and the true cost c and can solve a finite-horizon first-exit deterministic optimal control problem [35] over the L-MDP: where Q * (x, u) is the optimal value function. Since (1) is a deterministic optimal control problem, there exists an openloop control sequence which is optimal, i.e., achieves the same cost as an optimal closed-loop policy function [35,Chapter 6]. However, we consider experts that do not necessarily choose strictly rational controls. Instead, we model the expert behavior using a stochastic Boltzmann policy over the optimal values π * (u|x) ∝ exp − 1 η Q * (x, u) , where η ∈ (0, ∞) is a temperature parameter representing a continuous spectrum of rationality. For example, η → 0 means that the expert takes strictly optimal controls while η → ∞ means random controls are selected. The Boltzmann expert model was previously introduced and studied in [33], [36], [37]. It provides an exponential preference for controls that incur low long-term costs. This expert model also allows efficient policy search, as shown in Sec. IV-B, and computation of the policy gradient with respect to the cost needed to optimize the cost parameters, as shown in Sec. IV-C.

III. PROBLEM STATEMENT
The agent needs to infer the unknown task model h and unknown cost function c from the expert demonstrations D = (x n 0:Tn , u n 0:Tn , s n ) N n=1 . Problem 1. Given the demonstrations D and labeling σ n Fig. 2: Inferring the hidden state progression αt from events σt can be acheived by an RNN with initial hidden state α0, hidden state transition αt+1 = g1(σt, αt, W) and outputŝ = h ψ (σ0:T ) = g2(αT+1, β), where g1, g2 are nonlinear functions. The weights ψ = (α0, W, β) can be learned via the loss L(ŝ, s) in (2) between RNN outputsŝ and demonstration scores s. squared error: Similarly, the agent needs to obtain an approximation c θ with parameters θ of the unknown cost function c. This allows the agent to obtain a control policy: approximating the expert model using a value function Q θ computed according to (1) with c and h replaced by c θ and h ψ , respectively. log π θ (u n t |x n t ), (4) where 1 is an indicator function and ξ is the known task satisfaction threshold.

IV. TECHNICAL APPROACH
We first discuss how to learn a task model h ψ from demonstrations D in Sec. IV-A. Next, in Sec. IV-B, we learn a cost model c θ by solving the optimal control problem in (1) to obtain an agent policy π θ . Finally, in Sec. IV-C, we show how to backpropagate the policy loss L c (θ) in (4) through the optimal control problem to update the cost parameters θ.

A. Spectral learning of task specifications
Fitting a single cost neural network c θ that is capable of generalizing to various environment configurations and tasks is difficult when state and control spaces are large and the task horizon is long. An alternative is to consider the cost function and its corresponding policy only for small segments of the task, associated with different subtasks. This idea is based on the observation that task specifications often have a compositional logic structure. For example, the demonstrated trajectory in the DoorKey environment in Fig. 1 can be decomposed into three segments, each denoted by a high-level state α. The transitions between the highlevel states are triggered by events like σ 0 : a key is picked up, and σ 1 : a door is opened. Note that there is no direct transition between α 1 and α 3 because the door cannot be opened without possessing a key. Such high-level state abstraction and transitions are commonly learned via recurrent neural network (RNN) or memory architectures [38], [39]. For example, to solve Problem 1, we can use an RNN h ψ in Fig. 2 with initial hidden state α 0 , hidden state transition α t+1 = g 1 (σ t , α t , W) and output function h ψ (σ 0:T ) = g 2 (α T+1 , β), where g 1 , g 2 are nonlinear functions and ψ = (α 0 , W, β) are learnable weights. Instead of an RNN model, in this work, we propose to use a weighted finite automaton (WFA) [40] to represent h ψ . A WFA is less expressive than an RNN [41] but can be trained more effectively from small demonstration dataset. Moreover, a WFA generalizes deterministic and nondeterministic finite automata, which are commonly used to model logic task specifications for autonomous agents [20], [22]- [24]. Hence, a WFA model is sufficiently expressive to represent a complex task and allows one to focus on a temporal abstraction without reliance on the low-level system dynamics.
Definition 2. A weighted finite automaton (WFA) with m states is a tuple ψ = α 0 , β, {W σ } σ∈Σ where α 0 , β ∈ R m are initial and final weight vectors and W σ ∈ R m×m are transition matrices associated with each symbol σ ∈ Σ. A WFA ψ represents a function h ψ : A WFA represents the task progress for a given word σ 0:t via h ψ (σ 0:t ) = α 0 W σ0 W σ1 . . . W σt β, where the highlevel state at time t+1 is α t+1 = α 0 W σ0 W σ1 . . . W σt . When the WFA is learned correctly, its prediction for an expert word should approximate the expert score s, i.e., h ψ (σ 0:T ) ≈ s. This can be used to guide a task planning algorithm by providing a task satisfaction criterion. A trajectory with corresponding word σ 0:T is identified as successful if the WFA prediction passes the known performance threshold introduced in Sec. II-B, i.e., h ψ (σ 0:T ) = α T+1 β ≥ ξ.
Our approach to learn a minimal WFA is based on the spectral learning method developed by [40]. The spectral method makes use of a Hankel matrix H h ∈ R Σ * ×Σ * associated with the function h : Σ * → R, which is a bi-infinite matrix with entries H h (u, v) = h(uv) for u, v ∈ Σ * . We assume the class of functions h that can be represented by a WFA are rational power series functions and their associated Hankel matrix H h has finite rank [42], [43]. It can be showns that under certain assumptions WFA are expressively equivalent to monadic second-order logic. The quantitative property of WFA allows us to model the performance score s of the demonstrated trajectories. Assumption 1. The Hankel matrix H h associated with the true task specification h has finite rank.
In practice, only finite sub-blocks of the Hankel matrix, constructed from the expert demonstrations D, can be con-sidered. Given a basis B = (P, S) where P, S ⊂ Σ * are finite sets of prefixes and suffixes respectively, define H B and {H σ } σ∈Σ as the finite sub-blocks of H h such that The foundation of the spectral learning method is summarized in the following theorem.
A basis can be chosen empirically from demonstrations D. For example, we can choose a basis that includes all prefixes and suffixes that appear in the words σ n

B. Planning in a product WFA-MDP system
Given a learned WFA representation h ψ and an initial cost estimate c θ , we propose a planning algorithm to solve the deterministic optimal control problem in (1) and obtain a control policy π θ (u|x) as in (3). To determine the termination condition for the problem in (1), we define the product of the WFA, modeling the task, and the L-MDP, modeling the agent-environment interactions.
To obtain the agent policy in (3) for any state x t ∈ X and control u t ∈ U, our goal is to compute the optimal cost-to-go values for the WFA-MDP model: where s t+1 = T (s t , u t ) and α T+1 β ≥ ξ. We have rewritten the terminal state condition as α T+1 β ≥ ξ, where we keep track of the task hidden state α t using the WFA-MDP transition function T . Our key observation is that (5) is a deterministic shortest path problem and V θ (T (s t , u t )) can be obtained via any shortest path algorithm, such as Dijkstra [44], A* [45] or RRT* [46]. When we use a shortest path algorithm to update the cost-to-go values of successor states s t+1 = T (s t , u t ), we concurrently compute the corresponding WFA state α t+1 = W σt α t where σ t = (x t , u t ). A goal state s T+1 is reached when its WFA state α T+1 satisfies α T+1 β ≥ ξ. The agent policy π θ in (3) with respect to the current cost estimate c θ can be obtained from the cost-to-go values Q θ in (5) computed by the shortest path algorithm.

C. Optimizing cost parameters
We discuss how to differentiate the loss function L c (θ) in (4) with respect to θ through the deterministic shortest path problem defined by the product WFA-MDP model. [33] introduce a sub-gradient descent approach to differentiate the log likelihood of expert demonstrations from the Bolzman policy in (3) through the optimal cost-to-go values in (5). The cost parameters can be updated by (stochastic) subgradient descent at each iteration k with learning rate γ (k) , θ (k+1) = θ (k) − γ (k) ∇L c (θ (k) ). Intuitively, the subgradient descent makes the trajectory starting with a demonstrated control more likely, while those with other controls less likely. The analytic subgradient computation is presented below. Proposition 1. [33, Proposition 1] Consider an expert transition (x t , u t ). Define τ (x t , u) as the optimal path starting from state x t and any control u ∈ U that achieves Q θ (x t , u) in (5) under cost estimate c θ . A subgradient of the agent policy (3) evaluated at expert transition (x t , u t ) with respect to cost parameters θ can be obtained via the chain rule as: Substituting (6) in the gradient of L c (θ) in (4), Proposition 1 provides an explicit subgradient computation to allow backpropagation with respect to θ through the value function Q θ of the deterministic shortest path problem in (5). The subgradient only affects the cost parameters through the optimal trajectories τ (x t , u ), ∀u ∈ U for expert transitions (x t , u t ) which can be retrieved from any optimal planning algorithm applied in Sec IV-B. Thereafter, the cost parameters can be optimized depending on the specific form of ∂c θ (x,u) ∂θ .
Our complete approach WFA-IRL is summarized in Fig. 3. We first solve Problem 1 to find a WFA h ψ which models the demonstrated task. The learned WFA provides termination conditions for a deterministic shortest path problem in the Fig. 3: WFA-IRL architecture for joint learning of a task specification h ψ and cost function c θ . Given demonstrations D and a labeling function , we learn the unknown task specification with a weighted finite automaton. We construct a product WFA-MDP space from the learned WFA ψ = α0, β, {Wσ} σ∈Σ to solve a deterministic shortest path problem with cost estimate c θ . The agent policy π θ is compared with the demonstrated controls to backpropagate the loss Lc(θ) with respect to θ.  Table I. The task specifications can be expressed in terms of these propositions, e.g., one possible trajectory that fulfills task T1 is to evaluate the propositions p 1 , p 2 , p 3 as true sequentially.

A. Demonstrations
An expert trajectory is collected by iteratively rolling out the controls sampled from the expert policy π * at each state x, where Q * (x, u) in (1) is computed via the Dijkstra's algorithm with cost of 1 for any feasible transition. For each task, we consider two sets of expert demonstrations D 1 and D 2 , each with 32 trajectories collected from expert policies with temperatures η ∈ {0, 0.5}. The expert trajectories in D 1 and D 2 are strictly optimal and suboptimal, respectively, and are labeled with score s = 1. In each set we also add 128 failed trajectories with score s = 0 from a random exploration policy (effectively setting expert policy temperature η → ∞).
The full demonstration set is used in each case to learn a WFA representation h ψ of the task via the spectral method in Sec. IV-A while only the successful trajectories are used to learn the cost function c θ , as in Sec. IV-B and IV-C.

B. Our method and baselines
Our method WFA-IRL uses a neural network architecture to represent the cost function. For a detailed description, please refer to Appendix A. We use the spectral learning algorithm in the Scikit-SpLearn toolbox [47] to learn the parameters ψ of the WFA from the expert demonstrations D. In the implementation, we first compress the demonstration words σ n 0:Tn where consecutive identical symbols are removed. This greatly reduces the complexity of learning the WFA while keeping the symbol sequences unchanged. The hyperparameters for the spectral learning method are the rank of the automaton (m in Theorem 1) and the sizes (rows and cols) of the prefix and suffix basis (B = (P, S) in Theorem 1), which determine the size of the Hankel matrix estimated empirically from demonstrations. The complexity is O(n × rank × rows × cols) since we iterate through the ranks to find a minimal WFA and count the prefix and suffix frequencies for a given word. The spectral method can learn almost perfectly with near zero loss in (2) for all tasks and the best hyperparameter configurations are shown in Table II. We observe that larger WFA capacity is required to learn from suboptimal trajectories and thus more diverse words from D 2 .
As baselines, we first ablate the WFA component in our method to understand its effects. Instead of planning in the product WFA-MDP space and checking the WFA termination condition in (5), the agent without WFA component simply plans in the original MDP and checks whether a goal state is achieved. Additionally, we compare our method with standard imitation learning and inverse reinforcement learning algorithms, including behavioral cloning (BC) [48] and GAIL [49] 1 . The value/policy functions in these baselines Fig. 5: Agent trajectory (left column) trained with D1 and expert trajectory (right column) in task T3 during testing. The agent WFA only learns words that appear in demonstration D1, which always moves Ball away from Door first before picking up Key. In testing it fails to recognize a lower cost trajectory of a different word sequence, where Key is carried closer to Door before moving away Ball. follow our cost neural network architecture to fit the statecontrol input format and to compare fairly in representation power across methods. This includes the policy network in BC, the discriminator in GAIL, the policy and value networks in PPO [51], used as generator in GAIL. Only the size of the last fully-connected layer is modified depending on whether it is action or value prediction. GAIL is known to achieve stable performance in fixed horizon environments while the MiniGrid environments terminate as soon as the agent fulfills the tasks. We fix this issue by adding a virtual absorbing state as suggested in [52] when training GAIL.

C. Results
We report the average performance of each method in Table II by testing on 64 new environment configurations generated randomly for each task. First, we observe that our method can achieve almost perfect performance when trained on D 1 . This is expected since the learned WFA strictly chooses planned trajectories whose words would match the optimal behavior. Interestingly, the learned WFA could make the agent suboptimal if the optimal word in testing is not seen in training, as shown in Fig. 5. Next, our method matches the expert performance well using either D 1 or D 2 and outperforms BC and GAIL (even without WFA). This demonstrates that using planning to solve tasks that encode logical structures performs better than a reactive policy employed by BC. Moreover, the performance gap between our method and ours without WFA shows that learning logic specifications explicitly with a WFA can further improve the policy. On the other hand, we find the performance of GAIL is limited as PPO cannot easily generate successful samples similar to the demonstrations (notice that the random policy never succeeds) to improve the cost discriminator and, in turn, the generator itself. We visualize the agent policy in Fig. 6 and observe that our method has a stronger bias on controls that follow the learned logical sequences.

VI. CONCLUSION
We present WFA-IRL which solves tasks with high-level reasoning and outperforms prior imitation learning and IRL methods that do not exploit logical structures from demonstrations. We show that cost functions learned via solving deterministic shortest path problems in the product WFA-MDP can generalize well in unseen environments and across demonstations of different optimality levels. Fig. 7: Neural network architecture for the transition cost c θ (xt, ut). The state xt consists of the grid image mt, the agent position pt, direction dt, object it is carrying ot. The grid mt is fed through a convolutional neural network (Conv), while the discrete variables pt, dt, ot and the control ut are converted to embedding vectors (Embed) to provide latent representations for learning the cost function. The concatenated vector of Conv and Embed layer outputs is passed through three fully-connected layers (Dense) to obtain c θ (xt, ut).

A. Neural network cost representation
We use a neural network, shown in Fig. 7 to learn a nonlinear cost function c θ , mapping from each state-control pair to a non-negative cost value. The cost neural network is separated into two parts. The first part is a feature extractor which processes each input type accordingly. The grid image is passed through a convolutional neural network, consisting of 3 stacks of convolution + ReLU layers with {16, 32, 64} filters of size 2. The agent position, direction, object carried and control are discrete variables and are passed through embedding layers to produce high-dimensional feature vectors. The embedding dimensions are {128, 64, 64, 128} respectively. The outputs from each feature extractor are flattened and concatenated to construct a latent vector representing the state-control pair in feature space. In the second part, a fullyconnected neural network maps the latent vector to a scalar output for cost prediction. The 3 fully-connected layers have sizes {64, 32, 1} with ReLU activation function. The cost neural network architecture is trained using Proposition 1 in PyTorch [53] with the Adam optimizer [54].