# Reward Machines for Deep RL
in Noisy and Uncertain Environments

Andrew C. Li
University of Toronto
Vector Institute
&Zizhao Chen
Cornell University
&Toryn Q. Klassen
University of Toronto
Vector Institute
Pashootan Vaezipoor
Vector Institute
&Rodrigo Toro Icarte
Pontificia Universidad Católica de Chile
Centro Nacional de Inteligencia Artificial
&Sheila A. McIlraith$\dagger$
University of Toronto
Vector Institute
Work done while at the University of Toronto.Also affiliated with the Schwartz
Reisman Institute for Technology and Society.

###### Abstract

Reward Machines provide an automata-inspired structure for specifying
instructions, safety constraints, and other temporally extended reward-worthy
behaviour. By exposing complex reward function structure, they enable
counterfactual learning updates that have resulted in impressive sample
efficiency gains. While Reward Machines have been employed in both tabular and
deep RL settings, they have typically relied on a ground-truth interpretation
of the domain-specific vocabulary that form the building blocks of the reward
function. Such ground-truth interpretations can be elusive in many real-world
settings, due in part to partial observability or noisy sensing. In this
paper, we explore the use of Reward Machines for Deep RL in noisy and
uncertain environments. We characterize this problem as a POMDP and propose a
suite of RL algorithms that leverage task structure under uncertain
interpretation of domain-specific vocabulary. Theoretical analysis exposes
pitfalls in naive approaches to this problem, while experimental results show
that our algorithms successfully leverage task structure to improve
performance under noisy interpretations of the vocabulary. Our results provide
a general framework for exploiting Reward Machines in partially observable
environments.

Code and videos available at https://github.com/andrewli77/reward-machines-
noisy-environments.

††footnotetext: Correspondence to<EMAIL_ADDRESS>
##  1 Introduction

Formal languages, including programming languages, have long been used for
objective specification in sequential decision-making. Using a vocabulary of
domain-specific properties, expressed as propositional variables, formal
languages such as Linear Temporal Logic (LTL) [42] capture complex temporal
patterns—such as the objectives of an agent—by composing variables via
temporal operators and logical connectives. These languages provide well-
defined semantics while enabling semantics-preserving transformations to
normal-form representations such as automata, which can expose the discrete
structure underlying an objective to a decision-making agent. One such
representation is the increasingly popular Reward Machine which combines
expression of rich temporally extended objectives via automata, with
counterfactual learning updates, resulting in impressive improvements in
sample efficiency (e.g., [50, 52, 17]). Importantly, Reward Machines can be
specified directly, constructed via translation from any regular language
including variants of LTL, synthesized from high-level planning
specifications, or learned from data [6]. For these reasons, formal languages
and in particular Reward Machines have been adopted across a diversity of
domains, ranging from motion planning [29, 14, 48] and robotic manipulation
[7, 25, 30] to, more recently, general deep Reinforcement Learning (RL)
problems [e.g., 1, 33, 34, 36, 50, 51, 20, 61, 27, 58, 31, 21, 59, 60, 16, 44,
10, 26, 39, 47, 56, 11, 63, 7, 9, 37, 17, 46, 62, 55].

Critically, the use of formal languages in deep RL is often predicated on
knowledge of a “ground-truth” interpretation of the symbolic vocabulary,
realized via a _labelling function_ , which provides a mapping from
environment states to the truth or falsity of abstract properties that form
the building blocks of objective specifications. However, in practice, real-
world environments are typically partially observable and rely on high-
dimensional sensor data such as images, resulting in labelling functions that
are, by necessity, noisy and uncertain, compromising the application of formal
languages for objective specification, and notably the application of Reward
Machines. The contributions of this paper are as follows:

(1) We propose a deep RL framework for Reward Machines in settings where the
evaluation of domain-specific vocabulary is uncertain, characterizing the RL
problem in terms of a POMDP. To our knowledge, this is the first deep RL
framework for Reward Machines that broadly supports the imperfect detection of
propositions, allowing us to extend Reward Machines to general partially
observable environments.

(2) We propose and analyze a suite of RL algorithms that exploit Reward
Machine structure and that can be deployed without a ground-truth labelling
function. We show how preexisting “abstraction models”, noisy estimators of
task-relevant features that may manifest as pretrained neural networks,
sensors, heuristics, or otherwise, can be brought to bear to improve the
efficiency of learning.

(3) We theoretically and experimentally evaluate our proposed RL algorithms.
Theoretically, we discover a pitfall of naively leveraging standard
abstraction models—namely, that errors from repeated queries of a model are
correlated rather than i.i.d. We show that this can have serious
ramifications, including unintended or dangerous outcomes, and demonstrate how
this issue can be mitigated. Experimentally, we consider a variety of
challenging domains, including domains with partial observability and high-
dimensional observations. Results show that our algorithms successfully
leverage task structure to improve performance under noisy interpretations of
the vocabulary.

##  2 Background

We use the following probability notation. For a set $X$, $\Delta X$ is the
set of distributions over $X$; $\tilde{(\cdot)}$ denotes a particular
distribution; and for a categorical distribution $\tilde{w}\in\Delta X$ and
some $x\in X$, we denote $\tilde{w}[x]$ as the probability of $x$ under
$\tilde{w}$. We use $x_{i:j}$ as a shorthand for the sequence
$x_{i},\ldots,x_{j}$.

#### POMDPs

A _Partially Observable Markov Decision Process_ (POMDP) $\langle
S,O,A,P,R,\omega,\mu\rangle$ [3] is defined by the state space $S$,
observation space $O$, action space $A$, reward function $R$, transition
distribution $P:S\times A\to\Delta S$, observation distribution
$\omega:S\to\Delta O$, and initial state distribution $\mu\in\Delta S$. An
_episode_ begins with an initial state $s_{1}\sim\mu(\cdot)$ and at each
timestep $t\geq 1$, the agent observes an observation
$o_{t}\sim\omega(s_{t})$, performs an action $a_{t}\in A$, and receives reward
$r_{t}=R(s_{t},a_{t})$. The environment then transitions to the next state
$s_{t+1}\sim P(s_{t},a_{t})$. Denote the agent’s observation-action history at
time $t$ by $h_{t}=(o_{1},a_{1},\ldots,o_{t-1},a_{t-1},o_{t})$ and the set of
all possible histories as $H$. A fully observable _Markov Decision Process_
(MDP) serves as an important special case.

#### Reward Machines

A Reward Machine (RM) [50] is a formal automaton representation of a non-
Markovian reward function that captures temporally extended behaviours.
Formally, an RM $\mathcal{R}=\langle
U,u_{1},F,\mathcal{AP},\delta_{u},\delta_{r}\rangle$, where $U$ is a finite
set of states, $u_{1}\in U$ is the initial state, $F$ is a finite set of
terminal states (disjoint from $U$), $\mathcal{AP}$ is a finite set of atomic
propositions, $\delta_{u}:U\times 2^{\mathcal{AP}}\rightarrow(U\cup F)$ is the
state-transition function, and $\delta_{r}:U\times
2^{\mathcal{AP}}\rightarrow\mathbb{R}$ is the state-reward function. Each
transition in an RM is labelled with a scalar reward along with a
propositional logic formula over $\mathcal{AP}$ representing the occurrence of
salient events in the environment, while accepting states represent task
termination.

#### Labelling Function

While an RM captures the high-level structure of a non-Markovian reward
function, concrete rewards in an environment are determined with the help of a
labelling function $\mathcal{L}:S\times A\times S\to 2^{\mathcal{AP}}$, a
mapping of state transitions ($s_{t-1},a_{t-1},s_{t}$) in the environment to
the subset of propositions that hold for that transition. To obtain rewards,
the sequence of environment states and actions
$s_{1},a_{1},\ldots,s_{t},a_{t},s_{t+1}$ are labelled with propositional
evaluations $\sigma_{1:t}$, where
$\sigma_{i}=\mathcal{L}(s_{i},a_{i},s_{i+1})\in 2^{\mathcal{AP}}$. A sequence
of transitions in the RM are then followed based on $\sigma_{1:t}$ to produce
the reward sequence $r_{1:t}$. In an MDP environment, RL with rewards
specified by an RM is _Markovian_ over an extended state space $S\times U$,
hence, there is an optimal policy of the form $\pi(a_{t}|s_{t},u_{t})$ where
$u_{t}\in U$ is the RM state at time $t$ [50]. During execution, $u_{t}$ can
be recursively updated given $u_{t-1}$ by querying $\mathcal{L}$ after each
environment transition.

##  3 Problem Framework

###  3.1 Formalization

We now formalize the problem of solving an RM objective under an uncertain
interpretation of the vocabulary. Consider an agent acting in a POMDP
environment (without the reward function) $\mathcal{E}=\langle
S,O,A,P,\omega,\mu\rangle$. Rewards are provided by an RM $\mathcal{R}=\langle
U,u_{1},F,\mathcal{AP},\delta_{u},\delta_{r}\rangle$ as interpreted under a
(hidden) labelling function $\mathcal{L}:S\times A\times S\to
2^{\mathcal{AP}}$. The distinguishing assumption of our framework is that the
agent does not observe $\mathcal{L}$ when acting, thus, during an episode, the
agent may be uncertain about the occurrences of propositions $\mathcal{AP}$.

Instead, we introduce the concept of an abstraction model $\mathcal{M}:H\to Z$
that the agent can query based on the observations so far, $h_{t}\in H$. The
abstraction model outputs $z_{t}\in Z$, where $Z$ is an arbitrary feature
space. We leave the definition of $\mathcal{M}$ to be as general as possible;
it may be a classifier predicting occurrences of propositions (i.e.
$Z=2^{\mathcal{AP}}$), or it may model some other relevant abstraction.
Crucially, $\mathcal{M}$ can be noisy or erroneous, and in the real world,
$\mathcal{M}$ might manifest as pretrained foundation models [43, 35, 4, 13],
sensors [15], task-specific classifiers [19]), or so on.

