Deployment Efficient Reward-Free Exploration with Linear Function Approximation

We thank the reviewer for the insightful comments. Below we provide our responses to each point.

Regarding the bad dependencies on $d, H$ and $1/\epsilon.$

The main reason of the bad dependency is that: The main algorithm (Algorithm 1) involves two iterative processes, and since the results of different iterations all rely on the same offline dataset, these results are subtly coupled with each other. To break the statistical coupling, we simply make independent copies of the offline datasets by following the exploration policy and repeatedly sampling trajectories with fresh randomness.

One potential approach to improving the sample complexity is to prove concentration inequalities (e.g., Lemma 17) through union bound arguments. The major difficulty in this approach is that the complexity of the offline planning policy in Algorithm 3 and 4 could be high.

Regarding the proof sketch of the sample complexity.

Thanks for the suggestion. In Section 6, we present the framework for proving the main theorem. The most complicated components are the proofs of Lemmas 6 and 15, for which we will provide high-level proof sketches in the next revision.

Here, we present a summary of the sample complexity for each component of the algorithm. We will provide the details in Appendix E.

We begin by counting the number of sub-datasets required throughout the learning process. Then the sample complexity (total number of episodes) is obtained by multiplying this number $N = \frac{10^{9}d^7H^7\log\left(\frac{dH}{\epsilon\delta}\right)}{\epsilon^3}$.

Algorithm 4 (Truncated-Matrix-Eval): This algorithm requires at most $H$ sub-datasets.

Algorithm 3 (Matrix-Eval): This algorithm makes $O(m)$ calls to Algorithm 4, each requiring at most $O(Hm)$ sub-datasets.

The effectiveness about Algorithm 3 (including Algorithm 4) is provided in Lemma 18, which means we could achieve efficient truncation with recursive truncated planning.

Algorithm 5 (Planning) and Algorithm 6 (Planning-R): These two algorithms shares similar structure, which requires at most $H$ sub-datasets.

Algorithm 2 (Policy-Design): This algorithm makes $O(m)$ calls to Algorithm 3 and Algorithm 5, which requires at most $O(m^2H)$ sub-datasets.

Algorithm 1 (Exploration): This algorithm makes $H$ calls to Algorithm 2, which requires at most $O(m^2H^2)$ sub-datasets.

Putting all together, the total number of episodes is $O(m^2H^2N)=\tilde{O}\left( \frac{d^{15}H^{14}}{\epsilon^5}\right)$.

Regarding the typos.

Thanks for pointing out the typos and we will fix accordingly in the next revision.

We are grateful to the reviewer for the constructive feedback. Below we present our response.

Regarding the bad polynomial dependency.

Indeed our current sample complexity is far from being optimal. The main reason of the bad dependency is that: The main algorithm (Algorithm 1) involves two iterative processes, and since the results of different iterations all rely on the same offline dataset, these results are subtly coupled with each other. To break the statistical coupling, we simply make independent copies of the offline datasets by following the exploration policy and repeatedly sampling trajectories with fresh randomness.

One potential approach to improving the sample complexity is to prove concentration inequalities (e.g., Lemma 17) through union bound arguments. The major difficulty in this approach is that the complexity of the offline planning policy in Algorithm 3 and 4 could be high.

Regarding the lower bound.

While the precise trade-off between sample complexity and deployment complexity remains unknown, Theorem 3.2 in Huang et al., 2022 provides an $\Omega(H/\log_d(1/\epsilon))$ lower bound for the sample complexity under polynomial sample complexity constraints.

Regarding the numerical experiments.

The primary goal of this work is to eliminate dependence on reachability in both sample complexity and deployment complexity. To ensure our algorithm outperforms reachability-dependent approaches, we require the reachability parameter to be exponentially small. However, this leads to highly artificial MDP constructions. In practice, features are typically learned via neural networks, making it unclear how to test reachability parameters in such settings. Since different features yield different reachability values, evaluating the algorithm in a natural, practical environment becomes challenging.

Regarding $z$ in Algorithm 5.

We set $z = \frac{100000\epsilon^2}{d^4H^5}$. Please refer to line 781 for the parameter settings.

Regarding the tabular case.

Let $S$ and $A$ be respectively the sizes of the state space and the action space. By the method in (Zhang et al., 2022), one could reach the asymptotically optimal $\tilde{O}(\frac{SAH^3}{\epsilon^2})$ sample complexity (in episodes) with $H+1$ deployments. In this approach, we use the first $H$ deployments (which corresponds to $H$ batches in Zhang et al., 2022) to learn an approximate transition model $\tilde{P}$ using $\mathrm{poly}(S,A,H)$ episodes. Then we design an exploration policy $\pi'$ with minimax coverage under the approximate model $\tilde{P}$ such that $\max_{\pi} \sum_{s,a,h} \frac{d_{\pi}(h,s,a)} {d_{\pi'}(h,s,a)} = O(SAH).$ Here $d_{\pi}(h,s,a) = \mathbb{E}_{\pi,\tilde{P}} \mathbb{I}(s_h=s,a_h=a)$ denotes the occupancy distribution of the policy $\pi$ under the transition $\tilde{P}$. By running $\pi'$ for $O(\frac{SAH^3}{\epsilon^2})$ episodes, we could learn an $\epsilon$ optimal policy. Similar approaches have also been explored by Qiao et al. (2022).

References:

