Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity

We thank reviewer ycxM for their valuable comments and feedback.

$~$

C.1 Diagrams and Intuition for Policy Class

We have uploaded a new pdf version of the paper that now contains a section with diagrams illustrating the construction of the hard MDP instance (Appendix D.5, pages 28-29) as well as a diagram of hyper-spherical sectors in Appendix B. We hope this provides some clarity and better intuition.

$~$

C.2 Improving the Lower-Bound

In the final version, with the additional allowed page, we will include this discussion on the improvement of the lower-bound:

To improve the lower-bound with the current construction, we would require the existence of a subspace packing with minimal chordal distance between subspaces $d_{\min} (\mathcal{C}) \geq \sqrt{d - g(\gamma)^2}$ (where $g(\gamma) = 2\gamma^2 - 1$) whose size is exponential in $d$ and the dimension of the subspaces is some constant fraction of $d$ (instead of $d^{1/4}$ as we have currently, this would be the crucial difference), say $c d$ for some $c < 1$. After $k$ rounds, information would be missing along a subspace of dimension $c^k d$, (instead of $d^{1/4^k}$) from which we could get a $\log d$ lower-bound. As far as we are aware, such a result is not available in the subspace packing literature, nor is a subspace covering result that would rule out the possibility of such a packing. We highlight that our MDP construction can be combined with any other subspace packing result, paving the way for improved lower-bounds should new subspace packing procedures be developed.

$~$

C.3 Typos

Thank you for pointing this typo out! As for $g(\gamma)$, it is defined in the statement of Lemma C.5 but in fact we use it before this (e.g.\ statement of Lemma C.4) - we will properly define it earlier on in Appendix C.

$~$

C.4 Finite Horizon

Finite-horizon linear MDPs can even be solved in the offline setting ($K=1$) with a total of $d \cdot H$ queries (where $Q^\pi_t$ realizability is assumed at each step $t \in \{1, ..., H\}$). This can be seen by at each step $t$ selecting $d$ queries whose features form a basis and then running a backward induction (See Appendix D.2 of Zanette (2021) for details).

Therefore, under our $Q^\pi$ realizability assumption, there is a gap between infinite horizon and finite horizon MDPs. There may also exist a gap between linear MDPs and our $Q^\pi$ realizability assumption, since the former is a stronger assumption.

$~$

C.5 Improving the Lower-Bound

See C.2 for a discussion of what is required to improve the lower-bound.

As we have stressed in the conclusion section, it is unclear if the $\log \log d$ dependence on $d$ is tight, which we leave as an open question. We add here that the subspace packing result we use currently is not tailored to our setting in the sense that we associate a learner's query with an entire subspace and use that all vectors in that subspace are far enough in inner product from vectors of any other subspace in the packing. But we only need this for the query not the entire subspace associated to the query. Therefore there is room for improvement with some more specific subspace packing reasoning but it remains unclear if this would allow an improvement to $\log d$ or higher.

We thank reviewer XsoY for their valuable comments and feedback.

$~$

B.1 Weaknesses of Proposed Problem Setting

The mentioned weakness on considering a worst-case evaluation error (instead of a regret guarantee) (point 1.) does not apply to the best policy identification (BPI) problem for which there is no worst-case evaluation (Definition 3.2). For the policy evaluation (PE) problem, it is true that the lower bound no longer holds for the proposed definition of Definition 3.1. Though this is not the setting we study and our definition (and results) remains relevant if the interest is a worst-case policy evaluation error.

As for point 2. on the additional assumptions not covered by our results, it is also common to have an infinite action space and no additional assumption on the sub-optimality gaps. Additionally, while it may be necessary to have coverage assumptions in an offline setting where the learner has no control over the data collection, this assumption need not be made when data is collected adaptively, as in our setting, since the learner is selecting the state-action pairs to query. For PE, in our second result (Theorem 4.5), the target policy can be fully revealed before collecting any data so the learner can choose the data with knowledge of the target policy (and indeed the hardness is introduced by the worst-case evaluation error). It is an interesting direction to understand if our results continue to hold under these additional assumptions or if these assumptions lead to a difference in the sample-efficiency of low-adaptivity RL. We leave this as future-work and will include a discussion about these assumptions in the final version.

We note that this setting has been considered in prior work (in particular Zanette (2021)) to establish some important results from the existing literature.

$~$

B.2 Comparison to Zanette (2021)

Please refer to Section A.6 in response to reviewer 7s3L for an additional comparison that we will include in Section 5.

The technical novelty of our work is using (as mentioned by reviewer 7s3L) ``novel tools such as subspace packing with chordal distance" (Soleymani & Mahdavifar, 2021) and applying them to our setting (see Appendix C). These tools have not been applied in an RL setting before as far as we are aware. In particular, the technical challenges include the following points.

• 1. Relating the subspace packing result with chordal distance to the existence of a subspace $B_k$ that is far (does not intersect the $\gamma$-hyperspherical cones) from all the learner's queries up to round $k$ if there are polynomial in $d$ number of queries (Section C). Information can then be erased in the directions of the subspace $B_k$ whose dimension is large if $k \neq \Omega(\log \log d)$.

