{'fraction_non_alphanumeric': 0.03366087798446738, 'fraction_numerical': 0.010197144799456152, 'mean_word_length': 4.628289855072464, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Task-Guided Inverse Reinforcement Learning Under Partial Information

We study the problem of inverse reinforcement learning (IRL), where the learning agent recovers a reward function using expert demonstrations. Most of the existing IRL techniques make the often unrealistic assumption that the agent has access to full information about the environment. We remove this assumption by developing an algorithm for IRL in partially observable Markov decision processes (POMDPs). The algorithm addresses several limitations of existing techniques that do not take the information asymmetry between the expert and the learner into account. First, it adopts causal entropy as the measure of the likelihood of the expert demonstrations as opposed to entropy in most existing IRL techniques, and avoids a common source of algorithmic complexity. Second, it incorporates task specifications expressed in temporal logic into IRL. Such specifications may be interpreted as side information available to the learner a priori in addition to the demonstrations and may reduce the information asymmetry. Nevertheless, the resulting formulation is still nonconvex due to the intrinsic nonconvexity of the so-called forward problem, i.e., computing an optimal policy given a reward function, in POMDPs. We address this nonconvexity through sequential convex programming and introduce several extensions to solve the forward problem in a scalable manner. This scalability allows computing policies that incorporate memory at the expense of added computational cost yet also outperform memoryless policies. We demonstrate that, even with severely limited data, the algorithm learns reward functions and policies that satisfy the task and induce a similar behavior to the expert by leveraging the side information and incorporating memory into the policy.


Introduction
Inverse reinforcement learning (IRL) is a technique that recovers a reward function using expert demonstrations and learns a policy inducing a similar behavior to the expert's. IRL techniques have found a wide range of applications (Abbeel, Coates, and Ng 2010;Kitani et al. 2012;Hadfield-Menell et al. 2016;Dragan and Srinivasa 2013;Finn, Levine, and Abbeel 2016). The majority of the work has focused on Markov decision processes (MDPs), assuming that the learning agent can fully observe the state of the environment and the expert's demonstrations (Abbeel, Copyright © 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Coates, and Ng 2010;Ziebart et al. 2008;Zhou, Bloem, and Bambos 2017;Ziebart, Bagnell, and Dey 2010;Hadfield-Menell et al. 2016;Finn, Levine, and Abbeel 2016). Often, in reality, the learning agent will not have such full observation. For example, a robot will never know everything about its environment (Ong et al. 2009;Bai, Hsu, and Lee 2014;Zhang et al. 2017) and may not observe the internal states of a human with whom it works (Akash et al. 2019;Liu and Datta 2012). Such information limitations violate the intrinsic assumptions made in existing IRL techniques.
We study IRL in partially observable Markov decision processes (POMDPs), a widely used model for decisionmaking under imperfect information. The partial observability brings three key challenges in IRL. The first two challenges are related to the so-called information asymmetry between the expert and the learner. First, the expert typically has access to full information about the environment, while the learner has only a partial view of the expert's demonstrations. Second, even in the hypothetical case in which the actual reward function is known to the learner, the learner's optimal policy under limited information may not yield the same behavior as the expert due to information asymmetry.
The third challenge is due to the computational complexity of policy synthesis in POMDPs. Many standard IRL techniques rely on a subroutine that solves the so-called forward problem, i.e., computing an optimal policy for a given reward. Solving the forward problem for POMDPs is significantly more challenging than MDPs, both theoretically and practically. Optimal policies for POMDPs may require infinite memory of observations (Madani, Hanks, and Condon 1999), whereas memoryless policies are enough for MDPs.
An additional limitation in existing IRL techniques is due to the limited expressivity and often impracticability of state-based reward functions in representing complex tasks (Littman et al. 2017). For example, it will be tremendously difficult to define a merely state-based reward function to describe requirements such as "do not steer off the road while reaching the target location and coming back to home" or "monitor multiple locations with a certain order." On the other hand, such requirements can be concisely and precisely specified in temporal logic (Baier and Katoen 2008;Pnueli 1977). Recent work has demonstrated the utility of incorporating temporal logic specifications into IRL in MDPs (Memarian et al. 2020;Wen, Papusha, and Topcu 2017). In this work, we address these challenges and limitations in IRL techniques by studying the problem: Task-guided IRL: Given a POMDP, a task specification ϕ expressed in temporal logic, and a set of expert demonstrations, learn a policy along with the underlying reward function that maximizes the causal entropy of the induced stochastic process, induces a behavior similar to the expert's, and ensures satisfaction of ϕ.
We highlight two parts of the problem statement. Using causal entropy as an optimization criterion results in a leastcommittal policy that induces a behavior obtaining the same accumulated reward as the expert's demonstrations while making no additional assumptions about the demonstrations. Given the task requirements, the task specifications guide the learning process by describing the feasible behaviors and allowing to learn performant policies with respect to the task requirements. Such specifications can also be interpreted as side information available to the learner a priori in addition to the demonstrations and partially alleviates the information asymmetry between the expert and the learner.
Most existing work on IRL relies on entropy as a measure of the likelihood of the demonstrations, yet, when applied to stochastic MDPs, has to deal with nonconvex optimization problems (Ziebart et al. 2008;Ziebart, Bagnell, and Dey 2010). On the other hand, IRL techniques that adopt causal entropy as the measure of likelihood enjoy formulations based on convex optimization (Zhou, Bloem, and Bambos 2017;Ziebart, Bagnell, and Dey 2010). We show similar algorithmic benefits in maximum-causal-entropy IRL carry over from MDPs to POMDPs.
A major difference between MDPs and POMDPs in maximum-causal-entropy IRL is, though, due to the intrinsic nonconvexity of policy synthesis in POMDPs, which yields a formulation of the task-guided IRL problem as a nonconvex optimization. It is known that this nonconvexity severely limits the scalability for synthesis in POMDPs. We develop an algorithm that solves the resulting nonconvex problem in a scalable manner by adapting sequential convex programming (SCP) (Yuan 2015;Mao et al. 2018). The algorithm is iterative. In each iteration, it linearizes the underlying nonconvex problem around the solution from the previous iteration. The algorithm introduces several extensions, among which a verification step not present in existing SCP schemes. We show that it computes a sound and locally optimal solution to the task-guided IRL problem.
In several examples, we show that the algorithm scales to POMDPs with tens of thousands of states as opposed to tens of states in the existing work, e.g., belief-based techniques. In POMDPs, finite-memory policies that are functions of the history of the observations outperform memoryless policies (Yu and Bertsekas 2008). Computing a finitememory policy for a POMDP is equivalent to computing a memoryless policy on a larger product POMDP (Junges et al. 2018). On the other hand, existing IRL techniques on POMDPs cannot effectively utilize memory, as they do not scale to large POMDPs. We leverage the scalability of our algorithm to compute more performant policies that incorporate memory using finite-state controllers (Meuleau et al. 1999;Amato, Bernstein, and Zilberstein 2010).
We demonstrate the applicability of the approach through several examples. We show that, without task specifications, the developed algorithm can compute more performant policies than a straight adaptation of the original GAIL (Ho and Ermon 2016) to POMDPs. Then, we demonstrate that by incorporating task specifications into the IRL procedure, the learned reward function and policy accurately describe the behavior of the expert while outperforming the policy obtained without the task specifications. Additionally, we show that incorporating memory into the learning agent's policy leads to more performant policies. We also show that with more limited data, the performance gap becomes more prominent between the learned policies with and without using task specifications. Finally, we demonstrate the scalability of our approach for solving the forward problem through extensive comparisons with several state-of-the-art POMDP solvers and show that on larger POMDPs, the algorithm can compute more performant policies in significantly less time.
Related work. The closest work to ours is by Choi and Kim (2011), where they extend classical maximum-marginbased IRL techniques for MDPs to POMDPs. However, even on MDPs, maximum-margin-based approaches cannot resolve the ambiguity caused by suboptimal demonstrations, and they work well when there is a single reward function that is clearly better than alternatives (Osa et al. 2018). In contrast, we adopt causal entropy that has been shown (Osa et al. 2018;Ziebart, Bagnell, and Dey 2010) to alleviate these limitations on MDPs. Besides, Choi and Kim (2011) rely on efficient off-the-shelf solvers to the forward problem. Instead, this paper also develops an algorithm that outperforms off-the-shelf solvers and can scale to POMDPs that are orders of magnitude larger compared to the examples in Choi and Kim (2011). Further, Choi and Kim (2011) do not incorporate task specifications in their formulations.
IRL under some restricted notion of partial information has been studied in prior work. Boularias, Krömer, and Peters (2012) consider the setting where the features of the reward function are partially specified. Kitani et al. (2012); Bogert and Doshi (2014) consider IRL problems from partially observable demonstrations and use the hidden Markov decision process framework as a solution. Therefore, all these approaches consider a particular case of POMDPs. We also note that none of these methods incorporate side information into IRL and do not provide guarantees on the performance of the policy with respect to a task specification.

Background
Notation. We denote the set of nonnegative real numbers by R + , the set of all probability distributions over a finite or countably infinite set X by Distr(X ), the set of all (infinite or empty) sequences x 0 , x 1 , . . . , x ∞ with x i ∈ X by (X ) * for some set X , and the expectation of a function g of jointly distributed random variables X and Y by E X,Y [g(X, Y )].

POMDPs.
A partially observable Markov decision process (POMDP) is a tuple M = (S, A, Z, P, O, R, µ 0 , γ), with finite sets S, A and Z denoting the set of states, actions, and observations, respectively, a transition function P : S × A → Distr(S), an observation function O : S → Distr(Z), a reward function R : S × A → R + , an initial state of distribution µ 0 ∈ Distr(S), and a discount factor γ ∈ (0, 1). We denote P(s |s, α) as the probability of transitioning to state s after an action α is selected in state s, and O(z|s) is the probability of observing z ∈ Z in state s.
Policies. An observation-based policy σ : (Z×A) * ×Z → Distr(A) for a POMDP M maps a sequence of observations and actions to a distribution over actions. A M-finite-state controller (M-FSC) consists of a finite set of memory states of size M and two functions. The action mapping η(n, z) takes a FSC memory state n and an observation z ∈ Z, and returns a distribution over the POMDP actions. The memory update δ(n, z, α) returns a distribution over memory states and is a function of the action α selected by η. An FSC induces an observation-based policy by following a joint execution of these two functions upon a trace of the POMDP. Memoryless FSCs, denoted by σ : Z → Distr(A), are observation-based policies, where σ z,α is the probability of taking the action α given solely observation z.
Remark 1 (REDUCTION TO MEMORYLESS POLICIES). In the remainder of the paper, for ease of notation, we synthesize optimal M-FSCs for POMDPs (so-called forward problem) by computing memoryless policies σ on theoreticallyjustified larger POMDPs obtained from the so-called product of the memory update δ and the original POMDPs. Indeed, Junges et al. (2018) provide product POMDPs, whose sizes grow polynomially with the size of the domain of δ.
Causal Entropy in POMDPs. For a POMDP M, a policy σ induces the stochastic processes S σ 0:∞ := (S σ 0 , . . . , S σ ∞ ), A σ 0:∞ := (A σ 0 , . . . , A σ ∞ ), and Z σ 0:∞ := (Z σ 0 , . . . , Z σ ∞ ). At each time index t, the random variables S σ t , A σ t , and Z σ t take values s t ∈ S, α t ∈ A, and z t ∈ Z, respectively. We consider the infinite time horizon setting and define the discounted causal entropy as (Zhou, Bloem, and Bambos 2017): We use general linear temporal logic (LTL) to express complex task specifications on the POMDP M. Given a set AP of atomic propositions, i.e., Boolean variables with truth values for a given state s or observation z, LTL formulae are constructed inductively as following: ϕ := true | a | ¬ϕ | ϕ 1 ∧ϕ 2 | Xϕ | ϕ 1 Uϕ 2 , where a ∈ AP, ϕ, ϕ 1 , and ϕ 2 are LTL formulae, ¬ and ∧ are the logic negation and conjunction, and X and U are the next and until temporal operators. Besides, temporal operators such as always (G) and eventually (F) are derived as Fϕ := trueUϕ and Gϕ := ¬F¬ϕ. A detailed description of the syntax and semantics of LTL is beyond the scope of this paper and can be found in Pnueli (1977); Baier and Katoen (2008). Pr σ M (ϕ) denotes the probability of satisfying the LTL formula ϕ when following the policy σ on the POMDP M.

Formal Problem Statement
In this section, we formulate the problem of task-guided inverse reinforcement learning (IRL) in POMDPs. Given a POMDP M with an unknown reward function R, we seek to learn a reward function R along with an underlying policy σ that induces a behavior similar to the expert demonstrations.
We define an expert trajectory on the POMDP M as the perceived observation and executed action sequence τ = {(z 0 , α 0 ), (z 1 , α 1 ), . . . , (z T , α T )}, where z i ∈ Z and α i ∈ A for all i ∈ {0, . . . , T }, and T denotes the length of the trajectory. Similarly to Choi and Kim (2011), we assume given or we can construct from τ (Bayesian inference), the belief trajectory b τ = {b 0 := µ 0 , . . . , b T }, where b i (s) is the probability of being at state s at time index i. In the following, we assume that we are given a set of belief trajectories D = {b τ1 , . . . , b τ N } from trajectories τ 1 , . . . , τ N , where N denotes the total number of underlying trajectories.
We build on the traditional encoding of the reward function as R(s, is a known vector of basis functions with components referred to as feature functions, θ ∈ R d is an unknown weight vector characterizing the importance of each feature, and d is the number of features.
Specifically, we seek for a weight θ defining R and a policy σ such that its discounted feature expectation R φ σ matches an empirical discounted feature expectationR φ of the expert demonstration D.
However, there may be infinitely many reward functions and policies that can satisfy this feature matching condition. Therefore, to resolve the policy ambiguity, we seek for a policy σ that also maximizes the discounted causal entropy H γ σ . We now define the problem of interest. Problem 1. Given a reward-free POMDP M, a demonstration set D, and a feature φ, compute a policy σ and weight θ such that (a) ∞ t=0 γ t E S σ Additionally, we seek to incorporate, if available, a priori high-level side information on the task demonstrated by the expert in the design of the reward R and the policy σ. Problem 2. Given a linear temporal logic formula ϕ, compute a policy σ and weight θ such that the constraints (a) and (b) in Problem 1 are satisfied, and Pr σ M (ϕ) ≥ λ for a given parameter λ ≥ 0.
We note that, even though the parameter λ that specifies the threshold for satisfaction of ϕ is assumed to be given, the approach can easily be adapted to compute the optimal λ.

Nonconvex Formulation for IRL in POMDPs
In this section, we formulate the IRL problem and the constraints induced by (a) and (b) in Problem 1 and Problem 2 as a nonconvex optimization problem. Then, we utilize a Lagrangian relaxation of the nonconvex problem as a part of our solution approach. We recall the reader (see Remark 1) that we compute M-FSC for POMDPs by computing memoryless policies σ on larger product POMDPs.
Substituting Visitation Counts. We eliminate the (infinite) time dependency in H γ σ and the feature matching constraint by a substitution of variables involving the policyinduced discounted state visitation count µ γ σ : S → R + and state-action visitation count ν γ σ : S × A → R + . For a policy σ, state s, and action α, the discounted visitation counts We first provide a concave expression for the discounted causal entropy H γ σ as a function of µ γ σ and ν γ σ : where the first equality is due to the definition of the discounted causal entropy H γ σ , the second equality obtained by expanding the expectation. The third and fourth equalities follow by the definition of the state visitation count µ γ σ , and the state-action visitation count ν γ σ . Next, we obtain a linear expression in ν γ σ for the discounted feature expectation R σ φ as: where the second equality is obtained by the definition of the visitation count ν γ σ . The following nonconvex constraint in µ γ σ (s) and σ z,α ensures observation-based policies: Algorithm 1: Compute the weight vector θ and policy σ solution of the Lagrangian relaxation of the IRL problem.
Computing a policy σ that satisfies the feature matching constraint R φ σ =R φ might be infeasible due toR φ being an empirical estimate from the finite set of demonstrations D. Additionally, the feature matching constraint might also be infeasible due to the information asymmetry between the expert and the learner, e.g., the expert has full observation.
We build on a Lagrangian relaxation to incorporate the feature matching constraints into the objective of the forward problem, similar as other IRL algorithms in the literature. Specifically, we introduce θ ∈ R d as the dual variables of the relaxed problem. The desired weight vector θ and policy σ of Problem 1 and Problem 2 are the solutions of min θ f (θ) := max σ H γ σ + θ T (R φ σ −R φ ). Algorithm 1 updates the reward weights by using gradient descent. To this end, the algorithm computes the gradient ∇f In the following, we refer to the problem of computing such σ k given θ k as the forward problem, and we develop the algorithm SCPForward, presented in next section, to solve it in an efficient and scalable manner while incorporating high-level task specifications to guide the learning.
Nonconvex Formulation of the Forward Problem. Given a weight vector θ k , we take advantage of the obtained substitution by the expected visitation counts to formulate the forward problem associated to Problem 1 as the nonconvex optimization problem: where the source of nonconvexity is from (3), and we remove the constant −(θ k ) TRφ from the cost function.

Sequential Convex Programming Formulation
We develop SCPForward, adapting a sequential convex programming (SCP) scheme to efficiently solve the nonconvex forward problem (5)- (7). SCPForward involves a verification step to compute sound policies and visitation counts, which is not present in the existing SCP schemes. Additionally, we describe in the next section how to take advantage of high-level task specification (Problem 2) through slight modifications of the obtained optimization problem solved by SCPForward.

Linearizing Nonconvex Problem
SCPForward iteratively linearizes the nonconvex constraints in (3) around a previous solution. However, the linearization may result in an infeasible or unbounded linear subproblem (Mao et al. 2018). We first add slack variables to the linearized constraints to ensure feasibility. The linearized problem may not accurately approximate the nonconvex problem if the solutions to this problem deviate significantly from the previous solution. Thus, we utilize trust region constraints (Mao et al. 2018) to ensure that the linearization is accurate to the nonconvex problem. At each iteration, we introduce a verification step to ensure that the computed policy and visitation counts are not just approximations but actually satisfy the nonconvex policy constraint (3), improves the realized cost function over past iterations, and satisfy the temporal logic specifications, if available.
Linearizing Nonconvex Constraints and Adding Slack Variables. We linearize the nonconvex constraint (3), which is quadratic in µ γ σ (s) and σ z,α , around the previously computed solution denoted byσ, µ γ σ , and ν γ σ . However, the linearized constraints may be infeasible. We alleviate this drawback by adding slack variables k s,α ∈ R for (s, α) ∈ S × A, which results in the affine constraint: Trust Region Constraints. The linearization may be inaccurate if the solution deviates significantly from the previous solution. We add following trust region constraints to alleviate this drawback: where ρ is the size of the trust region to restrict the set of allowed policies in the linearized problem. We augment the cost function in (5) with the term −β (s,α)∈S×A k s,α to ensure that we minimize the violation of the linearized constraints, where β is a large positive constant.
Linearized Problem. Finally, by differentiating x → x log x and y → x log(x/y), we obtain the coefficients required to linearize the convex causal entropy cost function in (5). Thus, we obtain the following linear program (LP):

Verification
Step. After each iteration, the linearization might be inaccurate, i.e, the resulting policyσ and potentially inaccurate visitation countsν γ σ ,μ γ σ might not be feasible to the nonconvex policy constraint (3). As a consequence of the potential infeasibility, the currently attained (linearized) optimal cost might significantly differ from the realized cost by the feasible visiation counts for theσ. Additionally, existing SCP schemes linearizes the nonconvex problem around the previously inaccurate solutions forν γ σ , andμ γ σ , further propagating the inaccuracy. The proposed verification step solves these issues. Given the computed policyσ, SCPForward computes the unique and sound solution for the visitation count µ γ σ by solving the corresponding Bellman flow constraints: for all s ∈ S, and where µ γ σ ≥ 0 is the only variable of the linear program. Then, SCPForward computes ν γ σ (s, α) = µ γ σ (s ) z∈Z O(z|s)σ z,α and the realized cost cost at the current iteration is defined by where we assume 0 log 0 = 0. Finally, if the realized cost C(σ, θ k ) does not improve over the previous cost C(σ, θ k ), the verification step rejects the obtained policyσ, contracts the trust region and SCPForward iterates with the previous solutionsσ, µ γ σ , and ν γ σ . Otherwise, the linearization is sufficiently accurate, the trust region is expanded, and SCPForward iterates withσ, µ γ σ and ν γ σ . By incorporating this verification step, we ensure that SCPForward always linearizes the nonconvex optimization problem around a solution that satisfies the nonconvex constraint (3).

Incorporating High-Level Task Specifications
Given high-level side information on the agent tasks as the LTL formula ϕ, we first compute the product of the POMDP and the ω-automaton representing ϕ to find the set T ⊆ S of states, called target or reach states, satisfying ϕ with probability 1 by using standard graph-based algorithms as a part of preprocessing step. We refer the reader to Baier and Katoen (2008) for a detailed introduction on how LTL specifications can be reduced to reachability specifications given by T .
Algorithm 2: SCPForward: Linear programming-based algorithm to solve the forward problem (5)-(7), i.e., compute a policy σ k that maximizes the causal entropy, considers the feature matching, and satisfies the specifications, if available.
Incorporating Undiscounted Visitation Variables to Linearized Problem. We append new constraints, similar to (6), (7), and (8), into the linearized problem (10), where the variables µ γ σ , ν γ σ , k s,α , µ γ σ , ν γ σ are replaced by µ sp σ , ν sp σ , k sp s,α , µ sp σ , ν sp σ , respectively. Further, we add the constraint which is a modification of the Bellman flow constraints such that µ sp σ (s) for all s ∈ T only counts transitions from nontarget states. Finally, we penalize the introduced slack variables for feasibility of the linearization by augmenting the cost function with the term −β (s,α)∈S×A k sp s,α . Relaxing Specification Constraints. We add the constraint (spec) := s∈T µ sp σ (s) + Γ sp ≥ λ to the linearized problem, where Γ sp ≥ 0 is a slack variable ensuring the linearized problem is always feasible. We augment the cost function with −β sp Γ sp to penalize violating ϕ, where β sp is a hyperparameter positive constant .

Updating Verification
Step. We modify the previouslyintroduced realized cost C(σ, θ k ) to penalize if the obtained policy does not satisfy the specification ϕ. This cost also accounts for the linearization inaccuracy of the new policy constraint due to σ, µ sp σ , and ν sp σ . At each iteration, SCPForward computes the accurate µ sp σ of current policyσ through solving a feasibility LP with constraints given by the modified Bellman flow constraints (13). Then, it augments C sp σ = min{0, ( s∈T µ sp σ (s)−λ)β sp } to the realized cost to take the specification constraints into account.

Numerical Experiments
We evaluate the proposed IRL algorithm on several POMDP instances, from Junges, Jansen, and Seshia (2020). We first compare our IRL algorithm with a straightforward variant of GAIL (Ho and Ermon 2016) adapted for POMDPs. Then, we provide some results on the data-efficiency of the approach when taking advantage of side information. Finally, we demonstrate the scalability of the routine SCPForward for solving the forward problem through comparisons with state-of-the-art solvers such as SolvePOMDP (Walraven and Spaan 2017), SARSOP (Kurniawati, Hsu, and Lee 2008), PRISM-POMDP (Norman, Parker, and Zou 2017). We consider throughout this section the hyperparameters β = 1e 3 , β sp = 10, ρ = 1.01, ρ 0 = 1.5, ρ lim = 1e −4 , and γ = 0.999. Besides, we provide in the supplementary materials additional details on the key results of this paper and the experiments, e.g., preprocessing steps such as the product POMDP with M-FSC or computing reachability specifications from LTL specifications. Benchmark Set. The POMDP instances are as follows.
Evade is a turn-based game where the agent must reach a destination without being intercepted by a faster player. In Avoid, the agent must avoid being detected by two other moving players following certain preset, yet unknown routes. In Intercept, the agent must intercept another player who is trying to exit a gridworld. In Rocks, the agents must sample at least one good rock over the several rocks without any failures. Finally, in Maze, the agent must exit a maze as fast as possible while avoiding trap states.
Variants of Learned Policies and Experts. We refer to four types of policies. The type of policy depends on whether it uses side information from a temporal specifica- tion ϕ or not, and whether it uses a memory size M = 1 or M = 10. We also consider two types of experts. The first expert has full information about the environment and computes an optimal policy in the underlying MDP. The second expert has partial observation and computes a locally optimal policy in the POMDP with a memory size of M = 15. Recall that the agent always has partial information. Therefore, the first type of expert corresponds to having information asymmetry between the learning agent and expert. Besides, we consider as a baseline a variant of GAIL where we learn the policy on the MDP without side information, and extend it to POMDPs via an offline computation of the belief in the states. Doing so provides a significant advantage to GAIL since we learn on the MDP. We do not compare with Choi and Kim (2011) as explained in the related work.
We discuss the effect of side information and memory in the policies. While we detail only on the Maze example, where the agent must exit a maze as fast as possible, we observe similar patterns for other examples. We give detailed results for the other examples in the supplementary material.

Maze Example
The POMDP M is specified by S = {s 1 , . . . , s 14 } corresponding to the cell labels in Figure 1. An agent in the maze only observes whether or not there is a wall (in blue) in a neighboring cell. That is, the set of observations is O = {o 1 , . . . , o 6 , o 7 }. For example, o 1 corresponds to observing west and north walls (s 1 ), o 2 to north and south walls (s 2 , s 4 ), and o 5 to east and west walls (s 6 , s 7 , s 8 , s 9 , s 10 , s 11 ). The observations o 6 and o 7 denote the target state (s 13 ) and bad states(s 12 , s 14 ). The transition model is stochastic with a probability of slipping p = 0.1. Further, the states s 13 and s 14 lead to the end of the simulation (trapping states).
In the IRL experiments, we consider three feature functions. We penalize taking more steps with φ time (s, α) = −1 for all s, α. We provide a positive reward when reaching s 13 with φ target (s, α) = 1 if s = s 13 and φ target (s, α) = 0 otherwise. We penalize bad states s 12 and s 14 with φ bad (s, α) = −1 if s = s 12 or s = s 14 , and φ bad (s, α) = 0 otherwise. Finally, we have the LTL formula ϕ = G ¬ bad as the task specification, where bad is an atomic proposition that is true if the current state s = s 12 or s = s 14 . We constrain the learned policy to satisfy Pr σ M (G ¬ bad) ≥ 0.9. Side Information Alleviates the Information Asymmetry. Figure 2 shows that if there is an information asymmetry between the learning agent and the expert, the policies that do not utilize side information suffer a significant performance drop. The policies that do not incorporate side information into learning obtain a lower performance by 57% under information asymmetry, as shown in the top row of Figure 2. On the other hand, as seen in the bottom row of Figure 2, the performance of the policies that use side information is almost unaffected by the information asymmetry.
Memory Leads to More Performant Policies. The results in Figure 2 demonstrate that incorporating memory into the policies improves the performance, i.e., the attained reward, in all examples, both in solving the forward problem and learning policies from expert demonstrations. Incorporating memory partially alleviates the effects of information asymmetry, as the performance of the finite-memory policy decreases by 18% under information asymmetry as opposed to 57% for the memoryless policy.
We see that in Table 2, incorporating memory into policy on the Maze and Rocks benchmarks, allows SCPForward to compute policies that are almost optimal, evidenced by  Table 1: Results for the benchmarks. On larger benchmarks (e.g., Evade and Avoid), the method we developed can compute a locally optimal policy. We set the time-out to 3600 seconds. An empty cell (denoted by −) represents the solver failed to compute any policy before the time-out, while NA refers to not applicable due to the approach being based on belief updates.
obtaining almost the same reward as the solver SARSOP.
Side Information Improves Data Efficiency and Performance. Figure 3 shows that even on a low data regime, learning with task specifications achieves significantly better performance than without the task specifications. Besides, in a more complicated environment such as Avoid, Figure 9 shows that task specifications are crucial to hope even to learn the task. We refer the reader to the supplementary material for the details of the experiment.

With side information
Without side information

SCPForward Yields Better Scalability
We highlight three observations regarding the scalability of SCPForward. First, the results in Table 2 show that only SARSOP is competitive with SCPForward on larger POMDPs. SolvePOMDP runs out of time in all but the smallest benchmarks, and PrismPOMDP runs out of memory in all benchmarks. Most of these approaches are based on updating a belief over the states, which for a large state space can become extremely computationally expensive. Second, in the benchmarks with smaller state spaces, e.g., Maze and Rock, SARSOP can compute policies that yield better performance in less time. This is due to the efficiency of belief-based approaches on small-size problems. On the other hand, SARSOP does not scale to larger POMDPs with a larger number of states and observations. For example, by increasing the number of transitions in Intercept benchmark from 5021 to 7041, the computation time for SARSOP increases by 516%. On the other hand, the increase of the computation time of SCPForward is only 28%.
Third, on the largest benchmarks, including tens of thousands of states and observations, SARSOP fails to compute any policy before time-out, while SCPForward found a solution. Finally, we also note that SCPForward can also compute a policy that maximizes the causal entropy and satisfies an LTL specification, unlike SARSOP.

Conclusion
We develop an algorithm for inverse reinforcement learning under partial observation. We empirically demonstrate that by incorporating task specifications into the learning process, we can alleviate the information asymmetry between the expert and the agent and learn policies that yield similar performance to the expert. Further, we show that our routine SCPForward to solve the forward problem outperforms state-of-the-art POMDP solvers on instances with a large number of states and observations. Work Limitations. This work assumes that the transition and observation functions of the POMDP are known to the algorithm. Future work will investigate removing this assumption and developing model-free-based approaches. We will also integrate the framework with more expressive neural-network-based reward functions.
Nonlinear Reward Parameterization. Consider the parameterization of the reward function as R(s, α) h θ (s, α), where θ ∈ R d is an unknown parameter vector and h is a nonlinear function of θ. Then, at each iteration of Algorithm 2 in line 3, the gradient step can be computed ∇h θ (θ k ) or the corresponding the subgradient in the case h θ is not differentiable. We recall that for a linear parameterization, the gradient is obtained by ∇f (θ k ) = R φ σ k −R φ . Furthermore, the reader can straightforwardly observe that SCPForward remains practically unchanged as, given θ k , we only need to replace the linear term (s,α)∈S×A (θ k ) T φ(s, α)ν γ σ (s, α) in the cost function by (s,α)∈S×A (θ k ) T h θ k (s, α)ν γ σ (s, α), which is also linear in the state-action visitation count ν γ σ . Thus, the only challenge in handling nonlinear parameterization is computing the corresponding gradient, which can be done by standard platforms such as TensorFlow and Torch. Note that nonlinear parameterization enables to learn more expressive reward functions that are typically represented by neural networks.

Experimental Tasks
In this section, we first provide a detailed description of the POMDP models used in the benchmark. The simulations on the benchmark examples empirically demonstrate that side information alleviates the information asymmetry, and more memory leads to more performant policies. Then, we provide additional numerical simulations supporting the claim that SCPForward is sound and yields better scalability than off-the-shelf solvers for the forward problem, i.e., computing an optimal policy on a POMDP for a given reward function.

Computation Resources and External Assets
All the experiments of this paper were performed on a computer with an Intel Core i9-9900 CPU 3.1GHz ×16 processors and 31.2 Gb of RAM. All the implementations are written and tested in Python 3.8, and we attach the code with the supplementary material.
Required Tools. Our implementation requires the Python interface Stormpy of Storm (Hensel et al. 2020) and Gurobipy of Gurobi 9.1 (Gurobi Optimization 2021). On one hand, we use Storm, a tool for model checking, to parse POMDP file specifications, to compute the product POMDP with the finite state controller in order to reduce the synthesis problem to the synthesis of memoryless policies, and to compute the set T of target states satisfying a specification ϕ via graph preprocessing. On the other hand, we use Gurobi to solve both the linearized problem in (7) and the feasible solution of the Bellman flow constraint needed for the verification step.
Off-The-Shelf Solvers for Forward Problem. In order to show the scalability of the developed algorithm SCPForward, we compare it to state-of-the-art POMDP solvers SolvePOMDP (Walraven and Spaan 2017), SARSOP (Kurniawati, Hsu, and Lee 2008), and PRISM-POMDP (Norman, Parker, and Zou 2017). The solver SolvePOMDP implements both exact and approximate value iterations via incremental pruning (Cassandra, Littman, and Zhang 1997) combined with state-of-the-art vector pruning methods (Walraven and Spaan 2017). Finally, PrismPOMDP discretizes the belief state and adopts a finite memory strategy to find an approximate solution of the forward problem. For all the solvers above, we use the default settings except from the timeout enforced to be 3600 seconds. These solvers are not provided with our implementation. However, we provide the POMDP models that each of the solvers can straightforwardly use. Further details are provided in the readme files of our implementation.

Benchmark Set
We evaluate the proposed learning algorithm on several POMDP instances adapted from (Junges, Jansen, and Seshia 2020). We attached the modified instances in our code with the automatically generated models for each off-the-shelf solver that the reader can straightforwardly use to reproduce Table 2. The reader can refer to Table 2 for the number of states, observations, and transitions of each environment of the benchmark set. In all the examples, we gather 10 trajectories from an expert that can fully observe its current state in the environment and an expert having partial observation of the environment. Our algorithm learns reward functions from these trajectories under different memory policies and high-level side information.
Rocks Instance. In the environment Rocks, an agent navigates in a gridworld to sample at least one valuable rock (if a valuable rock is in the grid) over the two possibly dangerous rocks, without any failures. When at least one valuable rock has been collected, or the agent realizes that all the rocks are dangerous, it needs to get to an exit point to terminate the mission. The partial observability is due to the agent can only observe if its current location is an exit point or a dangerous rock. Furthermore, the agent has noisy sensors enabling sampling neighbor cells.
We consider three feature functions. The first feature provides a positive reward when reaching the exit point with at least one valuable rock or no rocks when all of them are dangerous. The second feature provides a negative reward when the agent is at the location of a dangerous rock. Finally, the third feature penalizes each action taken with a negative reward to promote reaching the exit point as soon as possible.

No information asymmetry
Under information asymmetry We compare scenarios with no side information and the a priori knowledge on the task such as the agent eventually reaches an exit point with a probability greater than 0.995. Figure 5 supports our claim that side information indeed alleviates the information asymmetry between the expert and the agent. Additionally, we also observe that incorporating memory leads to more performant policies in terms of the mean accumulated reward.
Obstacle Instance. In the environment Obstacle[n], an agent must find an exit in a gridworld without colliding with any of the five static obstacles in the grid. The agent only observes whether the current position is an obstacle or an exit state. The parameter n specifies the dimension of the grid. Similar to the Rocks example, the agent receives a positive reward if it successfully exits the gridworld and a negative reward for every taken action or colliding with an obstacle.
As for the side information, we specify in temporal logic that while learning the reward, the agent should not collide any obstacles until it reaches an exit point with a probability greater than 0.9.

No information asymmetry
Under information asymmetry  Figure 6 supports our claim that side information alleviates the information asymmetry and memory leads to more performant policies.
Evade Instance. Evade[n, r, slip] is a turn-based game where the agent must reach a destination without being intercepted by a faster player. The player cannot access the top row of the grid. Further, the agent can only observe the player if it is within a fixed radius from its current location and upon calling the action scan. The parameters n, r, and slip specify the dimension of the grid, the view radius, and the slippery probability, respectively.
The feature functions are defined such that the agent receives a positive reward if at the destination, a high negative reward if it is intercept by the player, and a small negative reward for each action taken, including the scan action.
With side information Without side information As for the side information, we specify in temporal logic that while learning the reward, the agent must reach an exit point with probability greater than 0.98. Figure 7 shows that learning with side information provides higher reward than without side information. Besides, there is less randomness in the policy with side information compared to the policy without side information. Specifically, the standard deviation of the policy with side information is significantly smaller than the policy without side information.
We did not discuss the impact of different memory size policies in this example since the performance of the memoryless policy is already near-optimal, as the policy obtains the same reward as SARSOP (see Table 2 for a reference. Specifically, we observe that the optimal policy on the underlying MDP yields comparable policies to the optimal memoryless policy on the POMDP. As a consequence, we observe that the information asymmetry between the expert and the agent does not hold here either, and the learned policies obtain a similar performance.
Intercept Instance. Intercept[n, r, slip] is a variant of Evade where the agent must intercept another player who is trying to exit the gridworld. The agent can move in 8 directions and can only observe the player if it is within a fixed radius from the agent's current position when the action scan is performed. Besides, the agent has a camera that enables it to observe all cells from west to east from the center of the gridworld. In contrast, the player can only move in 4 directions. The parameters n, r, and slip specify the dimension of the grid, the view radius, and the slippery probability, respectively.
We consider three feature functions to parameterize the unknown reward. The first feature provides a positive reward to the agent upon intercepting the player. The second feature penalizes the agent if the player exits the gridworld. The third feature imposes a penalty cost for each action taken.
With side information Without side information We encode the high-level side information as the temporal logic task specification Eventually intercept the player with probability greater than 0.98, i.e., the agent should eventually reach an observation where its location coincides with the player's location. Figure 8 demonstrates that side information does not improve the performance of the policy. This result is because memoryless policies are optimal in this example, and a combination of the given reward features can perfectly encode the temporal logic specifications, similar to the Evade example.
Avoid Instance. Avoid[n, r, slip] is a variant of Evade, where the agent must reach an exit point while avoiding being detected by two other moving players following certain predefined yet unknown routes. The agent can only observe the players if they are within a fixed radius from the agent's current position when the action scan is performed. Besides, with the players' speed being uncertain, their position in the routes can not be inferred by the agent. The parameters n, r, and slip specify the dimension of the grid, the view radius, and the slippery probability, respectively.
We consider four feature functions to parameterize the unknown reward. The first feature provides a positive reward to the agent upon reaching the exit point. The second feature penalizes the agent if it collides with a player. The third feature penalizes the agent if it is detected by a player. The fourth feature imposes a penalty cost for each action taken.
With side information Without side information We encode the high-level side information as the temporal logic task specification avoid being detected until reaching the exit point with probability greater than 0.98. Figure 9 shows that the algorithm is unable to learn without side information while side information induces a learned policy that is optimal. Specifically, the learned policy without side information seems to only focus on avoiding being detected and collision as the corresponding learned features were close to zero. Thus, the agent using that policy does not move until sensing a player is closed by. As a consequence it gets always a negative reward from taking actions at each time step.

Summary of the Results
Side Information Alleviates the Information Asymmetry. As mentioned in the submitted manuscript, side information can indeed alleviate the information asymmetry. Specifically, we observe that if there is an information asymmetry in the forward problem, i.e., the obtained reward from an optimal policy on the underlying POMDP is lower than from an optimal policy on the underlying fully observable MDP, incorporating side information in temporal logic specifications alleviates the information asymmetry between the expert and the agent. For example, we can see the effects of such information asymmetry in the Maze, Rocks, Obstacle, and Avoid examples. In these examples, having partial observability reduces the obtained reward in the forward problem. The policies that do not incorporate side information into the learning procedure also obtain a lower reward under information asymmetry.
Memory Leads to More Performance Policies. Similarly to the side information, we also observe that if incorporating memory improves the performance of the learned policies, if it also improves the obtained reward in the forward problem, as seen in the Maze, Rocks, and Obstacle instances. In Table 2, we can also see that incorporating memory helps to compute a better optimal policy in these examples, unlike computing a memoryless policy.

SCPForward Yields Better Scalability.
We support our claim that SCPForward yields better scalability through additional simulations on the benchmark examples by varying the size of the considered examples. Specifically, we demonstrate that on large-size problems, only SARSOP attempts to solve the problems, and when it succeeds, its computation time is at least two orders of magnitude slower than SCPForward.