Prompt-Based M onte- C arlo Tree Search for Goal-oriented Dialogue Policy Planning (2023)

Abstract: Planning for goal-oriented dialogue often requires simulating future dialogue interactions and estimating task progress. Many approaches thus consider training neural networks to perform look-ahead search algorithms such as A* search and Monte Carlo Tree Search (MCTS). However, this training often require abundant annotated data, which creates challenges when faced with noisy annotations or low-resource settings. We introduce GDP-Zero, an approach using Open-Loop MCTS to perform goal-oriented dialogue policy planning without any model training. GDP-Zero prompts a large language model to act as a policy prior, value function, user simulator, and system model during the tree search. We evaluate GDP-Zero on the goal-oriented task PersuasionForGood, and find that its responses are preferred over ChatGPT up to 59.32% of the time, and are rated more persuasive than ChatGPT during interactive evaluations.

## introduction in many goal-oriented conversation tasks, interacting parties must retake initiative @xcite by executing conversational strategies to lead the conversation a desired outcome (e.g. successful negotiation @xcite or emotional support @xcite ). as such, it is imperative to have high-quality dialogue policy planners that can prescribe an "optimal" strategy at each turn of the dialogue @xcite @xcite . optimal policy planning is a difficult task. while in task-oriented settings (e.g. restaurant booking) there at least is objectivity with respect to successful planning, many goal-oriented tasks like persuasion are often subjective. for instance, in a persuasion task, individual persuaders might adopt different strategies, making it difficult to train or 1 code available at: https://github.com/jasonyux/gdpzero evaluate a policy planner 2 . moreover, "optimality" in these complex tasks may require expert domain knowledge (e.g., negotiation skills). this also makes collecting and annotating high-quality conversations difficult @xcite . in this work, we contribute a novel approach to goal-oriented dialogue planning with zero training (gdp-zero). gdp-zero prompts a large language model (llm) to perform planning by simulating future dialogue interactions (figure 1 ), making it particularly suitable for tasks which would otherwise require high-quality conversations 2 in our extensive initial experiments to build a policy planner for the persuasionforgood @xcite ) task, we found 1) training a supervised or reinforcement learningbased multi-class classifier for next-dialogue-act-prediction yields only 18-25% accuracy at best (including finetuning llama @xcite , roberta @xcite , and prompting llms such as chatgpt), and 2) converting the multiclass policy prediction task into a binary task of whether to "propose to donate" still yields only 74% accuracy. and annotations. unlike previous approaches, we treat policy planning as a stochastic game, and use prompting for every stage of an open-loop tree search. we evaluate gdp-zero on persuasionfor-good due to its difficult planning task @xcite , and find its responses are preferred over chatgpt in both static and interactive evaluations. ## method in this work, we introduce gdp-zero, an algorithm-focused dialogue policy planner for goaloriented dialogue tasks like persuasion. gdp-zero uses zero model training and instead performs open-loop mcts at decision time by prompting an llm to simulate user and system response, evaluate current task progress, and predict a prior next dialogue act. building on findings from @xcite , our approach has two main differences from existing policy planning work: we use few-shot prompting to bypass the need for model training on noisy data, and we use open-loop mcts to reduce compounding simulation errors by continuously re-generating system and user responses during the tree search. ## experiments we evaluate gdp-zero in the context of persua-sionforgood (p4g; wang et al. (2019) ), a dataset with 300 annotated dialogues where a "persuader" attempts to persuade a "persuadee" to donate to a charity called save the children (appendix e). due to the subjective nature of persuasion, it is not clear whether the annotated conversations reflect optimal persuasion strategies @xcite . this makes training and evaluating a policy planner challenging, since different persuaders likely adopt different strategies (section 1). motivated by this challenge, we employ gdp-zero to perform decision-time planning based on dialogue simulations, and focus on evaluating our approach's end-to-end performance in achieving the desired task outcome: successfully persuading a user to donate to save the children. ## conclusion we propose gdp-zero, an algorithm to perform look-ahead policy planning with a large language model for goal-oriented dialogues. end-to-end evaluation shows that using the policy from gdp-zero surpasses previous state-of-the-art system (rap) and direct prompting with state-of-the-art llms on the task of persuasion without any model training. strong performance in the zero-data regime opens the possibility of future work building dialogue systems in more conversational tasks under data-scarce settings.