# Prompt-Based Monte-Carlo Tree Search for Goal-Oriented Dialogue Policy Planning

arXiv: https://arxiv.org/abs/2305.13660 · HTML: https://mlsanity.com/paper/2305.13660/

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 58 references that are in the map.
- First posted on arXiv 23 May 2023.

## Builds on (most cited first, 30 of 35)

- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment](https://mlsanity.com/paper/2303.16634/) (2023)
- [ChatGPT Outperforms Crowd-Workers for Text-Annotation Tasks](https://mlsanity.com/paper/2303.15056/) (2023)
- [MultiWOZ -- A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling](https://mlsanity.com/paper/1810.00278/) (2018)
- [How Close is ChatGPT to Human Experts? Comparison Corpus, Evaluation, and Detection](https://mlsanity.com/paper/2301.07597/) (2023)
- [Towards Emotional Support Dialog Systems](https://mlsanity.com/paper/2106.01144/) (2021)
- [Deal or No Deal? End-to-End Learning for Negotiation Dialogues](https://mlsanity.com/paper/1706.05125/) (2017)
- [Persuasion for Good: Towards a Personalized Persuasive Dialogue System for Social Good](https://mlsanity.com/paper/1906.06725/) (2019)
- [Want To Reduce Labeling Cost? GPT-3 Can Help](https://mlsanity.com/paper/2108.13487/) (2021)
- [Do the Rewards Justify the Means? Measuring Trade-Offs Between Rewards and Ethical Behavior in the MACHIAVELLI Benchmark](https://mlsanity.com/paper/2304.03279/) (2023)
- [AnnoLLM: Making Large Language Models to Be Better Crowdsourced Annotators](https://mlsanity.com/paper/2303.16854/) (2023)
- [SODA: Million-scale Dialogue Distillation with Social Commonsense Contextualization](https://mlsanity.com/paper/2212.10465/) (2022)
- [Decoupling Strategy and Generation in Negotiation Dialogues](https://mlsanity.com/paper/1808.09637/) (2018)
- [GALAXY: A Generative Pre-trained Model for Task-Oriented Dialog with Semi-Supervised Learning and Explicit Policy Injection](https://mlsanity.com/paper/2111.14592/) (2021)
- [PLACES: Prompting Language Models for Social Conversation Synthesis](https://mlsanity.com/paper/2302.03269/) (2023)
- [Few-Shot Bot: Prompt-Based Learning for Dialogue Systems](https://mlsanity.com/paper/2110.08118/) (2021)
- [Improving Multi-turn Emotional Support Dialogue Generation with Lookahead Strategy Planning](https://mlsanity.com/paper/2210.04242/) (2022)
- [Dialogue Learning with Human Teaching and Feedback in End-to-End Trainable Task-Oriented Dialogue Systems](https://mlsanity.com/paper/1804.06512/) (2018)
- [How to Build User Simulators to Train RL-based Dialog Systems](https://mlsanity.com/paper/1909.01388/) (2019)
- [InstructDial: Improving Zero and Few-shot Generalization in Dialogue through Instruction Tuning](https://mlsanity.com/paper/2205.12673/) (2022)
- [Controllable Mixed-Initiative Dialogue Generation through Prompting](https://mlsanity.com/paper/2305.04147/) (2023)
- [Iterative Policy Learning in End-to-End Trainable Task-Oriented Neural Dialog Models](https://mlsanity.com/paper/1709.06136/) (2017)
- [Building a Role Specified Open-Domain Dialogue System Leveraging Large-Scale Language Models](https://mlsanity.com/paper/2205.00176/) (2022)
- [Zero-Shot Dialog Generation with Cross-Domain Latent Actions](https://mlsanity.com/paper/1805.04803/) (2018)
- [Multi-Stage Prompting for Knowledgeable Dialogue Generation](https://mlsanity.com/paper/2203.08745/) (2022)
- [Deep Dyna-Q: Integrating Planning for Task-Completion Dialogue Policy Learning](https://mlsanity.com/paper/1801.06176/) (2018)
- [Learning Goal-oriented Dialogue Policy with Opposite Agent Awareness](https://mlsanity.com/paper/2004.09731/) (2020)
- [Schema-Guided Paradigm for Zero-Shot Dialog](https://mlsanity.com/paper/2106.07056/) (2021)
- [LEGOEval: An Open-Source Toolkit for Dialogue System Evaluation via Crowdsourcing](https://mlsanity.com/paper/2105.01992/) (2021)

## Built on by (most cited first, 30 of 61)

- [A Survey on Recent Advances in LLM-Based Multi-turn Dialogue Systems](https://mlsanity.com/paper/2402.18013/) (2024)
- [Plug-and-Play Policy Planner for Large Language Model Powered Dialogue Agents](https://mlsanity.com/paper/2311.00262/) (2023)
- [A Review of Prominent Paradigms for LLM-Based Agents: Tool Use (Including RAG), Planning, and Feedback Learning](https://mlsanity.com/paper/2406.05804/) (2024)
- [ExACT: Teaching AI Agents to Explore with Reflective-MCTS and Exploratory Learning](https://mlsanity.com/paper/2410.02052/) (2024)
- [Multi-Agent Verification: Scaling Test-Time Compute with Multiple Verifiers](https://mlsanity.com/paper/2502.20379/) (2025)
- [Learning to Clarify: Multi-turn Conversations with Action-Based Contrastive Self-Training](https://mlsanity.com/paper/2406.00222/) (2024)
- [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026)
- [Towards Human-centered Proactive Conversational Agents](https://mlsanity.com/paper/2404.12670/) (2024)
- [Planning Like Human: A Dual-process Framework for Dialogue Planning](https://mlsanity.com/paper/2406.05374/) (2024)
- [RARE: Retrieval-Augmented Reasoning Enhancement for Large Language Models](https://mlsanity.com/paper/2412.02830/) (2024)
- [Strength Lies in Differences! Improving Strategy Planning for Non-collaborative Dialogues via Diversified User Simulation](https://mlsanity.com/paper/2403.06769/) (2024)
- [A Survey on LLM Test-Time Compute via Search: Tasks, LLM Profiling, Search Algorithms, and Relevant Frameworks](https://mlsanity.com/paper/2501.10069/) (2025)
- [PRINCIPLES: Synthetic Strategy Memory for Proactive Dialogue Agents](https://mlsanity.com/paper/2509.17459/) (2025)
- [Simulation-Free Hierarchical Latent Policy Planning for Proactive Dialogues](https://mlsanity.com/paper/2412.14584/) (2024)
- [Dyna-Think: Synergizing Reasoning, Acting, and World Model Simulation in AI Agents](https://mlsanity.com/paper/2506.00320/) (2025)
- [ARES: Alternating Reinforcement Learning and Supervised Fine-Tuning for Enhanced Multi-Modal Chain-of-Thought Reasoning Through Diverse AI Feedback](https://mlsanity.com/paper/2407.00087/) (2024)
- [RoT: Enhancing Large Language Models with Reflection on Search Trees](https://mlsanity.com/paper/2404.05449/) (2024)
- [ChatSOP: An SOP-Guided MCTS Planning Framework for Controllable LLM Dialogue Agents](https://mlsanity.com/paper/2407.03884/) (2024)
- [FLAP: Flow-Adhering Planning with Constrained Decoding in LLMs](https://mlsanity.com/paper/2403.05766/) (2024)
- [Planning without Search: Refining Frontier LLMs with Offline Goal-Conditioned RL](https://mlsanity.com/paper/2505.18098/) (2025)
- [Dyna-Mind: Learning to Simulate from Experience for Better AI Agents](https://mlsanity.com/paper/2510.09577/) (2025)
- [Natural Language Actor-Critic: Scalable Off-Policy Learning in Language Space](https://mlsanity.com/paper/2512.04601/) (2025)
- [Simulating Before Planning: Constructing Intrinsic User World Model for User-Tailored Dialogue Policy Planning](https://mlsanity.com/paper/2504.13643/) (2025)
- [Who Deserves the Reward? SHARP: Shapley Credit-based Optimization for Multi-Agent System](https://mlsanity.com/paper/2602.08335/) (2026)
- [PCQPR: Proactive Conversational Question Planning with Reflection](https://mlsanity.com/paper/2410.01363/) (2024)
- [SAPIENT: Mastering Multi-turn Conversational Recommendation with Strategic Planning and Monte Carlo Tree Search](https://mlsanity.com/paper/2410.09580/) (2024)
- [Feedback-Aware Monte Carlo Tree Search for Efficient Information Seeking in Goal-Oriented Conversations](https://mlsanity.com/paper/2501.15056/) (2025)
- [The Behavior Gap: Evaluating Zero-shot LLM Agents in Complex Task-Oriented Dialogs](https://mlsanity.com/paper/2506.12266/) (2025)
- [AI Agents for Web Testing: A Case Study in the Wild](https://mlsanity.com/paper/2509.05197/) (2025)
- [SeRTS: Self-Rewarding Tree Search for Biomedical Retrieval-Augmented Generation](https://mlsanity.com/paper/2406.11258/) (2024)

## Abstract (arXiv)

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 requires 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.