acceptodds
Withdrawn from ICLR 2027

Greedy alignment methods are probably (and provably) more efficient than you think

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

AI alignment methods based on Bradley-Terry reward-model fitting and KL-regularized Alignment methods are remarkably effective in both offline and online preference-learning pipelines, yet existing online and offline rate guarantees can seem pessimistic relative to their empirical performance. We argue that this mismatch reflects a distinction between two learning targets: KL-regularized regret measures recovery of the entire finite-temperature policy, whereas reward learning and best-response identification ask whether the learned reward induces the correct top-ranked response. To isolate this reward-learning component, we study the traditional temperature-zero regret criterion, which evaluates only the top-ranked response at inference time. Under this decision-centric notion of performance, we prove that exact reference-logged offline RLHF achieves exponentially small expected temperature-zero regret, and therefore reaches expected regret at most \(\epsilon\) with \(O(\log(1/\epsilon))\) offline comparisons. We also prove that standard greedy online alignment methods, including online RLHF and online DPO, achieve constant \((O(1))\) cumulative temperature-zero regret. By separating selector identification from full soft-policy recovery, our results provide a sharper theoretical explanation for the empirical efficiency of greedy alignment.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
AI alignment, regret analysis

Reviews

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

The paper studies greedy reinforcement learning from human feedback (RLHF), where a reward model is learned from preference comparisons and used to construct a KL-regularized policy. The authors consider a different notion of regret, called temperature-zero regret, which measures the loss from selecting the response with the highest estimated reward, rather than evaluating the full KL-regularized policy. Under realizability, compactness, and a uniform reward-gap assumption, they show that greedy online RLHF achieves O(1) cumulative temperature-zero regret, improving on the O(log⁡T)O(\log T) bound known for KL-regularized regret. For the offline setting, they obtain exponentially decreasing expected temperature-zero regret, corresponding to O(log⁡(1/ε))O(\log(1/\varepsilon)) sample complexity. The results are illustrated with experiments on a linear Bradley–Terry model.

Critical strengths

The paper on online learning and its connections to alignment is interesting, and the proofs seem correct as far as I can see.

Critical weaknesses

My main concern is that the theoretical results rely on very strong assumptions and fairly standard arguments (independently of alignment). In fact, if the context space were finite, the techniques would be rather straightforward. Let me explain why.

1. Online Result is Not Specific to Greedy Alignment.

Because fitted rewards are uniformly bounded, KL-tilted sampling simply mixes in the reference policy with a fixed weight, so it ends up as a fancy variant of epsilon-greedy. Bounded temperature-zero regret follows directly from the offline proof, and the same bound holds for pure reference logging. The reason is that it is not really "regret" (in the bandit sense), but a measure of how far estimates are from true quantities. It is well known that this works with epsilon-greedy. Thus, comparing this to logarithmic KL-regularized regret (Table 1) is quite misleading.

2. Condition (C2) is Unrealistically Strong.

By Lemma 17, (C2) forces the best-response rule to be constant on connected components. For standard continuous parameter spaces (balls, boxes), this requires all candidate rewards to share the exact same best response. With a large context space, this assumption is huge (unless for finite ones).

3. Rates Hide Enormous Constants.

The bounds hide extreme dependencies on the reference policy π0\pi_0. When π0\pi_0 assigns tiny probabilities to responses, as base language models do, the required sample size scales with their inverse square (if I am correct, maybe just the inverse). These rates are not comparable to explicit coverage bounds (e.g., Zhao et al., 2025b). Indeed, imagine that π0\pi_0 puts all its weight (but ε)\varepsilon) on an action that is clearly suboptimal. Then the number of "true observations" is multiplied by ε\varepsilon, and hence the rates degrade substantially.

4. Weak Empirical Validation.

Assumptions are violated in practice, and I am not convinced by many of the arguments in this section (since some of them seem to be contradicted by the theoretical results in the Appendix).

Conclusion

