Continuous Control with Contexts, Provably
Authors: Simon Du
Mengdi Wang
Ruosong Wang
Lin F. Yang
Venue:  (2020)
Keywords: continuous control
learning
context

Abstract: A fundamental challenge in artificially intelligence is to build an agent that generalizes and adapts to unseen environments. A common strategy is to build a decoder that takes a context of the unseen new environment and generates a policy. The current paper studies how to build a decoder for the fundamental continuous control environment, linear quadratic regulator (LQR), which can model a wide range of real world physical environments. We present a simple algorithm for this problem, which uses upper confidence bound (UCB) to refine the estimate of the decoder and balance the exploration-exploitation trade-off. Theoretically, our algorithm enjoys a $\widetilde{O}\left(\sqrt{T}\right)$ regret bound in the online setting where $T$ is the number of environments the agent played. This also implies after playing $\widetilde{O}\left(1/\epsilon^2\right)$ environments, the agent is able to transfer the learned knowledge to obtain an $\epsilon$-suboptimal policy for an unseen environment. To our knowledge, this is first provably efficient algorithm to build a decoder in the continuous control setting. While our main focus is theoretical, we also present experiments that demonstrate the effectiveness of our algorithm.

Under review as a conference paper at ICLR 2020
PROVABLY EFFICIENT QUADRATIC REGULATOR
CONTEXTUAL
LINEAR
Anonymous authors Paper under double-blind review
ABSTRACT
A fundamental challenge in artificially intelligence is to build an agent that gen- eralizes and adapts to unseen environments. A common strategy to build a de- coder that takes a context of the unseen new environment and generates policy. The current paper studies how to build a decoder for the fundamental continuous control environment, linear quadratic regulator (LQR), which can model wide range of real world physical environments. We present simple algorithm for this problem, which uses upper confidence bound (UCB) refine the estimate of the decoder and balance the exploration-exploiiaa
trade-off. Theoretically, our al- gorithm enjoys a Ō (VT) regret bound the online setting where T is the num-
ber of environments the agent played. This also implies after playing Ô (1/e²) environments, the agent is able to transfer the learned knowledge to obtain an c-suboptimal policy for unseen environment. To our knowledge, this is first provably efficient algorithm to build a decoder in the continuous control setting. While our main focus is theoretical, also present experiments that demonstrate the effectiveness of our algorithm.
INTRODUCTION
Humans are able solve new task without any training based on previous experience in similar tasks. Our intelligent agent should be able do the same, learning from previous experience, adapting to the new ones and improving the performance as the agent gains more experience. This challenging problem from classical supervised learning methods.
need to design adaptation mechanism which is fundamentally different
A common approach is to build decoder so that once the agent sees a description of new task, ie., the context of the new task, the decoder turns the context into a succinct representation of the new task, based which the agent is able design policy to solve the task. Note this procedure resembles how human solves a new task. For example, if a human wants to push an object a table, the human first the object and the table (context). Then, in his/her mind, the context becomes a representation of this task, e.g., sense of weight of the object. Based on this representation, the human can easily reason about how much force to exert on the object.
This general approach has been applied in practice. For example, Wu et al. (2018) studied the visual navigation task and built a Bayesian model that takes the context of new environments and outputs the policy that enables the agent to navigate. Killian et al. (2016) used this approach to develop personalized medicine policies for HIV treatment.
While this is promising approach, currently we only have limited theoretical understanding. The approach can formulated Contextual Markov Decision Process (CMDP) framework (Hallak et al. 2015). Recently, there is a line of work gave provable guarantees for CMDP (Abbasi- Yadkori & Neu 2014 Hallak et al. 2015 Dann et al.) 2018 Modi et al. 2018 Modi & Tewari 2019). These work all studied tabular MDPs, and use function approximation, e.g., linear functions, generalized linear models, etc, to model the mapping from the context to the probability transition matrix. A major drawback of these work is that they are restricted to the tabular setting and thus only deal with discrete environments. Therefore, they can hardly model real-world continuous control tasks, like the task of pushsing an object described above. A natural question arises:

---

Under review as a conference paper at ICLR 2020
Can design provably efficient decoder for continuous control problems?
In this paper, make important step towards answering this question. We study the fundamental setting in continuous control, linear quadratic regulator (LQR). LQR is arguably the most widely used framework in continuous control, LQR easily models real world physical phenomena, e.g.. the pushing object task we described earlier. We propose a new algorithm that builds a decoder, so that for a new LQR task, the decoder takes LQR's context and outputs a representation based on which the agent can easily infer a near-optimal policy for new continuous control tasks. In the training phase, build the decoder via sequence of LQRs (in an online fashion) with unknown parameters. For each new task, we first use the current decoder to build the representation of this task, infer policy based on this representation and use this policy do control for this episode. There are two crucial components in our algorithm. First, after each episode, we will refine the estimate of the decoder based on the observations from this episode. Second, upper confidence bound (UCB) estimator of the decoder to build the representation so that the agent can perform near-optimal trade-off between exploration and exploitation. In this way, we provably show the decoder improves the performance it experiences more training tasks. Formally, show our algorithm enjoys
crucial use a
VT regret (the difference between the cumulative rewards of our algorithm and the unknown optimal policy on every seen environment) bound in the online setting- Moreover, the algorithm is able to obtain an e-suboptimal policy for an unseen LQR environment after playing Ô 3 environments. To our knowledge, this is the first provably efficient algorithm that builds a decoder for continuous control environments. Empirically, we simulate several physical environments to illustrate the effectiveness of our algorithm.
Organization This paper organized as follows. In Section 2 we discuss related work. In Section 3 we formally describe the problem setup. In Section we present our algorithm and its theorefical guarantees. Section we use simulation on physical environments to demonstrate the effectiveness of our approach. We conclude in Section 6 and defer most technical proof's to the appendix.
2 RELATED WORK
Recently there a large body of literature focusing on learning for control in LQR systems. The first work we are aware of is |Fiechter (1997) which studies the sample complexity of LQR in the offline setting. For the online setting, where the agent can only obtain the next state starting from the & Szepesvári (201T) which studies the learning problem in the infinite-horizor average-case cost setting. Later on, a sequence of papers (Tu & Recht. 2017: Dean et al. 2017]: 2018 Tu & Rechi 2018 Abbasi-
present state, the first near-optimal regret bound (Ö(vT)) is due to Abbasi-
Yadkori al. 2018 Cohen al. 2019) studied this problem in similar settings, improved efficiency of the algorithms and characterized the gap between model-free and model- approaches.
Building an agent that quickly adapts new environment has received increasing interest in the machine learning community. TTylor & Stone (2009) gave summary for the literature status before 2009. More recently, a sequence of theory papers Lehnert & Littman| (2018): Spector Belongie 2018 Abel et al. (2018); Lehnert et al. (2019) studied the transferability of reward knowledge, state-abstraction, and model features for Markov decision processes. Please also refer to references in paper cited above for more details. There are also some experimental works, c.g.. (Santara et al. (2019); Yu et al.) (2018); WWu et al.] (2018); Gaamrian Goldberg (2018), studying how to transfer knowledge from seen tasks unseen tasks. Nevertheless, we not aware of any study on how to provably perform continuous control with contexts.
PRELIMINARIES
Notations.
We begin by introducing necessary notations. We write [h] to denote the set {L..... .......,A h). We use la E dxd to denote the d-dimensional identity matrix. We use 0axæ to represent the all- zero matrix in dxxd', If it is clear from the context, omit the subscript d x d'. Let I1-112 denote the Fuclidean norm of a vector in Rd. For symmetric matrix A, let ||Al|op denote its operator
2

---

Under review as a conference paper at ICLR 2020
norm and A (A) denote its i-th eigenvalue. Throughout the paper, all sets are multisets, i.e., single element can appear multiple times.
Finite Horizon Linear Quadratic Regulator. We now formally define the finite horizon Linear Quadratic Regulator (LQR) problem. In the LQR problem, there a state space X C IR and a closed action space U C Rd Suppose we always start from the initial state 2 = Finit. E X and play for H steps. Then at state 2h X, if an action Wp. 4 is played, the next state given by
1h+1 Am, Bug + wh+1,
(1)
where A, B matrices of proper dimension and Wh+11 is a zero-mean random vector. Here A, B can be viewed as the succinct representation of this LQR because as will be explained below, given A, B, we can easily infer the optimal policy for this LQR. For simplicity, we additionally denote
M [A, B], and y/ [=7,, " E IRd+-'"
Now the state transition can be rewritten 24+1 Myn Wh+11 - For the ease of presentation, assume that the covariance matrix noise vector wh+1 is E(w,+1 Wh = la. Our analysis follows similarly if the covariance matrix is not Ia (see e.g. Remark of Abbasi- Yadkori & Szepesvári 2011 ) After each step, the player receives an immediate cost x, QA + U2 R2 up, where Qn. Rş positive definite (PD) matrices of proper dimensions. Throughout the paper, we assume the agent knows Qn and R2, for all h. At a terminal state IH there is no action to be played, and the player receives terminal cost Q HTH where QH is PD matrix of proper dimension, The goal of the player is to find a policy π : (X x U)) x X + U, which is a function that maps the trajectory {(x,, } L {2x} to the next action uh, such that the following objectives are minimized:
JR( = E F (
H-1
Σ
Ty Qur un RR ZzQQEH
Th = NEIHi
where the action Uh is given by tion is over the randomness of w/ and
x [ u1), (x2, u2)...... (IΛ-1, un 11 Fn), and the expecta-
It is well-known that the optimal policy x² is Markovian Puterman 2014). i.e., it only depends on the present state. For an unconstrained action space U, we have
Vx E X, h E [] <x,,, (,
where M [A. B] and (MM is matrix that will be defined shortly. It also known (see e.g. Bertsekas (1966) that the optimal cost function (z) == JJ (x) is given by
J=, = T PR(M)x (M(M) inf (M,,
(2)
where
Qn + AT PM)4 P + B Pa+ (M)B) P QH
(M)A
h < H
Pa(M)
h H1
and
< H (M+)(M) + E [WTT]] Ph+1 (M)wn+1)
(MM
10
h = H
We now define Kx(M)
(x(M) -(R + PM+ IM)
(4)
Note that the optimal value Equation (2) satisfies Bellman equations,
vh E H - 1]: x) x. T n (x)) RAT (x)
"xx"(()) + B[Jht1 (Ax + BT Bx)(x) + w)]
and
vh. E H 1]: a),, x Thx + min B[u R. + Than (Ax + Bu +w)]
Now we have shown that if we given A and B. then this paper, we deal with setting where and B are unknown and we need to use decoder to decode A and B from the contexts of the current LQR, specified below.
obtain the optimal policy directly. In
3

---

