# Joint Learning of Reward Machines and Policies in Environments with
Partially Known Semantics

Christos K. Verginis, Cevahir Koprulu, Sandeep Chinchali, Ufuk Topcu

###### Abstract

We study the problem of reinforcement learning for a task encoded by a reward
machine. The task is defined over a set of properties in the environment,
called atomic propositions, and represented by Boolean variables. One
unrealistic assumption commonly used in the literature is that the truth
values of these propositions are accurately known. In real situations,
however, these truth values are uncertain since they come from sensors that
suffer from imperfections. At the same time, reward machines can be difficult
to model explicitly, especially when they encode complicated tasks. We develop
a reinforcement-learning algorithm that infers a reward machine that encodes
the underlying task while learning how to execute it, despite the
uncertainties of the propositions’ truth values. In order to address such
uncertainties, the algorithm maintains a probabilistic estimate about the
truth value of the atomic propositions; it updates this estimate according to
new sensory measurements that arrive from the exploration of the environment.
Additionally, the algorithm maintains a hypothesis reward machine, which acts
as an estimate of the reward machine that encodes the task to be learned. As
the agent explores the environment, the algorithm updates the hypothesis
reward machine according to the obtained rewards and the estimate of the
atomic propositions’ truth value. Finally, the algorithm uses a Q-learning
procedure for the states of the hypothesis reward machine to determine the
policy that accomplishes the task. We prove that the algorithm successfully
infers the reward machine and asymptotically learns a policy that accomplishes
the respective task.

##  1 Introduction

Reinforcement learning (RL) studies the problem of learning an optimal
behavior for agents with unknown dynamics in potentially unknown environments.
A variety of methods incorporate high-level knowledge that can help the agent
explore the environment more efficiently [TS07]. This high-level knowledge is
usually expressed through abstractions of the environment and sub-goal
sequences [Sin92, KNST16, AALL18] or linear temporal logic [LVB17, AJK+16].
Recently, the authors in [IKVM18] proposed the concept of reward machines in
order to provide high-level information to the agent in the form of rewards.
Reward machines are finite-state structures that encode a possibly non-
Markovian reward function. They decompose a task into several temporally
related subtasks, such as “get coffee and bring it to the office without
encountering obstacles”. Reward machines allow the composition of such
subtasks in flexible ways, including concatenations, loops, and conditional
rules, providing the agent access to high-level temporal relationships among
the subtasks. These subtasks are defined over a set of properties in the
environment, called atomic propositions, and represented by Boolean variables,
such as “office” and “obstacle” in the aforementioned example. Intuitively, as
the agent navigates in the environment, it transits between the states within
a reward machine; such transitions are triggered by the truth values of the
atomic propositions. After every such transition, the reward machine outputs
the reward the agent should obtain according to the encoded reward function.
Furthermore, [IKVM18] develops a q-learning method that learns the optimal
policy associated with the reward function that is encoded by the reward
machine.

In many practical situations, the reward machines encode complex temporal
relationships among the subtasks and are hence too difficulty to construct.
Therefore, the need emerges for the learning agent to learn how to accomplish
the underlying task without having a priori access to the respective reward
machine. The work [XGA+20] develops an algorithm that infers both the reward
machine and an optimal RL policy from the trajectories of the system.

The procedure of inferring and using a reward machine is tightly connected to
the values of the atomic propositions; such values trigger the reward
machine’s transitions, which output the reward the agent should obtain. In the
related literature, there are mainly two ways that encode the access of the
learning agent to the truth values of the atomic propositions. First, the
agent has access to a so-called labelling function, a map that provides which
atomic propositions are true in which areas of the environment, e.g., which
room of an indoor environment has an office. Second, the agent detects the
truth values of the atomic propositions from sensors as it navigates in the
environment. However, many practical scenarios involve agents operating in a
priori unknown environments, and hence accurate knowledge of a labelling
function is an unrealistic assumption. Additionally, autonomous agents are
endowed with sensors that naturally suffer from imperfections, such as
misclassifications or missed object detections. Consequently, the truth values
of the atomic propositions are uncertain. When the reward machine that encodes
the task is a priori unknown, uncertainties in such values complicate
significantly the RL problem since they interfere with the estimation of the
reward machine and, consequently, the learning of a suitable policy.

We investigate an RL problem for a task encoded by a reward machine over a set
of atomic propositions. The reward machine and the labelling function
associated with the atomic propositions are a priori unknown. The agent
obtains the truth values of the atomic propositions via measurements from
sensors, which, however, suffer from imperfections. Consequently, the truth
values of the atomic propositions are uncertain. Our main contribution lies in
the development of an RL algorithm that learns a policy that achieves the
given task despite the a priori unknown reward machine and the atomic
proposition uncertainties. In order to account for such uncertainties, the
algorithm holds a probabilistic belief over the truth values of the atomic
propositions and it updates this belief according to new sensory measurements
that arrive from the exploration of the environment. Furthermore, the
algorithm maintains a so-called hypothesis reward machine to estimate the
unknown reward machine that encodes the task. It uses the rewards the agent
obtains as it explores the environment and the aforementioned belief on the
atomic propositions to update this hypothesis reward machine. Finally, the
algorithm deploys a q-learning procedure that is based on the hypothesis
reward machine and the probabilistic belief to learn a policy that
accomplishes the underlying task. An illustrative diagram of the proposed
algorithm is depicted in Fig. 1.

We establish theoretical guarantees on the algorithm’s convergence to a policy
that accomplishes the underlying task. Our guarantees rely on the following
sufficient conditions. First, the belief updates lead to better estimation of
the truth values of the atomic propositions. That is, there exists a finite
time instant after which the probability that the estimated propositions’
values match the actual ones is more than $0.5$. Second, the learning agent
explores the environment sufficiently well in each episode of the proposed RL
algorithm. More specifically, the length of each episode is larger than a pre-
defined constant associated with the size of the operating environment and of
the reward machine that encodes the task to be accomplished. Based on the
aforementioned assumptions, we prove that the proposed algorithm 1)
asymptotically infers a reward machine that is equivalent to the one encoding
the underlying task, and 2) asymptotically learns a policy that accomplishes
this task.

Finally, we carry out experiments comparing the proposed algorithm with a
baseline version that does not update the beliefs of the propositions’ truth
values. The experiments show that the proposed algorithm outperforms the
baseline version in terms of convergence. The experiments further show the
robustness of the proposed algorithm to inaccurate sensor measurements.

Figure 1: Overview of the proposed reinforcement-learning algorithm,
consisting of perception updates, inference of the reward machine, and
q-learning.

##  2 Related Work

Previous RL works on providing higher-level structure and knowledge about the
reward function focus mostly on abstractions and hierarchical RL; in such
cases, a meta-controller decides which subtasks to perform, and a controller
decides which actions to take within a subtask (e.g., [Kon19, KNST16, AKL17]).
Other works use temporal logic languages to express a specification, and then
generate the corresponding reward functions [WET15, LVB17, SKC+14, AJK+16,
HAK18, TIKVM18, WBP21, BWZP20, HPS+19, CJT20]. Inspired by [IKVM18], we use in
this work the concept of reward machines, which encode more compactly and
expressively high-level information on the reward function of the agent.
Additionally, unlike the works in the related literature, we consider that the
reward machine that encodes the task at hand is a priori unknown.

There exists a large variety of works dealing with perception uncertainty
[GBT20, dSKL19, AMCA14, GJD13, LMF+16, LMB12, MLD17, AAB13, CCSM17, RCBP19].
However, most of these works consider the planning problem, which consists of
computing an optimal policy by explicitly employing the underlying agent
model. Furthermore, the considered uncertainty usually arises from
probabilistic dynamics, which is resolved either by active-perception
procedures, belief-state propagation, or analysis with partially observable
Markov decision processes (POMDPs). Besides, the works that consider high-
level reward structure (like temporal logic [GBT20, dSKL19, GJD13, LMB12]),
assume full availability of the respective reward models, unlike the problem
setting considered in this paper.

The recent works [ZWL15, TIWK+19, XGA+20] consider tasks encoded by a priori
unknown automata-based structures, which they infer from the agent’s
trajectories. The authors in [XGA+20], however, do not consider uncertainty in
the truth values of the atomic propositions; [ZWL15] and [TIWK+19] assume
partial environment state observability by employing POMDP models, while
considering the truth values of atomic propositions in the environment known.
In contrast, in this work we consider uncertainty in the semantic
representation of the environment, i.e., the truth value of the environment
properties that define the agent’s task is a priori unknown.

##  3 Problem Formulation

This section formulates the considered problem. We first describe the model of
the learning agent and the environment, the reward machine that encodes the
task to be accomplished, and the observation model of the sensor the agent
uses to detect the values of atomic propositions.

###  3.1 Agent Model

We model the interaction between the agent and the environment by a Markov
decision process (MDP) [Bel57, Put14], formally defined below.

######  Definition 1.

An MDP is a tuple $\mathcal{M}=(S,s_{I},A,\mathcal{T}$, $R$,
$\mathcal{AP},{L}_{G},\hat{L},\gamma)$ consisting of the following: $S$ is a
finite state space, resembling the operating environment; $s_{I}\in S$ is an
initial state; $A$ is a finite set of actions; $\mathcal{T}:S\times A\times
S\to[0,1]$ is a probabilistic transition function, modelling the agent
dynamics in the environment; $R:S^{\ast}\times A\times S\to\mathbb{R}$ is a
reward function, specifying payoffs to the agent; $\gamma\in[0,1)$ is a
discount factor; $\mathcal{AP}$ is a finite set of Boolean atomic
propositions, each one taking values in $\\{\mathsf{True},\mathsf{False}\\}$;
${L}_{G}:S\to 2^{\mathcal{AP}}$ is the ground-truth labelling function,
assigning to each state $s\in S$ the atomic propositions that are true in that
state; $\hat{L}:S\to 2^{\mathcal{AP}}$ is an estimate of the ground-truth
labelling function ${L}_{G}$. We define the size of $\mathcal{M}$, denoted as
$|\mathcal{M}|$, to be $|S|$ (i.e., the cardinality of the set $S$).

