Augmented RBMLE-UCB Approach for Adaptive Control of Linear Quadratic Systems
Authors: Akshay Mete
Rahul Singh
Panganamala Kumar
Venue: NeurIPS 2022 Accept (2022)
Keywords: adaptive control
reinforcement learning
LQG systems

Abstract: We consider the problem of controlling an unknown stochastic linear system with quadratic costs -- called the adaptive LQ control problem. We re-examine an approach called ``Reward-Biased Maximum Likelihood Estimate'' (RBMLE) that was proposed more than forty years ago, and which predates the ``Upper Confidence Bound'' (UCB) method, as well as the definition of ``regret'' for bandit problems. It simply added a term favoring parameters with larger rewards to the criterion for parameter estimation.  We show how the RBMLE and UCB methods can be reconciled, and thereby propose an Augmented RBMLE-UCB algorithm that combines the penalty of the RBMLE method with the constraints of the UCB method, uniting the two approaches to optimism in the face of uncertainty. We establish that theoretically, this method retains ${\mathcal{O}}(\sqrt{T})$ regret, the best known so far. We further compare the empirical performance of the proposed Augmented RBMLE-UCB and the standard RBMLE (without the augmentation) with UCB, Thompson Sampling, Input Perturbation, Randomized Certainty Equivalence and StabL on many real-world examples including flight control of Boeing 747 and Unmanned Aerial Vehicle. We perform extensive simulation studies showing that the Augmented RBMLE consistently outperforms UCB, Thompson Sampling and StabL by a huge margin, while it is marginally better than Input Perturbation and moderately better than Randomized Certainty Equivalence.

Augmented RBMLE-UCB Approach for Adaptive Control of Linear Quadratic Systems
Akshay Mete Texas A & M University College Station, Texas, USA
Rahul Singh Indian Institute of Science Bengaluru, Karnataka, India
akshaymete@tamu.edd
Shhulsinghhiisce in
P. R. Kumar Texas A & University College Station, Texas, USA prk@tamu. edu
Abstract
We consider the problem of controlling an unknown stochastic linear system with quadratic costs called the adaptive LQ control problem. We re-examine an ap- proach called "Reward-Biaser Maximum Likelihood Estimate" (RBMLE) [ that was proposed more than forty years ago, and which predates the "Upper Confi- dence Bound" (UCB) method as well as the definition of "regret" for bandit prob- lems (2]. It simply added term favoring parameters with larger rewards the criterion for parameter estimation. We show how the RBMLE and UCB methods can be reconciled, and thereby propose an Augmented RBMLE-UCB algorithm that combines the penalty of the RBMLE method with the constraints of the UCB method (3), uniting the two approaches optimism in the face of uncertainty. We establish that theoretically, this method retains ((VT) regret, the best known far. We further compare the empirical performance of the proposed Augmented RBMLE-UCB and the standard RBMLE (without the augmentation) with UCB, Thompson Sampling, Input Perturbation, Randomized Certainty Equivalence and StabL on many real-world examples including flight control of Boeing 747 and Unmanned Aerial Vehicle. We perform extensive simulation studies showing that the Augmented RBMLE consistently outperforms UCB, Thompson Sampling and StabL by huge margin, while it is marginally better than Input Perturbation and moderately better than Randomized Certainty Equivalence.
1 Introduction
Consider a linear stochastic system F++1 A" + B+ + W1-1, where I, R", u, E R and wi E RR" are the state, control applied, and state noise, respectively, at time f. We study the adaptive where the controller's goal to minimize the expected finite horizon quadratic cost E ED' (x] Q2, + u, Ru;) by choosing the control input based on observing the past states and controls, without the knowledge of "true parameter" 0" (A*, BB)), The deviation from what would have been optimally possible had the true parameter been known is measured by the "regret," (2), R(T) := Σ (aIQx, + u, Ru) T J (8*). where J+(0*) = lim supp-+0
control/reinforcmmnnt learning problem 44
5
6
ET 1 (o) Qa, + un Rui) the optimal average cost achievable when
(A*, B*) are known.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

