acceptodds
Desk rejected at ICLR 2027

Preference Learning Beyond Confidence: Efficient Gradient-Based RLHF via Adversarial Preferences

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Recent advances in Large Language Models (LLMs) and robotics have intensified interest in Reinforcement Learning from Human Feedback (RLHF), where reward functions are learned from pairwise human preferences modeled via sigmoid-based utility functions. Despite their widespread adoption, existing RLHF frameworks either lack theoretical guarantees or are computationally intractable — relying on confidence-set-based methods that cannot scale to continuous, high-dimensional decision spaces. We address this gap by developing Mirror-Duel, an efficient gradient descent-based algorithm with provably optimal regret guarantees under adversarially changing preferences, without assuming a fixed stochastic reward model. Formalizing the problem as an adversarial online convex optimization (OCO) problem with only weak pairwise preference feedback, our online mirror descent (OMD) approach achieves an optimal regret bound — matching a lower bound — with only runtime. Beyond pairwise preferences, we extend Mirror-Duel to -batched and top- partial ranking feedback, respectively yielding improved and regret guarantees. We validate our theoretical findings extensively on synthetic adversarial instances as well as real-world RL environments (CartPole-v1, Acrobot-v1), demonstrating that Mirror-Duel consistently outperforms UCB-based baselines, including Online-IPO, APO, and Nash-MD in regret performance. Our work lays a theoretical and algorithmic foundation for scalable, gradient-based reward learning from human preferences, contributing to the broader effort of improving AI alignment with Human Preferences.

Primary area:
learning theory
Keywords:
Reinforcement Learning from Human Feedback, Online Learning, Preference-based Learning, Dueling Bandits, Online Convex Optimization, Mirror Descent Regret Minimization

Reviews

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

The paper addresses the challenge of computationally efficient preference learning under adversarially changing utilities. The authors propose Mirror-Duel, which combines symmetric pairwise comparisons with mirror descent and self-concordant regularization. They extend the method to batched comparisons and partial ranking feedback, and present regret upper and lower bounds to characterize the benefit of additional preference information. The authors also report synthetic experiments and evaluations on CartPole and Acrobot to examine regret performance and compare the proposed method with existing preference-learning approaches.

Critical strengths
  1. The paper studies an important problem: learning efficiently from preference feedback when the underlying utilities change. Developing an approach that avoids maintaining confidence sets is an interesting direction for continuous decision spaces.

  2. The paper considers pairwise, batched, and ranking feedback within a common framework. This provides a useful perspective on how different amounts and forms of preference information may affect learning efficiency.

Critical weaknesses
  1. The main theoretical guarantees are not established by the presented arguments.

    The relationships between preference regret, linear regret, and sample complexity in Remarks 1 and 2 do not hold as stated under adversarially changing utilities. The ranking-feedback reduction also contains unresolved issues concerning the comparison construction and the claimed independence of the extracted comparisons. These problems directly affect the validity of several central results.

    Essential supporting details are also difficult to verify. Section 3 refers to Sections C.1 and C.3 for the pseudocode and regret analysis (lines 285–286), and to Section C for the complete proof of Theorem 1 (line 312). The batched and ranking algorithms similarly refer to Sections D.1 and E.1 for their pseudocode (lines 349 and 417). However, I could not locate these sections in the material available to me. Together with inconsistent notation and insufficient explanation in the main text, this prevents a reliable assessment of the algorithms and their theoretical guarantees.

  2. The computational efficiency and practical advantages are not sufficiently established.

    The paper claims an overall runtime of O(dT)O(dT), but the algorithm requires Hessian eigendecomposition and a regularized optimization step at each round. It remains unclear how these operations are accounted for in the claimed complexity or whether additional assumptions are needed.

    Figure 1 presents synthetic regret curves, but these do not directly establish runtime efficiency or superiority over existing methods. Section 6 refers to Sections G.3 and G.4 for the CartPole and Acrobot results and baseline descriptions (lines 475–478), but I could not locate the referenced material. Therefore, I could not verify the practical advantages claimed in the abstract or assess the fairness of the comparisons. The connection between the studied linear optimization setting and general RLHF policy optimization also remains insufficiently explained, making the practical scope of the contribution unclear.

Questions for authors
  1. Under what conditions do the main theoretical reductions hold?

    Please clarify the assumptions needed for the relationships in Remarks 1 and 2 to hold when utilities change over time. Relatedly, how does the ranking-feedback construction guarantee valid and independent pairwise comparisons? Which theoretical results remain valid after addressing these concerns?

  2. Where can the referenced supporting material be found?

    The paper repeatedly refers to supplementary sections for algorithm pseudocode, proofs, and detailed experiments, but I could not locate this material. Were these sections submitted separately? The complete algorithm descriptions and proofs are necessary to assess the proposed guarantees.

  3. How is the claimed O(dT)O(dT) runtime obtained?

    Please account for Hessian construction, eigendecomposition, and the regularized optimization step. Does this complexity require a particular decision space, barrier function, or implementation? Are there runtime measurements supporting the claimed computational advantage?

  4. What evidence supports the claimed practical advantages in RLHF?

    Please identify the CartPole and Acrobot results referenced in Sections G.3–G.4 and clarify the policy parameterization, preference generation, and feedback budgets used for each method. How do these experiments correspond to the theoretical setting, and what evidence supports the claimed advantages over the baselines?