The atomic propositions $\mathcal{AP}$ are Boolean-valued properties of the
environment; we denote by $s\models p$ if an atomic proposition
$p\in\mathcal{AP}$ is true at state $s\in S$. The ground-truth labelling
function $L_{G}$ provides which atomic propositions are true in the states of
the environment, i.e., $L_{G}(s)=P\subseteq\mathcal{AP}$ is equivalent to
$s\models p$, for all $p\in P$. We consider that $L_{G}$ is unknown to the
agent, which detects the truth values of $\mathcal{AP}$ through sensor units
such as cameras or range sensors. However, such sensors suffer from
imperfections (e.g., noise). Therefore, the agent maintains a time-varying
probabilistic belief $\hat{\mathcal{L}}_{i}:S\times 2^{\mathcal{AP}}\to[0,1]$
about the truth values of $\mathcal{AP}$, where $i$ denotes a time index. More
specifically, for a state $s\in S$ and a subset of atomic propositions
$P\subseteq\mathcal{AP}$, $\hat{\mathcal{L}}_{i}(s,P)$ represents the
probability of the event that $P$ is true at $s$, i.e.,
$\hat{\mathcal{L}}_{i}(s,P)=\mathsf{Pr}(\bigcap_{p\in P}s\models p)$. Notice
that at each time index $i$ and for every state $s\in S$, it holds that
$\sum_{P\subset\mathcal{AP}}\hat{\mathcal{L}}_{i}(s,P)=1$. The prior belief of
the agent might be an uninformative prior distribution. We assume that the
truth values of the propositions are mutually independent in each state, i.e.,

$\displaystyle Pr\bigg{(}\bigcap_{p\in P}s\models P\bigg{)}=\prod_{p\in
P}Pr(s\models p),\ \ \forall s\in S,P\subset\mathcal{AP}$

and also between every pair,

$\displaystyle Pr\big{(}s\models P\land s^{\prime}\models
P^{\prime}\big{)}=Pr(s\models P)Pr(s^{\prime}\models P^{\prime}),\forall
s,s^{\prime}\in S,P,P^{\prime}\subset\mathcal{AP}$

The agent’s belief $\hat{\mathcal{L}}_{i}$, for some time index $i\geq 0$,
determines the agent’s inference of the environment configuration, and hence
the estimate $\hat{L}$ of the labelling function. More specifically, we define
$\hat{L}:(S\times 2^{\mathcal{AP}}\to[0,1])\times S\to 2^{\mathcal{AP}},$ with

$\displaystyle\hat{L}(\hat{\mathcal{L}}_{i},s)=\\{p\in\mathcal{AP}:\hat{\mathcal{L}}_{i}(s,p)\geq
0.5\\},$ (1)

i.e, the most probable outcomes. The following example illustrates the
relation between $L_{G}$ and $\hat{L}$.

######  Example 1.

Let the 10-state office workspace shown in Fig. 2. The set of atomic
propositions is $\mathcal{AP}=\\{\textup{c,o,X}\\}$, corresponding to
“coffee”, “office”, and “obstacle”, respectively. The ground-truth labelling
function, shown at the top of Fig. 2, is defined as
$L_{G}(s_{12})=\\{\textup{c}\\}$,
$L_{G}(s_{22})=L_{G}(s_{23})=\\{\textup{X}\\}$,
$L_{G}(s_{24})=\\{\textup{o}\\}$, and $\emptyset$ in the rest of the states.
Imperfect sensory measurements might lead to a distribution
$\hat{\mathcal{L}}$ and an estimate $\hat{L}(\hat{\mathcal{L}},\cdot)$ as
shown at the bottom of Fig. 2, i.e., $\hat{L}(s_{12})=\\{\textup{c,X}\\}$,
$\hat{L}(s_{22})=\\{\textup{c}\\}$,
$\hat{L}(s_{14})=\hat{L}(s_{24})=\\{\textup{o}\\}$,
$\hat{L}(s_{23})=\\{\textup{o},X\\}$, and $\emptyset$ in the rest of the
states.

Figure 2: Top: A workspace with 10 states $s_{ij}$ illustrating the ground-
truth labelling function ${L}_{G}:S\to 2^{\\{\textup{c,o,X}\\}}$, were
$\\{\textup{c,o,X}\\}$ stand for {“coffee”, “office”, “obstacle”},
respectively; Bottom: Perception uncertainty leads to the estimate
$\hat{L}(\hat{\mathcal{L}},s):S\to 2^{\\{\textup{c,o,X}\\}}$, according to
which the truth values of several properties are incorrect (e.g. X in $s_{12}$
or the absence of X in $s_{22}$).

A policy is a function that maps states in $S$ to a probability distribution
over actions in $A$. At state $s\in S$, an agent, using policy $\pi$, picks an
action $a$ with probability $\pi(s,a)$, and the new state $s^{\prime}$ is
chosen with probability $\mathcal{T}(s,a,s^{\prime})$, defined in Def. 1. A
policy $\pi$ and the initial state $s_{I}$ together determine a stochastic
process; we write $S_{0}A_{0}S_{1}$…for the random trajectory of states and
actions.

A trajectory is a realization of the agent’s stochastic process
$S_{0}A_{0}S_{1}$: a sequence of states and actions $s_{0}a_{0}s_{1}\dots
s_{k}a_{k}s_{k+1}$ with $s_{0}=s_{I}$. Its corresponding label sequence is
$\ell_{0}\ell_{1}\dots\ell_{k}$ with $\ell_{j}=L_{G}(s_{j})$, for all $j\leq
k$. Similarly, the reward sequence is $r_{0}r_{1}\dots r_{k}$, where
$r_{j}=R(s_{0}\dots s_{j}a_{j}s_{j+1})$, for all $j\leq k$. A trajectory
$s_{0}a_{0}s_{1}\dots s_{k}a_{k}s_{k+1}$ achieves a reward
$\sum_{j=0}^{k}\gamma^{j}R(s_{0}\dots s_{j}a_{j}s_{j+1})$, where $\gamma$ is
the discount factor defined in Def. 1. Note that the definition of the reward
function assumes that the reward is a function of the whole trajectory; this
allows the reward function to be non-Markovian [IKVM18]. Given a trajectory
$s_{0}a_{0}s_{1}\dots s_{k+1}$ and a belief $\hat{\mathcal{L}}_{i}$, we
naturally define then the observed label sequence by
$\hat{\ell}_{0}\hat{\ell}_{1}\dots\hat{\ell}_{k}$, with
$\hat{\ell}_{j}=\hat{L}(\hat{\mathcal{L}}_{i},s_{j})$ for all $j\leq k$ and
some $i\geq 0$.

######  Example 2 (Continued).

Let the 10-state office workspace shown in Fig. 2. Assume that the agent
receives award 1 if it brings coffee to the office without encountering states
with obstacles, and zero otherwise. Let now a state sequence
$s_{11}s_{12}s_{13}s_{14}s_{24}$ of a trajectory. According to the ground-
truth labelling function (see top of Fig. 2), such a trajectory would would
produce the label and reward sequence
$(\emptyset,0)(c,0)(\emptyset,0)(\emptyset,0)(o,1)$. However, the observed
label and reward sequence, based on the estimate $\hat{L}$ (see bottom of Fig.
2), is $(\emptyset,0)$ $((\textup{c,X}),0)$
$(\emptyset,0)(\textup{o},0)(\textup{o},1)$.

###  3.2 Reward Machines

Encoding a (non-Markovian) reward in a type of finite state-machine is
achieved by reward machines, introduced in [IKVM18] and formally defined
below.

######  Definition 2.

A reward machine is a tuple
$\mathcal{A}=(V,v_{I},2^{\mathcal{AP}},\mathcal{R},\delta,\sigma)$ that
consists of the following: $V$ is a finite set of states; $v_{I}\in V$ is an
initial state; $\mathcal{R}$ is an input alphabet; $\delta:V\times
2^{\mathcal{AP}}\to V$ is a deterministic transition function; $\sigma:V\times
2^{\mathcal{AP}}\to\mathcal{R}$ is an output function. We define the size of
$\mathcal{A}$, denoted by $|\mathcal{A}|$, to be $|V|$ (i.e., the cardinality
of the set $V$).

The run of a reward machine $\mathcal{A}$ on a sequence of labels
$\ell_{0}\dots\ell_{k}\in(2^{\mathcal{AP}})^{\ast}$ is a sequence
$v_{0}(\ell_{0},r_{0})v_{1}(\ell_{1},v_{1})$ $\dots$ $v_{k}$
$(\ell_{k},v_{k})$ of states and label-reward pairs such that $v_{0}=v_{I}$
and for all $j\in\\{0,\dots,k\\}$, we have $\delta(v_{j},\ell_{j})=v_{j+1}$
and $\sigma(v_{j},\ell_{j})=r_{j}$. We write
$\mathcal{A}(\ell_{0}\dots\ell_{k})=r_{0}\dots r_{k}$ to connect the input
label sequence to the sequence of rewards produced by the reward machine
$\mathcal{A}$. We say that a reward machine $\mathcal{A}$ encodes the reward
function $R$ of an MDP on the ground truth if, for every trajectory
$s_{0}a_{0}\dots s_{k}a_{k}s_{k+1}$ and the corresponding label sequence
$\ell_{0}\dots\ell_{k}$, the sequence of rewards equals
$\mathcal{A}(\ell_{0}\dots\ell_{k})$. Moreover, given a fixed $i\geq 0$, we
say that a reward machine $\mathcal{A}$ encodes the reward function $R$ on
$\hat{\mathcal{L}}_{i}$ if for every trajectory $s_{0}a_{0}\dots
s_{k}a_{k}s_{k+1}$ and the corresponding observed label sequence
$\hat{\ell}_{0}\dots\hat{\ell}_{k}$ the sequence of rewards equals
$\mathcal{A}(\hat{\ell}_{0}\dots\hat{\ell}_{k})$. Note, however, that there
might not exist a reward machine that encodes the reward function on
$\hat{\mathcal{L}}_{i}$, as the next example shows.