We refer to the tuple
$\mathcal{P}=\langle\mathcal{E},\mathcal{R},\mathcal{L},\mathcal{M}\rangle$ as
a Noisy Reward Machine Environment. Our objective is to obtain a policy
$\pi(a_{t}|h_{t},z_{1:t})$ based on all observable information up to time $t$
that maximizes the expected discounted return for some discount factor
$\gamma\in(0,1]$ in the Noisy RM Environment. Such a policy might seek
information or perform robust strategies in response to uncertain evaluations
of the propositions $\mathcal{AP}$, and we assume $\pi$ is learned through RL.
At the end of each training episode, the agent receives as a learning signal
that episode’s sequence of rewards $r_{1},r_{2},\ldots$ based on $\mathcal{R}$
and $\mathcal{L}$.

###  3.2 Running Example

0000000000000000

$u^{(0)}$$u^{(1)}$$u^{(2)}$$\langle\mathrm{o/w},0\rangle$$\langle\leavevmode\hbox
to8.34pt{\vbox to6.87pt{\pgfpicture\makeatletter\hbox{\hskip
4.47331pt\lower-3.86827pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}{{}}
{}\definecolor{tikz@axis@top}{rgb}{1,0.96875,0.8}\definecolor{tikz@axis@middle}{rgb}{1,0.984375,0.9}\definecolor{tikz@axis@bottom}{rgb}{0.884375,0.6875,0.1}\definecolor{tikz@axis@middle}{rgb}{0.9421875,0.828125,0.45}{}{{}}{}
{}{} {}{} {}{} {}{} {}{} {}{} {}{} {}{} {}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.927734375,0.82421875,0.5625}\definecolor[named]{pgfstrokecolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@color@rgb@stroke{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@setlinewidth{0.1pt}\pgfsys@invoke{
}\pgfsys@stroke@opacity{1}\pgfsys@invoke{
}\pgfsys@fill@opacity{1}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.30246pt}{-0.43471pt}\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@transformcm{0.16423}{0.0}{0.0}{0.13484}{0.0pt}{0.0pt}\pgfsys@invoke{
}\lxSVG@sh@defs{}\lxSVG@sh@insert{-69.44499pt}{-69.44499pt}{\lxSVG@sh}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\land\lnot\text{\faHome},0\rangle$$\langle\text{\faHome},0\rangle$$\langle\mathrm{o/w},0\rangle$$\langle\text{\faHome},1\rangle$

Figure 1:  The Gold Mining Problem is a _Noisy RM Environment_ where the
agent’s interpretation of the vocabulary is uncertain. Left: The four
rightmost cells yield gold (  ) while two cells in the second column yield
iron pyrite, which has no value. The agent cannot reliably distinguish between
the two metals—cells are labelled with the probability the agent believes it
yields gold. Right: The RM emits a (non-Markovian) reward of 1 for collecting
gold and delivering it to the depot.

The Gold Mining Problem serves as a running example of a Noisy RM Environment
(Figure 1). A mining robot operates in a grid with a non-Markovian goal: dig
up at least one chunk of gold (  ) and deliver it to the depot (). The
environment is an MDP where the robot observes its current grid position and
its actions include moving in the cardinal directions and digging. A labelling
function $\mathcal{L}$ associates the propositions $\mathcal{AP}=\\{\text{
\leavevmode\hbox to8.34pt{\vbox to6.87pt{\pgfpicture\makeatletter\hbox{\hskip
4.47331pt\lower-3.86827pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}{{}}
{}\definecolor{tikz@axis@top}{rgb}{1,0.96875,0.8}\definecolor{tikz@axis@middle}{rgb}{1,0.984375,0.9}\definecolor{tikz@axis@bottom}{rgb}{0.884375,0.6875,0.1}\definecolor{tikz@axis@middle}{rgb}{0.9421875,0.828125,0.45}{}{{}}{}
{}{} {}{} {}{} {}{} {}{} {}{} {}{} {}{} {}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.927734375,0.82421875,0.5625}\definecolor[named]{pgfstrokecolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@color@rgb@stroke{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@setlinewidth{0.1pt}\pgfsys@invoke{
}\pgfsys@stroke@opacity{1}\pgfsys@invoke{
}\pgfsys@fill@opacity{1}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.30246pt}{-0.43471pt}\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@transformcm{0.16423}{0.0}{0.0}{0.13484}{0.0pt}{0.0pt}\pgfsys@invoke{
}\lxSVG@sh@defs{}\lxSVG@sh@insert{-69.44499pt}{-69.44499pt}{\lxSVG@sh}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} , \text{\faHome}}\\}$
with grid states and actions:  holds when the robot is in the rightmost row
and digs and  holds when the robot is at the bottom-left cell.

However, the robot does not have access to $\mathcal{L}$ and cannot reliably
distinguish gold from iron pyrite. Thus, it cannot ascertain whether it has
obtained gold during the course of an episode. Luckily, the robot can make an
educated guess as to whether a cell contains gold, which is captured by an
abstraction model $\mathcal{M}:H\to[0,1]$ mapping the robot’s current position
(while ignoring the rest of the history) to its belief that the cell contains
gold.

We note that if the robot agent _could_ observe $\mathcal{L}$, then it can
learn an optimal _Markovian_ policy $\pi(a_{t}|s_{t},u_{t})$ with a relatively
simple form ($u_{t}$ is easily computed with access to $\mathcal{L}$). Roughly
speaking, such a policy should collect gold when in RM state $u^{(0)}$ and
head to the depot when in RM state $u^{(1)}$. Unfortunately, the
unavailability of $\mathcal{L}$ precludes us from directly learning a policy
with the simpler Markovian form above. In the following sections, we show how
the agent’s noisy belief captured by the abstraction model $\mathcal{M}$ can
be leveraged to simplify the learning problem.

##  4 Noisy RM Environments as POMDPs

We start with an analysis of the Noisy RM Environment framework, and contrast
with a standard RM framework. We ask: (1) What is the optimal behaviour in a
Noisy RM Environment? (2) How does the abstraction model $\mathcal{M}$ affect
the problem? (3) How does not observing the labelling function $\mathcal{L}$
affect the problem? We provide proofs for all theorems in Appendix A.

Observe that uncertainty in the labelling function is only relevant insofar as
it informs the agent’s knowledge of the current RM state $u_{t}$ since rewards
from an RM $\mathcal{R}$ are Markovian over extended states $(s_{t},u_{t})\in
S\times U$. Our first result is that a Noisy RM Environment
$\langle\mathcal{E},\mathcal{R},\mathcal{L},\mathcal{M}\rangle$ can be
reformulated into an equivalent POMDP with state space $S\times U$ and
observation space $O$ (Theorem 4.1). Here, we say two problems are equivalent
if there is a bijection between policies for either problem such that the
policies have equal expected discounted return and behave identically given
the same history $h_{t}$. Thus, optimal behaviour in a Noisy RM Environment
can be reduced to solving a POMDP.

###### Theorem 4.1

A Noisy RM Environment
$\langle\mathcal{E},\mathcal{R},\mathcal{L},\mathcal{M}\rangle$ is equivalent
to a POMDP over state space $S\times U$ and observation space $O$.

One may notice that the abstraction model $\mathcal{M}$ doesn’t appear in the
POMDP reformulation at all. We later show that an appropriate choice of
$\mathcal{M}$ can improve policy learning in practice, but this choice
ultimately does not change the optimal behaviour of the agent (Theorem 4.2).

######  Theorem 4.2 (_Does the choice of $\mathcal{M}$ affect optimal
behaviour?_)

Let $\mathcal{P}$ be a Noisy RM Environment
$\langle\mathcal{E},\mathcal{R},\mathcal{L},\mathcal{M}\rangle$, and
$\mathcal{P}^{\prime}$ be a Noisy RM Environment
$\langle\mathcal{E},\mathcal{R},\mathcal{L},\mathcal{M^{\prime}}\rangle$. Then
$\mathcal{P}$ and $\mathcal{P^{\prime}}$ are equivalent.

We also contrast our proposed framework, where the agent does not have direct
access to $\mathcal{L}$, with prior RM frameworks where the agent does. We
show that this difference does not affect the optimal behaviour in MDP
environments, but can affect the optimal behaviour in POMDPs (Theorem 4.3).

######  Theorem 4.3 (_Does observing $\mathcal{L}$ affect optimal behaviour?_)

Let $\mathcal{P}$ be a Noisy RM Environment
$\langle\mathcal{E},\mathcal{R},\mathcal{L},\mathcal{M}\rangle$. Consider a
problem $\mathcal{P}^{\prime}$ that is identical to $\mathcal{P}$ except that
the agent at time $t$ additionally observes $\mathcal{L}(s_{t},a_{t},s_{t+1})$
after taking action $a_{t}$ in state $s_{t}$. If $\mathcal{E}$ is an MDP, then
$\mathcal{P}$ and $\mathcal{P^{\prime}}$ are equivalent. If $\mathcal{E}$ is a
POMDP, $\mathcal{P}$ and $\mathcal{P^{\prime}}$ may be non-equivalent.

##  5 Method

In this section, we consider how to train policies that do not require the
labelling function $\mathcal{L}$ to act. Given Theorem 4.1, in principle we
can apply any deep RL approach suitable for POMDPs, such as a recurrent policy
that conditions on past actions and observations. However, such a learning
algorithm may be inefficient as it doesn’t exploit the known RM structure at
all.

We propose a class of policies that decouple inference of the RM state $u_{t}$
(treated as an unknown random variable) and decision making into two separate
modules. The _inference_ module models a belief $\tilde{u}_{t}\in\Delta U$ of
the current RM state $u_{t}$ over the course of an episode with the help of an
abstraction model $\mathcal{M}$. Specifically, we represent
$\tilde{u}_{t}=f(z_{1:t})$ as a function of the history of outputs from
$\mathcal{M}$ and the inference objective is to recover the optimal
distribution $\mathrm{Pr}(u_{t}|h_{t})\in\Delta U$ for any $h_{t}\in H$, which
is policy-independent. The _decision-making_ module is a policy
$\pi(a_{t}|h_{t},\tilde{u}_{t})$ that leverages the inferred belief
$\tilde{u}_{t}$. We hypothesize that inference of $u_{t}$ is critical for
decision making since, given $s_{t}$, it is sufficient for predicting future
rewards and deciding optimal behaviour.

We propose the following RM state inference algorithms. For each, we identify
the prerequisite abstraction model $\mathcal{M}:H\to Z$ and how $\mathcal{M}$
is leveraged to predict an RM state belief $\tilde{u}_{t}$.

###  5.1 Naive

Suppose that in lieu of the labelling function $\mathcal{L}$, we have a noisy
estimator of $\mathcal{L}$ that predicts propositional evaluations based on
the observation history. This is captured via an abstraction model of the form
$\mathcal{M}:H\to 2^{\mathcal{AP}}$ that makes discrete (and potentially
incorrect) predictions about the propositions
$\mathcal{L}(s_{t-1},a_{t-1},s_{t})$ that hold at time $t$, given the history
$h_{t}$. Then, we can recursively model a discrete prediction of the RM state
$\hat{u}_{t}\in U$ (which can be seen as a belief over $U$ with full
probability mass on $\hat{u}_{t}$) using outputs of $\mathcal{M}$ in place of
$\mathcal{L}$.

######  Method 1 (Naive)

Given $\mathcal{M}:H\to 2^{\mathcal{AP}}$, predict a discrete RM state
$\hat{u}_{t}\in U$ as follows. Set $\hat{u}_{1}=u_{1}$. For $t>1$, predict
$\hat{u}_{t}=\delta_{u}(\hat{u}_{t-1},\mathcal{M}(h_{t}))$.

A weakness of this approach is that it does not represent the uncertainty in
its prediction. Furthermore, since RM state predictions are updated
recursively, an error when predicting $\hat{u}_{t}$ will propagate to all
future predictions $(\hat{u}_{t+1},\hat{u}_{t+2},\ldots)$.

###### Example 5.1

Returning to the running example, suppose the agent uses its belief of
locations yielding gold to derive an abstraction model $\mathcal{M}:H\to
2^{\mathcal{AP}}$. For a history $h_{t}$, $\mathcal{M}$ takes the current grid
position $s_{t}$ and predicts  is true if it believes there is at least a 50%
chance it yields gold when it performs a digging action. We assume the agent
can always predict  correctly. Observing Figure 1, we see that $\mathcal{M}$
agrees with $\mathcal{L}$ in all cases except at one cell where there is
actually iron pyrite (that the agent believes has gold with 0.6 probability).
Given a trajectory where the agent mines at this cell, Thresholding would
erroneously assume gold was obtained.

###  5.2 Independent Belief Updating (IBU)

In order to capture the uncertainty in the belief over the RM state $u_{t}$,
one may instead wish to model a probability distribution
$\tilde{u}_{t}\in\Delta U$. Given an abstraction model of the form
$\mathcal{M}:H\to\Delta(2^{\mathcal{AP}})$ that predicts probabilities over
possible propositional evaluations $\mathcal{L}(s_{t-1},a_{t-1},s_{t})$, an
enticing approach is to derive $\tilde{u}_{t}$ by probabilistically weighing
all possible RM states at time $t-1$ according to the previous belief
$\tilde{u}_{t-1}$ along with all possible evaluations of
$\mathcal{L}(s_{t-1},a_{t-1},s_{t})$ according to $\mathcal{M}$.

######  Method 2 (IBU)

Given $\mathcal{M}:H\to\Delta(2^{\mathcal{AP}})$, predict a distribution over
RM states $\tilde{u}_{t}\in\Delta U$ as follows. Set $\tilde{u}_{1}[u_{1}]=1$
and $\tilde{u}_{1}[u]=0$ for $u\in U\setminus\\{u_{1}\\}$. For $t>1$, set

$\displaystyle\tilde{u}_{t}[u]$ $\displaystyle=\sum_{\sigma\in
2^{\mathcal{AP}},u^{\prime}\in
U}{\mathbbm{1}[\delta_{u}(u^{\prime},\sigma)=u]\cdot\tilde{u}_{t-1}[u^{\prime}]\cdot\mathcal{M}(h_{t})[\sigma]}$

On the surface, IBU may appear to solve the error propagation issue of the
Naive approach by softening a discrete belief into a probabilistic one.
Surprisingly, updating beliefs $\tilde{u}_{t}$ in this manner can still result
in a belief that quickly diverges from reality with increasing $t$. This is
because IBU fails to consider that propositional evaluations are linked,
rather than independent. Since the computation of $\tilde{u}_{t}$ aggregates
$t$ queries to $\mathcal{M}$, noise in the outputs of $\mathcal{M}$ can
dramatically amplify if the _correlation_ between these noisy outputs is not
considered. This is best illustrated by an example.

###### Example 5.2

The mining agent now considers a probability distribution over propositional
assignments of $\\{\leavevmode\hbox to8.34pt{\vbox
to6.87pt{\pgfpicture\makeatletter\hbox{\hskip 4.47331pt\lower-3.86827pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}{{}}
{}\definecolor{tikz@axis@top}{rgb}{1,0.96875,0.8}\definecolor{tikz@axis@middle}{rgb}{1,0.984375,0.9}\definecolor{tikz@axis@bottom}{rgb}{0.884375,0.6875,0.1}\definecolor{tikz@axis@middle}{rgb}{0.9421875,0.828125,0.45}{}{{}}{}
{}{} {}{} {}{} {}{} {}{} {}{} {}{} {}{} {}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.927734375,0.82421875,0.5625}\definecolor[named]{pgfstrokecolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@color@rgb@stroke{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@setlinewidth{0.1pt}\pgfsys@invoke{
}\pgfsys@stroke@opacity{1}\pgfsys@invoke{
}\pgfsys@fill@opacity{1}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.30246pt}{-0.43471pt}\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@transformcm{0.16423}{0.0}{0.0}{0.13484}{0.0pt}{0.0pt}\pgfsys@invoke{
}\lxSVG@sh@defs{}\lxSVG@sh@insert{-69.44499pt}{-69.44499pt}{\lxSVG@sh}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\text{\faHome}\\}$.
We assume the agent always perfectly determines  and applies its belief of
locations yielding gold; e.g., digging in the cell the agent believes has gold
with 0.3 probability yields the distribution
$(\emptyset:0.7,\\{\leavevmode\hbox to8.34pt{\vbox
to6.87pt{\pgfpicture\makeatletter\hbox{\hskip 4.47331pt\lower-3.86827pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}{{}}
{}\definecolor{tikz@axis@top}{rgb}{1,0.96875,0.8}\definecolor{tikz@axis@middle}{rgb}{1,0.984375,0.9}\definecolor{tikz@axis@bottom}{rgb}{0.884375,0.6875,0.1}\definecolor{tikz@axis@middle}{rgb}{0.9421875,0.828125,0.45}{}{{}}{}
{}{} {}{} {}{} {}{} {}{} {}{} {}{} {}{} {}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.927734375,0.82421875,0.5625}\definecolor[named]{pgfstrokecolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@color@rgb@stroke{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@setlinewidth{0.1pt}\pgfsys@invoke{
}\pgfsys@stroke@opacity{1}\pgfsys@invoke{
}\pgfsys@fill@opacity{1}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.30246pt}{-0.43471pt}\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@transformcm{0.16423}{0.0}{0.0}{0.13484}{0.0pt}{0.0pt}\pgfsys@invoke{
}\lxSVG@sh@defs{}\lxSVG@sh@insert{-69.44499pt}{-69.44499pt}{\lxSVG@sh}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\}:0.3,\\{\text{\faHome}\\}:0,\\{\leavevmode\hbox
to8.34pt{\vbox to6.87pt{\pgfpicture\makeatletter\hbox{\hskip
4.47331pt\lower-3.86827pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } \pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}{{}}
{}\definecolor{tikz@axis@top}{rgb}{1,0.96875,0.8}\definecolor{tikz@axis@middle}{rgb}{1,0.984375,0.9}\definecolor{tikz@axis@bottom}{rgb}{0.884375,0.6875,0.1}\definecolor{tikz@axis@middle}{rgb}{0.9421875,0.828125,0.45}{}{{}}{}
{}{} {}{} {}{} {}{} {}{} {}{} {}{} {}{} {}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.927734375,0.82421875,0.5625}\definecolor[named]{pgfstrokecolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@color@rgb@stroke{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.927734375}{0.82421875}{0.5625}\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.927734375,0.82421875,0.5625}\pgfsys@setlinewidth{0.1pt}\pgfsys@invoke{
}\pgfsys@stroke@opacity{1}\pgfsys@invoke{
}\pgfsys@fill@opacity{1}\pgfsys@invoke{
}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.30246pt}{-0.43471pt}\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@transformcm{0.16423}{0.0}{0.0}{0.13484}{0.0pt}{0.0pt}\pgfsys@invoke{
}\lxSVG@sh@defs{}\lxSVG@sh@insert{-69.44499pt}{-69.44499pt}{\lxSVG@sh}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}\pgfsys@moveto{-1.64394pt}{2.88924pt}\pgfsys@lineto{-0.65636pt}{2.74931pt}\pgfsys@curveto{-1.4343pt}{2.85951pt}{-2.54105pt}{2.52579pt}{-3.12836pt}{2.00389pt}\pgfsys@lineto{-3.35387pt}{1.80353pt}\pgfsys@curveto{-3.94118pt}{1.28163pt}{-4.41827pt}{0.22162pt}{-4.41946pt}{-0.56409pt}\pgfsys@lineto{-4.42114pt}{-1.67474pt}\pgfsys@curveto{-4.42233pt}{-2.46045pt}{-3.82848pt}{-2.86964pt}{-3.09471pt}{-2.58873pt}\pgfsys@lineto{-3.06406pt}{-2.577pt}\pgfsys@curveto{-2.33029pt}{-2.29608pt}{-1.33015pt}{-2.5597pt}{-0.83018pt}{-3.16579pt}\pgfsys@lineto{-1.40622pt}{-2.46748pt}\pgfsys@curveto{-0.90625pt}{-3.07358pt}{0.13489pt}{-3.60222pt}{0.91924pt}{-3.64821pt}\pgfsys@lineto{2.39822pt}{-3.73499pt}\pgfsys@curveto{3.18257pt}{-3.78098pt}{3.63936pt}{-3.20702pt}{3.41852pt}{-2.45299pt}\pgfsys@lineto{3.09987pt}{-1.36523pt}\pgfsys@curveto{2.87903pt}{-0.6112pt}{2.22504pt}{0.42445pt}{1.63918pt}{0.948pt}\pgfsys@lineto{2.21777pt}{0.43094pt}\pgfsys@curveto{1.63191pt}{0.95448pt}{0.6932pt}{1.81549pt}{0.12114pt}{2.35406pt}\pgfsys@lineto{0.80046pt}{1.71451pt}\pgfsys@curveto{0.2284pt}{2.25308pt}{-0.866pt}{2.77904pt}{-1.64394pt}{2.88924pt}\pgfsys@closepath\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},\text{\faHome}\\}:0)$.
Consider a trajectory where the agent digs at this cell multiple times. After
mining once, IBU updates the RM state belief $\tilde{u}_{t}$ to reflect a 0.3
probability of having obtained gold. After mining twice, this increases to
0.51 and in general, the belief reflects a $1-0.7^{k}$ probability after
mining $k$ times. In reality, mining more than once at this square should not
increase the probability beyond $0.3$ since all evaluations of  at that cell
are linked—they are all true, or they are all false.

###  5.3 Temporal Dependency Modelling (TDM)

Example 5.2 demonstrates a challenge when aggregating multiple predictions
from a noisy classifier—the noise may be correlated between evaluations. One
solution in the Gold Mining Problem is to update the RM state belief only the
first time the agent digs at any particular square, accounting for the fact
that all evaluations of  in that state yield the same result. Indeed, this
type of solution is used by many approaches in tabular MDPs with noisy
propositional evaluations [18, 57], but this solution does not scale to
infinite state spaces where propositional evaluations may be arbitrarily
linked between “similar” pairs of states.

We propose a form of abstraction model $\mathcal{M}:H\to\Delta U$ that
generalizes this solution by reasoning over states of the RM given the
history. $\mathcal{M}$ might internally model relevant correlations (such as
evaluations of  ) over the course of a trajectory while correcting for them
when predicting the RM state belief. Such a model needs to consider
propositions only insofar to predict a belief over RM states, and may forgo
predicting propositional evaluations altogether. In this case, the abstraction
model acts as the entire RM state inference algorithm.

######  Method 3 (TDM)

Given an abstraction model of the form $\mathcal{M}:H\to\Delta U$ predict
$\mathcal{M}(h_{t})$ directly.

###  5.4 Theoretical Analysis

Table 1: Inference algorithms of the RM state $u_{t}$. We highlight the prerequisite abstraction model, the target feature the abstraction model aims to predict, and the algorithm’s _consistency_ in MDPs and POMDPs. Inference | Abstraction | Target | Consistent | Consistent
---|---|---|---|---
Algorithm | Model |  | (MDPs) | (POMDPs)
Naive | $H\to 2^{\mathcal{AP}}$ | $\mathcal{L}(s_{t-1},a_{t-1},s_{t})$ | ✓ | ✗
IBU | $H\to\Delta(2^{\mathcal{AP}})$ | $\mathcal{L}(s_{t-1},a_{t-1},s_{t})$ | ✓ | ✗
TDM | $H\to\Delta U$ | $u_{t}$ | ✓ | ✓

We now compare the advantages of each algorithm, with our conclusions
summarized in Table 1. Consider the accuracy of an RM state inference
algorithm with respect to the optimal belief $\mathrm{Pr}(u_{t}|h_{t})$. This
largely depends on the veracity of the abstraction model $\mathcal{M}$, but
nonetheless, a desirable property of such an algorithm is that it can recover
the optimal RM state belief under an ideal abstraction model. We say an
algorithm is consistent if there exists such an abstraction model such that
the algorithm recovers this optimal belief.

######  Definition 5.3 (Consistency)

Consider an RM state inference algorithm $\mathcal{A}$ (as described in
Section 5) that takes an abstraction model of the form $\mathcal{M}:H\to Z$.
The algorithm is _consistent_ if there exists some $\mathcal{M^{\prime}}:H\to
Z$ such that for every history $h_{t}\in H$, running $\mathcal{A}$ with
$\mathcal{M^{\prime}}$ on $h_{t}$ produces the optimal RM state belief
$\tilde{u}_{t}=\mathrm{Pr}(u_{t}|h_{t})$.

In the case that $\mathcal{E}$ is an MDP, Naive, IBU, and TDM are all
consistent since there exists an abstraction model that can recover the
labelling function $\mathcal{L}$ (for Naive and IBU) and $u_{t}$ (for TDM)
with certainty. However, in the general case when $\mathcal{E}$ is a POMDP,
only TDM remains consistent. Proofs and counterexamples are provided in
Appendix A.

##  6 Experiments

We conduct experiments to investigate the following questions in the context
of Noisy RM Environments: (1) Can the proposed policies from Section 5 improve
RL performance and sample efficiency over methods that do not exploit task
structure? (2) Are these methods robust to noisy abstraction models? (3) How
well do the RM state inference algorithms model a belief over RM states?

Our experimental settings consider challenges that may arise when scaling to
complex, real-world environments—we target domains requiring temporally
extended behaviours under partial observability, high-dimensional
observations, and sparse and non-Markovian rewards. Abstraction models take
the form of noisy classifiers trained from data.

###  6.1 Environments

trash

Figure 2: Traffic Light (top left) and Kitchen (bottom left), are MiniGrids
with image observations, where key propositions are partially observable.
Colour Matching (right) is a MuJoCo robotics environment where the agent must
identify colour names by their RGB values to solve a task.

Our environments include the Gold Mining Problem as a toy environment, along
with two MiniGrid [8] environments with image observations and a MuJoCo
robotics environment (Figure 2). Full details on the environments are provided
in Appendix B.

Traffic Light is a partially observable MiniGrid where the agent must drive
along a road to pick up a package and then return home. A traffic light along
the road cycles between green, yellow, and red at stochastic intervals and the
agent receives a delayed penalty if it runs the red light. The agent only has
a forward-facing camera and it can drive forwards, backwards, wait, or make a
U-turn. We encode this task with an RM (Figure 6) with propositions for
running a red light, collecting the package, and returning home. Crucially,
the agent does not observe the light colour when entering the intersection _in
reverse_ , causing the agent to be uncertain about the evaluation of the red
light proposition.

Kitchen is a partially observable MiniGrid where a cleaning agent starts in
the foyer of a home and is tasked with cleaning the kitchen before leaving.
There are three chores: the agent must make sure the dishes are washed, the
stove is wiped, and the trash is emptied, but not every chore necessarily
requires action from the agent (e.g. there might be no dirty dishes to begin
with). However, the agent doesn’t know how clean the kitchen is until it
enters it. For each chore, a proposition represents whether that chore is
“done” (e.g. the dishes are clean) in the current state of the
environment—thus, the propositional evaluations are unknown to the agent until
it enters the kitchen. The RM for this task (omitted due to its size) uses the
automaton state to encode the subset of chores that are currently done and
gives a reward of 1 for leaving the house once the kitchen is clean.

In Colour Matching, the agent controls a robot car while observing LiDAR and
RGB observations of nearby objects. The agent observes an instruction with the
name of a colour (e.g. “blue”) and it must touch _only_ that pillar and then
enter the portal. Propositions for each pillar evaluate whether the agent is
touching it. The colours of the pillars (and in the instruction) are
randomized from a set of 18 possible colours in each episode, so to reliably
solve the task, the agent must learn the correct associations of colour names
to their RGB values.

###  6.2 Baselines

We consider the methods Naive, IBU, and TDM from Section 5 that use the
abstraction models described below. For RL experiments, we baseline against a
Memory-only method for general POMDPs that does not exploit the RM structure.
As an upper bound on performance, we compare against an Oracle agent that has
access to the labelling function. In the toy Gold Mining Problem, policies are
trained using Q-learning [49] with linear function approximation [38]. In all
other domains, policies are neural networks trained with PPO [45], and the
Memory-only policy is Recurrent PPO [24], a popular state-of-the-art deep RL
method for general POMDPs.

###  6.3 Abstraction Models

In the Gold Mining Problem, we consider toy abstraction models based on the
probabilities in Figure 1 as described in the running examples. TDM is
equivalent to the full RM state inference procedure for IBU except it only
updates the RM state belief when digging for the first time at the current
cell.

In all other domains, abstractions models are neural networks trained from
data. We collect training datasets comprising 2K episodes in each domain
(equalling 103K interactions in Traffic Light, 397K interactions in Kitchen,
and 3.7M interactions in Colour Matching), along with validation and test
datasets of 100 episodes each. This data is generated by random policy and
labelled with propositional evaluations from $\mathcal{L}$ and ground-truth RM
states. To obtain abstraction models, we train classifiers on their respective
target labels and we select optimal hyperparameters according to a grid
search.111For RL training on Traffic Light and Kitchen, we continue to
finetune the abstraction models using data collected by the policy— this is to
verify that partial observability is difficult to handle even with virtually
unlimited data and no distributional shift.

We note that all abstraction models are trained on equivalent data, ensuring a
fair comparison between different RM state inference algorithms. To verify
that these abstraction models are indeed noisy, we use the test set to
evaluate the precision and recall of a classifier trained to predict
propositional evaluations (Figure 5). We find that key propositions towards
decision making, such as running a red light in Traffic Light, or whether the
chores are done in Kitchen, are uncertain.

###  6.4 Results – Reinforcement Learning

Figure 3: RL curves averaged over 8 runs (error bars show standard error). TDM
exhibits strong performance in all domains without access to the labelling
function, while Recurrent PPO fails.

We train policies for each method and report RL learning curves in Figure 3.
The TDM policy performs well in all domains without access to the labelling
function, achieving similar performance to the Oracle agent. In contrast, the
Memory only agent, which does not exploit the RM structure, makes little
progress on any domain. Naive and IBU perform well in some cases, but can be
unstable—each fails completely on one of the partially observable domains.

Qualitatively, we observe the following noteworthy behaviours. In Gold Mining,
the Naive policy often digs at the nearby cell believed to yield gold with 0.6
probability (but in actuality yielding iron pyrite) before immediately heading
to the depot. IBU repeatedly digs at the same cell to increase its belief of
having obtained gold. Meanwhile, TDM learns a robust strategy of mining at
multiple different cells to maximize its chance of having obtained gold.

In Traffic Light, the Naive policy often runs the red light by driving in
reverse to get through the intersection faster. This shortcoming stems from
its inability to represent uncertainty about running the red light. In
Kitchen, IBU often stays in the foyer without ever entering the kitchen.
Despite this, the RM state belief erroneously reflects that all chores have a
high probability of being done. This is similar to Example 5.2—each chore is
initially “clean” with some small probability, and this is compounded over
time by the incorrect independence assumption. In reality, the state of the
chore is linked between timesteps (and doesn’t change unless the agent
intervenes).

###  6.5 Results – RM State Inference

Figure 4: Accuracy of RM state inference algorithms measured by log-likelihood
(higher is better) of the true RM state, averaged over 8 runs with lines
showing standard error. TDM predicts the RM state belief more accurately than
Naive and IBU.

We compare Naive, IBU, and TDM in terms of RM state inference accuracy. We use
each approach to obtain an RM state belief on trajectories from the test set
(which follows the same distribution as the training set). We measure the log-
likelihood of the true RM state under the belief, averaged over all
predictions. Since Naive makes a discrete prediction, we lower bound all log
likelihoods at $\ln{0.01}$ to avoid $\log{0}$. Results show that TDM
outperforms Naive and IBU on all domains in terms of predicting an RM state
belief. Note that all abstraction models were trained from the same dataset.

##  7 Related Work

Many recent works leverage structured task specifications such as RMs or
Linear Temporal Logic (LTL) in deep RL. However, the vast majority of these
works assume access to the perfect labelling function when acting, e.g. [55,
28, 32, 37, 17]. We note a few works that learn policies that do not rely on a
labelling function for execution. Kuo et al. [31] solve LTL tasks by encoding
them with a recurrent policy. Andreas et al. [2] and Oh et al. [41] learn
modular subpolicies and termination conditions, avoiding the need for a
labelling function, but these approaches are restricted to simple sequential
tasks.

Some recent works have considered applying formal languages to deep RL under a
noisy evaluation of propositions. Nodari and Cerutti [40] empirically show
that current RM algorithms are brittle to noise in the labelling function but
do not offer a solution. Tuli et al. [53] teach an agent to follow LTL
instructions in partially observable text-based games using the Naive method,
but only consider propositions that are observable to the agent. Umili et al.
[54] use RMs in visual environments with a method similar to IBU, while
Hatanaka et al. [23] update a belief over LTL formulas using IBU, but only
update the belief at certain time intervals. While these last three works
offer solutions that tackle noise for a specific setting, they do not consider
the efficacy of these methods more generally. Hence, we believe our framework
and the insights from this paper will provide a useful contribution.

Despite the large corpus of prior work in fully observable settings, RMs and
LTL have rarely been considered for general partially observable problems. We
believe this is due to the difficulty of working with an uncertain labelling
function when propositions are defined over a partially observed state. The
closest work by Toro Icarte et al. [51] applies RMs to POMDPs but only
considers propositions defined as a function of observations.

LTL has long been used for specification in motion planning [29], and some
works consider an uncertain labelling function or partial observability.
However, solutions nearly always depend on a small, tabular state space, while
we focus on solutions that scale to infinite state spaces. Ding et al. [12]
propose an approach assuming that propositions in a state occur
probabilistically in an i.i.d. manner. Ghasemi et al. [18], Verginis et al.
[57], Hashimoto et al. [22], and Cai et al. [5] consider a setting where
propositions are initially unknown but can be inferred through interactions.

##  8 Conclusion

This work proposes a framework for Reinforcement Learning with Reward Machines
where the interpretation or perception of the domain-specific vocabulary is
uncertain. To tackle this problem, we propose a suite of approaches that allow
the agent to leverage the structure of the task and exploit prior knowledge
through the use of _abstraction models_. Through theory and experiments we
find that exploiting task structure can significantly accelerate RL, but naive
modelling assumptions can lead to dangerous outcomes. We demonstrate how to
train an abstraction model that is aware of temporally correlated predictions
to mitigate this issue while scaling to environments with partial
observability or infinite state spaces. On the topic of societal impact, our
work aims to ameliorate the impact of noisy interpretations of symbols, which
can lead to dangerous outcomes. A limitation of TDM, our best-performing
method, is that it relies on a task-specific abstraction model (to predict the
state in the specific RM). For some real-world tasks, it might not be possible
to get enough training data to learn accurate abstraction models (some RM
transitions might very rarely be observed), so deploying TDM could lead to
poor outcomes. Future work could aim to train a more general-purpose
abstraction model that could predict the states in many RMs. We also note that
our proposed methods elucidate the internal decision-making process of RL
agents within a formal framework, potentially providing enhanced
interpretability. Finally, another direction for future work would be to
investigate relaxing the assumption that the RL agent has access to ground
truth rewards during training.

## Acknowledgements

We gratefully acknowledge funding from the Natural Sciences and Engineering
Research Council of Canada (NSERC), the Canada CIFAR AI Chairs Program, and
Microsoft Research. The second-to-last author also acknowledges funding from
the National Center for Artificial Intelligence CENIA FB210017, Basal ANID.
Resources used in preparing this research were provided, in part, by the
Province of Ontario, the Government of Canada through CIFAR, and companies
sponsoring the Vector Institute for Artificial Intelligence
(https://vectorinstitute.ai/partnerships/). Finally, we thank the Schwartz
Reisman Institute for Technology and Society for providing a rich multi-
disciplinary research environment.

## References

  * Aksaray et al. [2016] Derya Aksaray, Austin Jones, Zhaodan Kong, Mac Schwager, and Calin Belta.  Q-learning for Robust Satisfaction of Signal Temporal Logic Specifications.  In _Proceedings of the 55th IEEE Conference on on Decision and Control (CDC)_ , pages 6565–6570. IEEE, 2016.
  * Andreas et al. [2017] Jacob Andreas, Dan Klein, and Sergey Levine.  Modular multitask reinforcement learning with policy sketches.  In _Proceedings of the 34th International Conference on Machine Learning (ICML)_ , pages 166–175, 2017.
  * Åström [1965] Karl Johan Åström.  Optimal control of Markov processes with incomplete state information.  _Journal of Mathematical Analysis and Applications_ , 10(1):174–205, 1965.
  * Baker et al. [2022] Bowen Baker, Ilge Akkaya, Peter Zhokov, Joost Huizinga, Jie Tang, Adrien Ecoffet, Brandon Houghton, Raul Sampedro, and Jeff Clune.  Video pretraining (VPT): Learning to act by watching unlabeled online videos.  _Advances in Neural Information Processing Systems_ , 35:24639–24654, 2022.
  * Cai et al. [2021] Mingyu Cai, Shaoping Xiao, Baoluo Li, Zhiliang Li, and Zhen Kan.  Reinforcement learning based temporal logic control with maximum probabilistic satisfaction.  In _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 806–812. IEEE, 2021.
  * Camacho et al. [2019] Alberto Camacho, Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. McIlraith.  LTL and beyond: Formal languages for reward function specification in reinforcement learning.  In _Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 6065–6073, 2019.
  * Camacho et al. [2021] Alberto Camacho, Jacob Varley, Andy Zeng, Deepali Jain, Atil Iscen, and Dmitry Kalashnikov.  Reward machines for vision-based robotic manipulation.  In _Proceedings of the 2021 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 14284–14290, 2021.
  * Chevalier-Boisvert et al. [2023] Maxime Chevalier-Boisvert, Bolun Dai, Mark Towers, Rodrigo de Lazcano, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and Jordan Terry.  Minigrid & Miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks.  _CoRR_ , abs/2306.13831, 2023.
  * Corazza et al. [2022] Jan Corazza, Ivan Gavran, and Daniel Neider.  Reinforcement learning with stochastic reward machines.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 6429–6436, 2022.
  * De Giacomo et al. [2020] Giuseppe De Giacomo, Marco Favorito, Luca Iocchi, Fabio Patrizi, and Alessandro Ronca.  Temporal logic monitoring rewards via transducers.  In _Proceedings of the 17th International Conference on Knowledge Representation and Reasoning (KR)_ , pages 860–870, 2020.
  * DeFazio and Zhang [2021] David DeFazio and Shiqi Zhang.  Learning quadruped locomotion policies with reward machines.  _arXiv preprint arXiv:2107.10969_ , 2021.
  * Ding et al. [2011] Xu Chu Dennis Ding, Stephen L Smith, Calin Belta, and Daniela Rus.  LTL control in uncertain environments with probabilistic satisfaction guarantees.  _IFAC Proceedings Volumes_ , 44(1):3515–3520, 2011.
  * Du et al. [2023] Yuqing Du, Ksenia Konyushkova, Misha Denil, Akhil Raju, Jessica Landon, Felix Hill, Nando de Freitas, and Serkan Cabi.  Vision-language models as success detectors.  _arXiv preprint arXiv:2303.07280_ , 2023.
  * Fainekos et al. [2009] Georgios E Fainekos, Antoine Girard, Hadas Kress-Gazit, and George J Pappas.  Temporal logic motion planning for dynamic robots.  _Automatica_ , 45(2):343–352, 2009.
  * Finucane et al. [2010] Cameron Finucane, Gangyuan Jing, and Hadas Kress-Gazit.  LTLMoP: Experimenting with language, temporal logic and robot control.  In _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 1988–1993. IEEE, 2010.
  * Furelos-Blanco et al. [2020] Daniel Furelos-Blanco, Mark Law, Alessandra Russo, Krysia Broda, and Anders Jonsson.  Induction of subgoal automata for reinforcement learning.  In _Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 3890–3897, 2020.
  * Furelos-Blanco et al. [2023] Daniel Furelos-Blanco, Mark Law, Anders Jonsson, Krysia Broda, and Alessandra Russo.  Hierarchies of reward machines.  In _International Conference on Machine Learning_ , pages 10494–10541. PMLR, 2023.
  * Ghasemi et al. [2020] Mahsa Ghasemi, Erdem Arinc Bulgur, and Ufuk Topcu.  Task-oriented active perception and planning in environments with partially known semantics.  In _Proceedings of the 37th International Conference on Machine Learning (ICML)_ , 2020.
  * Goyal et al. [2019] Prasoon Goyal, Scott Niekum, and Raymond J Mooney.  Using natural language for reward shaping in reinforcement learning.  _arXiv preprint arXiv:1903.02020_ , 2019.
  * Hasanbeig et al. [2018] Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening.  Logically-constrained reinforcement learning.  _arXiv preprint arXiv:1801.08099_ , 2018.
  * Hasanbeig et al. [2020] Mohammadhosein Hasanbeig, Daniel Kroening, and Alessandro Abate.  Deep Reinforcement Learning with temporal logics.  In _Proceedings of the 18th International Conference on Formal Modeling and Analysis of Timed Systems (FORMATS)_ , pages 1–22, 2020.
  * Hashimoto et al. [2022] Kazumune Hashimoto, Natsuko Tsumagari, and Toshimitsu Ushio.  Collaborative rover-copter path planning and exploration with temporal logic specifications based on bayesian update under uncertain environments.  _ACM Transactions on Cyber-Physical Systems (TCPS)_ , 6(2):1–24, 2022.
  * Hatanaka et al. [2023] Wataru Hatanaka, Ryota Yamashina, and Takamitsu Matsubara.  Reinforcement learning of action and query policies with ltl instructions under uncertain event detector.  _IEEE Robotics and Automation Letters_ , 2023.
  * Hausknecht and Stone [2015] Matthew Hausknecht and Peter Stone.  Deep recurrent Q-learning for partially observable MDPs.  In _2015 AAAI Fall Symposium series_ , 2015.
  * He et al. [2015] Keliang He, Morteza Lahijanian, Lydia E Kavraki, and Moshe Y Vardi.  Towards manipulation planning with temporal logic specifications.  In _2015 IEEE international conference on robotics and automation (ICRA)_ , pages 346–352. IEEE, 2015.
  * Jiang et al. [2021] Yuqian Jiang, Suda Bharadwaj, Bo Wu, Rishi Shah, Ufuk Topcu, and Peter Stone.  Temporal-logic-based reward shaping for continuing reinforcement learning tasks.  In _Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 7995–8003, 2021.
  * Jothimurugan et al. [2019] Kishor Jothimurugan, Rajeev Alur, and Osbert Bastani.  A composable specification language for reinforcement learning tasks.  In _Proceedings of the 33nd Conference on Advances in Neural Information Processing Systems (NeurIPS)_ , volume 32, pages 13041–13051, 2019.
  * Jothimurugan et al. [2021] Kishor Jothimurugan, Suguman Bansal, Osbert Bastani, and Rajeev Alur.  Compositional reinforcement learning from logical specifications.  _Advances in Neural Information Processing Systems_ , 34:10026–10039, 2021.
  * Kress-Gazit et al. [2009] Hadas Kress-Gazit, Georgios E Fainekos, and George J Pappas.  Temporal-logic-based reactive mission and motion planning.  _IEEE transactions on robotics_ , 25(6):1370–1381, 2009.
  * Kunze et al. [2011] Lars Kunze, Mihai Emanuel Dolha, and Michael Beetz.  Logic programming with simulation-based temporal projection for everyday robot object manipulation.  In _2011 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 3172–3178. IEEE, 2011.
  * Kuo et al. [2020] Yen-Ling Kuo, Boris Katz, and Andrei Barbu.  Encoding formulas as deep networks: Reinforcement learning for zero-shot execution of LTL formulas.  In _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 5604–5610. IEEE, 2020.
  * León et al. [2022] Borja G León, Murray Shanahan, and Francesco Belardinelli.  In a nutshell, the human asked for this: Latent goals for following temporal specifications.  In _Proceedings of the 10th International Conference on Learning Representations (ICLR)_ , 2022.
  * Li et al. [2017] Xiao Li, Cristian Ioan Vasile, and Calin Belta.  Reinforcement learning with temporal logic rewards.  In _Proceedings of the 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 3834–3839, 2017.
  * Li et al. [2018] Xiao Li, Yao Ma, and Calin Belta.  A policy search method for temporal logic specified reinforcement learning tasks.  In _Proceedings of the 2018 Annual American Control Conference (ACC)_ , pages 240–245. IEEE, 2018.
  * Lifshitz et al. [2023] Shalev Lifshitz, Keiran Paster, Harris Chan, Jimmy Ba, and Sheila McIlraith.  STEVE-1: A generative model for text-to-behavior in Minecraft.  _arXiv preprint arXiv:2306.00937_ , 2023.
  * Littman et al. [2017] Michael L Littman, Ufuk Topcu, Jie Fu, Charles Isbell, Min Wen, and James MacGlashan.  Environment-independent task specifications via GLTL.  _arXiv preprint arXiv:1704.04341_ , 2017.
  * Liu et al. [2022] Jason Xinyu Liu, Ankit Shah, Eric Rosen, George Konidaris, and Stefanie Tellex.  Skill transfer for temporally-extended task specifications.  _arXiv preprint arXiv:2206.05096_ , 2022.
  * Melo and Ribeiro [2007] Francisco S Melo and M Isabel Ribeiro.  Q-learning with linear function approximation.  In _International Conference on Computational Learning Theory_ , pages 308–322. Springer, 2007.
  * Neary et al. [2021] Cyrus Neary, Zhe Xu, Bo Wu, and Ufuk Topcu.  Reward machines for cooperative multi-agent reinforcement learning.  In _Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , pages 934–942, 2021.
  * Nodari and Cerutti [2023] Lorenzo Nodari and Federico Cerutti.  Assessing the robustness of intelligence-driven reinforcement learning.  In _2023 IEEE International Workshop on Technologies for Defense and Security (TechDefense)_ , pages 439–443. IEEE, 2023.
  * Oh et al. [2017] Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmeet Kohli.  Zero-shot Task Generalization with Multi-Task Deep Reinforcement Learning.  In _International Conference on Machine Learning_ , pages 2661–2670. PMLR, 2017.
  * Pnueli [1977] Amir Pnueli.  The temporal logic of programs.  In _18th Annual Symposium on Foundations of Computer Science (sfcs 1977)_ , pages 46–57. IEEE, 1977.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_ , pages 8748–8763. PMLR, 2021.
  * Rens and Raskin [2020] Gavin Rens and Jean-François Raskin.  Learning non-Markovian Reward Models in MDPs.  _arXiv preprint arXiv:2001.09293_ , 2020.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Shah et al. [2024] Ameesh Shah, Cameron Voloshin, Chenxi Yang, Abhinav Verma, Swarat Chaudhuri, and Sanjit A Seshia.  Deep policy optimization with temporal logic constraints.  _arXiv preprint arXiv:2404.11578_ , 2024.
  * Shah et al. [2020] Ankit Shah, Shen Li, and Julie Shah.  Planning with Uncertain Specifications (PUnS).  _IEEE Robotics and Automation Letters_ , 5(2):3414–3421, 2020.
  * Sun and Shoukry [2024] Xiaowu Sun and Yasser Shoukry.  Neurosymbolic motion and task planning for linear temporal logic tasks.  _IEEE Transactions on Robotics_ , 2024.
  * Sutton and Barto [2018] Richard S. Sutton and Andrew G. Barto.  _Reinforcement Learning: An Introduction_.  MIT press, second edition, 2018.
  * Toro Icarte et al. [2018] Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. McIlraith.  Using reward machines for high-level task specification and decomposition in reinforcement learning.  In _Proceedings of the 35th International Conference on Machine Learning (ICML)_ , pages 2107–2116, 2018.
  * Toro Icarte et al. [2019] Rodrigo Toro Icarte, Ethan Waldie, Toryn Q. Klassen, Rick Valenzano, Margarita P. Castro, and Sheila A. McIlraith.  Learning reward machines for partially observable reinforcement learning.  In _Proceedings of the 33nd Conference on Advances in Neural Information Processing Systems (NeurIPS)_ , pages 15497–15508, 2019.
  * Toro Icarte et al. [2022] Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. McIlraith.  Reward machines: Exploiting reward function structure in reinforcement learning.  _Journal of Artificial Intelligence Research_ , 73:173–208, 2022.
  * Tuli et al. [2022] Mathieu Tuli, Andrew C. Li, Pashootan Vaezipoor, Toryn Q. Klassen, Scott Sanner, and Sheila A. McIlraith.  Learning to follow instructions in text-based games.  In _Proceedings of the 36rd Conference on Advances in Neural Information Processing Systems (NeurIPS)_ , 2022.
  * Umili et al. [2023] Elena Umili, Francesco Argenziano, Aymeric Barbin, Roberto Capobianco, et al.  Visual reward machines.  In _Proceedings of the 17th International Workshop on Neural-Symbolic Learning and Reasoning, La Certosa di Pontignano, Siena, Italy_ , pages 3–5, 2023.
  * Vaezipoor et al. [2021] Pashootan Vaezipoor, Andrew Li, Rodrigo Toro Icarte, and Sheila McIlraith.  LTL2Action: Generalizing LTL instructions for multi-task RL.  In _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , pages 10497–10508, 2021.
  * Velasquez et al. [2021] Alvaro Velasquez, Andre Beckus, Taylor Dohmen, Ashutosh Trivedi, Noah Topper, and George Atia.  Learning probabilistic reward machines from non-Markovian stochastic reward processes.  _CoRR_ , abs/2107.04633, 2021.  URL http://arxiv.org/abs/2107.04633.
  * Verginis et al. [2022] Christos Verginis, Cevahir Koprulu, Sandeep Chinchali, and Ufuk Topcu.  Joint learning of reward machines and policies in environments with partially known semantics.  _arXiv preprint arXiv:2204.11833_ , 2022.
  * Xu and Topcu [2019] Zhe Xu and Ufuk Topcu.  Transfer of temporal logic formulas in reinforcement learning.  In _Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 4010–4018, 2019.
  * Xu et al. [2020] 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.  In _Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS)_ , volume 30, pages 590–598, 2020.
  * Xu et al. [2021] Zhe Xu, Bo Wu, Aditya Ojha, Daniel Neider, and Ufuk Topcu.  Active finite reward automaton inference and reinforcement learning using queries and counterexamples.  In _International Cross-Domain Conference for Machine Learning and Knowledge Extraction_ , pages 115–135. Springer, 2021.
  * Yuan et al. [2019] Lim Zun Yuan, Mohammadhosein Hasanbeig, Alessandro Abate, and Daniel Kroening.  Modular deep reinforcement learning with temporal logic specifications.  _arXiv preprint arXiv:1909.11591_ , 2019.
  * Zhang et al. [2023] Hao Zhang, Hao Wang, and Zhen Kan.  Exploiting transformer in sparse reward reinforcement learning for interpretable temporal logic motion planning.  _IEEE Robotics and Automation Letters_ , 2023.
  * Zheng et al. [2022] Xuejing Zheng, Chao Yu, and Minjie Zhang.  Lifelong reinforcement learning with temporal logic formulas and reward machines.  _Knowledge-Based Systems_ , 257:109650, 2022.

##  Appendix A Additional Definitions and Theorems

See 4.1

###### Proof.

The POMDP $\mathcal{K}=\langle
S^{\prime},O^{\prime},A^{\prime},P^{\prime},R^{\prime},\omega^{\prime},\mu^{\prime}\rangle$,
where $S^{\prime}=S\times U$, $O^{\prime}=O$, $A^{\prime}=A$,

$\displaystyle
P^{\prime}((s_{t+1},u_{t+1})|(s_{t},u_{t}),a_{t})=P(s_{t+1}|s_{t},a_{t})\cdot\mathbbm{1}[\delta_{u}(u_{t},\mathcal{L}(s_{t},a_{t},s_{t+1}))=u_{t+1}],$
$\displaystyle
R^{\prime}((s_{t},u_{t}),a_{t},(s_{t+1},u_{t+1}))=\delta_{r}(u_{t},\mathcal{L}(s_{t},a_{t},s_{t+1})),$
$\displaystyle\omega^{\prime}(o_{t}|(s_{t},u_{t}),a_{t})=O(o_{t}|s_{t},a_{t}),$
$\displaystyle\mu^{\prime}(s,u)=\mu(s)\mathbbm{1}[u=u_{1}]$

is equivalent to the Noisy RM Environment
$\langle\mathcal{E},\mathcal{R},\mathcal{L},\mathcal{M}\rangle$ in the
following sense. For any policy $\pi(a_{t}|h_{t},z_{1:t})$ in the noisy RM
environment we can obtain an equivalent policy
$\pi^{\prime}(a_{t}|h_{t})=\pi(a_{t}|h_{t},\mathcal{M}(h_{1}),\ldots,\mathcal{M}(h_{t}))$
for $\mathcal{K}$ that achieves the same expected discounted return and vice-
versa. To see why the reverse direction is true, we note that
$z_{1:t}=\mathcal{M}(h_{1}),\ldots,\mathcal{M}(h_{t})$ is a function of
$h_{t}$ for a fixed abstraction model $\mathcal{M}$. These policies behave
identically given the same history $h_{t}$. ∎

See 4.2

###### Proof.

Consider any policy $\pi(a_{t}|h_{t},z_{1:t})$ for $\mathcal{P}$ and notice
that the sequence of outputs from the abstraction model $\mathcal{M}$ is a
function of the history $h_{t}$, i.e. $z_{1:t}=f(h_{t})$. Thus, a valid policy
in $\mathcal{P}^{\prime}$ is
$\pi^{\prime}(a_{t}|h_{t},z^{\prime}_{1:t})=\pi_{*}(a_{t}|h_{t},f(h_{t}))$
(where $z^{\prime}_{1:t}$ are the outputs from the abstraction model
$\mathcal{M}^{\prime}$ but do not affect the policy $\pi^{\prime}$).
Similarly, a policy for $\mathcal{P^{\prime}}$ can be used to obtain a policy
for $\mathcal{P}$ that is identical. Thus, $\mathcal{P}$ and
$\mathcal{P}^{\prime}$ are equivalent. ∎

See 4.3

###### Proof.

Consider that $\mathcal{E}$ is an MDP. At time $t$, denote the sequence of
outputs from the labelling function up to time $t$ by $\sigma_{1:{t-1}}$,
where
$\sigma_{i}=\mathcal{L}(s_{i},a_{i},s_{i+1})=\mathcal{L}(o_{i},a_{i},o_{i+1})$
(we assume $s_{i}=o_{i}$ since $\mathcal{E}$ is an MDP). Consider a policy
$\pi^{\prime}(a_{t}|h_{t},z_{1:t},\sigma_{1:t-1})$ for $\mathcal{P}^{\prime}$
that conditions on all observable information (including the outputs of the
labelling function) up to time $t$. However, since $\mathcal{E}$ is fully
observable, the labelling function outputs $\sigma_{1:t}$ can be represented
as a function of the history $h_{t}$, i.e. $\sigma_{1:t}=f(h_{t})$. Then the
policy $\pi(a_{t}|h_{t},z_{1:t})=\pi^{\prime}(a_{t}|h_{t},z_{1:t},f(h_{t}))$
for $\mathcal{P}$ is identical to $\pi^{\prime}$. Similarly, given a policy
$\pi(a_{t}|h_{t},z_{1:t})$ for $\mathcal{P}$, we can obtain an identical
policy
$\pi^{\prime}(a_{t}|h_{t},z_{1:t},\sigma_{1:t})=\pi(a_{t}|h_{t},z_{1:t})$ for
$\mathcal{P}^{\prime}$.

Note that if $\mathcal{E}$ is a POMDP, this is not true, since the outputs of
the labelling function $\sigma_{1:{t-1}}$ (which is a function of the history
of states and actions) cannot be determined from the history of observations
and actions. For an explicit counterexample, consider that $\mathcal{E}$ is a
two-state POMDP with states $s^{(0)}$ and $s^{(1)}$ where the initial state is
equally like to be $s^{(0)}$ or $s^{(1)}$, and that state persists for the
remainder of the episode regardless of the agent’s actions. The agent receives
a single, uninformative observation $o$ regardless of the state. Let there be
two actions $a^{(0)}$ and $a^{(1)}$, where a reward of 1 is received for
taking action $a^{(i)}$ in state $s^{(i)}$ (a reward of 0 is received
otherwise). Let there be a single proposition $A$ that holds for a transition
$(s_{t},a_{t},s_{t+1})$ if $s_{t}=s^{(0)}$. For the Noisy RM Environment
$\mathcal{P}$ (where the agent cannot observe $\mathcal{L}$), the optimal
policy receives no information about the current state and has no better
strategy than to randomly guess between $a^{(0)}$ and $a^{(1)}$ at each
timestep. In $\mathcal{P}^{\prime}$ (where the agent can observe
$\mathcal{L}$), the agent can deduce the state based on whether $A$ holds or
not, enabling a strategy that receives a reward of 1 on each step. There is no
identical policy in $\mathcal{P}$ that achieves this, thus the problems are
not equivalent. ∎

###### Proposition A.1

TDM is consistent.

###### Proof.

This is immediate because the optimal RM state belief
$\mathrm{Pr}(u_{t}|h_{t})$ is a function of $h_{t}$. Thus, choose
$\mathcal{M}(h_{t})=\mathrm{Pr}(u_{t}|h_{t})$ and we are done. ∎

###### Lemma A.2

If $\mathcal{E}$ is fully observable, then there exist grounding models
$\mathcal{M}_{1}:H\to 2^{\mathcal{AP}}$,
$\mathcal{M}_{2}:H\to\Delta(2^{\mathcal{AP}})$, and
$\mathcal{M}_{3}:H\to\Delta U$ such that
$\mathcal{M}_{1}(h_{t})=\mathcal{L}(s_{t-1},a_{t-1},s_{t})$,
$\mathcal{M}_{2}(h_{t})[\mathcal{L}(s_{t-1},a_{t-1},s_{t})]=1$, and
$\mathcal{M}_{3}(h_{t})[u_{t}]=1$ for all $h_{t}\in H$. In other words,
$\mathcal{M}_{1}$, $\mathcal{M}_{2}$ recover the labelling function
$\mathcal{L}$ and $\mathcal{M}_{3}$ recovers the RM state at time $t$ with
certainty.

###### Proof.

Since $\mathcal{E}$ is an MDP, we assume states $s_{t}$ and observations
$o_{t}$ are interchangeable. The desired statements immediately result from
the fact that the labelling function $\mathcal{L}(s_{t-1},a_{t-1},s_{t})$ and
$u_{t}$ are deterministic functions of the history $h_{t}$. ∎

###### Proposition A.3

If $\mathcal{E}$ is fully observable, then Naive and IBU are consistent.

###### Proof.

Choose the abstraction models $\mathcal{M}_{1}$, $\mathcal{M}_{2}$ and
$\mathcal{M}_{3}$ as in Lemma A.2. Running Naive with $\mathcal{M}_{1}$
precisely mirrors the procedure for computing RM states $u_{t}$ with the
ground-truth labelling function $\mathcal{L}$, and therefore recovers $u_{t}$
with certainty.

For IBU with $\mathcal{M}_{2}$, we perform a simple proof by induction. At any
time $t$, we propose that the predicted belief $\tilde{u}_{t}$ assigns full
probability to the ground-truth RM state $u_{t}$. At time $1$, this is true by
the initialization of the algorithm. At time $t>1$, we have

$\displaystyle\tilde{u}_{t}(u)$ $\displaystyle=\sum_{\sigma\in
2^{\mathcal{AP}},u^{\prime}\in
U}{\mathbbm{1}[\delta_{u}(u^{\prime},\sigma)=u]\cdot\tilde{u}_{t-1}(u^{\prime})}\cdot\mathcal{M}(h_{t})[\sigma]$
$\displaystyle=\sum_{\sigma\in
2^{\mathcal{AP}}}{\mathbbm{1}[\delta_{u}(u_{t-1},\sigma)=u]\cdot\mathcal{M}(h_{t})[\sigma]}$
$\displaystyle=\mathbbm{1}[\delta_{u}(u_{t-1},L(s_{t-1},a_{t-1},s_{t}))=u]$
$\displaystyle=\mathbbm{1}[u_{t}=u]$

∎

###### Proposition A.4

Naive is not necessarily consistent in general POMDP environments
$\mathcal{E}$.

###### Proof.

This result stems from the fact that Naive cannot model an RM state belief of
a strictly probabilistic nature.

Consider a POMDP with two states, $s^{(0)}$ and $s^{(1)}$, where the initial
state is equally likely to be $s^{(0)}$ or $s^{(1)}$, and that state persists
for the remainder of the episode regardless of the agent’s actions. The agent
receives a single, uninformative observation $o$ regardless of the state.
Thus, the agent always observes the same sequence of observations
$(o,o,\ldots)$ and the sequence of states is equally likely to be either
$(s^{(0)},s^{(0)},\ldots)$ or $(s^{(1)},s^{(1)},\ldots)$.

Let there be a single proposition $A$ that holds when the agent is currently
in state $s^{(0)}$. Let the RM $\mathcal{R}$ have two states: an initial state
$u^{(0)}$ that transitions to the state $u^{(1)}$ when the proposition $A$
holds. The ground-truth RM state belief is given by
$\mathrm{Pr}(u_{t}=u^{(1)}|h_{t})=0.5$ for all timesteps $t\geq 2$. This
belief cannot be captured by Naive under any abstraction model, thus, Naive is
not consistent. ∎

###### Proposition A.5

IBU is not necessarily consistent in general POMDP environments $\mathcal{E}$.

###### Proof.

Suppose for a contradiction that IBU is consistent and therefore, produces the
optimal belief $\tilde{u}_{t}=\mathrm{Pr}(u_{t}|h_{t})$ for some
$\mathcal{M}$.

Consider the same POMDP as in Proposition A.4, with one small change. Now,
while in any state $s^{(i)}$ the observation emitted is $o$ with 0.5
probability or $o^{(i)}$ (revealing the state) with 0.5 probability. Consider
a history $h_{t}$ with the observation sequence $o,o^{(1)}$. After seeing the
observation $o$, it must be the case that $\tilde{u}_{2}$ assigns 0.5
probability to both $u^{(0)}$ and $u^{(1)}$, as before. Then after seeing the
observation $o^{(1)}$, it becomes certain that the persistent state is
$s^{(1)}$, and therefore the optimal RM state belief assigns probability 1 to
$u^{(0)}$. However, regardless of how $\mathcal{M}(h_{t})$ is assigned, it is
impossible to achieve this optimal belief for $\tilde{u}_{3}$. This is since
$\tilde{u}_{2}[u^{(1)}]=0.5$ but there are no RM transitions out of $u^{(1)}$,
so $\tilde{u}_{3}[u^{(1)}]\geq 0.5$. ∎

##  Appendix B Experimental Details

Figure 5:  Precision and recall of a classifier trained to predict occurrences
of propositions. Key propositions in each domain are uncertain. Values are
averaged over 8 training runs, with lines showing standard error.

###  B.1 Gold Mining Experiments

The Gold Mining Problem is described in Example 3.2. We also introduce a small
(Markovian) penalty of 0.02 each time the agent selects a movement action to
incentivize the agent towards shorter solutions.

Policy models. The Oracle baseline learns a Q-value for each (_location_ , _RM
state_ , _action_) combination without memory or function approximation. The
Memory only baseline and all the proposed methods are conditioned on six
additional binary features corresponding to each square with gold or iron
pyrite (i.e. where the agent places non-zero probability of  ) that indicates
whether the agent has previously mined at that location. We use this as a
tractable alternative to representing the entire history without neural
network encoders.

All approaches except Oracle use a linear decomposition of Q-values to allow
for generalization and to reduce the number of estimated Q-values. Naive, IBU,
and TDM use the following approximation.

$\displaystyle
Q(\mathrm{\emph{location}},\tilde{u},\mathrm{\emph{memory}}_{1:6},\mathrm{\emph{action}})$
$\displaystyle=\sum_{u\in
U}\Bigl{[}{\tilde{u}(u)\cdot\bigl{[}Q_{1}(u)+Q_{2}(\mathrm{\emph{location}},u,\mathrm{\emph{action}})+\frac{1}{6}\sum_{i=1}^{6}{Q_{3}(\mathrm{\emph{location}},u,\mathrm{\emph{memory}}_{i},\mathrm{\emph{action}})}\bigr{]}}\Bigr{]}$

The Memory only baseline use the following approximation.

$\displaystyle
Q(\mathrm{\emph{location}},\mathrm{\emph{memory}}_{1:6},\mathrm{\emph{action}})$
$\displaystyle=Q_{1}(\mathrm{\emph{location}},\mathrm{\emph{action}})+\frac{1}{6}\sum_{i=1}^{6}{Q_{2}(\mathrm{\emph{location}},\mathrm{\emph{memory}}_{i},\mathrm{\emph{action}})}$

Hyperparameters. All methods use a learning rate of $0.01$, a discount factor
of $0.99$, and a random action probability of $\epsilon=0.2$.

Evaluation Details. All methods are trained for $1$M steps, and the policy is
evaluated every $10$K steps without $\epsilon$-greedy actions. Since the
evaluation policy and the environment are deterministic, each evaluation step
records the return from a single episode.

###  B.2 MiniGrid Experiments

In the Traffic Light domain, the task is described by the RM in Figure 6.
There are propositions corresponding to reaching the squares with the package,
the home, and for crossing a red light. The light colour cycles between green,
yellow, and red, where the duration of the green and red lights are randomly
sampled. The yellow light always lasts a single timestep and serves to warn
the agent of the red light.

The RM for the Kitchen domain (not shown) has 9 states, encoding all possible
subsets of the completed chores plus one additional terminal state that is
reached upon leaving the house. The episode is initialized such that each
chore needs cleaning with $\frac{2}{3}$ probability, and a chore can be
completed by visiting that square. The agent can observe tasks that are
completed when inside the kitchen. There is one proposition per chore marking
whether that chore is done (regardless of whether the agent can observe this)
and a proposition for leaving the house through the foyer. We implement a
small cost of $-0.05$ for opening the kitchen door and performing each task,
making it so the agent must do so purposefully.

$u^{(0)}$$u^{(1)}$$u^{(2)}$$u^{(3)}$$u^{(4)}$$\langle\text{package},1\rangle$$\langle\text{red},0\rangle$$\langle\text{home},1\rangle$$\langle\text{red},0\rangle$$\langle\text{package},1\rangle$$\langle\text{home},-1\rangle$
Figure 6: An RM for Traffic Light. The goal is to pick up the package and
return home (each stage gives a reward of 1). If the agent crosses a red
light, it gets a delayed penalty upon returning home. To simplify formulas on
edge transitions, we assume all propositions occur mutually exclusively, and
if no transition condition is satisfied, the RM remains in the same state,
receiving 0 reward.

Network architectures: A policy is composed of an observation encoder followed
by a policy network. The observation encoder takes in the current environment
observation $o_{t}$ as well as a belief over RM states (when applicable) and
produces an encoding. This encoding is fed to a GRU layer to produce an
encoding of the history. The policy network takes the history encoding and
feeds it to an actor and critic network, which predicts an action distribution
and value estimate, respectively. We use ReLU activations everywhere except
within the critic, which use Tanh activations. The observation encoder
consists of two 64-unit hidden layers and produces a 64-dimensional encoding.
We use a single GRU layer with a 64-dimensional history encoding. The actor
and critic both use two 64-dimensional hidden layers. The abstraction models
use a separate, but identically structured observation encoder and GRU layer.
The history encoding is fed to a single, linear output layer.

###  B.3 Colour Matching Experiment

The atomic propositions in the Colour Matching domain are $\\{a,b,c,d\\}$,
where $a$ means the agent is currently in range of the target pillar, and $b$
and $c$ mean the agent is in range of the second and third pillars,
respectively. The order of the three pillars is specified at the beginning of
the episode via an index vector, where each index corresponds to one of the 18
possible colours.

The RM for this task has 6 states and encodes two pieces of information:
whether the target pillar was ever reached, and the last pillar the agent
visited. Each time the agent visits an incorrect pillar, a negative reward of
-0.2 is issued, but this penalty is not applied if the agent visits the same
pillar multiple times in succession. A reward of 1 is given for visiting the
target pillar, and then for subsequently going to the portal. We omit a
visualization of the RM due to the excessive number of edges.

Network architectures. The policy and grounding model networks are similar to
those in the previous experiments. The policy uses an observation encoder with
two 256-unit hidden layers and a 128-unit output layer. This is fed to a
single GRU layer with a hidden size of 128. The actor has one encoding layer
with hidden size 128, followed by linear layers to predict a mean and standard
deviation for continuous actions. The critic has two 128-unit hidden layers.

The abstraction models for Thresholding and IBU are MLPs with five 128-unit
hidden layers (the environment is nearly fully observable and encoding the
history is not necessary for predicting the labelling function). The
abstraction model for TDM first predicts evaluations of propositions at each
step, and then aggregates the history of these predictions with history of
observations, before predicting the RM state belief. We find this approach to
work well with a limited dataset as it can also exploit labels corresponding
to the evaluations of individual propositions. The network architecture is as
follows. An observation encoder first produces a 128-dimensional embedding
using three 128-unit hidden layers. This is fed to a decoder that predicts
propositional probabilities using one 128-unit hidden layer. The observation
embedding and the outputs of this decoder are both fed through 2 GRU layers
with hidden size 128, and finally, another decoder uses the memory from the
GRU layers to predict the RM state belief.

###  B.4 PPO Training Details

We report all hyperparameter settings for the Deep RL experiments in Table 2.
Experiments were conducted on a compute cluster. Each run occupied 1 GPU, 16
CPU workers, and 12G of RAM. Runs lasted approximately 18 hours for Colour
Matching, and 5 hours for Traffic Light and Kitchen. The Gold Mining
experiments took negligible time and were run on a personal computer. The
total runtime for these experiments is estimated at 1100 GPU hours. Prior
experiments that did not make it into the paper accounted for at least 1000
GPU hours. We used the implementation of PPO found here under an MIT license:
https://github.com/lcswillems/torch-ac.

Table 2: Hyperparameters for deep RL experiments PPO hyperparameters | Traffic Light | Kitchen | Colour Matching
---|---|---|---
Env. steps per update | 32768 | 32768 | 32000
Number of epochs | 8 | 8 | 8
Minibatch size | 2048 | 2048 | 8000
Discount factor ($\gamma$) | 0.97 | 0.99 | 0.999
Learning rate | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$
GAE-$\lambda$ | 0.95 | 0.95 | 0.95
Entropy coefficient | 0.01 | 0.01 | 0.001
Value loss coefficient | 0.5 | 0.5 | 0.5
Gradient Clipping | 0.5 | 0.5 | 5
PPO Clipping ($\varepsilon$) | 0.2 | 0.2 | 0.2
LSTM Backpropagation Steps | 4 | 4 | 4
Abstraction model hyperparameters |  |  |
Env. steps per update | 32768 | 32768 | 32000
Number of epochs | 8 | 8 | 8
Minibatch size | 2048 | 2048 | 8000
Learning rate | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$
LSTM Backpropagation Steps | 4 | 4 | 4