Feedback-Aware Monte Carlo Tree Search for Efficient Information Seeking in Goal-Oriented Conversations

• URL: http://arxiv.org/abs/2501.15056v1
• Date: Sat, 25 Jan 2025 03:42:22 GMT
• Title: Feedback-Aware Monte Carlo Tree Search for Efficient Information Seeking in Goal-Oriented Conversations
• Authors: Harshita Chopra, Chirag Shah,
• Abstract summary: We introduce a novel approach to adaptive question-asking through a combination of Large Language Models (LLM) for generating questions that maximize information gain.<n>We present two key innovations: (1) an adaptive MCTS algorithm that balances exploration and exploitation for efficient search over potential questions; and (2) a clustering-based feedback algorithm that leverages prior experience to guide future interactions.
• Score: 10.352944689413398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The ability to identify and acquire missing information is a critical component of effective decision making and problem solving. With the rise of conversational artificial intelligence (AI) systems, strategically formulating information-seeking questions becomes crucial and demands efficient methods to guide the search process. We introduce a novel approach to adaptive question-asking through a combination of Large Language Models (LLM) for generating questions that maximize information gain, Monte Carlo Tree Search (MCTS) for constructing and leveraging a decision tree across multiple samples, and a hierarchical feedback mechanism to learn from past interactions. We present two key innovations: (1) an adaptive MCTS algorithm that balances exploration and exploitation for efficient search over potential questions; and (2) a clustering-based feedback algorithm that leverages prior experience to guide future interactions. Each incoming sample is assigned to a cluster based on its semantic similarity with previously observed samples. Our UCT (Upper Confidence bound for Trees) formulation selects optimal questions by combining expected rewards, a function of information gain, with a cluster-specific bonus that decays with depth, to emphasize the importance of early-stage questions that have proven effective for narrowing the solution space in similar samples. Experiments across three domains, including medical diagnosis and troubleshooting, demonstrate that our method leads to an average of 12% improvement in success rates and a 10x reduction in the average number of LLM calls made per conversation for the search process, in comparison to the state of the art.

Related papers

• Teaching Language Models To Gather Information Proactively [53.85419549904644]
  Large language models (LLMs) are increasingly expected to function as collaborative partners.<n>In this work, we introduce a new task paradigm: proactive information gathering.<n>We design a scalable framework that generates partially specified, real-world tasks, masking key information.<n>Within this setup, our core innovation is a reinforcement finetuning strategy that rewards questions that elicit genuinely new, implicit user information.
  arXiv  Detail & Related papers  (2025-07-28T23:50:09Z)
• Reinforcing Question Answering Agents with Minimalist Policy Gradient Optimization [80.09112808413133]
  Mujica is a planner that decomposes questions into acyclic graph of subquestions and a worker that resolves questions via retrieval and reasoning.<n>MyGO is a novel reinforcement learning method that replaces traditional policy updates with gradient Likelihood Maximum Estimation.<n> Empirical results across multiple datasets demonstrate the effectiveness of MujicaMyGO in enhancing multi-hop QA performance.
  arXiv  Detail & Related papers  (2025-05-20T18:33:03Z)
• Reasoning of Large Language Models over Knowledge Graphs with Super-Relations [53.14275361052276]
  We propose the ReKnoS framework, which aims to Reason over Knowledge Graphs with Super-Relations.<n>Our framework's key advantages include the inclusion of multiple relation paths through super-relations.<n>The results demonstrate the superior performance of ReKnoS over existing state-of-the-art baselines, with an average accuracy gain of 2.92%.
  arXiv  Detail & Related papers  (2025-03-28T06:11:04Z)
• Dancing with Critiques: Enhancing LLM Reasoning with Stepwise Natural Language Self-Critique [66.94905631175209]
  We propose a novel inference-time scaling approach -- stepwise natural language self-critique (PANEL)<n>It employs self-generated natural language critiques as feedback to guide the step-level search process.<n>This approach bypasses the need for task-specific verifiers and the associated training overhead.
  arXiv  Detail & Related papers  (2025-03-21T17:59:55Z)
