
\section{Generative Adversarial Network with Direct Importance Estimation}
\label{sect:algo}
In this section, we introduce our algorithm, GANDI, 
which can take advantage of 
off-target samples from $q_{\act|\s}$ using importance weights. 
We first describe how to formulate the objective for training 
GANs with importance weights. For the purpose of exposition, we begin by 
assuming we are given $w(a)$, and we only have samples 
from the off-target distribution, $\mathbf{A}_q$, and none from the 
target distribution. Using importance weights $w(a)$,  
the objective for the discriminator in GANs becomes
\begin{align}
D&= \arg\min_D \sum_{i=1}^{n_q} w(a_q^{(i)})\log D(a_q^{(i)}) + \sum_{i=1}^{n_g} \log (1-D(a_g^{(i)}))
\label{eq:igan}
\end{align}
In trying to solve the equation~\ref{eq:igan},  it is
 critical to have balanced training set sizes $n_p$ and $n_g$.
In the importance weighted version of the GAN shown in 
equation~\ref{eq:igan}, however, the sum 
of the weights  $c = \sum_{i=1}^{n_q} w(a_q^{(i)})$, serves as an 
{\em effective sample size} for the data $\mathbf{A}_q$.  
To achieve a balanced objective, we might then select $n_g$ 
to be equal to c.  

Taking this approach would require adjusting the the GAN objective 
function and modifying mini-batch gradient descent algorithm to
use  uneven mini-batch sizes in every batch in training,
 which is awkward in many
 high-performance NN software packages.  Instead,
 we develop a method for bootstrapping $\mathbf{A}_q$ that allows us to use existing
 mini-batch gradient descent codes without modification.
Specifically, instead of multiplying each off-target sample by its importance weight, 
we bootstrap (i.e. re-sample the data from $\mathbf{A}_q$ with replacement), 
with a probability $p_w(a)$, where
$
p_w(a) = \frac{w(a)}{\sum_{i=1}^{n_q} w(a_q^{(i)})} \, .
$
This method allows us to generate a dataset $\hat{\mathbf{A}}$ in which the 
expected number of instances of each element of 
$\mathbf{A}$ is proportional to its importance weight.
Moreover, since we bootstrap, the amount of training data remains the same, 
and $D$ now sees a balanced number of samples effectively drawn from 
$p(a)=w(a)q(a)$ and $p_G$.

One can show that $p_w$ is actually proportional to $p$.
\begin{prop} For $ a \in \mathbf{A}_q$,
$$p_w(a) = k\cdot p(a)\text{ where } k=\frac{1}{ \sum_{i=1}^{n_q}w(a_q^{(i)})} \, .$$ 
\end{prop}
\iffalse
\begin{proof}
\begin{align*}
p_w(x) &= \frac{w(a)}{\sum_{i=1}^{n_q}w(a_q^{(i)})} \cdot q(a)\\
&=\frac{p(x)}{ \sum_{i=1}^{n_q}w(a_q^{(i)})}\\
&\propto p(x)
\end{align*}
\end{proof}
\fi
This means that samples drawn from the importance-reweighted data $\mathbf{A}$
 can play the role of $\mathbf{A}_p$ in the GAN objective.


We now describe some practical details for approximating $w(a)$ with
$\hat{w}(a)$, whose architecture is a DNN. Equation \ref{eq:lsif} can be
readily solved by a mini-batch gradient-descent algorithm implemented
using any readily available NN software package.  The non-negativity
constraint can also be straight-forwardly incorporated by simply using
the rectified linear activation function at the output
layer\footnote{In practice, this often lead the weights to
  converge to 0.  Although this can be avoided with a careful
  initialization method, we found that it is effective to just
  use linear activation functions, and then just set $w(a)=0$ if
  $w(a)<0$.}.  Now, with estimated importance weights and bootstrapped
samples, the objective for $D$ shown in equation~\ref{eq:igan} becomes
\begin{align}
 \hat{D} = \arg\min_D\sum_{i=1}^{n_q} D(a_w^{(i)}) + \sum_{i=1}^{n_g} \log(1-D(a_g^{(i)})) \label{eq:gandiD} \, ,
\end{align}
 where $a_w^{(i)}$ denotes a bootstrapped sample from $\mathbf{A}_q$, and $n_q=n_g$.
This involves just using $\mathbf{A}_q$, but 
in practice, we also use $\mathbf{A}_p$, by simply augmenting the  dataset $\mathbf{A}_q$ with 
$\mathbf{A}:=\mathbf{A}_q \cup \mathbf{A}_p$, and then applying $\hat{w}(\cdot)$ to $\mathbf{A}$ for bootstrapping, yielding 
final dataset $\hat{\mathbf{A}}$.  Algorithm~\ref{alg:GANDI}
contains the code for GANDI.

We illustrate the result of the bootstrapping with a simple example, shown 
in Figure \ref{fig:toyex}, where we have a Gaussian mixture model for both 
on-and off-target distributions $p$ and $q$, where $p$ is a mixture of two
Gaussians centered at $(1,1)$ and $(3,1)$, and $q$ is a mixture of three 
Gaussians at $(1,1), (3,1),$ and $(2,2)$ 
with larger variances than those of $p$.
\begin{figure*}
\centering
\begin{subfigure}[t]{0.3\textwidth}
  \centering
  \includegraphics[width=0.6\linewidth,height=2cm]{./figure/p_and_q.png}
  \caption{ Distributions $p$ and $q$}
\label{fig:pq}
\end{subfigure}
\begin{subfigure}[t]{0.3\textwidth}
  \centering
  \includegraphics[width=0.6\linewidth,height=2cm]{./figure/Xp_Xq.png}
  \caption{ Off- and on-target samples }
\end{subfigure}\\
\begin{subfigure}[t]{0.3\textwidth}
  \centering
  \includegraphics[width=0.6\linewidth,height=2cm]{./figure/w_distribution.png}
  \caption{Importance weights of $\mathbf{A}$.}
  \label{fig:trainset_toy}
\end{subfigure}\hfill
\begin{subfigure}[t]{0.3\textwidth}
  \centering
  \includegraphics[width=0.6\linewidth,height=2cm]{./figure/hatX.png}
  \caption{ Bootstrapped samples  }  
\end{subfigure}\hfill
\begin{subfigure}[t]{0.3\textwidth}
  \centering
  \includegraphics[width=0.6\linewidth,height=2cm]{./figure/Pg_and_P.png}
  \caption{  $p_G$ and the target distribution $p$. }
\end{subfigure}
\caption{Example of importance weight estimation (c), bootstrapping (d),
 and samples from $p_G$ and $p$ (e) in an illustrative domain with Gaussian mixtures. }
