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

CRII：CIF：多臂老虎机中高效子集选择和黑盒函数优化的顺序决策算法

• 批准号: 2246187
• 负责人: Ardhendu Tripathy
• 金额: $ 17.5万
• 依托单位: Missouri University of Science and Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-05-01 至 2025-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2246187&HistoricalAwards=false
• 关键词: CRII; CIF; Sequential; Decision; Making

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.

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