Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics

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):

$

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,

$

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:

$

P = \begin{bmatrix} P_{xx} & P_{xu} \\ P_{ux} & P_{uu} \end{bmatrix}

$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$:

$

& \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

$

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

$

\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

$

Plugging the above back into $\widetilde{Q}$, we get

$

\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'

$

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,

$

\widetilde{Q}(x, u) = & \begin{bmatrix} x \\ u \end{bmatrix}^\top \widetilde{P} \begin{bmatrix} x \\ u \end{bmatrix} + c,

$

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.

Thank you for your valuable feedback! We have fixed the typo you mentioned in the current draft. We will also ensure to improve the paper by elaborating more on the difficulty in stochastic dynamics as per your suggestions.

In addition, we would like to provide our thoughts on your concerns below.

One concern is with the presentation style of the paper. The assumption of deterministic dynamics appears to be critical for the regret analysis, yet it is unclear why stochastic dynamics would impede the success of the method. Although it is mentioned that the deterministic nature of the system enables value decomposition as shown in Lemma 10, the necessity of this condition is not explicitly explained in the main body of the paper.

We will ensure a more comprehensive discussion on this. In summary, the key point is: deterministic transitions are needed in our current analysis due to the span argument (see Appendix B, particularly B.1). The span argument divides the proof into two cases based on whether the entire trajectory generated by the current policy ($\pi_t$) falls completely within the data span or not. This step relies on the observation that, under deterministic transitions, our estimates are accurate within the data span--this will not hold under stochastic transition.

There are some typos: e.g., "to the learn parameters" in p.2, and "where the it is" in p.6.

Thanks you! We have fixed them.

Why are the constrained squared loss minimization problems first converted to the convex feasibility problem, and then solved by random walk method that depends on a separation oracle? It seems that when S and A are infinite, then it is challenging to design an appropriate separation oracle for K. Even when and are finite, then each minimization problem has decision variables and constraints, requiring any separation oracle to evaluate the membership for inequality constraints.

The l_infinity norm of the constraint set in our constraint optimization problem is exponential in H. Thus, to ensure computational efficiency, we need an optimization procedure that can solve this constrained optimization problem in $\text{poly}(d, \log R)$ time where $R$ is the l_infinity norm of the constraint set. The random walk-based approach from Bertsimas & Vempala (2004) gives us this guarantee; however we can easily substitute reliance on their procedure by any other procedure to solve constrained optimization problems whose running time is $\text{poly}(d, \log R)$.

The procedure of Bertsimas and Vempala (2004) needs a separation oracle, and in our setting, this separation oracle can be implemented using a linear optimization oracle over the feature space. Assuming such a linear optimization oracle over the feature space is standard in RL theory. To conclude, your point is correct, our procedure is efficient conditional on solving the constrained optimization problem efficiently, which in turn relies on the access to a linear optimization oracle w.r.t. the feature space; but these assumptions are standard in RL theory.

Additionally, if we are willing to assume bounded $\ell_2$-norm of Bellman backup as commonly imposed in prior works (though we did not make this assumption in our paper), the exponential blow-up will just happen in terms of $\ell_2$-norm. In that case, we can just use these $\ell_2$-norm constraints. Then, the problem is easier to solve (since it does not involve the feature anymore) so no need for the optimization oracle.

We are happy to discuss further in case this does not address your concerns.

Thank you for your valuable feedback! We appreciate your insightful questions about the span argument and optimization. We would like to share our thought on these below:

Not clear if the dependences on d and H are optimal in the main theorems, or if there is still work to do in that direction

This is a very good point. While we do not know either, we hope to share what is already known as a reference. We consider two cases:

(1) Known reward: in this case, our regret bound is $\tilde{O}(dH^2)$ (see line 373). A naive lower bound for table MDP with deterministic transition is $\Omega(SAH)$. Since $d = SA$ in the tabular case, there seems to be a gap of $H$ in this case.

(2) Unknown reward: existing results (e.g. proposition 1 in [1]) show a lower bound of $\Omega(dH\sqrt{T})$. This differs from our bound by a factor of $d\sqrt{H}$. However, the lower bound does not assume deterministic transition, so it may not be comparable in general.