The work of Zanette (2021) only requires showing the existence of a $1$-dimensional subspace. A volumetric argument can be used in their setting: since the sum of the volumes of an exponential (in $d$) number of hyper-spherical cones is less than the volume of the unit-sphere, there must exist a point in the sphere not covered by these exponentially many cones. This point can be used as the 1-dimensional subspace. However, we cannot proceed with a similar volumetric argument because we consider $m$-dimensional subspaces. The space in the sphere left vacant by the cones of the learner's queries can easily be used to argue the existence of individual points not covered by the cones, but not the existence of subspaces of multiple dimensions. Instead, as mentioned above, we adapt tools from the theory of subspace packing.

• 2. Using the existence of these subspaces to extend the hard instance construction of Zanette (2021) to our setting over multiple adaptive rounds, while preserving the realizability assumptions. The extension over multiple rounds requires a careful treatment of the dependence of the queries on observed feedback (see Appendix D.4.2/E.4.2) to establish the existence of these subspaces, which does not arise when considering a single round as in Zanette (2021).

We have uploaded a new pdf version of the paper that now contains a section with diagrams illustrating the construction of the hard MDP instance (Appendix D.5, pages 28-29). We hope this provides some more clarity on the technical differences with Zanette (2021).

Aside from the technical novelties outlined above, we would like to stress the novelty of our main result, which is to show the need for dimension-dependent adaptivity in RL under linear function approximation.

We thank reviewer 7s3L for their valuable comments and feedback. $~$

A.1 Weaknesses

The significance of the presented result is in the existence of a dependence on the dimension $d$ for the amount of adaptivity $K$. From a theoretical perspective, this represents an important difference to $K$ being constant with respect to $d$. Our results provide an important step in studying the limits of RL under low-adaptivity by showing a dependence on dimension is unavoidable but much is left to understand. In particular, as we stress in the conclusion, it remains unclear if the $\log \log d$ dependence on $d$ is tight, which we leave as an open question.

$~$

A.2 Assumption that $\gamma \geq \sqrt{3/4}$

It is an assumption to make the analysis work. In the analysis, we show the existence of subspaces that are at least some chordal distance away from each other and the distance depends on $g(\gamma) = 2\gamma^2 - 1$. We assume $\gamma \geq \sqrt{3/4}$ to ensure $g(\gamma)$ is not too small, which allows us to get the right dependence on the dimension $d$. Given that the discount factor $\gamma$ in discounted MDPs is considered to be close to 1, this assumption is not restrictive.

$~$

A.3 Relationship between Theorems 4.4 and 4.5

The proofs of both Theorems are based on the same idea of the existence of a sequence of subspaces but the way the constructions of the MDP classes incorporate this sequence of subspaces is different. Therefore once the proofs have been reduced to using the existence of this sequence of subspaces, they are essentially the same. In the final version, we will better unify these sections to avoid repetition.

$~$

A.4 Choice of epsilon, delta for Theorems 4.4 and 4.5

The proof of both Theorems conclude with the existence of two MDPs which are indistinguishable given the queries made by the learner. One of them has value $+1$ and the other $-1$ (optimal state-value for best policy identification (BPI) and action-value of the target policy for policy evaluation (PE)) in the initial state.

If the learner aims to minimise $\delta$, it can randomise equally between $+1$ and $-1$ and have an error of $2$ with probability $1/2$. If the learner aims to minimise $\varepsilon$, it can deterministically output $0$ and have an error $\varepsilon$ of $1$ with probability $1$.

The values of $\varepsilon = 1$, $\delta = 1/2$ from Theorems 4.4 and 4.5 comes from taking the learner's best-case in the combination of these. However, we obtain the more general conclusion that any learner must be between $(2,1/2)$-soundeness and $(1,1)$-soundeness. The $(1,1)$-soundeness covers any value of $\varepsilon < 1$ and the $(2,1/2)$-soundeness with $\varepsilon = 2$ is the largest error value since our results hold for MDPs whose values are within $[-1,1]$ (we did not explicitly point this out but will in the final version). Therefore our results cover all relevant $\varepsilon$ values (for which there is a trade-off with $\delta$).

$~$

A.5 Fully-Adaptive Setting

"I don’t quite understand the second paragraph of Section 4" - we believe you meant Section 4.3 but please correct us if not.

This paragraph is related to the fully-adaptive setting where adaptivity constraints are removed and the number of batches $K$ is equal to the number of queried data-points $n$. This is in contrast to our main results (Theorems 4.4 and 4.5), which show $K > \log \log d$ are needed to solve BPI/PE when $n \gg K$ but $n$ is polynomial in $d$. In Appendix A, we show that in the fully-adaptive setting, $n \geq d$ is needed to solve BPI/PE to arbitrary accuracy (and therefore $K\geq d$ since $K = n$). We also show a matching upper bound of $K=n\leq d$ to fully solve a PE problem under an assumption on the action space, hence the matching upper and lower bound.

Therefore the relation between the lower-bound in the fully-adaptive setting and the main results is that they consider different settings of how $K$ relates to $n$.

$~$

A.6 Comparison to Zanette (2021) in Proof Sketch

In the final version, with the additional allowed page, we will include this comparison to the work of Zanette (2021) in Section 5:

Comparison to Zanette (2021): The work of Zanette (2021) erases information along a 1-dimensional subspace ($X$ is of rank $d-1$). Therefore after having observed one round of feedback, the learner only needs a single query to fully distinguish the MDP and solve the problem. Our constructions erase information along $m$-dimensional subspaces where we attempt to maximise $m$ so that even after having observed feedback revealing this subspace, a polynomial number of queries remains insufficient to distinguish the MDP and solve the problem, more adaptive rounds are needed.