mlsanityData to 7 Oct 2026

Thompson Sampling in Online RLHF with General Function Approximation

arXiv 2505.23927 ↗First posted 29 May 2025cs.LGcited by 0

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

Abstract (arXiv)

Reinforcement learning from human feedback (RLHF) has achieved great empirical success in aligning large language models (LLMs) with human preference, and it is of great importance to study the statistical efficiency of RLHF algorithms from a theoretical perspective. In this work, we consider the online RLHF setting where the preference data is revealed during the learning process and study action value function approximation. We design a model-free posterior sampling algorithm for online RLHF inspired by Thompson sampling and provide its theoretical guarantee. Specifically, we adopt Bellman eluder (BE) dimension as the complexity measure of the function class and establish O(√T) regret bound for the proposed algorithm with other multiplicative factor depending on the horizon, BE dimension and the log-bracketing number of the function class. Further, in the analysis, we first establish the concentration-type inequality of the squared Bellman error bound based on the maximum likelihood estimator (MLE) generalization bound, which plays the crucial rules in obtaining the eluder-type regret bound and may be of independent interest.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 49 of its 60 references that are in the map. First posted on arXiv 29 May 2025.

Builds on

49 of 60 references.

Closest ancestors · 13

Same direction, newest first

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint18 Dec
  2. 2023Making RL with Preference-based Feedback Efficient via Randomization23 Oct
  3. 2023ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Models16 Oct
  4. 2023Reinforced Self-Training (ReST) for Language Modeling17 Aug
  5. 2023Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback27 Jul
  6. 2023Is RLHF More Difficult than Standard RL?25 Jun
  7. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimism29 May
  8. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Model29 May
  9. 2023SLiC-HF: Sequence Likelihood Calibration with Human Feedback17 May
  10. 2023RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignment13 Apr
  11. 2023RRHF: Rank Responses to Align Language Models with Human Feedback without tears11 Apr
  12. 2022Scaling Laws for Reward Model Overoptimization19 Oct
1 more
  1. 2017Deep reinforcement learning from human preferences12 Jun

Other references · 36

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2022Training language models to follow instructions with human feedbackcited by 15,712
  3. 2017Proximal Policy Optimization Algorithmscited by 14,441
  4. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  5. 2020Learning to summarize from human feedbackcited by 2,562
  6. 2019An Introduction to Variational Autoencoderscited by 997
  7. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 906
  8. 2023Statistical Rejection Sampling Improves Preference Optimizationcited by 321
  9. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  10. 2013Learning to Optimize Via Posterior Samplingcited by 253
  11. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  12. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 218
24 more
  1. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  2. 2020Implementation Matters in Deep Policy Gradients: A Case Study on PPO and TRPOcited by 184
  3. 2023Beyond Reverse KL: Generalizing Direct Preference Optimization with Diverse Divergence Constraintscited by 174
  4. 2017Interactive Learning from Policy-Dependent Human Feedbackcited by 155
  5. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  6. 2015Contextual Dueling Banditscited by 101
  7. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
  8. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  9. 2019On the Weaknesses of Reinforcement Learning for Neural Machine Translationcited by 82
  10. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  11. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  12. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  13. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  14. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  15. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  16. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  17. 2023Fine-Tuning Language Models with Advantage-Induced Policy Alignmentcited by 48
  18. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  19. 2013Learning Trajectory Preferences for Manipulators via Iterative Improvementcited by 31
  20. 2023Approximate Thompson Sampling via Epistemic Neural Networkscited by 31
  21. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  22. 2022Efficient Active Learning with Abstentioncited by 21
  23. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  24. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Provably Efficient Online RLHF with One-Pass Reward Modeling
  2. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Sampling
  3. 2026f-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analyses
  4. 2025Greedy Sampling Is Provably Efficient for RLHF
  5. 2024Online Bandit Learning with Offline Preference Data for Improved RLHF
  6. 2025Avoiding mathbfexp(Rmax) scaling in RLHF through Preference-based Exploration
  7. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  8. 2024RLHF Workflow: From Reward Modeling to Online RLHF