Marc Abeille

Alessandro Lazaric

Improved Regret Bounds

published or not. The documents may come

Introduction

Designing algorithms to properly trade off exploring an unknown environment and exploiting the estimated optimal control policy, is one of the most important challenges towards scaling reinforcement learning (RL) [START_REF] Sutton | Introduction to Reinforcement Learning[END_REF] to problems with large or continuous state and action spaces. The exploration-exploitation dilemma in RL Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s). has been mostly addressed following two main approaches: optimism-in-face-of-uncertainty (OFU) and Thompson sampling (TS) (also referred to as posterior-sampling in RL, PSRL [START_REF] Strens | A bayesian framework for reinforcement learning[END_REF]). Following the OFU approach (see e.g., [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], we first construct the set of admissible environments whose parameters are within confidence intervals constructed on the samples collected so far. Then the optimal policy w.r.t. the optimistic admissible environment (i.e., the one maximizing the optimal value function) is executed. PSRL is a Bayesian algorithm that executes the optimal policy w.r.t. a environment drawn at random from the posterior computed from a given prior and the samples observed so far. The flexibility of applying PSRL to any parametric MDP (as soon as sampling from a posterior can be done efficiently) and the difficulty of deriving tight confidence intervals and computing the optimistic policy in OFU, often make PSRL the more effective approach. Empirical evidence of the performance of PSRL ranges from multiarmed bandit (Chapelle & Li, 2011) to RL with linear and non-linear function approximation (Osband et al., 2016b;a).

On the theoretical side, several results exist on PSRL in the episodic setting under the regret framework, where the cumulative reward collected by the learning agent is compared to the performance of the optimal policy. Given the Bayesian nature of PSRL, its regret is often analyzed in expectation w.r.t. the prior over the environments (i.e., the so-called Bayesian regret). [START_REF] Osband | more) efficient reinforcement learning via posterior sampling[END_REF] proved the first regret bound for PSRL in finite MDPs of order O(S √ AT ). The more general setting of learning in parameterized MDPs is studied in (Osband & Van Roy, 2014), where it is shown that the regret of PSRL depends on the dimensionality of the space of parameters rather than its cardinality. Osband & Roy (2016) showed how leveraging over posterior sampling in PSRL actually leads to improved regret bounds w.r.t. OFU in finite MDPs. Finally, [START_REF] Gopalan | Thompson sampling for learning parameterized markov decision processes[END_REF] proved regret bounds in a slightly more general non-episodic setting under the assumption that the MDP is ergodic and an initial state is positive recurrent under any policy. While these results match the frequentist bounds of OFU, when moving from the episodic to infinite horizon setting the results of TS are still limited. While most of the results for OFU hold in both cases (see e.g. [START_REF] Bartlett | REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs[END_REF][START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]Abbasi-Yadkori & Szepesvári, 2011)), Osband & Van Roy (2016) reviewed in detail the challenges of extending episodic results to infinite horizon showing how previous attempts in proving regret for infinite horizon problem were possibly flawed [START_REF] Abbasi-Yadkori | Bayesian optimal control of smoothly parameterized systems[END_REF]. While Osband & Van Roy (2016) conjecture that standard O( √ T ) bounds should hold for TS in infinite horizon, [START_REF] Agrawal | Optimistic posterior sampling for reinforcement learning: worst-case regret bounds[END_REF] only recently proved that a specific optimistic version of PSRL is able to achieve a O( √ T ) regret in finite MDPs, while [START_REF] Kim | Thompson sampling for stochastic control: The finite parameter case[END_REF] proved problem-dependent log T regret for ergodic finite parametric MDPs. On the other hand, for continuous state-action spaces, [START_REF] Ouyang | Learning-based control of unknown linear systems with thompson sampling[END_REF] proved a O( √ T ) regret only in the Bayesian setting for infinite-horizon linear quadratic (LQ) control, while [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF] showed that TS may suffer a frequentist regret O(T 2/3 ), which is significantly worse than the O( √ T ) result proved by Abbasi-Yadkori & Szepesvári (2011) and [START_REF] Faradonbeh | Finite time analysis of optimal adaptive policies for linear-quadratic systems[END_REF] for OFU. [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF] justify this result by an unfavourable trade-off between lazy updates and number of optimistic steps, which leads to shorter episodes than in OFU. While increasing the number of episodes also increases the chance of selecting optimistic environments, which is critical for the functioning of TS, this leads to a larger regret due to the continuous switching between different policies.

In this paper, we build on the result of [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF] and we prove that their bound can be reduced to O( √ T ). This result is obtained using a novel bound on the regret suffered at the switch between two episodes (the consistency regret in [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF]). We show that the regret incurred at policy switches is related to expected absolute deviation of the solution to the Riccati equation under the TS distribution, which is cumulatively bounded as O( √ T ). As a result, we are able to reduce the length of episodes even further (i.e., constant length or even one single step) at no additional cost and fully exploit the optimism of TS. While the novel bound on the consistency regret is derived for the general case, our final regret bound relies on a lower-bound on the probability of optimistic sampling derived by [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF], which only holds for one-dimensional systems. We conjecture that a similar bound should hold for any dimension and we provide preliminary numerical simulations to support such conjecture.

Preliminaries

Most of the material in this section is borrowed from Abbasi-Yadkori & Szepesvári (2011) and [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF].

Notation. For any matrix A ∈ R n×m , we denote as A[i, j] its i, j component. For any vector x and matrix A of appropriate dimensions we define the following norms x = √

x T x, A F = Tr(AA T ) 1/2 , A 2 = sup x =1 Ax and for any positive definite matrix V ,

A V = V 1/2 A F .
We use d = to denote equality in distribution.

The control problem. At any time t, given state x t ∈ R n and control u t ∈ R d , in a linear quadratic (LQ) control problem, the next state and cost are obtained as

x t+1 = A * x t + B * u t + t+1 ; c(x t , u t ) = x T t Qx t + u T t Ru t , (1)
where A * , B * , Q, R are matrices of appropriate dimension and { t+1 } t is a zero-mean process. The dynamics parameters are summarized in θ T * = (A * , B * ). The solution to an LQ is a stationary deterministic policy π : R n → R d mapping states to controls minimizing the infinite-horizon average expected cost

J π (θ * ) = lim sup T →∞ 1 T E T t=0 c(x t , u t ) , (2)
with x 0 = 0 and u t = π(x t ). We denote as π * (θ * ) the optimal policy of the LQ parametrized by θ * .

Let F t = σ(x 0 , u 0 , . . . , x t , u t ) be the filtration that represents the knowledge up to time t. We also define the "extended" filtration F x t = (F t-1 , x t ). We impose the following assumptions over the noise process and the linear system of Eq. 1. Assumption 1 (Noise). The noise { t } t is a F t -martingale difference sequence and it is conditionally Gaussian, i.e., t |F t ∼ N (0, I) for all t ≤ T . Assumption 2 (LQ). The cost matrices Q and R are symmetric p.d. and (A * , B * ) is stabilizable. 1 Under Asm. 1 and 2, Thm.16.6.4 in [START_REF] Lancaster | Algebraic riccati equations[END_REF] guarantees the existence and uniqueness of an optimal policy π * (θ * ) = K(θ * )x, where,

K(θ * ) = -R + B T P (θ * )B -1 B T P (θ * )A, P (θ * ) = Q + A T P (θ * )A + A T P (θ * )BK(θ * ). (3)
The optimal average cost is J * = J π * (θ * ) = Tr(P (θ * )).

For notational convenience, we introduce H(θ * ) T = I K(θ * ) T and we have that the closed-loop matrix

