Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning

Thank you for your valuable feedback. We address your questions point-by-point.

Q1: How valuable is it to prove an instance-dependent bound when we have to impose a uniform coverage assumption? Which part of the proof requires uniform data coverage while partial data coverage does not work?

A1: In this work, we aim to achieve an optimal dependency on the complexity of the function class. For this purpose, we utilize the technique of reference-advantage decomposition to overcome the challenge posed by the additional error from uniform convergence over the function class $\mathcal F_h$. However, the uniform coverage assumption is essential in the reference-advantage decomposition when we prove the advantage part is dominated by the reference part. In detail, in the proof of Lemma F.1 in Appendix G.1, we need the uniform coverage condition to bound the last inequality of Eq. (G.2). Note that Lemma F.1 provides an upper bound on the weighted $D^2$-divergence, and plays a pivotal role in proving Lemma F.2 through reference-advantage decomposition. The uniform coverage assumption is also required in existing works on the optimal complexity for offline RL with linear function approximation [1][2]. How to relax the uniform coverage assumption to partial coverage assumption while still achieving the optimal statistical efficiency remains an open problem and we will study it in the future.

---

Q2: Can you provide a lower bound for general function approximations?

A2: That’s a good question. Currently we don’t know how to prove a lower bound for general function approximation in our framework. In most studies of RL with general function approximation, they do not provide a lower bound dependent on the complexity of the function class. As far as we know, the only exception is DEC [3], which is a framework for online RL and their application to offline RL remains open. How to obtain a lower bound for general function approximations is an interesting future direction, especially for offline RL.

---

Q3: The authors do not provide any numerical experiments in the paper. In my opinion, adding numerical experiments can better showcase the benefits of the proposed algorithm compared to other offline RL algorithms with general function approximation.

A3: The main focus and contribution of our work is on the theoretical side of offline RL. We plan to implement the proposed offline RL algorithm using general function approximation and compare it with existing empirically strong baselines on offline RL benchmarks in our future work.

---

Q4: More concrete examples beyond linear MDPs.

A4: Besides the linear MDP, the differentiable function class studied in [4] is also an example covered by our general function class. We have added a comment in Remark 3.7 in the revision.

---

[1] Xiong et al. 2023 Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent MDP and markov game, ICLR.

[2] Yin et a;. 2022a Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism. ICLR

[3] Foster et al. 2021 The statistical complexity of interactive decision making.

[4] Yin et al. 2022, Offline reinforcement learning with differentiable function approximation is provably efficient. ICLR

Dear Reviewer 38or,

We greatly appreciate your valuable feedback and are reaching out to see whether there have been any remaining questions that you have. If our response and revision have addressed your questions and concerns, we kindly request you to re-evaluate our work. Thank you!

Dear Reviewer 38or

As the deadline for the author-reviewer discussion is fast approaching, we would like to kindly inquire whether our response and revision have adequately addressed your questions and concerns. We really appreciate your feedback.

Thank you for your positive feedback. We address your questions as follows.

Q1: The work is overall incremental. The key techniques are largely known, either from online RL or offline RL. I can see that there are technical barriers in directly extending them to the problem of offline RL with general function approximation, but such extensions are mostly not too difficult.

A1: We agree with the reviewer that the extension of RL with linear function approximation to general function approximation is in general not too difficult given so many recent developments. However, as acknowledged by the reviewer, there are still numerous technical barriers that require effort, and our work is dedicated to addressing these challenges.

In pursuit of optimal statistical complexity in offline RL, we delve into leveraging variance information within the general function approximation setting—a previously unexplored domain. We believe our contribution in this regard is quite significant.

---

Q2: Improving the regret by a square-root of $d$ is quite standard for reference-advantage decomposition. This is more about the previous paper not doing the best job than developing truly novel method/analysis.

A2: We agree with the reviewer that improving the regret by $\sqrt{d}$ is anticipated when doing reference-advantage decomposition. However, such a technique has never been explored in offline RL with general function approximation, and we are the first to extend this decomposition technique to this setting.

---

Q3: How to interpret Thm 5.1?

A3: Thm 5.1 establishes an upper bound for the suboptimality of our policy $\hat \pi$. It is an instance-dependent result because it depends on the expected uncertainty, which is characterized by the weighted $D^2$-divergence along the trajectory. Both the trajectory and the weight function are based on the optimal policy and the optimal value function, respectively. Moreover, our result has an optimal dependency on the complexity of the function class when it is specialized to the linear case, characterized by the cardinality of the function class $\tilde O(\sqrt{\log \mathcal N})$.

---

Q4: When is Thm 5.1 better than instance-independent regret bounds?

A4: The suboptimality bound in Theorem 5.1 is always no worse than the corresponding instance-independent regret bounds under the same setting. In the worst case, $D_{ \mathcal F_h}$ $(z_h,\mathcal D_h,$ \mathbb V_h V^*_{h+1} $(\cdot,\cdot))$ in Theorem 5.1 can be bounded by $\tilde O(\frac{H}{\sqrt{K\kappa}})$ due to Lemma F.1, which reduces to the instance-independent regret bound.

---

Q5: Your coverage assumption is weaker, but does it really matter in practice?

A5: Our goal in comparing various coverage assumptions is to provide a comprehensive review of the assumptions prevalent in the literature. Additionally, we want to ensure that our coverage assumption is no more stringent than that of related works, ensuring a fair comparison of the efficacy of our method against others. It is worth noting that, in practice, verifying the coverage assumption may be challenging. This is precisely why we opt for the weaker coverage assumption—to maximize its practical satisfaction to the greatest extent.

