Year: 2021

Abstract:
A misspecified reward can degrade sample efficiency and induce undesired behaviors in reinforcement learning (RL) problems. We propose symbolic reward machines for incorporating high-level task knowledge when specifying the reward signals. Symbolic reward machines augment existing reward machine formalism by allowing transitions to carry predicates and symbolic reward outputs. This formalism lends itself well to inverse reinforcement learning, whereby the key challenge is determining appropriate assignments to the symbolic values from a few expert demonstrations. We propose a hierarchical Bayesian approach for inferring the most likely assignments such that the concretized reward machine can discriminate expert demonstrated trajectories from other trajectories with high accuracy. Experimental results show that learned reward machines can significantly improve training efficiency for complex RL tasks and generalize well across different task environment configurations.

heading: 1 INTRODUCTION
text: Reinforcement Learning (RL) agents rely on rewards to measure the utility of each interaction with the environment. As the complexity of RL tasks increases, it becomes difficult for the agent to grasp the intricacies of the task solely from goal-driven reward functions – rewarding the agent only at the end of each episode. Reward machine (RM) is a formalism proposed by Icarte et al. (2020) for representing a reward function as a finite state automaton (FSA). However, the design of RMs can quickly become cumbersome as the complexity of the tasks increases. In this paper, we draw inspiration from symbolic finite automaton (SFA) and symbolic finite transducer (SFT) Antoni & Veanes (2017) and propose symbolic reward machine (SRM) which augment FSA-based RMs by allowing the internal state transitions of the RM to carry predicates and functions on the trajectory. In addition to improving interpretability and conciseness of the reward model, a salient benefit of SRM is that it allows human engineers to express complex task scenarios and reward design patterns.
In many existing works on logically designed reward functions, the reward values are manually assigned based on heuristics which can undermine the effectiveness of the resulting reward functions. For instance, if a learning agent is excessively awarded for the completion of a certain stage of a task, the agent may tend to repeatedly complete the same stage to accumulate rewards instead of commencing the next stage, a phenomenon known as reward hacking Amodei et al. (2016). We envision that, in a typical design routine of an SRM, a human engineer constructs the SRM to incorporate high-level task information, but leave the low-level details, such as the right amount of reward for a specific event or sub-task, empty or as holes. The SRM formalism also facilitates the specification of symbolic constraints over the holes for capturing important task-specific nuances.
A major contribution of this paper is a learning framework for filling out the holes in an SRM, which we call concretization. The input to the framework includes a set of example trajectories demonstrated by a human expert, an SRM and optionally a symbolic constraint that the holes in the SRM must satisfy. We leverage the generative adversarial approaches from Finn et al. (2016); Jeon et al. (2018) to construct a discriminator with a neural network reward function to distinguish the expert
trajectories from the trajectories of an agent policy. However, our framework works in a hierarchical Bayesian manner. Basically, to circumvent the non-differentiability of SRMs, we employ a sampler to sample candidate instantiations of the holes to concretize the SRM. Then we introduce a stochastic reward signal as the latent variable dependent on the output of the concretized SRM and employ a neural-network reward function to perform importance sampling of the stochastic rewards for trajectory discrimination. We summarize our contributions below.
• We propose to use SRMs to represent reward functions for RL tasks. • We develop a hierarchical Bayesian inference framework that can concretize an SRM by
learning from expert demonstrations. • Our approach enables RL agents to achieve state-of-the-art performance on highly complex
environments with only a few demonstrations. In addition, we show that SRMs generalize well across different environment configurations of the same task.

heading: 2 RELATED WORK
text: Inverse Reinforcement Learning. We first note that the IRL formulation proposed in Ng & Russell (2000); Abbeel & Ng (2004) has an infinite number of solutions. The Max-Entropy IRL from Ziebart et al. (2008), Max-Margin IRL from Abbeel & Ng (2004); Ratliff et al. (2006) and Bayesian IRL from Ramachandran & Amir (2007) aim at resolving the ambiguity of IRL. However, those approaches restrict the reward function to be linear on the basis of human designed feature functions. Deep learning approaches proposed in Fu et al. (2018); Ho & Ermon (2016); Jeon et al. (2018); Finn et al. (2016) have substantially improved the scalablity of IRL by drawing a connection between IRL and Generative Adversarial Networks (GANs) introduced by Goodfellow et al. (2014). Our work, while embracing the data-driven and generative-adversarial ideologies, further extends IRL to cope with symbolically represented human knowledge.
Reward Design. There have been substantial efforts on enriching the information in reward functions. Reward shaping proposed by Ng et al. (1999) adds state-based potentials to the reward in each state. Exploration driven approaches such as Bellemare et al. (2016); Pathak et al. (2017); Alshiekh et al. (2017); Flet-Berliac et al. (2021) incentivize agents with intrinsic rewards. Compared with these methods, we do not seek to generate reward functions densely ranging over the entire state space but rather design intepretable ones that selectively or even sparsely produce non-zero rewards. Reward machines from Icarte et al. (2020) directly represent the reward functions as FSAs. The symbolic reward machine in our work is also automata-based but augments RMs in a similar way to SFA for FSA Veanes et al. (2012). There have been efforts on learning a so-called perfect RM as termed in Toro Icarte et al. (2019) from the experience of an RL agent in partially observable environment. However, the RM is still based on FSA and the rewards are still manually assigned. Regarding leveraging human demonstrations, inverse reward design (IRD) proposed in HadfieldMenell et al. (2017) is analogous to IRL but aims at inferring a true reward function from some proxy reward function perceived by a RL agent. Safety-aware apprenticeship learning from Zhou & Li (2018) pioneers the incorporation of formal verification in IRL. However, those works confine the reward functions to be linear of features as the generic IRL does. Our work does not have such limitations.
Interpretable Reinforcement Learning. There have been continual researches on designing interpretable policies Andre & Russell (2001; 2002); Verma et al. (2018); Zhu et al. (2019); Yang et al. (2021); Tian et al. (2020). This paper concerns the design of interpretable reward functions rather than interpretable policies. Our motivation is that a well-designed reward function is transferable and can be a powerful complement to the vast literature on RL policy learning.

