A POMDP Formulation of Preference Elicitation Problems

Craig BoutilierAAAI 2002 · OpenReview

Abstract

Preference elicitation is a critical challenge for intelligent systems that must make decisions on behalf of users with unknown priorities. Because elicitation effort is costly, determining which questions to ask is a sequential decision problem that balances information gain against user burden. We formulate preference elicitation as a partially-observable Markov decision process (POMDP) over a continuous state space of utility functions. By exploiting the linear structure of expected utility, we develop methods for managing parameterized belief states and optimizing continuous query actions via gradient techniques. Our approach overcomes the limitations of myopic (greedy) elicitation strategies, enabling systems to recognize the long-term value of sequences of queries.

Introduction: The Challenge of Myopia

In many AI applications, such as personalized travel planning or automated bidding, the system must act according to a user's utility function. However, this function is typically unknown and must be elicited through queries. Each query imposes a cost—time, mental effort, or annoyance—on the user.

Traditional elicitation systems often employ "myopic" strategies, selecting the single next question that maximizes the immediate expected value of information. A significant drawback of this approach is its inability to look ahead. If no single question can change the current optimal decision, a myopic agent will stop asking questions prematurely, even if a sequence of questions would have revealed a significantly better outcome. This paper addresses this "myopia trap" by framing elicitation as a long-term optimization problem using a POMDP.

Methodology: Continuous POMDPs and Gradient Optimization

The core of the proposed framework is a POMDP where the hidden state is the user's utility vector. Unlike standard discrete POMDPs, both the state space (utilities) and action space (queries) are continuous.

To handle the continuous state space, the authors represent uncertainty using mixture models (e.g., mixtures of Gaussians). They employ asynchronous value iteration with function approximation to solve the Bellman equations. A key insight is that because expected utility is linear in the utility values, the value of a mixture belief state can be computed as a weighted sum of the values of its individual components.

For the continuous action space, the system must optimize the parameters of a query, such as the probability $l$ in a standard lottery query ("Would you prefer outcome A or a gamble with probability $l$ for outcome B?").

The value of a query as a function of the lottery probability $l$. The non-linear relationship necessitates gradient-based optimization to find the optimal query parameter.

As shown in Figure 5, the value of a query varies non-linearly with its parameters. The authors use gradient ascent to efficiently find the optimal query parameters, allowing the system to tailor questions precisely to the current belief state rather than choosing from a predefined set.

Key Results and Convergence

The framework was evaluated on several scenarios, ranging from small decision problems to complex combinatorial bidding tasks. A primary metric of success was the convergence of the value function approximation.

Convergence of the Bellman error over thousands of backups. The error stabilizes at approximately 2.5%, indicating a high-quality approximation of the value function.

In a 4-outcome scenario, the Bellman error—a measure of the consistency of the value function approximation—dropped significantly and stabilized at around 2.5% (Figure 6). This demonstrates that the function approximation techniques effectively capture the underlying value structure of the elicitation problem.

Furthermore, the POMDP approach successfully navigated "myopic traps." In scenarios specifically designed to stall greedy agents, the POMDP formulation correctly identified sequences of queries that, while individually "useless" to a myopic viewer, collectively led to the discovery of optimal decisions.

Discussion and Future Work

By moving the heavy computation of the value function offline, the POMDP approach enables real-time, high-quality elicitation during user interaction. However, challenges remain regarding scalability. As the number of outcomes increases, the complexity of the utility representation grows quadratically. Future research will explore more compact representations, such as additive utility models, and more sophisticated function approximators to handle higher-dimensional spaces. Additionally, incorporating more complex user response models that account for learning or fatigue could further enhance the system's practical utility.

Summary updated

Abstract

Preference elicitation is a key problem facing the deployment of intelligent systems that make or recommend decisions on the behalf of users. Since not all aspects of a utility function have the same impact on object-level decision quality, determining which information to extract from a user is itself a sequential decision problem, balancing the amount of elicitation effort and time with decision quality. We formulate this problem as a partially-observable Markov decision process (POMDP). Because of the continuous nature of the state and action spaces of this POMDP, standard techniques cannot be used to solve it. We describe methods that exploit the special structure of preference elicitation to deal with parameterized belief states over the continuous state space, and gradient techniques for optimizing parameterized actions. These methods can be used with a number of different belief state representations, including mixture models.
BibTeX
@inproceedings{boutilier2002pomdp,
  author = {Craig Boutilier},
  title = {{A POMDP Formulation of Preference Elicitation Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2002},
  url = {https://openreview.net/forum?id=ByETh6xOWH},
}
Figure