Evaluating the Robustness ofOff-Policy Evaluation
Yuta Saito, Takuma Udagawa, Haruka Kiyohara,
Kazuki Mogi, Yusuke Narita, Kei Tateno
Haruka Kiyohara, Tokyo Institute of Technology
https://sites.google.com/view/harukakiyohara

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

1

Machine decision making in recommenders

a coming user

an itemreward (e.g., click)a policy (e.g., contextual bandit)
makes decisions to recommend items,with the goal of maximizing the (expected) reward

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

2

The system also produces logged dataa coming user(context 𝒙)

an item(action 𝒂)

reward (e.g., click)(reward 𝒓)

logged bandit feedback collectedby a behavior policy 𝝅𝒃Motivation:
We want to evaluate the future
policies using the logged data.
September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

3Off-Policy Evaluation (OPE)
In OPE, we aim to evaluate the performance of a new evaluation policy 𝜋𝑒using logged bandit feedback collected by the behavior policy 𝜋𝑏. distribution shift෡hyperparameters of the OPE estimator 𝑽

whereexpected reward obtained by running on 𝝅𝒆 the real system

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

4Off-Policy Evaluation (OPE)
In OPE, we aim to evaluate the performance of a new evaluation policy 𝜋𝑒using logged bandit feedback collected by the behavior policy 𝜋𝑏. distribution shift෡hyperparameters of the OPE estimator 𝑽An accurate OPE is beneficial, because it..
• avoids deploying poor policies without A/B tests• identifies promising new policies among many candidates
Growing interest in OPE!

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

5Inverse Provability Weighting (IPW) [Strehl+, 2010]
IPW mitigates the distribution shift between 𝜋𝑏 and 𝜋𝑒 using importance sampling.

where：empirical average

Unbiased*, but large variance. *when 𝜋𝑏 is known or accurately estimatedHyperparameter: 𝜋ො 𝑏 (when 𝜋𝑏 is unknown)

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

6

Doubly Robust (DR) [Dudík+, 2014]
DR tackles the variance of IPW by leveraging baseline estimation 𝑞ො and performing
importance weighting only on its residual.

wherebaseline

importance weighting on the residual

Unbiased* and lower variance than IPW. *when 𝜋𝑏 is known or accurately estimatedHyperparameter: 𝜋ො 𝑏 (when 𝜋𝑏 is unknown) + 𝑞ො

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

7

Pessimistic Shrinkage (IPWps, DRps) [Su+, 2020]
IPWps and DRps further reduce the variance by clipping large importance weights.

clipped importance weightLower variance than IPW / DR.
Hyperparameter: 𝜋ො 𝑏 (when 𝜋𝑏 is unknown) (, 𝑞)ො +𝜆

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

8

Many estimators with different hyperparameters

Estimator Selection:
Which OPE estimator (and hyperparameters) should be used in practice?
September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

9What properties are desirable in practice?
• An estimator that works without significant hyperparameter tuning.
.. because hyperparameters may depend on the logged data and evaluation policy,
which might also entail risks for overfitting.
• An estimator that is stably accurate across various evaluation policies.
.. because we need to evaluate various candidate policies to choose from.

• An estimator that shows acceptable errors in the worst case.
.. because uncertainty of estimation is of great interest.
We want to evaluate the estimators’ robustness to the possible changes
in configurations such as hyperparameters and evaluation policies!
September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

10Is conventional evaluation sufficient?
Conventional OPE experiments compare mean-squared-error to evaluate theperformance (estimation accuracy) of OPE estimators.

evaluate only on a single set of configurations

Pitfall: fails to evaluate the estimators’ robustness for configuration changes..
(such as hyperparameters 𝜃 and evaluation policy 𝜋𝑒)

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

11

Towards more informative evaluation for practice
To tackle the issues in conventional experimental procedure, we propose
Interpretable evaluation for offline evaluation (IEOE), which can..

✓ evaluate the estimators’ robustness to the possible configuration changes✓ provide a visual interpretation of the distribution of estimation errors✓ be easily implemented using our open-source Python software, pyIEOE

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

