# An extension of Arakeljan’s Theorem

###### Abstract

Arakeljan’s Theorem provides conditions on a relatively closed subset $F$ of a
domain $G\subset\mathbb{C}$, such that any continuous function
$f:F\rightarrow\mathbb{C}$ that is analytic in $F^{\circ}$, can be
approximated by analytic functions defined on $G$. In this paper we will
extend Arakeljan’s theorem by adding the extra requirement that the analytic
functions that approximate $f$ may also be chosen to be bounded on a closed
set $C\subset G.$ In [1] the same problem has been considered but for the
specific case that $G=\mathbb{C}$. In this paper we will extend the result in
[1] and show that is true for an arbitrary $G$, provided that $F$ and $C$
satisfy a certain condition in $G$. Additionally, we will show that the result
holds always true when $G$ is simply connected.

Spyros Pasias

Orcid:0000-0001-6611-0155
<EMAIL_ADDRESS>
Limassol, Cyprus

Keywords: Arakeljan’s Theorem, $G-$holes, Arakeljan set, $G-$hole independent,
strict hole

## Introduction

In this paper we will generalize an important theorem in the field of Complex
approximation, namely we will generalize _Arakeljan’s Theorem_. It is well
known by Weirstrass Approximation Theorem that in a real closed interval, any
continuous function can be approximated uniformly by polynomials. In the
complex case things are different. Since polynomials are analytic, by Morera’s
Theorem it follows that if $f$ is uniformly approximated by polynomials, then
$f$ better be an analytic function. However, $f$ being analytic is not enough
to guarantee uniform approximation by polynomials. This is indeed the case if
we let $f(z)={1}/{z}$ defined on the annulus
$F=\\{z\in\mathbb{C}:\frac{1}{2}<z<2\\}.$ Even though $f$ is analytic in $F$,
in this case $f$ cannot be approximated by polynomials because by Cauchy’s
theorem if $f$ was approximated by polynomials, the contour integral around
the unit circle would have to be equal to zero. However direct computation
shows it is equal to $\frac{1}{2\pi}$ instead. Of course this happens because
$f$ cannot be analytically continued inside the unit circle, which occurs
because $F$ has a bounded connected component(a hole) in its complement.
A special case of _Runge’s Theorem_ states that any function $f$ that is
analytic on a domain $G$ which contains a compact set $F$, can be uniformly
approximated by polynomials provided $F$ has a connected complement. Runge’s
Theorem is a classical theorem and it essentially serves as the starting point
of Complex Approximation. The theorem in all of its generality does not
require $F$ to have a connected complement, and thus the approximation in
general is not by polynomials but rather by rational functions. The theorem
also asserts that the poles of those rational functions may be chosen freely
to lie anywhere in the respective connected component on $G\setminus F$ they
lie at. As a corollary when $G\setminus F$ has a single component the pole may
be chosen to be at ”$\infty$”, thus $f$ may be approximated by polynomials
rather than rational functions. Another well known theorem is _Mergelyan’s
Theorem_ which improves Runge’s Theorem when $F$ has a connected complement.
The theorem states that any function that is continuous on a compact set
$F\subset\mathbb{C}$ and analytic on $F^{o}$ can be uniformly approximated by
polynomials on $F$, provided our set $F$ has a connected complement.
Arakaljan’s Theorem on the other hand deals with analytic functions defined in
more general sets $F$ that are neither compact nor do they have connected
complement. Consequently we don’t expect the approximation to be by
polynomials.
To this end, let $G\subset\mathbb{C}$ be an arbitrary domain and $F\subset G$
a relatively closed subset of $G$. Arakeljan’s Theorem provides conditions
that determine whether a function $f\in A(F)$ can be approximated on $F$ by
functions $g\in Hol(G).$

$\displaystyle Hol(G)=\\{g:g\text{ analytic in }G\\}$ $\displaystyle
A(F)=\\{f:f\text{ analytic on }F^{o},\text{ continuous on F}\\}$

The main result in [1] generalizes Arakeljan’s Theorem when $G=\mathbb{C}$. In
[1] the authors consider two closed sets $F$ and $C$ and find necessary and
sufficient conditions so that every function defined on $F\subset\mathbb{C}$
can be approximated by entire functions that are bounded on $C$. In this paper
we will extend this even further by considering the result for a more general
$G$. We will see that if our sets $C$ and $F$ satisfy a certain condition in
$G$, or if $G$ is a simply connected then Arakeljan’s theorem can be extended.
The results in this paper fit in the category of joint approximation. We
provide some relevant articles where similar problems have been considered. In
particular, articles ([5]-[8]) are devoted to various problems regarding
bounded approximation by polynomials. Whereas articles ([9]-[11]) are devoted
to problems regarding the joint approximation by analytic functions in Banach
Spaces.

## Description of Arakelan sets

In the proof of Arakeljan’s Theorem in ([2], p. 142-144) the definition used
for $F$ to be an Arakeljan set is different than definition we will use in
this paper. The definition used in ([2], p. 142) is more topological but it
turns out that both definitions are equivalent. The definition we will use in
this paper is also used in [1] to prove an extension of Arakeljan’s Theorem
for the case $G=\mathbb{C}$.
The definition we will use for an Arakeljan set in this paper is based on the
concept of a $G-$hole.

Definition 1. Let $G\subset\mathbb{C}$ be an arbitrary domain and $F\subset G$
be a relatively closed subset of $G$. A non empty connected component $g$ of
$G\setminus F$ is called a $G-$hole of $F$ if it can be enclosed in a compact
subset $L\subset G.$

Remark 1. It is important to note that a $G-$ hole of $F$ is essentially a
bounded connected component of the complement (a hole) whose boundary does not
intersect with the boundary of $G$.

Now that we defined what a hole is in the setting of Arakeljan’s theorem on an
arbitrary domain, we are ready to define Arakeljan sets.

Definition 2. Let $G$ be an arbitrary domain and let $F$ be a relatively
closed subset, then we call $F$ an Arakeljan set if:

  1. 1.

The set $F$ has no $G-$holes.

  2. 2.

For any connected compact set $K\subset G$ such that $\partial K$ is the union
of disjoint jordan curves111So that locally, the neighborhood around any point
on $\partial K$ looks like an open interval., the set
$H\equiv\\{\bigcup\\{h\\}:h\text{ is a $G$-hole of }F\cup K\\}$ can be
contained in a compact subset of $G$.

Remark 2. Clearly since the boundary of $G-$holes does not intersect with the
boundary of $G$, it follows that if $H$ has only a finite number of $G-$holes
and $F$ has no $G-$holes, then $F$ is an Arakeljan set. Additionally, it
follows that if $F$ has no $G-$holes and it fails to be an Arakeljan set, then
either $H$ must be unbounded or $\partial H\cap\partial G\not=\emptyset$.
Now, in order to compare our definition with the more topologically flavored
definition presented in ([2], p. 142), we will need to some tools from
topology. To this end let us recall the _Alexandroff compactification_ of an
arbitrary domain $G\subset\mathbb{C}$. The set $G^{*}$ is defined by
introducing the point $\infty$ so that $G^{*}=G\cup\\{\infty\\}$. The topology
of $G^{*}$ is defined to consist from the open sets of $G$ and in addition all
the sets that are complements of compact subsets $K\subset G$. Under this
topology one may check that $G^{*}$ is compact.
We are ready now to provide the definition of an Araklejan set as presented in
([2], p. 142).

Definition 3. The conditions given on the set $F$ to be an Arakeljan set are:

  1. 1.

$G^{*}\setminus F$ is connected.

  2. 2.

$G^{*}\setminus F$ is locally connected at $\infty$.

The following proposition introduced in ([2], p. 133) provides us with an
intuitive approach for determining whether $G^{*}\setminus F$ is connected.

######  Proposition 1.

The space $G^{*}\setminus F$ is connected if and only if each component of the
open set $G\setminus F$ has an accumulation point on $\partial G$ or is
unbounded.

###### Proof.

The proof can be found in ([2], p. 133-134). ∎

Even though the conditions of Definition 3 given above seem different from the
ones in Definition 2, actually they are the same.

######  Proposition 2.

Definition 2 and Definition 3 describing Arakeljan sets are equivalent.

###### Proof.

Indeed, let $G$ be an arbitrary domain and $F$ a relatively closed subset of
$G$. By Proposition 1, the set $G^{*}\setminus F$ is connected if and only if
each component of the open set $G\setminus F$ has an accumulation point on
$\partial G$ or is unbounded. Therefore, $G\setminus F$ is connected if and if
every hole (component of $G\setminus F$) is not a $G-$hole. Therefore,
conditions 1 of both definitions are equivalent. Now we will show that
conditions 2 of both definitions are equivalent as well.
Indeed, suppose that for any connected compact set $K$ where $\partial K$ is
the union of disjoint jordan curves, the set of $G-$holes of $(F\cup K)$ can
be contained in a compact subset of $G$. We will show that this implies that
$G^{*}\setminus F$ is locally connected at $\infty$. Now, recall that
$G^{*}\setminus F$ being locally connected at $\infty$ by definition requires
that every open set of $G^{*}\setminus F$ containing $\infty$ contains a
connected sub-neighborhood containing $\infty$. However, every open set in
$G^{*}\setminus F$ is simply the complement of a compact set $K\subset
G\setminus F$.
Suppose for a contradiction that $G^{*}\setminus F$ is not locally connected.
Then there must exist a compact set $K\subset G\setminus F$ such that for all
compact subsets $C\subset G$, where $K\subset C$, the set
$G^{*}\setminus(C\cup F)$ is not connected. This of course can only happen
when the set of $G-$holes of $C\cup F$ cannot be contained in a compact subset
of $G$. Now since $G$ is open and path connected we can enclose each component
of $K$ either by a compact set homeomorphic to a disk or by a compact set
homeomorphic to a wedge of annuluses. Then since $G$ is path connected we can
join the enclosed components by a tube222If $\gamma$ is a path joining two
enclosed components of our compact set, say $A$ and $B$. If we remove a small
interval from $\partial A$ and a small interval from $\partial B$, then since
$G$ is open we can join $\partial A$ with $\partial B$ via a rectangular path
”tube” that follows the path of $\gamma$ to form a set $L\supset K$, such that
$\partial L$ is the union of disjoint jordan curves and the set of $G-$holes
$F\cup L$ cannot be contained in a compact subset of $G$, i.e a contradiction.
The other direction is obvious since for any compact set $K\subset G$ that
fails condition 2 of definition 2, the neighborhood $G^{*}\setminus(F\cup
K)\subset G^{*}\setminus F$ is not locally connected at $\infty$. The proof is
complete. ∎

Now we are ready to formally state Arakeljan’s Theorem.

######  Theorem 1 (Arakeljan’s Theorem).

Let $F$ and $G$ be as above, then any $f\in A(F)$ can be uniformly
approximated by functions $g\in Hol(G)$ if and only if $F$ is an Arakeljan
set.

###### Proof.

Arakeljan’s Theorem was first stated and proved in [4] by an Armenian
Mathematician named Arakeljan. An additional proof may be found in ([2], p.
142-144). ∎

Our goal now is to move past the restriction $G=\mathbb{C}$ and prove the
following:

######  Theorem 2 (Extension of Arakeljan’s Theorem).

Let $G\subset\mathbb{C}$ be an arbitrary domain and suppose $F$ is a
relatively closed subset of $G$. Moreover assume that $C\subset G$ is a closed
subset in $G$333Here we mean that $C$ is a closed set in $\mathbb{C}$ that is
also a subset of $G$. In particular it is a relatively closed subset whose
boundary does not intersect with the boundary of $G$. such that $C$ and $F$
are $G-$hole independent. In order that every function $f\in A(F)$ can be
approximated uniformly on $F$ by functions $g\in Hol(G)$, each of which is
bounded on $C$, it is necessary and sufficient that:

  1. 1.

$F$ is an Arakeljan set.

  2. 2.

There exists a closed Arakeljan set $C_{1}\not=G$, so that $C\subset C_{1}$
and $F\cap C_{1}$ can be contained in a compact set in $G$.

## Main result

In [1] the specific case where $G=\mathbb{C}$ Arakeljan’s Theorem has been
extended to the following:

######  Theorem 3 (Extension of Arakeljan’s Theorem when $G=\mathbb{C}$).

Let $F$ and $C$ be closed sets in the complex plane, with $C\not=\mathbb{C}$.
In order that every function $f\in A(F)$ can be approximated uniformly on $F$
by entire functions, each of which is bounded on $C$, it is necessary and
sufficient that:

  1. 1.

$F$ be an Arakeljan set.

  2. 2.

There exists an Arakeljan set $C_{1}$, $C_{1}\not=\mathbb{C}$, so that
$C\subset C_{1}$, and $F\cap C_{1}$ is a bounded set in $\mathbb{C}$.

The proof of the extended version of Arakeljan’s Theorem for $G=\mathbb{C}$
stated above is based on the following two lemmas.

######  Lemma 1.

Let $f$ be an entire function, and let $C$ a closed subset in $G$, $C\not=G$.
In order that $f$ be bounded on $C$ it is necessary and sufficient that there
exists a closed Arakeljan set $C_{1}\subset G$ so that $C\subset C_{1}$ and
$f$ is bounded on $C_{1}$.

######  Lemma 2.

The union of two disjoint Arakeljan sets $E$ and $F$ is again an Arakeljan
set.

In order to prove the Extension of Arakeljan’s Theorem we have to generalize
Lemma 1 and Lemma 2 for a general domain $G$. The reason we did not use the
more intuitive definition for Arakeljan sets and $G-$holes (see Remarks 1 and
2) is so that we can adjust the proofs presented in [1] to fit the case of an
arbitrary domain $G$.

######  Lemma 3.

Let $G\subset\mathbb{C}$ be an arbitrary domain and let $f\in Hol(G)$. Suppose
$C$ is a closed subset in $G$. In order that $f$ is bounded on $C$ it is
necessary and sufficient that there exists a closed Arakeljan set
$C_{1}\subset G$ so that $C\subset C_{1}$ and $f$ is bounded on $C_{1}$.

###### Proof.

The proof of sufficiency is obvious so we will only prove necessity.
Therefore, lets assume that there exists an $M>0$ such that $|f(z)|<M$ for all
$z\in C$, our goal is to show that there is an Arakeljan set $C_{1}$
containing $C$ such that $f$ is bounded on $C_{1}$. Now since $G$ is open and
$C$ is a closed subset in $G$, by continuity of $f$ on $C$, it follows that
for each $z\in C$ there exists an open disk $U(z)$ centered at $z$ of radius
less than $\delta_{z}$, so that $|f(t)|<M+1$ for all $t\in U(z)$. Furthermore,
we pick $\delta_{z}<dist(C,\partial G)$, so that:

$\displaystyle\overline{\bigcup_{z\in C}U(z)}\cap\partial G=\emptyset.$
$\displaystyle(*)$

The open cover $\\{U(z)\\}$ , $z\in C$ of the closed set $C$ has a locally
finite subcover which we denote by $\\{U_{n}\\}$, $n=1,2,3,....$ Hence we have

  1. 1.

$C\subset\bigcup_{n=1}^{\infty}U_{n}$

  2. 2.

For any compact subset $K$ of $G$ only a finite number of disks $\\{U_{n}\\}$
intersect $K$.
Write $E=\bigcup_{n=1}^{\infty}\overline{U_{n}}$. By 2, $E$ is closed.

  3. 3.

$|f(z)|<M+1,\ \ z\in E$

Let $C_{1}$ be the intersection of $G$ with the union of $E$ and its $G-$holes
(if any exist). $C_{1}$ is the union of a locally finite collection of closed
sets, thus it is closed and by $(*)$ is a subset of $G$. Furthermore by
construction $C_{1}$ does not have any $G-$holes. From $(3)$, by the maximum
principle, we have

$|f(z)|<M+1,\ \ z\in C_{1}$

By $(1)$, we also have $C\subset C_{1}$. Hence the lemma will be proved when
we show $C_{1}$ is an Arakeljan set. Recall that to show that $C_{1}$ is
Arakeljan set we must show that:

  1. a)

The set $C_{1}$ has no $G-$holes

  2. b)

For any connected compact set $K\subset G$ the set $H\equiv\\{h:h\text{ is a
$G-$ hole of }C_{1}\cup K\\}$ can be contained in a compact set $L\subset G$.

Condition $(a)$ is satisfied by construction of the set $C_{1}$, thus by
Remark 2 it suffices to prove that for any such connected compact set
$K\subset G$ such that $\partial K$ is the union of disjoint jordan curves,
$C_{1}\cup K$ has only a finite number of $G-$holes.
To this end, let $K$ be such a compact subset of $G$. By $(2)$ in the sequence
$\\{\overline{U_{n}}\\}$, there exists only a finite number of disks
$\overline{U_{n_{1}}},\overline{U_{n_{2}}},....\overline{U_{n_{k}}}$, each of
which intersects $K$. The set $(\partial
K)\setminus\bigcup_{m=1}^{m=k}\overline{U_{n_{m}}}$ is the union of a finite
number of disjoint open intervals $I_{1},I_{2},...,I_{p}$ on $\partial K$. For
any $G-$hole $h$ of $K\cup C_{1}$, there exists at least one interval $I_{k}\
\ (1\leq k\leq p)$ so that $I_{k}\subset\partial h$. (Otherwise $h$ would be a
$G-$hole of $C_{1}$, which is impossible, since $C_{1}$ is without $G-$holes).
If $h_{1},h_{2}$ are two distinct $G-$holes of $K\cup C_{1}$ and
$I_{k_{1}}\subset\partial h_{1}\ \ (1\leq k_{1}\leq
p),I_{k_{2}}\subset\partial h_{2}\ \ (1\leq k_{2}\leq p)$, then
$k_{1}\not=k_{2}$, since otherwise we would have $h_{1}\cap
h_{2}\not=\emptyset$ which is impossible since $h_{1}$ and $h_{2}$ are
distinct $G-$holes.
Consequently, the number of $G-$holes of $K\cup C_{1}$ cannot be more than the
number of intervals $I_{k}$. Thus the number of $G-$holes of $C_{1}\cup K$ is
finite, hence by Remark 2 it follows that $C_{1}$ is an Arakeljan set and the
proof is complete. ∎

In order to state the corresponding analogue of Lemma 2 for the case
$G=\mathbb{C}$, we first need to introduce the following definition.
Definition 4. Let $G\subset\mathbb{C}$ be a domain and let $F$ be a relatively
closed subset of $G$. Then we call a _strict hole_ of $F$ any connected
component of $G\setminus F$ (hole) that cannot be contained in a compact
subset of $G$ (i.e a hole that is not a $G-$hole).
Definition 5. Let $E$ and $F$ be disjoint relatively closed subsets of $G$.
Then we say that $E$ and $F$ are $G-$hole independent if any non empty
pairwise intersection of strict holes of $E$ with strict holes of $F$ is not a
$G-$hole.

######  Lemma 4.

Let $G$ be an arbitrary open domain in $\mathbb{C}$ and suppose $E$ and $F$
are two disjoint Arakeljan sets in $G$ that are $G-$hole independent. Then the
set $E\cup F$ is an Arakeljan set in $G$.

###### Proof.

The set of holes of $E\cup F$ is the following:

$\displaystyle G\setminus(E\cup F)$ $\displaystyle=(G\setminus
E)\cup(G\setminus F)$
$\displaystyle=\bigcup_{i=1}^{\infty}E_{i}\cap\bigcup_{j=1}^{\infty}F_{j}$
$\displaystyle=\bigcup_{i=1}^{\infty}G_{i}.$

Where $E_{i}$ are the set of holes of $E$, $F_{j}$ the set of holes of $F$ and
$G_{i}=\bigcup_{j=1}^{\infty}(E_{i}\cap F_{j}).$ Since $E$ and $F$ are
Arakeljan sets it follows that none of them has $G-$holes, and since they are
$G-$hole independent it follows that indeed $E\cup F$ has no $G-$holes as
required. Therefore, it remains to verify the latter condition of definition 2
describing Arakeljan sets. To this end, assume for a contradiction that there
exists a connected compact subset $K\subset G$ where $\partial K$ is the union
of disjoint jordan curves, and such that $H$, the set of all $G-$ holes of
$E\cup F\cup K$ is either unbounded or $\partial H\cap\partial
G\not=\emptyset$. Then by Remark 2 it follows the set $E\cup F\cup K$ has
infinite $G-$holes. Consequently, the set $H$ must have infinitely many
components i.e $H=\bigcup_{i=1}^{\infty}\\{h_{i}\\}$ where each $h_{i}$
represents a $G-$hole of $E\cup F\cup K$. Now for fixed $i$, let $a_{k}^{i},\
\ k=1,2,...$ be all the $G-$holes of $\overline{h_{i}}\cup K$. The connected
compact set $\overline{h_{i}}\cup\bigcup_{k}\overline{a_{k}^{i}}$ has no
$G-$holes. Denote by $d_{i}$ the interior of this connected compact set which
contains $h_{i}$. Now $\partial d_{i}$ consists of an open arc on $\partial
K$444Since $\partial K$ is the union of disjoint jordan curves and $K$ is
connected and a connected compact set which we denote by $K_{i}$. That is,
$K_{i}=\overline{(\partial d_{i})\setminus\partial K}.$ Clearly, $K_{i}\subset
E\cup F$. Hence $K_{i}$ lies completely either on $E$ or in $F$. Let $i_{n}$,
$n=1,2,...,$ be all the natural numbers for which $K_{i_{n}}\subset E$ and let
$i_{l},\ \ l=1,2,...,$ be the remaining natural numbers such that
$K_{i_{l}}\subset F$. Now by our assumption the set
$H=\bigcup_{i=1}^{\infty}\\{h_{i}\\}$ is either unbounded or $\partial
H\cap\partial G\not=\emptyset$ or both. The case where $H$ is unbounded is
already dealt with on [1]. For the case $\partial H\cap\partial
G\not=\emptyset$ we simply note that since $H$ has an accumulation point on
$\partial G$, it follows that one or both of the sets $\\{h_{i_{n}}\\}$ or
$\\{h_{i_{l}}\\}$ has an accumulation point on $\partial G$. Without loss of
generality let’s assume that $\\{h_{i_{n}}\\}$ has an accumulation point on
$\partial G$. Now let us consider the holes of $\\{h_{i_{n}}\\}\cup K$. Since
$K_{i_{n}}\subset E$ and $h_{i_{n}}$ is a $G-$hole of $E\cup F\cup K$, we see
that there exists a $G-$hole $V_{i_{n}}$ of $E\cup K$ so that
$h_{i_{n}}\subset V_{i_{n}}\subset d_{i_{n}}$. Hence the set
$\bigcup_{n=1}^{\infty}\\{V_{i_{n}}\\}$ has an accumulation point on $\partial
G$, which implies that the set $E$ is not an Arakeljan set. This is a
contradiction hence the lemma is proved. ∎

