A modified Thompson sampling-based learning algorithm for unknown linear systems

The problem of learning an optimal policy for a system with linear dynamics and quadratic cost with unknown parameters has received considerable attention in the literature. Historically, the focus has been on developing algorithms which asymptotically learn optimal policies using techniques from adaptive control and reinforcement learning [2, 3, 4, 5]. In recent years, the emphasis has shifted towards developing algorithms with finite-time regret guarantees.

Broadly speaking, three classes of learning algorithms have been considered in the literature: optimism in the face of uncertainty [6, 7, 8, 9], certainty equivalence [10, 11, 12, 13, 14], and Thompson sampling [15, 16, 14, 17]. These algorithms provide two kinds of regret guarantees: frequentist and Bayesian. In the frequentist setting, it is established that the regret for the unknown system is bounded with high probability (with respect to the distribution of the process noise and the randomness introduced by the algorithm). In the Bayesian setting, it is assumed that there is a prior on the unknown system parameters and it is established that the expected regret is bounded (where the expectation is with respect to the prior, the distribution of the process noise, and the randomness introduced by the algorithm). These two notions of regret are different and, since the per-step cost is not bounded, one form of the regret does not imply the other.

In this paper, we revisit a recently proposed algorithm for establishing Bayesian regret called Thompson sampling with dynamic episodes (TSDE) [1]. The main result of [1] is to show that the Bayesian regret of TSDE accumulated up to time $T$ is bounded by $\tilde{\mathcal{O}}(\sqrt{T})$, where the $\tilde{\mathcal{O}}(\cdot)$ notation hides constants and poly-logarithmic factors. This result was derived under a technical assumption on the induced norm of the closed loop system. In this paper, we present a variation of the TSDE algorithm and obtain a $\tilde{\mathcal{O}}(\sqrt{T})$ bound on the Bayesian regret by imposing a much milder technical assumption.

We consider the same model as [1]. For the sake of completeness, we present the model below.

Consider a linear system with state $x_{t}\in\mathds{R}^{n}$, control input $u_{t}\in\mathds{R}^{m}$, and disturbance $w_{t}\in\mathds{R}^{n}$. For the ease of exposition, we assume that the system starts from an initial state $x_{1}=0$. The state evolves over time according to

where $A\in\mathds{R}^{n\times n}$ and $B\in\mathds{R}^{n\times m}$ are the system dynamics matrices. The noise $\{w_{t}\}_{t\geq 1}$ is an independent and identically distributed Gaussian process with $w_{t}\sim\mathcal{N}(0,\sigma_{w}^{2}I)$.

In [1], it was assumed that $\sigma_{w}^{2}=1$. Using a general $\sigma_{w}^{2}>0$ does not fundamentally change any of the results or the proof arguments.

At each time $t$, the system incurs a per-step cost given by

where $Q$ and $R$ are positive definite matrices.

Let $\theta^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}=[A,B]$ denote the parameters of the system. $\theta\in\mathds{R}^{d\times n}$, where $d=n+m$. The performance of any policy $\pi=(\pi_{1},\pi_{2},\dots)$ is measured by the long-term average cost given by

Let $J(\theta)$ denote the minimum of $J(\pi;\theta)$ over all policies. It is well known [18] that if the pair $(A,B)$ is stabilizable, then $J(\theta)$ is given by

where $S(\theta)$ is the unique positive semi-definite solution of the following Riccati equation:

Furthermore, the optimal control policy is given by

where the gain matrix $G(\theta)$ is given by

As in [1], we are interested in the setting where the system parameters are unknown. We denote the unknown parameters by a random variable $\theta_{1}$ and assume that there is a prior distribution on $\theta_{1}$. The Bayesian regret of a policy $\pi$ operating for horizon $T$ is defined by

where the expectation is with respect to the prior on $\theta_{1}$, the noise processes, the initial conditions, and the potential randomizations done by the policy $\pi$.

As in [1], we assume that the unknown model parameters $\theta$ lie in a compact subset $\Omega_{1}$ of $\mathds{R}^{d\times n}$. We use $p|\Omega$ to denote the restriction of probability distribution $p$ on the set $\Omega$. We assume that there is a prior $\mu_{1}$ on $\Omega_{1}$ which satisfies the following assumption.

We maintain a posterior distribution $\mu_{t}$ on $\Omega_{1}$ based on the history $(x_{1:t-1},u_{1:t-1})$ of the observations until time $t$. From standard results in linear Gaussian regression [19], we know that the posterior is a truncated Gaussian distribution

