Reinforcement Learning for Spoken Dialogue Systems

Satinder P. Singh, Michael J. Kearns, Diane J. Litman, Marilyn A. WalkerNeurIPS 1999 · OpenReview

Introduction

Designing a "strategy" for a spoken dialogue system—deciding when the system should speak, when it should ask for clarification, or when it should just listen—has historically been an ad-hoc process. Designers often have to choose between "system initiative" (where the computer leads with menus) and "mixed initiative" (where the user speaks freely) based on intuition and limited trial-and-error.

The fundamental challenge is that dialogue is a complex, temporally dependent interaction. To optimize it using machine learning, researchers need a way to represent the "state" of a conversation. However, the true state includes the entire history of the dialogue, which is effectively infinite. This paper introduces a formal framework and a software tool called RLDS (Reinforcement Learning for Dialogue Systems) that treats spoken dialogue systems as Markov Decision Processes (MDPs). By applying reinforcement learning to real-world dialogue corpora, the authors demonstrate how to move away from ad-hoc design toward data-driven strategies that optimize for user satisfaction.

Methods: The RLDS Framework

The authors propose mapping the infinite history of a dialogue into a manageable, "approximately Markovian" state space that allows reinforcement learning (RL) algorithms to find optimal behaviors. The core innovation of RLDS is the use of a State Estimator (SE).

  1. State Estimation: Instead of using the entire dialogue history, the SE maps a dialogue into a simplified vector of features (e.g., "Does the system know the departure city?", "What is the average speech recognition confidence so far?").
  2. Empirical MDPs: By applying the SE to existing dialogue logs (passive corpora), the authors construct an "empirical MDP." This model estimates the probability of moving from one simplified state to another based on the system's actions.
  3. Value Iteration: Once the empirical MDP is built, the system uses standard RL value iteration to compute an optimal policy—a mapping from states to actions that maximizes a long-term reward, which in this context is usually user satisfaction.

This approach allows researchers to "browse" the data and see which system behaviors actually correlate with successful outcomes.

Datasets

The study utilizes two primary datasets gathered from systems built at AT&T Labs:

  • TOOT: A system for voice retrieval of Amtrak train schedules (146 dialogues).
  • ELVIS: A system for voice retrieval of electronic mail (227 dialogues).

These datasets include system actions, user utterances, speech recognition confidence scores, and crucially, user satisfaction surveys that serve as the "reward" signal for the RL agent.

Key Insights and Ideas

By analyzing the empirical MDPs, the authors uncovered several non-obvious insights about dialogue strategy:

  • Confirmation is King: In the TOOT experiments, the value function was more strongly influenced by the number of confirmed attributes than the number of obtained attributes. In other words, the system "knowing" the destination is less valuable than the system "knowing that the user knows the system knows."
  • Distress Features: The authors quantified the impact of "distress" (timeouts, help requests). They showed that even a single distress event significantly drops the expected "value" of the dialogue, providing a clear metric for where systems need the most improvement.
Value functions showing the impact of confirmed attributes (a) and distress features (b).
  • The "Optimal" Dialogue Length: The paper reveals a nuance in user preference regarding the length of an interaction. For the train schedule (TOOT), shorter was almost always better. However, for email (ELVIS), the data showed an "inverse U-shaped" curve. This suggests there is an appropriate, "optimal" length for certain tasks—too short might mean the task wasn't completed, while too long indicates a struggle.
Value functions demonstrating the relationship between the number of turns and task progress.
  • System Initiative Wins (For Now): Contrary to the hype around "natural" mixed-initiative systems, the RL analysis confirmed that system-led initiative actually resulted in higher user satisfaction for these specific tasks.

Key Results

The RLDS tool successfully derived "sensible" policies purely from data, without any prior knowledge of the system's goals. For example, in the TOOT domain, the learned policy correctly prioritized greeting the user, asking for missing information (Departure, Arrival, Date), confirming all information once gathered, and finally closing the dialogue.

Quantitatively, the researchers showed that their value functions were robust; even when they changed the reward function from "user satisfaction" to "task completion," the resulting optimal policies remained largely consistent.

Limitations and Future Work

The authors are transparent about several hurdles in applying RL to dialogue systems:

  • Data Sparsity: In large state spaces, many states are rarely visited in the corpora, making it impossible to draw strong conclusions about the "optimal" action in those specific scenarios.
  • The Markov Assumption: The approach relies on the State Estimator making the dialogue "approximately Markovian." If the SE misses a crucial piece of context from earlier in the conversation, the model's recommendations may be flawed.
  • Passive vs. Active Learning: This paper focuses on learning from existing logs (passive). The "holy grail" mentioned by the authors is the end-to-end automated synthesis of systems that learn and improve in real-time as they interact with users.

While the field hasn't reached that "holy grail" yet, RLDS serves as a powerful diagnostic tool for understanding the complex correlations within dialogue data and moving toward empirically grounded system design.

Summary updated

Abstract

Recently, a number of authors have proposed treating dialogue systems as Markov decision processes (MDPs). However, the practical application ofMDP algorithms to dialogue systems faces a number of severe technical challenges. We have built a general software tool (RLDS, for Reinforcement Learning for Dialogue Systems) based on the MDP framework, and have applied it to dialogue corpora gathered from two dialogue systems built at AT&T Labs. Our experiments demonstrate that RLDS holds promise as a tool for "browsing" and understanding correlations in complex, temporally dependent dialogue corpora.
BibTeX
@inproceedings{singh1999reinforcement,
  author = {Satinder P. Singh and Michael J. Kearns and Diane J. Litman and Marilyn A. Walker},
  title = {{Reinforcement Learning for Spoken Dialogue Systems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1999},
  url = {https://openreview.net/forum?id=HkEZnvW_br},
}
Figure