Doubly Optimal Policy Evaluation for Reinforcement Learning

Many thanks for the encouraging feedback and detailed review. Your comments truly highlight the core strength of this work: combining rigorous theoretical results with state-of-the-art empirical performance.

In your formulation your assume that Q_{\pi} is learned from the offline data, one would expect that a basic estimator of V(S0) in this case would be \sum_a \pi(a|S0) Q(a, S0) you should explain why it is not an appropriate estimator and add it to some of your empirical evaluations.

Thank you for your question! We want to clarify that in the setting we consider, the goal is to obtain an unbiased estimator. The $q$ value computed from the offline data is biased, as clarified in by Levein et al, 2020, “Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems”. There is no way to quantify this bias in practice. By contrast, our method is theoretically guaranteed to give an unbiased estimation regardless of the offline data we use (Lemma 2).

Based on your arguments in Section 4 (Lines 190-230) you require unbiasedness in every state not just s0, how does it reconcile with your argument that you enlarge the state space?

Thank you again for your insightful question. To begin with, we have enlarged the search space for policies instead of states. Specifically, in line 190-200, we presents the traditional wisdom which searches the unbiased behavior policies in a smaller policy space,

$\Lambda^- = \{\mu \mid \forall t, s, a, \mu_t(a|s) = 0 \implies \pi_t(a|s) = 0\}$.

In comparison, we search for the behavior policies in a larger space while still ensuring the unbiasedness (Lemma 2):

$\Lambda = {\mu \mid \forall t, s, a, \mu_t(a|s) = 0 \implies \pi_t(a|s)u_{\pi, t}(s, a) = 0}$.

A detailed proof of $\Lambda^-\subseteq \Lambda$ is provided in our Appendix A.1. The boardness of our policy search space enables us to find a better variance-minimizing behavior policy compared with the traditional wisdom.

Figure 1 shows similar patterns for sample counts of 1000 and 27000. Can the authors clarify why similar accuracy requires the same number of samples for differently scaled problems?

Thank you for your question. Let’s clarify point-by-point.

1. Larger Gridworld uses larger data size

The x-axis of Figure 1 represents the number of online episodes, as specified in line 476-477. To achieve the same relative error, the data size needed for the larger Gridworld is also larger. Specifically, in Girdworld with size 1000, the episode length is 10; while in Girdworld with size 27,000, the episode length is 30. Thus, under the same number of episodes, the data size is bigger for Girdworld with size 27,000 because of the longer episode length.

2. Y-axis as relative error

The y-axis on Figure 1 represents the relative error. As described in line 478-479, relative error is the error of each estimator normalized by the estimation error of the on-policy Monte Carlo estimator after the first episode. We use relative error beacause we believe it is a more direct representation of the variance reduction across different enviornments. This representation is also adopted by the ODI paper (Liu and Zhang, ICML 2024). Therefore, the same number of online samples does not lead to similar absolute error across differen Gridworlds.

3. Difference between DR and ODI

Besides, there is another notable difference in the results from Gridworld with different sizes. As shown in Table 1 of our paper, in Girdworld with size 1,000, DR outperforms ODI; while in Girdworld with size 27,000, ODI outperforms DR. Additionally, our method outperforms both ODI and DR by a great margin. This is because our method considers variance reduction in both data-collecting and data-processing phases.

Including a background on DR and ODI in the background section could enhance reader comprehension, as these are central to the analytical comparisons made.

Thank you for your suggestion! We have taken this to heart. We have spent our Section 5 comparing the variance reduction property of our method with ODI and DR (Theorem 5 & 6). We have also provided comprehensive discussions on these two works in the related work section too.

Details on estimating \ni in practical settings should be incorporated into the main text. Without this information, readers may struggle to understand the algorithm’s practical execution.

Many thanks for your constructive comment! We have added more detailes in estimating $\nu$ in our main text (line 435-436).

Thank you again for your positive review, and please let us know if we have addressed your questions!

In the experiments these offline datasets are collected by random policies. I wonder what if it is collected by an expert policy or other more sophisticated behavior policies, like in most RL settings? This is important to demonstrate the applicability of the proposed method on datasets with different expertise levels.

