mlsanityData to 7 Oct 2026

Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences

arXiv 2602.23116 ↗First posted 26 Feb 2026cs.LG cs.GT stat.MLcited by 5

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF

Abstract (arXiv)

We consider the problem of regularized best-response max-regret minimization in online RLHF under general preferences and bandit feedback. While various regularizers are utilized to robustify alignment, known polylogarithmic regret guarantees remain heavily specific to KL. To investigate whether such fast rates extend beyond KL, we adopt the Generalized Bilinear Preference Model (GBPM) -- capturing intransitive preferences over d-dimensional item-wise features via a rank-2r skew-symmetric matrix -- to isolate the impact of generic regularization. Crucially, under GBPM, we prove that the dual gap of any greedy policy is bounded by the squared estimation error, derived using only strong convexity and skew-symmetry. Under a feature coverage assumption, we establish a generic polylogarithmic regret of tildeO(η d4 Cmin-1 (log T)2 wedge d2 Cmin-1/2 √T) with Greedy Sampling, and a dimension-wise improved regret (for well-conditioned arm-sets) of tildeO(Cmin-2 √η r T wedge r1/3 Cmin-4/3 T2/3) with Explore-Then-Commit, where η-1 is the regularization coefficient, T is the time horizon, and Cmin is an arm-set dependent quantity. This demonstrates that ``fast'' regrets are not KL-specific, but rather a fundamental consequence of generic strongly convex geometry.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 91 of its 134 references that are in the map. First posted on arXiv 26 Feb 2026.

Builds on

91 of 134 references.

Closest ancestors · 18

Same direction, newest first

  1. 2025Greedy Sampling Is Provably Efficient for RLHF28 Oct
  2. 2025RSPO: Regularized Self-Play Alignment of Large Language Models24 Feb
  3. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descent24 Feb
  4. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learning11 Feb
  5. 2025KL-Regularized RLHF with Multiple Reference Models: Exact Solutions and Sample Complexity3 Feb
  6. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHF7 Nov
  7. 2024Beyond Bradley-Terry Models: A General Preference Model for Language Model Alignment3 Oct
  8. 2024RLHF Workflow: From Reward Modeling to Online RLHF13 May
  9. 2024Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences4 Apr
  10. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Model11 Feb
  11. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedback8 Jan
  12. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint18 Dec
6 more
  1. 2023Nash Learning from Human Feedback1 Dec
  2. 2023Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback27 Jul
  3. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons26 Jan
  4. 2022Causal Confusion and Reward Misidentification in Preference-Based Reward Learning13 Apr
  5. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback12 Apr
  6. 2017Deep reinforcement learning from human preferences12 Jun

Other references · 73

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2024The Llama 3 Herd of Modelscited by 14,192
  3. 2024Qwen2.5 Technical Reportcited by 4,713
  4. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  5. 2023UltraFeedback: Boosting Language Models with Scaled AI Feedbackcited by 394
  6. 2019A Theory of Regularized Markov Decision Processescited by 279
  7. 2017Training GANs with Optimismcited by 217
  8. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  9. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  10. 2017A unified view of entropy-regularized Markov decision processescited by 174
  11. 2023Beyond Reverse KL: Generalizing Direct Preference Optimization with Diverse Divergence Constraintscited by 174
  12. 2015Fast Convergence of Regularized Learning in Gamescited by 149
38 more
  1. 2024Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputscited by 148
  2. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  3. 2023Aligning Language Models with Preferences through f-divergence Minimizationcited by 118
  4. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  5. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  6. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  7. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  8. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  9. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  10. 2015Contextual Dueling Banditscited by 101
  11. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  12. 2019Open-ended Learning in Symmetric Zero-sum Gamescited by 96
  13. 2017Mostly Exploration-Free Algorithms for Contextual Banditscited by 85
  14. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  15. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  16. 2024Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimizationcited by 78
  17. 2018What Doubling Tricks Can and Can't Do for Multi-Armed Banditscited by 69
  18. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  19. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  20. 2020High-Dimensional Sparse Linear Banditscited by 61
  21. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  22. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 56
  23. 2019Doubly-Robust Lasso Banditcited by 49
  24. 2020Low-Rank Generalized Linear Bandit Problemscited by 48
  25. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  26. 2015Fighting Bandits with a New Kind of Smoothnesscited by 45
  27. 2020Sparsity-Agnostic Lasso Banditcited by 44
  28. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  29. 2020Understanding Learned Reward Functionscited by 37
  30. 2017Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learningcited by 36
  31. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  32. 2020Adversarial Dueling Banditscited by 33
  33. 2016A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Banditscited by 31
  34. 2020Self-Concordant Analysis of Generalized Linear Bandits with Forgettingcited by 29
  35. 2024A Unified Confidence Sequence for Generalized Linear Models, with Applications to Banditscited by 27
  36. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  37. 2018Path Consistency Learning in Tsallis Entropy Regularized MDPscited by 22
  38. 2021A Simple Unified Framework for High Dimensional Bandit Problemscited by 21

50 most cited of 73 All 73 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 1
  2. 2026Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecificationcited by 1
  3. 2026Demystifying the unreasonable effectiveness of online alignment methodscited by 0
  4. 2026Efficient Exploration for Iterative Nash Preference Optimizationcited by 0
  5. 2026When Greedy Sampling Explores: KL-Regularized Contextual Bandits without Eluder-Dimension Dependencecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Offline and Online KL-Regularized RLHF under Differential Privacy
  2. 2025Thompson Sampling in Online RLHF with General Function Approximation
  3. 2024On the Exponential Convergence for Offline RLHF with Pairwise Comparisons
  4. 2026Offline Constrained RLHF with Multiple Preference Oracles
  5. 2025Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds
  6. 2026f-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analyses
  7. 2024Online Bandit Learning with Offline Preference Data for Improved RLHF
  8. 2024Generalized Preference Optimization: A Unified Approach to Offline Alignment