Timezone: »

Online Linear Quadratic Control
Alon Cohen · Avinatan Hasidim · Tomer Koren · Nevena Lazic · Yishay Mansour · Kunal Talwar

Fri Jul 13 02:00 AM -- 02:20 AM (PDT) @ A5
We study the problem of controlling linear time-invariant systems with known noisy dynamics and adversarially chosen quadratic losses. We present the first efficient online learning algorithms in this setting that guarantee $O(\sqrt{T})$ regret under mild assumptions, where $T$ is the time horizon. Our algorithms rely on a novel SDP relaxation for the steady-state distribution of the system. Crucially, and in contrast to previously proposed relaxations, the feasible solutions of our SDP all correspond to ``strongly stable'' policies that mix exponentially fast to a steady state.

Author Information

Alon Cohen (Google Inc.)
Avinatan Hasidim (Google)
Tomer Koren (Google Brain)
Nevena Lazic (Google)
Yishay Mansour (Google)
Kunal Talwar (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors