We consider the problem of controlling an unknown linear time-invariant
dynamical system from a single chain of black-box interactions, with no access
to resets or offline simulation. Under the assumption that the system is
controllable, we give the first efficient algorithm that is capable of
attaining sublinear regret in a single trajectory under the setting of online
nonstochastic control. This resolves an open problem on the stochastic LQR
problem, and in a more challenging setting that allows for adversarial
perturbations and adversarially chosen and changing convex loss functions.
We give finite-time regret bounds for our algorithm on the order of
$2^{\tilde{O}(\mathcal{L})} + \tilde{O}(\text{poly}(\mathcal{L}) T^{2/3})$ for
general nonstochastic control, and $2^{\tilde{O}(\mathcal{L})} +
\tilde{O}(\text{poly}(\mathcal{L}) \sqrt{T})$ for black-box LQR, where
$\mathcal{L}$ is the system size which is an upper bound on the dimension. The
crucial step is a new system identification method that is robust to
adversarial noise, but incurs exponential cost.
To complete the picture, we investigate the complexity of the online
black-box control problem, and give a matching lower bound of
$2^{\Omega(\mathcal{L})}$ on the regret, showing that the additional
exponential cost is inevitable. This lower bound holds even in the noiseless
setting, and applies to any, randomized or deterministic, black-box control
method.

研究使用单个黑盒交互控制未知的线性时不变动态系统的问题，探讨在线非随机控制的情况下如何获得次线性后悔量，该方法可处理对抗性干扰及凸损失函数的变化。我们提供了一种新的系统识别方法，并在一些条件下给出了后悔上界以及结果的匹配性下界。

线性动态系统的黑箱控制

Black-Box Control for Linear Dynamical Systems

We prove that stochastic gradient descent efficiently converges to the global
optimizer of the maximum likelihood objective of an unknown linear
time-invariant dynamical system from a sequence of noisy observations generated
by the system. Even though the objective function is non-convex, we provide
polynomial running time and sample complexity bounds under strong but natural
assumptions. Linear systems identification has been studied for many decades,
yet, to the best of our knowledge, these are the first polynomial guarantees
for the problem we consider.

我们证明了随机梯度下降算法可以高效地收敛于未知线性时不变动态系统的极大似然目标函数的全局极值。虽然该目标函数是非凸的，但我们在强但自然的假设下提供了多项式运行时间和样本复杂度界限。尽管线性系统识别已经研究了许多年，但据我们所知，这是我们所考虑的问题的第一个多项式保证。