Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds
This work addresses the challenge of optimizing actions using limited and costly human feedback, with incremental improvements in theoretical guarantees for the BOHF framework.
The paper tackles the problem of Bayesian optimization with preference-based feedback (BOHF), where only pairwise preferences are available, and derives tighter regret bounds of ̃O(√(Γ(T)T)), significantly improving existing results and showing that preferential samples can be as efficient as scalar-valued samples for finding near-optimal solutions.
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 $\tilde{\mathcal{O}}(\sqrt{Γ(T)T})$, where $Γ(T)$ represents the maximum information gain$\unicode{x2014}$a kernel-specific complexity term$\unicode{x2014}$and $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 BO$\unicode{x2014}$achieved with richer feedback models$\unicode{x2014}$are recovered. In other words, the same number of preferential samples as scalar-valued samples is sufficient to find a nearly optimal solution.