---

Q6: You assume that dataset is produced by a single BP. In reality, this may not always be true. What is the impact of different BPs?

A6: The key part of our proof is Assumption 3.5, where we make assumptions on the distribution of the dataset. For simplicity, we consider the single behavior policy situation, which satisfies Assumption 3.5. But it doesn't really matter as long as we have an assumption similar to Assumption 3.5.

Thank you for your positive feedback. We address your questions point-by-point.

Q1: How to computationally efficiently obtain the condition for the second bullet point in 4.3?

A1: In Appendix C, we actually discuss how to efficiently compute the optimization problem $\max\{ |f_1(z_h)-f_2(z_h)|, f_1,f_2 \in \mathcal F_h: \sum_{k \in [K] } \frac{(f_1(z_h^k)- f_2(z_h^k))^2}{(\hat \sigma_h(s_h^k,a_h^k))^2} \leq (\beta_h)^2\}$. With the definition of the D^2 divergence, for any $f_1,f_2 \in \mathcal F_h$ satisfying $\sum_{k \in [K]}\frac{1}{(\hat\sigma_h(z_h^k))^2}(f_1(z_h^k)-f_2(z_h^k))^2 \le (\beta_h^2)$, we have $|f_1(z_h)-f_2(z_h)| \le D_{\mathcal F_h}(z;\mathcal D_h; \hat\sigma_h^2) \sqrt{(\beta_h)^2 + \lambda}$. Therefore, the second bullet is automatically satisfied. We have provided a more detailed explanation in Appendix C in the revision.

---

Q2: This paper claims it generalizes over the differentiable parametric models in [1]. Would the main theorem 5.1 improve the results obtained in [1]?

A2: Yes, our Theorem 5.1 improves the results obtained in [1]. The main improvement is the dependency on the complexity of the function class. Consider the covering number (or the cardinality for finite function class) for the differentiable parametric model studied in [1], which is covered by our framework. It has been proved in [1] that the covering number is $\tilde O(d)$, and their result has a linear dependency on $d$. Using our Theorem 5.1, we get a $\tilde O (\sqrt{d})$ dependency on $d$, which has a $\sqrt {d}$ improvement compared with the results obtained in [1].

---

Q3: This paper seems to be closely related to [Alekh et al. 23], however is not enough discussion about. May I consider this paper as an offline version of [Alekh et al. 23]? If not, what are differences?

A3: Alekh et al. 23 [2] is an inspiring work in the realm of online RL with general function approximation. We have drawn considerable insights from their research, particularly in the definition of $D^2$-divergence and the selection of the bonus function, which we have discussed. However, there is a key distinction beyond the apparent difference between the settings of online and offline RLs. Unlike the approach in [2], which involves a very intricate policy derived from the optimistic Q-value function or, under specific conditions, the overly optimistic Q-value function, our algorithm employs a simple greedy policy. This eliminates the need for an overly pessimistic Q-value function (the counterpart of the overly optimistic Q-value function as we’re doing offline RL) in addition to the pessimistic Q-value function. Our approach simplifies the algorithm significantly, distinguishing it from a direct offline version of the online algorithm in [2].

---

[1] Yin et al. 2022, Offline reinforcement learning with differentiable function approximation is provably efficient. ICLR

[2] Agarwal et al. 2023, $VOQL$: Towards optimal regret in model-free rl with nonlinear function approximation. COLT

Thank you for your strong support. We will address your questions as follows.

Q1: In section 3, I think you went a bit too far with the abuse of notation when defining Bellman operators. Is $f$ a function of the state or the state and action? How can you define the relationship between the Q and the V function of a fixed policy by Bellman's optimality operator?

A1: Thank you for your suggestion. We have defined $f(s) = \max_{a}f(s,a)$ and added a footnote to clarify the two slightly abused notations $f(s)$ and $f(s,a)$.

For the Bellman operator, we have two separate equations. One is the Bellman equation for value functions of a fixed policy. The other is the Bellman optimality equation for optimal value functions.

---

Q2: Assumption 3.2 is followed/complemented by other assumptions that are just given in-line. I suggest to state them as separate assumptions to improve clarity.

A2: Thanks for your suggestion. We have revised it to be two separate assumptions (i.e., Assumptions 3.2 and 3.3): realizability and completeness.

---

Q3: You define $\mathcal{N}$ as the cardinality of the hypothesis class but refer to it as the "covering number". The two are not the same, and the only covering argument that I could find was in Remark 5.3. for the linear case.

A3: Sorry for the confusion. In this paper, for simplicity, we assume the function class is finite, and we simply use $\mathcal N$ to denote the cardinality of the hypothesis class. For the infinite function class, we can use the covering number to replace the cardinality. Note that the covering number will be reduced to the cardinality when the function class is finite. We have added a clarification to avoid any misunderstanding.

---

Q4: Intuitive reason for why you also need an underestimation of the variance. A smaller variance estimate has the effect of inflating the value estimate since you are using inverse variance weights, so it would seem more optimistic than pessimistic.

A4: In fact, we only need an accurate enough estimation of the variance. In Eq. (6.1), we prove that the variance estimator is very close to the true variance (same order for large enough $K$). Therefore, we can use it as the weight (more precisely, inverse weight) for weighted regression. We have removed “pessimistic” from “pessimistic variance estimator” to avoid any confusion.

---

Q5: Typos: page 4 "closed to the optimal value function" page 6: "construct this variance estimator with..."

A5: Thanks for pointing out our typos. We have fixed them.