A General Framework for Off-Policy Learning with Partially-Observed Reward

We appreciate the valuable and thoughtful feedback from the reviewer. We respond to the concrete questions and comments in detail below.

Can you elaborate a bit on the design choices for the secondary rewards in your experimental settings?

Can you provide ablation studies on the secondary reward dimensions? I would like to see which dimensions are responsible for the HyPeR good performance. My intuition would say that, in the real data case for example, it is because of s_1 and s_2, since you can almost construct the target reward r based on those.

Thank you for the question and the valuable suggestion. In the real-world experiment, we focused on designing secondary rewards that are indeed worth maximizing, as explained in Section 6. For example, $s_1$ aims to prioritize sessions with an exceptionally long watch ratio, and $s_2$ aims to raise the engagement floor. We agree with the reviewer that $s_1$ and $s_2$ are correlated with the target reward. However, it is worth noting that the other two secondary rewards do not necessarily correlate with the target reward, and our algorithm does not use any prior knowledge about the correlation structure.

It is also interesting to see the center figure of Figure 14 in Appendix C.3. It shows that, in terms of the target policy value, the policy performance becomes much worse when we use only the secondary rewards (i.e., HyPeR’s performance at $\beta=1.0$), compared to the case where we use the only target reward (i.e., performance of r-DR). Similarly, the right-hand figure in Figure 14 demonstrates that the maximization of the target reward (i.e., performance of r-DR) does not improve the secondary policy value at all. This demonstrates that the sum of the secondary rewards that we used in our real experiment is only slightly correlated with the target reward. We will mention this observation in the main text in the revision.

