) \nabla_{\theta}    \log P_{\theta}({\mathbf x} | {\mathbf y})  \right]
\end{align}
Here we have used the product rule and the identity $\nabla P = P \cdot \nabla \log P$. Notice that, the reward depends (differentiably) on $\theta$, because of the reconstruction term.

Since the gradient is a conditional expectation, one can sample ${\mathbf y}$ to obtain an unbiased estimate of the expected gradient~\citep{sutton2000policy}:
\begin{equation}
\nabla_{\theta} \mathbb{E}_{{\mathbf y}|{\mathbf x}}[R]  \approx \frac{1}{K} \displaystyle \sum_{i} 
R({\mathbf y}_i)  \nabla_{\theta} \log P_{\theta}({\mathbf y}_i | {\mathbf x})   + (1 - \alpha) 
  \nabla_{\theta} \log P_{\theta}({\mathbf x} | {\mathbf y}_i)
\end{equation}

Any sampling approach can be used to estimate the expected gradient. 
\citet{he2016dual} use beam search instead of sampling to avoid large variance and unreasonable results. 
We generate from the policy by randomly sampling the next word from the predicted word distribution.
However, we found it helpful to make the distribution more deterministic using a low softmax temperature ($0.002$). 
 In order to reduce variance further, we compute a baseline through the batch. 
That is, we compute the average of each reward through the whole batch and subtract it from each reward.
We optimize the likelihood of the translation system on the monolingual data of both the source and target languages, while scaling the gradients (equivalently, the loss or the negative likelihood) with the total rewards. 


\subsection{System implementation}

\begin{figure}
\centering
\includegraphics[scale=0.67]{img/model.pdf}
\caption{The zero-shot dual learning procedure (bottom-up,
  left-to-right). The encoder, on the 
  forward translation step, receives the source sentence ${\mathbf x}$
  as input with the target language tag $y_{tag}$. The decoder, on the
  forward translation step, randomly samples a translation
  ${\mathbf y}$, which is passed to the language model to
  generate the fluency reward. At the same time, ${\mathbf y}$
  is encoded, by the same model, now with the source language tag
  $x_{tag}$. Then the decoder is used to compute the probability of
  the original sentence ${\mathbf x}$, conditioning on
  ${\mathbf y}$. Both encoders and decoders share the same parameters.} 
\label{fig:model_arch}
\end{figure}

The system is implemented as an extension of the Tensorflow \cite{abadi2016tensorflow} NMT tutorial
code,\footnote{\url{https://www.tensorflow.org/tutorials/seq2seq}.} and will be released as open source.
Figure~\ref{fig:model_arch} visualizes the training
process. 
The model is optimized after two calls: one for the forward translation and another for the backward translation.
During the forward translation, the encoder takes a sentence ${\mathbf x}=y_{\mathrm{tag}}, x_1,..., x_M$, where $y_{\mathrm{tag}}$ is the tag of the
target language, and
samples a translation output ${\mathbf y} = y_1, y_2,..., y_N$.  At each step the decoder randomly picks the next word from the current distribution.  This word is fed as input at the next decoding step. 

Then, ${\mathbf y}$ is used by the language model RNN trained on the target language. 
The language model is kept fixed during the whole process. 
Observe that initially the special begin-of-sentence symbol is fed, 
so that we can also obtain the probability for the first word. 
Here, we use the output logits in order to calculate the probability of the sample sentence. The first reward is computed as:

\begin{equation}
  r_1 = \log P_{Y}({\mathbf y}) = \displaystyle \sum_{i=1}^N \log  P_{Y}(y_i | y_1, \ldots, y_{i-1}) 
\end{equation}

In addition, the backward translation call is executed: 
 ${\mathbf y}$, plus the source language tag added 
in the beginning, $ x_{\mathrm{tag}} $, is encoded to a sequence of hidden state
vectors 
$h_0, h_1, h_2, \ldots, h_N$
using the encoder.
These outputs are passed to the decoder which is fed with the original source words $x_i$ at each step. 
The output logits are used to calculate the probability of the source 
sentence ${\mathbf x}$ being reconstructed from ${\mathbf y}$. 
This value is used as the second reward:

\begin{equation}  
r_2 = \log P_{\theta}({\mathbf x}| {\mathbf y}) = \sum_{i=1}^M \log P_{\theta}(x_i | x_1, \ldots, x_{i-1}, h_0,
h_1, \ldots, h_N)
\end{equation}












\subsubsection*{Acknowledgments}

\bibliographystyle{abbrvnat}

\section{Qualitative Analysis}
\label{ch:appendix}

\subsection{Experiment with Three Languages}

Here we analyze the translation quality of the translations 
for the test set before and after the zero-shot dual learning algorithm.
Some examples are shown in Table \ref{tab:results-qualit3}. 
Examples are separated by a double horizontal line. 
For each, the source, the translation from the multilingual NMT baseline (trained on en-es and en-fr data), the translation after the zero-shot dual learning and the corresponding reference are provided.

After analyzing the output translations for both directions of the zero-shot pair on a high level,
we have noticed that the multilingual NMT baseline tends to translate to English, 
approximately half of the times. 
Apart from these, 
many sentences are rewritten in the source language.
Still, there is also a number of sentences that are correctly translated to the target language,
already with the multilingual NMT baseline model.
We have observed that these sentences are in general short or have a specific structure,
for example, meeting dates.

If we analyze the translations obtained after the reinforcement learning algorithm, instead,
we could see that all outputs are in the target language; 
just a few sentences contain some word that is not correctly translated. 
This means that our approach is capable of training the model to translate to the required language, 
even without any parallel data for the zero-shot language pair.




\begin{center}
\begin{longtable}{ll}  
  \caption{Qualitative analysis of the translations for the experiment with 3 languages. Examples are separated by a double horizontal line. For each, the first row shows the source sentence, the second is the outcome of the multilingual NMT baseline NMT-0 (trained on en-es, en-fr data), the third line shows the translation of the model after the zero-shot dual learning Dual-0 and the last row shows the reference.}
  \endfirsthead
  \multicolumn{2}{r}{{Continued on next page}} \\ \hline
  \endfoot
  \endlastfoot
    \midrule
    \textbf{(1) Source} & \textbf{L'EIIL a mis en ligne des vidéos dans lesquelles on peut voir des } \\ 
    & \textbf{personnes subir toute une série de châtiments abominables : (...) } \\
    NMT-0 & L'EIIL a mis en place des videos en indiquant que les personnes \\ 
    & séroviennent d'un ensemble d'abominables, (...)\\
   
   
    Dual-0 & La EIIL puso en marcha videos en los que se puede ver a \\
    & personas que padecen toda una serie de castigos abominables: (...) \\
    \textbf{Reference} & \textbf{El propio EIIL ha publicado vídeos en los que se muestran } \\ 
    & \textbf{imágenes de personas sometidas a una serie de castigos atroces, (...)} \\
    \midrule
    \midrule 
    \textbf{(2) Source} & \textbf{El propio EIIL ha publicado vídeos en los que se muestran imágenes} \\ 
    & \textbf{de personas sometidas a una serie de castigos atroces, (...)} \\
    NMT-0 & L'EIIL itself a publié des videos en indiquant des images de personnes \\ 
    & faisant l'objet d'une série de atroces châtiments, (...) \\
   
   
    Dual-0 & L'ensem