11institutetext: ZOZO Research, Tokyo, Japan
11email<EMAIL_ADDRESS>
# Generalization Bounds for Set-to-Set Matching with Negative Sampling

Masanari Kimura 11 0000-0002-9953-3469

###### Abstract

The problem of matching two sets of multiple elements, namely set-to-set
matching, has received a great deal of attention in recent years. In
particular, it has been reported that good experimental results can be
obtained by preparing a neural network as a matching function, especially in
complex cases where, for example, each element of the set is an image.
However, theoretical analysis of set-to-set matching with such black-box
functions is lacking. This paper aims to perform a generalization error
analysis in set-to-set matching to reveal the behavior of the model in that
task.

###### Keywords:

Set matching Generalization bound Neural networks

##  1 Introduction

The problem of matching two sets of multiple elements, namely set-to-set
matching, has received a great deal of attention in recent years [3, 6, 7,
16]. The problem is formalized as a task that, given two distinct sets, finds
the goodness of match between them. In particular, when the elements of the
set are high-dimensional, neural networks are used as the matching function
[11]. Although these strategies have been reported to work well
experimentally, there is a lack of research on their theoretical behavior. A
mathematical understanding of the behavior of the algorithm is an important
issue since a lack of theoretical research hinders the improvement of existing
algorithms for set-to-set matching.

We aim to perform a generalization error analysis of set-to-set matching
algorithms in the context of statistical learning theory [15, 14]. In
particular, existing deep learning-based set-to-set matching algorithms rely
on negative sampling, a procedure in which negative examples are randomly
generated while learning process [11]. Therefore, we clarify the theoretical
behavior of the set-to-set matching algorithm with negative sampling.

##  2 Preliminaries

Let $\bm{x}_{n},\bm{y}_{m}\in\mathfrak{X}=\mathbb{R}^{d}$ be $d$-dimensional
feature vectors representing the features of each individual item. Let
$\mathcal{X}=\\{\bm{x}_{1},\dots,\bm{x}_{N}\\}$ and
$\mathcal{Y}=\\{\bm{y}_{1},\dots,\bm{y}_{M}\\}$ be sets of these feature
vectors, where $\mathcal{X},\mathcal{Y}\in 2^{\mathfrak{X}}$ and
$N,M\in\mathbb{N}$ are sizes of the sets. The function
$f:2^{\mathfrak{X}}\times 2^{\mathfrak{X}}\to\mathbb{R}$ calculates a matching
score between the two sets $\mathcal{X}$ and $\mathcal{Y}$. Guaranteeing the
exchangeability of the set-to-set matching requires that the matching function
$f(\mathcal{X},\mathcal{Y})$ is symmetric and invariant under any permutation
of items within each set as follows.

######  Definition 1 (Permutation Invariance)

A set-input function f is said to be permutation invariant if

$\displaystyle
f(\mathcal{X},\mathcal{Y})=f(\pi_{x}\mathcal{X},\pi_{y}\mathcal{Y})$ (1)

for permutations $\pi_{x}$ on $\\{1,\dots,N\\}$ and $\pi_{y}$ on
$\\{1,\dots,M\\}$.

######  Definition 2 (Permutation Equivariance)

A map $f:\mathfrak{X}^{N}\times\mathfrak{X}^{M}\to\mathfrak{X}^{N}$ is said to
be permutation equivariant if

$\displaystyle
f(\pi_{x}\mathcal{X},\pi_{y}\mathcal{Y})=\pi_{x}f(\mathcal{X},\mathcal{Y})$
(2)

for permutations $\pi_{x}$ and $\pi_{y}$, where $\pi_{x}$ and $\pi_{y}$ are on
$\\{1,\dots,N\\}$ and $\\{1,\dots,M\\}$, respectively. Note that $f$ is
permutation invariant for permutations within $\mathcal{Y}$.

######  Definition 3 (Symmetric Function)

A map $f:2^{\mathfrak{X}}\times 2^{\mathfrak{X}}\to\mathbb{R}$ is said to be
symmetric if

$\displaystyle f(\mathcal{X},\mathcal{Y})=f(\mathcal{Y},\mathcal{X}).$ (3)

######  Definition 4 (Two-Set-Permutation Equivariance)

Given $\mathcal{X}^{(1)}\in\mathfrak{X}^{N}$ and
$\mathcal{Z}^{(2)}\in\mathfrak{X}^{M}$, a map
$f:\mathfrak{X}^{\ast}\times\mathfrak{X}^{\ast}\to\mathfrak{X}^{\ast}\times\mathfrak{X}^{\ast}$
is said to be two-set-permutation equivariant if

$\displaystyle
pf(\mathcal{Z}^{(1)},\mathcal{Z}^{(2)})=f(\mathcal{Z}^{(p(1))},\mathcal{Z}^{(p(2))})$
(4)

for any permutation operator $p$ exchanging the two sets, where
$\mathfrak{X}^{\ast}=\cup^{\infty}_{n=0}\mathfrak{X}^{n}$ indicates a sequence
of arbitrary length such as $\mathfrak{{X}^{N}}$ or $\mathfrak{X}^{M}$.

We consider tasks where the matching function f is used per pair of sets [18]
to select a correct matching. Given candidate pairs of sets
$(\mathcal{X},\mathcal{Y}^{(k)})$, where $\mathcal{X},\mathcal{Y}^{(k)}\in
2^{\mathfrak{X}}$ and $k\in\\{1,\dots,K\\}$, we choose
$\mathcal{Y}^{(k^{\ast})}$ as a correct one so that
$f(\mathcal{X},\mathcal{Y}^{(k^{\ast})})$ achieves the maximum score from
amongst the $K$ candidates.

###  2.1 Set-to-set matching with negative sampling

In real-world set-to-set matching problems, it is often the case that only
positive example set pairs can be obtained. Then, we consider training a model
for set-to-set matching with negative sampling. The learner is given positive
examples $S^{+}=\\{(\mathcal{X},\mathcal{Y})\\}^{m^{+}}_{i=1}$. Then, negative
examples $S^{-}=\\{(\mathcal{X},\mathcal{Y})\\}^{m^{-}}_{i=1}$ are generated
by randomly combining set pairs from the given sets. We assume that positive
and negative examples are drawn according to the underlying distribution
$p^{+}$ and $p^{-}$, respectively. Given training sample set
$S=(S^{+},S^{-})$, the goal of set-to-set matching with negative sampling is
to learn a real-valued score function $f:2^{\mathfrak{X}}\times
2^{\mathfrak{X}}\to\mathbb{R}$ that ranks future positive pair
$(\mathcal{X},\mathcal{Y})^{+}$ higher than negative pair
$(\mathcal{X},\mathcal{Y})^{-}$. Let $\ell$ be the loss function, which is
defined as

$\displaystyle\ell(f,Z^{+},Z^{-})\coloneqq\varphi(f(Z^{+})-f(Z^{-})),$ (5)

where $Z^{+}=(\mathcal{X},\mathcal{Y})^{+}$,
$Z^{-}=(\mathcal{X},\mathcal{Y})^{-}$ and
$\varphi:\mathbb{R}\to\mathbb{R}^{+}$ is a convex function. Typical choices of
$\varphi$ include the logistic loss

$\displaystyle\varphi(f(Z^{+})-f(Z^{-}))=\log\left\\{1+\exp(-(f(Z^{+})-f(Z^{-}))\right\\}.$
(6)

######  Definition 5 (Expected set-to-set matching loss)

Expected set-to-set matching loss $R(f)$ is defined as

$\displaystyle R(f)$ $\displaystyle\coloneqq\mathbb{E}_{Z^{+}\sim
p^{+},Z^{-}\sim p^{-}}\left[\ell(f,Z^{+},Z^{-})\right].$ (7)

######  Definition 6 (Empirical set-to-set matching loss)

Empirical set-to-set matching loss $\hat{R}(f;S)$ is defined as

$\displaystyle\hat{R}(f;S)\coloneqq\frac{1}{m^{+}m^{-}}\sum^{m^{+}}_{i=1}\sum^{m^{+}+m^{-}}_{j=m^{+}+1}\ell(f,Z^{+},Z^{-}).$
(8)

Here, we assume that $\varphi$ has the Lipschitz property with respect to
$\mathbb{R}$, i.e.,

$\displaystyle\left|\varphi(a)-\varphi(b)\right|\leq L\cdot\left|a-b\right|,$
(9)

where $a,b\in\mathbb{R}$ and $L>0$ is a Lipschitz constant.

##  3 Margin bound for set-to-set matching

Our first result is based on the Rademacher complexity.

######  Definition 7 (Empirical Rademacher complexity)

Let $\mathcal{F}$ be a family of matching score functions. Then, the empirical
Rademacher complexity of $\mathcal{F}$ with respect to the sample $S$ is
defined as

$\displaystyle\hat{\mathcal{R}}_{S}(\mathcal{F})\coloneqq\mathbb{E}_{\sigma}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum^{m}_{i=1}\sigma_{i}f(Z_{i})\right].$
(10)

######  Definition 8 (Rademacher complexity)

Let $p$ denote the distribution according to which samples are drawn. For any
integer $m\geq 1$, the Rademacher complexity of $\mathcal{F}$ is the
expectation of the empirical Rademacher complexity over all samples of size
$m$ drawn according to $p$:

$\displaystyle\mathcal{R}_{m}(\mathcal{F})\coloneqq\mathbb{E}_{S\sim
p^{m}}\left[\hat{\mathcal{R}}(\mathcal{F})\right].$ (11)

