Thompson Sampling Efficiently Learns to Control Diffusion Processes
Authors: Mohamad Kazem Shirani Faradonbeh
Mohamad Sadegh Shirani Faradonbeh
Mohsen Bayati
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
Posterior Sampling
Continuous-Time Systems
Stochastic Differential Equations
Linear Systems
Adaptive Control

Abstract: Diffusion processes that evolve according to linear stochastic differential equations are an important family of continuous-time dynamic decision-making models. Optimal policies are well-studied for them, under full certainty about the drift matrices. However, little is known about data-driven control of diffusion processes with uncertain drift matrices as conventional discrete-time analysis techniques are not applicable. In addition, while the task can be viewed as a reinforcement learning problem involving exploration and exploitation trade-off, ensuring system stability is a fundamental component of designing optimal policies. We establish that the popular Thompson sampling algorithm learns optimal actions fast, incurring only a square-root of time regret, and also stabilizes the system in a short time period. To the best of our knowledge, this is the first such result for Thompson sampling in a diffusion process control problem. We validate our theoretical results through empirical simulations with real matrices. Moreover, we observe that Thompson sampling significantly improves (worst-case) regret, compared to the state-of-the-art algorithms, suggesting Thompson sampling explores in a more guarded fashion. Our theoretical analysis involves characterization of a certain \emph{optimality manifold} that ties the local geometry of the drift parameters to the optimal control of the diffusion process. We expect this technique to be of broader interest.

Thompson Sampling Efficiently Learns to Control Diffusion Processes
Mohamad Kazem Shirani Faradonbeh
Mohamad Sadegh Shirani Faradonbeh
Department of Statistics
Graduate School of Business
University of Georgia Athens, GA 30602
Stanford University
Stanford, CA, 94305 sshirani @etanniitttaaor...omm edu
mohamadksf @uga
Mohsen Bayati
Graduate School of Business Stanford University Stanford, CA, 94305 bayati@stanford.. edu
Abstract
Diffusion processes that evolve according to linear stochastic differential equations are an important family continuous-time dynamic Decision-making models. Optimal policies are well-studied for them, under full certainty about the drift matrices. However, little is known about data-driven control of diffusion processes with uncertain drift matrices conventional discrete-time analysis techniques are not applicable. In addition, while the task can be viewed as a reinforcement learning problem involving exploration and exploitation trade-off, ensuring system stability is fundamental component of designing optimal policies. We establish that the popular Thompson sampling algorithm learns optimal actions fast, incurring only a square-root of time regret, and also stabilizes the system in short time period. To the best of our knowledge, this is the first such result for Thompson sampling a diffusion process control problem. We validate our theoretical results through empirical simulations with real matrices. Moreover, we observe that Thompson sampling significantly improves (worst-case) regret, compared to the state-of-the- art al algorithms, suggesting Thompson sampling explores in more guarded fashion. Our theoretical analysis involves characterization of certain optimality manifold that ties the local geometry of the drift parameters to the optimal control the diffusion process. We expect this technique to be of broader interest.
1 Introduction
One of the most natural reinforcement learning (RL) algorithms for controlling a diffusion process with unknown parameters is based Thompson sampling (TS) [I] Bayesian posterior for the model is calculated based on its time evolution, and a control policy is then designed by treating sampled model from the posterior as the truth. Despite its simplicity, guaranteeing efficiency and whether sampling the actions from the posterior could lead to unbounded future trajectories is unknown. In fact, the only known such theoretical result for control of diffusion process is for epsilon-greedy type policy that randomize the control actions at a certain rate (2).
In this work, we consider p dimensional state signal {æth22 that obeys the (Ito) stochastic differential equation (SDE)
dæ. = (Apz; + B dt dW,
(1)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where the drift matrices Au and Bo are unknown, Ue E R is the control action at any time t 2 0, and it designed based on values of v, for E [0. f). The matrix Bo E R models the influence of the control action on the state evolution over time, while An E RPXP is the (open-loop) transition matrix reflecting interactions between the coordinates of the state vector at.. The diffusion term in (I) consists of non-standard Wiener process W. that will be defined in the next section. The goal is to study efficient RL policies that can design Ut to minimize a quadratic cost function, defined in the next section, subject to uncertainties around Ag and Bo.
At a first glance, this problem is similar to most RL problems since the optimal policy must balance between the two objectives of learning the unknown matrices Au and Bu (exploration) and optimally selecting the control signals u, to minimize the cost (exploitation). However, unlike most RL problems that have finite or bounded-suppor a crucial part of designing optimal policies. For example, in the discrete-time version of the problem, robust exploration is used to protect against unpredictably unstable trajectories K6
state space, ensuring stability, that o, stays bounded, is
Related literature. The existing literature studies efficiency of TS for learning optimal decisions in finite action spaces [7-2]. In this stream of research, it shown that, over time, the posterior distribution concentrates around low-cost actions 13.55 TS is also studied in further discrete-time settings with the environment represented by parameters that belong a continuum, and Bayesian and frequentist regret bounds are shown for tinear-uudraati regulators [1] However, effectiveness of TS in highly noisy environments that are modeled by diffusion processes remains unexplored to date, due to technical challenges that will be described below.
For continuous-time linear time invariant dynamical systems, infinite-time consistency results shown under a variety of technical assumptions, followed by alternating policies that cause (small) linear regrets [6). From computational viewpoint, pure exploration algorithms for computing optimal policies based on multiple trajectories of the state and action data are studied as well (37-39, for which a useful survey is available [40) However, papers that study exploration versus exploitation and provide asympotti estimation rates or regret bounds are limited to a few recent work about offline RL 45). with the exception of Randomized -sttmmatss policies that TS outperforms them, as will be illustrated at the end of this paper.
Contributions. This work, first establishes that TS learns to stabilize the diffusion process I Specifically, in Theorem [ of Section 3 we provide the first theoretical stabilization guarantee for diffusion processes, showing that the probability of preventing the state process from growing unbounded grows to 1, at an exponential rate that depends on square-root of the time length devoted to stabilization. As mentioned above, for RL problems with finite state spaces, the process is by definition stabilized, regardless of the policy. However, for the Euclidean state space of æ, in (T) stabilization is necessary to ensure that the state and the cost do not grow unbounded.
Then, efficiency of TS in balancing exploration versus exploitation for minimizing a cost function that has quadratic form of both the state and the control action is shown. Indeed, we establish in Theorem 2 of Section 4 that the regret TS incurs, grows the square-root of time, while the squared estimation error decays with the same rate. It is also shown that both the above quantities grow quadratically with the dimension. To the authors' knowledge, the presented results are the first theoretical analyses of TS for learning to control diffusion processes.
Additionally, through extensive simulations we illustrate that TS enjoys smaller average regret and substantially lower worst-case regret than the existing policies 2 thanks to its informed exploration.
It is important to highlight that theoretical analysis of RL policies for diffusion processes is highly non-trivial. Specifically, the conventional discrete-time -ieee RL technical tools are not applicable. due to uncountable cardinality of the random variables involved in diffusion process, the unavoidable dependence between them, and the high level of processing and estimation noise. To address these, we make four main contributions. First, non non-asymptotic and uniform upper bounds for continuous time martingales and for Ito integrals are required to quantify the estimation accuracy. For that purpose, we establish concentration inequalities and show sub-ex sub-exponential tail bounds for double stochastic integrals. Second, one needs sharp bounds for the impact of estimation errors on eigenvalues of certain non-linear matrices of the drift parameters that determine actions taken by TS policy. To tackle that, we perform a novel and tight eigenvalue perturbation-anallye based on the approximation error, dimension, and spectrum of the matrices. We also establish Lipschitz continuity of the control policy

---

with respect to the drift matrices, by developing new techniques based on matrix-valued curves. Third, to capture evaluation of both immediate and long-term effects of sub-optimal actions, we employ Ito calculus to bound the stochastic regret and specify effects of all problem parameters. Finally, to study learning from data trajectories that the condition number of their information matrix grows unbounded, we develop stochastic inequalities for self-normalized continuous-tin martingales, and spectral analysis of non-linear functions of random matrices.
Organization. The organization of the subsequent sections is as follows. We formulate the problem in Section 2 while Algorithm that utilizes TS for learning to stabilize the process and its high- probability performance guarantee are presented in Section 3 Then, in Section TS is considered for learning to minimize quadratic cost function, and the rates of estimation and regret are established. Next, theoretical analysis are provided in Section [ followed by real-world numerical results of Section 6 Detailed proofs, auxiliary lemmas, and additional simulations are provided longer version of the paper [54].
Notation. The smallest (the largest) eigenvalue of matrix M, magnitude, is denoted by A (M) (A (M)). For a vector a, |a| is the &2 norm, and for a matrix M. |M is the operator norm that is the supremum of [Ma] for on the unit sphere. N (μ. 2) is Gaussian distribution with mean μ and covariance Σ. If y a matrix (instead of vector), then N (H, Σ) denotes a distribution on matrices of the same dimension Jr, such that all columns are independent and share the covariance matrix Σ. In this paper, transition matrices A E RPxP together with input matrices E RPX0 are jointly denoted by the (p + q) x parameter matrix 0 = [A, B] We employ V (A) for maximum (minimum). Finally, a S b expresses that a I agb, for some fixed constant ag.
2 Problem Statement
We study the problem of designing provably efficient reinforcement learning policies for minimizing a quadratic cost function in an uncertain linear diffusion process. To proceed, fix the complete probability space (12, {Fi) IP), where Ω is the sample space, {Fi is a continuous-ting time fields), and IP is the probability measure defined on Foc
filtration (i.e., increasing
The state comprises the diffusion process 2; in (]. where Oo- = [Ao. Bol E x(++9)xp is the un- known drift parameter. The diffusion term in (T) follows infinitesimal variations of the p dimensional Wiener process [Weh That is, (We) he is multivariate Gaussian process with independent increments and with the stationary covariance matrix Ew, such that for all 0 S 81
S 82 < 41 S l2.
Wx2 - Wr, W., N N (8:
0 (t2 - +1)2
0 Opxp S1)
W
Opxp
Existence, construction, continuity, and non-differenniabiliy of Wiener processes are well-known 44 is standard to assume that Σn is positive definite, which is a common condition in lcarning-based control 40 2 42 to ensure accurate estimation over time.
The RL policy designs the action {ur) based on the observed system state by the time, as well as the previously applied actions, to minimize the long-run average cost
/ [x u. T-
1 T
Qzu Q
lim sup
dt, for Q
v Q xTL
0
Above, the cost is determined by the positive definite matrix Q, where Qz E ReXp, Qu R Qru E RR*x In fact, Q determines the weights of different coordinates of x,, u, in the cost function, so that the policy aims to make the states small, by deploying small actions. The cost matrix Q is assumed known to the policy. Formally, the problem is to minimize (3) by the policy
ui Å (Q, (xolosege (us)osuet)
(4)
Without loss of generality, and for the ease of presentation, we follow the canonical formulation that sets Qzu = O; one can simply convert the case Qun o to the canonical form, by employing a rotation to Er, (45)48). It is well-known that if, hypothetically, the truth Og was known, optimal
3

---

policy Topt could be explicitly found by solving the continuous time algebraic Riccati equation. That is, for generic drift matrix 0 [A, [3] finding the symmetric p x p matrix P (0) that satisfies
P ((0) + Qx = 0. A P (0) + P P )0)4 - P (0) BQ_ BT
(5)
This means, for the true parameter 0o [Mo: Bo]] we can let (0o) solve the above equation, and define the policy
Topt Ue - BU (0o) Tt, 11 2 0.
(6)
It is known that the linear time-invariant policy Topt minimizes the average cost in 3 optimal policy also stabilizes the system such that under Topt, the diffusion process æ, does not grow unbounded with time. Below, we define stabilizability and elaborate these properties.
45
45 This
Definition 1 The process in ① is stabilizable, if all eigenvalues of A Ao + BoK have negative real-parts, for a matrix K. Such K, are called a stabilizer and the stable closed-loop matrix.
We assume that the process ① with the drift parameter Og is stabilizable. Therefore, P (0o) exists, is unique, and can be computed according to continuous-time Riccati differential equations 45 48). Furthermore, it is known that real-parts of all eigenvalues of Ag = As B B P (0)) are negative, i.c., the matrix exp (Aot) decays exponentially fast as grows 45) So, under
the linear feedback in (6), the closed-loop transition matrix is Ay and the solution of (T) is the
OmsteinnUUllebbed process 2t = e Aot xo + Aot(t=> dw, 44 which evolves in a stable manner
In the sequel, we use and refer the solution P(0) for different stabilizable 0. More details about the above optimal feedback policy can be found in the aforementioned references.
because of X (exp Aot))
In absence of exact knowledge of 0., a policy â collects data and leverages it to approximate Topt in (). Therefore, all (finite) times, there is gap between the cost of म., compared to that of Topt- The cumulative performance degradation due to this gap is the regret of the policy т. that we aim to minimize. Technically, whenever the control action u, designed by the policy π according (4)
concatenate the resulting state and input signals to get the observation 2;( [[a]] [,,]] If is clear from the context, we drop म. Similarly, z, (Topp) denotes the observation signal of Topt- Now, the regret at time T is defined by:
Rega (7) (T)= m= (1QU) 11122222 -
secondary objective the learning accuracy of 0o from the single trajectory of the data generated by म. Letting Oz be the parameter estimate time I, are interested in scaling of 0r 0 with respect to 1, and
3 Stabilizing the Diffusion Process
This section focuses on establishing that Thompson sampling (TS) learns to stabilize the diffusion process (T.. First, let intuitively discuss the problem of stabilizing unknown diffusion processes. Given that the optimal policy in (6) stabilizes the process in ( a natural candidate to obtain stable process under uncertainty of the drift matrices Ag. Bo, is linear feedback of the form u, K Kay.
So. letting Ā = Au + K, have 2; A'xo A(t-s)
Thus, if real-part of an
eigenvalue of Á is non-negative, then the magnitude of æ; grows unbounded with t Therefore, addressing instabilities of this form is important, prior to minimizing the cost. Otherwise, the regret grows (super) linearly with time. In particular, Ao has some eigenvalue(s) with nen-negative real-part(s), then it is necessary employ feedback to preclude instabilities.
In addition to minimizing the cost, the algebraic Riccati equation in provides a reliable and widely-used framework for stabilization, as discussed after Definition Accordingly, due to

---

uncertainty about do. one can solve 5 and find P only for an approximation 0 of 0o. Then, we expect to stabilize the system in ① by applying a linear feedback that is designed for the approximate drift matrix 0. Technically, we need to ensure that all eigenvalues of An B BT θ lie in the open left half-plane. To ensure that these requirements are met in a sustainable manner, the main challenges are
(i) fast and accurate learning of Oo so that after short time period, small error 0 0-0o is guaranteed,
(ii) specifying the effect of the error fo. on stability of A BoQ BT P and
(iii) devising remedy for the case that the stabilization procedure fails.
Note that the last challenge is unavoidable, since learning from finite data can never be perfectly accu- rate, and so any finite-time stabilization procedure has a (possibly small) positive failure probability.
Algorithm addresses the above challenges by applying additionally randomized control actions, and using them to provide a posterior belief DD about 0g. Note that the posterior not concentrated at Og. and a sample from D approximates dg. crudely. Still, the theoretical analysis of Theorem indicates that the failure probability of Algorithm [T decays exponentially fast with the length of the time interval it is executed. Importantly, this small failure probability can shrink further by repeating the procedure of sampling from D. So, stabilization under uncertainty is guaranteed, after limited time of interacting with the environment.
To proceed, let {wn)n be sequence of independent Gaussian vectors with the distribution Wn N (0, o [.), , for some fixed constant ow. Suppose that we aim to devote the time length t to collect observations for learning to stabilize. Note that since stabilization performed before moving forward to the main objective of minimizing the cost functions, the stabilization time length T is desired to be as short as possible. We divide this time interval of length T to x sub-intervals of equal length, and randomize an initial linear feedback policy by adding {w, j n== That is, for n 0, 1, ......... K Algorithm Beammmempllll Templos the control action
nT
1)T Stc
u Kx, + Wn. for
K
K
where K is initial stabilizing feedback that all eigenvalues of As BoK lie in the open left half-plane. In practice, such K is easily found using physical knowledge of the model, e.g.. via conservative control sequence for an airplane 49 [0]. However, note that such actions sub-optimal involving large regrets. Therefore, they are only temporarily applied, for the sake of will be utilized by the algorithm to determine the posterior belief Dr. as follows. Recalling the notation x, = [ "
data collection. Then, the data collected during the time interval 0 < 1
let po. Eg be the mean and the precision matrix of prior normal distribution on 0, (using the notation defined in Section [ random matrices). Such a prior belief can be objectively calculated according to a previously available data or formed by subjective believes about the diffusion process understudy, and in both cases can be used for speeding up the learning- based control of the system.
Nonetheless, if there is such prior, we simply let ñuo 0 0(ptg)xp and En Ip+g. Then, define
Eopo + f !zdd!!
Ex = E0 +
2 ds,
2
Tr = 55
Using Er E IR (B( together with the mean matrix Pr., Algorithm forms the posterior belief
N (p.. (N+: E71).
about the drift parameter 0g. So, as defined in the notation, the posterior distribution of every column i = 1, , of Oo. is an independent multivariate normal with the covariance matrix E while the mean is the column i of pr. The final step of Algorithm is to output a sample Ø from Dr.
Next, to establish performance guarantees for Algorithm 1
let us quantify the ideal stability by
Co = -log (exp [Ao BoQ, B P (06)))
(10)
5

---

Algorithm : Stabilization under Uncertainty
Inputs: initial feedback K, stabilization time length for n = 0, 1,1,,... K 1 do
while ntk S (n 1)TK* do
Apply control action u, in 7 end while
end for
Calculate E.,, Fr according to ( Return sample 0 from the distribution D, in (
By definition, Ço is positive. In fact, it is the smallest distance between the imaginary axis in the complex-plane and the eigenvalues of the transition matrix Ao Au BoQ, B P (0o), under the optimal policy in (6). Since d, is unavailable, it is not realistic to expect that after applying a policy based on given by Algorithm L real-parts of all eigenvalues of the resulting matrix Ao B-BO0T TT P are most Coo However, Ço is crucial in studying stabilization, such that stabilizing controllers for systems with larger Ço can be learned faster. The exact effect of this quantity, as well as those of other properties of the diffusion process, are formally established the following result. Informally, the failure probability of Algorithm decays exponentially with 71/2.
Theorem (Stabilization Guarantee) For the sample 0 given by Algorithm 1
let E be the failure
event that As BoQu 1T 0
has an eigenvalue the closed right half-plane. Then, if k Z 72
and log (pqre) x T 1/2 ., we have
A(Ew) d X(Ew) o |K] V pdq
1 So
log 5
(11)
The above result indicates that more heterogeneity in coordinates of the Wiener noise renders stabilization harder. Moreover, using (TO), the term Co" reflects that less stable diffusion processes with smaller Ço. are significantly harder to stabilize under uncertainty. Also one can expect, larger dimensions make learning to stabilize harder. This is contributed by higher number of parameters to learn, as well as higher sensitivity of eigenvalues for processes of larger dimensions. Finally, the failure probability decays as T 1//2, mainly because continuous timeuuuuus-mmeeeeee martingales have sub-exponential distributions, unlike -abssaaaiintty of discrete-time counterparts (51
4 Thompson Sampling for Efficient Control: Algorithm and Theory
In this section, we proceed towards analysis of Thompson sampling (TS) for minimizing the quadratic cost in ( and show that efficiently learns the optimal control actions. That is. TS balances the exploration versus exploitation, such that its regret grows with (nearly) the square-root rate, time grows. In the sequel, we introduce Algorithm@]an and discuss the conceptual and technical frameworks it relies on. Then, we establish efficiency by showing regret bounds in terms of different problem parameters and provide the rates of estimating the unknown drift matrices.
In Algorithm 2 first the barning-based stabilization Algorithm is run during the time period 0 < 1. < To. So, according to Theorem the optimal feedback of Oo stabilizes the system with high probability, as long as To is sufficiently large. Note that if growth of the state vector indicates that Algorithm|] [ failed to stabilize, one repeat sampling from Dr.- So, we assume that the evolution the controlled diffusion process remains stable when Algorithm(Zij i2is being executed. On the other hand, the other benefit of running Algorithm T at the beginning is that it performs initial exploration phase that will be utilized by Algorithm to minimize the regret.
Then, in order to learn the optimal policy Topt with minimal sub-optimality, RL algorithms need to cope with a fundamental challenge, commonly known as the exploration-exxllootaioon dilemma. To see that, first note that an acceptable policy that aims to have sub-linear regret, needs to take near-optimal control actions in long run; u, R Q_= BJ P (fo) x,, Although such policies exploit well and their control actions are close to that of Topt. their regret grows large since they fail to

---

explore. Technically, the trajectory of observations {z is not rich enough to provide accurate estimations, since in z! . u, the signal u, (almost) linear function of the state signal and so does not contribute towards gathering information about the unknown parameter do. Conversely, for sufficient explorations, RL policies need take actions that deviate from those of Topt, which imposes large regret. Accordingly, the above trade-off needs to be delicately balanced; what we show that TS does.
Algorithm is episodie; the parameter estimates On are updated only at the end of the episodes at times {T m while during every episode, actions taken as if 0, Ann By is the unknown truth gg. That is, for Tn-1 S Tn, using P (0.) in (5). we let u,
1 O Zt.
Then, for each n = 1, at time Tn, we use all the observations collected so far, to find Σ TT,,, PT.. according to (8 Next,
them sample On from the posterior Dr, in (
The episodes in Algorithm are chosen such that their end points satisfy
Tn+1=
Tn
Tn+1
Tn
< S inf n20
S sup n20
a < 0o,
(12)
Tn
for some fixed constants a, a. Broadly speaking, 12) lets the episode lengths of Algorithm 2 scale properly avoid unnecessary updates of parameter estimates, while the same time performing sufficient exploration. To see that, first note that since Σ, grows with T, the estimation error 0,, 0o decays (at best polynomially fast) with T.. So, until ensuring that updating the posterior yields to significantly better approximations, it will not be beneficial to update it, sample from it, and solve (5) So, the period 1 T, that the data up time Tn is utilized, is set to be long at.- On the other hand, the above period cannot be too long, since we aim to improve the parameter estimates after collecting enough new observations; 7 < (1 + a) Tu. A simple setting is to let = TF, which yields to exponential episodes тn To (1 + T Note that for TS in continuous time, posterior updates should be limited to aufficiently-paarr time points. Otherwise, repetitive updates are computationally impractical, and also can degrade the performance by preventing control actions from having enough time to effectively influence.
Algorithm 2 Thompson Sampling for Efficient Control of Diffusion Processes
Inputs: stabilization time To Calculate sample Og by running Algorithm for time To for n = 2, do
while Tn-1 S f T. do
Apply control action u, -- BT_, P P at
end while Letting Ar. be as sample 0, from Dr,, given in ( end for
We show next that Algorithm addresses the exploration-exploiie trade-off efficiently. To see the intuition, consider the sequence of posteriors Dr,, The explorations Algorithm 2 performs by sampling 0n from D depends on Σr., Now, hypothetically A (Er.) is not large enough, then Dr, does not sufficiently concentrate around Pr. and so θ, will probably deviate from the previous n-1
samples 0
So, the algorithm explores more and obtains richer data z, by diversifying the control signal ug This renders the next mean PT.4. a more accurate approximation of 6.. and also
i=1
makes
S ( grow faster than before. Thus, the next posterior Dr provides a better sample
with smaller estimation error 0 θnt1 Og Similarly, if posterior is excessively concentrated, in few episodes the posteriors adjust accordingly to the proper level of exploration. Hence, TS eventually balances the exploration versus the exploitation. This is formalized below.
7

---

Theorem 2 (Regret and Estimation Rates) Parameter estimates and regret of Algorithm 2 satisfy
X (Ew)
0n 0o|
()+ Tn
1/2 log nn.
A (Ew)
A (Ew)² 22 | (0o) ((w)) (Q))
Reg (T)
(XEww + to 2 ww) To +
0 (p+g) 1 T.
In the above regret and estimation rates, and similar to Theorem X / (Ew) reflects the impact of heterogeneity in coordinates of W, on the quality of learning. Also, larger log(1 + a) corresoonds to longer episodes which compromises the estimation. Further, p(p+ shows that larger number of parameters linearly worsens the learning accuracy. In the regret bound, (00)l (Q) indicates effect of the true problem parameters Oo, Q. Finally, (Aww) + o to captures the initial phase that Algorithm iss run for stabilization, which takes sub-optimal control actions as in
5 Intuition and Summary of the Analysis
The goal of this section is to provide high-level roadmap of the proofs of Theorems [ and [ and convey the main intuition behind the analysis. Complete proofs and the technical lemmas can be found in the longer version of the paper (54).
The main steps involve analyzing the estimation, studying its effect on the solutions of (5). and characterizing impact of errors in entries of parameter matrices on their eigenvalues. Next, we elaborate on these steps.
Summary of the Proof of Theorem [
We show that the error satisfies @0-0| - p(p + /)2 1/2, More preciscly, the error depends mainly on total strength of the observation signals zt. which are captured in the precision matrix Σ,, as well total interactions between the signal 2 and the noise W. in the form of the stochastic
integral matrix [ Z.dW However, we establish an upper bound X (S-') ST-,, that indicates the
concentration rate of the posterior D,- Similarly, thanks to the randomization signal Wp, the signals z; are diverse enough to effectively explore the set of matrices 0 = [A, B] leading to accurate approximation of 0 by the posterior mean matrix f0- Then, to bound the error terms caused by the Wiener noise Wt we establish the rate p(p + q) 1/2 Indeed, we show that the entries of this error matrix are continuous-time martingales, and use exponential inequalities for quadratic forms and double stochastic integrals 552 51 to establish that they have sub-exponential distribution.
Moreover, the error rate of the feedback satisfies a similar property; A P 0 - BJ P (0o) x
p(p + //2 11/2, So, letting A = Ao B.Q. BT
and Ao Ao BOQ, P (0o). it
holds that A Aoll S 2(2+ 11/2, Next, to consider the effect of the errors on the eigenvalues of A, we compare them to the eigenvalues of An, which are bounded by Coo in [T). To that end, establish novel and tight perturbation analysis for eigenvalues of matrices, with respect their entries and spectral properties. Using that, we show that the difference between the eigenvalues of
A and Ao scales as (1 V 1/2 A - Aoll)//r where r is the size of the largest block in the Jordan dlock-iiagonalization of Ap. Therefore, for stability of A, we need || Aoll S --12 (1 A Co"), 1/2
since r < p. Note that if Ag is diagonalizable, r 1 implies that we can replace the above upper bound by 1 A Co- Putting this stability result together with the estimation error in the previous paragraph, we obtain
Summary of the Proof Theorem 2 To establish the estimation rates, we develop multiple intermediate lemmas quantifying the exact amount of exploration @eporithm@eerfone utilize the fact that the bias of the posterior distribution Dr, depends on its covariance matrix Σ... valuue martingale. For the effect the former,
First, we
as well as nelf-normalized continuous-timg i.e., X //2) we show an upper-bound of the order Tn - 114 To that end, the local geometry of the optimality manifolds that contain drift parameters 0 that has the same optimal feedback that of the
8

---

unknown truth do in (6) are fully specified, and spectral properties of non-linear functions of random matrices are studied. Then, we establish stochastic inequality for the self-normalized martingale. indicating that its scaling is the order p(p + q) log Tn- Therefore, utilizing the fact that 0, Pra has the same scaling as the bias matrix Pr,, 0.. we obtain the estimation rates of Theorem 2
Next, to prove the presented regret bound, we establish a delicate and tight analysis for the dominant effect of the control signal on the regret Algorithm Santhmm@@incu incurs. Technically, by carefully examining the infinitesimal influences of the control actions at every time on the cost, we show that it suffices to
+ Qu' P On Zt ||2
to obtain Reg (T). We proceed toward specifying the effect of the exploration Algorithm 2 performs on its exploitation performance by proving the Lipschitz continuity of the solutions of the Riccati equation (5) with respect to the drift
integrate the squared deviations
parameters: | (O - (0o) - 0n 0o This result is very important property of (5) that
lets the rates of deviations from the optimal action scale the same as the estimation error, and is proven by careful analysis of integration along matrix-valued curves in the space of drift matrices, as well as spectral analysis for approximate solutions Lyapunov equation. Thus, the regret bound is achieved, using the estimation error result in Theorem
6 Numerical Analysis
We empirically evaluate the theoretical results of Theorems 1 1nd 2 for the flight control of X-29A airplane 2000 [49] Further numerical results for Boeing 747 airplanes (50) and for blood glucose control (55), can be found in the longer version of the paper [54]. The true drift matrices of the X-29A airplane are
00.6
0.07
-1.00
0.047
-..000
0.0007
-
15.20
-266
1.11
0.00
1.3430
0,2345
AA- =
Bg
6.84
-0.10
-0.06
0.00
0.0897
-0.0710
0.00
1.00
0.07
0.00
0.0000
0.0000
Further, we let Eny 0.25 pp Q2 12 Ip and Q = 0.1 I, where In is the n by n identity matrix. To
update the diffusion process æt in ( time-steps of length 10 are employed. Then, in Algorithm
we let Twe 5, K |/3/3]. while T varies from 4 to 20 seconds. The initial feedback K is generated randomly. The results for 1000 repetitions are depicted on the left plot Figure I confirming Theorem that the failure probability of stabilization, decreases exponentially in
On the right hand side of Figure Algorithm 2 executed for 600 second, for T., 20 1.1". We compare TS with the Randomized Estimate algorithm (2] for 100 different repetitions. Average- and worst-case values of the estimation error and the regret are reported, both normalized by their scaling with time and dimension, as in Theorem 2 The graphs show that (especially the worst-case) regret of TS substantially outperforms, suggesting that TS explores in more robust fashion.
7 Concluding Remarks and Future Work
We studied Thompson sampling (TS) reinforcement learning policies to control a diffusion process with unknown drift matrices. First, we proposed stabilization algorithm for linear diffusion processes, and established that its failure probability decays exponentially with time. Furthermore, efficiency of 'T in balancing exploration versus exploitation for minimizing a quadratic cost function shown. More precisely, regret bounds growing as square-root of time and square of dimensions are established for Algorithm 2 Empirical studies showcasing superiority of TS over ofate-of-the-art, provided as well.
As the first theoretical analysis of TS for control of a continuous model, this work implies multiple important future directions. Establishing minimax regret lower-bounds for diffusion process control problem is yet unanswered. Moreover, studying the performance of TS for robust control of the diffusion processes aiming to simultaneously minimize the cost function for a family of drift matrices, is also an interesting direction for further investigation. Another problem of interest is efficiency of 'S for learning to control under partial observation where the state not observed and instead noisy linear function of the state is available the output signal.

---

12
Thempson Bamplnng werst case -.. Thompson Sampling everaee
Fandomize Estimato wors: case
Ran dondomlzdd Estimate average
Normatzed extimation
100
0.8
0.6
Percentage of stabilizatinn
95
0.4
02
90
85
Normalized regret
2.5
1.5
75
0.5
70
8
10 12
14 16
18
20
60
100
150
200
250
900
350
400
450
500
550
600
Stabilization time
Time
For the X-29A flight control problem, percentage of stabilization for 1000 runs of Algo- rithm is plotted on the left. The graphs on the right depict the performance of Algorithm 2 (blue) compared to Randomized Estimate policy (red) (2). The top graph plots the normalized squared
Figure 1:
estimation error, 0 0, divided by p(p q) 1/221on log Tn. versus time, while lower one
showcases the regret Reg (T), normalized by p(p + +) 4)7 log T. Curves for the worst-case among 100 replications provided for both quantities, well as for the averages all replicates.
References
[1] W. R. Thompson, "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples," Biometrika, vol. 25, no. 3/4, pp. 285-294, 1933.
[2] M. K. S. Faradonbeh and M. S. S. Faradonbeh, "Efficient estimation and control of unknown stochastic differential equations," arXiv preprint arXiv:2109.07630 2021.
[3] A. Ioannou and J. Sun, Robust adaptive control. 1996, vol. 1.
PTR Prentice-Hall Upper Saddle River, NJ,
[4] L. Lewis, L. Xie, and D. Popa, Optimal and robust estimation: with an introduction to stochastic control theory. CRC press, 2017.
[5] A. Subrahmanyam and G. P. Rao, Identification of CoCConnnuustiiin Systems: Linear and Robust Parameter Estimation. CRC Press, 2019.
[6] J. Umenberger, M. Ferizbegovic, B. Schön, and H. Hjalmarsson, "Robust exploration in linear quadratic reinforcement learning," Advances in Neural Information Processing Systems, vol. 32, 2019.
[7] Agrawal and N. Goyal, "Analysis of thompson sampling for the multi- armee bandit problem." in Conference on learning theory. JMLR Workshop and Conference Proceedings, 2012, pp. 39-1.
8 "Further optimal regret bounds for thompson sampling," in Artificial intelligence and statistics. PMLR, 2013, pp. 99-107.
[9] A. Gopalan and S. Mannor, "Thompson sampling for learning parameterized markov decision processes," in Conference on Learning Theory. PMLR, 2015, 861-898.
[10] M. J. Kim, "Thompson sampling for stochastic control: The finite parameter case," IFEE Transactions Automatic Control, vol. 62, 12, pp. 6415-6422, 2017.
10

---

[11] M. Abeille and A. Lazaric, "Linear thompson sampling revisited," in Artificial Intelligence and Statistics. PMLR, 2017, pp. 176-184.
[12] N. Hamidi and M. Bayati, "On worst-case regret of linear thompson sampling." arXiv preprint arXiv:2006.067900 2020.
[13] D. Russo and B. Van Roy, "Learning to optimize via posterior sampling." Mathematics of Operations Research, vol. 39, no. 4, pp. 1221-1243, 2014.
[14] An cnoomattion-thoorcee analysis of thompson sampling," The Journal of Machine Learning Research, vol. 17, no. 1. pp. 2442-2471, 2016.
[15] D. Russo, B. Van Roy, A. Kazerouni, Osband, and Z. Wen, "A tutorial on thompson sampling." arXiv preprint (rxXiv:/07..2220
2017.
[16] A. A. Feldbaum, "Dual control theory. i," Avtomatika Telemekhanika, vol. 21, no. 9, pp. 1240-1249, 1960.
[17] J. Florentin, "Optimal, probing, adaptive control of a simple bayesian system," International Journal of Electronics, vol. 13, no. 2, pp. 165-177, 1962.
[18] E. Tse and Y. Bar-Shalom, "An actively adaptive control for linear systems with random parameters via the dual control approach," IEEE Transactions on Automatic Control, vol. 18, no. pp. 109-117, 1973.
[19] Sternby, "A simple dual control problem with an analytical solution." IEEE Transactions on Automatic Control, vol. 21, no. 6, pp. 840-844, 1976.
[20] R. F. Stengel, Optimal control and estimation. Courier Corporation, 1994.
[21] B. Wittemmark, "Adaptive dual control methods: An overview." Adaptive Systems in Control and Signal Processing 1995, pp. 67-72, 1995.
[22] E. D. Klenske and P. Hennig, "Dual control for approximate bayesian reinforcement learning," The Journal of Machine Learning Research, vol. 17, no. pp. 4354-4383, 2016.
[23] M. Abeille and A. Lazaric, "Improved regret bounds for thompson sampling in linear quadratic control problems," in International Conference on Machine Learning. PMLR, 2018, pp. 1-9.
[24] Y. Ouyang, M. Gagrani, and R. Jain, "Posterior sampling- based reinforcement learning for control of unknown linear systems," IEEE Transactions on Automatic Control, vol. 65, no. 8, pp. 3600-3607, 2019.
[25] M. K. S. Faradonbeh, A. Tewari, and G. Michailidis, "Finite-time adaptive stabilization of linear systems," IEEE Transactions on Aulomatic Control, vol. 64, no. 8, pp. 3498-3505 2018.
[26]
"Randomized algorithms for data-driven stabilization of stochastic linear systems," in 2019 IEEE Data Science Workshop (DSW). IEEE, 2019, pp. 170-174.
[27]
"On applications of bootstrap in continuous space reinforcement learning," in 2019 IEEE Conference on Decision and Control (CDC). IEEE, 2019, pp. 1977-1984.
58th
[28]
"On adaptive linear-quadratic regulators," Automatica, vol. 117, p. 108982, 2020.
[29]
"Input perturbations for adaptive control and learning," Automatica, vol. 117, p. 108950,
2020.
[30]
"Optimism-based based adaptive regulation of linear-quadratic systems." IEEE Transactions Automatic Control, vol. 66, no. 4, pp. 1802-1808, 2020.
[31] S. Sudhakara, A. Mahajan, A. Nayyar, and Y. Ouyang, "Scalable regret for learning to control network-coupled subsystems with unknown dynamics," arXiv preprint arXiv:2108. 07970, 2021.
[32] Mandl, "Consistency estimators in controlled systems," Stochastic Differential Systems. Springer, 1989, pp. 227-234.

---

[33] T. E. Duncan and B. Pasik- Duncan, "Adaptive control of continuous- time linear stochastic systems," Mathematiics of Control, signals and systems, vol. no. pp. 45-60, 1990.
[34] Caines, "Continuous time stochastic adaptive control: non-explosion, e e-consistency and stability," Systems & control letters, vol. 19, no. 3, pp. 169-176, 1992.
[35] E. Duncan, L. Guo, and B. Pasik-Duncan, "Adaptive continuous-time linear quadratic gaussian control," IEEE Transactions on automatic control, vol. 44, no. 9, pp. 1653-1662, 1999.
[36] P. E. Caines and D. Levanony, "Stochastic s-optimal linear quadratic adaptation: An alternating controls policy," SIAM Journal on Control and Optimization, vol. 57, no. 2, pp. 1094-104 1126, 2019.
[37] S. A. A. Rizvi and Z. Lin, "Output feedback reinforcement learning control for the continuous- time linear quadratic regulator problem," in 2018 Annual American Control Conference (ACC). IEEE, 2018, pp. 3417-3422.
[38] K. Doya, "Reinforcement learning in continuous time and space," Neural computation, vol. 12, pp. 219-245, 2000.
[39] H. Wang, Zariphopoulou, and Y. Zhou, "Reinforcement learning in continuous time and space: A stochastic control approach." J. Mach. Learn. Res., vol. 21, pp. 198-1, 1, 2020.
[40] Z.-P. Jiang, T. Bian, and W. Gao, "Learning-basee based control: A tutorial and some recent results," Foundations and Rrends in Systems and Control, vol. no. 3, 2020.
[41] M. Basei, X. Guo, A. Hu, and Y. Zhang, "Logarithmic regret for episodic continuous-úme quear--uadratic reinforcement learning over a finite-time horizon," Available at SSRN 3848428, 2021.
[42] L. Szpruch, T. Treetanthiploet, and Y. Zhang, "Exxloration-exploitaiio trade-off for continuous-tine time episodic reinforcement learning with linear-convex models," arXiv preprint arXiv:2112.10264 2021.
[43] M. K. S. Faradonbeh and M. S. S. Faradonbeh, "Bayesian algorithms learn stabilize unknown continuous-time systems," arXiv preprint arXiv:2112.15094, 2021.
[44] I. Karatzas and S. Shreve, Brownian motion and stochastic calculus. Springer Science & Business Media, 2012, vol. 113.
[45] G. Chen, G. Chen, and S.-H. Hsu, Linear stochastic control systems. CRC press, 1995, vol. 3.
[46] J. Yong and X. Y. Zhou, Stochastic controls: Hamiltonian systems and HJB equations. Springer Science Business Media, 1999, vol. 43.
[47] H. Pham, Continuous-time stochastic control and optimization with financial applications. Springer Science & Business Media, 2009, vol. 61.
[48] P. Bhattacharyya and L. H. Keel, Linear Multivariable Control Systems. University Press, 2022.
Cambridge
[49] J. T. Bosworth, Linearized aerodynamic and control law models of the X-29A airplane and comparison with flight data. National Acronautics and Space Administration, Office of Management ... 1992 vol. 4356.
[50] Ishihara, H.-J Guo, and H. Takeda, "A design of discrete-time integral controllers with computation delays via loop transfer recovery," Automatica, vol. 28, no. 3, pp. 599-603, 1992.
[51] P. Cheridito, H. M. Soner, and N. Touzi, "Small time path behavior of double stochastic integrals and applications to stochastic control," The Annals of Applied Probability, vol. 15, no. 4, pp. 2472-2495, 2005.
[52] B. Laurent and Massart, "Adaptive estimation of quadratic functional by model selection," Annals of Statistics, pp. 1302-1338, 2000.
12

---

[53] A. Tropp, "User-friendly tail bounds for sums of random matrices," Foundations of computa- tional mathematics, vol. 12, no. 4, pp. 389-434, 2012.
[54] M. K. S. Faradonbeh, M. S. Faradonbeh, and M. Bayati, "Thompson sampling efficiently learns to control diffusion processes," arXiv preprint arXiv:2206.09977 2022.
[55] T. Zhou, J. L. Dickson, and J. Geoffrey Chase, "Autoregressive modeling of drift and random error to characterize a continuous intravascular glucose monitoring sensor," Journal of Diabetes Science and Technology, vol. 12, 1, pp. 90- 10-104,2 2018.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]: ; See Sections 3 and 4
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]: See Theo- rems as well as their discussions.
(b) Did you include complete proofs of all theoretical results? [Yes]; Proofs are provided
in the longer version of the paper [54].
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either the supplemental material or as a URL)? [Yes] See
Section 6
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]: The reported curves reflect the worst-case analysis and so no error bars are needed.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "kUfI8F-O0j", "reviewer": "Reviewer_Vgkm", "summary": "The paper studies policies for systems that evolve according to Ito stochastic differential equation (1) with unknown drift parameters. The cost function is quadratic. The goals are: first, to minimize the regret; and second, to accurately estimate the drift parameters. The authors first propose Alg. 1 and show that with high probability it stabilize the process. The they propose Alg 2 using Thompson Sampling. Regret bound and estimation rates are given in Theorem 2. Experiments are conducted comparing the proposed method to reference [2].", "questions": "The first part of the paper focuses on stabilization. But Definition 1 is given before proper introduction. Moreover, the definition directly refers to the eigenvalues of the closed-loop matrix, which uses a linear feedback. Perhaps it would be better to give some intuitions about stability of the system and what the failure event implies. Also, does Algorithm 2 have similar stability result?\n\nThe numerical results in Figure 1 suggest that the randomized estimation performs better in terms of the normalized estimation error. How would you interpret the results?\n\nThe problem setting is very similar to reference [2]. It would be better to elaborate the introduction about [2], especially because it is also used as the baseline.", "limitations": "not applicable", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThere is a gap in the literature on applying TS to controlling the continuous-time diffusion process. The paper first provide algorithms and analysis for such method. Detailed proofs are given in the appendices.\n\nWeaknesses:\nThe problem setting is very similar to reference [2]. The experimental results in section 6 and appendix D do not  reflect a significant improvement. In fact, the normalized estimation error using randomized estimation seems to be better than the proposed method on average.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RFL5JD63BZ", "reviewer": "Reviewer_59Mc", "summary": "This paper proposes a Thompson-Sampling-based method to learn how to make decisions in a class of continuous-time linear-quadratic (LQ) problems with unknown coefficients in the linear dynamics.\n", "questions": "Please address the comments listed above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: Reinforcement Learning (RL) for LQ problems is a tropical topic in recent years since it is the building to understand how machine learning methods perform for general decision-making problems. Thompson Sampling, on the other hand, is a practically-popular and theoretically-plausible algorithm for bandits and reinforcement learning method for Markov Decision Process (MDP) due to its efficiency in exploration. Therefore, it is interesting to see what additional benefit Thompson Sampling could bring to the LQ problem compared to the existing methods.\n\nCons: The contribution seems to be marginal compared to two existing papers [1] and [2]. [1] showed that the continuous-time least-squares algorithm leads to logarithmic regret and hence greedy algorithm (with no exploration) is sufficient for finite-horizon LQ problem. [2] proved an $O(\\sqrt{T})$ regret for infinite-horizon ergodic LQ problem in discrete time. \n\nIt is not clear, from both theoretical and empirical perspectives, what is the benefit of using Thompson Sampling (or Guassian exploration on the estimated model parameters). This is because it has been shown in the literature that:\n\n(1) LG problems have self-exploration properties (due to the Gaussian noise in the linear dynamics) and the least-square estimate (exploration-free method) leads to log regret bound [1]\n\n(2) Using linear regression to estimate parameters in the dynamics is sample efficient [3]\n\n[1] Basei, Matteo, et al. \"Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon.\" arXiv preprint arXiv:2006.15316 (2020).\n\n[2] Abeille, Marc, and Alessandro Lazaric. \"Improved regret bounds for thompson sampling in linear quadratic control problems.\" International Conference on Machine Learning. PMLR, 2018.\n\n[3] Dean, Sarah, et al. \"On the sample complexity of the linear quadratic regulator.\" Foundations of Computational Mathematics 20.4 (2020): 633-679.\n\n==========\nI have read the reviews from other reviewers and the responses from the authors. The authors have addressed my concerns and I raised my rating to 6.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8AwzIScQmq", "reviewer": "Reviewer_qy7p", "summary": "I do not have the background to give a reasonable assessment. So, please ignore this review. ", "questions": "No", "limitations": "I can't see any limitations and potential negative societal impact from their work.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I do not have the background to give a reasonable assessment. So, please ignore this review. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "4mrxfdFoWO", "reviewer": "Reviewer_u7y2", "summary": "The paper discusses Thompson sampling for linear-quadratic continuous-time stochastic optimal control problems. \n\nThe analysis and numerical algorithms are developed using a conjugate Gaussian prior distribution. \nThe paper discusses thoroughly theoretical implications, including (i) a bound on the probability of not stabilizing the system under a linear exploration strategy, (ii) a bound on the squared estimation error, and (iii) a finite-time regret bound.\n\nThe developed algorithm is numerically investigated using some synthetic examples of stochastic optimal control problems.", "questions": "Something I did not understand was in the paragraph in line 131:\n\"We assume that the process (1) with the drift parameter [...] is stabilizable. Therefore, [...] exists, is unique, and can be computed using continuous-time Riccati differential equations similar to (5), except that the zero matrix on the right-hand side will be replaced by the derivative of [...] [32–35].\"\nWhat is meant by this? I know of the Riccati equation for finite-time optimal control problems, which is an ODE. Though, here an average reward criterion is discussed. Maybe the authors can elaborate a bit on this.\n\nIn line 192: \"Nonetheless, if there is no such prior, we simply let [...] and [...].\" This formulation confuses me. I think it shadows a bit that the hyper-parameters are set in this way because in the proceeding bounds the hyper-parameters $\\hat{\\mu}_0$ and  $\\hat{\\Sigma}_0$ are not appearing anymore. Some explanation for this would be appreciated.\n\nThe last question I have is: Would it be possible to also derive these bounds under different posterior distributions than a Gaussian? For example when using a sparsity-prior.", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It was very surprising to me that nobody until now did a theoretical analysis for this linear-quadratic setting. In my opinion, this paper solidly develops theoretical guarantees for the popular Thompson sampling algorithm. Since model-based RL algorithms in continuous-time are still lacking within machine learning, I very much appreciate this work.\nIt is nicely written, and I enjoyed reading it. I appreciate that the authors discuss the intuitive implications of the bandit analysis, which is normally filled with hard-to-understand mathematical intricacies.\n\nA minor point I have to critique is, in my opinion, the claim in line 70:  \"Additionally, through extensive simulations we illustrate that TS enjoys smaller average regret and substantially lower worst-case regret than the existing RL policies, thanks to its informed exploration.\", which is a bit far stretched, as this work only compares one other algorithm to this Thompson sampling strategy.\n\nThis brings me to my main critique point, which is that the topics adaptive control and dual control (Bayesian reinforcement learning within machine learning) are not sufficiently mentioned in the paper, see, e.g., [1]. Theory discussing simultaneous optimal estimation and control is unsurprisingly very old. This goes back to the more than 50-year-old works of Feldbaum [2] and is since then been discussed within the control community. This topic, which in principle optimally solves the problem has to be discussed within the related work.\nThis would also give a nice numerical example. For example, there are very simple dual control problems, see, e.g., [3], where one could try to find the solution to the HJB equation numerically using the finite difference method. This would result in a control strategy that Bayes-optimally selects the actions and hence, balances exploration and exploitation optimally.\n\nHowever, all critique aside, I am of the opinion that this paper is a solid contribution to the community.\n\n- [1] Stengel, Robert F. Optimal control and estimation. Courier Corporation, 1994.\n- [2] Feldbaum, Aleksandr Aronovich. \"Dual control theory. I.\" Avtomatika i Telemekhanika 21.9 (1960): 1240-1249.\n- [3] Florentin, J. J. \"Optimal, probing, adaptive control of a simple Bayesian system.\" International Journal of Electronics 13.2 (1962): 165-177.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept