  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.
