Sampling for Informative Query Selection in Constructive Preference Elicitation

In Multi-Objective Combinatorial Optimization, the Constructive Preference Elicitation (CPE) framework has been proposed to learn objective importance from the Decision Maker's perspective through pairwise comparisons between candidate solutions. State-of-the-art methods draw these query pairs from a precomputed solution pool based on an explicit exploration and exploitation tradeoff, which depends on a tuned parameter. In the context of dueling bandits, Thompson-sampling approaches instead balance exploration and exploitation implicitly by sampling from a posterior distribution over the objective weights. We explore this concept in the context of CPE for the first time, with a new query selection criterion that samples objective weights from the current estimated belief to generate pairs of candidates. However, posterior sampling ensures only that each candidate is plausible under the current belief, without guaranteeing that their comparison will provide useful information. We therefore introduce DRES (Disagreement Reranked Ensemble Sampling), which combines this sampling mechanism with disagreement-based reranking, selecting the candidate query pair expected to provide the strongest learning signal. We evaluate DRES across three multi-objective combinatorial domains and showcase that it reduces both end-regret and the number of queries compared to the state-of-the-art.