I did not find an error in the proofs, which appear careful. My concern is rather that, under these assumptions, the results follow from standard arguments and do not, in my view, explain the efficiency of greedy alignment. For instance, consider the case without context and only two actions. The results would be fairly standard and well known. Going beyond this setting seems to be purely a matter of handling technicalities that provide no new insights into the problem.

Questions for authors

I invite the authors to address the points raised in "critical weaknesses"

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

This work studies whether existing regret guarantees for preference-based alignment are overly pessimistic when the goal is to identify the best response rather than learn the entire KL-regularized policy. In this setup, a reward model is fitted at each step and then used to update the policy. The authors then consider temperature-zero regret, which measures the loss of selecting the response with the highest estimated reward rather than the true best one. Under assumptions on the reward class, they show that the expected regret decreases exponentially with the number of offline comparisons, along with other results on online procedures and DPO-like formulation. They illustrate their findings using a synthetic experiment with six actions.

Critical strengths

It is useful whether existing regret guarantees are overly pessimistic if one considers simpler objectives. The paper is also reasonably easy to follow.

Critical weaknesses

I am not sure that the specified objective helps explain the effectiveness of preference-based alignment. I hope the authors can help me understand the following, what is the practical decision problem that this metric is intended to capture? If the goal is simply learning a good reward model, why do we need to do so in an online setting as part of policy training?

For one, the authors evaluate the response with highest estimated reward over the entire support of the reference. For LLMs, this support includes responses that are extremely unlikely to be sampled. Hence, we can achieve zero tempeturare-zero regret even when the learned policy is unlikely to generate the best response. Relatedly, I encourage the authors to consider standard assumptions like that of coverage, common in inference-time alignment analysis [1] (noting that this targets another objective than what the authors have). This point is particularly relevant, since despite logarithmic sample complexity, it might be highly improbable to get the best response during training so the constants blow up and the guarantee has minimal practical consequence.

Side note: I find the term temperature-zero confusing, it makes me think you are evaluating the most probable response under the model, as in greedy decoding.

[1] Huang, Audrey, et al. "Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment."

Questions for authors

See my questions in the weaknesses section.

Also, assume the reward class is convex and C2 holds. Wouldn't you achieve zero regret w/o learning anything from data? Since all the reward models in your class must have the same best response under C2, independently of the preference data.

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

This paper studied that existing KL-regularized regret guarantees for greedy RLHF understate how quickly the reward model learns the best response. It introduces "temperature-zero regret", which evaluates only the top-ranked response of the fitted reward. The analysis assumes realizability, a compact reward class (C1), and a uniform best-response margin over every reward in the class (C2). Under these assumptions, exact offline RLHF on reference-policy data has expected temperature-zero regret that decays exponentially in n. Exact greedy online RLHF has bounded O(1) cumulative temperature-zero regret. Simulations are conducted.

Critical strengths

The paper draws a useful distinction between identifying the best response and recovering the full soft policy. It gives a clean explanation of why KL-regularized regret may look pessimistic when a reward model is only used to choose the top response.

Critical weaknesses
  1. Condition C2 requires a margin for every reward in the fitted class, not only for the true reward. This condition is too strict. The paper's own experiment violates C2. Table 1 also contrasts rates proved under C2 with rates from Wu et al. (2025), which do not assume it.

  2. The paper did not conduct real data analysis.

Questions for authors
  1. Can the results be proved with a margin only at the true reward?
  2. Under C1–C2, is KL-regularized regret still O(logT)O(log T) online and O(1/ϵ)O(1/\epsilon) offline? A matching lower bound under the same assumptions would be needed to support the separation in Table 1.
  3. Temperature-zero regret scores an ideal argmax over the reference support, assumes an exact ERM every round, and for DPO assumes exact optimization over a matched policy class. How do the guarantees change with approximate optimization?
  4. Is it possible to conduct real data analysis?

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

Related papers

Discussion (0)

Sign in to comment.