Short talk for AutoML 2025
The Gittins Index: A Design Principle for
Decision-making Under Uncertainty
Joint work with Ziv Scully
Decision-making Under Uncertainty
This work: motivated by cost-aware variants of problems like this
Pandora's Box
Decision problem with collection of boxes with unknown rewards:
- Rewards: $v(x_i) \~ p_i$ (where $p_i$ is known, different boxes independent)
- Cost to open: $c(x_i)$
- Goal: maximize $\displaystyle\E \max_{1 \leq t \leq T} v(x_t) - \E \smash{\sum_{t=1}^T} c(x_t)$
Solution:
(Notation: $\footnotesize\f{EI}_\psi(x;y) = \E \max(0,\psi(x) - y)$)
$\alpha^*(x) = g$ where $g$ solves $\f{EI}_f(x; g) = c(x)$
Gittins Index Theory
General theory: equivalent deterministic value for stochastic objects
We think this might help design acquisition function in complex settings
Thank you!
https://avt.im/· @avt_im
Thank you!
https://avt.im/· @avt_im
Z. Scully and A. Terenin. Gittins Index: A Design Principle for Decision-making Under Uncertainty. INFORMS Tutorials in Operations Research, 2025.
