Rescue Conversations from Dead-ends: Efficient Exploration for Task-oriented Dialogue Policy Optimization (2024)

Abstract: Training a task-oriented dialogue policy using deep reinforcement learning is promising but requires extensive environment exploration. The amount of wasted invalid exploration makes policy learning inefficient. In this paper, we define and argue that dead-end states are important reasons for invalid exploration. When a conversation enters a dead-end state, regardless of the actions taken afterward, it will continue in a dead-end trajectory until the agent reaches a termination state or maximum turn. We propose a Dead-end Detection and Resurrection (DDR) method that detects dead-end states in an efficient manner and provides a rescue action to guide and correct the exploration direction. To prevent dialogue policies from repeating errors, DDR also performs dialogue data augmentation by adding relevant experiences that include dead-end states and penalties into the experience pool. We first validate the dead-end detection reliability and then demonstrate the effectiveness and generality of the method across various domains through experiments on four public dialogue datasets.

## introduction task-oriented dialogue (tod) systems are designed to help users perform a specific task (also referred to as the user goal), such as booking a restaurant or movie ticket @xcite . typically, tod systems are built on a structured database (db) containing many task-related entries, where entries are potential solutions to the task at hand @xcite . every entry of db is represented in terms of a set of attributes (known as slots) and their values. for example, in the movie domain, slots for the movie entry include movie name, theater, and date. in order to interact with users, tod systems require a dialogue policy (dp) that determines how the system should reply to the user's input @xcite . a wellperforming dp is expected to gather as much user requirements as possible in as few dialogue turns as possible and, by using these requirements as constraints, to find matching entries in the db to accomplish user goals @xcite . according to tod system construction, dp operates in two ways: through pipeline or end-toend architectures. pipeline architecture separates dp from natural language understanding, dialogue state tracking, and natural language generation modules @xcite . end-to-end architecture integrates all or some of these modules into one sequence-to-sequence task but raises concerns about interpretability and controllability @xcite . in this paper, we focus on pipeline-based architecture with better controllability. partially observable markov decision process provides a natural way of modeling tod, where the dp is often optimized using deep reinforcement learning @xcite . however, in many real-world dialogue scenarios, transition probabilities or rewarding transitions are not known in advance, such that dialogue agents usually require extensive exploration of the environment @xcite . some of these explorations are valid, and some are not, and the more invalid explorations there are, the less effective learning of dialogue policies becomes @xcite . a dialogue segment constitutes an invalid exploration due to the effect of task: when a user wants to book two tickets for the movie 'creed' for tomorrow in the la city and requests to know the theater that runs the movie creed. we may get the following dialogues (where u represents the user and s represents the system). example 1 example 2 u0: which theater will creed run? u0: can i get some tickets for creed? s1: which city would you like? s1: how many tickets do you need? u2: i want to watch at la. u2: i want 2 tickets, please! s3: how many tickets do you need? s3: what date would you like to watch it? u4: i want 2 tikets please! u4: tomorrow. s5: what city would you like? s5: carmike summit 16 is available. u6: la (slot and value error from (decision failures: inform the highest upstream modules: 'la' is misrecognized count in the database) as 'ca') u6: could you help me to book the s7: sorry, there is no ticket available. tickets? u8: can i get two tickets? s7: okay, you purchase of 2 tickets at s9: do you have any constraints on the carmike summit 16 for creed today at price? la is confirmed. u10: i do not care. u8: oh, sorry! this is the wrong tickets! s11: do you want to purchase the tickets? s9: yes, please! u12: yes, i want. u10: i want to set it up tomorrow. s13: oh sorry, there is no ticket available. s11: date is not available! .... .... by having a trajectory of unnecessary interactions, which makes it more difficult for the dialogue agent to learn which responses are bad among a lengthy dialogue. this paper defines dead-end states and introduces a dead-end detection and resurrection (ddr) method. ddr efficiently identifies deadend states and provides rescue actions to guide exploration. by mitigating the adverse effects of dead-ends, ddr enhances exploration efficiency and generates more diverse training samples. specifically, we define a reliable dead-end detection criterion for tod systems. the state is considered a dead-end state if all trajectories starting from this state fail with probability one after a pre-defined number of dialogue turns. once a certain dead-end is detected, a rescue module in ddr is activated, which transfers the current dead-end state to the previous safe state and provides rescue guidance. ddr comprises two types of rescue guidance: one that provides explicit rescue actions with maximum information gain (figure 1b ) and the other blocks incorrect paths, enabling diverse exploration (figure 1c ). we conducted extensive experiments to evaluate the advantages and applicability of the two types of rescue guidance. to prevent repetitive mistakes, we employ a dialogue data augmentation (dda) module, introducing an experience pool with warning experiences, which consist of dead-end states and associated penalties. the effectiveness of ddr was validated on four public datasets, demonstrating its robustness even in noisy environments. notably, ddr is a model-agnostic algorithm applicable to various rl-based dp methods. in summary, our contributions are as follows: learning efficiency. our work connects to several research attempts to apply rl to learn dialogue policies for tod systems. we touch on the research works aiming to make rl learning efficient by improving sample efficiency through i) generating effective exploration strategies, and ii) manipulating generated training samples. type i: research in the field of rl has developed many studies on general and effective exploration strategies to address the issue of sample efficiency, e.g., the -greedy @xcite , boltzmann exploration @xcite , upper confidence bounds @xcite , and gaussian exploration @xcite . given that both our ddr and baseline methods have the potential to combine with these exploration strategies, resulting in a more efficient learning process, we conduct comparisons in our experiments based on the same exploration strategy for all baseline methods, rather than directly comparing with exploration strategies. type ii: some rl studies applied to tod policies improve sample efficiency by manipulating the training samples. companion learning introduced by @xcite provides necessary guidance for dialogue policies, but it also transfers the training burden to the design of the teacher model @xcite . hindsight experience replay (her) @xcite extracts partial success segments from failed dialogues to synthesize successful artificial dialogues, but the quality of synthetic experience impacts her's effectiveness @xcite . trainable-action-mask (tam) @xcite learns action masks to block ineffective actions for generating more informative samples. loop-clipping policy optimisation (lcpo) @xcite clips useless trajectories to improve sample efficiency. however, both lcpo and her may involve artificial synthesis and parameter tuning, leading to potential limitations in generating diverse and high-quality dialogues. essentially, they only process the dialogue segments after the conversation ends, while our ddr detects and fixes the dialogue during the conversation. besides the above methods, there are non-deep learning-based planning methods for dialogue management @xcite @xcite . these approaches utilize domain knowledge to organize domain actions in a rational order, aiming to recover from misunderstandings. however, planning-based approaches, while successful in certain domains, often lack scalability and rely on expert-designed heuristics. in contrast, our method avoids these challenges, distinguishing it fundamentally from the mentioned approaches. dead-end. @xcite introduced and formalized the theory of dead-ends in stochastic shortest path mdps. subsequently, @xcite extended this theory to the atari gaming domain, introducing the concept of deadends along with corresponding safety conditions. in their work, undesirable terminal states were identified as dead-ends, representing situations where the game agent is compelled to terminate or restart before achieving its goals. additionally, @xcite introduced concepts related to dead-ends, with a primary focus on policy evaluation. they proposed the notion of feasible states-the states in which the agent has a non-zero probability of achieving success according to an optimal policy and does not face immediate defeat. our definition of dead-ends draws inspiration from the aforementioned studies and applies it to the domain of tod. it should be noted that due to unique characteristics in different domains, these studies are not applicable in the dialogue domain. in the dialogue domain, @xcite proposed a simple solution (rdpm) to deal with dead-ends by relaxing one of the user's constraints as unknown. this approach heavily relies on manual intervention to select acceptable alternatives and cannot learn from past dead-end experiences. consequently, it often faces recurring dead-end problems repeatedly and is limited to simple dialogue scenarios. in contrast, our approach can automatically evaluate and select appropriate recovery actions. in hierarchical reinforcement learning with guidance (hrlg), a related concept of confounded state was introduced, representing a situation within a dialogue where the same state appears three or more times @xcite . this differs from our notion of a dead-end state. we concentrate on the states where, if the dialogue continues from that state, it inevitably fails (invalid explorations), regardless of the chosen actions. in such cases, actions and states are not necessarily repeated. in other words, dead-end states cover the confounded states, but not vice versa. 2 additionally, hrlg focuses on multi-domain dialogue tasks rather than invalid exploration issues. ## method as illustrated in figure 2 , ddr consists of three main stages: 1) dead-end detection process automatically detects whether the current conversation with the original action a o leads to a dead-end. if so, 2) rescue process transfers the current dead-end state back to the previous safe state and provides a rescue action a r as the system action a s for the response. and 3) dialogue data augment process is performed by adding a warning experience containing this dead-end state and warning penalties into the experience buffer to prevent the dialogue policy from repeatedly making the same mistake. if a o does not lead to a dead-end state, a o is transferred directly to the user simulator as a a s without rescue and dialogue data augment stages. these stages are described in detail in the following subsections. foot_1 ## experiments our experiments have five objectives: i) verifying the effectiveness of our ddr in simulated (section 4.4) and human (section 4.9) experiments; ii) investigating the advantages and applicability of two rescue modules (section 4.5); iii) analyzing the efficiency of the dead-end detection (section 4.6); iv) evaluating the individual contribution of the different modules in our ddr (section 4.7), and v) validating the generality of our ddr (section 4.8). foot_4 ## conclusion and future work this paper identifies the dead-end as a critical source for invalid exploration of task-oriented dialogue policies and proposes a novel dead-end detection and rescue method (ddr). the method effectively rescues conversations from dead-ends. dead-end detection in ddr introduces an efficient criterion for detecting dead-ends, and its effectiveness has been experimentally verified. once a certain dead-end is detected, rescue in ddr provides rescue exploration guidance for avoiding invalid exploration and thus generates more high-quality and diverse conversations. in addition, the experience containing dead-ends is added for dda to prevent the same mistakes from occurring in the dialogue policy. the extensive results demonstrate the superiority and generality of our approach. although our ddr algorithm is efficient and very general to be used with different rl algorithms on tod systems, it has two main limitations: 1) our method is challenging to use for other types of dialogue systems where the database is not accessible. even though this paper focuses on tod systems that work on the database, it is undeniable that other types of dialogue systems, such as chatbots or recommendation systems, may also have dead-end problems. future efforts will extend our method to accommodate these inaccessible database scenarios. 2) the scope of dead-end rescue addressed in this paper pertains to the category of dead-ends resolvable by dialogue policies, while our defined dead-end concept can generally cover all dead-end situations. it struggles to handle dead-ends arising from reasons beyond dialogue policies, such as cases where user requests cannot be fulfilled due to absence from the database. while our ddr techniques effectively mitigate many dead-ends, some persist, as illustrated in