The problem of piecewise affine (PWA) regression and planning is of foundational importance to the study of online learning, control, and robotics, where it provides a theoretically and empirically tractable setting to study systems undergoing sharp changes in the dynamics. Unfortunately, due to the discontinuities that arise when crossing into different ``pieces,'' learning in general sequential settings is impossible and practical algorithms are forced to resort to heuristic approaches. This paper builds on the recently developed smoothed online learning framework and provides the first algorithms for prediction and simulation in PWA systems whose regret is polynomial in all relevant problem parameters under a weak smoothness assumption; moreover, our algorithms are efficient in the number of calls to an optimization oracle. We further apply our results to the problems of one-step prediction and multi-step simulation regret in piecewise affine dynamical systems, where the learner is tasked with simulating trajectories and regret is measured in terms of the Wasserstein distance between simulated and true data. Along the way, we develop several technical tools of more general interest.
翻译:平方英尺(PWA)回归和规划问题对于在线学习、控制和机器人的研究具有根本重要性,因为它为研究动态发生急剧变化的系统提供了一个理论上和经验上可操作的环境。 不幸的是,由于在进入不同的“件”时出现的不连续问题,一般的相继学习是不可能的,实际算法被迫采用休眠方法。本文件以最近开发的平稳在线学习框架为基础,为PWA系统预测和模拟提供了第一批算法,而PWA系统中的所有相关问题参数在光滑的假设下都是多式的;此外,我们的算法在要求优化或触觉的次数方面效率很高。我们进一步将我们的结果应用于单步预测和多步模拟的遗憾问题,在这种系统中,学习者的任务是模拟轨迹和遗憾,用模拟数据与真实数据之间的瓦瑟斯坦距离来衡量。此外,我们开发了几个具有普遍兴趣的技术工具。