You are here

Myopic Policies for Budgeted Optimization with Constrained Experiments

TitleMyopic Policies for Budgeted Optimization with Constrained Experiments
Publication TypeConference Paper
Year of Publication2010
AuthorsAzimi, J., X. Z. Fern, A. Fern, E. Burrows, F. Chaplen, Y. Fan, H. Liu, J. Jaio, and R. Schaller
Conference NameAAAI
PaginationAAAI Conference on Artificial Intelligence (AAAI-10)
Date Published07/2010
Conference LocationAtlanta, Georgia

Motivated by a real-world problem, we study a novel budgeted optimization problem where the goal is to optimize an unknown function f(x) given a budget. In our setting, it is not practical to request samples of f(x) at precise input values due to the formidable cost of precise experimental setup. Rather, we may request a constrained experiment, which is a subset r of the input space for which the experimenter returns x in r and f(x). Importantly, as the constraints become looser, the experimental cost decreases, but the uncertainty about the location x of the next observation increases. Our goal is to manage this trade-off by selecting a sequence of constrained experiments to best optimize f within the budget. We introduce cost-sensitive policies for selecting constrained experiments using both model-free and model-based approaches, inspired by policies for unconstrained settings. Experiments on synthetic functions and functions derived from real-world experimental data indicate that our policies outperform random selection, that the model-based policies are superior to model-free ones, and give insights into which policies are preferable overall.