Remark 3. Note that in the lemma above we must necessarily require $E$ and $F$
to be $G-$hole independent. Indeed, if we let $G$ to be the punctured unit
disc and $E$ and $F$ circles with radii $\frac{1}{2}$ and $\frac{1}{4}$
respectively. Then we can easily verify that $E$ and $F$ are disjoint
Arakeljan sets whose union $E\cup F$ has the annuls
$A=\\{z\in\mathbb{C}:\frac{1}{4}<|z|<\frac{1}{2}\\}$ as a $G-$hole. This
happens of course because they are not $G-$hole independent.

Now that we have the two lemmas in our arsenal we are ready to prove the
Extension of Arakeljan’s Theorem.

######  Theorem 4 (Extension of Arakeljan’s Theorem).

Let $G\subset\mathbb{C}$ be an arbitrary domain and suppose $F$ is a
relatively closed subset of $G$. Moreover assume that $C\subset G$ is a closed
subset in $G$ such that $C$ and $F$ are $G-$hole independent. In order that
every function $f\in A(F)$ can be approximated uniformly on $F$ by functions
$g\in Hol(G)$, each of which is bounded on $C$, it is necessary and sufficient
that:

  1. 1.

$F$ is an Arakeljan set.

  2. 2.

There exists a closed Arakeljan set $C_{1}\not=G$, so that $C\subset C_{1}$
and $F\cap C_{1}$ can be contained in a compact set in $G$.

###### Proof of Extension of Arakeljan’s Theorem.

(Necessity.) Assume that any $f\in A(F)$ can be approximated uniformly by
functions $g\in Hol(G)$, each of which is bounded on $C$. By Arakeljan’s
Theorem it follows $F$ is an Arakeljan set. Clearly the function $\phi(z)=z$
belongs to the class $Hol(G)$, thus there exists a function $f\in Hol(G)$ such
that:

$|z-f(z)|<1,\ \ z\in F$ (1)

and $f$ is also bounded on C. By lemma 1 there exists a closed Arakeljan set
$C_{1}\subset\mathbb{C}$ such that that $C\subset C_{1}$ and $f(z)$ is bounded
on $C_{1}$. By $(1)$ clearly $F\cap C_{1}$ is bounded. Since $C_{1}$ is a
closed subset inside $G$, it follows that it stays away from the boundary
$\partial G$. Therefore, since $F\cap C_{1}$ is bounded it follows that it can
be contained in a compact set $L\subset G$. The proof of necessity is
complete.
(Sufficiency.) We have Arakeljan sets $F$ and $C_{1}$, $C\subset C_{1}$, such
that $F\cap C_{1}$ is a bounded set. Let $L$ be a compact set in $G$ such that
$\partial K$ is the union of disjoint jordan curves and so large that:

$F\cap C_{1}\subset L$ (2) $(\partial L)\setminus C_{1}\not=\emptyset$ (3)

Note that $(3)$ is possible since $C_{1}\not=G$ is a closed set without
$G-$holes.
The set $C_{1}\setminus L$ is also without $G-$holes, because otherwise there
would exist a $G-$hole $g$ of $C_{1}\setminus L$. This leads to a
contradiction since we must have $\partial g\subset C_{1}$. However, since
$C_{1}$ has no $G-$holes it follows that $g=L$ and this contradicts $(3)$.
Moreover, since by assumption of the theorem $C$ and $F$ are $G-$hole
independent, without loss of generality we may assume that the set
$F\cup(C_{1}\setminus L)$ is without $G-$holes. The set $C_{1}\setminus L$ is
also an Arakeljan set. Otherwise, there would exist a compact set $K\subset G$
so that the set $H\equiv\\{h:h\text{ is a }G-\text{hole of
}K\cup(C_{1}\setminus L)\\}$ is either unbounded or $\partial H\cap\partial
G\not=\emptyset$. But this is a contradiction because then the set of
$G-$holes of the set $C_{1}\setminus L$ union the compact set $K\cup L$ would
also have to either be unbounded or accumulate to a point in $\partial G$.
Indeed, the claim follows, since $(K\cup L)\cup(C_{1}\setminus L)=C_{1}\cup
K$. This contradicts that $C_{1}$ is an Arakeljan set, as such, by the
contradiction we conclude $C_{1}\setminus L$ is an Arakeljan set.
Now the Arakeljan sets $F$ and $C_{1}\setminus L$ are disjoint by $(2)$,
therefore by the lemma 4 it follows that $F\cup(C_{1}\setminus L)$ is an
Arakeljan set.
Let $\phi(z)\in A(F)$ be any function. Define a function $h(z)$ by
$h(z)=\phi(z)$ on $F$ and $h(z)=0$ on $C_{1}\setminus L$. Clearly by $(2)$ it
is evident that $h(z)\in A(F\cup(C_{1}\setminus L))$. Therefore by Arakeljan’s
theorem $h(z)$ is uniformly approximable by functions in $A(G)$. Therefore for
any $\epsilon>0$, there exists a function $f\in A(G)$ such that
$|h(z)-f(z)|<\epsilon$ for any $z\in F\cup(C_{1}\setminus L)$. Hence we have
that $|\phi(z)-f(z)|<\epsilon$ on $F$ and $|f(z)|<\epsilon$ on $C_{1}\setminus
L$. The function $f(z)$ is bounded on $C_{1}\setminus L$, moreover $f(z)$ is
bounded on the compact set $C_{1}\cap L$ thus, $f(z)$ uniformly approximates
$\phi(z)$ on $F$ and is bounded on $C$. The proof is complete. ∎

The following lemma is proven in [[3], p2.65] and replaces lemma 4 for the
case $G$ is simply connected.

######  Lemma 5.

Let $G\subset\mathbb{C}$ be a simply connected open set
$\\{F_{n}\\}_{n=1}^{\infty}$ is a locally finite family of pairwise disjoint
Arakeljan sets in $G$, then the union $\bigcup_{n=1}^{\infty}F_{n}$ is also an
Arakeljan set in $G$.

######  Corollary 1 (Extension of Arakeljan’s Theorem when $G$ is simply
connected).

Let $G\subset\mathbb{C}$ be an arbitrary simply connected domain and suppose
$F$ is a relatively closed subset of $G$. Moreover assume that $C\subset G$ is
a closed subset in $G$. In order that every function $f\in A(F)$ can be
approximated uniformly on $F$ by functions $g\in Hol(G)$, each of which is
bounded on $C$, it is necessary and sufficient that:

  1. 1.

$F$ is an Arakeljan set.

  2. 2.

There exists a closed Arakeljan set $C_{1}\not=G$, so that $C\subset C_{1}$
and $F\cap C_{1}$ can be contained in a compact subset $L\subset G$.

###### Proof.

The proof is identical to the one above where of course we use lemma 5 instead
of lemma 4. ∎

To conclude we ask the following open question that occurs naturally. Does the
Extension of Arakeljan’s Theorem still hold if we require that the
approximating functions to be uniformly bounded on $C$? This question remains
unanswered even for the case $G=\mathbb{C}$

## References

  * [1] A.A Danielyan and L.A Rubel, Uniform Approximation by Entire Functions That Are All Bounded on a Given Set, Const. Approx. (1998) 14: 469-473.
  * [2] Dieter Gaier, Lectures on Complex Approximation, Brickhauser Boston, Inc., 1987.
  * [3] Fournodavlos, G. On a characterization of Arakelian sets. J. Contemp. Mathemat. Anal. 47, 261–269 (2012)).
  * [4] N. U Arakeljan: Uniform and tangential approximations by analytic functions. Izv. Akad. Nauk Armjan. SSR Ser. Mat. 3 1968 no. 4-5, 273–286.
  * [5] L.A. Rubel: Joint approximation in the complex domain. Symposium on Complex Analysis, Canterbury 1973 (J. Clunie, W.K Hayman, eds.).Cambridge: Cambridge University Press,pp 115-118 (1974)
  * [6] L.A Rubel, A.L Shields,:Bounded approximation by polynomials. Acta Math.,112:145-162. (1964)
  * [7] On some problems arising from Rubel’s problem in joint approximation. Dokl. Akad. Nauk Russ.,341 (1995)
  * [8] : On the representation of functions by sequences of uniformly bounded polynomials on compact sets of the complex plane. Isz. Akad. Nauk Armyan. SSR Ser. Math., 21:345–357.(1986)
  * [9] L.A Rubel, Lee A.; Stray, Arne. Joint approximation in the unit disc. J. Approx.Theory 37, no. 1, 44–50. (1983)
  * [10] Beise, Hans-Peter, Muller, Jurgen. Generic boundary behaviour of Taylor series in Hardy and Bergman spaces. Math. Z. 284, no. 3-4, 1185–1197.(2016)
  * [11] Muller, Jurgen. Spurious limit functions of Taylor series. Anal. Math. Phys.9, no. 2, 875–885.(2019)


# Compositional Learning-based Planning for Vision POMDPs

Sampada Deglurkar∗,1<EMAIL_ADDRESS>
Michael H. Lim∗,1<EMAIL_ADDRESS>
Johnathan Tucker2<EMAIL_ADDRESS>
Zachary N. Sunberg2<EMAIL_ADDRESS>
Aleksandra Faust3<EMAIL_ADDRESS>
Claire J. Tomlin1<EMAIL_ADDRESS>
1UC Berkeley  2CU Boulder  3Google Research

###### Abstract

The Partially Observable Markov Decision Process (POMDP) is a powerful
framework for capturing decision-making problems that involve state and
transition uncertainty. However, most current POMDP planners cannot
effectively handle high-dimensional image observations prevalent in real world
applications, and often require lengthy online training that requires
interaction with the environment. In this work, we propose Visual Tree Search
(VTS), a compositional learning and planning procedure that combines
generative models learned offline with online model-based POMDP planning. The
deep generative observation models evaluate the likelihood of and predict
future image observations in a Monte Carlo tree search planner. We show that
VTS is robust to different types of image noises that were not present during
training and can adapt to different reward structures without the need to re-
train. This new approach significantly and stably outperforms several baseline
state-of-the-art vision POMDP algorithms while using a fraction of the
training time.

###### keywords:

Partially Observable Markov Decision Process, Monte Carlo Tree Search,
Compositional Learning, Generative Models

##  1 Introduction

Many sequential decision making problems, such as autonomous driving (Bai et
al., 2015; Sunberg et al., 2017), cancer screening (Ayer et al., 2012), spoken
dialog systems (Young et al., 2013), and aircraft collision avoidance (Holland
et al., 2013), involve uncertainty in both sensing and planning. Planning
under partial observability is challenging, as the agent must address both
localization and uncertainty-aware planning through active information
gathering in the environment. By capturing the observation uncertainty through
a belief distribution over possible states, the agent will be able to fully
close the observation-plan-action loop. While there are many methods that can
either handle visual localization (Jonschkowski et al., 2018; Karkus et al.,
2020, 2021) or planning under uncertainty (Van Den Berg et al., 2012; Todorov
and Li, 2005), a naïve combination of these methods, for instance by assuming
the certainty equivalence principle or simplifying the observation space, may
not yield meaningful closed-loop control policies that enable active
information gathering under more general environmental assumptions.

