Multiple-policy Evaluation via Density Estimation

Thank you for your efforts on reviewing our paper. We are confident that we can solve your concerns and questions. And we kindly request you to consider increasing your score if you think we address your concerns.

The hybrid setting of online and offline is confusing.

Sorry to cause the confusion. The setting of our problem is online. Our problem formulation is: given a set of target policies and an unknown MDP, evaluate the performance of all these policies. No additional dataset is given, interactions with the environment are necessary, so it is definitely online.

We do mention in the paper that our method is implemented more like in an offline manner. Since for offline RL, an offline dataset is given and no more interaction is allowed, i.e. we can only sample data from this fixed given distribution. This is exactly the second phase of our algorithm, where we have a fixed sampling distribution/policy derived from the first phase, and use data from this fixed distribution to perform the evaluation.

The connection between our method and offline RL.

In offline RL, an offline dataset is given and usually is assumed to have good coverage over the state space. In our scenario, if we already have an offline dataset that has good coverage over the space of these target policies, then we can directly use methods from offline RL to do off-policy evaluation of these target policies. However, it is not the case. We don't assume such a good offline dataset which is always unpractical because we have multiple policies, and even if it exists, it may be super sub-optimal with respect to the policies at hand, e.g. a uniform offline dataset.

What our method does is, we first interact with the environment to get some information of the target policies and then we can calculate an approximately optimal sampling policy in terms of the coverage over the target policies. We successfully show that only low-order samples are needed to construct such a sampling dataset/policy. In the second phase, we can just sample data using this fixed sampling policy to do policy evaluation just like offline RL.

Doubts on the reasonability of coarse estimation.

That's one of our contributions. In our work, we theoretically show the effectiveness of coarse estimation in multiple-policy evaluation problem. The coarse estimation has been proved reasonable.

We are not sure what exact concerns you have about coarse estimation. Are you concerned about how coarse estimation leads to final accurate performance evaluation? It is true that one can never achieve estimation up to $\epsilon-$accuracy by just doing coarse estimation with $\tilde{O(1/\epsilon)}$ sample costs, the technique is that coarse estimation is only used to approximate an intermediate quantity in the whole procedure, e.g. the sampling distribution $\hat \mu^*$ in our scenario. In our setting, to evaluate the final performance accurately, the second phase is unavoidable.

Coarse estimation is powerful since first, it only needs low-order samples which is negligible compared to the main order of sample costs, second, the multiplicative constant error it induces is acceptable. In other words, it enables us to approximate some useful intermediate quantities at an acceptable sample cost and error which serves an important role to achieve the ultimate goal.

The comparison with existing results is unclear which is better.

We already discussed the comparison of our sample complexity with the existing work in Section 5.1. It is unclear whether our sample complexity is universally better, however, our result is meaningful and significant by offering new insights for the problem and sharing many advantages. First, we solve the unfavorable dependency of $1/d^{max}(s)$ in existing results. Second, our work tackles the problem from a different perspective which is complementary to the existing method. Third, our sample complexity is cleaner and more interpretable than the existing result. Finally, we can parallelize our method while the existing method can't since it relies on trajectory stitch which is a practical advantage.

Why lower bound of MARCH need the assumption that policies are deterministic?

It is not an assumption. MARCH is our proposed algorithm to coarsely estimate all deterministic policies. Since we consider tabular MDPs, any policy can be expressed as a combination of deterministic policies. So it is enough to estimate all deterministic policies.

Why MoM is introduced? Why the bounded expectation in Lemma 4.7 does not directly indicate the high probability bound?

A result holds in expectation usually does not imply that the result holds with high probability. In our scenario, we get our importance density estimators by Algorithm 1 which uses stochastic gradient descent.

Other comments

Thanks for the comment. We will consider updating our paper to make the setting clearer, include more related works in offline RL and implement some experiments.

Thank you for your efforts on reviewing our paper. We really appreciate your positive feedbacks on our work. We agree that framing the task as 'offline' multiple-policy evaluation is kind of wired and may cause some unnecessary confusions. Thanks for pointing it out and we will consider reorganizing the language.

Thanks the reviewer for the detailed comments on our work. We are confident that we can solve your concerns well. And we kindly request you to consider increasing your score based on our following elaboration.

One of your main concerns is about our optimization objective (5):

The problem (5) is hard to solve since the inner maximization is non-concave. The sample complexity of solving (5) is unclear.

We want to correct this comment since it is not true. Our opt objective is a well-formulated convex problem. Let's denote $\sum_{s,a} \frac{(\hat d_h^{\pi^k}(s,a))^2}{\mu_h(s,a)}$ by $f_k(\mu)$. It is trivial that $f_k(\mu)$ is convex w.r.t $\mu$, and we know the maximum of a bunch of convex functions is still convex, hence, our objective $\max_{k\in[K]} f_k(\mu)$ is convex. It is ready to be solved by any convex optimization solver which means no sample is needed in solving (5).

Our opt problem (5) is identical to the one in Amortila et al. (2024).

The formulation same to the one in Amortila et al. (2024) is (4) instead of (5). (4) is common in many works since it is a standard formulation to describe the coverage property of a dataset. The emphasis of two works is different. We show that an up to constant optimal $\mu$ is enough in our scenario, hence we use coarse estimators to approximate (4), leading us to (5) which is easy to solve. They want an exact optimizer to (4) which is not straightforward to solve since the true visitation distribution is unknown, and they have to reformulate the problem as a RL problem.

The sample complexity of coarse estimation for all policies depends on poly(K).

