Parallel Bayesian Optimization Using Satisficing Thompson Sampling for
  Time-Sensitive Black-Box Optimization
Xiaobin Song Benben Jiang
Bayesian optimization (BO) is widely used for black-box optimization
problems, and have been shown to perform well in various real-world tasks.
However, most of the existing BO methods aim to learn the optimal solution,
which may become infeasible when the parameter space is extremely large or the
problem is time-sensitive. In these contexts, switching to a satisficing
solution that requires less information can result in better performance. In
this work, we focus on time-sensitive black-box optimization problems and
propose satisficing Thompson sampling-based parallel Bayesian optimization
(STS-PBO) approaches, including synchronous and asynchronous versions. We shift
the target from an optimal solution to a satisficing solution that is easier to
learn. The rate-distortion theory is introduced to construct a loss function
that balances the amount of information that needs to be learned with
sub-optimality, and the Blahut-Arimoto algorithm is adopted to compute the
target solution that reaches the minimum information rate under the distortion
limit at each step. Both discounted and undiscounted Bayesian cumulative regret
bounds are theoretically derived for the proposed STS-PBO approaches. The
effectiveness of the proposed methods is demonstrated on a fast-charging design
problem of Lithium-ion batteries. The results are accordant with theoretical
analyses, and show that our STS-PBO methods outperform both sequential
counterparts and parallel BO with traditional Thompson sampling in both
synchronous and asynchronous settings.