######  Example 3 (Continued).

Let the 10-state office workspace shown in Fig. 2. Assume that the agent
receives award 1 if it brings coffee to the office without encountering states
with obstacles, and zero otherwise. Such a task is encoded by the reward
machine shown in Fig. 3. Let also the state sequence
$s_{11}s_{12}s_{13}s_{14}s_{24}$ of a given trajectory. As stated before, the
trajectory produces, via the ground-truth labelling function, the label and
reward sequence $(\emptyset,0)(c,0)(\emptyset,0)(\emptyset,0)$ $(o,1)$. Such a
label sequence produces the run of the reward machine

$v_{0}(\emptyset,0)v_{0}(c,0)v_{1}(\emptyset,0)v_{1}(\emptyset,0)v_{1}(o,1)v_{3}.$

The observed label and reward sequence, based on the estimate $\hat{L}$, is
$(\emptyset,0)$ $((\textup{c,X}),0)$
$(\emptyset,0)(\textup{o},0)(\textup{o},1)$, which produces the reward-machine
run

$v_{0}(\emptyset,0)v_{0}((\textup{c,X}),0)v_{2}(\emptyset,0)v_{2}(\textup{o},0)v_{2}(\textup{o},0)v_{2},$

which clearly does not comply with the observed reward sequence. Hence, we
conclude that the reward machine does not encode the reward function on
$\hat{\mathcal{L}}$. In fact, note that we cannot construct a reward machine
that encodes the reward function on $\hat{\mathcal{L}}$. The actual reward
function of bringing coffee from $s_{12}$ to the office in $s_{24}$ cannot be
expressed via the set $\mathcal{AP}$ with this specific $\hat{\mathcal{L}}$,
because of the ambiguity in the states satisfying “o” and “c”; a single
accepting trajectory does not correspond to a unique observed label sequence.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$(\neg\textup{c}\land\neg\textup{X},0)$$(\textup{c}\land\neg\textup{X},0)$$(\textup{X},0)$$(\textup{True},0)$$(\neg\textup{o}\land\neg\textup{X},0)$$(\neg\textup{o}\land\textup{X},0)$$(\textup{o},1)$$(\textup{True},0)$
Figure 3: Reward machine for the task of Fig. 2.

###  3.3 Observation Model

The probabilistic belief is updated based on an observation model
$\mathcal{O}$. More specifically, at each time step, the agent’s perception
module processes a set of sensory measurements regarding the atomic
propositions $\mathcal{AP}$. In the Bayesian framework, the observation model
is used for the update of the agent’s belief, as specified in the following
definition.

######  Definition 3.

Let $\mathcal{Z}(s_{1},s_{2},p)\in\\{\mathsf{True},\mathsf{False}\\}$ denote
the perception output of the agent, when the agent is at state $s_{1}$, for
the atomic proposition $p\in\mathcal{AP}$ at $s_{2}$. The joint observation
model of the agent is $\mathcal{O}:S\times
S\times\mathcal{AP}\times\\{\mathsf{True},\mathsf{False}\\}\to[0,1]$, where
$\mathcal{O}(s_{1},s_{2},p,b)$ represents the probability that
$\mathcal{Z}(s_{1},s_{2},p)=\mathsf{True}$ if the truth value of $p$ is
identical to $b$.

In particular, an accurate observation model is the one for which
$\mathcal{O}(s_{1},s_{2},p,b)$ $=$ $1$ for $b=\mathsf{True}$ and
$\mathcal{O}(s_{1},s_{2},p,b)=0$ for $b=\mathsf{False}$. In the Bayesian
framework, the observation model is used for the update of the agent’s belief.
Nevertheless, in the absence of such observation model, one can perform the
update in a frequentist way.

###  3.4 Problem Statement

We consider an MDP-modeled autonomous agent, whose task is encoded by a reward
machine that is unknown to the agent. The ground-truth labelling function
$L_{G}$, providing the truth values of the atomic propositions, is also
unknown to the agent. The formal definition of the problem statement is as
follows.

######  Problem 1.

Let an MDP agent model
$\mathcal{M}=(S,s_{I},A,\mathcal{T},R,\mathcal{AP},L_{G},\hat{L},\gamma)$ with
unknown ground-truth labelling function $L_{G}$ and transition function
$\mathcal{T}$. Let also an unknown reward machine $\mathcal{A}$ that encodes
the reward function $R$ on the ground truth, representing a task to be
accomplished. Develop an algorithm that learns a policy $\pi$ that maximizes
$Z(s_{I})=\mathbb{E}_{\pi}[\sum_{i=0}^{\infty}\gamma^{i}R(S_{0},A_{0}\dots
S_{i+1})]$.

##  4 Main Results

This section gives the main results of this paper, which is a joint perception
and learning algorithm. We first give an overview of the JIRP algorithm of
[XGA+20], which handles the joint inference of reward machines and policies,
with perfect knowledge of the ground-truth labelling function $L_{G}$.

The JIRP algorithm [XGA+20] (see Algorithm 1) aims at learning the optimal
policy for maximizing $Z(s_{I})$ by maintaining hypothesis reward machines.
Its main component is the QRM$\\_$episode(), shown in Algorithm 2 and
originally proposed in [IKVM18] for accurately known reward machines.
QRM$\\_$episode() maintains a set Q of q-functions, denoted by $q^{v}$, for
each state $v$ of the reward machine. The current state $v$ of the reward
machine guides the exploration by determining which $q$-function is used to
choose the next action. In particular, the function
$\mathsf{GetEpsilonGreedyAction}(q^{v},s)$ (line 3 of Alg. 2) selects a random
action with probability $\epsilon\in(0,1)$ and an action that maximizes
$q^{v}$ with probability $1-\epsilon\in(0,1)$, balancing exploration and
exploitation. However, in each single exploration step, the $q$-functions
corresponding to all reward machine states are updated (lines 7 and 11 of Alg.
2). Note that the returned rewards in $\rho$ are observed (line 6 of Alg. 2),
since the reward machine encoding the actual reward function is not known.
Instead, JIRP operates with a hypothesis reward machine, which is updated
using the traces of QRM$\\_$episode(). In particular, the episodes of QRM are
used to collect traces and update $q$-functions. As long as the traces are
consistent with the current hypothesis reward machine, QRM explores more of
the environment using the reward machine to guide the search. However, if a
trace $(\lambda,\rho)$ is detected that is inconsistent with the hypothesis
reward machine (i.e., $\mathcal{H}(\lambda)\neq\rho$, line 6 of Alg. 1), JIRP
stores it in a set $X$ (line 7 of Alg. 1) - the trace $(\lambda,\rho)$ is
called a counterexample and the set $X$ a sample. Once the sample is updated,
the algorithm re-learns a new hypothesis reward machine (line 8 of Alg. 1) and
proceeds iteratively.

Algorithm 1 JIRP Algorithm

1:$\mathcal{H}\leftarrow\mathsf{Initialize}(V)$

2:$Q=\\{q^{v}|v\in V\\}\leftarrow\mathsf{Initialize}()$

3:$X\leftarrow\emptyset$

4:for episode $n=1,2,\dots$ do

5: $(\lambda,\rho,Q)\leftarrow\text{QRM}\\_\text{episode}(\mathcal{H},Q,L)$

6: if $\mathcal{H}(\lambda)\neq\rho$ then

7: $\mathsf{Add}(X,(\lambda,\rho))$

8: $\mathcal{H}\leftarrow\mathsf{Infer}(X)$

9: $Q\leftarrow\mathsf{Initialize}()$

10: end if

11:end for

Algorithm 2 QRM$\\_$episode($\mathcal{H}$, $Q$, $L$)

1:A reward machine
$\mathcal{H}=(V,v_{I},2^{\mathcal{P}},\mathcal{R},\delta,\sigma)$, a set of
$q$-functions $Q=\\{q^{v}|v\in V\\}$, a labelling function ${L}$.

2:$s\leftarrow\mathsf{InitialState}()$; $v\leftarrow v_{I}$,
$\lambda\leftarrow[]$; $\rho\leftarrow[]$

3:for $0\leq t<eplength$ do

4: $a\leftarrow\mathsf{GetEpsilonGreedyAction}(q^{v},s)$

5: $s^{\prime}\leftarrow\mathsf{ExecuteAction}(s,a)$

6: $v^{\prime}\leftarrow\delta(v,{L}(s^{\prime}))$

7: $r\leftarrow\mathsf{ObserveReward}()$

8: $q^{v}(s,a)\leftarrow\mathsf{Update}(r)$

9: for $\hat{v}\in V\backslash{v}$ do

10: $\hat{v}^{\prime}\leftarrow\delta(\hat{v},{L}(s^{\prime}))$

11: $\hat{r}\leftarrow\sigma(\hat{v},{L}(s^{\prime}))$

12: $q^{\hat{v}}(s,a)\leftarrow\mathsf{Update}(\hat{r})$

13: end for

14: $\mathsf{Append}(\lambda,{L}(s^{\prime}))$; $\mathsf{Append}(\rho,r)$

15: $s\leftarrow s^{\prime}$; $v\leftarrow v^{\prime}$

16:end for

17:return $(\lambda,\rho,Q)$

###  4.1 Proposed Algorithm

Algorithm 3 Joint Perception and Learning Algorithm

