\section{Introduction}\label{sec:introduction}
The combination of online Monte Carlo Tree Search (MCTS) \cite{browne2012survey} in self-play and offline neural network training has been widely applied as a deep reinforcement learning technique, in particular for solving game-related problems by means of the AlphaGo series programs~\cite{silver2016mastering,silver2017mastering,silver2018general}. The approach of this paradigm is to use game playing records from self-play by MCTS as training examples to train the neural network, whereas this trained neural network is used to inform the MCTS value and policy. Note that in contrast to AlphaGo Zero or AlphaZero,\footnote{AlphaZero is a general framework based on AlphaGo Zero for different games} the original AlphaGo also uses large amounts of expert data to train the neural network and a fast rollout policy together with the policy provided by neural network to guide the MCTS search.

However, although the transition from a combination of using expert data and self-play (AlphaGo) to only using self-play (AlphaGo Zero and AlphaZero) appears to have only positive results, it does raise some questions.

The first question is: `should all human expert data be abandoned?' In other games we have  seen that human knowledge is essential for mastering complex games, such as StarCraft~\cite{vinyals2019grandmaster}. Then when should expert data be taken into consideration while training neural networks?

The second question is: `should the fast rollout policy be abandoned?' Recently, \cite{wang2020warm} have proposed to use warm-start search enhancements~\textbf{at the start phase} in AlphaZero-like self-play, which improves performance in 3 small board games. Instead of only using the neural network for value and policy, in the first few iterations, classic rollout can be used (or RAVE, or a combination, or a combination with the neural network). This can improve  training especially at the start phase of self-play training.

In fact, the essence of the warm-start search enhancement is to re-generate expert knowledge in the start phase of self-play training, to reduce the cold-start problem of playing against untrained agents. The method uses rollout (which can be seen as experts) instead of a randomly initialized neural network, up until a number of $I^\prime$ iterations, when it switches to the regular value network.
In their experiments, the $I^\prime$ was fixed at 5.
Obviously, a fixed $I^\prime$ may not be optimal. Therefore, in this work, we propose an adaptive switch method. The method uses an \textbf{arena} in the self-play stage~(see Algorithm~\ref{alg:adaptivea0g}), where the search enhancement and the default MCTS are matched, to judge whether to switch or not. With this mechanism, we can dynamically switch off the enhancement if it is no longer better than the default MCTS player, as the neural network is being trained.

Our main contributions can be summarized as follows:

\begin{enumerate}
\item Warm-start method improves the Elo of AlphaZero-like self-play in small games, but it
 introduces a new hyper-parameter. Adaptive warm-start further improves performance and removes the hyper-parameter.
\item For deep games (with a small branching factor) warm-start works better than for shallow games. This indicates that the effectiveness of warm-start method may increase for larger games.

\end{enumerate}

The rest of paper is designed as follows.
An overview of the most relevant literature is given in Sect.\,\ref{sec:relatedwork}. Before proposing our adaptive switch method in Sect.\,\ref{sec:adaptivealphazero}, we describe the warm-start AlphaZero-like self-play algorithm in Sect.\,\ref{sec:warmalphazero}. Thereafter, we set up the experiments in Sect.\,\ref{sec:setup} and present their results in Sect.\,\ref{sec:results}. Finally, we conclude our paper and discuss future work.

\section{Related Work}\label{sec:relatedwork}

There are a lot of early successful works in reinforcement learning~\cite{sutton2018reinforcement}, e.g.  using temporal difference learning with a neural network to play backgammon \cite{tesauro1995temporal}. MCTS has also been well studied, and many variants/enhancements were designed to solve problems in the domain of sequential decisions, especially on games. For example, enhancements such as Rapid Action Value Estimate~(RAVE) and All Moves as First~(AMAF) have been conceived to improve MCTS~\cite{gelly2007combining,gelly2011monte}.
The AlphaGo series algorithms replace the table based model with a deep neural network based model, where the neural network has a policy head~(for evaluating of a state) and a value head~(for learning a best action)~\cite{wang2019alternative}, enabled by the GPU hardware development. Thereafter, the structure that combines MCTS with neural network training has become a typical approach for reinforcement learning tasks and many successful applications~\cite{segler2018planning,wang2020tackling} of this kind model-based deep reinforcement learning~\cite{schmidhuber2015deep}. Comparing AlphaGo with AlphaGo Zero and AlphaZero, the latter did not use any expert data to train the neural network, and abandoned the fast rollout policy for improving the MCTS on the trained neural network. Therefore, all training data is generated purely by self-play, which is also a very important feature of reinforcement learning. We base our work on an open reimplementation of AlphaZero, AlphaZero General~\cite{surag2018}.

There are many interesting works on self-play in reinforcement learning ~\cite{tesauro1995temporal,runarsson2005coevolution,plaat2020learning}. Temporal difference learning for acquiring position evaluation in small board Go with co-evolution has been compared to self-play~\cite{runarsson2005coevolution}. These works demonstrated the impressive results for self-play and emphasized its importance.

Within a general game playing framework, in order to improve training examples efficiency,~\cite{wang2018assessing} assessed the potential of classical Q-learning by introducing Monte Carlo Search enhancements. In an AlphaZero-like self-play framework,~\cite{wu2019accelerating} used domain-specific features and optimizations, starting from random initialization and no preexisting data, to accelerate the training.

However, AlphaStar, the acclaimed algorithm for beating human professionals at StarCraft \cite{vinyals2019grandmaster}, went back to utilizing human expert data, thereby suggesting that this is still an option at the start phase of training. Apart from this, there are few studies on applying MCTS enhancements in AlphaZero-like self-play.
Only \cite{wang2020warm}, which proposed a warm-start search enhancement method, pointed out the promising potential of utilizing MCTS enhancements~(like a rollout policy) to re-generate expert data at the start phase of training. Our approach  differs from AlphaStar, as we generate expert data using MCTS enhancements other than collecting it from humans; further, compared to the static warm-start of \cite{wang2020warm}, we propose an adaptive method to control the iteration length of using such enhancements instead of a fixed $I^\prime$.

\section{Warm-Start AlphaZero Self-play}\label{sec:warmalphazero}
We will now introduce the warm-start enhancement method.
\subsection{The Algorithm Framework}\label{a0gintroduction}

Based on~\cite{silver2018general,wang2019alternative,wang2020warm}, the core of AlphaZero-like self-play~(see Algorithm~\ref{alg:a0gwarm}) is an iterative loop which consists of three different stages within the single iteration as follows:
\begin{enumerate}
    \item \textbf{self-play}: The first stage is  playing several games against with itself to generate training examples.
    \item \textbf{neural network training}: The second stage is feeding the neural network with training examples~(generated in the first stage) to train a new model.
    \item \textbf{arena comparison}: The last stage is employing a tournament to compare the newly trained model and the old model to decide whether to update or not.
\end{enumerate}

The detail description of these 3 stages can be found in~\cite{wang2020warm}. Note that in the Algorithm~\ref{alg:a0gwarm}, line~\ref{linewithorwithoutenhancement}, a fixed $I^\prime$ is employed to control whether to use neural network  MCTS or MCTS enhancements, the $I^\prime$ should be set as relatively smaller than $I$, which is known as warm-start search. The MCTS algorithm and MCTS enhancements will be introduced in next subsections.