A * + B * K(θ * ) = θ T * H(θ *
) is asymptotically stable. Finally, we recall the definition of differential value function in state x as V (x; θ * ) = x T P (θ * )x, which measures the (limit) difference in cumulative cost between executing the optimal policy from x and the average cost J(θ * ). Finally, we recall a result about the regularity of the Riccati solution. Proposition 1. Under Asm. 1 and for any LQ with parameters θ T = (A, B) and cost matrices Q and R satisfying Asm. 2, let P (θ) be the unique solution of Eq. 3. Then, for any compact set

S 0 ⊂ {θ ∈ R (n+d)×n s.t. θ T = (A, B) stabilizable}, 1 (A, B
) is stabilizable if there exists a gain matrix K s.t. A + BK is stable, i.e., all eigenvalues are in (-1, 1).

the mapping θ ∈ S 0 → P (θ) is continuously differentiable. Furthermore, let A c (θ) = θ T H(θ) be the closed-loop matrix, then the directional derivative2 of P (θ) in a direction δθ, denoted as dP (θ)(δθ), is the solution of the Lyapunov equation

X = A c (θ) T XA c (θ) + C(θ, δθ) + C(θ, δθ) T ,
where C(θ, δθ) = A c (θ) T P (θ)δθ T H(θ).

The learning problem. Following the setting of Abbasi-Yadkori & Szepesvári (2011), we assume that Q and R are known, while θ * needs to be estimated from data. We consider the standard online learning setting where at each step t the learner receives the current state x t as input, it executes a control u t and it observes the associated cost c(x t , u t ); the system then transitions to the next state x t+1 according to Eq. 1. The learning performance is measured by the cumulative regret over T steps defined as

R T (θ * ) = T t=0 c t -J * (θ * ) .
Exploiting the linearity of the dynamics, the unknown parameter θ * can be directly estimated from data by regularized least-squares (RLS). For any sequence of controls (u 0 , . . . , u t ) and the induced states (x 0 , x 1 , . . . , x t+1 ), let z t = (x t , u t ) T , then the RLS estimator with regularization parameter λ ∈ R * + is computed as

θ t = V -1 t t-1 s=0 z s x T s+1 , with V t = λI + t-1 s=0 z s z T s . (4)
Proposition 2 (Thm. 2 in Abbasi-Yadkori et al. 2011). For any δ ∈ (0, 1) and any F t -adapted sequence (z 0 , . . . , z t ), the RLS estimator θt is such that

θ * -θ t Vt ≤ β t (δ), β t (δ) = n 2 log det(V t ) 1/2 det(λI) 1/2 δ + λ 1/2 Tr(θ * θ T * ), (5)
w.p. 1 -δ (w.r.t. the noise { t+1 } t and any randomization in the choice of the control).

Finally, we recall this standard result of RLS. Proposition 3 (Lem. 10 in Abbasi-Yadkori & Szepesvári 2011). Let λ ≥ 1, for any arbitrary F t -adapted sequence (z 0 , z 1 , . . . , z t ), let V t+1 be the corresponding design matrix, then

t s=0 min z s 2 V -1 s , 1 ≤ 2 log det(V t+1 ) det(λI) .
Moreover when z t ≤ Z for all t ≥ 0, then Following [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF], we define TS for LQ as a randomized algorithm that samples a system θ, computes the corresponding optimal policy π( θ) and performs the associated controls K( θ)x. As θ * is initially unknown and TS may sample systems that are not stabilizable, we first need to characterize the set of "admissible" systems that the learner may use. We first recall the following result.

t s=0 z s 2 V -1 s ≤ 2 Z 2 λ (n + d) log 1 + (t + 1)Z 2 λ(n + d) . (6
Proposition 4 (Cor. 12 in [START_REF] Klamka | Controllability of dynamical systems[END_REF]). For any dimensions n and d, the set of controllable dynamical systems is open and dense in the space R n(n+d) of all dynamical systems of the form (1).

Since controllability implies stabilizability, the previous result implies that the set of non-stabilizable systems is of zero Lebesgue measure. Since for a non-stabilizable system (A, B), there exists no control K that can make the dynamics stable, then the state process x t diverges exponentially and the associated "optimal" average cost is J(θ) = +∞. This property has two major implications: 1) it is possible to define the optimal value function over the whole space R n(n+d) in a continuous manner by setting its value to +∞ wherever θ is a non-stabilizable pair; 2) for any sampling distribution absolutely continuous w.r.t the Lebesgue measure, the associated optimal average cost is finite with probability one. However, TS may still sample parameters that are almost non-stabilizable (and hence of large cost), which is still harmful from both theoretical and practical perspective. This motivates the introduction of the constraint set

S = {θ s.t. J(θ) ≤ D, θ T H(θ) 2 ≤ ρ < 1, θ F ≤ S}.
This definition directly implies the following guarantees.

Proposition 5. S is a compact set. For any θ ∈ S, θ is a stabilizable pair and there exists C < ∞ positive constant such that C = sup θ∈S K(θ) 2 .

We now introduce the TS instance that we study. At each step t, given the RLS-estimate θ t , TS samples a perturbation matrix η ∈ R (n+d)×n from a component-wise normal distribution and computes the perturbed parameter θ t as

θ t d = R S ( θ t + β t V -1/2 t η), (7)
where

β t = β t (δ/8T
) is defined as in (5) with Tr(θ * θ T * ) replaced by S and R S is the rejection sampling w.r.t. the admissible set S. Then the control u t = K( θ t )x t is executed and the next state x t+1 and c t are observed. The new samples are then used to update θ t and V t .

Unlike many previous instances, we consider the most basic implementation of the TS principle. Alg. 1 does not require any initial exploration phase (see e.g., [START_REF] Faradonbeh | Finite time analysis of optimal adaptive policies for linear-quadratic systems[END_REF] in the case of OFU) and it directly executes the control associated with the sampled environment, instead of using optimistic sampling as in [START_REF] Agrawal | Optimistic posterior sampling for reinforcement learning: worst-case regret bounds[END_REF] for finite MDPs. Unlike the instances of TS studied by [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF][START_REF] Abbasi-Yadkori | Bayesian optimal control of smoothly parameterized systems[END_REF], and [START_REF] Ouyang | Learning-based control of unknown linear systems with thompson sampling[END_REF], we consider a "frequent-update" version of TS, where a new parameter θ t is sampled at each step, without the need of introducing any notion of episode and stopping criterion. Furthermore, in order to avoid almost non-stabilizable systems, we only require a rejection sampling step over S, which is always computationally feasible. This is in contrast with requiring a stabilizing controller as [START_REF] Abbasi-Yadkori | Bayesian optimal control of smoothly parameterized systems[END_REF], assuming recurrent states as [START_REF] Gopalan | Thompson sampling for learning parameterized markov decision processes[END_REF], stating by assumption that any sampled θ is stabilizable as [START_REF] Ouyang | Learning-based control of unknown linear systems with thompson sampling[END_REF], or assuming that the dynamics under different parameters is easily distinguishable [START_REF] Kim | Thompson sampling for stochastic control: The finite parameter case[END_REF]. Finally, notice that the computational cost of frequent updates could be mitigated by sampling every fixed number of steps.

Theoretical analysis

In order to make the learning problem well-posed, we first state the following assumption3 . Assumption 3. Let S be the set of admissible systems, then θ * ∈ S.

In the rest of the paper, we prove this novel bound of the frequentist regret.

Theorem 1. Consider the LQ system in Eq. 1 of dimension n = 1 and arbitrary d. Under assumptions 1, 2 and 3, for any 0 < δ < 1, the cumulative regret of TS (Alg. 1) over T steps is bounded w.p. at least 1-δ as4 R T = O √ T where O hides logarithmic factors in T and 1/δ, and problem dependent constants.

