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

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

• 批准号: 2149617
• 负责人: Christopher Quinn
• 金额: $ 25万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-03-01 至 2025-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2149617&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.

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

项目成果

Size-Constrained k-Submodular Maximization in Near-Linear Time

近线性时间内尺寸约束的 k 子模最大化

• 发表时间: 2023
• 期刊: Uncertainty in Artificial Intelligence
• 作者: Nie, Guanyu;Zhu, Yanhui;Nadew, Yiddiya Y.;Basu, Samik;Pavan, A.;Quinn, Christopher John}
• 通讯作者: Quinn, Christopher John}

Fractional Budget Allocation for Influence Maximization

• DOI: 10.1109/cdc49753.2023.10384250
• 发表时间: 2023-12
• 期刊: 2023 62nd IEEE Conference on Decision and Control (CDC)
• 作者: A. Umrawal;Vaneet Aggarwal;Christopher J. Quinn

Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback

全老虎机反馈下非单调随机子模最大化的随机贪婪学习

• 发表时间: 2023
• 期刊: Proceedings of the International Workshop on Artificial Intelligence and Statistics
• 作者: Fourati, Fares;Aggarwal, Vaneet;Quinn, Christopher John;Alouini, Mohamed-Slim
• 通讯作者: Alouini, Mohamed-Slim

An explore-then-commit algorithm for submodular maximization under full-bandit feedback

• 发表时间: 2022
• 作者: G. Nie;Mridul Agarwal;A. Umrawal;V. Aggarwal;Christopher J. Quinn

A Community-Aware Framework for Social Influence Maximization

• DOI: 10.1109/tetci.2023.3251362
• 发表时间: 2022-07
• 期刊: IEEE Transactions on Emerging Topics in Computational Intelligence
• 影响因子: 5.3
• 作者: A. Umrawal;Christopher J. Quinn;V. Aggarwal