On the Role of General Function Approximation in Offline Reinforcement Learning

We appreciate the reviewer for the valuable feedback, particularly the critical comments on writing have helped us improve the presentation of our paper. We have addressed the comments, and incorporated your suggestions in the revised paper. We hope the reviewer will be content with our response and revision. Additional comments are also welcome during the discussion phase.

Response to the first paragraph in the weakness part:

Your comments have been well-taken. We acknowledge that the paper and certain terminologies are somewhat technical. One reason for this perception is that we intended to convey as much information as possible to readers, which may result in a lack of clarity for general readers. In fact, to address this, we included a notation table in Appendix A to ensure the clarity of the notations.

In response to your comment about the data assumption by Xie and Jiang, we have added a detailed description at its first occurrence in the revision. Moreover, we have also incorporated your other suggestions into the revision (please refer to our subsequent responses). We hope that the presentation of our revised paper meets your expectations.

Response to Weakness 1

Thanks for your suggestion. The definition of Bellman-completeness was provided in Example 3. In the revision, we have added its definition at its initial occurrence to ensure better clarity. For the comparison with assumptions in previous works, please see our response to weakness 4. Regarding the Q-pi-realizability in example 2, corresponding to Definition 2, we have $\mathcal{F}^\star=${$Q_{\pi}|\pi\in\Pi$}, $\mathcal{F}=\mathcal{Q}$ and $\mathcal{G}=\Pi$. Explicit specifications in the examples have also been added in the revision.

Response to Weakness 2

Yes, you are correct. As stated in Example 3, the function $\phi$ is a mapping from $q$ to $\pi_q$, where $\pi_q$ is the optimal/greedy policy for $q$. This conversion is to emphasize the role of policy in RL analysis.

Response to Weakness 3

Most previous works construct MDP families satisfying assumptions of model-free functions (as mentioned in section 2.4.), whereas we propose building lower bounds for model-based functions. This type of construction enables us to extend the lower bound to a wide class of functions, making it more generic and versatile.

Response to Weakness 4

As stated in the paragraph before theorem 1, our data assumptions are stronger than the partial coverage (the assumption in works like [1,2,4,8]), exploratory coverage (the assumptions in works like [7]), and some refined data assumptions [5,6].

Our function assumptions are designed to verify if learning with weak function assumptions is possible. To build some generic lower bounds, we focus on the model class in the theorem. Our function class assumptions are weaker than the ones made in model-based analysis ([8], as mentioned in remark 4). A comparison with model-free algorithms is hard to compose. Nevertheless, when specifying to concrete functions like the value function and the density ratio, one can show that our function class assumptions are weaker than the ones with completeness-type assumptions (like [1,4,7]), and are at the same level compared with literature making only realizability-type assumptions (like [2,5,6]). We aim to demonstrate that completeness-type assumptions are particularly challenging to be mitigated. We have added this part of the comparison to our paper (Appendix F, due to the page limitation). Thanks again for your advice.

Response to Weakness 5

The lower bound construction (as shown in section D.1) can actually ensure that we can have $J_M(\xi(M))=J_M(\pi^\star)$, i.e., $\xi(M)$ is optimal w.r.t. $M$ from the initial distribution. Therefore, we have $J_M(\xi(M))-J_M(\hat{\pi})=J_M(\pi^\star_M)-J_M(\hat{\pi})$. This makes the comparison interesting. Also, a relationship with the coverage assumptions in previous works is that: coverage assumptions w.r.t. $\xi(M)$ are the same as $\pi^\star$ (which is optimal from every state or state-action pair), since we only consider coverage assumptions from the initial distribution.

Moreover, as the dataset is uncontrollable in most cases, assuming it covers the optimal policy is a bit strong. One may instead want to learn a policy that performs better than a specific one. This corresponds to the use of $\xi$.

[1] Bellman-consistent Pessimism for Offline Reinforcement Learning

[2] Offline reinforcement learning with realizability and single-policy concentrability

[3] is pessimism provably efficient for offline rl

[4] Provably good batch reinforcement learning without great exploration

[5] Batch value-function approximation with only realizability

[6] Refined value-based offline rl under realizability and partial coverage

[7] information-theoretic considerations in batch reinforcement learning

[8] Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage

We would like to thank the reviewer for the positive assessment of this work. We also appreciate your efforts and valuable time for carefully reviewing this paper.

We thank the reviewer for the valuable comment. Here are our responses:

Could you explain how it happens for $\xi(M)$ can be optimal while the value function class does not contain optimal $Q^\star$. Example or intuition could be helpful.

This is a good question. Note that $\xi(M)$ is only required to be optimal with respect to the initial state distribution, whereas $\pi^\star$ should be optimal from every state or state-action pair. The degree of strictness in optimality is the major difference.

We thank the reviewer for the valuable comment. Here are our responses:

Although lower bound results are also meaningful, it would be better if there are some upper bound results to understand what we can do.

The focus and novelty of this work is to develop new lower bounds to understand the fundamental limitation of learnability in offline RL. Several prior works have already established upper bounds on the same problem. In our paper, we have provided a review of these works in Sections 2.2 and 2.3.

As for the results in Section 6, can you explain more about the difference between the data coverage assumptions in (Xie & Jiang 2020) and the lower bound instance in Theorem 2?

Thanks for your question. In short, the data assumption in section 6 is weaker than the one in (Xie & Jiang 2020)---it is the partial coverage, while the one in (Xie & Jiang 2020) is even more stringent than exploratory coverage.

Besides, as for the data coverage assumption used in Theorem 2, how does it compare with the practical scenarios? Would it be too restrictive in practice (maybe in practice we may rarely encounter such bad case)?

The data assumption used in Theorem 2 is the partial coverage, which assumes that the dataset covers only one policy. This is practical and is fulfilled in benchmarks like D4RL. Furthermore, as we construct information-theoretic lower bounds, we prefer a "restrictive" condition, as it reveals a more crucial fundamental limitation.

I'm still trying to understand more about Def. 2. Consider the completeness assumption that $\forall f\in\mathcal{F}$, we have $\mathcal{T}^\star\in\mathcal{F}$. I wonder what the corresponding $\mathcal{F}$ and $\mathcal{G}$ in Def. 2 should be in this case?

Bellman-completeness is paired with realizability-type assumptions (e.g., $f^\star\in\mathcal{F}$ where $f^\star$ is the optimal value function) in most cases, thus we can conclude that $\mathcal{F}$ is realizable. Therefore, $\mathcal{F}$ in your question can be considered as $\mathcal{F}$ and $\mathcal{Q}$ in Definition 2 simultaneously. Also, we have that $\mathcal{F}^\star=${$\mathcal{T}^\star f| f\in\mathcal{F}$}.

It also seems unclear to me how Def. 2 "captures" what common completeness assumptions ensure: "the existence of a function class that can minimize a set of loss functions indexed by another function class".

This is a good question. Note that approximating one target $g\in\mathcal{G}$ with a function class $\mathcal{F}$ is identical to finding $f\in\mathcal{F}$ to minimize the loss $\lVert f-g\rVert_{\infty}$. Thus, the completeness-type assumption essentially imposes a set of loss functions as {$\lVert f-g\rVert_{\infty}|g\in\mathcal{G}$}.

We thank the reviewer for the valuable comment. Here are our responses:

1. The presentation is not clear. Some new words, such as exploratory-accurate(accuracy) and data assumption are used without pre-defined.

Your comments have been well-taken. In fact, the exploratory-accurate is defined right after the definition of the Realizability-type assumption (Definition 1). Different coverage assumptions are defined in the second paragraph in section 2.2.

In the revised version, we have made every effort to provide formal or informal definitions (or at least references to formal definitions) for technical terms when they are first used. For instance, in footnote 2, we provide a reference to the definition places for the terms you point out.

2. While there are examples about those assumptions, I think a big table summarizing and connecting existing concrete examples and assumptions and the proposed general assumptions can make the paper easier to understand.

Thanks for your suggestion. In the revision, we have added a table (on page 32 of the Appendices) that compares the assumptions made in this work with those in other related works. We believe this addition further enhances the quality of this paper.

It seems like function approximation on policy class or value function class results in impossible learning tasks, does it mean that learning with a model class might have positive results?

This is a good question. In fact, both model-free learning and model-based learning have positive results. Whether we have negative or positive results depends on the assumptions of function classes and the data. This paper aims to understand that if we can learn good policies under weak function assumptions in offline RL.