heading: 3 BACKGROUND
text: An RL environment is a tupleM = 〈S,A,P, d0〉 where S is the state space; A is an action space; P(s′|s, a) is the probability of reaching a state s′ by performing an action a at a state s; d0 is an initial state distribution. A policy π(a|s) determines the probability of an RL agent performing an action a at state s. By successively performing actions for T steps after initializing from a state s(0) ∼ d0, a trajectory τ = s(0)a(0)s(1)a(1) . . . s(T )a(T ) is produced. A state-action based reward function
is a mapping f : S × A → R to the real space. With a slight abuse of notations, we denote the total reward along a trajectory τ as f(τ) = ∑T t=0 f(s
(t), a(t)) and similarly for the joint probability p(τ |π) = ∏T−1 t=0 P(s(t+1)|s(t), a(t))π(a(t)|s(t)) of generating a trajectory τ by following π. The objective of an entropy-regularized RL task is to maximize JRL(π) = Eτ∼π[f(τ)] +H(π) where τ ∼ π is an abbreviation for τ ∼ p(τ |π) andH(π) is the expected entropy of π. When the reward function is unknown but a set of expert trajectories τE is sampled with some expert policy πE , GAIL Ho & Ermon (2016) trains an agent policy πA to match πE by minimizing Jadv in Eq.2 via RL algorithms such as PPO Schulman et al. (2017). Adversarially, GAIL optimizes a discriminator D : S × A → [0, 1] to accurately identify τE’s from τA ∼ πA by maximizing Jadv . From a probabilistic inference perspective, Bayesian GAIL from Jeon et al. (2018) labels any expert trajectory τE with 1E and 0E to respectively indicate τE as being sampled from an expert demonstration set E and from some agent policy πA. Likewise, the trajectory τA of πA is labeled with 1A and 0A for the same indications. Assuming that the labels 0A, 1E are known a priori, Bayesian GAIL solves the most likely discriminator D by maximizing p(D|0A, 1E ;πA;E) ∝ p(D)p(0A, 1E |πA, D;E) ∝ ∑ τA p(τA|πA)p(0A|τA;D) ∑ τE p(τE |E)p(1E |τE ;D) of which the logarithm as in Eq.1 is lower-bounded due to Jensen’s inequality by Eq.2. It is further proposed in Fu et al. (2018) that by representing D(s, a) = exp(f(s,a))exp(f(s,a))+πA(a|s) with a neural network f , when Eq.2 is maximized, it holds that f ≡ log πE and f equals the expert reward function which πE is optimal w.r.t, given that ∀τ.p(τ |E) ≈ p(τ |πE). Hence, by representing D in Eq.1 and 2 with f , an objective of solving the most likely expert reward function f is obtained.
log ∑ τA p(τA|πA)p(0A|τA;D) ∑ τE p(τE |E)p(1E |τE ;D) (1)
≥ E τE∼E
[ log T∏ t=0 D(s (t) E , a (t) E ) ] + E τA∼πA [ log T∏ t=0 (1−D(s(t)A , a (t) A )) ] := Jadv(D) (2)

heading: 4 SYMBOLIC REWARD MACHINES (SRMS)
text: We first give a formal definition of SRM and motivate the use of SRMs with a task from a Mini-Grid environment introduced in Chevalier-Boisvert et al. (2018). We highlight that the human insights incorporated in the SRM can hardly be realized with conventional goal-driven reward mappings or function approximations. We then formulate the problem of concretizing SRMs.

