引言

在常规的优化问题中，目标函数和约束条件通常有着清晰的解析形式。针对不同类型的目标函数和约束条件，优化领域已经设计和开发出了大量高效的算法，比如线性规划、二次规划和半定规划等^[1]。但是传统的优化方法也具有局限性。现实中存在大量的黑箱优化问题，它们所要优化的系统往往非常复杂。在这种情况下，如果使用简单的数学模型来刻画，该模型很可能没办法真实反映系统内部的真实动态，据此分析出的结果现实指导意义有限。但如果对其建立具有高保真度的数学模型，所需的理论分析又会过于复杂，求解难度高，甚至会出现找不到最优解的情况。解决这类问题的一个潜在途径是仿真优化。仿真优化首先利用计算机构建现实复杂随机系统的数字仿真模型，然后设计仿真优化算法指导仿真实验，最后通过大量实验得出随机仿真结果进而为现实中日益复杂化和精细化的管理决策提供重要支持。

排序择优问题是仿真优化领域中的一个基础性研究问题。该问题考虑如何设计统计算法在$ k $个均值未知的统计分布中进行采样，并基于观测结果将均值最大的分布给挑选出来^[2~3]。在这里，统计分布代表着，人们进行决策过程中面临有限个备选方案时，对每个方案所建立的仿真模型；对一个分布进行采样代表着，运行某一方案的仿真模型时，所观测到的随机表现结果；而均值最大的分布代表着，平均表现最好的方案。该问题在20世纪50年代被提出^[4]，到目前为止不仅在仿真优化领域，在统计以及机器学习领域人们都对该问题已进行了广泛的研究。针对此问题设计出的算法被广泛用于生产^[5]、医疗^[6~7]、金融风险^[8]、交通运输^[9]等领域的最优决策过程中。

对于排序择优问题，由于采样过程中每个观测值都带有噪声，给定采样总预算有穷的情况下，没有算法能保证能以概率1选择到真实均值最大的分布。所以在进行算法设计的过程中，一般会对原有目标进行弱化。一类算法通常不对采样预算作严格限制，但需要算法在停止时，能以一定概率保证挑选出真实均值最大的分布，这类算法被称为固定精度算法；另外一类算法则关注当采样总预算给定的情况下，如何分配样本到不同分布，从而使得算法能以尽可能大的概率挑选出真实均值最大的分布，这类算法被称为固定预算算法。前一类算法更强调选择结果的质量，本质上在进行“可靠”（Reliable）选择，而后一类算法更强调样本的有效分配，本质上在进行“尽力而为”（Best Effort）选择。本文将只考虑固定精度算法的设计。

在现有固定精度算法的研究中，人们通常假设$ k $个统计分布为正态分布，进而基于正态分布随机数的相关性质进行算法设计。但在现实中，应用仿真模型进行方案选择时，其输出的随机表现结果通常不满足正态分布。例如，在进行生产线设计时，如果目标是挑选预期成品率最高的设计方案，每次运行仿真模型所得的输出将会是一个在$\left[ {0,1} \right] $区间内取值的随机变量。此时如果采用一个假设输出是正态分布随机数的排序择优算法来指导仿真实验采样，其所能提供的概率保证可能会失效，无法确保选择结果“可靠”。因此，本文考虑将现有进行算法设计时所用到的假设拓展到更为一般的情况。具体来说，本文假设进行采样的k个分布为有界域分布，进而开展算法设计。值得一提的是，虽然在机器学习Best Arm Identification问题的研究中已有类似的算法设计^[10~11]，但本文将在数值实验部分验证所提出的算法效率是高于现有算法的。

一、  模型假设