1:$\mathcal{H}\leftarrow\mathsf{Initialize}(V)$

2:$Q=\\{q^{v}|v\in V\\}\leftarrow\mathsf{Initialize}(V)$

3:$X\leftarrow\emptyset$

4:$j\leftarrow 0$

5:$\hat{\mathcal{L}}_{h}\leftarrow\hat{\mathcal{L}}_{0}$;

6:for episode $n=1,2,\dots$ do

7: $(\lambda,\rho,Q,\hat{\mathcal{L}}_{j})\leftarrow$
QRM_episode_mod($\mathcal{H},Q,\hat{\mathcal{L}}_{h},\hat{\mathcal{L}}_{j}$)

8: if $\mathcal{H}(\lambda)\neq\rho$ then

9: add $(\lambda,\rho)$ to $X$

10: $\mathcal{H}\leftarrow\mathsf{Infer}(X)$

11: $Q\leftarrow\mathsf{Initialize}()$

12: end if

13: if $\mathsf{SignifChange}(\hat{\mathcal{L}}_{h},\hat{\mathcal{L}}_{j})$
then

14: $\mathcal{H}\leftarrow\mathsf{Initialize}$

15: $Q\leftarrow\mathsf{Initialize}()$

16: $X\leftarrow\emptyset$

17: $\hat{\mathcal{L}}_{h}\leftarrow\hat{\mathcal{L}}_{j}$

18: end if

19:end for

Algorithm 4 QRM_episode_mod($\mathcal{H}$, $Q$,
$\hat{\mathcal{L}}_{h},\hat{\mathcal{L}}_{j}$)

1:A reward machine
$\mathcal{H}=(V,v_{I},2^{\mathcal{P}},\mathcal{R},\delta,\sigma)$, a set of
$q$-functions $Q=\\{q^{v}|v\in V\\}$, two probabilistic beliefs
$\hat{\mathcal{L}}_{h},\hat{\mathcal{L}}_{j}$.

2:$s\leftarrow\mathsf{InitialState}()$; $v\leftarrow v_{I}$,
$\lambda\leftarrow[]$; $\rho\leftarrow[]$

3:for $1\leq t<eplength$ do

4: $a\leftarrow\mathsf{GetEpsilonGreedyAction}(q^{v},s)$

5: $s^{\prime}\leftarrow\mathsf{ExecuteAction}(s,a)$

6: $v^{\prime}\leftarrow\delta(v,\hat{L}(\hat{\mathcal{L}}_{h},s^{\prime}))$

7: $r\leftarrow\mathsf{ObserveReward}()$

8: $q^{v}(s,a)\leftarrow\mathsf{Update}(r)$

9: for $\hat{v}\in V\backslash{v}$ do