Huang et al., 2022: Towards deployment-efficient reinforcement learning: lower bound and optimality.

Zhang et al., 2022: Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning.

Qiao et al., 2022: Sample-efficient reinforcement learning with $\log\log(t)$ switching cost.

We appreciate the reviewer's valuable comments. We respond to each comment below.

Regarding the numerical experiments.

We thank the reviewer for the suggestion. The primary goal of this work is to eliminate dependence on reachability in both sample complexity and deployment complexity. To ensure our algorithm outperforms reachability-dependent approaches, we require the reachability parameter to be exponentially small. However, this leads to highly artificial MDP constructions. In practice, features are typically learned via neural networks, making it unclear how to test reachability parameters in such settings. Since different features yield different reachability values, evaluating the algorithm in a natural, practical environment becomes challenging.

Regarding the hardness in improving the sample complexity.

You are right that the sample complexity of our algorithm is $O(d^{15}H^{15}/\epsilon^5)$. In the next revision, we will provide the precise sample complexity in the theorem statement.

The main reason of the bad dependency is that: The main algorithm (Algorithm 1) involves two iterative processes, and since the results of different iterations all rely on the same offline dataset, these results are subtly coupled with each other. To break the statistical coupling, we simply make independent copies of the offline datasets by following the exploration policy and repeatedly sampling trajectories with fresh randomness.

One potential approach to improving the sample complexity is to prove concentration inequalities (e.g., Lemma 17) through union bound arguments. The major difficulty in this approach is that the complexity of the offline planning policy in Algorithm 3 and 4 could be high.

Regarding the trade-off between deployment efficiency and sample efficiency.

By Theorem 3.2 in Huang et al., 2022, achieving polynomial sample complexity requires at least $cH/\log_d(1/\epsilon)$ deployments for some constant c > 0. Any deployment budget below this threshold results in super-polynomial sample complexity. With $O(H)$ deployments, our algorithm achieves polynomial sample complexity. Moreover, with $\tilde{O}(dH)$ deployments, one could learn an $\epsilon$ optimal policy with a near optimal sample complexity of $\tilde{O}(\frac{d^2H^3}{\epsilon^2})$ with the help of online learning methods (He et al., 2022).

The remaining challenge is to determine the deployment complexity threshold for achieving near-optimal sample complexity. Specifically, we ask: Are $\Omega(dH)$ deployments necessary to attain the near-optimal sample complexity of $\tilde{O}(\frac{d^2H^3}{\epsilon^2})$?
We leave this problem as an open question for future research.

Regarding the finite state space.

We are sorry for the confusion. We will redefine $\mu$ as $d$ measures $(\mu_1,\mu_2,\ldots, \mu_d)$ over the state space $\mathcal{S}$ as in Jin et al., 2019. We emphasize that our algorithm and theoretical analysis hold even for infinite state spaces.

About the exact number of deployments.

The number of deployments is exactly $H$ assuming the initial state is fixed as $s_1$. Without this assumption, we need $H+1$ deployments. We will clarify this in the next revision.

Regarding the table to summarize the related works.

We thank the reviewer for this suggestion and will include the table in the next revision.

References:

Huang et al., 2022: Towards deployment-efficient reinforcement learning: lower bound and optimality.

He et al., 2022: Nearly minimax optimal reinforcement learning for linear Markov Decision Processes.

Jin et al., 2019: Provably efficient reinforcement learning with linear function approximation.

We thank the reviewer for the valuable comments. Below we provide our responses to each point.

Regarding the linear MDP assumption.

While our algorithm is currently limited to linear MDPs, extending these results to low-rank MDPs or MDPs with linear Bellman completeness would be an interesting direction for future work.

Regarding the table to summarize the related works.

Thanks for the suggestion. We will include this table in the next revision. The most important related works include: (i) Huang et al., 2022, which achieves $O(H)$ deployment complexity with the reachability assumption; (ii) Zhao et al., 2023, which obtains $O(dH)$ deployment complexity for general function approximation.

Regarding the trade-off between deployment efficiency and sample efficiency.

By Theorem 3.2 in Huang et al., 2022, achieving polynomial sample complexity requires at least $cH/\log_d(1/\epsilon)$ deployments for some constant c > 0. Any deployment budget below this threshold results in super-polynomial sample complexity. With $O(H)$ deployments, our algorithm achieves polynomial sample complexity. Moreover, with $\tilde{O}(dH)$ deployments, one could learn an $\epsilon$ optimal policy with a near optimal sample complexity of $\tilde{O}(\frac{d^2H^3}{\epsilon^2})$ with the help of online learning methods (He et al., 2022).

The remaining challenge is to determine the deployment complexity threshold for achieving near-optimal sample complexity. Specifically, we ask: Are $\Omega(dH)$ deployments necessary to attain the near-optimal sample complexity of $\tilde{O}(\frac{d^2H^3}{\epsilon^2})$? When the reachability assumption holds, it could be possible to improve the deployment complexity to $H$ while maintaining near optimal sample complexity with existing techniques. However, when the reachability assumption does not hold, the technical tools we have so far fail to address this problem. We leave this problem as an open question for future research.

References:

Huang et al., 2022: Towards deployment-efficient reinforcement learning: lower bound and optimality.

Zhao et al., 2023: A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation.

He et al., 2022: Nearly minimax optimal reinforcement learning for linear Markov Decision Processes