Elamur Research⌕
☰
home / papers / 2017 / Deal or No Deal? End-to-End Learning of Negotiation Dialogues

Deal or No Deal? End-to-End Learning of Negotiation Dialogues

Summary

The paper treats negotiation as a test bed for dialogue agents that must handle both language and strategic reasoning. Two parties with hidden, differing preferences must agree on a shared decision, and success is easy to score. The authors crowdsourced a dataset of human-human bargaining dialogues on Amazon Mechanical Turk. In each dialogue, two people split a pool of books, hats and balls through free-form chat. They first trained a GRU-based sequence-to-sequence model to imitate humans, with no annotated dialogue states. This model produced fluent text but gave in too easily. Two goal-driven improvements followed. The first is self-play reinforcement learning, interleaved with supervised updates so the language stays human-like. The second is dialogue rollouts, a decoding strategy that simulates full continuations of the conversation to estimate the expected reward of candidate utterances. Both made the agents stronger than the supervised baseline, including in negotiations with humans. Agents even learned deceptive tactics without being designed to. The work matters because it shows end-to-end agents can be optimized for goals, not just likelihood, and it releases code and data.

Key points

  • The dataset contains 5808 dialogues over 2236 unique scenarios. A held-out test set of 252 scenarios (526 dialogues) forces generalisation to new situations.
  • The task setup works as follows:
    • Each pool holds 5–7 items of 3 types.
    • Each player's item values sum to 10.
    • Conflicting final decisions give both players zero points.
    • After 10 turns, players may end without a deal, also worth zero.
  • Each dialogue becomes two training examples, one per participant's perspective. The model predicts both sides' tokens, so it can serve as a forward model for rollouts. An attention-based classifier predicts the final split.
  • The authors report this as the first case where reinforcement learning made an end-to-end goal-oriented dialogue agent perform better against human partners than its supervised counterpart. Combining RL with rollouts helped most.
  • Observed behaviours include feigning interest in worthless items in order to "concede" them later. A common error was opening with agreement and then making a counter-offer, which annoyed human partners. Code and data are released as facebookresearch/end-to-end-negotiator.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

81 papers of our library cite it (of the 140884 whose bibliographies we read); 10 of them have a page here, 71 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/d17-1259

