Collaborative Research: CIF: Small: Sequential Decision Making Under Uncertainty With Submodular Rewards

合作研究：CIF：小：不确定性下的顺序决策与子模奖励

基本信息

批准号：
2149588
负责人：
Vaneet Aggarwal
金额：
$ 25万
依托单位：
Purdue University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-03-01 至 2025-02-28
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2149588&HistoricalAwards=false
关键词：
Collaborative Research CIF Small Sequential

项目摘要

Many companies, government agencies, and individuals make sequences of challenging decisions over time, for which they must choose from among many possible options, may have limited knowledge about the outcomes of their decisions, and will receive limited feedback. For example, search engines and content providers make decisions for what sets of websites, products, or media to recommend each time a user logs on to their system or submits a query, in some cases having limited knowledge of the users’ underlying preferences. If users' privacy is protected, then only users' past actions, such as which links or media were selected by earlier users, will be available as feedback to inform the search engine or content provider on what to recommend next. This project aims to develop provably good strategies that decision makers can use in such settings, aiding their decision making under uncertainty and with limited feedback. This project will also develop strategies for the more challenging setting where multiple decision makers must coordinate with each other on such problems, but have limited communication available to do so. Furthermore, this project will support undergraduate and graduate research training, as well as graduate-level course development, in machine learning and artificial intelligence, preparing students for careers in advanced technical fields.The goal of this project is to develop novel, provably good strategies for solving sequential decision problems (multi-armed bandit problems) when the actions available have a combinatorial structure (such as choosing subsets of products to recommend), the rewards have a diminishing returns property (submodularity), and there is no side-information available -- the only feedback comes from the reward itself. The proposed work builds on the rich literature of multi-armed bandits and of submodular optimization. The technical aims of the project are divided into two thrusts. The first thrust focuses on developing algorithms and identifying their regret bounds for combinatorial multi-armed bandit problems with submodular rewards and no additional feedback. The second thrust extends those strategies and regret analyses to a decentralized setting, where multiple agents coordinate to solve combinatorial multi-armed bandit problems, despite limited resources for communication.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.

随着时间的推移，许多公司、政府机构和个人会做出一系列具有挑战性的决策，他们必须从许多可能的选项中进行选择，他们对其决策结果的了解可能有限，并且收到的反馈也有限。内容提供商在用户每次登录其系统或提交查询时决定推荐哪些网站、产品或媒体，在某些情况下对用户的潜在偏好了解有限。那么只有用户过去的操作，例如选择了哪些链接或媒体早期用户提供的信息将作为反馈，告知搜索引擎或内容提供商接下来要推荐什么。该项目旨在开发决策者可以在此类环境中使用的可证明的良好策略，帮助他们在不确定性和反馈有限的情况下做出决策。该项目还将针对更具挑战性的环境制定策略，在这种情况下，多个决策者必须在此类问题上相互协调，但可用的沟通有限。此外，该项目还将支持本科生和研究生以及研究生的研究培训。机器学习和人工智能方面的水平课程开发，为学生做好准备该项目的目标是开发新颖的、可证明良好的策略来解决顺序决策问题（多臂老虎机问题），当可用的操作具有组合结构（例如选择要推荐的产品子集）时，奖励具有递减收益属性（子模块性），并且没有可用的辅助信息——唯一的反馈来自奖励本身。所提出的工作建立在多臂老虎机和子模块优化目标的丰富文献之上。该项目分为两个重点。第一个重点是开发算法并确定具有子模块奖励的组合多臂强盗问题的遗憾界限，第二个重点将这些策略和遗憾分析扩展到分散的环境中。尽管沟通资源有限，但多个代理协调解决组合多臂老虎机问题。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。