Source-linked AI summary
Improving the Expected Improvement Algorithm
Chao Qin, Diego Klabjan, Daniel Russo
TL;DR
The paper studies how to allocate noisy measurements for confidently identifying the best arm when standard EI is too greedy. It introduces TTEI, a simple top-two modification of EI, and shows that it is asymptotically optimal for Gaussian best-arm identification while outperforming standard EI by an order of magnitude. The analysis focuses on uncorrelated priors, with correlated-prior extensions discussed as future scope.
Problem
Standard EI is widely used but too greedy, allocating too few samples to suboptimal arms in finite-grid best-arm identification.
Method
TTEI combines top-two sampling with a modified EI improvement measure and allocates samples using a tuning parameter β.
Results
TTEI achieves asymptotic optimality guarantees for Gaussian best-arm identification and offers an order of magnitude improvement over standard EI in experiments.
Takeaways & Limitations
A simple modification of EI can distribute measurement effort optimally among suboptimal arms while retaining easy implementation.
Takeaways & Limitations
The theoretical study focuses on uncorrelated priors, while correlated-prior suitability is presented as an extension rather than established result.
Abstract
from arXiv · showhide
The expected improvement (EI) algorithm is a popular strategy for information collection in optimization under uncertainty. The algorithm is widely known to be too greedy, but nevertheless enjoys wide use due to its simplicity and ability to handle uncertainty and noise in a coherent decision theoretic framework. To provide rigorous insight into EI, we study its properties in a simple setting of Bayesian optimization where the domain consists of a finite grid of points. This is the so-called best-arm identification problem, where the goal is to allocate measurement effort wisely to confidently identify the best arm using a small number of measurements. In this framework, one can show formally that EI is far from optimal. To overcome this shortcoming, we introduce a simple modification of the expected improvement algorithm. Surprisingly, this simple change results in an algorithm that is asymptotically optimal for Gaussian best-arm identification problems, and provably outperforms standard EI by an order of magnitude.
1 Introduction
Bayesian optimization uses noisy measurements to optimize unknown objectives, but greedy EI under-samples alternatives. The paper introduces TTEI, which achieves asymptotic optimality guarantees and order-of-magnitude empirical improvement over EI.
- EI is a widely used, simple Bayesian optimization heuristic that samples the point with greatest expected improvement over the current best sampled point.It handles uncertainty and noise within a decision-theoretic framework.
- EI is too greedy because it concentrates sampling near the estimated optimum and gathers too little information elsewhere.In best-arm identification, EI allocates a vanishing proportion of samples to suboptimal arms.
- TTEI combines top-two sampling with a modified EI improvement measure as a simple replacement for standard EI.
- TTEI achieves strong asymptotic optimality properties for Gaussian best-arm identification and is benchmarked in simulation experiments.
- TTEI’s sample proportions are characterized asymptotically, supporting optimal posterior-convergence rates and near-minimal expected samples under fixed-confidence stopping.
- A remaining limitation is TTEI’s dependence on a tuning parameter, although the theory indicates robustness and motivates adaptive variants.Removing the tuning parameter remains future work.
- TTEI can be implemented by modifying existing EI code and can offer an order of magnitude improvement in experiments.The experiments also compare TTEI with an oracle rule targeting asymptotically optimal proportions.
2 Problem Formulation
The paper formulates Gaussian best-arm identification with noisy rewards, unknown fixed arm means, Bayesian posterior updating, and unique best-arm assumptions. It evaluates optimality through posterior convergence and fixed-confidence sample efficiency.
- Problem Formulation: The objective is to identify the highest-mean arm confidently while using a small number of noisy measurements.
- Problem Formulation: Each arm produces normally distributed rewards with common known variance and unknown mean, with unique ordered means and arm 1 optimal.
- Problem Formulation: The true arm means are fixed but unknown, while Bayesian algorithms initialize priors and update posterior beliefs as observations accumulate.
- Problem Formulation: Posterior distributions remain normal under the specified prior because conjugate updating provides recursive posterior means and variances.
- Two notions of asymptotic optimality: The first optimality notion maximizes the exponential rate at which posterior probability assigned to nonoptimal arms vanishes.
- Fixed confidence: In the fixed-confidence setting, the algorithm may stop and return an optimal-arm estimate while minimizing expected observations subject to error probability at most δ.The analysis combines TTEI with an established stopping rule.
3 Sampling Rules
The paper introduces EI and explains its greedy weakness, then proposes TTEI, which modifies the improvement criterion and randomizes between two promising arms.
- Expected Improvement: EI samples the arm with the largest expected improvement over the current largest posterior mean.Its criterion increases with both posterior mean and posterior uncertainty.
- Top-Two Expected Improvement: EI can allocate nearly all future samples to one seemingly promising arm, leaving suboptimal arms with only O(log n) samples asymptotically.This can require extremely large sample sizes before the evidence is sufficient for confident identification.
- Top-Two Expected Improvement: TTEI identifies two promising arms and uses a β-weighted random choice, with β controlling the probability assigned to the top arm.The naive version selects the two arms with largest EI, but that variant is not optimal for any β.
- Top-Two Expected Improvement: TTEI replaces standard EI with an arm-pair criterion that integrates uncertainty over both arms when measuring expected improvement.For arms i and j, v_n,i,j is the expected magnitude of improvement arm i offers over arm j.
- Top-Two Expected Improvement: For β∈(0,1), TTEI allocates more effort to suboptimal arms than EI and asymptotically reserves β of samples for the best arm.The remaining 1−β fraction gathers evidence against suboptimal arms; β=1 recovers standard EI.
4 Convergence to Asymptotically Optimal Proportions
The paper characterizes TTEI’s limiting sampling proportions and shows that these proportions equalize evidence against suboptimal arms while determining convergence and fixed-confidence performance.
- Interpretation of the Optimal Proportions: The allocation w_β equalizes the standardized evidence against every suboptimal arm, making their false-best probabilities equal.This condition is expressed by requiring (μ_1−μ_i)/σ̃_i to be equal across suboptimal arms.
- Convergence of Sampling Proportions: TTEI’s sampling proportions converge to w_β, allocating β of samples to the true best arm and distributing 1−β optimally across the remaining arms.The theorem requires additional control of the expected time until empirical means and proportions become accurate for fixed-confidence results.
- Tuning Parameter and Convergence Rate: The optimal convergence exponent Γ* is obtained by maximizing Γ*_β over β∈(0,1), so the tuning parameter controls the rate achieved by TTEI.The exponent depends on the true arm means and variances and governs posterior convergence and fixed-confidence sample usage.
- Tuning Parameter and Convergence Rate: Using the default β=1/2 yields a convergence exponent at least half of the optimal one, while values near β* approach Γ*.The paper describes this as a surprising degree of robustness to the tuning parameter.
5 Implied Optimality Results
The paper derives posterior-convergence and fixed-confidence guarantees from asymptotically optimal sampling proportions, using Chernoff’s stopping rule for confident identification.
- Conditions for Optimality: The optimality results apply to any sampling rule whose proportions converge appropriately and whose expected convergence time is finite.This broadens the implications beyond TTEI itself.
- Posterior Convergence: No algorithm can converge faster than e^(−Γ*n), and TTEI with β* attains this optimal posterior-convergence rate.More generally, TTEI with parameter β achieves e^(−nΓ*_β) and is optimal among rules allocating β to the optimal arm.
- Posterior Convergence: With β=1/2, TTEI’s convergence exponent is at least half the optimal exponent.Thus the default tuning provides a factor-two approximation in the exponent guarantee.
- Chernoff’s Stopping Rule: Chernoff’s stopping rule uses a generalized likelihood-ratio statistic based on empirical means to stop when one arm is sufficiently distinguished from the others.The rule targets confidence at least 1−δ through an appropriate threshold.
- Fixed-Confidence Sample Complexity: When β=β*, TTEI combined with Chernoff’s stopping rule essentially matches the lower bound 1/Γ* on fixed-confidence sample complexity.With β=1/2, its sample complexity is at most twice the optimal value when the threshold parameter approaches one.
6 Numerical Experiments
The experiments evaluate TTEI against EI and several alternative or oracle sampling strategies in Gaussian five-arm instances. TTEI with β = 1/2 outperforms standard EI by an order of magnitude in measurements needed to reach high posterior confidence.
- The experiments use known variance σ2 = 1, five arms, and three mean configurations, with optimal β∗ values of 0.48, 0.45, and 0.35.
- TTEI with β = 1/2 outperforms standard EI by an order of magnitude in average measurements required to reach confidence level c = 0.95.Table 1 reports averages over 100 trials.
- A second experiment compares TTEI variants with TTTS, knowledge gradient, random sampling oracle, and tracking oracle.
- Table 2 evaluates average measurements required to reach the stricter confidence level c = 0.9999.
7 Conclusion and Extensions to Correlated Arms
The conclusion explains how TTEI’s modified information measure favors promising but under-explored arms and discusses extensions beyond the analyzed uncorrelated-prior setting. It also records the theoretical development and implementation trade-offs surrounding the algorithm.
- The paper thoroughly studies TTEI for uncorrelated priors but identifies complex correlated priors and large arm sets as important extension settings.
- TTEI’s correlation-aware information measure favors arms with high posterior mean, high variance, and low correlation with the estimated optimum.The third factor encourages exploration of promising regions far from the current estimated optimum.
- The appendix establishes that TTEI satisfies sufficient conditions for two notions of optimality, thereby proving the main theorems.
C Proof of Theorem 2
The proof of Theorem 2 analyzes TTEI’s asymptotic sampling proportions and posterior convergence. It combines Gaussian tail bounds, logarithmic asymptotics, and sufficient conditions on arm allocations.
- Gaussian tail inequalities and logarithmic equivalence control posterior probabilities that suboptimal arms exceed the best arm.
- The proof separates arms sampled infinitely often from those sampled only finitely often before bounding the posterior error probability.
- The analysis begins from improper priors and uses posterior parameters that coincide with empirical quantities after observations are collected.
- The proof uses asymptotic sampling proportions to characterize posterior convergence toward the optimal arm.
D Proof of Theorem 3
The proof of Theorem 3 establishes fixed-confidence guarantees by relating TTEI’s sampling and empirical means to a generalized likelihood-ratio stopping rule. Technical lemmas provide concentration and effort-allocation bounds needed for the argument.
- The generalized likelihood-ratio statistic aggregates pairwise evidence using empirical means and the numbers of samples allocated to the leading and competing arms.
- Under unique arm means and sufficiently large sample counts, empirical arm ordering matches the true ordering, supporting the stopping analysis.
- The stopping rule τδ ensures that the probability of stopping with an incorrect best-arm identification is at most δ.
- The proof controls deviations of empirical means, sampling counts, and top-two allocation fluctuations using Gaussian and martingale concentration results.
- Auxiliary lemmas show that exponential growth eventually dominates polynomial factors used in the proof’s stopping-time bounds.
F Results specific to TTEI
The analysis establishes that TTEI’s empirical means and proportions become accurate after a finite expected time, which is sufficient for both stated notions of asymptotic optimality.
- TTEI’s theoretical analysis targets the time required for all arms’ empirical means and proportions to become ε-accurate.
- The proof controls T_β^ε through polynomial bounds in W1 and W2 whose expectations are finite.
- E[T_β^ε] is finite, establishing TTEI’s sufficient conditions for both notions of asymptotic optimality.The threshold T_β^ε is the time after which every arm’s empirical mean and empirical proportion is ε-accurate.
F.1 Sufficient Exploration
The sufficient-exploration analysis shows that TTEI eventually samples every arm, using a sequence of arguments that eliminate persistently under-sampled arms.
- TTEI eventually samples every arm frequently enough to prevent persistent under-sampling.
- The proof defines under-sampled sets and shows that their nonemptiness forces additional sampling across successive periods.
- The sufficient-exploration argument relies on polynomial thresholds in W1 and W2, with σ, k, arm means, and β treated as constants.
F.2 Concentration of Empirical Means
The concentration analysis shows that TTEI’s empirical means and sampling proportions converge to their target values, supporting asymptotically optimal allocation.
- For every ε > 0, TTEI eventually makes each empirical mean ε-close to its true arm mean.
- The concentration proof uses finite polynomial thresholds in W1, W2, and 1/ε to obtain eventual accuracy.
- TTEI eventually identifies the empirically best arm as the true best arm under the unique-means assumption.
- The best arm’s empirical sampling proportion converges to the tuning parameter β.
- The analysis further establishes concentration of each arm’s empirical proportion around its optimal proportion.