考虑存在$ k $个有界域分布，标记为分布$ \mathrm{1,2},\cdots ,k $，且令$ \mathcal{K}=\left\{\mathrm{1,2},\cdots ,k\right\} $。假设这$ k $个分布的真实均值未知，分别用$\; {\mu }_{1},{\mu }_{2},\cdots ,{\mu }_{k} $表示。不失一般性假设这k个分布的真实均值以升序排列，即$\; {\mu }_{1} < {\mu }_{2} < \cdots < {\mu }_{k} $。在这里分布$ k $的均值最大，为需要寻找的真实最优分布。对于有界域分布，其采样结果可通过标准化处理转化成0到1之间。因此可进一步假设这$ k $个分布的支撑集为集合$ \left[\mathrm{0,1}\right] $的子集。对任一分布$ i $（$ i\in \mathcal{K} $）进行采样，将会得到一系列独立同分布随机观测值，记为$\left\{{X}_{i,\ell}:\ell=\mathrm{1,2},\cdots \right\}$。对分布i进行前t次采样，所得的样本均值假设在不同分布中采样所得随机观测值相互独立。令$ \alpha $（$ 0 < \alpha < 1/k $）为用户运行算法时事先设置的允许犯错的概率定义分布$ I $（$ I\in \mathcal{K} $）为算法经过采样并基于样本信息最终所选择到的最优分布。值得注意的是，当求解排序择优问题时，如不对均值构成做出任何假设，最好分布和次好分布的真实均值可能无限接近。在这种情况下没有算法能始终保证在有穷的样本预算内以一定概率将最优分布挑选出来。为解决此问题，根据文献[12]，本文在进行算法设计时对选择最优分布$ k $这一目标进行了弱化。具体来说，本文设计的算法需用户定义一个无差别区间参数（Indifference Zone Parameter）$ \delta $（$ \delta > 0 $）。在此基础上，算法需保证在采样结束后，即使无法准确选择出真实最优的分布$ k $，也需要至少以概率$ 1-\alpha $选择一个均值与分布$ k $均值之差小于$ \delta $的较好分布，即$ \mathbf{P}\left({\mu }_{k}-{\mu }_{I}\le \delta \right)\ge 1-\alpha $。

二、  算法设计

本文借鉴排序择优领域的经典算法设计框架^[13~14]—— 顺序淘汰式框架，设计了一个固定精度算法，称RSBO（Ranking and Selection with Bounded Observations）算法。该算法是以迭代的方式进行选择，在每轮对所有还存留的分布进行一次采样，采样结束后对所有分布进行是否淘汰判定。判定方法是将每个存留分布$ i $与其他所有还存留的分布进行比较。当累积到足够多样本信息证明，存在至少一个分布的均值大于分布i，即可淘汰分布$ i $。当对所有存留分布进行完是否淘汰判定后，算法进入下一轮迭代并重复上述过程。算法的停止条件有两个：一个是只剩一个分布存留，并且将其选为最优分布；另一个是所有存留分布的采样数达到预先设定的上限，并将样本均值最大的选为最优。值得注意的是，RSBO算法每轮进行是否淘汰判定的目的是及时将均值明显较低的分布淘汰，以此节省算法在选择最优分布时所需样本量，从而提升算法效率。以下为RSBO算法的详细描述。

输入：设置允许犯错概率$ \alpha $（$ 0 < \alpha \le 1-1/k $）、无差别区间参数$ \delta $（$ \delta > 0 $）和调节参数 $ \lambda $（$ 0 < \lambda < \delta $）。

初始化：记$ \mathcal{J}=\left\{\mathrm{1,2},\cdots ,k\right\} $为还存留分布集合。对每一个分布$ i $（$ i\in \mathcal{J} $）采样一次并观测输出$ {X}_{i,1} $。计算，

设置t=1。

筛选：令$ {\mathcal{J}}^{\mathrm{o}\mathrm{l}\mathrm{d}}=\mathcal{J} $。计算

停止条件：