• MCTS-KBQA: Monte Carlo Tree Search for Knowledge Base Question Answering [5.926690985669765]
  This study explores how to enhance the reasoning capabilities of large language models (LLMs) in knowledge base question answering (KBQA) by leveraging Monte Carlo Tree Search (MCTS)<n>We design a carefully designed step-wise reward mechanism that requires only direct prompting of open-source instruction LLMs.<n>We contribute new data resources to the KBQA community by annotating intermediate reasoning processes for existing question-SPARQL datasets using distant supervision.
  arXiv  Detail & Related papers  (2025-02-19T04:58:39Z)
• Boost, Disentangle, and Customize: A Robust System2-to-System1 Pipeline for Code Generation [58.799397354312596]
  Large language models (LLMs) have demonstrated remarkable capabilities in various domains, particularly in system 1 tasks. Recent research on System2-to-System1 methods surge, exploring the System 2 reasoning knowledge via inference-time computation. In this paper, we focus on code generation, which is a representative System 2 task, and identify two primary challenges.
  arXiv  Detail & Related papers  (2025-02-18T03:20:50Z)
• Open-Ended and Knowledge-Intensive Video Question Answering [20.256081440725353]
  We investigate knowledge-intensive video question answering (KI-VideoQA) through the lens of multi-modal retrieval-augmented generation. Our analysis examines various retrieval augmentation approaches using cutting-edge retrieval and vision language models. We achieve a substantial 17.5% improvement in accuracy on multiple choice questions in the KnowIT VQA dataset.
  arXiv  Detail & Related papers  (2025-02-17T12:40:35Z)
• Context Awareness Gate For Retrieval Augmented Generation [2.749898166276854]
  Retrieval Augmented Generation (RAG) has emerged as a widely adopted approach to mitigate the limitations of large language models (LLMs) in answering domain-specific questions.<n>Previous research has predominantly focused on improving the accuracy and quality of retrieved data chunks to enhance the overall performance of the generation pipeline.<n>We investigate the impact of retrieving irrelevant information in open-domain question answering, highlighting its significant detrimental effect on the quality of LLM outputs.
  arXiv  Detail & Related papers  (2024-11-25T06:48:38Z)
• Enhancing LLM Reasoning with Reward-guided Tree Search [95.06503095273395]
  o1-like reasoning approach is challenging, and researchers have been making various attempts to advance this open area of research.<n>We present a preliminary exploration into enhancing the reasoning abilities of LLMs through reward-guided tree search algorithms.
  arXiv  Detail & Related papers  (2024-11-18T16:15:17Z)
• Exploring Knowledge Boundaries in Large Language Models for Retrieval Judgment [56.87031484108484]
  Large Language Models (LLMs) are increasingly recognized for their practical applications. Retrieval-Augmented Generation (RAG) tackles this challenge and has shown a significant impact on LLMs. By minimizing retrieval requests that yield neutral or harmful results, we can effectively reduce both time and computational costs.
  arXiv  Detail & Related papers  (2024-11-09T15:12:28Z)
• Benchmarking Multimodal Retrieval Augmented Generation with Dynamic VQA Dataset and Self-adaptive Planning Agent [92.57125498367907]
  Multimodal Retrieval Augmented Generation (mRAG) plays an important role in mitigating the "hallucination" issue inherent in multimodal large language models (MLLMs) We propose the first self-adaptive planning agent for multimodal retrieval, OmniSearch.
  arXiv  Detail & Related papers  (2024-11-05T09:27:21Z)
• AGENT-CQ: Automatic Generation and Evaluation of Clarifying Questions for Conversational Search with LLMs [53.6200736559742]
  AGENT-CQ consists of two stages: a generation stage and an evaluation stage. CrowdLLM simulates human crowdsourcing judgments to assess generated questions and answers. Experiments on the ClariQ dataset demonstrate CrowdLLM's effectiveness in evaluating question and answer quality.
  arXiv  Detail & Related papers  (2024-10-25T17:06:27Z)
• MindStar: Enhancing Math Reasoning in Pre-trained LLMs at Inference Time [51.5039731721706]
  MindStar is a purely inference-based searching method for large language models. It formulates reasoning tasks as searching problems and proposes two search ideas to identify the optimal reasoning paths. It significantly enhances the reasoning abilities of open-source models, such as Llama-2-13B and Mistral-7B, and achieves comparable performance to GPT-3.5 and Grok-1.
  arXiv  Detail & Related papers  (2024-05-25T15:07:33Z)
