Conversational Tree Search: A New Hybrid Dialog Task (2023)

Abstract: Conversational interfaces provide a flexible and easy way for users to seek information that may otherwise be difficult or inconvenient to obtain. However, existing interfaces generally fall into one of two categories: FAQs, where users must have a concrete question in order to retrieve a general answer, or dialogs, where users must follow a pre-defined path but may receive a personalized answer. In this paper, we introduce Conversational Tree Search (CTS) as a new task that bridges the gap between FAQ-style information retrieval and task-oriented dialog, allowing domain-experts to define dialog trees which can then be converted to an efficient dialog policy that learns only to ask the questions necessary to navigate a user to their goal. We collect a dataset for the travel reimbursement domain and demonstrate a baseline as well as a novel deep Reinforcement Learning architecture for this task. Our results show that the new architecture combines the positive aspects of both the FAQ and dialog system used in the baseline and achieves higher goal completion while skipping unnecessary questions.

## introduction complex processes, e.g., healthcare, insurance, or travel reimbursement, can be challenging for users to navigate. faq and task-oriented dialog systems can provide immediate support, which is especially helpful as questions in these areas can be time sensitive, e.g., whom to contact in case of a lost passport. to support all types of users, however, such systems must be fast to satisfy those with more experience and thorough, so that those with less experience understand all steps needed to accomplish their goals. above all, however, accuracy is critical in such susceptible domains. faq systems can directly answer to user queries by matching them to predefined common question/answer pairs. it enables quick access to information while allowing subject experts to define system output and ensure it is factually correct @xcite . however, this approach does not allow for personalizing answers to a user's specific case, e.g., a specific user's per diem might depend on their destination and length of travel. including information for all cases in one faq answer would make it long and hard to understand, while adding faqs for each case, would make retrieval challenging. additionally, as retrieval accuracy could be better @xcite , the top answer might be incorrect, but displaying multiple answers makes the search process longer and transfers the responsibility of selecting the correct answer to the user. finally, faq systems expect concrete information needs from users; but, new users may not be familiar enough with the complex process they wish to navigate in order to pose specific questions. dialog systems provide the opportunity for turnbased interaction, which can solve many of the shortcomings of faq systems (allowing process guidance, and shorter, more personalized answers). while automatically learning dialog behavior can be quicker and allow for more flexibility than designing a handcrafted system, such dialog systems rely on large amounts of data @xcite , and their behavior can be challenging to control @xcite . as such, handcrafted dialog systems have generally still been preferred in lowresource settings, where there is not enough data to train a machine learning approach @xcite , and in domains where it is essential that dialog designers can carefully control the system's behavior @xcite . in these cases, it is common for non-technical experts to define the system behavior using a graphical interface @xcite , resulting in a dialog tree. however, the structure of such systems can be rigid to traverse, making it less suitable for experienced users who want a specific question answered as fast as possible, rather than having to navigate through the whole tree until they reach the answer they were looking for. in trying to implement a dialog system for travel reimbursement, we confirmed the shortcomings of both faq-and dialog-based approaches through pilot studies. as we are unaware of any system at the time of writing that can handle both forms of information-seeking behavior, we propose a new task called conversational tree search (cts). in this task, subject-experts can design arbitrarily complex dialog trees from which a dialog policy can be automatically trained to support both a guided dialog mode -where users with a vague information need can be guided by questions each turn until they reach their answer -and a free dialog modewhere users with a concrete information need can receive an answer as efficiently as possible (see figure 1 ). in this way, cts offers a hybrid solution where experts can still carefully control dialog structure and system responses while also profiting from the flexibility of a machine learning policy that can navigate the tree efficiently, only asking questions necessary to clarify information needs or personalize answers. providing both dialog modes allows both novices and more experienced users to receive the correct level of support. to solve our newly proposed task, we focus on the following research questions: (rq1) how can we develop a dialog policy that can navigate an expert-designed dialog tree, supporting both users with a specific information need and those with only a vague information need? in the process of answering these research questions, we make the following concrete contributions: 1) we define a new task, cts, and its evaluation criteria; 2) we collect and publish reim-burse, a low resource, real-world german language dataset for cts in the domain of travel reimbursement, consisting of a dialog tree and user utterances; 3) we implement a domain-agnostic user simulator for cts, using it to generate new dialogs based on the reimburse data; and 4) we design a novel reinforcement learning (rl) architecture and train an agent to achieve significant performance increases over the baseline system on noisy and unseen data. our data, simulator, and code are released foot_0 under an open source license to encourage more research into this task. our results show that an rl agent, based on our novel architecture, can learn to differentiate between both modes of interaction (guided and free) and skip unnecessary questions in free mode. furthermore, the rl agent can significantly outperform the baseline system even in settings where gaussian noise is applied to the user utterance encodings. finally, the rl agent outperforms the baseline on dialogs that are generated based on unseen user utterances. its success in this setting indicates an understanding of the user's text input, as the agent cannot exploit structural features, e.g., positional information. ## definition of conversational tree search task the goal of this task is, given a dialog tree, to develop an interactive dialog system able to efficiently navigate a user to their goal by traversing the tree, and only outputting questions which are needed to clarify the user's intention and personalize the output accordingly. in order to accomplish this, a policy has two types of actions it can choose at any node, either to ask, which represents outputting the system text associated with that node, or to skip , which represents transitioning to a connected node without outputting the text at the current node. ## methods we develop and release 1 a baseline system, an rlagent, and a domain-agnostic user simulator for training and evaluating dialog policies on the new cts task. ## reimburse: a dataset for cts for this task, we collect and publish a dataset from two sources: a dialog tree, defining the general system behavior, and a corpus of user utterances, with paraphrases for both user questions and responses to system questions. this dataset represents challenging real-world data, both in the complex structure of the dialog tree for this domain, and the real-world nature of the user utterances. examples of user questions and user responses are provided in appendix b. ## experimental setup the rl agents receive the following inputs: beliefstate, last system action type, action index, and current node type encoded by one-hot vectors, current node position as a binary tree encoding @xcite , the dialog history, initial user utterance, current user utterance, current node text and the node's prototypical answer texts encoded by either an english-german roberta @xcite foot_1 or sentence transformers @xcite model. the model is trained against the user simulator using the adam optimizer (kingma and ba, 2015) with a learning rate of 1e -4 . we set the maximum number of training dialog turns to 1.5m and save the model which performs best in evaluation (performed every 10k turns with 500 simulated dialogs) for testing. evaluation and testing are also performed against the user simulator. however, in this mode agent exploration is disabled. for more details on model and training parameters, see appendix d. testing is done on 500 simulated dialogs (in rq3 generated from held out utterances). we measure success and skip ratios for guided and free mode separately and jointly. to check task understanding, we measure the dialog mode prediction consistency: we calculate the difference between the percentage of turns predicted for guided and free mode per dialog, then averaging across all dialogs. ## conclusion and future work in this work, we introduced a new task, cts which combines the positive aspects of both an faq retrieval and task-based dialog system, along with a real-world german language dataset, re-imburse, a domain-agnostic user simulator, and baseline system based on state-of-the-art language models. furthermore, we demonstrated a novel, scalable rl architecture, showing significant performance improvements over the baseline. our models are able to handle high levels of noise in the input data and demonstrate the ability to learn textbased information from user utterances, as seen by their ability to handle unseen data. in the future, it would be interesting to explore data augmentation for generating unseen utterances as well as to explore methods, particularly for guided mode dialogs, to encourage the model to rely even more information from text. we also hope that the community helps in exploring performance on additional languages and task instances.