• 如果$ \left|\mathcal{J}\right|=1 $，停止并选择集合$ \mathcal{J} $还包含的分布为最优，即令$ I=\mathcal{J}\left[1\right] $。其中$ \left|\mathcal{J}\right| $代表集合$ \mathcal{J} $中包含的元素个数，$ \mathcal{J}\left[1\right] $代表集合$ \mathcal{J} $中的第一个元素。

• 否则如果$ t=N $，停止并选择集合$ \mathcal{I} $还包含的分布中样本均值最大的分布为最优，即令$I= \mathrm{arg}\underset{i\in \mathcal{J}}{\mathrm{max}}{\bar{X}}_{i}\left(t\right)$。

• 否则，对集合$ \mathcal{J} $中每一个分布多采样一次，设置$ t=t+1 $以及重新回到筛选。

在RSBO算法中参数$ \mathrm{\lambda } $是一个调节参数，用于控制每轮淘汰标准。RSBO算法在筛选步骤对每轮还存留分布进行是否淘汰判定，集合$ \mathcal{J} $记录每轮还存留的分布。算法的停止条件为：1.当$ \mathcal{J} $中只存在一个分布时，算法停止并选择$ \mathcal{J} $中唯一存留的分布为最优；2.当存留分布采样总次数达到预先设定的上限时，即每个存留分布已采$ N $个样本时，算法停止并选择集合$ \mathcal{J} $中样本均值最大的分布为最优。

三、  统计有效性证明

以下将对RSBO算法的统计有效性进行证明，验证RSBO算法选择出来的分布均值与真实最优分布均值之差小于$ \delta $的概率至少为$ 1-\alpha $，即$ {{\rm{P}}}\left({\mu }_{k}-{\mu }_{I}\le \delta \right)\ge 1-\alpha $。

引理1（Hoeffding’s Lemma^[15]）：令$ l{'} $、$ u{'} $为两个常数且满足$ -\infty < {l}{{'}} < {u}{{'}} < \infty $。令$ G $为一个随机变量，满足$ \rm{E}\left[G\right]=\mu {'} $以及$ G\in \left[{l}{{'}},u{'}\right] $几乎必然成立。那么，对于任一实数$ s $，不等式$ \rm{E}\left[{e}^{s\left(G-\mu {'}\right)}\right]\le {e}^{{s}^{2}{\left({u}{{'}}-{l}{{'}}\right)}^{2}/8} $恒成立。

首先令$ {G}_{1},{G}_{2},\cdots ,{G}_{t} $为一组均值为$\; \mu $（$ \;\mu < 0 $），支撑集为$ \left[l,u\right] $的独立同分布随机数。其中，$ l $、$ u $为两个常数且满足$ -\mathrm{\infty } < \mathrm{l} < \mathrm{u} < \mathrm{\infty } $。根据引理1（Hoeffding’s Lemma）可得，存在一个实数$ {\sigma }_{p}^{2} $（$ 0 < {\sigma }_{p}^{2}\le {\left(u-l\right)}^{2}/4 $）使得对于任一实数$ s $，不等式$ \rm{E}\left[{e}^{s\left({G}_{1}-\mu \right)}\right]\le {e}^{{s}^{2}{\sigma }_{p}^{2}/2} $恒成立。定义一个随机过程$\left\{{M}_{\mu }\left(t\right)={\displaystyle\sum }_{\ell =1}^{t}{G}_{\ell }:t=\mathrm{1,2},\cdots ,\right\}$。记$ {a}^{*} $、$ {b}^{*} $为两个常数且满足$ -\infty < {b}^{*} < 0 < {a}^{*} < \infty $。在对算法的统计有效性进行分析之前，首先对随机过程$ {M}_{\mu }\left(t\right) $首次击中$ {a}^{*} $概率（First Hitting Probability），即$\rm{P}({\mathrm{sup}}_{t\ge 0}{M}_{\mu }\left(t\right)\ge {a}^{*})$ ，进行分析。

令$\; \beta =-2\mu /{\sigma }_{p}^{2} $和$ A\left(t\right)={e}^{\beta {M}_{\mu }\left(t\right)} $。定义3个停时（Stopping Times）：

进一步定义一个随机过程$ A\left(t\right) $的停止过程（Stopped Process） $ \bar{A}\left(t\right) $：

其中，1(·)是指示函数。在此可证明如下引理。

引理2：随机过程$ A\left(t\right) $是一个超鞅（Supermartingale）并且停止过程 $ \bar{A}\left(t\right) $是一致有界（Uniformly Bounded）。

证明：首先证明${ \rm{E}}\left[\left|A\left(t\right)\right|\right] < \infty$。因为$ {M}_{\mu }\left(t\right)= {\displaystyle\sum }_{\ell =1}^{t}{G}_{\ell } $以及$\; \beta \mu =-{\sigma }_{p}^{2}\beta /2 $，有：

根据$ {\sigma }_{p}^{2} $定义有：

对于所有正整数$ {t}{{'}} $，满足$ 0\le {t}{{'}} < t $，有：

结合式（1）和式（2）结论，可得$ \mathrm{A}\left(t\right) $为一个超鞅。

对于停止过程 $ \bar{A}\left(t\right) $，由于 $ \bar{A}\left(t\right)\ge 0 $几乎必然成立，根据定义 $ \bar{A}\left(t\right)\le {{\rm{e}}}^{\beta {M}_{\mu }\left({\mathcal{N}}_{{a}^{*}}\right)}\le {{\rm{e}}}^{\beta \left({a}^{*}+u\right)} $几乎必然成立，因此 $ \bar{A}\left(t\right) $是一致有界。引理2得证。□

同时存在如下引理。

引理3（Doob’s Lemma^[16]）：如果以下任意一个条件满足：（1） $ \bar{A}\left(t\right) $是一致有界；（2）$ {\mathcal{N}}_{{a}^{*}{b}^{*}} $有界；（3）$ \rm{E}\left[{\mathcal{N}}_{{a}^{*}{b}^{*}}\right] < \infty $，以及存在一个常数H（$ H < \mathrm{\infty } $）使得：

那么对于超鞅$ A\left(t\right) $，有${\rm{E}}\left[A\left({\mathcal{N}}_{{{\rm{a}}}^{*}{{\rm{b}}}^{*}}\right)\right]\le {\rm{E}}\left[A\left(0\right)\right]$。

基于引理2与引理3可得：

因此，基于式（3）结论，可对概率${\rm{P}}({\mathrm{sup}}_{{\rm{t}}\ge 0}{M}_{\mu }\left({\rm{t}}\right)\ge {a}^{*})$进行分析，归纳为如下引理。

引理4：对于随机过程$ {M}_{\mu }\left(t\right) $，如果$ {a}^{*} > 0 $，有

证明：对随机过程$ {M}_{\mu }\left(t\right) $，有$ {\mathrm{lim}}_{t\to \infty }{M}_{\mu }\left(t\right)=-\infty $几乎必然成立。所以，$ {\mathcal{N}}_{{a}^{*}{b}^{*}}\le {\mathcal{N}}_{{b}^{*}} < \infty $几乎必然成立，进一步可得：

再有，由于$ {M}_{\mu }\left({\mathcal{N}}_{{a}^{*}}\right)\ge {a}^{*} $和$ {M}_{\mu }\left({\mathcal{N}}_{{b}^{*}}\right)\ge {b}^{*}+l $，根据式（3）有：

根据式（4）和式（5）结果可得：

定义事件$ {\mathcal{D}}_{{b}^{*}}=\left\{{\mathcal{N}}_{{a}^{*}{b}^{*}}={\mathcal{N}}_{{b}^{*}}\right\} $，当$ {b}_{1} < {b}_{2} < 0 $时，有$ {\mathcal{D}}_{{b}_{2}}\supset {\mathcal{D}}_{{b}_{1}} $。因此，

