# Trajectory-Aware Best-Arm Identification for Local Search Allocation in Bayesian Optimization and Beyond

arXiv: https://arxiv.org/abs/2605.31050 · HTML: https://mlsanity.com/paper/2605.31050/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 43 references that are in the map.
- First posted on arXiv 29 May 2026.

## Builds on (most cited first, 16 of 16)

- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [pymoo: Multi-objective Optimization in Python](https://mlsanity.com/paper/2002.04504/) (2020)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Efficient Automatic CASH via Rising Bandits](https://mlsanity.com/paper/2012.04371/) (2020)
- [Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces](https://mlsanity.com/paper/2307.00618/) (2023)
- [Approximation Theory Based Methods for RKHS Bandits](https://mlsanity.com/paper/2010.12167/) (2020)
- [Best Arm Identification for Stochastic Rising Bandits](https://mlsanity.com/paper/2302.07510/) (2023)
- [Regional Expected Improvement for Efficient Trust Region Selection in High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2412.11456/) (2024)
- [BOIDS: High-dimensional Bayesian Optimization via Incumbent-guided Direction Lines and Subspace Embeddings](https://mlsanity.com/paper/2412.12918/) (2024)

## Abstract (arXiv)

Bayesian optimization (BO) is effective for expensive black-box optimization, but its performance often degrades on multimodal or high-dimensional problems. A promising remedy is to run multiple local search processes, such as trust region--based BO, and allocate evaluations to those with high potential. However, current best values do not always reflect the final performance of each process. We propose a trajectory-aware best-arm identification (BAI) framework that uses optimization history to guide this allocation. The proposed method extrapolates improvement trajectories, estimates final performance, and progressively eliminates low-potential candidates. For trust region--based BO, we theoretically show that the proposed BAI-guided allocation accelerates convergence to the global optimum under mild assumptions. Experiments on synthetic and real-world benchmarks demonstrate that our method improves BO on multimodal problems. We also show that the same mechanism can enhance other local or population-based optimizers, suggesting its potential as a general extension strategy for multimodal black-box optimization.