Optimal Bayesian Recommendation Sets and Myopically Optimal Choice Query Sets

Paolo Viappiani, Craig BoutilierNeurIPS 2010 · OpenReview

Introduction

In personalized systems—such as apartment finders, car recommenders, or streaming platforms—the system must quickly learn what a user wants without overwhelming them with questions. The theoretical "gold standard" for selecting these questions is Expected Value of Information (EVOI), which involves picking the query that will most improve the quality of the system's final recommendation.

However, this paper addresses a critical roadblock: calculating the optimal query using EVOI is a computational nightmare. It requires simulating every possible user response, updating the system's beliefs for each, and then finding the best possible recommendation for every resulting scenario. Because of this, real-world applications often abandon EVOI for simple heuristics that lack theoretical guarantees. This paper proves a surprising and computationally useful equivalence that bridges the gap between recommendation and information gathering, enabling near-optimal query selection in a fraction of the time.

The Core Insight: Recommendation Equals Elicitation

The authors focus on choice queries, where a user is shown a "slate" of $k$ items and asked to pick their favorite. They analyze the relationship between two objectives:

  1. Expected Posterior Utility (EPU): The value of a set when used as a query (how much information we learn).
  2. Expected Utility of Selection (EUS): The value of a set when used as a recommendation (how happy the user is with their choice from that set).

The core "aha moment" of the paper is the Equivalence Theorem. The authors prove that under standard noiseless and constant-noise models, the set of items that maximizes EUS is identical to the set that maximizes EPU. Intuitively, a diverse recommendation set that covers different possible user preferences naturally makes for a great query. If you show a user a sports car, a minivan, and a sedan, their choice tells you a lot about their lifestyle (elicitation) while also giving them a good chance of seeing something they like (recommendation).

Algorithmic Advantages

By showing that query optimization reduces to recommendation optimization, the computational complexity is cut by a factor of $n$ (the total number of items). This moves the problem from "impossible for real-time" to "feasible."

Furthermore, the authors demonstrate that EUS is a submodular function. This is a significant property in optimization because it guarantees that a simple greedy algorithm (adding the best item one by one to the slate) will get very close to the absolute best set.

To push performance even further, they introduce Query Iteration (QI), a local search heuristic. QI starts with a random set and repeatedly replaces items with the "optimal" choice based on the current belief state until it converges, proving to be exceptionally fast in practice.

Key Results

The researchers evaluated their algorithms on two datasets: an Apartment Rental Dataset (187 items, 10 attributes) and the Boston Housing Dataset (506 items, 14 attributes).

Rapid Convergence

In simulations, the greedy algorithm optimizing for EUS performed almost as well as the computationally expensive exact EVOI optimization. Starting from a state of total uncertainty, the system was able to identify the user's optimal item rapidly.

Convergence of loss over number of queries

As shown above, the normalized average loss drops dramatically in the first few queries, often converging to near-zero within just 10 to 15 queries.

Computational Efficiency

While greedy algorithms are effective, the Query Iteration (QI) method proved to be significantly faster, making it highly suitable for large-scale systems.

Computation times for different algorithms and dataset sizes

For the larger Boston Housing dataset ($n=506, k=6$), the standard greedy approach took 32.8 seconds. In stark contrast, the QI algorithm with sampling initialization took only 0.09 seconds to generate a query slate, easily meeting the threshold for real-time interactive interfaces.

Limitations and Future Work

While the results are highly promising, the paper notes a few limitations:

  • Myopic Focus: The approach optimizes for "myopic" EVOI (looking only one step ahead). While standard for real-time systems, it does not account for long-term query strategies that might be more efficient over a long sequence of questions.
  • Fixed Slate Size: The size of the query set ($k$) is assumed to be fixed. Future work could explore adaptively changing the number of items shown based on the system's confidence.
  • Large-Scale Configuration: The authors suggest extending this framework to "constructive" spaces (like building a custom PC), where the number of possible configurations is too large to list and must be handled via constraint satisfaction (CSP).

Summary updated

Abstract

Bayesian approaches to utility elicitation typically adopt (myopic) expected value of information (EVOI) as a natural criterion for selecting queries. However, EVOI-optimization is usually computationally prohibitive. In this paper, we examine EVOI optimization using \emph{choice queries}, queries in which a user is ask to select her most preferred product from a set. We show that, under very general assumptions, the optimal choice query w.r.t.\ EVOI coincides with \emph{optimal recommendation set}, that is, a set maximizing expected utility of the user selection. Since recommendation set optimization is a simpler, submodular problem, this can greatly reduce the complexity of both exact and approximate (greedy) computation of optimal choice queries. We also examine the case where user responses to choice queries are error-prone (using both constant and follow mixed multinomial logit noise models) and provide worst-case guarantees. Finally we present a local search technique that works well with large outcome spaces.
BibTeX
@inproceedings{viappiani2010optimal,
  author = {Paolo Viappiani and Craig Boutilier},
  title = {{Optimal Bayesian Recommendation Sets and Myopically Optimal Choice Query Sets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=HyWOEPZuZB},
}
Figure