As discussed in Sect. 3, here we analyze a very basic instance of TS, which removes any restriction on the algorithm. This result greatly improves the previous analysis by [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF] by reducing the regret from O(T 2/3 ) down to O( √ T ), thus matching the performance of OFU for LQ problems (Abbasi-Yadkori & Szepesvári, 2011;[START_REF] Faradonbeh | Finite time analysis of optimal adaptive policies for linear-quadratic systems[END_REF]. Together with the recent result of [START_REF] Agrawal | Optimistic posterior sampling for reinforcement learning: worst-case regret bounds[END_REF], Thm. 1 confirms the conjecture of Osband & Van Roy (2016) that O( √ T ) regret guarantees of TS extends to learning in the infinite-horizon setting. Furthermore, this result shows that the frequentist regret is as small as existing Bayesian regret guarantees for (variants) of TS [START_REF] Ouyang | Learning-based control of unknown linear systems with thompson sampling[END_REF]. Finally, beside the improvement on the rate, Thm. 1 also removes the (somewhat unnatural) inverse dependency on J(θ * ) in the previous bound (see Eq.11 in Abeille & Lazaric, 2017). The main limitation of this result lies on the restriction to n = 1 dimensional problems. This limitation is due to the proof lower-bounding the probability of being optimistic (Lem.3 in Abeille & Lazaric, 2017), which we could not extend beyond n = 1. On the other hand, as illustrated in the next section, all the new results we develop in this paper (in particular the bound on the regret of policy switches) hold in the general case n ≥ 1, d ≥ 1. See also Sect. 6 for further discussion.

Challenges and Main Tools

In this section we discuss the technical challenges in proving the final O( √ T ) regret bound and we report the core results that enable the final result in Thm. 1.

Regret decomposition. We introduce the same events as in [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF].

Definition 1. Let δ ∈ (0, 1) and δ = δ/(8T ) and t ∈ [0, T ]. We define two concentration ellipsoids

E RLS t = {θ ∈ R (n+d)n s.t. θ -θ t Vt ≤ β t }, E TS t = {θ ∈ R (n+d)n s.t. θ -θ t Vt ≤ γ t },
where γ t := n 2(n + d) log (2n(n + d)/δ )β t and intro- duce the event (RLS estimate concentration) E t = ∀s ≤ t, θ s ∈ E RLS s and the event (parameter θ s concentrates around θ s ) E t = ∀s ≤ t, θ s ∈ E TS t
. Furthermore, let X, X be two problem dependent positive constants, we define the event (bounded state) Ēt = ∀s ≤ t, x s ≤ X log X δ . Finally, we define E t = E t ∩ E t ∩ Ēt . Proposition 6 (Cor.1 in [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF]). The events in Def. 1 jointly hold with high probability, i.e., P(

E T ∩ E T ∩ ĒT ) ≥ 1 -δ/2.
Conditioned on the filtration F t and event E t , we have θ ∈ E RLS t , θ t ∈ E TS t and x t ≤ X. We decompose the regret and bound it on this event in line with (Sect. 4.2 Abbasi-Yadkori & Szepesvári, 2011) as

RT 1{ET } ≤ T t=0 {J( θt) -J(θ * )}1 {E t } (R TS ) + T t=0 {z T t θtP ( θt) θ T t zt -z T t θ * P ( θt)θ T * zt}1 {E t } (R RLS ) + T t=0 {V (xt; θt)1 {E t } -E V (xt+1; θt+1)1 {E t+1 } |Ft } (R mart ) + T t=0 E (V (xt+1; θt+1) -V (xt+1; θt))1 {E t+1 } |Ft . (R gap )
As discussed in [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF], while R RLS and R mart can be easily bounded using Prop. 3 and Azuma's inequality, the main technical challenge is to prove the boundedness of R TS and R gap . 5 In fact, the former requires TS to sample optimistic parameters θ t as often as possible, so that J( θ t ) ≤ J(θ * ) and R TS is cumulatively small. As Abeille & Lazaric (2017) (Lemma 3) proved that TS has a fixed probability to sample optimistic parameters, this suggests implementing a frequent update scheme, where a new parameter is sampled at each time step (as in Alg. 1). Nonetheless, this may cause a linear regret in R gap , as the difference between the differential value function at state x t+1 for any two different parameters θ, θ is bounded by a constant. In fact, let assume x t+1 ≤ X and θ, θ ∈ S, then

x T t+1 P (θ ) -P (θ) x t+1 = V (x t+1 ; θ ) -V (x t+1 ; θ) ≤ X 2 P ( θ) -P ( θ ) 2 ≤ 2X 2 D, (8)
where we use the fact that P (θ) 2 ≤ TrP (θ) = J(θ) ≤ D for any θ in S. Based on this observation, [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF] claimed that TS should trade off between frequent (and thus optimistic) updates and lazy updates to avoid regret associated to policy changes. Unfortunately, the resulting balance leads to an overall O(T 2/3 ) regret. Nonetheless, while the bound in Eq. 8 is correct in the worst case, in the next lemma, we prove that the expected difference in the regret decomposition is such that R gap is cumulatively bounded by O( √ T ), even when a new parameter is sampled at each step. Lemma 1. Consider the LQ system in Eq. 1 of dimension n and d. Under Asm. 1 and 2, for any 0 < δ < 1, the regret R gap incurred by running the TS (Alg, 1) is bounded w.p. at least 1 -δ/6 as6 R gap = O √ T .

While the full proof of the lemma is postponed to Sect. 5, we provide a first intuition behind this result. By inspecting the definition of R gap and Eq. 8 we notice that if θ and θ were generated by the same distribution (i.e., they were independent realizations of the TS distribution at time t), then the expectation of the norm P ( θ) -P ( θ ) 2 could be simply upper-bounded by twice the expected absolute deviation, which is bounded in the next lemma (the need for the two slightly different definitions is detailed in Sect. 5). Lemma 2. For arbitrary dimensions n and d, for any t ≥ 1, let θ t be the un-rejected sampling parameter, i.e., θ

t d = θ t + β t V -1/2 t η, where η ∈ R (n+d)×n is component-wise normal.
We introduce two expected values for P

P t = E P ( θ t )|F x t , E t ; P t = E P ( θt )1 S ( θt )|F x
t , E t , and we define the corresponding expected absolute deviation

∆ t = E P ( θ t ) -P t 2 F x t , E t ; (9)
∆ t = E P ( θ t ) -Pt 2 F x t , E t . ( 10
)
Then for any 0 < δ < 1, w.p. at least 1 -δ/12,

T t=0 ∆ t = O √ T and T t=0 ∆t = O √ T .
Intuitively, the absolute deviation measures the expected diameter of the TS sampling ellipsoid using the 2 -norm of the Riccati solution P (θ) as a metric. The fact that this is cumulative small indicates that the TS generates distributions (i.e., the sampling ellipsoid) that are well-adapted to the sensitivity of the Riccati solution, so that deviations in P (θ) are kept small. The impact of such behavior is even clearer if we consider the average gain J(θ) = Tr(P (θ)). Since A 2 ≤ Tr(A), we have that Lemma 2 directly implies that

T t=0 E J( θ t ) -E J( θ t ) F x t , E t F x t , E t ≤ O( √ T ).
Notice that while this quantity was previously bounded by [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF], the result of Lem. 2 is more general and it also removes problem-dependent quantities such as J(θ * ).

Unfortunately, Lem. 2 is not sufficient to bound R gap , as θ t and θ t+1 follow different distributions. Then we also need to control how the evolution of the distribution of θ over two consecutive time steps influences the value of P ( θ). By carefully decomposing R gap , we only need to measure the effect of shifting distributions for "un-rejected" parameters (i.e., obtained by removing the rejection sampling step), which is bounded in the next lemma. Lemma 3. Let P t as defined in Lem. 2, then the difference between two consecutive steps is bounded almost surely as

T t=0 P t+1 -P t F 1 {Et+1} ≤ O( √ T ).
The combination of lemmas 2 and 3 finally leads to Lem. 1.

The final regret bound is then obtained following similar steps as in [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF] to bound the remaining terms (notably R TS ).

Proof

In this section we prove the lemmas reported in the previous section, while technical details are left to the supplement.

Bounding the average absolute deviation

Lem. 2 bounds two different instances of the average absolute deviation ∆ t and ∆t , which only differ in the way the rejection sampling is treated. We focus here on bounding ∆ t and postpone the other part of the proof to App. B.1. We follow similar steps as Abeille & Lazaric (2017):7 1) we use the weighted Poincaré inequality to relate ∆ t to the average gradient norm, 2) we link this gradient to the control K( θ t ) selected by TS over time on average, 3) we introduce the state x t to obtain a bound that depends on z t V -1 t which is cumulatively bounded by Prop. 3.

First, we use the relationship θ t d = θt |S to deal with the rejection sampling and we use the fact that for any matrix

A ∈ R n×n , A F ≤ n i,j=1 |A[i, j]| to rewrite ∆ t as ∆ t = E P ( θt ) -P t F 1 S ( θt ) F x t , E t P( θt ∈ S|F x t , E t ) ≤ n i,j=1 ∆ ij t P( θt ∈ S|F x t , E t )
,

where

∆ ij t = E |P ( θt )[i, j] -P t [i, j]|1 S ( θt ) F x t , E t .
We apply the following Poincaré inequality.

Proposition 7 (Lemma. 4 in [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF]).

Let Ω ⊂ R d be a convex domain with finite diameter diam and denote as W 1,1 (Ω) the Sobolev space of order 1 in L 1 (Ω). Let p be a non-negative log-concave function on Ω with continuous derivative up to the second order. Then, for all u ∈ W 1,1 (Ω) such that Ω u(z)p(z)dz = 0 one has

Ω |f (z)|p(z)dz ≤ 2diam Ω ||∇f (z)||p(z)dz.

Recalling the definition of θt

d = θ t + β t V -1/2 t η, we can rewrite ∆ ij
t as a function of the random variable η as

∆ ij t = E η |f ij t (η)| F x t , E t
where f ij t is properly defined. From Prop. 1, we have that θ → P (θ) is continuously differentiable on S, which implies that f ij t is continuously differentiable almost everywhere on R n (n+d) . Furthermore, the conditioning on E t imposes that θ t ∈ E TS t and thus f ij t ∈ W 1,1 (Ω) where Ω = {η ∈ R n(n+d) s.t. η ≤ γ t /β t }. Let Φ η be the pdf of η. On Ω, up to a normalization factor, Φ η is the product of standard gaussian pdf and hence log-concave and twice differentiable. Finally, it is easy to check that E(f ij t (η)|F x t , E t ) = 0. Therefore, we can apply Prop. 7 as

∆ ij t ≤ 2γ t /β t E ∇f ij t (η) F F x t , E t , = 2γ t /β t E β t V -1/2 t ∇P ( θt )[i, j] F 1 S ( θt ) F x t , E t .
Plugging everything together and reintegrating the conditioning on S, one obtains:

∆ t ≤ 2γ t n i,j=1 E ∇P ( θ t )[i, j] V -1 t F x t , E t . ( 11
)
We use the following property which links the gradient of P (θ)[i, j] to the optimal controller H(θ) (proof in App. A).

Proposition 8. For any θ ∈ S, for any i, j,

∇P (θ)[i, j] V -1 t ≤ 2ρD 1 -ρ 2 H(θ) V -1 t .
Using Prop. 8 in Eq. 11, one obtains:

∆ t ≤ 4ρDγ t n 2 1 -ρ 2 E H( θ t ) V -1 t F x t , E t . (12)
Finally, the last step of the proof consists in integrating the state x t in Eq. 12, in order to obtain a bound that depends on z t V -1 t using the fact that z t = H( θ t )x t . We rely on the following proposition (proof in App. B.2).

Proposition 9. Let α t = 2n log(3n) + xt where xt = E(x t |F t-1 , θt , E t-1 ). Then,

E x t x T t 1 { xt ≤αt} |F t-1 , θt , E t-1 1 8(1 + 1/β 2 t ) I. Further, if θt ∈ E TS , 1 { xt ≤αt} ≤ 1 { xt ≤α} where α = (1 + 1/β 2 t ) 2n log(3n) + γ t + (1 + C)SX .
Since on E t , θt ∈ E TS t and θ t = θ t |S, we can apply Prop. 9 to the conditional expectation in Eq. 12 to bound

H( θt ) V -1 t ≤ 8 1 + 1 βt H( θt )E x t x T t 1 { xt ≤α} |F t-1 , θt , E t-1 V -1 t , ≤ 8 1 + 1 βt E H( θt )x t x T t 1 { xt ≤α} |F t-1 , θt , E t-1 V -1 t , ≤ 8α 1 + 1 βt E H( θt )x t V -1 t 1 { xt ≤α} |F t-1 , θt , E t-1 ,
and finally obtain

∆ t ≤ 8α 1+ 1 β t 4ρDγtn 2 1-ρ 2 Y t , where Y t = E E z t V -1 t 1 { xt ≤α} |F t-1 , θ t , E t-1 F x t , E t .
By the law of iterated expectation,

E(Y t |F t-1 ) = E( z t V -1 t 1 { xt ≤α} |F t-1 ) and z t V -1 t 1 { xt ≤α} ≤ (1 + C)α/λ. As a result, {Y t -z t V -1 t 1 { xt ≤α} } t≥0
is a F t-1 bounded martingale difference sequence and by Azuma's inequality and Prop. 3 w.p. at least 1 -δ/12

T t=0 ∆ t ≤ γ abs T t=0 z t V -1 t + 2α λ (1 + C) 2T log 12 δ ,
which concludes the proof.

Bounding the consistency regret

We now bound the consistency regret in term of the average absolute deviation ∆t and the KL divergence between two subsequent sampling distributions. Let R gap t = x T t+1 P ( θ t+1 ) -P ( θ t ) x t+1 1 Et+1 (i.e., an element in R gap without the expectation). On E t+1 , x t+1 ≤ X and thus

R gap t ≤ X 2 P ( θ t+1 ) -P ( θ t ) F 1 Et+1 ≤ X 2 ( P ( θ t+1 ) -Pt+1 F + P ( θ t ) -Pt F + Pt+1 -Pt F 1 Et+1 )
where Pt is defined in the statement of the lemma. Plugging this inequality into R gap = T t=0 E(R gap t |F t ), using the law of iterated expectation, and Azuma's inequality, we obtained that w.p. at least 1 -δ/12

R gap ≤X 2 T t=0 E( ∆t+1 |F t ) + X 2 T t=0 E( ∆t |F t ) + X 2 T t=0 E( Pt+1 -Pt F 1 Et+1 )|F t ) ≤X 2 T t=0 ( ∆t+1 + ∆ t ) + X 2 T t=0 Pt+1 -Pt F 1 Et+1 + 12 √ nDX 2 2T log(12/δ).
While the first two terms can be directly bounded by Lem. 2, we need to prove Lem. 3 to conclude the proof of Lem. 1.

For any t ≥ 0, denote by Φ t and φ t the pdf of θt |F x t , E t and θt |F x t respectively. Since the conditioning on E t is equivalent to θt ∈ E TS t , one has Φ t (θ) = φ t (θ)1 E TS t (θ)/P( θt ∈ E TS t ). Rewriting Pt and Pt+1 using integrals gives

Pt+1 -Pt F = S P (θ)Φ t+1 (θ)dθ - S P (θ)Φ t (θ)dθ F ≤ S P (θ) F |Φ t+1 (θ) -Φ t (θ)|dθ ≤ √ nD S |Φ t+1 (θ) -Φ t (θ)|dθ. Furthermore S |Φ t+1 (θ) -Φ t (θ)|dθ ≤ |Φ t+1 (θ) -φ t+1 (θ)|dθ + S |φ t+1 (θ) -φ t (θ)|dθ + |φ t (θ) -Φ t (θ)|dθ,
and algebraic manipulations show that