We acknowledge the importance of this question and believe it is an interesting future direction.

The paper mentions that "Many efficient algorithms can be applied to find approximate D-optimal designs such as the Frank-Wolfe". I think this is the case when S,A are finite, but what if they are infinite? Is there any efficient algorithm?

Thank you for this important point. It is correct that frank-wolfe is efficient only when SA is finite. However, the running time for frank-wolfe scales as $\text{poly}(d, \log \log |SA|)$, which is tolerate for us for extremely large SA. Furthermore, under slightly sophisticated initializations, this dependence on SA can be completely eliminated. We refer to bullet points 3 and 4 in section 21.2 in the book "Bandit Algorithms" by Csaba Szepesvari and Tor Lattimore (https://tor-lattimore.com/downloads/book/book.pdf) for more details. We will clarify this in the next version of our paper.

Additionally, if we are willing to assume bounded $\ell_2$-norm as commonly imposed in prior works (though we did not make this assumption in our paper), the identity matrix suffices for initialization. So there is no need for a D-optimal.

It is not clear why constrained least squares regression, instead of an unconstrained one, is needed since there is no assumption on boundedness of the true parameters. Could you clarify?

Our algorithm is inspired by RLSVI to inject random noise to encourage exploration and achieve optimism. The key argument here is that the noise must be large enough to cancel out the estimation error. This means, when designing the noise sampling procedure, we have to know an upper bound of the estimation error--this is why we need the parameter to be bounded and hence we solved a constrained regression problem.

Regarding boundedness of parameters: while we cannot control the $\ell_2$ norm of the parameter as argued in Section 3.1, we observe that the parameter is naturally bounded under what we defined as the "$\ell_\infty$-functional norm" (Line 334). So we are still able to control the size of the parameter in terms of this norm. Importantly, this norm property arises as a conclusion of linear Bellman completeness rather than being an additional assumption. And we use this norm in our regression constraints.

Even though it acts only on the null space, it was not clear to me why the injected noise (ie \sigma_h) has to be exponential in H

As mentioned in the previous question, the noise must exceed the estimation error, which can become exponentially large because the parameter norm (of $\theta$) can grow exponentially large--this is because adding noise to the parameter scales its norm multiplicatively. All these blow-ups happen in the null space, so the noise there has to be exponentially large as well.

Does the algorithm need to know that the MDP has deterministic transitions? In other words, if applied to a stochastic MDP, would the algorithm still make sense or would it break for some reason?

Our algorithm does not need to know that the MDP is deterministic, and will run even if the underlying MDP is stochastic. However, our performance guarantees only hold under deterministic transitions.

Thank you for your valuable feedback! We have fixed the typo you mentioned in the current draft. We will also ensure to improve the paper by elaborating more on the key design choices and reasoning as per your suggestions.

In addition, we would like to provide our thoughts on your questions below.

Therefore, it is unclear to me what is blocking the analysis from extending to MDPs with stochastic transitions.

You are right regarding Eq (10). As you pointed out, when the transition is not deterministic, a variant of Eq. (10) still holds, where we take an expectation with respect to the trajectory randomness on the RHS. However, in our proof, we specifically require a version without the expectation. This is needed so that we can divides the proof into two cases based on whether the entire trajectory generated by the current policy ($\pi_t$) falls completely within the data span--this is the span argument in our paper (see Appendix B, particularly B.1). This step crucially relies on Eq. (10) being derived without expectation to show that our estimates are accurate within the data span. We will make sure to clarify this point in the next version of the draft.

Example 1 in Section 3.1 is confusing.

Thanks for checking our examples. \mu(s_2) is not a typo. Here we are using the notation from Linear MDP (so we have $P(s_2|s_1,a_1)= \langle\phi(s_1,a_2),\mu(s_2)\rangle$).

And you are right, we aim to demonstrate the existence of an MDP and a feature mapping that lead to unbounded $\ell_2$ norm. We agree it is possible that a better feature mapping for the same MDP may exist and bound the norm; however, searching for such a mapping is likely a hard problem. Additionally, the MDP in this example does not need to be tabular. Since we have formulated it as a linear MDP, we can append a true linear MDP to it to extend to infinite state space.