Demystifying the unreasonable effectiveness of online alignment methods
Provides a sharper theoretical foundation for the effectiveness of online RLHF and online DPO, addressing a key gap for practitioners and theorists in AI alignment.
The paper resolves the mismatch between theoretical guarantees and empirical performance of greedy online alignment methods by proving they achieve constant (O(1)) cumulative regret under a decision-centric temperature-zero regret criterion, explaining their practical efficiency.
Iterative alignment methods based on purely greedy updates are remarkably effective in practice, yet existing theoretical guarantees of \(O(\log T)\) KL-regularized regret can seem pessimistic relative to their empirical performance. In this paper, we argue that this mismatch arises from the regret criterion itself: KL-regularized regret conflates the statistical cost of learning with the exploratory randomization induced by the softened training policy. To separate these effects, 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 standard greedy online alignment methods, including online RLHF and online DPO, achieve constant \((O(1))\) cumulative regret. By isolating the cost of identifying the best response from the stochasticity induced by regularization, our results provide a sharper theoretical explanation for the practical superb efficiency of greedy alignment.