Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the task of controlling an unknown (stochastic) linear dynamical system subject to changing convex costs revealed online. The main result is a computationally efficient achieving T^0.5 regret against the class of stable linear policies. 
strengths_and_weaknesses: — The previously best known regret bound was T^2/3, improvable to T^0.5 for strongly convex costs or in the stochastic setting. This is an unambiguous improvement.

— The primary innovation here is choosing the compatible efficient implementation of OFU to combine with OGD/regret-minimizing algorithm. The typically non-convex optimistic cost can be convexified with the correct guess of the active norm constraint; this was used in the recent result (CCK’22) on stochastic costs. 

— Here the natural choice would be to use a regret minimizer to guess this active constraint, except such a procedure would only be sound if the cost associated the norm penalty was stationary, i.e. when the best in hindsight decision coincides with the point-wise best. This stationarity is what the paper notes (Line 211). Notably, this characterization was also true, but not necessary for the result, in the stochastic case (CCK’22). I think this observation is neat.

— The paper is well written, and, to a great extent, linearly readable.

Setting apart the FTPL/switching issue (see below), I do not have any reservations on the claims made.

questions: I understand the need to play slow-moving iterates. But neither once-randomized FTPL nor shrinking dartboard is necessary here, to the best of my comprehension, because the underlying decision space is continuous, obviating the need for explicit sampling. Here is a simpler alternative.

Given M_1, … M_K expert recommendations, and (normalized) weights from a MW instance p_1, .. p_K, play the policy M’=sum_i p_i M_i. By convexity of the true cost, cost(M’) < sum_i p_i cost(M_i). Furthermore, p_i’s change slowly as usual. I point out MW for simplicity, but any low-regret algorithm with slow moving iterates is equally suitable (e.g. OGD or the expected iterate for FTPL).

In fact, this approach has potentially greater technical merit in that it also works for adaptive adversaries.

Can the authors comment on this consideration?
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper provides a high-probability $\tilde{O}(\sqrt{T})$ regret bound for online linear control with convex, Lipshitz costs and stochastic noise with known covariance provided a stabilizing controller.  This is in contrast to existing work with $O(T^{2/3})$ regret for convex costs or $\tilde{O}(\sqrt{T})$ with restrictions on costs like strong convexity.
strengths_and_weaknesses: Strengths:
- Online linear control is a classically important problem and policy regret approaches to the problem have been popular in the last few years.  Improved rates are a worthwhile problem.
- The approach is technically challenging, combining lower confidence bound techniques, online control policies, along with slowly changing experts.  These cannot be naively combined as dealing with the nonconvexity of the lower confidence bounds requires cleverness.
- The exposition of the algorithm/proof are relatively easy to understand and follow

Weaknesses:
- Much of the recent work in online control focused on regret-minimization allows for adversarial bounded costs.  Stochastic noise with known covariance is much weaker.
- Stabilizing controller is required for this method while some other methods are fully black box.
- Some parts of the writing can be a bit hard to follow notation wise.  For example, understanding that $k$ was a tuple as defined in the equation 3 required reference to the algorithm. 
questions: Could notation be described earlier before the algorithm?
limitations: The authors could do a better job of relating the assumptions of this work to other related works.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper looks at the problem of controlling a linear dynamical system when there are adversarial convex cost functions. They study this problem in the setting when there is full feedback on the cost and the current state of the system. They provide an algorithm that obtains optimal regret even when the cost functions are not strongly convex. They also provide a non-convex lower bound for the cost.
strengths_and_weaknesses: - Originality: The problem of controlling linear dynamical systems has been studied in the literature. The paper attempts to further this study by considering the model of adversarial and general convex cost functions. They provide a computationally efficient algorithm that gives near-optimal regret.

- Quality and Clarity: The paper is well written and clear.

- Significance:  The paper claims to provide the first computationally efficient algorithm that achieves near-optimal regret for the linear dynamical system when the cost functions change over time.
questions: What are the challenges of moving away from a full feedback model to a limited feedback model? What if you were to observe the state and/or the cost function, with some form of error? How would this affect the tractability of the problem?
limitations: The paper points out that the meta-algorithms they use as experts have inherent randomness that could result in instability. They point out that the use of a follow the lazy leader algorithm helps stabilize the effects. They state that there are inherent challenges of using the follow the lazy leader algorithm as it does not work well against non-oblivious adversaries. They do get over this barrier by using gaussian distribution assumptions on noise.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors study the problem of online control of an unknown linear dynamical system w.r.t. a sequence of (oblivious) adversarial cost functions. They give a computationally efficient algorithm that achieves $O(\sqrt{T})$ regret, compared to the best static stabilizing controller in hindsight. Their approach does not require strong convexity of the cost functions as in prior work.
strengths_and_weaknesses: **Strengths:**
- Paper is well written.
- Authors advance the state of the art in online LQR control.
- Proof techniques may be of independent interest. 

**Weaknesses:**
- The algorithm is not the most straightforward, and involves a lot of different components (each of the components are, however, standard in the OCO literature). 
- No experiments showing that the algorithm is actually practical.
- I would have liked to see a much more detailed comparison to Cassel et al. [16]. The setting of [16] is stochastic (instead of adversarial costs), but Algorithm 1 from [16] seems similar. The main difference is that the OFU step in [16] is replaced with the BFPL step in Lines 15-18 of Algorithm 1. Is this for computational reasons only, or is this actually necessary? (Apologies if this is an obvious question, I am not an expert in online convex optimization). This is also where an experiment would have been nice, to see the practical difference between these two algorithms.
questions: - As pointed out by the authors, one drawback of the DAP policy class is that it requires the noise disturbance sequence $\{w_t\}$ to compute the action $u_t$. An alternative parameterization is the system level synthesis framework (see Section 2 of Anderson et al. https://www.sciencedirect.com/science/article/abs/pii/S1367578819300215), which is essentially the DAP parameterization with an extra subspace constraint involving the dynamics. By adding the subspace constraint (which can be encoded using the current $(A_t, B_t)$), one can then turn the DAP policy into a proper state feedback policy. I wonder if this parameterization would simplify various aspects of both the algorithm (no need to estimate the noise sequences in Line 8), and the proof.  
limitations: - As mentioned previously, no experiments. In my opinion, condensing Section 4 and adding an experimental evaluation would further strengthen this paper from accept to strong accept.
review_title: null

Meta-review: metareview: I recommend acceptance due to the unabiguously and uniformly positive opinions of the reviewers. The reviews identify the authors' clear contribution (improving the rate) for a problem of interest in the community (online linear control with relaxed assumptions). Concerns about clarity or alternative approaches were resolved during the discussion period.
confidence: Certain
Decision: Accept