Department of Industrial Engineering & Decision Analytics - The Gittins-Index Design Principle for Cost-aware Bayesian Decision-Making under Uncertainty

Selecting high-performing designs through costly evaluations is a crucial problem in automated machine learning and adaptive experimentation, with applications including hyperparameter tuning, scientific discovery, as well as the optimization of LLM systems and AI agents. In these settings, decision makers adaptively gather information while balancing potential performance improvements against cumulative evaluation costs under uncertainty.

In this talk, I will present my work on cost-aware Bayesian decision-making based on the Gittins index. The first part of the talk connects cost-aware Bayesian optimization to the Pandora’s Box problem from economics, where the Gittins index policy is Bayesian-optimal. This perspective leads to a novel and principled policy class for adaptive acquisition and stopping, supported by theoretical guarantees and validated through competitive empirical performance on black-box optimization tasks.

In the second part of the talk, I will discuss a broader class of bandit-like Bayesian decision problems connected to Bayesian bandits and Markov chain selection problems, where Gittins index policies are also known to be Bayesian-optimal. In these settings, information about the quality of each option is revealed gradually over multiple stages through costly evaluations. We develop computationally efficient Gittins index policies for adaptively allocating evaluations across options with varying evaluation costs, with applications including efficient LLM evaluation.

Together, these works illustrate how the Gittins index serves as a unifying design principle for cost-aware Bayesian decision-making under uncertainty.