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

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

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.