Provable Sim-to-real Transfer in Continuous Domain with Partial Observations
Authors: Jiachen Hu
Han Zhong
Chi Jin
Liwei Wang
Venue: ICLR 2023 poster (2023)
Keywords: sim-to-real
RL theory
partial observations

Abstract:     Sim-to-real transfer, which trains RL agents in the simulated environments and then deploys them in the real world, has been widely used to overcome the limitations of gathering samples in the real world. Despite the empirical success of the sim-to-real transfer, its theoretical foundation is much less understood. In this paper, we study the sim-to-real transfer in continuous domain with partial observations, where the simulated environments and real-world environments are modeled by linear quadratic Gaussian (LQG) systems. We show that a popular robust adversarial training algorithm is capable of learning a policy from the simulated environment that is competitive to the optimal policy in the real-world environment. To achieve our results, we design a new algorithm for infinite-horizon average-cost LQGs and establish a regret bound that depends on the intrinsic complexity of the model class. Our algorithm crucially relies on a novel history clipping scheme, which might be of independent interest.

Published as a conference paper at ICLR 2023
PROVABLE SIM-TO-REAL TRANSFER IN CONTINUOUS DOMAIN WITH PARTIAL OBSERVATIONS
Jiachen Hu*
Han Zhong'
School of Computer Science, Peking University Ni ckHkpku edu.cn
Center for Data Science, Peking University
hanzhong@atu. . edu.
Chi Jin
Department of Electrical and Computer Engineering, Princeton University chi phijjppinneton.com edu
Liwei Wang
National Key Laboratory of General Artificial Intelligence, School Intelligence Science and Technology, Peking University Center for Data Science, Peking University, Beijing Institute of Big Data Research wanglw@ eis. pku. edu. on
ABSTRACT
Sim-to-real transfer, which trains RL agents in the simulated environments and then deploys them in the real world, has been widely used to overcome the lim- itations of gathering samples in the real world. Despite the empirical success of the sim-to-real transfer, its theoretical foundation is much less understood. In this paper, we study the sim-to-real transfer continuous domain with partial observations, where the simulated environments and real-world environments are modeled by linear quadratic Gaussian (LQG) systems. We show that a popular robust adversarial training algorithm is capable of learning a policy from the sim- ulated environment that competitive to the optimal policy the real-world en- vironment. To achieve our results, we design new algorithm for horrinn average-cost LQGs and establish regret bound that depends on the intrinsic com- plexity of the model class. Our algorithm crucially relies novel history clip- ping scheme, which might be of independent interest.
INTRODUCTION
Deep reinforcement learning has achieved great empirical successes in various real-world decision- making problems, such as Atari games (Mnih et al.) 2015). Go (Sileer et al.] 2016 2017). and robotics control (Kober et al., 2013). In addition to the power of large-scale deep neural networks, these successes also critically rely on the availability of a tremendous amount of data for training. For these applications, lions to billions of samples in a short time. However, in many other applications such as auto-driving (Pan al. 2017) and healthcare (Wang al., 2018), interacting with the environment repeatedly and collecting a large amount of data is costly and risky or even impossible.
have access to efficient simulators, which capable of generating mil-
promising approach solving the problem of data scarcity is sim-to-real transfer (Kober al. 2013 Sadeghi & Levine 2016); Tan et al.) 20188] Zhao et al.) (020). which uses simulated environ- ments generate simulated data. These simulated data is used train the RL agents, which will be then deployed in the real world. These trained RL agents, however, may perform poorly in real- world environments owing to the mismatch between simulation and real-world environments. This mismatch is commonly referred to as the sim-to-real gap.
To close such gap, researchers propose various methods including (1) system identification Kristinsson & Dumont 1992), which builds precise mathematical model for the real-world envi-
"Equal Contribution.

---

Published as a conference paper at ICLR 2023
ronment; (2) domain randomization (Tobin et al. 2017), which randomizes the simulation and trains an agent that performs well on those randomized simulated environments; and (3) robust adversarial training (Pinto et al.] 2017b), which finds policy that performs well in bad or even adversarial environment. Despite their empirical successes, these methods have very limited theoretical guaran- tees. A recent work [Chnn al. (202T) studies the domain randomization algorithms for sim-to-real transfer, but this work has two limitations: First, their results (Chen et al.) [021] Theorem 4) heav- ily rely on domain randomization being able sample simulated models that are very close to the real-world model with at least constant probability, which is hardly the case for applications with continuous domain. Second, their theoretical framework do not capture the problem with partial observations. However, sim-to-real transfer in continuous domain with partial observations is very common. Take dexterous in-hand manipulation (OpenAl et al., 2018) as an example, the domain consists of angels of different joints which is continuous and the training on the simulator has partial information due to the observation noises (for example, the image generated by the agent's 'een's camera can be affected by the surrounding environment). Therefore, we ask the following question:
Can we provide rigorous theoretical analysis for the sim-to-real gap in continuous domain with partial observations?
This paper answers the above question affirmatively. We study the sim-to-real gap of the robust adversarial training algorithm and address the aforementioned limitations. To summarize, our con- tributions are three-fold:
We use finite horizon LQGs to model the simulated and real-world environments, and also formalize the problem of sim-to-real transfer in continuous domain with partial observa- tions. Under this framework, the learner is assumed to have access to simulator class 8, each of which represents a simulator with certain control parameters. We analyze the sim-to-real gap (Eqn. (6)) of the robust adversarial training algorithm trained in simulator class &. Our results show that the sim-to-real gap of the robust adversarial training algo- rithm is Ö(vōg H.) Here H is the horizon length of the real task, and ōg denotes some intrinsic complexity of the simulator class &. This result shows that the sim-to-real gap is small for simple simulator classes and short tasks, while it gets larger for complicated classes and long tasks. By establishing a nearly matching lower bound, we further show this sim-to-real gap enjoys a near-optimal rate in terms of H.
To bound the sim-to-real gap of the robust adversarial training algorithm, we develop a new reduction scheme that reduces the problem of bounding the sim-to-real gap to designing sample-efficient algorithm in infinite-horizon average-cost LQGs. Our reduction scheme for LQGs is different from the one in Chen et al. (02T) for MDPs because the value function (or more precisely, the optimal bias function) is not naturally bounded in a LQG instance, which requires more sophisticated analysis.
To prove our results, we propose a new algorithm, namely LQG-VTR, for infinite-horizon average-cost LQGs with convex cost functions. Theoretically, we establish regret bound O for LQG-VTR, where T is the number of steps. To the best of our knowl- edge, this is the first "instance-dependen"" result that depends on the intrinsic complexity of the LQG model class with convex cost functions, whereas previous works only provide worst-case regret bounds depending on the ambient dimensions (i.c., dimensions of states, controls, and observations).
At the core of LQG-VTR is history clipping scheme, which uses a clipped history instead of the full history estimate the model and make predictions. This history clipping scheme helps us reduce the intrinsic complexity óg exponentially from O(T) to O(poly(log T)) (cf. Appendix G)
Our theoretical results also have two implications: First, the robust training algorithm is provably efficient (cf. Theorem [ in continuous domain with partial observations. One can turn to the robust adversarial training algorithm if the domain randomization has poor performance (ef. Ap- pendix[A.4] Second, for stable LQG systems, only a short clipped history needs to be remembered to make accurate predictions in the infinite-horizon average-cost setting.
2

---

Published as a conference paper at ICLR 2023
1.1 RELATED WORK
Sim-to-real Transfer Sim-to-real transfer, using simulated environments to train a policy that can be transferred to the real world, is widely used in many realistic scenarios such robotics (e.g.. Rusu et al. [0177] [Tan et al., 2018: Peng et al., 2018: OpenAl et al. 2018 Zhao et al. 2020). To close the sim-to-real gap, various empirical algorithms are proposed, including robust adversarial training (Pinto et al. 2017b), domain adaptation (Tzeng et al. (015), inverse dynamics methods (Christiano al. 2016), progressive networks (Rusu al. 2017), and domain randomization (Tobin et al.)
2017 In this work, we focus on the robust adversarial training algorithm. [Tian (2018); Feng et al. (2019; Zhong et al. (2019) studies the sim-to-real transfer theoretically, but they require real-world samples to improve the policy during the training phase, while our work does not use any real-world samples. Our work is mostly related to Chen et al. (202I), which studies the benefits of domain randomization for sim-to-real transfer. As mentioned before, however, Chen et al. (2021) cannot tackle the sim-to co-tto-raal transfer in continuous domain with partial observations, which is the focus of work.
Robust Adversarial Training Algorithm There are many empirical works studying robust ad- versarial training algorithms, Pinto al. (2017b) proposes the robust adversarial training algorithm, which trains a policy in the adversarial environment. Then Pinto et al. (2017a); Mandlekar et al.) (2077 Pattanaik et al. (2017); Dennis et al. (2020) show that the robust policy obtained by the ro- bust adversarial training method can achieve good performance in the real world. But these works lack theoretical guarantees. Broadly speaking, the robust adversarial training method is also related to the min-max optimal control (Ma et al.) 1999 Ma & Braatz 2001) and robust RL (Morimoto &
Doya
2005:
Iyengar| 22055] Xu Mannor 2010 Ho et al.
2018 Tessler et al. 2019 Mankowitz
al.
2019 Goyal & Grand- Clemmeet 2022
Cohen et al. 2019) Simchowitz & 2022) studying the infinite-horizon linear quadratic regulator (LQR), where the learner can observe the state. For the more challenging infnite-horizon LQG control, where the learner can only observe the noisy observations generated from the hidden state, Manna et al.) (2019): Simchowitz et al. (2020); Lale et al.] (2020c) 2021) propose various algorithms and establish regret bound for them. specific, Mania et al. (2019 9 Lale et al. (2020b) study the strongly conver cost setting, where it is possible to achieve Ol Oppoly llog T))
LQR and LQG There is a line of works (Mania et al.
2019
Foster 2020 Lale al. 2020a Chen & Hazan 2021 Lale al.
regret bound. Simchhowtz et al. (2000) Lale et al. (2020c) (021) and our work focus on the conver cost, where Simchowitz et al. (2020); Lale al. (2020c) establish a T2/3 worst-case regret. Lale al. 2021) derives 1/2 worst-case regret depending on the ambient dimensions, which is based on strong assumptions and complicated regret analysis. In contrast, with weaker assumptions and cleaner analysis, our results only depend on the intrinsic complexity of the model class, which might be potentially small (cf. Appendix G
2 PRELIMINARIES
2.1 FINITE-HORIZON LINEAR QUADRATIC GAUSSIAN
We consider the following finite-horizon linear quadratic Gaussian (I.QG) model:
Th+1
Ar + Bun + Wh, yh =Cr + Zh.
where 24 E R" is the hidden state at step h; up E R is the action at step h; wA (O, In) is the
process noise step h; yh e I2 is the observation at step h; and 24, ~ (O, Ip) the measurement noise at step h. Here the noises are i..d. random vectors. The initial state Ep is assumed to follow a Gaussian distribution. Moreover, we denote by = (A E Raxn, E Raxm C E RR'X)) the parameters of this LQG problem.
The learner interacts with the system as follows. At each step h, the learner observes an observation yh, chooses an action un, and suffers loss Ca. c(ys, un), ), which is defined by
c(y,, ux) yb Qun + un Run:
where Q TRPX and R Rmxm are known positive definite matrices.
3

---

Published as a conference paper at ICLR 2023
For the finite-horizon setting, the interaction ends after receiving the cost eH, where H is positive integer. Let H. = {Bo, uo," -h 44-1, 3h be the history at step h. Given policy x = ={TL {Th
H,, up h== its expected total cost is defined by
H
V (*( Ex
Σ h=0
Uh Qun + W/ Run
where the expectation taken with respect to the randomness induced by the underlying dynamics and policy The learner aims to find the optimal policy ne with minimal expected total cost, which is defined by n² arg min, (+))). For simplicity, we use the notation V*(@) V (0).
2.2 INFINITE-HORIZON LINEAR QUADRATIC GAUSSIAN
For the infinite-horizon average-cost LQG, we use the and to denote the time step and expected total cost function respectively to distinguish them from the finite-horizon setting. Similar to the finite-horizon setting. the learner aims to find policy x {Te He + us t that minimizes the expected total cost J (0), which is defined by
(*)
lim T
E
Σ 1=
Ve Qu: + un Rum
T
The optimal policy Tin is defined by Tip arg min, (=))). We also use the notation J²(@) = J (O). We measure the T-step optimality of the learner's s policy by its regret:
Regret m: T) B-
(2)
Throughout this paper, when is clear from the context, we may omit from Regret( T).
It is known that the optimal policy for this problem is a linear feedback control policy, i.e., un = -K (K) (O) where K (+) the optimal control gain matrix and ê.lr.e e the belief state at step (i.c. the estimated mean of 2z). One can use the Kalman filter (Kalman 1960) to obtain & and dynamic programming to obtain K (+) when the system θ is known. In particular, denote P(0) as the unique solution to the discrete-time algebraic Riccati equation (DARE):
P(O) = A P(O)A+ C QC A P(O) B P(O)B) P()))A
then K(O) can be obtained using P(O). We also use E(e) denote the steady-state covariance matrix of 2t. More details are deferred to Appendix A.3
The LQG instance ! can be depicted in the predictor form Kalmann 1960 Lale al. 2020b 2021
It+1 (A C(O)))a,, + Bu, + F(O),,, Vt Cr. 6t2
(3)
where F(0) AT( and e denotes zero-mean innovation process.
Bellman Equation
We define the optimal bias function θ (A, B, C) for (λrjr.e, vt) as
he (fqr.. vi) #T - C. -- @C) y. Qy:
(4)
With this notation, the Bellman optimality equation (Lale et al. 2020c Lemma 4.3) is given by (+) + hy (ftr.e. vt) min {c(yr, u) + Ee... hhe (1++)))+1...
(5)
where the equality is achieved by the optimal control of e.
Notation We use 0(-) notation highlight the dependency on H, H,,, m. p. yet omit the polyno- mial dependency on some complicated instance-dependent constants (Ö(-) further omits polylog- arithmic factors). For function f X - R. its -oom || is defined by supzex f(x). We
also define | sup ll Let p(-) denote the spectral radius, i.c., the maximum absolute value of eigenvalues.

