Checking Only the Decision: Convergence Diagnostics for Regret-Based Preference Queries

A recommender that learns what a user wants by asking comparison questions faces a choice. It can ask about everything it is unsure of, or it can ask only about what could change its recommendation. The regret-based approach does the second. The system recommends the option whose worst-case loss is smallest, finds the rival option that could most embarrass that choice (the "adversarial witness"), and asks the user to compare the two. This works well when users answer consistently. When users answer noisily, as real people do, the hard constraints behind the method contradict each other and the set of plausible utilities becomes empty. The natural repair is to replace that set with a Bayesian posterior, meaning a probability distribution over utility weights given the noisy answers, and to sample from it with Markov chain Monte Carlo (MCMC), a method that draws approximate samples by running a random walk whose long-run distribution is the posterior.

That repair creates a new problem nobody in this literature has addressed. The worst-case regret is computed from the tail of a sampled distribution. Tails are where unfinished MCMC runs are least reliable, and global convergence checks are known to miss exactly this kind of failure. This note proposes a convergence diagnostic aimed at the decision. It does not certify that the whole posterior is well sampled. It checks whether the specific one-dimensional tail quantities that determine the current recommendation and its witness have converged. When that check fails, the system spends more computation instead of spending a human query. The claim is that this avoids asking users about "phantom witnesses," rivals that look threatening only because the sampler has not finished, and that it does so at a fraction of the cost of certifying the full posterior.

Core Claim

Let $w$ be the user's utility weights and $\phi(x)$ the feature vector of option $x$. Under a Bradley-Terry-Luce response model, in which the user prefers the higher-utility option with probability given by a logistic function of the utility gap, the past answers $D$ induce a posterior $p(w \mid D)$. We replace the polytope maximum regret with a quantile version:

$$\mathrm{MR}_\alpha(x) = \max_{x'} \; Q_{\alpha}\big[\, w^\top(\phi(x') - \phi(x)) \,\big],$$

where $Q_\alpha$ is the $\alpha$-quantile under $p(w \mid D)$. The system recommends $x^* = \arg\min_x \mathrm{MR}_\alpha(x)$ and asks the user to compare $x^*$ with the maximizing witness $x'^*$. When responses become noise-free and $\alpha \to 1$, this reduces to classical minimax regret.

The key observation is that the decision depends on the posterior only through a few scalar random variables: the gaps $r_{x,x'}(w) = w^\top(\phi(x')-\phi(x))$ for the recommendation and its top few rivals, evaluated at a single quantile. We therefore propose a decision-local diagnostic. It applies the quantile-specific $\hat{R}(x)$ of On the use of a local $\hat{R}$ to improve MCMC convergence diagnostic to these projected gap variables at level $\alpha$. It pairs this with a Monte Carlo standard error on each quantile and stops sampling only when two conditions hold: the local $\hat{R}$ values are near one, and the margin between $\mathrm{MR}_\alpha(x^*)$ and the next-best recommendation exceeds that error.

The claim has three parts:

  1. The diagnostic is sufficient for what matters, namely the stability of the recommendation and the identity of the queried witness.
  2. Its cost does not grow with the posterior's dimension in the way full-distribution checks do.
  3. It catches failures that global checks miss, specifically the equal-mean, unequal-tail failures. Noisy and contradictory answers produce exactly these, through ridge-shaped or skewed posteriors.

Position Relative to Prior Work

The regret machinery comes from the elicitation literature. Elicitation of Factored Utilities defines the polyhedral knowledge set and the adversarial witness. Regret-based Incremental Partial Revelation Mechanisms and Robust Approximation and Incremental Elicitation in Voting Protocols show that querying the recommendation against its witness shrinks worst-case regret quickly. Optimal Set Recommendations Based on Regret proves that the regret-minimizing slate is a myopically optimal query. All of these assume hard linear constraints, and that assumption is what breaks under noise.

Robustness in the Face of Partial Identifiability in Reward Learning carries minimax regret into reward learning through a Chebyshev-center solution. It also keeps a deterministic feasible set. We supply the noise model these works lack, and with it a sampling problem they never face.

On the Bayesian side, Gaussian Process Preference Elicitation handles noisy answers but uses a Laplace approximation, a Gaussian fitted at the posterior peak. That approximation is cheap but cannot represent skew or multiple peaks. We motivate our choice of MCMC by the cases where that Gaussian misplaces the tail. We also test those cases directly instead of assuming them.

The diagnostic side supplies the method and constrains its design. Measuring Sample Quality with Kernels shows that effective sample size can favor the most biased sampler, and that light-tailed kernel Stein discrepancies have blind spots in dimension three and above. The Minimax Lower Bound of Kernel Stein Discrepancy Estimation shows that the error constant of kernel Stein estimation degrades exponentially with dimension under Gaussian kernels. Together these suggest that certifying a full high-dimensional posterior at every interaction round is both expensive and statistically weak, which motivates projecting onto decision directions. The local $\hat{R}$ paper supplies the quantile-level tool. It also warns that joint multivariate versions are costly, and our design avoids that cost by working only with scalar projections.

What is new is not any single component but the coupling. The witness search selects which scalar quantities the diagnostic must certify. The diagnostic's verdict then decides whether the next unit of effort goes to the human or to the sampler.

Research Program

We will build the loop on a standard gradient-based sampler. The No-U-Turn sampler is appropriate because the logistic posterior has an available gradient, and On the convergence of dynamic implementations of Hamiltonian Monte Carlo and No U-Turn Samplers gives its theoretical footing. The sampler runs with several chains warm-started from the previous round's samples.

Each round proceeds in five steps:

  1. Draw a batch of samples.
  2. Estimate $\mathrm{MR}_\alpha$ for the candidate options, using constraint generation over witnesses as in the setwise-regret work.
  3. Take the top $m$ (recommendation, witness) pairs by estimated regret.
  4. Compute local $\hat{R}$ and quantile standard errors for their gap variables.
  5. If the check fails, sample more. If it passes, issue the query.

We will analyze two properties. The first is when certifying $m$ pairs suffices. A small witness set can miss a rival whose gap is badly estimated precisely because the sampler has not reached its region, so we will measure how often the certified witness changes when sampling continues to a large reference budget. This also lets us study how $m$ trades cost against safety. The second is a simple bound. If every certified quantile is within its error, the regret of the chosen option exceeds the reference-posterior minimax regret by at most the sum of those errors, because $\mathrm{MR}_\alpha$ is a maximum of quantiles and each quantile is perturbed by at most its error.

As an extension, we will replace the linear utility with a small nonlinear one, such as random features over the Sushi item attributes. This is where Laplace approximations should fail most clearly and where linear-only methods like Optimal Design for Human Feedback cannot be applied.

Baselines

The naive reference point is uniformly random comparison queries combined with a posterior-mean recommendation. Every adaptive method must beat it in queries-to-target-regret.

The classical method is setwise maximum regret over the hard polytope, as in Optimal Set Recommendations Based on Regret. We also run a version with slack variables that tolerates contradicted constraints. The paper reports that its method reached within 3% of true maximum utility in 5 to 6 cycles on the apartment data, while critiquing heuristics plateaued at 10 to 18% regret. We will reproduce the noise-free result first. Our method should then match it at zero noise and degrade more gracefully as noise rises. That is the comparison that defines a win on this baseline.

The strongest Bayesian competitor is the same quantile-regret rule computed from a Laplace posterior, in the style of Gaussian Process Preference Elicitation. That paper reports reaching, after 4 to 6 Sushi queries, accuracy other methods needed 10 or more queries to reach. No absolute loss value is reported on Lacuna. This baseline is cheap, so we give it the same wall-clock budget.

