Feature-based offline algorithm selection has shown its effectiveness in a
wide range of optimization problems, including the black-box optimization
problem. An algorithm selection system selects the most promising optimizer
from an algorithm portfolio, which is a set of pre-defined optimizers. Thus,
algorithm selection requires a well-constructed algorithm portfolio consisting
of efficient optimizers complementary to each other. Although construction
methods for the fixed-target setting have been well studied, those for the
fixed-budget setting have received less attention. Here, the fixed-budget
setting is generally used for computationally expensive optimization, where a
budget of function evaluations is small. In this context, first, this paper
points out some undesirable properties of experimental setups in previous
studies. Then, this paper argues the importance of considering the number of
function evaluations used in the sampling phase when constructing algorithm
portfolios, whereas the previous studies ignored that. The results show that
algorithm portfolios constructed by our approach perform significantly better
than those by the previous approach.

离线算法选择，算法组合，固定预算设置，函数评估，优化问题。

在固定预算设置下构建算法选择中的算法组合对计算密集型黑箱优化问题的解决

On Constructing Algorithm Portfolios in Algorithm Selection for  Computationally Expensive Black-box Optimization in the Fixed-budget Setting

We study the problem of best-arm identification (BAI) in the fixed-budget
setting with heterogeneous reward variances. We propose two variance-adaptive
BAI algorithms for this setting: SHVar for known reward variances and SHAdaVar
for unknown reward variances. Our algorithms rely on non-uniform budget
allocations among the arms where the arms with higher reward variances are
pulled more often than those with lower variances. The main algorithmic novelty
is in the design of SHAdaVar, which allocates budget greedily based on
overestimating the unknown reward variances. We bound probabilities of
misidentifying the best arms in both SHVar and SHAdaVar. Our analyses rely on
novel lower bounds on the number of pulls of an arm that do not require
closed-form solutions to the budget allocation problem. Since one of our budget
allocation problems is analogous to the optimal experiment design with unknown
variances, we believe that our results are of a broad interest. Our experiments
validate our theory, and show that SHVar and SHAdaVar outperform algorithms
from prior works with analytical guarantees.

研究在异质奖励方差的固定预算设置下的最佳臂识别问题，提出两种方差自适应的算法：SHVar 和 SHAdaVar，分别用于已知奖励方差和未知奖励方差情况下，通过不均匀预算分配实现对高方差臂的偏好，本文还给出了误判最佳臂的概率界限。