# Demystifying the unreasonable effectiveness of online alignment methods

arXiv: https://arxiv.org/abs/2604.17207 · HTML: https://mlsanity.com/paper/2604.17207/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in LLM preference optimization methods, one of 10 directions in LLM alignment / RLHF / preference optimisation.
- Builds on 20 of its 24 references that are in the map.
- First posted on arXiv 19 Apr 2026.

## Placed in

- LLM alignment / RLHF / preference optimisation / [LLM preference optimization methods](https://mlsanity.com/alignment/llm-preference-optimization-methods/)

## Builds on (most cited first, 20 of 20)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Direct Language Model Alignment from Online AI Feedback](https://mlsanity.com/paper/2402.04792/) (2024)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Is RLHF More Difficult than Standard RL?](https://mlsanity.com/paper/2306.14111/) (2023)
- [Preference-based Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2006.08910/) (2020)
- [Online Iterative Reinforcement Learning from Human Feedback with General Preference Model](https://mlsanity.com/paper/2402.07314/) (2024)
- [Sharp Analysis for KL-Regularized Contextual Bandits and RLHF](https://mlsanity.com/paper/2411.04625/) (2024)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [Simple Regret Minimization for Contextual Bandits](https://mlsanity.com/paper/1810.07371/) (2018)
- [Greedy Sampling Is Provably Efficient for RLHF](https://mlsanity.com/paper/2510.24700/) (2025)
- [Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization](https://mlsanity.com/paper/2307.02108/) (2023)
- [Coverage Improvement and Fast Convergence of On-policy Preference Learning](https://mlsanity.com/paper/2601.08421/) (2026)
- [Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences](https://mlsanity.com/paper/2602.23116/) (2026)

## Abstract (arXiv)

Greedy AI alignment methods based on Bradley-Terry reward-model fitting and KL-regularized Alignment are remarkably effective in both offline and online preference-learning pipelines, yet existing O(log T) online and O(1/epsilon) offline KL-regularized regret 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 how fast we can recover the KL-regularized aligned policy, whereas we often only ask how fast we can learn the reward function that induces the correct best 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 realizability, compactness, and a uniform best-response margin over the fitted reward class, 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ε)) offline comparisons. We also prove that exact greedy online RLHF achieves bounded O(1) cumulative temperature-zero regret; the same guarantee extends to its equivalent pairwise online DPO formulation. By separating selector identification from full soft-policy recovery, our results provide a sharper theoretical explanation for the empirical efficiency of greedy alignment.