mlsanityData to 14 Oct 2026

Demystifying the unreasonable effectiveness of online alignment methods

arXiv 2604.17207 ↗First posted 19 Apr 2026cs.LG cs.AI cs.CCcited by 0

On the map: LLM alignment / RLHF / preference optimisation → LLM preference optimization methods

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.

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.

Builds on

20 of 24 references.

Closest ancestors · 5

Same direction, newest first

  1. 2026Coverage Improvement and Fast Convergence of On-policy Preference Learning13 Jan
  2. 2025Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment27 Mar
  3. 2024Direct Language Model Alignment from Online AI Feedback7 Feb
  4. 2023A General Theoretical Paradigm to Understand Learning from Human Preferences18 Oct
  5. 2022Training language models to follow instructions with human feedback4 Mar

Other references · 15

  1. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  2. 2017Deep reinforcement learning from human preferencescited by 3,912
  3. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,986
  4. 2021WebGPT: Browser-assisted question-answering with human feedbackcited by 1,745
  5. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 350
  6. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  7. 2023Is RLHF More Difficult than Standard RL?cited by 96
  8. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  9. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  10. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 33
  11. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 22
  12. 2018Simple Regret Minimization for Contextual Banditscited by 16
3 more
  1. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 11
  2. 2023Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimizationcited by 7
  3. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Oracle-Robust Online Alignment for Large Language Models
  2. 2024Sample-Efficient Alignment for LLMs
  3. 2026Reward Shaping for (Inference-Time) Alignment: A Stackelberg Game Perspective
  4. 2024Understanding the performance gap between online and offline alignment algorithms
  5. 2026Personalized Alignment Revisited: The Necessity and Sufficiency of User Diversity
  6. 2024Generalized Preference Optimization: A Unified Approach to Offline Alignment
  7. 2025The Differences Between Direct Alignment Algorithms are a Blur
  8. 2026Towards a theory of inference-time alignment with unknown rewards