# Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 48 references that are in the map.
- First posted on arXiv 28 Jun 2024.

## Builds on (most cited first, 20 of 20)

- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning](https://mlsanity.com/paper/1903.04703/) (2019)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Bayesian Optimization for Materials Design with Mixed Quantitative and Qualitative Variables](https://mlsanity.com/paper/1910.01688/) (2019)
- [A Study of Bayesian Neural Network Surrogates for Bayesian Optimization](https://mlsanity.com/paper/2305.20028/) (2023)
- [Cost-aware Bayesian Optimization](https://mlsanity.com/paper/2003.10870/) (2020)
- [Efficient Nonmyopic Bayesian Optimization via One-Shot Multi-Step Trees](https://mlsanity.com/paper/2006.15779/) (2020)
- [Why Non-myopic Bayesian Optimization is Promising and How Far Should We Look-ahead? A Study via Rollout](https://mlsanity.com/paper/1911.01004/) (2019)
- [A Nonmyopic Approach to Cost-Constrained Bayesian Optimization](https://mlsanity.com/paper/2106.06079/) (2021)
- [Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs](https://mlsanity.com/paper/2111.06537/) (2021)
- [The Price of Information in Combinatorial Optimization](https://mlsanity.com/paper/1711.00405/) (2017)
- [Descending Price Optimally Coordinates Search](https://mlsanity.com/paper/1603.07682/) (2016)
- [The Markovian Price of Information](https://mlsanity.com/paper/1902.07856/) (2019)
- [Bayesian Optimization Over Iterative Learners with Structured Responses: A Budget-aware Planning Approach](https://mlsanity.com/paper/2206.12708/) (2022)
- [Bayesian Optimization with Adaptive Kernels for Robot Control](https://mlsanity.com/paper/2402.07021/) (2024)
- [Gaussian Processes and Statistical Decision-making in Non-Euclidean Spaces](https://mlsanity.com/paper/2202.10613/) (2022)

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

- [Optimal Stopping vs Best-of-N for Inference Time Optimization](https://mlsanity.com/paper/2510.01394/) (2025)
- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Cost-aware Stopping for Bayesian Optimization](https://mlsanity.com/paper/2507.12453/) (2025)
- [Re-FORC: Adaptive Reward Prediction for Efficient Chain-of-Thought Reasoning](https://mlsanity.com/paper/2511.02130/) (2025)
- [Cost-Sensitive Freeze-thaw Bayesian Optimization for Efficient Hyperparameter Tuning](https://mlsanity.com/paper/2510.21379/) (2025)
- [Constrained Bayesian Experimental Design via Online Planning](https://mlsanity.com/paper/2605.26990/) (2026)
- [Pandora's AI Model Routing Box: Efficient Allocation with Costly Value Estimation](https://mlsanity.com/paper/2608.20316/) (2026)
- [A Bayesian Approach for Task-Specific Next-Best-View Selection with Uncertain Geometry](https://mlsanity.com/paper/2605.05095/) (2026)
- [The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costs](https://mlsanity.com/paper/2410.14533/) (2024)
- [Bayesian Algorithms for Adversarial Online Learning: from Finite to Infinite Action Spaces](https://mlsanity.com/paper/2502.14790/) (2025)
- [In-Context Decision Making for Optimizing Complex AutoML Pipelines](https://mlsanity.com/paper/2508.13657/) (2025)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)
- [Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings](https://mlsanity.com/paper/2601.06505/) (2026)
- [Transferring Information Across Interventions in Causal Bayesian Optimization](https://mlsanity.com/paper/2606.01457/) (2026)
- [Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices](https://mlsanity.com/paper/2609.25645/) (2026)
- [NeuronSifter: An Agent-in-Twin for Prioritizing Central Nervous System Interventions with World Action Models](https://mlsanity.com/paper/2609.35445/) (2026)

## Abstract (arXiv)

Bayesian optimization is a technique for efficiently optimizing unknown functions in a black-box manner. To handle practical settings where gathering data requires use of finite resources, it is desirable to explicitly incorporate function evaluation costs into Bayesian optimization policies. To understand how to do so, we develop a previously-unexplored connection between cost-aware Bayesian optimization and the Pandora's Box problem, a decision problem from economics. The Pandora's Box problem admits a Bayesian-optimal solution based on an expression called the Gittins index, which can be reinterpreted as an acquisition function. We study the use of this acquisition function for cost-aware Bayesian optimization, and demonstrate empirically that it performs well, particularly in medium-high dimensions. We further show that this performance carries over to classical Bayesian optimization without explicit evaluation costs. Our work constitutes a first step towards integrating techniques from Gittins index theory into Bayesian optimization.