Let $p_{1}$ the marginal distribution of the first element of the pairs, and
by $p_{2}$ the marginal distribution with respect to the second element of the
pairs. Similarly, $S^{1}\sim p_{1}$ and $S^{2}\sim p_{2}$. We denote by
$\mathcal{R}^{1}_{m}$ the Rademacher complexity of $\mathcal{F}$ with respect
to the marginal distribution $p_{1}$, that is
$\mathcal{R}^{1}_{m}(\mathcal{F})=\mathbb{E}[\hat{\mathcal{R}}_{S^{1}}(\mathcal{F})]$,
and similarly
$\mathcal{R}^{2}_{m}(\mathcal{F})=\mathbb{E}[\hat{\mathcal{R}}_{S^{2}}(\mathcal{F})]$.

Here, we assume that the loss function is the following margin loss.

###### Definition 9

For any $\rho>0$, the $\rho$-margin loss is the function $\ell_{\rho}$ defined
for all $z,z^{\prime}\in\mathbb{R}$ by
$\ell_{\rho}(z,z^{\prime})=\phi(zz^{\prime})$ with,

$\displaystyle\phi_{\rho}(z)=\begin{cases}0&(\rho\leq z)\\\ 1-z/\rho&(0\leq
z\leq\rho)\\\ 1&(z\leq 0).\end{cases}$ (12)

###### Lemma 1

Let $Z\in\mathbb{R}$ be any input space, and $\mathcal{G}$ be a family of
functions mapping from $Z$ to $[0,1]$. Then, for any $\delta>0$, with
probability at least $1-\delta$, each of the following holds for all
$g\in\mathcal{G}$:

$\displaystyle\mathbb{E}[g(z)]$
$\displaystyle\leq\frac{1}{m}\sum^{m}_{i=1}g(z_{i})+2\mathcal{R}_{m}(\mathcal{G})+\sqrt{\frac{\log\frac{1}{\delta}}{2m}},$
(13) $\displaystyle\mathbb{E}[g(z)]$
$\displaystyle\leq\frac{1}{m}\sum^{m}_{i=1}g(z_{i})+2\hat{\mathcal{R}}_{S}(\mathcal{G})+3\sqrt{\frac{\log\frac{2}{\delta}}{2m}}.$
(14)

###### Proof

Let
$\psi(S)=\sup_{g\in\mathcal{G}}\mathbb{E}[g]-\frac{1}{m}\sum^{m}_{i=1}g(z_{i})$.
Then, for two samples $S$ and $S^{\prime}$, we have

$\displaystyle\psi(S^{\prime})-\psi(S)\leq\sup_{g\in\mathcal{G}}\frac{g(z_{m})-g(z^{\prime}_{m})}{m}\leq\frac{1}{m}.$

where $z_{m}\in S$ and $z^{\prime}_{m}\in S^{\prime}$. Then, by McDiarmid’s
inequality, for any $\delta>0$, with probability at least $1-\delta/2$, the
following holds.

$\displaystyle\psi(S)\leq\mathbb{E}_{S}[\psi(S)]+\sqrt{\frac{\log\frac{2}{\delta}}{2m}}.$

We next bound the expectation of the right-hand side as follows.

$\displaystyle\mathbb{E}_{S}[\psi(S)]$
$\displaystyle=\mathbb{E}_{S}\left[\sup_{g\in\mathcal{G}}\mathbb{E}[g]-\frac{1}{m}\sum^{m}_{i=1}g(z_{i})\right]$
$\displaystyle\leq\mathbb{E}_{S,S^{\prime}}\left[\sup_{g\in\mathcal{G}}\frac{1}{m}\sum^{m}_{i=1}(g(z^{\prime}_{i})-g(z_{i}))\right]$
$\displaystyle=\mathbb{E}_{\sigma,S,S^{\prime}}\left[\sup_{g\in\mathcal{G}}\frac{1}{m}\sum^{m}_{i=1}\sigma_{i}(g(z^{\prime}_{i})-g(z_{i}))\right]$
$\displaystyle\leq\mathbb{E}_{\sigma,S^{\prime}}\left[\sup_{g\in\mathcal{G}}\frac{1}{m}\sum^{m}_{i=1}\sigma_{i}g(z^{\prime}_{i})\right]+\mathbb{E}_{\sigma,S}\left[\sup_{g\in\mathcal{G}}\frac{1}{m}\sum^{m}_{i=1}-\sigma_{i}g(z_{i})\right]$
$\displaystyle=2\mathbb{E}_{\sigma,S}\left[\sup_{g\in\mathcal{G}}\frac{1}{m}\sum^{m}_{i=1}\sigma_{i}g(z_{i})\right]=2\mathcal{R}_{m}(\mathcal{G}).$

Here, using again McDiarmid’s inequality, with probability at least
$1-\delta/2$, the following holds.

$\displaystyle\mathcal{R}_{m}(\mathcal{G})\leq\hat{\mathcal{R}}_{S}(\mathcal{G})+\sqrt{\frac{\log\frac{2}{\delta}}{2m}}.$

Finally, we use the union bound which yields with probability at least
$1-\delta$:

$\displaystyle\phi(S)\leq
2\hat{\mathcal{R}}_{S}(\mathcal{G})+3\sqrt{\frac{\log\frac{2}{\delta}}{2m}}.$
(15)

######  Theorem 3.1 (Margin bound for set-to-set matching)

Let $\mathcal{F}$ be a set of matching score functions. Fix $\rho>0$. Then,
for any $\delta>0$, with probability at least $1-\delta$ over the choice of a
sample $S$ of size $m$, each of the following holds for all $f\in\mathcal{F}$:

$\displaystyle R(f)$
$\displaystyle\leq\hat{R}_{\rho}(f)+\frac{2}{\rho}\left(\mathcal{R}^{1}_{m}(\mathcal{F})+\mathcal{R}^{2}_{m}(\mathcal{F})\right)+\sqrt{\frac{\log\frac{1}{\delta}}{2m}},$
(16) $\displaystyle R(f)$
$\displaystyle\leq\hat{R}_{\rho}(f)+\frac{2}{\rho}\left(\hat{\mathcal{R}}_{S^{1}}(\mathcal{F})+\hat{\mathcal{R}}_{S^{2}}(\mathcal{F})\right)+3\sqrt{\frac{\log\frac{2}{\delta}}{2m}}.$
(17)

###### Proof

Let $\tilde{\mathcal{F}}$ be the family of functions mapping
$(\mathfrak{X}\times\mathfrak{X})\times\\{-1,+1\\}$ to $\mathbb{R}$ defined by
$\tilde{\mathcal{F}}=\\{z=(Z^{\prime},Z),a)\mapsto a[f(Z^{\prime})-f(Z)]\ |\
f\in\mathcal{F}\\}$, where $a\in\\{0,1\\}$. Consider the family of functions
$\tilde{\mathcal{F}}=\\{\phi_{\rho}\circ g\ |\ f\in\tilde{\mathcal{F}}\\}$
derived from $\tilde{\mathcal{F}}$ which are taking values in $[0,1]$. By
Lemma 1, for any $\delta>0$ with probability at least $1-\delta$, for all
$f\in\mathcal{F}$,

$\displaystyle\mathbb{E}\left[\phi_{\rho}(a[f(Z^{+})-f(Z^{-})])\right]\leq\hat{R}_{\rho}(f)+2\mathcal{R}_{m}(\phi_{\rho}\circ\tilde{\mathcal{F}})+\sqrt{\frac{\log\frac{1}{\delta}}{2m}}.$
(18)

Since $1_{u\leq 0}\leq\phi_{\rho}(u)$ for all $u\in\mathbb{R}$, the
generalization error $R(f)$ is a lower bound on left-hand side,
$R(f)=\mathbb{E}[1_{a[f(Z^{\prime})-f(Z)]\leq
0}]\leq\mathbb{E}[\phi_{\rho}(a[f(Z^{\prime})-f(Z)])]$, and we can write

$\displaystyle
R(f)\leq\hat{R}_{\rho}(f)+2\mathcal{R}_{m}(\phi_{\rho}\circ\tilde{\mathcal{F}})+\sqrt{\frac{\log\frac{1}{\delta}}{2m}}.$
(19)

Here, we can show that
$\mathcal{R}_{m}(\phi_{\rho}\circ\tilde{\mathcal{F}})\leq\frac{1}{\rho}\mathcal{R}_{m}(\tilde{\mathcal{F}})$
using the $(1/\rho)$-Lipschitzness of $\phi_{\rho}$. Then,
$\mathcal{R}_{m}(\tilde{\mathcal{F}})$ can be upper bounded as follows:

$\displaystyle\mathcal{R}_{m}(\tilde{\mathcal{F}})$
$\displaystyle=\frac{1}{m}\mathbb{E}_{S,\sigma}\left[\sup_{f\in\mathcal{F}}\sum^{m}_{i=1}\sigma_{i}a_{i}(f(Z^{\prime}_{i})-f(Z_{i}))\right]$
$\displaystyle=\frac{1}{m}\mathbb{E}_{S,\sigma}\left[\sup_{f\in\mathcal{F}}\sum^{m}_{i=1}\sigma_{i}(f(Z^{\prime}_{i})-f(Z_{i}))\right]$
$\displaystyle\leq\frac{1}{m}\mathbb{E}_{S,\sigma}\left[\sup_{f\in\mathcal{F}}\sum^{m}_{i=1}\sigma_{i}f(Z^{\prime}_{i})+\sup_{f\in\mathcal{F}}\sum^{m}_{i=1}\sigma_{i}f(Z_{i})\right]$
$\displaystyle=\mathbb{E}_{S}\left[\mathcal{R}_{S^{2}}(\mathcal{F})+\mathcal{R}_{S^{1}}(\mathcal{F})\right]=\mathcal{R}^{p_{2}}_{m}(\mathcal{F})+\mathcal{R}^{p_{1}}_{m}(\mathcal{F}).$

##  4 RKHS bound for set-to-set matching

