mlsanityData to 14 Oct 2026

Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds

arXiv 2505.23673 ↗First posted 29 May 2025cs.LGcited by 3

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

Abstract (arXiv)

Bayesian optimization (BO) with preference-based feedback has recently garnered significant attention due to its emerging applications. We refer to this problem as Bayesian Optimization from Human Feedback (BOHF), which differs from conventional BO by learning the best actions from a reduced feedback model, where only the preference between two actions is revealed to the learner at each time step. The objective is to identify the best action using a limited number of preference queries, typically obtained through costly human feedback. Existing work, which adopts the Bradley-Terry-Luce (BTL) feedback model, provides regret bounds for the performance of several algorithms. In this work, within the same framework we develop tighter performance guarantees. Specifically, we derive regret bounds of tildeO(√Gamma(T)T), where Gamma(T) represents the maximum information gainunicodex2014a kernel-specific complexity termunicodex2014and T is the number of queries. Our results significantly improve upon existing bounds. Notably, for common kernels, we show that the order-optimal sample complexities of conventional BOunicodex2014achieved with richer feedback modelsunicodex2014are recovered. In other words, the same number of preferential samples as scalar-valued samples is sufficient to find a nearly optimal solution.

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

Builds on

37 of 60 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Bandits with Preference Feedback: A Stackelberg Game Perspective24 Jun
  2. 2024Active Preference Optimization for Sample Efficient RLHF16 Feb
  3. 2023Making RL with Preference-based Feedback Efficient via Randomization23 Oct

Other references · 34

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2018A Tutorial on Bayesian Optimizationcited by 744
  3. 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 609
  4. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  5. 2017On Kernelized Multi-armed Banditscited by 352
  6. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  7. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  8. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  9. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 102
  10. 2015Contextual Dueling Banditscited by 101
  11. 2020Mat'ern Gaussian processes on Riemannian manifoldscited by 82
  12. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
22 more
  1. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  2. 2013A Literature Survey of Benchmark Functions For Global Optimization Problemscited by 77
  3. 2017Preferential Bayesian Optimizationcited by 74
  4. 2023InstructZero: Efficient Instruction Optimization for Black-Box Large Language Modelscited by 68
  5. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  6. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  7. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  8. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  9. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  10. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  11. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  12. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  13. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 37
  14. 2024Prompt Optimization with Human Feedbackcited by 35
  15. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 27
  16. 2023On the Sublinear Regret of GP-UCBcited by 26
  17. 2020Projective Preferential Bayesian Optimizationcited by 22
  18. 2023Towards Practical Preferential Bayesian Optimization with Skew Gaussian Processescited by 19
  19. 2017Maximum Selection and Ranking under Noisy Comparisonscited by 18
  20. 2024Principled Preferential Bayesian Optimizationcited by 16
  21. 2019Zeroth Order Non-convex optimization with Dueling-Choice Banditscited by 11
  22. 2023Kernelized Offline Contextual Dueling Banditscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  2. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0
  3. 2026On the Complexity of Preference-Based Banditscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026A Regret Minimization Framework on Preference Learning in Large Language Models
  2. 2025Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
  3. 2026Wasserstein Distributionally Robust Regret Optimization for Reinforcement Learning from Human Feedback
  4. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences
  5. 2025Efficient Reinforcement Learning from Human Feedback via Bayesian Preference Inference
  6. 2026Reinforcement Learning from Human Feedback: A Statistical Perspective
  7. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Sampling
  8. 2024Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences