Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Minimal Expected Regret in Linear Quadratic Control   We consider the problem of online learning in Linear Quadratic Control
systems whose state transition and state-action transition matrices $A$ and $B$
may be initially unknown. We devise an online learning algorithm and provide
guarantees on its expected regret. This regret at time $T$ is upper bounded (i)
by $\widetilde{O}((d_u+d_x)\sqrt{d_xT})$ when $A$ and $B$ are unknown, (ii) by
$\widetilde{O}(d_x^2\log(T))$ if only $A$ is unknown, and (iii) by
$\widetilde{O}(d_x(d_u+d_x)\log(T))$ if only $B$ is unknown and under some mild
non-degeneracy condition ($d_x$ and $d_u$ denote the dimensions of the state
and of the control input, respectively). These regret scalings are minimal in
$T$, $d_x$ and $d_u$ as they match existing lower bounds in scenario (i) when
$d_x\le d_u$ [SF20], and in scenario (ii) [lai1986]. We conjecture that our
upper bounds are also optimal in scenario (iii) (there is no known lower bound
in this setting).
  Existing online algorithms proceed in epochs of (typically exponentially)
growing durations. The control policy is fixed within each epoch, which
considerably simplifies the analysis of the estimation error on $A$ and $B$ and
hence of the regret. Our algorithm departs from this design choice: it is a
simple variant of certainty-equivalence regulators, where the estimates of $A$
and $B$ and the resulting control policy can be updated as frequently as we
wish, possibly at every step. Quantifying the impact of such a
constantly-varying control policy on the performance of these estimates and on
the regret constitutes one of the technical challenges tackled in this paper.

34
The categories of this paper are: chem-ph
30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
25
The categories of this paper are: patt-sol
10
The categories of this paper are: q-bio
33
The categories of this paper are: plasm-ph
32
The categories of this paper are: atom-ph
26
The categories of this paper are: bayes-an
27
The categories of this paper are: comp-gas
28
The categories of this paper are: alg-geom
20
The categories of this paper are: acc-phys
11
The categories of this paper are: hep-lat
3
The categories of this paper are: physics
0
The categories of this paper are: hep-ph
17
The categories of this paper are: q-fin
18
The categories of this paper are: econ