It is not true. We want to emphasize that our low order term for coarse estimation is always bounded by $\tilde{O}(poly(H,S,A)/\epsilon)$ without $poly(K)$ which is a non-trivial contribution. We achieve this by proposing MARCH algorithm along with novel theoretical analysis (utilizing our proposed $\beta$-distance which possesses lots of nice properties). We briefly discussed it in Line 240-249 (left) in the main page. The detailed content is in Appendix B due to page limits. We will consider updating the paper to emphasize it more in the main page.

The complexity of estimating $\hat w$ in IDES is unclear.

The sample complexity of IDES is exactly the number of optimization iterations since we are using stochastic gradient. Specifically, in each iteration of optimization, one sample is used to estimate the stochastic gradient. The sample complexity of IDES is same as the one presented in Theorem 4.9, which is also presented in Algorithm 1 where the iteration number $n_h$ is specified.

Missing related works.

We appreciate it that you listed these related works which we didn't mention in the current version carelessly due to the massive amount of literature. We will definitely update our paper to include these works as well as the discussions on relations.

We also want to clarify here that the statement of "Amortila et al. (2024) is a "concurrent work" (L144)" is not dishonest. Our first draft version was made public in the same period as Amortila et al. (2024). But we understand reviewers have no information on our submission. We will update the expression to make it more appropriate for this submission.

The novelty of coarse estimation and other derivation techniques is limited.

We agree that low order sub-procedure is not new in the literature. And thanks for providing these related works. We will definitely include them in the updated version. However, we disagree that the existing results can imply our results on coarse estimation. The Lemma A.22 in Zhang and Zanette (2023) is based on estimation of transition functions, while we directly estimate visitations. And in our result, the constant (i.e. $c$ in Definition 4.1) can be any value (see Appendix A). Eq (45) in Li et al. (2023) is similar to our results, however, our formulation is much cleaner and more elegant based on simple concentration inequalities while they have more additional complex terms. We formally formulate the technique as coarse estimation in this work and present results that are ready to use in other different scenarios.

We disagree with the comment that the contribution of our work is just simply combining existing techniques. We presented our contributions clearly in the end of introduction section. Multiple policy evaluation is a very challenging and under-studied problem, and we provide very nice theoretical results for this problem which is a significant step along with many useful side products which have many potential usages.

Again, we appreciate your efforts on reviewing our paper. Please let us know if our above rebuttal solves your concerns and we are happy to keep discussing if you have more questions.

Thank you for your efforts on reviewing our paper. We appreciate your comments. And we kindly request you to consider increasing your score if we solve your concerns and questions.

The intuition behind $\beta$-distance does not seem entirely clear.

The $\beta$-distance is defined as follows $dist^{\beta}(x,y)=\min_{\alpha\in[1/\beta, \beta]} |\alpha x - y|$. The $\beta$-distance is zero as long as $\frac{x}{\beta} \le y \le \beta x$ which means $x$ approximates $y$ up to multiplicative constant $\beta$ error. The intuition behind $\beta$-distance is that we want a metric that can measure the coarse estimation. $\beta$-distance is such a metric. We showed that in Lemma B.5, if $\beta$-distance is smaller than $\epsilon$, then we can show $x$ is a coarse estimator for $y$. With this metric, we can focus on analyzing the bound of $\beta$-distance, $dist^{\beta}(\hat d, d)$, to show $\hat d$ is a coarse estimator for visitation distribution $d$. Analyzing $\beta$-distance is much more convenient than analyzing the formulation in Definition 4.1.

Thanks for the comment. The detailed elaboration of $\beta$-distance and MARCH is in Appendix B. We will consider updating the paper to clarify $\beta$-distance and MARCH more in the main page.

It would be better to include experiments that can show the $H^4$ dependency of sample complexity.

We do agree with the reviewer that having such an experiment will strengthen the paper, but practically, to show the dependency of $H^4$ in experiments would be extremely hard since it is just an upper bound with high probability. And we also want to reiterate that we consider the scope of our submission to be the advancement of our theoretical understanding of this problem. As such we hope to obtain a fair evaluation of our submission based on its merits to advance theoretical research in RL.

What's more, same as most theoretical works in RL, we were concerned with achieving the sharpest S and K (for this specific problem) dependence, which given the large size of S in applications is typically considered more consequential than dependence on H. Our minimax upper bounds achieve the sharpest dependence on S and A.

Elaborate that a different loss function might address the sub-optimal dependency on $H$. And is there any other approach to address it?

The loss function we defined to estimate the importance densities is a step-wise loss function (see L312-315 (right)). And we are adopting a step-by-step optimization procedure, i.e., we first get the estimator at step h-1 by minimizing the loss function $l_{h-1}(w)$, and then, utilizing it to get estimator at step $h$ by minimizing $l_h(w)$. Since the loss function at step $h$ depends on the estimator from last step, there is an additive error propagation which induces the $H^4$ dependency.

What we are thinking is to propose a comprehensive loss function $L(w)$ that incorporates all steps utilizing some coarse knowledge of transition functions. By minimizing this loss function, we can get the importance density estimator for all layers at once which avoids the step-to-step error propagation thus gets rid of $H^4$ dependency.

It is a good question that if there are other approaches to solve multiple policy evaluation problems well with optimal dependency on $H$. Based on our pipeline, we think it is hard to do more beyond the method we described above but we are optimistic that there exists totally different methods that can achieve it. Multiple policy evaluation is a challenge and under-studied problem which is worth exploring.