\begin{table}[t]
    \centering
    \caption{Average \gap and time (seconds) per iteration. We run 100  repeats for each method and each function with $2d$ random initial observations of the function. 
    Bold: best, blue: not significantly worse than the best under paired one-sided sign rank test with $\alpha=0.05$.}
    \label{table:synthetic_results}
    \vspace{1ex}
    \input{tables/synthetic_functions_gap_signrank_test}
\end{table}

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


We follow the experimental setting of \citep{jiang2019binoculars}, 
and test our algorithms using the same set of synthetic and real benchmark functions. Due to the space limit, we only present the results on the synthetic benchmarks here; more results are given in Appendix \ref{appd:realfunctions}. 
All algorithms are implemented in \botorch \citep{balandat2019botorch}, and we use a \gp with a constant mean and a Mat\'ern $\nicefrac{5}{2}$ \acro{ARD} kernel for \bo. \gp hyperparameters are re-estimated by maximizing the evidence after each iteration. 
For each experiment, we start with $2d$ random observations, and perform $20d$ iterations of \bo; 100 experiments are repeated for each function and each method. 
We measure performance with \gap $=(y_i - y_0)/(y^* - y_0)$. 
All experiments are run on \acro{CPU} Linux machines; each experiment only uses one core.  


\cite{jiang2019binoculars} used nine ``hard'' synthetic functions, motivated by the argument that the advantage of nonmyopic policies are more evident when the function is hard to optimize.

We follow their work and use the same nine functions. 


\cite{jiang2019binoculars} thoroughly compared \binoc with some well known nonmyopic baselines such as rollout and \glasses and demonstrate superior results, so we will focus on comparing with \ei, \binoc and the ``envelope two-step'' (\ets) method \citep{wu2019practical}. We choose the best reported variant 12.\ei.s for \binoc on these functions \citep{jiang2019binoculars},  i.e., first compute an optimal batch of 12 points (maximize \qei), then sample a point from it weighted by the individual \ei values. 


All details can be found in our attached code. 

We use the following nomenclature: 
``$k$-step'' means $k$-step lookahead ($k=2,3,4$) with number of \gh samples $m_1=10, m_2=5, m_3=3$. These numbers are heuristically chosen to favor more
accuracy in earlier stages.


``$k$-path'' is the multi-step path variant that uses only one sample for each stage. 
``$k$-\eno'' is \eno using non-adaptive approximation of the future $k-1$ steps with a $q$-\ei batch with $q=k-1$.


The average \gap at terminal and average time (in seconds) per iteration for all methods are presented in Table \ref{table:synthetic_results}.
The average over all functions are also plotted in Figure \ref{fig:synthetic_gap_time}. 
Some entries are omitted from the table and plots for better presentation. We summarize some main takeaways below.

\begin{figure*}
	\centering
	\begin{subfigure}[b]{.45\textwidth}
		\centering
		\includegraphics[width=\linewidth]{figures/synthetic_gap_time_scatter_only_warmstart.pdf}
		\subcaption{}
		\label{fig:synthetic_gap_time}
	\end{subfigure}
	\hspace{0.5cm}
	\begin{subfigure}[b]{.45\textwidth}
		\centering
		\includegraphics[width=\linewidth]{figures/synthetic_iter_aggregated.pdf}
		\subcaption{}
		\label{fig:nonmyopic_behavior}
	\end{subfigure}
	\caption{(a) Aggregated \gap with error bars vs. time per iteration, averaged over the nine synthetic functions by 100 repeats.
		(b) Aggregated optimization trace: \gap versus number of iterations, normalized into 0-1.}
\end{figure*}


\textbf{Baselines.} First, we see from Table \ref{table:synthetic_results} \ets outperforms \ei on $\nicefrac{5}{9}$ of the functions, but on average is worse than \ei, especially on the two shekel functions, and the average time/iter is over 30min. 
Our results for 12.\ei.s and \ei closely match those reported in \citep{jiang2019binoculars}. 

\textbf{One-Shot Multi-Step.} We see from Figure \ref{fig:synthetic_gap_time} 


\emph{2,3,4-step outperform all baselines by a large margin}.


We also see diminishing returns with increasing horizon. 
In particular, performance appears to stop improving significantly beyond 3-step.    
It is not clear at this point whether this is because we are not optimizing the increasingly complex multi-step objective well enough or 


if additional lookahead means increasing reliance on the model being accurate, which is often not the case in practice \citep{yue2019why}. 

\textbf{One-Shot Pseudo Multi-Step.}
Note that the average time/iteration grows exponentially when looking more steps ahead if we use multiple fantasy samples for each stage.

In Figure \ref{fig:synthetic_gap_time}, we see 2- and 4-path produce similar results in significantly less time, {suggesting that a noisy version of the multi-step tree is a reasonable alternative.}

The average \gap and time for 2,3,4-path are: \gap= 0.747, 0.750, 0.761, time = 4.87s, 10.4s, 17.5s. We also run 12-\eno. $k=12$ is chosen to match with 12.\ei.s. The \gap and time/iteration are very close to 4-path.
More interestingly, it exhibits more evident \emph{nonmyopic behavior} than other nonmyopic methods shown in Figure \ref{fig:nonmyopic_behavior}: 
12-\eno first underperforms, but catches up at some point, and finally outperforms, the less myopic methods. 
Similar behavior has been consistently observed in efficient nonmyopic active search \citep{jiang2017efficient, jiang2018efficient}.
All plots for the individual functions are given in Appendix \ref{appd:syntheticfunctions}. {Note that these pseudo multi-step methods have objectives that are much lower dimensional and hence easier to optimize --- this may partly contribute to their effectiveness.}
{"config": "arxiv", "file": "2006.15779/content/experiments.tex"}