Long-term Off-Policy Evaluation and Learning
Yuta Saito Himan Abdollahpouri Jesse Anderton Ben Carterette Mounia Lalmas





Long-term Off-Policy Evaluation and Learning]Long-term Off-Policy Evaluation and Learning





Short- and long-term outcomes of an algorithm often differ, with damaging downstream effects. A known example is a click-bait algorithm, which may increase short-term clicks but damage long-term user engagement. A possible solution to estimate the long-term outcome is to run an online experiment or A/B test for the potential algorithms, but it takes months or even longer to observe the long-term outcomes of interest, making the algorithm selection process unacceptably slow. This work thus studies the problem of feasibly yet accurately estimating the long-term outcome of an algorithm using only historical and short-term experiment data. Existing approaches to this problem either need a restrictive assumption about the short-term outcomes called surrogacy or cannot effectively use short-term outcomes, which is inefficient. Therefore, we propose a new framework called Long-term Off-Policy Evaluation (LOPE), which is based on reward function decomposition. LOPE works under a more relaxed assumption than surrogacy and effectively leverages short-term rewards to substantially reduce the variance. Synthetic experiments show that LOPE outperforms existing approaches particularly when surrogacy is severely violated and the long-term reward is noisy. In addition, real-world experiments on large-scale A/B test data collected on a music streaming platform show that LOPE can estimate the long-term outcome of actual algorithms more accurately than existing feasible methods.
 



<ccs2012>
<concept>
<concept_id>10002951.10003317.10003338</concept_id>
<concept_desc>Information systems Retrieval models and ranking</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10002951.10003317.10003359</concept_id>
<concept_desc>Information systems Evaluation of retrieval results</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>


[500]Information systems Retrieval models and ranking
[500]Information systems Evaluation of retrieval results







