# Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 16 references that are in the map.
- First posted on arXiv 20 Dec 2024.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Multi-Information Source Optimization](https://mlsanity.com/paper/1603.00389/) (2016)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Budget-Constrained Bandits over General Cost and Reward Distributions](https://mlsanity.com/paper/2003.00365/) (2020)
- [Multi-armed Bandits with Cost Subsidy](https://mlsanity.com/paper/2011.01488/) (2020)

## Abstract (arXiv)

Bayesian Optimization (BO) is a widely-used method for optimizing expensive-to-evaluate black-box functions. Traditional BO assumes that the learner has full control over all query variables without additional constraints. However, in many real-world scenarios, controlling certain query variables may incur costs. Therefore, the learner needs to balance the selection of informative subsets for targeted learning against leaving some variables to be randomly sampled to minimize costs. This problem is known as Bayesian Optimization with cost-varying variable subsets (BOCVS). While the goal of BOCVS is to identify the optimal solution with minimal cost, previous works have only guaranteed finding the optimal solution without considering the total costs incurred. Moreover, these works assume precise knowledge of the cost for each subset, which is often unrealistic. In this paper, we propose a novel algorithm for the extension of the BOCVS problem with random and unknown costs that separates the process into exploration and exploitation phases. The exploration phase will filter out low-quality variable subsets, while the exploitation phase will leverage high-quality ones. Furthermore, we theoretically demonstrate that our algorithm achieves a sub-linear rate in both quality regret and cost regret, addressing the objective of the BOCVS problem more effectively than previous analyses. Finally, we show that our proposed algorithm outperforms comparable baselines across a wide range of benchmarks.