Unified Conversational Recommendation Policy Learning via Graph-based Reinforcement Learning

Conversational recommender systems (CRS) enable the traditional recommender systems to explicitly acquire user preferences towards items and attributes through interactive conversations. Reinforcement learning (RL) is widely adopted to learn conversational recommendation policies to decide what attributes to ask, which items to recommend, and when to ask or recommend, at each conversation turn. However, existing methods mainly target at solving one or two of these three decision-making problems in CRS with separated conversation and recommendation components, which restrict the scalability and generality of CRS and fall short of preserving a stable training procedure. In the light of these challenges, we propose to formulate these three decision-making problems in CRS as a unified policy learning task. In order to systematically integrate conversation and recommendation components, we develop a dynamic weighted graph based RL method to learn a policy to select the action at each conversation turn, either asking an attribute or recommending items. Further, to deal with the sample efficiency issue, we propose two action selection strategies for reducing the candidate action space according to the preference and entropy information. Experimental results on two benchmark CRS datasets and a real-world E-Commerce application show that the proposed method not only significantly outperforms state-of-the-art methods but also enhances the scalability and stability of CRS.


INTRODUCTION
Conversational recommender systems (CRS) aim to learn user's preferences and make recommendations through interactive conversations [12,16,41]. Since it has the natural advantage of explicitly acquiring user's preferences and revealing the reasons behind recommendation, CRS has become one of the trending research topics for recommender systems and is gaining increasing attention. Unlike traditional recommender systems [8,23,43] or interactive recommender systems (IRS) [49,51], which mainly focus on solving the problem of which items to recommend, there exists generally the other two core research questions for CRS [11], namely what questions to ask and when to ask or recommend. Recent works have demonstrated the importance of interactivity of asking clarifying questions in CRS [4,41,50]. More importantly, deciding when to ask or recommend is the key to coordinating conversation and recommendation for developing an effective CRS [12,14,26].
Different problem settings of CRS have been proposed, either from the perspective of dialog systems, being a variation of taskoriented dialog [13,16,48], or from the perspective of recommender systems, being an enhanced interactive recommender system [3,12,26]. In this work, we study the multi-round conversational recommendation (MCR) setting [12,26], where the system asks questions about users' preferences on certain attributes or recommends items multiple times, and the goal is to make successful recommendation with the minimum number of interactions.
In MCR scenario, the CRS is typically formulated as a multi-step decision-making process and solved by reinforcement learning (RL) methods for policy learning [12,14,26]. As shown in Figure 1(a), RL-based IRS is only required to learn the policy to decide which items to recommend. However, the situation is more complicated in CRS, since there are two components that need to be coherently considered [19], i.e., conversation and recommendation components. Existing methods CRM [26] and EAR [12] employ policy gradient [27] to improve the strategies of when and what attributes to ask, while the recommendation decision is made by an external recommendation model. In order to reduce the action space in policy learning, another state-of-the-art method SCPR [14] only considers learning the policy of when to ask or recommend, while two isolated components are responsible for the decision of what to ask and which to recommend. The policy learning frameworks of these two kinds of CRS are presented in Figure 1(b) and 1(c).
Despite the effectiveness of these methods, there are some issues remained to be tackled for real-world applications: (i) The models trained with existing CRS methods lack generality to different Work done when Yang Deng was an intern at Alibaba. This work was supported by Alibaba Group through Alibaba Research Intern Program, and a grant from the Research Grant Council of the Hong Kong Special Administrative Region, China (Project Codes: 14200719). Figure 1: Illustration of policy learning frameworks for IRS and CRS, including CRM [26], EAR [12], and SCPR [14].
domains or applications, since there are three different decisionmaking processes to be considered in CRS, including what attributes to ask, which items to recommend, and when to ask or recommend. It requires extra efforts to train an offline recommendation model [12,14] or pretrain the policy network with synthetic dialogue history [12,26]. (ii) The policy learning is hard to converge, since the conversation and recommendation components are isolated and lack of mutual influence during the training procedure.
To address these issues, in this work, we formulate the aforementioned three separated decision-making processes in CRS as a unified policy learning problem to harness the ultimate goal of CRS as well as fill the gap between the recommendation and conversation components during the training procedure. Such unified conversational recommendation policy learning (UCRPL) aims at learning a unified policy to decide the action, either ask an attribute or recommend items, at each conversation turn to maximize the cumulative utility over the whole MCR process. The overview of the proposed unified policy learning for CRS is depicted in Figure 2.
However, the UCRPL problem comes along with two challenges: (i) How to systematically combine conversation and recommendation components for unified policy learning? (ii) How to deal with sample efficiency issues? As the action space becomes overwhelmingly large in UCRPL, including all available attributes and items, it requires tremendous amount of interaction data to learn the optimal policy. Fortunately, the graph structure, capturing the rich correlated information among different types of nodes (i.e., users, items, and attributes), enables us to discover collaborative user preferences towards attributes and items. Thus, we can leverage the graph structure to integrate the recommendation and conversation components as an organic whole, where the conversation session can be regarded as a sequence of nodes maintained in the graph to dynamically exploit the conversation history for predicting the action at the next turn. On the other hand, although the connectivity of the graph can also be used to eliminate invalid actions by path reasoning [14], there are still a large number of candidates left for action searching. Since users are not likely to be interested in all items and attributes, we can focus on the potentially important candidates to improve the sample efficiency of UCRPL.
To this end, we propose a novel and adaptive graph-based reinforcement learning framework, namely UNIfied COnversational RecommeNder (UNICORN). Specifically, due to the evolving nature of CRS, we leverage a dynamic weighted graph to model the changing interrelationships among users, items and attributes during the conversation, and consider a graph-based Markov Decision Process (MDP) environment for simultaneously handling the  decision-making of recommendation and conversation. Then we integrate graph-enhanced representation learning and sequential conversation modeling to capture dynamic user preferences towards items and attributes. In addition, two simple yet effective action selection strategies are designed to handle the sample efficiency issue. Instead of enumerating the whole candidate item and attribute set, we adopt preference-based item selection and weighted entropy-based attribute selection strategies to only consider potentially important actions.
In summary, the contributions of this paper are as follows: • We formulate three separated decision-making processes in conversational recommender systems, namely when to ask or recommend, what to ask, and which to recommend, as a unified conversational recommendation policy learning problem. • To tackle the challenges in UCRPL problem, we propose a novel and adaptive reinforcement learning framework, namely UNIfied COnversational RecommeNder (UNICORN), based on dynamic weighted graph. To handle the sample efficiency issue, we further design two simple yet effective action selection strategies. • Experimental results show that the proposed method significantly outperforms state-of-the-art CRS methods across four public benchmark datasets and a real-world E-Commerce application.

RELATED WORKS
Conversational Recommendation. Based on the problem settings, current CRS studies can be categorized into four directions [5,11]: (1) Exploration-Exploitation Trade-offs for Cold-start Users [4,17,40]. These approaches leverage bandit approaches to balance the exploration and exploitation trade-offs for cold-start users in conversational recommendation scenarios. (2) Question-driven Approaches [3,41,50] aim at asking questions to users to get more information about their preferences, which is often addressed as "asking clarification/clarifying question". (3) Dialogue Understanding and Generation [16,18,47,48]. These studies focus on how to understand users' preferences and intentions from their utterances and generate fluent responses so as to deliver natural and effective dialogue actions. (4) Multi-round Conversational Recommendation [12,14,26]. Under this problem setting, the system asks questions about the user's preferences or makes recommendations multiple times, with the goal of achieving engaging and successful recommendations with fewer turns of conversations. Among these problem settings, we focus on the MCR problem. RL in Recommendation. Reinforcement learning (RL) has been widely introduced into recommender systems due to its advantage of considering users' long-term feedbacks [44,45]. RL-based recommendation formulates the recommendation procedure as an MDP of the interactions between the user and a recommendation agent, and employs RL algorithms to learn the optimal recommendation strategies [22,25,44,45]. Recent works on sequential recommendation [30,37] and interactive recommendation [39,49,51] adopt RL to capture users' dynamic preferences for generating accurate recommendations over time. The goal of these approaches typically is to learn an effective policy for determining which items to recommend. As for CRS, RL-based methods are adopted to improve the strategies of the other two decision processes, including (i) what attributes to ask [12,26] and (ii) when to ask or recommend [14].
In order to simplify the overall framework of MCR with better scalability and generality, we formulate these three core decision processes in CRS as a unified policy learning problem.
Graph-based Recommendation. Graph-based recommendation studies mainly leverage the graph structure for two purposes. The first one is to enhance the recommendation performance by graphbased representation learning, including exploiting the structure information for collaborative filtering [7,31,46], and adopting knowledge graph embeddings as rich context information [9,38].
The other group of studies models recommendation as a path reasoning problem for building explainable recommender systems [20,32]. Recent years have witnessed many successful applications of graphbased RL methods on different scenarios of recommender systems [14,15,33,36,42,49]. For example, Xian et al. [36] employ a policy-guided graph search method to sample reasoning paths for recommendation, which is enhanced with adversarial actor-critic for demonstration-guided path reasoning [42]. Lei et al. [15] and Zhou et al. [49] employ graph convolutional network (GCN) [10] for state representation learning to enhance the performance of traditional RL methods on recommendation policy learning. In this work, we study graph-based RL method for the conversational recommendation scenario based on a dynamic weighted graph.