2024
2024
acmlicensed[WWW '24]Proceedings of the ACM Web Conference 2024May 13–17, 2024Singapore, Singapore
Proceedings of the ACM Web Conference 2024 (WWW '24), May 13–17, 2024, Singapore, Singapore
10.1145/3589334.3645446
979-8-4007-0171-9/24/05



[
    Orazio Pontorno0009-0009-0381-9971 Luca Guarnera0000-0001-8315-351X Sebastiano Battiato0000-0001-6127-2470
    April 29, 2024
==============================================================================================================





§ INTRODUCTION
 
The rate of algorithmic developments in online services, such as recommender and search engines, is rapid. These developments range from minor adjustments in feature preprocessing to complex alterations within the algorithm itself. Efficient and reliable measurement of the value of these ideas is thus crucial to the success of such services <cit.>. In particular, there is often interest in understanding the long-term outcome or reward (e.g., the annual number of active users or revenue) of these algorithmic changes to make informed decisions regarding algorithm evaluations and selection <cit.>.

The most accurate and intuitive method to achieve this is to run an online experiment (or A/B test) comparing new and baseline algorithms over a sufficiently long period. However, this approach of running two (or more) candidate algorithms for a long period presents several clear disadvantages:


    
  * The process of algorithm selection becomes extremely slow. If we conduct a year-long online experiment to measure the number of active users after a full year of deployment, we may miss opportunities to test other, better technologies that emerge over the course of that year.
    
  * Running an extended experiment with multiple algorithms can be highly risky, as some candidate algorithms may significantly underperform compared to others, negatively impacting user experience.


Therefore, it is advantageous to develop reliable statistical methods that use only existing historical datasets (collected by baseline algorithms prior to the experiment) and short-term experiments (e.g., several weeks to a month) to accurately estimate the long-term outcome of algorithms, allowing for quicker yet accurate algorithm evaluation and selection <cit.>.



A conventional approach to estimating the long-term outcome of algorithmic changes is through a method known as long-term causal inference (LCI) <cit.>. LCI aims to achieve this by using historical data to infer the causal relationship between short-term surrogate outcomes (such as clicks, likes) and long-term outcomes (such as user activeness indicator a year from now). For this to be valid, LCI necessitates an assumption known as surrogacy. This requires that the short-term outcomes hold sufficient information to identify the distribution of the long-term outcome. However, this assumption has been considered restrictive and challenging to satisfy because it demands the presence of sufficient short-term surrogates that enable perfect identification of the long-term outcome <cit.>. In other words, the connection between short-term and long-term outcomes must remain entirely consistent across all algorithms.

To estimate the long-term outcome without the restrictive surrogacy assumption, one could potentially apply off-policy evaluation (OPE) techniques <cit.>, such as inverse propensity scoring (IPS) and doubly-robust (DR) methods <cit.>, to historical data. Unlike LCI, OPE employs action choice probabilities under new and baseline algorithms, eliminating the need for surrogacy. However, typical OPE methods cannot take advantage of short-term rewards, which could be very beneficial as weaker yet less noisy signals particularly when the long-term reward is noisy. 

To address the limitations of both LCI and OPE methods, we propose a new framework and method, which we call Long-term Off-Policy Evaluation (LOPE). LOPE is a new OPE problem where we aim to estimate the long-term outcome of a new policy, but we can use short-term rewards and short-term experiment data. To solve this new statistical estimation problem efficiently, we develop a new estimator that is based on a decomposition of the expected long-term reward function into surrogate and action effects. The surrogate effect is a component of the long-term reward that can be explained by the observable short-term rewards, while the action effect is the residual term that cannot be captured solely by the short-term surrogates and is also influenced by the specific choice of actions or items. The surrogacy assumption of LCI can be viewed as a special case of this reward function decomposition since surrogacy is an assumption that completely ignores the action effect. As LOPE considers a non-zero action effect, it is a strictly more general formulation than LCI. On top of the reward decomposition, our new estimator estimates the surrogate effect via importance weights defined using short-term rewards. The action effect is then addressed via a reward regression akin to LCI.

To demonstrate the effectiveness of LOPE formally, we provide a theoretical analysis of its statistical properties showing that (1) it is unbiased under a less restrictive assumption than surrogacy of LCI, and (2) it produces much lower variance than typical OPE by leveraging short-term rewards to estimate the surrogate effect. We also design a new policy learning algorithm to directly optimize the long-term outcome based only on historical data by applying LOPE to policy-gradient estimation. Finally, we perform experiments on synthetic data and real-world data collected from a large-scale music streaming service. The results show that LOPE provides more accurate estimation, policy selection, and policy learning in terms of the long-term outcome than LCI and OPE methods, particularly with large reward noise and violation of surrogacy.




§ PROBLEM FORMULATION
 
 We first formally formulate the statistical problem of estimating algorithms' long-term values. Let x∈ denote the context vector (e.g., user demographics, consumption history, weather) and a∈ denote a (discrete) action where a indicates a particular product, video, song, or a ranking of them. w ∈{0,1} identifies a model or algorithm. For recommender systems applications, w could be seen as a recommender model index where w=0 indicates a baseline model currently running on the system, while w=1 indicates a new model not yet  deployed. π_w denotes the action distribution conditional on the context vector x (typically called a policy) induced by the model w, and thus π_w(a|x) indicates the probability of action a being chosen by model w for a given x. We also consider two types of rewards, namely short-term and long-term rewards, which are denoted by s ∈ and r ∈ [0,r_max], respectively. The long-term reward is the primary metric of interest such as the user activeness indicator a year from now. Long-term reward is often hard to observe directly since it requires deploying a policy for some long period. The short-term rewards can be multi-dimensional and typically consist of weaker signals such as clicks, conversions, likes, dislikes, and shorter-term user activeness, and are much easier to observe and less noisy than the long-term reward. It is thus crucial to leverage short-term reward observations in situations where the long-term reward is extremely noisy.

We define the long-term value (a measure of effectiveness) of a policy π_w induced by model w by the expected long-term reward:

    V(π_w) _p(x)π_w(a|x)p(r|x,a) [r] = _p(x)π_w(a|x) [q(x,a)],

where p(x) is an unknown context distribution and p(r|x,a) is an unknown long-term reward distribution. q(x,a) _p(r|x,a)[r] is the expected long-term reward function given context x and action a. If the long-term reward is defined as a binary indicator of whether a user remains active a year from now, V(π_w) is the expected fraction of users still active a year later under policy π_w. The main goal of this work is to develop an estimator V̂ that can accurately estimate the long-term value of a new model, i.e., V(π_1), without running a long-term experiment of π_1.


Below, we summarize existing approaches and their limitations.[In Appendix <ref>, we discuss contributions from related work.]



  
Long-term Experiment 
The Long-term Experiment method deploys π_1 for a long period and obtains the following data <cit.>.

    _E{r_i}_i=1^n_E,   r_i ∼ p(r |π_1),

where E stands for Experiment. p(r|π_1) is a marginal distribution of the long-term reward under π_1.[p(r |π_1) ∫_x,s p(x)π_1(a|x)p(s|x,a)p(r|x,a,s) dxds.] After running a long-term online experiment and obtaining _E, we can estimate the long-term value of policy π_1 by the following empirical average (AVG) estimator.

    1/n_E∑_i=1^n_E r_i.
 
Since we observe the long-term reward r in _E, the simple estimator in Eq. (<ref>) is unbiased, i.e., __E [] = V(π_1). However, this method is often infeasible, since we need to deploy the new policy for a long period to observe r.



  
Long-term Causal Inference (LCI) 
LCI enables an estimation of V(π_1) without running a long-term experiment <cit.>. Instead, this approach uses a historical dataset _H that contains short-term and long-term rewards, and a short-term experiment dataset _S that contains only short-term rewards. _H and _S are given as

    _H{(x_i,s_i,r_i)}_i=1^n_H,     (x_i,s_i,r_i) ∼ p(x,s,r |π),   
    _S{(x_i,s_i)}_i=1^n_S,     (x_i,s_i) ∼ p(x, s |π_1),

where _H is a historical dataset that contains only (x,s,r) and can be generated by an arbitrary policy.[It might be generated by the baseline policy π_0 or by multiple policies other than π_0 (i.e., the multiple logger setting <cit.>). LCI does not care about what policies generated _H, since it uses the dataset only to infer the connection between s and r.] _S is a short-term experiment dataset generated by running the new policy only for a short period and thus it contains only (x,s).



An important starting point of the LCI approach is the following surrogacy assumption <cit.>:
  (Surrogacy) The short-term rewards s satisfy surrogacy if r ⊥ a | x,s.


Figure <ref> illustrates this assumption, showing that surrogacy requires that every causal effect of the model w or action a on the long-term reward r should be fully mediated by the observed short-term rewards s. This enables us to characterize the expected long-term reward function q(x,a,s) by using only the context x and short-term rewards s as q(x,a,s) =q(x,s). LCI uses this assumption and estimates the long-term value V(π_1) as

    1/n_S∑_i=1^n_Sq̂(x_i,s_i;_H).

This estimator is performed on the short-term experiment data _S. However, since the long-term reward r is missing in _S, it leverages a long-term reward predictor q̂(x_i,s_i;_H) trained on the historical data _H as a proxy. For example, we can obtain q̂(x_i,s_i;_H) by performing the following regression problem based on _H:

    q̂ = _q' ∈𝒬∑_(x,s,r)∈_H( r - q'(x,s) )^2,

where 𝒬 is some class of reward predictors such as neural networks.

LCI is feasible with only historical and short-term experiment datasets and is justified under surrogacy <cit.>. Many existing methods to estimate the long-term value follows this high-level framework <cit.>. However, if this assumption is not satisfied, LCI may produce large bias. It also depends highly on the accuracy of the regression in Eq. (<ref>). Given that Eq. (<ref>) aims to predict the long-term reward, which is often highly sparse and noisy, this regression problem is often very challenging. Besides, LCI does not result in a new learning algorithm that directly optimizes the long-term value V(π) since it does not formulate action a nor policy π.





  
Typical Off-Policy Evaluation (OPE) 
Another high-level approach to feasibly estimate the long-term value V(π_1) is to apply typical OPE estimators on the historical dataeset _H <cit.>. Here we consider a situation where the historical dataset _H is generated by a baseline policy π_0 (called the logging policy in OPE), i.e.,

    _H{(x_i,a_i,r_i)}_i=1^n_H,  (x_i,a_i,r_i) ∼ p(x, a, r |π_0).


Given that the historical dataset _H contains long-term reward r observations, we can apply typical estimators such as inverse propensity score (IPS) <cit.> and doubly robust (DR) <cit.> as follows:

    1/n_H∑_i=1^n_Hπ_1(a_i|x_i)/π_0(a_i|x_i) r_i, 
       1/n_H∑_i=1^n_H{π_1(a_i|x_i)/π_0(a_i|x_i) (r_i - q̂(x_i,a_i)) + q̂(x_i,π_1) },

where q̂(x,a) is a predictor of q(x,a) and q̂(x,π_1) _π_1(a|x)[q̂(x,a)]. We can obtain q̂ by regressing the long-term reward r using context vector x and action a as inputs in the historical dataset. The weight w(x,a)π_1(a|x)/π_0(a|x) is called the importance weight, and due to this weighting, the IPS and DR estimators achieve unbiased estimation of the long-term value based solely on _H, i.e., 
    __H[] = __H[] = V(π_1).
 Despite their unbiasedness, it is well-known that these estimators based on importance weighting are likely to suffer from substantial variance <cit.>, which is given as

    n __H[ ] 
            =  _p(x)π_0(a|x) [ w(x,a)^2 σ^2 (x,a) ] 
          + _p(x)[  _π_0(a|x) [ w(x,a) Δ_q,q̂ (x,a) ] ] 
          + _p(x)[  _π(a|x) [ q (x,a) ] ],

where σ^2 (x,a)  [r|x,a] and Δ_q,q̂ (x,a)  q(x,a)-q̂(x,a). Note that the variance of IPS can be obtained by setting q̂(x,a) = 0 by definition. The variance reduction of DR against IPS is due to the second term where Δ_q,q̂ (x,a) can be much smaller than q(x,a) depending on the accuracy of q̂(x,a). However, the first term in the variance can be extremely large for both IPS and DR when the long-term reward is noisy and the weights w(x,a) have a large variation. In particular, the dependence of their variance on the long-term reward noise σ^2 (x,a) is a serious issue in our long-term value estimation task since the long-term reward r is often substantially noisy. It is thus crucial to be able to leverage short-term rewards s and short-term experiment data _S (if available) to deal with this variance issue of OPE methods. However, there is no existing method in OPE that can exploit short-term rewards to reduce variance.

To achieve this, the following develops a new statistical framework that can take advantage of short-term rewards to provably and substantially reduce the variance of OPE methods while assuming only less restrictive assumptions than LCI.





§ LONG-TERM OFF-POLICY EVALUATION
 
This section proposes our new framework for long-term value estimation called Long-term Off-Policy Evaluation (LOPE), which integrates the strengths of LCI and typical OPE, i.e., LOPE

    
  * can take advantage of short-term rewards and short-term experiment data to deal with noisy long-term rewards by reducing variance.
    
  * needs only more relaxed assumptions than surrogacy.
    
  * can produce a policy learning algorithm to optimize the long-term value more efficiently from only historical data.


Table <ref> summarizes the comparison among existing and our methods. Below, we describe the specific construction of the proposed estimator and its theoretical foundations.



 §.§ The LOPE Estimator

To construct our method, we begin with introducing the following decomposition of the expected long-term reward function.

    q(x,a,s)  = g(x,s)_surrogate effect +  h(x,a,s)_action effect,

where the surrogate effect g(x,s) is a factor of the expected reward function that is predictable by only the short-term surrogate rewards s while the action effect h(x,a,s) is the effect that is not predictable with only the short-term surrogates. This decomposition does not assume anything since we do not posit specific forms of the g and h functions. Our decomposition can be considered a generalization of the surrogacy assumption of LCI. If we assume that h(x,a,s) = 0,  ∀ x,a,s, then Eq. (<ref>) is reduced to q(x,a,s) =g(x,s), which is equivalently r ⊥ a | x,s, recovering Assumption <ref>. Therefore, as long as being based on Eq. (<ref>), the resulting estimator has a weaker condition to work compared to LCI. Eq. (<ref>) also enables us to effectively leverage the short-term rewards to substantially improve the typical OPE methods in terms of estimation variance.

Based on this decomposition, we design a new estimator by applying different estimation strategies between the g and h functions. Specifically, our estimator deals with the surrogate effect by applying importance weighting with respect to the short-term reward distributions and with the action effect via a reward regression as

    1/n_H{π_1(s_i|x_i)/π_0(s_i|x_i) (r_i - ĥ(x_i,a_i,s_i)) + ĥ(x_i,π_1) } ,

where π(s|x) = π(a|x)p(s|x,a) is the marginal surrogate distribution induced by policy π and w(x,s) π_1(s|x) / π_0(s|x) is called the surrogate importance weight (Figure <ref> provides an intuitive illustration of w(x,s)). We also use ĥ(x,π_1) _π_1(a|x)p(s|x,a)[ĥ(x,s,a)] in Eq. (<ref>). The first term of LOPE based on the surrogate importance weight aims to estimate the surrogate effect g(x,s) in Eq. (<ref>). In contrast, the second term of LOPE aims to estimate the action effect h(x,a,s) via a reward regression model ĥ, which can be obtained, for example, via performing ĥ = _h∑_(x,a,s,r)∈_H (r - h(x,a,s))^2, on the historical data. At a high-level, our LOPE estimator makes the most of the short-term rewards to estimate the surrogate effect g while typical OPE does not estimate the g function separately from the other factor of the reward function. In addition, LOPE addresses the action effect by applying a reward predictor ĥ while LCI completely ignores the h function by assuming surrogacy.



Below, we demonstrate desirable theoretical properties of LOPE. First, the following shows that LOPE can be unbiased under a new doubly-robust style condition.

 LOPE is unbiased, i.e., __H[] =, if either of the following holds true:

    
  * the surrogacy assumption (Assumption <ref>)
    
  * the conditional pairwise correctness (CPC) assumption, which requires: q(x,a,s) - q(x,b,s) = ĥ(x,a,s) - ĥ(x,b,s), ∀ a,b ∈,   s ∈.




Theorem <ref> provides conditions needed for the unbiasednesss of LOPE. It is unbiased under the surrogacy assumption. However, it can also be unbiased under a new assumption about the reward function estimator (ĥ) called conditional pairwise correctness (CPC), which only requires the reward function estimator accurately estimate the relative long-term reward differences between two different actions, a and b, conditional on short-term rewards s. This assumption is weaker than an accurate estimation of the (global) long-term reward function q(x,a,s).[This is because, if q(x,a,s) = ĥ(x,a,s), CPC is true, but the satisfaction of CPC does not necessarily imply q(x,a,s) = ĥ(x,a,s).] The important point here is that LOPE needs only one of the assumptions to become unbiased, which can be considered a new doubly-robust style guarantee.

Next, the following shows that the surrogate importance weight of LOPE can have substantially lower variance than the vanilla importance weight of IPS and DR.

 The difference in the variance of the surrogate and vanilla importance weights can be represented as follows.

    _p(x)π_0(a|x) [w(x,a)] - _p(x)π_0(a|x)p(s|x,a) [w(x,s)]    
    
         = _p(x)π_0(s|x)[ _π_0(a|x,s)[ w(x,a) ]  ]    ,

which is always non-negative.



Theorem <ref> characterizes the reduction in variance provided by surrogate importance weighting of LOPE. It is worth noting that the variance reduction is characterized by the variance of the vanilla importance weight _π_0(a|x,s)[ w(x,a) ], which suggests that surrogate importance weighting provides increasingly larger variance reduction when typical weighting has a larger variance. Based on Theorem <ref>, in Appendix <ref>, we also show that the noise-dependent term in the variance of LOPE has substantially lower variance than that in the variance of IPS and DR.



 §.§ Estimating Surrogate Importance Weights
 
When using LOPE, we need to estimate the surrogate importance weight w(x,s) from the logged data. We can achieve this by leveraging the following formula (derived via Bayes' rule).

    w(x,s) = _π_0(a|x,s)[ w(x,a) ].

Eq. (<ref>) implies that we need an estimate of π_0(a|x,s), which we can derive by regressing a on (x,s).
We can then estimate w(x,s) by computing ŵ(x,s) = _π̂_0(a|x,s)[ w(x,a) ]. This estimation procedure can easily be implemented even when the short-term reward s is high-dimensional. Even though LOPE is feasible with only historical data, we can additionally use short-term experiment data _S (if available) to estimate π_0(a|x,s) more accurately to further improve estimation of the surrogate effect.



 §.§ Extension to Policy Learning

Beyond estimation of the long-term value V(π_1), we can formulate a problem of learning a new policy to improve the long-term reward using only historical data. We can formulate this long-term off-policy learning (long-term OPL) problem as 
    max_θ V(π_θ)
 where θ∈ℝ^d is a policy parameter and V(π) is defined in Eq. (<ref>). A typical approach to solve this learning problem is the policy-based approach, which updates the policy parameter via iterative gradient ascent as θ_t+1←θ_t + ∇_θ V(π_θ). Because the true gradient ∇_θ V (π_θ) = _p(x)π_θ(a|x)[q(x,a)∇_θlogπ_θ(a | x)] is unknown, we need to estimate it from the logged data where we can apply LOPE. In Appendix <ref>, we show how we can easily extend LOPE to estimate the policy gradient ∇_θ V (π_θ) to learn a new policy to improve the long-term value based only on the historical data _H. 

The next section empirically demonstrates that LOPE results in a better policy compared to the baseline OPL methods of using IPS (Eq. (<ref>)) and DR (Eq. (<ref>)) to estimate the policy gradient ∇_θ V (π_θ).




§ SYNTHETIC EXPERIMENTS
 
This section evaluates LOPE on synthetic data to identify the situations where it is particularly appealing to perform policy evaluation, selection, and learning regarding the long-term value V(π_1). Our experiment code for the synthetic experiment is available at https://github.com/usaito/www2024-lopehttps://github.com/usaito/www2024-lope.




  
Synthetic Data Setup.
We create synthetic datasets to compare the estimates to the ground-truth long-term value of policies. We first define 1,000 unique (synthetic) users represented by 10-dimensional feature vectors x, which are sampled from the standard normal distribution. We then synthesize the expected reward function given x and a (note that ||=30 in our synthetic experiments) as

    q(x,a;λ) = (1-λ)g(x,f(x,a)) + λ h(x,a)

where the g and h functions define the surrogate and action effects, and the f function specifies the expected short-term reward function. Appendix <ref> defines the f, g, and h functions in greater detail. λ∈ [0,1] is an experiment parameter to control the violation of surrogacy. When λ = 0, surrogacy is satisfied while a larger value of λ increasingly violates the assumption. We use λ=0.5 as a default setup throughout the synthetic experiment to compare the methods under a moderate violation of surrogacy (we vary the value of λ in one of our simulations to investigate its effect on the comparison of the methods).

We synthesize the baseline (logging) policy π_0 by applying the softmax function to the expected reward function q(x,a) as

    π_0(a  |  x; β) =  exp( β· q(x,a))/∑_a' ∈exp( β· q(x,a'))  ,

where β is a parameter that controls the optimality and entropy of the logging policy, and we use β=0.5 as default.

In contrast, we define the new policy π_1 by applying an epsilon-greedy rule as

    π_1(a  |  x; ϵ) = (1 - ϵ) ·𝕀{a = _a' ∈ q(x,a') } + ϵ/||,

