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 O √ T regret bound in the online setting where T is the number of environments the agent played. This also implies after playing O 1/ 2 environments, the agent is able to transfer the learned knowledge to obtain an -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.
# Summary
- 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.
- 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.
# Decision
Although 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.
# Concerns
1) First, a conceptual question. I can see a straightforward algorithm that can learn the linear mapping \theta from context to [A, B] as follows.
        - In episode k, obtain trajectory (x_{1:H}, u_{1:H-1})
        - By least squares, find [A, B] from the obtained trajectory
        - Since context [C, D] is observed, find \theta : [C, D] -> [A, B] again by least squares
One can do this using data from K episodes if needed, one can sequentially update the controller for collecting data, etc.
=>  A comparison to such a basic approach should be definitely included in the paper, in my opinion.
2) 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,
        - 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.
        - More importantly, the UCB bound \beta in Eq. (11) is not used at all in the experiments.
            => 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?
3) 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.
=> Clarify whether [Q, R] are context-dependent and observed.
# AFTER REBUTTAL
After 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.