heading: 4.1 DEFINITION
text: The definition of SRM is inspired from those of SFA and SFT in Veanes et al. (2012). To adapt them to the RL setting, we assume a background theory equipped with fixed interpretations on the state and actions in the RL environment as well as a language of functions. Following Pierce (2002), a λ-term is a function written in the form of λx.ρ. The type of a λx.ρ is a mapping from the type of input argument x to the type of function body ρ. The free variable set FV (ρ) of ρ is the set of symbolically denoted variables appearing in ρ while not appearing in the input of any λ-term inside ρ. Given some concrete input x̂, the evaluation of λx.ρ is written as [[λx.ρ]](x̂) or [[ρ[x̂/x]]] where [x̂/x] represents the replacement of x with x̂ in ρ. The denotation stays the same if x and x̂ are not unary. A predicate is a specific set of λ-terms mapping to Boolean type B = {>,⊥} where >,⊥ mean True and False respectively. The set of predicates is closed under Boolean operations ∧,∨,¬. Definition 1. Given an RL environmentM = 〈S,A,P, d0〉, a symbolic reward machine (SRM) is a tuple L = 〈Q,Ψ,R, δ, q0, Acc〉 where Q is a set of internal states; Ψ ⊆ (S ×A)∗ → B is a set of predicates on trajectories inM; R is a set of λ-terms of type (S ×A)∗ → R; δ is a set of transition rules (p, ψ, r, q), where p, q ∈ Q, ψ ∈ Ψ, r ∈ R; q0 ∈ Q is an initial state; Acc ⊆ Q is a set of accepting states; the free variables set of L is defined as FV (L) =
⋃ ρ∈R∪Ψ FV (ρ).
We use the notation p ψ//r−−−→ q for a rule (p, ψ, r, q) ∈ δ and call ψ its guard. The input to an SRM
is a trajectory τ ∈ (S ×A)∗. A rule p ψ//r−−−→ q is applicable at p iff [[ψ]](τ) = >, in which case L outputs a reward [[r]](τ) for the last state-action pair in τ while the state p transitions to q. If no rule is applicable, the state p does not transition and L outputs a fixed constant reward such as 0, in
which case we dub a dummy transition p
∧ (¬ψ)
∃q∈Q.(p,ψ,r,q)∈δ //0
−−−−−−−−−−−−→ p. An SRM L is called deterministic if given an input trajectory τ at any state p ∈ Q, |{(p, ψ, r, q) ∈ δ|ψ(τ) = >}| ≤ 1 in which case with a little abuse of notations we write the next state as q = δ(p, τ) either obtained from the uniquely applicable transition rule (p, ψ, r, q) ∈ δ s.t. ψ(τ) = >, or from a dummy transition such that q = p. To deploy a deterministic SRM in an RL task is to construct a synchronous product as defined below. Definition 2. A synchronous product between an M and a deterministic L is a tuple M⊗ L = 〈(S ×A)∗ × S ×Q,A,Ψ,R,P δ, d0, q0, Acc〉 where a product state in (S ×A)∗ × S ×Q is a pair (τ :: s, q) where :: means concatenation; τ :: s means concatenating a trajectory τ ∈ (S×A)∗ with anM state s ∈ S; q ∈ Q is an L state; the product transition rule P δ follows Eq.3 where τ :: s :: a is a trajectory resulted from further concatenating τ :: s with an action a ∈ A; the initial product state is (s0, q0) where s0 ∼ d0; the rest follows the definitions inM and L.
(P δ)((τ :: s, p), a, (τ :: s :: a :: s′, q)) = { P(s′|s, a) if q = δ(p, τ :: s :: a) 0 Otherwise
(3)
Proposition 1. Suppose that L is deterministic. Starting from any p(0) ∈ Q, as the input trajectory extends from τ = s(0)a(0) to τ = s(0)a(0) . . . s(T )a(T ), there can only be at most one path σ = p(0)p(1) . . . q(T+1) obtained by applying the uniquely applicable or a dummy transition successively to τ from t = 0 to t = T , i.e., ∀t = 0, 1, . . . , T.p(t+1) = δ(q(t), s(0)a(0) . . . s(t)a(t)).
Suppose that at time step t there is a transition from (τ :: s(t), p(t)) to (τ :: s(t) :: a(t) :: s(t+1), p(t+1)) with (P δ)((τ :: s(t), p(t)), a(t), (τ :: s(t) :: a(t) :: s(t+1), p(t+1))) > 0. While L witnesses such product state transition, the RL agent only observes the state transition in M. Furthermore, L returns a reward [[r(t)]](τ :: s(t) :: a(t)) at time step t, where r(t) is either 0 or the
λ-term associated with the rule p(t) ψ(t)//r(t)−−−−−−→L p(t+1). We further inductively define [[L]](τ) as [[L]](τ :: s(t) :: a(t)) = [[L]](τ) :: [[r(t)]](τ :: s(t) :: a(t)). For simplicity, we also write τ :: s :: a as τ :: (s, a) as if τ is a list of (s, a)’s, if it does not raise ambiguity in the context. We denote L(τ) = ∑T−1 t=0 [[L]](τ [: t]) where τ [: t] is the partial trajectory from initialization up until step t.
For clarification, we remark that an SRM is an SFT only under stricter conditions, in which case the SRM retains all the properties of SFT, e.g., composability and decidability. While SFT emphasizes the acceptance of inputs, SRM emphasizes more on computing the rewards for the trajectories.

heading: 4.2 MOTIVATING EXAMPLE
text: Fig.1a shows an 8×8 DoorKey task in the Mini-Grid environment. An agent needs to pick up a key, unlock the yellow door on the grey wall and reach the green goal tile. In every step, the agent can observe at most the 7× 7 tiles in front of it if the tile is not blocked by walls and doors. By default, the environment only returns a reward when the agent reaches the goal tile.
We show in Fig.1b the diagram of a SRM designed for this task. The symbols {?id}5id=1 indexed by id’s are free variables, which we dub holes, of which values are to be determined. The ellipses in Fig.1b indicate the internal states Q. The directed edges indicate the transition rules δ. Each edge carries a predicate ψ as well as a λ-term r separated by the //-sign. We omit the λ-signs and write ψ and r in plain English for explanatory purposes. Some predicates, such as Reach Goal, makes proposition on the event occurring at present time step, i.e. the last state-action pair in the input
trajectory. In some other predicates, the terms starting with a #-sign, e.g., #CLOSEDOOR, takes the present trajectory as input and outputs a N≥0 type value, counting the number of occurrence of the event as described next to the #-sign. The initial internal state q0 is the one that contains “(Start)”. The state “(End)” constitutes a singleton Acc. We omit all the dummy transitions in the diagram, i.e., if none of the depicted transitions is applicable at a state, the output reward is a fixed constant such as 0 and this state does not transition. Determining appropriate values for the ?id’s, however, can be difficult. An instance of a flawed design is to have an excessively large ?4 which can cause reward hacking. Basically, the agent can repetitively pick up and drop the key to collect a higher net reward than that of reaching the goal. On the other hand, if the returned ?5 for dropping the key is too negative, the agent may end up avoiding picking up the key entirely. To address this issue, we can add the constraint ?4+?5 ≤ 0 to the SRM. Finally, we need to find appropriate assignments to the holes so that the resulting RM is effective for the RL task.

heading: 4.3 PROBLEM FORMULATION
text: For a predicate λx.ρ, if ρ does not include trajectory τ but includes holes ?id’s in its free variable set FV (ρ), e.g., ρ := ?4+?5 ≤ 0 in the previous example, such ρ’s can be potentially used as symbolic constraints. When having a concrete value hid for a hole ?id, one can concretize L by replacing ?id with hid in L, written as L[hid/?id]. We define the problem of concretizing an SRM below. Definition 3 (Symbolic Reward Machine Concretization). The concretization problem of a symbolic reward machine is a tuple 〈L,H, c〉 where L is an SRM with holes ? = {?1, ?2, . . .} ⊆ FV (L); H = H1×H2 . . . with eachHid being the assignment space of ?id; c is a symbolic constraint subject to FV (c) ⊆ ?. An SRM L can be concretized by any h ∈ H into an l := L[h/?] iff [[c[h/?]]] = >.
Concretizing an SRM does not readily mean that the resulting reward function will be effective for the RL task. Hence, we further assume that a set E of demonstrated trajectories is provided by the expert, thus inducing a learning from demonstration (LfD) version of the SRM concretization problem 〈L,H, c, E〉. The solution h of this problem not only concretizes the SRM L but also satisfies ∀π.Eτ∼E [L[h/?](τ)] ≥ Eτ∼π[L[h/?](τ)], which inherits the definition of generic IRL in Ng & Russell (2000).

heading: 5 A HIERARCHICAL BAYESIAN LEARNING FRAMEWORK
text: In this section, we propose an approach to solve the LfD version of the SRM concretization problem. The generic IRL approach cannot be used to solve for the holes since the SRM such as the one in Fig.1b may have the holes in the transition predicates. Our approach is inspired by Bayesian GAIL as mentioned in the Background section. However, directly using L to substitute f in the discriminator D in Eq.2 is not practical due to the following challenges: a) L is not differentiable w.r.t the holes; b) L is trajectory based. In short, stochastic gradient descent with batched data is not readily applicable. Hence, we propose a hierarchical inference framework to circumvent this issue.
An overview of the graphical model of our hierarchical inference framework is shown in Fig.2a. Given a πA, we seek the most likely concretized SRM l from the log-likelihood log p(l|0A, 1E ;πA, E) = log p(0A, 1E |πA, E, l)p(l) + constant where the prior p(l) can be an uniform distribution over some allowable SRM set. The log-likelihood log p(0A, 1E |πA, E, l) is factorized as in Eq.4 by introducing two latent factors, fτA and fτE , which are two sequences of rewards for the state-action pairs along τA and τE . On one hand, each element of fτ constitutes a discriminator for the labels 0A or 1E in the same way as the reward f(s, a) does in the discriminator D of Eq.2. On the other hand, fτ is viewed as a noisy observation of [[l]](τ) in that the latent distribution p(fτ |τ ; l) is interpreted as the likelihood of observing fτ given [[l]](τ). Here, we adopt a tractable model such as Gaussian noise ∼ N (0, 1) to simulate a stochastic reward fτ = [[l]](τ) + which means adding the same to each reward in the reward sequence [[l]](τ). It is trivially provable that given any reward function f , supposed that a policy π is the optimal policy to maximize JRL(π), then this π retains optimal if f is replaced with its stochastic version f + with ∼ N (0, 1), if the trajectory lengths are considered equal. To measure the integrals in Eq.4, we re-introduce a neurally simulated reward function f for the importance sampling of the stochastic fτ ’s. We define p(fτ |τ ; f) in the same way as p(fτ |τ ; l) except for replacing fτ = [[l]](τ) + with fτ = f(τ [t]) + . With the sampled fτ ∼ p(fτ |τ ; f), we obtain a lower-bound Eq.5 where the
GAIL objective Jadv as defined in Eq.2 is embedded but with D (s, a) := exp(f(s,a)+ ) exp(f(s,a)+ )+πA(a|s) in place of D. We also abbreviate p(·|τ ; l) and p(·|τ ; f) as pl(τ) and pf (τ) in the KL-divergence DKL(pf (τ)||pl(τ)), which can be viewed as a regularization term and turns out to be proportional to the squared error ∑T−1 t=0 ([[l]](τ [: t]) − f(τ [t]))2. With Eq.5 we decouple the optimization of the GAIL objective Jadv from l such that a standard stochastic gradient descent with batched data can be conducted on the GAIL objective Jadv . We prove in the Appendix that the stochastic version E ∼N (0,1)[Jadv(D )] has the same optimal condition as that of Jadv(D) in Eq.2.
log p(0A, 1E |πA, E, l) := log ∑ τA,τE
p(τA|πA)p(τE |E)∫∫ fτAfτE p(0A|τA;πA, fτA)p(1E |τE ;πA, fτE )p(fτE |τE ; l)p(fτA |τA; l) (4)
≥ max f E ∼N (0,1)
[ Jadv(D ) ] − E τ∼πA,E [ DKL(pf (τ)||pl(τ)) ] (5)
As Eq.5 is still not differentiable w.r.t. the holes in l, we resort to finding a distribution q of l to match the likelihood p(l|0A, 1E ;πA, E). It can be realized by minimizing a KL-divergence DKL [ q(l)||p(l|0A, 1E ;πA, E) ] = E
l∼q
[ log q(l) − log p(0A,1E |πA,E,l)p(l)p(0A,1E |πA,E) ] , or by maximizing its
evidence lower-bound (ELBO) which is further lower-bounded by Eq.6. When a symbolic constraint is considered, the prior p(l) can be viewed as being uniform only among those l’s satisfying the symbolic constraint while being zero everywhere else. We let Jcon(q) := −DKL[q(l)||p(l)] be a supervised learning objective and abbreviate everything else in Eq.6 as a soft-maximization objective Jsoft(q, f).
ELBO(q) ≥ max f E ∼N (0,1)
[ Jadv(D ) ] − E l∼q
τ∼πA,E
[ DKL(pf (τ)||pl(τ)) ] −DKL [ q(l)||p(l) ] (6)
:= Jsoft(q, f) + Jcon(q)
In our implementation, we consider the case when the holes are all real numbers, i.e., ∀id.Hid = R. We construct a neurally simulated sampler qϕ to output the mean and diagonal variance matrix of a multivariate Gaussian distribution of which the dimension equals the number of holes. As each hole assignment h sampled from this Gaussian corresponds to a l := L[h/?], we still denote by qϕ(l) the distribution of l’s. Besides qϕ, we let fθ be the neurally simulated f . To calculate the gradients of Jsoft(qϕ, fθ) w.r.t ϕ and θ, we use the logarithmic trick from Peters & Schaal (2008) to handle El∼qϕ [·] ≈ 1K∇ϕi log qϕi(lk)[·] with K samples of concretized SRMs. Reparameterization trick Kingma & Welling (2013) is also used to optimize the stochastic adversarial objective E ∼N (0,1)[Jadv(D )] w.r.t fθ. As for Jcon, since we only consider the case where the symbolic constraints are all conjunctions of atomic predicates that only involve linear arithmetic, e.g., ?4+?5 ≤ 0, we make a relaxation by assigning the mean of the multivariate Gaussian produced by qϕ to the holes and then evaluating a binary cross-entropy loss of violating the symbolic constraint. As a result, Jcon is differentiable w.r.t ϕ. We use a neural network πφ to simulate the agent policy πA and train it with the most likely l∗ = arg maxl[qϕ(l)] which can also be readily obtained from the mean of the multivariate Gaussian distribution specified by qϕ. We summarize the algorithm in Algorithm 1 and illustrate the flow chart of Algorithm 1 in Fig.2b.
Algorithm 1 Hierarchical Bayesian Inference For SRM Concretization Input: Expert demonstration E, initial agent policy πφ0 , reward function fθ0 , sampler qϕ0 , iteration number i = 0, maximum iteration number N Output: πφN and qϕN
1: while iteration number i < N do 2: Sample trajectory set {τA,i}mi=1 by using policy πφi 3: Computing reward {l∗(τA,i)}mi=1 with the most likely l∗ = arg maxl qϕi(l) 4: Update φi → φi+1 using policy optimization, e.g., PPO 5: Sample K samples {lk}Ki=1 by using qϕi 6: Sample {fθi(s, a) + | ∼ N (0, 1)} respectively with (s, a) ∈ E and {τA,i}mi=1 7: Update θi+1 ← θi + α∇θiJsoft(qϕi , fθi) with a step size parameter α 8: Update ϕi+1 ← ϕi + β∇ϕiJsoft(qϕi) + βη∇ϕiJcon(qϕi) with step size parameters β, η 9: end while
10: return πφN and qϕN