Section on the tuning procedure: in my opinion, this section may be a bit misleading (not intentionally, of course). This is because the authors claim that we can simply apply a cross-validation procedure to tune a hyperparameter as we do in the supervised setting. However, this is not so trivial as they claim: the fact that we are dealing with an Off-Policy problem means that the data is not iid with the target data. Hence, performing a cross-validation on such data will not give an unbiased estimation of the performance of the target policy. Nevertheless, it may be a heuristic way of performing hyperparameter tuning (I've seen papers in the OPE/OPL domain doing it), but it must be acknowledged that it is a biased way of performing hyperparameter tuning.

Do you agree that the cross-validation procedure that you proposed is biased by design? In my opinion (if I am correct), you can still leave the section as is, but just acknowledge this caveat. Indeed, empirically, this procedure seems to work despite being biased, so it is not a big deal.

Thank you for the interesting questions. First, we would like to point out a potential critical misunderstanding made by the reviewer. That is, our data-generating process is indeed i.i.d (same as most other OPE papers), as formulated in Eq.(6), and thus there is no bias due to the data being non-i.i.d.

Can you provide an ablation study on what happens when you perform cross-validation with sampling without replacement? You claim that it is important to have sampling with replacement. Do you have empirical data to support this claim? It can be useful for researchers in the future.

Thank you for the interesting suggestion. Initially, we implemented the tuning procedure without replacement but found that it did not perform well. The issue is that the training data size during cross-validation becomes significantly smaller than that used in the actual training, making it difficult to precisely evaluate the variance of the policy gradient estimator and resulting in ineffective tuning. That is how we arrived at the current proposed procedure with replacement to ensure that the training data size during tuning is the same as that during actual learning.

The following table reports our additional experiment results comparing our method with and without replacement during weight tuning on synthetic data. The result suggests that tuning with replacement empirically outperforms tuning without replacement for a range of the true weight $\beta$.

We appreciate the valuable and thoughtful feedback from the reviewer. We respond to the concrete questions and comments in detail below.

In eqn (6), you write down the distribution in a way that allow $r_i$ to also depend on $o_i$. This will cause the problem of confounding bias, which does not give rise to an unbiased estimator of $q(x,a)$. See Kato et al. 2021 or Pearl, 2009 for details. Is this a typo or is there something missing? I found in the proof of Theorem 1 that you indeed assume $r$ to be independent of $o$ when conditioned on other observable variables (x, a, s). If this is an assumption, you should clearly state it.

This is a good catch. This is indeed a typo. We meant to write $\mathcal{D} := \\{ (x\_i, a\_i, o\_i, s\_i, r\_i) \\}\_{i=1}^n \sim p(\mathcal{D}) = \prod\_{i=1}^n p(x\_i) \pi\_0(a\_i \mid x\_i) p(o\_i \mid x\_i) p(s\_i \mid x\_i, a\_i) p(r\_i \mid x\_i, a\_i, s\_i)$,

where $r$ is independent from $o$. We have fixed this.

In Eqn (10), you perhaps miss out a $o_i/p(o_i|x_i)$ term in the second line, as you cannot evaluate this term when $o_i=0$ and $r_i$ is missing from the observational data.

Thank you for catching this too. This was indeed not intentional, and we do need $o_i/p(o_i|x_i)$ in the second line. We have already fixed this as well.

In the proof of Theorem 2, what are $s_i^{(j)}(x, a)$, $\sigma^2(x, a, s, o)$? Are they also typos? You also miss out a variance symbol in the first line of the proof.

Thank you for pointing these out. $s_i^{(j)}(x, a)$ was meant to be $g_i^{(j)}(x, a)$, which is the policy score function of the $j$-th element. In addition, we meant to write $\sigma^2(x, a, s)$, which is equal to $\mathbb{V}[r|x, a, s]$, instead of $\sigma^2(x, a, s, o)$. We have fixed all of these and added the variance symbol already, and they do not affect our main results.

If the reviewer has any technical points to discuss that may currently prevent them from reconsidering the score, we would be more than happy to discuss further.

Why did you need to introduce the combined policy value? And why did you define it with the sum of secondary rewards? In addition, It is better to change the name to "policy combined value", "policy secondary value" as it reflects more the quantities defined.

Thank you for the questions and valuable suggestions. As we stated in the introduction and formulation sections, we introduced the combined policy value because there exist various real-life scenarios where we aim to optimize both the target reward and the secondary reward. We incorporate such a prevalent motivation by defining the weighted sum of the two reward types as the combined policy value. This is the most simple, interpretable, and common way for controlling the prioritization [1] [2].

[1] Imo3:Interactive multi-objective off-policy optimization. Nan Wang, Hongning Wang, Maryam Karimzadehgan, Branislav Kveton, and Craig Boutilier.

[2] Pessimistic off-policy multi-objective optimization. Shima Alizadeh, Aniruddha Bhargava, Karthick Gopalswamy, Lalit Jain, Branislav Kveton, and Ge Liu

The baselines s-IPS and s-DR use aggregation function $F(s)$ over the secondary rewards, why they do not use also the primary reward when available, giving F(s, r)?

The s-DR and s-IPS estimators are only there as a baseline for the case where one type of reward was used because previously, it was common to rely either on dense secondary rewards or sparse target rewards for policy learning. The reviewer’s example ‘using target reward $r$ when available’ would not work well unless there is a suitable function $F$, which is unknown. In fact, finding a suitable function that appropriately balances the two rewards in a data-driven fashion is fundamentally what we were doing in our proposed tuning procedure, and this is not an already existing baseline.

If it is difficult to derive the theoretical value of $\\gamma^*$ as defined in your paper, one can derive the theoretical value of $\\gamma^{**}$ to minimize the MSE of the gradient, did you explore this path?

Yes, we did think about it. However, there is no guarantee that the minimization of MSE leads to a better performance in OPL. MSE is often used in OPE only because minimizing it is the ultimate goal of the OPE problem. In OPL, the ultimate goal is to maximize the test policy value, and thus it is reasonable to perform cross-validation regarding that metric rather than MSE.

There is a new line of work [2] that optimises for long term reward, using dense, secondary/surrogate reward, is there a reason why you did not compare to it?

Yes, we are aware of the work by Saito et al. However, as we have already discussed in the related work section, LOPE is critically different from our work. Specifically, LOPE considers the historical data of the form $\\mathcal{D}= \\{(x_i, a_i, s_i, r_i)\\}^{n}_{i=1} \\sim p(x)\\pi_0(a|x)p(s|x, a)p(r|x, a, s)$, where $s$ is short-term and $r$ is long-term reward. Under their formulation, the two types of rewards have no difference in observation density, i.e., the long-term reward is NOT partial. We will clarify this important distinction further in the revision.

Is there a reason why you did not include the large spectrum of pessimistic OPL?

Thank you for the interesting comment. We did not discuss the pessimistic OPE/OPL because they are irrelevant in our context. It is crucial to note that our main motivation is to address the prevalent problem of partial target rewards. The techniques around pessimism do not mean to address the problem that we are tackling. However, we could easily combine our proposed method with the pessimistic approach if one wants to do so. We will clarify this in the revision.

There is a problem in Equation (10), which is the core result of the paper. The gradient boils down to a doubly robust gradient that does not use any secondary reward. This is a major typo that needs fixing.

Thank you for catching this. This is indeed a typo, and we have added the observational weight ($o_i/p(o_i|x_i)$) on the second line of Eq.(10) in the revision.

We appreciate the valuable and thoughtful feedback from the reviewer. We respond to the concrete questions and comments in detail below.

The framework's data generation process (DGP) is restrictive and was not properly tested: If the DGP models missing, non delayed rewards, the claim that it can model delayed rewards is not supported, as these rewards can be observed after many interactions with the system and attribution of the reward to a certain action becomes the main difficulty [1]. How can we test if the DGP hold in real world problems? The real world experiment section in your paper is still a synthetic experiment simulated (with the DGP you suggest) on real world data.

Thank you for raising the good points. We argue that all the partial observation scenarios discussed in Section 1 can be addressed by our formulation and method. In particular, we would like to highlight a critical misunderstanding by the reviewer regarding the delayed reward setup. In this problem, $r$ represents the observed reward, and if it is missing, we define it as $r = N/A$, as described around L164. The observation indicator $o$ specifies whether the reward is observed ($o=1$) or unobserved due to delay ($o=0$). This formulation is consistent with the real-world delayed reward setup. Therefore, it is unnecessary to verify whether this DGP is reasonable when it is already known that the reward is delayed.

The policy gradient approach relies on $p(o|x)$ which is unknown, thus the PG is never unbiased as we need to model $p(o|x)$. In addition, this quantity can be really hard to model in real life scenarios (For example, we do not know what explains why a user did not purchase an item after he clicked on it).

In real world scenarios, we never have access to the observation probability $p(o|x)$. How do you estimate it in the real world? And what is the impact of its estimation in the efficiency of your algorithm?

This is a good question, and we are happy to clarify. We can estimate probabilities by solving a classification task that predicts $o$ from $x$ based on the available data. The reviewer particularly highlighted the difficulty of feature selection in estimating such probabilities. However, this challenge applies not only to the estimation of $p(o|x)$ but also to other aspects of the DGP, such as $p(r|x)$, which every method, including the baselines, must address. In practice, we can perform feature selection in a data-driven manner using cross-validation based on the policy value, as we always do.

Additionally, to investigate the robustness of our method to estimated probabilities $p(o|x)$, we performed additional experiments under unknown $p(o|x)$ and with varying noise. The results are summarized in the following tables. We can see that HyPeR is yet the most effective method despite the need to estimate $p(o|x)$. The results also demonstrate that HyPeR(Tuned $\gamma^*$) is particularly robust to the noise in $p(o|x)$, as it can adaptively add more weight to the secondary policy gradient when effective. We will add these interesting observations in the revision and thank the reviewer for guiding us to these results.

Combined Policy Value

Target Policy Value

We would like to thank the reviewer for the additional thoughtful comments and suggestions. We will address them below.

Delayed rewards should not be treated as missing rewards. In your formulation, a delayed reward is treated the same way as a missing reward, as once we do not observe it after making the action, we get $o=0$ and $r=N/A$. Delayed rewards are rewards that we observe, just a long time after playing an action, and requires a sequence aware framework and/or proper attribution, which is not taken into consideration by your formulation. Imagine the case of a video streaming platform, where each time the user watches a video, the system shows him a different ad for the same item. This user watches 4 videos (thus 4 ads) and later buys the item on another website. The sale is a delayed reward, it did not happen instantly and attributing it to the latest interaction/ad is suboptimal [1]. In your formulation, a delayed reward will not be taken into consideration as it is treated as missing.

We think this point is worth clarifying. The reviewer brought up a specific example that involves both the attribution and the delayed issues, whereas we only mentioned the latter. (Indeed, we cannot find the term “attribution” in our text and previous responses.)

In our formulation and motivation, there is a logging policy $\pi_0$ that might run for a week on the platform, during which we collect data of the form $\\{(x_i, a_i, o_i, r_i)\\}\_{i=1}^n$ (excluding $s_i$ here to focus on the reviewer’s point). $x$ might include both user and video features, and $a$ represents the ad for a product that was presented. If the product has already been sold during the week, we know that $o_i = r_i = 1$. If the purchase has not yet been observed, then $o_i = 0$ and $r_i = \text{N/A}$.

We think the reviewer may have conflated the attribution and delayed reward issues in this context. If the reviewer is arguing that we cannot be sure which action $a$ causes $r = 1$, that is not a problem of delay but rather a problem of “attribution” (as indicated in the title of the reference provided by the reviewer). We acknowledge that many real-world scenarios might involve both attribution and delay issues; however, we did not claim that our formulation incorporates the attribution problem (refer to Table 1 for clarification). It is also worth noting that one can think of a scenario where only the issue of attribution arises without any delay, demonstrating that these two problems are orthogonal.

We will explicitly discuss the distinction between attribution and delay problems in the paper to avoid any potential confusion. We would appreciate it if the reviewer could confirm whether our clarification above addresses their argument about our formulation.

A pretty straightforward definition of $F(s, r)$ is $F(s, r)=r$ when r is available, else $F(s, r)=F(s)$. Your method combines both signals in a clever way but it needs to be compared to methods, that at least have access to both signals ($s$ and $r$) when available.

Thank you for the interesting suggestion. We compared the suggested baseline of using $F(s, r)=r$ when $o=1$, and otherwise $F(s)$ with HyPeR (our proposed method). The result is summarized in the following table, which reasonably shows that our proposed method outperformed the suggested baseline (DR with $F(s, r)$) on all experimented true weights $\beta$. This observation empirically demonstrates how combining the target and secondary rewards is indeed crucial, and our proposed method does it effectively. We will add this additional result in the revised version.

Synthetic Data

Real-World Data

If the reviewer has any remaining concerns, we would be more than happy to discuss them.

We appreciate the valuable and thoughtful feedback from the reviewer. We respond to the concrete questions and comments in detail below.

It is common to consider a weighted combination of the original and secondary information in machine learning algorithms. Similar strategies are used in few-shot learning [2], informed learning [1], etc. The authors need to compare the proposed algorithm with them and emphasize their uniqueness.

We thank the reviewer for providing valuable references. It is important to note, however, that the papers and areas mentioned by the reviewer are completely orthogonal to our work regarding off-policy learning and, therefore, NOT directly comparable.

The paper considers the setting with some types of reinforcement learning settings and secondary information, and the authors only consider policy gradient, so I would not regard the framework as "general".

Thank you for pointing this out. We would like to clarify that we say our formulation is general because it can deal with various partial observation settings such as delayed rewards, missing rewards, multi-stage rewards, etc, under a unified framework as summarized in Table 1. We will clarify what we mean by "general" in the revision.

The strategy to tune the weight $\gamma$ is straightforward. Can the authors show the improvement in theory?

Thank you for raising this important point for discussion. While our tuning strategy might appear straightforward, this does not necessarily imply that it lacks novelty. In fact, our approach of intentionally using an incorrect (but tuned) weight $\gamma (\neq \beta)$ as opposed to the ground-truth weight $\beta$ that defines the combined policy value is, to the best of our knowledge, unprecedented. If the reviewer is aware of any similar ideas in the existing literature, we would be eager to learn about them.

It is also not entirely clear what the reviewer considers to be a meaningful and interesting theoretical contribution in this context. It is important to note that the baseline here is to merely and naively setting $\gamma = \beta$ without tuning, and it is therefore expected that parameter tuning would outperform this approach. (This is analogous to comparing a predictor without any hyperparameter tuning to one with hyperparameter tuning. In this work, we propose the latter with respect to the weight in the objective function, and it is clearly more desirable.)

Indeed, our experiments effectively demonstrate the advantage of weight tuning (HyPeR w/ Tuned $\hat{\gamma}$) over the naive use of the true weight (HyPeR w/ $\gamma = \beta$) across various experimental setups. Furthermore, it is worth noting that the parameter tuned via our procedure, $\hat{\gamma}$, is already nearly optimal when compared to the true optimal parameter $\gamma^*$ in terms of the combined policy value (as shown in Figures 4 and 5).

Dear Gholamali,

Thank you for your kind words and for bringing your work to our attention.

We find your study relevant to our work, and we have included the citation in our paper.

Best regards,

Rikiya Takehi