Many thanks for this constructive question! To answer your question, we made additional ablation studies to test the performance of our method when the offline data is generated by an expert policy: the target policy. This offline data set is considered to have better quality because it contains more state-action pairs that are frequently visited by the target policy. As for the other columns, the offline data is generated by 30 different policies with various performances. Both types of data sets contain $1000$ episodes.

Table: Relative variance of estimators on MuJoCo. The relative variance is defined as the variance of each estimator divided by the variance of the on-policy Monte Carlo estimator. Numbers are averaged over 900 independent runs (30 target policies, each having 30 independent runs).

Figure (link): Results on MuJoCo. Each curve is averaged over 900 independent runs. Shaded regions denote standard errors and are invisible for some curves because they are too small.

As shown in the results, data generated by expert policy (target policies) improves performance, and our algorithm scales with data quality.

The figure further shows that our method (with both expert and regular offline data set) outperforms all the other baselines by a large margin consistently. This demonstrates the fact that the majority of improvement comes from the algorithmic side. Specifically, our method reduces substantially more variance compared with ODI (Liu and Zhang, ICML [3]) and DR (Jiang and Li, ICML [4]) because we leverage offline data to achieve optimal online data collecting and data processing for policy evaluation. This superiority is proved in our Theorem 5 and Theorem 6. Across different MuJoCo environments with different quality of offline data, our method saves 50.8%-79.6% online samples, achieving state-of-the-art performance.

Thank you again for your review, and please let us know if we have addressed your comments and questions! We’ll be happy to discuss further.

[1] (NeurIPS Zhong et al. 2022) "Robust On-Policy Sampling for Data-Efficient Policy Evaluation in Reinforcement Learning" (ROS)

[2](ICML Hanna et al. 2017) "Data-Efficient Policy Evaluation Through Behavior Policy Search" (BPG)

[3] (ICML Liu and Zhang, 2024) “Efficient Policy Evaluation with Offline Data Informed Behavior Policy Design” (ODI)

[4] (ICML Jiang and Li, 2016) “Doubly Robust Off-Policy Value Evaluation For Reinforcement Learning” (DR)

Thank you for your time and comments. As you pointed out, our method is theoretically guaranteed and empirically proven to achieve lower variance than previous best performing methods.

For weaknesses:

A potential error in the proof… Unless I'm missing something, this seems to be an error that may invalidate the optimality of the proposed behavior policy, as the results is used in subsequent analysis and proofs.

Thank you for your feedback! However, we respectfully disagree with your assertion that this is an error. Let’s clarify it with a closer look.

By equation (12), $\mu^{*}_t (a|s) \propto \pi _ t (a|s) \sqrt{u _ { \pi, t} (s,a)}$ where the $\propto$ means “proportional to”. This notation is widely used, for example, by Sutton and Barto (2018), Reinforcement Learning: An Introduction, in their Chapter 13.

That is, $\mu^{*}_t (a|s) = \frac{\pi _ t(a|s) \sqrt{u _ { \pi, t} (s,a)}}{\sum_b\pi_t(b|s)\sqrt{u _ { \pi, t}(s,b)}}$, as written in our paper line 272.

Thus, $\sum_{a} \frac{\pi _ t(a|S_t)^2}{\mu^{*}_t (a|S_t)} u _ {\pi, t}(S_t,a)$

$=\sum_{a} \frac{\pi _ t(a|S_t)^2}{\pi_t(a|s)\sqrt{u_{\pi,t}(s,a)}} \sum_b\pi_t(b|s)\sqrt{u_{\pi,t}(s,b)}u _ {\pi, t}(S_t,a)$

$=\sum_{a}\pi_t(a|S_t)\sqrt{u _ {\pi, t}(S_t, a)} \sum_{b}\pi_t(S_t, b)\sqrt{u _ {\pi, t}(S_t, b)}$, which matches the proof in our paper.

In your derivation, you might have treated "$\propto$" as "$=$". Thus, you obtained

$\sum_{a} \frac{\pi _ t(a|S_t)^2}{\mu^{*}_t (a|S_t)} u _ {\pi, t}(S_t,a)$