The partially observable Markov decision process (POMDP) formalism is a
powerful framework that can capture and systematically solve these sequential
decision making under uncertainty problems. However, finding an optimal POMDP
policy is computationally demanding, and often intractable, due to the
uncertainty introduced by imperfect observations (Papadimitriou and
Tsitsiklis, 1987). One popular approach to deal with this challenge is to use
_online_ algorithms that look for local approximate policies as the agent
interacts with the environment rather than a global policy that maps every
possible outcome to an action, such as Monte Carlo tree search (MCTS) and
similar variants (Browne et al., 2012; Silver and Veness, 2010; Sunberg and
Kochenderfer, 2018; Ye et al., 2017; Kurniawati and Yadav, 2016). Many of
these state-of-the-art MCTS algorithms enjoy computational efficiency (Sunberg
and Kochenderfer, 2018; Mern et al., 2021; Lim et al., 2021) and finite sample
convergence guarantees to the optimal policy (Lim et al., 2020, 2021). Despite
their flexibility and optimality, these methods rely on having access to
generative models and observation density models, which limits the class of
problems they can solve in practice. In many realistic scenarios with high
dimensional observations like RGB images, these POMDP methods cannot be
applied without knowing or learning the relevant models or simplifying the
environment.

Recently, there has been an increased interest in solving vision POMDPs, i.e.
POMDPS with image or video observations, using deep learning methods. Model-
free vision POMDP algorithms train an end-to-end deep neural network policy to
learn both a latent belief representation and a planner (Karkus et al., 2017;
Mnih et al., 2013; Igl et al., 2018), which benefit from not having to specify
the transition and observation models and can learn complex policies. However,
they may lack interpretability, not generalize well to new unseen tasks, and
not leverage much prior knowledge about the system, especially in robotics
settings. In contrast, model-based vision POMDP algorithms (Wang et al., 2020;
Singh et al., 2021) combine classical filtering and planning techniques with
deep learning. While such algorithmic structure allows the models to focus on
specific tasks, making them sample efficient and robust, these methods often
rely on simplified approaches for planning in the belief space and require
learning an advantage function that only partially captures uncertainty by
coupling observations with rewards.

Figure 1: Visual Tree Search interfaces offline deep generative model training
with online model-based POMDP filtering and planning.

Thus, we propose Visual Tree Search (VTS), a procedure to solve vision POMDPs
by combining deep generative models and online tree search planning,
effectively framing the POMDP reinforcement learning problem as a
compositional unsupervised learning problem. Our key insight is to utilize
compositional learning approaches to bridge the offline training of individual
sets of models with online model-based planning that uses learning-enabled
components. Introducing the algorithmic prior knowledge of particle filtering
and MCTS decreases the computational complexity required by the learning and
captures state and transition uncertainty without dependence on reward
structure. Our empirical analyses demonstrate that tackling uncertainty via
VTS enhances performance, robustness, and interpretability of neural network
components.

##  2 Background

#### POMDPs.

A POMDP is defined with a 7-tuple $(S,A,O,T,Z,R,\gamma)$, with state space
$S$, action space $A$, observation space $O$, transition density
$T(s^{\prime}|s,a)$, observation density $Z(o|s)$, reward function $R(s,a)$,
and discount $\gamma\in[0,1)$ (Kochenderfer, 2015; Bertsekas, 2005).
Specifically, we say “continuous POMDPs” to denote those with continuous
state, action, and observation spaces. For POMDPs, since the agent receives
only noisy observations of the true state, it can infer the state by
maintaining a belief $b_{t}\in B$ at each step $t$ and updating it with the
new action and observation pair $(a_{t+1},o_{t+1})$ via Bayesian filtering
(Kaelbling et al., 1998). A policy $\pi:B\to A$ maps a belief $b$ to an action
$a$. The agent seeks to find an optimal policy $\pi^{*}$ that maximizes the
expected cumulative reward.

#### Monte Carlo Tree Search.

In Monte Carlo planning, it is not always necessary to evaluate the exact
probability of all transitions and observations, and merely generating samples
of next state $s^{\prime}$, reward $r$, and observation $o$ is sufficient. In
particular, many Monte Carlo Tree Search (MCTS) algorithms only require that
we have generative models that can generate $(s^{\prime},r,o)$ samples with
densities $s^{\prime}\sim T(s^{\prime}|s,a)$ and $o\sim G(o|s^{\prime})$, and
observation density models that can evaluate the likelihood
$w=Z(o|s^{\prime})$. Using these samples, MCTS can reason about the transition
and observation densities by balancing exploration and exploitation to
approximate the true reward distribution. This results in an approximate
online policy that maximizes the expected sum of rewards at each planning
step.

#### Deep generative models.

Many models in deep learning are used to approximate probability distributions
over high dimensional spaces such as spaces of images and videos. However,
sampling from these distributions requires deep generative models. While some
deep generative models, such as Generative Adversarial Networks (GANs), try to
sample from distributions by making the samples seem as “realistic” as
possible, other models such as Variational Autoencoders (VAEs) map complex
distributions to simpler ones via latent space embedding. Conditional
generative models condition on another variable to sample from conditional
distributions (Mirza and Osindero, 2014; Zhao et al., 2017). In our MCTS
planner, we use deep generative models $G$ to sample observations conditioned
on the state, and $P$ to propose state particles given the current
observation. For our neural network training procedures, we make the ground
truth state information available to the planner during training, but keep it
unavailable during testing.

##  3 Related Works

#### Planning under uncertainty.

Planning under state and transition uncertainty requires planners to
simultaneously localize and optimally plan through active information
gathering. Popular control-based methods involve variants of the iterative
Linear Quadratic Gaussian (Todorov and Li, 2005; Van Den Berg et al., 2012;
Lee et al., 2017), which perform trajectory optimization over a simplified
belief space. While such methods can handle continuous dynamics and leverage
fast optimization computational tools, they cannot effectively handle image
observations and high-dimensional state spaces. They also make simplifying
Gaussian belief assumptions and are only locally optimal within the simplified
belief space. Other sampling-based methods such as Sequential Monte Carlo
(SMC) (Piché et al., 2019; Wang et al., 2020) ameliorate the above
shortcomings by augmenting sampling-based planning with advantage networks,
but do so at the cost of being unable to reason about future observations.
Such an approximation effectively assumes that the state uncertainty vanishes
at the next step, which is proven to be sometimes suboptimal (Kaelbling et
al., 1998).

On the other hand, state-of-the-art tree search planners have shown success in
relatively large or continuous space POMDP planning problems. Most notably,
POMCPOW and PFT-DPW (Sunberg and Kochenderfer, 2018), LABECOP (Hoerger and
Kurniawati, 2020), and DESPOT-$\alpha$ (Garg et al., 2019) were shown to be
effective in solving continuous observation POMDP problems. They use weighted
collections of particles to efficiently represent complex beliefs. Provided
the particles are weighted appropriately based on the observation likelihood,
tree search using these particle beliefs will converge to a globally optimal
policy (Lim et al., 2020). Furthermore, these works led to planners that can
solve fully continuous or even hybrid space POMDP problems, using techniques
such as continuous bandits (Lim et al., 2021) or Bayesian optimization (Mern
et al., 2021). These tree search methods require access to generative models
and observation density models to effectively plan, which we aim to learn with
neural networks to extend the scope of the tree search methods. In this work,
we integrate the PFT-DPW algorithm to handle learning-based model components.

#### Deep learning for vision POMDP.

Recently, there has been increased interest in solving POMDPs involving visual
observations through deep learning (Guillén et al., 2005; Karkus et al., 2018;
Zhang et al., 2019). Model-free vision POMDP solvers such as QMDP-net (Karkus
et al., 2017) and Deep Variational Reinforcement Learning (Igl et al., 2018)
maintain a latent belief vector whose update rule is learned via a neural
network. They then learn corresponding value or policy networks in this latent
belief state and action space. Furthermore, since these methods usually make
minimal sets of assumptions, extensions of such techniques can also be seen in
embodied artificial intelligence applications (Karkus et al., 2021; Ai et al.,
2022)

Model-based vision POMDP works such as Differentiable Particle Filter (DPF)
(Jonschkowski et al., 2018) allow conventional particle filtering techniques
to be interfaced with complex visual observations. This algorithm contains
multiple linked neural network components, including a particle proposer, an
observation model, and a dynamics model, that are designed to be trained end-
to-end. A recent work extends DPF with entropy regularization and provides
convergence guarantees (Corenflos et al., 2021). Dual Sequential Monte Carlo
(DualSMC) (Wang et al., 2020) extends the DPF methods further to introduce an
adversarial filtering objective and integrate in the SMC planner, making it a
fully closed-loop POMDP solver. In this work, we extend DPF and DualSMC to
interface tree search planners.

#### Compositional learning.

In compositional learning, a learning task is broken down into neural network
components that each specialize in different tasks. These components are then
integrated to learn complex relations, allowing for less data and training
resources to be used overall. Compositional learning can be achieved either
through provided compositional structure in the form of an algorithmic prior
(Andreas et al., 2016; Hudson and Manning, 2018), or by automatically
discovering such structures (Rosenbaum et al., 2018; Alet et al., 2018; Kirsch
et al., 2018; Meyerson and Miikkulainen, 2018). Specifically, algorithmic
prior knowledge can be introduced by specifying neural network architectures
or model components, which then allows for intelligent planning with minimal
training from limited or specialized data. Furthermore, this paradigm has
enjoyed success in various reinforcement learning settings, particularly
multi-task problems (Devin et al., 2017; Ha and Schmidhuber, 2018; Yang et
al., 2020; Mittal et al., 2020; Lim et al., 2022).

##  4 Visual Tree Search

Figure 2: Overview of Visual Tree Search (VTS). The models learned with neural
networks are shown in yellow – the transition model is shown in gradient,
since it can be learned or pre-defined. The contributions of the models for
filtering are shown in blue arrows, and planning in red arrows, and numbers in
brackets show corresponding steps in Algorithm 1.

Solving a POMDP can be split into solving the filtering and the planning
problems separately. In the Visual Tree Search (VTS) algorithm, we integrate
the learned POMDP model components with classical filtering and planning
techniques. This results in a POMDP solver that can learn model components
that are more sample efficient and interpretable than end-to-end approaches.
It also benefits from having a robust particle filter and planner built upon
techniques with theoretical guarantees, and can adapt to different task
rewards. To integrate planning techniques that use online tree search, we must
have access to a conditional generative model that can generate image
observations $o$ from a given state $s$ according to the likelihood density
$Z(o|s)$. In this section, we outline the filtering and planning algorithms
and models, and the compositional training procedure.

###  4.1 Differentiable Particle Filtering

For particle filtering, we leverage a family of architectures called
Differentiable Particle Filters (DPF) (Jonschkowski et al., 2018), which
combine classical particle filtering algorithms with convolutional neural
networks that can handle complex observations. We learn two neural network-
based models: (1) Observation density $Z_{\theta}$ that gives the likelihood
weights $w_{t}=Z_{\theta}(o_{t}|s_{t})$, (2) Particle proposer $P_{\phi}$ that
allows us to sample states $s_{t}\sim P_{\phi}(o_{t})$. The Greek letters
denote the parameters of these neural network models. Specifically for our
work, we adapt the DPF architecture introduced in DualSMC (Wang et al., 2020),
in which the observation and proposer networks are trained with an adversarial
optimization objective. In principle, we can also train DPF with entropy
regularization (Corenflos et al., 2021) with optimality guarantees. We assume
that the transition model $T$ is known, which is not a limiting assumption for
many POMDP problems (e.g. POMDPs with physical dynamics), but in principle it
can be learned and modeled with a neural network $T_{\psi}$ as well.

The filtering procedure is described below; the belief is represented by
$b_{t}\approx\\{s_{t}^{(k)},w_{t}^{(k)}\\}_{k=1}^{K}$, with $K$ as the number
of particles. First, the agent takes a step with an action chosen by the
planner. Then, the agent updates the predicted states
$(s_{t+1}^{\prime})^{(k)}$ with the transition model $T$. The observation
$o_{t}$ obtained from the environment is fed into the observation density
$Z_{\theta}$, which provides the likelihood of an observation given the state.
This is used to update the likelihood weights $(w_{t+1}^{\prime})^{(k)}$ of
each particle. In order to ensure robustness in the particle representation of
the belief state, the particle proposer deep generative model $P_{\phi}$
proposes plausible state particles for a given observation, replacing some
fraction of the particles. This fraction is made to decay exponentially over
time.

