Information theory for ranking and selection
Information theory for ranking and selection
复制标题
DOI：
10.1002/nav.21903
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Saeid Delshad;A. Khademi
中科院分区：
文献类型：
--
作者：
Saeid Delshad;A. Khademi
我们研究经典的排名和选择问题，其最终目标是根据正确选择的概率或预期机会成本找到未知的最佳替代方案。然而，本文采用替代抽样方法来实现这一目标，其中抽样决策的目标是最大化有关未知最佳替代方案的信息，或者等效地最小化其香农熵。这种自适应学习是通过贝叶斯随机动态规划问题来表述的，通过该问题提出了学习问题的几个属性，包括信息寻求环境中最优值函数的单调性。由于随机动态程序的状态空间在高斯设置中是无界的，因此使用一步前瞻方法来制定策略。所提出的策略旨在最大化未知最佳替代方案的一步信息增益，因此称为信息梯度（IG）。还证明了IG策略是一致的，即当抽样预算增长到无穷大时，IG策略几乎肯定会找到真正的最佳替代方案。后来，引入了对所提出的策略的计算有效估计，称为近似信息梯度（AIG），并在数值实验中根据最近的基准以及一些敏感性分析来测试其性能。结果表明，AIG 的性能与文献中的其他算法相比具有竞争力。
We study the classical ranking and selection problem, where the ultimate goal is to find the unknown best alternative in terms of the probability of correct selection or expected opportunity cost. However, this paper adopts an alternative sampling approach to achieve this goal, where sampling decisions are made with the objective of maximizing information about the unknown best alternative, or equivalently, minimizing its Shannon entropy. This adaptive learning is formulated via a Bayesian stochastic dynamic programming problem, by which several properties of the learning problem are presented, including the monotonicity of the optimal value function in an information‐seeking setting. Since the state space of the stochastic dynamic program is unbounded in the Gaussian setting, a one‐step look‐ahead approach is used to develop a policy. The proposed policy seeks to maximize the one‐step information gain about the unknown best alternative, and therefore, it is called information gradient (IG). It is also proved that the IG policy is consistent, that is, as the sampling budget grows to infinity, the IG policy finds the true best alternative almost surely. Later, a computationally efficient estimate of the proposed policy, called approximated information gradient (AIG), is introduced and in the numerical experiments its performance is tested against recent benchmarks alongside several sensitivity analyses. Results show that AIG performs competitively against other algorithms from the literature.