\label{fig:toyex}
\end{figure*} 

\begin{algorithm}[tb]
\small
   \caption{GANDI($\mathbf{A}_p,\mathbf{A}_q$)}
   \label{alg:GANDI}
\begin{algorithmic}
\STATE $\hat{w} \leftarrow  EstimateImportanceWeights(\mathbf{A}_p,\mathbf{A}_q)$ // objective (\ref{eq:lsif}) with on-and off-target samples $\mathbf{A}_p$ and $\mathbf{A}_q$ \\
\STATE $p_w(a) := \frac{\hat{w}(a)}{\sum_{i=1}^{n_q}\hat{w}(a_q^{(i)}) + \sum_{i=1}^{n_p}\hat{w}(a_p^{(i)}) }$ // define bootstrap probability distribution
\STATE $\mathbf{A} \leftarrow \mathbf{A}_p \cup \mathbf{A}_q$ 
\STATE $\hat{\mathbf{A}} \leftarrow Bootstrap(\mathbf{A}, p_w)$ // sample $\mathbf{A}$ with probability $p_w$, with replacement
\STATE $G \leftarrow TrainGAN(\hat{\mathbf{A}})$ // train the GAN using objectives (\ref{eq:ganD}) and (\ref{eq:ganG}) with $\hat{\mathbf{A}}$ as on-target samples
\STATE{\bf return} $G$
\end{algorithmic}
\end{algorithm}
\iffalse
Consider the following toy example
\begin{align*}
p &= \frac{1}{2} \cdot \mathcal{N}(\mu_1,\Sigma_1) + \frac{1}{2}\cdot\mathcal{N}(\mu_2,\Sigma_1) \\
q &= \frac{1}{3} \cdot \mathcal{N}(\mu_1,\Sigma_2) + \frac{1}{3}\cdot\mathcal{N}(\mu_2,\Sigma_2) +  \frac{1}{3} \cdot \mathcal{N}(\mu_3,\Sigma_2) 
\end{align*}
where
\begin{align*}
\mu_1 &= \begin{bmatrix} 1 \\ 1 \end{bmatrix}, 
\mu_2 = \begin{bmatrix} 3 \\ 1 \end{bmatrix},
\mu_3 = \begin{bmatrix} 2 \\ 2 \end{bmatrix}\\
\Sigma_1 &= \begin{bmatrix}
0.05 & 0.05 \\
0.05 & 0.05 
\end{bmatrix},
 \Sigma_2 =\begin{bmatrix}
0.1& 0.1\\
0.1& 0.1
\end{bmatrix}
\fi

\section{Background}
\subsection{Planning in continuous spaces}
A deterministic continuous action and state space planning
 problem is a tuple $[\mathcal{S}, \mathcal{A},s_0, G, T]$ where 
$\mathcal{S}$ and $\mathcal{A}$ are state and action spaces,
 $T:\mathcal{S} \times 
\mathcal{A} \rightarrow \mathcal{S}$ is a transition function that
maps a state and an action to a next state, $s_0 \in \mathcal{S}$ is the
initial state and $G \subset \mathcal{S}$ is a goal set.

An instance of a planning problem consists of a tuple $(s_0,G,\omega)$, 
where $\omega\in \Omega$ represents parameters of a problem instance. 
While the state changes according to $T$ when an action is executed, 
the parameters represent aspects of the problem that do not change within
the given instance. For example, a state might represent
poses of objects to be manipulated by a robot,
 while $\omega$ might represent their
shapes.  Given a planning problem instance, a heuristic state-space planner
requires a heuristic function $H:\mathcal{S} \rightarrow \mathbb{R}$
that estimates a cost-to-go. This function might be learned, or
designed by a user. The planning algorithm shown in 
Algorithm~$\ref{alg:planalgo}$ describes an extension of
discrete-space heuristic planner to continuous-spaces. This version 
of the algorithm is greedy with respect to
$H$, but it is straightforward to arrange for a version that is more
like A*, by taking path cost to the current state into account as well.


The key distinction from a discrete state-action space heuristic search 
algorithm is the action-sampling distribution $q_{\act|\s}$ and the 
reconsideration strategy for a node.
While in the discrete case we push all the neighbors of the current
node, here we sample $k$ actions and then push the resulting nodes.
Without any domain-specific knowledge, $q_{\act|\s}$ is a uniform distribution
in some bounded region in $\mathcal{A}(s,\omega)$ that depends on the 
current state and the parameters of the problem. 
The reconsideration strategy refers to 
pushing the node that we just popped  back to the queue, in order to 
guarantee probabilistic completeness. 


Given this setup, we can see that even a perfect heuristic will not be
helpful unless good action samples are generated. Moreover, in most
cases we have an imperfect heuristic function. This motivates the
problem of learning an action-sampling distribution, which we formulate next
by considering what information we can extract from search experience.


\iffalse
In many settings, a robot must face a sequence of related planning
problems, which share some aspects, such as the robot's kinematics and
placement of permanent obstacles, but differ along other aspects, such
as the placement of movable objects, starting configuration, or goal.
Let us define $\Omega$ to be the space of parameters of the planning
problems that the robot will encounter.  Furthermore, we will assume
that the particular problem instance $\omega \in \Omega$, together
with any states that will be encountered, are fully observable.

A solution to a planning problem, which is a sequence of states and
actions $(s_0, a_1), \ldots, (s_k, {it None})$, where $s_k \in  G$ and
$s_i = T(s_{i-1}, a_i)$ for all $i = 1..k$.

Our objective is:  given experience with previous problem instances
$\omega$, learn something that will make it possible to plan much more
efficiently to find solutions for  new problem instances in $\Omega$.    

To make the problem and solution more concrete, consider the planning
algorithm shown in algorithm~$\ref{alg:planalgo}$.  Like most planning
algorithms, it takes as input the initial state, goal set, and
transition function of a planning problem.  In addition, it takes a
batch size $k$, a heuristic function
$H:\mathcal{S} \rightarrow \mathbb{R}$, and a sampling distribution
$q_{\act|\s}$.  This version of the algorithm is greedy with respect to
$H$, but it is straightforward to arrange for a version that is more
like A*, by taking path cost into account as well.

The most important feature of this algorithm is that it operates in
{\em continuous action space}.  So, when a node is removed from the search
queue, $k$ actions are sampled from distribution $q_{\act|\s}(a \mid s)$
and used to create $k$ child nodes of node $n$.  However, to maintain
completeness, we push node $n$ back onto the queue, in case the
action samples that were originally drawn did not lead to a good
solution.