heading: 6 EXPERIMENTS
text: Our benchmark includes three tasks of growing difficulty in the Mini-Grid environment: Door-Key, KeyCorridor and ObstructedMaze. The first task has been introduced earlier. The latter two are respectively shown in Fig.3b and Fig.3c in which the agent needs to pick up a targeted purple/blue ball in a locked room. In KeyCorridor, there are multiple closed doors blocking the view. In ObstructedMaze, some doors are locked; the keys for the locked doors are hidden in grey boxes; and each locked door is obstructed by a green ball. We note that despite the difficulty of these tasks, our designed SRMs do not carry out any motion planning and are solely based on reasoning the significant events. The details are explained in the Appendix. In all three tasks, the environments can vary in size by changing the number of rooms and tiles (e.g., DoorKey-8x8 vs. DoorKey-16x16). The placements of the objects and doors are randomized in each instance of an environment.

heading: 6.1 MAIN RESULTS
text: In this section, we investigate the following questions: A. Performance: whether Algorithm 1 can train an agent policy to achieve high average returns with a small number of environment interactions; B. Example Efficiency: whether Algorithm 1 can train an agent policy to achieve high performance with fewer number of demonstrated trajectories; C. Generalization: whether the SRM concretized by Algorithm 1 for one environment can be used to improve the performance of RL agents on a different environment for the same task.
There are two main categories of baselines: (1) generic IRL algorithms, including GAN-GCL from Fu et al. (2018) and GAIL from Ho & Ermon (2016); (2) generic RL algorithm, PPO Schulman et al. (2017), and exploration driven RL algorithms, including RIDE Raileanu & Rocktäschel (2020) and AGAC Flet-Berliac et al. (2021) which have performed well and even achieved stateof-the-art (SOTA) performance in some of the Mini-Grid tasks by generating intrinsic rewards. To answer question A, we implement PPO or AGAC in line 4 of Algorithm 1, and compare the results with those of the IRL baselines in which PPO is used for policy learning. We also include the results of the exploration driven RL algorithms that achieved SOTA in the benchmarks for reference. To answer question B, we vary the number of demonstrated trajectories and observe the results. To answer questions C, we directly adopt the SRMs concretized via Algorithm 1 in small environments to train RL agents in much larger environments and compare with training with the default reward.
For each task, our basic setup includes 10 demonstrated trajectories, an SRM, optionally a symbolic constraint, an actor-critic agent πφ, a neurally simulated reward function fθ and a sampler qϕ that generates a multivariate Gaussian distribution. The actor-critic networks of πφ have two versions, a non-recurrent CNN version and an LSTM version. In most tasks we only report the results from the versions with higher performance. The reward function fθ is simulated by an LSTM network. For fair comparisons, we use identical hyperparameters and the same actor-critics and neurally simulated reward functions, if applicable, when comparing our approach with PPO, GAN-GCL, GAIL and AGAC. To measure training efficiency, we show how the average return, i.e. the average default reward achieved over a series of consecutive episodes by the agent policy, changes as the number
of frames, i.e. the number of total interactions between the agent and the environment, increases. To measure demonstrated example efficiency, we show how many frames that an algorithm takes to pass a certain level of average return for different number of demonstrations.
DoorKey. We use 10 example trajectories for the DoorKey-8x8 environment shown in Fig.2a. In Fig.3d, running Algorithm 1 by using PPO and AGAC in line 4 respectively produces policies with higher performance and needing fewer frames than by training PPO or AGAC with the default reward. RIDE, GAN-GCL+PPO(CNN) and GAIL+PPO(CNN) fail with close-to-zero returns. In Fig.3g we reduce the number of examples from 10 to 1 and it does not affect the number of frames that Algorithm 1 needs to produce a policy with average return of at least 0.8, regardless of whether PPO or AGAC is used in line 4. We use the concretized SRM to train PPO and AGAC agents in a 16x16 DoorKey environment as shown in Fig.3a and achieve higher performances with significantly fewer frames than training PPO, AGAC or RIDE with the default reward as shown in Fig.3k.
KeyCorridor. We use 10 example trajectories for a 6 × 6 KeyCorridorS3R3 environment. By using PPO and AGAC in line 4 of Algorithm 1, we respectively obtain higher performance with
significantly fewer frames than by training AGAC with the default reward as shown in Fig.3e. GAIL and GAN-GCL fail again in the KeyCorridor task. Hence we omit their results in the plot. As shown in Fig.3h, reducing the number of examples (to 1) does not affect performance of Algorithm 1 for producing a policy with average return of at least 0.8. In Fig.3k, we use the concretized SRM to train RL agents in the 10× 10 KeyCorridorS4R3 and 16× 16 KeyCorridorS6R3 environments, and achieve higher performances with fewer frames than training with the default rewards. We omit the results from other baselines in this task since AGAC(CNN) is the current SOTA for this task.
ObstructedMaze. We use 10 example trajectories in a two-room ObstructedMaze-2Dhlb environment to concretize three differently designed SRMs, i.e., SRM1∼3, via Algorithm 1. We show the results for concretizing SRM1 in Fig.3f where Algorithm 1 produces policies with higher performance and needing fewer frames than AGAC trained with the default reward. When training the PPO agent, we discount PPO by episodic state visitation counts as in many exploration-driven approaches including AGAC. GAIL and GAN-GCL fail again in this task. As shown in Fig.3i, reducing the number of examples (to 1) does not affect the performance of Algorithm 1 for producing a policy with average return of at least 0.7. We also use all the concretized SRMs to train RL agents in a 9-room ObstructedMaze-Full environment. We show in Fig.3l that the RL agent trained with SRM2 attains high performance more efficiently than that with the default reward. The concretized SRM1 does not generalize as well (with performance similar to that of AGAC with default reward) as SRM2 does in this larger environment. The main difference between SRM1 and SRM2 is that SRM1 implements a hindsight reward modification functionality similar to that in Andrychowicz et al. (2017) but SRM2 does not. Since SRM1 modifies the hindsight reward to 0, it may make the reward signals too sparse for the RL agent to learn efficiently for the larger environment. We provide more details on the experimental comparison of all three SRMs in the Appendix.

