Regret-Based Utility Elicitation in Constraint-Based Decision Problems
- Craig Boutilier, Department of Computer Science, University of Toronto
- Relu Patrascu, Department of Computer Science, University of Toronto
- Pascal Poupart, University of Waterloo
- Dale Schuurmans, AICML
We propose new methods of preference elicitation for constraintbased optimization problems based on the use of minimax regret. Specifically, we assume a constraint based optimization problem (e.g., product configuration) in which the objective function (e.g., consumer prefer ences) are unknown or imprecisely specified. Assum ing a graphical utility model, we describe several elicita tion strategies that require the user to answer only binary (bound) queries on the utility model parameters. While a theoretically motivated algorithm can provably reduce re gret quickly (in terms of number of queries), we demon strate that, in practice, heuristic strategies perform much better, and are able to find optimal (or nearoptimal) con figurations with far fewer queries.
Citation
C. Boutilier, R. Patrascu, P. Poupart, D. Schuurmans. "Regret-Based Utility Elicitation in Constraint-Based Decision Problems". International Joint Conference on Artificial Intelligence (IJCAI), Edinburgh, Scotland, August 2005.| Keywords: | elicitation, constraint-based, machine learning |
| Category: | In Conference |
BibTeX
@incollection{Boutilier+al:IJCAI05,
author = {Craig Boutilier and Relu Patrascu and Pascal Poupart and Dale
Schuurmans},
title = {Regret-Based Utility Elicitation in Constraint-Based Decision
Problems},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2005,
}Last Updated: June 01, 2007Submitted by Staurt H. Johnson
