acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Pairwise-Feedback Sampling for Multi-Prompt KL-Regularized Policies

Abstract

Pairwise comparisons can be easier to obtain than calibrated rewards, yet using them to construct response policies usually involves fitting a reward model or a parameterized policy. We study a complementary setting: each prompt has a fixed finite set of candidate responses, and a limited feedback budget must be distributed across prompts with different deployment importance and sampling difficulty. We introduce a direct sampling procedure that constructs KL-regularized response policies from fresh comparisons. Under the Bradley–Terry model, accepting a proposed response after repeated comparison wins yields a Markov chain with the desired stationary policy at an implementable temperature. We analyze the empirical occupation policy actually returned by the sampler, establishing a finite-sample objective-gap bound and an exact asymptotic leading term. This characterization reveals a square-root allocation rule balancing deployment weights and local sampling difficulties. An adaptive scheduler estimates these difficulties online and converges to the oracle allocation. At deterministic horizons of global update rounds, the adaptive procedure achieves an expected aggregate objective gap of and an rate matching the oracle's order. Synthetic experiments show objective gaps comparable to the known-difficulty oracle and smaller than round-robin allocation, supporting the practical value of the allocation rule. Experiments on SQLite questions further illustrate improved pairwise preference performance over round-robin under LLM evaluation. Together, these results connect direct comparison-based sampling, policy-quality guarantees, and adaptive feedback allocation.

Primary area:
reinforcement learning
Keywords:
Markov chain, pairwise feedback, online adaptive allocation

Reviews

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

This paper studies the problem of constructing KL-regularized response policies directly from pairwise comparisons, assuming a fixed finite set of candidate responses for each prompt. The authors propose an MCMC-based sampling method that constructs a Markov chain whose stationary distribution corresponds to the desired KL-regularized policy under the Bradley–Terry preference model. The paper further analyzes the finite-sample error of the proposed sampling procedure and develops an adaptive feedback allocation strategy across multiple prompts based on their sampling difficulties. The authors provide theoretical guarantees for the proposed approach and evaluate its effectiveness through synthetic experiments and an LLM-based question-answering task.

Critical strengths
  1. The paper presents an elegant approach to constructing KL-regularized policies through MCMC sampling. The idea of designing a Markov chain that converges to the desired policy distribution using only pairwise comparisons is clever and technically interesting. This provides an alternative to explicitly learning reward models or parameterized policies.

  2. The proposed approach is supported by a relatively comprehensive theoretical analysis. Beyond designing the MCMC sampling procedure, the authors characterize its finite-sample approximation error and derive a principled feedback allocation strategy across multiple prompts. These results provide theoretical support for the proposed method and offer insights into its sampling efficiency.

  3. The experimental results on synthetic datasets are promising. The proposed adaptive sampling strategy achieves performance close to the oracle allocation with known sampling difficulties and consistently outperforms simpler allocation baselines. These results provide empirical support for the effectiveness of the proposed approach.

Critical weaknesses
  1. The proposed method is restricted to a fixed finite set of candidate responses, which limits its applicability to modern LLM generation scenarios. In practice, LLMs typically generate responses autoregressively over an extremely large output space, rather than selecting from a predefined discrete candidate set. This creates a considerable gap between the proposed formulation and the predominant generation paradigm, raising concerns about the broader applicability of the method.

  2. The practical motivation for the specific problem setting is not sufficiently justified. In realistic applications, it is unclear how frequently one would encounter a scenario where a fixed finite set of candidate responses is available and the objective is specifically to sample from a KL-regularized policy over these candidates. Even when such a candidate set exists, directly selecting or ranking high-quality responses may be more natural than sampling from a prescribed distribution. The authors should provide stronger justification for the necessity and practical relevance of this problem formulation.

Questions for authors

Please see the weaknesses.

1 comment

Thanks for the rebuttal, which has addressed my concerns. I am happy to maintain the positive score

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