Reviewer_jirdOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies online linear optimization with adversarially changing preferences under logistic pairwise feedback. The authors propose Mirror-Duel, a gradient-based algorithm using online mirror descent, and extend it to batched pairwise and top-m ranking feedback. The paper claims nearly optimal regret guarantees and evaluates the proposed methods on synthetic instances and RL environments.

Critical strengths

The problem of computationally efficient online optimization with preference feedback is of theoretical interest. The paper also considers multiple feedback settings, including pairwise, batched, and ranking feedback.

Critical weaknesses

Insufficient novelty and incomplete presentation. This paper exhibits substantial overlap with [1], but does not appear to properly acknowledge or discuss this closely related work. Compared with the prior paper, the current submission includes additional synthetic experiments and theoretical results, including Theorems 3, 6, and 9. However, the proofs of these theorems appear to be missing. I believe the authors should clearly explain the relationship between the two papers, identify the novel contributions of the current submission, and provide complete proofs for the additional theoretical results.

Concerns regarding the correctness of the theoretical analysis. Several steps in the proofs appear questionable. In particular, the inequality marked (a) in the proof of Remark 1 is incorrect. Moreover, the conclusion of Lemma 11 requires further justification, as the boundedness of the derivative of the sigmoid function does not necessarily imply that the conditional expectation of the gradient estimator is a scalar multiple of θt\theta_{t} These issues raise concerns about the validity of the subsequent regret analysis. I encourage the authors to carefully re-examine the theoretical arguments and provide rigorous justifications for the key results.

[1] Saha, Aadirupa, Yonathan Efroni, and Barry-John Theobald. "Dueling in the Dark: An Efficient and Optimal Mirror Descent Approach for Online Optimization with Adversarial Preferences." OPT 2024: Optimization for Machine Learning.

Questions for authors

Could the authors clarify the relationship between this work and [1], and highlight the novel contributions of this paper?

Could the authors provide the complete proofs of Theorems 3, 6, and 9? These results are essential to the claimed optimality of the proposed algorithms, but their proofs appear to be missing from the current manuscript.

Reviewer_HtPwOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online preference learning, where a learner repeatedly offers pairs of actions from a continuous decision set and receives binary feedback from a logistic preference model whose underlying parameter may change adversarially over time. The proposed method, Mirror-Duel, follows an online mirror descent design: it maintains a regularized leader iterate defined by a self-concordant barrier, offers symmetrically perturbed action pairs along a random direction determined by the barrier curvature, and builds a one-point gradient estimate from the observed preference, with the symmetric construction avoiding the link-derivative assumptions common in generalized linear bandit analyses. The stated regret guarantee matches a lower bound up to logarithmic factors, and the approach extends to batched pairwise feedback and to partial ranking feedback under a Plackett-Luce model, where more feedback per round helps but larger choice subsets do not.

Critical strengths
  • The gradient-based viewpoint is a real and relevant alternative to confidence-set methods for this problem class
  • The three feedback models are treated in a unified and reasonably complete way
  • The core proof obligations are at least present and organized
Critical weaknesses
  • The work is not practical in its present form, and its framing overstates its reach. Although the title, abstract, and introduction motivate the method almost entirely through LLM alignment and RLHF, the formal model is a context-free linear utility over a continuous decision set with no function approximation and no experiment involving a language model or human preferences; the only non-synthetic experiments use very low-dimensional linear policies on classic control tasks with a simulated preference oracle.

  • The theoretical novelty appears limited and is not delineated sharply enough. By the paper's own description, the algorithm is motivated by the Scrible-style mirror-descent construction with a self-concordant barrier and symmetric one-point gradient estimation, and one remark attributes the optimality of the main rate to an existing lower bound for this problem, while the contributions present a matching lower bound as a new result.

Questions for authors
  • What is the precise relationship between the lower bound of Thm. 3 and the existing lower bound of Saha (2021b) invoked in Rem. 3?

  • Mirror-Rank extracts mm pairs from a single Plackett–Luce ranking; these pairs are not independent Bernoulli observations with a common θt∗\theta_t^\ast (Supp. Lem. 14). How exactly do the unbiasedness and variance calculations for the aggregated gradient estimate handle this dependence, and does the reduction to the B=mB = m batched setting lose anything in constants or logarithmic factors?

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

Related papers

Discussion (0)

Sign in to comment.