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 computational frameworks (e.g., TensorFlow, PyTorch). We exploit this to develop a novel Monte Carlo method for EVOI optimization, which is much 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 recommender systems, passive observation of user clicks is often insufficient for deep personalization. Systems must frequently engage in "active" preference elicitation—asking targeted questions like "Do you prefer Movie A or Movie B?"—to refine their internal models. The gold standard for selecting these questions is the Expected Value of Information (EVOI), which identifies the query expected to maximize recommendation improvement.
However, calculating optimal EVOI is a combinatorial nightmare. In a catalog of one million items, there are approximately $10^{12}$ possible pairs to evaluate. Traditional heuristics are either too slow for real-time interaction or fail to scale beyond small datasets. This research introduces a way to make Bayesian preference elicitation scalable to millions of items by relaxing the discrete item space into a continuous one and leveraging gradient-based optimization.
Methodology: Continuous Relaxation of EVOI
The core innovation of this work is a differentiable formulation of the preference elicitation problem. Instead of searching through a discrete list of items, the authors treat items as continuous vectors in an embedding space (e.g., $\mathbb{R}^d$).
- Differentiable Network: The EVOI objective is formulated as a differentiable network, allowing the use of standard optimization tools like TensorFlow or PyTorch to "nudge" a hypothetical query toward the most informative point using gradient ascent.
- Projection (Deep Retrieval): Once the optimizer identifies the "perfect" hypothetical items, the system projects these back to the closest real items in the dataset.
- Partial Comparison Queries: The framework extends to "partial" queries, where the system optimizes a query specifying only a few key attributes (e.g., "Do you prefer a high-MPG sedan or a high-towing-capacity truck?"), reducing the cognitive load on the user.
Experimental Evaluation
The researchers evaluated their approach using synthetic data, MovieLens-100k, and the large-scale Goodreads dataset ($2 \times 10^5$ items).
Key Results
- Scalability and Speed: On a dataset of 1 million items, the proposed ContFree method generated queries in approximately 1 second, significantly outperforming the standard Greedy baseline, which took over 17 seconds.
- Efficiency: In MovieLens experiments, continuous methods reached target "regret" (the distance between the recommendation and the user's true preference) in just 5-6 queries, matching or exceeding state-of-the-art discrete heuristics.
- Partial Queries: The ContPartial algorithm successfully identified small subsets of attributes that provided high EVOI, proving that simplified questions can be nearly as informative as full-item comparisons.
Discussion and Insights
- The "Hypothetical" Advantage: Allowing the optimizer to "dream up" non-existent items enables it to find the steepest gradient toward information gain faster than checking every real item pair.
- Hardware Acceleration: By relying on matrix operations and gradients, the method can be offloaded to GPUs, enabling real-time performance on production-scale datasets.
- Myopia vs. Long-term Gain: Interestingly, exhaustive myopic search (finding the absolute best single next question) sometimes performs worse over a long trajectory than gradient-based approximations, which appear to find more robust queries.
Conclusion and Future Work
While the EVOI objective is non-convex, the authors mitigate local optima through multiple restarts and smart initialization. Current limitations include the assumption of linear user utility, which may not capture complex attribute interactions. Future research will explore non-linear utility models and real-world user testing to assess how humans interact with "partial" queries and whether projected items feel naturally relevant.
Summary updated