论文标题
向许多轨迹学习
Learning from many trajectories
论文作者
论文摘要
我们从非独立的协变量的许多独立序列（“轨迹”）中开始研究，以序列建模，控制和增强学习来反映任务。从概念上讲，我们的多条件设置位于统计学习理论中的两个传统设置之间：从独立示例中学习，并从单个自动相关的序列中学习。我们有效学习的条件将以前的环境推广 - trajectories必须以扩展独立示例的标准要求的方式是非分类的。值得注意的是，我们不需要轨迹是崇高的，长的，也不严格稳定。 对于$ m $轨迹产生的$ n $维度示例，对于线性最小二乘的回归，每一个。长度$ t $，我们观察到统计效率的显着变化，因为轨迹的数量从少数（即$ m \ millysim n $）增加到许多（即许多$ M \ gtrsim n $）。具体而言，我们确定此问题的最坏情况错误率是$θ（n / m t）$，只要$ m \ gtrsim n $。同时，当$ m \ lyssim n $ n $时，我们建立了一个（尖锐的）下限$ω（n^2 / m^2 t）$在最坏情况下的错误率上，这是通过一个简单，边缘不稳定的线性动力学系统实现的。一个关键的结果是，在轨迹定期重置的域中，错误率最终表现得好像所有示例都是独立的，是从它们的边缘绘制的。作为分析的必然性，我们还提高了线性系统识别问题的保证。
We initiate a study of supervised learning from many independent sequences ("trajectories") of non-independent covariates, reflecting tasks in sequence modeling, control, and reinforcement learning. Conceptually, our multi-trajectory setup sits between two traditional settings in statistical learning theory: learning from independent examples and learning from a single auto-correlated sequence. Our conditions for efficient learning generalize the former setting--trajectories must be non-degenerate in ways that extend standard requirements for independent examples. Notably, we do not require that trajectories be ergodic, long, nor strictly stable. For linear least-squares regression, given $n$-dimensional examples produced by $m$ trajectories, each of length $T$, we observe a notable change in statistical efficiency as the number of trajectories increases from a few (namely $m \lesssim n$) to many (namely $m \gtrsim n$). Specifically, we establish that the worst-case error rate of this problem is $Θ(n / m T)$ whenever $m \gtrsim n$. Meanwhile, when $m \lesssim n$, we establish a (sharp) lower bound of $Ω(n^2 / m^2 T)$ on the worst-case error rate, realized by a simple, marginally unstable linear dynamical system. A key upshot is that, in domains where trajectories regularly reset, the error rate eventually behaves as if all of the examples were independent, drawn from their marginals. As a corollary of our analysis, we also improve guarantees for the linear system identification problem.
