Optimistic methods have been applied with success to single-objective
optimization. Here, we attempt to bridge the gap between optimistic methods and
multi-objective optimization. In particular, this paper is concerned with
solving black-box multi-objective problems given a finite number of function
evaluations and proposes an optimistic approach, which we refer to as the
Multi-Objective Simultaneous Optimistic Optimization (MO-SOO). Popularized by
multi-armed bandits, MO-SOO follows the optimism in the face of uncertainty
principle to recognize Pareto optimal solutions, by combining several
multi-armed bandits in a hierarchical structure over the feasible decision
space of a multi-objective problem. Based on three assumptions about the
objective functions smoothness and hierarchical partitioning, the algorithm
finite-time and asymptotic convergence behaviors are analyzed. The finite-time
analysis establishes an upper bound on the Pareto-compliant unary additive
epsilon indicator characterized by the objectives smoothness as well as the
structure of the Pareto front with respect to its extrema. On the other hand,
the asymptotic analysis indicates the consistency property of MO-SOO. Moreover,
we validate the theoretical provable performance of the algorithm on a set of
synthetic problems. Finally, three-hundred bi-objective benchmark problems from
the literature are used to substantiate the performance of the optimistic
approach and compare it with three state-of-the-art stochastic algorithms,
namely MOEA/D, MO-CMA-ES, and SMS-EMOA in terms of two Pareto-compliant quality
indicators. Besides sound theoretical properties, MO-SOO shows a performance on
a par with the top performing stochastic algorithm, viz. SMS-EMOA.

本文介绍了一种基于多臂赌博机的乐观方法，称之为多目标同时乐观优化（MO-SOO）。该算法通过结合多个多臂赌博机在多目标问题的可行决策空间中建立分层结构，以识别帕累托最优解。通过描述该算法的有限时间和渐近行为，分别分析了算法的上界和一致性性质。在 300 个双目标基准问题中，与三个随机算法进行比较，MO-SOO 表现出与顶尖随机算法一致的性能，即 SMS-EMOA 算法。