# Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds

arXiv: https://arxiv.org/abs/2505.23673 · HTML: https://mlsanity.com/paper/2505.23673/

## 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.

## Placed in

- LLM alignment / RLHF / preference optimisation / [Reward modeling and RLHF](https://mlsanity.com/alignment/reward-modeling-and-rlhf/)

## Builds on (most cited first, 30 of 37)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [Mat'ern Gaussian processes on Riemannian manifolds](https://mlsanity.com/paper/2006.10160/) (2020)
- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [A Literature Survey of Benchmark Functions For Global Optimization Problems](https://mlsanity.com/paper/1308.4008/) (2013)
- [Preferential Bayesian Optimization](https://mlsanity.com/paper/1704.03651/) (2017)
- [InstructZero: Efficient Instruction Optimization for Black-Box Large Language Models](https://mlsanity.com/paper/2306.03082/) (2023)
- [Preference-based Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2006.08910/) (2020)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [Active Preference Optimization for Sample Efficient RLHF](https://mlsanity.com/paper/2402.10500/) (2024)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Dueling Posterior Sampling for Preference-Based Reinforcement Learning](https://mlsanity.com/paper/1908.01289/) (2019)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Prompt Optimization with Human Feedback](https://mlsanity.com/paper/2405.17346/) (2024)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)

## Built on by (most cited first, 3 of 3)

- [A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback](https://mlsanity.com/paper/2604.25025/) (2026)
- [Learning Kernel-Based MDPs from Episodic Preferential Feedback](https://mlsanity.com/paper/2605.23650/) (2026)
- [On the Complexity of Preference-Based Bandits](https://mlsanity.com/paper/2609.39351/) (2026)

## 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.