Given the fact that the action space is continuous and may only ever
by partially sampled, even if $H$ were perfect, the search might be
very inefficient, if the sample actions do not, with high probability,
have low values of $H$.   Thus, our focus will be on $q_{\act|\s}$: an
uninformed sampling distribution can lead to a disastrously bad
search.  In many robotics problems, in fact, successful samples must
be drawn from a lower-dimensional sub-manifold of $\mathcal{A}$ (for
example, finding a configuration of the robot that will allow it to
grasp an object at a certain pose with a certain grasp);  we will
assume for purposes of this paper that when conditioning on the state
$s$, it is known what an appropriate sample space for actions is,
$\mathcal{A}(s)$, and 
that the set of potentially successful actions has positive measure
under the uniform distribution on $\mathcal{A}(s)$.
\fi

\begin{algorithm}[tb]
\small
 \caption{Search($s_0,G,T,k, H, q_{\act|\s}$)}
 \label{alg:planalgo}
\begin{algorithmic}
\STATE $Q = {\it InitQueue}({\it Node}(s_0))$
\WHILE{True}
\STATE $n= Q.pop(\arg\min_{n\in Q} H(n.s))$ //dequeue the cheapest $n$
\IF {$n.s \in G$}
\STATE {\bf return} $n$
\ENDIF
\FOR{$i \in 1..k$} 
\STATE Sample $a \sim q_{\act|\s}(a \mid n.s)$
\STATE $Q.push( Node(T(n.s,a) )$
\ENDFOR
\STATE $Q.push(n)$ // reconsideration
\ENDWHILE
\end{algorithmic}
\end{algorithm}


\subsection{Problem formulation}
Ideally, our objective would be to learn a distribution that
assigns zero probability to actions that are not on an
optimal trajectory to $G$, and non-zero probability to actions on 
an optimal trajectory. Such a distribution would yield a path to
a goal without any exploration, regardless of the quality of the given
heuristic function.


Unfortunately, in sufficiently difficult problems, optimal planners are 
not available, therefore it is 
impossible to determine  whether an action was on an optimal 
path from the search-experience data. Thus, we consider
an alternative objective: learn a distribution that 
assigns low probability to actions
that lead to undesirable parts of the state space.
 We now examine two types of undesirable actions that lead
to such states.

The first type is {\em dead-end actions} that lead to {\em dead-end states}. 
A state $s$ is a dead-end state if there is no feasible path
from $s$ to a state in $G$.  Dead-end states are clearly to be avoided if
possible, because all search effort below them in the search tree is
guaranteed to be wasted. An example of a dead-end state is shown in
Figure~\ref{fig:deadend_ex}. Here, the robot is asked to pack
five objects into the relatively tight bin. It cannot move an object
once it is placed, so if the robot places a first few objects
in the front of the bin like in Figure~\ref{fig:deadend_ex} (left),
then it will be in a dead-end state. 

The second type is {\em no-progress actions} that transition to a state
that has the same or greater true cost-to-go as the current state.
 An example is shown in Figure~\ref{fig:cycle_ex}, where 
the robot has to reconfigure
poses of the green objects to find a collision-free space to
reach the orange object with its left arm. When the robot moves 
the light green object as shown in Figure~\ref{fig:cycle_ex} 
(left) to (right), this action does not constitute progress towards making room for 
reaching the target object.

Now, our objective is to learn an action distribution $p_{\act|\s}$ that assigns
low probabilities to these two types of actions.
We denote the $m$ search experience episodes for training data,
 collected using a
domain-independent action sampler $q_{\act|\s}$, as
$\Big\{ \Big[(s_i,a_p^{(i)})_{i=1}^{n_p},(s_i,a_q^{(i)})_{i=1}^{n_q},(\omega^{(j)},s_0^{(j)},G^{(j)}) \Big] \Big\}_{j=1}^{m}  $
where $a_p^{(i)}$ is an action on the trajectory from $s_0^{(j)}$ to $s\in G^{(j)}$, 
$a_q^{(i)}$ is an action in the search tree, but not the solution
trajectory, and $s_i$ is the state in which $a_p^{(i)}$ or $a_q^{(i)}$ was executed.
$n_p$ and $n_q$ denote the number of state and action pairs that
are on the trajectory to the goal and the rest, respectively.

Fortunately, the distribution of $(s,a)$ pairs on successful
trajectories in the data has the following properties: they have
zero probability assigned to dead-end states and actions, dead-end
actions and states cannot occur on a path to the goal. They also have
low probability assigned to no-progress actions, because most
actions, though not necessarily all, are making progress.  However, we
cannot say anything about $(s,a)$ pairs not on a successful trajectory:
they may or may not be desirable.  Therefore, we will call the $a_p^{(i)}$
values \emph{on-target} samples, and the $a_q^{(i)}$ as \emph{off-target}
samples. Our algorithm, GANDI, uses both of these two sources of data
to learn a target distribution.

\subsection{Generative Adversarial Networks}
The objective of a GAN is to obtain a
generator $G$ that transforms a random variable $z$, 
sampled usually from a Gaussian or a uniform distribution, to
a random variable of interest which in our case is an action $a$.
A GAN learns $p_G$, an approximation of the target distribution, which
in our case is $p_{\act|\s}$. For the purpose of
description of GAN, we will treat the distributions 
as unconditional; they can be directly extended to condition on 
$s$ by viewing the transformation as mapping $(s,z)$ to $a$.

We denote the on-target samples
$\mathbf{A}_p := \{a_p^{(i)}\}_{i=1}^{n_p}$, and the samples generated by $G$ as 
$\{a_g^{(i)}\}_{i=1}^{n_g}$. To learn the generator $G$, a GAN alternates
between optimizing a function $D$, which tries to 
output 1 on on-target samples and output 0 on samples generated by $G$,
and optimizing $G$, which tries
 to generate samples that cause $D$ to output 1. 
This leads to the following objectives:
\begin{align}
D  &= \arg\min_D\sum_{i=1}^{n_p} \log D(a_p^{(i)}) + \sum_{i=1}^{n_g} \log(1-D(a_g^{(i)}))
\label{eq:ganD}\\
G  &= \arg\max_G \sum_{i=1}^{n_g} \log D(a_g^{(i)})
\label{eq:ganG}
\end{align}
where $n_p=n_g$ to force $D$ to assume the classes are equally likely.
After training, given a sample of $z \sim p_z$, the neural
 network $G(z)$ outputs $a$ with probability
$p_G(a)$.

\subsection{Direct importance ratio estimation}
We now describe an approach to estimate  importance weights between the 
target and uniform distribution,
$
w(a;s) = p_{\act|\s}(a|s)/q_{\act|\s}(a|s)
$ using a deep neural network (DNN).  If we had these weights, then
we could use $\mathbf{A}_q$ to augment $\mathbf{A}_p$ used for training the 
generative model $p_G$ to approximate $p_{\act|\s}$. While
there are several methods for estimating 
$w(a)$~\citep{HuangNIPS2007,KanamoriJMLR2009,SugiyamaNIPS2008}, 
we will use the least squares
approach of Kanamori et al.~\citeyearpar{KanamoriJMLR2009} because it integrates easily 
into DNN-based methods. In this approach, we approximate $w$ with $\hat{w}$ using 
the objective function 
\begin{align*}
J(\hat{w}) &= \int_a (\hat{w}(a)-w(a))^2 q(a) da \, .
\end{align*}
In practice, we optimize its sample approximation version, $\hat{J}(\hat{w})$, 
which yields
\begin{align}
\hat{w}
&= \arg\min_{\hat{w}} \sum_{i=1}^{n_q} \hat{w}^2(a_q^{(i)}) - 2\sum_{i=1}^{n_p} \hat{w}(a_p^{(i)}), \text{ s.t } \hat{w}(a) \geq 0 \label{eq:lsif}
\end{align}
where the constraint is enforced to keep the importance weights positive.
Intuitively, $\hat{w}$ attempts to assign high values  to $a_p^{(i)}$ and 
low values $a_q^{(i)}$, to the degree allowed by its hypothesis class. 

The method was originally proposed to be used with a linear architecture, 
in which $\hat{w}(a) = \theta^T\phi(a)$; this implies there is a 
unique global optimum as a function of $\theta$, but 
requires a hand-designed feature 
representation $\phi(\cdot)$.
For robot planning problems, however,
 manually designing features is
difficult, while special types of DNN architectures, 
such as convolutional neural networks, may effectively
learn a good representation. 
In light of this, we represent $\hat{w}$ with a DNN. 
The downside of this  strategy is the loss of
convexity with respect to the free parameters $\theta$, but we have found that the 
flexibility of representation offsets this problem.





\section{Conclusion}
We presented GANDI, a generative model learning
algorithm that uses both on-target and
cheaper off-target samples for data efficiency using importance-ratio estimation.
We provided guarantees on how the error in importance-ratio estimation affects the
performance of the learned model, and  illustrated
that this learning algorithm is effective for learning an 
action sampling distribution for guiding the search of a 
planner in difficult robot planning problems.

\section{Experiments} \label{sec:experiments}


We validate GANDI on three different robot planning 
tasks that involve continuous state and action spaces and finite depths.
The purpose of these experiments is to verify the hypothesis
that learning an action sampling distribution
improves planning efficiency relative to a standard uniform sampler,
and a GANDI is more data efficient than a standard GAN that is
only trained with on-target samples.

We have three tasks that might occur in a warehouse.
The first is a bin-packing task, where a robot has to
pack different numbers of objects of different sizes into a
relatively tight bin. The second task is to stow objects into
crowded bins, where there already are obstacles. The final
task is a reconfiguration task,
where a robot needs to reconfigure five randomly placed
moveable objects in order to make room to reach
a target object. In the first two tasks, the robot is not 
allowed to move the objects once they are placed, which leads
 to a large volume of dead-end 
states that cause wasted computational effort for a 
planner with an uniform action sampler. In the third task,
we have no dead-end states, but a planner could potentially
waste computational effort in trying no-progress actions.
For all tasks, the robot is only allowed to grasp
objects from the side; this is to simulate a common scenario
in a warehouse environment, with objects in 
a place covered on top, such as a shelf.
For the first two experiments, we use depth-first-search. This
is equivalent to having a heuristic that estimates a cost-to-go
by number of objects placed, since we cannot move objects
once they are placed. For the last experiment we use 
breadth-first-search as our planner, since there is no
simple heuristic function evident. For all
cases, the number of action samples per node, $k$, is 3.
We use Algorithm~\ref{alg:planalgo} with a given action
sampler.

Throughout the three tasks, we compare three different 
action samplers in terms of success rate within a given
time limit: the uniform sampler that uniformly samples
an action from a specified action space, a standard GAN
 trained only with on-target samples, and GANDI, which is 
trained with both on and off-target samples. We use the same
architecture for both the standard GAN and GANDI, and
perform 100 repetitions to obtain the 95\% confidence intervals
for all the plots. The architecture description is in
the appendix.

A crucial drawback of generative adversarial networks
is that they lack an evaluation metric; thus it is
difficult to know when to stop training. We
deal with this by testing weights from all epochs on
10 trials, and then picking the weights with the 
best performance, with which we performed 100 additional
repetitions to compute the success rates.
\begin{figure*}
\centering
	\begin{subfigure}[b]{0.23\textwidth}	
		\centering
		\includegraphics[width=2.5cm,height=2.5cm]{./figure/gan_placement_ex}
		\caption{GAN's action sampling distribution }
		\label{fig:gan_ex}
	\end{subfigure} 
	\begin{subfigure}[b]{0.23\textwidth}	
		\centering
		\includegraphics[width=2.5cm,height=2.5cm]{./figure/ian_placement_ex}
		\caption{GANDI's action sampling distribution}
		\label{fig:gandi_ex}
	\end{subfigure} 
  \begin{subfigure}[b]{0.23\textwidth}	
		\centering
		\includegraphics[width=2.5cm,height=2.5cm]{./figure/reconfig_ex}
		\caption{A GANDI's action distribution }
		\label{fig:rearrangement_ex}
	\end{subfigure} 
  \begin{subfigure}[b]{0.23\textwidth}	
		\centering
		\includegraphics[width=2.5cm,height=2.5cm]{./figure/ex_stow}
		\caption{A stow domain problem instance}
		\label{fig:stow_ex}
	\end{subfigure} 
		\caption{The left two figures show examples from the bin packing domain when 20 episodes of training data are used. Green indicates the on-target samples, and blue indicates the learned distributions. Figure \ref{fig:rearrangement_ex} shows an action distribution for the reconfiguration domain when given 35 training episodes.}
\end{figure*} 
\begin{figure*}
\centering
	\begin{subfigure}[b]{0.23\textwidth}	
		\centering
		\includegraphics[height=2.5cm]{./figure/placement}
    \caption{The bin packing domain}
		\label{fig:bin_packing_rate}
	\end{subfigure} 
	\begin{subfigure}[b]{0.23\textwidth}	
		\centering
		\includegraphics[height=2.5cm]{./figure/stow_succ_rate}
    \caption{The stow domain }
		\label{fig:stow_rate}
	\end{subfigure} 
	\begin{subfigure}[b]{0.24\textwidth}	
		\centering
		\includegraphics[height=2.5cm]{./figure/rearrangement_succ_rate}
    \caption{The reconfiguration domain}
		\label{fig:rearrangement_rate}
	\end{subfigure} 
	\caption{Plots of success rate vs. number of training episodes for all three tasks}
\end{figure*} 
\subsection{Bin packing problem}
In this task, a robot has to move 5, 6, 7 or 8 objects into
a region of size 0.3m by 1m (width by length). 
The size of each object is uniformly random between 0.05m to 0.11m,
depending on how many objects the robot has to pack. 
A problem instance is defined by the
number of objects and the size of each object, 
$\omega = [n_{obj},O_{size}]$. A state is defined by the
object placements. For a given problem instance,
all objects have the same size. An example of a solved problem 
instance with $n_{obj}=5$ and $O_{size}=0.11$m is given
 in Figure~\ref{fig:deadend_ex} (right). 

The action space consists of the two dimensional (x,y) 
locations of objects inside the bin, and a uniform action sampler
uniformly samples these values from this region. The robot 
base is fixed. The planning depth varies from 5 to 8, depending
on how many objects need to be placed. This means that
plans consist of 10 to 16 decision variables. 
Clearly, there is a large of volume
of dead-end actions: any action that puts objects down in the 
front of the bin early will lead to a dead-end state.

Figure~\ref{fig:bin_packing_rate} shows the comparison among
GANDI, standard GAN, and uniform action sampling in terms of
success rate when given 5.0 seconds to solve a problem instance. 
We can see the data efficiency of GANDI: with 
20 training episodes, it outperforms the uniform sampler, 
while a standard GAN requires 50 training
episodes to do so. The uniform sampler can only solve
 about 50\% of the problem instances within this time limit, 
while GANDI can solve more than 70\%.

We also compare the distributions for GAN and
GANDI when the same number of training data are given.
Figures~\ref{fig:gan_ex} and~\ref{fig:gandi_ex} show
1000 samples  from GAN and GANDI for packing 5 objects. 
While GANDI learns to avoid the front-middle locations, GAN is
still close to a uniform distribution, and has
a lot of samples in this region which lead to dead-end
states. GANDI focuses its samples to the corners at the back or
the front so that it has spaces for all 5 objects.

\subsection{Stowing objects into crowded bins}
In this task, a robot has to stow 8 objects into 
three different bins, where there already are 10 obstacles. 
A bin is of size 0.4m by 0.3m, an obstacle
is of size 0.05m by 0.05m, and the objects to be placed down
are all of size 0.07m by 0.07m. A problem instance is defined
by the (x,y) locations of 10 obstacles, each of which is randomly
distributed in one of the bins. 
Figure~\ref{fig:stow_ex} shows an instance of a solved stow problem.

The action space for this problem 
consists of (x,y) locations of an object to be placed, 
and the robot's 
(x,y) base pose. This makes 4 dimensional continuous action-space.
The planning depth is always 8, for placing 8 objects.
Thus plans consist of of 36 continuous decision variables.
Again, there is a large volume of dead-end actions, 
similarly to the previous problem: 
putting objects down without consideration of poses of
 later objects can potentially block collision-free 
paths for placing them.

Figure~\ref{fig:stow_rate} compares the success rates of 
the algorithms with a 30-seconds time limit for planning. For the uniform
sampler, we sample first an object placement pose, and then
sample a base pose that can reach the object at its new 
location without colliding with other objects. Unlike the 
previous task, learning-based approaches significantly
outperform the uniform sampling approach for this task.
This is because there is an unstated constraint between
the object placement location and base pose, which is that
the location must be within a reachable distance from
the sampled robot base pose. 
Again, we can observe the data efficiency of GANDI compared to GAN.
When the number of training data points is small, it outperforms it.

\subsection{Reconfiguration planning in a tight space}
In this task, a robot has to reconfigure movable obstacles out of the
way in order to find a collision-free inverse-kinematics solution for its 
left-arm to reach the target object. 
There are five movable obstacles in this problem,
each with size 0.05m by 0.05m, and the target object of size 0.07m by 0.07m, 
and the reconfiguration must happen within a bin, which is of size
0.7m by 0.4m. A problem instance is defined by (x,y) locations 
of the movable obstacles and the target object.  The movable obstacles are randomly 
distributed within the bin; the target object location is distributed along the back of the bin.
Figure \ref{fig:rearrangement_ex} shows an example of a rearrangement 
problem instance at its initial state, with the black region indicating
the distribution of target object locations.


An action specification consists of one discrete value and two continuous values:
what object to move and the (x,y) placement pose of the object being moved.
There is no fixed depth. For both the uniform random sampler and 
the learned generative model, we uniformly at random choose an object to move. 
The robot base is fixed, and the robot is not allowed to use its right arm.

Figure~\ref{fig:rearrangement_rate} compares the success rates of the
algorithms with a 10-seconds time limit for planning. In this problem, 
the learning based approaches outperform the uniform sampler 
even with a small number of training data points. The relationship 
between GANDI and GAN is similar to the previous experiment, except 
that GANDI and GAN are within the each other's confidence interval
when a small number of training points are used. Eventually,
GANDI comes to clearly outperform GAN.

We would like to know if GANDI's distribution indeed
assigns low probabilities to no-progress actions. 
In Figure~\ref{fig:rearrangement_ex},
we show GANDI's distribution of obsject placements after training on 35 episodes. 
The left top corner of the bin is empty because there are no
collision-free inverse-kinematics solution for that region
\footnote{ The robot's left arm will collide
with the bin}. As the figure shows, there are no placement samples 
in front of the target object, but only on the sides that 
 would contribute to clearing space for the robot's left arm to reach
the target object.




\section{Introduction}
The ability to efficiently plan in domains with
continuous state and action spaces  is a crucial 
yet challenging skill to obtain for a robot. 
For the classical path planning problem of getting
from an initial state to a goal state, the motion
planning community has found that random sampling
strategies or gradient-based approaches
work reasonably well~\citep{rrt,ZuckerIJRR13}.

In a variety of important planning problems, however, 
these approaches fall short. Consider the problem in 
Figure~\ref{fig:cycle_ex}, where the robot has to find 
a collision-free inverse kinematics solution
to reach the orange object by reconfiguring the green objects.
An unguided uniform sampling approach performs poorly since the state 
space is extremely high-dimensional, consisting of 
the combined configuration spaces of the robot and many objects.
A gradient computation is also difficult, since the robot 
has to make choices that are both discrete, 
such as which object to move, and continuous, 
such as where to place the chosen object, making the problem's
optimization manifold non-smooth. This type of hybrid 
optimization problem is difficult to solve efficiently.

\begin{figure}
  \centering
  \begin{subfigure}[t]{0.5\textwidth}
		  \centering
      \includegraphics[height=2cm]{./figure/cycle_ex1}
		  \includegraphics[height=2cm]{./figure/cycle_ex2}
      \caption{An example of the reconfiguration task. The movable obstacles are colored green, and the target object is colored with orange. }
		  \label{fig:cycle_ex}
  \end{subfigure}
  \begin{subfigure}[t]{0.5\textwidth}
      \centering
		  \includegraphics[height=2cm]{./figure/deadend_1}
		  \includegraphics[height=2cm]{./figure/deadend_2}
      \caption{ An example of the bin packing task. The color of objects indicate 
the order of placement, and the darker the earlier.}
		  \label{fig:deadend_ex}
  \end{subfigure}
  \caption{Examples of reconfiguration and bin packing. For both tasks, the robot can only grasp objects from the side.}
\end{figure} 

A promising approach for such complex hybrid planning problems 
is to sample some predefined number of actions in each state, 
and then treat the resulting problem as a heuristic search
over discrete states and actions. 
A reconsideration strategy, which reconsiders states that 
has been previously expanded, can be employed to guarantee 
completeness.

The main distinction from a search in discrete state and action spaces is
that, in the discrete case, having a good heuristic
function is sufficient for efficiently finding a solution. A perfect
heuristic, for instance, would find a plan without any exploration.
However, in the continuous state and action spaces this is not true;
if there is a very small volume of actions that lead to the goal, then
even with a perfect heuristic we might inefficiently sample actions
and reject most of them. Moreover, if the heuristic is not perfect,
as is typically the case, having samples in undesirable regions of
the action space could lead to expanding nodes that do not efficiently
lead to a goal state.

Based on this observation, our objective in this paper is to learn 
from search 
experience an action sampling distribution  that will guide the search of a planner
that has an imperfect heuristic. 
We use a generative adversarial network (GAN), 
a recent advance in generative model learning, to approximate this 
distribution~\citep{GoodfellowNIPS2014}.
Unlike other methods, a GAN only requires a forward pass through a neural 
network to generate a sample, and does not require any prior
distributional assumptions.
The main challenge in learning a generative model from search
experience data is that in a successful 
episode of search, there is a large number of state and action
pairs that we sample but are not known to be on a trajectory to the goal,
and only a relatively small number of samples that are on a 
trajectory to the goal. We will refer to samples on a
successful trajectory as \emph{on-target} samples, to indicate
that they are from a target distribution that we would like to learn,
and the rest as \emph{off-target} samples.
While we could just use the small number of on-target samples, 
learning would be much more effective 
if we can find a way to use the abundant off-target samples as well.

In light of this, we propose a principled approach that can
learn a generative model from both on- and off-target samples.
To do this, we estimate the importance-ratio between the on-target 
and off-target distributions using both classes of
samples. We then extend GAN to introduce a new 
generative-model learning algorithm, called 
generative adversarial network with direct importance estimation (GANDI),
that uses the importance ratio to learn from
not only on-target samples, but also from off-target samples.
While this algorithm is domain independent, 
we will demonstrate its effectiveness in learning a target
action-sampling distribution.
We theoretically analyze how the importance-ratio estimation 
and the difference between target and non-target distributions
affect the quality of the resulting approximate distribution. 

We evaluate GANDI in three different planning problems
that commonly occur in warehousing applications.
We show that our algorithm outperforms a 
standard uniform sampler and a standard GAN in terms of 
planning  and data efficiency.



\section{Notation}
\begin{table*}[t]
\begin{tabular}{ |c |c|  }
\hline
$s,\mathcal{S}$  & state and state space \\
\hline
$a,\mathcal{A}$  & action and action space \\
\hline
$T $  & transition function \\
\hline
$\omega,\Omega$  & problem and problem space \\
\hline
$s_0,s_g$  & init and goal \\
\hline
$V$  & value function \\
\hline
$q_{\act|\s},p_{\act|\s},\mathcal{P}_{a|s},p^*_{\act|\s}$  & the given and target distributions, a set of target distributions, the ideal target distribution \\
\hline
$p_G,p_w$  & generator and bootstrap distributions \\
\hline
$a_p^{(i)},a_q^{(i)},a_g^{(i)},a_w^{(i)} $  & on,off, generator, and bootstrapped samples \\
\hline
$n_p,n_q,n_g $  & number of on,off, and generator samples \\
\hline
$w,\hat{w} $  & true  importance weight and its estimation \\
\hline
$ \mathbf{A}_q,\mathbf{A}_p$ & off target and ontarget datasets\\
\hline
\end{tabular}
\end{table*}
\fi

\section{Related work}
Our work touches upon four different topics: continuous state-action 
space planning, learning to guide planning, importance-ratio 
estimation, and generative model learning. 
We provide descriptions of approaches in these 
areas that are closest to our problem in terms of motivation and technique.

In the area of continuous-space planning, there are several approaches
that attempt to sample actions by employing optimistic optimization
methods for black-box functions. Mansley
et. al~\citeyearpar{MansleyICAPS2011} assign a hierarchical optimistic
optimization (HOO)~\citep{BubeckNIPS2009} agent at each state to
decompose the action space to sample promising ones. A similar
approach is taken by Bus\c{o}niu
et. al,~\citeyearpar{LucianADPRL2011}, where a simultaneous optimistic
optimization (SOO) agent is assigned at each
state~\citep{MunosNIPS11}. There are other approaches to more
specialized continuous state and action problems, such as
motion-planning and task-and-motion planning; these include
sample-based methods~\citep{rrt,prm,GarrettRSS2017,VBrownWAFR2016},
and gradient-based optimization methods
~\citep{ZuckerIJRR13,SchulmanIJRR14,ToussaintIJCAI15}.  The main
objective of all these approaches is to construct, on-line, an optimal
or a feasible plan without any off-line learning. No knowledge of
solving one problem instance is transferred to another.


In learning to guide search, there is a large body of work 
that attempts to learn a policy or a value function off-line,
 and then use this information during an on-line search 
to make planning efficient. These methods are usually applied to
discrete-action problems, where a recent prominent example is
 AlphaGo~\citep{alphago}. 
In that paper, Silver et. al train a supervised policy off-line, 
using imitation 
learning and train a value function using self-play; they then guide 
Monte Carlo Tree Search (MCTS) in an on-line phase using these functions.
In a similar line of work, Gelly et al.~\citeyearpar{GellyICML07} also integrates
an off-line learned value function with MCTS. For
learning to guide search in continuous-space planning problems, 
Kim et. al~\citeyearpar{KimICRA17}  describe an approach for 
predicting constraints on the solution space rather than a value 
function or an action itself.
The intuition is that a constraint is much more easily 
transferable across problem instances than a specific action in complex 
planning problems. We share this intuition, and we
may view the learned action distribution as constraining the search
space of a planning problem to promising regions.

Two recent advancements in generative-model learning, 
GANs~\citep{GoodfellowNIPS2014} 
and Variational Auto Encoders (VAEs)~\citep{VAE}, are 
appealing choices for learning an action-sampling 
distribution because inference is 
simply a feed-forward pass through a network.
GANs are especially appealing,
because for generic action spaces, we do not have any metric information
 available. VAEs, on the other hand, require a metric in an action space in 
order to compute the distance between a decoded sample and a true sample. Both
of these methods require samples  to be from a target distribution
that one wishes to learn. Unfortunately, in our case we have limited access to
samples from the target distribution, and this brings us to the importance-ratio
estimation problem.

There is a long history of work that uses importance sampling to 
approximate desired statistics for a target distribution $p$ using 
samples from another distribution $q$,
for example, in probabilistic graphical models~\citep{KollerFriedman2009} and
reinforcement learning problems~\citep{PrecupICML2001,SuttonBarto1998}.
In these cases, we have a surrogate distribution $q$ that is cheaper 
to sample than the target distribution $p$. 
Our work shares the same motivation as these problems, 
in the sense that in search experience data, samples that are on 
 successful trajectories are expensive to obtain, while other 
samples are relatively cheaper and more abundant.

Recently, importance-ratio estimation has been studied for the 
problem of covariate shift adaptation, which closely resembles our setting. 
Covariate shift refers to the situation where we have samples from 
a training distribution that is different from the target distribution. 
Usually, an importance-ratio
estimation method~\citep{KanamoriJMLR2009,SugiyamaNIPS2008,HuangNIPS2007} is 
employed to re-weight the samples from the training
distribution, so that it matches the target distribution 
for supervised learning.  We
list some prominent approaches here.
In kernel-based methods for estimating the importance~\citep{HuangNIPS2007},
authors try to match the mean of samples of $q$ and $p$ in a
feature space, by re-weighting the samples from $q$. In the direct estimation
approach, Sugiyama et al.~\citeyearpar{SugiyamaNIPS2008} try to minimize the
KL divergence between the distributions $q$ and $p$ by re-weighting $q$. In
another approach, Kanamori et al.~\citeyearpar{KanamoriJMLR2009} directly minimize 
the least squares objective between the approximate importance-ratios and the
 target importance-ratios. All these formulations yield convex
optimization problems, where the decision variables are parameters of a linear
function that computes the importance weight for a given random variable. Our
algorithm extends the direct estimation approach using a deep neural network, 
and then applies it for learning a generative model using off-and-on target samples.


\iffalse
In probabilistic graphical models, $q$ is used to
generate samples that are re-weighted to reflect
$p$~\cite{KollerFriedman2009}. Also related is \emph{off-policy}
learning for reinforcement learning problems, where there is an
exploration policy whose data we re-weight with importance weights to
approximate the value function for the target
policy~\cite{PrecupICML2001,SuttonBarto1998}.
Our work shares the same motivation as these works, in the sense that
in search experience data, samples that are on a success trajectories 
are expensive to obtain, while other samples are relatively
cheaper and abundant. However, our work differs in the sense that we
do not have {\it a priori} models for $p$ or $q$, but just have
samples drawn from each of them.  Thus, we would like to directly
estimate the importance weights based on these samples.
\fi
\iffalse

- Covariate shift problem
- Importance weight estimation
- Generative model learning

\fi

\iffalse
A recent method uses importance weights for training
variational autoencoders (VAEs), another type of NN generative model~\cite{BurdaICLR2005}.
However, their objective is to learn the VAE by deriving a strictly 
tighter log-likelihood lower bound using importance weighting,  
in order to alleviate modeling assumptions
made in the original objective of VAE, rather than to use off-target samples.

Note that GANs have been used in a semi-supervised learning
setting~\cite{Salimans2016ImprovedTF} to augment the training data for
a classifier.  This is quite distinct from our use of data from a
different distribution to improve a generator.  We do not know of any
work that uses off-target samples to improve the quality of a GAN model.
\fi


\section{ Proof for theorems}
We first have the following lemma, that readily follows
from the Proposition 1 and Theorem 1 of Goodfellow et al~\cite{GoodfellowNIPS2014}.
\begin{lemma}
For a fixed generator $G$, the optimal discriminator $\hat{\mathbf{A}}$
 that achieves the minimum of equation (6) is
$$ \hat{\mathbf{A}}^*(a) = \frac{\hat{w}(a)q(a)}{\hat{w}(a)q(a) + p_G(a)}$$
and the $p_G$ that achieves the maximum of of $\hat{D}^*$ is
$p_G = \hat{w}(a)q(a)$
\end{lemma}

Recall the definition of $\rho$, $$\rho = \sup_{x \in \mathcal{A}_p} \frac{q(a)}{p(a)}$$

We first prove the upper-bound on KL divergence between $p$ and $p_G$.
\begin{theorem} If $w(a) \geq \epsilon\ \forall x\in \mathcal{A}_q$,
 and $J(\hat{w}) \leq \epsilon^2$, then 
$$ {\rm KL}(p||p_G) \leq \log \Big(\frac{1}{1-\epsilon \rho}\Big)$$ 
\begin{proof}
\begin{align*}
{\rm KL}(p||p_G) &= \int_a p(a) \log \frac{p(a)}{\hat{w}(a)q(a)}da\\
\end{align*}
Since $J(\hat{w})\leq \epsilon^2$, we have
 $|\hat{w}(a) - w(a)|\leq \epsilon$, and
 $\forall a\in \mathcal{A}_q$, $\hat{w}(a) \geq w(a) -
\epsilon$. Decreasing the denominator increases
the value of the whole expression, we may take $ w(a)-\epsilon$ 
to upper bound the ${\rm KL}(p||p_G)$. 
\begin{align*}
{\rm KL}(p||p_G) &\leq \int_a p(a) \log \frac{p(a)}{q(a)(w(a)-\epsilon)}\\
&= -\int_a p(a) \log \frac{q(a)w(a) - q(a)\epsilon}{p(a)}\\
&= -\int_a p(a) \log \Big( 1 - \frac{q(a)}{p(a)}\epsilon \Big)\\
&\leq  -\int_a p(a) \log \Big( 1 - \rho\epsilon \Big)
\end{align*}
where the last line follows from the definition of $\rho$, and decreasing the quantity inside
log increases the value of the whole expression. Now this is equivalent to
\begin{align*}
{\rm KL}(p||p_G) \leq -log(1-\rho\epsilon)
\end{align*}
Notice that $0\leq\rho \epsilon\leq 1$ because 
$\rho = \sup_{ x \in \mathcal{A}_p} \frac{1}{w(a)}$ and
$\epsilon < w(a)$. 
\end{proof}
\end{theorem}


We now prove the upper-bound on reverse-KL divergence between $p$ and $p_G$.
\begin{theorem}
If $J(\hat{w}) \leq \epsilon^2$, then
\[KL(p_G || p) \leq (1 + \epsilon) \log (1 + \epsilon\rho) \]
\end{theorem}

\begin{proof}
By Lemma 1,  $p_G(a) = \hat{w}(a) q(a)$, so
\[KL(p_G || p) = \int_a \hat{w}(a) q(a) \log \frac{\hat{w}(a) q(a)}{p(a)} da
\]
 Since $J(\hat{w})\leq \epsilon^2$, we have
 $|\hat{w}(a) - w(a)|\leq \epsilon$, and
 $\forall x\in \mathcal{A}_q$, $\hat{w}(a) \leq w(a) +
\epsilon$. So,
\begin{align*}
KL(p_G \mid p) & \leq \int_a (w(a) + \epsilon)q(a) \log \frac{(w(a) + \epsilon)
    q(a)}{p(a)} da \\
& \leq \int_a (w(a)q(a) + \epsilon q(a)) \log \frac{w(a)q(a) + \epsilon
    q(a)}{p(a)} da \\
& \leq \int_a (p(a) + \epsilon q(a)) \log \frac{p(a) + \epsilon q(a)}{p(a)} da \\
& \leq \int_a (p(a) + \epsilon q(a)) \log \left(1 +
  \epsilon\frac{q(a)}{p(a)}\right) da\\ 
& \leq \int_a (p(a) + \epsilon q(a)) \log (1 + \epsilon\rho) da\\
&  \leq \log (1 + \epsilon\rho) \int_a) (p(a) + \epsilon q(a)) da\\
&  \leq  (1 + \epsilon) \log (1 + \epsilon\rho)\\
\end{align*}
\end{proof}

\section{Details of experiments}
We have used Keras\footnote{\url{https://github.com/fchollet/keras}}, a deep learning software package, to
implement our NNs.

\subsection{ Architecture for experiments}
For the first domain, $D$, $G$, and $\hat{w}$ takes in  as input 
the number of objects to be placed and the shape of the object.
They do not conditioned on a state.
For the second domain, they take poses of objects as an input.
They do not condition on the objects already placed. For the last
domain, they take poses of all the objects on the table as input.

For the first domain, we use 3 layers of dense network for $D$,$G$, and $\hat{w}$.
For the second and last domain, we use convolutional layers, as the location of each
pose in the vector is unimportant.
Specifically, for $D$, we have a input convolutional layer that has filter 
size 2 by 2, with stride of 2 by 1, and 256 filters. This is followed by
a max pooling layer whose size is 2 by 1, and then this conv-max pooling is
repeated one more time. Then, it is followed by two more conv layers whose
number of filters is 256, and the filter size is 3 by 1. Then, the output
gets merged with the action input, which is then
followed by three dense layers each with size 32, 256, and 32. Lastly,
It uses sigmoid activation in its output layer.

The generator has exactly the same architecture, except that the last 
three dense layers have 32, 32, and 32 as its number of nodes. It has
linear output layer. $\hat{w}$ has exactly the same architecture as the generator

The maximum number of epochs for training $D$ and $G$ is 500, with 
batch size of 32. We used Adam with learning rate 0.001 for $D$ and $G$,
and Adadelta with learning rate 1.0 for $\hat{w}$.
\bibliographystyle{aaai}

\section{Theoretical analysis}
\label{sect:theory}
In this section, we analyze how error in importance estimation 
affects the performance of $p_G$ in approximating $p$.
The basic result on GANs, shown in the limit of infinite data,
representational and computational capacity, is that $p_G$ converges to
$p$~\citep{GoodfellowNIPS2014}, although subsequent papers have 
presented more subtle form of analysis~\citep{Arjovsky2017}.


Now, under the same assumptions, we consider the effect of using
importance weighted off-target data. If $w$ is exact, then $p(a)=w(a)q(a)$
and the GAN objective is unchanged. If, however, we use an estimation of
importance weighting function $\hat{w}$, then the objective of $\hat{D}$,
the importance-weight corrected discriminator, 
differs from $D$ and they achieve different solutions. 

We wish to analyze the effect of importance estimation error on KL and
reverse-KL divergence between $p$ and $p_G$. First,
define $\rho = \sup_{a \in \mathcal{A}_p} q(a)/p(a)$,
where $\mathcal{A}_p$ is the support of $p$.
We can see that $\rho >= 1$, with equality 
occurring when $p(a) = q(a)$ for all $a$.

For the KL divergence, we have the following theorem.
\begin{theorem} If $w(a) \geq \epsilon\ \forall a\in \mathcal{A}_q$,
 and $J(\hat{w}) \leq \epsilon^2$, then 
$$ {\rm KL}(p||p_G) \leq \log \Big(\frac{1}{1-\epsilon\rho}\Big)\;\;.$$ 
\end{theorem}
Note that $0\leq \epsilon \rho \leq 1$ due to the
 condition $w(a) \geq \epsilon$.
For reverse KL we have:
\begin{theorem}
If $J(\hat{w}) \leq \epsilon^2$,
$KL(p_G || p) \leq (1 + \epsilon) \log (1 + \epsilon\rho)$\;.
\end{theorem}
The proofs are included in the supplementary material.

These theorems imply three things:
(1) If $w=\hat{w}$, then $\epsilon=0$, and both divergences go to 0, regardless of $\rho$;
(2) If $p=q$, then the error in importance weight estimation is the only
source of error in modeling $p$ with $p_G$. This error can be arbitrarily large, as
$\epsilon$ becomes large; and
(3) If $p\neq q$ then $\rho>1$, and it contributes to the error in modeling $p$ with $p_G$.

