Research map / Probabilistic and scientific modeling / Bayesian optimization
Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index
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.
Connects cost-aware Bayesian optimization to the Pandora's Box problem and proposes PBGI acquisition functions (Gittins index as acquisition), with a decaying-lambda variant PBGI-D, evaluated on synthetic, benchmark and empirical cost-aware tasks.
Problem
Cost-aware Bayesian optimization needs acquisition functions that are theoretically principled and computationally simple; EIPC can perform arbitrarily worse than optimal and is insensitive to cost scale.
Approach
Reinterpret the Gittins index solution of the Pandora's Box problem as an acquisition function: the fair value g solving EI(x; g) = lambda*c(x), applied to the GP posterior at each step, with lambda acting as a risk/budget hyperparameter and a decay schedule (PBGI-D).
Key results
- PBGI variants match or outperform the strongest baselines on most medium-hard problems of moderate dimension, and are competitive in uniform-cost settings.
- On the Ackley function (d=16), PBGI outperforms PBGI-D and baselines in the uniform-cost setting; on Rosenbrock, PBGI-D performs strongest among cost-aware methods.
- On Robot Pushing, PBGI performs poorly while LogEI variants perform best; PBGI-D works reasonably well on five of six cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PBGI instead of non-myopic (B)MSEI | Bayesian optimization · Bayesian regret d=16 | regret | Helped |
| Use PBGI rather than the strongest baselines | Bayesian optimization · Bayesian regret d=8 | regret | No clear effect |
| Use PBGI on uniformly costly problems | Bayesian optimization · Bayesian regret d=32 | regret | No clear effect |
| Use PBGI on Ackley | Bayesian optimization · Ackley d=16 | regret | Helped |
| Use PBGI-D on Levy instead of other methods | Bayesian optimization · Levy d=16 varying costs | regret | No clear effect |
| Use PBGI on Levy | Bayesian optimization · Levy d=16 uniform costs | regret | Helped |
| Use PBGI-D on Rosenbrock instead of PBGI or (B)MSEI | Bayesian optimization · Rosenbrock d=16 uniform costs | regret | Helped |
| Use PBGI on Pest Control and Lunar Lander | Bayesian optimization · Pest Control and Lunar Lander | regret | Helped |
| Use PBGI on Robot Pushing | Bayesian optimization · Robot Pushing | regret | Hurt |
| Use PBGI-D rather than PBGI under uniform costs | Bayesian optimization · Rosenbrock d=16 | regret | Helped |
Surprising findings
- EIPC chooses the same points regardless of the constant cost level, so it is insensitive to overall cost scale.
- For d=32 uniform-cost, all deterministic methods perform near-identically and none outperforms random search.
Limitations
- PBGI underperforms when baselines are stronger, e.g., Robot Pushing where LogEI is best.
- Performance depends on lambda hyperparameter; PBGI sensitive to lambda choice while PBGI-D is more robust but less performant on some problems.
- Theoretical optimality holds only for the discrete independent Pandora's Box setting; extension to GP correlations is heuristic.
Experimental setup
Datasets: Ackley Levy Rosenbrock Pest Control Lunar Lander Robot Pushing
Benchmarks: Bayesian regret (GP prior samples, d=8,16,32) Ackley Levy Rosenbrock Pest Control Lunar Lander Robot Pushing
Metrics: simple regret median regret curves with quartiles
Baselines: LogEIPC LogEICC MFMES BMSEI LogEI Thompson sampling UCB MES knowledge gradient MSEI
Builds on: Pandora's Box problem (Weitzman 1979) expected improvement LogEI multi-step expected improvement Gaussian processes
Closest papers by meaning
- BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability (NeurIPS 2026 · similarity 0.89)
- A General Framework for User-Guided Bayesian Optimization (ICLR 2024 · similarity 0.89)
- A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization (ICML 2025 · similarity 0.88)
- FunBO: Discovering Acquisition Functions for Bayesian Optimization with FunSearch (ICML 2025 · similarity 0.87)
- Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs (AAAI 2025 · similarity 0.87)
- Stopping Bayesian Optimization with Probabilistic Regret Bounds (NeurIPS 2024 · similarity 0.86)
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.