where the noise ϵ∈ [0,1] controls the quality of π_1, and we set ϵ=0.1 as default. Note that we define the logging and new policies by following the synthetic experiment setups of existing relevant work <cit.>.




  
Results in Policy Evaluation and Selection.
Figures <ref> to <ref> compare the MSE, squared bias, and variance of LOPE, LCI, IPS, and DR against the ground-truth long-term value V(π_1). We use the true importance weight w(x,a) for IPS and DR, while we estimate the surrogate importance weight w(x,s) using _H and _S as in Section <ref> for LOPE. We also report the accuracy if we could run a long-term experiment as a skyline reference (grey lines) showing the best accuracy achievable by the feasible methods.[To implement the long-term experiment method, we sample _E = {r_i}_i=1^n_E∼ p(r  | π_1) from the synthetic environment and compute  as in Eq. (<ref>).] 

Figure <ref> compares the estimators’ accuracy regarding long-term value estimation when we vary the size of the historical and short-term experiment data from 200 to 1,000 to compare how sample-efficient each method is. We observe that LOPE provides the lowest MSE among the feasible methods in all cases. LOPE is substantially better than the OPE methods, particularly when the data size is small (LOPE achieves 36% reduction in MSE from DR when n=200). This is because LOPE produces substantially lower variance as shown in Theorem <ref> by effectively combining short-term rewards and long-term reward while the OPE methods use only the latter, which is extremely noisy. In addition, LOPE performs much better than LCI, particularly when the data size is large (LOPE achieves 71% reduction in MSE from LCI when n=1,000), since LOPE has much lower bias. The substantial bias of LCI even with large data sizes is due to its inability to deal with the violation of surrogacy.