Algorithm 1 Visual Tree Search Algorithm.

Input: Hyperparameters for neural networks ($\zeta$), DPF ($\chi$), MCTS
($\rho$), maximum time step $T_{\max}$.
Output: Action $a_{t}$ at each step $t$.

1: Collect data $\mathcal{D}$ of tuples $(s_{t},a_{t},o_{t},s_{t+1})$ through
random sampling or exploration.

2: [Optional] Train the transition model $T_{\psi}$ with data tuples
$(s_{t},a_{t},s_{t+1})$.

3: [Training] Jointly train the observation density model $Z_{\theta}$ and
particle proposer model $P_{\phi}$ with data tuples
$(s_{t},o_{t},\\{\hat{s}_{t,i}\\})$, where $\\{\hat{s}_{t,i}\\}$ are particle
estimates of $s_{t}$.

4: [Training] Train the observation conditional generator model $G_{\xi}$ with
data tuples $(s_{t},o_{t})$.

5: for $t=1$ to $T_{\max}$ do

6: [Filtering] If $t=1$, initialize the belief state $b_{t}$. Otherwise, after
receiving $o_{t}$, update the belief state $b_{t}$ with
DPF($T_{\psi},Z_{\theta},P_{\phi},\chi$).

7: [Planning] Run MCTS($T_{\psi},Z_{\theta},G_{\xi},\rho$) on the belief state
$b_{t}$ to obtain and perform action $a_{t}$.

8: end for

###  4.2 Tree Search Planner

#### Monte Carlo Tree Search.

For the online planner, we use the Particle Filter Trees-Double Progressive
Widening (PFT-DPW) algorithm (Sunberg and Kochenderfer, 2018). PFT-DPW is a
particle belief-based MCTS planner that is relatively easy to implement and
efficiently vectorizes particle filtering. Additionally, a simplified version
of PFT-DPW has optimality guarantees (Lim et al., 2020). However, any
continuous POMDP tree search planner can be used instead.

For our navigation problems, we discretize the action space such that the
robotic agent moves in the 8 cardinal and diagonal directions with full
thrust. While this means we work with a limited action space, we can ensure
that we travel with full thrust to get to the goal faster and reduce the
complexity of both planning and generating observations. However, we could
also work with a continuous action space in principle. Furthermore, we provide
PFT-DPW with a naïve rollout policy of actuating straight towards the goal and
calculating the expected reward, which PFT-DPW can use as a reference and
vastly improve upon.

#### Observation conditional generative model.

Deep conditional generative models enable online model-based POMDP planning
with images. To plan with a tree search planner, we need to be able to
generate the next step states and observations, and evaluate the likelihood of
the observations. With models from DPF, we can generate the next step state
with transition model $T$ and calculate the likelihood weight with observation
density $Z_{\theta}$, which are also used in the filtering procedure. Thus, we
only additionally need to learn a deep generative model $G_{\xi}$ that
generates an observation $o_{t}$ given a state $s_{t}$: $o_{t}\sim
G_{\xi}(s_{t})$. We use a Conditional Variational Autoencoder (CVAE) (Sohn et
al., 2015) to model the observation conditional generator $G_{\xi}$, where the
state $s_{t}$ is the conditional variable, since it had the most consistent
training and performance in our experiments.

###  4.3 Compositional Training of Visual Tree Search

We train each neural network model with pre-collected data $\mathcal{D}$,
containing tuples of $(s_{t},a_{t},o_{t},s_{t+1})$, as shown in Lines 1-4 of
Algorithm 1. We provide the $Z_{\theta}$ and $P_{\phi}$ models with randomly
sampled batches of state, observation, and synthetic belief particle sets
$(s_{t},o_{t},\\{\hat{s}_{t,i}\\})$. While the belief particle sets are not a
part of the pre-collected data, we can easily create them by sampling states
from a normal distribution centered at $s_{t}$. The $Z_{\theta}$ and
$P_{\phi}$ are trained with the adversarial objective in DualSMC (Wang et al.,
2020): $Z_{\theta}$ serves as a discriminator that gives higher likelihoods to
states that are more likely for a given observation, and $P_{\phi}$ serves as
a conditional generator that proposes plausible state particles for a given
observation. The $G_{\xi}$ model is trained with random batches of samples of
state and observation pairs: $(s_{t},o_{t})$. These random batches provide a
good data prior for all types of states and observations an agent may
encounter during planning, unlike methods such as DualSMC which only encounter
data collected from the locally optimal policy.

Compared to other on-policy RL algorithms and architectures, the VTS training
procedure shifts the POMDP problem from a reinforcement learning problem to a
compositional learning problem, in which training each model in the POMDP is
framed as an unsupervised learning problem. This drastically decreases the
problem complexity, as we have explicit control over the learning objective of
each model and the schedule of the training. It also allows us to better
approximate the data distribution via sampling or exploration, as opposed to
an evolving on-policy planner distribution that often starts off poorly and
provides heavily biased data.

##  5 Experiments

We compare VTS to other state-of-the-art vision POMDP algorithms, DualSMC
(Wang et al., 2020), DVRL (Igl et al., 2018) and PlaNet (Hafner et al., 2019),
on two benchmark vision POMDP problems. First, we tested our algorithm on the
2D Floor Positioning problem (Wang et al., 2020) to demonstrate that using the
VTS learning and planning procedure can significantly decrease the training
time to learn a solver that is agnostic to the task or reward structure of the
problem. Then, we prepared our own version of the 3D Light-Dark problem in the
Stanford Large-Scale 3D Indoor Spaces dataset (Armeni et al., 2017) to set up
a more challenging navigation task that requires the agent to plan with
realistic indoor building RGB images. We also performed ablation tests with
the 3D Light-Dark experiment in which we varied the reward structure using
spurious traps and the observation space using random visual occlusions. In
each section, we calculate the results of the planner performances for 1000
testing episodes for Floor Positioning and 500 for 3D Light-Dark. For online
planning speed, VTS takes around 0.26 seconds to plan for Floor Positioning
and 0.80 seconds for 3D Light-Dark on average, while other planners require
less than 0.05 seconds for both problems. The experimental summary figures are
given in Fig. 3. In addition, the full tabular summary is given in Appendix A,
VTS training data details in Appendix B, and the hyperparameters and
computation details in Appendix C.

Figure 3: The results of 4 different planners, VTS, DualSMC, DVRL, and PlaNet,
on Floor Positioning and 3D Light-Dark. Sub figures denote: (a) training time,
(b) steps taken, (c) task success, and (d) episode reward.

###  5.1 Floor Positioning Problem

In this problem, a robotic agent is randomly placed around the center of
either the top or the bottom floor, and it must infer its position by relying
on a radar-like observation in all four cardinal directions, which bounces off
the nearest wall. The top and bottom floors are indistinguishable within the
“corridor states” of the hallways, but the robotic agent can take advantage of
the “wall states” by traveling closer to the top or bottom walls of each
floor, where it can receive different observations due to the different wall
placements in each floor. The agent must reach the goal and avoid the trap,
where the goal is the left end of the hallway in the top floor and right end
in the bottom floor, and the trap is at the opposite side of the goal in each
floor.

[Initial Belief] [Localization] [Reaching Goal]

Figure 4: Example VTS behavior for Floor Positioning, where the planner starts
the problem with the initial belief (a), localizes in the wall states (b), and
successfully reaches the goal (c).

#### Planner comparison.

Overall, VTS is the most successful among the three planners with reasonable
online planning time and steps taken, while requiring less than half the
training time compared to the other planners. In Fig. 4, we show an example
trajectory of the VTS agent, in which the agent quickly localizes in the wall
states and then reaches the goal.

The VTS system gains significant performance optimality and efficiency by
balancing offline training and online planning. Specifically, VTS training is
quick since it does not rely on planner performance and only needs to be
supplied with relevant state and observation batches. However, other online
training algorithms require the policy to interact with the environment, and
as such, much of the time is spent earlier in the training episodes when the
planner can neither localize nor reach the goal. Since tree search methods
learn the policy online and are more difficult to parallelize, they typically
trade off the offline training time with the online learning and planning
time. Despite the longer planning, VTS plans reasonably fast while maintaining
the efficiency and flexibility of an online planner. We also tested DualSMC
with a known $T$ model to ensure VTS is not given an advantage by knowing $T$
for model-based planning, but observed no statistically significant difference
in performance.

###  5.2 3D Light-Dark Problem

Figure 5: Example schema for 3D Light-Dark, localizing in the light region to
reach the goal in the dark region.

The Light-Dark problem is a family of problems in which an agent starting in a
“dark” region can localize by taking a detour into a “light” region before
reaching the goal. Observations are noisier in the dark region than in the
light region. The 3D Light-Dark problem extends this problem to have 3D image
observations with salt-and-pepper pixel-wise noise.

The observations consist of $32\times 32\times 3$ RGB images from the agent’s
perspective. Our environment is more challenging to reason with than the one
in Wang et al. (2020), since the RGB images are rendered from a realistic
hallway scene dataset rather than a synthetic environment. The agent receives
a reward for reaching the goal and a penalty if it enters a “trap”.

#### Planner comparison.

Figure 6: VTS can localize without light observations (top), unlike DualSMC
(bottom).

In the Light-Dark problem and its variants, VTS performs the best among four
planners not only by taking full advantage of the image features, but also by
being able to adapt to different reward structures and distribution shifts in
the noisy observations during test time. Also, DualSMC sometimes fails to have
successful training seeds, and DVRL and PlaNet have lower task success rates
despite all successful training seeds.

Among the successful training seeds for DualSMC, VTS and DualSMC have
comparable success rates, but the VTS planner takes fewer steps to reach the
goal. While this is only 4.5 steps difference on average, further inspection
of the planner trajectories in Fig. 6 reveals an interesting insight. Unlike
the traditional light-dark problems, the VTS results for 3D Light-Dark suggest
that the planner in fact is able to localize solely with the noisy
observations in the dark region. This shows that while the salt-and-pepper
noise observations are hard to interpret, the corrupted RGB images actually
contain sufficient information to localize given enough observations.

#### Test-time changes: Spurious traps.

VTS has additional advantages in its robustness and adaptability, which we
showcase through experiments on modified Light-Dark environments. First, to
test the adaptability of different planners on test-time reward structure
difference, we perform an ablation with spurious traps that appear during test
time. These regions could represent the presence of unforeseen obstacles or
hazards. Over 500 testing episodes, we randomly generate the locations of two
$0.5\times 0.5$ square traps over a particular strip in the environment and
compare the performances of the models without additional training or
modification.

Figure 7: VTS can avoid new test time traps (top), while other planners like
DVRL disregard the traps (bottom).

Since VTS uses an online planner, it can easily adapt to new reward structures
at test time without the need to retrain an entire planner. We see in Fig. 7
that while the other planners ignore these new trap regions because they are
not represented by their models, the VTS planner is able to take into account
rewards seen while planning. Thus, while the success rate of all planners
remains similar to the vanilla experiment, VTS achieves a much higher reward
than all other planners while taking more steps as it actively tries to avoid
these traps.

#### Test-time changes: Image occlusions.

Second, we compare planner performances when the form of the noise in the
image observations changes during test time. During test time only, images
seen in the dark region contain random blacked out $15\times 15$ squares
instead of salt-and-pepper noise.

