acceptodds
Under review as a conference paper at ICLR 2027

Sampling for Informative Query Selection in Constructive Preference Elicitation

Abstract

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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Multi-objective combinatorial optimization, constructive preference elicitation, active learning, sampling, uncertainty models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_DgbVOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents an extension of a recent work for eliciting the trade-off weights of a constrained optimization problem. They introduce a sampling technique to select pair of candidates to present to the user that maximize disagreement between the current population of candidate weights (that is iteratively refined based on feedback).

Critical strengths

The proposed approach is simple and sensible, disagreement reranking is a sensible measure of uncertainty, albeit its relationship with standard measures of information like EVOI should be better investigated.

The experimental evaluation is extensive and carefully designed and covers different domains.

Critical weaknesses

The authors present in the motivation combinatorial settings as settings where assumptions of active learning (candidate alternatives available beforehand) do not hold, but then introduce a method that relies on a pool of candidate alternatives available beforehand. This sounds confusing, I believe the setting where the technique is expected to operate and its assumptions should be clarified.

Results do not indicate clear advantages over BALD and EVOI, which are principled preference learning alternatives. The authors do recognize the lack of significant advantages in the section devoted to the comparison, but the abstract states "showcase that it reduces both end-regret and the number of queries compared to the state-of-the-art.". I imagine this refers to the comparison with Defresne et al, the algorithm on top of which the approach is developed, but this should be made clearer to avoid overclaiming. In any case, BALD and EVOI and natural competitors and a lack of advantage wrt them substantially weakens the contribution.

There is a problem with the formatting of references, many of them only report authors, title and year. Not critical, but should be addressed.

Questions for authors

Aren't candidate alternatives assumed not to be available in combinatorial settings? can you clarify the setting where the approach operates?

Can you clarify the reasons why the proposed approach should be preferred wrt techniques like EVOI maximization?

2 comments

We thank the reviewer for pointing out the framing issues.

To address question 1, we develop our analysis in the setting where a solution pool of either pareto/feasible/relaxed can be pre-computed. We rely on solution enumeration, where DRES essentially replaces solver calls with an argmax. The final proposed solution is constructed using a solver call. In settings where precomputation is impossible, Dragone et al. (2018) is preferred.

For question 2, our methodological contribution is a query selection strategy that makes it possible to compare classes of uncertainty models, probabilistic or not. It does not aim to replace BALD or EVOI, which cannot be computed exactly for the non-Bayesian models central to our study; instead, it enables comparisons over a broader class of uncertainty models. The comparisons to BALD and EVOI are therefore not part of our primary contribution, which we will clarify in the revised manuscript.

I would like to thank the authors for the clarifications. However, my concerns are mostly unaffected.

The introduction, that hasn't been changed despite the possibility to upload a revised version, still mentions the motivation of combinatorial settings where assumptions of active learning (candidate alternatives available beforehand) do not hold. This is misleading.

The argument that BALD and EVOI cannot be computed for non-Bayesian models, while DRES can, is not entirely convincing, as the experimental evaluation applies all of these methods to the same ensemble particles, and none of them is exact for non-Bayesian ensembles.

Reviewer_hKU2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes DRES, a method for reducing the number of queries in constructive preference elicitation (CPE) for multi-objective combinatorial optimization. It generates candidate pairs by sampling user preference parameters and selects queries based on prediction disagreement between models. It also compares multiple uncertainty models and analyzes the relationship between model expressiveness and recommendation performance. Simulation experiments on three types of combinatorial optimization problems demonstrate improvements in regret and the number of queries compared to existing methods.

Critical strengths

The simplicity of the proposed query selection method is a strength. Since sampling alone does not guarantee informative queries, the method introduces reranking based on disagreement. While this is a combination of existing techniques, it is relatively easy to implement and offers practical value.