heading: 6.2 ABLATION STUDY
text: In all the previous tests, the symbolic constraints include relational predicates, i.e., ones that concern the relations between holes, such as the ?4+?5 ≤ 0 mentioned in the motivating example. To investigate whether Algorithm 1 can work with weaker symbolic constraint, we run Algorithm 1 without symbolic constraint for the DoorKey-8x8 task. For the KeyCorridorS3R3 and ObstructedMaze2Dhlb tasks, we remove all the relational predicates and keep those concerning only the signs of the holes, e.g. ?id ≤ 0. As shown in Fig.4, Algorithm 1 retains its high performance albeit needing more interactions in the DoorKey environment.

heading: 7 CONCLUSION
text: We propose symbolic reward machines to represent reward functions in RL tasks. SRMs complement policy learning methods by providing a structured way to capture high-level task knowledge. In addition, we develop a hierarchical Bayesian framework to concretize SRMs by learning from expert demonstrations. Experimental comparison with SOTA baselines on challenging benchmarks validates our approach. Future works will focus on reducing human efforts in the design of SRMs.

heading: A APPENDIX
text: In this appendix, we will present additional experimental results; the design details of the SRMs and the symbolic constraints used in the experiments; a detailed experimental setup including the hyperparameters.

heading: A.1 ADDITIONAL RESULTS
text: We show some addition experimental results in this section to answer the following questions.
E. Can arbitrarily concretized SRM effectively train RL agents?
F. How much do the performance of Algorithm 1 depend on the designs of the SRMs?
For question E, we randomly generate hole assignments that satisfy the symbolic constraints for the SRMs of the DoorKey and KeyCorridor tasks. The SRMs are shown in Fig.8 and 9. The symbolic constraints contain the relational predicates as shown in Table.1 and 2. Those SRMs and symbolic constraints produce the main results in the main text. Now the assignments are generated by only optimizing the supervised objective Jcon mentioned in the main text. The concretized SRMs are used for training RL policies in the following large DoorKey and KeyCorridor environments.
• DoorKey-16x16 . In Fig.5a, we test three 3 randomly generated hole assignments for the SRM, each annotated by PPO(LSTM) rand# . The PPO(LSTM) agents trained with those SRMs achieve certain level of performance than that trained with the default reward. However, the SRM concretized with a learned hole assignment, annotated by PPO(LSTM)+SRM, enables the agent to attain much higher performance with much lower amount of frames.
• KeyCorridorS4R4 . we test 3 randomly generated hole assignments for the SRMs, each annotated by AGAC(CNN) rand#. As in Fig.5b, the agents trained with the SRMs with random assignments do not perform at all. In contrast, the agent trained with the SRM that is concretized with a learned hole assignment achieves high performance with comparable amount of frames to that trained with the default reward.
For question F, as mentioned in the main text we design three SRMs for the ObstructedMaze task. We will describe the difference between these SRMs in the next section. We run Algorithm 1 with those SRMs in the ObstructedMaze-2Dhlb environment and compare the results in Fig.6. In Fig.7b, we use those concretized SRMs to train RL agents in ObstructedMaze-Full. However, the SRM1 that achieves highest performance in Fig.7b is outperformed by two others.
Besides answering those two questions, we recall that we run Algorithm 1 in DoorKey and KeyCorridor tasks without symbolic constraint and with weaker symbolic constraint in the ablation study
of the main text. Under the same conditions, we vary the number of demonstrations and check the number of frames needed for πA to attain high performance. In Fig.7a and Fig.7b, we show that when the number of examples is reduced from 10 to 1, number of frames that Algorithm 1 needs to produce a policy with average return of at least 0.8 are not severely influenced.

