Annealed Entropic Allocation: Smarter sequential budget allocation for near-tied challengers

Researchers Xin Fei and Juergen Branke have proposed Annealed Entropic Allocation (AEA), a novel framework for sequential budget allocation in ranking and selection problems. These problems arise in applications like A/B testing, simulation optimization, and clinical trials, where an experimenter must allocate a limited budget across multiple options (challengers) to identify the best one. Traditional methods often rely on a maximin large-deviation rate objective, which can be non-smooth and lead to hard switching between challengers when they are nearly tied. AEA replaces this with a weighted log-sum-exp surrogate that aggregates pairwise scores using soft-min weights, smoothing the optimization landscape and stabilizing allocation decisions.

The method further improves finite-budget performance by incorporating saddlepoint approximations—refined sub-exponential corrections derived from pairwise tail asymptotics. Since these corrections are sub-exponential and the smoothing parameter is annealed to zero, the surrogate objective converges uniformly to the original hard minimum while maintaining the same first-order large-deviation target. The authors prove that the soft-min weights concentrate on the active challengers and that the induced allocation map is continuous on the simplex interior. Numerical experiments on Gaussian and exponential instances demonstrate competitive performance, particularly when multiple challengers are nearly tied, where AEA outperforms classical approaches. This work offers a principled, theoretically grounded tool for practitioners facing budget-constrained selection problems.