The comparative experiments are another strength. The paper compares existing methods, simple Ensemble Sampling, and the proposed DRES, isolating the effects of each component to some extent. In particular, for the TSP problems, clear improvements are observed in both regret and the number of queries. Additionally, comparing different uncertainty models provides useful insights.

Critical weaknesses

The novelty of the methodology is limited. Both sampling and reranking based on disagreement are well-known techniques in preference learning and active learning; the primary novelty lies in their combination and application to CPE. The contribution beyond a simple combination of existing techniques is not sufficiently clear.

There are concerns regarding the reliance on a linear utility model. Since the proposed method generates candidate comparisons based on a linear weighted sum of objective functions, unsupported Pareto-optimal solutions are not selected through standard candidate generation, and nonlinear preferences cannot be adequately represented. Furthermore, simulated Decision Makers in the experiments are also assumed to have linear utility functions, leaving the effectiveness for more general preferences or actual users unclear.

The improvements are not consistent across problems. While there is clear improvement in the TSP problems, the improvement in the number of queries is small for the PC problem, and no improvement in regret is observed for DRES with a fixed ensemble size in the Land problem. Additionally, since performance varies significantly depending on the ensemble size, further analysis is required regarding the effectiveness of the proposed query selection method itself.

Questions for authors

Q1. How does the method perform if disagreement-based reranking is applied to randomly generated candidate pairs rather than pairs generated by Ensemble Sampling? This comparison would help isolate the contribution of Ensemble Sampling.

Q2. In candidate generation based on a linear utility model, unsupported Pareto-optimal solutions are typically not selected. How does this constraint affect the applicability of the proposed method? Furthermore, how does the method perform for Decision Makers with nonlinear preferences?

Q3. Why is there no improvement in regret for the Land problem, and why is the improvement in the number of queries limited for the PC problem? In what types of problem settings is selection based on disagreement expected to be effective?

1 comment

We thank the reviewer for their constructive questions.

Regarding Question 1, we implemented uniform sampling of the solution pool and compared it against ES. On TSP20, ES significantly outperforms single-pair uniform sampling (K=1) in both end-regret and number of queries; on TSP10, ES requires x2.4 fewer queries; and on PC and LAND they perform similarly. We will add this to Table 3 and Figure 1.

Regarding Question 2, modeling preferences through linear scalarization and evaluating them using a noisy Bradley-Terry user simulation follows established CPE evaluation practices, as in Dragone et al. (2018), Defresne et al. (2025), and Foschini et al. (2026). Moreover, psychological research and empirical studies suggest that linear models can effectively approximate nonlinear human decision-making (Dawes, 2008; Foschini et al., 2026). From a computational perspective, nonlinear objectives are not supported by all solvers and can substantially increase computational time, potentially limiting the applicability and scalability of the approach. Extending CPE to nonlinear preferences would therefore require non-trivial, objective-specific adaptations, which is outside the scope of this paper..

Regarding Question 3, on Land Conservation and The PC configuration task, there is little to elicit. Each instance has a few distinct optima, making it relatively easy for the methods to identify a solution over which the DM is indifferent. DRES does find those distinct optima significantly faster: Table 4 shows DRES (N-tuned) requires 2.8 queries on LAND, significantly outperforming CLUSTER, ES and DRES, and 73 queries on PC, outperforming CLUSTER and ES. We will adjust Table 4 and update our explanation in the Results section. A fixed budget analysis shows that DRES's PC advantage, which is only insignificant after Holm correction, appears only near the end of the budget, which we now state in a fixed-query-budget table for the appendix.

Across the different problem settings, each with a different combinatorial solution space, our methodology is generally among the most effective approaches for query selection. More generally, disagreement-based selection helps most when the members’ argmax solutions differ.

Reviewer_3N5kOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies informative query selection for constructive preference elicitation in multi-objective combinatorial optimization. It proposes Disagreement Reranked Ensemble Sampling (DRES), which generates candidate comparisons from solutions preferred by sampled utility-weight particles and selects the pair with the greatest disagreement across their predicted preference probabilities. The paper also compares several uncertainty models and investigates the relationship between posterior representation, ensemble size, and elicitation performance. Results claims to show that a simple ensemble combined with informative query selection can be effective, although the improvements are less consistent on land conservation.

