Technical Summary: QUIVER – Cost-Aware Adaptive Preference Querying

1. Problem Statement

Interactive Multi-Objective Optimization (MOO) systems face a fundamental resource allocation dilemma. Given a fixed budget, an optimizer must decide how to distribute resources between objective evaluations (expensive, e.g., physical simulations) and preference elicitation (identifying the decision-maker's (DM) preferred region of the Pareto set).

This problem is compounded by the heterogeneity of preference query modalities:

• Pairwise Preferences (PS): "Do you prefer A or B?" These are cognitively cheap but provide only ordinal (1-bit) information.
• Indifference Adjustments (IA): "How much must you adjust objective $k$ to make A and B equally preferred?" These are cognitively more demanding but reveal cardinal trade-off information (marginal rates of substitution).

Existing methods typically fix the query protocol (e.g., periodic pairwise comparisons) or treat the DM as a post-hoc selector. There is a lack of frameworks that adaptively allocate a unified budget across objective evaluations and heterogeneous preference queries based on their relative Value of Information (VOI) per unit cost.

2. Methodology: The QUIVER Framework

The authors propose QUIVER (Query-Informed Value Estimation for Regret), a surrogate-assisted evolutionary multi-objective optimizer. The system couples an NSGA-II search layer with a cost-aware controller that dynamically selects actions from a unified space: $\{ \text{Eval}, \text{PS}, \text{IA} \}$.

2.1 Core Components

• Search Layer: Uses NSGA-II to maintain a population of candidate solutions and an archive of evaluated points. It employs a particle-filter posterior to represent the distribution of latent preference weights $w$.
• Preference Modeling:
  • Assumes a linear scalarization utility $u(f; w) = w^\top f$.
  • PS Likelihood: Modeled via a logistic function (Bradley-Terry style) with noise.
  • IA Likelihood: Modeled as a Gaussian distribution where the DM reports an adjustment $\tilde{\delta}$ to equalize utility. This provides cardinal information about the weight vector.
  • Inference: Uses Sequential Monte Carlo (SMC) with a particle filter to update the posterior $p(w | \mathcal{D}_{pref})$ based on observations.
• Cost-Aware Action Selection:
  At each step, the controller selects the action $a$ that maximizes the expected decision-quality improvement per unit cost:
  $$a^* = \arg \max_{a} \frac{\mathbb{E}[\Delta Q \mid a, \mathcal{H}_t]}{c(a)}$$
  Where:
  • $c(a)$ is the cost of the action ($c_{eval} \gg c_{IA} > c_{PS}$).
  • $\Delta Q$ is the expected improvement in decision quality.
    • For Preference Queries (PS/IA): $\Delta Q$ is the expected entropy reduction (Information Gain) in the preference posterior.
    • For Evaluations: $\Delta Q$ is the Value of Clairvoyance (VOC), representing the expected improvement in the posterior expected utility of the best candidate.
  • Estimation: Expected Information Gain (EIG) is estimated via Monte Carlo simulation. To ensure fair comparison between continuous IA responses and binary PS responses, IA outcomes are discretized into bins before calculating mutual information.

2.2 Query Selection Strategy

• Pair Selection: For preference queries, pairs are selected based on posterior disagreement (maximizing the probability that the DM is indifferent, i.e., $p \approx 0.5$).
• Dimension Selection (for IA): The objective dimension $k$ is selected to maximize the posterior variance of the corresponding weight $w_k$.

3. Key Contributions

1. Formalization: Defined cost-aware interactive MOO under an unknown linear scalarization, treating objective evaluations and heterogeneous preference queries (PS and IA) as a unified budgeted action space.
2. VOI-Based Selection Rule: Derived a practical action selection rule using Monte Carlo estimation of expected entropy reduction, unifying objective exploration and preference learning under a single criterion.
3. Algorithm Implementation: Proposed QUIVER, an evolutionary algorithm with an NSGA-II backbone that implements this adaptive policy via a particle-filter preference posterior.
4. Empirical Validation: Demonstrated that adaptive modality selection yields lower utility regret per unit cost compared to fixed-schedule and single-modality baselines.

4. Experimental Results

The framework was evaluated on DTLZ and WFG benchmarks with synthetic decision-makers.

• Performance on Easy Problems (DTLZ2): All methods, including "Eval-only" and "PS-only," achieved near-zero regret. QUIVER predominantly selected cheap PS queries (approx. 80–87% of preference queries), as the problem was solvable with less information.
• Performance on Hard Problems (WFG4, WFG9):
  • QUIVER achieved the lowest utility regret, outperforming all baselines.
  • On WFG9 (the most challenging), QUIVER achieved a regret of 2.82, a 25% improvement over the best baseline (3.77–3.90).
  • Adaptive Shift: On hard problems, QUIVER shifted its strategy, increasing the fraction of IA queries to 35% (compared to 20% on easy problems). This demonstrates the system's ability to recognize when the higher information content of IA justifies its extra cost.
• Cost Sensitivity: When the relative cost of IA ($c_{IA}/c_{PS}$) was increased, the system automatically reduced IA usage, confirming the cost-aware nature of the controller.
• Fatigue Regime: In a dynamic cost scenario where IA costs increased with usage (simulating cognitive fatigue), QUIVER adaptively reduced IA usage and shifted budget toward evaluations, showing graceful degradation in performance rather than catastrophic failure.

5. Significance and Claims

The paper claims that the primary significance of QUIVER lies in its adaptive modality selection. By treating $\{ \text{Eval}, \text{PS}, \text{IA} \}$ as a unified action space, the system can dynamically allocate resources based on problem difficulty and the evolving cost-information trade-off.

• Theoretical Insight: The authors establish a modality switching threshold: IA is selected over PS only when the ratio of their information gains exceeds the ratio of their costs ($IG_{IA}/IG_{PS} > c_{IA}/c_{PS}$).
• Practical Impact: The framework demonstrates that for challenging optimization problems, rigid strategies (fixed schedules or single modalities) are suboptimal. Instead, a cost-normalized VOI approach allows the optimizer to "spend" more on rich, expensive queries only when the uncertainty is high enough to warrant it.
• Generalizability: The controller is optimizer-agnostic. While instantiated with NSGA-II, the VOI-per-cost principle can be applied to other backends (e.g., Bayesian Optimization, Random Search) provided they can generate candidates and maintain a preference posterior.

The authors remain modest regarding limitations, noting that the current framework assumes linear utility (which may struggle with non-convex Pareto fronts) and synthetic DMs. They identify extending to non-linear utility models and validating with real human decision-makers (accounting for complex fatigue and inconsistency patterns) as necessary future work.