Figure 8: VTS can optimally plan even with occlusions (top), while other
planners like PlaNet fail to reach the goal (bottom).

We also find that VTS is robust to distribution shifts in the image noise at
test time. Fig. 8 shows VTS maintaining a good success rate and number of
steps taken, while other planners are struggling to generalize to this new
scenario. The additional robustness of VTS seems to be due to the $Z_{\theta}$
and $P_{\phi}$ models being trained with high fidelity data samples through
random batch sampling or exploration.

In contrast, other planners that use on-policy training and complex non-
separable architectures suffer from such distribution shifts. This is likely
due to lack of control over on-policy exploration and the inability to cover
many possible scenarios with such limited interaction with the environment.
Due to this difference in data variation, we conjecture that the $Z_{\theta}$
and $P_{\phi}$ models in VTS learn more precise and robust features.

##  6 Conclusion

The development of Visual Tree Search suggests new ways to think about
integrating uncertainty-aware learning and control. VTS demonstrates that a
more principled integration of control and planning techniques both
illuminates the interpretability of each model component and saves training
time by cleanly partitioning what each network is responsible for. This
benefits researchers and practitioners alike, as a more interpretable and
theoretically principled planner that is also quicker to train is beneficial
in many practical safety critical scenarios with limited training resources.

Our work also raises the question of what is the most natural, effective, and
safety-ensured method of combining pre-existing controllers and planners,
which are extensively studied both theoretically and experimentally, with
learning-based components, which can model many complex functions and
phenomena. VTS is one such way of accomplishing that goal, but there are other
ways to achieve principled integration of learning and control.

## Acknowledgments

This material is based upon work supported by a DARPA Assured Autonomy Grant
No. FA8750-18-C-0101, the SRC CONIX program No. 2018-JU-2779, NSF CPS
Frontiers No. CPS-1545126, the ONR Multibody Control Systems Basic Research
Challenge No. N000141812214, Google-BAIR Commons, University of Colorado
Boulder, the NASA University Leadership Initiative Grant No. 80NSSC20M0163,
and the National Science Foundation Graduate Research Fellowship Program under
Grant Nos. DGE 1752814 and DGE 2146752. Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
authors and do not necessarily reflect the views of any aforementioned
organizations.

## References

  * Ai et al. (2022) Bo Ai, Wei Gao, Vinay, and David Hsu.  Deep visual navigation under partial observability.  In _2022 International Conference on Robotics and Automation (ICRA)_ , pages 9439–9446, 2022.
  * Alet et al. (2018) Ferran Alet, Tomas Lozano-Perez, and Leslie P. Kaelbling.  Modular meta-learning.  volume 87 of _PMLR_ , pages 856–868. PMLR, 29–31 Oct 2018.
  * Andreas et al. (2016) Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein.  Neural module networks.  In _IEEE CVPR_ , June 2016.
  * Armeni et al. (2017) I. Armeni, A. Sax, A. R. Zamir, and S. Savarese.  Joint 2D-3D-Semantic Data for Indoor Scene Understanding.  _ArXiv e-prints_ , February 2017.
  * Ayer et al. (2012) Turgay Ayer, Oguzhan Alagoz, and Natasha K. Stout.  A POMDP approach to personalize mammography screening decisions.  _Operations Research_ , 60(5):1019–1034, 2012\.
  * Bai et al. (2015) Haoyu Bai, Shaojun Cai, Nan Ye, David Hsu, and Wee Sun Lee.  Intention-aware online POMDP planning for autonomous driving in a crowd.  In _IEEE ICRA_ , pages 454–460, Seattle, WA, USA, 2015. IEEE.
  * Bertsekas (2005) D. Bertsekas.  _Dynamic Programming and Optimal Control_.  Massachusetts: Athena Scientific, 2005.
  * Browne et al. (2012) C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton.  A survey of monte carlo tree search methods.  _IEEE T-CIAIG_ , 4(1):1–43, 2012.
  * Corenflos et al. (2021) Adrien Corenflos, James Thornton, George Deligiannidis, and Arnaud Doucet.  Differentiable particle filtering via entropy-regularized optimal transport.  In _ICML_ , volume 139 of _PMLR_ , pages 2100–2111. PMLR, 18–24 Jul 2021.
  * Devin et al. (2017) Coline Devin, Abhishek Gupta, Trevor Darrell, Pieter Abbeel, and Sergey Levine.  Learning modular neural network policies for multi-task and multi-robot transfer.  In _IEEE ICRA_ , pages 2169–2176. IEEE, 2017.
  * Garg et al. (2019) Neha P. Garg, David Hsu, and Wee Sun Lee.  DESPOT-$\alpha$: Online POMDP planning with large state and observation spaces.  In _RSS_ , 2019.
  * Guillén et al. (2005) María Elena López Guillén, Luis Miguel Bergasa, Rafael Barea, and María Soledad Escudero.  A navigation system for assistant robots using visually augmented pomdps.  _Auton. Robots_ , 19(1):67–87, 2005.
  * Ha and Schmidhuber (2018) David Ha and Jürgen Schmidhuber.  Recurrent world models facilitate policy evolution.  In _NeuRIPS_ , pages 2451–2463. Curran Associates, Inc., 2018.
  * Hafner et al. (2019) Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson.  Learning latent dynamics for planning from pixels.  In _International Conference on Machine Learning_ , pages 2555–2565, 2019.
  * Hoerger and Kurniawati (2020) Marcus Hoerger and Hanna Kurniawati.  An on-line POMDP solver for continuous observation spaces.  _ArXiv e-prints_ , 2020.
  * Holland et al. (2013) Jessica E. Holland, Mykel J. Kochenderfer, and Wesley A. Olson.  Optimizing the next generation collision avoidance system for safe, suitable, and acceptable operational performance.  _Air Traffic Control Quarterly_ , 21(3):275–297, 2013.
  * Hudson and Manning (2018) Drew Arad Hudson and Christopher D. Manning.  Compositional attention networks for machine reasoning.  In _ICLR_ , 2018.
  * Igl et al. (2018) Maximilian Igl, Luisa Zintgraf, Tuan Anh Le, Frank Wood, and Shimon Whiteson.  Deep variational reinforcement learning for POMDPs.  In _ICML_ , volume 80 of _PMLR_ , pages 2117–2126. PMLR, 10–15 Jul 2018.
  * Jonschkowski et al. (2018) Rico Jonschkowski, Divyam Rastogi, and Oliver Brock.  Differentiable particle filters: End-to-end learning with algorithmic priors.  In _RSS_ , Pittsburgh, Pennsylvania, June 2018.
  * Kaelbling et al. (1998) Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra.  Planning and acting in partially observable stochastic domains.  _Artificial Intelligence_ , 101(1):99 – 134, 1998\.
  * Karkus et al. (2017) Peter Karkus, David Hsu, and Wee Sun Lee.  Qmdp-net: Deep learning for planning under partial observability.  In _NeuRIPS_ , volume 30. Curran Associates, Inc., 2017.
  * Karkus et al. (2018) Peter Karkus, David Hsu, and Wee Sun Lee.  Integrating algorithmic planning and deep learning for partially observable navigation.  _ArXiv e-prints_ , 2018.
  * Karkus et al. (2020) Peter Karkus, Anelia Angelova, Vincent Vanhoucke, and Rico Jonschkowski.  Differentiable mapping networks: Learning structured map representations for sparse visual localization.  In _IEEE ICRA_ , pages 4753–4759, 2020.
  * Karkus et al. (2021) Peter Karkus, Shaojun Cai, and David Hsu.  Differentiable slam-net: Learning particle slam for visual navigation.  In _IEEE CVPR_ , pages 2815–2825, June 2021.
  * Kirsch et al. (2018) Louis Kirsch, Julius Kunze, and David Barber.  Modular networks: Learning to decompose neural computation.  In _NeuRIPS_ , volume 31. Curran Associates, Inc., 2018.
  * Kochenderfer (2015) Mykel J. Kochenderfer.  _Decision Making Under Uncertainty: Theory and Application_.  Massachusetts: MIT Press, 2015.
  * Kurniawati and Yadav (2016) Hanna Kurniawati and Vinay Yadav.  An online POMDP solver for uncertainty planning in dynamic environment.  In _Robotics Research_ , pages 611–629. Springer, 2016.
  * Lee et al. (2017) Gilwoo Lee, Siddhartha S. Srinivasa, and Matthew T. Mason.  GP-ILQG: Data-driven robust optimal control for uncertain nonlinear dynamical systems.  _ArXiv e-prints_ , 2017.
  * Lim et al. (2020) Michael H. Lim, Claire Tomlin, and Zachary N. Sunberg.  Sparse tree search optimality guarantees in POMDPs with continuous observation spaces.  In _IJCAI_ , pages 4135–4142. International Joint Conferences on Artificial Intelligence, Inc., 7 2020.
  * Lim et al. (2021) Michael H. Lim, Claire J. Tomlin, and Zachary N. Sunberg.  Voronoi progressive widening: Efficient online solvers for continuous state, action, and observation POMDPs.  In _IEEE CDC_ , pages 4493–4500, 2021.
  * Lim et al. (2022) Michael H. Lim, Andy Zeng, Brian Ichter, Maryam Bandari, Erwin Coumans, Claire Tomlin, Stefan Schaal, and Aleksandra Faust.  Multi-task learning with sequence-conditioned transporter networks.  In _IEEE ICRA_ , pages 2489–2496, 2022.
  * Mern et al. (2021) John Mern, Anil Yildiz, Zachary Sunberg, Tapan Mukerji, and Mykel J. Kochenderfer.  Bayesian optimized Monte Carlo planning.  In _AAAI_. AAAI Press, 2021.
  * Meyerson and Miikkulainen (2018) Elliot Meyerson and Risto Miikkulainen.  Beyond shared hierarchies: Deep multitask learning through soft layer ordering.  In _ICLR_ , 2018.
  * Mirza and Osindero (2014) Mehdi Mirza and Simon Osindero.  Conditional generative adversarial nets.  _ArXiv e-prints_ , 2014.
  * Mittal et al. (2020) Sarthak Mittal, Alex Lamb, Anirudh Goyal, Vikram Voleti, Murray Shanahan, Guillaume Lajoie, Michael Mozer, and Yoshua Bengio.  Learning to combine top-down and bottom-up signals in recurrent neural networks with attention over modules.  In _ICML_ , volume 119 of _PMLR_ , pages 6972–6986. PMLR, 2020\.
  * Mnih et al. (2013) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  In _NeurIPS Deep Learning Workshop_. 2013.
  * Papadimitriou and Tsitsiklis (1987) Christos H. Papadimitriou and John N. Tsitsiklis.  The complexity of Markov decision processes.  _Mathematics of Operations Research_ , 12(3):441–450, 1987.
  * Piché et al. (2019) Alexandre Piché, Valentin Thomas, Cyril Ibrahim, Yoshua Bengio, and Chris Pal.  Probabilistic planning with sequential monte carlo methods.  In _ICLR_ , 2019.
  * Rosenbaum et al. (2018) Clemens Rosenbaum, Tim Klinger, and Matthew Riemer.  Routing networks: Adaptive selection of non-linear functions for multi-task learning.  In _ICLR_ , 2018.
  * Silver and Veness (2010) David Silver and Joel Veness.  Monte-Carlo planning in large POMDPs.  In _NeuRIPS_ , pages 2164–2172. Curran Associates, Inc., 2010.
  * Singh et al. (2021) Gautam Singh, Skand Peri, Junghyun Kim, Hyunseok Kim, and Sungjin Ahn.  Structured world belief for reinforcement learning in POMDP.  In _ICML_ , volume 139, pages 9744–9755. PMLR, 18–24 Jul 2021.
  * Sohn et al. (2015) Kihyuk Sohn, Honglak Lee, and Xinchen Yan.  Learning structured output representation using deep conditional generative models.  In _NeuRIPS_ , volume 28. Curran Associates, Inc., 2015.
  * Sunberg and Kochenderfer (2018) Zachary Sunberg and Mykel J. Kochenderfer.  Online algorithms for POMDPs with continuous state, action, and observation spaces.  In _ICAPS_ , Delft, Netherlands, 2018. AAAI Press.
  * Sunberg et al. (2017) Zachary N. Sunberg, Christopher J. Ho, and Mykel J. Kochenderfer.  The value of inferring the internal state of traffic participants for autonomous freeway driving.  In _ACC_ , pages 3004–3010, Seattle, WA, USA, 2017. IEEE.
  * Todorov and Li (2005) E. Todorov and Weiwei Li.  A generalized iterative lqg method for locally-optimal feedback control of constrained nonlinear stochastic systems.  In _ACC_ , volume 1, pages 300–306, 2005.
  * Van Den Berg et al. (2012) Jur Van Den Berg, Sachin Patil, and Ron Alterovitz.  Motion planning under uncertainty using iterative local optimization in belief space.  _International Journal of Robotics Research_ , 31(11):1263–1278, 2012.
  * Wang et al. (2020) Yunbo Wang, Bo Liu, Jiajun Wu, Yuke Zhu, Simon S. Du, Li Fei-Fei, and Joshua B. Tenenbaum.  Dualsmc: Tunneling differentiable filtering and planning under continuous pomdps.  In _IJCAI_ , pages 4190–4198. International Joint Conferences on Artificial Intelligence Organization, 7 2020.
  * Yang et al. (2020) Ruihan Yang, Huazhe Xu, Yi Wu, and Xiaolong Wang.  Multi-task reinforcement learning with soft modularization.  _ArXiv e-prints_ , 2020.
  * Ye et al. (2017) Nan Ye, Adhiraj Somani, David Hsu, and Wee Sun Lee.  DESPOT: Online POMDP planning with regularization.  _Journal of Artificial Intelligence Research_ , 58:231–266, 2017.
  * Young et al. (2013) Steve Young, Milica Gašić, Blaise Thomson, and Jason D Williams.  POMDP-based statistical spoken dialog systems: A review.  _IEEE_ , 101(5):1160–1179, 2013.
  * Zhang et al. (2019) Marvin Zhang, Sharad Vikram, Laura M. Smith, Pieter Abbeel, Matthew J. Johnson, and Sergey Levine.  SOLAR: deep structured representations for model-based reinforcement learning.  In _ICML_ , volume 97, pages 7444–7453, 2019.
  * Zhao et al. (2017) Shengjia Zhao, Jiaming Song, and Stefano Ermon.  Towards deeper understanding of variational autoencoding models.  _ArXiv e-prints_ , 2017.