Critical strengths
  1. DRES combines plausible candidate solutions with disagreement-based selection in a computationally inexpensive procedure. Its compatibility with different particle representations makes the approach easy to incorporate into existing preference-elicitation systems.

  2. DRES improves final regret on the traveling-salesman and computer-configuration tasks and substantially reduces queries on the traveling-salesman tasks. Separate tuning and evaluation users, repeated runs, paired comparisons, and multiple-testing correction strengthen these results.

Critical weaknesses
  1. The experiments do not isolate the benefit of the proposed candidate-generation mechanism against the most direct alternative. Sampling candidate pairs and selecting those with high ensemble disagreement already appears in the cited work of Christiano et al. (2017) and Lee et al. (2021). DRES's main distinction is generating candidates from particle-preferred solutions. However, Table 3 compares DRES with single-pair ensemble sampling and the cluster-based baseline, without evaluating uniformly sampled pairs followed by the same disagreement reranking. Table 2 changes the reranking criterion while retaining the proposed candidate-generation mechanism.

    The existing results demonstrate that reranking improves over using one sampled pair, but do not establish whether the proposed sampling distribution improves over an established disagreement-based approach.

  2. The uncertainty-model study does not cleanly measure posterior fidelity or representational capacity. The NUTS reference in Eq. (13) uses a Dirichlet prior on simplex weights, whereas Appendices A.1–A.2 specify Gaussian priors in additive log-ratio coordinates for the approximate Bayesian methods. These induce different priors, and therefore different target posteriors. Distance to the reference can consequently reflect prior mismatch even with accurate inference. This weakens the interpretation of the posterior-fidelity comparisons.

    Weight-scale calibration also requires clarification. The simulated weights for the traveling-salesman and land tasks are scaled by 100100, while ALR weights lie on the unit simplex. Positive rescaling preserves the preferred solution, but changes the BT probabilities σ(λw⊤Δϕ)\sigma(\lambda w^\top\Delta\phi) unless the inverse temperature is adjusted.

    The ordering of ensemble, Laplace, sampling, and flow methods by representational capacity is asserted without a common quantitative definition or a demonstrated nesting of model classes.

Questions for authors
  1. See weaknesses.

  2. How does DRES compare with uniformly sampling KK candidate pairs from the same solution pool and applying the identical disagreement reranker, with matched ensemble size, update rule, and tuning budget?

  3. Do the NUTS reference and approximate Bayesian methods use the same prior and likelihood? How should the Dirichlet prior in Eq. (13) be reconciled with the Gaussian ALR priors in the appendix?

  4. How are indifferent responses incorporated into model updates, and do they count toward the interaction budget? Since stopping uses the true regret threshold, do the main advantages also hold when comparing methods at common fixed query budgets?

1 comment

We thank the reviewer for the careful reading; especially the comments on the fidelity study allowed for a cleaner analysis.

To better isolate the benefit of ensemble sampling, we implemented uniform sampling by drawing K{1,10,100,1000} solutions from the solution pool, alongside the query selection strategies proposed by Christiano et al. (2017) and Lee et al. (2021, B-Pref), evaluated over the same 40 user seeds, 3 runs per user. Results are listed at the bottom of this comment per problem. Single-pair uniform sampling (K=1) is significantly worse than ES on TSP20, and requires significantly more queries on TSP10, and on par on PC and LAND. On the harder PC configuration task, DRES significantly outperforms the cited works on end-regret and number of queries, and on LAND significantly fewer queries were required to satisfy the DM’s. We will add these comparisons to the appendix section. And add the uniform sampling comparisons to Table 3 and Figure 1.

