The Gittins Index: A Design Principle for Decision-Making Under Uncertainty
Making decisions under uncertainty is central to much of what we as humans do throughout our personal and professional lives. This includes everyday business decisions, for instance, where to invest limited resources, without exact knowledge of eventual outcomes. In many such situations, it can be reasonable to build a stochastic model which describes what might happen, and update that model to learn from observed data using Bayes’ Rule. Given the ubiquity of scenarios such a setup could in principle handle, it is of fundamental scientific importance to ask: are there broad theoretical frameworks which describe how an abstract agent should make decisions under a stochastic model?
A surprising feature of the above question is that it has a clean theoretical answer in greater generality than one might expect. Specifically, if the agent is choosing between several abstract actions, each of which is described by an arbitrarily-rich stochastic model – but where different models do not affect each other in a precise sense – then one can characterize the optimal decisions by way of a Gittins Index Theorem. This result says, roughly, that one should imagine an equivalent deterministic result for each stochastic action, rank all options, and pick the best one.
In this talk, we study Gittins indices in settings beyond those covered by classical theory – where, in general, the key optimality claim is not true. Despite this, we show that the key definitions behind Gittins Index can continue to make sense, and yield state-of-the-art performance in practice, showcasing examples from the domain of Bayesian optimization.
The implication of these results is that Gittins indices can reasonably be viewed as a general design principle for making decisions under uncertainty, rather than a narrow theoretical tool for analyzing optimality in a very specific set of problems. We discuss current progress towards making this vision real, in the form of developing numerical methods for reliably working with Gittins indices in advanced setups.
Bio: Alexander Terenin is an assistant research professor with the Center for Data Science for Enterprise and Society and the School of Operations Research and Information Engineering at Cornell. Prior to receiving his Ph.D. from Imperial College London in 2022, he earned B.S. and B.A. degrees from the University of California, Santa Barbara and an M.S. from the University of California, Santa Cruz.
His current research focuses on non-discrete decision-making under uncertainty.