$=\sum_{a} \frac{\pi _ t(a|S_t)^2}{ \pi_t (a| S_t) \sqrt{u_{\pi,t}(S_t,a)} } u_{\pi,t}(S_t,a)$

$= \sum_{a} \pi _ t (a|S_t)\sqrt{u _ {\pi, t} (S_t, a)}$.

After the second equal sign in equation (18), there's an extra ")" after $\bar{b}_t(S_t)$.

Thank you for your detailed review. Indeed, we believe that the “)” is necessary. In (18), the term containing $\bar{b}_t(S_t)$ is:

$V_{A_t}(\rho_t [q_{\pi,t}(S_t,A_t)-b_t(S_t,A_t)]+\bar{b}_t(S_t)\mid S_t)$. Here, the last “)” is for closing the variance term.

At the start of equation (20), $\nu_t(St,At)=$ should be removed.

We sincerely appreciate your detailed review! We have deleted the extra term in our revision.

In page 17, the $\mu^*_t$ after the third equal sign should be $\mu_t$.

Many thanks for pointing this out. We agree that this is a typo, and we have corrected it in the current paper. We assure you the last two typos are in the notation level of the appendix. Our results are checked by multiple fellows and are ensured to be correct. We thank you again for your careful review.

Figure 3 looks exactly the same as the Figure 3 in the following paper [1], however without citing the source.

Thank you for your suggestion. Figure 3 is a visual demonstration of the MuJoCo tasks screenshotted from OpenAI Gym (Brockman et al., 2016). We have added the citation for this picture.

While the experiments show good improvement of baseline algorithms, I would suggest the experiments be expanded to more environments such as Atari (RL with visual input) and more tasks in MuJoCo, where the sampling are generally less efficient.

Thank you for your advice. In fact, as shown in the following table, the environments we tested are among the most complex environments used in RL policy evaluation papers. Also, our method imposes weaker assumptions on the data.

For questions:

According to algorithm 1, will the offline dataset affect the performance?

Thank you for your questions. As with most offline RL approaches, the quality of offline data does impact the quality of the learned policy. This is inherent to offline RL and cannot be fully resolved, as pointed out by Levein et al, 2020, “Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems”.

As the rebuttal phase is nearing its end, we wanted to kindly follow up to check if you had any additional feedback or comments for our paper. Your input would be greatly appreciated, and we are confident to discuss and address any concerns you may have.

Thank you again for your time and effort in reviewing our work!

since the definition of u(s,a) needs lots of information e.g. the transition function.

To learn the behavior policy $\mu$, we do not need to estimate the transition function. This is because, as written in our Algorithm 1, we use Fitted Q-Evaluation (Le et al. (2019)) to learn $q$ and $u$. Notably, Fitted Q-Evaluation is a model free algorithm that does not require estimating the transition function.

And the optimal baseline function is found to be the q-value function of the target policy. If we already figure out an optimal baseline function, i.e. the q-value of the target policy, then it is done. No need to do importance-weighting any more.

1. Biased Estimation from q

We want to clarify that in the setting we consider, the goal is to obtain an unbiased estimator. The $q$ value computed from the offline data is biased, as clarified in by Levein et al, 2020, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems. There is no way to quantify this bias in practice. Thus, it is not done after we compute the $q$ value from offline data because it only gives biased estimation.

2. Leverage offline data while ensuring unbiased estimation

Bedies, as answered above for your first concern, using the $q$ value learned from the offline data to obtain an unbiased Monte Carlo estimator is a widely accepted norm. This strategy is adopted in the well-known ICML paper (Jiang and Li, 2016, Doubly Robust Off-Policy Value Evaluation For Reinforcement Learning) and the ODI paper [1] (also published on ICML).

Compared with these two previously best-performing approaches, our method also gives inherently unbiased estimation. Moreover, since our method considers variance reduction in both data-collecting and data-processing phases, it is theoretically guaranteed and empirically demonstrated to achieve lower variance than both of them.

The set $\Lambda$ of feasible behavior policies seems weird to me. It contains behavior policy $\mu$ such that $\mu(a|s)=0$ while $\pi(a|s)>0$ $(q(s,a)=0)$. In this case, the importance weighting estimator goes to infinity, let alone control the variance.