where $\bar{\mu}_{t}(\theta(i))=\mathcal{N}(\hat{\theta}_{t}(i),\Sigma_{t})$ and $\{\hat{\theta}_{t}(i)\}_{i=1}^{n}$ and $\Sigma_{t}$ can be updated recursively as follows:

where $z_{t}=[x_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}},u_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$.

For the ease of notation, we use $R(T)$ instead of $R(T;\texttt{TSDE})$ in this section. Let $K_{T}$ denote the number of episodes until horizon $T$. Following the exact same steps as [1], we can show that

where

We establish the bound on $R(T)$ by individually bounding $R_{0}(T)$, $R_{1}(T)$, and $R_{2}(T)$.

The terms in (19) are bounded as follows:

1. 1.

   $R_{0}(T)\leq\tilde{\mathcal{O}}(\sigma_{w}^{2}\sqrt{(n+m)T})$.

2. 2.

   $R_{1}(T)\leq\tilde{\mathcal{O}}(\sigma_{w}^{2}\sqrt{(n+m)T})$.

3. 3.

   $R_{2}(T)\leq\tilde{\mathcal{O}}(\sigma_{w}^{2}(n+m)\sqrt{nT})$.

Combining Lemma IV with equation (19) establishes Theorem III-C. Before presenting the proof of Lemma IV, we establish some preliminary results.

In this paper, we present a variation of the TSDE algorithm of [1] and show that its Bayesian regret up to time $T$ is bounded by $\tilde{\mathcal{O}}(\sqrt{T})$ under a milder technical assumption than [1]. The result in [1] was derived under the assumption that there exists a $\delta<1$ such that for any $\theta,\phi\in\Omega_{1}$, $\|A_{\theta}+B_{\theta}G(\phi)\|\leq\delta$. For our analysis, we impose a different assumption for the closed loop gain when the system dynamics are $\theta$ and the controller is chosen according to $\phi$. We show that the assumption of [1] implies our assumption. Our assumption is also implied by $\rho(A_{\theta}+B_{\theta}G(\phi))\leq\delta$.

The key technical result in [1] as well as our paper is Lemma IV-A, which shows that for any $q\geq 1$, $\mathds{E}[X_{T}^{q}/\sigma_{w}^{q}]\leq\tilde{\mathcal{O}}(\log T)$. The proof argument in both [1] as well as our paper is to show that there is some constant $\alpha_{0}$ such that $X_{T}\leq\sigma_{w}+\alpha_{0}W_{T}$. Under the stronger assumption in [1], one can show that for all $t$, $\|x_{t+1}\|\leq\delta\|x_{t}\|+\|w_{t}\|$, which directly implies that $X_{T}\leq\sigma_{w}+W_{T}/(1-\delta)$. Under the weaker assumption in this paper, the argument is more subtle. The basic intuition is that in each episode, the system is asymptotically stable and, being a linear system, also exponentially stable (in the sense of Lemma III-B). So, if the episode length is sufficiently long, then we can ensure that $\|x_{t_{k+1}}\|\leq\beta\|x_{t_{k}}\|+\bar{\alpha}W_{T}$, where $\beta<1$ and $\bar{\alpha}$ is a constant. This is sufficient to ensure that $X_{T}\leq\sigma_{w}+\alpha_{0}W_{T}$ for an appropriately defined $\alpha_{0}$.

The fact that each episode must be of length $T_{\min}$ implies that the second triggering condition is not triggered for the first $T_{\min}$ steps in an episode. Therefore, in this interval, the determinant of the covariance can be smaller than half of its value at the beginning of the episode. Consequently, we cannot use the same proof argument as [1] to bound $R_{2}(T)$ because that proof relied on the fact that for any $t\in\{t_{k},\dots,t_{k+1}-1\}$, $\det\Sigma_{t}^{-1}/\det\Sigma_{t_{k}}^{-1}\leq 2$. So, we provide a variation of that proof argument, where we use a coarser bound on $\det\Sigma_{t}^{-1}/\det\Sigma_{t_{k}}^{-1}$ given by Lemma F.

We conclude by observing that the milder technical assumption imposed in this paper may not be necessary. Numerical experiments indicate that the regret of the TSDE algorithm shows $\tilde{\mathcal{O}}(\sqrt{T})$ behavior even when the uncertainty set $\Omega_{1}$ does not satisfy Assumption 4 (as was also reported in [1]). This suggests that it might be possible to further relax Assumption 4 and still establish an $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound.

We would like to thank Borna Sayedana for pointing out a mistake in Lemma 9 in a previous draft of this paper.