|φ t (θ) -Φ t (θ)|dθ ≤ 2 1 -P( θt ∈ E TS t ) ≤ 2δ , |φ t+1 (θ) -Φ t+1 (θ)|dθ ≤ 2 1 -P( θt+1 ∈ E TS t+1 ) ≤ 2δ .
Finally, using Pinsker's inequality, we have

S |φ t+1 (θ) -φ t (θ)|dθ ≤ 2KL(φ t ||φ t+1 ),
which means that the consistency regret is kept under control as long as the KL divergence between two subsequent unrejected distributions is cumulatively small. This is provided by the following proposition (proof in App. C).

Proposition 10. For any t ≥ 0, on E t+1 ,

KL(φ t ||φ t+1 ) ≤ γ KL z t 2 V -1 t .
Using Prop. 3, we obtain that w.p. 1 -δ/6, R gap = O( √ T ).

Discussion

While Thm. 1 reports the first O( √ T ) frequentist regret bound for standard TS in infinite-horizon LQ problems, the final result is still limited to n = 1 systems because of the lower bound on the probability of being optimistic. In this section we provide preliminary evidence that the difficulty in extending the lower bound to n ≥ 1 is not related to an intrinsic difference in the "nature" of the problem8 , but rather to technical challenges in the proof. We then conjecture that the O( √ T ) bound holds in systems of arbitrary dimension.

Stacked systems. Consider a n-dimensional system consisting in n independent 1-dimensional problems. The structure of the system is then diagonal, i.e., A * = diag(a 1 * , . . . , a n * ),

A * = diag(b 1 * , . . . , b n * ) (similar for Q and R).
Let assume that the learner is aware of this structure. In this case, each system can be estimated and sampled independently, so one can write θ t = [ θ 1 t , . . . , θ

Tr(P (θ * )) = n i=1 J(θ i * ).
As a consequence, the probability of being optimistic can be lower bounded as P Tr(P ( θ t )) ≤ Tr(P (θ * ))

≥ P J( θ i t ) ≤ J(θ i * ), ∀i = 1..n ≥ n i=1 P J( θ i t ) ≤ J(θ i * ) .
By independence, the probability of being optimistic reduces to the probability of being jointly optimistic in each direction. In order to compensate for the reduction of probability due to the product in the previous expression, it is sufficient to slightly increase the "size" of the TS distribution by a √ n factor. While Prop. 2 can be written as

Tr ( θi t -θ i * ) T V i t ( θi t -θ i * ) ≤ β i t (δ) 2 , ∀i ∈ [1, . . . , n],
we need to sample parameters component-wise as [1, . . . , n]. This √ n over-sampling ensures the joint probability to be constant (Lem. 3 of [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF]). Despite the lack of generality due to the diagonal structure, this example stresses the intuition that over-sampling (coming from β) prevents the probability of being optimistic to poorly scale with the dimension, and that the difficulty in the analysis lies in the characterization of the optimistic set Θ opt . While in the diagonal case one can focus on the joint probability of each system being optimistic, this is no longer possible in the general case, as increasing the cost along one direction may be compensated by decreasing it in another direction. In fact, as J(θ) = Tr(P (θ)), we need to control the overall sum of the eigenvalues of P (θ). Unfortunately, we are not aware of any perturbation theory for the trace of Riccati/Lyapunov solutions, which makes the analysis challenging. A more restrictive analysis may rather focus on a super-set of optimistic parameters Θ opt,+ such that P (θ) P (θ * ), thus requiring optimism in every direction. A preliminary study of this problem shows that it is possible to derive a lower bound on the mass of Θ opt,+ which depends on t, thus failing to provide an "any-time" lower bound on the probability of being optimistic as required by the current proof.

θ i t = R S θ i t + β i t V i,-1/2 t η i t , with β i t ≥ √ nβ i t for all i ∈
Numerical simulations. Since all the results in Sect. 5 hold for n ≥ 1, we try to simulate several random LQ systems of variable dimensionality and numerically estimate the probability of being optimistic (p opt ) in each of them. We first analyze the "evolution" of p opt over time. We construct S by setting D = 20J(θ * ). For different values of n and d, we sample θ * as θ * [i, j] ∼ N (0, 1) independently and we run multiple trajectories of TS of length T = 500 steps. At each step t, we sample 1000 θ t from the TS distribution (with rejection), we compute the corresponding average cost J( θ t ) and we compare it to J(θ * ). Since the early steps of the trajectories mostly depend on the initialization of the RLS, we wait for t ≥ 10 to estimate p opt . The fraction of θ t with J( θ t ) ≤ J(θ * ) corresponds to our estimate of p opt,t . In Fig. 2 we report the minimum, maximum, and average value of p opt,t across 100 trajectories. We notice that for all values of n and d, p opt rapidly increases and converges to a fixed value. Even considering the minimum value obtained across all trajectories at each step t, p opt is always lower bounded away from 0. In order to better validate the fact that p opt is lower bounded, we report additional results in Tab. 1, where we report the minimum value of p opt,t at time t = 100 across 100 trajectories and 5000 values of θ * for many combinations of n and d.9 Notice that this analysis is over-pessimistic since in order to prove the O( √ T ) regret we only need to lower bounded the probability of being optimistic conditioned on the high-probability event related to the RLS ellipsoid, which is somehow ignored here. Nonetheless, Tab. 1 illustrates that p opt,t is indeed strictly bigger than zero, thus providing a numerical support to the conjecture that Lem.3 in [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF] does extend to LQ systems of arbitrary dimension.

A. Control theory

A.1. Proof of Prop. 5 1. By construction, for any θ ∈ S, θ T H(θ) 2 ≤ ρ < 1 thus, |λ max θ T H(θ) | < 1. As a result, there exists a K such that A + BK is stable, which is the definition of a stabilizable pair.

2. The mapping θ → θ T H(θ) 2 is continuous (from the continuity of P (θ), see Lem. 1). Thus, S is compact as the intersection between a closed and a compact set.

3. The continuity of the mapping θ → K(θ) together with the compactness of S justifies the finite constants C. Moreover, since for every θ ∈ S, J(θ) ≥ Tr(Q) > 0, D > 0.

Proposition 8. For any θ ∈ S, for any i, j,

∇P (θ)[i, j] V -1 t ≤ 2ρD 1 -ρ 2 H(θ) V -1 t .
Proof. We first show that for any θ ∈ S, ∇P (θ

)[i, j] V -1 t ≤ sup δθ F =1 dP (θ)(V -1/2 t δθ) 2 .
The proof can be decomposed in two step:

1. ∀θ ∈ S, ∇P (θ)[i, j] V -1 t = sup δθ F =1 |dP (θ)(V -1/2 t δθ)[i, j]|, 2. ∀θ ∈ S, ∀δθ ∈ R n(n+d) , |dP (θ)(δθ)[i, j]| ≤ dP (θ)(δθ) 2 .
Using matrix norm equivalence, it is easy to see that, for any θ ∈ S, for any δθ ∈ R n(n+d) ,

|dP (θ)(δθ)[i, j]| ≤ dP (θ)(δθ) max ≤ dP (θ)(δθ) 2 .
which proves the second point. For the first equality, using the relationship between differential and gradient, one has that, for all θ ∈ S, for all δθ F = 1,

|dP (θ)(V -1/2 t δθ)| = |Tr ∇P (θ)[i, j](V -1/2 t δθ) T ≤ ∇P (θ)[i, j] V -1/2 t δθ F ≤ ∇P (θ)[i, j] V -1/2 t .
However, the equality holds for δθ = V -1/2 t ∇P (θ)[i, j]/ ∇P (θ)[i, j] V -1/2 t which proves point 1. As a result, one obtains that, for all θ ∈ S, ∇P

[i, j] V -1 t ≤ sup δθ F =1 dP (θ)(V -1/2 t δθ) 2 . (θ)
Now, from Prop. 1, we have, for any θ ∈ S, for any δθ F = 1,

dP (θ)(V -1/2 t δθ) 2 ≤ A c (θ) 2 2 dP (θ)(V -1/2 t δθ) 2 + 2 A c (θ) 2 P (θ) 2 δθ T V -1/2 t H(θ) 2 ≤ A c (θ) 2 2 dP (θ)(V -1/2 t δθ) 2 + 2 A c (θ) 2 P (θ) 2 δθ T V -1/2 t H(θ) F ≤ A c (θ) 2 2 dP (θ)(V -1/2 t δθ) 2 + 2 A c (θ) 2 P (θ) 2 δθ F H(θ) V -1 t ,
where we used the matrix norm equivalence from line 1 to line 2 and Cauchy-Schwartz from line 2 to line 3. Finally, on S,

A c (θ) 2 ≤ ρ and P (θ) 2 ≤ TrP (θ) ≤ D. Thus, dP (θ)(V -1/2 t δθ) 2 ≤ 2Dρ/(1 -ρ 2 ) H(θ) V -1 t which concludes the proof. B. Proof of Lemma. 2 B.1. Bounding ∆t
The proof of Lemma. 2 derived in Subsec. 5.1 focuses on bounding ∆ t . A similar derivation can be done to guarantee a upper bound for ∆t . For the sake of completeness, we detail here the part of the proof that are different. First, we deal with the rejection sampling as ∆t = 1

P( θt ∈ S|F x t , E t ) E P ( θt ) -Pt F 1 S ( θt ) F x t , E t , ≤ 1
P( θt ∈ S|F x t , E t ) n i,j=1 E |P ( θt )[i, j] -Pt [i, j]|1 S ( θt ) F x t , E t , = 1 P( θt ∈ S|F x t , E t ) n i,j=1 E |P ( θt )[i, j]1 S ( θt ) -Pt [i, j]|1 S ( θt ) F x t , E t , ≤ 1
P( θt ∈ S|F x t , E t ) n i,j=1 E |P ( θt )[i, j]1 S ( θt ) -Pt [i, j]| F x t , E t .
For any i, j, we redefine

∆ ij t = E |P ( θt )[i, j]1 S ( θt ) -Pt [i, j]| F x t , E t and rewrite the expectation w.r.t. η as ∆ ij t = E η |f ij t (η)| F x t , E t where f ij t (η) = P ( θ t + β t V -1/2 t η)[i, j])1 S ( θ t + β t V -1/2 t η) -Pt [i, j].
In line with Subsec. 5.1,

