Gradient-based Optimization for Bayesian Preference Elicitation

Ivan Vendrov, Tyler Lu, Qingqing Huang, Craig Boutilier

Abstract

Effective techniques for eliciting user preferences have taken on added importance as recommender systems (RSs) become increasingly interactive and conversational. A common and conceptually appealing Bayesian criterion for selecting queries is expected value of information (EVOI). Unfortunately, it is computationally prohibitive to construct queries with maximum EVOI in RSs with large item spaces. We tackle this issue by introducing a continuous formulation of EVOI as a differentiable network that can be optimized using gradient methods available in modern machine learning (ML) computational frameworks (e.g., TensorFlow, PyTorch). We exploit this to develop a novel, scalable Monte Carlo method for EVOI optimization, which is more scalable for large item spaces than methods requiring explicit enumeration of items. While we emphasize the use of this approach for pairwise (or k-wise) comparisons of items, we also demonstrate how our method can be adapted to queries involving subsets of item attributes or "partial items," which are often more cognitively manageable for users. Experiments show that our gradient-based EVOI technique achieves state-of-the-art performance across several domains while scaling to large item spaces.

Introduction

In modern conversational recommender systems, the goal is to minimize user effort by asking the most informative questions possible. The "gold standard" for this task is the Expected Value of Information (EVOI), which identifies the query that will most significantly improve recommendation quality after a user responds. However, maximizing EVOI is a combinatorial challenge; in a catalog of a million items, finding the optimal pair to compare involves trillions of possibilities. Existing heuristics often fail to scale or rely on oversimplifying assumptions. This research addresses the computational intractability of EVOI, making principled Bayesian elicitation practical for real-world, large-scale systems.

Methodology

The researchers propose a continuous formulation of EVOI. Rather than searching through discrete item lists, items are represented as vectors in a continuous embedding space. This transformation allows the preference elicitation utility (PEU) to be modeled as a differentiable network.

Continuous formulation of EVOI as a differentiable network, showing the flow from inputs to preference elicitation utility (PEU) metrics.

Key Components:

  1. Continuous Relaxation: By allowing item attributes in a query to vary continuously, the discrete search problem becomes a differentiable optimization task.
  2. Gradient-Based Optimization: Standard ML tools like the Adam optimizer can be used to navigate the EVOI gradient and identify the most informative "hypothetical" items.
  3. Projection (Deep Retrieval): Once optimal hypothetical items are found, they are projected back onto the nearest actual items in the catalog to generate a valid user query.
  4. Partial Comparisons: The method extends to ContPartial, which generates queries about specific attributes (e.g., "Do you prefer 'action' or 'drama'?") rather than full items, reducing the cognitive load on the user.

Experimental Results

The methodology was evaluated across several datasets, including a synthetic environment, MovieLens-100k, and the large-scale Goodreads dataset (2 million items).

Scalability and Performance

On the Goodreads dataset, traditional greedy methods required over 17 seconds to generate a single query. In contrast, the proposed ContFree method achieved this in under one second, maintaining consistent speed regardless of catalog size. Despite the continuous relaxation, these methods achieved "regret" (the difference between the recommendation and the user's true preference) comparable to or better than state-of-the-art discrete heuristics.

Regret reduction on the Goodreads dataset (2M items) comparing various initialization strategies and algorithms.

As shown in Figure 6, the choice of initialization (e.g., "balanced" vs. "rand_user_top_item") impacts the speed of convergence, but the continuous methods consistently drive regret down significantly within the first few questions. In MovieLens experiments, user regret was reduced by 90% in just 5 to 6 queries.

Discussion and Future Work

By framing EVOI as a network, the researchers leverage highly optimized ML hardware (GPUs/TPUs) and software, shifting the burden from custom combinatorial algorithms to standard gradient descent. The use of hypothetical items as anchors effectively bypasses the "curse of dimensionality" inherent in large catalogs.

However, challenges remain. The EVOI objective is non-convex, meaning gradient descent can occasionally get stuck in local optima. The authors currently mitigate this with multiple random restarts. Future work may involve integrating natural language processing to create more personalized and human-like elicitation queries, moving beyond fixed attribute tags to more fluid conversational interfaces.

Summary updated

Abstract

Effective techniques for eliciting user preferences have taken on added importance as recommender systems (RSs) become increasingly interactive and conversational. A common and conceptually appealing Bayesian criterion for selecting queries is expected value of information (EVOI). Unfortunately, it is computationally prohibitive to construct queries with maximum EVOI in RSs with large item spaces. We tackle this issue by introducing a continuous formulation of EVOI as a differentiable network that can be optimized using gradient methods available in modern machine learning (ML) computational frameworks (e.g., TensorFlow, PyTorch). We exploit this to develop a novel, scalable Monte Carlo method for EVOI optimization, which is more scalable for large item spaces than methods requiring explicit enumeration of items. While we emphasize the use of this approach for pairwise (or k-wise) comparisons of items, we also demonstrate how our method can be adapted to queries involving subsets of item attributes or "partial items," which are often more cognitively manageable for users. Experiments show that our gradient-based EVOI technique achieves state-of-the-art performance across several domains while scaling to large item spaces.
BibTeX
@inproceedings{vendrov2020gradient,
  author = {Ivan Vendrov and Tyler Lu and Qingqing Huang and Craig Boutilier},
  title = {{Gradient-based Optimization for Bayesian Preference Elicitation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=IoPZDKikKy},
}
Figure