In this section, we consider more precise bounds that depend on the size of
the negative sample produced by negative sampling. Let
$S=((\mathcal{X}_{1},\mathcal{Y}_{1}),\dots,(\mathcal{X}_{m},\mathcal{Y}_{m}))\in(\mathfrak{X}\times\mathfrak{X})^{m}$
be a finite sample sequence, and $m^{+}$ be the positive sample size. If the
positive proportion $\frac{m^{+}}{m}=\alpha$, then sample sequence $S$ also
can be denoted by $S_{\alpha}$.

Figure 1: RKHS bound w.r.t. sample size $m$ and positive ratio $\alpha$.

Let $\mathfrak{R}_{K}$ be the reproducing kernel Hilbert space (RKHS)
associated with the kernel $K$, and $\mathcal{F}_{r}$ is defined as

$\displaystyle\mathcal{F}_{r}=\\{f\in\mathfrak{R}_{K}\ |\ \|f\|_{K}\leq r\\}$
(20)

for $r>0$.

######  Theorem 4.1 (RKHS bound for set-to-set matching)

Suppose $S_{\alpha}$ to be any sample sequence of size $m$. Then, for any
$\epsilon>0$ and $f\in\mathcal{F}_{r}$,

$\displaystyle\mathbb{P}_{S_{\alpha}}\left[|\hat{R}(f;S_{\alpha})-R(f)|\geq\epsilon\right]\leq
2\exp\left\\{\frac{\alpha^{2}(1-\alpha)^{2}m\epsilon^{2}}{2L^{2}\kappa^{2}r^{2}}\right\\},$
(21)

where $\kappa\coloneqq\sup_{x}\sqrt{K(x,x)}$.

###### Proof

Denote $S=(S^{+},S^{-})=\\{Z_{1},\dots,Z_{m}\\}$ and

$\displaystyle z_{i}\coloneqq z(Z_{i})\coloneqq=\begin{cases}+1&(Z_{i}\in
S^{+}),\\\ -1&(Z_{i}\in S^{-}).\end{cases}$ (22)

First, for each $1\leq k\leq m^{+}$ such that $z_{i}=+1$, let $(Z_{k},+1)$ be
replaced by
$(Z^{\prime}_{k},+1)\in(\mathfrak{X}\times\mathfrak{X})\times\\{-1,+1\\}$, and
we denote by $S^{k}$ as this sample. Then,

$\displaystyle|\hat{R}(f;S)-\hat{R}(f;S^{k})|$
$\displaystyle\leq\frac{1}{m^{+}m^{-}}\sum^{m^{+}+m^{-}}_{j=m^{+}+1}\left|\varphi(f(Z_{k})-f(Z_{j}))-\varphi(f(Z^{\prime}_{k})-f(Z_{j}))\right|$
$\displaystyle\leq\frac{1}{m^{+}m^{-}}\sum^{m^{+}+m^{-}}_{j=m^{+}+1}L\cdot\left|f(Z_{k})-f(Z_{j})-f(Z^{\prime}_{k})+f(Z_{j})\right|$
$\displaystyle=\frac{1}{m^{+}m^{-}}\cdot m^{-}\cdot
L\cdot\left|f(Z_{k})-f(Z^{\prime}_{k})\right|\leq\frac{2L}{m^{+}}\|f\|_{\infty}.$

Next, for each $m^{+}+1\leq k\leq m$ such that $z_{i}=-1$, let $(Z_{l},-1)$ be
replaced by
$(Z^{\prime}_{k},-1)\in(\mathfrak{X}\times\mathfrak{X})\times\\{-1,+1\\}$ and
we denote by $\bar{S}^{k}$ as this sample. Similarly, we have

$\displaystyle|\hat{R}(f;S)-\hat{R}(f;\bar{S}^{k})|$
$\displaystyle\leq\frac{2L}{m^{+}}\|f\|_{\infty}.$

Finally, for each $1\leq k\leq m^{+}$ such that $z_{i}=+1$, let $(Z_{k},+1)$
be replaced by
$(Z^{\prime}_{k},-1)\in(\mathfrak{X}\times\mathfrak{X})\times\\{-1,+1\\}$, and
we denote by $\tilde{S}^{k}=\bar{S}^{k}\cup\\{(Z_{m+1},-1)\\}$ as this sample.
Then, we have

$\displaystyle|\hat{R}(f;S)-\hat{R}(f;\tilde{S}^{k})|$
$\displaystyle\leq\Gamma_{1}+\Gamma_{2},$

where $\Gamma_{1}=|\hat{R}(f;S)-\hat{R}(f;S\cup\\{Z_{m+1},-1\\})|$ and
$\Gamma_{2}=|\hat{R}(f;S\cup\\{Z_{m+1},-1\\})-\hat{R}(f;\tilde{S}^{k})|$.
Since $\Gamma_{1}\leq\frac{2L}{m^{-}+1}\|f\|_{\infty}$ and
$\Gamma_{2}\leq\frac{2L}{m^{+}}\|f\|_{\infty}$, we have

$\displaystyle|\hat{R}(f;S)-\hat{R}(f;\tilde{S}^{k})|$ $\displaystyle\leq
2L\left(\frac{1}{m^{+}}+\frac{1}{m^{-}+1}\right)\|f\|_{\infty}.$ (23)

Combining them and applying McDiarmid’s inequality, we have the proof.

###### Remark 1

Given $m,\epsilon,L$, we can find that the tight bound can be achieved when
$\alpha=\frac{1}{2}$. This means that it is desirable the number of positive
samples be equal to the number of negative samples (See Figure 1).

###### Remark 2

For any $\delta>0$, with probability at least $1-\delta$, we have

$\displaystyle\left|\hat{R}(f;S_{\alpha})-R(f)\right|\leq\frac{L\kappa
r}{\alpha(1-\alpha)}\sqrt{\frac{2\log\frac{2}{\delta}}{m}}.$ (24)

###### Remark 3

For Remark 2, Let $m=m^{+}+m^{-}$ and fix $m^{+}\in\mathbb{N}$. Then, we have
the optimal negative sample size as $(1-\alpha)=2/3$.

##  5 Conclusion and Discussion

In this paper, we performed a generalization error analysis in set-to-set
matching to reveal the behavior of the model in that task. Our analysis
reveals what the convergence rate of algorithms in set matching depend on the
size of negative sample. Future studies may include the following:

  * •

Derivation of tighter bounds. There are many types of mathematical tools for
generalization error analysis of machine learning algorithms, and it is known
that the tightness of the bounds depends on which one is used. For tighter
bounds, it is useful to use mathematical tools not addressed in this paper [1,
9, 8, 10, 2].

  * •

Induction of novel set matching algorithms. It is expected to derive a novel
algorithm based on the discussion of generalized error analysis.

  * •

The effect of data augmentation for generalization error of set-to-set
matching. Many data augmentation methods have been proposed to stabilize
neural network learning, and theoretical analysis when these are used would be
useful [5, 4, 13, 17, 12].

## References

  * [1] Bartlett, P.L., Bousquet, O., Mendelson, S.: Local rademacher complexities. The Annals of Statistics 33(4), 1497–1537 (2005)
  * [2] Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Local privacy and statistical minimax rates. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 429–438. IEEE (2013)
  * [3] Iwata, T., Lloyd, J.R., Ghahramani, Z.: Unsupervised many-to-many object matching for relational data. IEEE transactions on pattern analysis and machine intelligence 38(3), 607–617 (2015)
  * [4] Kimura, M.: Understanding test-time augmentation. In: International Conference on Neural Information Processing. pp. 558–569. Springer (2021)
  * [5] Kimura, M.: Why mixup improves the model performance. In: International Conference on Artificial Neural Networks. pp. 275–286. Springer (2021)
  * [6] Kimura, M., Nakamura, T., Saito, Y.: Shift15m: Multiobjective large-scale fashion dataset with distributional shifts. arXiv preprint arXiv:2108.12992 (2021)
  * [7] Lisanti, G., Martinel, N., Del Bimbo, A., Luca Foresti, G.: Group re-identification via unsupervised transfer of sparse features encoding. In: Proceedings of the IEEE International Conference on Computer Vision. pp. 2449–2458 (2017)
  * [8] McAllester, D.A.: Pac-bayesian model averaging. In: Proceedings of the twelfth annual conference on Computational learning theory. pp. 164–170 (1999)
  * [9] McAllester, D.A.: Some pac-bayesian theorems. Machine Learning 37(3), 355–363 (1999)
  * [10] Millar, P.W.: The minimax principle in asymptotic statistical theory. In: Ecole d’Eté de Probabilités de Saint-Flour XI—1981, pp. 75–265. Springer (1983)
  * [11] Saito, Y., Nakamura, T., Hachiya, H., Fukumizu, K.: Exchangeable deep neural networks for set-to-set matching and learning. In: European Conference on Computer Vision. pp. 626–646. Springer (2020)
  * [12] Shorten, C., Khoshgoftaar, T.M.: A survey on image data augmentation for deep learning. Journal of big data 6(1), 1–48 (2019)
  * [13] Van Dyk, D.A., Meng, X.L.: The art of data augmentation. Journal of Computational and Graphical Statistics 10(1), 1–50 (2001)
  * [14] Vapnik, V.: The nature of statistical learning theory. Springer science & business media (1999)
  * [15] Vapnik, V.N.: An overview of statistical learning theory. IEEE transactions on neural networks 10(5), 988–999 (1999)
  * [16] Xiao, H., Lin, W., Sheng, B., Lu, K., Yan, J., Wang, J., Ding, E., Zhang, Y., Xiong, H.: Group re-identification: Leveraging and integrating multi-grain information. In: Proceedings of the 26th ACM international conference on Multimedia. pp. 192–200 (2018)
  * [17] Zhong, Z., Zheng, L., Kang, G., Li, S., Yang, Y.: Random erasing data augmentation. In: Proceedings of the AAAI conference on artificial intelligence. vol. 34, pp. 13001–13008 (2020)
  * [18] Zhu, P., Zhang, L., Zuo, W., Zhang, D.: From point to set: Extend the learning of distance metrics. In: Proceedings of the IEEE international conference on computer vision. pp. 2664–2671 (2013)


