SAPIENT : Mastering Multi-turn Conversational Recommendation with Strategic Planning and M onte C arlo Tree Search (2025)

Abstract: Conversational Recommender Systems (CRS) proactively engage users in interactive dialogues to elicit user preferences and provide personalized recommendations. Existing methods train Reinforcement Learning (RL)-based agent with greedy action selection or sampling strategy, and may suffer from suboptimal conversational planning. To address this, we present a novel Monte Carlo Tree Search (MCTS)-based CRS framework SAPIENT. SAPIENT consists of a conversational agent (S-agent) and a conversational planner (S-planner). S-planner builds a conversational search tree with MCTS based on the initial actions proposed by S-agent to find conversation plans. The best conversation plans from S-planner are used to guide the training of S-agent, creating a self-training loop where S-agent can iteratively improve its capability for conversational planning. Furthermore, we propose an efficient variant SAPIENT for trade-off between training efficiency and performance. Extensive experiments on four benchmark datasets validate the effectiveness of our approach, showing that SAPIENT outperforms the state-of-the-art baselines. Our code and data are accessible through https://github.com/ninglab/SAPIENT.

## introduction conversational recommender systems (crss) are developed to proactively engage users with interactive dialogues to understand user preferences and provide highly personalized recommendations @xcite . for example, on an online dining platform such as yelp @xcite , crs can chat with users through natural language dialogues (e.g., ask a question like, "what is your preferred food type?") and recommend products that best match the users' preferences expressed in the conversation. among different settings of crs @xcite @xcite , the multi-turn conversational recommendation (mcr) setting @xcite is popular as it can interact/communicate with users multiple times (i.e., multiple turns) to iteratively learn user preferences @xcite . in this work, we develop an innovative monte carlo tree search (mcts)based mcr framework to enhance the strategic conversational planning ability for mcr, offering a fresh perspective for handling complex conversation environments and enhancing user experiences. a key of mcr is to decide what action (asking a question on specific attribute values or recommending specific items) to take at each conversational turn-a conversational turn consists of the crs taking an action and the user responding to that action-to effectively elicit information on user preferences and make personalized recommendations @xcite . to achieve this, previous methods formulated mcr as a markovian decision process (mdp) @xcite , and trained policy-based @xcite or value-based @xcite agents via reinforcement learning (rl) to learn conversation strategies. despite promising, these methods could suffer from myopic actions and limited planning capability due to the following reasons. first, they base their planning solely on observations of the current state (e.g., items that the user indicates a negative preference for) without exploring potential future states. as a result, they could take myopic actions @xcite . second, they generate conversation trajectories, also referred to as conversation plans, by sequentially sampling actions, and thus could suffer from the cumulative error, especially when generating long trajectories for planning @xcite . to address these limitations, we present a novel mcts-based mcr framework-strategic action figure 1 : an example of conversational search tree for a user. conversation starts at the root node with the user specifying preference on an attribute type and its value. the search tree expands as s-agent decides different action types-ask and rec-at each turn. red line connects the highest-rewarded conversation plan found by the tree. planning with intelligent exploration non-myopic tactics, referred to as sapient. sapient comprises a conversational agent, referred to as s-agent, where s-agent utilizes an mcts-based algorithm, referred to as s-planner, to plan conversations. s-agent builds a global information graph and two personalized graphs with dedicated graph encoders to extract the representation of the conversational states, and synergizes a policy network and a qnetwork to decide specific actions based on the learned state representations. s-planner leverages mcts @xcite to simulate future conversations with lookahead explorations. this non-myopic conversational planning process ensures s-planner can strategically plan conversations that maximize the cumulative reward (a numerical signal measuring whether the action taken by s-agent is good or not), instead of greedily selecting actions based on immediate reward. the best conversation plans with the highest cumulative rewards found by s-planner are used to guide the training of s-agent. in this way, s-agent can engage in a self-training loop @xcite -collecting trajectories from multiple conversation simulations and training on selected, high-rewarded trajectories-to iteratively improve its planning capability without additional labeled data. after s-agent is well-trained, it can directly make well-informed decisions without s-planner during inference, since it inherits the s-planner's expertise in strategic, non-myopic planning. to make mcts scalable w.r.t. the size of items and attributes, we introduce a hierarchical action selection process @xcite , and two action types: ask and rec. at each turn, instead of searching over all the items and attribute val-ues, s-planner builds a conversational search tree (figure 1 ) that only searches over the two action types and uses the q-network to decide the specific action, thus greatly reducing the search space. we evaluate sapient against 9 state-of-the-art crs baselines, and show sapient significantly outperforms baselines on 4 benchmark datasets. our case study also shows that the action strategies of sapient are beneficial for information seeking and recommendation success in the conversations. furthermore, we develop an efficient variant of sapient, denoted as sapient-e. different from sapient, which is trained on selected, highrewarded trajectories, sapient-e consumes all trajectories found by s-planner for training via a listwise ranking loss. as a result, sapient-e requires less cost of collecting training trajectories compared to sapient, and enables superior efficiency. our contributions are summarized as follows: reinforcement learning for crs reinforcement learning (rl) has achieved great success in tasks requiring strategic planning in complex and interactive environments, such as computer go @xcite and dialogue planning @xcite . rl is also employed to train crs agents to make strategic actions, and current rl-based crss can be mainly categorized into two types of methods: ## notations and definitions we denote u as the set of users, v as the set of items, y as the set of attribute types (e.g., price range, star rating), and p as the set of attribute values (e.g., medium price range, five-star rating). each user @xmath0.g., view, purchase) with a set of items v(u). each item @xmath1. each conversation is initialized by a user specifying preference on an attribute type y 0 ∈ y and its corresponding attribute value p 0 ∈ p (e.g., the user says "i am looking for a place with medium price range."). at the t-th conversational turn, s-agent can either ask for preferences over attribute values from a set of candidate attribute values p c t , or recommend items from a set of candidate items v c t . based on the user's reply (accept or reject attribute values/items), s-agent repeatedly communicates with users until the user accepts at least one recommended item at turn t (success), or the conversation reaches the maximum number of turns and terminates at @xmath2. the goal of mcr is to recommend at least one item that the user accepts, and complete the conversation in as few turns as possible to prevent the user from becoming impatient after too many turns. ## method we introduce sapient, an mcts-based mcr framework that achieves strategic and non-myopic conversational planning. sapient formulates mcr as an mdp with a hierarchical action selection process (section 4.1). a conversational agent (s-agent) observes the current state and decides the actions in each conversational turn (section 4.2), a conversational planner (s-planner) leverages an mcts-based algorithm to plan conversations (section 4.3), and s-agent engages in a self-training loop with guidance from s-planner (section 4.4). once s-agent is well-trained, it can directly make well-informed decisions without s-planner during inference, since it inherits the s-planner's expertise in strategic and non-myopic planning. a frame-work overview of sapient is in figure 2 and the training algorithm is in algorithm 1. we summarize all the notations in appendix a. ## experimental settings datasets we evaluate sapient on 4 benchmark datasets: yelp @xcite , lastfm @xcite , amazon-book @xcite and movielens @xcite . dataset details are available in appendix f.1. user simulator training and evaluating crs with real-world user interactions can be impractically expensive at scale. to address this issue, we adopt the user simulator approach @xcite and simulate a conversation for each user as detailed in appendix f.2. note that this user simulator is widely adopted in the literature @xcite @xcite @xcite and studies show the simulations are of high quality and suitable for evaluation purposes @xcite @xcite , allowing for large-scale evaluations at a relatively low cost. evaluation metrics following the literature @xcite , the success rate (sr) is adopted to measure the ratio of successful recommendations within t max turns; average turn (at) to evaluate the average number of conversational turns; and hdcg @xcite to evaluate the ranking order of the ground-truth item among the list of all the recommended items. for sr and hdcg, a higher value indicates better performance, while for at, a lower value indicates better performance. details for hdcg calculation are available in appendix f.3. baselines and implementation details we choose 9 state-of-the-art baselines for a comprehensive evaluation, including: (1) max entropy @xcite ; (2) abs greedy @xcite ; (3) crm @xcite ; (4) ear @xcite ; (5) scpr @xcite ; (6) unicorn @xcite ; (7) mcmipl @xcite ; (8) hutcrs @xcite ; and a large language model (llm) baseline core @xcite . baseline details are available in appendix f.4. implementation details of sapient are available in appendix f.5. 6 experimental results ## conclusion we present sapient, a novel mcr framework with strategic and non-myopic conversational planning tactics. sapient adopts a hierarchical action selection process, builds a conversational search tree with mcts, and selects the high-rewarded conversation plans to train s-agent. during inference, s-agent can make well-informed decisions without s-planner, as it inherits s-planner's expertise in strategic planning. furthermore, we develop a variant sapient-e to address the efficiency issue with mcts. extensive experiments on benchmark datasets verify the effectiveness of our framework.