Research map / Probabilistic and scientific modeling / Bayesian optimization
Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MR-LPF, a multi-round, variance-driven pair-selection algorithm with action elimination for Bayesian optimization from pairwise preference feedback under the BTL model, proving regret O~(sqrt(Gamma(T) T)) without kappa dependence.
Problem
Bayesian optimization from binary pairwise preference feedback (BOHF) under the Bradley-Terry-Luce model, where existing regret bounds are loose (kappa-dependent, or polynomial in T) for kernels with slow eigendecay such as Matérn and NT kernels.
Approach
A multi-round algorithm (MR-LPF) that in each round samples the pair with maximum kernel-based preference variance, then eliminates actions whose upper confidence bound on preference against any other action falls below 0.5; the round structure makes observation points independent of outcomes, yielding tighter confidence intervals and removing the kappa dependence in regret.
Key results
- MR-LPF achieves regret bound O~(sqrt(Gamma(T) T)), improving over the O~(Gamma(T) kappa^2 sqrt(T)) bound of MaxMinLCB and the O~((Gamma(T)T)^{3/4}) bound of POP-BO.
- Sample complexities for linear, SE and Matérn kernels match conventional BO lower bounds up to logarithmic factors (informal argument).
- In experiments averaged over 60 runs, MR-LPF consistently achieves lower average regret than MaxMinLCB on RKHS test functions, Ackley, and the Yelp dataset.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MR-LPF instead of MaxMinLCB | BOHF · BOHF | cumulative regret upper bound: \Oct\left(\Gamma(T)\kappa^2\sqrt{T}\right) -> \Oct\left(\sqrt{\Gamma(T)T}\right) | Helped |
| use MR-LPF instead of POP-BO | BOHF · BOHF | cumulative regret upper bound: \Oct\left((\Gamma(T) T)^{3/4}\right) -> \Oct\left(\sqrt{\Gamma(T)T}\right) | Helped |
| use MR-LPF instead of MaxMinLCB | BOHF test functions · RKHS and Ackley test functions | average regret | Helped |
| use MR-LPF instead of MaxMinLCB | BOHF · Yelp Open Dataset | average regret | Helped |
Surprising findings
- Binary preference feedback achieves the same order of sample complexity as scalar-valued feedback in conventional BO.
Limitations
- The sample complexity comparison to conventional BO lower bounds is informal, since the lower bound construction assumes Gaussian noise while BTL corresponds to Gumbel-type noise.
- Regret bound depends on the RKHS norm bound B and on L, and requires T at least a threshold T_0 for the confidence intervals to hold.
- Experiments are limited to a 1D synthetic setting, Ackley, and a 32-dimensional Yelp embedding, with a single kernel choice for Yelp.
Experimental setup
Datasets: Yelp Open Dataset
Benchmarks: RKHS test functions Ackley function Yelp Open Dataset
Metrics: cumulative regret average regret
Baselines: MaxMinLCB POP-BO
Builds on: Batch Pure Exploration (BPE) MaxMinLCB POP-BO
Closest papers by meaning
- Principled Preferential Bayesian Optimization (ICML 2024 · similarity 0.90)
- Making RL with Preference-based Feedback Efficient via Randomization (ICLR 2024 · similarity 0.89)
- Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences (ICML 2024 · similarity 0.89)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.89)
- A Minimaximalist Approach to Reinforcement Learning from Human Feedback (ICML 2024 · similarity 0.89)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.