Figure <ref> reports the estimators’ accuracy when we vary the value of λ from 0.0 to 1.0 and control the violation of surrogacy (a larger λ increases the violation). The MSE of LCI increases with a more severe violation of surrogacy since it produces larger bias under these conditions as shown in the squared bias figure. In contrast, LOPE is not negatively affected by larger violations of the surrogacy assumption, since it is based on a reward function decomposition in Eq. (<ref>) and is free from surrogacy, showing its robustness to the potential violation of this unverifiable assumption.[Note that the MSEs of IPS, DR, and LOPE change with varying values of λ even though these methods do not rely on surrogacy. This is because, when we vary the value of λ, the ground-truth value of the new policy V(π_1) also slightly changes.]

Figure <ref> demonstrates the estimators’ accuracy under varying levels of noise of the long-term reward, i.e., σ_r from 1.0 to 9.0, to demonstrate how robust each method is to the noisy long-term reward. A larger noise on the long-term reward makes long-term value estimation increasingly difficult and it becomes more important to leverage short-term rewards as less noisy signals to reduce variance. The left plot of Figure <ref> shows that LOPE performs the best in most cases. In particular, when the noise is large, LOPE is much more accurate than IPS and DR since LOPE has substantially lower variance due to the effective use of the short-term rewards (LOPE achieves 45% reduction in MSE from DR when σ_r=9.0). In contrast, LOPE is more accurate than LCI when the noise is small, since the bias becomes more dominant in MSE in that case and LOPE generally produces much lower bias due to its less restrictive assumption compared to LCI.

