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算法，利用连续臂均值之间的间隙获得良好的子集。这样就不需要指定一个参数来定义好的子集。SDM算法将利用线性多臂强盗模型中的臂特征，理论分析将获得所提出算法的样本复杂度界。在黑盒优化的第二个问题中，这种臂特征是不可用的，通常使用基于分区的优化方法。本项目将开发SDM算法，使分区方案适应正在优化的黑箱函数。将确保收敛到最优值，并在基准模拟中测量它们的实际性能。该项目的成果将在论文中进行交流，开发的代码将向公众提供。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.