1. Infinity term will not be sampled

We are actually drawing samples using the behavior policy $\mu$ when collecting data. In the example you give, the action $a$ that has $\mu(a|s) = 0, \pi(a|s) > 0$ will never be sampled from the behavior policy $\mu$ because $\mu(a|s) = 0$. Thus, the infinity importance sampling ratio will never appear in samples.

2. Superiority of our policy search space

Our policy searching space

$\Lambda = \{ \mu \mid \forall t, s, a, \mu_t(a|s) = 0 \implies \pi_t(a|s)u_{\pi, t}(s, a) = 0 \}$

is proved to guarantee unbiasedness (Lemma 2), and it is larger than the traditional search space

$\Lambda^- = \{\mu \mid \forall t, s, a, \mu_t(a|s) = 0 \implies \pi_t(a|s) = 0\}$, as proved in Lamma 1.

A detailed proof of $\Lambda^-\subseteq \Lambda$ is provided in our Appendix A.1. The boardness of our policy search space enables us to find a better variance-minimizing behavior policy compared with the traditional wisdom.

Thank you again for your review! And we would be glad to answer any further questions.

[1] (ICML Liu and Zhang, 2024) “Efficient Policy Evaluation with Offline Data Informed Behavior Policy Design” (ODI)

Thank you for your time and comments! We believe we can address your comments and questions by detailed clarifications.

For weaknesses:

However, in the first stage, in order to calculate the optimal behavior policy and baseline function, lots of samples are needed and I think the samples needed in this stage are much more than the second stage.

1. Why leverage offline data

We consider the setting where offline data is much cheaper than online data. This setting is widely studied for off-policy evaluation problems, as specified by the well-known ICML paper Jiang and Li, 2016, Doubly Robust Off-Policy Value Evaluation For Reinforcement Learning; and it is also a key motivation for offline RL, according to Levein et al, 2020, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems.

Consider in most tech companies like TikTok, Google, and Amazon, there are large volumes of existing offline data obtained from previous algorithmic implementations. However, taking the advertisement recommendation systems widely used by these companies as an example, excessive online evaluation risks disrupting user experience and losing customers. Thus, these companies prioritize approaches that maximize the utility of their offline data while minimizing online interactions.

2.Existing methods

In most RL implementations, to avoid potential damage from bad target policies in the online execution phase, RL practitioners usually use offline data to approximate $q$ a priori. This provides a preliminary, though biased, estimation of the target policy’s performance. In the existing best-performing approaches, prior to performing policy evaluation, the DR method (Jiang and Li, 2016) learns $q$ from offline data to serve as a baseline function, and the ODI method [1] learns $q$ and $\hat{q}$ (an extended q-value they defined) from offline data to approximate their behavior policy. In short, their pipelines are:

(1) Learn $q$ (and $\hat{q}$) from offline data.

(2) Use the learned functions to perform online policy evaluation.

However, since these two methods only focus on reducing variance in data collecting (ODI) or data processing (DR) phase, respectively, they have not effectively leveraged the offline data.

3. Our Superiority

As clarified in our algorithm, we use existing and cheap offline data to learn the behavior policy. The variance reduction property of our behavior policy can greatly reduce the samples needed in the expensive online interaction.

Compared with the ODI and DR methods, which also need offline data to learn the $q$ function, we innovatively reduce variance in both data collecting and data processing phases. Thus, it is theoretically proved that our estimator achieves lower variance than ODI and DR (Theorem 5 and Theorem 6). Empirically, our method outperforms the existing methods by a large margin across environments, achieving state-of-the-art performance in saving online data.

In short, the pipeline of our method is:

(1) Learn $q$ and $u$ from offline data.

(2) Use the learned functions to perform online policy evaluation, saving 50.8% to 77.5% online samples.

Please let us know if we have addressed your question about this setting! We’ll be happy to discuss further.

As the rebuttal phase is nearing its end, we wanted to kindly follow up to check if you had any additional feedback or comments for our paper. Your input would be greatly appreciated, and we are confident to discuss and address any concerns you may have.

Thank you again for your time and effort in reviewing our work!