For this adaptive linear- linear-quadradd quadratic (LQ) control problem, there are broadly four classical approaches: the Reward- Reward-Biased Biased Maximum Likelihood Estimate (RBMLE) approach [T. the Diminishing Ex- citation (DE) approach [ the Upper Confidence Bound (UCB) approach [2), and the Thompson Sampling (TS) 9 approach based on sampling from the posterior distribution. The RBMLE and UCB approaches are "certainty equivalent" (CE) in the sense that they make an estimate 0, of the unknown true parameter, and then take an action u, = K (0.)ar that would be optimal if the estimate & were indeed the true parameter. They only differ in what parameter estimate they choose. The DE approach applies u4 K ((0))ar + le. where is an added "excitation," an independent noise, of diminishing variance and 0g is the maximum likelihood estimate. The Randomized Certainty Equivalence (RCE) [10] adds excitation to the parameter estimate.
1.1 The Contributions
We unite the two approaches to "optimism under uncertainty". RBMLE 1 and UCB (2, by showing that the RBMLE method ís penalty version of the constrained optimization
problem of UCB for the case of linear quadratic systems [T] 12 13 14 3). Based on this
we propose an Augmented RBMLE (ARBMLE) method that combines the penalty and constrained versions so that on the one hand it retains the analytical tractability UCB and on the other hand provides the performance of RBMLE.
2. We determine how to choose the biasing factor att) for ARBMLE, and establish finite time regret bound Ö(VT), the same as the OFULQ algorithm of 3 the best order avail- able to date.
3. We perform extensive comparative simulation studies of the performance of:
(a) ARBMLE and the standard RBMLE
(b) OFULQ 3 which is the UCB-approach adapted to the LQ problem.
(c) TS 15 which is the Thompson sampling approach adapted to the LQ problem
(d) Input Perturbation (IP) [16] which is a recent reincarnation of DE for the adaptive LQ problem that additionally assumes apriori knowledge of a stabilizing controller.
(e) Stabl 17
modified OFULQ that adds "excitation" to the input for initialization. RCE 10 which adds excitation to the Least Squares Estimate (LSE).
(f)
The examples used for simulation study have been used in many recent papers
17), namely (a) the longitudinal flight control of Boeing 747 with linearized dy- namics 17 (bb Unmanned Aerial Vehicle (UAV) 20 17 (c) unstable Laplacian dynamics 18]. and (d) large transient dynamics [88. Our simulation results show that ARBMLE outperforms OFULQ, TS and StabL by large margin, which is primarily due to lack of stabilization experienced by OFULQ and TS (17.. RCE also exhibits a higher regret than ARBMLE. While the empirical performance of IP is marginally worse than ARBMLE. The results show that the ARBMLE has the same performance (21). and they both outperform all the above other algorithms. Notably the choices made by ARBMLE and OFULQ within the confidence interval are very far apart, with ARBMLE outperforming OFULQ by large margin.
18
19
the original RBMLE
1.2
Previous Works
Prior work RBMLE has concentrated establishing long-term average optimality 22 23
11
24
25
12,
13.
14
26
27 28. Recently, its regret performance has been addressed for Multi-
Armed Bandits (MABs) 29 linear contextual bandits (30), and MDPs B1. Forced exploration
techniques, somewhat similar in spirit to the (g-gredy learning algorithm of 7 32), are studied in
33
34
35
vis-a-vis ensuring that they do not suffer from the insufficient exploration. An adaptive
LQG control based on the UCB approach, called OFULQ, is proposed in (3 which establishes
regret of Ö(VT). A similar algorithm to address the adaptive LQG control problem is also designed
in 36 A computationally efficient algorithm called ROBUST with a regret of Ö(T3) 3 is proposed in
An alternative approach for designing learning algorithms Thompson sampling [9, and [37]
38
have established an expected regret of ((VT) in a Bayesian context. More recently, new DE-
based algorithms, IP [16 and RCE [10] have been proposed that make additional assumption, not

---

made in ARBMLE, OFULQ or TS, that one has access to stabilizing controller for the unknown system, and establish ((VT) regret.
1.3 The RBMLE Approach
The RBMLE approach, proposed four decades ago M. was the first approach not resorting to forced choices as in 39]. We begin by giving informal description of it in the context of the adaptive LQ problem. Since the true parameter 0* == (A", )² is not known, one can make Least-Squares
Estimate (LSE) 0 = (A,, B²) of them:
0. E ArgMing=(A.BB)
Σ |1 Ax, Bu,l12
(1)
==0
Under the the optimal linear feedback gain for the LQ problem when the system is described by 0 (A, B) Suppose now that these estimates were converge + to 6x (A Box Then, asymp- totically, the input applied is ue R K (00x) )at. The closed-loop system therefore settles down to behaving according to
approach, the control input applied is u, = K (0; 22 where K K(0) is
1+41 ~ (A" B'K((x))) W1+11
As it does so, one loses the ability to identify the matrices (A", B*), and asymptotically one can only identify the closed-loop gain A B 1* ((..)). The problem is that as the parameter estimates begin to converge to A the control gain converges K(0x)) and further exploration ceases, and one ends up only identifying the behavior of the system under the limiting gain K (0,2) being applied to the system. Since the limiting policy Ue = K 00 )z, need not be optimal for the long-term average sub-optimal performance. Indeed, this the closed-
cost for the true system (A*BB* the CE rule leads
problem goes by various names in different fields the dual control problem 40 41
identifiability problem [42 43 44 or exploration vs. exploitation dilemma
This problem was resolved in without resorting to forced exploration as in 39 The key ob- servation made there was that under CE the limiting parameter estimate O(oo) has one-sided bias. Specifically, J (Ôxx)) 2 (0*), i.e., the limiting parameter estimate has an optimal cost that is larger than the optimal cost of 0*. To see this, denote by J J(K, 0) the long-term cost of using the control gain K when the parameter is 0. Then the fact that the models 0.0 and 0* have identi- cal behavior under the gain ((xx)) implies that J ((((0x)) 0oc) = JK (dx))..). 6r). Now note that J ((=)))),, (roo since the gain K ((((c))) is optimal for 0x However the gain K (0x0) is necessarily optimal for 0*, and J (( 0*) > (0*).. Therefore,
J (0x) = J(K( 0.) = 20))))
(3)
Following from this observation, it was reasoned in ( that if one could slightly bias the MLE to favor models with lower optimal costs (+) to obtain (+x)) S J**)),, then one would have equality throughout (3). to obtain (K (0x), 0-) (0-),, yielding the desired result that the gain K (0xz) is optimal for 6* So motivated, [1] proposed RBMLE which in the context of the LSE suggests choosing the parameter estimate ÓRBMLE(T) (ARBMLE. BREMLE) as:
ÜRBMLE(t) E ArgMin,- [a(t))
|| - Ar. Buel?
(4)
Generally att) = o(t) with the precise growth rate of a(t) / too dependent on the context.
It has been called the Cost-Biased MLE, as in 12 or Reward-Biased MLE (RBMLE) in 29 depending whether minimizes cost maximizes reward.

---

1.4 The UCB Approach
The "Upper Confidence Bound" (UCB) approach was first proposed in the context of Multi-Armed Bandit (MAB) Problems in (2]. In the context of Bernoulli bandits, it essentially consists of con- structing, for each arm i at each time probability with confidence (1 - -(1), for 5(L) o( o and playing the arm i with the highest value of (i, 1;4). This approach has been generalized to variety of contexts including linear contextual
confidence interval (8(,, (ii. 2))) of its payoff
bandits 46 Gaussian Processes 47.. MDPs 48 49), and LQ systems 3
Particularized to LQ systems, the OFULQ algorithm of 3 that is based on the UCB approach suggests choosing (oFLUQ()) = (AoFULQ. BOFULQ) as the minimizer of:
min (0),,, where (E)
(5)
C, 11-100-00 ().
[s41
Ar. - Bu,ll² S vT(())
(6)
==0
a (1 Shghigh confidence set of parameters for an appropriate choice of yr (6) 3
2 The Augmented RBMLE-UCB Method
The UCB approach has been called "Optimism in the Face of Uncertainty" (OFU), since chooses an optimistic arm after calculating the confidence intervals. The RBMLE version is also the same, though it does rewards. It arrives at optimism in very systematic way by noticing that closed-loop identification leads to the chain incqualities
different way by directly giving preference to parameters that can yield better
3 which could then be made into equalities by ensuring that
J+(00)) < (0*).
We now show how one may reconcile the two approaches to optimism in the face of uncertainty in the context of the LQ problem, and then combine them to obtain a method that has experimentally superior empirical performance while also allowing a proof that it achieves the currently best known order regret.
It can be seen that the RBMLE approach (4) can be considered an unconstrained penalty version _ for constraint violation. of the constrained optimization problem (6 with a penalty factor a<e)
This provides a justification for employing "optimism" in the UCB approach.
This raises the question of whether we can take advantage of these synergies to fashion a superior algorithm, that is superior from the viewpoint of being able provide a theoretical guarantee of the best known order of regret to date, as well as superior from the point of view of providing the best experimental performance of the algorithms Augmented Lagrangian Method of [50, [SI] Given constrained problem as in (5)-()), it adds penalty for constraint violation, and also adjoins the constraint through a Lagrange multiplier, thus involving the constraint twice. In our case, we add the penalty and also retain the constraint. This leads to the Augmented RBMLE-UCB method:
date. One can draw inspiration here from the
(oooccssss((())( (a(t)>((0) Σ | Ar, 11.
Aug (t) ArgMing
The advantage of retaining the constrained optimization is in enabling theoretical analysis, in that we can make use of the bounds on parameter estimates from concentration inequalities, as we shall show in the sequel. We thereby prove in Section 4 that it also has Õ(VT) order of regret, which is the best known so far [3]. Moreover, simulations reported in Section 5) show that its performance is also much improved. In all cases, the simulation performance of ARBMLE is the same as RBMLE, raising the open problem of proving that the original RBMLE for the LQ problem also has the best known order of regret.
3 Problem Formulation
As introduced in section we consider the following linear system,
Tt+1
ATx,,
Bu,, + Wi+1
(8)

---

where, A E R and B E R" are unknown system parameters. Define 27 == (2) u, Then, the linear stochastic system can equivalently be written as
I++1 -0- + w1++1
The system incurs cost at time given by, x QTx + 2n Ru,. We assume that Q E R and R E R are known positive semi-definite and positive definite matrices respectively. We make the following assumptions on
(A).B*)..
There exists a known positive constant e. such that 6* E S = So n S1 where, Su (0- = B) (A, B) stabilizable and Q122) is detectable (A, B) (trace( cc.
Assumption 1.
(54), and S {0
Let Fr := (( uo); (2), until time i. The state noise {wi) is a martingale difference sequence with respect to {Ft). with Elwe+ww44113
Assumption 2.
Ue)) denote the history of states and inputs
Ins and is element-wise nau--aussian, i.e., for any 7 E R, there exists L >
with E [ezp()we,,) Fil S exp 11. V and V t.
For matrix M, we use || to denote its operator norm induced from the 4oonr.m
3.1 Controller Design for Known LQG System
For discrete time linear system, Fe+11 0T W1+1, where 0 (A, B)T E S, there is unique positive semidefinite matrix P(0) that satisfies the Riccati equation (see [6]
P(O) Q + AT A AT ((O))B((BT(O))) BB P(O)A.
The optimal control law which minimizes the long-term average quadratic cost is u4 = K(0 P() The optimal average cost,
where the "gain matrix" is K(#)= := - P()) B + (0) is equal to trace( (ra))) As a consequence of Assumption the parameter set bounded, hence one can show that P(0) is bounded as well:
D = sup |P(())] < oc.
(10)
dES
The following assumption is commonly made online LQR learning problem in which the knowl- edge of stabilizing controller is not made [3 38). Assumption 3.
p sup AES
|A + BK(0) < 1, and
(11)
sup [(]]] < +oc. OES
(12)
Note that there are recent works which relax [I] slightly to supaes p(A+ BK(0)) < 1, however
they assume that the learner has access to stabilizing controller [8 55 56
3.2 Construction of Confidence Interval
The éz-regularized squared fitting error with parameter À > 0 given by:
Vi(0) = 2llllak
| - 0T 2z.1
(13)
==0
Let O, be the by regularized least-squares estimate of 0*, if,i,...,00 0, E arg minses Vo(O). Next, given the history Fr, we construct a thigh-probabiliis confidence ball," (d) around 0,, i..., set of plausible system parameters that contains the true parameter 0* with high probability. Let
(6) == {0. trace (10 (10- 0.) 6.) S {())).
(14)
We note that though requires each 0 from So to satisfy the stronger machability-ossevabiiie assumption, the results therein hold true this is replaced by the weaker tion (52) p.61]. In fact all that is required for the proofs to go through, is that for each 0 E So. the corresponding (53) that stabilizability and detectability. as above, is
assump-
Riccati equation have a unique solution. It is sufficient for this.
5

---

where Zt == Xna+m + Ei=o Z52g, f and
(.
Be(6)= = nly, 2og
+ VTc
(15)
6
Define
and (t) = 10t E C,/44)) === ,t) and (t) = {||=|| |1 - d,, as s)
(16)
where de is defined in the Appendix. Let &l (T) and & (T) Then, as in ( &2) 2 2- Moreover, on the event (t) defined in (6)) the following holds,
3
max | S Xx yutm+l 1I ...... where, 1se50
(17)
Y max
e, (nnn dd(( -1
4 ci log
1 + 02 log )))
log² 4ci log
(t)
t 402 log
) 5
with and being problem dependent constants.
4 The Augmented RBMLE-UCB Algorithm
We employ a version the Augmented RBMLE-UCB (ARBMLE) algorithm that proceeds in an episodic manner. Let la denote the starting time of the k-th episode. Then, during episode k; it implements the control policy, v, K(r,,) )x,, A (44, ......44. .4+1 - 13. where, 0z, obtained by solving the following optimization problem.
Olc E arg min (V), + (())))
(18)
BEsnCi, (8)
where the bias-term, a(I) Vg Vt, for ag
Algorithm Augmented RBMLE-UCB (ARBMLE)
Initialize: = 0, 7%0 Am
for 0, 1, do
if det( > 2det 2det(Zr... ( then
solve the following optimization to obtain Oz*
E arg min BesniC, (8)
(Vi, (0) aa(t))/
else 0: 01-1
end if
14 K(())
7++1 -
Ze + 2
end for
In Theorem 4.1 we show that regret for ARBMLE is upper bounded by Ô (VTTToo T/ol same order as OFULQ 3.
which is
Theorem 4.1. For any 8 E (0,1) and T with a probability at least (1 (1-8), 8). the regret of the ARBMLE Algorithm upper-bounded by R(T) s Ö (VTlog) !).
Proof. Appendix A.1

---

Ex.
RBMLE
ARBMLE
OFULQ
TS
IP
RCE
STABL
(a)
3233
3233
1.2 x 10
4.2 x 10"0
3251
3408
1.8 X 10
(b)
5930
5930
5.4 x 10"2
2.8 X 10th
5955
6396
1.9 X 10TH
(C)
16144
16135
2.1 x 10
1.1 X 1020
16164
180639
1,2 X 10
(d)
540297
528805
4.9 x 10
8.2 x 10"h
540248
2.2 10a4
1.4 x 10
Table 1: Average Regret Performance T 500.
5
Empirical Performance
We evaluate the empirical performance of ARBMLE as well as standard (unaugmented) RBMLE. We compare these algorithms with OFULQ (3. Thompson Sampling (TS) [15, Input Perturbations
(IE) [16], Randomized Certainty Equivalence (RCE) [I0), and Stabl [17] The results shown here are for the following examples of linear systems that have appeared in the recent literature on adaptive control of linear systems:
1. Unstable Laplacian dynamics
18
17
2. Large transient dynamics 18
3. Unmanned Aerial Vehicle (UAV) 20
4. Longitudinal Flight Control of Boeing 747
The details of these examples are provided in the Appendix.
Each simulation experiment is performed for a time horizon of 500 steps, and repeated 50 times. The reported results the averaged values of the averaged regret of ARBMLE, OFULQ. TS and Stabl. In Figure 2, we plot the averaged regret of RBMLE, ARBMLE, IP and RCE. We summarize the results using the regret values at 500, averaged over the 50 runs, in Table [ Results for more examples are provided in the Appendix. Details of the implementations
the 100 runs. In Figure 1, compare the log10
be found in the Appendix.
We highlight the key observations from above experiments:
ARBMLE and RBMLE always found have the same empirical performance in most cases. More specifically, both these algorithms choose the same estimate 6,, and this suggests that a(t) needs to be greater than the Lagrange multiplier for the ball constraint O Ct2y (6). This also motivates future study of the regret the (unaugmented) RBMLE.
As can be seen in Figure [ ARBMLE/RBMLE outperform OFULQ and TS by a huge margin. We conjecture that this is due to temporary instability when OFULQ. TS are em- ployed [7]. ARBMLE/RBMLE also has a signficantly lower regret as compared with StabL.
Figure shows that ARBMLE/RBMLE also outperforms RCE moderately, and IP marginally.
Remark Our simulations for ARBMLE, OFULQ and TS are based the confi- dence interval 3x(5) as defined in (15). Instead, recent works [17 18] use Br(ō)
trace (00- ( -b:)) ing agent, and so such a definition of Be(5) is not a viable implementation. The effect of the choice of (,) on the regret performance is shown in the appendix.
However, one may note that 6* in 3r(5) is not known to the learn-
6 Concluding Remarks
We reconcile the RBMLE and UCB approaches by showing that RBMLE is an unconstrained penalty version of the constrained optimization problem of UCB. Showing that UCB a con- strained version of RBMLE also explains why the optimism embodied in JCB-based schemes is justified. In particular, it justified by the goal of nullifying the one-sided bias that results from the closed-loop identification of dynamics.
7

---

ARBMLE
ARBMLE
10
DFULQ
OFULQ
Building on this, we propose an Augmented RBMLE-UCB method that not only matches the best known order of regret, (( to date that of the OFULQ algorithm but also outperforms OFULQ, TS and Stabl by significant margin simulation experiments. In fact, for the UAV experiment, the regret of OFULQ is ~ 10 TS = 10 and Stabl. ~ 10 times that of RBMLE. It outperforms RCE also, but the gains are moderate, while with respect to the gains are smaller. The simulations were carried out on real-world examples such as Boeing 747, UAV, Unstable Laplacian on adaptive Lo (Regret)
TS
Logso(Regret)
TS
STABL
1.
STABL
2
100
200
500
400
500
100
200
300
400
500
Time Horizon
Time Horizon
(a) Unstable Laplacian
(b) Large Transient Dynamics
20.0
ARBMLE
12
ARBMLE
Loggu(Regre]
17.5
TS
OFULQ
Log:o(Regret)
10
OFULQ
TS
STABL
STABL
12.5
10.0
100
300
402
500
100
200
300
400
500
Time Horizon
Time Horizon
(c) UAV
(d) Boeing 747
Figure 1: Logarithm of the Averaged Regret over 50 runs RBMLE, ARBMLE, OFULQ and TS for various example systems.
and Large Transient Dynamies which were taken from recent works 18 55 LQG control.
This work further extends recent studies of RBMLE for MDPs 31 stochastic Multi-Armed Ban- dits [29] and Contextual bandits 330 establishing state-of-art regret results as well as empirically good performance.
There remain several open questions.
Currently we study only augmented form of RBMLE, i.e. ARBMLE, in which the agent searches for parameter value that optimizes a certain reward- biased maximum likelihood objective function within "high-confidence ball." However, (unaugmented) RBMLE optimizes this over the larger set S (Assumption) that known to contain true parameter. The reason for this augmentation is simply that currently we are unable prove regret bounds for RBMLE without it. By including it, we can capitalize on the nice technical results in (3] in the analysis of OFULQ. Simulations show that the constraint is loose, and performance is the same with/without the constraint. In fact, as shown by the simulations, the choices of 0z, made by the standard RBMLE, and the Augmented RBMLE are the same. It remains to be seen whether similar regret guarantees can be obtained by the (unaugmented) RBMLE, which remains an open problem.
One may note that ARBMLE and OFULQ differ in their choices of decisions. Denoting their esti- mates of the unknown parameter at given time by AarbMle e and fouuL respectively, OOFUL always lies at the boundary of the UCB-ball constraint. This is easily seen to be true for bandits and MDPs, and empirically observed to so for LQ systems. contrast, AARBMlE most often in the interior of the UCB-ball. Moreover, while OFULQ treats all models within the UCB-ball equally and only

---

3.5
RBMLE ARBMLE
RBMLE ARBMLE
3.5
LogioRRegreg
3.0
Log:ofRegret)
3.0
2.5
2.5
2.0
2.0
1.5
1.00
200
300
400
500
Time Horizon
Time Horizon
(a) Unstable Laplacian
(b) Large Transient Dynamics
6.0
RBMLE
RBMLE
14
ARBMLE
10gio(Regrep
5.0
Logio(Regret)
12
RCE
3.5
2.5
100
200
300
400
500
100
200
300
400
500
Time Horizon
Time Horizon
(c) UAV
Boeing 747
Figure 2: Logarithm of the Averaged Regret over 50 runs of RBMLE, ARBMLE, IP and RCE for various example systems. Table providees the quantative results for finer comparative evaluation of the regrets.
assesses them by their cost, ARBMLE prefers models that are closer to the Least Squares Estimate (OLSE). For example, if (01) J (02). then ARBMLE prefers the 6, that closer OLSE We conjecture that this is the reason why ARBMLE has significantly better performance than OFULQ but we are unable prove it.
has been shown in previous works on adaptive LQG control 12 that under appropriate for- mulations RBMLE is guaranteed to stabilize an unknown LQG system over an infinite horizon, i.e., lim simsupr-so + El ([]=(t)]1 [|u(t)]]3) oo a.s.. Morover, the sample path performance cost Ei
lim s T -==1 (xT())xz(1) u (L) is (a.s.) equal to the optimal performance that could be attained if the system parameters (A*, B*) were known. In fact, stability is a prerequi- establish the latter type of result, the decades of work stochastic adaptive control in the nineteen seventies to the nineties has shown. While recent work has tended to study the finer performance measure of regret, it is usually over finite horizon, and more attention to the stability of the learning process over an infinite horizon appears well deserved. Similarly, robustness which also rigorously formulated and addressed in earlier decades needs to be re-examined [57].
site before
Acknoweldgments
This material is based upon work partially supported by the US Army Contracting Command un- der W91 US Office of Naval Research under N00014-21-1-23885; 4/21-22 DARES: Army Research Office W91 INF-21-20066 US National Science Foundation under CMMI-2038625, The views expressed herein and conclusions contained in this document are those the authors and should be interpreted as representing the views official policies, either expressed im- plied, of the U.S. Army Contracting Command, ONR, ARO, NSF, or the United States Government. The U.S. Government authorized reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. The work of Rahul Singh was partially supported by the SERB Grant SRG/2021/002300 and PC 39010B.

---

References
[1] R. Kumar and A. Becker. A new family of optimal adaptive controllers for Markov chains. IEEE Transactions Automatic Control, 27(1):137-146, 1982.
[2] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4 22, 1985.
[3] Yasin Abbasi- Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1-26. JMLR Workshop and Conference Proceedings, 2011.
[4] Karl Äström and Björn Wittenmark. Adaptive control. Courier Corporation, 2013.
[5] P. R. Kumar. A survey of some results in stochastic adaptive control. SIAM Journal on Control and Optimization, 23(3)3329-380, 1985.
[6] R. Kumar and Pravin Varaiya. Stochastic systems: Estimation, identification, and adaptive control. Prentice-Hall, Englewood Cliffs, NJ, 1986.
[7] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[8] Han-Fu Chen and Lei Guo. Identification and stochastic adaptive control, volume 5. Springer Science & Business Media, 1991.
[9] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933.
[10] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. On adaptive linear-quadratic regulators. Automatica, 117: 2020.
[11] R. Kumar. Optimal adaptive control of lunear- quuusatia--aaaussiinnn systems. SIAM Journal on Control and Optimization, 21(2):163-178, 1983.
[12] Marco C. Campi and P. Kumar. Adaptive linear quadratic Gaussian control: the cost-biased approach revisited. SIAM Journal on Control and Optimization, 3606):1800-1907, 1998.
[13] Maria Prandini and Marco C. Campi. Adaptive lqg control of input-output systems- cost- biased approach. SIAM Journal on Control and Optimization, 3995):1499-1511 2000.
[14] Sergio Bittanti, Marco C. Campi, al. Adaptive control of linear time invariant systems: the "Bet on the Best" principle. Communications in Information & Systems, 6(4):299-320, 2006.
[15] Mare Abeille and Alessandro Lazaric. Thompson sampling for linear-uudraati control prob- lems. In Artificial Intelligence and Statistics, pages 1246-1254 PMLR, 2017.
[16] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Input pertur- bations for adaptive control and learning. Automatica, 117:108950, 2020.
[17] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Animashree Anandkumar. Rein- forcement learning with fast stabilization linear dynamical systems. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages
PMLR, 28-30 Mar 2022.
[18] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018.
[19] Yasin Abbasi-Yadkori, Nevena Lazic, and Csaba Szepesvári. Model-free linear quadratic con- trol via reduction to expert prediction. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 3108-3117. PMLR, 2019.
10

---

[20] Feiran Zhao, Keyou You, and Tamer Basar. Infinite-horizzn risk-constrained linear quadratic regulator with average cost. In Proceedings of the 60th IEEE Conference on Decision and Control (CDC), pages 390-395. IEFF, 2021.
[21] Marco C. Campi and P. R. Kumar. Adaptive linear quadratic Gaussian control: the cost-biased approach revisited. SIAM Journal on Control and Optimization, 36(6):1890-190) 1998.
[22] R. Kumar. Adaptive control with a compact parameter set. SIAM Journal on Control and Optimization, 20(1):9-13 13, 1982.
[23] P. R. Kumar and Woei Lin. Optimal adaptive controllers for unknown Markov chains. IEEE Transactions on Automatic Control, 27(4):765-774, 1982.
[24] R. Kumar. Simultaneous identification and adaptive control of unknown systems over finite parameter sets. IEEE Transactions on Automatic Control, (88(1)68-77) -6887,6,75 1983.
[25] V. S. Borkar. The applications, 66(2):289-33) 1990.
scheme revisited. Journal of optimization theory and
[26] Lukasz Stettner. On nearly self-optimizing strategies for a discrete-time uniformly ergodic adaptive model. Applied Mathematics and Optimization, 27(2):161-177, 1993.
[27] V. S. Borkar. Self-tuning control of diffusions without the identifiability condition. Journal of optimization theory and applications, 18-1):117-33, 1991.
[28] TE Duncan, Pasik-Duncan, and L Stettner. Almost self-optimizing strategies for the adaptive control of diffusion processes. Journal of optimization theory and applications, 81(3):479-507, 1994.
[29] Xi Liu, Ping-Chin Hsich, Yu Heng Hung, Anirban Bhattacharya, and R. Kumar. Exploration through reward biasing: Reward-biased maximum likelihood estimation for stochastic multi- armed bandits. In International Conference on Machine Learning, pages 6248 0288-628. PMLR, 2020.
[30] Yu-Heng Hung, Ping-Chun Hsieh, Xi Liu, and P. R. Kumar. Reward- maximum like- lihood estimation for linear stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7874-7882, 2021.
[31] Akshay Mete, Rahul Singh, Xi Liu, and P. R. Kumar. Reward Biased Maximum Likelihood Estimation for Reinforcement Learning. Learning for Dynamics and Control, pages 815- 827. PMLR, 2021.
[32] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[33] Tze Leung Lai and Ching Zong Wei. Least squares estimates in stochastic regression models with applications to identification and control of dynamic systems. The Annals of Statistics, 10(1):154-166, 1982.
[34] Tze Leung Lai and Ching-Zong Wei. Asymptotically efficient self-tuning regulators. SIAM Journal on Control and Optimization, 25(2):466-481, 1987.
[35] Han-Fu Chen and Lei Guo. Optimal adaptive control and consistent parameter estimates for armax model with quadratic cost. SIAM Journal on Control and Optimization, 25(4))845-867, 1987.
[36] Morteza Ibrahimi, Adel Javanmard, and Benjamin Van Roy. Efficient reinforcement learning for high dimensional linear quadratic systems. NIPS, pages 2645-2653, 2012.
[37] Yasin Abhasi-Yadkori Yadkori and Csaba Szepesvári. Bayesian optimal control of smoothly parame- terized systems. In UAI, pages 1-11. Citeseer, 2015.
[38] Yi Ouyang, Mukul Gagrani, and Rahul Jain. Control of unknown linear systems with thompson sampling. In Proceedings of the 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages (198-1205. IEEE, 2017.
11

---

[39] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
[40] Aleksandr Aronovich Feldbaum. Dual control theory. Avtomatika
i Telemekhanika,
21(9):1240-122 12400,0-22,,1--1 1960.
[41] Björn Wittenmark, Adaptive dual control methods: An overview. Adaptive Systems in Control and Signal Processing 1995, pages 67-72, 1995.
[42] Vivek Borkar and P. Varaiya. Adaptive control of Markov chains, Finite parameter set. IEEE Transactions on Automatic Control, 24(6):953-957, 1979.
[43] Donald A Berry and Bert Fristedt. Bandit problems: sequential allocation of experiments (monographs on statisties and applied probability). London: Chapman and Hall, 5(71-87):7- 7. 1985.
[44] John Gittins, Kevin Glazebrook, and Richard Weber. Multi-armed bandit allocation indices. John Wiley & Sons, 2011.
[45] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[46] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pages 208-214 JMLR Workshop and Conference Proceedings, 2011.
[47] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
[48] Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforce- ment learning. In Advances in neural information processing systems, pages 49-56, 2007.
[49] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1144), 2010.
[50] Magnus R Hestenes. Multiplier and gradient methods. Journal of optimization theory and applications, 3(5):303-320, 1969.
[51] Michael JD Powell. A method for nonlinear constraints in minimization problems. Optimization, pages 283-298, 1969.
[52] Yasin Abbasi-Yadkori. Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, Edmonton, Alberta, 2013.
[53] Frank L Lewis, Draguna Vrabie, and Vassilis L Syrmos. Optimal control. John Wiley & Sons, 2012.
[54] Thomas Kailath. Linear systems, volume 156. Prentice-Had Hall Englewood Cliffs, NJ, 1980.
[55] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sam- ple complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-673 679, 2020.
[56] Max Simchowitz and Dylan Foster. Naive exploration is optimal for online LQR. In International Conference on Machine Learning, pages 8937-8948. PMIR, 2020.
[57] Praly, S-F Lin, and P. Kumar. robust adaptive minimum variance controller. SIAM journal on control and optimization, 27(2):235-266, 1989.
[58] Stephen Tu and Benjamin Recht. Least-squares temporal difference learning for the linear quadratic regulator. In International Conference on Machine Learning, pages 5005-5014. PMLR, 2018.
[59] Tadashi Ishihara, Hai-Jiao Guo, and Hiroshi Takeda. A design of discrete-time integral con- trollers with computation delays via loop transfer recovery. Automatica, 28(3):599-603, 1992.
12

---

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]
(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]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(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)? [Yes]
4. If you are using existing assets (e-g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able 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 to 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 participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "oUFuYmQ41k", "reviewer": "Reviewer_JHn3", "summary": "This paper proposes RBMLE and ARBMLE algorithms for LQR with unknown dynamics. The authors point out that RBMLE for LQR can be viewed as a penalty version for constrained optimization in UCB for LQR. For theoretical purposes, additional constraints are added to the unconstrained optimization (4) in RBMLE, yielding ARBMLE. An O(sqrt T) regret bound is provided for ARBMLE. Then, several numerical experiments are conducted to show that RBMLE and ARBMLE yield similar performance and achieve better performance than existing methods. ", "questions": "See above.", "limitations": "No", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written. The connection between RBMLE and UCB in the LQR problem is interesting and inspiring. The augmented version ARBMLE achieves the best regret order in terms of T. Numerical results show promising improvements over the existing methods. The appendices are also written clearly. The proof is standard and correct.\n\nHowever, I have the following concerns and questions.\n\n1. [Tractability] UCB-LQR is known to be intractable when the dimensionality is large due to the involved constrained optimization. Since ARBMLE also involves the constrained optimization, the proposed algorithm also suffers the tractability problem. \n\n2. [Same numerical results for RBMLE and ARBMLE] The authors claim that numerically, RBMLE and ARBMLE always generate the same theta_t. I found this quite surprising. Does this result still hold for different choices of alpha0 and lambda and beta_t(sigma)? \n\n3. [Dependence on dimensionality] Though the regret bound is optimal in terms of the dependence on T, the dependence on the dimensionality of the problem is not discussed. It has been shown that CE-type (certainty-equivalence) methods can achieve optimal regret even in terms of n and m. How does the regret of the proposed method compare with the optimal dimensional dependence in the literature?\n\n4. [Numerical results] The authors provide four interesting numerical experiments to demonstrate the improved performance. However, all of the experiments consider a relatively small dimensionality.  How do the algorithms perform for larger dimensions, especially in comparison with CE-type methods?\n\n=== Typos ===\n1. Line 168: it should be \\mathcal S instead of S.\n2. Line 253: furtjer.", "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": "gnF9ejJXAUL", "reviewer": "Reviewer_Qpy8", "summary": "This paper revisits two commonly used approaches in online adaptive LQR control: Reward-Biased Maximum Likelihood Estimate (RBMLE) and Upper Confidence Bound (UCB). The authors show that these two methods can be reconciled, and thereby propose an Augmented RBMLE-UCB algorithm that combines the penalty from the RBMLE method and the confidence interval of the UCB method. Theoretically, the authors establish a $O(\\sqrt{T})$ regret upper bound. Empirically, the proposed algorithm outperforms several baselines in online adaptive LQR control.", "questions": "Please see the limitation section below.", "limitations": "Since 2011 (when the paper [3] is published), there are over 1000 papers studying online LQR control via learning-theoretical perspectives. In particular, the 2021 paper by Simchowitz and Foster \"Naive Exploration is Optimal for Online LQR\" clearly shows that the regret lower bound of online LQR control is $O(d_u^2 d_x \\sqrt{T})$. Moreover, a \"naive\" CE control plus continual exploration (i.e., solve $K$ from OLS and $u=Kx+\\mathrm{noise}$) exactly matches this lower bound! Therefore, the reviewer believes that a new paper needs to be novel and impressive enough to be published at a top conference since this field is already very crowded. \n\nThis paper provides a new algorithm for online LQR control with theoretical justification (a $O(\\sqrt{T})$ regret bound) and empirical benchmarking. However, it is unclear whether the novelty is enough: Theoretically, the analysis framework is mainly from the classic UCB (OFU) method from [3]. The extra regularization term $\\alpha J^*$ from RBMLE seems not fundamentally change the analysis. Empirically, the performance of the proposed augmented RBMLE-UCE approach seems to inherit from RBMLE. In Table 1, the regret numbers of RBMLE and the proposed method are exactly \\emph{identical}! Given the fact that there is no regret bound for RBMLE, it seems that the UCB part is only for theoretical analysis, and does not contribute to the empirical performance at all.\n\nMinor points:\n1. In Eq. (6) and other related equations, please do not use $()^2$ as the norm of a vector. Please use $||\\cdot ||^2$.\n2. Assumption 3 is actually very strong. Stabilizable $(A,B)$ only guarantees the spectral radius of $A+BK$ is less than 1, rather than the 2-norm. Please comment on this.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the connection between RBMLE and UCB is interesting and the empirical performance of the proposed augmented RBMLE-UCB algorithm is sound.\n\nWeakness: the theoretical analysis is mainly adopted from the analysis of the UCB method in [3], and the empirical performance is mainly from RBMLE. Therefore the contribution is limited.", "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": "gcmJBNyPs6F", "reviewer": "Reviewer_wX3F", "summary": "The paper addresses the control of a fixed stochastic linear system of known order but unknown parameters with the objective of minimizing a finite horizon quadratic cost. The solution to this problem when the parameters are known (and under certain assumptions) is a well known result. However, when the parameters are unknown, various approaches have been suggested and explored. Many of these are mentioned in the introduction of the paper. \n\nThe paper re-examines an approach that first appeared in 1982 (ref [1]): Reward Biased Maximum Likelihood Estimate (RBMLE) but with a new twist. The new twist is to unite RBMLE with another approach known as upper confidence bound (CB) from 1985 (ref [2]). This allows the authors to show that RBMLE is a penalty version of of the UCB approach; This admits a finite time regret bound for the modified algorithm of $O(\\sqrt{T})$, the best bound to date.  \n\nThrough a series of simulations using established test-bed systems, the paper verifies that the new algorithm (ARMBLE) outperforms other methods, except RBMLE which achieves comparable performance.\n", "questions": "Line 49: OFU is used before being defined.\n\nLine 141: \"synergies to in fact fashion\" perhaps simplify to \"synergies to fashion\"\n\nLine 180: Space after ${\\cal F}_t$, \n\nLine 191: \"the the\".\n\nLine 192: In equation on next line $min$ should be $\\min$\n\nLine 268: $\\theta_{ARBMLE}$ should be $\\theta_{\\rm ARBMLE}$ and $\\theta_{OFU}$ should be $\\theta_{\\rm OFU}.$\n", "limitations": "Nothing stands out. One suggestion is listed above. Since this is a somewhat specialized theoretical result. Perhaps its worth explaining in greater detail its value to the community. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(S) Very well written, with clear explanations and a very solid and insightful analysis of a classic problem. Results in the best regret bound known to date.\n\n(W) This is a somewhat specialized theory result. Perhaps its worth explaining in greater detail its value to the community. ", "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": "eskY3xGOKXZ", "reviewer": "Reviewer_narw", "summary": "This paper develops a Reward-Biased Maximum Likelihood Estimate-Upper Confidence Bound (RBMLE-UCB) policy for controlling a stochastic linear system with quadratic costs, when its system parameters are not known to the agent. This problem is sometimes called the adaptive LQ control problem. The authors prove that this policy achieves the best-known square-root-T regret rate, and they empirically show via several numerical experiments that this approach is competitive against existing ones.", "questions": "I do not have any questions.", "limitations": "Not applicable", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths of the paper are that the proposed policy is interesting, the theoretical analysis is excellent, and the numerical experiments are compelling and convincing in the quality of the proposed policy.\n\nI do not think the paper has noticeable weaknesses.", "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": "RXMhY3DkJjw", "reviewer": "Reviewer_dwt7", "summary": "The authors revisit an old approach to LQR, called RBMLE, and reconcile it with UCB-based methods. They show regret guarantees and good empirical performance.", "questions": "See above on the form of the regret bound", "limitations": "see main review", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I want to highlight that I am not familiar with the LQR setting, and I do not know part of the literature that the authors build on, in particular RBMLE approach to LQR. \nI apologize with the authors and the meta-reviewer as I can only offer an educated guess; my review should be appropriately discounted.\n\nThe paper appears not to be written in a professional way. There are some inconsistencies both in the fonts and on the overall presentation style. As stated, the sequence of Lemmas is the regret analysis is not useful to understand what is going on. At a minimum, I believe that the paper writing would need to be improved for the paper to be accepted.  \n\nI have some trouble interpreting what the main result aims to convey. What \\widetilde O hides here? Any dependence on the dimensionality of the system appears to be missing in the main regret bound. Shouldn’t there be any? I think the authors should try to clarify this point in the rebuttal. To me, this is the most troubling aspect of the paper.\n\nWhile it appears the algorithm proposed here has better numerical performance, in practice I expect the constants in the construction of confidence intervals to play a leading role in this. I am unsure what choices were made here for this and other algorithms in order to obtain a comparison, but the point here is that the observed numerical performance may be justified by reasons that are different from the theoretical ones expressed in the paper. \n\nAgain, my apologies if I missed some important points in the paper.", "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