1.
* Infinite dimensional objects arise from finite dimensional control problems when we use a **policy** to react to disturbances.
* The linear control problem is not convex unless we lift from system state space into the (infinite dimensional) DAC policy space. This is *not* a result of a proof technique and has algorithmic implications.
* The linear dynamics that define the control problem have a finite ($d$) dimensional representation. However, the presence of external disturbances means that we need to model the *system response* rather than merely the *system state*. The system response is infinite dimensional. For example, see [System Level Synthesis, Anderson et al., 2019](https://arxiv.org/abs/1904.01634).
* To compute how policies (decisions) affect costs (losses) through the function $\tilde{f}_t$, we need to model the system response. So, this is an algorithmic consideration and not just the result of a proof technique.
* [Agarwal et al., 2019b] consider a *truncated* system response of length $O(\log T)$ that is an approximation. This is also where they appeal to results for OCO with finite memory, which our paper should be seen as a replacement for.
* More generally, other examples of infinite dimensional history/states include infinite impulse response filters in signal processing (e.g., elliptic filters).
* To contrast, suppose instead of choosing policies, we were interested in a "fixed constant input" model of control. That is, the learner chooses a fixed control input in each round and the benchmark is the best fixed control input. This would indeed result in a finite dimensional history space.
* The history combines "noiseless" state with action: $\bar{s}_{t+1} F \bar{s}_t + G a_t, h_t = (\bar{s}_t, a_t)$.
* The linear operators are block matrices: $A = [F, 0; 0, 0]$ and $B = [G; I] / \| [G; I] \|$. (The scaling on $B$ is to ensure that it has unit norm, which we assume in our paper for convenience.)
* The loss functions are $f_t(h_t) = c_t( \bar{s}\_t + \sum_{k=1}^t F^k G w_{t-k} , a_t) = c_t(s_t, a_t)$.
2. Yes, you are correct. The algorithm of [Agarwal et al., 2019b] and their proofs work for standard Euclidean norms and the corresponding matrix norms. If the state and history spaces are infinite dimensional with non-standard norms, then there is a mismatch between the problem setup and their algorithm and proofs. So, in some sense the regret is unbounded because of both the algorithm and the proof technique. The algorithm would use a regularizer that is strongly convex with respect to the Euclidean norm, resulting in suboptimal regret compared to our algorithm that uses a regularizer adapted to the appropriate norm; the proofs would compute the Euclidean norm of infinite dimensional objects.
3. We agree with your point.
* See lines 981 - 988 in the appendix where we discuss this issue. We believe that it is a feature that our framework provides a clean abstraction for the user that they can use for a variety of applications. The dimensionality of $\mathcal{X}$, the choice of the operator $A$, etc. are application dependent. The user could use our framework with a lower dimensional decision space $\mathcal{X}'$ and then analyze the error that results from such an approximation. Meanwhile, our framework allows the user to define non-standard norms on the decision and history spaces. This can be a simple but powerful way of encoding prior knowledge about the application, and our framework handles the technical complications that arise from this (e.g., bounding the Lipschitz constant, operator norms, etc. - see Lemmas E.2 and E.6 (especially lines 885 - 891) for an illustration).