@inproceedings{lewis2017deal,
  title = {{Deal or No Deal? End-to-End Learning of Negotiation Dialogues}},
  author = {Lewis, Mike and Yarats, Denis and Dauphin, Yann and Parikh, Devi and Batra, Dhruv},
  booktitle = {Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing},
  year = {2017},
  doi = {10.18653/v1/d17-1259},
  url = {https://doi.org/10.18653/v1/d17-1259}
}

References

38 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Nicholas Asher, Alex Lascarides, Oliver Lemon, Markus Guhe, Verena Rieser, Philippe Muller, Stergos Afantenos, Farah Benamara, Laure Vieu, Pascal Denis, et al. 2012. Modelling Strategic Conversation: The STAC project. Proceedings of SemDial, page 27. find
  2. Tim Baarslag, Katsuhide Fujita, Enrico H Gerding, Koen Hindriks, Takayuki Ito, Nicholas R Jennings, Catholijn Jonker, Sarit Kraus, Raz Lin, Valentin Robu, et al. 2013. Evaluating Practical Negotiating Agents: Results and Analysis of the 2011 International Competition. Artificial Intelligence, 198:73… find
  3. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014. Neural Machine Translation by Jointly Learning to Align and Translate. arXiv preprint arXiv:1409.0473. find our card
  4. Antoine Bordes and Jason Weston. 2016. Learning End-to-End Goal-oriented Dialog. arXiv preprint arXiv:1605.07683. find
  5. Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014. On the Properties of Neural Machine Translation: Encoder-decoder Approaches. arXiv preprint arXiv:1409.1259. find our card
  6. Heriberto Cuayáhuitl, Simon Keizer, and Oliver Lemon. 2015. Strategic Dialogue Management via Deep Reinforcement Learning. arXiv preprint arXiv:1511.08099. — [arXiv:1511.08099](https://arxiv.org/abs/1511.08099) find
  7. Abhishek Das, Satwik Kottur, Khushi Gupta, Avi Singh, Deshraj Yadav, José MF Moura, Devi Parikh, and Dhruv Batra. 2016. Visual Dialog. arXiv preprint arXiv:1611.08669. — [arXiv:1611.08669](https://arxiv.org/abs/1611.08669) find
  8. Abhishek Das, Satwik Kottur, José MF Moura, Stefan Lee, and Dhruv Batra. 2017. Learning Cooperative Visual Dialog Agents with Deep Reinforcement Learning. arXiv preprint arXiv:1703.06585. — [arXiv:1703.06585](https://arxiv.org/abs/1703.06585) find
  9. David DeVault, Johnathan Mell, and Jonathan Gratch. 2015. Toward Natural Turn-taking in a Virtual Human Negotiation Agent. In AAAI Spring Symposium on Turn-taking and Coordination in Human-Machine Interaction. AAAI Press, Stanford, CA. find
  10. Jesse Dodge, Andreea Gane, Xiang Zhang, Antoine Bordes, Sumit Chopra, Alexander H. Miller, Arthur Szlam, and Jason Weston. 2016. Evaluating Prerequisite Qualities for Learning End-to-End Dialog Systems. ICLR, abs/1511.06931. find
  11. Mehdi Fatemi, Layla El Asri, Hannes Schulz, Jing He, and Kaheer Suleman. 2016. Policy Networks with Two-stage Training for Dialogue Systems. arXiv preprint arXiv:1606.03152. find
  12. Chaim Fershtman. 1990. The Importance of the Agenda in Bargaining. Games and Economic Behavior, 2(3):224–238. find
  13. Milica Gašic, Catherine Breslin, Matthew Henderson, Dongho Kim, Martin Szummer, Blaise Thomson, Pirros Tsiakoulis, and Steve Young. 2013. POMDP-based Dialogue Manager Adaptation to Extended Domains. In Proceedings of SIGDIAL. find
  14. Jonathan Gratch, Zahra Nazari, and Emmanuel Johnson. 2016. The Misrepresentation Game: How to win at negotiation while seeming like a nice guy. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pages 728–737. International Foundation for Autonomous Agents… find
  15. H. He, A. Balakrishnan, M. Eric, and P. Liang. 2017. Learning Symmetric Collaborative Dialogue Agents with Dynamic Knowledge Graph Embeddings. In Association for Computational Linguistics (ACL). find
  16. Matthew Henderson, Blaise Thomson, and Jason Williams. 2014. The Second Dialog State Tracking Challenge. In 15th Annual Meeting of the Special Interest Group on Discourse and Dialogue, volume 263. find
  17. Simon Keizer, Markus Guhe, Heriberto Cuayáhuitl, Ioannis Efstathiou, Klaus-Peter Engelbrecht, Mihai Dobre, Alexandra Lascarides, and Oliver Lemon. 2017. Evaluating Persuasion Strategies and Deep Reinforcement Learning methods for Negotiation Dialogue agents. In Proceedings of the European Chapter o… find
  18. Levente Kocsis and Csaba Szepesvári. 2006. Bandit based Monte-Carlo Planning. In European conference on machine learning, pages 282–293. Springer. find
  19. Adam Lerer and Alexander Peysakhovich. 2017. Maintaining Cooperation in Complex Social Dilemmas using Deep Reinforcement Learning. arXiv preprint arXiv:1707.01068. — [arXiv:1707.01068](https://arxiv.org/abs/1707.01068) find
  20. Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. 2015. A Diversity-promoting Objective Function for Neural Conversation Models. arXiv preprint arXiv:1510.03055. find our card
  21. Jiwei Li, Will Monroe, Alan Ritter, Michel Galley, Jianfeng Gao, and Dan Jurafsky. 2016. Deep Reinforcement Learning for Dialogue Generation. arXiv preprint arXiv:1606.01541. find our card
  22. Chia-Wei Liu, Ryan Lowe, Iulian V. Serban, Michael Noseworthy, Laurent Charlin, and Joelle Pineau. 2016. How NOT To Evaluate Your Dialogue System: An Empirical Study of Unsupervised Evaluation Metrics for Dialogue Response Generation. In Proceedings of the Conference on Empirical Methods in Natural… find
  23. Junhua Mao, Xu Wei, Yi Yang, Jiang Wang, Zhiheng Huang, and Alan L. Yuille. 2015. Learning Like a Child: Fast Novel Visual Concept Learning From Sentence Descriptions of Images. In The IEEE International Conference on Computer Vision (ICCV). find
  24. Igor Mordatch and Pieter Abbeel. 2017. Emergence of Grounded Compositional Language in Multi-Agent Populations. arXiv preprint arXiv:1703.04908. — [arXiv:1703.04908](https://arxiv.org/abs/1703.04908) find
  25. John F Nash Jr. 1950. The Bargaining Problem. Econometrica: Journal of the Econometric Society, pages 155–162. find
  26. Yurii Nesterov. 1983. A Method of Solving a Convex Programming Problem with Convergence Rate O (1/k2). In Soviet Mathematics Doklady, volume 27, pages 372–376. find
  27. Olivier Pietquin, Matthieu Geist, Senthilkumar Chandramohan, and Hervé Frezza-Buet. 2011. Sample-efficient Batch Reinforcement Learning for Dialogue Management Optimization. ACM Trans. Speech Lang. Process., 7(3):7:1–7:21. find
  28. Verena Rieser and Oliver Lemon. 2011. Reinforcement Learning for Adaptive Dialogue Systems: A Data-driven Methodology for Dialogue Management and Natural Language Generation. Springer Science & Business Media. find
  29. Jason D Williams and Steve Young. 2007. Partially Observable Markov Decision Processes for Spoken Dialog Systems. Computer Speech & Language, 21(2):393–422. find
  30. Ronald J Williams. 1992. Simple Statistical Gradient-following Algorithms for Connectionist Reinforcement Learning. Machine learning, 8(3-4):229–256. find
  31. Alan Ritter, Colin Cherry, and William B Dolan. 2011. Data-driven Response Generation in Social Media. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 583–593. Association for Computational Linguistics. find our card
  32. Avi Rosenfeld, Inon Zuckerman, Erel Segal-Halevi, Osnat Drein, and Sarit Kraus. 2014. NegoChat: A Chat-based Negotiation Agent. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS ’14, pages 525–532, Richland, SC. International Foundation for Auton… find
  33. David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. 2016. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529(7587):484–489. find
  34. Satinder Singh, Diane Litman, Michael Kearns, and Marilyn Walker. 2002. Optimizing Dialogue Management with Reinforcement Learning: Experiments with the NJFun System. Journal of Artificial Intelligence Research, 16:105–133. find
  35. Victoria Talwar and Kang Lee. 2002. Development of lying to conceal a transgression: Children’s control of expressive behaviour during verbal deception. International Journal of Behavioral Development, 26(5):436–444. find
  36. David Traum, Stacy C. Marsella, Jonathan Gratch, Jina Lee, and Arno Hartholt. 2008. Multi-party, Multi-issue, Multi-strategy Negotiation for Multi-modal Virtual Agents. In Proceedings of the 8th International Conference on Intelligent Virtual Agents, IVA ’08, pages 117–130, Berlin, Heidelberg. Sprin… find
  37. Oriol Vinyals and Quoc Le. 2015. A Neural Conversational Model. arXiv preprint arXiv:1506.05869. find our card
  38. Tsung-Hsien Wen, David Vandyke, Nikola Mrksic, Milica Gasic, Lina M Rojas-Barahona, Pei-Hao Su, Stefan Ultes, and Steve Young. 2016. A Network-based End-to-End Trainable Task-oriented Dialogue System. arXiv preprint arXiv:1604.04562. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lewis-2017-deal-or-no-deal-end/