## Appendix

##  Appendix A Tabular Summary of Experimental Results

Table 1: Summary of planner performances on the Floor Positioning problem and the 3D Light-Dark problem variants. Each column reports the mean of means estimator over different seeds, and $\pm$ indicates one standard error of the estimator. Mean particle distance is defined as the mean of the distance between the mean belief state and the true state. All statistics are for when the agent is successful. Planner & Problem | Task | Episode | Steps | Training | Planning | Particle
---|---|---|---|---|---|---
(Successful Trials) | Success (%) | Reward | Taken | Time (h) | Time (s) | Distance
Floor Positioning |  |  |  |  |  |
VTS | (10/10) | 97.6 $\pm 0.002$ |  99.36 $\pm$ 0.12 | 28.85 $\pm 0.28$ |  5.88 $\pm 0.02$ | 0.26 $\pm 0.0022$ |  0.07 $\pm 0.002$
DualSMC | (10/10) | 94.0 $\pm 0.049$ |  100.0 $\pm 0.0$ | 24.78 $\pm 0.70$ |  14.27 $\pm 2.39$ | 0.04 $\pm 0.0003$ |  0.08 $\pm 0.003$
DVRL | (10/10) | 91.0 $\pm 0.084$ |  100.0 $\pm 0.0$ | 45.71 $\pm 9.01$ |  12.74 $\pm 0.72$ | 0.0063 $\pm 6.4$e-5 | –
3D Light-Dark |  |  |  |  |  |
VTS | (10/10) | 99.6 $\pm 0.002$ |  98.71 $\pm$ 0.22 | 18.18 $\pm$ 0.76 |  9.42 $\pm 0.21$ | 0.76 $\pm$ 0.005 |  0.48 $\pm$ 0.07
DualSMC | (6/10) | 99.0 $\pm 0.009$ |  98.05 $\pm$ 0.62 | 22.71 $\pm$ 1.70 |  20.31 $\pm 3.13$ | 0.06 $\pm$ 0.003 |  0.50 $\pm$ 0.02
DVRL | (10/10) | 76.1 $\pm 0.081$ |  91.88 $\pm$ 2.2 | 55.33 $\pm$ 6.94 |  80.65 $\pm 1.18$ | 0.0076 $\pm 3.0$e-4 | –
PlaNet | (4/4) | 72.7 $\pm 0.029$ |  89.35 $\pm$ 4.84 | 27.1 $\pm$ 2.67 |  157.1 $\pm 0.66$ | 0.061 $\pm 4.1$e-4 | –
3D LD + Traps |  |  |  |  |  |
VTS |  | 97.7 $\pm 0.003$ |  85.34 $\pm 3.33$ | 27.96 $\pm 1.06$ | – | 0.80 $\pm 0.0039$ |  0.42 $\pm 0.06$
DualSMC |  | 99.2 $\pm 0.007$ |  0.48 $\pm 4.45$ | 22.55 $\pm 1.80$ | – | 0.06 $\pm 0.0006$ |  0.49 $\pm 0.02$
DVRL |  | 76.6 $\pm 0.078$ |  -136.14 $\pm 34.42$ | 55.79 $\pm 6.34$ | – | 0.0076 $\pm 2.9$e-4 | –
PlaNet |  | 67.6 $\pm 0.016$ |  35.41 $\pm 3.38$ | 28.31 $\pm 2.63$ | – | 0.061 $\pm 7.1$e-4 | –
3D LD + Occlusions |  |  |  |  |  |
VTS |  | 97.0 $\pm 0.007$ |  91.05 $\pm 1.73$ | 33.25 $\pm 1.33$ | – | 0.77 $\pm 0.0051$ |  0.82 $\pm 0.08$
DualSMC |  | 78.3 $\pm 0.052$ |  17.45 $\pm 7.82$ | 46.38 $\pm 0.97$ | – | 0.06 $\pm 0.0005$ |  0.91 $\pm 0.03$
DVRL |  | 72.9 $\pm 0.081$ |  77.0 $\pm 7.97$ | 62.32 $\pm 4.56$ | – | 0.0075 $\pm 3.1$e-4 | –
PlaNet |  | 36.8 $\pm 0.078$ |  75.07 $\pm 14.55$ | 34.62 $\pm 3.69$ | – | 0.059 $\pm 5.4$e-4 | –

For all methods, the episode length was $200$ steps. If the agent reached the
goal in under $200$ steps, this was considered a success with a positive
reward of $100$ and a termination of the episode. Entrance into traps incurred
a negative reward of $-100$ per entry. This is with the exception of DVRL, in
which rewards were scaled to lie between $-1$ and $1$ to ensure stability of
the training. The DVRL rewards reported here are scaled by $100$.

In addition to statistics such as the success rate, reward, and so on, we have
provided values for the number of successful trials for the method. This is
because certain seeds for DualSMC failed to produce any goal-reaching behavior
at all during training. Since the provided statistics are only for episodes in
which the goal was reached, those seeds of DualSMC were dropped entirely.

The prohibitive training time of PlaNet allowed for only $4$ trials to be run
with reasonable computational resources. Training for all methods was done on
NVIDIA Tesla K80 GPUs.

Note that the “planning time” reported for DVRL is actually the time to run
the forward pass of the DVRL policy, since the method does not perform
planning. The number has been provided to display that aspect of the
algorithm.

##  Appendix B VTS Training Data Generation Details

The open source code for our implementations will be available at
https://github.com/michaelhlim/VisualTreeSearch.

###  B.1 Floor Positioning

We trained the $Z_{\theta},P_{\phi}$, and $G_{\xi}$ models with random data
batches. $Z_{\theta}$ and $P_{\phi}$ were provided with random batches of
samples $(s_{t},o_{t},\\{\hat{s}_{t,i}\\})$, with $s_{t}=(x_{t},y_{t})$ being
the agent’s position. The $\\{\hat{s}_{t,i}\\}$ were generated from a normal
distribution centered at $s_{t}$ with standard deviation 0.01. $G_{\xi}$ was
provided with random batches of samples $(s_{t},o_{t})$, where for each batch
we sampled the $s_{t}$ and generated each $o_{t}$ from the corresponding
$s_{t}$. The sampling procedure for the states was biased towards the wall
states, since those states were more difficult to learn from. Specifically,
for $Z_{\theta}$ and $P_{\phi}$, in each batch a state would be chosen from a
wall with $0.5$ probability and from anywhere in the environment with $0.5$
probability. For $G_{\xi}$, in each batch a state would be chosen from a wall
with $0.5$ probability, from a non-wall area with $0.375$ probability, and
from anywhere in the environment with $0.125$ probability.

###  B.2 3D Light-Dark

To train the $Z_{\theta}$ and $P_{\phi}$ models, we employed the following
procedure. Each training batch consisted of random batches of samples
$(s_{t},\theta_{t},o_{t},\\{\hat{s}_{t,i}\\})$, where $s_{t}=(x_{t},y_{t})$.
The agent’s location could be described by both its position $s_{t}$ and its
heading $\theta_{t}$, though only $s_{t}$ was unknown. In each batch,
$\theta_{t}$ was discretely chosen from $[0,2\pi)$ at intervals of $\pi/4$.
This is because the agent’s actions were in the form of discrete commands
instantaneously changing its heading. If $s_{t}$ was in the dark region, then
the $\\{\hat{s}_{t,i}\\}$ were generated from a normal distribution centered
at $s_{t}$ with standard deviation 0.1, and 0.01 for the light region. The
difference in standard deviation was to enable the $Z_{\theta}$ and $P_{\phi}$
models to cause better localization in the light region than in the dark
region. The two models were trained on a schedule that gradually introduced
noise in the image observations $o_{t}$ over the training epochs. In contrast,
$G_{\xi}$ was trained simply with the random batches
$(s_{t},\theta_{t},o_{t})$ without the noise schedule, as if it were data
collected by a randomly exploring agent. However, both sets of models could be
trained either way in principle. For these conditional generative models, the
concatenation of $s_{t}$ and $\theta_{t}$ formed the conditional variable.

###  B.3 On-Policy Refining

Technically, we could employ additional on-policy learning to refine the
networks to focus on parts of the problem that are relevant for a given task
as done in training DPF-based policies (Jonschkowski et al., 2018). However,
we found that on-policy learning does not significantly improve performance in
addition to regular training, since the planner often successfully and quickly
reaches the goal and does not provide many new samples in areas where the
models need improvement.

##  Appendix C Hyperparameters and Computation Details

Table 2 shows the hyperparameters used in training and filtering for VTS. Our
models were trained on NVIDIA Tesla K80 GPUs. The hyperparameters for DualSMC
training remained the same as the original work (Wang et al., 2020). For 3D
Light-Dark, we maintained a training pool of data to draw random batches of
samples from instead of generating image observations at every training step.

