CRII: CIF: Sequential Decision-Making Algorithms for Efficient Subset Selection in Multi-Armed Bandits and Optimization of Black-Box Functions

与固定决策算法不同，顺序决策(SDM)算法通常在解决问题所需的样本数量方面更有效。获取额外的样本可能既昂贵又耗时。因此，SDM算法已经被广泛地应用于从推荐系统和自动药物发现到工程设计模型中的参数调整的广泛应用。该项目将开发新的算法，以增强SDM的适用性，提高其效率。算法的性能将得到保证，并将在真实世界的数据实验中进行测试。项目成果可导致电子商务和药物设计等工业部门更多地使用SDM。该项目将为不同的学生群体提供研究机会，所获得的知识将被纳入大学的研究生课程，并将扩大调查人员开展的K-12外联活动。该项目在两个问题框架下组织：子集选择和黑箱优化。在子集选择的第一个问题中，目标是从众多备选方案中选择一个较好的子集。这一目标被描述为多臂土匪模型中的子集选择问题。该项目将开发SDM算法，利用连续ARM均值之间的差距获得良好的子集。这消除了指定定义好的子集的参数的需要。SDM算法将利用线性多臂土匪模型中的ARM特征，理论分析将得到所提出算法的样本复杂性界。在第二个黑盒优化问题中，ARM特征是不可用的，通常使用基于划分的优化方法。该项目将开发SDM算法，使分区方案适应正在优化的黑盒函数。将确保收敛到最优值，并将在基准模拟上测量它们的实际性能。该项目的结果将在论文中传达，开发的代码将公开可用。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Unlike fixed decision-making algorithms, sequential decision-making (SDM) algorithms are often more efficient in the number of samples needed to solve a problem. Obtaining additional samples can be expensive and time-consuming. Consequently, SDM algorithms have been used in a wide range of applications ranging from recommender systems and automated drug discovery to the tuning of parameters in engineering design models. This project will develop new algorithms that enhance the applicability of SDM and improve its efficiency. Performance guarantees for the algorithms will be obtained and they will be tested in real-world data experiments. The project outcomes can lead to increased use of SDM in industry sectors such as e-commerce and drug design. The project will provide research opportunities for a diverse group of students and the knowledge gained will be integrated into the university’s graduate curriculum and will broaden the K-12 outreach activities undertaken by the investigator.The project is organized under two problem frameworks: subset selection and black-box optimization. In the first problem of subset selection, the objective is to select a good subset among many alternatives. This objective is formulated as a subset selection problem in multi-armed bandit models. The project will develop SDM algorithms that obtain a good subset using the gaps between consecutive arm means. This removes the need to specify a parameter that defines the good subset. The SDM algorithms will exploit arm features in linear multi-armed bandit models and the theoretical analysis will obtain sample complexity bounds for the proposed algorithms. In the second problem of black-box optimization, such arm features are not available, and partition-based optimization methods are often used. This project will develop SDM algorithms that adapt the partitioning scheme to the black-box function being optimized. Convergence to the optimal value will be ensured and their practical performance on benchmark simulations will be measured. The outcomes of the project will be communicated in papers and the developed code will be made publicly available.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.