Deep Reinforcement Learning for Dialogue Generation

In plain words

Chatbots built from neural sequence models tend to give safe replies such as "I don't know", and they can get stuck repeating themselves. Each reply is chosen to be locally likely, with no thought for where the conversation goes next.

This paper trains a chatbot against a score that looks further ahead. The score rewards replies that are hard to dismiss with a dull answer, that bring new content instead of repeating the last turn, and that still fit what was said. The model is first trained in the usual way, then two copies of it talk to each other, and the conversation is scored as it goes. The rewards are simple, hand-written rules, so the method is only as good as those rules.

The result is replies that keep a conversation going for more turns. The authors also say the replies are not better as single answers, so the gain is in the conversation, not in each sentence.

TL;DR

• A seq2seq chatbot is tuned with policy gradients on a hand-designed reward: ease of answering, information flow and semantic coherence §3.4.
• Training starts from a mutual-information model; the two-agent simulation then samples dialogues and updates the policy §4.2 §4.3.
• Author-reported gains are in dialogue length, diversity and multi-turn human judgments; single-turn quality is roughly a tie and BLEU is lower §5.2.
• The paper ships no code. The rewards are heuristics the authors call insufficient §5.2.

Problem

Sequence-to-sequence models trained with maximum likelihood produce generic replies such as "I don't know" regardless of input, and they fall into loops of repeated turns §1 tab. 1. The maximum-likelihood objective does not measure whether a reply keeps a conversation going, and generic replies are favoured because they are frequent in the training data §1.

The paper assumes that the target behaviour can be written as rewards on generated turns, and that a model can be pre-trained with maximum likelihood and then moved towards those rewards §3 §4.

Method

The model is a dialogue simulator with two agents that alternate turns. A dialogue is the sequence p1, q1, p2, q2, ..., where each turn is an action sampled from a policy §3.

Components §3.1–§3.3

• Action. An action is a whole utterance. The action space is infinite because utterance length is unbounded §3.1.
• State. The state is the previous two turns [p_i, q_i], encoded by an LSTM encoder §3.2.
• Policy. The policy is an LSTM encoder-decoder, p_RL(p_{i+1} | p_i, q_i). It is stochastic. The authors argue a deterministic policy would give a discontinuous objective that gradient methods cannot optimise well §3.3. They prefer policy gradients over Q-learning, because a policy can start from maximum-likelihood parameters that already give plausible replies §3 §3.3.

Reward §3.4

The reward for an action a in context [p_i, q_i] is a weighted sum of three terms eq. 4:

• Ease of answering eq. 1: the negative average log-likelihood that a fixed list of 8 dull replies follows a. The list includes phrases such as "I don't know what you are talking about" and "I have no idea" §3.4.
• Information flow eq. 2: the negative log of the cosine between encoder representations of consecutive turns from the same agent. It penalises repetition §3.4.
• Semantic coherence eq. 3: the forward log-likelihood of a given the previous turns, plus the backward log-likelihood of the previous turn q_i given a. Both are divided by their target lengths §3.4.

Weights are λ1 = 0.25, λ2 = 0.25, λ3 = 0.5 §3.4. A reward is observed when the agent reaches the end of each sentence §3.4.

Training stages §4

1. Supervised model §4.1. An attention seq2seq model is trained on about 80 million source-target pairs from OpenSubtitles. Each turn is a target, and the concatenation of the two previous sentences is the source §4.1.
2. Mutual-information model §4.2. The policy is trained to maximise a mutual-information score m(â, [p_i, q_i]) for sampled candidates â. The score is computed with the forward model and the backward model. Gradients come from the likelihood-ratio trick with a neural baseline eq. 6 eq. 7. Sequence-level training is mixed with maximum likelihood by a curriculum: the first L tokens use the maximum-likelihood loss and the rest use the reinforcement signal, with L annealed to zero §4.2.
3. Two-agent simulation §4.3. The policy is initialised from the mutual-information model. A message from the training set starts the dialogue; each agent's reply is fed to the other agent fig. 1. The objective is the expected sum of rewards over the simulated turns eq. 8, with the gradient in eq. 9.
4. Curriculum over turns §4.4. Simulated dialogues start at 2 turns and grow up to 5 turns. Five candidate replies are sampled at each simulation step §4.4.

Update rules

Objective of the two-agent stage eq. 8:

J_{RL}(\theta) = \mathbb{E}_{p_{RL}(a_{1:T})} \Big[ \sum_{i=1}^{T} R(a_i, [p_i, q_i]) \Big] eq. 8

Gradient estimate printed in the paper eq. 9:

\nabla J_{RL}(\theta) \approx \sum_{i} \nabla \log p(a_i \mid p_i, q_i) \sum_{i=1}^{T} R(a_i, [p_i, q_i]) eq. 9

Mutual-information stage eq. 5–eq. 7:

J(\theta) = \mathbb{E}[m(\hat{a}, [p_i, q_i])] eq. 5

\nabla J(\theta) = m(\hat{a}, [p_i, q_i]) \nabla \log p_{RL}(\hat{a} \mid [p_i, q_i]) eq. 6

\nabla J(\theta) = \nabla \log p_{RL}(\hat{a} \mid [p_i, q_i]) \big[ m(\hat{a}, [p_i, q_i]) - b \big] eq. 7

The reward terms as printed:

r_1 = -\frac{1}{N_{\mathbb{S}}} \sum_{s \in \mathbb{S}} \frac{1}{N_s} \log p_{\text{seq2seq}}(s \mid a) eq. 1

r_2 = -\log \cos(h_{p_i}, h_{p_{i+1}}) eq. 2

r_3 = \frac{1}{N_a} \log p_{\text{seq2seq}}(a \mid q_i, p_i) + \frac{1}{N_{q_i}} \log p^{\text{backward}}_{\text{seq2seq}}(q_i \mid a) eq. 3

r(a, [p_i, q_i]) = \lambda_1 r_1 + \lambda_2 r_2 + \lambda_3 r_3 eq. 4

Pseudocode for the reward and the two-agent update, following eq. 1–eq. 4 and eq. 9. Names are ours. Learning rate, number of candidates and baseline for this stage are not stated, so they are arguments:

# Ease of answering: dull-reply likelihood  [eq. 1] [§3.4]
def ease_of_answering(action, dull_replies):
    total = 0
    for dull in dull_replies:
        # log-likelihood of the dull reply, divided by its length  [eq. 1]
        total += log_prob_seq2seq(dull, given=action) / num_tokens(dull)
    # negative mean over the list; N_S = len(dull_replies)  [eq. 1]
    return -total / len(dull_replies)

# Information flow: cosine between encoder states  [eq. 2] [§3.4]
def information_flow(encoding_prev, encoding_next):
    # Not stated: what happens when cos <= 0 (log is undefined)
    cos = dot(encoding_prev, encoding_next) / (
        norm(encoding_prev) * norm(encoding_next))
    return -log(cos)

# Semantic coherence: forward and backward log-likelihood  [eq. 3] [§3.4]
def coherence(action, prev_turn, last_turn):
    forward = log_prob_seq2seq(action, given=(last_turn, prev_turn))
    forward = forward / num_tokens(action)
    backward = log_prob_backward(last_turn, given=action)
    backward = backward / num_tokens(last_turn)
    return forward + backward

# Weighted reward with lambda = (0.25, 0.25, 0.5)  [eq. 4] [§3.4]
def reward(action, prev_turn, last_turn, enc_prev, enc_next):
    return (0.25 * ease_of_answering(action, DULL_REPLIES)
            + 0.25 * information_flow(enc_prev, enc_next)
            + 0.5 * coherence(action, prev_turn, last_turn))

# Two-agent policy-gradient update  [eq. 8] [eq. 9] [§4.3]
def update_policy(policy, actions, rewards, learning_rate):
    # Printed Eq. 9 multiplies each step by the sum over all turns
    total_reward = sum(rewards)
    gradient = zeros_like(policy.parameters)
    for action in actions:
        # gradient of the log-probability of this generated turn  [eq. 9]
        gradient += grad_log_prob(policy, action) * total_reward
    # ascent step; learning rate not stated  [§4.3]
    policy.parameters += learning_rate * gradient

Hyperparameters

Results

Author-reported. Setup: OpenSubtitles-trained models; simulated dialogues from 1,000 test inputs; the three human settings and their sample sizes are in §5.2. Hardware is not stated.

The authors call the single-turn quality change "not a significant boost" and the ease-to-answer and multi-turn gains "significant". No significance test is reported §5.2. Sampled replies are in tab. 3; a dialogue that cycles over two turns is in tab. 6.

Paper vs code

No official code.

Searched: the paper, its abstract and footnotes contain no code link. No project page is linked. A GitHub search for the title and the method returned only third-party reimplementations, which are not used. The first author's repository jiweil/Neural-Dialogue-Generation (MIT, commit 87c698c60ae486a54cf714996800a054eeaab132 at the time of checking) is by an author, but it does not implement this paper: its README lists other papers from the same group, and a search of the repository found no implementation of the dull-reply, cosine or ease-of-answering rewards. Its Adversarial/Reinforce folder belongs to a different paper (arXiv 1701.06547).

Because there is no code, the pseudocode above is our reading of the paper, not a verified implementation.

Pitfalls

• Typo in the normaliser of eq. 1. The text says N_S is "the cardinality of N_S". It means the size of the dull-reply list 𝕊 (8 replies) §3.4.
• Extra length scaling in the reward. The text says r1 is "further scaled by the length of target 𝕊". Eq. 1 already divides by N_s, and the list length is already applied. The extra scaling is not written in an equation §3.4.
• Undefined information-flow term. −log cos is undefined for cos = 0 and for negative cos, and the paper does not say what to do. The paper also does not say which encoder states h are used eq. 2 §3.4.
• Input order of the forward term. Eq. 3 writes p(a | q_i, p_i), while the text writes p(a | p_i, q_i). Concatenation order is not stated, and it changes the model's input eq. 3 §3.4.
• Mixed signs and scales. r1 is non-negative (it is a negative log-likelihood). r2 is non-negative for cos ≤ 1. r3 is non-positive because it is a sum of log-probabilities. The paper gives no normalisation before the weighted sum eq. 4. This is derived from the equations, not stated.
• Eq. 9 index. The printed gradient sums over i twice. We read it as the whole-dialogue reward multiplied by the gradient of each turn. A per-turn reward-to-go is another reading and is not ruled out eq. 9.
• No baseline or discount in the two-agent stage. A baseline is described only for the mutual-information stage §4.2. The two-agent objective has no discount factor and no baseline in the compiled text eq. 8 eq. 9.
• Contradictory initialisation. §4.1 says the supervised model will be used for initialisation. §4.2 says the policy should not be initialised from the plain Seq2Seq model. §4.3 says it is initialised from the mutual-information model. The mutual-information model is the consistent reading §4.1 §4.2 §4.3.
• The MI score m is not written out. §4.2 names its two inputs but gives no formula in the compiled paper. The LaTeX source contains a commented-out draft with a weight of 0.5, a discount of 0.99 and length-normalised candidate probabilities. That draft is not part of the published text. We do not use it.
• Dull-reply lists differ. The 8 replies in §3.4 are used as the reward. The 8 phrases in §5.2 are used for evaluation. The paper does not say they are the same list, and the phrase in §5.1 is quoted with "taking" §3.4 §5.1 §5.2.
• The reward can be gamed. The authors state that the hand-written rewards cannot cover what makes a good conversation, and that real human reward would be preferable §5.2. The length metric uses the same dull-reply rule as the reward, so it is not an independent check.
• Evaluation is partly circular. Dialogue length is measured by the same dull-reply and repetition rules that shaped the reward, and with rule-based matching that has known false positives and negatives §5.2 [fn. 3].
• Diversity set not stated. The paper does not say which generated responses are used for the type-token ratio §5.2 tab. 4.
• Human evaluation is small. There are 500 and 200 items with three judges each. Inter-annotator agreement is not reported. The text mentions the mean difference in scores, but only win, lose and tie rates appear in tab. 5 §5.2.
• BLEU goes down. The authors report lower BLEU for the RL model and say it is expected under this objective. Do not treat BLEU as a quality target §5.2 [fn. 2].
• Turn cap is ambiguous. "less than 8" may mean a cap of 7 or of 8 §5.2.
• Cycles and topic drift remain. Dialogues can loop over more than two turns and can drift off topic. The authors attribute the loops to short history and the drift to the trade-off in the reward §5.2 tab. 6.
• Exponential cost. The authors say the number of candidates and simulated turns they could explore is small because the search grows exponentially §5.2.

Lineage

• Builds on: attention seq2seq models for dialogue (Bahdanau et al., 2015; Sutskever et al., 2014) §4.1; the mutual-information objective of Li et al. (2016a) §4.2; sequence-level training with a curriculum (Ranzato et al., 2015) §4.2; policy gradients with a baseline (Williams, 1992; Zaremba and Sutskever, 2015) §4.2; the AlphaGo-style initialise-then-tune strategy (Silver et al., 2016) §4.
• Compared against: a maximum-likelihood Seq2Seq model and the mutual-information model of Li et al. (2016a) §5.2 tab. 2 tab. 4 tab. 5.