Table 2: Summary of hyperparameters used in training and filtering. Hyperparameters | Floor Positioning | 3D Light-Dark
---|---|---
Training gradient steps | 500,000 | 100,000
Training sample pool size | - | 16,000
Learning rate | 0.001 | 0.0003
Batch size | 64 | 64
Filtering particles | 100 | 100
Percent of particles proposed | 0.3 | 0.3
Resampling frequency | 3 | 3

Unlike DualSMC, VTS does not use an LSTM as one of the intermediate layers in
$Z_{\theta}$ because $Z_{\theta}$ is trained offline from randomly collected
data. We observed that this would result in particle de-localization, as the
observation density could not propagate forward the localized information. In
essence, the VTS solver would be quick to localize, but sometimes would need
to take a detour in order to re-localize. Particle de-localization has been
observed before in the literature and there are many potential methods to
remedy this problem. We found an exponential decay of the number of particles
proposed, as suggested by Wang et al. (2020), to provide the best results and
solve the issue. That is, for episode step number $n$ and nominal particle
proposal amount $p$, the number of particles proposed is $p*\gamma_{d}^{n}$.
We set the decay rate $\gamma_{d}$ to $0.9$.

Table 3 shows the hyperparameters used for PFT-DPW planner. While
hyperparameters for tree search planners are often chosen with hyperparameter
sweeps and/or optimization, such meta-optimization in our algorithm would mean
having to run our algorithm on a GPU numerous times, which was practically
very inefficient. Thus, the hyperparameters were manually chosen via a
combination of inspection and prior experience. For both Floor Positioning and
3D Light-Dark, we found the rollout strategy that yielded the best results to
be one in which we assume that the uncertainty in the current belief collapses
in the next step. Essentially, we select a random particle from the belief and
calculate its straight-line direction and distance to the goal. We use this
distance to estimate the discounted reward associated with that particle. We
add that with the weighted sum of rewards obtained when all other particles
move in that same direction and distance.

Table 4 shows some parameters for the Floor Positioning and 3D Light-Dark
environments. The environment parameters for Floor Positioning were left
unchanged from Wang et al. (2020).

Across all baseline planning methods, the dimension of the action varied
according to the problem in accordance with Wang et al. (2020); for the Floor
Positioning problem, the action dimension was $2$, representing a change in
the 2D state. For the 3D Light-Dark problem, the action dimension was $1$,
representing a change in the agent’s orientation. DVRL, however, was found to
produce the best performance when the action was 2D for both problems.

Table 3: Summary of hyperparameters used in PFT-DPW. | $n$ | $c$ | $k_{a}$ | $\alpha_{a}$ | $k_{o}$ | $\alpha_{o}$ | $m$ | $H$ | $\gamma$
---|---|---|---|---|---|---|---|---|---
Floor Positioning |  |  |  |  |  |  |  |  |
| 100 | 10.0 | 3.0 | $\frac{1}{4}$ | 4.0 | $\frac{1}{4}$ | 100 | 10 | 0.99
3D Light-Dark |  |  |  |  |  |  |  |  |
| 100 | 10.0 | 3.0 | $\frac{1}{4}$ | 4.0 | $\frac{1}{4}$ | 100 | 10 | 0.99
Table 4: Summary of environment parameters. Hyperparameters | Floor Positioning | 3D Light-Dark
---|---|---
Observation size | 4 | 32 $\times$ 32 $\times$ 3
Agent velocity | 0.05 | 0.2
Noise amount (image) | - | 40$\%$
Occlusion amount (image) | - | 15 $\times$ 15

For the 3D Light-Dark problem, the $Z_{\theta}$ and $P_{\phi}$ modules were
trained with a gradual noise schedule that was as follows: for the first $1/4$
of the number of training epochs, the images in the training data had $0\%$
noise. For the next $1/4$ of the epochs, the images corresponding to states in
the dark region had $final\;noise\;\%*1/4$ noise. For the next $1/4$ of the
epochs, the images had $final\;noise\;\%*1/2$ noise. For the final $1/4$ of
the epochs, the images had the full $final\;noise\;\%$. (As seen in Table 4,
$final\;noise\;\%$ was $40\%$.) This percentage corresponds to the percent of
locations on the $32\times 32$ image that were corrupted by the salt-and-
pepper noise.

Finally, Table 5 shows the neural network architecture details for the $Z,P,G$
models we trained on different experimental domains. We note here that
although VTS and DualSMC differ in the architectures of their $Z_{\theta}$ and
$P_{\phi}$ models in that the networks for VTS have deeper structures than
those for DualSMC, we did not see any noticeable increase in performance for
DualSMC with the deeper architectures in a preliminary exploration.

Table 5: Network details. Model | Layers | # Channels
---|---|---
Floor Positioning |  |
$Z_{\theta}$ | 5-layer MLP | $256\times 3,128,16$
| Concat: state | $18$
| 3-layer MLP | $256\times 2,1$
$P_{\phi}$ | 3-layer MLP | $256\times 2,64$
| Concat: $z(64)\sim\mathcal{N}(0,1)$ | $128$
| 4-layer MLP | $256\times 3,2$
$G_{\xi}$ Encoder | 5-layer MLP |  $256\times 4$, 64
| 1 layer to output $\mu$, $\sigma$ | 64
Decoder | 5-layer MLP |  $256\times 4$, 4
3D Light-Dark |  |
$Z_{\theta}$ | Conv2d, filter (3, 3), stride 1 | num image channels
| Conv2d $\times$ 4, filter (3, 3), stride 2 | 32, 64, 128, 256
| Conv2d, filter (3, 3), stride 1 | 512
| 3-layer MLP | 1024, 512, 256
| Normalize output (*) | 256
| 3-layer MLP | 256 $\times$ 3
| Concat: state, orientation | 259
| 4-layer MLP | 128 $\times$ 3, 1
$P_{\phi}$ | Same as $Z_{\theta}$ up to (*) | 256
| 1-layer MLP | 256
| Concat: $z(256)\sim\mathcal{N}(0,1)$, orientation | 513
| 3-layer MLP | 128 $\times$ 2, 2
$G_{\xi}$ Encoder | Same as $Z_{\theta}$ up to (*) | 256
| Concat: state, orientation | 259
| 5-layer MLP | 256 $\times$ 4, 128
| 1 layer MLP to output $\mu$, $\sigma$ | 128
Decoder | Concat $z(128)\sim\mathcal{N}(0,1)$, state, orientation | 131
| 5-layer MLP | 256 $\times$ 5
| 3-layer MLP | 256, 512, 1024
| Conv2dTranspose $\times$ 3, filter (3, 3), stride 2 | 128, 64, 32
| Conv2d, filter (3, 3), stride 2 | num image channels

##  Appendix D Stanford 3D Light-Dark Environment Implementation Details

Figure 9: The overview diagram of the 3D Light-Dark problem implemented using
the Stanford dataset (left), and a top-down map of a floor in a building in
the Stanford dataset that we use to recreate the 3D Light-Dark problem
(right).

Fig. 9 shows the overview diagram of the 3D Light-Dark problem implemented
using the Stanford dataset (left), and a top-down map of a floor in a building
in the Stanford dataset (right).

The environment diagram depicts the “trap” regions in orange, the goal region
in green, and the agent in blue. The agent’s location is given by
$(x,y,\theta)$, where $x,y$ are the unknown absolute position coordinates and
$\theta$ is the known heading. The shaded part of the environment depicts the
“dark” region, where the image observations received by the agent are
corrupted by salt-and-pepper noise. The rest of the environment is in the
“light”, where the image observations are uncorrupted. The darkest gray region
is a wall region that the agent cannot enter. The agent’s initial state is
randomly chosen from a strip in the dark region.

In the top-down map, the red rectangle denotes the part of the building that
forms our environment (top right). We chose a subset of the Stanford dataset
region in order to replicate the exact settings of the 3D Light-Dark problem
in Wang et al. (2020). However, since our 3D Light-Dark implementation uses
realistic images rendered with the Stanford dataset as opposed to using
synthetic backgrounds generated with the DeepMind simulation platform, our
problem is more realistic and challenging.

##  Appendix E Baseline Planner Implementation Details

We compare the performance of VTS against two baselines in addition to
DualSMC: Deep Variational Reinforcement Learning for POMDPs (DVRL), and Deep
Planning Network (PlaNet).

We evaluated DVRL in both the Floor Positioning and 3D Light-Dark environments
and PlaNet in the 3D Light-Dark environment. This was so that we could
minimally modify the model architectures provided by the two methods; while
DVRL architectures supported both vector and image observations, the PlaNet
architecture only supported image observations. This was also the reason for
running the PlaNet 3D Light-Dark experiments with $64\times 64$ images while
all other baselines and VTS used $32\times 32$ images. In this way, the
baselines were advantaged in our comparisons.

###  E.1 DVRL

Table 6 shows the parameters modified when running DVRL, with all other
parameters unchanged from the original work. For Floor Positioning, a sweep
was performed over the encoder channel dimensions, presence of the BatchNorm,
multiplier backprop length, and number of particles. For 3D Light-Dark, a
sweep was performed over the number of environment processes, number of
environment steps per gradient step, and multiplier backprop length to balance
performance and computation time.

Since the DVRL implementation is designed to produce trajectories in the
environment by running multiple environment processes in parallel, we
performed both training and testing in this multiprocessing framework. For
testing, we ran $2$ environment processes in parallel and collected the $1000$
testing episodes for Floor Positioning and $500$ testing episodes for 3D
Light-Dark from their combined results. Also, the DVRL policy produces actions
for these parallel environments at once. Therefore, the “planning time”
provided is the time for the policy to produce $2$ actions.

Table 6: Summary of DVRL environment, training, and model hyperparameters. Hyperparameters | Floor Positioning | 3D Light-Dark
---|---|---
Environment |  |
Observation size | 4 | 32 $\times$ 32 $\times$ 3
Agent velocity | 0.05 | 0.2
Noise amount (image) | – | 40$\%$
Occlusion amount (image) | – | 15 $\times$ 15
Training |  |
Number of training frames | 2.5e7 | 1.2e6
Number of env steps per gradient step | 25 | 5
Multiplier backprop length | 1 | 100
Number of particles | 10 | 10
Number of environment processes | 16 | 4
Model |  |
Encoder channel dimensions | $[64,64]$ | $[32,64,32]$
BatchNorm present | Yes | Yes
RNN latent state size ($h$) | 256 | 256
Additional latent state size ($z$) | 256 | 256
Action encoding size | 64 | 128

###  E.2 PlaNet

Table 7 shows the parameters modified when running PlaNet, with all other
parameters unchanged from the original work. A sweep was performed over action
repeat and learning rate. The occlusion amount was increased to $30$ as
compared to $15$ for the other baselines to maintain consistency with the
larger image size.

Since the action repeat for the PlaNet baseline is 2, the agent only needs to
perform the planning, which is done via the Cross Entropy Method (CEM), every
2 steps. This is because the action resulting from the plan is applied twice.
To reflect this aspect of the algorithm in the results, we divided the
obtained planning time by 2 to produce the final numbers.

Table 7: Summary of PlaNet environment and training hyperparameters. Hyperparameters | 3D Light-Dark |
---|---|---
Environment |  |
Observation size | 64 $\times$ 64 $\times$ 3 |
Agent velocity | 0.2 |
Action repeat | 2 |
Noise amount (image) | 40$\%$ |
Occlusion amount (image) | 30 $\times$ 30 |
Training |  |
Number of training steps | 1e6 |
Number of training steps per data collection phase | 100 |
Environment steps per data collection phase | 200 |
Learning rate | 1e-3 |