Autonomous Sub-domain Modeling for Dialogue Policy with Hierarchical Deep Reinforcement Learning

Giovanni Yoko Kristianto, Huiwen Zhang, Bin Tong, Makoto Iwayama, Yoshiyuki KobayashiEMNLP 2018

TL;DR

This paper introduces a novel framework for dialogue systems that can autonomously discover and learn policies for sub-tasks within a larger, composite dialogue. By combining hierarchical reinforcement learning with proto-value functions, their approach reduces the need for manual sub-domain definition, leading to more efficient and competitive dialogue agents.

What Problem Does This Paper Address?

Modern dialogue systems often need to handle complex, multi-step tasks like booking a hotel, which can be broken down into smaller sub-tasks (e.g., searching for a hotel, booking a room, making a payment). Traditionally, solving these "composite tasks" involved manually defining these sub-tasks and their associated policies. This manual process is labor-intensive and limits the adaptability of dialogue systems to new domains. The challenge is to create dialogue agents that can automatically identify these sub-tasks and learn how to execute them, and crucially, how to transition between them, without human intervention. This is particularly difficult because flat reinforcement learning methods struggle with the increased complexity and sparse rewards of composite tasks.

Methods

The core of the proposed solution is a Hierarchical Reinforcement Learning (HRL) framework that autonomously discovers sub-domains. This is achieved by integrating two key techniques:

  • Option-Critic (OC) Architecture: This is a gradient-based RL approach that learns both intra-option policies (how to complete a sub-task) and termination conditions for those options. It allows the agent to learn from interactions with the environment.
  • Proto-Value Functions (PVFs): PVFs are learned representations that capture the "geometry" of the state space. The authors leverage PVFs to discover meaningful sub-domains. Specifically, they construct an adjacency matrix of state transitions and use eigen-decomposition to identify eigenvectors that correspond to intrinsic reward functions. These functions implicitly define options, guiding the agent towards states that represent sub-task completion or transitions.

The framework, dubbed HRL-OC_PVF, combines these by using PVFs to provide intrinsic rewards that guide the HRL-OC learning process. This allows the agent to learn not only how to complete sub-tasks but also how to discover them in the first place. They also compare this to a baseline HRL-OC that doesn't use PVFs for option discovery.

Datasets

The experiments were conducted using a simulated hotel reservation domain. This domain was set up as a Markov Decision Process (MDP) with specific characteristics:

  • State: 239 dimensions capturing user intents and requestable slots.
  • Actions: 44 dialogue actions (8 slot-independent, 36 slot-dependent).
  • Reward: -1 per turn, 0 or 20 at dialogue end (success/failure).
  • Discount Factor: 0.95.
  • Max Turns: 30.

A user simulator was employed, which randomly sets goals for hotel searching, booking, or payment, and can simulate realistic user behavior like not specifying all slot values or specifying them in a random order.

Key Insights and Ideas

  • Autonomous Sub-domain Discovery is Crucial: The paper strongly suggests that manually defining sub-domains is a bottleneck. Their autonomous approach shows promise in overcoming this.
  • PVFs Enhance Sub-domain Meaningfulness: Integrating PVFs into the HRL-OC framework led to the discovery of sub-domains that better align with the user's inherent sub-task structure, as evidenced by a smaller average turn distance between user sub-domain activation and agent sub-domain switching.
  • Intrinsic Rewards Alone Aren't Enough: Frameworks like HRL-DQN and HRL-PG_DQN, which relied solely on general-purpose intrinsic rewards for exploration without optimizing for extrinsic rewards, performed worse than flat RL baselines. This highlights the importance of optimizing for the ultimate dialogue goal.
  • Option Discovery vs. Option Learning: HRL-OC focuses on learning policies for pre-defined options, while HRL-OC_PVF aims to discover these options. The latter is more challenging but offers greater autonomy.
  • The "Curse of Dimensionality" in Dialogue: Flat RL methods struggle with the exponentially growing state and action spaces in complex dialogues, making HRL a more suitable approach.

Key Results

  • The proposed HRL-OC framework achieved a success rate (SR) of up to 73.4%, significantly outperforming flat RL baselines (DQN: 66.9%, PG: 62%).
  • HRL-OC_PVF (with α=0.2) showed more meaningful sub-domain discovery, with an average turn distance of 2.5-3.0 between user and agent sub-domain activation, compared to 2.8-5.3 for HRL-OC.
  • The autonomous HRL-OC framework was competitive with manually defined sub-domain approaches like HRL-GP (84.8% SR), achieving 73.4% SR.
  • Learning curves indicated that HRL-OC and HRL-OC_PVF had steeper learning curves than HRL-GP, suggesting a shorter learning time.
  • The optimal number of discovered options was found to be 2 or 3; using too many options proved detrimental.
  • The interpolation ratio α for combining extrinsic and intrinsic rewards had a complex effect, with PVFs seeming ineffective for SR when α > 0.

Limitations and Future Work

  • Fixed Sub-domain Order: The current simulator enforces a fixed order of sub-domains (hotel search -> booking/payment). The authors acknowledge that real-world conversations might involve interleaved or non-fixed sub-domain execution, which their framework hasn't been fully tested on.
  • Interleaved Sub-domains: A challenging situation to investigate further is when users frequently switch sub-domains before completing the current one.
  • PVF Construction: Future work could explore adjustments to PVF construction, including distance metrics, adjacency matrix creation, and the use of successor representations.
  • Reusability of Learned Options: Investigating the effectiveness of reusing learned options in other related dialogue domains is a promising direction.

Summary updated

BibTeX
@inproceedings{kristianto2018autonomous,
  author = {Giovanni Yoko Kristianto and Huiwen Zhang and Bin Tong and Makoto Iwayama and Yoshiyuki Kobayashi},
  title = {{Autonomous Sub-domain Modeling for Dialogue Policy with Hierarchical Deep Reinforcement Learning}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2018},
}
Figure