• HGOT: Hierarchical Graph of Thoughts for Retrieval-Augmented In-Context Learning in Factuality Evaluation [20.178644251662316]
  We introduce the hierarchical graph of thoughts (HGOT) to enhance the retrieval of pertinent passages during in-context learning. The framework employs the divide-and-conquer strategy to break down complex queries into manageable sub-queries. It refines self-consistency majority voting for answer selection, which incorporates the recently proposed citation recall and precision metrics.
  arXiv  Detail & Related papers  (2024-02-14T18:41:19Z)
• A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
  Subset selection is a fundamental problem that can play a key role in identifying smaller portions of the training data. We develop a novel factor 3-approximation algorithm to compute subsets based on the weighted sum of both k-center and uncertainty sampling objective functions.
  arXiv  Detail & Related papers  (2023-12-17T04:41:07Z)
• A Deep Reinforcement Learning Approach for Interactive Search with Sentence-level Feedback [12.712416630402119]
  Interactive search can provide a better experience by incorporating interaction feedback from the users. Existing state-of-the-art (SOTA) systems use reinforcement learning (RL) models to incorporate the interactions. Yet such feedback requires extensive RL action space exploration and large amounts of annotated data. This work proposes a new deep Q-learning (DQ) approach, DQrank.
  arXiv  Detail & Related papers  (2023-10-03T18:45:21Z)
• Feature Acquisition using Monte Carlo Tree Search [18.76745359031975]
  Feature acquisition algorithms address the problem of acquiring informative features while balancing the costs of acquisition to improve the learning performances of ML models. Previous approaches have focused on calculating the expected utility values of features to determine the acquisition sequences. In comparison to previous approaches, we focus on 1) formulating the feature acquisition problem as a MDP and applying Monte Carlo Tree Search, 2) calculating the intermediary rewards for each acquisition step based on model improvements and acquisition costs, and 3) simultaneously optimizing model improvement and acquisition costs with multi-objective Monte Carlo Tree Search.
  arXiv  Detail & Related papers  (2022-12-21T20:53:44Z)
• Contingency-Aware Influence Maximization: A Reinforcement Learning Approach [52.109536198330126]
  influence (IM) problem aims at finding a subset of seed nodes in a social network that maximize the spread of influence. In this study, we focus on a sub-class of IM problems, where whether the nodes are willing to be the seeds when being invited is uncertain, called contingency-aware IM. Despite the initial success, a major practical obstacle in promoting the solutions to more communities is the tremendous runtime of the greedy algorithms.
  arXiv  Detail & Related papers  (2021-06-13T16:42:22Z)
• An Information-Theoretic Framework for Unifying Active Learning Problems [44.758281991246825]
  This paper presents an information-theoretic framework for unifying active learning problems. We first introduce a novel active learning criterion that subsumes an existing LSE algorithm. By exploiting the relationship between LSE and BO, we design a competitive information-theoretic acquisition function for BO.
  arXiv  Detail & Related papers  (2020-12-19T14:22:48Z)
• Sequential Transfer in Reinforcement Learning with a Generative Model [48.40219742217783]
  We show how to reduce the sample complexity for learning new tasks by transferring knowledge from previously-solved ones. We derive PAC bounds on its sample complexity which clearly demonstrate the benefits of using this kind of prior knowledge. We empirically verify our theoretical findings in simple simulated domains.
  arXiv  Detail & Related papers  (2020-07-01T19:53:35Z)
• Model-based Multi-Agent Reinforcement Learning with Cooperative Prioritized Sweeping [4.5497948012757865]
  We present a new model-based reinforcement learning algorithm, Cooperative Prioritized Sweeping. The algorithm allows for sample-efficient learning on large problems by exploiting a factorization to approximate the value function. Our method outperforms the state-of-the-art algorithm sparse cooperative Q-learning algorithm, both on the well-known SysAdmin benchmark and randomized environments.
  arXiv  Detail & Related papers  (2020-01-15T19:13:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.