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

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

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.