We appreciate your thorough review of our manuscript and your insightful feedback. Your comments that this technique may have broader applications and your point about deterministic dynamics potentially making Bellman backups less ideal, are particularly valuable. In addition, we would like to share our thoughts below.
> Assuming deterministic dynamics is very restrictive and, most importantly, does not marry very well with Bellmann completeness.
We really appreciate you sharing your insight into this problem. Your intuition that deterministic transitions may make the Bellman operator less ideal—making it harder to smooth things so estimation using linear functions may be harder—is insightful. We believe that future research on both deterministic transitions and linear Bellman completeness should carefully consider it.
> Still, it must be noted that the assumption of linear Bellman completeness does not allow for an easy reduction: just creating a fictitious initial state does not work in this case.
Thank you for bringing this point! We will make sure to incorporate it.
> At line 2040, the authors claim that, due to the structure of the problem, the optimal actions writes as $Kx$, where $K$ is some matrix. Even if it is true that in the LQR the optimal policy takes this form, I am not convinced from that passage
Thank you for your comment, and we really appreciate that you pointed this out. We think LQR satisfies Bellman completeness for a convex subset of linear functions. In particular, consider the dynamics of LQR given by:
$$
\begin{aligned}
x' = Ax + Bu + \omega, \quad \text{where} \quad \omega \sim \mathcal N(0, \Sigma).
\end{aligned}
$$
We consider state-action value functions of the follow form (basically the same as what we used):
\begin{align}
Q(x, u) = \begin{bmatrix}
x \\\\ u
\end{bmatrix}^\top \begin{bmatrix}
P\_{xx} & P\_{xu} \\\\
P\_{ux} & P\_{uu}
\end{bmatrix}\begin{bmatrix}
x \\\\ u
\end{bmatrix} + c,
\end{align}
It is linear in the quadratic feature $\phi(x, u) = [x^2, u^2, xu, x, u, 1]$. Without loss of generality, we assume that $P\_{xu} = P\_{ux}^\top$; the induced $\theta$ is given by flattening our $P$ (We interchange $\theta$ and $P$ in our proof). As pointed out by the reviewer, we do not have Bellman completeness for *any* such $P$, but under the restriction that $P$ is PSD (note that the set of such $P$ or corresponding $\theta$ will be a convex set). To see this, recall that a matrix:
\begin{align}
P = \begin{bmatrix}
P\_{xx} & P\_{xu} \\\\
P\_{ux} & P\_{uu}
\end{bmatrix}
\end{align} is PSD iff (1) $P\_{xx}\succeq0$ and $P\_{uu}\succeq0$, and (2) its schur's component $P\_{xx} - P\_{xu} P\_{uu}^{-1} P\_{ux}\succeq 0$.
Then, we can compute the Bellman backup of $Q$:
\begin{align}
& \widetilde Q(x, u) \\\\
&= \mathbb{E}\_{x'} \left[{\min\_{u'} Q(x', u')}\right] \\\\
&= \mathbb{E}\_{\omega} \left[{\min\_{u'} \begin{bmatrix}
Ax + Bu + \omega \\\\ u'
\end{bmatrix}^\top \begin{bmatrix}
P\_{xx} & P\_{xu} \\\\
P\_{ux} & P\_{uu}
\end{bmatrix}\begin{bmatrix}
Ax + Bu + \omega \\\\ u'
\end{bmatrix} + c }\right] \\\\
&= \mathbb{E}\_{\omega} \left[{\min\_{u'} \left\\{{\left[ Ax + Bu + \omega \right]^T P\_{xx} \left[ Ax + Bu + \omega \right] + 2 \left[ Ax + Bu + \omega \right]^T P\_{xu} u' + u'^T P\_{uu} u'}\right\\}}\right] + c
\end{align}
Using first-order condition, we know that the optimal $u'$ satisfies
$$
u' = - P\_{uu}^{-1} P\_{ux} \left({Ax + Bu + \omega}\right),
$$
which implies that
\begin{align}
\min\_{u'} Q(x', u') = \left[ Ax + Bu + \omega \right]^T \left[{P\_{xx} - P\_{xu} P\_{uu}^{-1} P\_{ux}}\right]\left[ Ax + Bu + \omega \right] + c
\end{align}
Plugging the above back into $\widetilde{Q}$, we get
\begin{align}
\widetilde Q(x, u) &= \mathbb{E}\_\omega \left[{\left[ Ax + Bu + \omega \right]^T \left[{P\_{xx} - P\_{xu} P\_{uu}^{-1} P\_{ux}}\right]\left[ Ax + Bu + \omega \right] + c }\right] \\\\
&= \left[ Ax + Bu \right]^T \left[{P\_{xx} - P\_{xu} P\_{uu}^{-1} P\_{ux}}\right]\left[ Ax + Bu \right] + c~+ \text{tr}\left({\left({P\_{xx} - P\_{xu} P\_{uu}^{-1} P\_{ux}}\right)\Sigma}\right) \\\\
&= \left[ Ax + Bu \right]^T \left[{P\_{xx} - P\_{xu} P\_{uu}^{-1} P\_{xu}^\top}\right]\left[ Ax + Bu \right] + c' \\\\
&= \begin{bmatrix} x \\\\ u \end{bmatrix}^T
\begin{bmatrix} A^T \\\\ B^T \end{bmatrix}
\left( P\_{xx} - P\_{xu} P\_{uu}^{-1} P\_{xu}^\top \right)
\begin{bmatrix} A & B \end{bmatrix}
\begin{bmatrix} x \\\\ u \end{bmatrix} + c'
\end{align}
where $c'$ is some constant. The above matrix is PSD since $P\_{xx} - P\_{xu} P\_{uu}^{-1} P\_{xu}^\top \succeq 0$, which holds since $P$ itself is PSD. Thus,
\begin{align}
\widetilde{Q}(x, u) = & \begin{bmatrix}
x \\\\ u
\end{bmatrix}^\top \widetilde{P} \begin{bmatrix}
x \\\\ u
\end{bmatrix} + c,
\end{align}
for PSD matrix $\widetilde{P}$, and thus the Bellman completeness holds over this convex subset of linear functions for which the corresponding Ps are PSD.