CAREER: Non-asymptotic, Instance-optimal Closed-loop Learning

机器学习和人工智能可以识别和利用数据中的隐藏模式，以预测从内容推荐到个性化医疗等应用程序的未来结果。然而，在许多问题领域，收集数据很耗时(例如，细胞需要在实验室环境中培养)或昂贵(例如，需要特殊材料或专家意见)。理想情况下，为了减少得出结论所需的数据量，可以利用已经收集的数据以闭环方式指导未来测量的选择。虽然一些闭环数据收集策略的行为和益处在简单的环境中得到了很好的理解，但由于结果缺乏可预测性和准确性，这一系列策略在现实世界的科学实验室或医学试验中并不常见。该项目力求为理解闭环式学习战略作出基础性贡献，以期设计既有效又可靠的新数据收集战略。在实践中，这可能会导致在临床试验中需要更少的患者，或者将确定治愈疾病的药物的时间减半。调查人员还计划与高中生和机器学习爱好者进行接触，以提高他们对数据收集的认识水平--例如，即使是一个简单的调查，如果不仔细设计，如何导致侵犯隐私、人口统计不足和许多形式的偏见，所有这些都可能导致不准确的结论。对于许多对闭环系统学习感兴趣的问题，现有技术只关注极小最大最优，即最坏情况下问题实例的样本复杂性被最小化。这种方法导致的算法在“简单”或良性实例上明显逊色，这些实例可能在自然界中发生，但远不是对抗性的。相反，这个项目将研究在可能近似正确(PAC)的环境下交互学习和强化学习问题的实例最优样本复杂性的基本界限。将获得的洞察力将应用于算法的设计，这些算法自动适应所面临的特定问题实例的内在困难，无论它是良性的还是非良性的。所提出的方法的动机是观察到实例最优样本复杂性分解为一个渐近项和一个中等置信项，其中渐近项目前已经得到了很好的刻画，而中等置信项在所有实际目的中都支配着渐近项。由于后一项的性质仍然知之甚少，将与几乎实现它们的算法一起构造它的下界。这样的结果将导致算法大大降低总体实例最优样本的复杂性，并极大地改进倾向于迎合最坏情况的最先进算法。这些努力最初将集中在表格和线性函数近似设置中的结构化线性强盗和强化学习。虽然这些范例对实践具有广泛的适用性，但它们也具有足够的复杂性，允许将洞察力外推到更一般的闭环系统学习范例。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Machine Learning and Artificial Intelligence can recognize and exploit hidden patterns in data in order to predict future outcomes in applications ranging from content recommendation to personalized medicine. However, there are many problem areas where collecting the data is time-consuming (e.g., cells need to grow in lab environments) or expensive (e.g., special materials or expert opinions are required). Ideally, in order to reduce the amount of data needed to reach conclusions, already-collected data can be leveraged to guide the selection of future measurements in a closed-loop manner. While the behavior and benefits of some closed-loop data collection strategies are well understood in simple settings, this family of strategies is not commonly employed in real-world scientific laboratories or in medical trials due to a lack of predictability and accuracy of the outcomes. This project seeks to make foundational contributions to the understanding of closed-loop learning strategies with a view towards designing new data-collection strategies that are both effective and reliable. In practice, this may lead to requiring fewer patients in a clinical trial or to halving the time to identify a disease-curing drug. The investigator also plans to engage with high-school students and machine-learning enthusiasts alike to increase their level of awareness around data collection -- for instance, how even a simple survey, if not carefully designed, can result in privacy violations, demographic under-representation and bias of many forms, all of which may lead to inaccurate conclusions.For many problems of interest in closed-loop learning, prior art has focused only on minimax optimality, where the sample complexity of the worst-case problem instance is minimized. This approach leads to algorithms that are significantly inferior on "easy" or benign instances that may occur in nature but which are far from adversarial. In contrast this project will study the fundamental limits of instance-optimal sample complexity for problems of interactive learning and reinforcement learning in the Probably Approximately Correct (PAC) setting. The insights to be gained will be applied towards the design of algorithms that automatically adapt to the intrinsic difficulty of the particular problem instance being faced, be it benign or not. The proposed approach is motivated by the observation that the instance-optimal sample complexity decomposes into an asymptotic term, which is by now well characterized, and a moderate-confidence term, which is known to dominate the asymptotic term for all practical purposes. As the properties of the latter term are still poorly understood, lower bounds for it will be constructed together with algorithms that nearly achieve them. Such results will lead to algorithms that greatly reduce the overall instance-optimal sample complexity and vastly improve upon state-of-the-art algorithms that tend to cater to worst-case scenarios. The efforts will initially focus on structured linear bandits and reinforcement learning in the tabular and linear-function approximation settings. While these paradigms are of wide applicability to practice, they also have enough complexity to allow insights to be extrapolated to more generic closed-loop learning paradigms.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.