因为事件$ \left\{{\cap }_{{b}^{*} < 0}{\mathcal{D}}_{{b}^{*}}\right\} $等价于事件$\{{\mathrm{sup}}_{t\ge 0}{M}_{\mu }\left(t\right) < {a}^{*}\}$，得：

${\rm{P}}\left({\mathrm{sup}}_{{\rm{t}}\ge 0}{M}_{\mu }\left(t\right)\ge {a}^{*}\right)\le {{\rm{e}}}^{\frac{2\mu {{\rm{a}}}^{*}}{{\sigma }_{{\rm{p}}}^{2}}}$。

基于引理4结论，可证明RSBO算法统计有效性，归纳为如下定理。

定理1：如果对任一分布$ i $（$ i\in \mathcal{K} $）采样，所得随机观测值独立同分布，且与其他分布采样所得随机观测值相互独立，RSBO算法能以至少$ 1-\alpha $概率选到一个均值与真实最优分布均值之差小于$ \delta $的分布，即$\rm{P}\left({\mu }_{k}-{\mu }_{I}\le \delta \right)\ge 1-\alpha$。

证明：根据问题定义，有$ \;{\mu }_{1} < {\mu }_{2} < \cdots < {\mu }_{k} $。当$ \;{\mu }_{k}-{\mu }_{1}\le \delta $时，选择任一分布$ I\in \mathcal{K} $，$ \;{\mu }_{k}-{\mu }_{I}\le \delta $恒成立。因此以下在进行统计有效性分析时假设至少存在一个分布与分布$ k $真实均值之差大于$ \delta $，即$ \;{\mu }_{k}-{\mu }_{1} > \delta $。定义正整数$ {k}_{0} $，满足$ {k}_{0}\in \mathcal{K} $、$ {k}_{0}\ge 2 $、$ \;{\mu }_{k}-{\mu }_{{k}_{0}}\le \delta $和$ \;{\mu }_{k}-{\mu }_{{k}_{0}-1} > \delta $。根据RSBO算法描述可知，当事件$ \left\{{\mu }_{k}-{\mu }_{I} > \delta \right\} $发生可推出事件${\bigcup }_{j=1}^{{k}_{0}-1}${分布j淘汰分布k}与事件$ {\bigcup }_{i={k}_{0}}^{k-1} ${分布i在t<N时淘汰分布k}中至少有一个事件发生，因此有：

对一个分布$ j $（$ 1\le j\le {k}_{0}-1 $）满足$\; {\mu }_{j} < {\mu }_{k}-\delta $，定义事件${\varepsilon}_{1}=\{N({\bar{X}}_{j}\left(N\right)-{\bar{X}}_{k}\left(N\right))\ge 0\}，$和事件

则有${\varepsilon}_{1}\subset {\varepsilon}_{2}$。因此

根据引理1（Hoeffding’s Lemma），对随机变量$ {X}_{j,\ell }-{X}_{k,\ell }+\lambda $及任一实数$ s $有：

其中，式(7)中第一个等式成立是由于对分布$ j $与分布$ k $采样所得随机观测值相互独立，不等式成立是依据引理1以及$ {X}_{j,\ell } $和$ {X}_{k,\ell } $在$ \left[\mathrm{0,1}\right] $之间取值。因此，随机变量$ {X}_{j,\ell }-{X}_{k,\ell }+\lambda $均值为$ {\mu }_{j}-{\mu }_{k}+\lambda < 0 $及$ {\sigma }_{p}^{2}=1/2 $，结合引理4，式（7）可进一步写为：

类似地，对于分布$ i $（$ {k}_{0}\le i\le k-1 $）满足${\mu }_{i}\ge {\mu }_{k}-\delta$，则有：

结合式（7）式（8）以及式（10）结论有：

$\rm{P}\left({\mu }_{k}-{\mu }_{I}\le \delta \right)\ge 1-\alpha$ 。

四、  数值实验