---

Published as a conference paper at ICLR 2023
2.3 SIM-TO-REAL TRANSFER
The principal framework of sim-to-real transfer works as follows: the learner trains policy in the simulators of the environment, and then applies the obtained policy the real world. We follow Chen et al.] (2021) to present a formulation of the sim-to-real transfer. The simulators are modeled as a set finite-horizon LQGs with control parameters (e-g., physical parameters, control delays, etc.), where different parameters correspond to different dynamics. We denote this simulator class by & To make the problem tractable, we also impose the realizability assumption: the real-world environment O & is contained in the simulator set.
Now we describe the sim-to-real transfer paradigm formally. In simulation phase, the learner given the set 6, each of which is parameterized simulator (LQG system). During the simulation phase, the learner can interact with each simulator for arbitrary times. However, the learner does NOT know which one represents the real-world environment, which may cause the learned policy to perform poorly the real world. This challenge commonly referred to as the sim-to-real gap. Mathematically, assuming the learned policy in the simulation phase is л (66'), its sim-to-real gap is defined by
Gap(#(6)) = (*()) -
which is the difference between the cost of simulation policy (66) on the real-world model and the optimal cost in the real world.
2.4 ROBUST ADVERSARIAL TRAINING ALGORITHM
With our sim-to-rea transfer framework defined above. we now formally define the robust adversar- ial training algorithm used the simulator training procedure.
Definition 1 (Robust Adversarial Training Oracle). The robust adversarial training oracle returns a (history-dependent)) policy TRT such that
TRT = arg min max (
BEA
where V* is the optimal cost, and V is the cost of both on the LQG model e. Note that the real world model O* is unknown to the robust adversarial training oracle.
This robust adversarial training oracle aims to find policy that minimizes the worst case value gap.
This oracle can be achieved by many algorithms in min-max optimal control (Ma et al.) 1999 Ma &
Braatz 2001) and robust RL (Morimoto & Doya 2005 Iyengar [0055] Xu & Mannor [2100] Pinto
et al. 2017a Ho et al. Tessler et al. 2019 Mankowitz et al. 2019
Kuang et al. 2022
Goyal & Grand-Clement 2022
MAIN RESULTS
Before presenting our results, we introduce several standard notations and assumptions for LQGs.
Assumption 1. The real world LQG system O* (A*BB*
CC*) is open-loop stable, i.e., p(A*) <
1. Assume
[(At) < 400. P(A+)
((A))
def sup 720
We also assume that (A*, B²) and (A*, F((*)) controllable, (A*, C++) is observable.
For completeness, we provide the definitions of controllable, observable, and stable systems in Ap- pendix A.2 Assumption is common in previous works studying the regret minimization or system
identification of LQG (Lale et al. 2021 2020b; Oymak & Ozay 2019). The bounded (<AA*) condi- tion is a mild condition as noted in Lale et al. (2020c): Oymak & Ozay (2019): Mania et al. (2019), which is satisfied when A is diagonalizable. We emphasize that the (A" F(O*) coontrollable
sumption here only helps us simplify the analysis (can be removed by more sophisticated analysis). It is not necessary condition for results.
5

---

Published as a conference paper at ICLR 2023
In the framework of sim-to-real transfer, have access to a parameterized simulator class 6. It is natural to assume has bounded norm. The stability of the systems relies on the contractible property of the close-loop control matrix A BK (Lale al. 2020c 2021 Thus, make the
following assumption, which is also used in Lale et al. 2020c 2021).
have contractible close-lopp control matri- ces: [I<()))ll I NK and ||A'' - B'K( S n for fixed constant N& > 0, 0
Assumption 2. The simulators Ø B', CC')
"i 1. We
assume there exists constant Nş such that for any e E &, ||A'||2 12 C 112 S Ns.
As we study the partially observable setting with nninite-horizon average cost, we also require the belief states of any LQG model in & to be stable and convergent (Mania et al., 2019; Lale et al., 202TI. Since the dynamics for belief states follow the predictor form in we assume matrix A F(e)C is stable as follows.
Assumption 3. Assume there exists constant (K2. 72) such that for any e' = (A', C',""" E 8, the matrix A' F(O")C" (22,72))-stron -at-otrog stable. Here - F(O')C" is (K2. -stronny stable means [ S. K2 and there exists matrices L and G such that A' F(O')C' = GLG with K2.
||L||2 S 72. ||G||2|||=~11
We assume Zo ~ ~. 1) for simplicity. Note that the Kalman filter converges exponentially fast to its steady-state (Caines & Mayne 1970 Chan et al., 1984). we omit the error brought by Zo starting at covariance instead of the (()) (see e.g., Appendix G of Lale et al. (2021) without loss of generality.
Now are ready to state our main theorem, which establishes sharp upper bound for the sim-to- real gap of TRT-
Theorem 1. Under Assumptions and 3 the sim-to-real gap of गRT satisfies
Gap(Ter) S 2
where 0g (defined in Theorem characterizes the complexity of model class &.
Here we use Ô to highlight the dependency with respect the dimensions of the problem (i.e., m, n. p, H) and hide the uniform constants, log factors, and complicated instance-dependen con- stants. We present the high-level ideas of our proof in Section The full proof deferred to Appendix The following proposition shows that 5g has at most logarithmic dependency on H.
Proposition 1. Under Assumption by
and the intrinsic complexity 0g is always upper bounded
8g Ô (poly(m,,.p)))
The proof is deferred to Appendix policy is as large as O(H) since stable policies incur at most O(1) loss (compared with the optimal policy) at each step. Therefore, Theorem [ along with proposition [ ensures that TRT is highly non-trivial policy which only suffers O(H 1/2) loss per step. Moreover, we can show that deg will be smaller if & has more properties such as the low-rank structure. See Appendicies G.2 and G.3 for details.
G.1
Note that the sim-to-real gap of any trivial stable control
To demonstrate the optimality of the upper bound Theorem I we establish the following lower bound, which shows that the /H sim-to-real gap unavoidable. The proof is given in Appendix H
Theorem (Lower Bound). Under Assumptions 2 and 3 for any history-depender policy म,,
there exists model class & and choice of O* E 6 such that
Gap(#) 2 H)
4 ANALYSIS
We provide a sketched analysis of the sim-to-real gap of TRT in this section. In nutshell, first perform a reduction from bounding the sim-to-real gap to an infinite-horizon regret minimization problem. We further show that there exists history-dependent policy achieving low regret bound

---

Published as a conference paper at ICLR 2023
in the infinite-horizon LQG problem. This immediately implies that the sim-to-real gap of TRY will be small by reduction. Before coming to the analysis, we note first that any simulator @ E & not satisfying Assumption I cannot be the real world system. Therefore, we can prune the simulator set & to remove the models that do not satisfy Assumption
4.1 THE REDUCTION
Now we introduce the reduction technique, which connects the sim-to-real gap defined in Eqn. ( and the regret defined in Eqn. (
Lemma (Reduction). Under Assumptions 7 and the sim-to-real gap of тRT can be bounded by the H -teep regret bound of any (history-dependmm) policy defined in Eqn.
Gap(TRT) S Regret(T; H) + Dn.
where Dr, does not depend on H.
Although the idea of reduction is also used in Chen et al. (202T), our reduction here is very different from theirs. Their proof relies on the communication assumption, which ensures that the optimal bias function in infinite-horizon MDPs is uniformly bounded. In contrast, the optimal bias func- tion defined in (4) is not naturally bounded, which requires much more complicated analysis. See Appendix D for detailed proof.
By Lemma 3 it suffices to construct a history-dependen policy â that has low regret. Since we algorithm, it suffices to design efficient regret minimization algorithm for the infinite-horizn average-cost LQG systems as न.
can treat any dettedend policy
4.2 THE REGRET MINIMIZATION ALGORITHM
Motivated by the reduction the previous subsection, we construct a sample- efficient algorithm LQG-VTR (Algorithm D The key steps of LQG- VTR are summarized below.
Model Selection has been observed by many previous works (e.g., Simchowitz Foster (2020)
Lale et al. (2021] 2020c); Tsiamis et al. (2020)) that an inaccurate estimation of the system leads to the actions that cause the belief state to explode (i.e., || becomes linear or even super linear as grows). To alleviate this problem, we utilize a model selection procedure before the optimistic planning algorithm to stabilize the system. The model selection procedure rules out some unlikely systems from the simulator set, which ensures that the inaccuracies do not blow up during the exccution of LQG-VTR. To this end, we collect few samples with random actions, and use a modified system identification algorithm to estimate the system parameters (Lale et al. 2021 Oymak & Ozay 2019). After the model selection procedure, we show that with high probability the belief states and observations stay bounded throughout the remaining steps (cf. Lemma 5 in Appendix C. so LQG-VTR does not terminate at Line g
Estimate the Model with Clipped History As the simulator class & is known to the agent, the value-target model regression procedure (Ayoub et al. (020) estimate the real-world model O* at the end of each episode k. To be more concrete. suppose the agent has access to the regression dataset Z [E at the end of episode k; where E, is 1-th sample containing the belief state Expt. action uy, observation yt. the estimated bias function hi. and the regression target
(f++ 1|++1 11) Here Ô the optimistic model used in the 1-th sample. Then, inspired by the Bellman equation in (5) we can estimate the model by minimizing the following least-squares loss
0/+1 arg min
Σ (Ee... [ng ((+1))4418(411) @aje h2 (6441)4118641))
(8)
Seul E,EZ
where 1/4110+1: b'41 denotes the random belief state and observation step t 1. However, it show in Section 4.4 which leads to an O(H) intrinsic complexity (i.e., òg = O(H)). Then the sim-to-real gap of becomes O(H), which is vacuous. Fortunately,
requires the full history at step t to compute the expectation in Eqn. (8)
use a clipped history (Line 12 of Algorithm to compute approximation of the expectation. Let f u,
Tur in Theorem
[
7

---

Published as a conference paper at ICLR 2023
Algorithm LQG-VTR
1: Initialize: set model selection period length Tw by Eqn. (56)
2: set maximum state allowed M = X1 (X1 is defined in Lemma 5
3:
maximum number of episode K. by Eqn. (77
4:
set 2b by Lemma 9 8 by Eqn. 119).
( Hn + Hp)).
5:
Z Znew
initial state 2g (Q. 1). episode k 1.
Compute 1 = Model Selection(") w. 6) (Algorithm 2 θ = arg minecu. (+).
6:
7:
for step = Tw + 1.... H do
8:
if' [ > Mg then
9:
Take 4n = for the remaining steps and halt the algorithm.
10:
Compute the optimal action under system Oş: K(@x)
11:
Take action u, and observe V++1- de Let Leip min(l, t). define T² def (ye, 11-1, 1t 4 Vt- ... Us- Ua-la Ur -llii
Add sample E, def (Te, @. Ô₁, ue, & [411|1+1, M++1) the set Bnew-
[1 fa
if importance score f1EF 11/ fall Enam 2 1 and k < K. then
15:
Add the history data Znew to the set Z, and reset Znew 0. Calculate Õ using Eqn. (9)
16:
Update the confidence set Uk+1 C(ÔR+1, 2) by Eqn. 10
Compute θx+1 arg mingeu443 (O); episode counter k
Ee, l.hh (441 1441
dqj be the approximation of the expectation (see Section 4.4 for the formal definition), we use estimate @* with dataset Z:
Σ (Jo (Fele: ue, 3) - hig (1+41141113+1))
Ō = arg min
(9)
Sell
E,EZ
With this estimator, construct the following confidence set,
(0k+1: O U1
Σ E,EZ
(felenj ue, θ) fer.. (Bejes ue, 6)) S
(10)
Update with Low-switching Cost Since the regret bound of LQG-VTK has linear dependency control policies (cf. Appendix [E.5). we have to ensure the low-switching property (Auer et al. 2008 Bai et al.) 2019) of our algorithm. We follow the idea of Kong et al. (2021); Chen et al. (2021) that maintains two datasets and Znews representing current data used in model regression and
on the number of times the algorithm switches
incoming data. The importance score (Line 14 of Algorithm M measures the importance of the data in Znew with respect to the data in Z. We only synchronize the current dataset with the dataset and update the current policy when this value is greater than 1.
4.3 REGRET BOUND OF LQG-VTR
Theorem 4. Under Assumptions
a the regret (Eq. of LQG-VTR bounded by
δ (VōeH))
(11)
where the intrinsic model complexity 8g is defined as
8g dimg (F, log(N (F, (F,L
(12)
Here use function class FF capture the complexity of 8, which is defined in Section 4.4 dim 1/H) denotes the 1/11 -Eluder dimension F, (F, L/H) is the //o-vrrrinng number of F. The definitions of Eluder dimension and covering number are deferred to Appendix A.2
Under Assumptions
1 2 and
we obtain /H-regret desired because ög is most
Oppoly(m, n. p)) (cf. Appendix
Notably, if do not adopt the history clipping technique,
8

---

Published as a conference paper at ICLR 2023
5g will be linear in H. resulting in the regret bound becoming vacuous. Compared with existing works (Simchowitz et al. 2020 Lale al. 2020c; 2021). achieve / -regret bound for gen- eral model class & (depends on the intrinsic complexity of &)) with weaker assumptions and cleaner analysis. Theorem D directly implied by Theorem 4 and the reduction in 75
4.4 CONSTRUCTION OF THE FUNCTION CLASS F
In this subsection, we present the intuition and construction of F. To begin with, recall that the optimal bias function hig of the optimistic system θ
lig ( (# 1++1) = = 1, ( (p-ŌTQC) #411141,6 + Ve41 Qu++1,
where (P, C) are the parameters with respect to Ô. Given any underlying system O know the next step observation 1,+ given belief state &te, and action u is defined as
1,8 y ( u, ) 4ef CA + CBu + Cw, + CA(a, - f + #++1- Here we use y to denote the stochastic process that generates 1t+1,0 under system θ
Thus, we can define function f' be the one-step Bellman backup of the optimal bias function hig under the transition of the undertying system O:
I'e (r' 011, θ
def IF.
h ($141141,, V++1.)) 1. V++1,0 = > 3 (Fujc.e. 0).
(13)
The next step belief state L,4 11++1,6 is determined by the Kalman filter as
a 4411411,6 = (1 ( [c) (A + Bu) Ly
(14)
However, we need the full history r' to compute Etec as shown below, which is unacceptable. To mitigate this problem, compute the approximate belief state eir with clipped length-/ history
r' = [ur-1: -1---::----- 14 }e
f LC) 18, (C) Bu-1 1 + Lyf (require full history 7' to compute tt(r,))
= (A- LCA) 2 + Σ (A-1A (A-LCC)) ( (C) + Lyk-st1)
(15)
Thanks to Assumption
show that (A- I.CA)* f is small term whose l norm bounded by ( ) since [[ LC) |
Therefore, $fr. will be good approximation of f helping us control the error of clipping the history.
With the above observation, we formally define F, which is an approximation by replacing the full
history with the clipped history. Let the domain of F be X def (B7 B%) 3xx x xB x 8, where
Bd {z Rd || < w) for any (d, 2) ENN. x R. Here U, Y and X, will be specified in Lemma
We define FF formally as follows:
F (Se X
- R OE
So (r' (r. E (
Vi+1, (
(16)
Here 1.41|e41.6 is determined similarly as in Eqn. 14 where the only difference is the next observation Ut+1. replaced by vf+
CONCLUSION
In this paper, make the first attempt study the sim-to-real gap in continuous domain with partial observations. We show that the output policy the robust adversarial algorithm enjoys the near- optimal sim-to-real gap, which depends on the intrinsic complexity of the simulator class. This work opens up several directions: Can we extend our results to the non-line non-linear dynamics system? Can we design better sim-to-real algorithms beyond robust training? We leave them future investigations.

---

Published as a conference paper at ICLR 2023
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.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning, Advances neural information processing systems. 21, 2008.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with malue-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
Peter E Caines and David Q Mayne. On the discrete time matrix riccati equation of optimal control. International Journal of Control, 12(5):785-794, 1970.
Siew Chan, GC Goodwin, and Kwai Sin. Convergence properties of the riccati difference equation in optimal filteing of nonstabilizable systems. IEEE Transactions Automatic Control, 29(2): 110-118, 1984.
Xiaoyu Chen, Jiachen Hu, Chi Jin, Lihong Li, and Liwei Wang. Understanding domain randomiza- tion for sim-to -eal transfer. arXiv preprint arXiv:2110.03239. 2021.
Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference Learning Theory, pp. 1144-1143. PMLR, 2021.
Paul Christiano, Zain Shah, Igor Mordatch, Jonas Schneider, Trevor Blackwell, Joshua Tobin, Pieter Abbeel, and Wojeiech Zaremba. Transfer from simulation to real world through learning deep inverse dynamics model. arXiv preprint arXiv:1610.03518, 2016.
Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. In International Conference on Machine Learning, pp. 1029- 1038. PMLR, 2018.
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.
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. Advances neural information processing systems, 33: 130696 2020.
Fei Feng. Wotao Yin, and Lin F Yang. How does an approximate model help in reinforcement learning? arXiv preprint arXiv:/912.029000 1.009286 2019.
Vineet Goyal and Julien Grand-Clement, Robust markov decision processes: Beyond rectangularity. Mathematics of Operations Research, 2022.
Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Fast bellman updates for robust mdps. In International Conference Machine Learning, pp. 1979-1988, PMLR, 2018.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Nan Jiang. Pac reinforcement learning with an imperfect model. In Proceedings of the AAAI Con- ference Artificial Intelligence, volume 32, 2018
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 08.13406-13413 2021.
Rudolph Emil Kalman. A new approach linear filtering and prediction problems. 1960.
10

---

Published as a conference paper at ICLR 2023
Jens Kober, J Andrew Bagnell, and Jan Peters. International Journal of Robotics Research, Reinforcement learning in robotics: A survey. The 2013.
Dingwen Kong. Ruslan Salakhutdinov, Ruosong Wang. and Lin Yang. Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint urXiv:2106.07203 2021.
Kristinn Kristinsson and Guy Albert Dumont. System identification and control using genetic algo- rithms. IEEE Transactions on Systems, Man, and Cybernetics, 22(5):1033 (553::0333-0000 1046, 1992.
Yufei Kuang, Miao Lu, Jie Wang, Qi Zhou, Bin Li, and Houqiang L.i. Learning robust policy against disturbance in transition dynamics via conservvneevv policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7247-7254, 2022.
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar, Explore more and improve regret in linear quadratic regulators. arXiv preprint arXiv:2007. /22911 2020a.
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-20888. 2020b.
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Regret minimization in partially observable linear quadratic control. arXiv preprint arXiv:2002.00082, 2020c.
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Adaptive control and regret minimization in linear quadratic gaussian (lgg) setting. In 2021 American Control Conference (ACC), pp. 2517-2522. IEEE, 2021.
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Animashree Anandkumar. Reinforce- ment learning with fast stabilization in linear dynamical systems. In International Conference on Artificial Intelligence and Statistics, pp. 5354-5390. PMLR, 2022.
David I. Ma and Richard Braatz. Worst-case analysis of finite-time control policies. IEEE Trans- actions on Control Systems Technology, 95):7666-77, 2001.
David L Ma, Serena H Chung, and Richard D Braatz. Worst-case performance analysis of optimal batch control trajectories. AIChE journal, 45(7): 1469-1477,, 1999.
Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction of physically-plausible perturbations. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3932-3939. IEEE, 2017.
Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalent control of lqr is efficient. arXiv preprint arXiv:1902.0782. 2019.
Daniel J Mankowitz, Nir Levine, Rae Jeong, Yuanyuan Shi, Jackie Kay, Abbas Abdolmaleki, Jost Tobias Springenberg, Timothy Mann, Todd Hester, and Martin Riedmiller. Robust re- inforcement learning for continuous control with model misspecification. arXiv preprint NrXiv:1906.075/6 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 518(7540):59-5333 2015. 2015.
Jun Morimoto and Kenji Doya. Robust reinforcement learning. Neural computation, 17(2)3335-359 2005.
OpenAl, Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafat Józefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, Jonas Schneider, Szy- mon Sidor, Josh Tobin, Peter Welinder, Lilian Weng, and Wojciech Zaremba. Learning dexterous in-hand manipulation. CoRR, 2018. URL /ttps///ttt////aaa..ooo/////////
00177
Ian Osband and Benjamin Van Roy. Model based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
11

---

Published as a conference paper at ICLR 2023
Samet Oymak and Necmiye Ozay. Non-asymplotic identification of lti systems from single trajec- tory. In 2019 American control conference (ACC), pp.
IEEE, 2019.
Yunpeng Pan, Ching-An Cheng, Kamil Saigol, Keuntaek Lee, Xinyan Yan. Evangelos Theodorou, and Byron Boots. Agile autonomous driving using end-to-end deep imitation learning. arXiv preprint arXiv:1709.077 74, 2017.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. arXiv preprint vrXiv:1112.03880 2017.
Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference robofics and automation (ICRA), pp. 3803-3810. IEFE, 2018.
Lerrel Pinto, James Davidson, and Abhinav Gupta. Supervision via competition: Robot adversaries for learning tasks. In 2017 IEEE International Conference on Roboties and Automation (ICRA), pp. 1601-1608. IEBE, 2017a.
Lemrll Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial rein- forcement learning. In International Conference on Machine Learning, pp. 2817-2826. PMLR, 2017b.
Andrei A Rusu, Matej Večerík, Thomas Rothörl, Nicolas Heess, Razvan Pascanu, and Raia Hadsell. Sim-to-real robot learning from pixels with progressive nets. In Conference on robot learning, pp. 262-270. PMLR, 2017.
Fereshteh Sadeghi and Sergey Levine. Cad2rl: Real single-image flight without a single real image. arXiv preprint
2016.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
David Silver, Julian Schritwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 339, 2017.
Max Simchowitz and Dylan Foster. Naive exploration is optimal for online lqr. In International Conference on Machine Learning, pp. 9937-8948. PMLR, 2020.
Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pp. 3320-3436. PMLR, 2020.
Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai, Danijar Hafner, Steven Bohez, and Vincent Vanhoucke. Sim-to-real: Learning agile locomotion for quadruped robots. arXiv preprint arXiv:1804. 10332, 2018
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and appli- cations in continuous control. In International Conference Machine Learning, pp. 6215-6224. PMLR, 2019.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Do- main randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp. 23-30. IEEE, 2017.
Anastasios Tsiamis. Nikolai Matni, and George Pappas. Sample complexity of kalman filtering for unknown systems. In Learning for Dynamics and Control, pp. 435 444. PMLR, 2020.
Eric Tzeng, Coline Devin, Judy Hoffman, Chelsea Finn, Xingchao Peng, Sergey Levine, Kate Saenko, and Trevor Darrell. Towards adapting deep visuomotor representations from simulated to real environments. arXiv preprint
2(3), 2015.
12

---

Published as a conference paper at ICLR 2023
Lu Wang. Wei Zhang, Xiaofeng He, and Hongyuan Zha. Supervised reinforcement learning with recurrent neural network for dynamic treatment recommendation. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2447- 2456, 2018.
Huan Xu and Shie Mannor. Distributionally robust markov decision processes. Advances in Neural Information Processing Systems, 23, 2010.
Runyu Zhang. Yingying Li, and Na Li. On the regret analysis of online lqr control with predictions. In 2021 American Control Conference (ACC), pp. 697-703, IEEE, 2021.
Wenshuai Zhao, Jorge Peña Queralta, and Tomi Westerlund. Sim-to-real transfer in deep rein- forcement learning for robotics: a survey. In 2020 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 737-744. IEEE, 2020.
Yang Zheng, Luca Furieri, Maryam Kamgarpour, and Na Li. Sample complexity of linear quadratic gaussian (Iqg) control for output feedback systems. In Learning for dynamics and control, pp. 559-570. PMLR, 2021.
Yuren Zhong, Aniket Anand Deshmukh, and Clayton Scott. Pac reinforcement learning without real-world feedback. arXiv preprint
2019.
13

---

Published as a conference paper at ICLR 2023
A MISSING PARTS
A.1 1 NOTATION TABLE
For the convenience of the reader, summarize some notations that will be used.
Notation
Explanation
6,08
model class and its complexity
θ= (A, B) (*(0), K,P,L,Y F
dynamics parameters defined
optimal cost of smitc-hhorizon and infinite- setting for θ
sec (18) (17). (19). and (20)
AL (cf.
1,, 7/2
strongly stable coefficients
X1,Y,U X2
upper bounds of & @j., yt. ut, fte. in (55). (26). and
Ns
max ||| B ||. |C Ns for all e E
Nu
max 1112 || 2|
NR, Np, Ny. N
upper bounds of K, P, P, I, respectively (see Appendix B number of episodes of LQG-VTR, upper bound of IC (see Lemma start step and end step of episode k, respectively
K.K
T(k)
θ,
optimistic model used for planning at step /
optimistic model used during episode k (θ, = θ₁ for S(A) sts belief state at step measured under system θ
0,2
high probability upper bound of || / 2
6,
Gaussian noises used the induction stage the proof of Lemma quantities defined in the induction proof of Lemma lower bound T... for desired properties at induction stage 1 lower bound of Tw. for desired properties at induction stage 2 instance dependent constant used in reduction (see Lemma instance dependent constant used to define D₁.
Co, C1, C2
TA, To, Tı
T A T. go T1 g2.: TM
Da
an, bu,
D
the || Il norm of JF (see Lemma the clipping error (difference between f' and f, see Lemma
A
A.2 ADDITIONAL DEFINITIONS
Definition (Controllablity & Observability). A LQG system θ (, (A, B) controllable the controllability matrix [ AB A²B ... A B) has full rank. We say (A, C.) is observable if the observability matrix [CT (CA)T (CA3)T umn rank.
(CA"-1)T)* has full col-
Lale et al. 2022)), A LQG system C = (A, is stable if p(A - (K))) < It is strongly stable in terms of parameter (R, (()]] < k and there exists matrices L and H such that B---- HHH with |L]|2 < 1-m,, | 1 K.
Definition 3 (Stability (Cohen al. 2018
Note that any stable LQG system is also strongly stable in terms of some parameters (Cohen et al. 2018), and a strongly stable system is also stable.
Definition 4 (Covering Number). We use N(F,e) to denote the e-covering number of a set F with respect the loo norm, which is the minimum integer N such that their exists F' E F with FF = N, and for any f E their exists f' E F' satisfying I
f'lloo ffll Sc..
Definition 5 (e-Independent). For the function class F defined in Z, we say z e-independent of (a..... .,] E Z if there exist f. E satisfying VE (2))) < and f(2) 2.
Definition 6 (Eluder Dimension). For the function class F defined in Z, the e-Eluder dimension is the longest sequence { ...... ,2n} E Z such that there exists 2 e where 2; is é' é'-independent of (2 = for any i E [m].
14

---

Published as a conference paper at ICLR 2023
A.3 PRELIMINARIES ABOUT THE OPTIMAL CONTROL AND THE KALMAN FILTER
is known that the optimal policy for this problem is a linear feedback control policy, i.e., ut = K ( where (()) the optimal control gain matrix and &ttt,e e is the belief state step (i.e. the estimation of the hidden state).
Let P()) be the unique solution the discrete-time algebraic Riccati equation (DARE):
P(e) A P(O)A+ C² QC A B B(O) P(G))
(17)
Then (() can be calculated by
K(@) (R B B P(O) P(O)A.
(18)
The belief state E defined as the mean of x; under system O which is decided by the system parameter θ and history H4. Moreover, assuming 1, 0, the belief state be calculated by the Kalman filter:
f11e = (7 [10))) + L(O))r.
1,, A Bu-1,
(19)
((0) = ((e)) + +1)-1
where Σ(O) the unique positive semidefinite solution to the following DARE:
( A AC(O)C (Cx((OC + +1)-102((0)A" +1.
(20)
We sometimes use L, P, K, E as the shorthand of L(0), P(O), E(O) when the system θ is clear from the context.
The predictor form is another formulation of LQG instance 2021
Kalman 1960
Lale et al. 2020b
It+1 = (A F(O)C)=, + Bu, + F(O) = Cr2 + et
(21)
where F(O)= AL) and e denotes zero-mean innovation process. the steady state, we have ~ NOO, ("))CC + f). The dynamics of ê follows exactly the predictor form.
A.4 DOMAIN RANDOMIZATION
Definition (Domain Randomization Oracle (Chen et al. 2021)). The domain rundomization oracle returns (history-dependent)) policy TDR such that
DD = arg min Fa
(V (0) V*())),
(22)
where V is the optimal cost, v is the cost of n, and d(6)) ) is distribution over &.
Chen et al. (202T) even with an additional smooth assumption (Chen al. 2021 Assumption 3), the performance of TDR depends crucially on d(&') In high dimensional continuous domain, the probability of sampling an accurate model close to the real world model by uniform randomization is exponentially small. Thus, the learner needs to carefully choose the domain randomization distribution d(6') with strong prior knowledge of the real world model. In contrast, the robust adversarial training oracle does not worry about this, and just needs to solve 7 by some min-max optimal control or robust RL algorithms.
As shown in Theorem
B UNIFORM BOUNDED SIMULATOR SET
Under Assumptions I and 3. is possible to provide a uniform upper bound on the spec- tral norm of P(0), E(O), (() and I(O)) after the model selection procedure. Let No max(]|Q|12. [[]]]2).
For any θ (A, B, C') E 6, we have | I NK by Assumption 2
By definition the unique solution to the equation
(A BK) P(A BK) P C=C KT RK,
15

---

Published as a conference paper at ICLR 2023
where p(A-Bu 1. Therefore, Lemma B.4 of Simchowitz et al. (0200) shows
00
P= Σ ((A (A-BB)]T)* (CTQC++ QC K RK) BK)*
Since (1LA-BK)MN S -n)*
Pll & NN + No) 111-7) v Np de Nu + -Nk)
271 -71
k=
Similarly, Σ the unique solution the equation
-= (A- FC)E(A -
where AL and A FC is (K2, 72) stroongl stable under Assumption
Thus we know
|> No def +11+
27/2 - -2
Finally, we have
||||2 || (CECT + +1- S N def Ns
since (CEC +1)- 1.
In this paper, use Np, No,N .K, N& the uniform upper bound the spectral norm of ((0), K (0) and L( for any E 8.
C DETAILS FOR THE MODEL SELECTION PROCEDURE
In this section we provide a complete description of the model selection procedure.
The main purpose of running a model selection procedure at the beginning of LQG-VTR is to obtain more accurate estimate Á, B, Ć, f. of the real-world model O'. This accurate estimate is very useful to show that the belief states encountered in LQG-VTR will be bounded (see Lemma
We follow the warm up procedure used in Lale et al. (2021) to estimate Markov matrix M, and perform the model selection afterwards. The matrix is
M
CF CAF
CAR-IF
CB CÁB
CA"-IB
where Á = A - FC A-
Algorithm 2 Model Selection
Input: model selection period length Tw by Eqn. (56). simulator set &.
2: Set 1.
3: Execute action u, ~ oV for T,, steps, and gather dataset Dinit = (yt, Us T.
4: Set the truncation length = ()))g(()H))/ log(1/ng)
5: Estimate M. with Dinit following Eqn. (11) of Lale et al. 2021
6: Run SYSID(H, G, n) (Algorithm of et al. 2021 to obtain an estimate A, B, C, i of the real world system O*
7:
Return & n C, where C is computed through Eqn.
23
The regression model for M can be established by
1/1 Mét + ez + CAR x.-
where [M_1 D. JI_,
uI uTHH]
Here e, is a Gaussian noise, and
CAH Ft-H is an exponentially small bias term.
Thanks to Assumption Á is (K2, stronnyy stable matrix. Hence IA"12 = (1 O(1/ H2), and the bias term will be negligible.
16

---

Published as a conference paper at ICLR 2023
Therefore, by estimating M with random action set Diitt. come similar confidence set as shown in the Theorem 3.4 of Lale et al. (2021): There exists a unitary matrix T E Rax" such that with probability at least 6/4, the real world model 6 is contained in the set C, where
del 0 (A,
A A-T' T AT
S BA. B B-T B
S BB. C ČT S Sc; [ T | Be..
-
(23)
Here the unitary T' is used because any LQG system transformed by unitary matrix has exactly the same distribution of observation sequences as the original one (i.e., LQGs are equivalent under unitary transformations), Without loss of generality, we can assume T = I. 3A. 8B, Bc, 32 measure the width of the confidence set, and we have
C
Ba. BA. Sc BL S Tw
(24)
for some instance-dependen. parameter C.., according to Theorem 3.4 of Lale al. (2021)
Now we discuss how to decide the value of Two so that the following bounded state property holds after the model selection procedure, which is crucial bound the regret of LQG-VTR. We define I. as the number of episodes of LQG-VTR.
Lemma (Bounded State). With probability at least 1- throughout the optimistic planning stage of LQG-VTR (i.e., after the model selection procedure), there exists constants X X2, Y,U such that the belief state & measured in O₂ for any episode & [K] and any step in episode satisfy
| |
s 811.
(25)
Accordingly for any step E [H].
llvell2 SP, ||uell2 Ü.
(26)
For any step E [H] and any system B, B,C) E 8. the belief state measured under with
history (yo, Uo V1. 11, ... Ut-1: 14-1, Ue) is bounded
|2p1.l112 S X2,
(27)
where
-, vD) log H)
(28)
As consequence, the algorithum does not terminate at Line 9 with probability 1 5.
Proof. Let S(k) and T(k) be the starting step and ending step of episode k. For simplicity, we use 6, (A,, Br. C,) to denote θ for S(k) < T(k) for time step t (The first episode starts after the model selection procedure, (1) Tw + 1). The core problem here to show that after the model selection procedure (Algorithm 2.. the belief state &,,,, under θ stays bounded, then ui also stays bounded since u, = - assume this event happens.
Since O* with probability at least - 8/4, we
Before going through the proof, define constant 2 and ū such that with probability 1 - 8/4, [|well2 I T, ||æe|l2 < & for any < t S H, and ||uella I a for 0 < < T. Since Wes Res Ut are independent Gaussian variables, we know to = O(vn (og(H)); z = (Lvplog(H), O( O(ym log(T..)). For the model selection procedure (which contains the first Te, steps), it holds that with probability 5/4, for any t S Tw. ||,, 12 < O( (og(H)) ||uell2 I ū. llvellz s ONNs / log(H) + vplog(H)) by Lemma D.1 Lale et al. (2020c). We assume this high prob- ability event happens for now.
We use an inductive argument to show that for any episode and step t therein, it holds that | 1 ll2 Co(1 + 1/K)* for some Co. To guarantee action ut does not blow up, set the
17

---

Published as a conference paper at ICLR 2023
upper bound of [| é, 2 X1 der cCo 2 Co(1+ + 1/K0* for any h < K R. Thus, LQG- VTR terminates as long as || exceeds that upper bound (Line of Algorithm D. For convenient, we call the model selection procedure as episode 0 (so T(0) = Tw). As the inductive hypothesis, suppose that || S Do S Co(1 + 1/K)* holds for some Do and step S T(k)
when
k 2 1. We define Du Co for Cu = O((vá + vp) log H) specified later when & = 0. Then we know that the algorithm does not terminate in the first & episodes. Moreover, we have for any t s T(k) it holds that ||we||2 v Nx Do- Thus for 1 & T(k) + 1, by definition of 2t and we have
(AA))
| - - p(Ar) (NgN w) Melll = Nsllael2 2.
(29)
Suppose Do 2 wA()))((1 p(A")), that
| = (1+ N Do, llvoll2 -
1 Ns+ + N3Nxx((A') Du-
(30)
1 p(A()t)
1 1 --p(A*)
Hence, we define three constants Du, Dz, Dy such that for any /. T(k) it holds that |/ue12 S Dy Do: for any S T(k) + 1, we have | S D2 Do, llvel12 I Do Note that D,, Dæ, Dy are all instance- deeenddd constants. To more concrete, suffices to set
NsNxx((A)) Du NK D2 =+ 1- p(At)
NONKx((AA)
Dy = 1- p(AA))
INDUCTION STAGE 1: t T(k) + AND SHOW [ IS VERY CLOSE TO (e, lla
In stage 1, we need to derive four terms TB. Tc, Tr as the lower bound of Tw to achieve the desired concentration property. This means as long as Tw 2 TA.TB. Tc, T2, we can prove the induction stage thanks to the tight confidence set C defined in Eqn. (23). Now fix t T(k) S(k + 1), for any O E Ui we have
211000
Σ A (Bu-= Ly1- + Lyo.
(31)
where A (T-LC)A, dd (I LC)B. Note that ||At||| S k2(1 ) according to Assumption Therefore, for θ = θ₁ and θ Õx+1 (both θ₂ and Op+1 chosen from the confidence set C
by definition),
1 Σ A
(BRut-o Lxst--sti + AiLuv Σ Abtl (Br+1We-s + LR+1Me-st1) + Abt Lat
To move on,
Σ A (Bxte + +anns+-Twe--e Tunn--011) Σ
1--1 (Be41"m0s + + T44180-0411)
s=1
+
Σ
A (Bet1uls Lo41Ve-041)
Σ
(Befiue-o + Le4136-041) T--1 k+1 #=1
==1
L Alrn Le4190-
We bound these three terms separately in the following. For the first term, observe that when T, 2 Th, we have
2/Cw
A (Lx L++1 (k+1)yl-o47
N2(1 - -72) -1
DyDo
VTr
2
(32)
2x D, VCw Do-
TTT,,
18

---

Published as a conference paper at ICLR 2023
where the first inequality is due to the confidence set (Eqn.
23
the induction hypothesis, and
Assumption Thus, as long as Tμ 2 (12mzD, \/
( we know
Do
Σ A "Lx Lk+1)
(33)
6X
Similarly, we have
BR Batil/ S /v
1 N
N
NLNs
+
VTB
VTL
VTc
by checking the definition of By and B Therefore, as long as
TB 36ni2Du Cio(1 NLN -0(33
7/2
36mz Du NEK -0(K)
Tτ 2
7/2
36k² Du C NI, =K(3)
Tc
7/2
we have
BB.
BB+1
- 112io
7/2
Therefore, it holds that
Σ A - (B. - Bx+1)u+-
I
Do 6K
(34)
following the same reason as Eqn.
32
To sum up, we require TB 2 O(K²), T2 > O(K²), 2 O(R2) to ensure that as long as Tw 2 max(TB. T2, Tc). the first term bounded by
Σ Ag-
(B8s-
BB+1)U-- + (ix i ((+1))t
Do
(35)
3k
from Eqn. 33 and Eqn. 34
For the second term,
A - Aiti) B (Bu+iur La- 1ee-)))))))))
(36)
E (s - (1-2))--2 ((Ng N3ND)DD, + N2) Do
(see Eqn. [44
(37)
==1
$ Ex (k2/ (((1 - -22=
-1)) ((Ns +
+ N., Do.
(38)
where
Es = A. - A
Note that C₁ def max {(1 - --1 is a constant. Similarly, we require TA, Tc. Tr 2 O(R2) (see Eqn. 332 and Eqn. (33) for an example on how To.To, Tr are derived) to ensure that long as
T. 2 max Te, Ir), it holds that
Do 3R.
& (R2/12) ((Ns + NENL)D, +ND,,) Do -
(39)
19

---

Published as a conference paper at ICLR 2023
Using the same argument, by setting appropriate Ty we have as long Tw 2 TE, holds that
Do
La3o - A
(40)
3X
As consequence, combining Eqn. (35). (39). and (40)
gives
Do
1.... - Eett,
12
(41)
K
| 11: S
Do
1+
(42)
K.
For now we have proved the induction at the beginning step / = 5(k 1) of episode k++1 1, it suffices show that [| ll2 S (1 D/ for the rest of episode k 1.
INDUCTION STAGE 2: SHOW THAT | 11,0 1a S (1+ 1/KC)) HOLDS FOR THE WHOLE EPISODE k +.
Suppose LQG-VTR does not terminate during episode k+ 1, then the algorithms follows the optimal
control of θx+1- Denote O++1 (A, B,C C), we follow the Eqn. (46) of Lale et al. (2020c) to
decompose Eej1,2+: for S(k + +) + T(k +1:
8 :110 - + LC* (#111-1,0- -210-166) Lz + îo (xx f11-110.))
(43)
C*BR).. The main idea to prove induction stage 2 is to show that & Te,r, will also be bounded by (1 (1+11 1//) as long as 11-1jc-1, is bounded by (1 Do. given the conclusion & *3(++1)))(++1),..
where M def (Ā BK
1/KC) of the
induction stage 1. To achieve this end, we divide the induction stage into phases. We first show that 1.e 1, is small in the first phase, and prove the above main idea formally in the second phase.
Before coming the main proof for induction stage 2, we first observe that ē C* (Ie e.) is (NsNg + 1)-subGaussian noise, so with probability at least 1 - 8/4 we know ||e|||2 bounded by C2 + / n (o)(H) for any 1 S t H and some constant C2. Assume this high probability event happens for now.
def 24 +
- We mainly follow the decomposition and induction tech- niques in Lale al. (2020c) to finish phase However, we note that our analysis here is much more complicated than the analysis in Lale et al. (2020c), because they have only one commit episode after the pure exploration stage (the agent chooses random actions their pure exploration stage, just the same the model selection procedure in LQG-VTR) but we have multiple episodes here.
Phase 1: bound 1,6
Define A, def -+4 - $ +10044+1)))44404011101100 for 1 s T(++)) S(K+
1) + 1. For = 1, we have
A ( #S(H+))+11((-1))66..
(44)
A' + B Ug(K+1)) Aă S(K+T))S(++)))))
Bug
Since we have assumed O' C, we know || - ll2 will be small according to induction stage 1. Specifically, we can set Th, Ty O((Ni.Nsks)² 71 )
so that as long as Tw, 2 Ty T we have ||ill| S Do (8N, for constant Kg defined later. Now that have come up with upper bound on | we hope to bound each ||Arl2 and prove Eqn. 447
For < t < T(k + 1) S(A: + 1) + 1, we follow Eqn. (49) and Eqn. (50) of Lale et al. 2020c to perform the decomposition
[-1
A, = - G
Σ
G
1-1-
c
+
G -
-
Gz4, + êr, (45)
1=1
20

---

Published as a conference paper at ICLR 2023
where éN is noise term, whose 42 norm is bounded by Ol plvppuu plog(H) (H)) with probability 1 - 6/4 for any episode and step t. We again assume this high probability event happens for now. We define
Ag
del A A A
BK B K and thus
Go (A' + (T
G1 = (A* + A - [(- - Ag:
(46)
G2 = A" - BB*K + B =K(C-
G3 (A' - B" B'K + B" B'LLL'
Using a similar argument as in Lale et al. (020c), we define Too, Tg2 so that Gb, G2 are (K3, 78)- strongly stable for some 7 S min(?2/2,
71 /2) and 6i3 2 1 long as Tw 2 max (T b0; Tg2)- This is possible because as long as close enough θ Go will be strongly stable according to Assumption 3 while G2 will be contractible in that |G2 |l S (1 + 71 )/2 according to Assumption
2
more concrete, we show how to construct g2 the following, and the construction of To analogous to that of T22.
Observe that
(A- - BK-BKK
G2
BK
A"
BB
By a similar argument used in Eqn.
32) and Eqn.
33
we know
A- - A+ [B B*) + BB
||
1-
m1
$
2
as long as Tw 2 Tg2 del 36C N3 N N )
This further implies
1-71 1+
||22122 - i - BK||2 2 +
2
where the second inequality is by Assumption Now we prove that
1l < 1- Do
(47)
NN
holds for all S
First of all, we know || | I Do((1~n)/ (8.V S (1-9)) (A/( according to Eqn. for all S S 1-17 1-
44) and K3 2 1. For any fixed suppose |A, S (1
then the decomposition equation (45) implies
|ll12
G6
A
+ + Σ
Go dl-
G 2 25041)+11(0011)1
G Gsd.) +
<
G1
G6 1-1
G 3500+14441
Σ
G Gzd,
+ +xy(1 73)* 1 411111 /|2 + l|eell
1-1
j-1 Σ
< <||Gil|a- (t- 1)x3(1 | (3)* - 2Ns No)
G1
G
G
c
G3d.
j=1
+ + - " 112 + ||Ee|l2
K3 %
1 71 Do 4N,
< ||2 (t- 1)x 7a)ーh --1 2Ns(1 Nx) +
|G
+ +k - (1)(1)))*~111 ||2 + ||ee|12-
The first inequality follows from the strong stability of Go and the concentration noises ē, The second inequality is due to the strong stability of Go, G2, and || || < (1 +
21

---

Published as a conference paper at ICLR 2023
NK) (Ns No & 21 + D, according induction stage 1. The last inequality is
because the assumption that | I (1 (1 (4N for all S -
When Te 2 Toi for some T31 we know that
||G| - Ns (L+(L+
NLVO
VC+(1+NN VTyi
vCw (N (VO, + 1)(++
Vag
Since max 1) 73)(=1 and ||a||2 are both cestance-dependentt constants, there exists an instance deeendeede constant To that for T., 2 TaI. holds that
1 71 Do-
||Gill (t 1)x3(1 (1- 73)==
2N + NR) S
(48)
24NLNs
K3
1-71 Do v 4N
1- 71 Do- 24NNNs
|| 1|2
||alll
(49)
Moreover, the bound on | from Eqn.
(44 implies that
1 Do. (a)1-79)* -
(50)
8N
Note that we can set Co so that Do is large enough to guarantee
(1-1)Dy
24 2 lēell2 = Olv (l)(()))))
(51)
for any episode & and step in it.
The proof of Eqn. (47) can be obtained by combining Eqn. As final remark, Too, Toi, Tgp has dependency H.
(48
50 and (51)
Phase 2: finish induction stage 2 Now come back to the main decomposition formula 43
Define TM O(22/((22)) /(1 -)))²) so that ||C'- C'I2 is small enough to guarantee ||M [|2 S. (1/21 (see the definition of M at the beginning of induction stage 2) as long as Tw 2 TMr Suppose we know || ll2 I (1 1)/C) for time step t 1, then as long as Du NNs
1) nL (1) 71). we have
| 11
||Ill2
1+
Do + LC | [|AA-ssk+tilll + Le,
(52)
K
< 1+ 71
Do + 1-
1 1-71 71
1+ K
Do + Do
(53)
2
4
4
< 1 Do.
(54)
Fortunately, we know that || ())()++)]((++++ 1), 0 ll < (1 + 1/K) according to induction stage 1. Using the recursion argument above, we can show that | ll2 $ (1 1/R holds for S(k: 1) < < T(k + +)
We have proved the induction from episode k + so far under the condition that LQG- VTR does not terminate at Line during episode k. On the other hand, if for some step S(A: + 1) + < to S T(k 1) the algorithm entered Line 9 (note that it cannot be ta = 5(k + 1) because induction stage does not depend whether the algorithm terminates), then the decomposition for f 43 and decomposition for A (45) still works for steps < to. Therefore, there must be some high probability event fails at step to (i.c., - and/or ēt explode). This is impossible since we have assumed that all the high probability events happen.
22

---

Published as a conference paper at ICLR 2023
Thus under the condition that all the high probability events happen, it suffices choose the constant Co = O(( ( vP) log H) so that Eqn. (30). 51 52 all hold, and LQG-VTR does not terminate at Line 9 due to the definition of X1 = eCo- Since these high probability events happen with probability - 5 and recall that the total number of episodes is bounded by K, we know that with probability at least 1-
& qr. lla S Co (1 1+ K) sc - Xi = vD) log H).
(55)
As result, know || 12:1222 U del XI because ut -K(6)) Moreover,
- y/ T² + 24 = 0 c 1|t-1,0, + CO (I+ - -1e--(p-1,6) 1,0, .)
= C² ê 1, + B, -Bi-1u4-1]
+ +C (I2 - 1111-118--1)
C + + F4 1, + f1/0-100-
111-1 + -B2-14t1)
1161-1.6.11) + zc.
Observe that ||ue-ille I U, the 22-norm of noise term 3t 1, is bounded by C2 NN + nogglo and the last term 1,/c- - - 1, can be bounded through Eqn. 447 we have
llvell2 v N 0) CaNsNN logg)) (1 n-))
4N
Note that topo,e L(9))oo by Eqn. 31
| S K22(1 - 722 N Y Σ K2 -2-) -2) 1 NLNs)) + +NLY
< X2 K2(1+ N + K2 N2)
72
At the end of this section, we set the value of Th so that the confidence set C. is accurate enough to stabilize the LQG system:
To max Tr T', To To Tx) Ö(83).
(56)
D PROOF OF LEMMA 3
Proof of Lemma 3 The key observation to prove the lemma is that for any θ E 6, the difference of H-st H-step optimal cost between the affnite-horizon setting of θ and finite-horizon setting of θ is bounded:
V*(()= (H +))* s Da:
where D, is independent of H. We now prove this statement.
We first recall the optimal control of the finite horizon LQG problem. The cost for any policy π in H-step finite horizon LQG problem is defined as
H
E
Σ
Qun + un Rus
where the initial state 2o ~ I),
The optimal control depends the belief state E[r HA). where H, is the history observations and actions up to time step h. It is well known that Fy is a Gaussian variable, whose mean and covariance can be estimated by the Kalman filter.
23

---

Published as a conference paper at ICLR 2023
Define the initial covariance estimate 201-1 def then Kalman filter gives
En+1jh 1|h = AEpph-1 A AE 1 (CEMp--I" + -EN--CENN-IA + +I, (57)
and
Enjp = (1 LaC
where
= ENj-I (C -
The optimal control is linear the belief state [[xn| with an optimal control matrix Kr. This control matrix in turn depends the Riccati difference equation for Ps. takes the form:
Riccati difference equation as follows. Define Ph C CTQC,
Pr A Ph+ 1 + QCQC QC-QQ-AA AT B(R B Pr+1B)-'BB Pa+1A.
(58)
The optimal control matrix is K₁ = +R++ (R+BBTM PTB)) PrA. Then the optimal cost of the finite horizon LQG problem (*(@) equals
(*) Σ trace (Pr(Enja-1 Emjp)) + Σ trace (C QCEM)A)
(59)
h=
For the anfinite-horizon view of the same LQG instance O, we denote the stable solution to two DARES (57) and (58) by and (i.e., we use Σ, P and to represent E(O), P(O) and I(Oe)), then the optimal cost (+) equals
(*) trace (PLCE) + trace (C QC(C DF(CQC((C))) IC)E).
(60)
Now let us check the difference between (H+1)J*(() and (*(@). The difference can be bounded as
H
(*(0)- - + 1))*
trace (PLLnCEN)--i) - trace (PLCE))
(61)
h=0
H
LA LACC)=NNA-)) (traee -
trace (C QC(1-LC)2))
k=0
(62)
Positive definite matrix Q can be decomposed Q rT where I RPxP is also positive definite. Therefore, for matrix C' QC = (TC)TTC, TC, we can show that (A,TC) also observable owing to (A, C) observable and T positive definite. Since (A,TC) is observable, and (A, B) is controllable, we know that the DARE for P has unique positive semidefinite solution, and the Riccati difference sequence converges exponentially fast to that unique solution (see e.g., Chan lt al. [1984] Theorem 4.2), Caines & Mayne 1970. Theorem 2.2), and the references therein). That 1s, there exists uniform constant ag such that
|| Pall2 S H-
(63)
since ||A BK|| I Yi for any θ E
Similarly, Σnta-1 also converges to E exponentially fast in that there exists a (instance-dependen
constant bn (Chan al. 1984 Lale et al. 2021) such that
||ا Empn 1 1l, I (1-
(64)
which further implies that Ln also converges to exponentially fast for some constant Go:
1 S c0 =;
(65)
since 21j-1 / is positive definite (the techniques of Lemma 3.1 of Lale et al. (000cc can be used here).
To show the existence of by observe that
Enjh-1 E' -A- ALC (Moj-1 - M)h,,
(66)
24

---

Published as a conference paper at ICLR 2023
where oh _ (A- ALOC) -LAAA (A- AL In the proof of Theorem 4.2 of Chan et al. (984) we have
Sn/h-1 2h - -0 1h.
non-negative constant matrices.
(67)
Theorem 4.1 Caines & Mayne 1970) shows that for any θ 6 and any 0 s h H it holds that
x kz)
|Enjo-1|12 5
N5.,
(68)
272 72
which helps us determine bu = Ns.
The existence of ag also relies on the state transition matrix (Zhang et al. 2021 6 = (A (K+)(A- BK (A BK As minimum requirement to tackle the finite horizon LQR control problem, we shall assume |1% is uniformly upper bounded (i.e., the system θ is stable) for any & (in fact, people often assume a stronger condition that it exponentially stable). According to Assumption we can now identify the existence of ag.
As result, have
H
('(0') (H (H+1)
Σ (trace (Pr trace (PLCE))
(69)
(trace (C QC(1- -AC))ENN-1) - trace (C QC(1-
(70)
trace ((Ph- - P)L, Σ
trace (P (L,CEEM)11-
(71)
4=0
trace (CT (OhjA-N-- LOE. -x,
(72)
H
O (naum) H-h + nne + co)(1 (0)(1-12))) )
(73)
h=0
n00
mbn + too
Dr.
(74)
72
where the second inequality uses trace (X) S n|| X||a for any X Raxn.
Now for any (history-dependdnn) policy and any θ 8,
("(0)- - (+) < (+) (Hl + ()) +Ds
Regret(r;H))
Combined with the definition of काe in Eqn. 7b. have Gap(TRT) * (0*) (* max
(V* V*())) < Regret(m; H) Dny (75)
BEg
where the first inequality is by the minimax property of गरт and O* e &.
E PROOF OF THEOREM 4
For all the conclusions in this section, the bounded state property of LQG-VTR (Lemma 5 is crucial condition. Let V be the event that for all < t I H, @ lll I X, (so that LQG-VTR VTR does not terminate at Line 9) then by Lemma 5 we know P(V) 2 8. We provide the full proof of Theorem 4 in this section, but defer the proof of technical lemmas to Appendix F
25

---

Published as a conference paper at ICLR 2023
E. BOUNDED &o NORM OF F
To begin with, we show that ||Filo is well bounded under event V.
Lemma (Bounded norm of F). Suppose event V happens, then each sample
F #1,,, Wk ue, #+111++1,6 M++1)
(Line 13 of Algorithm satisfies for any S S H. (Te, @rr.b. ur Qx) E 2 (recall that X the
domain of f defined in Section 4.4)
There exists constant D such that for any θ E 8,
ll
del max BEX
(E)) & D O(n log H),
| - D.
E.2 THE OPTIMISTIC CONFIDENCE SET
Now that | is bounded, we can show the real-world model O* contained in the confidence set with high probability. Note that this lemma requires a more complicated analysis since we are using a biased value target regression (Ayoub et al. 2020).
Lemma (Optimism). It holds that with probability at least - 28,
e* E Uk
for any episode & E [K].
E.3 THE CLIPPING ERROR
We also analyze the clipping error introduced by replacing f' with f (see Section 4.4 in the LQG- VTR.
Lemma 8. Suppose event V happens, there exists constant A such that for any system θ
(A, (,, & and for any input (T', u. Q) X at time step
As (r',,,,, u,,,,,,) sot | (r',,, ( 6) s A O (m2(1 1200-22)) 72) ( + p) log H)
(76)
where 7¹ (yo, uo, ...... me3 is the full history, and 7! {ur-1 1/-1+11-" 11-1,135 11 is the clipped history.
E.4 Low SWITCHING PROPERTY
At last, we observe that the episode switching protocol based on the importance score (Line 14 of Algorithm I ensures that the total number of episodes will be only Ollog H). Lemma 9 (Low Switching Cost), Suppose event V happens and setting & 4D² + 1, the total number of episodes K. of LOG-VTRRAlgorithmm 1 is bounded by
K
where R. defined as
K. del
(F
(77)
for some constant Cx-
Proof. This lemma is implied by Lemma
T and the proof of Chen et 2021
Lemma 9).
This lemma also implies that the number of episode will NOT reach K. since K. R but not K. < R. This property is important as it guarantees that LQG-VIL VTR switches to a new episode immediately long as the importance score gets greater than 1.
26

---

Published as a conference paper at ICLR 2023
E.5 PROOF OF THEOREM! 4
We have prepared all the crucial lemmas for the proof of the main theorem till now. Putting every- thing together, we provide the full proof for the Theorem 4 below.
Proof of Theorem
Define
(egret(H))
def
Σ I=
(y) Qu: + un Ru: - J(
then Reg = E Regrot(H)) + O(Tw). We assume event happens and the optimistic property of 24 (Lemma [ holds for now, leaving the failure of these two events at the end of the proof. As a consequence of v, the algorithm will not terminate at Line
As know the regret incurred in the model selection stage is ((Tw)) O(K22) is only logarithmic in H, it cannot be the dominating term of the regret. Denote the full history at time step t as 7' (yo, uos ... 1t 3r we decompose the regret as
H
Regret(H))
=
Σ
(uTQw Qu: + u, Rw: (*()))
(78)
t
H
Σ
U. Que + ue Ru -
J Jr(())
(by Lemma
(79)
T=
K
T(k)
E
4h TTAT 2+111+1,0x (P-
H1111166 + TT 1 Qy
(80)
k= to S(()
T 6
(p (P-
BuleB - Vi Qui
(by the Bellman equation of system θ2)
(81)
T(K)
goMTT 1111111,x
(p-CTQQ)
a
1411111,, + 14 Qy
(82)
S(R)
- for (7 (7 u4, U1,6))
(83)
Ser (7 (T ur, 0x)
TT o1
(p-CTQC) E.l1.6. 3e Que
(84)
Here denote Ô₂ (A, B, C), and P P(θx). For any h: E [17, the last term (84) of the regret decomposition can be bounded as
T(k)
Σ fer (F's 4e 61) - IT &1 (i (P-CTQO) &110,6x - -. Qu
(85)
(())
T(k)-1
Σ for (7* ( ue, 0k)
aT 341111188 - (P-Ō-Q0) 2 &141/111,6 - -V-1
(=S(K)
(86)
+ for (TT(h), "Tr,,, 6x) S(n)ss (p-cTQC) (S(N)S(())) VS(()) -Us( Qus(k)
T
(87)
Observe that Eqn. 86) is martingale difference sequence, and Eqn. 87 is bounded by 2D by Lemma 6 Summing over k we have with probability 8,
K T(k)
4r Σ Se. (7', (g', ur 6x) - TT.. (p-CTQO) & - -i Qu
(88)
km (K)
< &DVHlog (0og(1)))+2)))
(89)
27

---

Published as a conference paper at ICLR 2023
Now focus Eqn.
(2) and (83).
Observe that Eqn.
(82 can be written
1,
(P- (P-ŌTQQ'
1. +
14116 Qu 11t11
TT
(90)
-So
7" 111.6, ue, 0k).
(91)
Therefore, Eqn.
and
83
becomes
T(k)
for (er,
Se. (e 6x)
(92)
Rm (=S(k)
Consider any episode 1 S v K,, define 2g to be the dataset used for the regression at the end of episode &s (Zo 0). The construction of confidence set set (Eqn. 110 shows that
[e. - fe-11 32_1 I 2B.
(93)
By the definition of importance score (Line of Algorithm I). we know for any S(k) S t 1 T(k),
Σ (Sor (Tos (1n.d, usy 6k) - Ser- ( us u. 6x)) S 23 4D2
(94)
8 S(A)
where T. = (ux Us-1t1, 11 ys ifl S 8, or T denotes the full history at step if >
Summing up Eqn. 193) and (94) implies for any k.
min(t.T(ol)
T a fn. us Go) for ut. u.))) $3 e 4D² (95)
Σ Σ
(fer
Uz
=S(()
Invoking
Jin et al. 2021 Lemma 26) with 9 F F, -é. fer, 1/H, and p,(+)
1[. (T., 3. a., us 6.)]. we have
T(k)
Σ
fer (T.. Ue, 0x) fer (Te (1:: 61))
(96)
S(k)
0 dimg (F, 1/) 3H + D minnHH dimg (F,1/H))
(97)
The clipping error between f' and f can be bounded by Lemma
T(k)
Ve. (7
Ser (7' (el,,, ue: Ox) 6x) @rr, ur,
(98)
k=
B(k)
T(k)
Σ
Sor (T. un 2x)x)) - for @T ue 6x)
(99)
R= (=8(K)
T(K)
Aiey (T ue, @x) + A (r', Reje, ue 6k)
(100)
((5)()
< 0 (dimm
3H + x2(1 - 72)((n + p)H log? H1
(101)
Therefore, we choose = O(log( Hn + Hp)) to obtain
T(k)
ΣΣ fo. (7 un @x) for
ur 0x) s <o(vdim (F,1/H) (f. 3H
S(k=
(102)
where B = O(D2lo 1/11)) is defined in Eqn. 119
28

---

Published as a conference paper at ICLR 2023
Plugging it into Eqn.
(92 combined with Eqn. 89
finally bound the regret
Regreu(H) s 00 co(Vviim dimm (F) 3H DV H log(1/)) + 2DK)
(103)
as long as happens, the optimistic property @ E U3 for any episode k, and the martingale difference (86) converges. The probability that any of these three events fail is 46, in which case the Regret H) can be very large.
The tail bound of the Gaussian variables (Abbasi-Yadkori Yadkori & Szepesvári, 2011 indicates that for any q > 0 and 0,
q²
(-9")
9"
P [[I 2 q) S exp
P (([]vel22 2 4) S 2pexp
(-2p)
2n
2p
Therefore, union bound implies
q²
IP (H,, max([|wxllal)) ||velll) 2 g) s 2Hnexp
pxpp
2n
2p
Note that long v0 < & H, |/ 22, |1x/12 ll2 S q. know that
Regret(H) CR(q² + U2).
since ||uel12 S Ú always hold for some instance dependent constant On thanks the terminating condition (Line of LQG-VTR.
Thus we know
9²
92
PP (Regret(H)
> Cn(l < 2Hnexp
+ 22H
2n
2p
We set = Hnp and = 1
(q² + - so that
Regret( (1) E' Regret(H))
+ +
(104)
- P + 44Cn(92+00) Cnl(2+03)
50 dime (F,1/H) 3H
(Regeet(H) > xx) dx (105)
0 dime (F,1/) 3H)
(106)
The integral above is a constant because P(Regret(H)) x) exponentially small term. The
theorem is finally proved since f Ö(D log (F,HHH)) and || S D Ö( + p). 0
F PROOF OF TECHNICAL LEMMAS IN APPENDIX
E
F.1 PROOF OF LEMMA 6
Proof of Lemma 6 The first part of the lemma is implied by the definition of V.
29

---

Published as a conference paper at ICLR 2023
By definition of X, we know that for any (r', I, u, b) E X' and θ 6,
T0 u, ))
Ee. x TP-
vit Qvi+1e (by Eqn. (6
(107)
-Ee
((1- (Ax + Bu) L (C CBu (
(P (P-CTQ0)
(108)
(T-
Ax Ax Bu) + (CA + CBu+ +
(109)
+ Ee, [CARRILO + +BBu+e) Q @(CAEfI + +CBu+ey
(110)
-(iCAifKL + iCBu+ (I- (Au BB++Bu) (P- (P-
(111)
(iCAFSRE + LCBu+ + (1- LC) (Az+ + Bu)
(112)
(CAR + +CBu) Q (CAA + +CBu)
(113)
+ +trace (JTPP-TQQC (CECT + +1)) + trace (Q (CECT +1))
(114)
+ 241 is the innovation noise such that 6:- ~ C2()) + +1) Zheng et al. 2021 Lale al. 2021).
where P = P(O), i L(ô), and e, Ow. + CA(2, ))
Note that & $11..0 = $1/L,0 - (A - LCA)' - so || S (2-+-2(1-2))) )22 Therefore,
each term in Eqn. (11) (144) is bounded in at most O((v + vD) log H)) besides || la =
O((V + vD) log H). We can finally find a constant Dj such that ll I D1 = O((n +
p) log" H) for any θ E &.
By the definition of optimal bias function in (4) we have
li v.)) = (P).)((()) - c. QC)))L + vi VIQQu Que
(115)
$ D2 del (Np +
N3NNu) NN++N3NuV) + N2
(116)
suffices to choose D def max D2) = O(n + p) log² H).
F.2 PROOF OF LEMMA 7
Proof of Lemmal) 7 As a starting point, O" e U1 holds with probability 1 6/4 4 due to the warm up procedure (see Appendix C. We assume event V happens for now, and discuss the failure of V at the end of the proof.
For episode 1 k K. and step t in the episode, define X, def (r', &r", ue, θx), #r (Xi)- (X.),,,, Y2 del *T
(41.6 (P-C (--CTCC) QC) + vIT Que+1 for P P(θx), C(êx)
(note that fei only depends on the 1-step nearest history n6 instead of the full history r²).
Let F be the filtration generated by (Xo, Yo. X1, Yi,..,,,,, Yi (X.) = E|Y, Fr-1] by definition. Define Z. def Y, - f/. (Xt), then Ze is D/ D/2-subGaussian random variable conditioned on F by Lemma 6 and it is Fr measurable (hence F-adapted). It holds that for the dataset Z at the end of episode A
then we know that
||Y f112 I
fall2
lff f112 + 222 + d. f)z,
where (z.y)2 2 def Eeez (())((e). ||- y11
~ (a v. 2. E fer
Rearranging the terms gives
2 llf. - f12 = Y - fll - | - fall2 + E(f),
30

---

Published as a conference paper at ICLR 2023
for
E
2 1l. - f112 + 2 d, f- --))2-
Recall that f dd fec.. = arg mingeu, IIfe Yll2 and f. L1, we have - - fl.. Y- Thus
-.- 1| E()). 2
In order to show that f is close to f., it suffices to bound E(f). For some fixed a > 0, let G(aa) be
a-cover of F in terms of || 11 Let f def minser Ilf fl1z. then
E ( = - E ( + ( F.
( - (f)
FF
max E(J). fEG(a)
We now start to bound these three terms. For any fixed f E F, we know that (Z - f+) is Dll Subaausuuaa.s Then it holds with probability 36/4 for any episode and X > that
1 log
4 35
D
|
fo1l
B(J) < - 111- SIE
+
2 fa)z
2
Choosing Ả = 1/ we get
4
4
E(J) - D2
+ 2d, f-)z S D² log
+ 2ADH,
(117)
35
35
since f f4) & || f-llz s AVH DVH ADH.
By union bound argument know with probability 1 35/4, the term maxfes(a) E(f) is bounded by D2 log(4)((a))/30) + 2ADH.
For E(f) E(f), we have
E f - (f)
- 11 fa - fo +2 +2 -F)
-
$ ( f.f+f+ +2(1Z
+ + ldll)) | f-
Note that by definition of / holds that
| S SOVH.
Together with 11 I1fAllz & DVH, bound E(f) E(f) as
E ( ( (J) < 2DaH (2AHH + D 2H log (3H + 1)/6) aVH H
< 2D + A) oHl + aHl log (3H + 1)/0).
Here we take advantage of the D/2 Subbuaussnnnn property of 2 that with probability 1 38/4 for any episode k.
D
D /2H log (3 + 1)/6).
12 S
/2 log (
(118)
2
2
Merging Eqn.
117 and 118) with another union bound, we get that with probability 1 - for any
episode k.
| |/--1l1 2D2 log (2Na/8) 4ADH + 2al1 (2(D + A) 22/2log (6/l + 11/8)
where No the (a, |loo)- covering number of F. Finally, we set a = 1/H and
8 2D2 log (2N(F, 1/H)) + 4ADH + +4 4D 4D 1)/8).
(119)
It holds that O U4 for any 1 k K. with probability 1 1 5/4 1/4-3 36/4 = 1 8 long as V happens. Since V happens with probability 6, we know the optimistic property holds with probability 1 28.
31

---

Published as a conference paper at ICLR 2023
F.3 PROOF OF LEMMA 8
Proof of Lemma
g
Define e (A LCA) - then Meee Lili. + te. Further, we
know ||e
2
Ro 72 X2 under event and Assumption 3
By the decomposition rule for f
and f (Eqn. 111
114 ) we know
16( x. u. θ
(120)
- 2e T C' (iCAE + LCBu = (1-ič) (Ax Bu))
(121)
t (P
(122)
+2ee AT Q (CARfi + +CBu) e VCTQQAA..
(123)
Note that X2 = =0(Vi vp) log H),, thereby there exists constant A such that
[6(('' æ, u, θ) fe(T iz, 6) s o (ma(1-22)'6 - r2) + +p) p) log 11.
(124)
G THE INTRINSIC MODEL COMPLEXITY ög
In this section, we show how large the intrinsic model complexity 8g will be for different simulator classes & An important message is that og does NOT have any polynomial dependency on H.
G.1 GENERAL SIMULATOR CLASS
Without further structures, we can show that & bounded by
dz Ô (np² (n + + p)(n + p) + p)
(125)
due to Proposition 2 and the fact that || S D = Ö(n p).
Proposition 2. Under Assumption 7 2 the 1/H-Eluder dimension of F is bounded by
dimg (F,1/H) = Ô (p* p2m +p² p²m²).
(126)
Proof. The bound on Eluder dimension mainly comes from the fact that fe(r', x., u, θ) can be regarded a linear function between features of θ and features of Ô. We use the "feature" of system θ to represent a quantity that only depends on θ (independent from é) and vice versa. well-known that the linear function class has bounded Eluder dimension. We formalize this idea below.
x, u, θ) X and O E In the proof of Lemma we know that for any (T',I,
fe(T', 2,, θ) (ICAESLS - +LCBu + (1 (1-1C)
(iCA-
LC) ( (Ax + Bu)) T (8 (T))x (127)
(ICAM + LCBu+ (1 (I-ic) (Bx+Bu))
Bu))
(128)
+ (CAE + CBB) @ (CCASS + CBB)
(129)
+ trace (IT(P- (TT(P-CTQC) ( + +1) + trace (Q (CECT++ +1)),
(130)
dd Denote the input as (7' xx, u, ②) E X, and define three feature mappings Ç X - Raxn.
X + R and & X + Rexp such that
<(E) = P p- 1- QÒO
(131)
s(E) = (1 (I- (Ax+ Bu)
(132)
((E) L. (T((E))+O +
(133)
32

---

Published as a conference paper at ICLR 2023
Then move to further write f as
fe(E) = (ÉCA#QEE + LCBu+ ICBu+ S(B) (iCAR + LCBu+
+ ((E))
(134)
+ (CAbbii + ) @(CAEiIL + CBu) + trace trace(((F) (CECT + +1))
(135)
By definition,
fi (A- ((A
(I- (C)
Lyn-
(136)
Define two series of feature mappings P Pg for S S on P : Rpxx and
Py : 6 + R2xP such that
2 = CA(A- LCA) - (1 LC)B
(137)
2 (+) CA(A- LCA)" L
Consider the terms in Eqn. 134 and 135 each term be written as the inner product of a feature of and feature of E. For example, trace ($())CEECT T)) is the inner product ((F)) (feature of E) and CΣC + (feature of θ, since it only depends on θ). As more complicated example, we check (LCAA))).)) ((E)))) ((,
(LCAA)ROO) ((E)LCAi
(138)
Σ (1) + (0) ) ET(EEE (0)m +1 (
(139)
Note that (0) and pjj (0) only depends on θ (so they can be regarded as feature of o), where Ue-s: M1-++1, L [ only depends on E. Consider any S $1, 82 in the summation, we pick the term below as an example:
(5 (9) (0) LT (CE
(140)
= (x) @ t. (9), vec(L ((E)L) x vec(u- "I uT,r)))
(141)
Here @ denotes the Kronecker product between two matrices, vec(X) for X Raxb denotes the vectorization matrix X (i.e., vxc(X) = [X1 X21 Xa1 X12 Xail E Rab), and (;:) is the inner product. In this way, decompose the term (140) the inner product of ddmeensina feature of θ (i.e., s2 (p)(@)) ()) 8 o. (0)) and a p²m dimensionall feature of E (i.e..
vec(īT ((E)L) x vec(u,-,, ),
We then observe that such decomposition is valid for any 1 < $1, S 1. Therefore, we can decompose each term in Eqn. (134) and (I35) as the inner product of features of O and E. Gathering all these features as the aggregated feature mapping fea, for θ and feaz for E, we have
fe(E) (fea) (9), feag (E)).
(142)
is not hard to observe that the dimension of aggregated feature mappings is bounded by dim(fear(e)) = dim dim (E) = (p* + + m + p² m²
(143)
since = (log( Hn + Hp)).
Note the ||fcaj ((taa(@)) (0) [cayy E| are both upper bounded by the domain of E X and O e 6, then Proposition 2 of Osband & Van Roy (2014) shows that
dimg (F, 1/H] Ô (p' + p2m +p p²m²²)
(144)
33

---

Published as a conference paper at ICLR 2023
Proposition 3. Under Assumptions L and the logarithmic Hoovering number of F is bounded by
log (F, (F. 1/H) = Ô (n² + nm + mp)
(145)
Proof. Under Assumption the spectral norm of the system dynamics of θ C)) & is bounded by ||Al2 B 2, 2 < Ns. Therefore, we can construct an co-net Gr, (6) such that for any θ (A, B, C), there exists θ (A, B, C) E & satisfying max(IIA All,, || Bl12, ||C Cll2) S cp- By classic theory, we know (ge (8) & O((1 + 2/TNs/<o)" (/mm//tt)(+ To see this, observe that || S -|I-IIr S ymin(n, m)ll 2/2 for any n x m matrix, so we can reduce the e-cover with respect to the 12- 12-norm to the E-cover with respect to the Frobenius norm. To show the covering number of F, we check the gap fife - fe olo
By Lemma 3.1 of Lale al. (2020c), we know that for small enough eo there exists instance depen- dent constants Cy and CL such that
- - E S CrEE,
1 1-122 S CLEO,
(146)
where Σ E(+), L()). The constant Cg slightly different from Lemma 3.1 of their paper, because we do not assume M def A - ALC is contractible (i.e., ||M]] < 1). Rather we know M is (K2, -st-onyyy stable. Therefore, the linear mapping 7 _ + - M is invertible with IT- 122 < /g/(21g - -ン2) according to Lemma B.4 of Simchowitz & Foster (2020). As result, we can set C3 by replacing the 1/(1 v²) term in the original constant of Lale et al. 2020c Lemma 3.1) by K2/ (2 72)
For any E = (r', I. u, )) X, it is desired to compute the difference (fe (E)) As first step, we show the difference between Ei and sc + Note that for any 1 1 s S I,
(IAA LCA) (Ā - LCA)= 211 S (s 1)m3( - 72)*
N + 2N).N)o (147)
This is because
2-2 A 1011 A 1 A (A A) A
6-2
(148)
for A def A LCA, A de A LČA, where
| All (1 + N3 + 2N, Ns) |A|,,,11A|: S n2(11 72).
Similarly we can bound [B LCB) (B I.. Follow the decomposition rule in Eqn. 136) and observe that ||0c= 2 S U, 11- ||tt0+1122 S y for S < 1, we have
- - 4 $ $ CzCu.
(149)
where Cn is instance dependent constant (also depends on Cx,, Cr.). By Eqn. (34) and 135). it holds that
So(E) - (E = trace (Ø(E) (CECT- C.CT)) + Diff, + Difl,,
(150)
where
(CARS + +CBu) T
Diff;
Q (CAAfir CBu)
(151)
-(CARi + CBU) Q @CCAES + CBu)
(152)
Diff, (I.CAR + i.BB)) ((F) (i.AAffr i.C.B)
(153)
- - + LCBu) ((E) (iCCE + LCBu).
(154)
34

---

Published as a conference paper at ICLR 2023
Checking each term in Diff, and Diff2, conclude that there exists instance dependent constant Ca1, Ca2 such that
Dif S Caiso; Diifll S Ca2co-
Note that |CECT - CECTl 112 (2NgNy + Ng and [[ S N2 + -NNNN) + NN, we have
Ife(E) - fE( = trace ($(E) (CECT CECT)) Diff, Diftz S Cyoo,
(155)
where
Cj = p| (2N + NN) + Ca1 + Can.
def
This means
Ie lolloo S Cyea-
Therefore, the subset (fs 6 E g (8)} forms Cyvo-covering set of F. Finally, if suffices to set to = - HH1 to induce a 1/ H/ooveriin set of
(F,1//H) (( +
- (1
(156)
which finishes the proof.
G.2 LOW-RANK SIMULATOR CLASS
In many sim-to-real tasks, there are only few control parameters that affect the dynamics in the simulator class & (see e.g.. Table of OpenAl et al. (2018). The number of control parameters is often constant that independent of the dimension of the task. This means our simulator class & a low-rank class in these scenarios:
= (0(t,,t2,..... tx) (f1, t2..,,)... E T),
where f2, th represent & control parameters, T is the domain of control parameters. The dynamics of simulator @ only depends on these control parameters (1, l2...,
common situation that (2, (x) is continuous function of (I1, fg). For example, it is continuous function when the control parameters are physical parameters like friction co- efficients, damping coefficients. simple example when θ linear combination of base simulators:
= (A, = Σ 40.
(157)
where θ = (A,, B,, C.) is a fixed base simulator. This can be achieved we approximate the effect of control parameters with some linear mappings on the states Zz. We can set different values of control parameters t,,... t to generate new simulators.
In such a continuous low rank class, the log covering number V(F,1/H) will reduce to only Ö(k) long θ is continuous with respect the control parameters. It is straightforward to this by
checking the proof of Proposition 3 Unfortunately. it is unclear whether the Eluder dimension of such a continuous low-rank class will be smaller due the existence of the Kalman gain matrix L.
Overall, the intrinsic model complexity óg will decrease from Ö(np² m () +p) p)²) to at most
Ö (m + Pn (1m++1 x)
for small constant k.
G.3 LOW-RANK SIMULATOR CLASS WITH REAL DATA
Many works studying sim-to-real transfer also fine-tune the simulated policy with few real data on the real-world model (Toiin et al., 2017 Rusu et al.) 2017). Moreover, the observations are usually the perturbed input states with observation noises introduced by vision inputs (e.g.. from the cameras) (Tobin et al. (017)) Peng et al.) 2018 OpenAl et al.) 2018). This means the observation Vi equals 34 2, for random noise 2,, without any linear transformation C. With these real data
35

---

Published as a conference paper at ICLR 2023
and noisy observations of the state, estimate the steady-state covariance matrix Σ(e") with random actions since it is independent of the policy! The intrinsic complexity the simulator set will be further reduced for this low-rank simulator set (e.g., the simulator set defined by Eqn. (157) combined with real data.
In such low rank simulator classes, know that Σ(0") is fixed estimator Σ computed with noisy observations yt 2₁ + 24. By definition we know L( also fixed as L + +)= Therefore, the Kalman dynamics matrix A LCA A LA belongs to k-dimensional space A lies in A dimensional space. As result, the dimension of feature mappings PP (11, t2...., tx); sg (t1,t2,..... t2..... tx) (Eqn. 137 reduces to ((. The Eluder dimension this
low rank simulator class reduces ( Ö(K* "ok""og" log2* (H)) for small constant A:
Therefore, the intrinsic model complexity 5g for a low-rank simulator class fine-tuned with real data
Ó((n + p) log 2gg (H)),
which implies that the robust adversarial training algorithms are very powerful with a small sim-to- real gap in such simulator classes.
H PROOF OF THEOREM
Throughout this proof, we assume H is sufficiently large and omit some (instacc-deepnddent constants because we focus on the dependency of H. Note that LQR a special case of LQG in the sense that the learner can observe the hidden state in LQR, it suffices to consider the case where is a set of LQRs. Since C = / in LQRs, Assumption 3 holds naturally. Let (A',, B*) be the parameters satisfying Assumptions and 2 and 6 = {(A, B) ||A-A*||>> I 17-1/2 where H is sufficiently large, by the same perturbation analysis in Simchowitz & Foster 2020 Appendix B), we have that all @ E & satisfy Assumptions and Fix policy we have
Proof of Theorem 2
| [x {).. Choosing
BES (0) 2 min max ( V oe
(158)
Since we can treat history-dependent policy as an algorithm, the lower bound in Simchowitz & Foster (2020) Corollary 1) implies that
min max V (0) [*)) 2 Q(VH). OES
(159)
Notably, Simchowitz & Foster (2020) only imposes the strongly stable assumption, which is weaker than our assumption, but their proof (Lemma B.7 in SSicchwitz & Foster (2020)) still holds under assumptions. Combining (158) and (159) conclude the proof of Theorem
36


Reviews:
[{"review_id": "te4tff8qJyF", "reviewer": "Reviewer_YiUA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the behavior of the sim-to-real gap for partially observed linear-Gaussian systems with quadratic cost. The authors formalize the sim-to-real gap as the finite-horizon minimax regret of a policy across a set of plausible simulators. The main argument is that the finite-horizon minimax regret can be bounded by a horizon-adjusted infinite-horizon regret up to an additive constant, hence it suffices to show that the infinite-horizon regret  minimization problem can be solved with bounded regret. The authors show this using an optimistic policy. There are, however, some number of technicalities to be taken care of along the way.", "summary_of_the_review": "I would generally recommend acceptance of this paper due to the novelty of the formalization and its bound.", "strength_and_weaknesses": "Strengths:\n* To the best of my understanding this is a sensible argument and there seems to be non-trivial novelty in this derivation.\n\nWeaknesses:\n* The paper is very dense and hard to unpack. Perhaps some of the technical details can be relegated to the appendix, giving more space for the main conceptual flow. Especially, for example, if the technical restrictions of the systems class are standard fare, they don't need to consume space in the main text given that they're not involved in any of the novel arguments. \n* There are some writing nits, such as the fact that Gaussian is not capitalized in \"linear quadratic gaussian\" but is capitalized in \"Gaussian distribution\". As a proper name, Gaussian needs to be capitalized in every situation. There are also some tautologies, e.g.  \"We follow\nChen et al. (2021) to present a formal formulation\" (as opposed to an informal formulation). Generally, the writing would benefit from some clean-up.\n* The preliminaries section seems to be very close to that of Lale's work. There are a number of common sentences. I do not believe this was done in bad faith, but the authors should consider rewriting this to avoid possible accusations of (auto)plagiarism.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "frDWSwV5xyN", "reviewer": "Reviewer_86xP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies provable sim-to-real transfer in the linear quadratic Gaussian (LQG) setting. The paper proposes a robust learning algorithm for the simulation part and derives provable guarantees without assuming access to real world data. In order to obtain the guarantees, the authors propose a novel history clipping technique that improves the bound significantly.", "summary_of_the_review": "Overall, I believe the submission offers a novel contribution to the field of sim-to-real transfer. The paper is not perfect and the presentation could certainly be improved. Nevertheless to me the pros outweigh the cons.", "strength_and_weaknesses": "Strength\n- The paper is theoretically sound and the proofs appear to be correct.\n- The paper is well-motivated by a practical need to extend sim-to-real analysis to continuous and partially observable regimes.\n\nWeakness\n- Section 4 took many reads to fully appreciate. Particularly, while section 4.1 is reasonable and the reduction technique is standard, as the authors argued, it was not immediately clear why Algorithm 1 (LQG-VTR) is necessary for proving the properties of $\\pi_{RT}$ defined in Definition 1. Since the section is the \"meat\" of the paper, so to speak, providing more intuition and insights into the analytical techniques could make the work easier to digest.\n- Some of the parts of the paper are not self contained. For instance, in Appendix C, multiple references to the algorithms and results in Lale et al (2021) are made without providing sufficient discussion on why the results in Lale et al (2021) are useful or intuition on what purposes these references serve, which makes it harder to properly assess the soundness of the paper. A further revision could greatly ameliorate this weakness.\n\n--------- Post Rebuttal Update --------------\n\nThank the authors for their commitment to making the paper easier to digest. I would like to keep my score as is.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UllyDH1fmZ_", "reviewer": "Reviewer_rBWA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper considers sim-to-real transfer and approaches this problem from a theoretical perspective. It uses LQG to model the system dynamics and establishes the upper and lower bounds on the sim-to-real gap. A new algorithm is also developed for transfer learning. ", "summary_of_the_review": "The paper provides a theoretical analysis for sim-to-real transfer. I feel the paper needs substantial revision to better highlight its proposed algorithm. In addition, the theoretical analysis can also be strengthened. ", "strength_and_weaknesses": "Strengths:\n\n1. Sim-to-real transfer is an important problem in practice. Nonetheless, its theoretical analysis is lacking. The paper contributes to this less explored area. \n\n2. The upper and lower bounds on the sim-to-real gap are novel, to my knowledge. \n\n3. A detailed algorithm is provided to conduct sim-to-real transfer. \n\nSome suggestions:\n\n1. Sim-to-real transfer is important in many real-world applications. This problem is application driven. However, I am not sure if the upper and lower error bounds of the sim-to-real gap would offer practitioners any useful insight when conducting transfer learning. The author(s) might want to heavily revised the article to better discuss the insights you obtained that are useful to practical situations. \n\n2. According to my understand, the paper borrows some techniques in minimax learning theory and seems to be an application of these techniques to sim-to-real transfer. The author(s) might want to discuss whether such an application is challenging and if the established results are sufficiently novel beyond the existing literature. \n\n3. $\\pi_{RT}$ is defined in a population level. It would be better if more details can be provided on how to obtain this oracle policy. In addition, the definition does not involve the sample size used for training. The theoretical results in Theorems 1 & 2 seem to be asymptotic. It also did not involve many other practically important parameters (e.g., the size of training data).\n\n4. Algorithm 1 shall be highlighted in the paper instead of putting it in Section 4. The paper would benefit from a detailed discussion on the advances of the this algorithm beyond the existing literature. \n\n5. The LQG model assumption is not very realistic in real applications. In the introduction, the author(s) mentioned that the partial observability was motivated by the OpenAI environments. However, do these environments satisfy the LQG model assumption?\n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster