Deployment Efficient Reward-Free Exploration with Linear Function Approximation

We thank the reviewer for the detailed comments and interesting questions. Below is our response.

About the writings: Thanks for the suggestion. We present the major high-level ideas in Section 4 and Section 5. We will try to combine the two sections together in the next version.

About the typos: Thanks for the careful review. We have fixed the typos accordingly. We have also added a table of notations in the revision.

About the question in Lemma 7: By "maps a context $X$ to a distribution over $X$", we mean that: given $X=\\{x_1,x_2,...,x_n\\}$, $\pi(X)$ is a distribution over $\\{x_1,x_2,...,x_n\\}$. In other words, $\pi(X)$ could also be viewed as a $n$-dimensional probability vector. We do not use $\mathcal{K}(X)$ because the computation cost for $\mathcal{K}(X)$ might be large, while an approximation could be efficiently computed.

About Eq.(10) in Lemma 8: Note that $\mathtt{T}(\phi\phi^{\top},\Lambda) = \min\\{\frac{1}{\phi^{\top}\Lambda^{-1}\phi},1 \\} \phi\phi^{\top}$. By the fact that $\mathrm{Trace}( \mathtt{T}(\phi\phi^{\top},\Lambda)\cdot (\Lambda)^{-1} ) = \mathrm{Trace}( \min\\{\frac{1}{\phi^{\top}\Lambda^{-1}\phi},1\\} \phi\phi^{\top}\cdot \Lambda^{-1} )$, which is equal to $\min\\{ \phi^{\top}\Lambda^{-1} \phi , 1\\}$. Then the inequality holds by the condition (6).

About $\mu$ and $\theta(v)$ in Lemma 11 and 14: $\mu$ is the underlying unknown transition kernel, and $\theta(v)$ is the vector $\mu^{\top}v$, which is the payoff vector with value function as v. Here we omit the script of $h$ for simplicity.

About $F^0(\Lambda)$ in Lemma 15: We are sorry for the ambiguity. Here $F^0(\Lambda)$ denotes the matrix in the return line. We have fixed accordingly.

We thank the reviewer for the detailed comments. We present our response as below.

About tractability: The current algorithm suffers from a high polynomial sample size, which is unaffordable in most applications.

About repeated sampling: We admit the current algorithm is not practical in many cases. We have to use these independent datasets to keep the correctness of the linear regression. It would be an interesting direction to weaken the dependence to reduce the sample complexity.

We thank the reviewer for the efforts in this review. We response as follows.

About technical problem without reachability :

The main problem is about evaluation of $\Lambda_h(\pi):=\mathbb{E}_{\pi}[\phi_h\phi_h^{\top]}]$ with the offline dataset before the $h$-th layer. We remark that online estimation is impossible in our setting because of the limitation of deployments. In this offline value evaluation (OPE) problem, with previous algorithm, one could get $\hat{\Lambda}$ be such that $\\|\hat{\Lambda}-\Lambda_h(\pi)\\| = O(\mathrm{err}_h)$, where $\mathrm{err}_h$ depends on the coverage ratio of datasets before the $h$-th layer.

Note the iteration method to find the coverage information matrix for the $h$-th layer is as follows: $\Lambda_1 = \zeta I$, $\pi_1$ be the empirical optimal policy w.r.t. $r_1 = \min\\{\phi_h^{\top}\Lambda_1^{-1}\phi_h,1\\}$, and then update $\Lambda_2 = \Lambda_1 + \hat{\Lambda}(\pi)$. Here we use the above OPE method to compute an estimator $\hat{\Lambda}(\pi)$ for $\Lambda_h(\pi)$, which has error $\mathrm{err}_h I$.

We do this recursively until we find some $n$ such that $\max_{\pi}E[r_n]\leq O(\epsilon)$. In general, we require $n = \text{poly}(d/\epsilon)$. In this process, the offline error $\mathrm{err}_h I$ is accumulated to be $n \cdot \mathrm{err}_h I$, and will leads to $\sqrt{n \cdot \mathrm{err}_h}$ error for the $h+1$-th layer.

In words, $\mathrm{err}_{h+1}\geq \Omega( \sqrt{ n\cdot \mathrm{err}_h})$ for some $n\geq 1$. As a consequence, the error increase very fast as the horizon gets large. We also remark that, with the reachability assumption, there exists $\pi$ such that $\Lambda_h(\pi)\geq z\mathbf{I}$ for some parameter $z$, which could help remove the regularization term by playing $\text{poly}(dH/z)$ samples.

With the proposed clipped evaluation method, instead of bounding $\hat{\Lambda}-\Lambda_h(\pi)$ with $\mathrm{err}_h \mathbf{I}$, we manage to prove that $\hat{\Lambda}-\Lambda_h(\pi)$ is bounded by $\mathrm{err}_h\Lambda$, where $\Lambda$ is some proper upper bound. One can thing $\Lambda$ as $\Lambda_h(\pi)$. In this case, we have $(1-\mathrm{err}_h)\Lambda_h(\pi)\leq \hat{\Lambda}\leq (1+\mathrm{err}_h)\Lambda_h(\pi)$, which help to eliminate the term $\mathrm{err}_h \mathbf{I}$ in the next steps.

We thank the reviewer for careful review and interesting questions. Below we present our response.

About numerical experiments: Due to repeated sampling to keep data independence, the order of $d$ and $H$ is large in the final sample complexity, which is a major obstacle to implement this algorithm with affordable number of samples. It is an interesting direction to reduce the order of these factors.

About price of reward-free learning: The algorithm is naturally reward-free, since the process of collecting data is independent of reward. As a price, the sample complexity is comparably large since we need to sample the same level repeatedly for many times.

About linear inaccuracy: When linear approximation is not accurate, the algorithm suffers linearly from the error term. By assuming $|Pv-\phi^{\top}\theta(v)|_{\infty}\leq \xi$ for all $v$ with infinite norm at most $1$, we could conduct the clipped offline evaluation with linear regression so that error due to linear inaccuracy is at most poly$(dH\xi) V$. To prove this claim, we provide a modified version of Lemma 14 allowing linear inaccuracy $\xi$ by adding poly$(dH\xi)V$ to the right hand side of the two inequalities.

About large d : As presented in the paper, the sample complexity depends on a polynomial factor of $d$, which is necessary in the worst case. In the case $d$ is very large, we require additional assumptions to simplify the function class so that the MDP is learnable.

About environments with inherent uncertainty: In an environment with inherent uncertainty, there would be a lower bound for the number of re-deployments. That is, it is impossible to learn the optimal policy with limited deployments. Nevertheless, our work provides ideas to explore more adaptive algorithms. For example, the proposed algorithm is robust under linear inaccuracy.

About balance between the exploration and the need to minimize exploration policies: Without the limitation on deployments, we could use a more adaptive strategy to explore the environment. For example, we can design reward function adaptively to explore some certain subsets of the state-action space with a set of different policies. However, in the case the number of deployments is limited, we have to find one policy to explore the whole state-action space, and we do so by devising efficient offline policy evaluation and offline policy optimization algorithms.