Figure <ref> evaluates the estimators’ accuracy with varying values of ϵ from 0.0 to 0.5 to compare how robust each method is to different types of new policies. A smaller value of ϵ makes the new policy π_1 increasingly better than the baseline policy π_0, which makes estimation of V(π_1) relatively difficult. The left plot in Figure <ref> shows that LOPE is particularly effective compared to other methods when the performance difference between π_1 and π_0 is large (i.e., smaller ϵ) where estimating V(π_1) is challenging. This is because LOPE produces much lower bias than LCI and much lower variance than the OPE methods. As ϵ becomes large, every method performs similarly since the value of the two policies are almost the same. However, given that we are often interested in estimating the value of a new policy that potentially improves the baseline policy, the more accurate estimation by LOPE in such difficult and practical situations is considered appealing.



In addition to the comparison regarding long-term value estimation, we compare the policy selection accuracy of the methods under varying values of σ_r (long-term reward noise) from 1.0 to 9.0 and ϵ (new policy parameter) from 0.0 to 0.5. For every value of σ_r and ϵ, the new policy performs better, i.e., V(π_1) > V(π_0). While σ_r does not have any effect on the values of π_0 and π_1, by definition, a larger ϵ makes the new policy increasingly worse and the difference in the value of the policies smaller, making the policy selection task more challenging.[Specifically, when ϵ=0.0, V(π_1) = 1.61 > V(π_0) = 0.79, while when ϵ=0.5, V(π_1) = 0.82 > V(π_0) = 0.79.] Figure <ref> shows the probability that each method identifies the better policy of the two (π_1 and π_0) as the accuracy in policy selection. We observe that LOPE becomes particularly effective when the long-term reward noise is large and the value difference between π_1 and π_0 is small (i.e., larger ϵ) where identifying the better policy is challenging. Specifically, when σ_r = 1.0 and ϵ=0.0, LOPE, IPS, and DR perform perfectly, successfully choosing the better policy without making a mistake. However, as σ_r and ϵ become larger, LOPE becomes more superior to the baseline methods. In particular, when σ_r = 9.0 in the left plot, LOPE is about 85% correct in policy selection while IPS and DR are 79% correct. Moreover, when ϵ=0.5 in the right plot, LOPE is 65% correct while the OPE methods are 55% correct, showing that LOPE enables not only a more accurate evaluation but also a more accurate policy selection regarding the long-term value.





  
Results in Policy Learning.
We now compare the estimators in terms of their resulting effectiveness in OPL when they are used to estimate the policy gradient . Here, we use only historical data _H since OPL is a process of learning a new policy, and thus when it is performed, short-term experiment is infeasible. We compare the long-term value of policies learned via IPS, DR, and LOPE (they are called IPS-PG, DR-PG, and LOPE-PG, respectively, where PG stands for Policy Gradient) as well as the regression-based (Reg-based) baseline, which first trains a long-term reward predictor q̂(x,a) based on the historical logged data _H ∼π_0, and chooses the best action for each x based on the estimated reward (i.e., a greedy policy based on q̂). We use a neural network with 3 hidden layers to parameterize the policy π_θ and obtain q̂(x,a) for LOPE-PG, DR-PG, and the Reg-based method. 

Figure <ref> compares the long-term value of the policies learned by each method in the test set (higher the better) under varying logged data sizes (n_H) and levels of noise on the long-term reward (σ_r). Note that the test policy values achieved by each method relative to that of LOPE-PG are reported (LOPE-PG thus has flat lines). 

