Decoupling Strategy and Generation in Negotiation Dialogues

In plain words

A bot that negotiates a price has to make two decisions at every turn: what move to make (ask for a lower price, accept, insist) and how to word it. End to end neural models learn both at once from human chats. That makes the strategy hard to control, and when they are trained to win the game they often collapse into repeating the same sentence.

The paper separates the two jobs. Each sentence is first reduced to a short label that keeps only its high-level move, such as "propose this price". A manager chooses the next label. A generator then picks a human-written sentence that fits that label and the conversation so far. Because the manager works on labels, a developer can set the strategy directly, by training it on data, by rewarding it for a goal, or by writing rules.

The authors also collected a new dataset of buyer and seller chats about real Craigslist listings, which contain more varied language than earlier game-based datasets. In human chats, the modular systems were rated about as human-like as the end-to-end ones, and reinforcement learning on the labels avoided the repetition seen when reinforcement learning was applied to the words directly.

TL;DR

• A modular negotiation bot: a rule-based parser turns each utterance into a coarse dialogue act (intent plus arguments), a manager picks the next act, and a retrieval generator fills in the wording §3.2 §3.3 §3.5.
• Three ways to train the manager: supervised learning on human acts, policy gradient on the acts with utility, fairness or length rewards, and a hybrid that uses a learned intent sequence with hand-coded argument rules §3.4.
• Author-reported: act-level RL keeps human-likeness near the supervised systems while RL on words collapses. The paper reports this on the new CraigslistBargain (CL) data and on DealOrNoDeal (FB) tab. 7.
• The official code (MIT, Stanford NLP) is Python 2.7 and PyTorch 0.4 and differs from the paper in several training details listed under Paper vs code.

Problem

End-to-end neural dialogue models learn strategy and language together. The authors say this makes the strategy hard to control and interpret, and that reinforcement learning on the words tends to produce degenerate text, such as ungrammatical or repetitive utterances §1. Earlier negotiation datasets were collected in closed games with few objects, such as dividing books, hats and balls, or Settlers of Catan resources, which restricts the language used §2.

The authors assume that a coarse act is enough to capture the strategy, but not the meaning of an utterance. The generator therefore has to read the full dialogue history, not only the act §3.2.

Method

Scenario and task. Two agents negotiate the price of a real item from a Craigslist posting. The listing price is shown to both. The buyer also gets a private target price, set at 0.5, 0.7 or 0.9 times the listing price. Either agent can make an offer at any time, and the other can accept, reject or quit §2. The dataset was collected on Amazon Mechanical Turk §2 tab. 3.

Coarse dialogue acts (CDA). An act has an intent and a set of arguments, for example propose(price=15) for "I am willing to pay $15" §3.2. The authors use fewer than ten intents, and argument values are normalised and binned §3.4.

The system has three modules, run once per turn §3.2:

1. Parser: maps the partner's last utterance x_{t-1} to an act z_{t-1}, using the dialogue history and the scenario. It is deterministic and rule-based §3.3.
2. Manager: predicts the next act z_t from the past acts z_{<t} and the scenario c §3.4.
3. Generator: turns z_t into a sentence x_t using the full history x_{<t} §3.5.

Parser. It detects entities (prices, items) and matches keyword patterns. The rules are checked in an ordered list and the first matching intent wins. If no rule fires, the act is unknown §3.3. The intent rules are in tab. 5. Price detection and, for FB, item and count detection are in app. B.

Price detection (CL): a number counts as a price if it starts or ends with a dollar sign. Otherwise it counts if its neighbouring words appear next to known prices in the training data, and it is at most 1.5 times the listing price app. B.

Manager. Three variants §3.4:

• Supervised (SL). A sequence-to-sequence model with attention, trained by maximum likelihood on the parsed training dialogues. Each act is a token sequence, such as "offer 150". An LSTM encodes the partner's act and another decodes the agent's act. Hidden states are carried through the whole dialogue.

• Reinforcement learning (RL). The SL model is fine-tuned with a reward on the whole act sequence R(z_{1:T}). Three rewards are used:

  • Utility: linear in the final price. The buyer gets 1 at its target, the seller gets 1 at the listing price, and both get 0 when the final price sits halfway between the listing price and the buyer's target. The game is zero-sum. For FB, utility is the total value of the items the agent receives.
  • Fairness: the difference between the two agents' utilities.
  • Length: the number of utterances, which encourages long dialogues.

  The reward is -1 if no agreement is reached §3.4. The update is policy gradient with a baseline, given in eq. 1. Pseudocode is below.

• Hybrid. The intent is predicted by a trigram language model over intent sequences from the training data. The arguments are filled in by rules. For CL, the agent always splits the difference when it counter-proposes, rejects an offer worse than its bottomline and accepts otherwise §4.2. For FB, the agent keeps an estimate of the partner's utility and gives up the item with the lowest value of own utility minus partner utility. It also agrees when a proposal beats the previous one or its target §4.2.

Policy-gradient update §3.4 eq. 1. For a sampled trajectory with final reward r, the authors update the parameters with the log-likelihood of each generated token, weighted by (r - b). Here b is the average return so far, used for variance reduction. Equation 1 is printed with a minus sign in front of the learning-rate term. See Pitfalls: the code performs ascent on this objective.

# Policy-gradient fine-tuning of the manager  [§3.4] [eq. 1]
# Input:  manager parameters theta, fixed partner model, scenarios
# Output: fine-tuned theta

def finetune(theta, partner, scenarios, num_dialogues, lr):
    returns = []
    for episode in range(num_dialogues):
        # Self-play one dialogue; the learned agent emits acts z_1..z_T  [§4.3]
        scenario = sample_scenario(scenarios)
        acts, log_probs = rollout(theta, partner, scenario)
        # One scalar reward for the whole act sequence  [§3.4]
        reward = reward_fn(acts, scenario)
        returns.append(reward)
        # Baseline b: average of the returns seen so far  [§3.4]
        baseline = mean(returns)
        # Raise the log-probability of the sampled acts in proportion to
        # the advantage  [eq. 1]
        advantage = reward - baseline
        theta = theta + lr * advantage * grad_theta(sum(log_probs))
    return theta

Price normalisation for act models §4.2. Prices are rescaled so that the agent's target is 1 and its bottomline is 0. For a buyer, the scale runs from its private target (mapped to 1) down to the listing price (mapped to 0). For a seller, the listing price maps to 1 and 0.7 times the listing price maps to 0. The scaled values are rounded to two decimals and binned. In the code this is a linear map p' = (p - b)/(t - b) price_tracker.py price_tracker.py.

Generator. Retrieval-based generation §3.5:

• Each training utterance is stored as a tuple of its context template d(x_{t-1}), the previous act, its own template d(x_t) and its act z_t. Templates replace arguments with placeholders such as [price], which are filled at generation time.
• Given z_t, keep candidates whose intent matches both z_t and z_{t-1}.
• Rank them by the dot product of TF-IDF bag-of-words vectors of their context template and the current context.
• Sample one candidate from the top K, with probabilities from a trigram language model over the training templates. Sampling adds diversity.

# Retrieval-based generation of the reply to act z_t  [§3.5]
# Input:  act z_t, previous act z_(t-1), dialogue context text
# Output: a template with placeholders, e.g. [price]

def generate(act, prev_act, context_text, database):
    # Only candidates whose intents match z_t and z_(t-1) survive  [§3.5]
    candidates = [c for c in database
                  if c.intent == act.intent
                  and c.prev_intent == prev_act.intent]
    # Rank by TF-IDF dot product of the context template d(x_(t-1))
    # and the current context  [§3.5]
    scores = tfidf_dot(candidates, context_text)
    # Keep the top K candidates; K is not stated in the paper  [§3.5]
    top = top_k(candidates, scores, K)
    # Sample one, with probabilities from a trigram LM over the training
    # data, to encourage diversity  [§3.5]
    template = sample_by_trigram_lm(top)
    # Fill the placeholders from the act's arguments  [§3.5]
    return fill(template, act.arguments)

Models compared tab. 6:

The paper names the word-based systems SL(word) and RL(word), and the act-based ones SL(act) and RL(act). Its reward variants are shown as RL-utility, RL-fairness and RL-length §4.2.

Hyperparameters

The paper's own values are shown as stated. "Not stated" means the paper gives no value. Code values are from the official repository at code_commit, and the README command lines are the authors' documented settings.

Results

Author-reported. Setup: the new CL dataset of 6682 human-human dialogues §2 tab. 3, and the FB dataset of Lewis et al. (2017) §4.1. Nine systems were put online. AMT workers chatted with a bot or a human partner, and then rated the question "Do you think your partner demonstrated reasonable human behavior?" on a 1-to-5 scale, running from "not at all" to "definitely" §4.4. Agreement rate (Ag), utility (Ut), fairness (Fa) and length (Len) are also reported. Bold in human-likeness (Hu) marks the best score in a group with p < 0.05 by paired t-tests. The highlighted column in each RL group is the objective optimised tab. 7.

Source: tab. 7. Square brackets mark the objective each RL group optimised (the paper highlights these cells). The caption does not explain the "x vs. y" utility cells on FB.

Headline claims, author-reported:

• Supervised act models and supervised word models have no statistically significant difference in human-likeness §4.4 tab. 7. The paper contradicts itself on which matches human statistics better: the text says SL(word) matches dialogue length and utility better §4.4, while the caption says act-based models match human statistics better across all metrics tab. 7. Table 7 supports the text for length (7.8 for SL(word), 14.0 for SL(act), 10.2 for humans on CL).
• RL on words degenerates. On CL, the three most frequent sentences make up 81.6%, 100% and 100% of all utterances for the utility, fairness and length models §4.4.
• RL on acts optimises its reward while keeping reasonable human-likeness §4.4 tab. 7.
• The utility-optimised act model learned to insist and refuse to budge, which lowered its agreement rate. The hybrid model, which adds domain knowledge, reached high utility and human-likeness on both tasks §4.4 tab. 7.

Paper vs code

Official code: the CraigslistBargain part of the stanfordnlp/cocoa repository, linked from the paper's project page §4.1 (https://stanfordnlp.github.io/cocoa). Its LICENSE is MIT, copyright Stanford NLP, and the commit is 52fb2d47a28537c7892f146a8972a75bcde4812c. The FB word-based baseline uses Lewis et al.'s repository, which is not the authors' code and is not used here. Setup requires Python 2.7 and PyTorch 0.4 README.md.

Discrepancies found after reading the code (paper value first):

1. SL epochs. Paper: 20, with the lowest validation loss kept §4.3. README commands use 15 README.md README.md. Code default is 14 options.py.
2. Act-model depth. Paper: two-layer LSTM for both encoder and decoder, for both word and act models §4.3. The act-model README command sets no layer count, so the default of one layer applies README.md options.py. The word-model command uses two layers README.md.
3. GloVe for the act model. Paper: GloVe initialisation for both models §4.3. The act-model README passes empty pretrained vectors README.md.
4. No-agreement reward. Paper: -1 §3.4. Code: -0.5 rl_trainer.py (the same value is used for the fairness and length rewards rl_trainer.py rl_trainer.py).
5. Baseline and scaling. Paper: subtract the average return so far §3.4. Code: standardise the reward using the mean and standard deviation of all rewards so far, with the standard deviation floored at 1e-4 rl_trainer.py.
6. Discounting. Not in the paper. Code multiplies the reward by a discount factor for each step back from the end of the dialogue, default 1.0 (no discount) rl_trainer.py options.py.
7. Equation 1 sign. The paper prints \theta \leftarrow \theta - \eta \sum_i \nabla_\theta \log p_\theta(a_i \mid a_{<i}, c)(r - b) eq. 1. Read literally, that descends the reward-weighted log-likelihood. The code minimises the reward-weighted negative log-likelihood rl_trainer.py, which is ascent. The pseudocode above uses ascent.
8. Fairness reward. Paper: the difference between the two agents' utilities §3.4. Code: 2 - |u| for each role, where u is that role's margin reward rl_trainer.py. Both peak at the midpoint, but the values differ.
9. Length reward. Paper: the number of utterances §3.4. Code: the number of events, divided by 10 rl_trainer.py. Events include offers and other actions, not only messages.
10. Intent names. Table 5 names the intents propose, counter, inquire and intro tab. 5. The code uses init-price, counter-price, inquiry and intro parser.py. The agreement rule in the code is a set of anchored regular expressions parser.py parser.py. It has no "perfect" pattern, which is in the paper's list tab. 5.
11. Trigram intent model. Paper: trigram language model over intent sequences for the hybrid policy §4.2. README step 2 learns an n-gram model over dialogue acts for the hybrid policy README.md. The retrieval generator's trigram model is at generator.py.
12. Retrieval sampling. Paper: top K candidates, K not stated §3.5. Code: top 20 by default generator.py. Sampling from the trigram model is a softmax over log-probabilities with temperature T, and the rule-based session uses T = 10 rulebased_session.py. Retrieval also excludes templates already used in the session while unused ones remain generator.py.
13. Hybrid bottomline and compromise. Paper: split the difference when counter-proposing §4.2. Code: compromise fraction 0.5, which is the midpoint rulebased_session.py rulebased_session.py. The bottomline is estimated from the partner's offers or the listing price, not taken from the 0.7 times listing value used in scaling rulebased_session.py rulebased_session.py.
14. Price scaling. Matches the paper's description: bottomline maps to 0, target maps to 1, two decimals price_tracker.py price_tracker.py price_tracker.py.
15. RL sampling. RL self-play uses sampling with temperature 0.5, max length 20 and max 20 turns README.md. None of these values is in the paper.

