Chain-of-Choice Hierarchical Policy Learning for Conversational Recommendation

Before each turn $T$, the CRS selects an option $\omega_{T}$ from $\Omega$ to decide the action type and extend the state space. The state-option pair $(s_{t},\omega_{T})$ at timestep $t$ in turn $T$ contains $\{u,\mathcal{V}^{(t)},\mathcal{P}^{t},\omega_{T}\}$, where $\mathcal{V}^{(t)}=\mathcal{V}^{(t)}_{rej}\cup\mathcal{V}^{(t)}_{cand}$, and $\mathcal{P}^{(t)}=\mathcal{P}^{(t)}_{acc}\cup\mathcal{P}^{(t)}_{rej}\cup\mathcal{P}^{(t)}_{cand}$. $\mathcal{P}^{(t)}_{acc}$ denotes all the accepted attributes, $\mathcal{V}^{(t)}_{rej}$ and $\mathcal{P}^{(t)}_{rej}$ denotes all the rejected items and attributes, $\mathcal{V}^{(t)}_{cand}$ and $\mathcal{P}^{(t)}_{cand}$ denotes the candidate items and attributes.

For $(s_{t},\omega_{rec})$ at timestep $t$, the candidate action space $\mathcal{A}_{t}$ is $\mathcal{V}^{(t)}_{cand}$ for the option $\omega_{rec}$. We have $\mathcal{V}_{cand}^{(t)}=\mathcal{V}_{\mathcal{P}_{acc}^{(t)}}\backslash\mathcal{V}_{rej}^{(t)}$ where $\mathcal{V}_{\mathcal{P}_{acc}^{(t)}}$ denotes all the items which contain all the accepted attributes. For another pair $(s_{t},\omega_{ask})$, the candidate attribute space $\mathcal{P}_{cand}^{(t)}=\mathcal{P}_{\mathcal{V}_{cand}^{(t)}}\backslash(\mathcal{P}_{acc}^{(t)}\cup\mathcal{P}_{rej}^{(t)})$ and $\mathcal{P}_{\mathcal{V}_{cand}^{(t)}}$ denotes the attributes of all the candidate items.

For the state-option pair $(s_{t},\omega_{ask})$, after the selection of $a_{t}$ at timestep $t$, if the CRS predicts that the user accepts $a_{t}$, then $s_{t}$ will transiton to $s_{t+1}$ and $\mathcal{P}_{acc}^{(t+1)}=\mathcal{P}_{acc}^{(t)}\cup a_{t}$. If rejected, $\mathcal{P}_{rej}^{(t+1)}$ are updated to $\mathcal{P}_{rej}^{(t)}\cup a_{t}$. The next candidate action space is updated to $\mathcal{P}_{cand}^{(t+1)}=\mathcal{P}_{cand}^{(t)}\backslash a_{t}$. The transition is similar for another pair $(s_{t},\omega_{rec})$.

To promote a universal and uniform distribution of rewards $\mathcal{R}$, a simplification of the reward structure is implemented as (1) $r_{ask\_suc}$: a slight reward when the user accepts the asked attribute, (2) $r_{ask\_fail}$: a slight penalty when the user rejects the asked attribute, (3) $r_{rec\_fail}$: a slight penalty when the user rejects the recommended item, (4) $r_{rec\_suc}$: a strong reward when the user accepts the recommended item.

We denote the dynamic undirected graph as ${G}_{u}=(\mathbf{V},\mathbf{A})$. The node set $\mathbf{V}$ consists of the related user, items, and attributes. And $\mathbf{A}$ is a $n\times n$ adjacency matrix representing each node’s edge weight in $\mathbf{V}$. During each timestep in the conversation, $G_{u}$ dynamically changes the node and adjacency matrix as follows:

where $w_{v}^{(t)}$ denotes the user’s preference score for the item $v$, calculated as:

