AF: Small: Optimization Algorithms for Multi-Armed Bandit Problems

AF：小：多臂老虎机问题的优化算法

• 批准号: 1117216
• 负责人: Sudipto Guha
• 金额: $ 38万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117216&HistoricalAwards=false
• 关键词: AF; Small; Optimization; Algorithms; Multi

Computation in many emerging applications, such as online advertising and large scale social, media or sensor networks, is increasingly moving away from a simplistic view of computing a fixed function on a well defined input. Increasingly we are realizing that the input and the function are only the means to an end; and are inexact and imprecise at best. In many of these applications, the cost of realizing the input, in possibly distributed and dynamic/interactive environments, is a significant fraction of the cost of the computation itself. The emerging theme has been (i) to formulate models (very often probabilistic) of the input, (ii) precompute strategies that probe or realize few pieces of the input, and (iii) execute the strategies while making small adjustments as the data is incrementally made available. Moreover all these three stages are interleaved and the optimization is often repetitive. The overall process corresponds to repeatedly adapting to the short run behavior of the input which is reset often, starting from an initial and aggregate model of the long term behavior. Thus the task is to design and analyze algorithms that span and adapt to multiple scales of time.Similar problems which encode the tradeoffs between exploration and exploitation has classically been modeled by the Multi-Armed Bandit problem, where the arms correspond to the available choices. However, these emerging domains differ in several critical aspects. This proposal seeks to extend the optimization and analysis of Multi-Armed Bandit problems in a number of novel dimensions, specifically in terms of nonlinear and subadditive objective functions, noisy and error-prone feedbacks, lack of centrality and entangled feedbacks, implementation barriers of budgets or policies, and dynamic behavior. These extensions are connected, and progress on these problems would lead to a wealth of new results and more importantly, new techniques, in optimization as well as in bandit literature.In addition to the development of new algorithmic and analysis ideas, the proposal would train graduate students to develop simultaneous expertise in theoretical computer science, machine learning and statistics, as well as stochastic control. Moreover the crosscutting aspect of the research would be disseminated through tutorials, surveys and monographs.

在许多新兴应用中，如在线广告和大规模社交、媒体或传感器网络，计算正日益远离在定义明确的输入上计算固定函数的简单化观点。我们越来越意识到，输入和功能只是达到目的的手段；充其量也是不准确和不精确的。在许多这样的应用中，在可能的分布式和动态/交互环境中实现输入的成本是计算本身成本的很大一部分。新出现的主题是(I)制定投入的模型(往往是概率的)，(Ii)探索或实现少量投入的预先计算战略，以及(Iii)随着数据的逐步提供而执行战略，同时进行小的调整。而且，这三个阶段都是交错的，优化往往是重复的。整个过程对应于反复适应经常重置的输入的短期行为，从长期行为的初始和聚合模型开始。因此，任务是设计和分析跨越并适应多个时间尺度的算法。类似的问题编码了勘探和开发之间的权衡，经典地由多臂强盗问题建模，其中臂对应于可用选择。然而，这些新兴领域在几个关键方面有所不同。这一建议试图在一些新的维度上扩展对多臂强盗问题的优化和分析，特别是在非线性和次可加性目标函数、噪声和容易出错的反馈、缺乏中心性和纠缠反馈、预算或政策的实施障碍和动态行为方面。这些扩展是相互关联的，在这些问题上的进展将导致大量的新结果，更重要的是，在优化和盗贼文献方面的新技术。除了开发新的算法和分析思想外，该提案还将培养研究生在理论计算机科学、机器学习和统计学以及随机控制方面同时发展专业知识。此外，研究的交叉方面将通过教程、调查和专著加以传播。