\begin{algorithm}[bth!]
\caption{Warm-start AlphaZero-like Self-play Algorithm}
\label{alg:a0gwarm}
\begin{algorithmic}[1]
\footnotesize
\State Randomly initialize $f_\theta$, assign retrain buffer $D$
\For{iteration=1, $\dots$,$I^\prime$, $\dots$, $I$}
\For{episode=1,$\dots$, $E$}\Comment{self-play}
\For{t=1, $\dots$, $T^\prime$, $\dots$, $T$}
\If{$I \leq I'$} $\pi_{t} \leftarrow$ \textbf{MCTS Enhancement}\label{linewithorwithoutenhancement}
\Else{} $\pi_{t} \leftarrow$ \textbf{default MCTS}
\EndIf
\If{$t \leq T'$} $a_t=$ randomly select on $\pi_t$
\Else{} $a_t = \arg\max_a(\pi_t)$
\EndIf
\State executeAction($s_t$, $a_t$)
\EndFor
\State $D \leftarrow (s_t,\pi_t,z_t)$ with  outcome $z_{t\in [1,T]}$
\EndFor
\State Sample  minibatch~($s_j$, $\pi_j$, $z_j$) from $D$ \Comment{training}
\State Train $f_{\theta^\prime}\leftarrow f_\theta$

\State $f_\theta=f_{\theta^\prime}$ if $f_{\theta^\prime}$ is better, using \textbf{default MCTS}\Comment{arena}
\EndFor
\State \Return $f_\theta$;
\end{algorithmic}
\end{algorithm}

\subsection{MCTS}\label{subsec:mctsnnt}
Classical MCTS has shown successful performance to solve complex games, by taking random samples in the search space to evaluate the state value. Basically, the classical MCTS algorithm can be divided into 4 stages, which are known as \textit{selection}, \textit{expansion}, \textit{rollout} and \textit{backpropagate}~\cite{browne2012survey}. However, for the default MCTS in AlphaZero-like self-play~(eg. our Baseline), the neural network directly informs the MCTS state policy and value to guide the search instead of running a rollout.

\subsection{MCTS enhancements}\label{subsec:mctsenhancements}
In this paper, we adopt the same two individual enhancements and three combinations to improve neural network training as were used by~\cite{wang2020warm}.

\noindent \textbf{Rollout} is running a classic MCTS random rollout to get a value that provides more meaningful information than a value from random initialized neural network.

\noindent \textbf{RAVE} is a well-studied enhancement to cope with the cold-start of MCTS in games like Go~\cite{gelly2007combining}, where the playout-sequence can be transposed. The core idea of RAVE is using AMAF to update the state visit count $N_{rave}$ and Q-value $Q_{rave}$, which are written as: $N_{rave}(s_{t_1},a_{t_2})\leftarrow N_{rave}(s_{t_1},a_{t_2})+1$, $Q_{rave}(s_{t_1},a_{t_2})\leftarrow\frac{N_{rave}(s_{t_1},a_{t_2})*Q_{rave}(s_{t_1},a_{t_2})+v}{N_{rave}(s_{t_1},a_{t_2})+1}$, where $s_{t_1}\in VisitedPath$, and $a_{t_2}\in A(s_{t_1})$, and for $\forall t < t_2, a_t\neq a_{t_2}$. The P-UCT of RAVE is calculated as follows:

\begin{equation}\label{equationUCTrave}
 UCT_{rave}(s,a)=(1-\beta)* U(s,a) + \beta*U_{rave}(s,a)
 \end{equation}
 where
 \begin{equation}
 U_{rave}(s,a) = Q_{rave}(s,a) + c*P(s,a)\frac{\sqrt{N_{rave}(s,\cdot)}}{N_{rave}(s,a)+1}
 \end{equation}
 and
 \begin{equation}
 \beta=\sqrt{\frac{equivalence}{3*N(s,\cdot)+equivalence}}
 \end{equation}
 The value of equivalence is usually set to the number of MCTS simulations~(i.e $m$=100 in our experiments).

\noindent \textbf{RoRa} is the combination which simply adds the random rollout to enhance RAVE.

\noindent \textbf{WRo} introduces a weighted sum of rollout value and the neural network value as the return value to guide MCTS. In our experiments, $v(s)$ is computed as follows:
\begin{equation}
v(s)=(1-weight)*v_{network}+ weight*v_{rollout}
\end{equation}

\noindent \textbf{WRoRa} also employs a weighted sum to combine the value from the neural network and the value of RoRa. The $v(s)$ for MCTS search in WRoRa is computed as follows:
\begin{equation}
v(s)=(1-weight)*v_{network}+ weight*v_{rora}
\end{equation}

Different from~\cite{wang2020warm}, since there is no pre-determined  $I^\prime$, in our work, $weight$ is simply calculated as $1/i, i\in [1,I]$, where $i$ is the current iteration number.

\section{Adaptive Warm-Start Switch Method}\label{sec:adaptivealphazero}

The fixed $I^\prime$  to control the length of using warm-start search enhancements as suggested by \cite{wang2020warm} works, but seems to require different parameter values for different games. In consequence, a costly tuning process would be necessary for each game. Thus, an adaptive method would have multiple advantages.

We notice that the core of the warm-start method is re-generating expert data to train the neural network at the start phase of self-training to avoid learning from weak (random or near random) self-play. We suggest to stop the warm-start when the neural network is on average playing stronger  than the enhancements. Therefore, in the self-play, we employ a tournament to compare the standard AlphaZero-like self-play model~(Baseline) and the enhancements~(see Algorithm~\ref{alg:adaptivea0g}). The switch occurs once the Baseline MCTS wins more than 50\%. In order to avoid spending too much time on this, these arena game records will directly be used as training examples, indicating that the training data is played by the enhancements and the Baseline. This scheme enables to switch at individual points in time for different games and even different training runs.

\begin{algorithm}[bth!]
\caption{Adaptive Warm-Start Switch Algorithm}
\label{alg:adaptivea0g}
\begin{algorithmic}[1]
\footnotesize
\State Initialize $f_\theta$ with random weights; Initialize retrain buffer $D$, Switch$\leftarrow$False, $r_{mcts} \leftarrow 0$
\For{iteration=1, $\dots$, $I$}
\Comment no $I^\prime$
\If{not Switch}\Comment{not switch}
\For{episode=1,$\dots$, $E$}\Comment{arena with enhancements}
\For{t=1, $\dots$, $T^\prime$, $\dots$, $T$}
\If{$episode \leq E/2$}
\If{t is odd} $\pi_{t} \leftarrow$
\textbf{MCTS Enhancement}
\Else{}  $\pi_{t} \leftarrow$  \textbf{default MCTS}
\EndIf
\Else{}
\If{t is odd}
$\pi_{t} \leftarrow$ \textbf{default MCTS}
\Else{} $\pi_{t} \leftarrow$ \textbf{MCTS Enhancement}
\EndIf
\EndIf
\If{$t \leq T'$} $a_t=$ randomly select on $\pi_t$
\Else{} $a_t = \arg\max_a(\pi_t)$
\EndIf

\State executeAction($s_t$, $a_t$)
\EndFor
\State $D \leftarrow (s_t,\pi_t,z_t)$ with  outcome $z_{t\in [1,T]}$
\State $r_{mcts}$+= reward of \textbf{default MCTS} in this episode
\EndFor
\Else\Comment{switch}
\For{episode=1,$\dots$, $E$}\Comment{purely self-play}
\For{t=1, $\dots$, $T^\prime$, $\dots$, $T$}
\State$\pi_{t} \leftarrow$
\textbf{default MCTS}
\If{$t \leq T'$} $a_t=$ randomly select on $\pi_t$
\Else{} $a_t = \arg\max_a(\pi_t)$
\EndIf
\State executeAction($s_t$, $a_t$)

\EndFor
\State $D \leftarrow (s_t,\pi_t,z_t)$ with  outcome $z_{t\in [1,T]}$
\EndFor
\EndIf
\State Set Switch$\leftarrow$True if $r_{mcts}>$0, and set $r_{mcts} \leftarrow 0$
\State Sample  minibatch~($s_j$, $\pi_j$, $z_j$) from $D$ \Comment{training}
\State Train $f_{\theta^\prime}\leftarrow f_\theta$

\State $f_\theta=f_{\theta^\prime}$ if $f_{\theta^\prime}$ is better, using \textbf{default MCTS} \Comment{arena}
\EndFor
\State \Return $f_\theta$;
\end{algorithmic}
\end{algorithm}

\section{Experimental Setup}\label{sec:setup}

Since~\cite{wang2020warm} only studied the winrate of single rollout and RAVE against a  random player, this can be used as a test to check whether rollout and RAVE work. However, it does not reveal any information about relative playing strength, which is necessary to explain how good training examples provided by MCTS enhancements actually are. Therefore, at first we let all 5 enhancements and the baseline MCTS play 100 repetitions with each other on the same 3 games~(6$\times$6 Connect Four, Othello and Gobang, game description can be found in~\cite{wang2020warm}) in order to investigate the relative playing strength of each pair.

In the second experiment, we tune the fixed $I^\prime$, where $I^\prime\in \{1,3,5,7,9\}$, for different search enhancements, based on Algorithm~\ref{alg:a0gwarm} to play 6$\times$6 Connect Four.

In our last experiment, we use new adaptive switch method~Algorithm~\ref{alg:adaptivea0g} to play 6$\times$6 Othello, Connect Four and Gobang. We set parameters values according to Table~\ref{defaulttab}. The parameter choices are based on~\cite{wang2020analysis}.

Our experiments are run on a high-performance computing (HPC) server, which is a  cluster consisting of 20 CPU nodes (40 TFlops) and 10 GPU nodes (40 GPU, 20 TFlops CPU + 536 TFlops GPU).  We use small versions of games (6$\times$6) in order to perform a medium number of repetitions. In the following, our figures show error bars of 8 runs, of 100 iterations of self-play. Each single run is deployed in a single GPU which takes several days for different games.

\begin{table}[bht!]
\centering\hspace*{-2.3em}
\begin{tabular}{lll}
\hline
Parameter& Description & Value\\
\hline
\emph{I}	&number of iteration		&100 \\
\emph{rs}	& number of retrain iteration		&20\\

\emph{ep}	& number of epoch	&10	\\

\emph{E}    &number of episode		&50\\
\emph{bs}	& batch size	&64\\

\emph{T'}	&step threshold		&15\\
\emph{lr}	& learning rate	&	0.005\\

\emph{m}	&MCTS simulation times	&100\\
\emph{d}    & dropout probability &0.3\\

\emph{c}    &weight in UCT		&1.0\\
\emph{n}   & number of comparison games	&40\\

\emph{u}	& update threshold		&0.6\\
\hline
\end{tabular}
\caption{Default Parameter Setting}\label{defaulttab}
\end{table}

\section{Results}\label{sec:results}
We list results for a tournament of Baseline and enhancements~(Table~\ref{comparisontable}). Digging deeper, we also report the effect of the hyper-parameter $I'$ (Fig~\ref{fig:subfigdifferentheuristics}). And results for the adaptive warm-start switch   are shown in Table~\ref{tab:Ifordifferentgames}, Fig~\ref{fig:balanceofothello} and Fig~\ref{fig:fixedvsadapt}.

\subsection{MCTS vs MCTS Enhancements}

Here, we compare the Baseline player (the neural network is initialized randomly which can be regarded as an arena in the first iteration self-play) to the other 5 MCTS enhancements players on 3 different games.
Each pair performs 100 repetitions.  In Table~\ref{comparisontable}, we can see that for Connect Four, the highest winrate is achieved by WRoRa, the lowest by Rave. Except Rave, others are all higher than 50\%, showing that the enhancements~(except Rave) are better than the untrained Baseline. In Gobang, it is similar, Rave is the lowest, RoRa is the highest. But the winrates are relatively lower than that in other 2 games. It is interesting that in Othello, all winrates are relatively the highest compared to the 2 other games~(nearly 100\%), although Rave still achieves the lowest winrate which is higher than 50\%.

One reason that enhancements work best in Othello is that the Othello game tree is the longest and narrowest (low branching factor). Enhancements like Rollout can provide relatively accurate estimations for these trees. In contrast, Gobang has the shortest game length and the most legal action options. Enhancements like Rollout do not contribute much to the search in short but wide search tree with limited MCTS simulation. As in shorter games it is more likely to reach a terminal state, both Baseline and enhancements get the true result. Therefore, in comparison to MCTS, enhancements like Rollout work better while it does not terminate too fast. Rave is filling more state action pairs based on information from the neural network, its weaknesses at the beginning are more emphasized. After some iterations of training, the neural network becomes smarter, and Rave can therefore enhance the performance as shown in~\cite{wang2020warm}.

\begin{table}[tbh!]
\centering
\caption{Results of comparing default MCTS with Rollout, Rave, RoRa, WRo and WRoRa, respectively on the three games with random neural network, weight as 1/2, $T^\prime$=0, win rates in percent (row vs column), 100 repetitions each. }\label{comparisontable}
\begin{tabular}{llll}
\hline
&\multicolumn{3}{c}{Default MCTS} \\
\hline
&ConnectFour&Othello&Gobang\\
\hline
Rollout 	&64  &  93 &65	 \\

Rave &27.5	 &53& 43\\

RoRa &76	  &98  &70\\
WRo &82	  &96& 57\\
WRoRa&	82.5  & 99& 62\\
\hline
\end{tabular}
\end{table}

\subsection{Fixed $I^\prime$ Tuning}
Taking Connect Four as an example, in this experiment we search for an optimal fixed $I^\prime$ value, utilizing the warm-start search method proposed in~\cite{wang2020warm}. We set $I^\prime$ as 1, 3, 5, 7, 9 respectively~(the value should be relatively small since the enhancement is only expected to be used at the start phase of training). The Elo ratings of each enhancements using different $I^\prime$ are presented in Fig~\ref{fig:subfigdifferentheuristics}. The Elo ratings are calculated based on the tournament results using a Bayesian Elo computation system~\cite{coulom2008whole}, same for Fig~\ref{fig:fixedvsadapt}.  We can see that for Rave and WRoRa, it turns out that $I^\prime=7$ is the optimal value for fixed $I^\prime$ warm-start framework, for others, it is still unclear which value is the best, indicating that the tuning is inefficient and costly.

\begin{figure}[!tbh]
\centering
\hspace*{-1.5em}
\subfigure[Rollout]{\label{fig:subfig:Rollout}
\includegraphics[width=0.53\columnwidth]{mctsrollout_arena_connect4_final.pdf}}
\hspace*{-1.5em}
\subfigure[Rave]{\label{fig:subfig:Rave}
\includegraphics[width=0.53\columnwidth]{mctsrave_arena_connect4_final.pdf}}
\hspace*{-1.5em}
\subfigure[RoRa]{\label{fig:subfig:RoRa}
\includegraphics[width=0.53\columnwidth]{mctsraverollout_arena_connect4_final.pdf}}
\hspace*{-1.5em}
\subfigure[WRo]{\label{fig:subfig:WRo}
\includegraphics[width=0.53\columnwidth]{weightmctsrollout_arena_connect4_final.pdf}}
\hspace*{-1.5em}
\subfigure[WRoRa]{\label{fig:subfig:WRoRa}
\includegraphics[width=0.53\columnwidth]{weightmctsraverollout_arena_connect4_final.pdf}}
\caption{Elo ratings for different warm-start phase iterations with different search enhancement on 6$\times$6 Connect Four}
\label{fig:subfigdifferentheuristics}
\end{figure}

\subsection{Adaptive Warm-Start Switch}

In this final experiment, we apply the newly suggested adaptive switch warm-start search enhancement method and compare it to the fixed $I^\prime$. We are especially interested in the averages and variances of the switching times that result from adaptive switching.

 We train models with the parameters in Table~\ref{defaulttab} and then let them compete against each other in different games. In addition, we record the specific iteration number where the switch occurs for every training run and the corresponding self-play arena rewards of MCTS before this iteration. A statistic of the iteration number for 3 games is  shown in Table~\ref{tab:Ifordifferentgames}.

\begin{table}[!bth]
\centering
\caption{Switching iterations for training on different games with different enhancements over 8 repetitions~(average iteration number $\pm$ standard deviation)}
\begin{tabular}{llll}
\hline
& Connect Four&Othello &Gobang \\
\hline
Rollout&6.625$\pm$ 3.039&5.5$\pm$ 1.732&1.375$\pm$0.484\\
Rave&2.375$\pm$1.218&3.125 $\pm$2.667&1.125$\pm$0.331\\
RoRa&7.75 $\pm$4.74&5.125 $\pm$1.364&1.125$\pm$0.331\\
WRo&4.25$\pm$1.561&4.375$\pm$1.654&1.125$\pm$0.331\\
WRoRa&4.375$\pm$1.576&4.0$\pm$1.0&1.25$\pm$0.433\\
\hline
\end{tabular}
\label{tab:Ifordifferentgames}
\end{table}

The table shows that, generally, the iteration number is relatively small compared to the total length of the training (100 iterations), and in these small games the neural network is quickly getting stronger. Besides, not only for different games, the switch iteration is different, but also for different training runs on the same game, the switch iteration also varies. This is because for different training runs, the neural network training progresses differently (we already start from different random initializations). Therefore, a fixed $I^\prime$ can not be used for each specific training. Note that for Gobang, a game with a large branching factor, with the default setting, it always switches at the first iteration. Therefore, we also test with larger $m = 200$, thereby providing more time to the MCTS. With this change, there are several runs keeping the enhancements~see Table~\ref{tab:Ifordifferentgames}, but it still shows a small influence on this game.

In addition, we show the arena results~(wins of default MCTS minus wins of enhancement) in each training iteration before switch happens in each run over 8 repetitions on Othello as an example in Fig~\ref{fig:balanceofothello}. In most curves, we can see improving reward balances achieved by default MCTS since it is getting stronger.

\begin{figure}[!b]
\centering
\hspace*{-1.5em}
\subfigure[Rollout]{\label{fig:subfig:balancerolloutothello}
\includegraphics[width=0.53\columnwidth]{66othello_noiprime_Rollout_balance_8runs.pdf}}
\hspace*{-1.5em}
\subfigure[Rave]{\label{fig:subfig:balanceraveothello}
\includegraphics[width=0.53\columnwidth]{66othello_noiprime_Rave_balance_8runs.pdf}}
\hspace*{-1.5em}
\subfigure[RoRa]{\label{fig:subfig:balanceroraothello}
\includegraphics[width=0.53\columnwidth]{66othello_noiprime_RoRa_balance_8runs.pdf}}
\hspace*{-1.5em}
\subfigure[WRo]{\label{fig:subfig:balancewroothello}
\includegraphics[width=0.53\columnwidth]{66othello_noiprime_WRo_balance_8runs.pdf}}
\hspace*{-1.5em}
\subfigure[WRoRa]{\label{fig:subfig:balancewroraothello}
\includegraphics[width=0.53\columnwidth]{66othello_noiprime_WRoRa_balance_8runs.pdf}}

\caption{Reward balances of default MCTS while competing with different enhancements in self-play arena for 6$\times$6 Othello. Exceeding 0 means default MCTS defeats the enhancement, switch occurs.}
\label{fig:balanceofothello}
\end{figure}

\begin{figure*}[t!]
\centering
\subfigure[Connect Four]{\label{fig:adaptconnect4}
\includegraphics[width=0.8\columnwidth]{fixedvsnoiprime_arena_connect4_final.pdf}}
\subfigure[Othello]{\label{fig:adaptothello}
\includegraphics[width=0.8\columnwidth]{fixedvsnoiprime_arena_othello_final.pdf}}
\caption{Comparison of adaptive switch method versus fixed $I^\prime$ based on a full tournament for 6$\times$6 Connect Four and Othello}
\label{fig:fixedvsadapt}
\end{figure*}

More importantly, we collect all trained models based on our adaptive method, and let them compete with the models trained using fixed $I^\prime=5$ in a full round-robin tournament where each 2 players play 20 games.

From Fig~\ref{fig:fixedvsadapt}, we see that, generally, on both Connect Four and Othello, all fixed $I^\prime$ achieve higher Elo ratings than the Baseline, which was also reported in~\cite{wang2020warm}). And all adaptive switch models also perform better than the Baseline. Besides, for each enhancement, it is important that the Elo ratings of the adaptive switch models are higher than for the fixed $I^\prime$ method, which suggests that our adaptive switch method leads to better performance than the fixed $I^\prime$ method when controlling the warm-start iteration length. Specifically, we find that for Connect Four, WRo and RoRa achieve the higher Elo Ratings~(see Fig~\ref{fig:adaptconnect4}) and  for Othello, WRoRa performs best~(see Fig~\ref{fig:adaptothello}), which reproduces the consistent conclusion~(at least one combination enhancement performs better in different games) as ~\cite{wang2020warm}).

In addition, for Connect Four, comparing the tuning results in Fig~\ref{fig:subfigdifferentheuristics} and the \emph{switch iterations} by our method in Table~\ref{tab:Ifordifferentgames}, we find that our method generally needs a shorter warm-start phase than employing a fixed $I^\prime$. The reason could be that in our method, there are always 2 different players playing the game, and they provide more diverse training data than a pure self-play player. In consequence, the  neural network also improves more quickly, which is highly desired.

Note that while we use the default parameter setting for training in the Gobang game, the \emph{switch} occurs at the first iteration. And even though we enlarge the simulation times for MCTS, only a few training runs shortly keep using the enhancements. We therefore presume that it is meaningless to further perform the tournament comparison for Gobang.

\section{Discussion and Conclusion}\label{sec:conclusion}

Since AlphaGo Zero' results, self-play has become a default approach for generating  training data tabula rasa, disregarding other information for training. However, if there is a way to obtain better training examples from the start, why not use them,  as has been done recently in StarCraft~(see DeepMind's AlphaStar~\cite{vinyals2019grandmaster}). In addition~\cite{wang2020warm} investigate the possibility of utilizing MCTS enhancements to improve AlphaZero-like self-play. They embed Rollout, RAVE and combinations as enhancements at the start period of iterative self-play training and tested this on small board games. Since the neural network and the MCTS statistics are initialized to random weights and zero, self-play suffers from a cold-start problem, and starting from scratch can lead to unstable learning at the start of the training. These problems can be cured by feeding human expert data or running MCTS enhancements or similar methods in order to generate expert data for training the neural network before switching to pure self-play.   (Not unlike RAVE warm-starts the winrate statistics of the original MCTS in 2007.)

Confirming~\cite{wang2020warm}, we find that finding an optimal value of fixed $I^\prime$ is difficult, therefore, we propose an adaptive method for deciding when to switch. We also use Rollout, RAVE, and combinations with network values to quickly improve MCTS tree statistics~(using RAVE) with meaningful information~(using Rollout) before we switch to Baseline-like self-play training. We employed the same games, namely the 6x6 versions of Gobang, Connect Four, and Othello.
In these experiments, we find that, for different games, and even different training runs for the same game, the new adaptive method generally switches at different iterations. This indicates the noise in the neural network training progress for different runs.
After 100 self-play iterations, we still see the effects of the warm-start enhancements as playing strength has improved in many cases, and for all enhancements, our method performs better than the method proposed in~\cite{wang2020warm} with $I^\prime$  set to 5. In addition, some conclusions are consistent to~\cite{wang2020warm}, for example, there is also at least one combination that performs better.

The new adaptive method works especially well on Othello and Connect Four, "deep" games with a moderate branching factor, and less well on Gobang, which has a larger branching factor. In the  self-play arena, the default MCTS is already quite strong, and for games with a short and wide episode, the MCTS enhancements do not benefit much.  Short game lengths reach terminal states early, and  MCTS can use the true reward information more often, resulting in a higher chance of winning.
Since, Rollout still needs to simulate, with a limited simulation count it is likely to not choose a winning terminal state but a state that has the same average value as the terminal state. In this situation, in a short game episodes, MCTS works better than the enhancement with $T^\prime$=15. With ongoing training of the neural network, both players become stronger, and as the game length  becomes longer,  $I^\prime=5$ works better than the the Baseline.

Our experiments are with small games. Adaptive warm-start works best in deeper games, suggesting a larger benefit  for bigger games with deeper lines. Future work includes larger games with deeper lines, and
using   different but stronger enhancements to generate training examples.

\bibliographystyle{named}


\section{Introduction}
Recently, Task-Oriented Dialog (TOD) systems \cite{mehri2019structured,zhang2020probabilistic,zhang2020task,le2020uniconv,hosseini2020simple,peng2020soloist,li2021multi} have achieved promising performance on accomplishing user goals.
Most systems typically query \textit{structured knowledge} such as tables and databases based on the user goals, and use the query results to guide the generation of system responses, as shown in the first dialog turn in Fig.~\ref{sskm}.

However, real-world task-oriented conversations often step into dialog turns which are grounded on \textit{unstructured knowledge} \cite{feng2020doc2dial}, such as passages and documents.
For example, as the second dialog turn in Fig.~\ref{sskm} shows, the user asks about customers' favorite food at \textit{Pizza Hut}, which is grounded on the customer reviews of this restaurant.
Current TOD systems fall short of handling such dialog turns since they cannot utilize relevant unstructured knowledge. This deficiency may interrupt the dialog process, causing difficulties in tracking user goals and generating system responses.

In this work, we consider incorporating more various forms of domain knowledge into the TOD systems.
Therefore, we define a task of modeling TOD whose turns involve either structured or unstructured knowledge.
In turns involving structured knowledge, the system needs to track the user goals as triples and use them to perform database queries, whose results are used to generate the system response.
While in turns involving unstructured knowledge, the system manages a document base to retrieve relevant references for generating the response.

To address our defined task, we propose a task-oriented dialog system with \textbf{Hy}brid \textbf{Know}ledge management (\ourmodel).
This model extends the belief state to handle TODs grounded on hybrid knowledge, and further uses the extended belief state to perform both database query and document retrieval, whose outputs are thereby used to generate the final response.
We consider two implementations of our system, with different schemes of extended belief state decoding.
Both implementations are in an end-to-end multi-stage sequence-to-sequence (Seq2Seq) \cite{lei2018sequicity,liang2020moss,zhang2020probabilistic,zhang2020task} framework, where dialog modeling grounded on the two kinds of knowledge can be jointly optimized.

We evaluate our system on the modified version of MultiWOZ 2.1 \cite{kim2020beyond} dataset, where dialogs are grounded on hybrid knowledge. Experimental results show that \ourmodel outperforms existing TOD systems which do not leverage large pretrained language models, no matter whether they add extra unstructured knowledge management or not. It also has a higher accuracy in unstructured knowledge retrieval, compared to the pipeline knowledge management schemes.

Our contributions are summarized as below:
\begin{itemize}
    \item We formulate a task of modeling TOD grounded on both structured and unstructured knowledge, to incorporate more domain knowledge into the TOD systems.
    \item We propose a TOD system \ourmodel to address our proposed task. It extends the belief state to manage hybrid knowledge, and is the first end-to-end model to jointly optimize dialog modeling grounded on the two kinds of knowledge.
    \item Experimental results show that \ourmodel has strong performance in dialog modeling grounded on hybrid knowledge.\footnote{The code is available at \url{https://github.com/truthless11/HyKnow}}
\end{itemize}

\section{Related Work}
TOD systems usually use belief tracking, i.e. dialog state tracking (DST) to trace the user goals, i.e. \textit{belief states}, through multiple dialog turns \cite{williams2013dialog,henderson2014second}. The states are converted into a representation of constraints based on different schemes to query the databases \cite{el2017frames,budzianowski2018multiwoz,rastogi2020towards,zhu2020crosswoz}. The entry matching results are then used to generate the system response.

With the development of intelligent assistants, the system should have a good command of massive external knowledge to better accomplish complicated user goals and improve user satisfaction. To realize this, some researchers \cite{zhao2017generative,yu2017learning,akasaki2017chat} equip the system with chatting capability to address both task and non-task content in TODs. Other studies apply knowledge graph \cite{liao2019deep,yang2020graphdialog} or tables via SQL \cite{yu2019cosql} to enrich the knowledge of TOD systems. However, all these studies are still limited in dialog modeling grounded on structured knowledge.

There are a couple of studies to integrate unstructured knowledge into TOD modeling recently. \citet{kim2020beyond} introduce knowledge snippets to answer follow-up questions out of the coverage of databases. \citet{feng2020doc2dial} formulate document-grounded dialog for information seeking tasks. However, they only focus on dialog turns grounded on unstructured knowledge instead. In this paper, we aims to fill the gap of managing domain-specific knowledge with various sources and structures in traditional TOD systems.

\begin{figure*}[t]
\centering
\includegraphics[width=\textwidth]{hyknow.pdf}
\caption{Overview of \ourmodel. Solid arrows denote the input/output of the encoders or decoders. Dashed arrows denote the knowledge operations. $C_{t}$, $\textbf{m}_{t}$, $D_{t}$ and $R_{t}$ represent turn $t$'s dialog context, DB query result, relevant document and system response. $\widetilde{B}_{t}$ and $\textbf{h}_{enc}^{\widetilde{B}_{t}}$ denote the extended belief state and its hidden states at turn $t$. The decoding of $\widetilde{B}_{t}$ (orange dashed box) is implemented in two different ways: (a) using a single decoder to generate the whole state, and (b) using two decoders to generate the domain-slot-value (DSV) triples and the topic separately.}
\label{hyknow}
\end{figure*}

\section{Task Definition}
In this section, we introduce our formulation of modeling TOD grounded on hybrid knowledge.
In particular, we assume that each dialog turn in TOD is grounded on either structured or unstructured knowledge.
We formulate the modeling of the two kinds of dialog turns separately.

In turns that are grounded on structured knowledge, the system needs to track user goals, i.e. the belief state, as domain-slot-value triples, and then query a database (DB) to guide response generation.
Specifically, we denote the user utterance and the system response at turn $t$ as $U_{t}$ and $R_{t}$ respectively.
Given the dialog context $C_{t}=[U_{t-k},R_{t-k},...,U_{t}]$ and previous belief state $B_{t-1}$, the system needs to generate current belief state $B_{t}$, which is formulated as $B_{t}=f^{(s)}_{b}(C_{t},B_{t-1})$.
Then the system performs DB query based on $B_{t}$ to get the matching result $\textbf{m}_{t}$. In this paper, we follow \citet{budzianowski2018multiwoz} to represent $\textbf{m}_{t}$ as a vector indicating the number of matched entities and whether the booking is available or not.
Afterwards, the system generates the response $R_{t}$, formulated as $R_{t}=f^{(s)}_{r}(C_{t},B_{t},\textbf{m}_{t})$.

In turns that are grounded on unstructured knowledge, the system manages a document base to guide response generation, which contains lists of documents characterized by different domains and entities, as showed in Fig.~\ref{sskm}.
Specifically, given the dialog context $C_{t}$, the system first retrieves a relevant document $D_{t}$ in the document base, formulated as $D_{t}=f^{(u)}_{d}(C_{t})$.
Then the system generates the response $R_{t}$ based on $C_{t}$ and retrieved $D_{t}$, which is formulated as $R_{t}=f^{(u)}_{r}(C_{t},D_{t})$. Noting that the original belief state is not updated in the unstructured knowledge-grounded turns, namely $B_{t}=B_{t-1}$. However, in this paper, we introduce extra belief state extension to facilitate the document retrieval.

\section{Proposed Framework}
Fig.~\ref{hyknow} shows an overview of our proposed system \ourmodel with end-to-end sequence-to-sequence (Seq2Seq) implementations.
It addresses our proposed task in three steps.
First, it uses the \textbf{extended belief tracking} to track user goals through dialog turns that involve hybrid knowledge.
Secondly, it performs \textbf{hybrid knowledge operations} based on the extended belief state, to search structured and unstructured knowledge that is relevant to the user goals.
Finally, it uses the extended belief state and relevant
 knowledge to perform the \textbf{knowledge-grounded response generation}.

\subsection{Extended Belief Tracking}
\textbf{Belief State Extension.}
We define an extended belief state $\widetilde{B}_{t}$ which is applicable to track user goals in TODs that are grounded on both structured and unstructured knowledge.
Specifically, in turns that are grounded on structured knowledge, $\widetilde{B}_{t}$ is same as the original $B_{t}$, which describes user goals as domain-slot-value triples.
While in turns that are grounded on unstructured knowledge, $\widetilde{B}_{t}$ has an additional slot \textit{ruk} to indicate that current dialog turn \textbf{r}equires \textbf{u}nstructured \textbf{k}nowledge. The prefix and value of the slot \textit{ruk} represent the involved domain and entity, e.g. \textit{restaurant}-\textit{ruk}: \textit{Pizza Hut} colored in red in Fig.~\ref{sskm}.
We denote the combination of original and newly introduced domain-slot-value triples as $DSV_{t}$.
In addition, the \textit{topic} of $U_{t}$ is abstracted in $\widetilde{B}_{t}$ as a word sequence $T_{t}$ in each unstructured knowledge-grounded turn, e.g. \textit{favorite} colored in blue in Fig.~\ref{sskm}.

\textbf{Extended Belief State Decoding.}\label{sec:ebsd}
Following Seq2Seq framework, we first use the \textit{context encoder} to encode the dialog context $C_{t}$, whose last output is used as the initial hidden state of decoders.
Based on the hidden states of context encoder $\textbf{h}_{enc}^{C_{t}}$ and previous extended belief state $\textbf{h}_{enc}^{\widetilde{B}_{t-1}}$, we then decode the current extended belief state $\widetilde{B}_{t}$ under two schemes, which are described as below.

Since $DSV_{t}$ and $T_{t}$ are grounded on quite different vocabularies, we consider implementing the decoding of $\widetilde{B}_{t}$ in two ways: (a) using the belief state decoder to generate the whole $\widetilde{B}_{t}$, and (b) using the DSV decoder and the topic decoder to generate $DSV_{t}$ and $T_{t}$ separately.
Each implementation has its own advantages over the other.
Specifically, in the single-decoder implementation, the decoding of $DSV_{t}$ and $T_{t}$ can be jointly optimized via shared parameters:
\begin{align}
    \widetilde{B}_{t}=\mathrm{Seq2Seq}^{(b)}(C_{t}|\textbf{h}_{enc}^{\widetilde{B}_{t-1}}).
\end{align}
While in the multi-decoder implementation, the decoding of $DSV_{t}$ and $T_{t}$ are fitted to their own smaller decoding spaces (vocabularies), and thus the generation of $\widetilde{B}_{t}$ can be decomposed into two simpler decoding processes:
\begin{align}
\begin{split}
   DSV_{t}&=\mathrm{Seq2Seq}^{(dsv)}(C_{t}|\textbf{h}_{enc}^{\widetilde{B}_{t-1}}), \\
   T_{t}&=\mathrm{Seq2Seq}^{(t)}(C_{t}|\textbf{h}_{enc}^{\widetilde{B}_{t-1}}), \\
   \widetilde{B}_{t}&=[DSV_{t},T_{t}].
\end{split}
\end{align}

\subsection{Hybrid Knowledge Operations}
Based on the extended belief state $\widetilde{B}_{t}$, we conduct both DB query and document retrieval to get the query result $\textbf{m}_{t}$ and the relevant document $D_{t}$, which are used to guide the generation of response.
In the operation of DB query, we simply match the original triples in $\widetilde{B}_{t}$ with the DB entries.
While in the operation of document retrieval, we first preprocess the document base to extract the topic of each document as its retrieval index, e.g. \textit{vegetarian} and \textit{favorite} colored in yellow in Fig.~\ref{sskm}.
Then we use the extended part of $\widetilde{B}_{t}$ to match the domain, entity and extracted topic of each document, and select the best-matched one as $D_{t}$.\footnote{
See Appendix \ref{document} for more details of the document preprocessing and matching.}

\subsection{Knowledge-Grounded Response Generation}
We generate system response based on the dialog context $C_{t}$, the extended belief state $\widetilde{B}_{t}$, and the outputs of hybrid knowledge operations $\textbf{m}_{t}$ and $D_{t}$.
We first use the same context encoder in Sec.~\ref{sec:ebsd} to encode $C_{t}$.
Moreover, we use the \textit{belief state encoder} and the \textit{document encoder} to encode $\widetilde{B}_{t}$ and $D_{t}$ into hidden states $\textbf{h}_{enc}^{\widetilde{B}_{t}}$ and $\textbf{h}_{enc}^{D_{t}}$, respectively.
Based on the hidden states of all the encoders and the vector $\textbf{m}_{t}$, we use the \textit{response decoder} to generate the system response $R_{t}$, formulated as:
\begin{align}
\begin{split}
    \textbf{h}_{enc}^{\widetilde{B}_{t}}&=\mathrm{Encoder^{(b)}}(\widetilde{B}_{t}), \\
    \textbf{h}_{enc}^{D_{t}}&=\mathrm{Encoder^{(d)}}(D_{t}), \\
    R_{t}&=\mathrm{Seq2Seq}^{(r)}(C_{t}|\textbf{h}_{enc}^{\widetilde{B}_{t}},\textbf{h}_{enc}^{D_{t}},\textbf{m}_{t}),
\end{split}
\end{align}
where $\mathrm{Encoder^{(b)}}$ and $\mathrm{Encoder^{(d)}}$ denote the belief state encoder and the document encoder.

Following previous TOD systems with Seq2Seq architectures \cite{lei2018sequicity,liang2020moss,zhang2020probabilistic,zhang2020task}, we use one-layer, bi-directional GRU as encoders and standard GRU as decoders.
We also apply global attention \cite{bahdanau2015neural} and copy mechanism \cite{gu2016incorporating} in all the Seq2Seq processes, to improve the context-awareness of decoding $\widetilde{B}_{t}$ and $R_{t}$.

\subsection{Model Training}
\ourmodel is optimized through supervised training.
Specifically, each dialog turn in the training data is initially labeled with the original belief state and the relevant document.
We extend the belief state label based on the domain, entity and extracted topic of the relevant document.
Then the extended belief state label and the reference response are used to calculate the cross-entropy loss with the generated $\widetilde{B}_{t}$ and $R_{t}$, respectively.
We sum the two losses together and perform gradient descent in each turn to optimize the model parameters.
In our paper, the dialog context $C_t$ is set as the concatenation of previous system response $R_{t-1}$ and current user utterance $U_t$.\footnote{See Appendix \ref{implement} for more implementation details.}

\section{Experimental Settings}
\subsection{Dataset}
We evaluate our proposed system on the modified MultiWOZ 2.1 \cite{kim2020beyond} dataset, where crowd-sourcing workers are hired to insert additional turns into the original MultiWOZ dialogs. Each newly inserted turn is grounded on unstructured knowledge in one of the four domains: restaurant, hotel, taxi and train, with the label of its relevant document in the document base.
While the other three MultiWOZ domains (attraction, hospital and police) are not involved in these new turns.\footnote{See Appendix \ref{statistics} for details of data statistics.}

\begin{table*}[t]
\centering
\resizebox{0.9\textwidth}{!}{
\smallskip\begin{tabular}{lccccccc}
\hline
Model               & Pretrained LM &     Inform    &    Success    &      BLEU     &     METEOR    &     ROUGE-L   &    Combined   \\
\hline
UniConv             &      none     &      71.5     &      61.8     &      18.5     &      37.8     &      40.5     &      85.7     \\
LABES-S2S           &      none     &      76.5     &      65.3     &      17.8     &      36.8     &      39.9     &      88.7     \\
UniConv + BDA       &        -      &      72.0     &      62.6     &      16.9     &      35.7     &      38.9     &      84.2     \\
LABES-S2S + BDA     &        -      &      77.1     &      66.2     &      15.7     &      33.8     &      37.8     &      87.4     \\
\ourmodel (Single)      &      none     & \textbf{81.9} & \textbf{68.3} & \textbf{19.0} & \textbf{38.5} &      40.9     & \textbf{94.1} \\
~~~- w/o Joint Optim    &      none     &      78.5     &      65.7     &      18.3     &      36.9     &      39.6     &  90.4 (-3.7)  \\
\ourmodel (Multiple)    &      none     &      79.1     &      67.6     &      18.7     &      38.1     & \textbf{41.0} &      92.1     \\
~~~- w/o Joint Optim    &      none     &      77.7     &      65.4     &      18.0     &      36.6     &      39.5     &  89.6 (-2.5)  \\
\hline
SimpleTOD           &      GPT-2    &      81.7     &      67.9     &      14.5     &      34.2     &      37.0     &      89.3     \\
SimpleTOD + BDA     &        -      &      83.3     &      68.6     &      14.8     &      33.6     &      36.5     &      90.8     \\
\hline
\end{tabular}
}
\caption{End-to-end evaluation results on modified MultiWOZ 2.1. ``+" denotes the combination of Beyond Domain APIs (BDA) with E2E TOD models. Best results among light-weight systems (i.e. above internal dividing line) are marked in bold.
Evaluation metrics are described and marked in bold in Sec.~\ref{sec:e2e}.
}
\label{table1}
\end{table*}

\subsection{Baselines}
We compare \ourmodel with 1) existing end-to-end (E2E) TOD models and dialog state tracking (DST) models, to show the benefits of incorporating unstructured knowledge management into TOD modeling.
We also compare \ourmodel with 2) unstructured knowledge management models, to investigate our system's document retrieval performance.
For the comparison with pipeline systems that have hybrid knowledge management, we also consider the combinations of 1) and 2) as our baselines.

\textbf{E2E TOD Models and DST Models.}
We consider three baseline E2E TOD models with different types of structures: \textbf{UniConv} \cite{le2020uniconv} uses a structured fusion \cite{mehri2019structured} design, \textbf{LABES-S2S} \cite{zhang2020probabilistic} uses a multi-stage Seq2Seq \cite{lei2018sequicity} architecture, and \textbf{SimpleTOD} \cite{hosseini2020simple} is based on a single auto-regressive language model initialized from GPT-2 \cite{radford2019language}. All three E2E models only manage structured knowledge (database) in their TOD modeling.
In addition to E2E TOD models, we also compare \ourmodel with existing DST models in the belief tracking evaluation.
Specifically, we use \textbf{TRADE} \cite{wu2019transferable} and \textbf{TripPy} \cite{heck2020trippy} as two DST baselines, which are representative BERT-free and BERT-based DST models, respectively.

\textbf{Unstructured Knowledge Management Models.}
We first compare our system with Beyond Domain APIs (\textbf{BDA}) \cite{kim2020beyond}.
This baseline model uses two classification modules based on BERT \cite{devlin2019bert} to detect unstructured knowledge-grounded dialog turns and retrieve relevant documents, respectively.
Moreover, we use standard information retrieval (IR) systems \textbf{TF-IDF} \cite{manning2008introduction} and \textbf{BM25} \cite{robertson2009probabilistic} as the other two baseline models.

\textbf{Combinations.}
We combine the unstructured knowledge management model BDA with every DST or E2E TOD model. Specifically, BDA detects dialog turns that are grounded on unstructured knowledge, and uses a fine-tuned GPT-2 to generate responses in these turns, based on the dialog context and retrieved documents. While the DST or E2E TOD model handles the rest dialog turns which are grounded on structured knowledge.

Noting that TripPy and SimpleTOD use large-scale pretrained language models (LM) to improve their dialog modeling performance, which requires large model sizes and computing resources.
For fair comparisons, we distinguish them from other light-weight models in our experiments.

\section{Results and Analysis}
We test our system's performance under both the single-decoder and multi-decoder belief state decoding implementations, denoted as \ourmodel (Single) and \ourmodel (Multiple), respectively.
Both implementations of \ourmodel come to the same conclusions when compared with the baseline models, which are described in detail below.

\subsection{End-to-End Evaluation}\label{sec:e2e}
Table \ref{table1} shows our experimental results of the end-to-end (E2E) evaluation, where we evaluate the task completion rate and language quality of system responses.
In terms of the task completion rate, we measure whether the system provides correct entities (\textbf{Inform} rate) and answers all the requested information (\textbf{Success} rate) in a dialog, following \citet{budzianowski2018multiwoz}.
For the evaluation of language quality, we adopt commonly used metrics \textbf{BLEU} \cite{papineni2002bleu}, \textbf{METEOR} \cite{banerjee2005meteor} and \textbf{ROUGE-L} \cite{lin2004rouge}.
Moreover, we use \textbf{Combined} score computed by $(Inform+Success)\times0.5+BLEU$ for overall evaluation, as suggested by \citet{eric2020multiwoz}.

We find that \ourmodel has better task completion rate than the light-weight E2E TOD models, which is comparable with SimpleTOD who uses large-scale pretrained GPT-2.
It also generates responses with better language quality compared to all the E2E models.
This is because our extended belief state can distinguish whether a dialog turn is grounded on structured or unstructured knowledge, which avoids the confusion between handling the two kinds of turns.
In addition, we manage the document base to provide relevant references for generating the response, which guide our system to give more appropriate responses in turns that are grounded on unstructured knowledge.

We also observe that \ourmodel outperforms the combinations of BDA and light-weight E2E TOD model.
This indicates that our end-to-end model framework has advantages over the pipeline structures of combination models.
In particular, dialog modeling grounded on the structured and unstructured knowledge are integrated in a uniform Seq2Seq architecture in our system, where they are jointly optimized to an overall better performance.
Although \ourmodel does not significantly outperform the combination of BDA and SimpleTOD, our system has lower deployment cost since it is trained end-to-end.

\begin{table}[t]
\centering
\resizebox{1.0\columnwidth}{!}{
\smallskip\begin{tabular}{l@{~~}c@{~~}c@{~~}c@{~~}c}
\hline
Model               &     Inform    &    Success    &      BLEU     &    Combined    \\
\hline
UniConv             &      84.2     &      71.8     &      19.0     &      97.3      \\
LABES-S2S           &      83.6     &      74.2     &      18.3     &      97.2      \\
UniConv + BDA       &      85.8     &      73.9     &      19.3     &      99.4      \\
LABES-S2S + BDA     &      85.0     &      75.3     &      18.9     &      99.1      \\
\ourmodel               & \textbf{87.2} & \textbf{76.5} & \textbf{19.5} & \textbf{101.4} \\
\hline
SimpleTOD           &      87.5     &      76.4     &      16.3     &      98.3      \\
SimpleTOD + BDA     &      89.0     &      77.2     &      17.0     &      100.1     \\
\hline
\end{tabular}
}
\caption{Context-to-response generation results on modified MultiWOZ 2.1. All symbols and markings have the same meaning as in Table \ref{table1}.}
\label{table2}
\end{table}

\subsection{Context-to-Response Generation}
We also conduct evaluations on the context-to-response (C2R) generation, where systems directly use the oracle belief state and knowledge to generate the response.
The experimental results are shown in Table \ref{table2}, where we observe the same conclusions as in the E2E evaluation (Table \ref{table1}). This again shows our system's superiority in TOD modeling grounded on hybrid knowledge.

Additionally, we observe that \ourmodel's performance gap between E2E and C2R evaluations is smaller than the baseline models, reflected in the smaller variations of the combined score.
This shows that the belief state and knowledge provided by our system are probably closer to the oracle and may give stronger guidance to generate a response.

\begin{table}[t]
\centering
\resizebox{0.9\columnwidth}{!}{
\smallskip\begin{tabular}{lcc}
\hline
Model               & Pretrained LM &   Joint Goal  \\
\hline
TRADE               &      none     &      42.9     \\
UniConv             &      none     &      45.5     \\
LABES-S2S           &      none     &      46.0     \\
TRADE + BDA         &        -      &      43.8     \\
UniConv + BDA       &        -      &      46.5     \\
LABES-S2S + BDA     &        -      &      46.8     \\
\ourmodel (Single)      &      none     & \textbf{48.0} \\
~~~- w/o Joint Optim   &      none     &  46.2 (-1.8)  \\
\ourmodel (Multiple)    &      none     &      47.6     \\
~~~- w/o Joint Optim   &      none     &  45.6 (-2.0)  \\
\hline
TripPy              &      BERT     &      50.4     \\
SimpleTOD           &      GPT-2    &      48.4     \\
TripPy + BDA        &        -      &      51.2     \\
SimpleTOD + BDA     &        -      &      49.8     \\
\hline
\end{tabular}
}
\caption{Original turns' belief tracking results on modified MultiWOZ 2.1. ``+" denotes the combination of BDA with DST/E2E models. The best result among light-weight systems (i.e. above internal dividing line) is marked in bold.
The evaluation metric is described and marked in bold in Sec.~\ref{sec:km}.
}
\label{table3}
\end{table}

\subsection{Knowledge Management}\label{sec:km}
To further investigate our system's end-to-end performance, we conduct evaluations on the intermediate knowledge management.
In particular, we evaluate the structured and unstructured knowledge management separately in the original and newly inserted dialog turns.
In the original turns grounded on structured knowledge, we evaluate the belief tracking performance which directly determines the database query accuracy.
Specifically, we use the \textbf{Joint Goal} accuracy \cite{henderson2014second} to measure whether belief states are predicted correctly in a dialog turn.
While in newly inserted turns grounded on unstructured knowledge, we adopt standard information retrieval metrics \textbf{R@1} and \textbf{MRR@5} to evaluate the document retrieval performance.
Table \ref{table3} and \ref{table4} shows our evaluation results of belief tracking and document retrieval, respectively.

\begin{table}[t]
\centering
\resizebox{1.0\columnwidth}{!}{
\smallskip\begin{tabular}{l@{~~}c@{~~}c@{~~}c@{~~}c}
\hline
Model                   &      Type       &     MRR@5     &     R@1       \\
\hline
TF-IDF                  &   standard IR   &     68.7      &     54.1      \\
BM25                    &   standard IR   &     69.2      &     52.5      \\
BDA                     & classification  &     80.6      &     69.8      \\
\hline
\ourmodel (Single)           & topic match  & \textbf{81.7} & \textbf{80.2} \\
~~~- w/o Joint Optim         & topic match  &  80.1 (-1.6)  &  77.8 (-2.4)  \\
\ourmodel (Multiple)         & topic match  &      81.1     &      79.5     \\
~~~- w/o Joint Optim         & topic match  &  79.7 (-1.4)  &  77.4 (-2.1)  \\
\hline
\end{tabular}
}
\caption{Newly inserted turns' document retrieval results on modified MultiWOZ 2.1.
Best results are marked in bold.
Evaluation metrics are described and marked in bold in Sec.~\ref{sec:km}.
}
\label{table4}
\end{table}

In terms of belief tracking, \ourmodel outperforms the light-weight DST/E2E models.
This is because our extended belief tracking can detect the newly inserted turns apart from the original turns (via the slot \textit{ruk}), which improves our system's awareness on deciding when to update the original triples in the belief state.
\ourmodel also has better belief tracking performance than the combinations of BDA and light-weight DST/E2E model.
This is because error propagation on updating belief states is eliminated in our system compared to the pipeline framework: The pipeline system either updates the belief state or retrieves the document in one turn, but \ourmodel can perform both operations in the nature of its E2E design.
Although the belief tracking performance of \ourmodel is not as good as that of TripPy and SimpleTOD, our system does not use large-scale pretrained BERT or GPT-2 and is thus computational cheaper.\footnote{See Appendix \ref{size} for details on model size comparison.}

In the document retrieval evaluation, we find that \ourmodel outperforms the unstructured knowledge management models, especially on the R@1 metric.
This shows that our system's document retrieval scheme with topic matching has a higher accuracy, compared to the classifier-based BDA and the standard information retrieval (IR) systems.
Specifically, \ourmodel retrieves documents based on the highly simplified semantic information, i.e. the topic, which reduces the complexity of the retrieval process.
This makes the retrieval scheme of \ourmodel more concise and effective than the baseline models, who directly calculate the relevance of dialog context to every document content.

\subsection{Single vs. Multiple Decoders}
We then compare our two implementations of extended belief state decoding. We calculate the vocabularies of DSV triples, the topic and their combination (which are 709, 166 and 862), and observe that the last one approximately equals to the sum of the former two.
This confirms our assumption in Sec.~\ref{sec:ebsd} that DSV triples and topic have quite different vocabularies, which motivates the multi-decoder implementation in belief state decoding.

However, we find that \ourmodel (Single) outperforms \ourmodel (Multiple) in both E2E and knowledge management evaluations, as shown in Table \ref{table1}, \ref{table3} and \ref{table4}.
This shows that the decoding of DSV triples and topic can benefit from the joint optimization via shared parameters, although they are grounded on quite different vocabularies.
The superiority of joint optimization further implies that the structured and unstructured knowledge management in TOD modeling have a positive correlation, since they commonly involve task-specific domain knowledge and entities. Therefore, the two kinds of knowledge management can learn from each other through joint training, and achieve overall better performance compared to separating them apart.

\begin{table*}[t]
\centering
\resizebox{0.9\textwidth}{!}{
\smallskip\begin{tabular}{clccccccc}
\hline
        Test Set          & Model                  &  Joint Goal  & Inform & Success &  BLEU  & METEOR & ROUGE-L &  Combined  \\
\hline
\multirow{3}{*}{Original} & LABES-S2S + BDA        &     49.0     &  82.1  &  69.8   &  17.8  &  37.1  &  40.2   &    93.8    \\
                          & SimpleTOD + BDA        &     51.8     &  85.6  &  70.9   &  16.3  &  34.5  &  38.6   &    94.6    \\
                          & \ourmodel (Single)     &     49.2     &  82.3  &  69.4   &  18.0  &  37.3  &  40.2   &    93.9    \\
\hline
\multirow{3}{*}{Modified} & LABES-S2S + BDA        &  46.8 (-2.2) &  77.1  &  66.2   &  17.7  &  36.8  &  39.6   &  89.4 (-4.4) \\
                          & SimpleTOD + BDA        &  49.8 (-2.0) &  83.3  &  68.6   &  15.8  &  33.6  &  37.8   &  91.8 (-2.8) \\
                          & \ourmodel (Single)     &  48.0 (-1.2) &  81.9  &  68.3   &  17.8  &  37.2  &  39.5   &  92.9 (-1.0) \\
\hline
\end{tabular}
}
\caption{End-to-end evaluation results on the original and modified MultiWOZ 2.1 test set. The evaluation is conducted only in the original dialog turns.}
\label{table5}
\end{table*}

\subsection{Ablation Study}
We ablate the joint optimization of structured and unstructured knowledge-grounded TOD modeling to investigate its role in our framework, denoted as w/o Joint Optim in Table \ref{table1}, \ref{table3} and \ref{table4}.
Specifically, we train two \ourmodel models separately on the original and newly inserted dialog turns, and use them to handle TOD grounded on structured and unstructured knowledge, respectively.
To determine which model should be used, the oracle label of slot \textit{ruk} is used to judge which knowledge type the current dialog turn is grounded on.

We observe that removing joint optimization brings \ourmodel evident performance declines in the end-to-end evaluation (Table \ref{table1}). This suggests that joint optimization plays a significant role in improving \ourmodel's end-to-end performance, where TOD modeling grounded on the two kinds of knowledge can benefit each other by learning shared parameters.
The ablation of joint optimization also causes performance declines in \ourmodel's knowledge management (Table \ref{table3} and \ref{table4}). This again indicates that the two kinds of knowledge management are positively correlative and can get benefit from joint training.

\subsection{Between Structured and Unstructured Knowledge}
In this section, we investigate how the newly inserted dialog turns (grounded on unstructured knowledge) affect systems' E2E performance in the original dialog turns (grounded on structured knowledge).
Specifically, we evaluate systems' E2E performance on both the original and modified MultiWOZ 2.1 test sets.
This evaluation is conducted only in the original dialog turns, which is different from the E2E evaluation conducted in all turns (Table \ref{table1}).
Table \ref{table5} shows the results of this experiment, where we compare \ourmodel (Single) with strong combination models.

We find that all the models' performance is degraded when transferred from the original to the modified test set. This indicates that the inserted turns grounded on new knowledge may interrupt the original dialogs, which complicates the dialog process and causes difficulties in the original turns' dialog modeling.

However, we observe that \ourmodel (Single) suffers from less reduction compared to the baseline combination models.
This shows that our system has a stronger resistance to the interruptions of newly inserted turns, which benefits from our end-to-end modeling.
Specifically, \ourmodel jointly optimizes dialog modeling of the original and newly inserted turns in a uniform end-to-end framework. This unified modeling approach improves our system's flexibility in switching between the two kinds of turns, and thus makes it more competent in handling the complicated dialog process.

\begin{table}[t]
\centering
\resizebox{1.0\columnwidth}{!}{
\smallskip\begin{tabular}{@{~}l@{~~}c@{~~}c@{~~}cc@{~~}c@{~~}c@{~}}
\hline
\multirow{2}{*}{Model} & \multicolumn{3}{c}{Original}                & \multicolumn{3}{c}{Newly Inserted}         \\
                         \cmidrule(lr){2-4}                              \cmidrule(lr){5-7}
                       &      Cohe.     &      Info.     &     Corr.      &      Cohe.     &      Info.     &      Corr.     \\
\hline
SimpleTOD              &      2.58     &      2.56     &     2.44      &      2.50     &      2.04     &      2.14     \\
SimpleTOD + BDA        &      2.56     &      2.60     & \textbf{2.46} &      2.52     &      2.30     &      2.22     \\
\hline
\ourmodel (Single)     & \textbf{2.60} & \textbf{2.62} &     2.42      & \textbf{2.56} & \textbf{2.36} & \textbf{2.50} \\
\hline
\end{tabular}
}
\caption{Human evaluation results on modified MultiWOZ 2.1, results in original and newly inserted turns are shown separately.}
\label{table6}
\end{table}

\begin{table*}[t]
\centering
\small
\resizebox{1.0\textwidth}{!}{
\begin{tabular}{c|l}
\hline
\multicolumn{2}{l}{$U_{1}$: Hello, I would like to find a \textbf{hotel} that has WiFi in the north part of the town.} \\
\multicolumn{2}{l}{$B_{1}$: hotel-area: north, hotel-internet: yes} \\
\multicolumn{2}{l}{$R_{1}$: The \textbf{Arbury Lodge Guesthouse} is one of 12 options for you. Shall I make a reservation for you?} \\
\multicolumn{2}{l}{$U_{2}$: Do they provide \textbf{Italian breakfast}?} \\
\hline
\multirow{3}*{Human} & $B_{2}$: hotel-area: north, hotel-internet: yes \\
                     & $D_{2}$: Full English \textbf{breakfast} is served every morning at Arbury Lodge Guesthouse. \\
                     & $R_{2}$: \textbf{No}, but they have a full English breakfast. Did you still want to book a room here? \\
\hline
\multirow{2}*{SimpleTOD} & $B_{2}$: hotel-area: north, hotel-internet: yes, \textbf{restaurant-food: Italian} \\
                     & $R_{2}$: Da Vinci Pizzeria serves Italian food and is located in the north. \\
\hline
\multirow{3}*{SimpleTOD + BDA} & $B_{2}$: hotel-area: north, hotel-internet: yes \\
                    & $D_{2}$: German, Italian, Spanish and English are \textbf{spoken} at Carolina Bed and Breakfast. \\
                    & $R_{2}$: \textbf{Yes}, the hotel has a Italian breakfast. Would you like to make a reservation?\\
\hline
\multirow{3}*{\ourmodel (Single)} & \\[-9pt]
                    & $\widetilde{B}_{2}$: hotel-area: north, hotel-internet: yes, \textbf{hotel-ruk: Arbury Lodge Guesthouse}, \textbf{breakfast}\\
                    & $D_{2}$: Full English \textbf{breakfast} is served every morning at Arbury Lodge Guesthouse. \\
                    & $R_{2}$: \textbf{No}, they provides full English breakfast. Would you like me to book a room for you?\\
\hline
\end{tabular}
}
\caption{Comparison of the belief tracking, document retrieval and response generation results when dialog steps into a newly inserted turn of modified MultiWOZ 2.1. ``Human'' denotes ground truth results.}
\label{table7}
\end{table*}

\subsection{Human Evaluation}
There is still a gap between the evaluation results of automatic metrics and the real E2E performance of TOD systems.
Therefore, we conduct human evaluation to more adequately test our system's E2E performance. In particular, we compare \ourmodel (Single) with a strong E2E baseline SimpleTOD and its combination with BDA.

We conduct human evaluation separately on the two types (original and newly inserted) of dialog turns.
Specifically, we sample fifty dialog turns of each type and ask the judges to evaluate each turn's system response on three aspects.
\textbf{Coherence} (Cohe.) measures how well the response is coherent with the dialog context.
\textbf{Informativeness} (Info.) measures how well the response can provide sufficient information that meets the user requests.
\textbf{Correctness} (Corr.) measures how well the information in response is consistent with the ground truth knowledge, i.e. relevant DB entries or documents.
All the three aspects are scored on a Liker scale of 1-3, which denotes \textit{bad}, \textit{so-so} and \textit{good}.

Table \ref{table6} shows our human evaluation results.
In the original dialog turns, \ourmodel (Single) scores close to SimpleTOD and its combination with BDA on all the three aspects. This indicates that our proposed light-weight system is comparable with the large GPT-2 based models in managing structured knowledge to generate the response.
In addition, our model outperforms the two baseline models in the newly inserted dialog turns.
Specifically, \ourmodel (Single) generates responses with significantly better informativeness and correctness than SimpleTOD. This again shows that the management of unstructured knowledge is beneficial for generating appropriate responses.
Compared to the combination of SimpleTOD and BDA, the responses generated by \ourmodel (Single) also achieve much better correctness, which benefits from our model’s higher document retrieval accuracy (as shown in Table \ref{table4}).

\subsection{Case Study}
An example dialog segment ($U_1$, $B_1$, $R_1$, $U_2$) and corresponding output results of each model ($B_2$, $D_2$, $R_2$) are presented in Table \ref{table7}.
Without access to unstructured document base, SimpleTOD misunderstands the user query, and instead recognizes the term ``Italian'' in user utterance as a constraint to update the belief state. As a result, the system makes an inappropriate recommendation.
By combining with BDA, SimpleTOD predicts correct belief state, but fails in finding the relevant document, thus providing a wrong answer. This is because the wrong document’s content has many common words with the dialog context, e.g. “Italian” and “Breakfast”, which mislead the retrieval process of BDA.
In contrast, \ourmodel gives a proper response with accurate information as it identifies the entity (``Arbury Lodge Guesthouse'') and captures the topic (``breakfast'') to avoid the misleading of common words in document retrieval.

\section{Conclusion}
In this paper, we define a task of modeling TOD with access to both structured and unstructured knowledge.
To address this task, we propose a TOD system \ourmodel which uses an E2E framework to jointly optimize TOD modeling grounded on the two kinds of knowledge.
In the experiments, \ourmodel shows strong performance in modeling TOD with hybrid knowledge management, compared to existing TOD systems and their pipeline extensions.
For future work, we plan to incorporate large-scale pretrained language models into our proposed system to further enhance its performance. Furthermore, we consider evaluating our system on different scenarios where dialogs are grounded on hybrid knowledge.

\section*{Acknowledgments}
This work was partly supported by the NSFC projects (Key project with No.~61936010 and regular project with No.~61876096).
This work was also supported by the Guoqiang Institute of Tsinghua University, with Grant No.~2019GQG1 and 2020GQG0005.
We would like to thank colleagues from HUAWEI for their constant support and valuable discussion.

\bibliographystyle{acl_natbib}