Machine Learning, Approximation Algorithms, and Planning under Uncertainty

该项目涉及发展不确定情况下规划的近似算法、机器学习和人工智能问题之间的联系。这项工作有两个主要的相关主题。第一个是将近似算法技术扩展到人工智能和机器人更感兴趣的问题上。这些问题包括不确定性下的路径规划问题、聚类问题以及机器学习中新挑战引发的问题。例如，在路径规划的背景下，经典的旅行推销员问题问：在某种确定的环境中，访问所有感兴趣的地点并返回到起点的最短路线是什么？但是，如果我们正在为一个机器人制定一个计划，它的行动可能是不可靠的，并且可能发生意外事件呢？在这种情况下，我们希望使用环境的随机模型，例如在马尔可夫决策过程中。在这种情况下，人们是否可以很好地近似于TSP的自然模拟？这项工作的目标之一是探索这个和几个相关的优化问题。在另一种情况下，在机器学习中，有许多问题可以被描述为一种形式的图划分，但是图嵌入在Rn中，并且在允许的切割形式上有一些几何限制。这项工作的第二个主题是在另一个方向，应用计算学习理论的技术，包括在线学习和样本复杂性分析，来设计具有可证明质量保证的优化问题的算法。这些问题包括路由问题，算法机制设计问题，以及在线优化中的一些问题。本提案中的其他主题包括探索机器学习中的核方法与降维之间的关系，以及研究如何使用在线学习技术收敛到某些博弈论均衡。这项工作的智力价值在于，这项研究将促进我们对所有三个领域的重要问题的理解：近似算法、机器学习和不确定性下的规划。更广泛的影响是，通过发展这些领域之间的联系，它将使它们更紧密地联系在一起，例如，通过开发算法，为机器人更感兴趣的模型提供良好的近似保证，或者为机器学习更感兴趣的聚类和图划分问题提供算法。反过来，我们希望，这将允许其他研究人员在每个领域的未来工作对其他领域产生更大的影响。

This project involves developing connections between Approximation Algorithms, Machine Learning and AI problems of planning under uncertainty. This work has two main related themes. The first is extending the technology of approximation algorithms to problems of greater interest to AI and Robotics. These include problems of path planning under uncertainty, clustering, and problems motivated by new challenges in machine learning. For instance, in the context of path planning, the classic Traveling Salesman Problem asks: what is the shortest route to visit all locations of interest in some deterministic environment and return back to the start? But what if we are developing a plan for a robot whose actions may be unreliable and to which unexpected events can occur? In that case, we would want to use a stochastic model of the environment such as in MarkovDecision Processes. Can one develop good approximations to the natural analog of the TSP in such settings? One of the goals of this work is to explore this and several related optimization problems. In a different context, in machine learning there are a number of problems that can be phrased as a form of graph partitioning, but where the graph is embedded in Rn and there is some geometric restriction on the form of cuts allowed.The second theme of this work is in the other direction, applying techniques from computational learning theory, including online learning and sample-complexity analysis, to the design of algorithms for optimization problems with provable quality guarantees. These include problems in routing, in algorithmic mechanism design, and a number of problems in online optimization.Other topics in this proposal include the exploring the relation between kernel methods in machine learning and dimensionality reduction, and investigating how online learning techniques can be used to converge to certain game-theoretic equilibria. The intellectual merit of the proposed work is that this research will advance our understanding of important problems in all three areas: approximation algorithms, machine learning, and planning under uncertainty. The broader impact is that by developing connections between these areas, it will bring them closer together, for instance by developing algorithms with good approximation guarantees for models of greater interest to robotics, or algorithms for clustering and graph partitioning problems of greater interest to machinelearning. This will in turn, we hope, allow future work by other researchers in each area to have a greater impact on each of the other areas.