where $\sigma(\cdot)$ is the sigmoid function and ${e_{u},e_{v},e_{p}}$ are pre-trained embeddings initialized as [2]. We can also calculate the preference score for candidate attributes at the current state: $w_{p}^{(t)}=\sigma(e_{u}^{\top}e_{p}+\sum\nolimits_{p\in\mathcal{P}_{acc}^{(t)}}\overline{e}_{p}^{\top}e_{p}-\sum\nolimits_{p\in\mathcal{P}_{rej}^{(t)}}\overline{e}_{p}^{\top}e_{p})$. With the calculated weights, we can reduce the action space size for different options by selecting the top-$K$ candidates in the action selection section 4.3, 4.4.

By incorporating both the current conversation and the historical conversation data, we can create a comprehensive global knowledge graph denoted as $G$. This knowledge graph captures the evolving preferences of users over time. To effectively leverage the correlation information among users, items, and attributes represented in the graph, we implement a two-layer graph convolutional network (GCN) [5, 17] as follows:

where $l$ is the layer number, $\mathcal{N}_{s}$ denotes the neighbors of $n_{s}$ and $D$ denotes the degree matrix with $D_{ii}=\sum\nolimits_{j}\bm{A}_{i,j}$. $B^{(l)}$ and $W^{(l)}$ are both trainable network parameters. To further extract the sequential information of the current conversation, we use a single-layer multi-head attention [12] network and calculate the final state representation by an average pooling:

After the sequential learning, the final state representation is generated, and $\theta_{S}$ denotes all parameters for the dynamic-graph state representation module.

To fairly evaluate CoCHPL, we utilized four widely recognized benchmark datasets [18] that are commonly used for conversational recommendation tasks involving multiple choice questions, namely: LastFM, Yelp, Amazon-Book and MovieLens. The statistics of datasets are shown in Table 1.

• •

  LastFM is a popular online platform that focuses on music recommendations and social networking. The original attributes in LastFM were treated as attribute instances, and a clustering method was utilized to identify 34 attribute types.

• •

  Yelp serves for business recommendations. In the context of Yelp, a two-layer taxonomy was created by [6], comprising 29 attribute types and 590 attribute instances. The attribute types in the taxonomy represent different categories or aspects of businesses, such as price range, ambiance, service quality, and more.

• •

  Amazon-Book is widely used for book recommendations. Users and items with a minimum of 10 interaction records are retained. Entities and relations in the knowledge graph are considered as attribute instances and attribute types, respectively.

• •

  MovieLens is a rating dataset that contains user ratings for movies. Interactions with ratings above three are retained, and the knowledge graph entities and relations are considered as attribute instances and attribute types.

To benchmark our model’s performance, we compared it against eight established baselines:

• •

  Abs Greedy [3] only recommends items in each turn until the user accepts the recommendation or the total turn number exceeds the maximum limit.

• •

  Max Entropy [6] asks or recommends the top-scored instances with the maximum entropy with a certain probability.

• •

  CRM [9] introduces a policy that selects the action and terminates the conversation when the recommendation is rejected.

• •

  EAR [6] proposes a three-stage pipeline called Estimation–Action-Reflection for selecting actions and optimizing the model.

• •

  SCPR [7] employs graph-based path reasoning to retrieve actions and graph embedding to represent user preferences dynamically.

• •

  UNICORN [4] offers a comprehensive approach for selecting optimal actions, integrating both the conversation and recommendation components.

• •

  MCMIPL [18] focuses on single-type attribute selection in multiple-choice question settings and uses a multi-interest extractor for preference capture.

• •

  DAHCR [20] employ a director to select the action type and an actor to choose the asked attribute or recommended item.

To ensure a fair comparison in the MTAMCR scenario, we made two kinds of modifications to UNICORN, MCMIPL, and DAHCR:

• •

  Single-Type attributes (-S): Also known as attribue type-based multiple choice [18]. In each round, CRS selected one attribute type and then chose multiple attribute instances within that type.

• •

  Multi-Type attributes (-M): In each round, we selected the top-K attribute instances with the highest Q-values, which could be from different or the same attribute types.

We evaluate the performance of our MCR recommendation system using three key metrics: (1) Success rate (SR@t) measures the cumulative ratio of successful recommendations within a maximum of $t$ turns. (2) Average turn (AT) evaluates the average number of terminated conversation turns for all sessions. Lower values indicate higher efficiency in the recommendation process. (3) hDCG@(T, K) [4] assesses the ranking performance of recommended items by considering the target item’s rank in the recommendation list, which extends the normalized discounted cumulative gain metric.