将通过数值实验对RSBO算法与现有的算法——Even-Dar等^[10]提出的SE（Succissive Elimination）算法以及ME（Median Elimination）算法和Jamieson等^[11]提出的lil’UCB算法，进行比较。数值实验部分考虑两个算例，一个是所有分布满足伯努利分布且均值满足SC（Slippage Configuration）构成，即$\;{\mu }_{1}={\mu }_{2}=\cdots ={\mu }_{k-1}= {\mu }_{k}-0.1=0.5$，另一个是所有分布满足伯努利分布且均值满足MIM（Monotone Increasing of Means）构成，即$ \;{\mu }_{i}=0.6-0.3{\left[\left(k-i\right)/k\right]}^{0.3} $，其中$ i=\mathrm{1,2},\cdots ,k $。值得注意的是，上述两种算例可以分别测试算法在求解较为集中和分散的均值构成时的表现。在这两个算例中，考虑了带有不同分布数目的问题，即在每个算例中令$ k $分别等于10、50、100、500、1000。当利用这四个算法求解不同算例中的不同问题时，无差别区间参数$ \delta $始终设为0.1，允许犯错的概率$ \alpha $始终设为0.05。对RSBO算法，调节参数$ \lambda $设定为0.05；对SE及ME算法，无其他额外参数需要设置；对lil’UCB算法，根据作者推荐，对调节参数ϵ，$ \beta $及$ \lambda $分别赋值0.01、1及9。在进行实验过程中，对每个问题，令每个算法重复求解一百次，并基于一百次结果估计每个算法在求解该问题时所需要的平均样本数，以及选择到的分布与真实最优分布均值之差小于$\delta $的概率。实验结果分别展示在表1及图1中。

表  1  RSBO、SE、ME、lil’UCB算法$ \mathrm{P}\left({\mu }_{k}-{\mu }_{I}\le \delta \right) $比较

算法	均值构成：SC						均值构成：MIM
	k=10	k=50	k=100	k=500	k=1000		k=10	k=50	k=100	k=500	k=1000
RSBO	1.00	1.00	1.00	1.00	1.00		1.00	1.00	1.00	1.00	1.00
SE	1.00	1.00	1.00	1.00	1.00		1.00	1.00	1.00	1.00	1.00
ME	1.00	1.00	1.00	1.00	1.00		1.00	1.00	1.00	1.00	1.00
lil’UCB	1.00	1.00	1.00	1.00	1.00		1.00	1.00	1.00	1.00	1.00

下载: 导出CSV 

| 显示表格

图  1  RSBO、SE、ME、lil’UCB算法样本量比较

下载: 全尺寸图片 幻灯片

由表1可得，对于四个算法，在求解以上所有问题时，始终能选择到一个均值与最优分布均值差距小于0.1的较好分布，说明这四个算法均能在求解不同问题时保证选择到分布的质量。由图1可得，当能确保选择结果质量的前提下，RSBO算法在进行选择过程中所需要的样本量最小，并远远小于其他三个算法，这说明在实际的使用过程中，RSBO算法的效率更高。值得注意的是，在求解输出为有界分布随机数的排序择优算法时，算法所需样本量通常是受分布的均值构成影响，而不同类型分布对算法表现影响相对较少^[10~11]。因此本数值实验部分，仅考虑了基于伯努利分布测试不同算法的表现。

五、  结束语

排序择优问题是仿真优化领域的一个基础性理论问题。现有文献在设计算法求解此问题时，通常假设对不同分布进行采样时，输出为正态分布随机数，进而基于正态分布随机数相关性质进行算法设计。然而，在现实中，该假设通常不成立，一旦假设不成立，现有算法的统计有效性将会大受影响。本文针对输出为有界域随机数的排序择优问题进行了算法设计，设计出一类顺序淘汰式的固定精度算法，称RSBO算法。通过数值实验验证，RSBO算法的实际表现远远优于现存的SE、ME和lil’UCB算法。