Under review as a conference paper at ICLR 2020
Learning to Control LQR with Contexts In the continuous control with contexts setting, in each episode we observe a context
(C,
where l is distribution RRxd TR'' xd' The context [C, D] encodes the information of the environment. Formally, the representation ([A, B)) of this environment can be decoded from the context via a decoding matrix θ, E Rdx((++');
C
Opxd
A, B| O
(5)
Op'xe
D
From now on, emphasize that the representation of LQR can be decoded from O. write
C
Opxd
Me..c,D == :=
= [A, B}.
(6)
Op'xd
D
If it is clear from the context, we ignore [C; D) for notational simplicity. Note the optimal decoder +, unknown to the agent and the goal to learn O, from contexts and interactions with the environment. Below we formally define the problem that we study.
Definition 3.1 (Contextual Transfer Learning Problem), Build an agent that plays on K LQR games (one trajectory per game) with context pairs {(C(), D("),, (C(2), D(2)), (C(K), D(K))} μs for some integer K 2 O such that for another new context pair (C, D) ~ the agent outputs policy nt based on (C, D) which satisfies
EJ (Me.,c.D 21) - JM.,,. 5
for some given target accuracy > O.
Here K is the sample complexity which ideally scales polynomially with and prepeem-de parameters. The performance of the agent can also be measured by regret, as defined below.
Regret (eegret(KH) (KH)
Σ J pW),, 21) - Jj (M),,,,.,. (ws,
where (K) is the policy played at episode k by the agent. This quantity measurse the sub-optimality of policies the agent played in the first K episodes.
Remark 3.1. We consider matrix-type linear maps from context the representation only for sake of presentation. Our algorithm and analysis can be readily extended to other linear maps, e.g., (A. f(C, D) for some unknown linear function f.
MAIN ALGORITHM
In this section, we first describe the algorithm and then present its sample complexity guarantees. Since the decoder is linear, a straightforward algorithm is first to estimate [A, B) using the trajectory from the single episode with system identification techniques (Mehra 1974). and then to use linear regression to estimate the mapping from (C, D) to (A, B). However, this naive algorithm has two drawbacks. First, estimating (A, B) accurately requires long horizon. However, in setup, we do not have any restrictions on the horizon. To fix this, we stack contexts and observations to construct more direct estimate on the decoder (ef. Equation equation 3 Second, in order to achieve VT-type regret guarantee, one needs to balance exploration and exploitation carefully, but the naive algorithm does not have such an component. Our algorithm uses UCB to construct confidence set which helps balance exploration and exploitation.
Algorithm We describe the high-level idea of the algorithm below. The agent maintains de- coder that maps the context (C, D) to the representation (A, B). We denote ((k) the decoder at the k-th episode. Initially, know nothing about O., so initialize our decoder by setting ((1) dd At the k-th episode, the agent plays policy (()) and in each time step h [H -1,, collects data
(K)
Th W
-
Dik)
Uh
4

---

Under review as a conference paper at ICLR 2020
Algorithm Linear Continuous Control with Contexts
1: Input Total number of episodes K;
2: Initialize ( -- 0 Rd Vil) 12p,2p, W t e Roxdd
for episode & = 1.2..... K do
Let == #init, v(++1) <- V(k), w((+2) w(k);
5: Obtain context [C(*), _D( ~ μi
Solve the present policy:
6 (k) arg min Ji (M x1 agc(e)
(10)
7: where JI is given by Equation and ((() is defined in Equation 11
8:
for stage h 1, 1,2..... H1
do
9:
Let the current state be "
10:
where Ka. is defined in Equation 4 Play action un Ki (MM(M ((t,,, 22/
Obtain the next state (16)
((A)
(k)
12:
(k) Let
((A) un
13:
Update: (k41) + v(k+1) + (8) (K)_ (N)T
2b. (1)
14:
Update: ((++1) + w(++1) + 2/ (1++1)
Compute (k+1)T <- (v(N*t) w(b+1))
15:
16:
output (k) where is chosen from K] uniformly random.
(8)
where 2/ can viewed as the context regularized observation. We now describe how to obtain policy x (R), We first solve the following optimization problem,
e arg min Ji pa, eceik)
where Jí is given by Equation 2 and the confidence set ((k) will be defined shortly. C(k) represents our confidence region on +.. Since we choose the one that minimizes the cost, this represents the principle "optimism in the face of uncertainty" and is the key balance exploration and exploitation which will be more clear in the proof. Notice that the above optimization problem is polynomial optimization problem. Then the policy given by
(b) Th
(z) (z)
KA (M)()) where (k) Mens, cu,, (4).
((k) 0
D
and K2 is given by Equation formulation to update decoder
After episode & [K], we use the following ridge regression
( = ((ritt)) -I w((tt))
(8)
where
k
H-1
b
#-1
v(++)= -
Σ
Σ
(k')
(R')T 2h
and ((k+1)_
Σ
(K')T
h-1
After playing K episodes, the algorithm outputs by picking one from (θ(k) ]Æee uniformly at random. Now for task with its context, learned policy map is given by:
TcDD((x) = KA o
C
0
VC, D ~ p, E X H -
(9)
The formal algorithm is presented in Algorithm
5

---

Under review as a conference paper at ICLR 2020
4.1 ALGORITHM ANALYSIS
To present the analysis of the algorithm, we first introduce some assumptions.
Assumption 4.1. The contexts and LQR satisfy the following properties.
vh E [H] (M)22 S Cq for some parameter cq 0.
||O||F S ce:
vh E [2, HJ i [d] Iwall2 < and Vy > 0, E(ywA,1] S 2 2))
Va E X, E,, D) E supp(u): ||Cx|2+ Dull S. c ||]| + | S E.
V)C, supp(u), E [H]: Kn. (M...... E.
where co, Cws are some positive parameters.
The first assumption is standard to ensure controllability. The second a regularity condition on the optimal decoder . The third assumption imposes almost sure boundedness of the noise The fourth assumption is regularity condition on the observation. The last assumption guarantees the optimal controller for the unconstrained I.QR problem is realizable in our control set U. Given these assumptions, We are now ready to define confidence set (()) as follows.
(2() = tr[(O- - (
B(R)
and vh E [M] (C, D) E supp(u), || (M.,c.))) sa
(11)
where Ph is given by Equation 3 and (()) defined as follows.
8(k)
(co + Gw 2d( log d log(1 + kHc2/p)/2 log 5-1)
(12)
We remark that ((k) is changing at every episode because we update ( and (kk) at every episode. The size ((R) is decreasing because ((k) strictly increasing at every episode.
With the above assumptions, the guarantee of Algorithm I formally presented in the next theorem. Theorem 4.1. Suppose we run Algorithm for
K2 HHa.pos dp log (dKK-1)
episodes. for some parameter CH..ay...oo.c depending polynomially H, Cg. Czs co, Cw. Then with probability least - 8, we have for TCDD be defined in Equation
E
IE ((.CC(,,,))D)))..)) JT((0.C,.. ( Se.
(13)
(C,Dimplac..
Theorem 13 states after playing polynomial number of episodes, our agent can learn a decoder θ such that given a new LQR with contexts (C, D), this decoder can turns the contexts into a near- optimal policy TC.D without any training on the new LQR. Note this the desired agent we want to build described in the introduction. We emphasize again that this is the first provably efficient algorithm that builds a decoder for continuous control environments.
Remark 4.1. Via similar analysis, it is easy to show that if the output θ is picked uniformly at random from (0()) the policy achieves similar accuracy.
In fact, Theorem 4.1 is implies by the following regret bound of our algorithm. Proposition 4.1. With probability at least - -5,
Regret ( S en dd/2p 22 (dK KHH.
where en is constant depending only polynomially H, Cq. Cz, CM, Cw-
By the definition of regret, this proposition justifies that the performance of the agent actually im- proves as it sees environment.

---

Under review as a conference paper at ICLR 2020
5 EXPERIMENTS
In this section, we validate the effectiveness of our algorithm via numerical simulations.
path-following task. In this task, we given trajectory zi 2 ................................ z E IR2 Our goal is to exert forces W1, W2,.... Um E R on objects with different (measurable) masses to minimize the total squared distance Σ || 2 + ||u/ Each state Th (ziir, E I is vector whose first two dimensions represent the current position and the last two dimension represent the current velocity. In each stage h, we may exert force un E IR² on the object, which produces accelerations E R2
We perform experiments
The dynamics of the system can be described as
21+1
2h + Ch Uh+1 k Un + un un/m
(14)
where 0 < A S. 1 is the decay rate of velocity induced by resistance. In our setting, the decay rate of velocity 1: is fixed (encoded O.), where the mass of the object m is drawn from the uniform distribution over [0.1. [ In our experiments,
set the noise vector 1. in the dynamics of the LQR system (ef. Equation ! to be a Gaussian random vector with zero mean and covariance 10- In each episode, receive an object with mass m where m draw from the uniform distribution over [0.1, 10). train one trajectory using that object, and the goal is to recover the physical law described in Equation [4|so so that our model can deal with objects with unseen mass m. Please see Appendix for the concrete value of O., Q and R and the distribution of C' and D.
use 100 different masses as training masses (fixed among all experiments), and use 100 different masses as test masses (again fixed among all experiments). All the training masses and test masses are drawn from the uniform distribution over [0.1, 10). We implement a practical version of Algorithm I In particular, instead of solving the optimization problem in Equa- tion 10 exactly, we sample 100 different θ from C(k) uniformly at random, and choose the θ which minimizes the objective function. Moreover, instead of using the theoretical bound for ,3() in Equa-
In our experiments,
tion 12 we treat ((4) as a tunable parameter and set g(() = 10 our experiments to encourage exploration at early stage of the algorithm. We two different metrics to measure the accuracy of the learned model. First, we use ||0; OxILP where θ2 is calculated Line 15 to measure the accuracy of the learned O Moreover, using the learned O we test 100 objects whose masses the 100 test masses to calculate the control cost Σ/ |2 - 11 + || l1 We compare the control cost of the learned θ and the optimal control cost, and use the mean value of the differences (named mean control error) to measure the accuracy.
In all experiments we fix H 20. We use three different types of trajectories: unit circle, parabola y 2² with æ E [0, 1] and Lemniscate of Bernoulli with a = 1| For all three types of trajectories we use their parametric equation
sx(() and = vl). divide the interval [0. 1] evenly into H parts, and set & to be the endpoints of these parts. We use these values to define the trajectory 21, 22, ..,
2H E R22 We set the decay ratio & to be k 1 or k 0.7 in our experiments.
We plot the accuracy of the learned model in Figure T Here we vary the number of training episodes (the number of training masses) and observe its effect on the accuracy. It can be observed that our algorithm achieves an satisfactory accuracy using only episodes. We also illustrate trajectories obtained by our resulting controllers in Figure 2 From Figure 2 it is clear that the agent plays more environments, it can enjoy better performance.
6 CONCLUSION
In this paper, we give a provably efficient algorithm for learning LQR with contexts. Our re- sult bridges two major fields, learning with contexts and continuous control from theoretically- principled view. For future work, it is interesting to study more complex settings, include non-linear control. Another interesting direction is design provable algorithm in our setting with safety guarantees (Dann et al., 2018).
7

---

Under review as a conference paper at ICLR 2020
0.20
Parabola, == 1.0
3,0
Parabela, == 1.0
Parabola, = 0.7
Parabola, 0.7
0.15
Lamniscate,
Mean Control Eroe
2.5
Lamniscate,
Lemmiscate,
Circle, & 1.0
2,0
Circle. &
Circle, À 0.7
1.5-
Circle. &
1.0
0.5-
8.00
0.0
10
2
Episodes
Episodes
Figure 1: ||0 O+11F and Mean Control Error.
km 0.7, m 0.1
k- 0.7, m 1.0
1.0
0.8
0.6
0.6
0.4
0.4
0.2
6.0
0.0
0.2
0.5
0.8
0.0
02
0.4
0.5
R 0.7, m 0.1
R- 0.7, 1.0
100
0.75
0.50
025
0.00
0.25
-0.50
-075
-0.75
-1.00
-100
-0.55
-0.30
-0.25
0.00
0.25
0.50
0.75
1.50
-1.00
-0.75
-330
-0.25
0.00
0.25
0.75
1.00
0.7. 0.1
0.7.7
0.4
0.2
-0.2
-1.0
-1.0 0.0
1.5
Figure 2: Example trajectories produced by the LQR controllers. We test the LQR policy to follow three types of paths: parabola, circle, and lemniscate. We first train decoder, then test it systems with m = 0.1, & 0.7 (left column), and m = 1.0, & 0.7 (right column). Dashed line with optimal policy. decoder trained by iteration randomly drawn contexts. A: decoder trained by 3 iterations on randomly drawn contexts. x: decoder trained by 10 iterations on randomly drawn contexts.
circles:target trajectories.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Yasin Abbasi-Yadkori and Gergely Neu. Online learning in mdps with side information. arXiv preprint arXiv: 1406.68/2, 2014.
Yasin Abbasi-Yadkon and Csaba Szepesvári. Regret Bounds for the Adaptive Control of Linear Quadratic Systems. Technical report, 2011. URL http:://proceedinneeeeeooo// mlr press/ v19/abbasi Saaabasi-yaakkorrla/aabbaaa waw.bbbaaiiydkkorii11 .dff
Yasin Abbasi- Yadkori, Nevena Lazic, and Csaba Szepesvári. Regret bounds for model-free linear quadratic control. arXiv preprint 1044vvv8000002211. 2018.
David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong reinforcement learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th In- ternational Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 10-19, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:://rrocecinngs mlr. www.:mmw.........eee.eee /v80/ aaaaablllBa html
Dimitri P Bertsekas. Dynamic programming and optimal control. Journal of the Operational Re- search Society, 47(6):833-833, 1996.
Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only vT regret. arXiv preprint 1922:0990200625: 2019.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. arXiv preprint /811v3/811.00055 2018.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample com- plexity of the linear quadratic regulator. arXiv preprint arXiv: 171.017700006888 2017.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Re- gret bounds for robust adaptive control of the linear quadratic regulator. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems 31, pp. 4188- 4197. Curran Associates, Inc., 2018. URL http::/pappes. nips cc/paper/ wob-t-oot-roo-tooooooooo--- sootrrttt--uud----oooo----------
In
pdf
Claude-Nicolas Fiechter. Pac adaptive control of linear systems. In Annual Workshop on Computa- tional Learning Theory: Proceedings of the tenth anmual conference on Computational learning theory, volume 6, pp. 72-80. Citeseer, 1997.
Shani Gamrian and Yoav Goldberg. Transfer learning for related reinforcement learning tasks via image-to-image translation. arXiv preprint 100v: 2018.
Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv preprint arXiv: 002.1002.000 1et.:02222022. 2015.
Taylor Killian, George Konidaris, and Finale Doshi-Velez. Transfer learning across patient varia- tions with hidden parameter markov decision processes. arXiv preprint arXiv:1612.00477 2016.
Lucas Lehnert and Michael L Littman. Transfer with model features in reinforcement learning. arXiv preprint arXiv: TXXiv:8807007730 2018
Lucas Lehnert, Michael Frank, and Michael I. Littman. Reward predictive representations gener- alize across tasks in reinforcement learning. BioRxiv, pp. 653493, 2019.
Raman Mehra. Optimal input signals for parameter estimation in dynamic systems-survey and new results. IEEE Transactions on Automatic Control, 19(6):53-768, 1974.
Aditya Modi and Ambuj Tewari. Contextual markov decision processes using generalized linear models. arXiv preprint arXiv: /90.006187 2019.
Aditya Modi, Nan Jiang, Satinder Singh, and Ambuj Tewari. Markov decision processes with con- tinuous side information. In Algorithmic Learning Theory, pp. 597-618, 2018.

---

Under review as a conference paper at ICLR 2020
Martin L Puterman. Markov Decision Processes.: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
Anirban Santara, Rishabh Madan, Balaraman Ravindran, and Pabitra Mitra. Extra: Transfer-guided exploration. arXiv preprint arXiv:196.11778, 2019.
Benjamin Spector and Serge Belongie. Sample-efficient reinforcement learning through transfer and architectural priors. arXiv preprint arXiv:/801.02260 2018.
Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: A survey.
Journal of Machine Learning Research, 10331)):133311685, 2009.
Stephen To and Benjamin Recht. Least-squares temporal difference learning for the linear quadratic regulator. arXiv preprint arXiv:1712.08642,, 2017.
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. arXiv preprint arXiv:1812.003555, 2018.
Yi Wu, Yuxin Wu, Aviv Tamar, Stuart Russell, Georgia Gkioxari, and Yuandong Tian. Learning and planning with a semantic model. arXiv preprint arXiv:1809 10842, 2018.
Lin Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kemels, and regret bound. arXiv preprint arXiv:
2019.
Yang Yu, Shi- Shi-Yong Chen, Qing Da, and Zhi-Hua Zhou. Reusable reinforcement learning via shallow trails. IEEE transactions on neural networks and learning systems, 29(6):2204-22155 2018.
10

---

Under review as a conference paper at ICLR 2020
A PROOF OF MAIN RESULTS
This sections devotes to proving the main results. Before prove Proposition 4.1 let use it to prove Theorem 4.1
Proof of Theorem 4.1
We rewrite the Equation equation 13 as follows.
E JH (Me. C.D. an)] Ec.D J. (M... m1)
EcDD [ji (MD....: 21)] EcD (iiD,, ai)]
K
BB.D JJ (Me..c,,, mi)] J (Mt,, 21) Jf (Cs,, 21)
K
k=1
J (Ct), 21) Ji pw, zι) - EcD Ji C,, m)))
= R1 + R2 R3
where
1 K
BeDDIJi (Me...D. =i) -J (wo, 21)),
R₁ K
1
(M 21) - Ecn [ m)))
R2 =
K
and
R3
K Σ
J (C,, mn) Jí (ce, m))
Let F& be the filtration of fixing all randomness before episode k. We have Rı and R2 are Martingale difference sum. Note that the magnitude of each summand in R₁ or R2 is upper bounded by (proved in Lemma A.3 and A.4),
almost surely. Therefore, by Azuma's inequality (Theorem A. than 8/2,
we have, with probability greater
log(S/5)
Ra + RRa S 2Ho
K
Moreover, by Proposition 4.1 we have with probability greater than - 5/2,
R&l dc.d log (
H K
where e is constant depending only polynomially on H, Cgy CM, and Cw. Combining the above two inequalities, and setting K appropriately, we complete the proof of Theorem 4.1
A.1 USEFUL CONCENTRATION BOUNDS
Before we prove the main proposition, we first recall some useful concentration bounds.
Theorem A.1 (Azuma's 's inequality). Assume that (Xa)a20 is a martingale and [X, Xg-1l S c. almost surely. Then for all I. and all >
Pr| Xol 2
2exp 2
11

---

Under review as a conference paper at ICLR 2020
Theorem A.2 (Martingale Concentration, Theorem 16 of Abbasi- Yadkori & Szepesvári (2011). Let Fit 2 0 be a filtration, (2t: 2 0) be an R vvalued stochastic process adapted to (Fi). Let (n& 2 1) be real-valued martingale difference process adapted to Fi. Assume that nhe is conditionally Sab-Gaussian with constant L,, i.e.
E/m(/Fi cxx((>>121))
Consider the following martingale
S. Σ
? --
T=1
and the matrix-valued processes
===1 1+ Σ 12-121-11
T=0
Then for any E (0, 1), with probability at least - 6,
[det(V))
vt 2 0,
|| S 21, 21,2log
where ||Sclli.-1 := 87 'T
A.2 PROOF OF PROPOSITION
In this section, we prove the main proposition. We first bound (et(V for any k. Lemma A.1. For all le E [K].
(V( S (1 (1H
Proof. Since (kk is PD, we have,
del(v(()) < (Ir(VIH))/D)* <
ΣΣ 11 12/11 p
k H-1
W=1
(k') 10 2. This completes the proof. By Assumption 4.1 we have 1/
Let us then define an event Eg as follows.
Definition A.1 (Good Event). We define event Eg. as (VK' kk: O. E C(K)).
We then show that the event Eg happens with high probability.
Lemma A.2. For all le E [K], we have Pr(FFx] 2 1 - 6.
Proof. Now we consider O ((k), We immediately have
k Ø-1
O. ((NT = =0, -v
(K) (0. 2/
(A') + +ww(() )T
2/
#=1
A=1
# - (((()))
Ø-1
H-1
(k') (K'T %/
O. +(((A))
(k) (K')
2h w h11
Next, we have
(+. (()) (((R)
=0.
1- (0
(V(4))-1 (1-(V(0))-
Σ Σ
H-1
(K)) (K)) v(N)
(T 1 (V(0)) (1-((0)))
Σ H-
ΣΣ (k))((
(K'T
oo
W= A=1
12

---

Under review as a conference paper at ICLR 2020
+ (1 -1
Σ
Ø-1
Σ
R
H- 1
(k) (K)T
(K)T
+
2/
%/1 Wh1l
h=1
h=1
H-1
k
H
(k') (T)T
T (V
-1
(k)) (1:)T
A.
1b+11
2/1 2/
k=
M=1 h=1
k H-1
* H-1
Σ
Σ
(k') (K)T (v(6))-1
Wh 1h
2/
h+1
k==1 h=1
===1 h=1
Note that Σ - (k)) (K)T
= V(k) - 1 and thus (x k1=1 %/
Σ#-1 (K)_
2/1 2/2
2/1
=
1 - -(((k))
Hence we have
tr((O. - ((0)) (0. (0.-
4 H-1 Σ
H-1
=I0"'Ilvce>- + 2tr (+ (V(6))-1
(K)
(
+
Σ Σ
2 wh++1 (V(A))-)
(k) (k')T 2
#= h=1
k==1 h=1
h
H
H-1
< |[..l[iieg=1 + +2|10. [
(K')
[K'TT
1 +
(
2
Wht1
n
wh+1
(Vin))
k==1
h=1
k=
h=1
where | = tr(x vX) and the last inequality uses
inequality. Notice that
| $ ||0.|F..
Moreover, we have
( 2
|1100) 1/2
(K))
(T)) 2
%/
h+1
(ra)y-
h+1
Am
R=
H
=
Σ
|
/2
w
1 %
(k))
cE(d
Σ
ΣΣΣΣ
(k') 2
1. 2/
jE|d
Famm
By Theorem A.2
we have, for every j E [d], with probability least 1 8/d, we have,
ΣΣ H-1
(K') (K')
( S 20 2cc.:o/(ddet((()))))////////
h+1.j&h
W= 1=1
By union bound, we have, with probability least 1 - 8,
Σ
Σ
w "h+1 || [ S 2de ((()) (8).
(3) (x)
Plugging to tr (r( - - we have, with probability at least 8,
- ur[(O, - (( (()) - 01()) )
S (c + cw / /2ll))((ddd((((8))))1137) 2
< ce + c v /2d + plog(1 + kHH kHHcgp))22 + log log 1-) 2
This completes the proof.
We define TE as the indicator for Ex happens. We denote
(((1) Me.,cu,),p pas, M(K] Mow, and yh (1) (K)T
.th T..
[=
13

---

Under review as a conference paper at ICLR 2020
On Ek, we have
vk E [K]: (M ,x4) S (MM)
We denote a == Jk (M x11 - Jh (M. .21). (21) We can rewrite equation 7 as
Regret (KH) Σ Ig. A (1)
where the second term is non-zero with probability less than 6. For the first term, we have
Lx A (k)
S LEE [J]" (M x1) - (T xr)i =: UE. (R))
where
A J (M. xn) xx)) - Jn (M 2n.)
Let us consider A (k) We denote filtration FR,n fixing the trajectory up time (k, h) and all
{CW*, D(K') D sss.
We have
A (k)
( Qnah (k) ( (6)
(k) 41 R + B (2) |J (ML , FR,N
- h
T
Qnahh (b) upp
(k)T Ruwh
(k)
Th
(M
(k)
+ w T Ph+i (M + +w/+tt) Fr.m
(k)
2/
- -Cut1(M((
=F,,0 whti
(J (M.
,x++11 , | Fa,n)
(k)
BBym whit
(M)
(M
(k) (K) (b) T Pa+i (M on + w(ill) Fu.m
2/
+ wn+1)
(R)
-Onta(M(()
-B w [Jit] (M (8) 2 Fx - J (1) + (MM,") 22/11)
(M 2/ (M ) ((()))=(()) -C(t2(
-Bast (1m/+1) Ph+ (M (1) ) Wh++1 Frnn)
(/t² Jut (t)
(k) .1+11) - (M(A) 2(1)) "Phti (MT(1)) (MT()) (10) - -Ca+1 (M)())
E (A) (5ht1 _² 200) " 1 (M)( (1 M 2/2 (10)) FrEA]]
(K)
R/
(k) Jutz (M!!.)
(1) , (M
2/ (11) Ph+1 (M (b)) (M)
2/ (10) Ch++1 (M
(6) T Pa+1 (M (z((t)) [Fah)] + (M/ ((x)) T ( ((1))
(2)
(1h41)
5/h 6p
(k)
6p
"(k)
+ I (1)) - Th+1 (TT()) 30/11))))))
(M.,
where
s/0) 10, [JÉt (M)
( 12411) [R.Nn] J (M. .2441)
(K) (1)
(K) (6)
(15)
5 (R) (1bb)) Ph+t (M (1)a))) - -B,,e [ [1//4]]] T (M+2(M(()) (2) Frnh
(16)
6 ((R) (M!" 2/ (10) T
2/1 ((1))) (
(174))((0)) T P (T7(k))
(17)
By induction, we have
k
Σ
A
(k)
(k) +
(K)
5 (
#=1
Notice that (/)) and 5% are Martingale difference adapted to FE We can well bound the sum of them via Azuma's inequality.
14

---

Under review as a conference paper at ICLR 2020
5h Lemma A.3. For all h [H], JJ (M!*) , (()))] S (H - 1).c. -Cq Cz.
CC.
Proof. Prove by induction on h. The base case Jh (A1,t) ,2H 2H QHTH S co holds straightforwardly. Consider an arbitrary < H. we have
(1))
(K)T (K)
Th (M. (1) Th ( Th
(M)T (K)T Quach +up R (1) +B 02 1 (M. ( 1
(8)
(6)
FRAA) S + (H- Cr
as desired.
U
Lemma A.4. For all x E X, we have Fg 1JA (M(h), xx)1 S cgex-
Proof. Follows from Assumption
We are now ready to prove Proposition
Proof of Proposition
4.7
Thus by Azuma's inequality, we have, with probability at least 1 - 6,
H-1
(
S v 22HH [(H h + 1)gcz cocz] 2
llog
2
And, with probability at least 1 - 8,
Σ
Σ
(K)
S
8kH c.. log 2
8
For
Σ
8%
"(k)
we bound it here.
k 1- 1
h
H-
k: 1-1
p
(h)
((k)
Phr+i | (3)
Uh )12 -1| (1) vix ||
(k)
h=1
k k=1
(1lPh+2 (M (1) ()())))))))))( ) || (M (1) (12)
(M7
y/ )12 (77)) 3/ )1))) (M
4-1
( - P (M (8) 1/2 (M w1 (()) [12 3/1/2
(1 112 + P (17 ((x)) l12 } 2,1/2
k=
Notice that || ( (1) S aecce and |P ( (/ )1 S cpca- Hence
(M'
k カ-
(M()) ( (1 + (17 2/122
Σ
S /VHH (c + 2
Moreover, by triangle inequality, we have
PP (17 1/2 (TT()) (1) 1l2 1| (17 (M w() ]12
- PP (MT( 1/2 (TT(M)) - 3n u/. 1
S c (MT(()) -/ (121|2 l|2
S cq (TT(A)) -1 (V())) -1/2 (1:) ||2
15

---

Under review as a conference paper at ICLR 2020
S cq (g (V(h() (V(() -1/3y// (16) 1|2
S cq BBk)) /|(((1)) y/ah11 222
By Assumption 2, we also have ((((4))-1/2/) (1) 12 - 11 (1) 112 S Cc. Hence,
PP / 1/2 (1(()) U/2
(k)) )l12 || (MT(K) 1/2 (M v/x ) l12
-1 1/2 U/ (k)) S cgvce B(K) min (1(1
11
Combining the above equations, we have,
H-1
Ø-1
(M)
S v kH (cgex(1 +e))) cgVCe - BBk)
min (1((V(6))-112)441 //
A
h=1
1==1 A=1
H
S 20 3/2 Gee B(h)
log (1 ((((()))-1//))))) 113) VkH.
A
Lastly, by Lemma 8 of Yang & Wang 2019).
have
log (1 + (1(v(()))
1/2 Un 11
< 2H log (V)(V()))
Together with Lemma A.1 we have
2H log dct((V()) < 2Hp log (1 + kHc2/p).
Overall, have,
k
1-
h
(R)
<
3/2 2c
000
V 22 log (1 kHc (3(K)) kH.
W=1
h=1
Putting everything together, with probability at least 1 - 25, we have
K H-1
5(()) + n
+ (1))
reg (KH)- S
k
h=1
< / 2KH [(H - h+ 1) + CgCo) 2 log g
2
+
v (88KH- .g log
+ 201/2 2g v 22H log (1 KHo./p) (B(K)) KH 3/2 2 SH 1 1/2
VKH.
where CH is a constant depending on H, Cg. Czi cg and c..
B CONCRETE CHOICE OF THE PARAMETERS
We further augment the state that the first coordinate is constant with value 1. More specifically, we set the state Th [l; 243 vn] E R5. We set
2h
0
Qn =
2
0
so that for any state Th. 1 TTQU = 1|
2%
12
We set R
with size 2 x 2. We set
1
0
0
0
0
0
1
0
e, =
0
0
1
0
1
0
0
0
0
1
0
0
0
0
1:
0
C' to be the 5 x 5 identity matrix and D to be 1/m with size 2 x 2 where m is sampled from the uniform distribution over [0.1, 10). to represent the physical law Equation 14
16


Reviews:
[{"review_id": "HJelb3w15r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In order to generalize the RL agent to unseen environment, in this work the authors studied the theoretical learning problem of building a decoder on top of linear continuous control using linear quadratic regulator (LQR). They presented a simple, UCB-based algorithm that refines the estimates of the encoder while doing LQR and balances  the exploration-exploitation trade-off. In the online setting, the proposed algorithm has a O(\\sqrt{T}) regret bound, where T is the number of environments the agent played. This also implies after certain exploration, the agent is able to transfer the learned knowledge to obtain a near-optimal policy to an unseen environment. To justify their theoretical bounds the authors also present experiments that demonstrate the effectiveness of the algorithm.\n\n\nThe work of designing decoder on top of RL/control in order to generalize to new, unseen environments is very interesting, and is pretty novel to my knowledge. The problem formulation of LQR is standard until the part where the authors introduced the output matrices (C,D), which extends the fully-observable case of LQR (that is based on state feedback only) to partially observable. Leveraging the theoretical analysis of LQR, the authors extended the analysis to the setting of output feedback with particular structures of decoder matrices (C,D) sampled from decoder \\mu. The algorithm proposed is quite standard in the output-feedback LQR literature (in control or RL). But the work is still interesting because to my knowledge I am not aware of general theoretical analysis of this setting (while most analysis is based on the full state feedback).\nI haven't checked the proofs very carefully in the appendix, but from the description in the main paper it seems the analysis of contextual transfer learning performance is sound, and under certain regularity assumptions the authors did provide a high-probability regret bound for this contextual transfer learning problem. It would be great if the experiments are more involved as they are a bit too simple at this point, (where the unseen environment is the change in the physical constants). I also have some difficulties understanding all the dots in figure 2. Perhaps the authors can simplify the number of trajectories plotted there to make the presentation clearer. Another comment is about the current title, currently by looking at it I have no idea that is about contextual transfer learning and LQR. It would be great if that can be more specific. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkeJLdEMnS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of changing environments for LQR. The authors model this through the use of a decoder that maps an incoming context (C,D) to the LQR matrices (A,B). They provide an algorithm for this setting based on a UCB strategy, prove sample complexity and regret bounds, and experimental results.\n\nOverall the paper was well written but I had several concerns.\n\n1. The results of this paper were not contrasted with other papers in this area. For example, if C,D are constant, and \\Theta_* is a Block diagonal matrix with A,B on the diagonal - then the contextual case reduces to the standard LQR problem. It's unclear how the results given compare to past results in this setting, for example those of Abbasi-Yadkori/Szepesvari 2011.\n\n2. I did not fully understand the UCB nature of the algorithm. In each round \\Theta^(k) (the least squares estimator) seems to be used to compute the optimal policy (line 10 of the algorithm) instead \\tilde{\\Theta}^(k)  -the optimistic estimate. The optimistic estimate is only used in line 16 - a randomized procedure that is unmotivated.\n\n3. Building on (1), it is hard to understand the results as given since there are no lower bounds given nor is there a discussion of the problem dependent parameters that arise. For example, in Theorem 1, is dp^2 suspected to be tight? Since the number of parameters in \\Theta^{\\ast} is d(p+p'), perhaps this is off by a factor of p?\n\n3. I struggled to understand the setup of the experiments - as described the algorithm given was not used at all, rather \\Theta^(k) was approximated and beta^k was set to be a constant. This does not seem like a fair evaluation of the method. \n\nIn summary, I would reject this submission unless the authors couch it better in past work, explain their results better, and improve the experiment setup.\n\nFinally, a typo: I think the indexing variable in the equation on the top of page 4 is h' not h. \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "B1lQPS9pYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n# Summary\n- The paper proposes a UCB-inspired algorithm for a contextual LQR problem. The problem itself is introduced in this paper and is similar in spirit to CMDPs, with the difference that instead of learning a mapping from context to transition matrix, a mapping from context to matrices [A, B] figuring in the system dynamics of LQR is learned.\n- The proposed algorithm is an online-learning algorithm shown to have sublinear regret in the number of experienced environments. A toy experiment with a 2D moving mass is presented to illustrate the theory.\n\n# Decision\nAlthough the problem setting is interesting and it is encouraging to have a guarantee, several important unclear points in the paper and a missing comparison to a straightforward baseline stop me from recommending it for publication in its present form. I detail my concerns below.\n\n# Concerns\n1) First, a conceptual question. I can see a straightforward algorithm that can learn the linear mapping \\theta from context to [A, B] as follows.\n        - In episode k, obtain trajectory (x_{1:H}, u_{1:H-1})\n        - By least squares, find [A, B] from the obtained trajectory\n        - Since context [C, D] is observed, find \\theta : [C, D] -> [A, B] again by least squares\nOne can do this using data from K episodes if needed, one can sequentially update the controller for collecting data, etc.\n=>  A comparison to such a basic approach should be definitely included in the paper, in my opinion.\n\n2) The authors might argue that the algorithm suggested above has no guarantee. I would be curious to hear in this regard a comment on the practical implementation suggested in the paper. Namely, after deriving the bounds etc., the authors make further approximations and modifications in the practical algorithm. From my point of view, these modifications defeat the purpose of the bounds, because then only empirical evaluation can confirm that these approximations have not destroyed the analysis. Alternatively, one needs to incorporate the introduced approximation errors in the analysis. In more detail,\n        - Eq. (9) is not solved exactly but by random sampling. In the 2D toy task, it may be OK, but in higher-dimensional spaces, a significant error can be introduced which is not accounted for.\n        - More importantly, the UCB bound \\beta in Eq. (11) is not used at all in the experiments.\n            => To my understanding, it is the crucial point of UCB to use the UCB-bound. If it is not used, how should one judge the resulting algorithm?\n\n3) This is a concern regarding clarity. I didn't get (i) if matrices [Q, R] are context-dependent or not and (ii) if the agent observes them or not. This is not clearly communicated in the text.\n=> Clarify whether [Q, R] are context-dependent and observed.\n\n# AFTER REBUTTAL\nAfter authors' clarifications and improvements on the paper, I update my score to weak reject. The reason I am still against acceptance is the lack of stronger empirical evaluations. As R4 pointed out, some clarifications on the side of the algorithm are also required.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work considers the popular LQR objective but with [A,B] unknown and dynamically changing. At each time a context [C,D] is observed and it is assumed there exist a linear map Theta from [C,D] to [A,B]. The particular problem statement is novel, but is heavily influenced by other MDP settings and the also follows very closely to previous works. The algorithm seems computationally intractable (a problem shared by previous work this work builds on) and so in experiments a gross approximation is used. 

Reviewers found the work very stylized and did not adequately review related work. For example, little attention is paid to switching linear systems and the recent LQR advances are relegated to a list of references with no discussion. The reviewers also questioned how the theory relates to the traditional setting of LQR regret, say, if [C,D] were identity at all times so that Theta = [A,B]. 

This paper received 3 reviews (a third was added late to the process) and my own opinion influenced the decision. While the problem statement is interesting, the work fails to put the paper in context with the existing work, and there are some questions of algorithm methods.  
Decision: Reject