Regret Bounds for Episodic Risk-Sensitive Linear Quadratic Regulator
Authors: Wenhao XU
Xuefeng Gao
Xuedong He
Venue: ICLR 2025 Poster (2025)
Keywords: reinforcement Learning
regret
LEQR
finite horizon
episodic setting
Primary area: learning theory

Abstract: Risk-sensitive linear quadratic regulator is one of the most fundamental problems in risk-sensitive optimal control. 
In this paper, we study online adaptive control of risk-sensitive linear quadratic regulator in the finite horizon episodic setting. 
We propose a simple least-squares greedy algorithm and show that it achieves $\widetilde{\mathcal{O}}(\log N)$ regret under a specific identifiability assumption, where $N$ is the total number of episodes. If the identifiability assumption is not satisfied, we propose incorporating exploration noise into the least-squares-based algorithm, resulting in an algorithm with $\widetilde{\mathcal{O}}(\sqrt{N})$ regret. 
To our best knowledge, this is the first set of regret bounds for episodic risk-sensitive linear quadratic regulator. 
Our proof relies on perturbation analysis of less-standard Riccati equations for risk-sensitive linear quadratic control, and a delicate analysis of the loss in the risk-sensitive performance criterion due to applying the suboptimal controller in the online learning process.

Published as a conference paper at ICLR 2025
REGRET BOUNDS FOR EPISODIC RISK-SENSITIVE LINEAR QUADRATIC REGULATOR
Wenhao Xu, Xuefeng Gao, & Xuedong He
Department of Systems Engineering and Engineering Management The Chinese University of Hong Kong, Hong Kong, China {whxu, xfgao, x @se. see cuhk. edu. hk
ABSTRACT
Risk-sensitive linear quadratic regulator is one of the most fundamental problems in risk-sensitive optimal control. In this paper, we study online adaptive control of risk-sensitive linear quadratic regulator in the finite horizon episodic setting. We propose simple least-squares greedy algorithm and show that it achieves Ollo N) regret under a specific identifiability assumption, where N is the total number of episodes. If the identifiability assumption is not satisfied, we propose incorporating exploration noise into the least-squares-basee algorithm, resulting in an algorithm with ((vN) regret. To our best knowledge, this is the first set of regret bounds for episodic risk-sensitive linear quadratic regulator. Our proof relies on perturhation analysis of less-standard Riccati equations for risk-sensitive linear quadratic control, and delicate analysis of the loss in the risk-sensitive per- formance criterion due to applying the suboptimal controller in the online learning process.
INTRODUCTION
In classical reinforcement learning (RL), one optimizes the expected cumulative rewards in an un- known environment modeled by a Markov decision process (MDP, Sutton & Barto (2018)). How- ever, this risk-neutral performance criterion may not be the most suitable one in applications such as finance, robotics and healtheare. Hence, a large body of literature has studied risk-sensitive RL, incorporating the notion of risk into the decision criteria, see, e.g., Mihatsch & Neuneier (2002); Shen et al. 4)014); Chow et al. 2017 Prashanth I. Fu (2018).
In this paper, we study online learning and adaptive control for risk-sensirive linear quadratic control problem, referred to as the Linear Exponential-on Quadratic
-f-uaraatii Regulator (LEQR) problem. The LEQR problem is one of the most fundamental problems in risk-sensitive optimal control, and there extensive literature on this topic (Jacobson 1973] Whittle 1990] Zhang et al. (021a). this control problem, the system dynamics is linear in the state and control variables, and it is disturbed with additive Gaussian noise. The cost in each period is convex quadratic in both the state and the control/action variables, and the performance criteria is the logarithm of the expectation of the exponential functions of the cumulative costs. When the system parameters are known, the optimal control at each stage is linear in state with the coefficient determined by certain Riccati equation. Different from the risk-neutral setting, the solution to the Riccati equation for LEQR explicitly depends on the risk parameter and the covariance matrix of the additve Gaussian noise in the system dynamics (Jacobson 1973). For general siskisensitive nonlinear control, one does not have such closed-form solutions. However, one can use LEQR as a local approximation model and solve risk-sensitive control problems by iteratively solving LEQR problems, see e.g. Roulet et al. (2020).
We consider the standard finitehorizon episodic RI. setting, where the system matrices of LEQR are unknown to the agent. The learning agent repeatedly interacts with the unknown system over N episodes, the time horizon of each episode is fixed, and the system resets to a fixed initial state distribution at the beginning of each episode. We focus the finite horizon LEQR model because is widely used as a model locally linear dynamics. The performance of the agent or the online
Corresponding author.

---

Published as a conference paper at ICLR 2025
algorithm is often quantified by the total regret, which measures the cumulative suboptimality of the algorithm accrued over time as compared to the optimal policy. We seek algorithms with (finite- time) regret that is sublinear in N, which means the per episode regret converges to zero and the agent can act near optimally as N grows.
Regret bounds for the risk-neutral linear quadratic regulator (LQR) in the infinite-horizon average reward setting have been extensively studied in the literature, see e.g. Abbasi- Yadkori & Szepesvári (201T); Mania al. (2019); Cohen all (2019) Simchowitz & Foster (2020). It has been shown that controller where the agent selects control inputs according to the optimal controller for her estimate of the system, together with a simple random-search type exploration strategy, is (rate-)ophin jatee)ootimmll for the online adaptive control of risk- neutral LQR (Simehowitz & Foster 2020). However, non-asymptotic regret analysis of the finite- horizon episodic LQR has received much less attention, though some applications, especially in finance, naturally fall into the episodic setting. For example, a common task faced by financial institution is to liquidate large position of assets, e.g., a stock, in a finite amount of time, e.g., in one day. With a linear price impact, such problems can be formulated as a stochastic control problem with linear dynamics and quadratic cost functions; see Section 1.5 of [Almgren & Chriss (001). One can consider optimizing the expected utility of the total cost of trading and with an exponential utility function (see e.g. [Schied et al.] (2010)), the problem becomes an episodic LEQR problem. In different days, the institution may need to liquidate different assets, so the initial state of this problem, which represents the initial position of the asset that the institution needs to liquidate during the day, resets at the beginning of each day, resembling the episodic setting, [Basei et al. 2022) is among the first establish regret bounds for the risk-neutral continuous time finite-horizon LQR in the episodic setting. They proposed greedy least-squares algorithm and established regret bound that is logarithmic in the number of episodes N under specific identifiability condition. By contrast, we study finite-horizon LEQR, which is risk-sensitive model, in discrete-time setting.
in this average reward setting, the certainy-
On the other hand, there surge of interest recently on studying finite-time regret bounds for risk-sensitive RI. The first regret bound for risk-sensitive tabular MDP is due to Fei et al. (2020), who study episodic RL with the goal of optimizing the exponential utility of the cumulative rewards. There is now a rapidly growing body of literature
this topic. see, c.g. (Fei et al.] 20020] 2021 Du
et al. 2022 Bastani et al. 2022 Liang & Luo 2022 Xu et al. 2023 Wang et al. [023] Wu & Xul
2023
Chen et al.) 2024). Most of the studies consider learning nsskssensitive MDPs with finite
state and action spaces.
Inspired by these studies, in this paper we study regret bounds for online adaptive control of the (discrete-time) risk-sensitive LEQR in the finite-horizon episodic setting, where both the state and the action spaces are continuous. In particular, we obtain two main results:
First, we propose simple least-squares greedy algorithm without exploration noise (AI- gorithm D. and show that it achieves regret of order log N under a certain identifiability condition (Assumption T on the LEQR model.
Second, without Assumption I we propose another algorithm with actively injected explo- ration noise (Algorithm 2). and show that it achieves regret of order VN.
To the best of our knowledge, this is the first set of regret bounds for finite-horizon episodic LEQR.. In the learning theory community, there has been significant interest in the questions of whether logarithmic regret is possible for what type of linear systems and under what assumptions. See e.g. Agarwal et al. (2019): Cassel et al. (2020); Faradonbeh et al. 2020); Foster & Simchowitz (2020): Lale et al. (2020). Our first result provides an answer to these questions in the setting of risk- LEQR models. In addition, our second result complements the first result by showing that VV-regret bounds can be established for risk-sensitive LEQR models without the identifiability assumption.
Lale
We briefly discuss the technical challenges and highlight the novelty of our regret analysis. Even though our proposed algorithms are fairly simple, the analysis is nontrivial and it builds on two new components: (a) perturbation analysis of Riccati equation for LEQR; and (b) analysis of risk- sensitive performance loss due to the suboptimal controller applied in the online control process. For the perturbation analysis in (a), we cannot use the existing techniques from the literature online learning in risk- neutral LQR (Mania et al.) 2019; Siimchowizz & Foster 2020) [asei et al.) 2022). This is because the Riccati equation for L.FOR is less standard and more complicated: there are some
2

---

