Online Policy Gradient for Model Free Learning
of Linear Quadratic Regulators with $\sqrt{T}$ Regret

Model-free, policy gradient algorithms have become a staple of Reinforcement Learning (RL) with both practical successes [19, 12], and strong theoretical guarantees in several settings [26, 24]. In this work we study the design and analysis of such algorithms for the adaptive control of Linear Quadratic Regulator (LQR) systems, as seen through the lens of regret minimization [1, 9, 21]. In this continuous state and action reinforcement learning setting, an agent chooses control actions $u_{t}$ and the system state $x_{t}$ evolves according to the noisy linear dynamics

where $A_{\star}$ and $B_{\star}$ are transition matrices and $w_{t}$ are i.i.d zero-mean noise terms. The cost is a quadratic function of the current state and action, and the regret is measured with respect to the class of linear policies, which are known to be optimal for this setting.

Model-based methods, which perform planning based on a system identification procedure that estimates the transition matrices, have been studied extensively in recent years. This started with Abbasi-Yadkori and Szepesvári [1], which established an $O\brk 0{\sqrt{T}}$ regret guarantee albeit with a computationally intractable method. More recently, Cohen et al. [9], Mania et al. [21] complemented this result with computationally efficient methods, and Cassel et al. [6], Simchowitz and Foster [25] provided lower bounds, showing that this rate is generally unavoidable; regardless of whether the algorithm is model free or not. In comparison, the best existing model-free algorithms are policy iteration procedures by Krauth et al. [18] and Abbasi-Yadkori et al. [2] that respectively achieve $\smash{\widetilde{O}}\brk 0{T^{2/3}}$ and $\smash{\widetilde{O}}\brk 0{T^{2/3+\epsilon}}$ regret for $\epsilon=\Theta(1/\log{T})$.

Our main result is an efficient (in fact, linear time per step) policy gradient algorithm that achieves $\smash{\widetilde{O}}\brk 0{\sqrt{T}}$ regret, thus closing the (theoretical) gap between model based and free methods for the LQR model. An interesting feature of our approach is that while the policies output by the algorithm are clearly state dependent, the tuning of their parameters requires no such access. Instead, we only rely on observations of the incurred cost, similar to bandit models (e.g., 5).

One of the main challenges of regret minimization in LQRs (and more generally, in reinforcement learning) is that it is generally infeasible to change policies as often as one likes. Roughly, this is due to a burn-in period following a policy change, during which the system converges to a new steady distribution, and typically incurs an additional cost proportional to the change in steady states, which is in turn proportional to the distance between policies. There are several ways to overcome this impediment. The simplest is to restrict the number of policy updates and explore directly in the action space via artificial noise (see e.g., 25). Another approach by Cohen et al. [9] considers a notion of slowly changing policies, however, these can be very prohibitive for exploration in policy space. Other works (e.g., 3) consider a policy parameterization that converts the problem into online optimization with memory, which also relies on slowly changing policies. This last method is also inherently model-based and thus not adequate for our purpose.

A key technical contribution that we make is to overcome this challenge by exploring directly in policy space. While the idea itself is not new, we provide a novel and tighter analysis that allows us to use larger perturbations, thus reducing the variance of the resulting gradient estimates. We achieve this by showing that the additional cost depends only quadratically on the exploration radius, which is a crucial ingredient for overcoming the $O\brk 0{T^{2/3}}$ limitation. The final ingredient of the analysis involves a sensitivity analysis of the gradient descent procedure that uses the estimated gradients. Here again, while similar analyses of gradient methods exist, we provide a general result that gives appropriate conditions for which the optimization error depends only quadratically on the error in the gradients.

We are now ready to present our main algorithm for model free regret minimization in LQR. The algorithm, given in Algorithm 1, optimizes an underlying controller $K_{j}$ over epochs of exponentially increasing duration. Each epoch consists of sub-epochs, during which a perturbed controller $K_{j,i}$ centered at $K_{j}$ is drawn and played for $\tau$ rounds. At the end of each epoch, the algorithm uses $c_{j,i,\tau}$, which is the cost incurred during the final round of playing the controller $K_{j,i}$, to construct a gradient estimate which in turn is used to calculate the next underlying controller $K_{j+1}$. Interestingly, we do not make any explicit use of the state observation $x_{t}$ which is only used implicitly to calculate the control signal, via $u_{t}=K_{t}x_{t}$. Furthermore, the algorithm makes only $O\brk*{d_{u}d_{x}}$ computations per time step.

Our main result regarding Algorithm 1 is stated in the following theorem: a high-probability $O(\sqrt{T})$ regret guarantee with a polynomial dependence on the problem parameters.

Here we give an overview of the main steps in proving Theorem 1, deferring the details of each step to later sections. Our first step is analyzing the utility of the policies $K_{j}$ computed at the end of each epoch. We show that the regret of each $K_{j}$ (over epoch $j$) in terms of its long-term (steady state) cost compared to that of the optimal $K_{\star}$, is controlled by the inverse square-root of the epoch length $m_{j}$.

The proof of the lemma is based on a careful analysis of gradient descent with inexact gradients and crucially exploits the PL and local-smoothness properties of the loss $J\brk*{\cdot}$. More details can be found in Section 4.

The more interesting (and challenging) part of our analysis pertains to controlling the costs associated with exploration, namely, the penalties introduced by the perturbations of the controllers $K_{j}$. The direct cost of exploration is clear: instead of playing the $K_{j}$ intended for exploitation, the algorithm actually follows the perturbed controllers $K_{j,i}$ and thus incurs the differences in long-term costs $J\brk*{K_{j,i}}-J\brk*{K_{j}}$. Our following lemma bounds the accumulation of these penalties over an epoch $j$; importantly, it shows that while the bound scales linearly with the length of the epoch $m_{j}$, it has a quadratic dependence on the exploration radius $r_{j}$.

There are additional, indirect costs associated with exploration however: within each epoch the algorithm switches frequently between different policies, thereby suffering the indirect costs that stem from their “burn-in” period. This is precisely what gives rise to the differences between the realized cost $c_{j,i,s}$ and the long-term cost $J\brk*{K_{j,i}}$ of the policy $K_{j,i}$, the cumulative effect of which is bounded in the next lemma. Here again, note the quadratic dependence on the exploration radius $r_{j}$ which is essential for obtaining our $\sqrt{T}$-regret result.

The technical details for Lemmas 7 and 8 are discussed in Section 5. We now have all the main pieces required for proving our main result.

At its core, Algorithm 1 is a policy gradient method with $K_{j}$ being the prediction after $j$ gradient steps. In this section we analyze the sub-optimality gap of the underlying controllers $K_{j}$ culminating in the proof of Lemma 6. To achieve this, we first consider a general optimization problem with a corrupted gradient oracle, and show that the optimization rate is limited only by the square of the corruption magnitude. We follow this with an analysis of the LQR gradient estimation from which the overall optimization cost follows readily.