This paper studies how to construct KL-regularized response distributions over fixed candidate sets using pairwise feedback and how to allocate updates across prompts. A repeated-win Markov sampler targets the desired distribution at reciprocal-integer temperatures. An analysis of its empirical occupation policy motivates a square-root allocation rule, which an adaptive scheduler learns online. The paper is well written, and the proofs appear technically sound under the stated assumptions (though I didn't verify the correctness of all equations). Relative to earlier comparison-based MCMC, I view the occupation-policy analysis and its connection to allocation as the main original contribution. Overall, I think the theoretical contribution is useful but focused, while the evaluation and motivation of the method remains insufficiently established.

Critical strengths
  1. The repeated-win rule uses binary comparisons to obtain a stationary distribution, without estimating utilities for the local sampler. Connecting this distribution to the KL-regularized objective gives the procedure a precise interpretation and makes it a useful alternative for fixed candidate pools.

  2. Theorems 3.2–3.3 bound the occupation policy's expected objective gap from arbitrary initialization and identify its exact leading coefficient. It connects sampling dependence directly to policy quality and supplies a principled allocation criterion.

  3. The scheduler consistently estimates the difficulties and converges to the oracle proportions. The uniform occupation addresses the dependence between allocation decisions and observed trajectories. This makes the adaptive guarantees credible.

Critical weaknesses
  1. The empirical evidence is narrow. Evaluation uses one synthetic instance and 30 constructed SQLite questions, with three replications and only m=2. In SQLite, strong answers deliberately receive little proposal mass, and the same model supplies sampling judgments and evaluation. Fresh, counterbalanced judgments are useful, but they do not verify the Bradley–Terry or independent-repeat assumptions, and the win ratio does not measure the KL-regularized objective. The reported win ratio is encouraging but insufficient to establish broader utility. Maybe consider to add a more realistic evaluation.

  2. The practical motivation in the LLM setting is a bit unclear. The method constructs a distribution over existing answers for each fixed prompt, without improving the language model or generalizing to new prompts. It appears useful when the same questions recur and the application benefits from randomly selecting among existing answers. However, the SQLite experiment does not establish why learning an entire answer distribution is preferable to selecting the most reliable answer. Fitting a preference-scoring model over these small candidate sets may already be inexpensive, so avoiding reward-model fitting alone does not demonstrate a practical advantage. A realistic repeated-use application and comparisons with lightweight preference-learning methods under the same feedback budget would strengthen the paper’s significance.

  3. All methods receive the same number of update rounds, but an update does not always require feedback. For example, when the sampler proposes its current answer, no comparison is needed. Consequently, different methods can use different numbers of actual judgments. The experiments therefore show performance under a common maximum budget, but do not clearly establish which method achieves the best quality for the same actual feedback cost.

Questions for authors

Can you identify a concrete application where retaining a distribution over answers to fixed prompts provides a measurable benefit over selecting one reliable answer? In that setting, how does your method compare with fitting a lightweight preference-scoring model?

Reviewer_A8JBOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors consider constructing KL-regularized response policies over fixed candidate sets using limited pairwise feedback across multiple prompts. They propose a Markov chain sampler based on repeated comparison wins and an adaptive scheduler that allocates feedback according to estimated sampling difficulties. They establish finite-sample and asymptotically sharp objective-gap bounds for the sampler, together with allocation consistency and objective-gap guarantees for the adaptive procedure. Experiments support the proposed method's effectiveness.

Critical strengths

The theoretical analysis is solid, especially the finite-sample and asymptotically sharp guarantees in Theorems 3.2 and 3.3.

Critical weaknesses
  • The practical motivation for the setting is unclear. Although the paper presents it as complementary to RLHF, it does not sufficiently explain which applications require learning and maintaining a distribution over fixed candidate responses rather than selecting the best response, or why online feedback collection is needed in these applications.
  • The experiments are limited to one synthetic instance and 30 constructed SQLite questions. The SQLite experiment also uses the same model for sampling judgments and final evaluation, leaving the robustness across tasks, judges, and deployment settings unclear.
  • The baseline comparison does not sufficiently establish the advantage of RWPS itself. Most baselines retain the proposed sampler and mainly differ in the allocation rule. Although the authors include the UNIFORM+ROUND-ROBIN, this is not sufficient to show the advantage of RWPS.
Questions for authors
  • Could the authors describe a concrete application with fixed candidate responses and explain how the deployment weights fxf_x would be determined? Why would online feedback collection be needed in that application?
  • Why does RWPS+ORACLE-CTM have a larger mean objective gap than RWPS+CTM in Table 2? Could the authors explain whether this reflects finite-budget effects or random variation?
  • The experiments only consider m=2m=2. How would larger values of mm affect the theoretical bounds and comparison efficiency? Could the authors provide a sensitivity analysis covering different values of mm?
  • Could the authors provide theoretical justification and/or empirical evidence to support the advantages of the RWPS estimator?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.