f ij t ∈ W 1,1 (Ω) where Ω = {η ∈ R n(n+d) s.t. η ≤ γ t /β t } and E(f ij t (η)|F x t , E t ) = E(P ( θt )1 S ( θt )|F x t , E t ) -Pt = 0.
Therefore, one can apply Lemma. 7 and gets:

∆ ij t ≤ 2γ t /β t E ∇f ij t (η) F F x t , E t = 2γ t /β t E β t V -1/2 t ∇P ( θt )[i, j] F 1 S ( θt ) F x t , E t .
Plugging everything together and reintegrating the conditioning on S, one obtains:

∆t ≤ 2γ t n i,j=1 E ∇P ( θ t )[i, j] V -1 t F x t , E t ,
which is identical to Eq. 12 so the same line of proof apply from this stage.

B.2. Proof of Prop. 9

We prove Prop. 9 in three steps. First, we deal with the conditioning, then with the boundedness of the state and finally, we bound 1 { xt ≤αt} when θt ∈ E TS t .

Proposition 11. Let θt

d = θ t + β t V -1/2 t
η where η[i, j] ∼ N (0, 1) for all i, j. Let x t be the state generated by any F x t -measurable sequence of control {u t } t , then,

V x t |F t-1 , θt , E t-1 1 1 + 1/β 2 t I.
Proof. This proposition is based on the following property for Gaussian random variables: let X ∼ N (µ x , Σ x ), Y ∼ N (µ y , Σ y ) and Cov(X, Y ) = Σ xy , then,

V(X|Y ) = Σ x -Σ xy Σ -1 y Σ T xy and E(X|Y ) = µ x + Σ xy Σ -1 y (Y -µ y ).
This property still holds for matrix Gaussian distribution (by vectorization).

To exhibit the dependency, we write θt = a t-1 + V -1 t z t-1 x T t + β t V -1/2 t η t where a t-1 , z t-1 and V t are F t-1 -measurable quantities and η t |F t-1 ∼ N (0, I). Then, applying the Gaussian property to X = x t |F t-1 and Y = θt |F t-1 one obtains by vectorization, re-ordering and a little bit of algebra:

V x t |F t-1 , θt , E t-1 = 1 + 1 β 2 t z t-1 2 V -1 t -1 I, E x t |F t-1 , θt , E t-1 = E(x t |F t-1 , E t-1 ) + θt -E( θt |F t-1 , E t-1 ) T V -1 t z t-1 z T t-1 V -1 t + β 2 t V -1 t -1 V -1 t z t-1 . (13)
Finally, since z t-1

2 Vt -1 = z T t-1 (V t-1 + z t-1 z T t-1 ) -1 z t-1 = zt-1 2 V -1 t-1 1+ zt-1 2 V -1 t-1
≤ 1, one obtains the desired result.

Proposition 12. Let θt

d = θ t + β t V -1/2 t
η where η[i, j] ∼ N (0, 1) for all i, j. Let x t be the state generated by any F x t -measurable sequence of control {u t } t , let α t = 2n log(3n) + xt where xt = E(x t |F t-1 , θt , E t-1 ), then,

E x t x T t 1 { xt ≤αt} |F t-1 , θt , E t-1 1/8V(x t |F t-1 , θt , E t-1 ).
The proof of Prop. 12 relies on properties of truncated Gaussian random variable. The main ingredient is that, if the truncation takes place far enough from the mean, the Gaussian properties are preserved and the second order moment is greater than the variance.

Property 1. Let ∼ N (0, 1), for any a ≥ 2 log(6),

V( | | | ≤ a) ≥ 1/2.
Proof. Explicit formula for the truncated normal distribution moment leads to

V( | | | ≤ a) = 1 - 2a √ 2π e -a 2 /2 P(| | ≤ a) ≥ 1 - ae -a 2 /2 P(| | ≤ a)
.

Standard inequality for the Gaussian cdf guarantees that P(| | ≤ a) ≤ e -a 2 /2 . Hence, for all a ≥ 2 log(6),

V( | | | ≤ a) ≥ 1 - ae -a 2 /2 1 -e -a 2 /2 ≥ 2 log(6) 5 ≥ 1/2
Property 2. Let ∼ N (0, 1), for any n ≥ 2, for any a ≥ 2 log(n), P(| | ≤ a) n ≥ 1/4.

Proof. Again, since P(| | ≤ a) ≤ e -a 2 /2 , one has, for any a ≥ 2 log(n),

P(| | ≤ a) ≤ (1 -1/n) n ≥ 1/4
Proof of Prop. 12. Denote as xt = E(x t | θt , F t-1 , E t-1 ) and Σ t = V(x t | θt , F t-1 , E t-1 ). By Prop. 11 Σ t 2 ≤ 1, hence, one has,

E(x t x T t 1 { xt ≤αt} |F t-1 , θt , E t-1 ) ≥ E(x t x T t 1 { xt-xt ≤αt-ρ xt } |F t-1 , θt , E t-1 ), ≥ Σ 1/2 t E(y t y T t 1 { yt-ȳt ≤αt-ρ xt } |F t-1 , θt , E t-1 )Σ 1/2 t , ≥ Σ 1/2 t E(y t y T t 1 {|y i t -ȳ i t |≤ α t -ρ xt √ n ,∀i≤n} |F t-1 , θt , E t-1 )Σ 1/2 t ,
where y t = Σ -1/2 t