The strongest non-adaptive competitor is Dope, from Optimal Design for Human Feedback. It reached the target ranking loss on Nectar in 150 rounds against 500 for the best baseline, a 3.3x gain, and matched uniform sampling's loss on the Anthropic data with nearly 50% fewer samples. We run Dope on the same embeddings and response simulator. Beating it means reaching the same decision regret in fewer queries.

The ablation that isolates our ingredient keeps the same quantile-regret rule and the same total sampler budget, but swaps the decision-local check for one of three alternatives:

  • a fixed sample count;
  • global rank-$\hat{R}$ with an effective sample size threshold;
  • an inverse multiquadric kernel Stein discrepancy over the full posterior.

A win means two things. At matched queries we should see fewer phantom-witness queries, meaning queries whose witness disappears under a long reference run, and equal or lower regret. At matched certified-decision quality we should use fewer gradient evaluations. All methods share the same simulated users, response noise, candidate sets, and hyperparameter search budget.

Why not just…?

Why not just run MCMC for a fixed, generous budget and skip diagnostics? If computation is effectively free, this works, and we will say so. The ablation reports the budget at which fixed sampling matches our certified decisions. The case for our method rests on interactive latency and on posteriors where no fixed budget is safe across rounds. As answers accumulate and contradict each other, the posterior's shape changes, so a budget tuned on early rounds can fail later. The phantom-witness rate as a function of round will show whether this happens in practice.

Why not just use a Laplace approximation? For linear utilities with many answers, the logistic posterior is close to Gaussian, and Laplace may tie with us. That is a real threat. Our expected advantage lies in early rounds, under high noise, and with nonlinear utilities, where skew or multiple peaks move the $\alpha$-quantile. We will report the regret gap separately by round and by utility class. If Laplace ties everywhere, the contribution shrinks to the nonlinear setting.

Why not just add slack variables to the polytope? Slack keeps the knowledge set non-empty. However, it requires choosing a penalty that has no probabilistic meaning, and it treats a single careless answer the same as a systematic preference. The noise sweep compares the two directly. If tuned slack matches us, the result would argue that the Bayesian machinery is unnecessary for linear utilities.

Why not just use global $\hat{R}$ or full kernel Stein discrepancy? Prior work already shows that global $\hat{R}$ misses equal-mean, unequal-variance failures (On the use of a local $\hat{R}$ to improve MCMC convergence diagnostic). It also shows that full kernel Stein estimation has an error constant that grows exponentially with dimension and a cost quadratic in sample size (The Minimax Lower Bound of Kernel Stein Discrepancy Estimation). The ablation measures both effects on real elicitation posteriors rather than assuming them.

Proposed Experiments

We will use four benchmarks:

  1. Apartment rental data, the classical setwise-regret testbed.
  2. Sushi, with 15-dimensional item features, and also with 85-dimensional user features to raise the posterior's dimension.
  3. Nectar and Anthropic preferences, with answers represented by fixed embeddings as in the Dope setup, to test high dimension.
  4. New Yorker caption ranking (yguooo/newyorker_caption_ranking), whose three-level human ratings give a natural noisy-response simulator.

Simulated users follow Bradley-Terry-Luce responses at several noise temperatures, plus a contradiction regime that flips a fixed fraction of answers. Metrics are:

  • true regret of the recommendation versus number of queries;
  • phantom-witness rate;
  • gradient evaluations per certified round;
  • whether the certified recommendation agrees with a long-run reference posterior.

The decisive check is a controlled one. We build posteriors in which one decision-relevant direction has a heavy or bimodal tail while means agree across chains. Global $\hat{R}$ should pass, the decision-local check should fail, and acting on the unconverged samples should produce a measurably wrong query. If our check does not separate these cases, or if it separates them but end-to-end regret is unchanged, the core claim is false.

A second check sweeps the dimension from 15 to 85 to embedding size. It should show that the decision-local check's cost stays roughly flat while full kernel Stein cost rises.