Research map / Probabilistic and scientific modeling / Bayesian optimization
Principled Preferential Bayesian Optimization
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 POP-BO, an optimistic preferential Bayesian optimization algorithm with a likelihood-ratio confidence set built from pairwise preference feedback, giving the first information-theoretic cumulative regret bound for preferential BO.
Problem
Preferential Bayesian optimization: maximizing a black-box function observed only through pairwise preference (duel) feedback, where existing methods are heuristic and lack cumulative regret or convergence guarantees on continuous domains.
Approach
Builds a likelihood-ratio confidence set over RKHS functions from Bradley-Terry-Luce preference data only, runs optimistic selection of duels with the reference point set to the previous query, and reduces the infinite-dimensional bi-level problems to finite convex programs via the representer theorem.
Key results
- On test functions after 30 steps, POP-BO has the lowest suboptimality on all seven problems, e.g., Beale 0.008±0.025 vs 0.10 for SGP and 0.15 for qEUBO.
- On GP-sampled instances, POP-BO achieves the lowest cumulative regret growth; qEUBO has more than 2.5 times the cumulative regret of POP-BO.
- POP-BO's computation time is about 0.09 of DTS's time (DTS normalized to 1.0), a more than 10x speed-up.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use POP-BO instead of SGP | preferential BO on Beale · Beale, final reported solution after 30 steps | suboptimality: 0.10\pm0.19 -> 0.008\pm0.025 | Helped |
| Use POP-BO instead of qEUBO | preferential BO on Branin · Branin, final reported solution after 30 steps | suboptimality: 0.71\pm1.16 -> 0.31\pm0.29 | Helped |
| Use POP-BO instead of qEUBO | preferential BO on Bukin · Bukin, final reported solution after 30 steps | suboptimality: 0.59\pm1.20 -> 0.92\pm0.54 | Hurt |
| Use POP-BO instead of DTS | preferential BO on Cross-in-Tray · Cross-in-Tray, final reported solution after 30 steps | suboptimality: 1.56\pm1.39 -> 1.38\pm0.97 | Helped |
| Use POP-BO instead of SGP | preferential BO on Eggholder · Eggholder, final reported solution after 30 steps | suboptimality: 1.87\pm0.94 -> 1.83\pm0.96 | Helped |
| Use POP-BO instead of SGP | preferential BO on Holder Table · Holder Table, final reported solution after 30 steps | suboptimality: 1.56\pm1.62 -> 1.22\pm1.01 | Helped |
| Use POP-BO instead of qEUBO | preferential BO on Levy13 · Levy13, final reported solution after 30 steps | suboptimality: 1.06\pm1.22 -> 0.35\pm0.31 | Helped |
| Use POP-BO instead of DTS | preferential BO on sampled Gaussian-process instances · Sampled Gaussian-process instances | computation time normalized against DTS: 1.0 -> 0.09 | Helped |
| Use SGP instead of POP-BO | preferential BO on sampled Gaussian-process instances · Sampled Gaussian-process instances | computation time normalized against DTS: 0.09 -> 0.07 | Helped |
| Use POP-BO instead of qEUBO | preferential BO on sampled Gaussian-process instances · Sampled Gaussian-process instances | cumulative regret | Helped |
| Report the maximizer of the minimum-norm MLE instead of the uncertainty-minimizing sampled solution | POP-BO on sampled Gaussian-process instances · Sampled Gaussian-process instances | convergence speed of reported solution | Helped |
Surprising findings
- The paper's kernel-specific bounds imply preference-based regret carries an extra factor of T^{1/4} compared with scalar-feedback GP-UCB, reflecting the lower information content of preferences.
- qEUBO slightly outperforms POP-BO in the reported-solution convergence on GP-sampled instances, though it has much higher cumulative regret.
Limitations
- Theory assumes a known compact domain, bounded RKHS norm B (adapted heuristically in practice), and a fixed kernel; the regret bounds are loose, with an extra T^{1/4} factor relative to scalar feedback.
- Grid search or nonlinear programming is needed for the inner/outer optimization, so high-dimensional scalability is only shown up to 12 dimensions.
- Experiments are limited to simulated preference oracles and a single real-world-style thermal comfort problem.
Experimental setup
Datasets: Gaussian process sampled instances standard global optimization test functions (Beale, Branin, Bukin, Cross-in-Tray, Eggholder, Holder Table, Levy13) thermal comfort optimization problem
Benchmarks: Gaussian process sampled instances (SE kernel, 30 instances) Beale Branin Bukin Cross-in-Tray Eggholder Holder Table Levy13 12-dimensional GP-sampled function
Metrics: cumulative regret suboptimality of reported solution normalized computation time
Baselines: dueling Thompson sampling (DTS) skew-GP preferential BO (SGP) qEUBO
Builds on: GP-UCB dueling Thompson sampling likelihood ratio confidence set Bradley-Terry-Luce model
Closest papers by meaning
- Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds (ICML 2025 · similarity 0.90)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.90)
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.89)
- Stopping Bayesian Optimization with Probabilistic Regret Bounds (NeurIPS 2024 · similarity 0.89)
- Preference-Aware Constrained Multi-Objective Bayesian Optimization (Student Abstract) (AAAI 2024 · similarity 0.88)
- Multi-Objective Bayesian Optimization with Active Preference Learning (AAAI 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.