We set the maximum turns $T$ to 15, and the agent can recommend up to $k_{v}=10$ items or ask $k_{p}=3$ attribute-related questions at every turn. We pre-train the graph nodes with TransE [2], and train each dataset for $10,000$ episodes online. Adam optimizer with the learning rate $1e-4$ and discount factor $\gamma$ is set to be 0.999. For our method CoCHPL, the reward settings were as follows: $r_{ask\_acc}=1e-2$, $r_{ask\_rej}=-1e-4$, $r_{rec\_rej}=-1e-4$, and $r_{rec\_suc}=1$. We found that the effect of retrieving accepted attributes was minimal in MovieLens, and then the reward for $r_{ask\_acc}$ was adjusted to $1e-5$ for it. The rewards for all state-of-the-art baselines remain unchanged as [18].

As detailed in Table 2, CoCHPL surpasses eight baselines across SR@15, AT, and hDCG metrics. Baselines with binary yes/no question settings exhibit lower efficiency and longer turn requirements for successful recommendations (Figure 1(a)). In single-type attributes scenarios, UNICORN-S, MCMIPL-S, and DAHCR-S show modest improvements, while in multi-type attributes contexts, UNICORN-M, MCMIPL-M, and DAHCR-M display enhanced success rates and reduced average turns, which indicates the effectiveness of our MTAMCR approach in preference capture. CoCHPL’s chain-of-choice generation leads to marked improvements in success rates and efficiency across benchmark datasets, notably reducing the number of turns for successful recommendations. In critical datasets like Yelp and Amazon-Book, CoCHPL demonstrates significant advancements over top methods with relative increases of $18.3\%$, $8.6\%$, and $6.9\%$ in SR@15, AT, and hDCG, respectively. For a clear comparison, we benchmarked against MCMIPL-M’s SR, with differences in SR among methods serving as a measure of relative success rate (Figure 4) and the comparison highlights the superior performance of CoCHPL, especially in Yelp and Amazon-Book, where extensive attribute preference extraction is essential.

We performed an ablation study on the Yelp and Amazon-Book datasets to assess the impact of different components on system performance as follows: (1) w/o policy over options: The CRS randomly selects options (action types) in each turn. (2) w/o intra-option policy (ask): The CRS chooses the top-$K$ attribute instances with the highest Q-value at every turn. (3) w/o intra-option policy (recommend): The CRS selected the top-$K$ items with the highest Q-value at each turn. (4) w/o termination function: The CRS asks for or recommends the maximum number of instances in each turn without appropriate termination. (5) w/o feedback prediction function: The CRS randomly predicts whether the user would accept or reject the previous choice. From Table 3, we can observe that short intra-option policy (ask) and long policy over options play crucial roles in performance improvement, which suggests that learning how to select options and effectively generate multiple-choice questions about attributes is essential in the MTAMCR scenario. Additionally, the significance of the termination and feedback prediction functions underscores the importance of learning appropriate termination conditions and the necessity of simulating user behavior during the chain-of-choice generation process.

Our study, using Yelp and Amazon-Book datasets, assessed the reasoning capabilities of our model, CoCHPL, against three baselines: UNICRON-M, MCMIPL-M, and DAHCR-M. We varied the number of attribute instances requested from 1 to 5 per turn as shown in Figure 5. We noted that while the success rate of baseline models improved with an increased number of attribute instances, the marginal gains diminished over time, approaching a plateau. This trend suggests that these models tend to select numerous but less effective attribute instances, leading to suboptimal exploitation of user preferences. In contrast, CoCHPL demonstrated a nearly linear performance improvement in both datasets. A case study depicted in Figure 6 further reinforces CoCHPL’s superiority. Unlike DAHCR, which selects the top-$2$ attribute instances based on Q-values, often resulting in homogenous choices due to similar embeddings, CoCHPL dynamically predicts user feedback and recalculates Q-values after each selection, prioritizing the top-$1$ attribute for subsequent choices. Both evaluations demonstrate that CoCHPL effectively diversifies and deepens the dependency among attributes, significantly enhancing the overall recommendation quality.