heading: A.2 DESIGN DETAILS OF THE SRMS
text: In this section, we show the diagrams of the SRMs as well as the symbolic constraints designed for the tasks. We will explain the design patterns in those SRMs in detail.

heading: A.2.1 DOORKEY TASK
text: For readers convenience, we show the diagram of the SRM for DooKey in Fig.8. This SRM implicitly identifies an unlocking-door sub-task with two internal states “Before Unlocking” and “After Unlocking”. The transitions are designed mostly based on high level human insights represented in first order logic: a) (Reach Goal@t) 7→ ∃t1 < t.∃t2 < t1.(Unlock Door@t1) ∧ (Pick up Key@t2) where @t indicates that the predicate preceding it, e.g., Reach Goal, operates on the time step t of the trajectory τ ; b) ∀t ∈ [t1, t2]. (Drop Key@t1, Before Unlocking) ∧ (¬Pick up Key@t) ∧ (Pick up Key@t2) 7→ ∀t′ ∈ [t1, t2].(¬Unlock Door@t′) where we additionally integrate the internal state, i.e., “Before Unlocking”, next to @t1, to indicate the internal
state at the time step t1. The predicate #CLOSEDOOR×?3+?2 > 0 in Fig.1b is introduced with due consideration of avoiding overly penalizing the agent for closing the door, which behavior is redundant for the task. The underlying idea is: if the reward function penalized an under-trained RL agent for every door closing behavior with some high penalty ?3 < 0 for a total of #CLOSEDOOR amount of times, and the accumulated penalty #CLOSEDOOR×?3 outweighed the reward ?2 > 0 for unlocking the door, then the agent in practice might be inclined to reside away from the door for good. The SRM in Fig.1b simply upper-bounds the accumulated penalty to avoid negative effects in practice. Then we show the atomic predicates in the symbolic constraint for this task in Table.1. The final symbolic constraint is c = ∧5 i=1 µi. We omit the explanation for the symbolic constraint since the atomic predicates are self-explanatory.

heading: A.2.2 KEYCORRIDOR TASK
text: We depict in Fig.9 the diagram of the SRM designed for this task. Due to the added complexity in this task in comparison with the DoorKey task, two sub-tasks, finding-key and unlocking-door, are implicitly established by using three internal states “Before Finding Key”, “Before Unlocking” and “After Unlocking”. Some important first order logic formulas that hold in most situations in the KeyCorridor task include: a) (Pick Up Target@t1) ∧ (Unlock Door@t2) 7→ ∃t ∈ [t2, t1].(Drop Key@t);

heading: Properties (Retaional) Predicates (Non-Relational) Predicates
text: b) ∀t′ < t.(Pick Up Key@t) ∧ (¬Pick Up Key@t′) 7→ ∃t′′ < t.(Open a Door@t′′); c) (Unlock Door@t) 7→ ∃t′ < t.(Open a Door@t′′). Regarding the implication a, two predicates Pick Up Key@t and Drop Key@t are added at the internal state “After Unlocking” to govern the rewards returned for their respectively concerned behaviors after the door is unlocked. As for the implications b and c, the caveat is to determine the utility of each door opening behavior. A designer may go to one extremity by rewarding every door opening behavior with some constant, which, however, either represses exploration by penalizing opening door, or oppositely raises reward hacking, i.e., agent accumulates reward by exhaustively searching for doors to open. Alternatively, the designer may go to another extremity by carrying out a motion planning and specify the solution in the SRM, which, however, is cumbersome and cannot be generalized. In this paper, we highlight a economical design pattern to circumvent such non-determinism.
As shown in Fig.9, before the agent accomplishes the finding-key sub-task, i.e., in the “Before Finding Key” internal state, once the agent opens a door, the predicate #OPENDOOR PRE× (?8−?5)+?2 > 0? checks whether the total reward gained from opening doors is about to exceed a threshold. The counter #OPENDOOR PRE counts the number of times that agent opens doors prior to the agent finding the key; the variable ?8 is expected to be a penalty for the agent closing a door, which is redundant. By introducing ?8, we specify that even if the agent closed doors instead of opening doors for equal number #CLOSEDOOR PRE ≡ #OPENDOOR PRE of times, the agent could still gain positive net reward by finishing the finding-key subtask, i.e., #CLOSEDOOR PRE×?8+?2 ≥ #OPENDOOR PRE×?5. When the agent accomplishes the finding-key sub-task, i.e., transitioning to the “Before Unlocking” internal state, the reward ?2 −#OPENDOOR PRE REWARDED×?3 subtracts the reward hitherto gained from opening doors with #OPENDOOR PRE REWARDED ≤ #OPENDOOR PRE counting the number of times that door opening behaviors are indeed awarded prior to the agent finding the key. In some sense, this approach amortizes the reward ?2 for finishing the finding-key sub-task over the door opening behaviors. The amortized reward #OPENDOOR PRE REWARDED×?3 cannot exceed ?2 and should be deducted from ?2. The same idea is adopted to award the door opening behaviors prior to the agent unlocking the door. The counter #OPENDOOOR POST in Fig.9 counts the number of times that agent opens doors after the agent finding the key prior to the agent unlocking the door; #OPENDOOR PRE REWARDED counts the number of times that door opening behaviors are awarded within that time interval. Apparently, such design pattern is convenient enough to be implemented via symbolic means. The challenge, however, remains to properly determine values for ?id’s. Then we show the atomic predicates in the symbolic constraint for this task in Table.2. The final symbolic constraint is c = ∧9 i=1 µi.