PROBLEM DEFINITION
Multi-round Conversational Recommendation. In this work, we focus on the multi-round conversational recommendation (MCR) scenario [12,14], the most realistic conversational recommendation setting proposed so far, in which the CRS is able to ask questions about attributes or make recommendations multiple times. Specifically, on the system side, the CRS maintains a large set of items V to be recommended, and each item is associated with a set of attributes P . In each episode, a conversation session is initialized by a user specifying an attribute 0 . Then, the CRS is free to ask the user's preference on an attribute selected from the candidate attribute set P cand or recommend a certain number of items (e.g., top-) from the candidate item set V cand . Following the assumptions from Lei et al. [12], the user preserves clear preferences towards all the attributes and items. Thus, the user will respond accordingly, either accepting or rejecting the asked attributes or the recommended items. The CRS updates the candidate attribute and item sets, and decides the next action based on the user response. The system-ask and user-respond process repeats until the CRS hits the target item or reaches the maximum number of turn . Unified Conversational Recommendation Policy Learning. Multi-round conversational recommendation aims to make successful recommendations within a multi-round conversation session with the user. At each timestep , according to the observation on past interactions, the CRS selects an action , either asking an attribute or recommending items. In return, the user expresses his/her feedback (accept or reject). This process repeats until the CRS hits the user-preferred items or reaches the maximum number of turn . Such MCR task can be formulated as a Markov Decision Process (MDP). The goal of the CRS is to learn a policy maximizing the expected cumulative rewards over the observed MCR episodes as where is the state representation learned from the system state and the conversation history, is the action that the agent takes at timestep , and (·) is the intermediate reward, abbreviated as .

METHODOLOGY
The overview of the proposed method, UNICORN, is depicted in Figure 3, which consists of four main components: Graph-based MDP Environment, Graph-enhanced State Representation Learning, Action Selection Strategy, and Deep Q-Learning Network.

Graph-based MDP Environment
The MDP environment is responsible for informing the agent about the current state and possible actions to take, and then rewards the agent based on how the current policy fits the observed user interactions. Formally, the MDP environment can be defined by a tuple (S, A, T , R), where S denotes the state space, A denotes the action space, T : S × A → S refers to the state transition function, and R : S × A → R is the reward function.

State.
As for the graph-based MDP environment, the state ∈ S at timestep is supposed to contain all the given information for conversational recommendation, including the previous conversation history and the full graph G that includes all the users, items, and attributes. Given a user , we consider two major elements: where rej ] denotes the conversation history until timestep , and G ( ) denotes the dynamic subgraph of G for the user at timestep (The graph construction will be introduced in Section 4.2). P denotes the user-preferred attribute. P rej and V rej are the attributes and items rejected by the user, respectively. The initial state 0 is initialized by the user-specified attribute 0 where V P ( ) is the set of item vertices directly connecting all P ( ) (i.e., items satisfying all the preferred attributes), and P V ( ) cand is the set of attribute vertices directly connecting to one of V ( ) cand (i.e., attributes belonging to at least one of the candidate items).

Transition.
We consider that the current state will transition to the next state +1 when the user responds to the action . In specific, if CRS asks an attribute and the user accepts it, the next state +1 will be updated by P ( +1) = P ( ) ∪ . Conversely, if the user rejects the action , +1 will be updated by P , G ( +1) ].

Reward.
Following previous MCR studies [12,14], our environment contains five kinds of rewards, namely, (1) rec_suc , a strongly positive reward when the user accepts the recommended items, (2) rec_fail , a negative reward when the user rejects the recommended items, (3) ask_suc , a slightly positive reward when the user accepts the asked attribute, (4) ask_fail , a negative reward when the user rejects the asked attribute, and (5) quit , a strongly negative reward when reaching the maximum number of turns.

Graph-enhanced State Representation
As we formulate conversational recommendation as a unified policy learning problem over a graph-based MDP environment, it is required to encode both the conversational and graph structural information into the latent distributed representations. In order to make use of the interrelationships among users, items, and attributes, we first adopt graph-based pre-training methods [2,35] to obtained node embeddings for all the nodes in the full graph G. Figure 3, we represent the current state of the graph-based MDP environment as a dynamic weighted graph. Formally, we denote an undirected weighted graph as G = (N, ), with the node ∈ N , the adjacency matrix element , denoting the weighted edges between nodes and . In our case, given the user , we denote the dynamic graph at timestep as G ( ) = (N ( ) , ( ) ):

Dynamic Weighted Graph Construction. As shown in
where ( ) is a scalar indicating the recommendation score of the item in the current state. In order to incorporate the user preference as well as the correlation between the asked attributes and the items, such weight ( ) is calculated as where (·) denotes the sigmoid function, , , and are the embeddings of the user, item, and attribute, respectively.

4.2.2
Graph-based Representation Learning. In order to comprehensively take advantage of the correlation information among the involved user, items, and attributes from the connectivity of the graph, we employ a graph convolutional network (GCN) [10] to refine the node representations with structural and relational knowledge. The representations of the node in the ( + 1)-th layer can be computed by: where N denotes the neighboring indices of the node , and are trainable parameters representing the transformation from neighboring nodes and the node itself, and is a normalization adjacent matrix as = − 1 2 − 1 2 with = , . 4.2.3 Sequential Representation Learning. Apart from the interrelationships among the involved user, items, and attributes, the CRS is also expected to model the conversation history in the current state. Unlike previous studies [12,14] that adopt heuristic features for conversation history modeling, we employ Transformer encoder [29] for capturing the sequential information of the conversation history as well as attending the important information for deciding the next action. As described in [29], each Transformer layer consists of three components: (i) The layer normalization is defined as LayerNorm(·). (ii) The multi-head attention is defined as MultiHead( , , ), where , , are query, key, and value, respectively. (iii) The feed-forward network with ReLU activation is defined as FFN(·). Take the -th layer for example: where ∈ R × denotes the embeddings, and is the sequence length. In our case, the input sequence (0) is the accepted attributes P ( ) in the current conversation history with the learned graph-based representation { ( ) : ∈ P ( ) }, where is the number of layers in GCN. After the sequential learning with Transformer layers, we can aggregate the information learned from both the graph and the conversation history by a mean pooling layer to obtain the state representation of : For simplicity, we denote the learned state representation of as ( ), where is the set of all network parameters for state representation learning, including GCN and Transformer layers.

Action Selection Strategy
A large action search space will harm the performance of the policy learning to a great extent [14]. Thus, it attaches great importance to handle the overwhelmingly large action space in UCRPL. To this end, we propose two simple strategies to improve the sample efficiency for candidate action selection. Preference-based Item Selection. In general, for candidate items to be recommended, we can consider only the action of making recommendations from a small number of candidate items that fit the user preference the most, since users are not likely to be interested in all items. To achieve this, we select top-candidate items from V ( ) cand into the candidate action space A at each timestep , which is ranked by the recommendation score ( ) in Eq. (6).
Weighted Entropy-based Attribute Selection. Whereas for candidate attributes to be asked, the expected one is supposed to be able to not only better eliminate the uncertainty of candidate items, but also encode the user preference. Inspired by [14], we adopt weighted entropy as the criteria to prune candidate attributes: where V denotes the items that have the attribute . Similar to item selection, we also select top-candidate attributes from P ( ) cand into A based on the weighted entropy score ( ) .

Deep Q-Learning Network
After obtaining the graph-enhanced state representation and the candidate action space, we introduce the deep Q-learning network (DQN) [21] to conduct the unified conversational recommendation policy learning. We further implement some techniques to enhance and stabilize the training of DQN. The training procedure of the Unified Conversational Recommender is presented in Algorithm 1.

4.4.1
Dueling Q-Network. Following the standard assumption that delayed rewards are discounted by a factor of per timestep, we define the Q-value ( , ) as the expected reward based on the state and the action . As shown in the rightmost part of Figure 3, the dueling Q-network [34] employs two deep neural networks to compute the value function (·) and advantage function (·), respectively. Then the Q-function can be calculated by: where (·) and (·) are two separate multi-layer perceptions with parameters and , respectively, and let = { , }. The optimal Q-function * ( , ), which has the maximum expected reward achievable by the optimal policy * , follows the Bellman equation [1] as: 4.4.2 Double Q-Learning with Prioritized Experience Replay. During each episode in the MCR process, at each timestep , the CRS agent obtains the current state representation ( ) via the graph-enhanced state representational learning described in Section 4.2. Then the agent selects an action from the candidate action space A , which is obtained via the action selection strategies described in Section 4.3. Here we incorporate -greedy method to balance the exploration and exploitation in action sampling (i.e., select a greedy action based on the max Q-value with probability 1 − , and a random action with probability ).
Then, the agent will receive the reward from the user's feedback. According to the feedback, the current state transitions to the next state +1 , and the candidate action space A +1 is updated accordingly. The experience ( , , , +1 , A +1 ) is then stored into the replay buffer D. To train DQN, we sample mini-batch of experiences from D, and minimize the following loss function: where is the target value based on the currently optimal * . To alleviate the overestimation bias problem in conventional DQN, we adopt Double Q-learning [28], which employs a target network ′ as a periodic copy from the online network. The target value of the online network is then changed to: where ′ denotes the parameter of the target network, which is updated by the soft assignment as: where is the update frequency.
In addition, the conventional DQN samples uniformly from the replay buffer. In order to sample more frequently those important transitions from which there is much to learn, we employ prioritized replay [24] as a proxy for learning potential, which samples transitions with probability relative to the absolute TD error:

Model Inference.
With the learned UNICORN model, given a user and his/her conversation history, we follow the same process to obtain the candidate action space and the current state representation, and then decide the next action according to max Q-value in Eq. (13). If the selected action points to an attribute, the system will ask the user's preference on the attribute. Otherwise, the system will recommend top-items with the highest Q-value to the user.

EXPERIMENT 5.1 Dataset
We evaluate the proposed method, UNICORN, on four existing multi-round conversational recommendation benchmark datasets, and further conduct evaluation on a real-world E-Commerce platform. The statistics of these datasets are presented in Table 1.
• LastFM and Yelp. The LastFM dataset is used for evaluation on music artist recommendation, while the Yelp dataset is for business recommendation. Lei et al. [12] manually categorize the original attributes in LastFM into 33 coarse-grained groups, and build a 2-layer taxonomy with 29 first-layer categories for Yelp. • LastFM* and Yelp*. Lei et al. [14] consider that it is not realistic to manually merge attributes for practical applications, so they adopt original attributes to reconstruct these two datasets. For a fair comparison, we adopt both versions for experiments. • E-Commerce. In order to evaluate the proposed method in realworld E-Commerce scenario, we collect the dataset by sampling logs from Taobao, the largest E-Commerce platform in China, in the same way as LastFM and Yelp. We randomly sample 30,000 items from the Women_Dress category and a certain number of users who have interacted with these items. And we treat the concatenation of the product property and the property value as the attribute to be asked, e.g., "Color=Red", where "Color" is a product property and "Red" is a property value. Following the MCR data construction described in Lei et al. [12], we obtain the E-Commerce dataset with the statistics shown in Table 1. As for graph construction, we consider two kinds of relations, including "purchased_by (item→ user)" and "belong_to (attribute→ item)". Compared with the imbalanced ratio of #items:#attributes at LastFM (0.88:1) and Yelp (119:1), the E-Commerce dataset preserves a large number of items as well as attributes, which is more in line with real-world applications in E-Commerce.

User Simulator.
Due to the interactive nature of MCR, it needs to be trained and evaluated by interacting with users. Following the user simulator adopted in [12,26], we simulate a conversation session for each observed user-item interaction pair ( , ).
We regard the item as the ground-truth target item and treat its attribute set P as the oracle set of attributes preferred by the user in this conversation session. The session is initialized by the simulated user who specifies a certain attribute randomly chosen from P . Then the session follows the process of "System Ask, User Respond" [41] as described in Section 4.

Baselines.
We compare the proposed method with several state-of-the-art methods on MCR as follows: • Max Entropy. This is a rule-based strategy to decide the next action, where the CRS selects an attribute to ask based on the maximum entropy within the current state, or chooses to recommend the top-ranked items with a certain probability [12]. • Abs Greedy [4]. This method only performs recommendation actions and updates itself until the CRS makes a successful recommendation or exceeds the maximum turns of conversation. • CRM [26]. This method is originally designed for single-round conversational recommendation, which employs policy gradient [27] to learn the policy deciding when and which attributes to ask. We follow [12] to adapt this method into MCR scenario. • EAR [12]. A three-stage method is proposed to enhance the interaction between the conversation and recommendation components with a similar RL framework as CRM. • SCPR [14]. This is the state-of-the-art method on MCR setting, which leverages interactive path reasoning on the graph to prune off candidate attributes and adopts the DQN [21] framework to determine when to ask or recommend.

Evaluation Metrics.
Following previous studies on multiround conversational recommendation [12,14], we adopt success rate at the turn (SR@ ) [26] to measure the cumulative ratio of successful conversational recommendation by the turn . Besides, average turn (AT) is adopted to evaluate the average number of turns for all sessions (if the conversation session reaches the maximum turn , the turn for such session is also counted as ). The higher SR@ indicates a better performance of the CRS at a turn , while the lower AT means an overall higher efficiency.
Although SR@ and AT are widely adopted for the evaluation of CRS, both of them are not sensitive to the rank order in the recommendation results and only consider a certain aspect of the performance of CRS. In order to conduct a comprehensive evaluation of CRS, we propose to extend the normalized discounted cumulative gain (NDCG@ ) to be a two-level hierarchical version, namely hNDCG@( , ), with the definition as follows: where and represent the number of conversation turns and recommended items in each turn, ( , ) denotes the relevance of the result at the turn and position . Then hNDCG@( , ) can be drawn from hDCG@( , ) with the same way as the original NDCG@ . Since there is only one target item for each session in MCR, we simply use hDCG@( , ) for evaluation. The intuition behind hNDCG@( , ) is that the less number of turns of a successful session is favorable for the CRS, while the target item is expected to be ranked higher in the recommendation list at the success turn.

Implementation Details.
Following [14], we split the E-Commerce dataset by 7:1.5:1.5 for training, validation, and testing, and set the size of the recommendation list as 10, the maximum turn as 15. We adopt TransE [2] from OpenKE [6] to pretrain the node embeddings in the constructed graph with the training set. We adopt the user simulator described in Section 5.2.1 to interact with the CRS for online training the model using the validation set. For all implemented methods, we conduct the online training for 10,000 episodes. To maintain a fair comparison with other baselines [12,14], we adopt the same reward settings to train the proposed model:  GCN layers and Transformer layers are set to be 2 and 1, respectively. The numbers of selected candidate attributes and items are set to be 10. During the training procedure of DQN, the size of experience replay buffer is 50,000, and the size of mini-batch is 128. The learning rate and the 2 norm regularization are set to be 1e-4 and 1e-6, with Adam optimizer. The discount factor and the update frequency are set to be 0.999 and 0.01. Table 2 shows the performance comparison between the proposed method, UNICORN, and all baselines across five datasets. In general, UNICORN outperforms all the baselines by achieving a significantly higher success rate and less average turn, which is also comprehensively validated by the improvements on hDCG. As for the real-world E-Commerce dataset, SCPR outperforms EAR and CRM, whose performance is largely affected by the large action space in E-Commerce dataset. Despite the effectiveness of SCPR to handle the issue of large action space in CRS, its performance in such a real-world application is still restricted by the separation of its conversation and recommendation components. Our UNICORN not only enables the conversation and recommendation to be mutually enhanced during the training process, but also attains an effective sample efficiency with the proposed action selection strategies. This leads to a substantial margin  from these baselines, about 18% for SR@15, 2 turns for AT, and 30% for hDCG. Detailed analyses can be found as follows.

5.3.2
Training Efficiency. Figure 4 shows the test performance curves of different methods. Since Max Entropy and Abs Greedy are unsupervised methods, their curves are presented as two lines for comparisons. It can be clearly observed that UNICORN is trained more stably and requires fewer training episodes (i.e., interaction data) to achieve a better performance than other strong baselines. Among these baselines, the curve of SCPR is the most vibrant, since it only considers the policy of when to ask or recommend, while the decisions of question-asking and recommendation are made by two separated components. As for EAR and CRM, due to the large action space in the last three datasets, there is no much performance increase during the online training process, even getting worse. These results demonstrate the efficiency and effectiveness of the proposed unified policy learning for CRS.

Comparison at Different Conversation Turns.
Besides SR@15, we also present the performance comparison of success rate at each turn (SR@ ) in Figure 5. In order to better observe the differences among different methods, we report the relative success rate compared with the state-of-the-art baseline SCPR. For example, the line of = 0 represents the curve of Success Rate* for SCPR against itself. There are several notable observations as follows: (i) The proposed UNICORN substantially and consistently outperforms these baselines across all the datasets and almost each turn in the conversation session.
(ii) Due to the nature of greedy recommendation approach (Abs Greedy), it may successfully hit target items at the early stage of the conversation, leading to a relatively strong performance at the first few turns, but the performance falls quickly as the turn increases.
(iii) UNICORN achieves an outstanding performance in the middle stage of the conversation, where there are still a large number of candidate items and attributes to be pruned. This shows the strong scalability of UNICORN to effectively handle large candidate action space in different situations.
(iv) The performance of SCPR is getting closer to UNICORN at the latter stage of the conversation, as the candidate item and attribute set is getting smaller and the task becomes easier.
(v) EAR and CRM share similar performance as Abs Greedy in those datasets with a large candidate attribute set, i.e., Yelp* and E-Commerce, indicating their policy learning is merely working when encountering a large action space.