# Pareto Monte Carlo Tree Search
for Multi-Objective Informative Planning

Weizhe Chen, Lantao Liu W. Chen and L. Liu are with the School of Informatics,
Computing, and Engineering at Indiana University, Bloomington, IN 47408, USA.
E-mail: {chenweiz<EMAIL_ADDRESS>
###### Abstract

In many environmental monitoring scenarios, the sampling robot needs to
simultaneously explore the environment and exploit features of interest with
limited time. We present an anytime multi-objective informative planning
method called Pareto Monte Carlo tree search which allows the robot to handle
potentially competing objectives such as exploration versus exploitation. The
method produces optimized decision solutions for the robot based on its
knowledge (estimation) of the environment state, leading to better adaptation
to environmental dynamics. We provide algorithmic analysis on the critical
tree node selection step and show that the number of times choosing sub-
optimal nodes is logarithmically bounded and the search result converges to
the optimal choices at a polynomial rate.

##  I INTRODUCTION

There is an increasing need that mobile robots are tasked to gather
information from our environment. Navigating robots to collect samples with
the largest amount of information is called informative planning [4, 21, 25].
The basic idea is to maximize information gain using information-theoretic
methods, where the information gain (or informativeness) is calculated from
the estimation uncertainty based on some prediction models such as the set of
Gaussian systems. Informative planning is challenging due to the large and
complex searching space. Such problems have been shown to be NP-hard [26] or
PSPACE-hard [23] depending on the form of objective functions and the
corresponding searching space.

Existing informative planning work is heavily built upon information-theoretic
framework. The produced solutions tend to guide the robot to explore the
uncertain or unknown areas and reduce the estimation uncertainty (e.g., the
entropy or mutual information based efforts). Aside from the estimation
uncertainty, there are many other estimation properties that we are interested
in. For example, when monitoring some biological activity in a lake,
scientists are interested in areas with high concentration – known as hotspots
– of biological activity [20]. Similarly, plume tracking is useful for
detection and description of oil spills, thermal vents, and harmful algal
blooms [29]. In these tasks, the robot needs to explore the environment to
discover hotspots first, and then visit different areas with differing effort
(frequency) to obtain the most valuable samples and catch up with the
(possibly) spatiotemporal environmental dynamics.

(a) Bathymetry

(b) Example trajectory

Figure 1: Illustrative multi-objective informative planning trajectory for
modeling the Bathymetry of New Zealand’s Exclusive Economic Zone. The goal is
to explore the environment while visiting areas with high value and
variability more frequently. (Source: NIWA)

Since exploration and exploitation cannot be achieved simultaneously most of
the time, different planning objectives may lead to distinct motion
trajectories. The problem falls within the spectrum of multi-objective
optimization in which the optima are not unique. In fact, continua of optimal
solutions are possible. The goal is to find the Pareto optimal set, or so
called Pareto front. The solutions in the Pareto optimal set cannot be
improved for any objective without hurting other objectives. A straightforward
solution to the multi-objective problem is to convert it into a single-
objective problem by linear scalarization (weighted sum of objectives is one
of the linear scalarization method). However, linear scalarization might be
impossible, infeasible, or undesirable for the following reasons. First of
all, objectives might be conflicting. Taking algal bloom monitoring as an
example, high-concentration areas and the areas with high temporal variability
(i.e., spreading dynamics) are both important. We expect the robot to visit
these areas more frequently, but these two types of areas are not necessarily
in the same direction. Furthermore, the weights among different objectives are
hard to determine in the linear scalarization approaches. Last but not least,
linear scalarization based approaches fail to discover the solutions in the
non-convex regions of the Pareto front.

This paper presents the following contributions:

  * •

Different from existing informative planning approaches where information-
seeking is the main objective, we propose a new generic planning method that
optimizes over multiple (possibly) competing objectives and constraints.

  * •

We incorporate the Pareto optimization into the Monte Carlo tree search
process and further design an anytime and non-myopic planner for in-situ
decision-making.

  * •

We provide in-depth algorithmic analysis which reveals bounding and converging
behaviors of the search process.

  * •

We perform thorough simulation evaluations with both synthetic and real-world
data. Our results show that the robot exhibits desired composite behaviors
which are optimized from corresponding hybrid objectives.

##  II RELATED WORK

Informative planning maximizes the collected information (informativeness) by
exploring (partially) unknown environment during its sampling process [4, 17].
Comparing with the lawnmower based sweeping style sampling mechanism which
focuses on spatial resolution, the informative planning method tends to
achieve the spatial coverage quickly with the least estimation uncertainty
[25]. Due to these reasons, the information planning has been widely used for
the spatiotemporal environmental monitoring. To explore and learn the
environment model, a commonly-used approach in spatial statistics is the
Gaussian Process Regression [22]. Built on the learned environmental model,
path and motion control can be carried out which is a critical ability for
autonomous robots operating in unstructured environments [9, 16].

Representative informative planning approaches include, e.g., algorithms based
on a recursive-greedy style [21, 25] where the informativeness is generalized
as submodular function and a sequential-allocation mechanism is designed in
order to obtain subsequent waypoints. This recursive-greedy framework has been
extended later by incorporating obstacle avoidance and diminishing returns
[4]. In addition, a differential entropy based framework [17] was proposed
where a batch of waypoints can be obtained through dynamic programming. Recent
work also reveals that online informative planning is possible [18]. The
sampling data is thinned based on their contributions learned by a sparse
variant of Gaussian Process. There are also methods optimizing over complex
routing constraints (e.g., see [27, 31]).

Pareto optimization has been used in designing motion planners to optimize
over the length of a path and the probability of collisions [6]. Recently, a
sampling based method has also been proposed to generate Pareto-optimal
trajectories for multi-objective motion planning [15]. In addition, multi-
robot coordination also benefits from multi-objective optimization. The goals
of different robots are simultaneously optimized [8, 14]. To balance the
operation cost and the travel discomfort experienced by users, the multi-
objective fleet routing algorithms compute the Pareto-optimal fleet operation
plans [5].

Related work also includes the multi-objective reinforcement learning [24].
Particularly, the prior work multi-objective Monte Carlo tree search (MO-MCTS)
is closely relevant to our method [30]. Unfortunately, MO-MCTS is
computationally prohibitive and cannot be used for online planning framework.
Vast computational resources are needed in order to maintain a global Pareto
optimal set with all the best solutions obtained so far. In contrast, we
develop a framework that maintains a local approximate Pareto optimal set in
each node which can be processed in a much faster way. Our approach is also
flexible and adaptive with regards to capturing environmental variabilities of
different stages.

##  III PRELIMINARIES

Figure 2: System flow chart of Pareto MCTS for the online planning framework.

###  III-A Pareto Optimality

Let $\bm{X}_{k}$ be a $D$-dimensional reward vector associated with a choice
$k$ and $X_{k,d}$ be the $d$-th element. The $i$-th choice is better than, or
dominating, another choice $j$, denoted by $i\succ j$ or $j\prec i$, if and
only if the following conditions are satisfied:

  1. 1.

Any element of $\bm{X}_{i}$ is not smaller than the corresponding element in
$\bm{X}_{j}$:
$\forall d=1,2,\dots,D,X_{i,d}\geqslant X_{j,d}$;

  2. 2.

At lease one element of $\bm{X}_{i}$ is larger than the corresponding element
in $\bm{X}_{j}$:
$\exists d\in\\{1,2,\dots,D\\}\text{ such that }X_{i,d}>X_{j,d}$.

If only the first condition is satisfied, we say that choice $i$ is weakly-
dominating choice $j$, denoted by $i\succeq j$ or $j\preceq i$.

In some cases, neither $i\succeq j$ nor $j\succeq i$ hold. We say that choice
$i$ is incomparable with choice $j$ ($i||j$) if and only if there exists one
dimension $d_{1}$ such that $X_{i,d_{1}}>X_{j,d_{1}}$, and another dimension
$d_{2}$ such that $X_{i,d_{2}}<X_{j,d_{2}}$. Also, we say that choice $i$ is
non-dominated by choice $j$ ($i\nprec j$ or $j\nsucc i$) if and only if there
exists one dimension $d$ such that $X_{i}^{d}>X_{j}^{d}$.

###  III-B Multi-Objective Informative Planning

In the general case, multi-objective informative planning requires solving the
following maximization problem:

$\displaystyle\bm{a}^{*}=\operatorname*{arg\,max}_{\bm{a}\in\mathcal{A}}\left\\{I(\bm{a}),F_{1}(\bm{a}),\dots,F_{D-1}(\bm{a})\right\\},$
(1) $\displaystyle\text{ s.t. }C_{\bm{a}}\leq B,$

where $\bm{a}$ is a sequence of actions, $\mathcal{A}$ is the space of
possible action sequences, $B$ is a budget (e.g. time, energy, memory, or
number of iterations), $C_{\bm{a}}$ is the cost of budget, and $I(\bm{a})$ is
a function representing the information gathered by executing the action.
$F_{d}(\bm{a}),d\in\\{1,\dots,D-1\\}$ are other objective functions defining
which types of behaviors are desired.

##  IV APPROACH

Figure 3: Illustration of main steps of Pareto Monte Carlo tree search (Pareto
MCTS).

###  IV-A Methodology Overview

An overview of our method is shown in Fig. 2. The planner computes an
informative path using the Pareto MCTS algorithm based on the current
estimation of the environment. As the robot travels along the path, it
continuously receives observations of the target variables . Then, these newly
acquired samples are used to refine its estimation of the environment, which
in turn influences the planning in the next round.

The specific form of rewards depend on the applications. For example, in the
informative planning problem, the rewards can be defined as the reduced amount
of estimation entropy, accumulated amount of mutual information, etc. In
hotspot exploration and exploitation task, the reward of a given path can be
defined as the sum of rewards of all sampling points along the path. Pareto
MCTS searches for the optimal actions for current state until a given time
budget is exhausted. The inputs of Pareto MCTS are a set of available
primitive paths at every possible state and the robot’s current knowledge
(estimation) of the world. It is worth noting that, the multi-objective
framework also allows us to incorporate prior knowledge, as illustrated on the
left side of Fig. 2.

###  IV-B Pareto Monte Carlo Tree Search

The proposed Pareto Monte Carlo tree search (Pareto MCTS) is a planning method
for finding Pareto optimal decisions within a given horizon. The tree is built
incrementally in order to expand the most promising subtrees first. This is
done by taking advantage of the information gathered in previous steps. Each
node in the search tree represents a state of the domain (in our context it is
a location to be sampled), and the edges represent actions leading to
subsequent states.

The framework of Pareto MCTS is outlined in Fig. 3. In each iteration, it can
be broken down into four main steps:

  1. 1.

Selection: starting at the root node, a child node selection policy (described
later on) is applied recursively to descend through the tree until an
expandable node with unvisited (unexpanded) children is encountered.

  2. 2.

Expansion: an action is chosen from the aforementioned expandable node. A
child node is constructed according to this action and connected to the
expandable node.

  3. 3.

Simulation: a simulation is run from the new node based on the predefined
default policy. In our case, the default policy chooses a random action from
all available actions. The reward vector of this simulation is then returned.

  4. 4.

Backpropagation: the obtained reward is backed up or backpropagated to each
visited node in the selection and expansion steps to update the attributes in
those nodes. In our algorithm, each node stores the number of times it has
been visited and the cumulative reward obtained by simulations starting from
this node.

These steps are repeated until the maximum number of iterations is reached or
a given time limit is exceeded.

The most challenging part of designing Pareto MCTS is the selection step. We
want to select the most promising node to expand first in order to improve the
searching efficiency. However, which node is the most promising is unknown so
that the algorithm needs to estimate it. Therefore, in the selection step, one
must balance exploitation of the recently discovered most promising child node
and exploration of alternatives which may turn out to be a superior choice at
later time.

In the case of scalar reward, the most promising node is simply the one with
highest expected reward. However, the reward is herein a vector corresponding
to multiple objectives. In the context of multi-objective optimization, the
optima are no longer unique. Instead, there is a set of optimal choices, each
of which is considered equally best. Below we define the Pareto optimal node
set. The nodes in the Pareto optimal set are incomparable to each other and
will not be dominated by any other nodes.

######  Definition 1 (Pareto Optimal Node Set).

Given a set of nodes $\mathcal{V}$, a subset
$\mathcal{P}^{*}\subset\mathcal{V}$ is the Pareto optimal node set, in terms
of expected reward, if and only if

$\begin{cases}\forall v_{i}^{*}\in\mathcal{P}^{*}\text{ and }\forall
v_{j}\in\mathcal{V},v_{i}^{*}\nprec v_{j},\\\ \forall
v_{i}^{*},v_{j}^{*}\in\mathcal{P}^{*},v_{i}^{*}||v_{j}^{*}.\end{cases}$

We treat the node selection problem as a multi-objective multi-armed bandit
problem. As shown in Alg. 1, the Pareto Upper Confidence Bound (Pareto UCB)
for each child node is first computed according to Eq. (2). Then an
approximate Pareto optimal set is built using the resulting Pareto UCB vectors
(see the green nodes in Fig. 3). Finally, the best child node is chosen from
the Pareto optimal set uniformly at random. Note that the reason for choosing
the best child randomly is that the Pareto optimal solutions are considered
equally optimal if no preference information is given. However, if domain
knowledge is available or preference is specified, one can choose the most
preferable child from the Pareto optimal set. For example, in the
environmental monitoring task, one might expect the robot to explore the
environment in the early stage to identify some important areas and spend more
effort exploiting these areas in the later stage. In such case, we can choose
the Pareto optimal node with highest information gain in the beginning because
the information gain based planning tends to cover the space quickly. Other
types of rewards can be chosen later to concentrate on examining the details
locally.

Note that this is different from weighting different objectives and solve a
single-objective problem, because choosing a preferred solution from a given
set of optimal solutions is often easier than determining the quantitative
relationship among different objectives. For instance, it is difficult to
quantify how much the information gain is more important than exploiting high-
value areas in the hotspot monitoring task. However, given several choices, we
may pick the most informative choice in the very beginning, and another one
with highest target value related reward in a later stage.

1 Function  _$\text{Search}(s_{0})$_

2 create root node $v_{0}$ with state $s_{0}$

3 while  _within computational budget_ do

4 $v_{\text{expandable}}\leftarrow\text{ Selection}(v_{0})$

5 $v_{\text{new}}\leftarrow\text{ Expansion}(v_{\text{expandable}})$

6 $\text{RewardVector}\leftarrow\text{ Simulation }(v_{\text{new}}.s)$

7 $\text{Backpropagation}(v_{\text{new}},\text{RewardVector})$

8

9 return $\text{MostVisitedChild}(v_{0})$

10

11

12Function  _$\text{Selection}(v)$_

13 while  _$v$ is fully expanded_ do

14 $v\leftarrow\text{ParetoBestChild}(v)$

15

16 return $v$

17

18

19Function  _$\text{ParetoBestChild}(v)$_

20 compute Pareto UCB for each child $k$:
$\bm{U}(k)=\frac{v_{k}.\bm{X}}{v_{k}.n}+\sqrt{\frac{4\ln{n}+\ln{D}}{2v_{k}.n}}$
(2)

21 build approximate Pareto optimal node set $v.\mathcal{P}$ based on
$\bm{U}(k)$

22 choose a child $v_{\text{best}}$ from $v.\mathcal{P}$ uniformly at random

23 return $v_{\text{best}}$

24

Note: We use $v.\text{attribute}$ to represent a node attribute of $v$. In Eq.
(2), $v_{k}.\bm{X}$ is the cumulative reward of the $k$-th child of node $v$,
$v_{k}.n$ is the number of times that the $k$-th child has been visited, and
$D$ is the number of objectives. Some standard components, such as Simulation,
Expansion, and Backpropagation, are not shown due to the lack of space.

Algorithm 1 Pareto MCTS

###  IV-C Algorithm Analysis

As mentioned earlier, the node selection is the most critical step and almost
determines the performance of the entire framework. Thus, here we spend effort
analyzing this step to better understand its important properties. Although
some (potentially) sub-optimal nodes may be selected inevitably, we show that
the number of times choosing a sub-optimal node can be bounded logarithmically
in Pareto MCTS. In addition, we want to know whether this anytime algorithm
will converge to the optimal solution if enough time is given and whether a
good solution can be returned if it is stopped midway. To answer this
question, we show that the searching result of Pareto MCTS converges to the
Pareto optimal choices at a polynomial rate.

######  Problem 1 (Node Selection).

Consider a node $v$ with $K$ child nodes in a Pareto Monte Carlo search tree.
At decision step $n$, a D-dimensional random reward $\bm{X}_{k,n_{k}}$ will be
returned after selecting child $v_{k}$. Successive selections of child $v_{k}$
yield rewards $\bm{X}_{k,1},\bm{X}_{k,2},\dots$, which are drawn from an
unknown distribution with unknown expected reward $\bm{\mu}_{k}$. A policy is
an algorithm that chooses a child node based on the sequence of past
selections and obtained rewards. The goal of a policy is to minimize the
number of times choosing a sub-optimal node.

In Pareto MCTS, node selection only happens after all child nodes have been
expanded. In other words, there is an initialization step in which each node
has been selected once. For easy reference, we summarize the node selection
policy below.

######  Policy 1.

Given a node selection problem as Problem 1, choose each child node once in
the first $K$ steps. After that, build an approximate Pareto optimal node set
based on the following upper confidence bound vector:

$\bm{U}(k)=\bar{\bm{X}}_{k,n_{k}}+\sqrt{\frac{4\ln{n}+\ln{D}}{2n_{k}}},$ (3)

where $K$ is the number of child nodes, $n_{k}$ is the number of times child
$k$ has been selected so far, $\bar{\bm{X}}_{k,n_{k}}$ is the average reward
obtained from child $k$, $D$ is the number of dimensions of the reward, and
$n=\sum^{K}_{k=1}n_{k}$.

In the following proof, we shall use the concept of most dominant optimal node
originated from the $\epsilon$-dominance concept [12] of multi-objective
optimization. Intuitively, the most dominant optimal node of a given node is
the one in the (estimated) Pareto optimal set which is the “farthest away”
from the given node.

######  Definition 2 (Most Dominant Optimal Node).

Given a node $v_{k}$ and a node set $\mathcal{V}$ such that $\forall
v_{k^{\prime}}\in\mathcal{V},v_{k^{\prime}}\succ v_{k}$. For all
$v_{k^{\prime}}\in\mathcal{V}$, there exists exactly one minimum positive
constant $\epsilon_{k^{\prime}}$ such that

$\epsilon_{k^{\prime}}=\min\\{\epsilon|\exists d\in\\{1,2,\dots,D\\}\text{
s.t. }\mu^{\prime}_{k,d}+\epsilon>\mu_{k,d}\\}.$

Let the index of the maximum $\epsilon_{k^{\prime}}$ be $k^{*}$,

$k^{*}=\operatorname*{arg\,max}_{k^{\prime}}\epsilon_{k^{\prime}},$

then the most dominant optimal node is $v_{k^{*}}$.

Throughout the paper, symbols related to the most dominant optimal node will
be indexed by a star(∗). As in [11], we allow the expected average rewards to
drift as a function of time and our main assumption is that it will converge
pointwise. Here we introduce two assumptions so that the later proof can
exploit.

######  Assumption 1 (Convergence of Expected Average Rewards).

The expectations of the average rewards $\mathbb{E}[\bar{\bm{X}}_{k,n_{k}}]$
converge pointwise to the limit $\bm{\mu}_{k}$ for all child nodes:

$\bm{\mu}_{k}=\lim_{n_{k}\rightarrow\infty}\mathbb{E}[\bar{\bm{X}}_{k,n_{k}}].$
(4)

For a sub-optimal node $v_{k}$ and its most dominant optimal node $v_{k^{*}}$
from $\mathcal{P^{*}}$, we define $\bm{\Delta}_{k}=\bm{\mu}^{*}-\bm{\mu}_{k}$
to denote their difference.

######  Assumption 2.

Fix $1\leq k\leq K$ and $1\leq d\leq D$. Let $\\{\mathcal{F}_{k,t,d}\\}_{t}$
be a filtration such that $\\{X_{k,t,d}\\}_{t}$ is
$\\{\mathcal{F}_{k,t,d}\\}$-adapted and $X_{k,t,d}$ is conditionally
independent of $\mathcal{F}_{k,t+1,d},\mathcal{F}_{k,t+2,d},\dots$ given
$\mathcal{F}_{k,t-1,d}$.

For the sake of simplifying the notation, we define
$\bm{\mu}_{k,n_{k}}=\mathbb{E}[\bar{\bm{X}}_{k,n_{k}}]$ and
$\bm{\delta}_{k,n_{k}}=\bm{\mu}_{k,n_{k}}-\bm{\mu}_{k}$ as the residual for
the drift. Clearly,
$\lim_{n_{k}\rightarrow\infty}\bm{\delta}_{k,n_{k}}=\bm{0}$. By definition,
$\forall\xi>0$, $\exists N_{0}(\xi)$ such that $\forall n_{k}\geq N_{0}(\xi)$,
$\forall d\in\\{1,2,\dots,D\\}$, $|\delta_{k,n_{k},d}|\leq\xi\Delta_{k,d}/2$.
We present the first theorem below.

######  Theorem 1.

Consider Policy 1 applied to the node selection Problem 1. Suppose Assumption
1 is satisfied. Let $T_{k}(n)$ denote the number of times child node $v_{k}$
has been selected in the first $n$ steps. If child node $v_{k}$ is a sub-
optimal node (i.e. $v_{k}\not\in\mathcal{P}^{*}$), then $\mathbb{E}[T_{k}(n)]$
is logarithmically bounded:

$\mathbb{E}[T_{k}(n)]\leq\frac{8\ln{n}+2\ln{D}}{(1-\xi)^{2}(\min\limits_{k,d}\Delta_{k,d})^{2}}+N_{0}(\xi)+1+\frac{\pi^{2}}{3}.$
(5)

###### Proof.

Proof is provided in Appendix A. ∎

The following lemma gives a lower bound on the number of times each child node
being selected.

######  Lemma 1.

There exists positive constant $\rho$ such that $\forall
k,n,T_{k}(n)\geq\lceil\rho\log(n)\rceil$.

The upcoming lemma states that the average reward will concentrate around its
expectation after enough node selection steps.

######  Lemma 2 (Tail Inequality).

Fix arbitrary $\eta>0$ and let $\sigma=9\sqrt{\frac{2\ln(2/\eta)}{n}}$. There
exists $N_{1}(\eta)$ such that $\forall n\geq N_{1}(\eta),\forall
d\in\\{1,\dots,D\\}$, the following bounds hold true:

$\displaystyle\mathbb{P}(\bar{X}_{n,d}\geq\mathbb{E}[\bar{X}_{n,d}]+\sigma)\leq\eta,$
(6)
$\displaystyle\mathbb{P}(\bar{X}_{n,d}\leq\mathbb{E}[\bar{X}_{n,d}]-\sigma)\leq\eta.$
(7)

Correctness of Lemma 1 and Lemma 2 is provided in [11].

######  Theorem 2 (Convergence of Failure Probability).

Consider the node selection policy described in Algorithm 1 applied to the
root node. Let $I_{t}$ be the selected child node and $\mathcal{P}^{*}$ be the
Pareto optimal node set. Then,

$\mathbb{P}(I_{t}\not\in\mathcal{P}^{*})\leq
Ct^{-\frac{\rho}{2}\left(\frac{\min\limits_{k,d}\Delta_{k,d}}{36}\right)^{2}},$
(8)

with some constant $C$. In particular, it holds that
$\lim_{t\rightarrow\infty}\mathbb{P}(I_{t}\not\in\mathcal{P}^{*})=0$

###### Proof.

Proof is provided in Appendix B. ∎

Theorem 2 shows that, at the root node, the probability of choosing a child
node (and corresponding action) which is not in the Pareto optimal set
converges to zero at a polynomial rate as the number of node selection grows.

(a)

(b)

Figure 4: (a) Environment with hotspots used as ground truth. The heat map
represents level of interest. (b) Primitive paths for a robot.

##  V EXPERIMENTS

To thoroughly evaluate our framework, we have compared different methods in
extensive simulations using both synthetic data and real-world data, where the
basic scenario is the hotspot monitoring task via informative planning for a
robot. The ideal behavior for the robot is to first explore the environment to
discover the hotspots and then exploit these important areas to collect more
valuable samples. This is a bi-objective task although our algorithm is
suitable for multi-objective tasks in general. We choose this scenario for
comparison (and illustration) purpose, since one of the comparing methods can
only handle bi-objective case. In addition, hotspot monitoring task can be
easily visualized for interpretation.

We have compared our algorithm with two other baseline methods. The first
method is the Monte Carlo tree search with information-theoretic objective,
which has been successfully applied to planetary exploration mission [1],
environment exploration [2, 7], and monitoring spatiotemporal process [19]. We
called the method information MCTS. The second method is a upper confidence
bound based online planner [28] which balances exploration and exploitation in
a near-optimal manner with appealing no-regret properties. However, when
choosing an optimal trajectory, only the primitive paths of current state are
considered in their model. For comparison, we modify and extend this model to
MCTS by using the upper confidence bound (see section IV of [28]) as the
reward function of MCTS, which is called UCB MCTS.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 5: The arrow represents the robot. (a)(c)(e) The line shows the
resulting path of each algorithm with the underlying environment as the
background. (b)(d)(f) Robot’s estimation of the target value and collected
samples. Red represents high value and blue indicates low value. (a)(b)
Information MCTS. (c)(d) UCB MCTS. (e)(f) Pareto MCTS.

(a)

(b)

(c)

(d)

Figure 6: The resulting error of the three algorithm in the synthetic problem.
(a) Root mean square error. (b) Mean absolute error. (c) Hotspot root mean
square error. (d) Hotspot mean absolute error.

Rewards:  As for the reward function, we choose variance reduction as the
information-theoretic objective as in [3, 10]. The other reward is devised as
adding up the predicted values of samples along the path, which encourages the
robot to visit high-value areas more frequently.

Metrics:  In the informative planning context, our goal is to minimize the
root mean square error (RMSE) between the estimated environmental state (using
GP prediction) and the ground truth. However, in our hotspot monitoring task,
we are more concerned with the modeling errors in high-value areas than the
entire environment. Therefore, a hotspot RMSE is employed for better
evaluating the “exploitation” performance. We classify the areas with target
values higher than the median as hotspots and calculate the RMSE within these
hotspots. In addition, larger errors in unimportant areas are acceptable in
this task and RMSE tends to penalize larger errors in a uniform way.
Therefore, we also evaluate the methods using mean absolute error (MAE).
Similarly, we introduced hotspot MAE to highlight algorithms’ performance in
the important areas. Last but not least, the percentage of samples in hotspots
measures the quality of the collected data. Ideally, the robot should locate
the important areas as soon as possible and gather more valuable samples in
these areas. Also, if there are multiple hotpots, the robot should visit as
many hotspots as possible instead of getting stuck in one specific area.

###  V-A Synthetic Problems

The robot is tasked to monitor several hotspots in an unknown $10\text{ km
}\times 10\text{ km }$ environment, illustrated in Fig. 4a. The hotspots to be
monitored are specified by three Gaussian sources with random placement and
parameters. At each position, the robot has $15$ Dubins paths [13] as its
primitive paths. Fig. 4b illustrates an example of available primitive paths.

(a)

(b)

Figure 7: (a) CDOM raw data of Gulf of Mexico. (b) A cropped region near
Louisiana Wetlands.

Fig. 5 shows the the ground truth and prediction with the robot’s path and
collected samples. As expected, the information MCTS tends to cover the whole
space and collect the samples uniformly, because less information will be
gained from a point once it has been observed. On the contrary, UCB MCTS spent
a small amount of effort exploring the environment during the initial phase in
order to reduce the uncertainty of the hotspot estimation. After that, it
tends to greedily wander around the high-value areas. This phenomenon is
consistent with the behavior of the UCB algorithm in the multi-armed bandit
problem in which the best machine will be played much more times than sub-
optimal machines. We noticed that the bias term in UCB-replanning [28] also
increases with the mission time, which means that, given enough time, the
robot will still try to explore other areas. However, in our experiments, the
task duration could not be set too long due to the scalability of the GP.
Pareto MCTS simultaneously optimize all the objectives. As a result, more
samples can be found in the upper hotspot (see Fig. 5f and Fig. 5d).

Fig. 6 presents the global error and hotspot error. The difference between the
global error and the hotspot error is negligible because the most important
variability is concentrated in the hotspot areas. We notice that, in the first
$200$ samples, the performance of Pareto MCTS is inferior to other two
methods. In fact, this is because Pareto MCTS has not yet discovered any
particular hotspot in the initial exploration phase. Once it finds the a
hotspot and starts exploiting that hotspot, the error curve drops drastically,
surpassing the other two methods at about $300$ samples. This property is
consistent with our motivation. It is also obvious that our method in general
has the steepest error reduction rate, which is particularly important in
monitoring highly dynamic environment.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 8: The resulting path, collected samples, and prediction of each
algorithm in the chromophoric dissolved organic material monitoring problem.
Blue and red correspond to low and high value, respectively. The arrow
represents the robot and the crosses are the sampled data. (a) Path and the
ground truth of information MCTS. (b) Collected samples and the estimated
hotspot map from information MCTS. (c) Path and the ground truth of UCB MCTS.
(d) Collected samples and estimation of UCB MCTS. (e) Path and the ground
truth of Pareto MCTS. (f) Collected samples and estimation of Pareto MCTS.

###  V-B Chromophoric Dissolved Organic Material Monitoring

We now demonstrate our proposed approach using the chromophoric dissolved
organic material (CDOM) data at the Gulf of Mexico, provided by National
Oceanic and Atmospheric Administration (NOAA). The concentration of CDOM has a
significant effect on biological activity in aquatic systems. Very high
concentrations of CDOM can affect photosynthesis and inhibit the growth of
phytoplanktons. Fig. 7a is the raw data of CDOM. We have cropped a smaller
region with a higher variability of the target value (Fig. 7b). Due to the
scalability issue of the GP, the raw data ($300\times 300$ grids) is down-
sampled to ($30\times 30$).

Fig. 8 reveals similar sample distribution patterns as in the synthetic data.
Specifically, the information MCTS features good spatial coverage. UCB MCTS
prefers to stay at the hotspot with highest target value after a rough
exploration of the environment. Pareto MCTS tends to compromise between
hotspot searching and hotspot close examination. As a result, it exhibits
interesting winding paths in some important areas (see Fig. 8f). This allows
the robot to collect more samples in those areas without losing too much
information gain.

In this experiment, we also show how to incorporate prior knowledge in the
Pareto MCTS. In robotic environmental monitoring, the robot needs to explore
the environment extensively in the early stage. To this end, we always choose
the most informative action from the Pareto optimal set at the beginning
(first $400$ samples), which makes Pareto MCTS degenerate to information MCTS.
As shown in Fig. 9, the root mean square error of information MCTS (blue line)
and that of Pareto MCTS (green line) visually overlap. This implies that there
is almost no loss in global modeling error. At the same time, the percentage
of samples collected from hotspots has increased. Fig. 10 shows the percentage
of hotspot samples. These results validate the benefits of multi-objective
informative planning and Pareto MCTS.

(a)

(b)

Figure 9: The root mean square error and mean absolute error of the three
algorithms in the chromophoric dissolved organic material monitoring problem.
(a) Root mean square error. (b) Mean absolute error. The blue line is visually
overlapped with the green line. They are separated after zooming in, but the
difference is negligible.  Figure 10: Percentage of hotspot samples of the
three algorithms in the chromophoric dissolved organic material monitoring
problem.

##  VI CONCLUSION

This paper presents a Pareto multi-objective optimization based informative
planning approach. We show that the searching result of Pareto MCTS converges
to the Pareto optimal actions at a polynomial rate, and the number of times
choosing a sub-optimal node in the course of tree search has a logarithmic
bound. Our method allows the robot to adapt to the target environment and
adjust its concentrations on environmental exploration versus exploitation
based on its knowledge (estimation) of the environment. We validate our
approach in a hotspot monitoring task using real-world data and the results
reveal that our algorithm enables the robot to explore the environment and, at
the same time, visit hotspots of high interests more frequently.

## APPENDIX

###  VI-A Proof to Theorem 1

Let variable $I_{t}$ be the index of the selected child node at decision step
$t$ and $\bm{1}\\{\cdot\\}$ be a Boolean predicate function. Let the bias term
in Eq. (3) be $c_{t,s}=\sqrt{\frac{4\ln{t}+\ln{D}}{2s}}$. Then $\forall
l>0\text{ and }l\in\mathbb{Z}^{+}$, for any sub-optimal node $v_{k}$, we have
the upper bound $T_{k}(n)$.

$\displaystyle T_{k}(n)=$ $\displaystyle
l+\sum^{n}_{t=K+1}\bm{1}\\{I_{t}=k\\}$ $\displaystyle\leq$ $\displaystyle
l+\sum^{n}_{t=K+1}\bm{1}\\{I_{t}=k,T_{k}(t-1)\geq l\\}$ $\displaystyle\leq$
$\displaystyle
l+\sum^{n}_{t=K+1}\bm{1}\\{\bar{\bm{X}}^{*}_{T_{j}(t-1)}+c_{t-1,T^{*}(t-1)}$
$\displaystyle\nsucc\bar{\bm{X}}_{k,T_{k}(t-1)}+c_{t-1,T_{k}(t-1)},T_{k}(t-1)\geq
l\\}$ $\displaystyle\leq$ $\displaystyle
l+\sum^{\infty}_{t=1}\sum^{t-1}_{s=1}\sum^{t-1}_{s_{k}=l}\bm{1}\\{\bar{\bm{X}}^{*}_{s}+c_{t,s}\nsucc\bar{\bm{X}}_{k,s_{k}}+c_{t,s_{k}}\\}$

$\bar{\bm{X}}^{*}_{s}+c_{t,s}\nsucc\bar{\bm{X}}_{k,s_{k}}+c_{t,s_{k}}$ implies
that at least one of the following must hold:

$\displaystyle\bar{\bm{X}}^{*}_{s}$
$\displaystyle\nsucc\bm{\mu}^{*}_{s}-c_{t,s}$ (9)
$\displaystyle\bar{\bm{X}}_{k,s_{k}}$
$\displaystyle\nprec\bm{\mu}_{k,s_{k}}-c_{t,s}$ (10)
$\displaystyle\bm{\mu}^{*}_{s}$
$\displaystyle\nsucc\bm{\mu}_{k,s}+2c_{t,s_{k}}$ (11)

Otherwise, If Eq. (9), (10) are false, then Eq. (11) is true.

We bound the probability of events Eq. (9) (10) using Chernoff-Hoeffding Bound
and Union Bound.

$\displaystyle\mathbb{P}(\bar{\bm{X}}^{*}_{s}\nsucc\bm{\mu}^{*}_{s}-c_{t,s})$
$\displaystyle=$
$\displaystyle\mathbb{P}\left((\bar{X}^{*}_{s,1}<\mu^{*}_{s,1}-c_{t,s})\lor\cdots\lor(\bar{X}^{*}_{s,D}<\mu^{*}_{s,D}-c_{t,s})\right)$
$\displaystyle\leq$
$\displaystyle\sum^{D}_{d=1}\mathbb{P}\left(\bar{X}^{*}_{s,d}<\mu^{*}_{s,d}-c_{t,s}\right)$
(Union Bound) $\displaystyle\leq$
$\displaystyle\sum^{D}_{d=1}\frac{1}{D}t^{-4}=t^{-4}$ (Chernoff-Hoeffding
Bound)

Similarly,
$\mathbb{P}(\bar{\bm{X}}_{i,s_{k}}\nprec\bm{\mu}_{i,s_{k}}-c_{t,s})\leq
t^{-4}$

Let

$l=\max\left\\{\bigg{\lceil}\frac{8\ln{t}+2\ln{D}}{(1-\xi)^{2}\min\limits_{k,d}\Delta^{2}_{k,d}}\bigg{\rceil},N_{0}(\xi)\right\\}.$

Since $s_{k,d}\geq l_{0}$, (11) is false.

Therefore, plugging the above results into the bound on $T_{k}(n)$ and taking
expectations of both sides, we get

$\displaystyle\mathbb{E}[T_{k}(n)]$
$\displaystyle\leq\bigg{\lceil}\frac{8\ln{t}+2\ln{D}}{(1-\xi)^{2}\min\limits_{k,d}\Delta^{2}_{k,d}}\bigg{\rceil}+N_{0}(\xi)+\sum^{\infty}_{t=1}\sum^{t-1}_{s=1}\sum^{t-1}_{s_{k}=l}$
$\displaystyle\left(\mathbb{P}(\bar{\bm{X}}^{*}_{s}\nsucc\bm{\mu}^{*}_{s}-c_{t,s})+\mathbb{P}(\bar{\bm{X}}_{k,s_{k}}\nprec\bm{\mu}_{k,s_{k}}-c_{t,s})\right)$
$\displaystyle\leq$
$\displaystyle\frac{8\ln{t}+2\ln{D}}{(1-\xi)^{2}\min\limits_{d}\Delta^{2}_{k,d}}+N_{0}(\xi)+1+\frac{\pi^{2}}{3},$

which concludes the proof.

###  VI-B Proof to Theorem 2

Let $k$ be the index of a sub-optimal node. Then
$\mathbb{P}(I_{t}\not\in\mathcal{P}^{*})\leq\sum_{v_{k}\not\in\mathcal{P}^{*}}\mathbb{P}\left(\bar{\bm{X}}_{k,T_{k}(t)}\nprec\bar{\bm{X}}^{*}_{T^{*}(t)}\right)$.
Note that $\bar{\bm{X}}_{k,T_{k}(t)}\nprec\bar{\bm{X}}^{*}_{T^{*}(t)}$ implies

$\bar{\bm{X}}_{k,T_{k}(t)}\nprec\bm{\mu}_{k}+\frac{\bm{\Delta}_{k}}{2},$ (12)

or

$\bar{\bm{X}}^{*}_{T^{*}(t)}\nsucc\bm{\mu}^{*}+\frac{\bm{\Delta}_{k}}{2}.$
(13)

Otherwise, suppose Eq. (12) and (13) do not hold, we have
$\bar{\bm{X}}_{k,T_{k}(t)}\prec\bar{\bm{X}}^{*}_{T^{*}(t)}$ which yields a
contradiction. Hence,

$\displaystyle\mathbb{P}\left(\bar{\bm{X}}_{k,T_{k}(t)}\nprec\bar{\bm{X}}^{*}_{T^{*}(t)}\right)$
$\displaystyle\leq$
$\displaystyle\underbrace{\mathbb{P}(\bar{\bm{X}}_{k,T_{k}(t)}\nprec\bm{\mu}_{k}+\frac{\bm{\Delta}_{k}}{2})}_{\text{first
term}}+\underbrace{\mathbb{P}(\bar{\bm{X}}^{*}_{T^{*}(t)}\nsucc\bm{\mu}^{*}+\frac{\bm{\Delta}_{k}}{2})}_{\text{second
term}}.$

Here we show how to bound the first term:

$\displaystyle\mathbb{P}(\bar{\bm{X}}_{k,T_{k}(t)}\nprec\bm{\mu}_{k}+\frac{\bm{\Delta}_{k}}{2})$
$\displaystyle\leq$
$\displaystyle\sum^{D}_{d=1}\mathbb{P}(\bar{X}_{k,T_{k}(t),d}>\mu_{k,d}+\frac{\Delta_{k,d}}{2})$
(Union Bound) $\displaystyle\leq$
$\displaystyle\sum^{D}_{d=1}\mathbb{P}(\bar{X}_{k,T_{k}(t),d}\geq\mu_{k,T_{k}(t),d}-\underbrace{|\delta_{k,T_{k}(t),d}|}_{\text{converges
to 0}}+\frac{\Delta_{k,d}}{2})$ $\displaystyle\leq$
$\displaystyle\sum^{D}_{d=1}\mathbb{P}(\bar{X}_{k,T_{k}(t),d}\geq\mu_{k,T_{k}(t),d}+\frac{\Delta_{k,d}}{4})$
$\displaystyle\leq$
$\displaystyle\sum^{D}_{d=1}\text{constant}(\frac{1}{t})^{\frac{\rho}{2}\left(\frac{\min\limits_{k,d}\Delta_{k,d}}{36}\right)^{2}}$
(Lemma 2)

The last step makes use of Lemma 1 and Lemma 2.

The second term can be bounded in a similar way. Finally, an integration of
the bounds shows that the failure probability converges to $0$ at a polynomial
rate as the number of selection goes to infinity.

## References

  * Arora et al. [2017] Akash Arora, Robert Fitch, and Salah Sukkarieh.  An approach to autonomous science by modeling geological knowledge in a bayesian framework.  In _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 3803–3810. IEEE, 2017.
  * Best et al. [2019] Graeme Best, Oliver M Cliff, Timothy Patten, Ramgopal R Mettu, and Robert Fitch.  Dec-mcts: Decentralized planning for multi-robot active perception.  _The International Journal of Robotics Research_ , 38(2-3):316–337, 2019.
  * Binney and Sukhatme [2012] Jonathan Binney and Gaurav S Sukhatme.  Branch and bound for informative path planning.  In _IEEE International Conference on Robotics and Automation_ , pages 2147–2154. IEEE, 2012.
  * Binney et al. [2013] Jonathan Binney, Andreas Krause, and Gaurav S. Sukhatme.  Optimizing waypoints for monitoring spatiotemporal phenomena.  _International Journal on Robotics Research (IJRR)_ , 32(8):873–888, 2013.
  * Cáp and Alonso-Mora [2018] Michal Cáp and Javier Alonso-Mora.  Multi-objective analysis of ridesharing in automated mobility-on-demand.  In _Robotics: Science and Systems_ , 2018.
  * Choudhury et al. [2016] Shushman Choudhury, Christopher M Dellin, and Siddhartha S Srinivasa.  Pareto-optimal search over configuration space beliefs for anytime motion planning.  In _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 3742–3749. IEEE, 2016.
  * Corah and Michael [2017] Micah Corah and Nathan Michael.  Efficient online multi-robot exploration via distributed sequential greedy assignment.  In _Proceedings of robotics: science and systems_ , 2017.
  * Ghrist et al. [2004] Robert Ghrist, Jason M O’Kane, and Steven M LaValle.  Pareto optimal coordination on roadmaps.  In _Algorithmic foundations of robotics VI_ , pages 171–186. Springer, 2004.
  * Guestrin [2003] Carlos Ernesto Guestrin.  _Planning Under Uncertainty in Complex Structured Environments_.  PhD thesis, Stanford, CA, USA, 2003.  AAI3104233.
  * Hollinger and Sukhatme [2014] Geoffrey A Hollinger and Gaurav S Sukhatme.  Sampling-based robotic information gathering algorithms.  _The International Journal of Robotics Research_ , 33(9):1271–1287, 2014.
  * Kocsis and Szepesvári [2006] Levente Kocsis and Csaba Szepesvári.  Bandit based monte-carlo planning.  In _European conference on machine learning_ , pages 282–293. Springer, 2006.
  * Kollat et al. [2008] Joshua B Kollat, Patrick M Reed, and Joseph R Kasprzyk.  A new epsilon-dominance hierarchical bayesian optimization algorithm for large multiobjective monitoring network design problems.  _Advances in Water Resources_ , 31(5):828–845, 2008.
  * LaValle [2006] Steven M LaValle.  _Planning algorithms_.  Cambridge university press, 2006.
  * LaValle and Hutchinson [1998] Steven M LaValle and Seth A Hutchinson.  Optimal motion planning for multiple robots having independent goals.  _IEEE Transactions on Robotics and Automation_ , 14(6):912–925, 1998.
  * Lee et al. [2018] Jeongseok Lee, Daqing Yi, and Siddhartha S Srinivasa.  Sampling of pareto-optimal trajectories using progressive objective evaluation in multi-objective motion planning.  In _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 1–9. IEEE, 2018.
  * Leonard et al. [2010] Naomi E Leonard, Derek A Paley, Russ E Davis, David M Fratantoni, Francois Lekien, and Fumin Zhang.  Coordinated control of an underwater glider fleet in an adaptive ocean sampling field experiment in monterey bay.  _Journal of Field Robotics_ , 27(6):718–740, 2010\.
  * Low [2009] Kian Hsiang Low.  _Multi-robot Adaptive Exploration and Mapping for Environmental Sensing Applications_.  PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, 2009.
  * Ma et al. [2018] Kai-Chieh Ma, Lantao Liu, Hordur K Heidarsson, and Gaurav S Sukhatme.  Data-driven learning and planning for environmental sampling.  _Journal of Field Robotics_ , 35(5):643–661, 2018\.
  * Marchant et al. [2014] Roman Marchant, Fabio Ramos, Scott Sanner, et al.  Sequential bayesian optimisation for spatial-temporal monitoring.  In _UAI_ , pages 553–562, 2014.
  * McCammon and Hollinger [2018] Seth McCammon and Geoffrey A Hollinger.  Topological hotspot identification for informative path planning with a marine robot.  In _IEEE International Conference on Robotics and Automation (ICRA)_ , pages 1–9. IEEE, 2018.
  * Meliou et al. [2007] Alexandra Meliou, Andreas Krause, Carlos Guestrin, and Joseph M. Hellerstein.  Nonmyopic informative path planning in spatio-temporal models.  In _Proceedings of National Conference on Artificial Intelligence (AAAI)_ , pages 602–607, 2007.
  * Rasmussen and Williams [2005] Carl Edward Rasmussen and Christopher K. I. Williams.  _Gaussian Processes for Machine Learning_.  The MIT Press, 2005.
  * Reif [1979] John H Reif.  Complexity of the mover’s problem and generalizations.  In _20th Annual Symposium on Foundations of Computer Science_ , pages 421–427, 1979.
  * Roijers et al. [2013] Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley.  A survey of multi-objective sequential decision-making.  _Journal of Artificial Intelligence Research_ , 48:67–113, 2013.
  * Singh et al. [2007] Amarjeet Singh, Andreas Krause, Carlos Guestrin, William Kaiser, and Maxim Batalin.  Efficient planning of informative paths for multiple robots.  In _Proceedings of the 20th International Joint Conference on Artifical Intelligence_ , pages 2204–2211, 2007.
  * Singh et al. [2009] Amarjeet Singh, Andreas Krause, Carlos Guestrin, and William J Kaiser.  Efficient informative sensing using multiple robots.  _Journal of Artificial Intelligence Research_ , 34:707–755, 2009.
  * Soltero et al. [2012] Daniel E Soltero, Mac Schwager, and Daniela Rus.  Generating informative paths for persistent sensing in unknown environments.  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 2172–2179. IEEE, 2012.
  * Sun et al. [2017] Wen Sun, Niteesh Sood, Debadeepta Dey, Gireeja Ranade, Siddharth Prakash, and Ashish Kapoor.  No-regret replanning under uncertainty.  In _IEEE International Conference on Robotics and Automation (ICRA)_ , pages 6420–6427. IEEE, 2017.
  * Susca et al. [2008] Sara Susca, Francesco Bullo, and Sonia Martinez.  Monitoring environmental boundaries with a robotic sensor network.  _IEEE Transactions on Control Systems Technology_ , 16(2):288–296, 2008.
  * Wang and Sebag [2012] Weijia Wang and Michele Sebag.  Multi-objective monte-carlo tree search.  In _Asian conference on machine learning_ , volume 25, pages 507–522, 2012.
  * Yu et al. [2014] Jingjin Yu, Mac Schwager, and Daniela Rus.  Correlated orienteering problem and its application to informative path planning for persistent monitoring tasks.  In _IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 342–349. IEEE, 2014.