12Interpretable evaluation for offline evaluation (IEOE)① set configurations spaces(hyperparameters 𝜃 andevaluation policies 𝜋𝑒)①② for each random seed 𝑠,sample configurations③ calculate the estimators’squared error on the sampled
configurations④ obtain an error distributionSeptember 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021②③④13

Visual comparison of OPE estimators
After gaining squared errors, we approximate cumulative distribution function (CDF).

We can interpret how the estimators are robust
across the given configurations.

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

14Quantitative performance measure
Based on the CDF, we can define some summary scores, which are useful for
quantitative performance comparisons.

• Area under the curve (AU-CDF) compares the estimators’ squared errors
below the threshold.

• Conditional value-at-risk (CVaR) compares the expected values of the estimators’squared error in the worst 𝛼 x 100 % trials.

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

15

Experiments in a real-world application• We applied IEOE to estimator selection in real e-commerce platform.
• The result demonstrates that SNIPW is stable across various configurations.
(the conclusion may change when we consider different applications)*The values are normalized by that of SNIPW.

The platform now uses SNIPW based on our analysis!
September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

16

Thank you for listening!
Find out more (e.g., synthetic and public data experiments) in the full paper!
contact: kiyohara.h.aa@m.titech.ac.jp

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

17September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

18

Direct Method (DM)DM estimates mean reward function.

where：empirical average

Large bias*, small variance. *due to inaccuracy of 𝑞ොHyperparameter: 𝑞ො

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

19

Self-Normalization (SNIPW, SNDR) [Swaminathan & Joachims, 2015]
SNIPW and SNDR address the variance issue of IPW and DR by using
self-normalized value for importance weights.

self-normalization

Consistent* and lower variance than IPW / DR. *when 𝜋𝑏 is known or accurately estimatedHyperparameter: 𝜋ො 𝑏 (when 𝜋𝑏 is unknown) (, 𝑞)ො

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

20

Switch-DR [Wang+, 2017]
Switch-DR interpolates between DM and DR (𝜏 → 0 to DM, 𝜏 → ∞ to DR).

use importance weighting only when the weight is small

Lower variance than DR.
Hyperparameter: 𝜋ො 𝑏 (when 𝜋𝑏 is unknown), 𝑞ො + 𝜏

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

21

DR with Optimistic Shrinkage (DRos) [Su+, 2020]
DRos use new weight function to bridge DM and DR (λ → 0 to DM, λ → ∞ to DR).

whereweight function to minimize error bounds

Minimize sharp bounds of mean-squared-error.
Hyperparameter: 𝜋ො 𝑏 (when 𝜋𝑏 is unknown), 𝑞ො + 𝜆September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

22

Conclusion• We studied evaluation of off-policy evaluation (OPE).
• When applying OPE to a real-world problem, we need to identify a robust estimatorthat works without significant hyperparameter tuning.

• We develop Interpretable evaluation for offline evaluation (IEOE) to provide fruitfulinsights on the estimators’ robustness.

We believe that IEOE will help practitioners to select a reliable OPE estimator!

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

23

References[Strehl+, 2010] Alex Strehl, John Langford, Sham Kakade, and Lihong Li. Learning from Logged Implicit
Exploration Data. NeurIPS, 2010. https://arxiv.org/abs/1003.0120[Dudík+, 2014] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li. Doubly Robust Policy
Evaluation and Optimization. Statistical Science, 2014. https://arxiv.org/abs/1503.02834[Swaminathan & Joachims, 2015] Adith Swaminathan and Thorsten Joachims. The Self-Normalized
Estimator for Counterfactual Learning. NeurIPS, 2015.
https://dl.acm.org/doi/10.5555/2969442.2969600[Wang+, 2017] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudík. Optimal and Adaptive Off-policy
Evaluation in Contextual Bandits. ICML, 2017. https://arxiv.org/abs/1612.01205[Su+, 2020] Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík. Doubly Robust
Off-policy Evaluation with Shrinkage. ICML, 2020. https://arxiv.org/abs/1907.09623[Narita+, 2021] Yusuke Narita, Shota Yasui, Kohei Yata. Debiased Off-Policy Evaluation for
Recommendation Systems. RecSys, 2021. https://arxiv.org/abs/2002.08536

September 2021

Evaluating the Robustness of Off-Policy Evaluation @ RecSys2021

24