x t , ȳt = Σ -1/2 xt and y i denotes the i th coordinate of the n-dimensional vector y. By definition y t |θ t,Ft-1,Et-1 ∼ N (ȳ t , I) thus,

E(y t y T t 1 {|y i t -ȳ i t |≤ α t -ρ xt √ n ,∀i≤n} |F t-1 , θt , E t-1 ) = P(|y i t -ȳ i t |≤ α t -ρ xt √ n ,∀i≤n)E(y t y T t |F t-1 , θt , E t-1 , {|y i t -ȳ i t |≤ α t -ρ xt √ n ,∀i≤n}) ≥ P(|y i t -ȳ i t |≤ α t -ρ xt √ n ,∀i≤n)V(y t |F t-1 , θt , E t-1 , {|y i t -ȳ i t |≤ α t -ρ xt √ n ,∀i≤n}) = P(| | ≤ α t -ρ xt √ n ) n V( | | | ≤ α t -ρ xt √ n )I,
where ∼ N (0, 1). ,∀i≤n} |F t-1 , θt , E t-1 ) ≥ 1/8I. As a results,

E(x t x T t 1 { xt ≤αt} |F t-1 , θt , E t-1 ) ≥ 1/8Σ t = 1/8V(x t |F t-1 , θt , E t-1 )
Proof of Prop. 9. Using Prop. 11 and Prop. 12, one directly proves the first assertion of Prop. 9. The remaining challenge is to bound

1 { xt ≤αt} when θt ∈ E TS t . Plugging θt = a t-1 + V -1 t z t-1 x T t + β t V
-1/2 t η t into Eq. 13, one can obtain the following bound for α t , conditioned on θt ∈ E TS t . Since this is equivalent to the conditioning η t ≤ γ t /β t , one has:

α t ≤ 2n log(3n) + E(x t |F t-1 , θt , E t-1 ) , ≤ 2n log(3n) + z t-1 V -1 t 1 + 1 β 2 t z t-1 2 V -1 t β t E( η t F t-1 , E t-1 ) + E(x t F t-1 , E t-1 ) 1 + 1 β 2 t z t-1 2 V -1 t + 1 - 1 1 + 1 β 2 t z t-1 2 V -1 t x t , ≤ 2n log(3n) + z t-1 V -1 t 1 + 1 β 2 t z t-1 2 V -1 t γ t + 1 1 + 1 β 2 t z t-1 2 V -1 t θ T * z t + 1 - 1 1 + 1 β 2 t z t-1 2 V -1 t x t , ≤ 2n log(3n) + γ t + (1 + C)SX + (1 - 1 1 + z t-1 2 V -1 t /β 2 t ) x t ,
Where we used the fact that z

t-1 2 V -1 t ≤ 1, θ * F ≤ S and z t-1 ≤ (1 + C)X on E t-1 . Therefore, x t ≤ α t =⇒ x t ≤ (1 + 1/β 2 t ) 2n log(3n) + γ t + (1 + C)SX . As a result, if θt ∈ E TS , 1 { xt ≤αt} ≤ 1 { xt ≤α} where α = (1 + 1/β 2 0 ) 2n log(3n) + γ T + (1 + C)SX .

C. Proof of Prop. 10

The whole derivation is made on E t+1 . Let φ t be the pdf of θt |F x t . Recalling that θt

d = θ t + β t V -1/2 t
η where η[i, j] ∼ N (0, 1) independently, one has:

φ t (θ) = |V t | n/2 β n(n+d) t (2π) n(n+d)/2 exp - 1 2β 2 t θ -θ t 2 Vt . (14)
Similarly to the standard multidimensional gaussian case, we can derive a closed-form expression for the KL divergence KL(φ t ||φ t+1 ). Formally,

KL(φ t ||φ t+1 ) = n 2 log |V t | |V t+1 | + n(n + d) log β t+1 β t + 1 2β 2 t+1 θ t+1 -θ t 2 Vt+1 + β 2 t 2β 2 t+1 Tr V -1 t V t+1 -Tr(I n+d ). Since V t+1 = V t + z t z T t , |V t | ≤ |V t+1 | and β t+1 ≥ β t ≥ β 0 = n 2 log(1/δ ) + √ λS. Thus, KL(φ t ||φ t+1 ) ≤ n(n + d) log β t+1 β t + 1 2β 2 t+1 θ t+1 -θ t 2 Vt+1 + 1 2 Tr V -1 t V t+1 -I .
We bound the three terms separately.

1. 1 2 Tr V -1 t V t+1 -I = 1 2 Tr V -1 t z t z T t = 1 2 z t 2 V -1 t .
2. From the Least Square updates, one has

θ t+1 = θ t + V -1 t zt 1+ zt 2 V -1 t (x t+1 -θ T t z t ) T . Then, 1 2β 2 t+1 θ t+1 -θ t 2 Vt+1 ≤ 1 2β 2 0 V -1 t z t 2 Vt+1 (1 + z t 2 V -1 t ) 2 x t+1 -θ T t z t 2 Further, V -1 t z t 2 Vt+1 = z t 2 V -1 t (1 + z t 2 V -1 t ), x t+1 -θ T t z t 2 = θ T * z t + t+1 -θ T t z t 2 ≤ β 2 t z t 2 V -1 t + W ≤ β 2 t ((1 + C)X) 2 /λ + W,
where on the last inequality, we use that, on E t+1 , Prop. 2 holds and t+1 ≤ W . As a result,

1 2β 2 t+1 θ t+1 -θ t 2 Vt+1 ≤ β 2 t ((1 + C)X) 2 /λ + W 2β 0 z t 2 V -1 t .
3. Using the expression of

β t = n 2 log |Vt| 1/2 |V0| 1/2 δ + √ λS and that |V t+1 | = |V t |(1 + z t 2 V -1 t
), one has

β t+1 ≤ β t + n log(1 + z t 2 V -1 t ) ≤ β t + n 1 + z t 2 V -1 t ≤ β t + n z t 2 V -1 t 2 log β t+1 β t ≤ log 1 + n z t 2 V -1 t 2β t ≤ n z t 2 V -1 t 2β 0 .
Plugging everything together, on E t+1 , KL(φ

t ||φ t+1 ) ≤ γ KL z t 2 V -1 t where γ KL = 1 2 + β 2 T ((1 + C)X) 2 /λ + W 2β 0 + n(n + d) n 2β 0 .

D. Regret proofs D.1. Regret decomposition

The regret decomposition that we use slightly differs from the one of Abbasi-Yadkori & Szepesvári (2011) and [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF]. We provide the proof for the sake of completeness.

Let R(T ) = T t=0 x T t Qx t + u T t Ru t -J(θ * ). Since {E t } t≤T is an decreasing sequence of events, one has

R(T )1{E T } ≤ T t=0 x T t Qx t + u T t Ru t -J(θ * ) 1{E t }.
From the Bellman optimality equations for LQ problems, we get that

J( θ t ) + x T t P ( θ t )x t = min u x T t Qx t + u T Ru + E xu,T t+1 P ( θ t )x u t+1 F t = x T t Qx t + u T t Ru t + E xut,T t+1 P ( θ t )x ut t+1 F t ,
where xu t+1 = θ T t z t + t+1 . Hence,