I found no discrepancy in the reward definitions for utility (linear in the final price, zero at the midpoint, zero-sum) rl_trainer.py.

Pitfalls

• Invalid dialogues are not penalised. get_reward sets a -1 reward for invalid dialogues (more than one offer, quit, accept or reject, or an accept before any offer). The next branch on reward_func then overwrites that value, so the penalty never takes effect rl_trainer.py rl_trainer.py. Implement the penalty correctly if you rely on it.
• Equation 1 sign. Implement ascent on the advantage-weighted log-likelihood. Following the printed sign of eq. 1 literally minimises the reward.
• Standardised rewards change the effective scale. The code divides the advantage by a running standard deviation rl_trainer.py. The paper's learning rate of 0.001 is not stated with this scaling, so a direct port may behave differently.
• Two different bottomlines. The 0.7 times listing bottomline is used only to scale prices for the act model §4.2. The rule-based bottomline is estimated separately rulebased_session.py.
• Price rounding. Scaled prices are rounded to two decimals, then binned §4.2. When converting back to a dollar price, the code truncates with int() price_tracker.py.
• Degenerate RL on words. RL on words gives repetitive text even when reward goes up §4.4 tab. 7. The authors' evaluation model is itself an SL model trained on human-human dialogue, which the paper says may not match real human behaviour in human-bot chat §4.4.
• Utility RL is stubborn. RL utility on acts refuses to make compromises, which frustrated human partners and lowered agreement. The paper's remedy is the hybrid rule set, which adds a compromise §4.4.
• Length reward is loose. It counts events, not sentences, and is divided by 10 rl_trainer.py. Scale it against the other rewards before combining them.
• Unspecified RL training details. The paper does not state the RL optimiser, the sampling temperature, the discount, the gradient clipping, or the maximum turns. The README uses AdaGrad, temperature 0.5 and 20 turns README.md.
• Undefined tables. The "x vs. y" utility cells on FB tab. 7 are not explained in the caption.
• Environment. Python 2.7 and PyTorch 0.4 are required README.md. The data is distributed through a CodaLab worksheet linked from the README README.md. This card does not use or redistribute that data.
• Reproducing human results. The human evaluation requires AMT and the bots' online deployment. The paper's numbers cannot be checked from the released code alone.

Lineage

• Builds on: the goal-oriented dialogue pipeline with parser, manager and generator of Young et al. (2013), cited as the framework §3.2. Also the Hybrid Code Network §5, which keeps a neural dialogue state where this work keeps a structured one.
• Compared against: end-to-end word models and RL on words, following Lewis et al. (2017) §1 §4.2. The FB word-based baseline uses Lewis et al.'s implementation §4.2.
• Superseded by: not stated.