heading: A.2.3 OBSTRUCTEDMAZE TASK
text: Fig.10 shows the diagram of the reward function designed for the ObstructedMaze task. Despite of the complexity of task, there are only three internal states, “(Start)”, “After Seeing the Target” and “(End)”. This is because only specifying the the sub-tasks is far from adequate for this task.
Once the “After Seeing the Target” state is reached, the reward function only concerns whether the agent drops or picks up a key or the target. In the “(Start)” state, the reward function views each door unlocking behavior as a milestone. If the agent does not unlock a
door at the present time step, the SRM awards the following agent behaviors: opening a box, picking up a ball, picking up a key, dropping a ball, dropping a key through a proposition ?5 + #OPENBOX× (?3−?6) + #PICKUPBALL× (?3−?7) + . . . > 0 which bounds the number of times that the those behaviors are awarded. The counters #OPENBOX,#PICKUPBALL . . . only count the number of respectively concerned behaviors between two successive door unlocking behaviors by resetting themselves to 0 once the agent unlocks a door. Thus far the design pattern is still similar to that adopted in the KeyCorridor tasks. What makes a difference here is that we assume the SRM to have access to the replay buffer of the agent policy, annotated as Replay Buffer. Suppose that in some time step t the agent unlocks a C colored door located at coordinate X, the SRM locates the last time step when the agent unlocked a door. Then it reassigns the rewards to 0 for all the opening a box, picking up a ball, picking up a key, dropping a ball, dropping a key behaviors stored in Replay Buffer ever since that last door locking time step till the present time step. Then it identifies the time steps of four milestone behaviors based on the following human insights represented in first order logic: a) (Unlock C Colored Door@t) 7→ ∃t1 < t.(Open Box@t1) ∧ (Find C Colored Key@t1 + 1), i.e., in time step t1 the agent opened the box that contains the key for this C colored door; b) (Unlock X Located Door@t) 7→ ∃t2 < t.∀t′2 > t2.(Pick Up X Located Ball@t2) ∧ (¬Pick Up X Located Ball@t′2), i.e., in time step t2 the agent picked up the ball obstructing this door at position X for the last time; c) (Unlock C Colored Door@t) 7→ ∃t3 < t.∀t′3 ∈ [t3, t].(Pick Up C Colored Key@t3) ∧ (¬Pick Up C Colored Key@t′3), i.e., in time step t3 the agent picked up the key for this C colored door for the last time; d) (Unlock Door@t) 7→ ∃t4 < t.∀t′4 ∈ [t4, t].(Drop Ball@t4) ∧ (¬Drop Ball@t′4), i.e., in time step t4 the agent dropped a ball for the last time. After identifying those milestone time steps, the SRM rewards the behaviors at the corresponding time steps. The intuition behind such design pattern is that the reward function simply encourages all those behaviors if it is unclear what outcome those behavior will lead to; once the agent unlocks a door, the reward function is able to identify the milestone behaviors that are most closely related to the door unlocking outcome. Then we show the atomic predicates in the symbolic constraint for this task in Table.3. The final symbolic constraint is c = ∧12 i=1 µi.
Note that the stored reward is not to be confused with the reward output at the present time. The syntax of sequencing in the Hindsignt code block depends on the language of the r term specified in the background theory. For the other two SRMs annotated by SRM2 and SRM3 as mentioned earlier, we remove the Hindsight block. Especially, in SRM2, we restrict that door unlocking and door opening behaviors are rewarded if only the accumulated rewards gained from those two behaviors do not exceed ?2. Otherwise, none of the behaviors correlated with the self-looping transitions at state “Before Seeing the Target” in Fig.10 will ever be rewarded. A possible reason for the policies trained by SRM1 do not generalize well in larger environment is that due to the hindsight reward modification, the reward output is too sparse in the large environment for the agent to learn. As shown by the experimental results of SRM2 and SRM3, once the Hindsight block is removed, the training performance in large environment is improved.

heading: Properties (Retaional) Predicates (Non-Relational) Predicates
text: [µ1]Reward picking up target 12∧
id=2 (?id ≤ ?1) ?1 ≥ 0
[µ2]Reward finding target ?2 ≥?4+?5 − 2?3 ?2 ≥ 0 [µ3]Reward opening door ?3 ≤ 0 ?3 ≤ 0 [µ4]Reward opening door ?4 ≥ 0 ?4 ≥ 0
[µ5]Reward unlocking door ?5 ≥ 10∑
id=6 ?id ?5 ≥ 0
[µ6]Penalize meaningless move ?3 ≤ 0 ?3 ≥ 0 [µ7]Penalize picking up used key ?11+?12 ≤ 0 ?11 ≤ 0 [µ8]Reward opening box ?6 ≥ 0 ?6 ≥ 0 [µ9]Reward picking up ball ?7 ≥ 0 ?7 ≥ 0 [µ10]Reward picking up key ?8 ≥ 0 ?8 ≥ 0 [µ11]Reward dropping ball ?9 ≥ 0 ?9 ≥ 0 [µ12]Reward dropping used key ?12 ≥ 0 ?12 ≥ 0

heading: A.3 TRAINING DETAILS
text: Parameter Value # Epochs 4 # minibatches (πφ) 8 # batch size (fθ, qϕ) 128 # frames stacked (CNN πφ) 4 # reccurence (LSTM πφ) 1 # recurrence (fθ) 8 Discount factor γ 0.99 GAE parameter λ 0.95 PPO clipping parameter 0.2 K 16 α 0.001 β 0.0003 η 1.e8 Entropy 1.e-2

