  We introduce a novel schema for sequence to sequence learning with a Deep
Q-Network (DQN), which decodes the output sequence iteratively. The aim here is
to enable the decoder to first tackle easier portions of the sequences, and
then turn to cope with difficult parts. Specifically, in each iteration, an
encoder-decoder Long Short-Term Memory (LSTM) network is employed to, from the
input sequence, automatically create features to represent the internal states
of and formulate a list of potential actions for the DQN. Take rephrasing a
natural sentence as an example. This list can contain ranked potential words.
Next, the DQN learns to make decision on which action (e.g., word) will be
selected from the list to modify the current decoded sequence. The newly
modified output sequence is subsequently used as the input to the DQN for the
next decoding iteration. In each iteration, we also bias the reinforcement
learning's attention to explore sequence portions which are previously
difficult to be decoded. For evaluation, the proposed strategy was trained to
decode ten thousands natural sentences. Our experiments indicate that, when
compared to a left-to-right greedy beam search LSTM decoder, the proposed
method performed competitively well when decoding sentences from the training
set, but significantly outperformed the baseline when decoding unseen
sentences, in terms of BLEU score obtained.
