Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^\pi$-Realizability and Concentrability

We thank the reviewer for their helpful feedback.

What is the reason that $G = \bar G$ passes the condition (14)? Is it because the concentrability assumption plus Lemma 4.2 results in a tight confidence interval for the q-value?

Yes, it is precisely as you say “because the concentrability assumption plus Lemma 4.2 results in a tight confidence interval for the q-value”. Lemma 4.2 establishes that the targets of the least-squares regressions in optimization problem 1 are linearly realizable with the features (because skipping with $\bar G$ results in an approximately linear MDP). Concentrability is then used to bound the average confidence of the least-squares predictor.

One thing I do not follow is how the algorithm eliminates incorrect guesses $G$. If I understand correctly, Lemma 4.2 only shows that linear $q^\pi$-realizable MDPs with skips can be approximated by linear MDPs under the true guess. Then for an incorrect guess $\bar G$, is the modified MDPs still linear? If not, does optimization problem 1 still give some meaningful guarantees so that the algorithm can eliminate these cases? In addition, since the optimization problem 1 is mostly built upon prior except for condition (14), if could be better to emphasize this new condition.

Regarding “how the algorithm eliminates incorrect guesses”: it doesn't (necessarily). For an incorrect guess the modified MDP may not be linear, as you point out. In a nutshell, there are two key guarantees for optimization problem 1. (1) that specifically $G=\bar G$ is not eliminated, and (2) that any $G$ that passes condition (14) leads to an accurate value estimation (even if the associated modified MDP isn't linear). To show guarantee (2), we use $q^\pi$-realizability only (no linear MDP properties) to prove that the true parameter $\psi_h(\pi^\star_G)$ realizing $q^{\pi^\star_G}$ for stage $h$ is included in $\Theta_{G, h}$ (Lemma C.2). Then the left hand side of condition (14) is exactly the confidence range for our estimator of $q^{\pi^\star_G}$. Condition (14) thus directly constrains these confidence ranges to be tight, leading to accurate estimators. Guarantee (1) gives legitimacy to including condition (14) in the optimization problem, by arguing that at least one choice ($G=\bar G$) leading to a near-optimal policy value is considered by optimization problem 1. Therefore, whatever $G$ the optimization problem ends up choosing can only have a larger or equal value estimation than this near-optimal value. This value estimation is accurate by guarantee (2), finishing the proof.

We will follow your suggestion to better highlight condition (14), and we will make sure that the proof intuition above is clearly communicated in the paper.

In the statement of problem 1, n does not depend on \delta.

Thanks for spotting the error in problem 1. We will revise it to $n = \text{poly}(1/\epsilon, H, d, C_\text{conc}, \log(1/\delta), \log(1/L_1), \log(1/L_2))$.

We thank the reviewer for their helpful feedback.

It would be beneficial if the authors could add the concrete definition of the previous non-trajectory data to make a direct comparison with full length trajectory data (Assumtpion 2). Also, the authors could add some comments on the hardness results without the trajectory data after the added definition.

We will add the definition of non-trajectory data and better highlight the corresponding negative result and how it contrasts with our positive one.

In Assumption 2, the notation $\phi(s_{h}^{1}, \cdot)$ is not clearly defined. It may lead to the meaning of $\phi(s_{h}^{1}, a)$ for all $a$.

The learner is actually given access to $\phi(s_h^1, a)$ for all $a \in \mathcal{A}$. Note that features corresponding to all actions are required for the optimization problem to be able to evaluate any choice of action. We will clarify the notation of Assumption 2 to reflect this.

Given the lengthy proof with complex notations and limited review time, the proof details are challenging to follow. Adding more discussion on algorithm design, including a pseudocode, and explaining the intuitions behind the proof would be helpful.

Although the algorithm itself is conceptually simple (solving the optimization problem and outputting the policy defined in Eq. (15)), we agree that its presentation was fragmented. Currently, the algorithm definition is only mentioned in one sentence directly above Eq. (15), making it easy to miss. To enhance clarity, we will add an algorithm pseudocode block to subsection 4.4 ("Learner") that explicitly outlines the algorithm steps. We will also improve the presentation of the intuition; see our response to reviewer sDBe for more details on this.

We thank the reviewer for their helpful feedback.

The presentation is a problem of this work. The notation system is not reading friendly, and there is no algorithm block. I suggest to add an algorithm to make the input and output clear.

As in the camera ready we can have an additional page, assuming the paper gets accepted, we will be happy to add an algorithm (solving the optimization problem and outputting the policy defined in Eq. (15)) to subsection 4.4 ("Learner") with clear inputs and outputs, thanks for pointing this out.

Regarding the notation, we thought a lot about how to present it in a clear and precise way, given the inherent complexity of dealing with many “modified MDPs” at once. We are keen to find ways to improve it further; could you please point to any specific notations that did not read well? Any further specific suggestions would be much appreciated.

The high-level idea is not clear.

We will improve the presentation of the high-level ideas; see our response to reviewer sDBe for more details on this.

The authors spend too much space on introducing their methods, and there is no explanation about the hard term in learning with independent terms.

We are having trouble understanding what you mean by "hard term in learning with independent terms". Could you clarify what you mean by this?

If you mean why trajectory data is crucial for our method, this is discussed in Section 4.2: “it is because we have full length trajectories that we can transform the data available to simulate arbitrary length skipping mechanisms.” In other words, without trajectory data, it is not possible to transform the existing data to data that one would have collected had one worked with a “skipping MDP”.

For example, why should we skip the states with small range(s)?

This is discussed in Section 4.3. We will improve this section to make sure the intuition that follows is clear. In a nutshell, if we could skip the states with small range(s), Lemma 4.2 shows the “modified MDP” would be approximately linear, transforming the problem to one we already know how to solve (e.g., with Eleanor [Zanette et al., 2020]). This would be great, but sadly it is hard to directly learn which states have small ranges. Instead, we use Lemma 4.2 as an analytical tool, as follows. We show that if we were to skip these states, the value function estimates in optimization problem 1 would be accurate. This guarantees that at least one near-optimal solution is considered by the optimizer. Without skipping, optimization problem 1 could optimize over the empty set, as it is possible that condition (14) would never be satisfied.

It is hard for readers to verify the result through touching the high-level intuition.

We hope that including the above, as well as the high-level argument using guarantees (1) and (2) in our response to reviewer sDBe will significantly improve this shortcoming.

Another concern is about the computational efficiency. Seems there is no evidence the optimization problem could be resolved efficiently.

The paper already acknowledges that computational efficiency is a concern. Through the skipping mechanism, our method inherently introduces complicated nonlinearities for value function estimations. It is an open question whether a computationally efficient solution to the problem considered in this paper exists at all. Our work only comments on statistical complexity, by discovering a polynomial-exponential complexity divide between trajectory data and individual transitions, which we found quite interesting. We think this contribution is of high interest and significance and thus warrants the paper to be published at NeurIPS even if we leave the question of efficient computation for future work.