Source-linked AI summary
A Deep Reinforcement Learning Chatbot
Iulian V. Serban, Chinnadhurai Sankar, Mathieu Germain, Saizheng Zhang, Zhouhan Lin, Sandeep Subramanian, Taesup Kim, Michael Pieper, Sarath Chandar, Nan Rosemary Ke, Sai Rajeshwar, Alexandre de Brebisson, Jose M. R. Sotelo, Dendi Suhubdy, Vincent Michalski, Alexandre Nguyen, Joelle Pineau, Yoshua Bengio
TL;DR
Conversational agents remain a major unsolved AI problem, motivating MILABOT’s development for open-ended socialbot interaction. The system combines learned retrieval and generation models in an ensemble and uses reinforcement learning trained on crowdsourced and real-world interactions to select responses. In semi-final evaluation, its best system achieved a 3.15 average user score on a 1 −5 scale and substantially outperformed competing teams.
Problem
Building intelligent conversational agents for coherent, engaging open-domain interaction remains a major unsolved problem in artificial intelligence.
Method
MILABOT combines deep-learning retrieval and generation models in an ensemble and trains reinforcement-learning response selection on crowdsourced data and real-world interactions.
Results
3.15 average user score on a 1 −5 scale was achieved by the best system in semi-final A/B testing, substantially exceeding the average of competing teams.
Takeaways & Limitations
The system’s machine-learning architecture is likely to improve with additional data because nearly all components are learnable.
Takeaways & Limitations
The system does not condition its response models or selection policy on ASR confidence, despite speech-recognition errors affecting user experience.
Abstract
from arXiv · showhide
We present MILABOT: a deep reinforcement learning chatbot developed by the Montreal Institute for Learning Algorithms (MILA) for the Amazon Alexa Prize competition. MILABOT is capable of conversing with humans on popular small talk topics through both speech and text. The system consists of an ensemble of natural language generation and retrieval models, including template-based models, bag-of-words models, sequence-to-sequence neural network and latent variable neural network models. By applying reinforcement learning to crowdsourced data and real-world user interactions, the system has been trained to select an appropriate response from the models in its ensemble. The system has been evaluated through A/B testing with real-world users, where it performed significantly better than many competing systems. Due to its machine learning architecture, the system is likely to improve with additional data.
1 Introduction
MILABOT addresses conversational agents as an unsolved AI problem through a large-scale ensemble of deep learning and reinforcement learning models. Trained on crowdsourced data and real-world interactions, it achieved strong semi-final performance with real users.
- Motivation: MILABOT targets coherent, engaging conversation on popular topics through a spoken socialbot.The system was developed for the Amazon Alexa Prize competition.
- Architecture: The system combines recurrent, sequence-to-sequence, and latent variable models for natural language retrieval and generation.These models are combined into an ensemble that generates candidate dialogue responses.
- Training: Reinforcement learning selects appropriate responses from the ensemble using value-function and policy-gradient methods.The procedure is trained on crowdsourced data and interactions with real-world users.
- Evaluation: 3.15 average user score on a 1 −5 scale was achieved by the best semi-final system.Its performance was substantially better than the average of all competing teams.
- Evaluation: 14.5 −16.0 average dialogue turns were achieved, exceeding the averages of all semi-final teams and finalist teams.The paper connects this higher number of back-and-forth exchanges with greater system engagement.
2 System Overview
MILABOT uses a largely statistical, ensemble-based architecture with few hand-crafted states and rules. Its dialogue manager generates candidate responses, applies selection logic, and does not generally use ASR confidence information.
- System architecture: The architecture relies primarily on statistical machine learning rather than enumerating hand-crafted states and rules.The authors describe this as using as few assumptions as possible about understanding and generating natural language.
- Response ensemble: The response-model ensemble combines independent sub-models that generate natural-language responses across diverse topics and strategies.Response models may also provide scalar confidence values.
- Dialogue manager: The dialogue manager takes dialogue history and ASR confidences, generates candidate responses, and then applies response-selection steps.The overall process is illustrated by the dialogue manager control flow.
- ASR handling: ASR confidences are used only below a threshold to request repetition and are otherwise ignored by response models and the selection policy.The paper identifies conditioning on ASR confidence as a plausible avenue for improvement.
3 Response Models
MILABOT’s response layer contains many specialized models spanning templates, retrieval, generation, factual question answering, and conversation initiation. These models produce candidate responses using rules, external knowledge sources, or learned classifiers.
- Model inventory: 22 response models include retrieval-based and generation-based neural networks, knowledge-base question answering, and template-based systems.The models are intended to cover diverse topics and response strategies.
- Template-based models: Template models use string matching, AIML templates, reflections, and predefined conversation-starting phrases.Initiatorbot asks open-ended questions, while Storybot responds to explicit story requests.
- Knowledge-base question answering: Evibot answers direct questions by querying Amazon’s Evi service and retrying with entity-based and non-entity subqueries when needed.Valid answers to wh-questions receive priority status.
- Knowledge-base question answering: BoWMovies identifies movie entities and query tags by string matching or embedding similarity before retrieving data through APIs.Its predefined templates are limited by the information available through those APIs.
- Learned response scoring: A logistic regression classifier was trained on 12, 000 annotated user-utterance and candidate-response pairs scored for appropriateness on a 1 −5 Likert-type scale.The utterances came from interactions with a preliminary system, and candidate responses were sampled from BoWEscapePlan.
4 Model Selection Policy
The dialogue manager treats response selection as reinforcement learning over dialogue histories, balancing immediate and long-term user satisfaction. It compares value-based and stochastic policies while handling state-dependent candidate sets.
- Policy objective: The selection policy must trade off immediate satisfaction against satisfaction over the entire dialogue.A response that pleases the user for one turn may create later disappointment if it limits subsequent conversation.
- Reinforcement learning formulation: At each turn, the agent observes dialogue history, chooses one of K candidate responses, receives a reward, and transitions to the next history.Its objective is to maximize the discounted sum of rewards, with γ ∈(0, 1] as the discount factor.
- Setting-specific issue: The candidate action set changes with dialogue history because response models are history-dependent and nondeterministic.This differs from reinforcement learning settings with a fixed action set for each state.
- Action-value policy: The action-value policy estimates expected return for each candidate and selects the response with the highest expected return.The scoring model is shared with the corresponding policy parametrization.
- Stochastic policy: A stochastic policy samples responses from a temperature-controlled distribution, while its greedy form selects the highest-probability action.Higher temperature produces a more uniform action distribution.
4.1 Input Features
The scoring model represents dialogue history and candidate responses with handcrafted and embedding-based features, then uses a five-layer neural architecture to produce response scores. The design favors computational efficiency, while deeper contextual encoders were excluded because of data and latency constraints.
- The model computes 1458 features from dialogue history and candidate responses using embeddings, dialogue acts, part-of-speech tags, word overlap, and model-specific signals.
- Embedding features summarize the candidate response, recent user utterances, and dialogue context using averages and embedding-similarity metrics.
- Binary lexical features indicate intensifiers in the user utterance and selected word, negation, or non-stop-word properties of candidate responses.
- RNN- and ConvNet-based feature encoders were ruled out for the competition because they lacked sufficient training data and could exceed the 150ms execution-time limit.
- The five-layer network maps the 1458 inputs through 500 and 20 hidden units, five softmax label probabilities, and a scalar output, with a skip connection.
- Deeper and shallower alternatives performed worse than the selected architecture, although alternative architectures remain future work.
4.3 Supervised AMT: Learning with Crowdsourced Labels
Supervised AMT trains the scoring model from crowdsourced appropriateness labels to predict response-quality classes and initialize later learning approaches. On held-out AMT data, it correlated with human scores and shifted selections toward higher-rated responses than baseline policies, while substantial low-rated selections remained.
- Supervised AMT learns the action-value scoring model from crowdsourced labels and initializes the later scoring approaches.
- AMT evaluators rate four candidate responses for overall appropriateness on a 1–5 Likert-type scale, where 1 is inappropriate and 5 is excellent.
- The annotation setup focuses on overall appropriateness rather than fluency or topical relevance, because most retrieved responses are already fluent and relevance is not evaluated.
- 199,678 labels were collected and split into 137,549 training, 23,298 development, and 38,831 test labels.
- Cross-entropy training predicts the five AMT classes, while the final scalar layer is fixed to scores 1.0 through 5.0 for very poor through excellent.
- 0.40 Pearson correlation and 0.38 Spearman correlation were achieved by Supervised AMT on the AMT test set, with mean squared error also substantially reduced relative to the Average Predictor.
- ~30% fewer very poor responses and ~8% excellent responses distinguish Supervised AMT from Random, with the excellent rate more than double that of each baseline.
- ~46% of Supervised AMT responses remained very poor or poor, leaving room to improve both the scorer and the candidate-response models.
4.4 Supervised Learned Reward: Learning with a Learned Reward Function
Supervised Learned Reward replaces fixed AMT-label scores with a model trained to predict Alexa user scores, then uses those predictions to train the scoring model. The learned reward model modestly improves prediction error over an average-score baseline but has low rank correlation.
- Learned Reward Function: The reward model predicts Alexa user scores from dialogue-history and candidate-response features, directly modeling the return the system seeks to maximize.It uses 23 higher-level features because training data is scarce.
- Learned Reward Function: The model is trained by minimizing squared error between predicted and observed dialogue returns, using L2 regularization selected on a hold-out set.Observed returns are optional Alexa scores in the range 1−5, including decimal scores.
- Limitations: Reward-model training excludes dialogues without Alexa user scores, introducing bias because users who abstain may have found the system poor or incomplete.The text explicitly identifies this as a significant bias in the reward model.
- Model Training: A five-model bagging ensemble averages linear regression outputs to improve data efficiency when training the reward model.The shuffled datasets use non-overlapping sub-hold-out sets for hyperparameter selection.
- Evaluation: 0.96 mean squared error and 0.19 Spearman correlation are achieved against real Alexa-user scores, versus 0.99 error and zero correlation for the average-score baseline.The authors attribute the low correlation partly to the small training set and high variance in user scores.
- Policy Training: The action-value model is initialized from Supervised AMT and fine-tuned against learned reward outputs rather than trained from scratch.This initialization is used to prevent overfitting.
4.5 Off-policy REINFORCE
Off-policy REINFORCE learns response-selection policies from recorded dialogues while correcting for the behavior policy. The method addresses high-variance updates with truncated importance weights and reward shaping, but truncation introduces bias.
- Policy Learning: Off-policy REINFORCE updates a softmax policy from recorded dialogue histories, actions, and dialogue returns using policy-gradient learning.The policy is initialized from Supervised AMT and trained with stochastic gradient descent using Adam.
- Off-policy Correction: The importance-weight ratio corrects for the discrepancy between the learned policy and the behavior policy that collected the data.It up-weights examples likely under the learned policy and down-weights examples unlikely under it.
- Variance Control: High-variance full-trajectory importance products are truncated to the current time step, reducing variance at the cost of bias.The paper describes truncation as also acting as a regularizer.
- Reward Shaping: Reward shaping assigns intermediate rewards using subsequent user sentiment to reduce the variance of updates based only on end-of-dialogue returns.The method addresses the problem that terminal returns update all intermediate actions with limited data.
- Evaluation: Estimated episode length is an orthogonal evaluation metric obtained by replacing each per-step reward with 1.0.This estimate excludes turns with priority responses because the agent has no action to take there.
4.6 Off-policy REINFORCE with Learned Reward Function
This approach combines Off-policy REINFORCE with the learned reward model by replacing per-step rewards with learned reward estimates. The same learned rewards are used for training and evaluation.
- Reward Construction: The learned reward model computes a new reward estimate at every time step for each dialogue.The estimate uses the model output except when the next user utterance has negative sentiment.
- Integration: The learned reward estimates are substituted into the Off-policy REINFORCE training and evaluation equations.This combines the learned reward and policy-gradient approaches within the same procedure.
- Training: The policy is initialized from Supervised AMT and trained with mini-batch stochastic gradient descent using Adam on the same dialogue split as Off-policy REINFORCE.Only weights related to the second-last layer are trained to reduce overfitting risk.
4.7 Q-learning with the Abstract Discourse Markov Decision Process
The Abstract Discourse MDP addresses the difficulty of estimating open-domain dialogue dynamics by modeling a compact abstract state and learning policies through simulation. Q-learning with experience replay trains the resulting policy.
- Bias-Variance Trade-off: The approach targets the bias-variance trade-off: learned-reward methods reduce bias but increase variance, while truncated importance weights remain biased.The proposed simulation-based method is presented as a way to trade off these sources of error.
- Motivation: Estimating a full open-domain conversational MDP is difficult because it requires learning next-utterance transitions and other complex dialogue dynamics.The paper motivates an abstract model as an alternative to naively estimating a full MDP from recorded dialogues.
- Abstract Discourse MDP: The Abstract Discourse MDP represents each dialogue state with a compact discrete variable covering dialogue act, user sentiment, and generic utterance status.The state omits topical information and can be expanded with other discrete or real-valued variables.
- Abstract Discourse MDP: The model samples a dialogue history matching the abstract state, selects a response with the policy, samples an appropriateness label and reward, then transitions to a new abstract state.The transition model uses multilayer perceptrons with response-class and user-state features.
- Data and Evaluation: The recorded-history set grows as the system is deployed, allowing the non-parametric model to incorporate additional data over time.Training and evaluation use disjoint history sets to reduce overfitting to the finite training histories.
- Policy Training: Q-learning with experience replay learns the policy in the simulated MDP using a memory buffer and ε-greedy exploration.The policy is trained and evaluated in alternating blocks of 100 episodes.
4.8 Preliminary Evaluation
The preliminary evaluation compares learned response-selection policies with heuristic baselines using human labels, off-policy estimates, simulations, and model-selection behavior. Learned policies generally outperform heuristics, while Q-learning AMT and Off-policy REINFORCE exhibit distinct risk and selection strategies whose interpretation is limited by biased evaluation.
- AMT Evaluation: Three learned policies significantly outperform Alicebot and Evibot + Alicebot on mean human score, with the difference amplified on the difficult test set.Q-learning AMT, Supervised AMT, and Off-policy REINFORCE perform overall equally well, while Q-learning AMT has higher standard deviations on both test sets.
- Off-policy Evaluation: 2.45 expected Alexa user score makes Off-policy REINFORCE 17.8% better than Q-learning AMT in biased off-policy evaluation.The estimator is biased because importance weights are truncated, and Off-policy REINFORCE was trained specifically to maximize this biased estimator.
- Response Model Selection Frequency: Off-policy REINFORCE strongly prefers generic Alicebot responses, indicating a highly risk-averse strategy.Alicebot responses are described as among the safest and most topic-dependent, generic responses in the system.
- Response Model Selection Frequency: Q-learning AMT has the strongest preference for Initiatorbot, potentially reflecting a system-initiative strategy that requires further analysis.The proposed strategy involves maintaining conversational control by asking questions and changing topics.
- Abstract Discourse MDP Evaluation: 43.24 average dialogue length is achieved by Off-policy REINFORCE in Abstract Discourse MDP simulations, while Random performs worst across all metrics.Q-learning AMT matches Supervised AMT at −0.15 average reward per time step, whereas Off-policy REINFORCE achieves −0.16.
- Response Model Selection Frequency: Q-learning AMT often replaces generic Alicebot and VHREDSubtitle selections with richer BoWFactGenerator, Initiatorbot, and VHREDRedditSports responses.There were 347 instances where Supervised AMT selected Alicebot but Q-learning AMT selected BoWFactGenerator, supporting a more risk-tolerant strategy.
5 A/B Testing Experiments
A/B tests found that reinforcement-learning dialogue policies, especially Q-learning AMT and Off-policy REINFORCE, outperformed supervised and heuristic alternatives across user scores, engagement, and response coherence. Results varied across experiments and user populations, but Q-learning AMT was ultimately identified as the better overall policy.
- Policy comparisons: 3.15 average user score made Q-learning AMT significantly better than all other policies and above the 2.92 semi-finals team average.The result was statistically significant at the 95% level using a one-tailed two-sample t-test.
- Policy comparisons: 37.51 average dialogue turns made Off-policy REINFORCE the most engaging policy, although it also produced slightly more negative-sentiment user utterances than Q-learning AMT.The semi-finals averages were 22 turns for all teams and 26 for finalist teams.
- Length analysis: Q-learning AMT performed better across nearly all dialogue-length intervals and showed excellent performance in long dialogues.It was better than the other policies in every interval except the medium-short interval of 10−19 turns, while some alternatives performed well only for short dialogues.
- Topical specificity and coherence: Q-learning AMT achieved significantly higher scores on both word-overlap metrics and on the average number of noun phrases per system utterance.These metrics indicate the highest topical coherence and the most topic-specific system responses among the six policies.
- Cross-experiment results: Across later experiments, the leading policy varied: Off-policy REINFORCE scored 3.06 versus 2.92 for Q-learning AMT in one test, while Q-learning AMT scored 3.06 versus 3.03 later.Neither difference was statistically significant, and changing user profiles and expectations may have contributed to the variation.
- Policy comparisons: Q-learning AMT and Off-policy REINFORCE substantially outperformed supervised-learning and heuristic policies in dialogue-manager evaluations.The overall discussion attributes gains to selecting among responses generated by multiple models using reinforcement-learning policies.
6 Related Work
Prior dialogue-system research explored reinforcement learning through simulated users, raw-text generative policies, and crowdsourced rewards. MILABOT instead proposes a non-parametric Abstract Discourse MDP that repeatedly reuses collected training data during policy training.
- Earlier dialogue research modeled conversation as sequential decision-making through Markov decision processes, especially for goal-oriented systems.
- Many reinforcement-learning approaches trained dialogue policies in simulations using abstract dialogue states and actions.
- Crowdsourced reward functions improved both response appropriateness and conversational depth in dialogue systems.
- Recent work learned generative neural policies directly from raw text through user simulations, requiring language understanding and generation.
- MILABOT’s Abstract Discourse MDP is non-parametric and repeatedly uses collected training data during policy training, unlike approaches that discard it after collection.
7 Future Work
Future work targets personalization and robustness to speech-recognition and turn-taking errors. The authors plan to use user information and embeddings while evaluating alternative policies through text-based interaction.
- Personalization is a future direction based on modeling each user’s personality, opinions, and interests.
- The planned personalization system would retrieve user attributes from a database using a user identifier to adapt response models.
- Future user embeddings could provide response models with context beyond the immediate dialogue history.
- Speech-recognition errors may particularly affect the system because it supports open-ended conversations without directing users toward canned keywords.
- Text-based evaluation on Amazon Mechanical Turk is planned to test policies while reducing speech-recognition and turn-taking errors.
8 Conclusion
The paper presents MILABOT as a large-scale ensemble dialogue framework combining deep learning and reinforcement learning. In competition evaluation, it achieved higher user scores and longer conversations than competing-team averages.
- MILABOT combines retrieval and generation models with a novel reinforcement-learning procedure in a large-scale ensemble framework.
- 3.15 average user score on a 1 −5 scale was substantially above the 2.92 average of all semi-final teams.
- 14.5 −16.0 turns per conversation was substantially above the averages of all teams and finalist teams.