Model Components.
We first evaluate the model components for the state representation learning, including the graphbased representation learning and the sequential representation learning. The ablation studies are presented in the first part in Table 3 (row (a-b)). We observe that the performance on 4 out of 5 datasets suffers a larger decrease by discarding sequential learning (row (a)) than discarding graph-based learning (row (b)). We attribute this to two reasons: (i) The pretrained TransE embeddings have already encoded certain graph-based knowledge into the node representations. (ii) Since there are relatively larger number of attributes in these four datasets than LastFM, it is more important to model the interrelationships among diverse user-accepted attributes for capturing user preferences.

5.4.2
Pre-training Embeddings. The second part in Table 3 (row (c-d)) presents the results that we replace pretrained TransE embeddings with randomly initialized embeddings (row (c)) and pretrained embeddings from FM model described in Lei et al. [12] (row (d)). We observe a substantial performance gap between UNI-CORN with randomly initialized embeddings and that with pretrained embeddings, either TransE or FM. This result shows that  pretraining is necessary and simply online training with interactive conversations is far from efficient and sufficient for training a CRS with limited interaction data. In addition, using TransE embeddings further improves the performance from FM embeddings to a great extent, which also validates the advantages of graph-enhanced RL. Table 3 (row (e-h)) presents the results that we replace or discard the proposed action selection strategies. One alternative attribute selection strategy is to adopt the same strategy as the preference-based item selection by changing the object from items to attributes. Another one is to use the original maximum entropy function [12]. The results (row (e,f)) show that the performance of UCRPL suffers a noticeable decrease when adopting the preference-based or entropy-based strategy, indicating that it is required to consider both the user preference and the capability of reducing candidate uncertainty when deciding the asked attribute. Without attribute selection, we observe that the impact on applications with small action space (e.g., LastFM and Yelp) is less than those with large action space (e.g., LastFM*, Yelp*, and E-Commerce). UNICORN is merely working without item selection, since there are no pretrained recommendation components in the framework and the preference-based item selection serves as an auxiliary item recall process.

Parameter Sensitivity Analysis
The upper part in Table 4 summarizes the experimental results (hDCG) by varying the number of selected candidate actions. Since similar conclusions can also be drawn on other datasets, we only report the results on LastFM* and E-Commerce datasets due to space limit. As for the number of selected attributes, it is likely to discard the important attributes when only selected the attribute with the highest weighted entropy (e.g., =1). However, within a certain training interaction period (10,000 episodes in our case), UNICORN generally achieves the best performance when only selecting a small number of candidate items for policy learning.
The results also demonstrate the necessity of pruning the available actions when there is a large action search space in UCRPL. The lower part shows the experimental results by varying the number of network layers. As for GCN, 1-hop aggregation ( =1) is not enough for capturing all the useful information for graph representational learning. However, there is no much difference between 2-hop ( =2) and 3-hop ( =3). Besides, for Transformer, we can see that 1-layer ( =1) is sufficient for a good performance.

Qualitative Analysis
In order to intuitively study the difference between the proposed UNICORN and other state-of-the-art CRS methods, we randomly sample a real-world interaction from the E-Commerce dataset. The generated conversations by UNICORN, SCPR, EAR, and CRM with the user simulator are presented in Figure 6. Facing the large candidate action space, CRM tends to only trigger the recommendation component to make recommendations, and EAR continuously asks the questions that are not preferred by the user. Despite the success of SCPR in predicting user-preferred attributes, the policy learning in SCPR only decides when to ask or recommend, based on the number of candidate items, which leads to some unnecessary or redundant question-asking turns. UNICORN systematically addresses these issues by making a comprehensive decision of the next action.

CONCLUSIONS
In this work, we formulate three separated decision-making processes in CRS, including when to ask or recommend, what to ask and which to recommend, as a unified policy learning problem. To tackle the unified conversational recommendation policy learning problem, we propose a novel and adaptive RL framework, which is based on a dynamic weighted graph. In addition, we further design two simple yet effective action selection strategies to handle the sample efficiency issue. Experimental results show that the proposed method significantly outperforms state-of-the-art CRS methods across four benchmark datasets and the real-world E-Commerce application with remarkable scalability and stability.