In the left plot, we see that every method performs more similarly with increased historical data sizes as expected, but particularly when the logged data size is not large (i.e., n_H = 500, 1000, 2000), LOPE-PG performs the best (when n=500, LOPE-PG achieved about 60% improvement over DR-PG). This superior performance of LOPE-PG in the small sample regime can be attributed to the fact that it reduces variance in policy-gradient estimation, which leads to a more sample-efficient OPL. Moreover, in the right plot, we can see that LOPE-PG is particularly effective when the long-term reward is noisy. In particular, when σ_r = 9.0, LOPE-PG outperforms DR-PG by about 80%. This observation is akin to what we observed in Figure <ref> regarding the OPE accuracy, and empirically demonstrates that the lower-variance policy-gradient estimation achieved by LOPE-PG results in a better long-term value via OPL. 





§ REAL-WORLD EXPERIMENT

This section demonstrates the effectiveness of LOPE using the logged data collected on a real-world music streaming platform.

We performed a long-term A/B test of three different policies (policy #1, #2, #3), which optimize content recommendations, over a 3-week period in May of 2023. Approximately four million users, chosen at random, were exposed to one of the recommendation policies during the experiment. We also use a historical logged dataset consisting of several million data points collected by a baseline policy prior to the experiment. In these datasets, for each user request, a recommendation policy recommends a content (as an action) such as a playlist, album, and podcast on the user's home page of the platform. The action space consists of the all candidate contents, and there are over thousands contents (i.e., || > 1,000) in our application. As a result of such recommendations, several short-term rewards were logged including streams, clicks, likes, and dislikes at week 1 (day 7). We regard streams at week 3 (day 21) as the long-term reward r and define the long-term value of a policy V(π) accordingly.

Using these large-scale historical and experiment datasets, we compare the policy evaluation accuracy of LOPE (ours), LCI, IPS, and DR by their MSE. Note that these methods use only the historical dataset and short-term experiment data to estimate the long-term value of the policies. In the real-world experiment, we never know the ground-truth long-term policy value V(π) as in the synthetic experiment, and thus we consider the estimates of the values of the policies based on the full experiment data as the ground-truth[It was regarded as the skyline reference (grey lines) in the synthetic experiment.] and compute the MSE of LCI, IPS, DR, and LOPE (ours) for each of the three different policies.

Table <ref> shows the MSE (lower the better) of the estimators when estimating the long-term value of three different policies from #1 to #3. The primary observation is that LOPE most accurately replicates the result of the actual long-term experiment for all three policies. Specifically, LOPE achieves 9.2%∼ 15.0% reduction in MSE compared to DR (the second best method), providing a further argument about its applicability in the industrial problem. In addition, LCI performs similarly to OPE in our real-world experiment. This observation is different from most of the synthetic results (Figures <ref> to <ref>). This is because in our real-world experiment, the action space is much larger than that of the synthetic experiment, and thus the variance issue of OPE becomes more severe. Thus, the result also implies that LOPE and its variance reduction property via leveraging short-term rewards (Theorem <ref>) is still effective in this large-scale problem.




§ CONCLUSION AND FUTURE WORK

This paper studied the problem of estimating and optimizing the long-term value of an algorithm without running a long-term online experiment. We proposed a new framework called LOPE, which integrates the advantages of Long-term Causal Inference (LCI) and typical Off-Policy Evaluation (OPE) methods. LOPE can exploit the useful short-term reward observations via a simple decomposition of the reward function and achieves lower variance than OPE methods under a doubly-robust unbiasedness. LOPE can also be readily extended to a policy learning method to optimize the long-term value directly via estimating the policy gradient efficiently.

Our work also raises several directions for future studies. First, our discussion does not cover how to pre-process the short-term rewards. However, a more refined method for performing representation learning of the short-term rewards may exist to improve the bias and variance of the LOPE estimator. Moreover, our LOPE framework as well as existing LCI and OPE methods assume the distributions of the short- and long-term rewards remain the same in the historical and experiment datasets (often called the comparability assumption <cit.>). However, there sometimes exist temporal effects in the reward distributions (e.g., users may prefer different types of songs in different seasons). Developing a framework to deal with violations of the comparability assumption would be considered valuable in better capturing the real-world non-stationarity nature of user preferences. Finally, even though LOPE estimates a week 3 metric most accurately in our real-world experiment, it would be valuable to perform a similar experiment regarding even longer-term metrics in the future.


ACM-Reference-Format






§ RELATED WORK
 
This section summarizes related literature regarding two existing approaches, i.e., LCI and typical OPE.



 §.§ Long-term Causal Inference (LCI)

Our work correlates with the literature on long-term causal effect estimation. Using short-term metrics as surrogates to model long-term causal effects is a typical strategy <cit.>. Early works relied on the surrogacy assumption requiring the short-term surrogates to entirely mediate the long-term outcome. <cit.> employed multi-dimensional surrogates, which may collectively fulfill the statistical surrogacy criteria even if no individual metric does so independently. Other recent studies have represented surrogates using sequential models <cit.>, and used surrogates for policy optimization, e.g., <cit.>. Several theoretical analyses derive the semiparametric efficiency bound in LCI <cit.> and deal with unobserved confounders <cit.>, which is of independent interest. However, all existing work in LCI relies on surrogacy or related assumptions, which are debatable and unverifiable, causing significant bias under their violations as shown in our simulations. Furthermore, the conventional LCI framework does not formulate an action distribution (policy) induced by an algorithm, thus failing to leverage algorithm similarities. LCI also fails to produce a learning algorithm for direct long-term outcome optimization. To address these limitations, we first provided a more general formulation that considers policy, enabling us to unify the LCI and OPE formulations, and combine the strengths of both to produce our LOPE framework. Consequently, LOPE does not rely on surrogacy and is provably more robust to violations of such controversial assumptions. In addition, LOPE can easily be extended to estimate the policy gradient from historical data, facilitating the learning of a new policy, which is not made possible by the LCI methods.




 §.§ Off-Policy Evaluation (OPE)

Off-Policy Evaluation (OPE) refers to a statistical estimation problem that estimates the expected reward under a new decision-making policy using only the historical dataset collected under a different policy. It has gained increasing attention in fields ranging from recommender systems to personalized medicine as a safer alternative to online A/B tests, which might be risky, slow, and sometimes even unethical. Among existing OPE estimators, DM and IPS are commonly considered the baseline estimators <cit.>. DM trains a reward prediction model to estimate the policy value. While DM does not produce large variance, it can be highly biased when the reward predictor is inaccurate. In contrast, IPS allows for unbiased estimation under standard identification assumptions but often suffers from high variance due to large importance weights. Doubly Robust (DR) <cit.> combines DM and IPS to improve variance while remaining unbiased. However, its variance can still be high under large action spaces <cit.>. As a result, the primary objective of OPE research has been to optimize the bias-variance tradeoff, and numerous estimators have been proposed to address this challenge <cit.>.

Compared to typical OPE methods, which do not assume or leverage short-term rewards and short-term experiment data, our LOPE is designed to harness these valuable additional inputs via a simple reward function decomposition. The use of short-term rewards is particularly crucial when estimating the long-term outcome, as it is often extremely noisy, and leveraging short-term surrogates as less noisy signals can make a significant difference. Broadly, our idea of reward function decomposition is related to a recent line of work on OPE for large action spaces <cit.>, which is based on a different type of reward function decomposition to leverage useful structure in the action space such as action clusters. While they also provide some variance reduction compared to typical OPE, especially when many actions exist, our motivation and formulation for enabling reasonable algorithm evaluations and selections leveraging short-term rewards are fundamentally different.




§ OMITTED PROOFS
 



 §.§ Proof of Theorem <ref>
 

To show the unbiasedness of LOPE, here we assume that there exists a function g: ×→ℝ that satisfies the following:

    Δ_q,ĥ (x,a,s) := q(x,a,s) - ĥ(x,a,s) = g(x,s),

which requires that the estimation error of the reward function estimator ĥ should be characterized by some action-independent function g(x,s). In fact, Eq. (<ref>) is satisfied if either of the surrogacy or conditional pairwise correctness is true.

Based on this assumption, the following derives LOPE's unbiaseness. From the linearity of expectation, first we have _ [  ] = _p(x) π_0 (a|x) p(s|x,a) p(r|x,a,s) [w(x,s)(r - ĥ(x,a,s)) + ĥ(x,π_1)]. Thus, the following calculates only the expectation of w(x,s)(r - ĥ(x,a,s)) + ĥ(x,π_1).

    _p(x) π_0 (a|x) p(s|x,a) p(r|x,a,s) [w(x,s)(r - ĥ(x,a,s)) + ĥ(x,π_1)] 
        = _p(x) π_0 (a|x) p(s|x,a)  [ w(x,s)(q(x,a,s) - ĥ(x,a,s)) + ĥ(x,π_1) ] 
        = _p(x) π_0 (a|x) p(s|x,a)  [ w(x,s)g(x,s) + ĥ(x,π_1) ]   ∵Eq. (<ref>)
        = _p(x)[ĥ(x,π_1) + π_0 (a|x)  p(s|x,a)  π_1(s|x)/π_0(s|x) g (x,s)  ] 
        = _p(x)[ĥ(x,π_1) + π_1(s|x)/π_0(s|x) g (x,s) π_0 (a|x) p(s|x,a)  ] 
        = _p(x)[ĥ(x,π_1) + π_1(s|x)/π_0(s|x) g (x,s) π_0(s|x)  ] 
        = _p(x)π_1(a|x)p(s|x,a)[ g (x,s) + ĥ(x,a,s) ] 
        = _p(x)π_1(a|x)p(s|x,a)[ q(x,a,s) ]   ∵Eq. (<ref>)
        =






 §.§ Proof of Theorem <ref>
 

Since _p(x)π_0(a|x)p(s|x,a) [w(x,s)] = _p(x)π_0(a|x)p(s|x,a) [w(x,a)] = 1, the difference in the variance of the surrogate and vanilla importance weights is attributed to the difference in their second moment, which is calculated below.

    _p(x)π_0(a|x)p(s|x,a) [w(x,a)]  - _p(x)π_0 (a|x)p(s|x,a) [w(x,s)] 
        = _p(x)π_0(a|x)p(s|x,a) [w^2(x,a)]  - _p(x)π_0 (a|x)p(s|x,a) [w^2(x,s)] 
        = _p(x)π_0(a|x)p(s|x,a)[w^2(x,a) -  (_π_0(a|x,s) [w(x,a)])^2 ] 
       = _p(x)[ π_0(a|x)  p(s|x,a) ( w^2(x,a) -  (_π_0(a|x,s) [w(x,a)])^2 ) ]  
        = _p(x)π_0(s|x)[ _π_0(a|x,s) [w^2(x,a)] -  (_π_0(a|x,s) [w(x,a)])^2  ] 
         ∵ p(s|x,a) = π_0(s|x) π_0(a|x,s)/π_0(a|x)
        = _p(x)π_0(s|x)[ _π_0(a|x,s) [w(x,a)] ]



Similarly to the variance of DR, which is given in Eq. (<ref>), the critical term in the variance is the first term, which depends on the squared importance weight and long-term reward variance. However, we can actually show that the first term in the variance of LOPE can be substantially smaller than that in the variance of DR.

 The difference in the first term of the variance of LOPE and DR can be represented as follows.

    _p(x)π_0(a|x)p(s|x,a) [w^2(x,a) σ^2(x,s)] 
        - _p(x)π_0(a|x)p(s|x,a) [w^2(x,s) σ^2(x,s)] 
       = _p(x)π_0(s|x)[ σ^2(x,s) _π_0(a|x,s)[ w(x,a) ]  ] ,

which is always non-negative.



Theorem <ref> indicates that the difference in the first term of the variance of the two estimators can be represented by the product of the noise σ^2(x,s) and the variance of the vanilla importance weight _π_0(a|x,s) [w(x,a)]. This suggests that the reduction provided by LOPE becomes increasingly large when the long-term reward noise and the variance of the vanilla importance weight are larger. This is particularly desirable in our long-term value estimation problem since the long-term reward noise is likely to be large. Theorem <ref> also justifies the empirical observation in Figure <ref> where we observe that LOPE substantially outperforms DR and IPS when the long-term reward is large due to its reduced variance.




 §.§ Derivation of Eq. (<ref>) in Section <ref>
 

    w(x,s) 
            = π(s|x)/π_0(s|x)
        =  p(s|x, a)  ·π(a|x) /π_0(s|x)
        = π_0(s|x)  (π_0(a|x,s) / π_0(a|x)) ·π(a|x) /π_0(s|x)
        = π_0(a|x,s)  π(a|x) /π_0(a|x)
        = _π_0(a|x,s)[ w(x,a) ]





§ EXTENSION TO LONG-TERM OFF-POLICY LEARNING (LONG-TERM OPL)

Beyond estimation of the long-term value V(π_1), we can formulate a problem of learning a new policy to improve the long-term reward using only historical data. This task, which we call long-term off-policy learning (long-term OPL), is framed as maximizing V(π_θ) with respect to θ∈ℝ^d, where θ denotes the policy parameters and V(π) is as defined previously. To address this learning problem, a common strategy is the policy-based method, which refines the policy parameters through gradient ascent, updating them as θ_t+1 = θ_t + η∇_θ V(π_θ), with η representing the learning rate. However, the policy gradient ∇_θ V (π_θ) = _p(x)π_θ(a|x)[q(x,a)∇_θlogπ_θ(a,|,x)] is not directly observable, necessitating estimation from the historical logged dataset _H.

We can unbiasedly estimate the policy gradient by applying importance weighting as follows.

    :=   w(x_i,a_i) r_i  (x_i,a_i),

where (x,a) := logπ_θ (a | x) is the policy score function, and w(x,a):= π_θ(a | x) / π_0(a | x) is the importance weight.

The IPS policy gradient in Eq. (<ref>) is unbiased (i.e., []=) under the full support assumption <cit.>. 

We can also apply the DR estimator to estimate the policy gradient to mitigate the variance issue. 

    := {   w(x_i,a_i) (r_i - q̂ (x_i,a_i))   (x_i,a_i) 
       + _π_θ(a|x) [ q̂ (x_i,a)  (x_i,a) ] },

As in OPE, DR incorporates a reward function estimator ĥ(x,a) ≈ q(x,a) while maintaining unbiasedness. Its variance is often lower than that of Eq.(<ref>). However, unless the long-term reward has minimal noise and the reward estimates ĥ(x,a) are highly accurate, its variance can still be extremely large, leading to inefficient OPL <cit.>.

To deal with the likely high variance of the typical off-policy policy gradient estimators, here we extend the LOPE estimator to estimate the policy gradient from historical data as below.

    := {    w_θ(x_i,s_i) (r_i - ĥ (x_i,a_i,s_i))   (x_i,a_i)  
       + _π_θ(a,s|x_i) [ ĥ (x_i,a,s)  (x_i,a) ] },

where w_θ(x,s) := π_θ(s|x) / π_0(s|x).

As a corollary of already shown theorems, we can show the unbiaseness of LOPE as a policy gradient estimator below.

 The LOPE policy-gradient estimator is unbiased, i.e., 
    __H[] = ,
 if either of the following holds true:

    
  * the surrogacy assumption (Assumption <ref>)
    
  * the conditional pairwise correctness, which requires: q(x,a,s) - q(x,b,s) = ĥ(x,a,s) - ĥ(x,b,s), ∀ a,b ∈,   s ∈.








§ ADDITIONAL EXPERIMENT DETAILS
 



  
Detailed Setup
This section describes how we define the reward functions to generate synthetic data. 
Recall that, in the synthetic experiments, we synthesized the expected long-term reward function as

    q(x,a;λ) = (1-λ)g(x,f(x,a)) + λ h(x,a),

where we use the following functions as g(·,·) (surrogate effect), f(·,·) (expected short-term rewards), and h(·,·,·) (action effect), respectively. 

    g(x,s)    = θ_g,c(x)^⊤ s , 
    
        f(x,s)    = x^⊤ M_f e_a + θ_f,c(x)^⊤ x +  θ_f,a^⊤ e_a, 
    
        h(x,a)    = x^⊤ M_h e_a + θ_h,c(x)^⊤ x +  θ_h,a^⊤ e_a,

 where (M_f,M_h), (θ_g,c(x), θ_f,c(x), θ_h,c(x)), and (θ_g,a, θ_f,a, θ_h,a) are parameter matrices or vectors to define the expected reward. These parameters are sampled from a uniform distribution with range [-1,1]. c(x) is a user cluster, which is learned by performing KMeans in the feature space , and different user clusters have different coefficient vectors in our reward functions. This imitates a real-world situation where the interpretation of the short-term rewards can be different across different user clusters. We set the default number of user clusters to 3. e_a is a 5-dimensional feature vector of action a, which is sampled from a standard normal distribution.



  
Additional Results

This section reports and discusses additional synthetic experiment results regarding varying numbers of user clusters and varying levels of noise on the short-term reward.

First, we compared the robustness of the estimators against varying levels of noise on the short-term reward. Figure <ref> shows the MSE, squared bias, and variance under different short-term reward noises. From the figure, we can see that LOPE, IPS, and DR are robust and perform similarly even with increased noise on the short-term reward, while LCI worsens when the short-term reward noise becomes larger. This empirical result suggests that LCI more crucially rely on the quality of the short-term reward. In contrast, LOPE relies on short-term rewards to reduce variance from the OPE methods, but it is more robust to noisy short-term reward. Second, we compared the accuracy of the estimators with varying numbers of user clusters (which affect the synthetic reward function as described in the previous subsection) to confirm the effect of this experiment parameter. Figure <ref> shows the MSE, squared bias, and variance of the estimators under varying numbers of user clusters. In the figures, we observe that there exist some small fluctuations in the accuracy metrics of every estimator with different numbers of user clusters, since this experiment parameter changes the reward functions and the value of π_1. However, it is also true that relative comparison of the estimators does not change with this experiment parameter.

