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?").
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.
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