- 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 bound known for KL-regularized regret. For the offline setting, they obtain exponentially decreasing expected temperature-zero regret, corresponding to 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 . When 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 puts all its weight (but on an action that is clearly suboptimal. Then the number of "true observations" is multiplied by , 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"