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

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

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.