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算法，该算法使用保守的ARM均值之间的差距获得良好的子集。这消除了指定定义良好子集的参数。 SDM算法将利用线性多臂匪徒模型中的ARM特征，理论分析将为所提出的算法获得样品复杂性界限。在黑盒优化的第二个问题中，此类ARM功能不可用，并且经常使用基于分区的优化方法。该项目将开发SDM算法，这些算法将分区方案调整到优化的黑框函数。将确保与最佳值的收敛性，并将测量其在基准模拟上的实际性能。该项目的结果将在论文中传达，并将公开提供开发的代码。该奖项反映了NSF的法定任务，并通过使用基金会的知识分子优点和更广泛的影响审查标准来评估被认为是宝贵的支持。