Published as a conference paper at ICLR 2025
extra parameters (see Pr. 0, - in involved in the equation, and the risk-sensitive parameter impacts the solution to the Riceati equation. To overcome this challenge, we first analyze one-step perturbation bound for the solution to Riccati equation, and then leverage the recursive structure of Riccati equation from our finite-horizon LEQR problem to establish a bound on the controller mismatch in terms of the error in the estimated system matrices. For the performance loss in (b), we can not employ the existing approach in online control of risk-neutral LQR as well. This because the performance objective in LEQR is nonlinear in terms of the random cumulative costs (unlike the expectation which is a linear operator). Indeed, this type of non- con-linearrty has been one of the key challenges in regret analysis for this challenge, we leverage results from Jacobson (1773) for LEQR to express the performance loss terms of the controller mismatch (i.e. the gap between the executed controller and the optimal controller). Due to these two new technical components, our analysís is substantially different from the proof in the closely related work Basei et al. (2022). In addition, Basei et al. (2022) did not analyze the case when the identifiability condition does not hold and provide v VN-regret bound.
1-1n
tabular MDPs (Fei et al., (021). To address
There are several recent studies on RL for LEQR. Zhang et al. a2021a) proposes model-free policy gradient methods for solving the finite-horizon LEQR problem and provides a sample complexity result. Sample complexity is another popular performance metric for RL algorithms in addition to the regret. Note that the controller in ZZhang et al. (2021a) is assumed to have simulation access to the model, i.e., the controller can execute multiple policies within each episode. By contrast, our work considers online control of LEQG with regret guarantees, where we do not assume access to simulator and the agent can only execute one policy within each episode. Other related works include Zhang et al. (2021b). which proposes a nested natural actor-critic algorithm for LEQR with the average reward criteria, and Cui et al. (2023). which proposes robust policy optimization algorithm for solving the LEQR problem to handle model disturbances and mismatches. These studies do not consider regret bounds for LEQR, and hence are different from our work.
Finally, we comment that an alternative approach to considering risk sensitive LQR is H adaptive control (Hassibi et al.) 1999). This approach takes a different perspective from LEQR: considers deterministic, unknown noise and, instead of taking expectation with respect to random noise as in LEQR, it considers the Ho0 norm the cost with respect to the deterministic, unknown noise. Thus, in the presence of system noise, Hoo opptimal adaptive control takes the robust control approach to consider the worst case performance while LEQR assumes a probabilistic model for the noise and degree of risk aversion. Regret bounds for H. control have been studied in e.g. Karapetyan et al.] (2022). Because of different settings and objective functions in LEQG and H optimal control, the regret bounds in these two problems are not directly comparable.
2 PROBLEM FORMULATION
2.1 THE LEQR PROBLEM
We first provide a brief review of the LEQR problem (Jacohson) 1973). linear discrete-time dynamic system:
We consider the following
xt+1 = Az, + Bu, + we. t= 0, ... TT
(1)
where the state vector 2, E R", the control vector Ue E R", the matrices A E R2 B E Raxm and the process noise w, RR form a sequence of i.i.d. Gaussian random vectors. For the simplicity of presentation, we assume the noise Wy ~ -N(0, 7) where I is the identity matrix. The goal in the finite-horizon LEQR problem is to choose a control policy æ {uo, ui. -T so as to minimize the exponential risk-sensitive cost given by
(Fo) = log E exp
? 2/4
Σ
(x ue) + + (e((rr)
(2)
7
where (2,, u,) = x.7 Qu, u, Ru, er (T(T)) = TTRT Q z 0, Qr 2 0 (i.e. positive semidefi- nite), R (i.c. positive definite), and y is the risk- sas--ennttyvvtt parameter.
Note that when y is small, we have by Taylor expansion:
1 log E Eexp(7 = E| V 0()?),
7 2
7
3

---

Published as a conference paper at ICLR 2025
for random variable Z with finite moment generating function. It is well understood in the economics literature that y measures the risk aversion degree, and a positive (negatively, respec- tively) y stands for risk-averse (risk-secking, respectively) attitude; see for instance Pratt (T964). When y + O, the LEQR problem reduces to the conventional risk-neutral linear quadratic control where minimizes the expected total quadratic cost and the controller becomes risk-neutral. For concreteness, we focus on the case where y > 0 (our analysis extends to S 0). The optimal performance denoted by
J (x0) = inf J (xn))
(3)
When the system parameters are all known, Jacobson
1973) shows that under the assumption that
- P-yPt+1 > for all t = 0, 1, ... T - (Note that if is too large, we have J J² (xo) oo for all
policies), the optimal feedback control for (3) is linear function of the system state
" = K, t= 0, , -,
(4)
where (K₂) can be solved from the following discrete-time (modified) Riccati equation:
Pr QT,
P++1 Pt+1 + 7P41 (1, -Pt++) P++1,
K, = - P.+1 + -) P
P. Q+ + K, RK, (A BK.) P441AA BK.),
f 0, , 1
(5)
One can see that scaling all the cost matrices Q, Qr. and R does not change the optimal controller, and hence we assume 2 Im without loss of generality. Note that in the risk-neutral setting where O, we have P. = Pt in the Riccati equation (). However, in the risk-sensitive setting, we have extra matrices (P:) in the Riccati equation. This is one of the difficulties we need to overcome when we study perturbation analysis of Riccati equations for the LEQR problem.
2.2 FINITE-IORIION EPISODIC RL IN LEQR
In this paper, consider the online learning/control setting for LEQR, where the system matrices (A, B) are unknown to the agent. The learning agent repeatedly interacts with the linear system ( over N episodes, where the time horizon of each episode is T. In each episode 1, N, arbitrary fixed initial state x Tо E R2 is picked] 1 An online learning algorithm executes policy n' throughout episode based on the observed past data (states, actions and costs) up to the end of episode 1. The performance of an online algorithm over N episodes of interaction with the linear system [T is the (total) regret:
Regret(N) Σ (1b6 ((
where the term (xb) I (*(()) (see 2 and
3 measures the performance loss when the agent
executes the suboptimal policy n² in episode
A LOGARITHMIC REGRET BOUND
In this section, propose simple least-squares greedy algorithm and show that it achieves regret that is logarithmic in N, under specific identifiability assumption.
3.1 A LEAST-SQUARES GREEDY ALGORITHM
We now present the details of the least-squares greedy algorithm, which combines least-squares estimation for the unknown system matrices (A, B) with greedy strategy.
'The results of the paper can also he extended to the case where the initial states are drawn from a fixed distribution over R
4

---

Published as a conference paper at ICLR 2025
We divide the N episodes into L epochs. The [-th epoch has my episodes, thus Σl= my N. At the beginning the 1-th epoch, we estimate the system matrices (A, B) by using the data from the 1)-th epoch, and the obtained estimator is denoted by (A', BB). Then select the control inputs according to the optimal controller for the estimate (A² B²) of the system, and execute such policy throughout epoch The feedback control K; is obtained by replacing (A, B) in ( with the estimate (A', B²). Then, in the k-th episode of epoch I, we play the greedy policy ui by taking K into (4.
remains to discuss the estimation procedure for (A', B') which conducted at the beginning of epoch l. Within the (-th epoch, note that the same policy is executed in each episode. Because we consider the episodic setting where the system state reset to the same state at f = 0, we obtain that the state-action trajectories across different episodes i.i.d within the same epoch. Note that the random linear dynamical system in epoch is given by
1+1 Art + Bud + w/y t
1
(6)
where u/ Kf,t. For simplicity of notation, denote by 2 = [xx]] w//]"" which the state-
action random vector at step epoch We also denote by 0 [A B) T for the system matrices.
Taking the transpose of (6) and multiplying of on both sides of (6). we can get 2/-r 2/2, 0 +
z/w;T Summing over T steps and taking the expectation, V -T- 2tT and y = ET-1 =/17711 It follows that
obtain E [Y E [V]] 0, where
0 [A BJ (R [V']) (B(")))(((("""))
provided that the matrix E[V'] is invertible. The formula 7 and the fact that state-action tra- jectories across different episodes are i.id. within the same epoch provide the basis for timation procedure. Given the data in epoch we now discuss the construction of the estimator
gi+1 = [A'+1 "
Consider the sample state process in the k-th episode of epoch I:
Lkk #++1
t 0,1, - Art + But:" + L.k
Denote the sample state-action vector by =t 1t
Then, we can design the 12- regularized least squares estimation for f by replacing the expectation in 7 with the sample average over the my episodes in epoch and adding the regularized term 1 Intm
L&T
uf
1
gi+1
In+m
P!
(9)
my
where 71= m/
Em
Ei
2'
1.k I.TT zt 4t
and
y
E
T- E 2t
LR
LAT #++1
LAT
my
We now summarize the details of the least-squares greedy algorithm in Algorithm input parameter H denotes the initial guess of the true system matrices (A,B)
Note that the
Algorithm The Least-Squares Greedy Algorithm
Input: Parameters L, m,, 0², 12,,2000 Q,Qr,. R
for l 1.... L do
my = 2 mm Compute (K)) for all t by
using 0'
for k: = 1,... my do
for 0,
do
1. K|a
Play u,
end for end for
Obtain gi+1 from the ly ly-reuularized least-squares estimation 9
end for
5

---

Published as a conference paper at ICLR 2025
3.2 LOGARITHMIC REGRET
In this section, we state our first main result. We first introduce the following assumption. Assumption 1. For the sequence of the controller (K₂) defined in ( assume that
(UE E R [I, K, 0, 14 0,
{0).
(10)
Assumption 1 is essentially Assumption H.1(2) in Basei et al. (022) for learning finite-horizon tontiuuos-tiime risk-netural LQR, and it is referred to as the self self-exploration property therein (i.e., exploration is "automatic' due to the system noise and the time-depee deneeddennden optimal feedback matrix (K))==0.... T-1 ). One can show that Assumption is equivalent the condition (see Lemma
-
E
Σ
2
In K
[
In K,
> O,
(11)
which resembles the persistence of excitation assumption in adaptive control (Aström & Witten- mark, 2008, Definition 2.1, Chapter 2).
In view of 7 and [11 Assumption I essentially guarantees the identifiability of the true system ma-
trices when the time-dependent optimal control in (5) is executed. This important for the proposed greedy leaat-squares algorithm to achieve a logarithmic regret bound. Assumption T can be satisfied under various sufficient conditions. We provide one set of sufficient conditions Proposition in the appendix.
We now present our first main result, which provides a logarithmic regret bound of Algorithm We denote || the spectral norm for matrices.
Theorem 1. Suppose Assumption 7 holds and assume the optimal controller for the initial estimate 8¹ also satisfy (10). Fix ö E (0, ) Then can choose mı = Col log 8) for some positive
constant Co such that with probability at least 1 3
z²6, the regret of Algorithm satisfies
m + [oog
Regret(N) SC
Σ the
-. T.
I. I.
(12)
v8
where C is constant independent of N and (th)) is sequence recursively defined by
= t/2 2 (i 12 t [T 2).
with
{1 || |BI, 1111, || [R], |P PP 1 f= 1 max
r, = max
(13)
V = 2( 1)T L (1-702Ty)
S log N, where S means the inequality holds with a multiplicative constant. Hence, Theorem lmplies that the regret of Algorithm satisfies Regret(A) (N) = (log N log log(N)) where O hides dependency on other constants. In Appendix C provide some further discussions the dependency of the regret bound on other problem parameters, including the horizon length T, and the risk parameter of the LEQR model. Note that Algorithm B requires L., equivalently N (the total number of episodes) as input. For unknown N. one can use the doubling trick (Besson & Kaufmann 2018). Specifically,
Because ΣL my = N and my = mm we infer that L logg
+
m2
consider increasing sequence [n where T4 2 for A > 1 and no O. For each k, one restarts Algorithm 0 at the beginning of episode n4 + 1, and run the algorithm until episode n
with the input N 11++1 n4. One can readily verify that this leads to an anytime algorithm which still achieves a logarithmic regret bound.
3.3 PROOF SKETCI OF THEOREM
In this section, we provide the proof sketch of Theorem 1 The full proof is given in Appendix A Step 1: We adapt the analysis in Basei et al. (2022) and use Bernstein inequality for the sub- exponential random variables to derive the following bound on estimation errors of system matrices.

---

Published as a conference paper at ICLR 2025
Proposition 1 (Informal). Fix E (0, ) Let d1 8/1. For my 2 log probability least 20j,
(m-=))
we have with
di
log (m++ 6,
log
(m++))
(m++)) log²
10 011
6i
5L
mi
mn
For a complete rigorous statement, see Proposition 3 in Appendix.
Step 2: We recursively carry the perturbation analysis of less-standard Riccati equation (5) and prove that the perturbation of the controller AK} : Kj - K₁ is on the order of O(er), where
6 = max [II4' All. |B - -B]]. The formal statement is presented Lemma 8
Step 3: We result of Jacobson (173) (see Lemma 10 and the proof technique in Fazel et al.
2018) to prove that
J (20 J (dttt)
log (det - -D)) + 2
I.T Doab"
27
where Dj is function of AK, AKG with |Dj|l 2i 22 + o(e?). See Proposition 5 Here, w is the sub-optimal controller 14.k executed in the k-th episode of the (-th epoch.
Step 4: We can then bound the regret: Regret(N) = Σte E (JU't (al J (3(0 S
Etnn mff 2 Σt= log(() & Ologg llog log(
A SQUARE-ROOT REGRET BOUND
Theorem I shows that the logarithmic regret bound achievable for episodic LEQR under As- sumption One may wonder how does the regret bound changes after removing Assumption D In particular, is VN regret achievable without Assumption L This section provides an affirmative answer to this question, by proposing and analyzing least-squares-buseee algorithm with actively injected exploration noise.
4.1 A LEAST-SQUARES SAAARE ALGORITHM WITH EXPLORATION NOISE
We now introduce the algorithm (Algorithm 2). which is is different from Algorithm ! We no longer divide the N episodes into epochs of increasing lengths to estimate the system matrices. Instead, in the k-th episode, the algorithm updates the estimation of the system matrices (A, B) by using the
data from the previous k episodes, which is denoted by (A*, B*). Similar to K. in Section 3.1
we can obtain the feedback control K by replacing the true system matrices in (5) with (A* B
Then, execute the control with exploration noise (gt) that follows Gaussian distribution in the k-th episode. The design of Algorithm 2 is inspired by (Mania et al. 2019) Simchowitz & Foster 2020) that establish VT regret bounds for risk-ncutral LQR in the infinite-horizon average reward setting, where 7' the number of time steps.
The estimation of system matrices (A, B) in Algorithm 2 is different from that in Algorithm In Algorithm 2 the estimator (A*+1 BB+1) is obtained by solving the following lz-regularized least- squares problem (based on the linear dynamics
& T-1
g++1 E arg min y
Ally/1
| - y T =
(14)
,24 where gl++1 [A++], Bb++1 solving 14). we can get
and A 0 is the regularization parameter. By u4
k
T-1
g++1 = (vi) -1
Σ
staiT1
(15)
where 1 AI E Σ 24

---

Published as a conference paper at ICLR 2025
Algorithm 2 The Least-Squarest Masst-Sqarre-Basee Algorithm with Exploration Noise
Input: Parameters T, .N, 0¹, Q,Qr,, for k 1, N do Compute (K²) for by (5) using 0h.
for to 0, ... T do
Play u + K2 ot + gt of ~ NO0,, + 7k mm).
end for
Obtain gh+1 from 15
end for
4.2 SQUARE-ROOT REGRET
In this section, we present the second main result of our paper, which demonstrates that Algorithm 2 can attain O V N >-regret (ignoring logarithmic factors). This is the first Ö ((v/)) for online learning in risk-sensitive LEQR models.
Theorem 2. Fix å E (0. When N 2 200 (3(n + m) + log (2 with probability at least 1-ô, 8, the regret of Algorithm satisfies
Regret (N) S Σ (a,CN + 90 90) VN,
where C is constant independent of N, CN exhibits logarithmic dependence N and depends on X, and (az), (3x) are two sequences recursively defined by
aT = 25
a₁ 2 (10V2 CT
2(T-t-1)
+ +12 a4415
PT
B. 12 12I 3441
with F V, L defined in 13
4.3 PROOF SKETCH OF THEOREM
2
provide a proof outline for Theorem The complete proof given Appendix B
Step 1: We adapt the self-normalized martingale analysis framework (Abbasi- Yadkori et al. 2011
Cohen et al. 2019) Simchowitz Foster, (2020) to derive the following high probability bound for the estimation error. See Proposition foor the complete statement.
Proposition 2 (informal). When k is large enough, with probability at least
|100t - 01| SK $1088 (1+ 11+klog 1+-klog log
N
1
(16)
Step 2: We conduct perturbation analysis of the Riccati equation 5 and show that AKF = K
K, is on the order of ((x)), where éş denotes the estimation enrrr of system matrices, i.e. right- hand-side of (16). This step is essentially the same as Step 2 in Section 3.3
Step 3: Because of the additional exploration noise added to the online control, show that the loss the risk-sensitive performance becomes
f= (x - J = 27 t=
log det (In - 7F( 2
log det (Im - )(² + -00 U
where F/ and U. are functions of AK = KMp - K;. t.... T 1, with F. < 2
+ +
v
and U < a, 2 (1+()) + o See Proposition 7
Step Finally we can bound the regret: Regret(N) = EN
-
SΣN E
ΣN J log (1 + Noog ())) s Ö(VN).
8

---

Published as a conference paper at ICLR 2025
5 SIMULATION STUDIES
We perform simulation studies to illustrate the regret performances of Algorithms I and 2 Note that our paper is the first to obtain regret bounds for episodic risk-sensitive LEQR and there are currently no other existing algorithms with sublinear regret for this problem. Our experiments are conducted on a PC with 2.10 GHz Intel Processor and 16 GB of RAM. We consider the following three LEQR systems for illustrations:
System 1. We use the system matrices and cost matrices in Section 6.1 of Dean et al. (020) with the following minor change: we set Qr Q 2 instead of Q 10-31 as in their paper because the effect of risk parameters is difficult to visualize when Q has small eigenvalues.
System 2.
non-symmetric random system matrices A RTx7 and B E RTx4 with all entries sampled from the uniform distribution (00 1). The cost matrices Q and R are randomly generated positive definite matrices, and we set Qr = 0.
We generate non wwwttiie--seiideiiiieee
System 3. We consider a flying robot problem in Section IV of Tsiamis et al. (2020) with the following minor change: we set QT = 0 instead of Qr diag (1, 0.1, 2, 0.13 as their paper so that the effect of risk parameters is easier to visualize.
We implement Algorithms D and 2 in all the systems and compute the expectation and 95% confi- dence interval of the regret of each algorithm using 150 independent runs. In both algorithms, we randomly generate the initial guess 6¹ = (A' B¹) with all entries of A' and B' sampled from the
uniform distribution. In Algorithm
we set mi 500 and
logz
N +1)]- In Algorithm 122
2. we set À = 0.8.
Because the simulation results for Systems 1, and are similar, we only present those for System
here and make the results for System 2 and system 3 available in Appendix [D] Figures Ia [b and Ic show the average regret of Algorithm[[] [ System using 150 independent runs and Figures Id] Te and Tf show the average regret of Algorithm Zin in the same system. The two blue dotted lines Figures Ta and Td depict the 95% confidence interval of the regret when y = 0.1 and We observe that Algorithm [ incurs large regret in the initial learning process, and result, the actual performance of Algorithm [ is worse than that of Algorithm 2 on this instance. This is because Algorithm [ updates parameter estimations less frequently compared with Algorithm 2 and the inaccurate estimations in the initial learning process lead to a large regret for Algorithm With T 3, Figure Tb illustrates the effect of the risk aversion the regret. The true value of the learning agent's risk aversion parameter 7 is 0. Figure Tb plots the regret of the algorithm when the true value of is used and when wrong value, e.g., 0.05, 0.2, and 0, is used. The plot shows that if one runs Algorithm | with a misspecified risk aversion degree 7, particularly with y O, which corresponds the algorithm in Basei et al. (2022) with the assumption of risk-neutral agents, the regret performance is much worse compared with the case of a correctly specified risk aversion parameter. Setting 7 = 0.01, Figure Ic illustrates the effect of the time horizon T Consistent with our theoretical results, the regret is increasing in T. The same parameter settings are used in Figures Td- Tf where we test the performance of Algorithm The results are similar to those of Algorithm
3.
Figures
la Ic
6 CONCLUSION AND FUTURE WORK
This paper proposes two simple least-qquares-basee algorithm for online adaptive control of LEQR in the finite-horizon episodic setting. We prove that the least-squares greedy algorithm can achieve a regret bound that is logarithmic in the number of episodes under a identifiability condition of the system. We also prove that the least-squares-buee based algorithm with exploration noise can achieve (VVN) )-rgret when the identifiability condition is not satisfied. To the best of our knowledge, this is the first set of regret bounds for LEQR.
The study of regret analysis for risk-sensitive control with continuous state and action spaces is still in its infancy, and there are many open questions. For instance, it would be interesting to
We choose 7 = 0.01 to ensure the existence of the solution to the Riccati equation for the values of T under consideration.

---

Published as a conference paper at ICLR 2025
12000
17000
10002
10000
Regret
Regret
2002
Algorithm
nik noutral
0.2
18
(a) Regret performance (Algorithm System I)
(b) Effect of the risk parameter (Algorithm) System 1)
15000
200
10000
Regret
100
Algorithm
(c) Effect of the time horizon (Algorithm) 1 System 1)
(d) Regret performance (Algorithm System
2000
300
-002
-0.1
-..--0.05 0.05 iisk-nautral
250
1000
200
1200
100
600
Effect of risk parameter (Algorithm) 2
System 1)
(f) Effect the time horizon (Algorithm) System
Figure 1: Simulation results in System
study regret bounds for LEQR in the infinite-horizon average-reward (non-episodic) setting. is straightforward extend our current proof methods this non-episodic setting because it is nontrivial to establish explicit perturbation bounds for the generalized algebraic Riccati equation for average-rewan LEQR (see e.g. Cui al. (203)). Another significant question to study regret bounds for online linear quadratic regulators with other risk measures such as coherent risk measures (see e.g. [aa et al. (2023)). Other interesting problems include lower bounds for online LEQR, regret bounds for LFQR with partially observable states and for more general risk-sensitive nonlinear control problems. We leave them for future work.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank the area chair and anonymous referees for many constructive comments and suggestions. Xuefeng Gao and Xuedong He acknowledge support from the Hong Kong Research Grants Council [Grants 14201424, 14200123, 14212522, 14218022].
REFERENCES
Yasin 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, pp. 1- 26. JMLR Workshop and Conference Proceedings, 2011.
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems. 24, 2011.
Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. Advances in Neural Information Processing Systems, 32, 2019.
Rinaldo Alessandro. 36-710; Advanced statistical theory: Lecture 5. https: wwtp//ww..ttt.t....... cmu. /ttp:////.aaaa////aaaaa////////1 Scriibbeed Lectures/Sepl7.pe 2018.
Robert Almgren and Neil Chriss. Optimal execution of portfolio transactions. Journal of Risk, 3: 5-40, 2001.
Karl Johan Aström and Bjöm Wittenmark. Adaptive Control. Dover, Mineola, New York, 2nd edition, 2008
Matteo Basei, Xin Guo, Anran Hu, and Yufei Zhang. Logarithmic regret for episodic continuous- time linear-quadratic reinforcement learning over finite-time horizon. The Journal of Machine Learning Research, 23(1):8055880) 2022.
Osbert Bastani, Yecheng Jason Ma, Estelle Shen, and Wanqiao Xu. Regret bounds for risk-sensitive reinforcement learning. arXiv preprint (.XXV:22200006666 2022.
Lilian Besson and Emilie Kaufmann. What doubling tricks can and can't do for multi-armed bandits. arXiv preprint /rXiv:/803. 08088000777711 2018.
Asaf Cassel, Alon Cohen, and Tomer Koren. Logarithmic regret for learning línear quadratic reg- ulators efficiently. International Conference on Machine Learning, pp. 1328-1337. PMLR, 2020.
Yu Chen, Xiangeheng Zhang, Siwei Wang, and Longbo Huang. Provable risk sensiivee distributional reinforcement learning with general function approximation. arXiv preprint arXiv:2402.18159, 2024.
Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained inforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18 (1):6070-66) 6120, 2017.
Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only vT regret. In International Conference on Machine Learning, pp. 1300-1309, PMLR, 2019.
Leilei Cui, Tamer Basar, and Zhong-Ping Jiang. A reinforcement learning look at risk-sensitive linear quadratic gaussian control. In Learning for Dynamics and Control Conference, pp. 534- 546. PMLR, 2023.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complex- ity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633-6) 679, 2020.
11

---

Published as a conference paper at ICLR 2025
Yihan Du, Siwei Wang, and Longbo Huang. Risk-sensitive reinforcement learning: Iterated evar and the worst path. arXiv preprint unXiv22206.02676 2022.
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Input perturbations for adaptive control and learning. Automatica, 117:108950, 2020.
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradi- ent methods for the linear quadratic regulator. In International conference on machine learning, pp. 1467-1476. PMLR, 2018.
Yingjie Fei and Ruitu Xu. Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforce- ment learning. In International Conference on Machine Learning, pp. 6392-6417. PMLR, 2022.
Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk-sensitive rein- forcement learning: Near-optimal siskle tradeoff regret. Advances in Neural Information Processing Systems, 13:22384-22399 2020.
Yingjie Fei, Zhuoran Yang, Yudong Chen, and Zhaoran Wang. Exponential bellman equation and improved regret bounds for risk-sensitive reinforcement learning. Advances Neural Information Processing Systems, 34:20436-20446, 2021.
Dylan Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In Interna- tional Conference on Machine Learning, pp. 3211-3221. PMLR, 2020.
Babak Hassibi, Ali H Sayed, and Thomas Kailath. calefinite-uaarruie estimation and control: unified approach H and = theories. SIAM, 1999.
Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. 2012.
David Jacobson. Optimal stochastic linear systems with exponential performance criteria and their relation deterministic differential games. IEEE Transactions on Automatic control, 18(2):124- 131, 1973.
Aren Karapetyan, Andrea lannelli, and John Lygeros. On the regret of Ho control. In 2022 IEEE 6lst Conference on Decision and Control (CDC), pp. 6181-6186. IEEE, 2022.
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Logarithmic gret bound in partially observable linear dynamical systems. Advances in Neural Information Processing Systems, 33:20876-20885 2020.
Thanh Lam, Arun Verma, Bryan Kian Hsiang Low, and Patrick Jaillet. Risk-aware reinforcement learning with coherent risk measures and non-linear function approximation. In The Eleventh International Conference on Learning Representations, 2023.
Hao Liang and Zhi tha-Quan Luo. Bridging distributional and risk- sensitive reinforcement learning with provable regret bounds. arXiv preprint 22Xiv:2210.. 14051, 2022.
Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
Oliver Mihatsch and Ralph Neuneier. Risk-sensitive reinforcement learning. Machine learning, 49 (2):267-290, 2002.
A Prashanth L and Michael Fu. 1IXiv:1810.09116, 2018
Risk-sensitive reinforcement learning. arXiv e-prints, pp-
John W Pratt. Risk aversion in the small and in the largel. Econometrica, 32(1/2):122-136, 1964.
Vincent Roulet, Maryam Fazel, Siddhartha Srinivasa, and Zaid Harchaoui. On the convergence of the iterative linear exponential quadratic gaussian algorithm to stationary points. In 2020 American Control Conference (ACC), pp. 132-137. IEEE, 2020.
Alexander Schied, Torsten Schöneborn, and Michael Tehranchi. Optimal basket liquidation for cara investors is deterministic. Applied Mathematical Finance, 17(6)4711-44 1-99,, 2010.
12

---

Published as a conference paper at ICLR 2025
Yun Shen, Michael J Tobia, Tobias Sommer, and Klaus Obermayer. Risk-sensitive reinforcement learning. Neural computation, 26(7):1298-15 1328, 2014.
Max Simchowitz and Dylan Foster. Naive exploration is optimal for online lqr. In International Conference on Machine Learning, pp. 8937-8948. PMLR, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Anastasios Tsiamis, Dionysios Kalogerias, Luiz FO Chamon, Alejandro Ribeiro, and George Pappas. Risk-constrained linear-quadratic regulators. In 2020 59th IEEE Conference Decision and Control (CDC), pp. 3040-3047. IEEE, 2020.
Roman Vershynin. Flighdiimensionll probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Martin Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Kaiwen Wang, Nathan Kallus, and Wen Sun. Near-mininaxx-ppimall risk-sensitive reinforcement learning with evar. arXiv preprint arXiv:2302.03201, 2023.
Peter Whittle. Risk-sensitive optimal control. Wiley, 1990.
Zhengqi Wu and Renyuan Xu. Risk-sensitive markov decision process and learning under general utility functions. arXiv preprint arXiv:2311.13588 2023.
Wenhao Xu, Xuefeng Gao, and Xuedong He. Regret bounds for markov decision processes with recursive optimized certainty equivalents. ICML, 2023.
Kaiqing Zhang, Xiangyuan Zhang, Bin Hu, and Tamer Basar. Derivative-free policy optimization for linear risk-sensitive and robust control design: Implicit regularization and sample complexity. Advances in Neural Information Processing Systems, 34:2949-209 2964, 2021a.
Yufeng Zhang, Zhuoran Yang, and Zhaoran Wang. Provably efficient actor-critic for risk-sensitive and robust adversarial rl: A linear-quadratic case. In International Conference on Artificial Intel- ligence and Statistics, pp. 2764 2772. PMLR, 2021b.
13

---

Published as a conference paper at ICLR 2025
A REGRET ANALYSIS FOR THE LEAST-SQUARES GREEDY ALGORITHM
In this section, we carry out the regret analysis for the least-squares greedy algorithm in Section We derive the proh-prbbbbility bounds for the estimation error of system matrices in Appendix A. We do the perturbation analysis of Riccati equations in Appendix A.2 We simplify the suboptimality gap due the controller mismatch in Appendix A.3 Finally, we combine the results derived/proved above and prove Theorem
A.1 BOUNDS FOR THE ESTIMATION ERROR OF SYSTEM MATRICES
In this section, we discuss the high probability bound for the estimation error of system matrices in Algorithm We adapt the analysis framework in Basei et al. (2022) and use the Bernstein inequality for the sub-exponential random variables to derive the desired error bound.
To facilitate the presentation, we first introduce some notations. We fix the 1-th epoch and define the following set
θ 0 R (2( xm
s |0-0|= uGO'). )
where p 0 is constant such that for any 0 e o,
(E(V') C2 and | [y]]]] s C2 for
some constant C2 2 1. We choose the initial number of episodes m2 such that
(n+m)²
log
63
2 3
Vj VjENt(I
my-
where 63-1 リ- My 2/ and C₁ is constant independent of my, Vj E (N but may depend on other constants including m, n, T. We will show how to choose my in Section A.4 We also define the event
g' = (0' E eovj= 1...,,1.111111
We will prove that P(G') 2 1ーー 1-1 6j in Section A.4 The following proposition is the main result
of this section. Recall that G1+1 [A4+1 BI+1JT are the estimated system matrices and [4 B T are the true system matrices.
Proposition 3. Conditional on event G' there exists a constant C3 2 1 such that for my 2
C3 log (x++==²²) with probability at least 28,.
log (n+m))²
log (In=m)²
log² ((n+m)²)
1
8|| S
my
m;
mf
The proof Proposition Bss long, and we discuss it in the new few sections.
A.1.1 PRELIMINARIES
In this section, recall the definition of sub-exponential random variables and state several well- known results about such random variables that will be used in our analysis later.
Definition (Definition 2.7 of Wainwwight (2019)). random variable with mean μ1
E.X is
sub-exponential if there non-negative parameters (v, a) such that EXexX--) _22 for all ||| < a Denote the set of such random variables as SE(v2, a).
Lemma (Bernstein Inequality, Proposition 2.9 of Wainwright (019)). Suppose that SE (E(22a)) a), and let = E.X. Then any Ç O, we have
2 5 1)
P(X- 14| Z C) S 2exp min 2
2a
14

---

Published as a conference paper at ICLR 2025
Lemma 2 (Lemma 5.1 of Alessandro 2018)). If X E (E((,,a)), [n]. then
SE
EE i= V maxic(m] as)
X are independent, X, are not independent.
Σx
X
SE
(E v1)) maxie(m] ai)
Lemma 3 (Lemma 2.7.7 of Vershynin (2018). Lel X and Y be sub-Gaussian random variables. Then, XY is sub-exponential.
A.1.2 PROPERTIES OF ESTIMATED SYSTEM MATRIX
In this section, we use the properties of sub- sub-exponential random variables derive some statistical properties for the estimated system matrix 0¹_
The following lemma shows that every element of the state-action random sample vector 2/
Jtt L u.AT] sub-Gaussian.
Lemma 4. Consider the sample state (8) in section 3.1 conditional on event G' we can prove that
every element of the sample state 2ith and action vector w4th -abb-Gassiin for any step t, episode k. epoch I.
Proof. By the definition
8 we have
2t l
Aut.i
Buith -1 + w
1,k
(A + B ) + w
(A BBB/-1(// + 2KI
1.k
(A (Kk/-)0(t + w
Repeating this procedure, we can get
i+1
2t 1
II (A + BK})
1.ke 2o
+
II (A+ BKY) (A+BK)) w/th
(17)
where IT/=e- (A + BK)) := I,. Recall the definition of Ki in 5) by using 0¹_ It's continuous in 0i E G, K; is uniformly bounded for any 6' θ by the boundedness of θ i.c. there exists some constant M > such that sup, || S M. Because 2/ za and fw 1=00
(w are independent zero-mean normal random variables, we can then readily obtain from 17 that every element of A sub-Gaussian by the uniform boundedness of K!. Similarly, we can prove that every element of sub-Gaussian, which completes the proof.
1.k u Kirt 1.k
Recall the following matrices in and 9
T-1
Y Σ
24
[m0
0=
(18)
F' 1 T-1
T-1
1.k TAT 4t
y =
46 L&T ΣΣ
2441
km t=
where V p/ E (R(+t))(p+m)) and Y V1 E R (n=m)xn We denote the elements of Vl Pt
y
as
V =
1 1.j [m
V/3 Σ
2 + E mm,m E [n]
2tá "tj i,j
1k 1.k
[n mm
mi
V! = Σ Σ
2t, 1.j E in +mm,j j E [n].
1.k 1.k
15

---

Published as a conference paper at ICLR 2025
Then we have the following result from Lemma
Lemma 5. There exist non-negative parameters and n such that V V., E SE i,j and E [T..
12 n
for all
my my
LKKT and 2, T++l are Proof. By Lemma and Lemma 4 we know that every element of 2, 2, L.k. .ik sub-exponential random variables. That is, *a,a Stj E SE' (vrss)) .a,.s) i,j E [n + ml and
1.* LKT
L.k L.k Fi, 141, E SF (w))))) Penss i E [n + ml,j E [n]. The subexponential parameters can be chosen independent of and by the proof of Lemma If we denote by
V/ max Ve,a.i
a max Oiti i
Wt max
B. max Be,idi
L.k 1.k then we have 2 Sig
E SE (vx)² at) for any k [mi], i,j E In + m] and 21111 L.k.
SE (wi)) 8r) for any k E [m]], in + ml.j |n].
By Lemma for non-independent sub-exponential random variables, we obtain
T-1
T-1
2
Lik 2, St.
E
SE
Σ
max
at
1=0
T-1
2
#+i ESE
Σ
We
max Br
Applying Lemma 2 aggann, but for independent sub-exponential random variables, we infer that
E
- Vt
max; Ore
4,
E SE
mi
2
mi
T-1
11=0
V/
max; ate
SE
1711
m1
mi T-1
Σ
2/ "41. ESE
J. LA
Ek=l k=1
Σ T-1
Σi=o
We
max;
B m711
mi
mi
We
max; Be
SE
m
m
The proof is complete by letting
2
Σ
Σ
max
11
Wi
1=0
77 max max at, max Br }
We derive the concentration inequalities for Vl and V
16

---

Published as a conference paper at ICLR 2025
Lemma 6. Conditional event G¹, we can derive that for any 0,
max {P (lVi EV' 2 5) P (| - -EY' 2 {)}
m2²²
Sin
(19)
2(n + m)² exp
-in
2.2 m) 21 m))
where 1- is a matrix norm that represents the summation of the absolute value of all the elements of the matrix, e.g. ||| Eis |aigl-
Proof. We first consider one element of the matrix VL, By Lemma I and Lemma
we have
mm mis
})
P ( EV <)
S exxp
min
262
2n
Then, by the fact that - X variables (X.) we can derive the concentration inequality for
MM
(xx,
for all M E and random
V EV
P ([ - 2()
n+m +m
P
V EV.
ntm
S
P
[ig
EV'l
2
(n + m)2
mi²²
217(n + m)² 1).
Sis
$ 2(n + m)² exp
-inn
21 + m)²²
Similarly, we can derive the concentration probability for y
P (
EY N 5)
B+ m n
P
Yi EY,, 25
j=1
1+ n
5
Σ P
EY,
2 (n + m)n
mis²
mi
< 2(n + mxmexp
min
2: 2: + m) m
2n(n + m m)n
(1) $ 2(n m)² exp
m2
miS
-minn min
2n²((n + +m)
2n + m)
where inequality (1) follows from the fact that + m 2 n.
Finally, combining the two probability inequalities above, we can obtain (19
In order to derive the probability bounds in Proposition 3 prove that (E[V')) and |B|'') bounded by positive constant for any 0 lies in O. The boundedness of |[Y be proved directly, because E[(' is continuous terms of 6l according to the definition of y in (18. In
terms of (EE(V'I) -|| we will use the following lemma to show that it's bounded when 0' O.
Similar results can be found in Proposition 3.10 of Basci et al. (2022).
Lemma 7. The following properties are equivalent:
1. For the sequence of the controller K,, t 0, ... T - 1 defined in (5).
{ E pu+m
[ K, T
0, VI = 0, ... T - = {0]
17

---

Published as a conference paper at ICLR 2025
2. B[]] > 0, where V Et=o 2 is generated by the optimal policy in 5
There exists A > 0 such that Amin (E[v") 2 Ao for any estimated e
Proof. We first prove property <
property
For simplicity of notation, let h2 = [7 K and H = [ho, h1," -rr-1] Property is equivalent
that there exists no nonzero v such that Too O, which is also equivalent to that for any # O,
v HH v > 0, i.e.
T-1
T-1 Σ
In
HH
= Σ hoh
=
[L K;
> O.
1=0
1=0
One can readily compute that
T
B
=
E
t=
T
E
|
[n,
K,]
Hdiag (E
[ I -er--=1-- (-1-1) H1,,
(20)
Kg
where diag(-) is the notation of diagonal block matrix. Next we show that E [,,=]]] is positive definite for each t. Similar to (7 we can expand the system dynamics under the true system matrix (A, B) as
0
2t =
II (=1-1
(A + BK,)
DO +
Σ 3=0
II fit-1
(A+ BK.) w/,
(21)
where IP (A + BK,) means (A+ 1K; + BK,-) ... (A+ + BKj+1). and [
(A
BK:) In. For simplicity of notation, let
P = (A+ (A + BK ... (A+ BKt)); for any 4 2 lo-
(22)
When 4 < lo, we set tt,.to In. Then we have It 1 + ΣE # It follows that
1-1
E [ [
12-1. (2 01
$ P1-1
[w;ww]] T D
1=0
11-1002020 2-
Σ
4 11
?
T
+
In
+
Σ
T
j=1
In: where the equality (1) follows from the fact that wy M 4n..5 0.... , 1, and equality (2) holds by the fact that P = In. Then, we can prove that property is equivalent to that for any #
E v Hdiag (E [mo=r]] .... [TT-IIT-1]] H 0.
which is equivalent to property 2.
We next prove property 2 > property 3.
In terms of property 3 = property 2, it's obvious that when = 8, we have Aunin (E 2 Ao > O,
ie. V > O.
In order to prove property = property 3, we prove the continuity of [[[] in terms the system matrices 0. By the recursive formula of the discrete-time Riccati equations and the optimal controller
18

---

Published as a conference paper at ICLR 2025
in 5 we can find that Pt, Pa and Kr are continuous in terms of f E 6. Recall that
E B[ 10-000 क T
n
1-1 P--1.
(23)
we can see that [V[V] is continuous in terms of f. So for any 0' E θ there exists Ao > 0 such that Amin (B(V*) 2 Ao-
where 1, is defined in 22). Plugging 23 into 20
Now we are ready for the proof of Proposition
Proof of Proposition Recall the definition of Vi, P v and y 18). we have
||0
811
p7
Intm
yl- (1-(E((V)) -1 I [r']
my
(E (14)) - | (B(() -11 || Elrl|
71
+ my
Intm
7| E [v') ||||| v' Inm In E [v-)]]
(24)
(1)
Fd + my
Inum
[B [1]) -1 1|| 1| [
p'+ Intm
| vl + my Intm - E [vi]
+ +||8-- B (r'll)
E
E-- (F E)F-!. inequality (2) follows where inequality (1) holds by the fact that E-1 F-1 E
from the results in Lemma 7 that ([E[V')) |
S C2. By Lemma 6 and the equivalence of matrix
norms, with probability at least -6,, we have where
| [vi] A and || E
[Y'] A
212 + m log
[n++m]3
2n(n + m) m)2
log (m+mm) ōL
A max
m
mm
For notational simplicity, we denote by
C max { (2222(n + m)),,m(m1 + m) 2.5
m)255]
C₁ is constant depending polynomially and depending y exponentially, For simplicity, we ignore the T-dependence C4. Then, we have
[n+m)]
(n++m) d,
log
log
A S C4 max
mi
Now can use Ar to further bound the terms in
24 Let be large enough so that Ar +
1
<
mi
(m+m)²²
2C, i.e. my 2 C3 log
for some constant
C3 2 1. Then, with probability at least 28,,
d,
we have
pl E V
+
1
Intm| < S my
< 20, and thus
mi
Amin
1
Jntm
2 Amin
E [v])
pl- E -'-E
Intm
2
1
mi
mi
2C,
19

---

Published as a conference paper at ICLR 2025
Then, we get (vi + 1 In+m)
)-1||
S 2C2. In terms
||]|| we have
(3)
| -i-||''-B
- E [r
+ +
I C2 || - E [r']] s + A1,
where inequality (3) follows from the fact that into 24). we can get
| [Y']]l S C2. Finally, substituting all the elements
0
811
2C2 (C2-(C22) [|++||rt-0 B -(= A my _ -11)
S3
2C2 (C2 Ai) (Ai+
1
S S²
+ )
mi
(4)
S 20
(1+ | + mi
_
+ D
+ 1
802
A + A
my
log
(x+m))² d1
log
[n+m)² 6t
log?
2
(n++m)) )
16C
81
m
mi
where inequality (4) follows from C2 2 1, inequality (5) holds by the fact that my 2 and inequality
(6) holds because log (n++m)² 1. The proof is hence complete.
Lemma 7 shows that Assumption [ can be extended to the neighbourhood of the true system matrices and thus guarantee the polldeossssess of the sample variance of the estimated system matrices within the neighbourhood. The following proposition provides sufficient condition for Assumption
Proposition 4. If the parameters defined in Section 2.1 satisfies
1. A E = has full rank;
2. Q > 0 and Qr = 0:
3. B E Raxm has full column rank,
then for the sequence of the controller Ke, = 0,-.. .T -
defined in 5 we have
E
R
[ K,
0, Vt = 0, , 1 1 {0].
Proof. Let e [o: 11 satisfying [ K, 10 v. - 1, where i1 RR,,0 U/ m
Recall the optimal control defined in ( by the condition Qr = 0. we have KT-1 = 0, and thus
2i O. Then, [I K, Ju 0, Vl ... T 1 is equivalent to KJT V2 0, vi 0,... T 1.
Substitute (5) into it, we can obtain
KJ A ( P R)
02 =2
Recall that
P = P41 + P (In - -Po41) Pu+1
P= [==+K; RK, + (B,) T =
We can prove that P: > 0 for any f = 0,..., - by the mathematical induction. When t = T, Pr 0, and thus Pr-1 0 by Q 0 and KT_RRKs 0. For any t 1,.*, 1,
20

---

Published as a conference paper at ICLR 2025
assume that Pa-1 > O, prove that Pa+1 > O, and thus P. > by 0, K2 RK, ż 0 and (A + BK,) T P (A + BK;) = 0, which finish the mathematical induction. And by the condition A E IR has full rank, we have
B P.I R) =.
(BT According to the setting in Section 2.1, R > 0, so B P-- R O. So B (B P B + +RR
has full column rank by the condition that B E Ruxm has full column rank, and thus = 0, which completes the proof.
A.2 PERTURBATION ANALYSIS OF RICCATI EQUATION
In this section, we discuss perturbation analysis of Riccati Equation, i.c., how the solutions to Riccati Equation (5) change when we perturb the system matrices.
The main result of this section is the following lemma. We fix epoch in the analysis below and recall that (A', B¹) are the estimators for the true system matrices (A, B).
Lemma 8. Assume - yT > O and fix any et > 0. Suppose || - All S ct |B have
B|l S c₁. then
for any 1 = 0, 1, 1,... T
| Kell S (10V ( VeL,
IPj P.ll & (10V² (T
where I, V and L are defined
(3).
To prove Lemma [ we need the following result, which provides 'one-step' perturbation bounds for the solutions to Riccati equations.
Lemma 9. Assume - 7 0. For any a > 0, W 2 1, assume ||A' - Al S e B|B B s et
and || P++1l S We S for given E {0, ... ,T - 1}. Then we have
|K K,ll < VWa,
|pl Poll < 10v ci*
where F, V and L are given in 13).
Proof. We first bound the perturbation of the optimal controller, i.e., AKt K² - Kr. Recall that
K: -(B" P B + RT)1BB3 TT PitIA, and Ki -(B' PL I +RR) R) B Pl Pl A'.
(25)
To bound AK7, we first bound |Ptt1 - Pet1 as follows:
P+1 P(+
@ (In - -yp/ - pl
(+1 - (In - -PP41)
[| - -7P( - P (In -PPP- + (In - ( (In - (Ptzll
(In - - (In -pP::) + - - (I, 7P41
< ([ -PPh)))- (In - -1. + -1 |P - Pa+1ll-
Here, the equality (1) follows by the definition P/41 and P.41, and the fact that
P = P: + PP(ln - -P:
= [T + 7P.(T - -Pp) Pt
[[TTn PP:) 7P)) P -P:)
=(In PP)))
21

---

Published as a conference paper at ICLR 2025
It follows from the fact that E F-1 = E EF FE) for any invertible matrix E and F,
Pt P(+1
$ *11(T- - --P(-1)- Pat1)(nn (Ptt1) -11111 || + 11( - P(tt1 "1 ||/ - Pat1l
1-11PPttll 1- 111111 W1IPH
Petill || + 1 1-1l1Ptt1ll
-IP-_ PPtall
1
"Wee +1)
I-7I' We
1 7I' 1 (WE +1)
rTwa+
1
Wa
(1 TT)2
1 1-
+
We
(1-1f)
1-
Wq
where the inequality (2) holds by the fact that for any matrix E R if |E|| < then 11 E) E
|aj and the inequality (3) holds because we assume that [||| Pa+ill S Wa $ 1.
To bound AKt, we next bound
B P - BT BT Bd
in view of the expressions in 25
B T Pr+1 B BTT pt
P B'
< BT Pe+i B T P.++ B¹d + BT Pe+ B' BT pl
P++ B² + B Pi+1 B'
BtT P B²
< |B Pitill :1B - BB
|B|| -| -P/+1ll ||8 + + ||B-B'| || B'|l
$ rI +ICWei ([ +4) + +
(1)
W2 + + +2c (Q
< 2( - -1)
where inequality (4) holds by the fact that We S 1. Similarly, we can derive that
BT P-iA-1B1 BT |
S B P441A- B P PetiAll + B P B PL PI + B A' B PL
$ 2( + 1)f
Then, following similar argument as in Lemma 2 of Mania et al. (0119) we can obtain
K = || KYll < 2(T + W)
Next we proceed bound ||l| Pt|l. Recall that
P. Q + K,T RK, + (A + BK)) (A (A + BK)),
P = Q + K. T RK} + (A' + B² kt) Pd. PA + BkK)).
We can directly compute that
A + BK, - A' - B' K
< ||4 - A'll + +|BK BK!|| + BK B'K:||
Sat + LVWQ + a(VWa+I)
(5)
$ 4 +TWWe + +yWe
< 2VTWa,
22

---

Published as a conference paper at ICLR 2025
where inequality (5) holds by the fact that et (VW& + r) & VWa T&WV when both W and V are larger than 1. Similarly, we can derive that
KJJ RK K RKIl
K RK, - K2 RK:|| + [KTRKK K. RK:
VW + (Wee
2
In addition, we can derive that
(A+ BK.) PTC))PPPP (A (A+ (A (A BKY
$ (A+ P BK,) (A+ (A+ Pi+1 (A+ BK))
+ (A BKK) P (A BK,) - (A+ BK)) P/ P
(A (A+BK))
+ (A + BK)) T 1
(A (A+ BK,) - -(A+ + P (A -BK))
- 2V + We <V>2<"WWe
I 8VV2LTTW
then follows that
|P - Pall s 10V2 Li
The proof is therefore complete.
With Lemma 9 we are now ready to prove Lemma
Proof of Lemma g By definition know that P/- Pr Qr, and thus have | - S a.
By Lemma we can derive that at time T - 1,
k Kr- ||| VEL,
| - 1| S (10V² LT^)a,,
which implies that
| - - Kr S (10V² LTt)
|| Pr- S (10022TT4)
Applying Lemma recursively, we obtain for any t 0, T - 1.
| - K,ll < (1002_Í-)TT---- VeL
||P| prll S (10V2 C
which completes the proof.
A.3 SUBOPTIMALITY GAP DUE TO THE CONTROLLER MISMATCH
In this section, will simplify the performance gap between the total cost under policy m.ik and the total cost under the optimal policy. We recall the corresponding total cost under entropic risk,
(3 2
Qraff ))
J5 (IO²
1 7
log EE exp
Σ
LAT wi
Quii L.k
I.AT + ui Ruf"*)
LNT xe
where df = K/att" and K! is obtained by substituting (A'BB) into equation 5
Let H. be the of possible histories up to the I-th step in the k-th episode of epoch Then, one sample of the history up to the t-th step in the k-th episode of epoch is
H!* (2)
1.1
1.1 122
2.1
211
Lk
1.k 1.8
27
20
20
26
24 24
23

---

Published as a conference paper at ICLR 2025
We also introduce some notations, which will be heavily used in the regret analysis. For any t 1, T 2, we define the following recursive equations:
D4-1 AK (R+ B PT A
D4-1 - (ln - -
Dj = AK? [R BT P1+IB) AK' + (A+ BK!) DA+1(A+
(26)
Dj (In -DDD)-1111 Di,
Dj AKO (R+ B BTBB AK) + (A+ BK)) (A BK)),
where ΔK} K. - K, and Pr is defined 5 In the following parts, we still consider the risk-averse setting, where 7 > 0. The following proposition is the key result of this section. Proposition 5. We can simplify the performance gap in the k-th episode of epoch I to
T
J8 (al Jo (al
log (det (In ->D()) + 200
LT&
Dja L.k.
(27)
27
where D2 is defined in 26
In order to prove Proposition
5 we introduce Lemma 10 see p.8 of Jacobson (1973).
Lemma 10 Jacobson (1973). Consider the linear dynamic system J++1 Ax, + Bu, + we, wi For any sequence of positive semidefinite matrix Es+1 satisfying
(0, 1 0,... T-1. 1.
In y Eet1 > we have
E exp (2 F Fe410441)
(3 (Ars + Buu) (Ax + Bui).
= (det(In y yEs+1)) cxp
where Es+1 = Est1 + +7E++1 (In -EE11)--
We apply Lemma 10 simplify the performance gap 15 (2b J5 (ab")) in the k-th episode of epoch in the following lemma.
Lemma 11. We can simplify the performance gap as
T-1
Jo LK (50 - -= log R
LKT AK
(R+BT BT
1.K
H
exp
1=
(28)
where AK! = K!- - Kr-
Proof. Denote ( = 2 It
L&T P.zt -ET-1 + log det (1 - 7Pt+1) , = 0, 0, ,T 1,
which is the dynamic programming equations of LEQR problem. Qray.
When 1 T. Jr (
L.T
FT
By the definition of J 1 (tt and (ob have
JØ
L.k
Já (1(b%)
L.T Qraft )) 1a0t H. Io(ab
1
?
LET Qat Lkk + uhAT Bublt)
log
exp
It
y
T-1
1
log
exp
?
Σ
((0 L Qurt + utt LKT Rul.t) + Je(at -.(ottt)))
7
1=0
Qrayh ))
L + Teg
Ja Ja(
(29)
24

---

Published as a conference paper at ICLR 2025
Recall that Jr (2T 1. L.AT
IT
QraT L.
we have
J0 (5t) Jo (3 (.ke
T-1
1
log E
exp
?
Σ
L.T Qat li +
LKT Relgh) Je(at() Je (x(
7
t=0
Jr((
Hi 16
1.k
log (exp(Jo(xb*)))
+
7 T-1
(1)
1
log
exp
I.TT Qalt + T Bultt) +e+1(a(411) J((o
x6 H
2
T
(2)
log
exp
7
2 Ft
LKkT
(Q + K. RK!)at 1. + +2 2 Petiaet1
INT
-2th
l.kT
Prrti
1
log de - pPt..))
l.k 20
H
+ 27
where equality (1) holds by canceling out the Jo (1)ga) inside and outside the entropic risk, and equality (2) follows from the definition of the total cost under entropic risk and u, &. By the law of total expectation, i.e. [[[ E[E[X|Y, Z|12] for any random variables X,Y, Y, Z, consider the conditional expectation
exp (1(2
(Q + K. RK))
1RT 2 .1+1 P4414441
1,KT 2 2t
P,x
+ log det - -PPtt)) H.t.
1 2n
1.T (Q + KiT RK;)a' 2"0
1 1.T z²t
Pial + log det -7Pan))
exp
27
(2
ait I.kT "11
Petiafti)
L.t H.h
(30)
exp
(7(1 1 T.kT (Q + KTT RK!)at
(3)
exp (
2 (?(""
1&T Plati + log det sPeta)) 2t
1
2
(A+ T P.+IAA BK)) )
(det(Ln (det(Ln->?lee -PP=1))
exp
1,K I4
? 1.T (Q + K RK (A (A+ T (A+ B x4 LAT
Pealit)
cxp 2 It
where the equality (3) follows from Lemma 10
Recall that AK? K K, and P. Q K, RK, + (A+ P + BK2). Then the RHS of Equation
30 becomes
x TT 2
(a+ (AK) + K.Y RRAK! K.)
cxp
+ (A + B(AK) + K.)) K. (A+ BIAK) + K.)) 2f -2
_Y 1.T P
Y LAT
AKT IT (R+ B B...PIBBBKKK LA +
LUT LNT AK! ((R+ BT P +
BT P41A)
exp
(1)
LKT 2
AK!T (R+ B B)AKK
exp
(31) 1B P.+1A Finally, substi-
where the equality (4) holds by the fact that K, tuting (31) into (30) and then substituting 30 into
(R+
P B
29
get (88
n
25

---

Published as a conference paper at ICLR 2025
With Lemma 11
now ready to prove Proposition S
Proof of Proposition
We prove the result recursively. When t= T 1, we have
E
exp
2 2
Y TAT
AKT
LK (R+ B PT -10-11
(2 - 1
H4
exp
2
(det(In 7 D4--1)) -
LKT (A + BK7 T BK7 22)-))---- 1.k 11 -T--
exp
2
where equality (1) follows from Lemma
10 and u/ - When t. T 2, we have
T-1
E
exp
7
Σ
LAT
AKI
(R+ BT P. B) 1141
2
1=--2
(det(In y DD
[ 2 "T- AKT 2 B P1-1BB)
exp
(A BK ) T DJ (A BK -)) LKk 1)
= - -D
[exp
exp
[ [I D2 T-2 DJ 2,k Hr.
-
T-1
II
(det(In - -DD)) - exp ( 2 1 BKG 2/- (A+ + L.k ))
T=T-2
When = i = 1, ... TT - 1, similarly, we have
7
Σ t=
AK! (R+ BT ( u
E
exp
2
T-1
exp [ (A+ BKLL) BK! )att 1)
= II
(det(Ln -DD)) E=
Repeating this procedure, we get
Jo
i
(50
L. - Jo(50) (
T-1
1
log
E
II
(det(In - -D())
7
1=1
7 L&T ((A+BK)) BK() (A D BKK) + AK! (R B B)BAK)))) bba)]
2 H..k
X exp
2
1
log E
(dct(In - -D))) - cxp (7x0
1,RT Db2b
1ik)
1ik
H.Hh A
T-
(2) 1
log
(det(L,. 7Di)) - exp ( IAAT Db=bb))
(2a0
T-1
Σ
log (det (In yD!)) + 1.kT Dyabk.
27
2
where inequality (2) holds because Dj, = 0,...
T ...
is based on the data from epoch 1 to epoch
1 1-1.
26

---

Published as a conference paper at ICLR 2025
A.4 PROOF OF THEOREM 1
Now, we can derive the regret upper bound for Algorithm 1 Before we derive the high probability bounds for (27). we introduce some new notations and provide the bounds for Dj in (6)). Recall that
6--11 - - い = ( + +12f=) t 0,... , ,T -2 2,
(32)
where the definitions of V and are given in 13 have
Assume that for any t = ,. ... , - 1, 1 E [L],
(33)
2 22
We can choose a proper constant Co for the initial epoch size my in Theorem so that y can satisfy
assumptions in (3) when it satisfies the assumption of In -P++1 > 0 and I, - > 0 in (5) Because D are defined recursively, we obtain the bounds recursively from step T - 1 to step 1. At step T-11 1,
| ||
AKF_ (R+ (R+BTPIB) P.B) AKt-1|
S R+ BT Pr. -|AK%
(1) $ v2
= MT V2
where inequality (1) follows from the definition of 1 in 13 and Lemma 8 for D4-11 have
In terms of the bound
D
(In DD -1 Dr-1
(In DD' -2
D
(2)
1|4_-11 11
1 > D
(3)
< 2/1D'--ll
= 2/T--1V2 V222.
where inequality (2) holds by the fact that for any matrix M E Rax= if |M] M) v T-IMT and inequality (3) follows from the assumption in 33
1, then [|(Tn
At step T 2, we have
|| = |KT (R+ BT PTPr-10 B) AKt_ (A + BK(_)) 2)
D (A+BK7
$ 2T (10V2CT*)
V2 + + + KT KT) -
(1) a (10)² 2 12et + 6π + 3 (10V2 uee?) -20T-
= 2 (1OV&CT*) 2
+ 12f vT V2 + o(ff)
= Vr-2V2G + o(2))
where inequality (4) follows from the fact that
Σの zz ||
< K DK K ||
Similarly, we have
|
2 + occ?)
2
27

---

Published as a conference paper at ICLR 2025
Fort T 2,
recursively derive that
[ - &.V + o( | - 20 + +(()),
|| vo 2 o(f))
(34)
According to Lemma
the performance loss in the k-th episode of epoch /
Jū
1.2
(
J.k
Jó
(3r L.k.
1
log (det (In -DD))) + 1 LT
2 20 D8
27
(35)
(5)
1
T-1
log (1-v1D=(1)* " + |10 ||
2-
Here, inequality (5) holds because I, DD = (1 (1->11DAll) I, (1 (1- 70: +o()))
and det (111)1 In) = (1-111D)11)* Substituting the inequalities in (34) into
35 we
obtain
J0th (100
1.b - JJ (z/x²)
(6)
T-1
Σ
log (1 - + |ool| (
22
(7) n
T-1
Σ
2 + to(
+ + |zol +o o
2
n T-1
1
1リ1 ||
vo V2 + o(E)),
2
2
t=1
inequality (6) holds by the inequalities in v) S for any y > 1.
34 and inequality (7) follows from the fact that log(1 +
Now, substitute the high probability bounds derived in Section A.1 into (35).
Recall that
conditional on event Gl-1 in Lemma with probability at least 1 26, we have
log
(m=+n)² 61-1
log
(m+n))
log²
(m++n) 6:-1
1 1 01 S se:== Ci
81-1
mi-1
m4-1
m
Similar to the procedure in page 26 in Basei et al. (2022), we set 8,-1
7- Mir-
8
3 21-2m, m, = Co(- log 6), where E (0,
and Co a finite positive constant that satisfies (m++n)² 81-1
log
Co C3
sup IEN+ (E)))E
2!-2(
log 8)
min
3C,
where p is defined at the beginning of Appendix A.1 thus
Then, we have m 2 C3 log
(mi+n) 81-1
and
log
(m=+n)2
log
(m++n)? 6y
?
log² 2
[m++n]2 67
[m+n]] log
8
C
3C1
my-1
7
mf-1
m
where inequality (8) holds because C3 2 1 in Proposition 3 page 27 in Basei et al. (2022), we can prove the following event
By a similar mathematical induction on
(m++))²
log
g
110 -0l
01l 3C1 V
W MENtYa Uuo Eδ)
(36)
mi-1
28

---

Published as a conference paper at ICLR 2025
holds with probability at least - 1-- 81-1 n'6 i.. P( 2 1
- m²6
Under the event G, which satisfies P(G) 2 3 Regret(N)
we can derive that
N
J (m²) Jr(()))))))
my
(Jalit (ogth) (xb+
1=1
(9)
2/ V 27 + 1 1 12 26 2 + o(E))
1
T-1
$ m1
Σ
+
Σ mi
Ve + 2 || 2l vo ot + o(E))
2 1=1
1=2
t=1
(20)
m1
Σ
T-1
w/e D2 o7 + 2 11100| 12 12 + o(ef)
+
Th
n
T Σ
4/ 2/212 122
9C
log
(m+n)²
m4--
1=2
log
(m++)² 6:-1
log
[m++]*
+ #2 | 222 9Cp
+o
62-1
m
m
(11)
2 Chigh + m2
12
T-1
Σ
w 12 cl
+
1
2
2
t=1
1/ + 1 ]
+
ocpp2
11
Σ
log
m + n2
v8
+ log(l (1(( -1)
1=1
1=2
(12)
T-1
Σ
log
L + L log
v
where inequality (9) follows from
35
inequality (10) follows from the definition of the event G
in 366. 1i is defined in (32). Chigh in inequality (11) is constant depends T, 7, m, V, polynomially and it can bound the higher order term in incquality (10), and inequality (12) holds by
Stirling's formula: E log(l 1)
[og((L- z C'LL - 1) log L 1), where C' is a positive constant, The expression of C given by
C = Polynomial (C1, C², V. E1, n, mi, ||=ol))
where e is the estimation error in the first epoch, mi is the number of episodes in the first epoch, The is defined in (32). C₁ = 16C is from the proof of Proposition 3 and V is defined in (13)
B REGRET ANALYSIS OF THE LEAST-SQUARES-BASS ALGORITHM WITH EXPLORATION NOISE
In this section, we prove Theorem discussed in Section 4 The proof structure of Theorem 2 similar the proof structure of Theorem We present the high probability bounds for the estimation error of system matrices in Section B.I. the perturbation analysis of Riecati equations in Section B.2 and the simplification of the suboptimality gap resulting from controller mismatch in Section B3
B. BOUNDS FOR THE ESTIMATION ERROR OF SYSTEM MATRICES
In this section, we derive the high probability bound for the estimation error of system matrices in Algorithm 2 Different from Acction[A1] we adapt the classical self-normalized martingale analysis framework to derive the desired error bound.
Similar as in Section A.
we fix the k-th episode and define the following compact set
{0 E [(n+m))x xn
0 oll < u
29

---

Published as a conference paper at ICLR 2025
where > 0 is constant that satisfies
3TN22 {
2n
3n?N
ëN log
max
log
(n mmmmlogg log
1+
2(n + m)
82
A
80n
ëN log 6
4TN22
80A(n + m) T
log
+ (n + m) log
1+
cT
82
A
cf
(37)
Here, I is defined in (1), À is the regularization parameter and c, 0 are two constants indepen- dent of and N but may depend on other constants including n, m, 7. The explicit expression of e and ē can be found in (44) and 53 For any estimated E E, there exists a universal constant
CK such that
|
S
Ck.
AI,
(38)
where K, is the control corresponding to & and it's continuous terms of according to (5) also define the following event
We
We will prove P(G+) 1- = E -,, A).
(39)
N-1 N-I (1-186 in Section B.4
The main result of this section is the following proposition, which provides the high probability bound for the estimation error of system matrices estimated in Algorithm
Proposition Let 8 E (0. 1). Conditional on event gh, when kT 200 (3(n + m) log (t)).
with probability at least 1 1-48.
| 1g5+1-8112
-012
80n
nn2 log
82 ) (n mo (1+ Tk log (25) )
80A(n m)² cTVK
cI
X
where I is defined in (13). the explicit expressions of c. and can be found in (44) and 53 n
is the dimension of the system state vector, is the dimension of the control vector and X is the regularization parameter. When kTT < 200 (3(n - + m) + log (t)). with probability at least 30,
||gh+1 -012
2n A
log
n²
+ (n + m)) log
1+
čk log
TN (
)) 2(n + m
A
The proof of Proposition i long, and we will discuss it in the following subsections.
B. PRELIMINARIES
In this section, we recall an important high probability bound, known self-normalized bound for vector-valued martingales. It will be used in the derivation of the bounds for the estimation error of system matrices.
Lemma 12 (Theorem in Abbasi- Yadkori et al. (2011). ). Let {Fi] be a filtration. Let {ntHe I be real-valued stochastic process such that 17, F.41 measurable and me is conditionally R-sub- Gaussian for some R 2 0 i.e.
E Be F.
S exp
R2 (~2
V.ER.
Let (X1 be Ie -vauued stochastic process such that X, is F-measurable. Assume that V is a d positive definite matrix. For any 2 O, define
V Σx,x,
S. Innx.
nxX.
Then, for any > with probability at least
for aol 2,0,
det (V:) det (V)
|| 2112 log
where ||5e112_11 STT (V.) S.
30

---

Published as a conference paper at ICLR 2025
B.1.2 SELF-NORMALIZED BOUNDS FOR THE ESTIMATION ERROR OF SYSTEM MATRICES
In this section, we analyze yze the estimation error based on bounds for the self-normalized martingale. Similar to Section A.3 let HH be the set of possible histories up to step t in the k-th episode. Denote the history up to step the k-th episode by
H (x)- u0: ... ZT. 0
(40)
2-
The following lemma is a modified version of Theorem 2 in Abbasi- Yadkori et al. (0111) and Lemma 6 in Cohen al. 2019), which provides a coarse self self-normalized bound for the estimation error.
Lemma 13. For any 8 E (0, 1), with probability at least
we have
n² det(VV)
Tr ((0kt1 -) T vh - -0) 2n log
+ 2A11011
(41)
82 det(Ar)
where (k+1 is the estimated system matrix defined in 15 regularization parameter and
0 is the true system matrix, X is the
A AI +
Proof.
We first follow Lemma in Cohen et al. (219) to simplify g++1 8. Recall that
i1+1 OT 2f + wt
w ~ N (0,
where 2/ = [2f]]] uf Together with 15) we can obtain
k Σ
g++1 = (D4)
(=t
0
wi:))
k T-1
k T-1
= -(Da)-
A0 +
ΣΣ
2 0 +
Σ
2 2wmg
i=1 t=
i=1
1=
= 0 (V²) -1 (S - A0).
where we denote 5 = Σx= Et=o z/1ęT for the simplicity of notation. Then, we obtain
Tr (akt+1 8) T _)_(T ph (Bh+1 -6)
Tr (s - 10) (p4) -1 (S -10)
= Tr [s (p²)= -1 st s + 1²0 (1i)- -1 0 --SSTT, (DA)-10 0 - -o0 (V*)) -1 s
(1)
< Tr (stT, (Dh) -1 -1 s + T²0T (Di)- -1)) +2 |0r (i²) - $1 ( - s
(2)
< 2T (s#), (p4) - + 2x (0T (FA)- -1)
(3) [ (v²)- -1 $ + 211101
2 2'r
(42)
Here, we use Cauwhy-Schwarz inequality (I.FF) < ||||||||| for any matrix E and F to obtain inequality (1), we use the inequality 2ab < a² 12 for any a and b to obtain inequality (2), and we use the fact that V 2 Al to obtain inequality (3).
We further bound Tr ( (VM) s4_1) in 42 to get the result in 41b Let St( =
Σ Σ. 2 2 (j),j 1,... n, 0, element of the random vector w³. Recall the trajectory in 40 of is H -easuuaueel for any step
1, k 1.... N. where wi(i) is the j-th
31

---

Published as a conference paper at ICLR 2025
in the i-th episode and w[( is W4+1-measuraie for any step in the i-th episode. Therefore, can apply Lemma 12 and obtain that with probability at least - &.
n dot(V
ST) (V*)* -1 - - 2 log
8 (eT)
By a union bound, we can obtain that with probability at least 8,
n² det(( 82 det(Al))
Tr ( (V+)
S
()) (VA)-* S - S nlog
(43)
On combining 42 with 43 we can obtain
After deriving the coarse nelf-norm bounds in [41] we need to find the upper and lower bounds for 7 to obtain the result in Proposition 6 We follow the proof of Theorem 20 in Cohen et al. (2019) to derive the high probability lower bound for V*. The main difference is that we consider a decaying exploration noise while they consider a nondecaying exploration noise, The next lemma provides a lower bound for the conditional expectation of af 2t Vk, t, which is modification of Lemma 34 in Cohen et al. (2019).
KT
Lemma 14. For all episode and step i, conditional on event Gr, we have RT [ 2 vk
E
2
Imtai
t + 0,
where e > O is a constant satisfying
C -xCK
CK + +
(44)
2
Ck CN v C +4+2
with CK defined in (38 and
10.
Proof. Recall that 24
[xt
AT
we have
I,
0
0
E [
K
E [ x4
T [ [
Ia
K,T
]
+
0
1
Im
VR
(2)
Tn
0
0
[ In
K&T ] +
K
Im
Vk
In
K.
Vke
+ Jatm
Kt
KV K
+ | (1
c) m
VTg
vk
In
|
و In vk
k
+ c
I Iutm
Kt
-
Vk
Intm-
Vk
Here, inequality (1) follows from the fact that 24_1 [ w/T1]] is H -easurable and
E [a kT [ = E (Art + But + w (Art + But + w /
= (Aat + Bu (Aat + But + E [ AT |
ż In.
For inequality (2), when 0 <es - /Ckc///tt +4+2
can obtain
1
Kh kk TT
3 KKKK
+
(1 - Im.
(45)
Vk
We can prove that (45) is equivalent to
K 3 -
K. - 1 (1 - c)
Solving the inequality - C2 < 1 c, can obtain 0 < < -k-Ck C3 +4+2
32

---

with Published as a conference paper at ICLR 2025
With the lower bound for the conditional expectation of 2f =f Vk, we can derive the high proba- bility lower bound as Lemma 33 in Cohen et al. (2019).
Lemma 15. Let 8 1). Conditional event G when KT > 200 (600(n + m) + log (1)), with probability at least 6, we have
cTVK
Intm-
(46)
Proof. Let e E g*+m-1 where g=+m-1 {E (o = 1}. Let T = eT 2 and let y be an indicator random variable that equals 1 if (1 > 2Vk and 0 otherwise. By the similar arguments
as in the proof of Lemma 35 in Cohen et al. 2019). we can prove that
E [> =P (> 1 5' if
(47)
Let U 5% [ Then, (UF) is martingale difference sequence with |U S Vk, So we can use Azuma-Hoefiding inequality to derive the high probability bound: with probability least 1 6,
ΣΣ
T-1 Uイ - 2kT 2kTlog log
{5
1
KT
(48)
10
1=1
where inequality (1) holds when KT > 200 log (t). we can obtain with probability at least 6,
On combining
Uj
y
E [1
48
ΣΣ
D
H
KT (2)
KT
kT
KT
(49)
10
10
10'
where inequality (2) follows from
47
Denote V
Σ
1i=1
11=1
44
Then, get with
probability at least 1 - 5,
T-1
(1) KT
VKTc 20
vvke= = ΣΣ
c
2
2vh
10
2/h
1=
1=1
t=1
i=1 t=1
where inequality (3) follows from the definition of I3 inequality (4) holds by (49 Finally, by the similar } -net argument in the proof of Theorem 20 in Cohen et al. (2019).
prove that when
KT > 200 (3(n m) log (t)), with probability at least 6,
40
cT
which is equivalent
T-1
cT vT
4
=
Intm-
40
In addition to the lower bound of k we also need to find the upper bound of V to get the final high probability bound for the estimation error of system matrices. In the following lemma, we provide the high probability upper bound for | [|. which plays a vital role in deriving the high probability upper bound of V.
Lemma 16. Let ö E (0, 2). Conditional on the event Gh. with probability at least - 28. for all SIS T, we have
| S 6 (T( +x)) (n² + mm) max f|lzoll 13 logg
TN
(50)
where T is defined in
13 and Cx is defined 38
33

---

Published as a conference paper at ICLR 2025
Proof. Recall that = A + But + w (A+ BK 1 + BBl-1 + w Similar
to 21
simplify 244
0
x
II (A+ + BKJ)
26 +
Σ
II j=t-1
(A 1A+Bu BKg)
(B9) + w
1=
==0
where I + BK}) (A + BK () + BK,
(A +
BK 1), and I (A +
)K = In. Similar to Theorem 21 and Lemma 32 of Cohen et al.
2019). we can use Hanson-
Wright inequality in Proposition 1.1 of Hsu al. (2012) to derive that
P (1|uB11
< 5n log
TN 8
|1sf/11 S 5m
log
TN
vkir r
2 1 - 25 (51)
8
Then, we can bound the state vector by
| ||
II |=
(A + BK5)
|| +
(A+ + BKJ)
-| + u=
0
<
II 5-t-1
(IAII + |BB|
(K | || + Σ II (|4|1 + |BI|| (|15 (I |1,.11 + 11 I))
(1) 2
+ (K]
Σ V5t
+ (1
mam + n²
log
(TN 8
ki
r=0
-i(11 120l|
+ F'(1 Ck) -1
v3
1
m n² log²
TN
T(1 Ck) -1
ki
2 ((([+CK)) ||00|| +5 5 (T(1+ (T()+CK))
( n Floo''
TNN
s6 ((f(1+CC)) (n² + +m3) max fll 1) i logg
TNN
where inequality (1) holds by the inequalities in (5 and inequality (2) follows from the fact that T(1 Ck) - 1 F(1 + Ck) - P + Ck) = 2 r + Ck) and k 2 1.
With the result in Lemma 16 we can derive the high probability bound for ||V*||
Lemma 17. Let 8 e (0, 1). Conditional on event T with probability least 25, we have
72 (f(11 + +Ck)) (n + +m²) .mxx { 11, 13 2 log (F(1 (R]++K)) -1
TN
| < S (1+21+CC#)
8
+ 20m 2 /KT log
TN 5
Proof. Recall that V = Nntm + Ek
2t=0 _xdT_2 24=xx; [ oz 1T. We have
h T-1
||
+
|
=x+
(1==|1 + [
(52)
(1|=1) + 2| ||
2
Σ
((1 + 2|=11= +2 17)
34

---

Published as a conference paper at ICLR 2025
where inequality (1) follows from the fact that uu + ell
I 2||u||² + 2||=/|?, Vu, inequality (2) with probability at least 28, we can
holds by (38). Combine the results in Lemma 16 with (52)
get
(3) ||
72 [ (1+ (T(++ 21 (n + +m+) max (1|zol1 F log 20x2
TN
X
(1 +
10m
(TN)
(N
log
Vi
[[(1 Cx)) 27
-1)
TN
= (1+1122C3
(n + m²) max {[<xol?? ( 13 f log
(î(I+ [k)
8
-1
TN 6
+ 20m 3 V.&logg
where inequality (3) follows from 2|10||| Yu,e. v.
50 and
511 in Lemma 16 the fact that |/u + u112 s 2/
For the simplicity of notation, we denote
72 (T (T(1+K)) -1)
ē= +1 20k)
(n + m²) max {1100l1 12
20m RT,
(f(1+CK))
-1
(53)
which is a constant independent of k and N. Then, we can get
TN
| S X ōk log
(54)
Now are ready to prove Proposition 6
Proof of Proposition 6 We can simplify
41
as follows:
Amin (V*) ||0tt1 - O1f < Tr (OOt) - 0) T p. (0h+1-0) 0))
n dot(TM))
< 2n log
82 det(AT)
+ 22
(55)
(1)
n2
|| )
S 2n
log
+ (n+ + m)
21110112
where inequality (1) follows from the fact that del (M) S del() Amx (M) In) A VM
Baxa When kT 2 200 (3(n + m) + log (t)). substituting (46) and 54 into 55
with probabil-
ity at least 1 - 48, we have
|10h+1 1 011 < ||ah+1 - o|l
80n
n²
x ōk log (2N) (10)) + 80A(n + m)
))
< cTVF log
+ (n + m) log 1
82
cI cl
When KT < 200 (3(n + m) + log (t)), because 1h = X + Σ 2' = 2 XI, with
probability least
1 38.
||ght1 01|² < ||tt1 0||
S 2n
n2
+nn + +m)+mauu log 1+ A + čk log
) ))
(TN)
log
+ +(n + r2
82
The proof is therefore complete.
35

---

Published as a conference paper at ICLR 2025
B.2 PERTURBATION ANALYSIS OF RICCATI EQUATION
The perturbation analysis of Riccati equation under Algorithm 1 and Algorithm 2 is the same. So can get the similar bounds of Riccati perturbation by replacing er with en in Lemma 8 where <x max [1] A|, | B The modified version of Lemma is presented in the following lemma.
Lemma 18. Assume 1 - -r' > 0 and fix any O. Suppose ||AR All S cR, BB - B| S
then for any = 0, 1... ,T 1. we have
| Kell & (10V -
|
Pill (1OD&CT")--EE.
where the definitions V. L and I can be found in 13
B.3 SUBOPTIMALITY GAP DUE TO THE CONTROLLER MISMATCH
In this section, we will connect the gap between the total cost under policy n² and the total cost under the optimal policy with the estimation error and the perturbation of Riccati equation in Appendix
B.I and B.2 The proof framework is similar need to analyse the additional exploration noise added to the control. We define the total cost under entropic risk following policy n (with slight abuse of notations) by
the framework in Appendix [A.3] except that
TeTTQri ut Ruf) + a Cratt) ))
JØ (xt)
1 Exgpe ?
2
Σ
K is obtained by substituting (A*, B*) into (5). Similar to Appendix A.3 we introduce the following new notations used in the regret analysis. For any = 0, ... 2, we define the following recursive equations:
where uf Kkt + of ot N - -e
D AKTI, ( B Br
レ = σF
[RK--1 + BT (A BK
F#_1 1 = of
R B BPBB.
U 1 = D4 + +yE+_ -
(Im F -
Ek
Ú (4, -U 1 -)-
(56)
D. A R BT BP++t1B AK, + (A+ BKA) T (A (A+ BK?),
EN = ON [KK] + +B (T++1+ + (A++)(A+BB
F = of R [P 1
U = D +TE, (Im -
Ú (In -
where AKŌ == K. - K1, a = k t/2 and Pr is defined in (
We then follow the proof framework of Appendix A.3 derive the bounds for the suboptimality gap due to the controller mismatch. The key result of this section is the following proposition. Proposition 7. We have
JØ (xx) (x
1 log det (In FF!
1
1 AT log det (Im (Im-7U7 )ū,) + 20 U
(57)
24
2" t=
where Fi and Up defined in 56
36

---

Published as a conference paper at ICLR 2025
In order to prove Proposition 7 extend Lemma I0 0h k #.
and prove the following result. Recall that
Lemma 19. For any t E [T
11, we have
D D
F F
][
1)
exp
Ox gt
Di
= (det(In
- -),)) -1/2 (det(Im - -1F()) -1/2
(58)
2 x (A + BK (A+ T0
x exp
2
+ 20 B U, (A+ + BK + ot U. Bgg
where given (x ub-1).
x l
N ([
A But
Lntm)
kk
Proof. We obtain from Lemma that
o ge 1)
xt
D
F
x
E
exp
Ek
E
ok
gt
D Et
E
1))
-
det
mm -
Fl
(59)
Ax
+ Bu
]'
(Imit ?
D
E
))
x exp
2
0
Er Ft
D
EKT F-
][
Art
+ But-1
1).
E
0
We perform block Gauss-Jordan elimination, take the inverse of the matrix in the determinant of and obtain
59
D EP
E F+t
1)
Intm
7
In
DD
-7 Fi
-c EEAe
Tm y Fl
In
0
(In - DDD - 2 (Im - - E3)
(Im
rF/)
-1 E.
Im
0
(Im - F(t)
In T.AT T (Tm
=
x
Im
EL
EL2
EL3 EL4
where
EL1 (In 7D E
TT (Im )F!)) -
FT, (In 7 D 72 Fi (Im - - F.t FF,)) -1 Fk (Im PPt)
FLg = (Im F!) -1 1 F (In - D. - 22 F
(Tm 7 F(i -1 )
EI4 (Im F Ex Ex D. 7 TT (Im -
kT (Im -
(Im F!! -1
37

---

Published as a conference paper at ICLR 2025
Then, can obtain
D
E
1))
det [nutm= -7 7
E
F
(det (In- - - F" (Im - -FF+) )
- (dot(Im 1 -) -
(60)
(det (In - )) (det(Im Im 7F+))
where U. D + FFtt (Im -ド -1 Fitt and
Art-1 1 + B T
Intm (Intm- -
D Eyy
F
1)
D
F Fl
][
Art + But
0
F
F
(Ax7-1 + But_1)" TT
(In - FF (Im - 7 PP:) Fx))
x <D, + 7E, (Im - -1E,t)
(Aut + But-i)
((A + 1 + Byjt1) Up ((A + BK ) + Bgt²-)
= = (A+ (A+ BK )) E (A + 1 + 2 B UA((A (A + BK )o +
&T
B U Bo 1
(61)
where Ü7 (In - -- On combining (60) and 61 with 59 we can obtain 58
The following lemma is an extension of Lemma 11 which provides a coarse simplification of the performance gap in one episode.
Lemma 20. With Lemma
10
we can simplify the performance gap to
J
(xx0)
0
T-1
1
log
E
exp
Σ
7
+ 22 T (RK# + BT PE+1 BKK) D
+ ot (R B BT Pi11B)st) )
z.. 2/ k -1
where AKF Kē- K₁ and Hh is defined in 44
Proof. By similar procedure in 22 we can derive that
JØd x (1))
Jj (20)
(a utt + Je+1( - ag. H²
log E
exp
7
2
T
11)
log
E
exp
?
Σ
2 rt
(Q + K. RK + st RKt 2 oh TT Rgt
1=0
log det - 7 Ppti)) ))
TT
P k
kT Paat +
1
20 H
+
2 i+1
x+1
2
(62)
38

---

Published as a conference paper at ICLR 2025
where equality (1) follows from the definition of the total cost under entropic risk and uf K2 + g.. Again, we apply the law of total expectation, and compute
1 AT (Q (16
exp
2
K T RK ya + 95 RT RK t + 2 TT Rgt
+
r 1+1 1
2" kT Prat +
log det(In - r(Ptti)
H
27
(63)
T (Q + Kt 2Kt)
ET Pask + St
RK + z
TT Refe
exp
2 -2"
log det (In 1 >Pttil)
aTT 2+1 Potzatti) Hi
+ 27
exp (2 x
follows from Lemma that
(7
kT (Q+ K&_ RKt)at
1 1 SttTPat + ot RKtat + 1 T not 2"0
2ot
exp
log det((n - - - >
1 27
+
(det(In - -7Ptt1))
2 KT (A+ (A+BK?) (A+ BK}),, + nit B P BKt)at
exp
It
2
TT B Bot
+
2
7
T (Q Kt RK! + (A+ PA+IAA )a x Pratt)
exp
2
+ +7th KT (RK) + PA
2. MT (R+ BT P.+ B)ss
Substituting AKt = - - K, and the Riccati equation P. = Q.K RK, RK, Pa+1(A+
BK)) into
63 we obtain
TT 24
(Q (AK + K,) R(AK + K2) + (A+ B(AK + K.)) P++ K. ( + Kil))at
cxp
2
+ g
T (RK) +B +B (A+ BK 2
kT (R B P1+
2
7 KT Pirt
2
2 TT AK! TT (R+ B P++1B)AK 7at KT AKt ((R Pr + B P(t1A)a 2
exp
+ g6t
KT (RK) +B P.+I(A+ BK + 9: (R+ BT PP+1BB)
KT
(2)
I ET T AK! (R+ T P ot + got TRKT(R + BT PT (A )k
exp
2
+ T 2
(R BT B191
(64) where the equality (2) holds by the fact that K, - (R + BT 1++1B)-1BT TT Substituting
Pi+1A.
64 into (63) and then substituting 63) into 62. we can get
J (x (x)))
T
1 - log E
AK. ET (R+ (R+B B)
exp
1t
7
2 1=0
at T (R+ B PetiB)ot 1)))
+ +2
2 + B Pr... (A + BK
39

---

Published as a conference paper at ICLR 2025
The proof is complete.
Combining Lemma 19 with Lemma 20 we can prove Proposition
Proof of Proposition
We prove the result recursively. Recall that k When / T - 1,
exp
| 2
RT TT-
AKT (R+ (R+ BT
2o 91-1
-1 ET
(RK) BT Pr(A + BK- (Kf--1)aa--
x 1 B Pr Hi-
-2
91
(-+ -ーー + 20 1ork-gr-11 DT-1 -
Fk
k
x 97 pk -1-- ) [
exp
+
2
2 (det(In - -))--1)
(det(Im -p
7
kT 2--
2AA BK*BB T (A + BK 2 1
exp
T B
U (A BK 2) , _._
2 U$
(65)
where equality (I) holds by (56). and equality (2) follows from Lemma have
When T 2, we
T-1
E
exp
Σ
&T
TRKTTR+ kT (R+ B Pet1B)aKf2t 20zor gt KT (RKK B (P
2
1=T-2
ofo=² 22
(R + BT B)+) M/
(det(In - -ー}ー-) 7 (det(Im - -PP4-1))
(2
NT 2---2 (K (R+ B Pr- + (A+ BK 2) (A 2
x E
exp
2
2 &
-1 KT
9T-2 2 (RK B (Pr (A BKT
(R + BT (PT-1 - 1)
2 KT 91
(Ie - -3
(det(Im (I - -}} -
x E
exp
(
D - -
+ 20 - トトーコ
+ ox AT - ) [
2
(5)
II
(det((n. ,U,)) - (det(Im ( -F,t)) -
T=
7 3 BKG U + a 2
x exp
(A+ -3 (A*
where equality (3) holds by applying the law of total expectation and applying (65). equality (4)
follows from (56) and equality (5) still holds by applying Lemma 19. When i, we can similarly
40

---

Published as a conference paper at ICLR 2025
derive
E
exp
Σ
kT AKt (R+ BR+BBAR af
+ 20 Si (RK) + B B P++1(A+ )z) + ozo TT. (R+ T B" Punt))tt) M
II t=1
(de [\ū!))
(eee((m--PPpp -
2 LT ( (A+ (A+ (. BK 1
x exp
2
+20 B Ú (A+ 3KL + Dh U. Bot-1)
Repeating this procedure, we can obtain
J
(xt)
1
log II
(det(In (det(Ln-7Ut)) )t())) (det(Im- -)Et))
7
1=1
1 E
[ [ (AKAT (R+ (R+BB B.B)AKK (( BKB) 28 KT 2 "
log
exp
7
+ 200
(RK + BT BTi + Ü BKG) - oxo 90 (R- BT TT ( +3)))188 2/ H
2
1 log II (del(In - )U 3 (det(Im )(t))
7
+
1
log
exp
( (20 D&at + 20 &T B + ox 36 kT ro:0)) 2
1 -1, 11
T-1
(8)
1
Σ
llog det (UA!) +
let (Im - 7111
27
1=1
Djrg
1
log det (
+ #22 van KT ENT - -1 FB
10
2
24
(7)
1
T-1
1
log det (In - PPt)
1 T-1
log det (Im - 7U,) +
1 T Up N
2 2
24
2-
where equality (6) holds by directly calculating the conditional expectation of quadratic function of of in the second term of the previous equality and equality (7) follows from the definition of U in
56
B.4 PROOF OF THEOREM 2
Now, derive the regret upper bound for Algorithm 2. Similar to Appendix(A.4 we derive the bounds for the equations (56). We recursively define the following constants similarly as 33 in
Appendix A.4 For any t 0,
-
ar 2
8T = 0,
0, 2 (1012 CT 2(T-6-1)
+
12
a14
8, = 12 + 12i 3.41,
41

---

Published as a conference paper at ICLR 2025
where V and L are defined in 13 0, ,T 1,
To derive the regret bounds, we assume that for any
(66)
2a, 12 + 23.- of + of
We are now ready to derive the bounds for D. Ex Ft, U Üp recursively from step T - 1 to step 0 conditional on event G in (39 At step T 1,
| |
AKT R B P,BAKKT
- |R B T BI |
(67)
2 2
= aT 1OT-IV2E
V2 5 8T-105
where inequality (1) holds by the definition I' in and Lemma 18 Similarly,
|| | = ( + BT Pr BK BK
5 oa R + KT-I)ll
+ B || (I1AII + |B|| || + |B| [[K--ll)
(68)
(2)
S ofVc + +f)+ + o2 ozF + TVG))
To +ox ox (f + VEE
- 3o + 20, V
where inequality (2) holds by the definition of I 13 and Lemma 18
We also have
F || = oR B B) S
2
oz
(69)
Substitute 67
668
and 69 into U. - we derive that
144
||
|| + 7 F. (mm - - 1
F
< || + | - (I 7 E3 1ーー1
< || + , - -) 11 ||
< 2 +
(30+I" +
20x 2o
1
1 1 21 37
= 2 + (90 + uot
120
(70)
1 3
(4)
I 2 + 18 + +(E))
(5)
$ 3 2 + 50 + olE))
ar-111 22 + 5 3 + 55 of o(EE)
where inequality (3) follows by substituting 67
68 and 69 into 70 and the fact that for any
matrix M E R.x* if |M < 1, then [[
[ai inqquality (4) holds by the assumption in 66 i.e. - 2 3 7o 2 1- foR 2 2. and inequality (5) still holds by assumption 166. i.e. 18
180 क
< 5 Note that conditional on event Gk. & is of order L V
so o and of share the same order conditional on event Gh. Then, we can obtain
(6)
| il
(7) $ 22
| = 11
(71)
|$_1
42

---

Published as a conference paper at ICLR 2025
where inequality (6) still holds by the fact that for any matrix M E Raxn if ||M|]| < 1, then
[I - -M) 11 S M-MMi and inequality (7) holds by the assumption in 66), i.c. 1 ->|10> 2
1 2 = 2
It follows from 70 that
[ - 2a V + 10f 3r- + +10 oî + o(e)).
With the bounds in the (T' - -) step, we can recursively derive the bounds in the (T - 2) step. At step T 2, by the similar arguments in step T 1, we can obtain
D 221
AK T-2 2 (R+ + B (R+BBPp-11) AK 2 2
(A BK 2) ŪT-1 (A - BK T- 2)
R+ B Pr-iBB ||AK/=21 2l + || BAK + BKT 2| 11?
<
(8)
S 2 (10)² (Ta) 2 V2
( F4 + 122 (10V2 2 (9() (ITUVe + 100
+3
+ o(
< (I0V² V2 + 12f 22 + +5 + +
= ar--2 22 + 5 31-20 + o(
where inequality (8) holds by Lemma 18 (71) and the fact that Ex 2t |
S K Xx= 1|
Similar to (68) we have
E 21 = 0h
[RK]- 2- 2 + T (Pr-1+ + ūb .) (A + BK
5.
RK 2- + BB Pr- (A + BK 7-2) 2) + +
B U
(A- - BK (++
|RAK] 1-2 + RKT || + ox B|| |
||A [L+BAK + BKT
| || || BAK BKT-2
+ +
TnT ((1022 DEs + +T) + Fox (2 + i'r (10D VeR)
+ to,f 12 + 100ffT> (2î² +r (OOV2 cf*) VEs)
=ox (f (10)2 + F3 (1O)2 Vek + ox (T2e + 2F + ol(2)
s 200 13 (10V² VEN + o
σx + o((2))
where inequality (9) follows from Lemma 18 and 77). Similar to 66 we have
|لحما| - | (R+ (R+BTT BT (Pr-I+0f-1) B) < 27 of o(e2)
Similar to 70). we have
||
< |D + + - - -1 11 2
$ 2 (10x22T*) 2 V2 + 6 (イ + 100 o?) + 1870 oz + +((2)
(72)
(10) 2 (10V2 CTM)
D2e + 6 (4 2 + 100 10f of. + of + =((E))
= 1222 + 5 3- + 5ी of + o(E)),
where inequality (10) follows from the assumption (66 and the similar arguments in 70 Then, by and assumption (6), we can get
レ 2 < 2oT 22T-22V2 + 100 3r + 10 is o% + +
43

---

Published as a conference paper at ICLR 2025
Repeat this procedure from step T - 1 step 0, get the following recursive inequalities. For any = 0, T 2,
| 5 - + +5 10
|| s 2
|0 S s + 51 BT 3--10 + 51 o o(()),
55
(73)
| 2 5T 3,0 +
|+]| 2 +o(e))
| S 2 + 51 3,0 + 5f + ole))
Substituting 73 into 57 in Lemma 7 we have
Joth (x))
(2
T-1
T-1
1
Σ
log det (0,,
log det (Im FF,t) + 20
TT Up T
24
2%
E=1
t=
1
Σ log (1 1 x||1%//1)>
1
log (1 - | +
1
|
| 2
27
24
t=0
(12)
log [ 7 (a. 51 3,o 5I
+ σी of + o(E
27
T-1
Σ m log
1 1 (2 + o( + V2 + zooR + +5f + o( ||
27
(13)
11
T-1
a..12 + 55 B1o + 5/ of + o(2))
+
m
T-1
Σ
2 of + o(
2
2
E=1
1=
1
+
2
12
a0
22
c
5 i + 5T + o(ei) ||00||
(74)
where inequality (11) holds because
In - -U = (1 - || (I) In - (1 (1- (arDee 55 3,0 + 51 + +((E)) In > 0,
and
In TF (1-7 || | 1) 4m (1 (1-7 2π
(2 o% + o((2)) Im ~
inequality (12) follows from the inequalities in (73) inequality (13) holds by the fact that log(1 + x) < x for any æ > -1.
Then, substituting the high probability bounds derived in Appendix B.I into we can further bound JJ (zt) - (=g). According to Proposition conditional on event G defined in 39
when kT 2 200 (3(n + m) + log (2)),, with probability at least N-I we have
| - 0012 < Ex =
CN
(75)
VI
where
4TN2
)
160n CN = cT
4nn.V
?N log
80X(n + m)²F2 (76)
log
+ (n + m) log 1
+
8
A
cT
200 ()( (N)
and c, č are defined in (44 and 53). Denote i
When à > k the
T
estimation emror bounds are given by 75
44

---

Published as a conference paper at ICLR 2025
By similar mathematical induction discussed in Section A.4 and page 27 in Basei et al. (022),
prove that the event 9 { 110 Al1 =, vk 2, N) U {0r =] holds with proba- bility at least Σ N-1 =1 8, i.e. P 9
6, where is defined in (37
Finally, conditional on the event G. we can derive an upper bound for Regret(N) Note that
Regret
Σ ( (xt) (xt) (r
Σ
(Jm (xt) J
(((x))
(77)
k=
where h 200 000 (3)m+++++) 42
We bound the terms in (7)) separately, We first bound the
regret incurred up to the k-th episode. We have
))
(20) (x
(a
log E exp
Σ t=
(1 11 +
u 12 + | 12
7
1=
(78)
It follows from 51 in Lemma 16 that
na (x)) - J' (xtt)
Tk
TN
+ 72T (T(1 + (T(+Cx)) 2T
(NN (n² + + max 11)521100 log
ölog
2
5
8
We next bound the regret in the remaining episodes follows:
N
Jnn (o)) - J (a
k=k+1
22 x 5 Boo of + =((2))
m Σ
2T
o(c))
2
k=b+1
1=0
2 + 51 B0o + -5 of + ol(2)) ||
a4 V2
5I
3:
5
2
Σ
+
olet)
+
+ ol
Vk
Vk
Vk
2
Vk
k=b+1
t=
CN
5T
30
5
+
+ +((())
||
Vk
Vk
Vi
C2 5
3
+ 5か
+ 2
(anD2ON +
+5 + 5ï
| vN o (VN).
(79)
74). the second inequality follows from 75) and Cy given in (76). On combining 778) with 79 we can obtain
where the first inequality follows from
Regret (N) s
(a.ON + 3.) VN,
where Č = Polynomial n, m. ē, V. T, (x) (f(1+Cx)) 2T
C DEPENDENCY OF THE REGRET BOUNDS ON OTHER PARAMETERS
In this section, we provide some further discussions on the dependency of the regret bounds on other problem parameters, including the horizon length T, and the risk parameter y of the LEQR
45

---

Published as a conference paper at ICLR 2025
model. Because the coefficient terms of regret bounds in Theorem Theorem share the similar recursive structure, we focus on the regret bound in Theorem [ and the regret bound in Theorem 2 can be analysed similarly. Spelling out the explicit dependency is generally difficult, due to the implicit dependency of I and constant C the model parameters. Hence, in the following focus our discussion on the term Σ & in view of the bound (22
Since {11) 1 is defined in recursive manner, one can directly verify that
2 (1ovv 2(T-1)
T
th S 2T (10V² 2(T-1)
(80)
The formula (80) implies that the term E/= 1/2 has exponential dependence the horizon length
T. When >F > 0 is small, according to Taylor's Theorem, we have
1
7f + (1T) se exp (1I)
(81)
7
Using the formula of C in [3) and plugging 81) into (80) find that the dependence of the term TT- V on y is on the order of exp (T- This also suggests that the regret bound in | has exponential dependence on 7 (ignoring the possible dependency of the constants and I' on these parameters).
Theorem
Note that [asei et al. (2022) proved a regret bound that is logarithmic in the number of episodes N for continuous-time risk neutral LQR problem, also in the finite-horizon episodic setting. They also mentioned (see Remark 2.2 in their paper) that the regret bound of their algorithm in general depends exponentially on the time horizon T. So our previous discussion consistent with their findings. Note that they did not make explicit of the dependency of their regret bound on the horizon length
We also compare results with Fei & Xu (2022). which proved gap-dependent logarithmic regret bounds for tabular MDPs under the entropic risk criteria. In particular, they showed their algorithms
achieve the regret of (exp( ((#) poly H, S, A) -log (MSAK) with probability least 1 6, 13 where poly(-) represents the polynomial function, is the length of the episode, the state space, A is the size of the action space, 3 is the risk coefficient and Amia is the minimum value of the sub-optimality gap of the value functions. Their regret bound also has exponential dependency on the risk coefficient and the length of the episode H, which is similar our regret bound. While there are some similarities, is also important to emphasize we consider LFQR which has continuous state and action spaces, which are different from tabular MDPs with finite state and action spaces.
the size of
D SIMULATION RESULTS IN SYSTEM 2 AND SYSTEM 3 IN SECTION 5
In this section, we present the simulation results of Algorithms and for System 2 and System that are defined in Section 5
D.1 SYSTEM 2
Figures 2a 2c show the average regret of Algorithm in System 2 using 150 independent runs and Figures 2d show the average regret of Algorithm in the same system. The two blue dotted lines in Figures 2a and 2d represent the 95% confidence interval of the regret when = 0.1 and = In Figures 2b and 2el we set the true risk aversion value 7 = 0.1 and plot the regret of our algorithms with the true risk aversion value and the regret of the algorithms with misspecified risk aversion values. The results show that applying the algorithms with a wrong risk aversion value, risk averse agent can lead to greater regret. In Figures 2c| and 21 we set ? = 0.001 and study the dependence of the regret on the time horizon T. As expected, longer time horizon implies greater regret.
e.g., applying the algorithm suitable for risk- learning agents
46

---

Published as a conference paper at ICLR 2025
5000
7000
3502
3000
1000
1502
1000
3000
Algorithm
(a) Regret performance (Algorithm) System 2)
(b) Effect risk parameter (Algorithm) System
250
150
9000
0002
300
Algorithm
1.5
2.5
(c) Rffect of the time horizon (Algorithm) System 2)
(d) Regret performance (Algorithm System 2)
600
500
000
Regrot
600
000
200
0.2
0.1
(St Seutrrr
0.5
1.5
0.5
1.5
2.5
-135
(e) Effect of the risk parameter (Algorithm) 2 System 2) (I) Effect of the time horizon (Algorithm) System
Figure 2: Simulation results System
47

---

Published as a conference paper at ICLR 2025
D.2 SYSTEM 3
Figures 3a 3c
show the average regret of Algorithm 1 in System using 150 independent runs and
Figures 3f
show the average regret of Algorithm 2 in the same system. The two blue dotted lines
in Figures 3a and 3d depict the 95% confidence interval of the regret when = 0.1 and T = 3. Setting the risk aversion value 7 0.1, Figures BaauuessBbandee Be the regret of the two algorithms with the true risk aversion value and the misspecified risk aversion values, which illustrates that applying the algorithms with an incorrect risk aversion value can cause poor performance of the algorithms. Setting 7 0.005, Figures 3c and 31 illustrates the dependence of the regret on the time horizon T. Similar to the results in the previous two systems, the regret of the algorithms can increase when the time horizon is longer.
66:0
Regret
3300
2000
2000
1.00
0.05 nectettr
Algorithm
(a) Regret performance (Algorithm System 3)
(b) Effect of the risk parameter (Algorithm) System 3)
450
3900
350
220
4000
Algor pprithm 2
0.5
0.5
35
(c) Effect of the time horizon (Algorithm) System 3)
(d) Regret performance (Algorithm System 3)
600
600
540
Rogno
200
200
200
100
0.1
nGk noutrol
A20
(c) Effect of the risk parameter (Algorithm) 2 System 3) (f) Effect of the time horizon (Algorithm System
Figure 3: Simulation results in System
48


Reviews:
[{"review_id": "hJHBpMuQTA", "reviewer": "Reviewer_pfYi", "summary": "This paper considers the risk-sensitive LQR problem with unknown system matrices. The authors consider the standard LEQR formulation to capture the risk-aware scenario in the control problem and study the episodic problem setting where the system needs to be reset to the initial condition at the end of each episode. The authors propose online learning algorithms to solve the problem and show that the regret of the algorithm is bounded as \\sqrt{N}, where N is the number of episodes in the problem. Under some additional assumption, the authors show that the regret bound becomes \\logN.", "questions": "Please refer to Weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThis paper initiate the consideration of risk-sensitive formulation of LQR in an online episodic setting.\n2.\tThe paper rigorously characterize the regret bounds of the proposed algorithms.", "weaknesses": "1. Although the authors mentioned a previous work Basei et al. 2022 that considers an episodic control problem, it would be good to further explain why it is important/of practical interest to consider the episodic setting in the control problem. In addition, it would be good to discuss what the major challenge is if we move to the non-episodic setting which is the most standard setting in control problems (i.e., the system involves continuously and does not reset).\n2. It would be good to explain more how the LEQR formulation captures the risk-aware scenario in Section 2.1. The authors also mention that their analysis extends to \\gamma<0. What does \\gamma<0 stand for in the risk-aware scenario? In general, it would be good to provide an intuitive explanation of how different values of γ (positive, negative, or zero) correspond to different risk attitudes. This would help readers better understand the practical implications of the LEQR formulation.\n3. The authors should justify their choice to use only data from epoch l-1 for estimation in Algorithm 1, and discuss whether using data from multiple previous epochs could improve accuracy. Additionally, they should clarify whether the i.i.d. assumption on initial states is necessary for their results to hold.\n4. The optimal controller based on the initial estimate \\theta^1 needs to satisfy Assumption~1 as well in Theorem 1. Could you justify this assumption on \\theta^1, i.e., how do you choose \\theta^1 so that the assumption is satisfied? \n5. Regarding the regret bounds provided in Theorems~1 and 2, they depend exponentially on the horizon length T for each episode. However, in episodic MDP problems, the regret bound depends on T only polynomially (e.g., https://proceedings.mlr.press/v70/azar17a/azar17a.pdf). Could the authors comment on this issue:  whether this is fundamental to the risk-sensitive setting or if it's an artifact of the regret analysis? Moreover, would it be possible to improve this dependence to polynomial in T?\n6. Could you explain why the least squares approach in Algoirthm~2 needs a regularization term?\n7. Please explicitly specify how the initial estimate \\theta^1 is chosen in Algorithm~2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "", "extra_scores": {}}, {"review_id": "xan4Iloi4J", "reviewer": "Reviewer_Z5vG", "summary": "This paper studies the online adaptive control of risk-sensitive Linear Quadratic Regulator (LQR) problem in a finite-horizon episodic setting, which is referred to as the Linear Exponential-of-Quadratic Regulator (LEQR) problem. The goal is to design the online algorithm that selects control that minimizes the total regret, i.e., the difference between the sum of minimum exponential risk-sensitive cost (defined in Eq. 2) and the algorithm's cost in each episode.\n\nThe authors introduce two algorithms: a least-squares greedy algorithm (Algorithm 1) that achieves $\\tilde{O}(\\log N)$ regret under identifiability condition (Assumption 1) and a second algorithm (Algorithm 2: Least-Squares-Based Algorithm with Exploration Noise) that incorporates exploration noise to achieve $\\tilde{O}(\\sqrt{N​})$ regret without the identifiability assumption. Finally, the authors have shown the different performance aspects of the proposed algorithms on two synthetic LEQR systems.", "questions": "Please address the weaknesses of the paper. I have a few more questions/comments:\n1. Instead of using exponential noise, can a UCB (upper confidence bound)-based exploration strategy in Algorithm 2?\n\n2. How to extend these results for other risk measures, e.g., coherent risk measures (VaR, CVaR, EVaR, etc.) as studies in the following paper:\n\t1. Lam et al., [Risk-Aware Reinforcement Learning with Coherent Risk Measures and Non-linear Function Approximation](https://openreview.net/pdf?id=-RwZOVybbj)\n\n3. What is the overall dependence of regret bounds given in Theorem 1 and 2 on horizon length ($T$) and risk-sensitivity parameter ($\\gamma$)?\n\n\n**Minor comment:**\n\nAdding the layman's explanation and consequences of Assumption 1 will help readers identify when this assumption can hold in practice. Also, details (in the appendix and refer to the main paper) can added on how the standard Riccati equations are modified to incorporate exponential risk-sensitive costs.\n\nI am open to changing my score based on the authors' responses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**The following are the strengths of the paper:**\n1. This paper is the first to provide regret bounds for the episodic finite-horizon LEQR problem, which has applications in risk-sensitive control problems in areas like finance and healthcare.\n\n2. The authors proposed two algorithms with sub-linear regret bounds guarantees. The regret bounds are derived using perturbation analysis of modified Riccati equations, which incorporate exponential risk-sensitive cost (defined in Eq. 2).\n\n3. Finally, the authors have demonstrated the different performance aspects (sub-linear regret and effect of risk parameter and horizon on regret) of the proposed algorithms on two synthetic LEQR systems.", "weaknesses": "**The following are the weaknesses of the paper:**\n1. Since verifying the identifiability assumption (Assumption 1) for a given problem may not be possible, the first algorithm may not be useful in practice. \n\n2. Both proposed algorithms are restricted to fixed finite-horizon settings and linear dynamics, which limits their real-world application, where horizon length can vary across episodes and problems with non-linear dynamics.\n\n3. The following parts of the paper are not clear enough:\n    - Why are the $N$ episodes in Algorithm 1 divided into epochs of increasing lengths to estimate the system matrices?\n    - Why does the paper only consider the exponential risk-sensitive cost? Are there any real-world motivating examples for this choice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "", "extra_scores": {}}, {"review_id": "aX3PEDx5GF", "reviewer": "Reviewer_y14b", "summary": "The paper studies an online linear quadratic regulator (LQR) problem with risk-sensitive cost functions. In particular, when the environment can provide enough exploration noise, a least-square model fitting algorithm is provided and it achieves log N regret. When the environment is not \"noisy\" enough, the authors present a gaussian exploration method that achieves square root N regret. Numerical experiments are provided to validate the proposed algorithms.", "questions": "*1.* Do the two theorems hold when gamma goes to 0, i.e., the limit is right-continuous in gamma? \n\n*2.* Typo: line 218-219, \"We\" play.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow. All the assumptions are well-motivated and standard in the literature. The proposed algorithms are simple and can be easily implemented by practitioners. \n\n----", "weaknesses": "*1.* I think the authors should provide an explicit dependence of gamma in the two theorems, i.e., the big O should contain gamma orders, as gamma is the key in the studied risk-sensitive LQR problems. With gamma dependence in the results, the authors could compare the regret order with risk-neural MDP/LQR problems. Discussions/guidance on gamma selections could be included.\n\n*2.* Literature/discussions on risk-averse RL/LQR problems are limited, in particular, the choice of risk-averse metrics and the reason for studying the LEQR problem.\n\n*3.* The authors could provide a more interesting real-world control problem in the simulation. \n\n----", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "", "extra_scores": {}}, {"review_id": "0JNM3vdoGz", "reviewer": "Reviewer_VSSt", "summary": "This paper proposes a least-squares greedy algorithm for the online adaptive control of the risk-sensitive linear quadratic regulator (LQR) in a finite-horizon, episodic setting, which achieves a regret bound of $O(\\log n)$ under identifiability assumption. It also proposes adding exploration noise to the least-squares algorithm when the identifiability assumption does not hold, resulting in a modified approach with a regret bound of $O(\\sqrt{n})$.", "questions": "- As the authors noted, studying regret bounds for LEQR in the infinite-horizon average-reward (non-episodic) setting would be interesting. What challenges arise in extending the current proof methods to this setting?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors introduce two algorithms based on least-squares methods tailored for LEQR. The first least-squares greedy algorithm without exploration noise achieves a logarithmic regret bound $O(\\log n)$ under an identifiability condition, and the second algorithm, designed for scenarios where the identifiability assumption does not hold, achieves a $O(\\sqrt{n})$ regret bound.\n- This work provides the first regret bounds for finite-horizon episodic LEQR, showing the existence of logarithmic regret under identifiability assumption.\n- The theoretical analysis relies on perturbation analysis of special Riccati equations for the risk-sensitive LEQR setting, where additional matrices ($\\widetilde P$) are present in the Riccati equations due to the risk sensitivity. The authors show nontrivial analysis techniques addressing the challenges in the analysis.\n- The authors also introduce novel analysis on risk-sensitive loss.", "weaknesses": "- It would be beneficial to establish matching lower bounds for both algorithms to provide a more comprehensive understanding of their optimality.\n- Typo/Inconsistency of the plot descriptions: Regret performance of Algorithm 1 (System 1) vs Effect of the risk parameter (Algorithm 1 System 1)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)