OFF POLICY EVALUATION AND LEARNINGFOR INTERACTIVE SYSTEMSYi SuCornell University
July 15th, 2021
1

News Feed

Search Engine

Food Recommendation

Autonomous Driving

Entertainment

Online Shopping

Interactive systems are everywhere2INTERACTIVE SYSTEMS SCHEMATIC
Context 𝒙 comes to the system

𝑥: user information, query information, etc.
3

INTERACTIVE SYSTEMS SCHEMATIC
Context 𝒙 comes to the system
System recommends action 𝒂𝑥: user information, query information, etc.
𝑎: ranking, recommended music/news, etc.
4INTERACTIVE SYSTEMS SCHEMATIC
Context 𝒙 comes to the system
System recommends action 𝒂User responds with reward 𝒓(𝒙, 𝒂)

𝑥: user information, query information, etc.
𝑎: ranking, recommended music/news, etc.
𝑟: click, dwell time, transactions, etc.

5

INTERACTIVE SYSTEMS SCHEMATIC
𝑥: user information, query information, etc.
𝑎: ranking, recommended music/news, etc.
𝑟: click, dwell time, transactions, etc.

𝒟=$𝑥! , 𝑎! , 𝑟! !"#Logged Dataset
6

INTERACTIVE SYSTEMS SCHEMATIC
We collect user interactions for:- Evaluating the system performance- Learning an improved system

7

EXAMPLE: NEWS RECOMMENDER
Context 𝒙:• User information/ Visiting history
Action 𝒂:• News article featured in the main
panel.
Reward 𝒓(𝒙, 𝒂):• Reading time8

CONTEXTUAL BANDIT PROTOCOL
Repeated Interaction:
Context 𝒙 i.i.d follows some distribution 𝑃 𝑥 .
(user information, visiting history etc.)

System chooses action 𝒂 according to some policy
𝜋(𝑎|𝑥).
(recommended music/news, ranking, etc.)

The user provides feedback 𝒓(𝒙, 𝒂) to the presented
action.
(click, dwell time, likes/shares, etc.)9Given a new system, how is the performance of it?

Policy Evaluation
How do we improve and learn new systems?

Policy Learning
10

POLICY EVALUATION➤ Definition [Utility of Policy]:
The expected reward/utility of a policy 𝜋 is:
𝑉 𝜋 = 𝔼!∼#(!) 𝔼&∼'(&|!) 𝔼)∼#()|!,&) [𝑟]11

ONLINE EVALUATION: A/B TESTING➤ Evaluation of Policy 𝝅:➤ Deploy system 𝜋 online.
➤ For user 𝑥 ∼ 𝑃(𝑥), draws action 𝑎 ∼ 𝜋(⋅ |𝑥), receives feedback 𝑟 𝑥, 𝑎 .
➤ Collect dataset in the format 𝒟 = {𝑥! , 𝑎! , 𝑟! }$!"#.
➤ Construct estimate of the policy utility:$
1
𝑉! 𝜋 = ' 𝑟!
𝑛
!"#

12

ONLINE EVALUATION: A/B TESTING
Draw 𝒟# from 𝜋#

5 #)Evaluate 𝑉(𝜋

' !)
𝑉(𝜋

Draw 𝒟, from 𝜋,

5 ,)Evaluate 𝑉(𝜋

' ")
𝑉(𝜋

Draw 𝒟- from 𝜋-

5 -)Evaluate 𝑉(𝜋

' #)
𝑉(𝜋

Draw 𝒟|ℋ| from 𝜋|ℋ|

5 |ℋ| )
Evaluate 𝑉(𝜋' |ℋ| )𝑉(𝜋13MOVE ONLINE EVALUATION TO OFFLINE➤ Problems with online A/B Testing:➤ Long turnaround time.
➤ High engineering cost.
➤ Limited number of policies being evaluated.
➤ High risk of deploying bad policy.

14

MOVE ONLINE EVALUATION TO OFFLINE➤ Problems with online A/B Testing:➤ Long turnaround time.
➤ High engineering cost.
➤ Limited number of policies being evaluated.
➤ High risk of deploying bad policy.

➤ Idea: Move online to offline:
logged data

' ")
𝑉(𝜋

' &)
𝑉(𝜋

' ()
𝑉(𝜋

' ℋ *! )
𝑉(𝜋

' #)
𝑉(𝜋

' ')
𝑉(𝜋

' ))
𝑉(𝜋

' ℋ)
𝑉(𝜋
15

GOALS
Provide statistically and computationally efficient way toevaluate and optimize interactive systems by exploiting
logs of past user interactions.

16

GOALS
Provide statistically and computationally efficient way toevaluate and optimize interactive systems by exploiting
logs of past user interactions. Specifically:
1. Off-policy Evaluation

17

GOALS
Provide statistically and computationally efficient way toevaluate and optimize interactive systems by exploiting
logs of past user interactions. Specifically:
1. Off-policy Evaluation
2. Off-policy Model Selection

18

GOALS
Provide statistically and computationally efficient way toevaluate and optimize interactive systems by exploiting
logs of past user interactions. Specifically:
1. Off-policy Evaluation
2. Off-policy Model Selection
3. Off-policy Learning
19

TALK OUTLINE
Off-policy Evaluation
Introduction and Background.

Off-policy Model Selection
SLOPE: A model selection
procedure in OPE.
[ICML, 2020]

Counterfactual family of estimators.
[ICML, 2019]

Optimization-based framework for
estimator design.
[ICML, 2020]

Off-policy Learning
Multiple logging policies.
[CausalML, 2018]

Deficient support data.
[KDD, 2020]
20

TALK OUTLINE
Off-policy Evaluation
Introduction and Background.

Off-policy Model Selection
SLOPE: A model selection
procedure in OPE.
[ICML, 2020]

Counterfactual family of estimators.
[ICML, 2019]

Optimization-based framework for
estimator design.
[ICML, 2020]

Off-policy Learning
Multiple logging policies[CausalML, 2018]

Deficient support data
[KDD, 2020]21

OFF-POLICY EVALUATION➤ Goal:7 𝝅 to measure the expected reward of a new policy 𝜋
Find an estimate 𝑽

𝑉 𝜋 = 𝔼!∼#(!) 𝔼&∼'(&|!) 𝔼)∼#()|!,&) [𝑟]Using the logged data from a different known logging policy 𝜇

𝒟 = 𝑥+ , 𝑎+ , 𝜇 𝑎+ 𝑥+ , 𝑟+ .+,3➤ Quality of the estimate 𝑉(𝜋):𝑀𝑆𝐸 𝑉5 𝜋= 𝔼 𝑉5 𝜋 − 𝑉 𝜋,= 𝐵𝑖𝑎𝑠 𝑉5 𝜋,

+ 𝑉𝑎𝑟 𝑉5 𝜋
22Challenges
Bias data: selection-bias due to the logging policy.
Partial information data: only observe the reward for recommended action.

23

OFF-POLICY EVALUATION: EXISTING APPROACHES➤ Model the bias: Inverse propensity scores (IPS).
➤ A weighted average of the data according to importancesampling weights.

.

1
𝑉3/#0 𝜋 = 6 𝑤 𝑥+ , 𝑎+ 𝑟+𝑛+,-[Horitz & Thompson, 1952; Strehl et al., 2011]24

OFF-POLICY EVALUATION: EXISTING APPROACHES➤ Model the bias: Inverse propensity scores (IPS).
➤ A weighted average of the data according to importancesampling weights.

.

1
𝑉3/#0 𝜋 = 6 𝑤 𝑥+ , 𝑎+ 𝑟+𝑛+,-[Horitz & Thompson, 1952; Strehl et al., 2011]

𝜋(𝑎|𝑥)
𝑤 𝑥, 𝑎 =𝜇(𝑎|𝑥)

25

OFF-POLICY EVALUATION: EXISTING APPROACHES➤ Model the bias: Inverse propensity scores (IPS).
➤ A weighted average of the data according to importancesampling weights.

.

1
𝑉3/#0 𝜋 = 6 𝑤 𝑥+ , 𝑎+ 𝑟+𝑛+,-𝜋(𝑎|𝑥)
𝑤 𝑥, 𝑎 =𝜇(𝑎|𝑥)

Unbiased estimator under full support.
High variance when logging policy and target policy differ a lot.
[Horitz & Thompson, 1952; Strehl et al., 2011]26

OFF-POLICY EVALUATION: EXISTING APPROACHES➤ Model the world: Direct Model (DM).

➤ Use logged data 𝒟 = 𝑥+ , 𝑎+ , 𝑟+ .
+,- to estimate reward predictor

𝛿8 𝑥, 𝑎 , then using this estimate to do the imputation.
.

1
8 + , 𝑎)𝑉312 𝜋 = 6 6 𝜋 𝑎 𝑥+ 𝛿(𝑥𝑛+,- &[Dudik et al., 2011]27

OFF-POLICY EVALUATION: EXISTING APPROACHES➤ Model the world: Direct Model (DM).

➤ Use logged data 𝒟 = 𝑥+ , 𝑎+ , 𝑟+ .
+,- to estimate reward predictor

𝛿8 𝑥, 𝑎 , then using this estimate to do the imputation.
.

1
8 + , 𝑎)𝑉312 𝜋 = 6 6 𝜋 𝑎 𝑥+ 𝛿(𝑥𝑛+,- &Low variance.
Typically has high bias due to model misspecification.
[Dudik et al., 2011]28

OFF-POLICY EVALUATION: EXISTING APPROACHES➤ Doubly Robust Estimator➤ Use Direct Model as a baseline, also leverages IPS weighting tomeasure the departure from the baseline.
.

1
8 + , 𝑎+ ))𝑉313 𝜋 = 𝑉312 𝜋 + 6 𝑤 𝑥+ , 𝑎+ (𝑟+ −𝛿(𝑥𝑛+,-[Robins & Rotnitzky, 1995; Dudik et al., 2011]29

OFF-POLICY EVALUATION: EXISTING APPROACHES➤ Doubly Robust Estimator➤ Use Direct Model as a baseline, also leverages IPS weighting tomeasure the departure from the baseline.
.

1
8 + , 𝑎+ ))𝑉313 𝜋 = 𝑉312 𝜋 + 6 𝑤 𝑥+ , 𝑎+ (𝑟+ −𝛿(𝑥𝑛+,-[Robins & Rotnitzky, 1995; Dudik et al., 2011]30

OFF-POLICY EVALUATION: EXISTING APPROACHES➤ Doubly Robust Estimator➤ Use Direct Model as a baseline, also leverages IPS weighting tomeasure the departure from the baseline.
.

1
8 + , 𝑎+ ))𝑉313 𝜋 = 𝑉312 𝜋 + 6 𝑤 𝑥+ , 𝑎+ (𝑟+ −𝛿(𝑥𝑛+,-Unbiased estimator, asymptotically optimal under mild conditions.
Variance improvement over IPS, but still suffer from high variance.
[Robins & Rotnitzky, 1995; Dudik et al., 2011]

31

DM

IPS

Measurement

DR

Variance
Bias

Estimator Space

32

DM

IPS

Measurement

DR

Variance
Bias

Estimator Space

1. How do we quantify estimators in between?
2. What is the estimator in the sweet spot?
33

TALK OUTLINE
Off-policy Evaluation
Introduction and Background.

Off-policy Model Selection
SLOPE: A model selection
procedure in OPE.
[ICML, 2020]

Counterfactual family of estimators.
[ICML, 2019]

Optimization-based framework for
estimator design.
[ICML, 2020]

Off-policy Learning
Multiple logging policies[CausalML, 2018]

Deficient support data
[KDD, 2020]
34

INTERPOLATED COUNTERFACTUAL ESTIMATOR FAMILY
Given a triplet 𝓦 = (𝒘𝜶, 𝒘𝜷, 𝒘𝜸 ) of weighting functions:
𝑉5 1 𝜋 =$$$!"# 2∈4

!"#

!"#

1
1
1
𝜷
𝜸
𝜶
I I 𝜋(𝑎|𝑥! ) 𝒘𝒊𝒂𝛼!2 + I 𝜋 𝑎! 𝑥! 𝒘𝒊 𝛽! + I 𝜋 𝑎! 𝑥! 𝒘𝒊 𝛾!
𝑛
𝑛
𝑛

35

Su,Y.*, Wang.L,*, Santacatterina, M., and Joachims,T. CAB: Continuous adaptive blending estimator for policy evaluation and learning. ICML 2019.

INTERPOLATED COUNTERFACTUAL ESTIMATOR FAMILY
Given a triplet 𝓦 = (𝒘𝜶, 𝒘𝜷, 𝒘𝜸 ) of weighting functions:
𝑉5 1 𝜋 =$$$!"# 2∈4

!"#

!"#

1
1
1
𝜷
𝜸
𝜶
I I 𝜋(𝑎|𝑥! ) 𝒘𝒊𝒂𝛼!2 + I 𝜋 𝑎! 𝑥! 𝒘𝒊 𝛽! + I 𝜋 𝑎! 𝑥! 𝒘𝒊 𝛾!
𝑛𝑛𝑛

7 𝒊 , 𝒂).
➤ First Component (Model part): 𝜶𝒊𝒂 = 𝜹(𝒙➤ “Model the world” by having a reward estimator for all (𝑥, 𝑎) pairs.
➤ The estimator that purely relies on this is DM, which has weights 𝑤 = (1,0,0).
➤ Induce high bias, but typically low variance.
36

INTERPOLATED COUNTERFACTUAL ESTIMATOR FAMILY
Given a triplet 𝓦 = (𝒘𝜶, 𝒘𝜷, 𝒘𝜸 ) of weighting functions:
𝑉5 1 𝜋 =$$$!"# 2∈4

!"#

!"#

1
1
1
𝜷
8
7
I I 𝜋(𝑎|𝑥! ) 𝑤!2 𝛼!2 + I 𝜋 𝑎! 𝑥! 𝒘𝒊 𝛽! + I 𝜋 𝑎! 𝑥! 𝑤! 𝛾!
𝑛𝑛𝑛𝒓(𝒙𝒊 ,𝒂𝒊 )➤ Second Component (Weighting part): 𝜷𝒊 : = 𝜷 𝒙𝒊 , 𝒂𝒊 =𝝁(𝒂𝒊 |𝒙𝒊 )➤ “Model the bias” by correcting the probability mismatch.
➤ The estimator that purely relies on this is IPS, which put weights 𝑤 = (0,1,0)➤ Induce high variance, but unbiased under mild conditions.
37

INTERPOLATED COUNTERFACTUAL ESTIMATOR FAMILY
Given a triplet 𝓦 = (𝒘𝜶, 𝒘𝜷, 𝒘𝜸 ) of weighting functions:
𝑉5 1 𝜋 =$$$!"# 2∈4

!"#

!"#

1
1
1
=
𝜸
7
I I 𝜋(𝑎|𝑥! ) 𝑤!2 𝛼!2 + I 𝜋 𝑎! 𝑥! 𝑤! 𝛽! + I 𝜋 𝑎! 𝑥! 𝒘𝒊 𝛾!
𝑛𝑛𝑛> (𝒙𝒊 ,𝒂𝒊 )𝜹➤ Third Component (Control Variate): 𝜸𝒊 ≔ 𝜸 𝒙𝒊 , 𝒂𝒊 = 𝝁(𝒂 |𝒙 )𝒊 𝒊

➤ Used as control variate for variance reduction, example: DR.
➤ This part could not be used in some partial information setting, such as
Learning to Rank.
38

INTERPOLATED COUNTERFACTUAL ESTIMATOR FAMILY
Given a triplet 𝓦 = (𝒘𝜶, 𝒘𝜷, 𝒘𝜸 ) of weighting functions:
𝑉5 1 𝜋 =$$$!"# 2∈4

!"#

!"#

1
1
1
𝜷
𝜸
𝜶
I I 𝜋(𝑎|𝑥! ) 𝒘𝒊𝒂𝛼!2 + I 𝜋 𝑎! 𝑥! 𝒘𝒊 𝛽! + I 𝜋 𝑎! 𝑥! 𝒘𝒊 𝛾!
𝑛
𝑛
𝑛

𝜷
𝜸
𝑉3 4 𝜋 = 𝒘𝜶𝒊𝒂 Model Part + 𝒘𝒊 Weighting Part + 𝒘𝒊 Control Variate

39

INTERPOLATED COUNTERFACTUAL ESTIMATOR FAMILY
Estimator

𝒘𝜶𝒊𝒂 (Model)

𝒘𝒊 (Weighting)𝒘𝒊 (Control
Variate)

DM

1

0

0

IPS

0

1

0

DR

1

1

-1

cIPS

0

0

MAGIC/SB1−𝜏

𝑀𝜇 𝑎0 𝑥0min{
, 1}
𝜋 𝑎0 𝑥0
𝜏SWITCH𝜋 𝑎 𝑥0𝕝{> 𝑀}
𝜇 𝑎 𝑥0 )𝜋 𝑎0 𝑥0𝕝{≤ 𝑀}
𝜇 𝑎0 𝑥0 )

0

𝜷

𝜸

0

40

INTERPOLATED COUNTERFACTUAL ESTIMATOR FAMILY
Estimator

𝒘𝜶𝒊𝒂 (Model)𝜷𝒘𝒊 (Weighting)𝜸

𝒘𝒊 (Control
Variate)

DM

1

0

0

IPS

0

1

0

DR

1

1

-1

cIPS

0

MAGIC/SB
SWITCH0

1−𝜏

𝑀𝜇 𝑎0 𝑥0min{
, 1}
𝜋 𝑎0 𝑥0
𝜏

𝜋 𝑎 𝑥0𝕝{> 𝑀}
𝜇 𝑎 𝑥0 )𝜋 𝑎0 𝑥0𝕝{≤ 𝑀}
𝜇 𝑎0 𝑥0 )00

SB(Static Blending)[Thomas & Brunskill, 2016]

Static weighting and does notdepend on importance weights.

SWITCH[Wang, et.al., 2017]

Hard switching makes it notdifferentiable w.r.t. parameter ofpolicy and could not be used in
gradient-based learning algorithms.
41

DESIRABLE PROPERTIES➤ Applicable for a wide range of settings, like LTR, need to makecontrol variate term to be 0.

42

DESIRABLE PROPERTIES➤ Applicable for a wide range of settings, like LTR, need to makecontrol variate term to be 0.
➤ Low MSE: data dependent weights that allow an instancedependent trade-off between bias and variance.

43

DESIRABLE PROPERTIES➤ Applicable for a wide range of settings, like LTR, need to makecontrol variate term to be 0.
➤ Low MSE: data dependent weights that allow an instancedependent trade-off between bias and variance.

➤ Sub-differentiable for gradient based learning.

44

CONTINUOUS ADAPTIVE BLENDING (CAB)
CAB is a specific estimator in the interpolated counterfactual estimator family with:
𝜇 𝑎 𝑥!
7
𝑤!2 = 1 − min{𝑀𝜋 𝑎 𝑥!

𝑉5P4Q 𝜋 = 𝑉5 1 𝜋

𝑤𝑖𝑡ℎ

R 𝑎 𝑥!
5
𝑉P4Q 𝜋 = 1 − min 𝑀 S 𝑎 𝑥 , 1!

𝜇 𝑎! 𝑥!
𝜷
𝒘𝒊 = min{𝑀
𝜋 𝑎! 𝑥!
𝜸
𝒘𝒊 = 0×Model Part + min

, 1}

, 1}

R 𝑎! 𝑥!
𝑀S 𝑎 𝑥! !

, 1 × Weighting Part

45

PROPERTIES OF CAB➤➤

Can be substantially less biased than clipped
IPS and DM.

Estim
ator

𝒘𝜶𝒊𝒂 (Model)

DM

1

While having low variance compared to IPS
and DR.

cIPS

0

CAB
➤

➤

Subdifferentiable and capable of gradient
based learning: POEM (Swaminathan &Joachims, 2015a), BanditNet (Joachims et.al.,2018)
Unlike DR, can be used in off-policy Learningto Rank (LTR) algorithms. (Joachims et.al.,2017)

1 − min 𝑀

𝜇 𝑎 𝑥!
,1
𝜋 𝑎 𝑥!

𝜸𝜷𝒘𝒊 (Weighting) 𝒘𝒊

0

0
min{

𝑀𝜇 𝑎! 𝑥!
, 1}
𝜋 𝑎! 𝑥!

0

𝜇 𝑎! 𝑥!
,1
𝜋 𝑎! 𝑥!

0

min 𝑀

46

PROPERTIES OF CAB
➤

➤

➤

➤

Can be substantially less biased than clipped
IPS and DM.
While having low variance compared to IPS
and DR.
Subdifferentiable and capable of gradient
based learning: POEM (Swaminathan &Joachims, 2015a), BanditNet (Joachims et.al.,2018)
Unlike DR, can be used in off-policy Learningto Rank (LTR) algorithms. (Joachims et.al.,
2017)

Estim
ator

𝒘𝜶𝒊𝒂 (Model)

IPS

0

1

0

DR

1

1

-1

CAB

1 − min 𝑀

𝜇 𝑎 𝑥!
,1
𝜋 𝑎 𝑥!

𝜸𝜷𝒘𝒊 (Weighting) 𝒘𝒊

min 𝑀

𝜇 𝑎! 𝑥!
,1
𝜋 𝑎! 𝑥!

47

0PROPERTIES OF CAB
➤

➤

➤

➤

Can be substantially less biased than clipped
IPS and DM.
While having low variance compared to IPS
and DR.
Estim
ator

Subdifferentiable and capable of gradient
SWIT
based learning: POEM (Swaminathan &CH
Joachims, 2015a), BanditNet (Joachims et.al.,
2018)
CAB
Unlike DR, can be used in off-policy Learningto Rank (LTR) algorithms. (Joachims et.al.,2017)

𝒘𝜶𝒊𝒂 (Model)𝜷𝒘𝒊 (Weighting) 𝒘𝒊

𝜋 𝑎 𝑥!
> 𝑀}
𝜇 𝑎 𝑥! )𝕝{𝕝{

1 − min 𝑀

𝜇 𝑎 𝑥!
,1
𝜋 𝑎 𝑥!

𝜸

𝜋 𝑎! 𝑥!
≤ 𝑀}
𝜇 𝑎! 𝑥! )0

𝜇 𝑎! 𝑥!
,1
𝜋 𝑎! 𝑥!

0

min 𝑀

48

PROPERTIES OF CAB
➤

➤

➤

➤

Can be substantially less biased than clipped
IPS and DM.
While having low variance compared to IPS
and DR.
Subdifferentiable and capable of gradient
Estim
based learning: POEM (Swaminathan &Joachims, 2015a), BanditNet (Joachims et.al., ator
DR
2018)
Unlike DR, can be used in off-policy Learningto Rank (LTR) algorithms. (Joachims et.al.,
2017)

CAB

𝒘𝜶𝒊𝒂 (Model)𝜸𝜷𝒘𝒊 (Weighting) 𝒘𝒊

1
1 − min 𝑀

𝜇 𝑎 𝑥!
,1
𝜋 𝑎 𝑥!

-1

1
min 𝑀

𝜇 𝑎! 𝑥!
,1
𝜋 𝑎! 𝑥!

49

0EXPERIMENTS: SETTINGS➤ Batch Learning from Bandit Feedback.
➤ Datasets: UCI multi-class classification, bandit conversion.
➤ Model: Logistic Regression➤ Policy: Softmax Policy➤ Learning to Rank.
➤ Datasets: Yahoo LTR!
➤ Model: Gradient Boosted Decision Tree
➤ Policy: SVM-Rank
50

EXPERIMENTS: UCI DATASET➤ Question 1: Can CAB achieve improved estimation by trading biasvariance through M?
% 𝑎𝑥
𝑉6"#$ 𝜋 = 1 − min 𝑴 & 𝑎 𝑥! , 1!

% 𝑎 𝑥
×Model Part + min 𝑴 & 𝑎! 𝑥! , 1 × Weighting Part!

!

Performance of CAB: satImage

51

EXPERIMENTS: UCI DATASET➤ Question 1: Can CAB achieve improved estimation by trading biasvariance through M?
% 𝑎𝑥
𝑉6"#$ 𝜋 = 1 − min 𝑴 & 𝑎 𝑥! , 1!

% 𝑎 𝑥
×Model Part + min 𝑴 & 𝑎! 𝑥! , 1 × Weighting Part!

!

Performance of CAB: satImage

52

EXPERIMENTS: YAHOO LTR!
➤ Question 1: Can CAB achieve improved estimation by trading biasvariance through M?
% 𝑎𝑥
𝑉6"#$ 𝜋 = 1 − min 𝑴 & 𝑎 𝑥! , 1!

% 𝑎 𝑥
×Model Part + min 𝑴 & 𝑎! 𝑥! , 1 × Weighting Part!

!

Performance of CAB: Yahoo LTR!

53

EXPERIMENTS➤ Question 2: How does CAB compared with other estimators?

54

LESSONS LEARNT

A family of estimators

CAB (smooth weight clipping)

Flexible bias variance tradeoff

slightly higher bias+
substantially lower variance55

A specific weight design → CAB
Is there any systematic way to design theweights for better bias-variance tradeoff?

56

TALK OUTLINE
Off-policy Evaluation
Introduction and Background.

Off-policy Model Selection
SLOPE: A model selection
procedure in OPE.
[ICML, 2020]

Counterfactual family of estimators.
[ICML, 2019]

Optimization-based framework for
estimator design.
[ICML, 2020]

Off-policy Learning
Multiple logging policies[CausalML, 2018]

Deficient support data
[KDD, 2020]
57

DOUBLY ROBUST ESTIMATOR WITH SHRINKAGE (DRS).

1
8 + , 𝑎+ ))𝑉313 𝜋 = 𝑉312 𝜋 + 6 𝑤 𝑥+ , 𝑎+ (𝑟+ −𝛿(𝑥𝑛+,-DR is asymptotically optimal.
However, it still suffers from the large variance due toutilizing the importance sampling weight.

Su.Y, Dimakopoulou.M, Krishnamurthy.A, and Dudík.M. Doubly robust off-policy evaluation with shrinkage. ICML, 2020.

58

DOUBLY ROBUST ESTIMATOR WITH SHRINKAGE (DRS)
Replace the original weight 𝒘 𝒙, 𝒂 by a shrinkage version 𝒘= 𝒙, 𝒂 .

- .
8
8 + , 𝑎+ )) + 𝑉312 𝜋
3𝑉13 𝜋, 𝑤,= 𝛿 = ∑+,- 𝑤 𝑥+ , 𝑎+ (𝑟+ −𝛿(𝑥.

- .
88 + , 𝑎+ )) + 𝑉312 𝜋
3
𝑉130 𝜋, 𝑤,= 𝛿 = ∑+,- 𝑤= 𝑥+ , 𝑎+ (𝑟+ −𝛿(𝑥.

0≤𝑤
= 𝑥+ , 𝑎+ ≤ 𝑤(𝑥+ , 𝑎+ )59

DOUBLY ROBUST ESTIMATOR WITH SHRINKAGE
Replace the original weight 𝒘 𝒙, 𝒂 by a shrinkage version 𝒘= 𝒙, 𝒂 .

- .
8
8 + , 𝑎+ )) + 𝑉312 𝜋
3
𝑉130 𝜋, 𝑤,= 𝛿 = ∑+,- 𝑤= 𝑥+ , 𝑎+ (𝑟+ −𝛿(𝑥.

Which form of shrinkage should we use?
Which one should we use for our specific reward predictor?
60

DOUBLY ROBUST ESTIMATOR WITH SHRINKAGE

Our approach:Directly finding the optimal weights byminimizing an upper bound of the MSE

61

APPROACH I: BEING PESSIMISTIC
Assume sup 𝑟 − 𝛿8 𝑥, 𝑎!,&≤1

➤ Bias: 𝐵𝑖𝑎𝑠 𝑤= ≤ 𝑈𝐵 𝐵𝑖𝑎𝑠 = 𝔼: [|𝑤= 𝑥, 𝑎 − 𝑤(𝑥, 𝑎)|]➤ Variance: 𝑉𝑎𝑟 𝑤= ≲ 𝑈𝐵 𝑉𝑎𝑟 =

.

𝔼: [𝑤
= 𝑥, 𝑎 ; ]62

APPROACH I: BEING PESSIMISTIC
Assume sup 𝑟 − 𝛿8 𝑥, 𝑎!,&≤1

➤ Bias: 𝐵𝑖𝑎𝑠 𝑤= ≤ 𝑈𝐵 𝐵𝑖𝑎𝑠 = 𝔼: [|𝑤= 𝑥, 𝑎 − 𝑤(𝑥, 𝑎)|]➤ Variance: 𝑉𝑎𝑟 𝑤= ≲ 𝑈𝐵 𝑉𝑎𝑟 =

.

𝔼: [𝑤
= 𝑥, 𝑎 ; ]➤ The optimal weights can be obtained by minimizing:
𝑈𝐵(𝐵𝑖𝑎𝑠) + 𝜆 ⋅ 𝑈𝐵(𝑉𝑎𝑟)63

APPROACH I: BEING PESSIMISTIC
Assume sup 𝑟 − 𝛿8 𝑥, 𝑎!,&≤1

➤ Bias: 𝐵𝑖𝑎𝑠 𝑤= ≤ 𝑈𝐵 𝐵𝑖𝑎𝑠 = 𝔼: [|𝑤= 𝑥, 𝑎 − 𝑤(𝑥, 𝑎)|]➤ Variance: 𝑉𝑎𝑟 𝑤= ≲ 𝑈𝐵 𝑉𝑎𝑟 =

.

𝔼: [𝑤
= 𝑥, 𝑎 ; ]➤ The optimal weights can be obtained by minimizing:
𝑈𝐵(𝐵𝑖𝑎𝑠) + 𝜆 ⋅ 𝑈𝐵(𝑉𝑎𝑟)➤ Solution: 𝑤= 𝑥, 𝑎 = min{𝜆, 𝑤(𝑥, 𝑎)}Clipping Estimator
64

APPROACH II: BEING OPTIMISTIC
Typically, the reward estimator 𝛿8 𝑥, 𝑎 is trained to minimize theweighted square loss based on some weighting function 𝑧 𝑥, 𝑎 :.

1
8𝐿(𝛿) = 6 𝑧 𝑥+ , 𝑎+𝑛𝑟+ − 𝛿8 𝑥+ , 𝑎+;+,-Popular choices include 𝑧 = 1, 𝑧 = 𝑤 𝑥, 𝑎 , 𝑧 = 𝑤 𝑥, 𝑎 ;65

APPROACH II: BEING OPTIMISTIC-

8➤ Bias: 𝐵𝑖𝑎𝑠 𝑤= ≤ 𝔼: [ < !,& 𝑤= 𝑥, 𝑎 − 𝑤(𝑥, 𝑎) ; ]𝐿(𝛿);➤ Variance: 𝑉𝑎𝑟 𝑤= ≲4 !,& !

𝔼: [

< !,&

8
𝑤
= 𝑥, 𝑎 ; ] 𝐿(𝛿)➤ Using similar trick to minimize an upper bound of MSE.

➤ Solution: S𝒘 𝒙, 𝒂 =𝝀𝝀>𝒘 𝒙,𝒂 𝟐𝒘(𝒙, 𝒂)Shrinkage Estimator
66

DOUBLY ROBUST ESTIMATOR WITH SHRINKAGE- .
8
8 + , 𝑎+ )) + 𝑉312 𝜋
3
𝑉130AB 𝜋, 𝑤,= 𝛿 = ∑+,- min{𝜆, 𝑤(𝑥, 𝑎)}(𝑟+ −𝛿(𝑥
.

- .
8
3
𝑉130AC 𝜋, 𝑤,= 𝛿 = ∑+,.

𝝀𝝀>𝒘 𝒙,𝒂8 + , 𝑎+ )) + 𝑉312 𝜋
𝒘(𝒙,
𝒂)
(𝑟
−
𝛿(𝑥
+
𝟐

➤ Interpolating between DM and DR:- 𝜆 = 0 → 𝑉&!" 𝜋 , small variance, large bias
- 𝜆 = ∞ → 𝑉&!# 𝜋 , large variance, small bias
67

EMPIRICAL EVALUATION
For non-combinatorial bandit, we perform 108 settings:- 9 UCI multi-class classification datasets- 6 different logging policies- 2 reward conditions: deterministic reward and stochastic reward

68

EMPIRICAL EVALUATION➤ Ablation Studies for DR with shrinkage.
- .
8
8 + , 𝑎+ )) + 𝑉312 𝜋
3
𝑉130 𝜋, 𝑤,= 𝛿 = . ∑+,- 𝑤= 𝑥+ , 𝑎+ (𝑟+ −𝛿(𝑥- evaluating different reward predictors: 𝑧 = 1, 𝑤 𝑥, 𝑎 , 𝑤 𝑥, 𝑎 ; .
$1Z
𝐿(𝛿) = I 𝑧 𝑥! , 𝑎!
𝑛𝑟! − 𝛿Z 𝑥! , 𝑎!

,!"#- evaluating the optimistic and pessimistic shrinkage types.
69

EMPIRICAL EVALUATION
Do we need all different reward predictors?

𝒛=𝟏

How often across 108
conditions is each of
the reward predictor
the best?

DM
DR
DRshrinkage

𝒛=𝒘

27

11

8

24

15

4

10

6

22

2

6

4 2

𝒛 = 𝒘𝟐

tie

34

8

69

43

29

70

EMPIRICAL EVALUATION
Do we need both pessimistic shrinkage and optimistic shrinkage?
Pessimistic wins

How often across 108
conditions is each ofthem better in DRwith shrinkage?

𝒛=𝟏

Tie

58

22

Optimistic wins
28

𝒛=𝒘

55

24

29

𝒛 = 𝒘𝟐

55

23

30

71

EMPIRICAL EVALUATION

Evaluation Performance

Learning Performance72

LESSONS LEARNT

Instead of manually constructing
estimators, there is an optimizationbased framework to design
estimators.

Different reward predictors andweight shrinkage types perform
well in different settings.

73

R 𝑎 𝑥!
𝑉5P4Q 𝜋 = 1 − min 𝑀,1
S 𝑎 𝑥!

×Model Part + min 𝑀

R 𝑎! 𝑥!
S 𝑎! 𝑥!

, 1 × Weighting Part- .
8
8 + , 𝑎+ )) + 𝑉312 𝜋
3
𝑉130AB 𝜋, 𝑤,= 𝛿 = ∑+,- min{𝜆, 𝑤(𝑥, 𝑎)}(𝑟+ −𝛿(𝑥
.

- .
8
3
𝑉130AC 𝜋, 𝑤,= 𝛿 = ∑+,.

𝝀𝝀>𝒘 𝒙,𝒂8 + , 𝑎+ )) + 𝑉312 𝜋
𝒘(𝒙,
𝒂)
(𝑟
−
𝛿(𝑥
+
𝟐

How do we select the hyper-parameters in OPE?

74

TALK OUTLINE
Off-policy Evaluation
Introduction and Background.

Off-policy Model Selection
SLOPE: A model selection
procedure in OPE.
[ICML, 2020]

Counterfactual family of estimators.
[ICML, 2019]

Optimization-based framework for
estimator design.
[ICML, 2020]

Off-policy Learning
Multiple logging policies[CausalML, 2018]

Deficient support data
[KDD, 2020]75

OFF POLICY MODEL SELECTION
Off-policy Model Selection:! (𝜋),
Among a family of off-policy estimates 𝑽
selects the one with highest evaluation accuracy.

76

OFF POLICY MODEL SELECTION: SLOPE
Ordering

Variance
Bias

Building CIs

𝐼G = [𝜃8+ − 2𝐶𝑁𝐹 𝑖 , 𝜃8+ + 2𝐶𝑁𝐹 𝑖 ]Su.Y, Srinath.P, Krishnamurthy.A, Adaptive Estimator Selection for Off-Policy Evaluation, ICML 202077

OFF POLICY MODEL SELECTION: SLOPE
Index Selection

Performance2𝚤̂ ≔ max{𝑖 ∈ 𝑀 : ∩G,𝐼G ≠ ∅}Su.Y, Srinath.P, Krishnamurthy.A, Adaptive Estimator Selection for Off-Policy Evaluation, ICML 202078

OFF POLICY LEARNING
Off-policy Learning:
Learn an optimal policy 𝝅∗ in some hypothesis space Π𝜋 ∗ = 𝑎𝑟𝑔𝑚𝑎𝑥 S∈V 𝑉(𝜋)Tool: ERM based on an OPE estimate
7 (𝝅)𝜋b ∗ = 𝑎𝑟𝑔𝑚𝑎𝑥 S∈V 𝑽

79

TALK OUTLINE
Off-policy Evaluation
Introduction and Background.

Off-policy Model Selection
SLOPE: A model selection
procedure in OPE.
[ICML, 2020]

Counterfactual family of estimators.
[ICML, 2019]

Optimization-based framework for
estimator design.
[ICML, 2020]

Off-policy Learning
Multiple logging policies[CausalML, 2018]

Deficient support data
[KDD, 2020]80

OFF POLICY LEARNING: MULTIPLE POLICIES
logged data
𝓓𝟏 from 𝛑𝟏logged data
𝓓𝟐 from 𝛑𝟐logged data
𝓓𝐤 from 𝛑𝐤Training logs are collected undermultiple policies.

Naively using IPS in learning will give
sub-optimal results.
Utilize a weighted estimator, to trackthe divergence between the learned
policy and various logging policies.
81

Su.Y, Agarwal.A, Joachims.T, Learning from Logged Bandit Feedback of Multiple Loggers, CausalML 2018TALK OUTLINE
Off-policy Evaluation
Introduction and Background.

Off-policy Model Selection
SLOPE: A model selection
procedure in OPE.
[ICML, 2020]

Counterfactual family of estimators.
[ICML, 2019]

Optimization-based framework for
estimator design.
[ICML, 2020]

Off-policy Learning
Multiple logging policies[CausalML, 2018]

Deficient support data
[KDD, 2020]82

OFF POLICY LEARNING: DEFICIENT SUPPORT DATA𝜋𝜇Effectiveness of IPS relies on the crucial
full support assumption

The logging policy 𝜇 is said to havefull support for 𝜋:
𝜇 𝑎 𝑥 > 0 whenever 𝜋 𝑎 𝑥 > 0

Sachdeva.N*, Su.Y*, Joachims.T, Off-policy Bandits with Deficient Support. KDD, 202083OFF POLICY LEARNING: DEFICIENT SUPPORT DATA𝜋
The logging policy needs to assign
non-zero probability to every action 𝒂for every context 𝑥 !

𝜇We propose three efficient approaches
to overcome the support deficient issue
by restricting action space,policy spaceand reward extrapolation.

Sachdeva.N*, Su.Y*, Joachims.T, Off-policy Bandits with Deficient Support. KDD, 202084

Beyond off-policy evaluation and learning …
Fairness...

Diversity

Societal
Roles

Robustness
Privacy85

MULTI-SIDED MARKET PLATFORM
Traditional Recommender Systems

Only users have preference.

Multi-sided Market Platforms

Preference from both sides.
Scarcity in the supply side.
86

MULTI-SIDED MARKET PLATFORM
Overwhelmedby interviews

No interview

Employers

Personalized rankings

Candidates Interviews they get

87

MULTI-SIDED MARKET PLATFORM
Overwhelmedby interviews

No interview

Societal Roles of Recommender Systems

88Thorsten Joachims (Cornell)
Miro Dudik (Microsoft Research, NYC)
Akshay Krishnamurthy (Microsoft Research, NYC)
Pavithra Srinath (Microsoft Research, NYC)
Maria Dimakopoulou (Netflix)
Michele Santacatterina (Cornell)
Luke Wang (Cornell)
Noveen Sachdeva (UCSB)

Thank you!
89

REFERENCES
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In International Conference on
Machine Learning, 2011.
Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In
International Conference on Machine Learning, 2015.
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evaluation in contextual bandits. In
International Conference on Machine Learning, 2017.
Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In International
Conference on Machine Learning, 2016.
Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims. Cab: Continuous adaptive blending for policy evaluationand learning. In International Conference on Machine Learning, 2019.
Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík. Doubly robust off-policy evaluation with shrinkage. In
International Conference on Machine Learning, 2020.
Yi Su, Pavithra Srinath, and Akshay Krishnamurthy, Adaptive Estimator Selection for Off-Policy Evaluation. In International
Conference on Machine Learning, 2020.
90

REFERENCES
Noveen Sachdeva, Yi Su, Thorsten Joachims, Off-policy bandits with deficient support. International Conference on
Knowledge Discovery & Data Mining, 2020.
Yi Su, Aman Agarwal, Thorsten Joachims, Learning from logged bandit feedback of multiple loggers. In CausalML, 2018.
Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray,
Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising.
The Journal of Machine Learning Research, 2013.
Robins, J. M. and Rotnitzky, A. Semiparametric efficiency in multivariate regression models with missing data. Journal of theAmerican Statistical Association, 90(429):122– 129, 1995.
Heejung Bang and James M Robins. Doubly robust estimation in missing data and causal inference models. Biometrics, 2005.
Swaminathan, Adith, Akshay Krishnamurthy, Alekh Agarwal, Miro Dudik, John Langford, Damien Jose, and Imed Zitouni.
"Off-policy evaluation for slate recommendation." In Advances in Neural Information Processing Systems, pp. 3632-3642.
2017.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In
International Conference on Machine Learning, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive.ics.uci.edu/ml.

91