10:
$\hat{v}^{\prime}\leftarrow\delta(\hat{v},\hat{L}(\hat{\mathcal{L}}_{h},s^{\prime})$

11:
$\hat{r}\leftarrow\sigma(\hat{v},\hat{L}(\hat{\mathcal{L}}_{h},s^{\prime}))$

12: $q^{\hat{v}}(s,a)\leftarrow\mathsf{Update}(\hat{r})$

13: end for

14: $j\leftarrow(n-1)\cdot eplength+t$

15:
$\hat{\mathcal{L}}_{j}\leftarrow\mathsf{BayesUpdate}(\hat{\mathcal{L}}_{j-1},s^{\prime})$

16: $\mathsf{Append}(\lambda,\hat{L}(\hat{\mathcal{L}}_{h},s^{\prime}))$;
$\mathsf{Append}(\rho,r)$

17: $s\leftarrow s^{\prime}$; $v\leftarrow v^{\prime}$

18:end for

19:return $(\lambda,\rho,Q,\hat{\mathcal{L}}_{j})$

In this paper, we extend the JIRP algorithm to account for the unknown
labelling function and the uncertainty in the truth values of the atomic
propositions. The proposed algorithms holds two probabilistic beliefs,
$\hat{\mathcal{L}}_{h}$ and $\hat{\mathcal{L}}_{j}$. It attempts to infer a
reward machine $\mathcal{A}_{h}$ that encodes the reward function on the
belief $\hat{\mathcal{L}}_{h}$, i.e.,
$\mathcal{A}_{h}(\hat{\ell}_{0},\dots,\hat{\ell}_{k})=r_{0}\dots r_{k}$, where
$\hat{\ell}_{0},\dots,\hat{\ell}_{k}$ is the label sequence generated
according to the estimate $\hat{L}(\hat{\mathcal{L}}_{h},\cdot)$. At the same
time, the algorithm updates the belief $\hat{\mathcal{L}}_{j}$ at every time
step $j$ based on the observation model defined in Def. 3. Similarly to
[GBT20], if the agent’s knowledge about the environment, encoded in
$\hat{\mathcal{L}}_{j}$, has changed significantly, the algorithm replaces
$\hat{\mathcal{L}}_{h}$ with $\hat{\mathcal{L}}_{j}$ and attempts to infer a
new reward machine that encodes the reward function on
$\hat{\mathcal{L}}_{h}$.

Algorithm 3 illustrates the aforementioned procedure. The algorithm uses a
hypothesis reward machine $\mathcal{H}$ (line 1 of Alg. 3) to guide the
learning process. Similarly to [XGA+20] and Algorithm 1, it runs multiple QRM
episodes to update the q-functions, and uses the collected traces to update
the counterexamples in the set $X$ and the hypothesis reward machine
$\mathcal{H}$ (lines 7-12 of Alg. 3). Nevertheless, in our case, $\mathcal{H}$
aims to approximate a reward machine $\mathcal{A}_{h}$ that encodes the reward
function on the most probable outcomes,
$\hat{L}(\hat{\mathcal{L}}_{h},\cdot)$, since that is the available
information to the agent; $\hat{\mathcal{L}}_{h}$ is the “current” belief that
the agent uses in its policy learning and reward-machine inference. This is
illustrated via a modified version of the QRM episode, which is called via the
command QRM_episode_mod in line 7 of Alg. 3; the modified QRM_episode_mod is
shown in Algorithm 4. In particular, QRM_episode_mod uses the probabilistic
belief $\hat{\mathcal{L}}_{h}$ in order to navigate in the hypothesis reward
machine $\mathcal{H}$ (lines 5, 9 of Alg. 4). Moreover,
$\hat{\mathcal{L}}_{h}$ is used to update the counterexample set $X$ with the
inconsistent traces (line 15 of Alg. 4 and lines 8-12 of Alg. 3). Hence, Alg.
3 aims to infer the reward machine that encodes the reward function on the
belief $\hat{\mathcal{L}}_{h}$. Of course, as illustrated in Example 1, there
might not exist a reward machine that encodes the reward function on
$\hat{\mathcal{L}}_{h}$. In that case, the algorithm cannot infer the
“correct” reward machine. For this reason, the algorithm holds a second belief
$\hat{\mathcal{L}}_{j}$, which it updates in every step of QRM_episode_mod
(line 14) in a Bayesian manner and based on the observation model of Def. 3;
such an update, encoded in the function $\mathsf{BayesUpdate}$ of Algorithm 4
is described in Section 4.2. The probabilistic belief $\hat{\mathcal{L}}_{h}$
used in the policy- and reward-machine-learning is updated with the current
belief $\hat{\mathcal{L}}_{j}$ only if the two are significantly different
(lines 13-18 of Algorithm 3). More specifically, if $\hat{\mathcal{L}}_{j}$ is
significantly changed with respect to the estimate $\hat{\mathcal{L}}_{h}$,
the algorithm replaces $\hat{\mathcal{L}}_{h}$ with $\hat{\mathcal{L}}_{j}$,
re-initializes the $Q$ functions, the hypothesis reward machine
$\mathcal{H}_{h}$, and the counterexample set $X$. The difference among
$\hat{\mathcal{L}}_{h}$ and $\hat{\mathcal{L}}_{j}$ is evaluated using a
divergence test, illustrated in Section 4.3.

###  4.2 Information Processing

Consider the agent being at state $s_{j}\in S$ at some time index $j$. The
agent receives new perception outputs according to the observation model
$\mathcal{O}(s_{j},\dots)$ for all states and atomic propositions. The agent
employs the observations to update its learned model of the environment in a
Bayesian approach. For ease of notation, let
$\hat{\mathcal{L}}_{j}=\hat{\mathcal{L}}_{j}(s,p)$ and
$\mathcal{O}(b)=\mathcal{O}(s_{j},s,p,b)$. Given the prior belief of the agent
$\hat{\mathcal{L}}_{j-1}$ and the received observations $\mathcal{Z}$, the
posterior belief $\hat{\mathcal{L}}_{j}$ follows

$\displaystyle Pr\big{(}s\models
p|\mathcal{Z}(s_{j},s,p)=\mathsf{True}\big{)}$
$\displaystyle=\frac{\hat{\mathcal{L}}_{j-1}\mathcal{O}(\mathsf{True})}{\hat{\mathcal{L}}_{j-1}\mathcal{O}(\mathsf{True})+(1-\hat{\mathcal{L}}_{j-1})(1-\mathcal{O}(\mathsf{True}))}$
(2a) $\displaystyle Pr\big{(}s\models
p|\mathcal{Z}(s_{j},s,p)=\mathsf{False}\big{)}$
$\displaystyle=\frac{\hat{\mathcal{L}}_{j-1}\mathcal{O}(\mathsf{False})}{\hat{\mathcal{L}}_{j-1}\mathcal{O}(\mathsf{False})+(1-\hat{\mathcal{L}}_{j-1})(1-\mathcal{O}(\mathsf{False}))}$
(2b)

for all $s\in S$ and $p\in\mathcal{AP}$. Depending on the truth value observed
for $p$, $\hat{\mathcal{L}}_{j}$ will be updated according to one of the
aforementioned expressions.

###  4.3 Divergence Test on the Belief

If the agent’s knowledge current estimate about the atomic propositions,
encoded in the current belief $\hat{\mathcal{L}}_{j}$, is not significantly
different from the estimate encoded in $\hat{\mathcal{L}}_{h}$, the algorithm
will continue attempting to infer a reward machine $\mathcal{A}_{h}$ that
encodes the reward function on $\hat{\mathcal{L}}_{h}$. Nevertheless, if
$\hat{\mathcal{L}}_{j}$ changes significantly with respect to
$\hat{\mathcal{L}}_{h}$, the algorithm updates the belief
$\hat{\mathcal{L}}_{h}$ and aims to infer a new reward machine (lines 13-18 of
Alg. 3). We use the Jensen-Shannon divergence to quantify the change in the
belief distribution between two consecutive time steps. The cumulative Jensen-
Shannon divergence over the states and the propositions can be expressed as

$\displaystyle D_{\mathcal{JSD}}(\hat{\mathcal{L}}_{h}$
$\displaystyle||\hat{\mathcal{L}}_{j})=\frac{1}{2}D_{\mathcal{KL}}(\hat{\mathcal{L}}_{h}||\hat{\mathcal{L}}_{m})+\frac{1}{2}D_{\mathcal{KL}}(\hat{\mathcal{L}}_{j}||\hat{\mathcal{L}}_{m})=$
$\displaystyle\frac{1}{2}\sum_{s\in
S}\sum_{p\in\mathcal{AP}}\hat{\mathcal{L}}_{h}(s,p)\log\frac{\hat{\mathcal{L}}_{h}(s,p)}{\hat{\mathcal{L}}_{m}(s,p)}+(1-\hat{\mathcal{L}}_{h}(s,p))\log\frac{1-\hat{\mathcal{L}}_{c}(s,p)}{1-\hat{\mathcal{L}}_{m}(s,p)}$
$\displaystyle+\frac{1}{2}\sum_{s\in
S}\sum_{p\in\mathcal{AP}}\hat{\mathcal{L}}_{j}(s,p)\log\frac{\hat{\mathcal{L}}_{j}(s,p)}{\hat{\mathcal{L}}_{m}(s,p)}+(1-\hat{\mathcal{L}}_{j}(s,p))\log\frac{1-\hat{\mathcal{L}}_{j}(s,p)}{1-\hat{\mathcal{L}}_{m}(s,p)}$

where
$\hat{\mathcal{L}}_{m}=\frac{1}{2}(\hat{\mathcal{L}}_{h}+\hat{\mathcal{L}}_{j})$
is the average distribution. One of the input parameters to the algorithm is a
threshold $\gamma_{d}$ on the above divergence. If $\gamma_{d}$ is not
exceeded, the algorithm uses the belief $\hat{\mathcal{L}}_{h}$ to guide the
learning and reward machine inference. Otherwise, it replaces
$\hat{\mathcal{L}}_{h}$ with $\hat{\mathcal{L}}_{j}$ and resets the procedure.

###  4.4 Inference of Reward Machines

The goal of reward-machine inference is to find a reward machine $\mathcal{H}$
that is consistent with all the counterexamples in the sample set $X$, i.e.,
such that $\mathcal{H}(\lambda)=\rho$ for all $(\lambda,\rho)\in X$, for the
current belief $\hat{\mathcal{L}}_{h}$. Unfortunately, such a task is
computationally hard in the sense that the corresponding decision problem
“given a sample X and a natural number $k>0$, does a consistent Mealy machine
with at most $k$ states exist?” is NP-complete [XGA+20, Gol78]. In this paper
we follow the approach of [XGA+20], which is learning minimal consistent
reward machines with the help of highly-optimized SAT solvers [NJ13, HV10,
Nei14]. The underlying idea is to generate a sequence of formulas
$\phi^{X}_{k}$ in propositional logic for increasing values of
$k\in\mathbb{N}$ (starting with $k=1$) that satisfy the following two
properties:

  * •

$\phi^{X}_{k}$ is satisfiable if and only if there exists a reward machine
with k states that is consistent with X;

  * •

a satisfying assignment of the variables in $\phi^{X}_{k}$ contains sufficient
information to derive such a reward machine.

By increasing $k$ by one and stopping once $\phi^{X}_{k}$ becomes satisfiable
(or by using a binary search), an algorithm that learns a minimal reward
machine that is consistent with the given sample is obtained.

As stressed in Example 1, however, a reward machine that encodes $R$ on
$\hat{\mathcal{L}}_{h}$ might not exist and the inference procedure might end
up creating an arbitrarily large Mealy machine and yielding very high
computation times (trying to compute a Mealy machine that does not exist). To
prevent such cases, one can limit the maximum allowable number of states of
the Mealy machine and the maximum number of episodes used to generate the
counterexamples, and use the last valid inferred Mealy machine (or the initial
estimate if there is no valid one). In the experimental results, such cases
did not prevent the successful convergence of the proposed algorithm.

###  4.5 Convergence in the limit

In this section, we establish the correctness of Algorithm 3. We provide
theoretical guarantees on its convergence based on two sufficient conditions.
First, the estimate $\hat{L}(\hat{\mathcal{L}}_{h},\cdot)$ becomes identical
with the ground-truth labelling function $L_{G}$ after a finite number of
episodes. Second, the length of each episode is larger than
$2^{|\mathcal{M}|+1}(|\mathcal{A}|+1)-1$, where $\mathcal{A}$ is the unknown
reward machine that encodes the task to be accomplished. The first condition
is tightly connected to the observation model $\mathcal{O}$ of the agent (see
Def. 3) and its effect on the updates (2). It can be verified that, when there
is no uncertainty in the observation model, i.e., it is sufficiently accurate
or inaccurate (the values $\mathcal{O}(s_{1},s_{2},p,b)$ are close to one and
zero depending on the value of $b$), the updates (2) lead to a
$\hat{L}(\hat{\mathcal{L}},\cdot)$ that converges to $L_{G}(\cdot)$.
Intuitively, if the agent is aware that its observation model is either
accurate or inaccurate, it adjusts its updates accordingly and based on the
respective perception outputs. Consider, for instance, an atomic proposition
$p\in\mathcal{AP}$ satisfying $s\models p$ for some state $s\in S$. Let also
an observation model satisfying $\mathcal{O}(s,s,p,\mathsf{True})=0.1$ and
$\mathcal{O}(s,s,p,\mathsf{False})=1-\mathcal{O}(s,s,p,\mathsf{True})=0.9$,
implying that the agent “knows” that the model is quite inaccurate. Then, a
sensor output $\mathcal{Z}(s,s,p)=\mathsf{False}$ will result in the update
$\hat{\mathcal{L}}_{j}=Pr(s\models
p|\mathcal{Z}(s,s,p)=\mathsf{False})=\frac{0.9\hat{\mathcal{L}}_{j-1}}{0.9\hat{\mathcal{L}}_{j-1}+0.1(1-\hat{\mathcal{L}}_{j-1})}>\hat{\mathcal{L}}_{j-1}$,
according to (2), giving hence a better estimate regarding the truth value of
$p$ at $s$. On the contrary, if
$\mathcal{O}(s,s,p,\mathsf{True})=\mathcal{O}(s,s,p,\mathsf{False})=0.5$, then
the agent has no a priori information regarding the accuracy of the
observation model, and the beliefs are not updated. Nevertheless, the
conditions stated above are only sufficient for the convergence guarantees.
The experiments of the next section illustrate that the proposed algorithm
learns how to accomplish the underlying task even with random observation
models.

Before proceeding with the convergence result, we introduce some necessary
concepts, starting with the attainable trajectory:

######  Definition 4.

Let $\mathcal{M}=(S,s_{I},A,\mathcal{T},R,\mathcal{AP},\hat{L},\gamma)$ be an
MDP and $m\in\mathbb{N}$ a natural number. We call a trajectory
$\zeta=s_{0}a_{0}s_{1}\dots s_{k}a_{k}s_{k+1}\in(S\times A)^{\ast}\times S$
$m$-attainable if (i) $k\leq m$ and (ii) $\mathcal{T}(s_{i},a_{i},s_{i+1})>0$
for each $i\in\\{0,\dots,k\\}$. Moreover, we say that a trajectory $\zeta$ is
attainable if there exists an $m\in\mathbb{N}$ such that $\zeta$ is
$m$-attainable.

Since the function $\mathsf{GetEpsilonGreedyAction}()$ (line 3 of Algorithm 4)
follows an $\epsilon$-greedy policy, we can show that the proposed algorithm
almost surely explores every attainable trajectory in the limit, i.e., with
probability 1 as the number of episodes goes to infinity.

######  Lemma 1.

Let $m\in\mathbb{N}$ be a natural number. Then, Algorithm 3, with
$eplength\geq m$, almost surely explores every $m$-attainable trajectory at
least once in the limit.

###### Proof.

The proof is identical the the one in [XGA+20, Lemma 1] and is omitted. ∎

Similar to Def. 4, we call an observed label sequence
$\hat{\lambda}=\hat{\ell}_{0},\dots,\hat{\ell}_{k}$ ($m$-)attainable on
$\hat{\mathcal{L}}_{h}$ if there exists an ($m$-)attainable trajectory
$s_{0}a_{0}s_{1}\dots s_{k}a_{k}s_{k+1}$ such that
$\hat{\ell}_{j}=\hat{L}(\hat{\mathcal{L}}_{h},s)$ for each
$j\in\\{0,\dots,k\\}$.

Consider now Algorithm 3 and assume that the condition of
$\mathsf{SignifChange}(\hat{\mathcal{L}}_{h},\hat{\mathcal{L}}_{j})$ (line 13)
is not satisfied after a certain number of episodes, i.e.,
$\hat{\mathcal{L}}_{h}$ remains fixed. Then, Lemma 1 implies that Algorithm 3
almost surely explores every $m$-attainable label sequences on
$\hat{\mathcal{L}}_{h}$ in the limit, formalized in the following corollary.

######  Corollary 1.

Assume that there exists a $n_{r}>0$ such that
$\mathsf{SignifChange}(\hat{\mathcal{L}}_{h},\hat{\mathcal{L}}_{j})=\mathsf{False}$
(line 13 of Algorithm 3), for all episodes $n>n_{r}$. Then Algorithm 3, with
$eplength\geq m$, explores almost surely every $m$-attainable label sequence
on $\hat{\mathcal{L}}_{h}$ in the limit.

Therefore, if Algorithm 3 explores sufficiently many $m$-attainable label
sequences on some distribution $\hat{\mathcal{L}}_{h}$ and for a large enough
value of $m$, it is guaranteed to infer a reward machine that is “good enough”
in the sense that it is equivalent to the reward machine encoding the reward
function $R$ on $\hat{\mathcal{L}}_{h}$ and on all attainable label sequences
on $\hat{\mathcal{L}}_{h}$, assuming that such a reward machine exists (see
Example 1). This is formalized in the next lemma.

######  Lemma 2.

Let $\mathcal{M}=(S,s_{I},A,\mathcal{T},R,\mathcal{AP},\hat{L},\gamma)$ be an
MDP and assume that there exists a reward machine $\mathcal{A}_{h}$ that
encodes the reward function $R$ on $\hat{L}(\hat{\mathcal{L}}_{h},\cdot)$ for
some belief $\hat{\mathcal{L}}_{h}$. Assume that there exists a $n_{r}>0$ such
that $\mathsf{SignifChange}(\hat{\mathcal{L}}_{h},\hat{\mathcal{L}}_{j})$ $=$
$\mathsf{False}$ (line 13 of Alg. 3), for all episodes $n>n_{r}$. Then,
Algorithm 3, with $\mathsf{eplength}\geq
2^{|\mathcal{M}|+1}(|\mathcal{A}_{h}|+1)-1$, almost surely learns a reward
machine in the limit that is equivalent to $\mathcal{A}_{h}$ on all attainable
label sequences on $\hat{\mathcal{L}}_{h}$.

###### Proof.

The proof is identical to the one in [XGA+20, Lemma 2] and is omitted. ∎

Following Lemma 2, Algorithm 3 will eventually learn the reward machine
encoding the reward function on $\hat{\mathcal{L}}_{h}$, when
$\hat{\mathcal{L}}_{h}$ is fixed. Intuitively, Lemma 2 suggests that,
eventually, the algorithm is able to learn a reward machine that encodes the
reward function on a fixed estimate $\hat{L}(\hat{\mathcal{L}}_{h},\cdot)$,
i.e., without the updates from the new observations. Nevertheless, the
potential perception updates (line 14 of Algorithm 4) might prevent the
algorithm to learn a reward machine, since $\hat{\mathcal{L}}_{h}$ might be
changing after a finite number of episodes. However, if the observation model
is accurate (or inaccurate) enough and the agent explores sufficiently many
label sequences, intuition suggests that $\hat{\mathcal{L}}_{j}$ will be
constantly improving, leading to less frequent updates with respect to the
divergence test (line 13 of Algorithm 3). Therefore, there exists a finite
number of episodes, after which $\hat{\mathcal{L}}_{h}$ will be fixed to some
belief $\hat{\mathcal{L}}_{f}$ and $\hat{L}(\hat{\mathcal{L}}_{f},\cdot)$ will
be “close” to the ground-truth function $L_{G}$. By applying then Lemma 2, we
conclude that Algorithm 3 will learn the reward machine that encodes the
reward function on $\hat{\mathcal{L}}_{f}$, and consequently converge to the
$q$-function that defines an optimal policy. This is formalized in the next
theorem.

######  Theorem 1.

Let $\mathcal{M}=(S,s_{I},A,\mathcal{T},R,\mathcal{AP},\hat{L},\gamma)$ be an
MDP and $\mathcal{A}$ be a reward machine that encodes the reward function $R$
on the ground truth. Further, assume that there exists a constant $n_{f}>0$
such that $\hat{L}(\hat{\mathcal{L}}_{h},\cdot)=L_{G}(\cdot)$, for all
episodes $n>n_{f}$ of Algorithm 3111Note that this implies that
$\\{p\in\mathcal{AP}:\hat{L}_{h}(s,p)\geq 0.5\\}=L_{G}(s)$ for all $s\in S$..
Then, Algorithm 3, with $eplength\geq 2^{|\mathcal{M}|+1}(|\mathcal{A}|+1)-1$,
converges almost surely to an optimal policy in the limit.

###### Proof.

Note first that the $\epsilon$-greedy action policy, imposed by the function
$\mathsf{GetEpsilonGreedyAction}()$, and $eplength\geq|\mathcal{M}|$ imply
that every action-pair of $\mathcal{M}$ will be visited infinitely often.
Moreover, $\mathsf{SignifChange}(\hat{\mathcal{L}}_{h},\hat{\mathcal{L}}_{j})$
will be always false for all episodes $n>n_{f}$, since $\hat{\mathcal{L}}_{h}$
will be an accurate enough estimate. By definition, the reward machine
$\mathcal{A}$ that encodes the reward function on the ground truth encodes the
reward function on $\hat{\mathcal{L}}_{h}$ as well. Therefore, Lemma 2
guarantees that Algorithm 3 eventually learns a reward machine $\mathcal{H}$
that is equivalent to $\mathcal{A}$ on all attainable label sequences.

According to Observation 1 of [IKVM18], given the MDP
$\mathcal{M}=(S,s_{I},A,\mathcal{T},R,\mathcal{AP},\hat{L},\gamma)$ and the
reward machine
$\mathcal{A}=(V,v_{I},2^{\mathcal{AP}},\mathcal{R},\delta,\sigma)$, one can
construct an MDP $\mathcal{M}_{\mathcal{H}}=(S\times
V,(s_{I},v_{I}),A,\mathcal{T}^{\prime},R^{\prime},\mathcal{AP},\hat{L},\gamma)$
with

$\displaystyle\mathcal{T}^{\prime}((s,v),a,(s^{\prime},v^{\prime}))=\left\\{\begin{matrix}\mathcal{T}(s,a,s^{\prime}),&\text{if
}v^{\prime}=\delta(v,L(s^{\prime}))\\\ 0&\text{otherwise}\end{matrix}\right.$
$\displaystyle
R^{\prime}((s,v),a,(s^{\prime},v^{\prime}))=\sigma(v,L(s^{\prime}))$

and a Markovian reward function such that every attainable label sequence of
$\mathcal{M}_{\mathcal{H}}$ receives the same reward as in $\mathcal{M}$.
Thus, an optimal policy for $\mathcal{M}_{\mathcal{H}}$ will be also optimal
for $\mathcal{M}$. Due to the $\epsilon$-greedy action policy, the episode
length being $eplength\geq|\mathcal{M}|$, and the fact that the updates are
done in parallel for all states of the reward machine $\mathcal{H}$, every
state-action pair of the MDP $\mathcal{M}_{H}$ will be visited infinitely
often. Therefore, convergence of q-learning for $\mathcal{M}_{\mathcal{H}}$ is
guaranteed [WD92]. Finally, since an optimal policy for
$\mathcal{M}_{\mathcal{H}}$ is optimal for $\mathcal{M}$, Algorithm 3
converges to an optimal policy too.

∎

##  5 Experimental Results

We test the proposed algorithm in floor plan environments based on the indoor
layouts collected in the HouseExpo dataset [TDC+19]. HouseExpo consists of
indoor layouts, built from 35,126 houses with a total of 252,550 rooms. There
are 25 room categories, such as bedroom, garage, office, boiler room, etc. The
dataset provides bounding boxes for the rooms with their corresponding
categories, along with 2D images of layouts. We pre-process these layouts to
generate grid-world-like floor plans, where every grid is labeled with the
type of the room it is in (see Fig. 4). We use these labels as atomic
propositions to define tasks encoded as reward machines. In particular, we use
the set of atomic propositions
$\mathcal{AP}=\\{\tt{kitchen},\tt{bathroom},\tt{bedroom},\tt{office},\tt{indoor}\\}$.

In the experiments, an episode terminates when the agents receives a non-zero
reward or the maximum number of steps allowed in one episode is exceeded. This
maximum number of steps per episode is 1000, whereas the maximum number of
total training steps is 500,000. Furthermore, we set the Jensen-Shannon
divergence threshold $\gamma_{d}$ of Section 4.3 to $10^{-5}$, and Algorithm 4
selects a random action with probability $\epsilon=0.3$. Our implementation
utilizes the RC2 SAT solver [MDMS14] from the PySAT library [IMM18]. All
experiments were conducted on a Lenovo laptop with 2.70-GHz Intel i7 CPU and
8-GB RAM.

We compare the following experimental settings regarding the observation model
and the belief updates:

  1. 1.

Time-varying Bayesian Observation Model (TvBNN): We use a number of training
HouseExpo layouts to train a Bayesian neural network, which the algorithm uses
as an observation model in test layouts for the experiments. The algorithm
samples observation probabilities of the atomic propositions’ truth value from
the neural network at the beginning of every training episode.

  2. 2.

Fixed Bayesian Observation Model (FiBNN): We use a number of training
HouseExpo layouts to train a Bayesian neural network, which the algorithm uses
as an observation model in test layouts for the experiments. The algorithm
samples observation probabilities of the atomic propositions’ truth value from
the neural network only once, at the beginning of training.

  3. 3.

Random Observation Model: The algorithm uses an observation model whose
observation probabilities are uniformly sampled from the interval [0.1,0.9].

  4. 4.

Random Observation Mode-2: The algorithm uses an observation model whose
observation probabilities are uniformly sampled from the interval [0.4,0.5].

  5. 5.

No Belief Updates: The algorithm uses a belief function that is randomly
initialized, without updating it.

The Bayesian observation model in the first two settings is a neural network
of three densely connected layers with flipout estimators [WVB+18]. The loss
function is the expected lower-bound loss, and a combination of Kullback-
Leibler divergence and categorical cross entropy. Given the information about
a grid in a floor plan, the Bayesian neural network (BNN) predicts category
probabilities of the room where the grid is located. The input vector consists
of the 2D coordinates of the grid, the size and the number of neighbours of
the room. The output is the predicted probabilities of the room type. The
training set consists of 3,000 pre-processed layouts from the HouseExpo
dataset, which we select based on the floor plan size and the number of
different room categories. After pre-processing, to eliminate variance with
respect to the initial position of grids, we rotate every training layout 3
times by 90 degrees, and then add each rotated version to the training set.

For the reward-machine-inference part of the algorithm, we limit the maximum
allowable number of states for the hypothesis reward machine to 4. Similarly,
we limit the maximum allowable size of the trace sets, which is the number of
episodes whose traces are recorded, to 20. In case the inference exceeds the
allowed number of states, the process is stopped and the training continues
with the last valid hypothesis reward machine until the next inference step.

We first specify the following task to the agent: $\phi_{1}=$ “Go to
$\tt{bedroom}$ or $\tt{office}$, and then to the $\tt{kitchen}$”, which is
encoded by the reward machine shown in Fig. 5.

Figure 4: Left: Sample indoor layout from HouseExpo dataset; Right: Pre-
processed sample layout
$v_{0}$$v_{1}$$v_{2}$$(\neg\textup{bedroom}\land\neg\textup{office},0)$$(\textup{bedroom}\lor\textup{office},0)$$(\neg\textup{kitchen},0)$$(\textup{kitchen},1)$$(\textup{True},0)$
Figure 5: Ground truth reward machine of the task $\phi_{1}$.

We execute the proposed algorithm in 75 test floor plans. For each one of the
first four experimental settings, where updates according to an observation
model are performed, the learning agent is trained 5 times in each test floor
plan, each one corresponding to a different random seed, leading to a total of
375 runs. For the last setting that does not include belief updates, we
removed 12 test floor plans where the inference procedure took unreasonably
long time to finish, resulting in 63 test floor plans. This is attributed to
the fact that the belief functions are randomly initialized and not updated
throughout the training. For this last setting, the learning agent is also
trained 5 times in each test floor plan, each one corresponding to a different
random seed, leading to a total of 290 runs. In each one of the aforementioned
runs, we perform an evaluation episode every 100 training steps and register
the obtained rewards. Figure 6 depicts the progression of these rewards during
training, separated in the ones belonging to the $25^{th}$ and $75^{th}$
percentiles, and the ones belonging to the $10^{th}$ and $90^{th}$
percentiles. The figures also depict the median values with solid line.
Similarly, Table LABEL:table:comparison shows the training steps required for
convergence for the $25^{th}$ (LP), $50^{th}$ (MP), and $75^{th}$ (HP)
percentiles of the attained rewards. The table also depicts the ratio of
successful inferences of reward machines (RS), and the average number of
belief updates (BU). One concludes that in the time-varying BNN (“TvBNN” in
Table LABEL:table:comparison) setting, the algorithm achieves on average
faster convergence, while requiring fewer belief updates. Additionally, the
results indicate that the algorithm has slower convergence in the fixed BNN
(“FiBNN” in Table LABEL:table:comparison) setting, which is attributed to the
fact that only one set of observation probabilities is sampled and used
throughout the training, compared to other settings, where one set is sampled
at the beginning of every training episode. Moreover, the first random
observation model (“Random” in Table LABEL:table:comparison) is faster than
the second one (“Random2” in Table LABEL:table:comparison), as the range from
which probabilities are sampled uniformly is wider and hence perception
outputs are less random, convergence is faster, and fewer belief updates are
necessary. Finally, one concludes that all settings where belief updates are
performed, with both time-varying and fixed observation models, outperform the
setting without any updates (“No update” in Table LABEL:table:comparison). It
is also noteworthy that, in the no-update setting, the algorithm does not
converge to the optimal policy in 21 of the 63 test floor plans.

(a) Time-varying BNN

(b) Fixed BNN

(c) Random Observation

(d) Random Observation - 2

(e) No Update

Figure 6: Attained rewards of 5 independent runs for every 100 training steps in 75 test indoor layouts for task $\phi_{1}$: The darker region is bounded by $25^{th}$ and $75^{th}$ percentiles, while the lighter region is bounded by $10^{th}$ and $90^{th}$. The solid line represents the median. Table 1: Comparison of experimental settings on 5 independent runs for 75 test indoor layouts and task $\phi_{1}$. Settings | TvBNN | FiBNN | Random | Random2 | No Update
---|---|---|---|---|---
LP | 95,800 | 109,600 | 103,000 | 107,800 | 500,000
MP | 44,400 | 48,900 | 40,100 | 45,700 | 189,900
UP | 9,900 | 22,700 | 11,200 | 17,200 | 35,000
RS | 75/75 | 75/75 | 75/75 | 75/75 | 63/75
BU | 1.6 | 2.79 | 3.73 | 6.64 | -

We further demonstrate the progression of belief updates throughout the
training in Figure 7. Fig. 7(a) shows the number of training runs (y-axis) in
which the belief function is updated for the $k^{th}$ time (x-axis). For
instance, in the time-varying BNN (“TvBNN”) setting, the learning agent
updates its belief for the third time in around 20 runs out of 375 training
runs (5 runs per every floor plan where a reward machine is successfully
inferred). Fig. 7(b) shows the number of the step (y-axis) in which the belief
function is updated for the $k^{th}$ time on average (x-axis), and Fig. 7(c)
displays the average Jensen-Shannon divergence value that led to the $k^{th}$
belief update. The time-varying BNN (“TvBNN”) setting allows the learning
agent to obtain a belief function that represents the environment well in a
couple of steps. When sampling observation probabilities once, as in the fixed
BNN (“FiBNN”) setting, it slows down the process since the sampled observation
might not be informative. Regarding the random observation model, due to the
wide uniform distribution range, the agent samples probabilities that are
close to zero or one, i.e. being more “certain” that an atomic proposition
won’t or will be observed, respectively. This is the reason why the second
random observation model performs more belief updates until the divergence
score drops below the threshold. Overall, it is expected to see that, in the
BNN settings, the algorithm performs fewer belief updates compared to the
random settings.

(a) Average number of runs for the $k^{th}$ belief update.

(b) Training step for the $k^{th}$ belief update, on average.

(c) Average value of the JSD that led to the $k^{th}$ update.

Figure 7: Progression of belief updates during training for task $\phi_{1}$.

To test the capabilities of our method in a more complicated scenario, we set
a second task as $\phi_{2}=$ “Go to $\tt{kitchen}$ while avoiding the
$\tt{bathroom}$, and then go to the $\tt{bathroom}$ while avoiding the
$\tt{bedroom}$”, which is encoded by the reward machine shown in Fig. 8.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$(\neg\textup{kitchen}\land\neg\textup{bathroom},0)$$(\textup{bathroom},0)$$(\textup{kitchen}\land\neg\textup{bathroom},0)$$(\textup{True},0)$$(\neg\textup{bathroom},0)$$(\textup{bedroom},0)$$(\textup{bathroom}\land\neg\textup{bedroom},1)$$(\textup{True},0)$
Figure 8: Ground truth reward machine of the task $\phi_{2}$.

For this second task, we execute the proposed algorithm in 7 test floor plans.
Figs. 9, 10, and Table LABEL:table:comparison2 show the convergence results
and belief updates, similar to the ones for $\phi_{1}$, for the first four
settings; we omit the last one (no belief updates) since training fails to
yield an inferred reward machine. As reported in Table LABEL:table:comparison,
the average number of belief updates is smaller for the BNN observation
settings compared to the random observation settings. The TvBNN setting
requires the fewest number of belief updates on average, whereas the Random-2
setting requires the highest number of updates. However, it is more difficult
to interpret and compare the results in terms of convergence. For example, the
Random setting converges the slowest and fastest in lower and upper quartiles,
respectively, whereas the opposite occurs for the Random-2 settings.
Nevertheless, the belief update pattern that we see in the outcomes of the
previous experiment remains unchanged. One can still conclude that the
proposed algorithm outperforms the final setting, where no belief updates are
performed.

(a) Time-varying BNN

(b) Fixed BNN

(c) Random Observation

(d) Random Observation - 2

Figure 9: Attained rewards of 5 independent runs for every 100 training steps in 7 test indoor layouts for task $\phi_{2}$: The darker region is bounded by $25^{th}$ and $75^{th}$ percentiles, while the lighter region is bounded by $10^{th}$ and $90^{th}$. The solid line represents the median. Table 2: Comparison of experimental settings on 5 independent runs for 7 test indoor layouts and task $\phi_{2}$. Settings | TvBNN | FiBNN | Random | Random2
---|---|---|---|---
LP | 255,500 | 263,100 | 341,100 | 231,100
MP | 146,700 | 141,800 | 137,100 | 122,200
UP | 81,500 | 80,000 | 74,200 | 91,100
BU | 1.57 | 2.85 | 3.45 | 6.22

(a) Average number of runs for the $k^{th}$ belief update.

(b) Average number of runs for the $k^{th}$ belief update.

(c) Average value of the JSD that led to the $k^{th}$ update.

Figure 10: Progression of belief update during training for task $\phi_{2}$.

##  6 Conclusion and Discussion

We develop a reinforcement algorithm subject to reward-machine-encoded tasks
and perceptual limitations. The algorithm holds probabilistic beliefs over the
truth value of the atomic propositions and uses a hypothesis reward machine to
estimate the reward machine that encodes the task to be accomplished. Both the
beliefs and the hypothesis reward machine are updated by using the agent’s
sensor measurements and the obtained rewards from the agent’s trajectories.
The algorithm uses the aforementioned beliefs and the hypothesis reward
machine in a q-learning procedure to learn an optimal policy that accomplishes
this task.

Currently, the theoretical guarantees, provided by Theorem 1, presuppose that
the algorithm obtains a good enough estimate of the atomic propositions’
value, as encoded in the ground truth labelling function $L_{G}$, i.e.,
$\hat{L}(\hat{\mathcal{L}}_{h},\cdot)=L_{G}(\cdot)$. The definition of
$\hat{L}(\mathcal{\hat{L}}_{h},\cdot)$ in (1), based on the most probable
atomic propositions $p$ for state $s$, i.e., $\hat{\mathcal{L}}_{h}(s,p)\geq
0.5$, mildens such an assumption, which is further verified to hold by the
experimental results. Nevertheless, our future directions aim to examine how
the observation model $O(\cdot)$, given in Def. 3, affects the estimate
$\hat{L}(\hat{\mathcal{L}}_{h},\cdot)$ and, consequently, the inferred reward
machine and the learned policy. Another limitation of the proposed algorithm
is that it is currently limited in discrete and static state and action
spaces. In the future, we will consider continuous spaces, possibly by
deploying neural-network approximations, and cases where the ground-truth
values of the atomic propositions change with time.

## References

  * [AAB13] AI Medina Ayala, Sean B Andersson, and Calin Belta.  Temporal logic motion planning in unknown environments.  IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5279–5284, 2013.
  * [AALL18] David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman.  State abstractions for lifelong reinforcement learning.  International Conference on Machine Learning, pages 10–19, 2018\.
  * [AJK+16] Derya Aksaray, Austin Jones, Zhaodan Kong, Mac Schwager, and Calin Belta.  Q-learning for robust satisfaction of signal temporal logic specifications.  IEEE 55th Conference on Decision and Control (CDC), pages 6565–6570, 2016.
  * [AKL17] Jacob Andreas, Dan Klein, and Sergey Levine.  Modular multitask reinforcement learning with policy sketches.  International Conference on Machine Learning, pages 166–175, 2017\.
  * [AMCA14] Ali-Akbar Agha-Mohammadi, Suman Chakravorty, and Nancy M Amato.  Firm: Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements.  The International Journal of Robotics Research, 33(2):268–304, 2014\.
  * [Bel57] Richard Bellman.  A markovian decision process.  Journal of mathematics and mechanics, pages 679–684, 1957.
  * [BWZP20] Alper Kamil Bozkurt, Yu Wang, Michael M Zavlanos, and Miroslav Pajic.  Control synthesis from linear temporal logic specifications using model-free reinforcement learning.  IEEE International Conference on Robotics and Automation (ICRA), pages 10349–10355, 2020.
  * [CCSM17] Alberto Camacho, Oscar Chen, Scott Sanner, and Sheila A McIlraith.  Non-markovian rewards expressed in ltl: guiding search via reward shaping.  Tenth Annual Symposium on Combinatorial Search, 2017.
  * [CJT20] Steven Carr, Nils Jansen, and Ufuk Topcu.  Verifiable rnn-based policies for pomdps under temporal logic constraints.  arXiv preprint arXiv:2002.05615, 2020.
  * [dSKL19] Rafael Rodrigues da Silva, Vince Kurtz, and Hai Lin.  Active perception and control from temporal logic specifications.  IEEE Control Systems Letters, 3(4):1068–1073, 2019.
  * [GBT20] Mahsa Ghasemi, Erdem Bulgur, and Ufuk Topcu.  Task-oriented active perception and planning in environments with partially known semantics.  International Conference on Machine Learning, pages 3484–3493, 2020\.
  * [GJD13] Meng Guo, Karl H Johansson, and Dimos V Dimarogonas.  Revising motion planning under linear temporal logic specifications in partially known workspaces.  2013 IEEE International Conference on Robotics and Automation, pages 5025–5032, 2013.
  * [Gol78] E Mark Gold.  Complexity of automaton identification from given data.  Information and control, 37(3):302–320, 1978.
  * [HAK18] Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening.  Logically-constrained reinforcement learning.  arXiv preprint arXiv:1801.08099, 2018.
  * [HPS+19] Ernst Moritz Hahn, Mateo Perez, Sven Schewe, Fabio Somenzi, Ashutosh Trivedi, and Dominik Wojtczak.  Omega-regular objectives in model-free reinforcement learning.  International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 395–412, 2019.
  * [HV10] Marijn JH Heule and Sicco Verwer.  Exact dfa identification using sat solvers.  International Colloquium on Grammatical Inference, pages 66–79, 2010.
  * [IKVM18] Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila McIlraith.  Using reward machines for high-level task specification and decomposition in reinforcement learning.  International Conference on Machine Learning, pages 2107–2116, 2018\.
  * [IMM18] Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva.  PySAT: A Python toolkit for prototyping with SAT oracles.  pages 428–437, 2018.
  * [KNST16] Tejas D Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum.  Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation.  Advances in neural information processing systems, 29:3675–3683, 2016.
  * [Kon19] George Konidaris.  On the necessity of abstraction.  Current opinion in behavioral sciences, 29:1–7, 2019.
  * [LMB12] Scott C Livingston, Richard M Murray, and Joel W Burdick.  Backtracking temporal logic synthesis for uncertain environments.  IEEE International Conference on Robotics and Automation, pages 5163–5170, 2012.
  * [LMF+16] Morteza Lahijanian, Matthew R Maly, Dror Fried, Lydia E Kavraki, Hadas Kress-Gazit, and Moshe Y Vardi.  Iterative temporal planning in uncertain environments with partial satisfaction guarantees.  IEEE Transactions on Robotics, 32(3):583–599, 2016.
  * [LVB17] Xiao Li, Cristian-Ioan Vasile, and Calin Belta.  Reinforcement learning with temporal logic rewards.  IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3834–3839, 2017.
  * [MDMS14] Antonio Morgado, Carmine Dodaro, and Joao Marques-Silva.  Core-guided maxsat with soft cardinality constraints.  pages 564–573, 2014.
  * [MLD17] Felipe J Montana, Jun Liu, and Tony J Dodd.  Sampling-based reactive motion planning with temporal logic constraints and imperfect state information.  Critical Systems: Formal Methods and Automated Verification, pages 134–149, 2017.
  * [Nei14] Daniel Neider.  Applications of automata learning in verification and synthesis.  PhD thesis, Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2014.
  * [NJ13] Daniel Neider and Nils Jansen.  Regular model checking using solver technologies and automata learning.  NASA Formal Methods Symposium, pages 16–31, 2013.
  * [Put14] Martin L Puterman.  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons, 2014.
  * [RCBP19] Bhaskar Ramasubramanian, Andrew Clark, Linda Bushnell, and Radha Poovendran.  Secure control under partial observability with temporal logic constraints.  American Control Conference (ACC), pages 1181–1188, 2019.
  * [Sin92] Satinder P Singh.  Reinforcement learning with a hierarchy of abstract models.  In Proceedings of the National Conference on Artificial Intelligence, number 10, page 202. Citeseer, 1992.
  * [SKC+14] Dorsa Sadigh, Eric S Kim, Samuel Coogan, S Shankar Sastry, and Sanjit A Seshia.  A learning based approach to control synthesis of markov decision processes for linear temporal logic specifications.  IEEE Conference on Decision and Control, pages 1091–1096, 2014\.
  * [TDC+19] Li Tingguang, Ho Danny, Li Chenming, Zhu Delong, Wang Chaoqun, and Max Q.-H. Meng.  Houseexpo: A large-scale 2d indoor layout dataset for learning-based algorithms on mobile robots.  arXiv preprint arXiv:1903.09845, 2019.
  * [TIKVM18] Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A McIlraith.  Teaching multiple tasks to an rl agent using ltl.  Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 452–461, 2018.
  * [TIWK+19] Rodrigo Toro Icarte, Ethan Waldie, Toryn Klassen, Rick Valenzano, Margarita Castro, and Sheila McIlraith.  Learning reward machines for partially observable reinforcement learning.  Advances in Neural Information Processing Systems, 32:15523–15534, 2019.
  * [TS07] Matthew E Taylor and Peter Stone.  Cross-domain transfer for reinforcement learning.  Proceedings of the 24th international conference on Machine learning, pages 879–886, 2007.
  * [WBP21] Yu Wang, Alper Kamil Bozkurt, and Miroslav Pajic.  Reinforcement learning with temporal logic constraints for partially-observable markov decision processes.  arXiv preprint arXiv:2104.01612, 2021.
  * [WD92] Christopher JCH Watkins and Peter Dayan.  Q-learning.  Machine learning, 8(3-4):279–292, 1992.
  * [WET15] Min Wen, Rüdiger Ehlers, and Ufuk Topcu.  Correct-by-synthesis reinforcement learning with temporal logic constraints.  IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4983–4990, 2015.
  * [WVB+18] Yeming Wen, Paul Vicol, Jimmy Ba, Dustin Tran, and Roger Grosse.  Flipout: Efficient pseudo-independent weight perturbations on mini-batches.  2018\.
  * [XGA+20] Zhe Xu, Ivan Gavran, Yousef Ahmad, Rupak Majumdar, Daniel Neider, Ufuk Topcu, and Bo Wu.  Joint inference of reward machines and policies for reinforcement learning.  Proceedings of the International Conference on Automated Planning and Scheduling, 30:590–598, 2020.
  * [ZWL15] Xiaobin Zhang, Bo Wu, and Hai Lin.  Learning based supervisor synthesis of pomdp for pctl specifications.  54th IEEE Conference on Decision and Control (CDC), pages 7470–7475, 2015.