Timezone: »

Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
Asaf Cassel · Alon Cohen · Tomer Koren

Tue Jul 14 02:00 PM -- 02:45 PM & Wed Jul 15 01:00 AM -- 01:45 AM (PDT) @ Virtual

We consider the problem of learning in Linear Quadratic Control systems whose transition parameters are initially unknown. Recent results in this setting have demonstrated efficient learning algorithms with regret growing with the square root of the number of decision steps. We present new efficient algorithms that achieve, perhaps surprisingly,regret that scales only (poly-)logarithmically with the number of steps, in two scenarios: when only the state transition matrix A is unknown, and when only the state-action transition matrix B is unknown and the optimal policy satisfies a certain non-degeneracy condition. On the other hand, we give a lower bound which shows that when the latter condition is violated, square root regret is unavoidable.

Author Information

Asaf Cassel (Tel Aviv University)
Alon Cohen (Technion, Google)
Tomer Koren (Tel Aviv University)

More from the Same Authors