x T t Qx t + u T t Ru t -J(θ * ) 1{E t } = J( θ t ) -J(θ * ) 1{E t } + z T t θ t P ( θ t ) θ T t z t -z T t θ * P ( θ t )θ T * z t 1{E t } + x T t P ( θ t )x t 1{E t } -E x T t+1 P ( θ t )x t+1 1{E t } F t
where we used in the last line that E t is F t -measurable. Noticing that E t+1 ⊂ E t , one has 1{E t+1 }1{E t } = 1{E t+1 } and since P ( θ t ) is positive definite, x T t+1 P ( θ t )x t+1 ≥ 0. Therefore, While all the above results are valid for LQ system of arbitrary dimensions n and d, the final bound is ultimately limited to LQ system with dimension n = 1 due to the bound of R TS . From Abeille & Lazaric (2017), we have that for any LQ system with n = 1, w.p. at least 1 -δ/6, R TS = Õ √ T . Finally, Prop. 6 guarantees that the event E T holds w.p. at least 1 -δ/2. Therefore, plugging everything together and using a union bound argument proves Thm. 1.

E x T t+1 P ( θ t )x t+1 1{E t } F t =E x T t+1 P ( θ t )x t+1 1{E t }(1{E t+1 } + 1{E c t+1 }) F t =E x T t+1 P ( θ t )x t+1 1{E +1 } F t + E x T t+1 P ( θ t )x t+1 1{E t }1{E c t+1 } F t ≥E x T t+1 P ( θ t )x t+1 1{E +1 } F t =E x T t+1 P ( θ t ) -P ( θ t+1 ) x t+1

E. Discussion on Asm. 3

We first focus on the one dimensional case for which we provide the regret bound, and then discuss the challenges that arise when moving to higher dimensional problem.

When n = 1, Asm. 3 is indeed equivalent to assuming that θ * ∈ S 0 i.e., that θ * forms a stabilizable pair. Indeed, by construction θ T * H(θ * ) is stable, thus, denoting as ρ(A) the spectral radius associated to any real-valued matrix A, we have that ρ * = ρ θ T * H(θ * ) < 1. Further, in the 1-dimensional case, one has that ρ(A) = A 2 , thus there always exists a set S such that Asm. 3 holds (it suffices to define it with ρ close enough to 1).

When n > 1 however, as pointed out by [START_REF] Faradonbeh | Finite time analysis of optimal adaptive policies for linear-quadratic systems[END_REF], the fact that ρ(A) ≤ A 2 for any matrix A induces that the stabilizability of θ * does not necessary implies the 2-norm of the closed-loop matrix θ T * H(θ * ) to be less than 1. Indeed, there exists θ * stabilizable such that θ T * H(θ * ) 2 > 1 and Asm. 3 may be violated for a potentially large class of true parameters θ * . A way to overcome this limitation is to consider a larger admissible set S and only impose that θ * ∈ S . Formally, we could consider S = {θ T ∈ R n(n+d) , J(θ) < D and Tr(θθ T ) ≤ S 2 }.

(15)

In a similar fashion, such admissible set is sufficient to ensure the stabilizability and the boundedness of the control, in line with Prop. 5.

Proposition 13. S is a compact set. For any θ ∈ S, θ is a stabilizable pair and there exist ρ < 1 and C < ∞ positive constants such that ρ = sup θ∈S ρ θ T H(θ) and C = sup θ∈S K(θ) 2 .

The proof follows a similar path to the one of Prop. 5. The continuity of J and the boundedness of S implies its compactness. Further, θ ∈ S are stabilizable since J(θ) = +∞ otherwise, and the continuity of the spectral radius as well as the controller guarantees the finite constant (strictly less than 1 for the spectral radius). Furthermore, thanks to Prop. 13, one can derive an inequality similar to Prop. 8, i.e., ∇P (θ)[i, j] V -1 t ≤ C H(θ) V -1 t for any θ ∈ S , using a slightly modified proof, leveraging the Riccati theory. Leveraging these guarantees, it is possible to extend all sub-results presented in the one dimensional case to the case n > 1, using the augmented admissible set S , except for the boundedness of the state process induced by the TS algorithm. Indeed, in line with [START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF], we rely on the fact that θ T t H( θ t ) 2 ≤ ρ < 1 for all t ≥ 0 to apply the proof of Abbasi-Yadkori & Szepesvári (2011), and ensure the boundedness of the state. However, such guarantee is no longer provided by Prop. 13, and hence proving the result for n > 1 requires a different stabilization procedure. A potential direction is to follow the approach of [START_REF] Faradonbeh | Finite time analysis of optimal adaptive policies for linear-quadratic systems[END_REF], where they propose to perform a finite time stabilization procedure before starting the algorithm. We believe this is an important direction for future investigation in order to relax Asm. 3.

) 3 .

 3 Thompson Sampling for LQR Input: θ0, V0 = λI, δ, T , t0 = 0 1: Set βt according to Eq. 5 2: for t = {0, . . . , T } do 3: Sample θt = RS ( θt + βtV control ut = K( θt)xt 5: Observe state xt+1 and cost ct = c(xt, ut) 6: Compute Vt+1 and θt+1 using Eq. 4 7: end for

Figure 1 :

 1 Figure 1: Thompson sampling algorithm for LQ.

Table 1 :

 1 Figure 2: Evolution of p opt,t for three systems of dimension N = n(n+d). Worst case values for p opt,t .

	n t ], and θ t = [ θ 1 t , . . . , θ n t ], with θ i t
	conditionally independent. Accordingly, each systems can
	be controlled independently, as Tr(P ( θ t )) =	n i=1 J( θ i t ),

  1{E +1 } F t + E x T t+1 P ( θ t+1 )x t+1 1{E +1 } F t Qx t + u T t Ru t -J(θ * ) 1{E t } = J( θ t ) -J(θ * ) 1{E t } + z T t θ t P ( θ t ) θ T t z t -z T t θ * P ( θ t )θ T * z t 1{E t } + x T t P ( θ t )x t 1{E t } -E x T t+1 P ( θ t+1 )x t+1 1{E +1 } F t + E x T t+1 P ( θ t+1 ) -P ( θ t ) x t+1 1{E +1 } F t .D.2. Final boundCollecting the results derived in Subsec. 5.1 and 5.2, we have that, w.p. at least1 -δ/6, R gap ≤ γ gap where γ gap = 2X 2 γ abs √ γ RLS + 6D 2n log(12/δ) + D √ nγ KL γ RLS ,On the other hand, collecting the result from[START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF], we have that,

	which implies that
	x T t √	T + 2X 2 √	nDδ = Õ	√	T ,
	γ RLS = 2	((1 + C)X) 2 λ	(n + d) log 1 +	T ((1 + C)X) 2 λ(n + d)	,
	γ KL =	1 2	+	β 2 T ((1 + C)X) 2 /λ + W 2β 0	+ n(n + d)	n 2β 0	.

w.p. at least 1 -δ/6, R mart = Õ √ T a.s. , R RLS = Õ √ T .

This proposition fixes Lem. 1 of[START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF], which incorrectly reports that the inner product ∇J(θ) T δθ is the solution of the Lyapunov equation. As they eventually consider one-dimensional systems, their derivation is still correct.

We discuss the validity of this assumption in App. E.

Explicit numerical and problem dependent constants can be collected from the proof.

For a more thorough discussion of the challenges of proving frequentist regret bounds for TS in LQ problems, refer to (Sect. 4.2,[START_REF] Abeille | Thompson sampling for linear-quadratic control problems[END_REF].

Explicit constant is provided in App. D.2.

Despite the similarity in the structure, every step reported here follows slightly different path to e.g., properly deal with the rejection set and integrating the state xt more carefully so as to avoid the dependency on J(θ * ).

While for n = 1, J(θ) = P (θ) and any analysis on P (θ) directly transitions to guarantees for the average cost, for n > 1 we have J(θ) = Tr(P (θ)) and we need to study the spectrum of P (θ) to provide guarantees on the performance. In general, this may indeed make the problem considerably more difficult.

The choice of such an early t is that from Fig.2, popt seems to converge fast and its smallest values are usually at early stages of the learning process.