Single-objective black box optimization (also known as zeroth-order
optimization) is the process of minimizing a scalar objective $f(x)$, given
evaluations at adaptively chosen inputs $x$. In this paper, we consider
multi-objective optimization, where $f(x)$ outputs a vector of possibly
competing objectives and the goal is to converge to the Pareto frontier.
Quantitatively, we wish to maximize the standard hypervolume indicator metric,
which measures the dominated hypervolume of the entire set of chosen inputs. In
this paper, we introduce a novel scalarization function, which we term the
hypervolume scalarization, and show that drawing random scalarizations from an
appropriately chosen distribution can be used to efficiently approximate the
hypervolume indicator metric. We utilize this connection to show that Bayesian
optimization with our scalarization via common acquisition functions, such as
Thompson Sampling or Upper Confidence Bound, provably converges to the whole
Pareto frontier by deriving tight hypervolume regret bounds on the order of
$\widetilde{O}(\sqrt{T})$. Furthermore, we highlight the general utility of our
scalarization framework by showing that any provably convergent
single-objective optimization process can be effortlessly converted to a
multi-objective optimization process with provable convergence guarantees.

本文提出了一种称为 hypervolume scalarization 的标量化函数，并显示出如何从适当选择的分布中绘制随机标量化以有效地近似 hypervolume indicator metric，进而用此联系说明 Bayesian optimization 具有证明收敛到整个 Pareto frontier 的保证收敛性，同时凸显了标量化框架的一般实用性。

随机超体积标量化技术的可证明多目标黑盒优化

Random Hypervolume Scalarizations for Provable Multi-Objective Black Box  Optimization

We consider black box optimization of an unknown function in the
nonparametric Gaussian process setting when the noise in the observed function
values can be heavy tailed. This is in contrast to existing literature that
typically assumes sub-Gaussian noise distributions for queries. Under the
assumption that the unknown function belongs to the Reproducing Kernel Hilbert
Space (RKHS) induced by a kernel, we first show that an adaptation of the
well-known GP-UCB algorithm with reward truncation enjoys sublinear
$\tilde{O}(T^{\frac{2 + \alpha}{2(1+\alpha)}})$ regret even with only the
$(1+\alpha)$-th moments, $\alpha \in (0,1]$, of the reward distribution being
bounded ($\tilde{O}$ hides logarithmic factors). However, for the common
squared exponential (SE) and Mat\'{e}rn kernels, this is seen to be
significantly larger than a fundamental $\Omega(T^{\frac{1}{1+\alpha}})$ lower
bound on regret. We resolve this gap by developing novel Bayesian optimization
algorithms, based on kernel approximation techniques, with regret bounds
matching the lower bound in order for the SE kernel. We numerically benchmark
the algorithms on environments based on both synthetic models and real-world
data sets.

本文通过对高斯过程黑盒优化中噪音模型的研究，提出了一种可用于重尾噪音的、基于核函数的 UCB 算法以及基于核函数近似的贝叶斯优化算法，解决了现有算法在重尾噪音下表现较差的问题，并在人造和真实数据集上验证了算法性能。

重尾利润下的贝叶斯优化

Bayesian Optimization under Heavy-tailed Payoffs

We explore the use of Evolution Strategies (ES), a class of black box
optimization algorithms, as an alternative to popular MDP-based RL techniques
such as Q-learning and Policy Gradients. Experiments on MuJoCo and Atari show
that ES is a viable solution strategy that scales extremely well with the
number of CPUs available: By using a novel communication strategy based on
common random numbers, our ES implementation only needs to communicate scalars,
making it possible to scale to over a thousand parallel workers. This allows us
to solve 3D humanoid walking in 10 minutes and obtain competitive results on
most Atari games after one hour of training. In addition, we highlight several
advantages of ES as a black box optimization technique: it is invariant to
action frequency and delayed rewards, tolerant of extremely long horizons, and
does not need temporal discounting or value function approximation.

使用黑盒优化算法 —— 进化策略，替代流行的基于 MDP 的 RL 技术，通过 MuJoCo 和 Atari 上的实验表明，ES 是一种可行的解决策略，随着可用 CPU 数量的增加而呈线性规模，同时 ES 具有不变性、容差性以及无需强化学习概念的优越性。