heading: A.4 DERIVATION OF THE OBJECTIVE FUNCTIONS
text: First, we derive the lower-bound of log p(0A, 1E |πA, E, l) in Eq.5 as follows.
log p(0A, 1E |πA, E, l) = log ∑ τA,τE p(τA|πA)p(τE |E) ∫∫
fτA ,fτE
p(0A|τA;πA, fτA)p(1E |τE ;πA, fτE )
p(fτE |τE ; l)p(fτA |τA; l)
≥ E τA∼πA τE∼E
[ log ∫∫ fτA ,fτE p(0A|τA;πA, fτA)p(1E |τE ;πA, fτE )p(fτE |τE ; l)p(fτA |τA; l) ]
= E τA∼πA τE∼E
[ log ∫∫ fτA ,fτE p(0A|τA;πA, fτA)p(1E |τE ;πA, fτE )p(fτA |τA; l)p(fτE |τE ; l)
p(fτA |τA; f)p(fτE |τE ; f) p(fτA |τA; f)p(fτE |τE ; f) ] ≥ max
f E
τA∼πA τE∼E
[ E
fτA∼p(·|τA;f) fτE∼p(·|τE ;f))
( log p(0A|τA;πA, fτA)p(1E |τE ;πA, fτE )
p(fτA |τA; l)p(fτE |τE ; l) p(fτA |τA; f)p(fτE |τE ; f) )] = max
f E ∼N
[ Jadv(D ) ] − E τ∼πA,E [ DKL(pf(τ)||pl(τ)) ] We justify the usage of the stochastic version E ∼N (0,1)[Jadv(D )], rather than the conventional generative adversarial objective Jadv(D), by showing that one of the saddle point of min πA max f E ∼N (0,1)[Jadv(D )] is attained when f ≡ log πE ≡ log πA where we write πE in proxy of E by assuming that the distribution of state-action pairs satisfies p(s, a|πE) ≡ p(s, a|E). Theorem 1. Given a πE , min
πA max f
E ∼N (0,1) { E(s,a)∼πE [ logD (s, a)] + E(s,a)∼πA [ log(1 −
D (s, a) ]} , where D (s, a) := exp(f(s,a)+ )
exp(f(s,a)+ )+πA(a|s)) , is optimal when f ≡ log πE ≡ log πA.
Proof. Firstly, we consider optimizing f under the condition of πA ≡ πE . Inspired by the proof of optimality condition of Generative Adversarial Nets in Goodfellow et al. (2014), we introduce two variables xs,a = ys,a ∈ (0, 1] to simulate p(s, a|πA) = p(s, a|πE) for any s, a ∈ S ×A. Then we prove that E ∼N (0,1) [ xs,a log x̂s,a·exp( ) x̂s,a·exp( )+ys,a + ys,a log ys,a x̂s,a·exp( )+ys,a ] as a function of x̂s,a has x stationary point at x̂s,a = xs,a by computing its gradient w.r.t x̂s,a as follows.
∇x̂s,aE ∼N (0,1) [ xs,a log
x̂s,a · exp( ) x̂s,a · exp( ) + ys,a + ys,a log ys,a x̂s,a · exp( ) + ys,a ]
= E ∼N (0,1) [ xs,a ·
x̂s,a · exp( ) + ys,a x̂s,a · exp( ) · exp( )(x̂s,a · exp( ) + ys,a)− x̂s,a exp(2 ) (x̂s,a · exp( ) + ys,a)2 +
ys,a · x̂s,a · exp( ) + ys,a ys,a · −ys,a exp( ) (x̂s,a · exp( ) + ys,a)2 ]
= E ∼N (0,1) [xs,ays,a/x̂s,a − ys,a exp( ) x̂s,a · exp( ) + ys,a ]
(7)
When x̂s,a = xs,a = ys,a, Eq.7 equals E ∼N (0,1) [ 1−exp( )
1+exp( )
] . Note that the probabilities of sampling
and − equal each other, and 1−exp( )1+exp( ) = − 1−exp(− ) 1+exp(− ) . Hence, E ∼N (0,1) [ 1−exp( ) 1+exp( ) ] = 0. It can trivially proved that the gradient of Eq.7 w.r.t x̂ is non-positive. Therefore, f ≡ log πE is a local maximum.
Next, we consider optimizing πA under the condition of f ≡ log πE . We denote p(s, a|πE) and p(s, a|πA) for any (s, a) ∈ S ×A as xs,a, ys,a ∈ (0, 1] for short. Then we show that E ∼N (0,1) [ ∑ (s,a)∈S×A xs,a log xs,a·exp( ) xs,a·exp( )+ys,a + ys,a xs,a+ys,a log ys,a xs,a·exp( )+ys,a ] as a function of
{ys,a|(s, a) ∈ S ×A} s.t. ∑
(s,a)∈S×A ys,a = 1 has a stationary point at xs,a ≡ ys,a by computing
the gradient of the Lagrangian of this constrained function as follows.
L = E ∼N (0,1) [ ∑ (s,a)∈S×A xs,a log xs,a · exp( ) xs,a · exp( ) + ys,a + ys,a log ys,a xs,a · exp( ) + ys,a ] −
λ( ∑
(s,a)∈S×A
ys,a − 1)
∇ys,aL = E ∼N (0,1)
[ log
ys,a xs,a · exp( ) + ys,a + xs,a(exp( )− 1) xs,a · exp( ) + ys,a
] − λ = 0
⇒ ∀(s, a) ∈ S ×A. E ∼N (0,1)
[ log
ys,a xs,a · exp( ) + ys,a + xs,a(exp( )− 1) xs,a · exp( ) + ys,a
] = λ (8)
∇λL = ∑
(s,a)∈S×A
ys,a − 1 = 0 (9)
Suppose that λ = E ∼N (0,1)[log 11+exp( ) ] and xs,a = ys,a holds for any (s, a) ∈ S ×A. Then both Eq.8 and Eq.9 hold. Hence, xs,a ≡ ys,a is a stationary point. It is also trivially provable that the gradient of Eq.8 w.r.t ys,a is non-negative. Therefore, πA ≡ πE is a local minimum. In conclusion, f ≡ log πE ≡ log πA is a saddle point.
We derive the lower-bound of the ELBO in Eq.6 as follows.
ELBO(q) = DKL
[ q(l)||p(l) ] + E l∼q [ log p(0A, 1E |πA, E, l) ] = E
l∼q
{ log E
τA∼πA τE∼E [ ∫∫ fτA ,fτE p(0A|τA;πA, fτA)p(1E |τE ;πA, fτE )p(fτE |τE ; l)p(fτA |τA; l) ]} −
DKL
[ q(l)||p(l) ] ≥ max
f E ∼N
[ Jadv(D ) ] − E l∼q
τ∼πA,E
[ DKL(pf(τ)||pl(τ)) ] −DKL [ q(l)||p(l) ] = Jsoft(q, f) + Jcon(q)

Review summaries:
The paper presents a method for inverse reinforcement learning for learning the non-Markovian (trajectory-based) rewards for symbolic transitions of a pre-speciefied (up to free variables that need to be learned) automaton. For this purpose, Symbolic Reward Machines (SRM) are introduced, which define symbolic states, transitions and rewards, whereby MDP-trajectories can be unambiguously mapped to SRM-trajectories. The method uses adversarial imitation learning, where the rewards that are computed by the SRM (for a given grounding of the free variables) are used by a discriminator to classify expert- and agent-trajectories. Following the framework of Bayesian GAIL, a distribution over groundings/rewards is learned. However, whereas Bayesian GAIL learns a particle approximation to the posterior, the submission learns a variational Gaussian distribution. The method is evaluted on (rather challenging) gridworlds, where it is able to learn rewards for concepts such as "picking up a key after finding the goal". 

The paper presents a new IRL algorithm built on top of a reward machine (FSA-like) representation of a reward function.  The machine is lifted to relational predicates that may have free variables that need to be inferred.  The IRL procedure takes in a set of expert trajectories that are used to ground (or “concretize”) these variables and an RL algorithm (such as PPO) that can be used to learn policies based on reward functions.  A GAN approach is then used until the policy converges to behavior that matches the experts.  Empirical results are shown in 3 mini-grid scenarios.

The paper presents Symbolic Reward Machines (SRM) which helps in achieving interpretable and explainable reward functions. The paper also proposes a hierarchical Bayesian framework to concretize Symbolic Reward Machines using expert demonstrations. The author evaluates the proposed method on a Mini-grid environment with varying complexity and compares against state-of-the-art methods.

This paper deals with the problem of learning non-Markov task specifications (or rewards) encoded as a reward machine by inferring the real-value parameters of a reward machine (typically the edge transition rewards in an RM). The authors adopt a Bayesian deep learning approach to simultaneously learn a reward approximator, a distribution over the parameters of the reward machine, and the policy to optimize the most-likely reward instance.   The authors then go on to demonstrate in grid world environments that benefit from non-Markov rewards and policy representations that the inferred RM outperforms standard reward definition using standard RL approaches. And they further demonstrate that the inferred reward machines are beneficial  in larger instances within the same domain.