Regarding Weakness 2 and Question 2, the reviewer is correct that Eq13 and the Appendix sections A1 and A2 describe different priors. We revised the corresponding sections accordingly: the NUTS reference, Laplace, and ALR samplers now share Dir(1) prior. Laplace and ALR samplers were returned under this prior, our conclusion becomes stronger. Excess is problem specific, significantly positive or negative depending on the problem, whereas accuracy is always significant for positive ρ\rho. The Flow model becomes indistinguishable from exact sampling with the same number of particles, yet its regret is worse than the Gaussian prior on all problems. We will adjust the appendix sections A1 and A2.

We agree that scaling the weightings will adjust the corresponding BT probabilities, and requires some more attention. To verify that scaling does not meaningfully impact the DM’s preference labels, we measured the effect of scaling the weights. We use DRES on exact NUTS draws with tempered posterior values \tau \in {0.25, 0.5, 1, 2, 4}. End regret and number of queries does not change significantly. The flow posterior, fitting the BT posterior almost perfectly, needs the same number of queries after scaling, so the slower elicitation does not come from approximation error, but the likelihood temperature λ, which was tuned accordingly. Likewise, the ensemble+DRES results are unaffected.

We agree that the ordering was asserted rather than properly motivated/measured; we removed it. After applying the dirichlet prior, our excess and accuracy measures improved due to a lower approximation error. The Dirichlet-prior Flow posterior now fits the BT posterior exactly at worse regret than the approximations. Our conclusion, based on empirical evaluation, that the decision quality increases with the accuracy of the posterior mean, remains.

Regarding Question 4, indifferent responses are counted in the interaction budget, but the current method does not use them to update the model. We leave the incorporation of indifferent preference labels for future work. To further investigate performance under fixed interaction budgets, we evaluate (q∈{10,25,50,100}q \in \{10, 25, 50, 100\}). DRES consistently outperforms ES on TSP-10 and TSP-20 across all budgets. On PC, however, the advantage of DRES emerges only at larger budgets: ES performs better at (q=10q=10), both methods achieve comparable performance at (q=25q=25) and (q=50q=50), and DRES outperforms ES at (q=100q=100). We will include these additional results in the revised manuscript.

TSP10

MethodEnd regretQueries% sat
Uniform K=10.114 (p=1)33.4 (p < 0.001)92% (p=0.15)
ES0.094 (p =1)17.7 (p=0.084)99% (p=0.95)
Christiano0.067 (p=1)12.7 (p=0.45)100% (p=1)
Lee0.085 (p=1)14.2 (p=0.14)100% (p=1)
DRES0.11011.2100%
TSP20
MethodEnd regretQueries% sat
------------
Uniform K=10.263 (p<0.001)65.5 (p<0.001)57% (p=0.005)
ES0.147 (p = 0.20)43.8 (p=0.007)78% (p=0.16)
Christiano0.063 (p = 0.008)†29.3 (p = 0.93)100% (p = 0.029)†
Lee0.078 (p = 0.038)†31.7 (p = 0.93)98% (p = 0.16)
DRES0.13330.489%

PC

MethodEnd regretQueries% sat
Uniform K=10.125 (p < 0.001)93.9 (p < 0.001)16% (p < 0.001)
ES0.090 (p = 0.001)95.8 (p < 0.001)14% (p < 0.001)
Christiano0.252 (p < 0.001)95.3 (p = 0.011)15% (p = 0.005)
Lee0.152 (p=0.003)96.8 (p=0.004)10% (p=0.002)
DRES0.02673.055%

LAND

MethodEnd regretQueries% sat
Uniform K=10.224 (p=0.40)16.1 (p=0.004)90% (p=0.63)
ES0.158 (p=0.40)12.4 (p=0.008)100% (p=1)
Christiano0.230 (p=0.37)10.8 (p=0.004)95% (p=0.95)
Lee0.249 (p=0.37)11.3 (3.5) (p=0.004)95% (p=0.95)
DRES0.1152.8100%

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.