Uncertainty-Aware Instance Reweighting for Off-Policy Learning
Authors: Xiaoying Zhang
Junpu Chen
Hongning Wang
Hong Xie
Yang Liu
John C.S. Lui
Hang Li
Venue: NeurIPS 2023 poster (2023)
Keywords: off-policy learning
uncertainty
TL;DR: This work explicitly models the uncertainty in the estimated logging policy, and proposes UIPS for improved off-policy learning, with a theoretical convergence guarantee.

Abstract: Off-policy learning, referring to the procedure of policy optimization with access only to logged feedback data, has shown importance in various important real-world applications, such as search engines and recommender systems. While the ground-truth logging policy is usually unknown, previous work simply takes its estimated value for the off-policy learning, ignoring the negative impact from both high bias and high variance resulted from such an estimator. And these impact is often magnified on samples with small and inaccurately estimated logging probabilities. The contribution of this work is to explicitly model the uncertainty in the estimated logging policy, and propose an Uncertainty-aware Inverse Propensity Score estimator (UIPS) for improved off-policy learning, with a theoretical convergence guarantee. Experiment results on the synthetic and real-world recommendation datasets demonstrate that UIPS significantly improves the quality of the discovered policy, when compared against an extensive list of state-of-the-art baselines.

Uncertainty-Aware Instance Reweighting for Off-Policy Learning
Xiaoying Zhang
Junpu Chen Hongning Wang" John C.S. Lui Hang Li'
Hong Xie
Yang Liu'
ByteDance Research *ChongQing University
TTinghua University
Chongqing Institute of Green and Intelligent Technology. Chinese Academy of Science
5 "The Chinese University of Hong Kong
(zhangxiaoying xy yang 1iu01,lihang, 1llaaagg..... waeeaang..../yyeee Abyteanneencce.........oo com {jumpchan98, hongx87 wang hongnj bhonnn)@gmmill @gmail com
csluiêcse. cuhk. edu.
Abstract
Off-policy learning, referring to the procedure of policy optimization with access only to logged feedback data, has shown importance in various real-world applica- tions, such search engines and recommender systems. While the ground-truth logging policy is usually unknown, previous work simply employs its estimated value for the off-pooiicy Icarning, ignoring the negative impact from both high bias and high variance resulted from such an estimator. And such impact is often magnified on samples with small and inaccurately estimated logging probabilities. The contribution of this work is to explicitly model the uncertainty in the estimated logging policy, and propose an Uncertainty-awan timator (UIPS) for improved off-policy learning, with a theoretical convergence guarantee. Experiment results on the synthetic and real-world recommendation datasets demonstrate that UIPS significantly improves the quality of the discovered policy, when compared against an extensive list of state-of-the-arr baselines.
Inverse Propensity Score es-
1 Introduction
In many real-world applications, including search engines (2) online advertisements [5 recom- mender systems [8] (22,, only logged data available for subsequent policy learning. For example, in recommender systems, various complex recommendation policies are optimized over logged user interactions (e.g., clicks or stay time) with items recommended by previous recommendation policies (referred to as the logging policy) [1 since the feedback on items where the logging policy did not take is unknown. This inevitably distorts the evaluation and optimization of a new policy when it differs from the logging policy.
However, such logged data often known be biased,
Off-policy learning 41 27 thus emerges as a preferred way to learn an improved policy only from the logged data, by addressing the mismatch between the learning and logging policies. One of the most commonly used off-policy learning methods is the Inverse Propensity Scoring (IPS) [8] 25), which assigns per-sample importance weight (i.e., propensity score) to the training objective on the logged data, so to get an unbiased optimization objective expectation. The importance weight in IPS is the probability ratio of taking an action between the learning and logging policies.
Unfortunately, the ground-truit logging policy is oftentimes unavailable to the learner in practice, due to reasons like legacy issues, i.e., it was not recorded the data. Additionally, in specific situations like the healthcare domain (28) two-stage recommender systems ( access to the ground-truth logging policy is not feasible. One common treatment by many previous studies 35 22 24
is to first estimate the logging policy using a supervised learning method (c.g., logistic regression,
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

-10-2
-10
Detimatod Legging, Probabilliy
6
Log(ttem free))
Leggi frewe)
(a) Estimated Logging Probability
(b) Uncertainty Estimation
Figure 1: Estimated logging policy and its uncertainty under different item frequency on KuaiRec.
neural networks, etc.), and then employ the estimated logging policy for off-policy learning. this work, we first show that such an approximation results in biased estimator which is sensitive to data with small estimated logging probabilities. Worse still, small estimated logging probabilities usually suggest there are limited related samples in the logged data, whose estimations can have high uncertainties, i.e., being wrong with high probability. Figure shows piece of empirical evidence from a large-scale recommendation benchmark KuaiRec dataset [12]. where items with lower frequencies in the logged dataset have lower estimated logging probabilities (via neural network estimator) and higher uncertainties at the same time. The high bias and variance caused by these samples can greatly hinder the performance of subsequent off- off-policy learning. We defer
detailed discussions of this result in Section 2
In this work, we explicitly take the uncertainty of the estimated logging policy into consideration and design an Uncertainty-awar Inverse Propensity Score estimator (UIPS) for off-policy learning. UIPS reweighs the propensity score of each logged sample to control its impact on policy optimization, and learns improved policy by alternating between: (1) Find the optimal weight that makes the estimator as accurate as possible, based on the uncertainty the estimated logging policy; (2) Improve the policy by optimizing the resulting objective function. The optimal weight for each sample is obtained by minimizing the upper bound the mean squared error (MSE) to the ground-truth policy evaluation, with a closed-fore form solution. Furthermore, UIPS ensures that off-policy learning converges stationary point where the true policy gradient is zero; while convergence may not be guaranteed when directly using the estimated logging policy. Extensive experiments on a synthetic and three real- world recommendation datasets against rich of State-of-thhe-ee baselines demonstrate the power of UIPS. All data and code can be found in httpt::/ thhptb// thub. com/ www.//oooo/iiiii Noom//aaoyingii/U119 gitt
2 Preliminary: off-policy learning
We focus on the standard contextual bandit setup to explain the key concepts in UIPS. Following the convention [6
29 36), let X C Rd be d-dimensional context vector drawn from an
unknown distribution p (z). Each context is associated with a finite set actions denoted by A. where
[A] < co. Let π A X' j0, 1] denote stochastic policy, such that x =aa (z) is the probability of selecting action a under context æ and EGEAT( Ta x)) 1. Under given context æ, the reward Ta.o only observed when action is chosen, i.e., bandit feedback. Without loss of generality, assume Tn.a E [0, 1]. Let (T)) denote the expected reward of the policy π:
V( = Bmsp()) [r..)]
We look for policy (aak)) to maximize (Tx). In the rest, denote (= 1:] as IE
In off-policy learning, one can only access a set of logged feedback data D = {L ans a E [N]]. Given æ,,, the action o, was generated by stochastic logging policy 3r i.e., On 3 )n) which is usually different from the learning policy т T(a xx) [24 40 g). The actions {a)..... ax and their corresponding rewards {ra,,a ..... Tæx ,ax are generated independently given 8* The main challenge is then to address the distributional discrepancy between 3 (x) and iT x), when
optimizing क T(a x)) to maximize V(T)) with access only to the logged datasct D.

---

One of the most widely used methods to address the distribution shift between TTa22) and (a(())))
the Inverse Propensity Scoring (IPS)
g 25 One can easily get that:
x
V n Ex-
(alar)
Tana
yielding the following empirical estimator of V (T²:
π Tann
VIrs(*)=
N n=1
Σ
3 (a (.n) Omn
(2)
where it (an 3/3) (un (zn) is referred to as the propensity score. Various algorithms can readily used for policy optimization under (Irs(T). including value- methods [33 and policy-based methods [9] 3 42 In this work, we adopt well-known policy gradient algorithm, REINFORCE
42]. Assume the policy [a]a)) is parameterized by 0, via the "log-trick", the gradient of ViP)(TT)
with respect to & can be readily derived as,
(o((an(n) 8 (an xnn) Ta Vo
V VoVIPS(TO) N
Σ
Approximation with an unknown logging policy. In many real-world applications, the ground toutt logging probabilities, i.e., 3 (a(zz) of each observation (æt, a) in D, are unknown. As a typical walk-around, previous work employs supervised learning methods such as logistic regression (30)
and nerural networks S to estimate the logging policy, and replaces 33 (ala)) with its estimated value
((alz) to get the following BIPS estimator for policy learning:
Σ (o((an(zn) ==
N
VBIPS(TO) = N ((an xxn)
Tan.on
However, shown in the following proposition, inaccurate ((a|z) leads to high bias and variance in BIPS. Worse still, smaller and inaccurate ((a)z) further enlarges this bias and variance. Proposition 2.1. The bias and variance of ViIrS(TT)) be derived follows:
(a
11
Bias (VEIPS(TO)) = -ED (VIIPSTTO= - ((TO)]
= Em
Faza
3(aaz)
N VarD (TBI))(TO)) = Var.o (a(azz)
TT(aaa) (a(x)) -1) -1)
8 (alax)) ,
3(a|z)
Tz.a
+ Eno
(a x))2 a,a
However, smaller (a(az) usually implies less number of related training samples in the logged data, and thus ((a(z) can be inaccurate with higher probability. To make it more explicit, let us revisit the We followed the method introduced in g to estimate the logging policy on KuaiRec dataset [12 and plotted the estimated (allz) and its corresponding uncertainties on items of different observation frequencies in the logged dataset. We adopted the method in 45 to
empirical results shown in Figure]] [
measure the confidence interval of 3(a|zz) ()) on each instance. A wider confidence interval, i.e., higher uncertainty in estimation, implies that with a high probability the true value may be further away from the empirical mean estimate. We can observe in Figure I that item frequency decreases, the estimated logging probability also decreases, but the estimation uncertainty increases. This implies that a smaller {( a:) is usually 1) more inaccurate and 2) associated with a higher uncertainty.
As a result, with high bias and variance caused by inaccurate (()]z), it is erroneous to learn To (a) () by simply optimizing (B Furthermore, this approach may also hinder the convergence of off-policy learning, discussed later Section 3.2
3 Uncertainty-awarr off-policy learning
Our idea is to consider the uncertainty of the estimated logging policy by incorporating per-sample weight Φn.a. and perform policy learning by optimizing the following empirical estimator:
NN
To (T.))
(UIPS(TT)
Dan.an -Ta ann
(4)
3aa xn))
3

---

Intuitively, one should assign lower weights to samples whose ((a(zz) (z) is small and far away from the ground-truth 5 (a/x) We then divide off off-policy optimization into two iterative steps:
Deriving the optimal instance weight: Find the optimal 6z make VUIPS(TO) approach its ground-truth (T)) as closely as possible, so as to facilitate policy learning. The derived optimal weight is denoted as 6z.a (see Theorem 3.2).
Policy improvement: Update the policy Th (a/z) using the following gradient:
1 To (An Faa) 3(a xx))
V. (oVrrs(TTO)
Σ
& Pz..an Taa.an V (og(zo(an)zn))
The whole algorithm framework and its computational cost, as well as important notations are summarized in Appendix 7.1
3.1 Derive the optimal uncertainty-awarr instance weight
We expect to find the optimal weight Φx.a to make the empirical estimator Vuurs(TT) as accurate as possible, taking into account the uncertainty in estimated logging probabilities. Intuitively, high accuracy of the estimator is crucial for determining the correct direction of policy learning. We follow previous work [36 [29] and measure the mean squared error (MSE) of (UIPs(TO) to the ground truth policy value V (T))), which captures both the bias and variance of estimator, A lower MSE indicates a more accurate estimator.
In UIPS, instead of directly minimizing the MSE, which is intractable, we find Φz,a minimize the upper bound of MSE. we show later, the optimal Φz.a has closed-form solution which relates to both the value of Th (a ( (((ll) and the estimation uncertainty of {(a(z)).
Theorem 3.1. The
squared error (MSE) between VUIPs (To) and ground-truth estimator (TTO) is upper bounded as follows:
MSE (VUIP((TO)) ED (FUIPs(FO)-
-
Bias (VUis((To)) Var (VUIPS(TO))
((31(12) Px -1]
27
))(a|z)) Ta.0
To(a|x)2
Eg-
+ Eg3-
22,0
B(a|z))
As the first expectation term Ero when searching for Φw.a- To minimize this upper bound of MSE, the optimal Φz,a for each sample (xx a) should minimize the following,
2 no (a)a m
is non-negative constant, we denote it as À E [0, x))
v..a (a(aa
2
8 (ala) (alor)
To (a(x2)) +
Pa.a -
62 22.0.
(6)
An interesting observation is that setting dz.a not result in the optimal solution of (6). This is because such a setting only reduces bias (i.e., the first term of Eq. ()) but fails control the second term, which is related to the variance. Moreover, we cannot directly minimize Eq.(6) due to the unknown 3 (alx). But it is possible to obtain a confidence interval which contains (a(zz with high probability, when 3(a ær) is obtained via specific estimator, e.g., (generalized) linear model or kernel methods.
M(la) i.e. turning B(a x) Pa.e into stalæ) (a(a))
I(a
("(a(z) does
we adopt the realizable assumption that 8 (a|az) can be represented by softmax function applied over parametric function fo- (x. Moreover, the universal approximation thcorem [8] states that parametric function with sufficient capacity, when combined with softmax function, approximate any distribution. Then we have:
Following previous work 23
16
8 (a|æ) exp(fe- (x, a)). ((a)=) exp(fo(x: a)).
where fa a) is an estimate of fe- (x, a). Following the conventional definition of confidence interval [20), we define 7 and Uz. such that ( a) fe (x. a) SUa, holds with probability

---

at least 1-ò, where is function of 8 (typically the smaller 8 is, the larger is). Then yU&.o measures the width of confidence interval of fz a) against its ground-truth fe- (x, As derived in Appendix 7.2 with probability at least 1-6, we have 8 (a(x)) E Ba and
2 exp (~7Um.)) ((a|z)) 2 exp (rUm.a) 3(a|z)
B B
=
Z"
Z
where Z = Ee exp(So- (a'(z)) and 2
As 8* (alar) can be any value in Bz,a with high probability, aim find the optimal oz. that minimizes the worst case of 6 thereby ensuring that (TI approaches its ground-trut V(T.) under the sense of MSE, even in the worst possible scenarios. This ensures the subsequent policy improvement direction will not be much worse with high probability. Thus, we formulate the following optimization problem:
Bana 3(a/z)
(a(a)))2 3(a|z)2
min
max
-
+
(8)
Pa.a Buy BB,,
The following theorem derives glosed-form formula for the optimal solution of Eq.
Theorem 3.2. Let n E (exp(=>Umas exp(=Umaax) where Umax max, Un,a. The optimization problem in Eq. 8 has a closed-form solution:
A
S2 min 2/
exp( am,,a)
2n/ (ex((UU,.0) exp( exp(~rUa.a)) 3(a|x)2 exp (->Ux,a)
The following corollary demonstrates the advantage of UIPS. The detailed proof of Theorem 3.2 and
Corollary 3.3 can be found in Appendix 7.8
Corollary 3.3. With H5,a derived in Theorem 3.2 (mp))(mo) in Eq. achieves a smaller upper bound of MSE than (IIPS(TT)) in Eq.
Insights about dz.a- The detailed analysis of the effect of dz can be found in Lemma 7.1 in Appendix 7.8 In summary, we have the following key findings,
For samples whose largest possible propensity score is under control: i.e., Te(ala)
VA, higher
min Bz,
uncertainty implies smaller values T/ B.. This suggests samples of this type with positive rewards are underestimated, and the extend of underestimation increases with the estimation uncertainty. UIPS thus chooses to increase Φ7.0 with uncertainty, to emphasize these long-tai tail positive samples. Conversely, for samples with large propensity scores, UIPS decreases oa the uncertainty increases, so as to prevent their distortion in policy learning.
Uncertainty estimation. Now describe how to calculate Un, i.e., the uncertainty of the estimated (a)a)). this work, we choose to estimate 3 (a|xr) using neural network, because its representation learning capacity has been proved in numerous studies, and 2) various ways [ 45 can be leveraged perform the uncertainty estimation its computational efficiency and theoretical soundness. Following the proof of Theorem 4.4 in 45 given the logged dataset D, we can get with high probability that there exists y such that:
neural network. We adopt [45] due to
[fe( fo. (In,, an))l S vV g( an) M, g( an)
where g( and is the gradient of (2 an) with respect to the neural network's 's last layer's parameter O.. 0, ie., g( an) V fo implying Ua...... V g (m a MM g (m an).
And MD >m g(En, an an)g( ( an) TT
3.2 Convergence of policy learning under UIPS
The following theorem provides the convergence result for UIPS, which converges to a stationary point of the expected reward function. The proof is provided in Appendix 7..
5

---

Theorem 3.4. Denote Gmax and & as the maximum value of | and B.
z3lal (m) (a(m))) ( )²
86
respectively, i.e.,
( 89
S Gmax and Egz.
Talaja) (P(aa))
(0
)2
S
And denote Vmax as the finite
maximum expected reward that can be achieved, and Piua = max {
(0(22)
3(alm) Pa,a -1 Assume
that the expected reward of n. i.e, ((Ta), ) is a differentiable and L-smooth function w.E. 9. Denote the policy parameters obtained by Eq. ( at iteration & E [K] as 02. then Pmax E (0, and
K Σ K
2LV
2Vmax
Gmax V VK
(TT
MII2
K(1 Pmax)
(1 pmax)
where (ma) is the true policy gradient under ground-truth logging probability, ie,, WV(Ta) = Eg-
[alall) (a/a) aea V (
Theorem 3.4 shows that, as K + oo and with 1/(1 - Pmax) and & being controlled, UIPS leads policy update to converge to a stationary point where the true policy gradient (TT)), is zero. And fortunately, UIPS is effective in controlling both 1/(1 (mmax) and $. Specifically, we
A (a|=) -2 denote Pa [((())
and 4 2z,a=
má(alm))
("(aa=)) (0 It is clear to note that Ay2 + 22.0
corresponds to the objective in 6) for deriving @ for each sample (x,, a). In other words, UIPS selects f } to minimize fuua max((p,,a] } and +- Eg. [..aa]. which directly accelerate the policy converge to a stationary point with the true policy gradient being zero.
In the case of BIPS in (3,, b, we have Φn.a = 1. Although & may be large due to small logging prob- abilities, the more concerning issue is that the requirement ymax (0, 1) is no longer satisfied when 3* (a)xx) 2 (a(z)) which may happen with non-negligible probability. Hence, the convergence of policy learning under VIIPS is no better than that under UIPS.
4 Empirical evaluations
We evaluate UIPS on both synthetic data and three real-world datasets with unbiased collection. We compare UIPS with the following baselines, which can be grouped into five categories:
Cross-Entropy (CE): A supervised learning method with the cross-entropy loss over its softmax output. No off-policy correction is performed in this method.
BIPS-Cap g The ooolpy learning solution under the BIPS estimator in Eq. 3 The estimated
propensity scores are further suppressed to control variance, i.e., taking min (c, p(a(=)) as the
(o(e]a)
propensity score. Setting to small value can reduce variance, but introduces bias.
Min & stableVar [46), Shrinkage (36): This line of work improves off-policy evaluation by heg
reweighing each sample. For example, Min and stable Var reweigh each sample by Σ. Mg."
with ha B(al=))
[a(a]=) and M1za no (a(a))) respectively, since they find that TH (a (x) / (z) is
V
directly related policy evaluation variance. Su al. 36 propose to shrink the propensity score by 2/(A+ + B(a[a)²
=a(alm)? which is special case of our UIPS with Uz, 0 and n 1. All these
methods simply treat B(a (x) as 3 (alzz) (z). and none of them consider the uncertainty of 3(aax).
SNIPS [39], BanditNet [16). POEM (38), POXM 23 Adaptive [22]: This line of work aims for more stable and accurate policy learning. For example, SNIPS normalizes the estimator by the sum of propensity scores in each batch. BanditNet extends SNIPS and leverages an additional Lagrangian term to normalize the estimator by an approximated sum of propensity scores of all samples. POEM jointly optimizes the estimator and its variance. POXM controls estimation variance by pruning samples with small logging probabilities. Adaptive proposes a new formulation to utilize negative samples.
ApproxKNN (5) and IPS-C-TS: The line of work improves off-policy learning by applying calibration to estimated logging probabilities. ApproxKNN utilizes the K-Nearest Neighbor algorithm for calibration, which exhibits the lowest calibration error in [5]. IPS-C-TS, on the other hand, employs temperature scaling, a widely recognized and effective calibration method for probability distribution (13).

---

Table 1: Experiment results on synthetic datasets. The best and second best results are highlighted with bold and underline respectively. The p-value under the t-test between UIPS and the best baseline on each dataset is also provided.
T 0.5
T T=2
Algorithm
P85
NDCGORS
FG5
RGF
N
P65
RB5
NDCG
IFS-OT
U.358951
0.1582a6-
0.009351c
0.5526=3
0.1565
0.600781:
0,1557e7:
0.6057a
CB
0.555326
0.157343
0.6037.56
0.5510
0.156125
0.59955
0.3861
0.1524 67
D.5874E2
BIPS-Cap
0.5515 mm
0.1553 14
0,6031 196
0,5526 7x
0.1561
0.6016114
0. 0.5409 13
0.1529.94
0,59011 2
MinVar
0.5340:3
0.585743-
0.5282-3
0.149147:
0
0,509
0.1415et:
3.5543:3e
StableVar
0.4877
0.1310 ste-
0,5111 1%
0.5373 36
0.586613--
0.5279 ca
0.1492
D.5781 33
Strinkage
0.5526:4
0.1562 =Tc
0.6024
0
0,1545
0,6040s3:
0.5347:2
0.1513
0.5824 =2:
SNIPS
6.2616-16-7
0.0729...->
0.3150=5
01997:41
0.414416--2
0,3779
0.1236:5--1
0.5177=3-
BandiiNet
0:4011=9<-*
0.1131=8
0-1830=2
0
0.1095=1.
0.4741
0:4122
0.1153
0.4934aa
POEM
D.54
0.15
0.6008--6-
0,5502-30"
0.60000:2-
0,1526:5:
POXM
0.4006=
0.1130
0,1828+2--
0.3616
0.1019
0.152264:
0.3816
0.1069
0.1680
Adaptive
D. 13383188-
0. 1050+6-
0,38249.-*
644734
0,1325e1e
0.532663: -1
0 0.3936e
0,109744:71
0:4368=3
AppooaNN
D.5576-1
0.1500
0.5527
1.1567
0.0010
0.4422
0,153266-
1.5890
IPS-C-TS
0,5565+1e
0.1577 =5c
0.6048477
0.5517=te
0.156342
0.6002s6:
1.5393
0.152655:
0.5879
UIPS-P
0.9004-11"
0.10%611
0.4749-3--2
0,109:3
0.1149
D.4922
UIPS-O
0.4138
1.1767
0.4954.a
0.3896.
0.1096.1.
L.
0.1268
0.5296
UIPS
0.5608
0.15#9:s-
0.6113:3-
0.5572-5-
0.1571
0.6074 -.
0.5432:3-
0,1534
0.5946-2
p-value
3e
Table 2: Performance under different uncertainties.
Actions Samples with High Uncertainty
Actions Samples with Low Uncertaluty
Agorithm
R
NIXCG055(R))
PRF5(R))
R
CE
0.5190
0.1231
0.5526
0.5913
0.1915
0.6549
BIPS-Cap
0.5117 (-1.1%%)
0.1202 (-2.33%)
0,5488 (-0.68%)
0.5913 (+0.00%)
0.1903 (-0.64%)
0.6574 (+0.39%)
Shrinkage
0,5158 (-0.628)
0.1217 (-1.11%)
0.5505
(- (-0.37%)
0,5892 (-0.35%)
0.1905 (-0.55%)
0.6546 (-0.05%)
CIPS
0.5222 (+06)1))
0.1237 (+0.50%)
0.5568 770,)
0.5934 38133%
0.1940 (+1.28%)
(=1.666)
UIPS-P and UIPS-O: These are two variants of our UIPS with different ways of leveraging uncertainties. UIPS-P directly penalizes samples whose estimated logging probabilities of high uncertainty, i.e., taking Øz.a = 1.0/ exx(>)Uz.)) which follows previous work on offline reinforcement learning 43 4. UIPS-O adversarially uses the worst propensity score for policy learning, i.e., Φz.a = 1.0/ exp(-nUa,a).
4.1 Synthetic data
we generate a synthetic dataset by a supervise- to-handit conversion Wiki10-31K dataset 7 which is extreme multi-label classification dataset. The Wikil0-31K dataset contains approximately 20K samples. Each sample is associated with a feature vector 0 of 101,938 dimensions and a label vector ya of 3 31K classes with more than one positive class. Let Ya denote the label of class a under æ. and we take each class as an action. The huge action space creates great challenges in off- off-policy learning, e.g., sparse observations, and therefore better evaluates different methods.
Data generation. Following previous work 24 23
We split the dataset into train, validation and test sets with size 1 I:KKKK The test set is from the official split. Since the original feature vector z is too sparse, for ease of learning, we first embedded to dimension by x Wa, and synthesized the ground-truth logging policy 3 (alæ) by:
8* (a(x) x exp (x OO/T),
where W and {0:} are pre-trained parameters by applying a logistic regression model on the train set, is positive hyper-parameter that controls the skewness of logging distribution. A small value of leads to a near-deterministic logging policy, while a larger r makes it flatter. More implementation details can be found in Appendix 7.3
Evaluation metrics. To evaluate the learned policy T (z). we calculate Precision @ (P@K) K), Recall @K K (R () and NDCG@K K following previous work [23 24 Higher P@ K, R@ K and
NDCG@K K imply better policy.
Effectiveness of policy learning. Table shows the average performance and standard deviations of all algorithms under 10 random seeds on three synthetic datasets generated under different т. As the ground-truth logging policy is accessible on the synthetic datasets, we included a new baseline IPS- GT, which uses the IPS estimator with the ground-truth logging probabilities. We calculated p-value under t-test between UIPS and the best baseline to investigate the significance of improvement.
First, we can observe that UIPS achieved similar and even better performance than IPS-GT when 0.5 and = 1, but performed worse than IPS-GT when 7 2. Despite using ground-truth
7

---

logging probabilities, IPS-GT GT still suffered from high variance caused by samples with small logging probabilities, which is the main cause of its worse performance when 0.5 and T = 1. In contrast, UIPS effectively controlled the negative impact of these high-variance samples, resulting in a better bias-variance trade-off.
With an increasing т, suggesting decrease in the probability of selecting positive actions, most algorithms experienced a drop in performance. However, UIPS consistently outperformed all other algorithms across all three datasets and metrics. Interestingly, as т decreases, the performance improvement of UIPS became even more pronounced, despite SNIPS, BanditNet, and POXM being designed to handle small logging probabilities of positive actions.
ApproxKNN and IPS-C-TS generally achieved better performance than BIPS-Cap, implying the effectiveness of calibration of estimated logging probabilities. However, UIPS still consistently outperformed both ApproxKNN and IPS-C-TS. The main reason that calibration primarily focuses on adjusting the estimated probabilities to ensure on average the model's predictions are reliable and accurate. In contrast, UIPS specifically handles the impact from each individual sample in policy learning.
UIPS also consistently outperformed Shrinkage (a special case of UIPS with uncertainties always being zero) on all three datasets, demonstrating the benefits of considering the estimation uncertainty. Finally, blindly reweighing through uncertainties, regardless of their impact on the accuracy of the resulting estimator and the learned policy, ultimately resulted in poor performance, as demonstrated by UIPS-P and UIPS-O.
Performance under different uncertainty levels. As shown in Figure 1 low-frequency samples in the logged dataset suffer higher uncertainties in their propensity estimation. Thus, we divided the test set into two subsets according to the average frequency of associated actions, where the uncertainty in the subset associated with low-frequency actions is on average 8% higher than that in fighffrreyency actions. Table shows the results on these two subsets when T = 0.5. In addition, we include the results of the top three baselines that directly utilize the estimated logging policy. Table 2 clearly demonstrates that only UIPS performed better than CE on the test set with low-frequency actions, implying the distortion of inaccurately estimated logging probabilities and the effectiveness of UIPS in efficiently handling them.
We further inspected whether VUIPS in Eq.44) leads to more accurate off- policy evaluation. Following previous work (29 46 (36), we evaluated the following c-greeyy policy: T (a|z)) = | x. For each x in the test set, we randomly sample 100 actions following the logging policy in (9)
Off-policy Evaluation.
I-c Ifa M,)+ c/lA), where M,, contains all positive actions associated with instance
to generate the logged dataset. Table ssbles the MSE of the estimators to the ground-trutt truth policy value under 20 different random seeds. From Table one can observe that: 1) IPS-GT with a skewer
logging policy (i.e., smaller 7) leads to higher MSE, consistent with previous findings (29 46 36 2) inaccurate logging probabilities result in high bias and variance, leading to much larger MSE of BIPS compared to IPS-GT. Furthermore, this distortion is particularly pronounced when the ground-truth logging policy is skewed (r = 0.5); and 3) although all using the estimated logging policy, VUPPS yields the smallest MSE, comparing to other baselines that are designed to improve over BIPS.
Hyper-parameter Tuning. Discussions about hyper-paramette tuning and performance of UIPS under different hyper- paraeeerrs can also be found in Appendix 7.3.1
4.2 Real-world data
To demonstrate the effectiveness of UIPS in real-world scenarios, we evaluate it on three recommen- dation datasets: (1) Yahoo! R: (2) Coaf (3) KuaiRec [12), for music, fashion and siort-video recommendations respectively. All these datasets contain unbiased test collected from randomized controlled trial where items are randomly selected. The statistics of the three datasets and implementation details, e.g., model architectures and dataset splits, can be found in Appendix 7.3.2
we take K- on Yahoo! R3 and Coat datasets, and K 50 on KuaiRec dataset. The p-value under the t-test between UIPS and the best baseline on each dataset is also reported to investigate the significance of improvement.
Following 10),
httpe://webscope.ste sandbox. aahoo..cmm httpp://www.
http://wwwww..wcll..ooooo. wornell. fornell.edu/'
8

---

Table 3: MSE of different off-policy estimators. A lower MSE indicates a more accurate estimator.
Algorithm
GT
BIPS
min Var
Var
Shrinage
CPP
T 0.5
0.0875++4e
15.786+1151
0.9021+7e- Is
0.8612+55
0.0718=5e
0.0210 2e
1.0
0.020948c
0,551040,388 388
0,901948c-1
0,857842c
O. 2.
0.0093 lc
2.0
0.0020+66
0.5669+00001
0.9015+56
0.
-
0.
0.0043 4e-
Table 4: Experimental results on weal-world datasets. The best and second best results are highlighted with bold and underline respectively. The p-value under the t-test between UIPS and the best baseline on each dataset is also provided.
Yahoo
Coat
KuaiReee
Algonihh CE
5
RGi
N
PGr5
Roi5
N
PG550
Ro050
NDCG S0
0.2819=2;-"
0.7594
0.6073atc
0.2799
0.4618a1e
0.4529#2=
0.8802+2.
0,0210aa:
0.8810
BIPS-Cap
0.2808=9""
0,7576e1
0.609948
0.2758e6:
0,452247"
0,4399
0,875063:
0,02844:
0.878845.
MinNar
6-
0.7685-1-73
0.616841-
0,281343-"2
0.4668
0.441418-1
0.8827746
0.0240.5--
0.888613
VaablcVar
0.2787=a-
0,5919 0.7499
0.2810=1--2
0.4662e5:
0:439322-
0.8524
0.021+22--
0.8570
Shrinkage
0.2843-3-
0.7654
06620477e
0.2790
0.46664477
0.4464a1e
0.874483-
0.8771 0,028
SNIPS
0.2222 6
0.5828 -
1.4357
0,2643.7-
144287
0.4009 19
0.841116-
0,0228 12--
0.8431 10s
BanditNet
8.
0.6442=2
0.498843
0.2781 58
0.4277
0.4251+1e
0.875845
0.029++2
0.8810
PORM
0.27332 sm
0.7357
0.5880
0.2791 1-4-
0446661--
0.7385
0.0210
0.7779..6-
POXM
0.2250.
0.5940.1e
1.4542
0,2663
0.4308
0.4006.1e
0.8962.1e
0.0245
0.9041 ste
Adaptive
0.2762-5-
0.7451:9-3
0,9919484-4
0,2830
0.46445--1
4.21745---1
0,8375
4.027
ApprosKNN
0.2697=2-7
0.7225e3c*
0,5760
0,2755+2:
0.4594
0,4490
0.883922:
0,024055:
0.8895+2
IPS-C-TS
0.2816:2-1
0,7582
0.611455-
0.2799
0.4625
044422mm-
0
00229
0.8749
UIFS.F
0.1829 mM
0.4500.3
0.350011
0.2685 17
0.436419
0.408717
0.863818
0.0255
0.8685 17e
UIPS-O
0.1947=3=
0.4959
0.3600
0.2657a3e
0.4306
0.4146
0.865
las:
0.025
0.8697
UIPS
0.7742 (x
0.6274.5-
0.2877 13.
0.4757
1.4576
0.9120
0.9174.1-
p-valinc
46
Te
36
26"
6r
6e
6c.
6e
1e
We can first observe from Table 4 that on all three datasets, the proposed UIPS achieved the highest precision, recall and NDCG. Apparently, accurate estimation of logging probabilities in real-world scenarios with large action spaces and sparse interactions is challenging to achieve, causing BIPS- Cap to underperform CE. Additionally, calibration poses difficulties in such scenarios, leading to poor performance of ApproxKNN and IPS-C-TS across all three real-world datasets. BanditNet, POEM and POXM performed better in problems with larger action space, while Min Var, stable Var and Shrinkage as well as Adaptive suited better for scenarios with a smaller action size. Again, UIPS outperformed Shrinkage, highlighting the importance of handling uncertainty in the estimated logging policy. But simply reweighing based uncertainties, without considering their impact on the accuracy of the resulting estimator and the learned policy, led to poor performance, as shown by UIPS-P and UIPS-O.
4.3 Comparisons against other lines of off-policy learning
We discuss about the difference between UIPS and recent work with direct propensity estimation R4 (1) the DICE line of work 226 47 9
as well as the work on the distributionally robust off- off-policy in Appendix 7.6 Appendix 7nd and Appendix [7.7 respectively Our empirical from all three lines suggest that these lines of work cannot properly handle inaccuracies in the estimated logging probabilities that hinder policy improvement. Moreover, we also integrated the proposed UIPS with the doubly-robust (DR) estimator and our results suggest the accuracy of the imputation model greatly affected policy learning under DR, but UIPS still provides benefits. More details can be found in Appendix (74
learning
32 17
evaluations on recent work (26 |4
5 Related work
Our work is the first of its kind to account for the uncertainty of logging policy estimation in off- off-policy learning. The following two lines of work are most related to this work.
Off-policy learning. In many real-world applications, such as search engines and recommender systems, interactive online model update is expensive and risky [T3] Off-policy learning has therefore attracted great interest, since it can leverage the already logged feedback data (2 8 22). The main challenge in off-policy learning is address the mismatch between the logging policy and the learning policy. One common and aaplled approach is to leverage the Inverse Propensity Scoring (IPS) method to correct the discrepancy between the two policies. And various methods are
proposed to enhance IPS for more stabilizing learning [39 37 38 and improved variance control
[23 22
well as extensions to more complex problems 40 24
9

---

However, all these solutions directly use the estimated logging policy for off- correction, leading to sub-optimal performance as shown in our experiments. A recent study on causal recommendation [10] also argues that propensity scores may not be correct due to unobserved confounders. They assume the effect of unobserved confounder for any sample can be bounded by pre-defined hyper- parameter, and adversarially search for the worst-case propensity for learning. Mapping to off-policy learning, their solution is special case of our UIPS-O variant with uncertainty pre-defined constant.
There were existing studies 34 21
26 47 9 also explore direct estimation of the propensity ratio Appendix 7.5
to bypass estimating the logging policy. However, discussed in Appendix 67.6 (.. they demonstrate inferior performance compared to UIPS. This is primarily due to either the lack of consideration for the accuracy of the estimated propensity ratio, similar to the limitations of existing IPS-type algorithms in handling inaccurately estimated logging probabilities, or the degeneration to a specific IPS estimator that suffers high variance.
also addresses uncertainty in off-policy learning. However, their approach to handling uncertainty and the underlying motivation differ significantly from ours, resulting in distinct techniques employed. Further details can be found in Appendix 7.7 Additionally, experiments conducted in Appendix /7.7 demonstrate that directly adapting methods from distributionally robust off- off-policy learning to handle inaccurately estimated logging probabilitics leads to poor performance.
Recent work on distributionally robust off-policy evaluation and learning 32
Off-policy learning can also be directly built on off-policy evaluation. Several work 136 46) also propose control the variance of the estimator caused by small logging probabilities through instance reweighing. Again, they directly use the estimated logging policy for correction, and thus performed worse than UIPS as observed in experiments. A recent study [29] assumed additional structure in the action space and proposed the marginalized IPS. Instead, our work considers the uncertainty in the estimated logging policy and thus does not add any new assumptions about the problem space.
Uncertainty-aware learning. Estimation uncertainty has been extensively studied 45 50 I.. In the context of on-policy reinforcement leanring and bandits ( 48 (4),, the use of uncertainty aims to strike a balance between exploration and exploitation by adopting an optimistic approach (i.e.. UCB
in bandits). One the other hand, most reseach on offline reinforcement learning/bandits 43 4 tends to be more conservative, employing techniques such as Lower Confidence Bounds (LCB) or penalizing out-of distiiiittiittoonnn states and actions based on uncertainty to address extrapolation errors. However, these principles differ fundamentally from UIPS, which directly minimizes the mean square error of off-policy evaluation. The closed-form solution of the resulting per-instance weight in UIPS reflects how uncertainty contributes to the policy evaluation error. Moreover, Our UIPS-O and UIPS-P baselines leverage uncertainties using the two aforementioned general principles respectively. However, empirical findings indicate that blindly penalizing or boosting samples based on uncertainty problematic. Proper correction depends on both uncertainty in logging policy estimation and the actual value of estimated logging probabilities.
6 Conclusion
In this paper, we propose Uncertainty-aware Inverse Propensity Score estimator (UIPS) explicitly model the uncertainty of the estimated logging policy for improved off- oof--ooicy learning. UIPS weighs each logged instance reduce its policy evaluation error, where the optimal weights have a closed- form solution derived by minimizing the upper bound of the resulting estimator's mean squared error (MSE) its ground-truth value. An improved policy is then obtained by optimizing the resulting estimation. Extensive experiments on synthetic and three real-world datasets as well as the theoretical convergence guarantee demonstrate the efficiency of UIPS.
As demonstrated in this work, explicitly modeling the uncertainty of the estimated logging policy is crucial for effective off-policy learning; but the best use of this uncertainty is not to simply down- weigh drop instances with uncertain estimations, but balance it with the actually estimated logging probabilities in a per- per-instance basis. As our future work, it is promising to investigate how UIPS can be extended to value- based learning methods, e.g., actor-crities. And on the other hand, it is also important to analyze how tight our upper bound analysis of policy evaluation error is; and possible, find new ways to tighten it for improvements.
10

---

References
[1] Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[2] Aman Agarwal, Ivan Zaitsev, Xuanhui Wang, Cheng Li, Mare Najork, and Thorsten Joachims. Estimating position bias without intrusive interventions. In Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, pages 474 482, 2019.
[3] Ahmad Ajalloeian and Sebastian U Stich. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008. 0000/, 2020.
[4] Gaon An, Seungyong Moon, Jang-Hyun Kim, and Hyun Oh Song. Uncertainty-base offline reinforcement learning with diversified q-ensemble. Advances in neural information processing systems, 34:7436-744) 2021.
[5] Raghu Aniruddh, Gottesman Omer, Liu Yao, Komorowski Matthieu, Faisal Aldo, Doshi-Velez Finale, and Brunskill Emma. Behaviour policy estimation off-policy policy evaluation: Calibration matters. arXiv preprint 10Xiv:187.00166. 2018.
[6] Chenjia Bai, Lingxiao Wang, Zhuoran Yang. Zhihong Deng, Animesh Garg, Peng Liu, and Zhaoran Wang. Pessimistic bootstrapping for uncertainty-driven offline reinforcement learning. arXiv preprint arXiv:2202.1 1566, 2022.
[7] K. Bhatia, K. Dahiya, H. Jain, P. Kar, Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets and code, 2016.
[8] Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k off-policy correction for a reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 456-464, 2019.
[9] Bo Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvári. and Dale Schuurmans. Coindice: Off-policy confidence interval estimation. Advances in neural information processing systems, 33:9398-944 99181,911111111111111111111 2020.
[10] Sihao Ding, Peng Wu, Fuli Feng, Yitong Wang, Xiangnan He, Yong Liao, and Yongdong Zhang. Addressing unmeasured confounder for recommendation with sensitivity analysis. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 305-315, 2022.
[11] Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pages 1050-1059, PMLR, 2016.
[12] Chongming Gao, Shijun Li, Wenqiang Lei, Jiawei Chen, Biao Li, Peng Jiang, Xiangnan He, Jiaxin Mao, and Tat-Seng Chua. Kuairec: A fully-observed dataset and insights for evaluating recommender systems. In Proceedings of the 3 Is ACM International Conference on Information and Knowledge Management, CIKM '22, 2022.
[13] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321-1330. PMLR, 2017.
[14] Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. Deepfim: a factorization-machine based neural network for ctr prediction. arXiv preprint 173.:47003.04447, 2017.
[15] Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652-661. PMLR, 2016
[16] Thorsten Joachims, Adith Swaminathan, and Maarten De Rijke. Deep learning with logged bandit feedback. In International Conference on Learning Representations, 2018.
[17] Nathan Kallus, Xiaojie Mao, Kaiwen Wang, and Zhengyuan Zhou. Doubly robust distribu- tionally robust off-policy evaluation and learning. In International Conference on Machine Learning, pages 10598-10632. PMLR, 2022.

---

[18] Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Conference on learning theory, pages 2306-2327. PMLR, 2020.
[19] Sergey Levine and Vladlen Koltun. Guided policy search. In International conference on machine learning, pages 1-9. PMLR, 2013.
[20] Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 2071-2080. PMLR, 2017.
[21] Xu-Hui Liu, Zhenghai Xue, Jingcheng Pang, Shengyi Jiang, Feng Xu, and Yang Yu. Regret minimization experience replay in off-policy reinforcement learning. Advances in Neural Information Processing Systems, 14:17704-17615, 2021.
[22] Yaxu Liu, Jui-Nan Yen, Bowen Yuan, Rundong Shi, Peng Yan, and Chih-Jen Lin. Practical counterfactual policy learning for top-k recommendations. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 111-11151, 2022.
[23] Romain Lopez, Inderjit S Dhillon, and Michael Jordan. Learning from extreme bandit feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8732-8740, 2021.
[24] Jiaqi Ma. Zhe Zhao, Xinyang Yi, Ji Yang. Minmin Chen, Jiaxi Tang, Lichan Hong, and Ed H Chi. Off-policy learning in two-stage recommender systems. In Proceedings of The Web Conference 2020, pages 463-473, 2020.
[25] Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc Bellemare. Safe and efficient off- off-policy reinforcement learning. Advances in neural information processing systems, 29, 2016.
[26] Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 32, 2019.
[27] Doina Precup.
Eligibility traces for policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[28] Aniruddh Raghu, Omer Gottesman, Yao Liu, Matthieu Komorowski, Aldo Faisal, Finale Deshi-Velez, and Emma Brunskill. Behaviour policy estimation in off-policy policy evaluation: Calibration matters. arXiv preprint /807 2018
[29] Yuta Saito and Thorsten Joachims. Off-policy evaluation for large action spaces via embeddings. arXiv preprint arXiv:2202.06317. 2022.
[30] Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and Thorsten Joachims. Recommendations as treatments: Debiasing learning and evaluation. In international conference on machine learning, pages 1670-1679. PMLR, 2016
[31] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897, PMLR, 2015.
[32] Nian Si, Fan Zhang, Zhengyuan Zhou, and Jose Blanchet. Distributionally robust policy evaluation and learning in offline contextual bandits. In International Conference on Machine Learning, pages 8884 8894. PMLR, 2020.
[33] David Silver, Aja Huang. Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Dricss- che, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
[34] Samarth Sinha, Jiaming Song, Animesh Garg, and Stefano Ermon. Experience replay with likelihood- free importance weights. In Learning for Dynamics and Control Conference, pages 110-123. PMLR, 2022.
12

---

[35] Alex Strehl, John Langford, Lihong Li, and Sham M Kakade. Learning from logged implicit exploration data, Advances neural information processing systems, 23, 2010.
[36] Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík. Doubly robust off-policy evaluation with shrinkage. In International Conference on Machine Learning, pages 9167-9176. PMLR, 2020.
[37] Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16(1):73111175, 2015.
[38] Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference on Machine Learning, pages 814-823. PMLR, 2015.
[39] Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. advances in neural information processing systems, 28, 2015.
[40] Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miro Dudik, John Langford, Damien Jose, and Imed Zitouni. Off-policy evaluation for slate recommendation. Advances in Neural Information Processing Systems, 30, 2017.
[41] Sebastian Thrun and Michael L Littman. Reinforcement learning: an introduction. Al Magazine, 21(1):103-103, 2000.
[42] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):229-256, 1992.
[43] Yue Wu, Shuangfei Zhai, Nitish Srivastava, Joshua Susskind, Jian Zhang, Ruslan Salakhutdinov, and Hanlin Goh. Uncertainty weighted actor-critic for offline reinforcement learning, arXiv preprint arXiv:2 10, 2021.
[44] Da Xu, Yuting Ye, Chuanwei Ruan, and Bo Yang. Towards robust off off-policy learning for runtime uncertainty. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10101-10109, 2022.
[45] Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. In International Conference on Learning Representa- tions, 2021.
[46] Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings the 27th ACM SIGKDD Conference on Knowledge Discovery & Duta Mining, pages 2125-2135, 2021.
[47] Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. arXiv preprint arXiv:2002.09007, 2020.
[48] Xiaoying Zhang, Hong Xie, Hang Li, and John CS Lui. Conversational contextual bandit: Algorithm and application. In Proceedings of the web conference 2020, pages 662-672, 2020.
[49] Xiaoying Zhang, Hong Xie, and John CS Lui. Heterogeneous information assisted bandit learning: Theory and application. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pages 2135-2140. IEEE, 2021.
[50] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.
[51] Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1059-1068, 2018
13

---

Algorithm UIPS
1: Input: The logged dataset D := {(I,, On Tm am n/ E [N]), the estimated logging policy
model ((aaz) En, " dimension d.
exp(fa
2: Initialize MD = Laxd.
3: for 1 to N do
4: MD = MD + Volo(an; On) (o
D Mp for uncertainty calculation.
5: end for
6: for = 10 N do
7:
Unn.an V Vefo(xns an) T MD an)
8: end for
9: while not converge do
for N do
11:
Calculate "2,,a, as in Theorem 3.2
12:
Calculate gradients as in Eq. 5 and updating Th (a(zz) end for
13:
14: end while
15:
Output:The learnt policy (a(a)))
Appendix
7.1
Notations and Algorithm Framework.
For ease of reading, we list important notations in Table and summarize the main framework of the proposed UIPS in Algorithm
Notation
Description
X
context space
A
action set
a: E Rd
context vector
a
action
Tw.o
reward
([a a))
targeted policy to evaluate the unknown ground-truth logging policy
3r az)
B(a x))
the estimated logging policy
V(T)
value function
D = (In, Ons Fm. am
12 E
logged dataset containing N samples the optimal uncertainty-awe
22.0
weight
the unknown ground truth function
(x)
that generates 3 (a ()) Σ. exp(fo= (æ.a')
exp(Jo- (2x,))
f0 a)
the estimate of fo- [x. a) that generates B(a confidence interval of ((a x))
Ba.a
Una
uncertainty defined as [ (x. a) Solæ, a) 70,a
g(En, (n))
gradient of fe a) regarding to the last layer.
Table 5: Notations
Computation Cost. The additional computation cost of UIPS over IPS comes from two parts:
Pre-calculate uncertainties (line 1-5 in Algorithm I This part calculates uncertainty of the logging probability for each (s, a) pair, and it only needs to be executed once. The computational cost of this step is O(Nd² + d²), where O(Nd) is for calculating uncertainties in each (x, a) pair and (dd²) for matrix inverse.
Calculate di during training (line in Algorithm It only takes O(1) time, the same computational cost calculating IPS score.
14

---

Note that calculating the logging probability for each sample, which is essential for both UIPS and IPS. takes ((Nd]A) time. Since the dimension d is usually much less than action size [.A] and sample size N, UIPS does not introduce significant computational overhead compared to the original IPS solution.
7.2
Derivation of confidence interval of logging probability.
Given that |fo- (æ, a) - =f( a)l 1 VUn, holds with probability at least and
(alx) = exp(fe. (x) B(alz) exp(fo(æ,a) a))
2
where ="= =e exp(fo- (a'(z)) and Ew exp(fo(d|(z))) get that with probability
least 1 0:
( a) folæ, a)l S yUn.a
< (o - TUe, S fe (x, a) S folæ, a) + +-aaa
exp(fo(az a)) exp( - x2) exp(So- (a. a)) exp(so exp(772..)
2 2 1epp(~UU,.d exp (2, a)) S (,((a(z)) exp(>Um.a)
@ 2 exp (->Uma) B(a S (a Z exp (nUzz,)) ((aaa))
7*
7
The step labeled as (1) is due the modelling of 3(a|zz). And the step labeled as (2) is because Z" is positive constant independent of (aaaz)) Thus with probability at least 1-8, we have 3 (a/x) Bæ, and
1 exp (-7Uma) (((lz)) 2 exp (YU/m, ((alz))
B
Z
Z.
7.3
Experiment details
7.3.1 Synthetic Data
Data generation. Given the ground-truth logging policy (a|z), we generate the logged dataset as follows. For each sample in train set, we first get the embedded context vector from its original feature vector We then sample action a according to 8 (alær, and obtain the reward Ym.o Ya.a, resulting bandit feedback (æc, o, Tn,a), where ya.a is the label of class a under the original feature vector ă. We repeat above process N times collect the logged dataset. In experiments, we take 64,
100.
We model the logging policy as in Eq. where {0a} are the parameters to be estimated. To train the logging policy, we take all samples the logged dataset as positive instances, and randomly sample non-selected actions as negative instances as in [8]
7.3.2 Real-world Data
Statistics of datasets. The statistics of three real-world recommendation datasets with unbiased data can be found in Table G
Table 6:
The statistics of three real-world datasets.
Dataset
#User
#ltem
#Biased Data
#Unbiased Data
Yahoo R3
15,400
1,000
311,704
54,000
Cout
290
300
6,960
4,640
KuaiRec
7,176
10,729
12,530,806
4,676,570
All these datasets contain a set of biased data collected from users' interactions on the platform, and set of unbiased data collected from a randomized controlled trial where items are randomly selected, As in [10], on each dataset, the biased data is used for training, and the unbiased data is for testing, with small part of unbiased data split for validation purpose (5% on Yahoo R3 and Coat,
15

---

and 15% on KuaiRec), We take the reward as 1 if (1) the rating is larger than 3 in Yahoo! R3 and Coat datasets; (2) the user watched more than 70% of the video KuaiRec. Otherwise, the reward is labeled as 0.
We adopted two-tower neural network architecture to implement both the logging and learning policy, as shown Figure 2 For the learning policy, the user representation and item representation are first modelled through two separate neural networks (i.e., the user tower and the item tower), and then their glement-b--elemen
product vector projected to predict the user's preference for the item. We then re-use the user state generated from the user tower of the learning policy, and model the logging policy with another separate item tower, following (8). We also block gradients prevent the logging policy learning interfering the user state of the learning policy. In each learning epoch, will first estimate the logging policy, and then take the estimated logging probabilities well as their uncertainties to optimize the learning policy.
B(abx)
TT(a
MLP
MLP
block
iter amb
user state
neural net
neural net
item tower
tower
feature
Figure Model architecture of the logging and the learning policy in real-world datasets
7.3.3 Implementation details.
To facilitate hyper- prper-parameter tuning, we disentangled two rys in two the terms of d2.. in Theorem 3.2 and introduce 1/1 and !/2 to represent v) in the first and second term respectively in our implementation. This is due to the scale of 1 in the first term is closely related to the scale of X, with X/ /1) the truly effective hyper-parameter. But the scale of 1) in the second term is independent from X.
cannot adaptively set the value of À since the ground-truth logging policy (alar) is unknown. However, we have:
Moreover, while À E [
(ala) (a(
depends mo as discussed in Eq.
To(a(x)) A = Ex a (alax)
Σ TO (a|x)))
Σ
<
B (al )2
B (a|z))
where the first inequality is due to the Cauchy-Schwarz inequality and the second inequality is r
because Σ. (a(a)=)) Σ. Te(alz>) = 1 with To(alæ) E [0, We denote = -Ea
J-(a|>))
which is dataset-specific constant and independent from By replacing À in Eq. with I, we can still minimize an upper bound of MSE(Vurrs which ensures that the result of our analysis still holds. Thus, considering ease of computation and efficiency, we take fixed X during our policy learning.
We then use grid search to select hyperparameters based on the model's performance on the validation dataset: the learning rate was searched (le-5, le 14- 1e-3, le-3): "); X, 7, 7/1 were searched (0.5, 0.1, 1, 2.5, 10, 15, 20, 25, 30, 40, 50). And 7/2 was searched in (1, 10, 100, 1000). For baseline algorithms, we also performed similar grid search as mentioned above, and the search range follows the original papers.
Ablation study: hyper- parameter tuning, Although UIPS has four hyperparameters (A, 7, 7/1 and )2), one only needs to carefully finctune two of them, i.c., 7 and n/ / A, to obtain good performance of UIPS. This is because:
16

---

+85
NDCGB5
0.310
0U000
33946
C:511
00233
3500
5.550
33.89
0352
6:104
0330
SUB-
A4100
8:000
$1:00
0393
61104
81923
1M
5194
335
8547
03812
33541
C:554
0351
61342
03555
81507
02171
0351
03980
00000
C.000
10
130
Procision@S
(bi Recall
(c) NDCGB5
Figure 3: Effect of À and 7 synthetic dataset with 0.5
acts as capping threshold to ensure &h S 27/2 holds even when the corresponding propensity scores very low. Hence, should be set to reasonably large value (e.g.. 100).
The key component (i.e., the first term) of & can be rewritten in the following way. While all (ær, a) pairs will be multiplied by &2,a Ti in the numerator will affect final performance too much, and the key to find good value of nl / balance the two terms in the denominator:
w1/x To (alar) 3(a|z)3 exp (~>Ux,
m/ exp (-)) +
Thus with 7n and 1/2 fixed, the effect of hyper-parameter y and À on precision, recall as well as NDCG be found in F We observe that to make UIPS excel, BR,a needs be of high confidence, c.g., = 25 performed the best on the dataset with t 0.5. Moreover, the threshold VX/m mn cannot be too small or too large.
7.4 Experiments on the doubly robust estimators.
The doubly robust (DR) estimator [15], which is a hybrid of direct method (DM) estimator and inverse propensity score (IPS) estimator, is also widely used for off- off-policy evaluation. More specifically, let X' x A - R be the imputation model in DM that estimates the reward of action a under context vector and ((aax:) ) be the estimated logging policy in the IPS estimator. The DR estimator evaluates policy ı based the logged dataset D (Zn,
One aa. )/1 [N]], []],bb by:
N x(an (n)) (Fmm.en iF an))
1
VDn(TT) = (TD
+
(10)
N
(anl(zn)
n=1
where (T) the DM estimator:
VDM((T)
((llx)))((nn.)))
(11)
n=1 DEA
Again assume the policy (a/ar) parameterized by the REINFORCE gradient of (D)((T)) with respect to 0 can be readily derived as follows:
V VoVDR(TT)
1
Σ
Σ NaEA
nH (aluaan a) Vo (og((Ta((azz..)))
N
V (a, (mn) (ramia, (x Vo lo (anl
(12)
iaa (x,))
The imputation model (x, a) pre-trained following previous work [22 with the same neural network architecture as the logging policy model. Besides the standard DR estimator, we also adapt
17

---

Table 7: Experiment results on synthetic datasets. The best and second best results are highlighted with bold and underline respectively. Two p-values are calculated: (1) p-value (UIPSDR): The p-value under the t-test between UIPSDR and the best DR baseline on each dataset; (2) p-value (UIPS): The p-value under the 1-test between UIPS and the best DR baseline on each dataset.
F- 0.5
r-2
Algreichm
PR5
Re5
N
PG8
R35
NDCGAR
PRR
NIXG@s
CiPS-Cap
0.551522
0,1553 Lne
0.0031
0.552622
0.1561am
0.0016116
0.5419
0.1529:
0.590L
UPPS
0.1983-5--*
0.6095
0.5872495"7
0.157148
0.5492-3-
0.1534:67
0.594669-
DR
0.3816=14
0.1082=3
0.66111
0,3631a3
0.101745
02
0.3560
0.099527
0.4170=2
MinNarDR
0.3
0.0908
0.4062=1-
0.3240
0.0500
0.3905
0.3234
0.0910
0.4059
ShrinkageDR
0,4189
0.1161
0.4969
0.3944
0.1101
0.4797
0,080
0.1135
0,4901
UIPSDR
0.4278-22
0.1200
0.5069
0.40088:5
0.112645
0.4847:22
0.144
0.1162:5.
0.4972
povalue (LIPSDRR
2--3
3e-1
4x-1
Gem1
6a-
4e
5e-1
p-value (UIPS)
Ge-13
4--13
1e-12
2em-2
1e-12
5e-12
S--12
8--12
Table 8: Experiment results real-world unbiased datasets. The best and second best results are highlighted with bold and underline respectively. Two p-values are calculated: (1) p-value (UIPSDR): The p-value under the t-test between UIPSDR and the best DR baseline each dataset; (2) p- p-value (UIPS): The p-value under the 1-test between UIPS and the best DR baseline on each dataset.
Yahoo
Cont
KuaiRee
Algreishi
PRS
Re05
NDCGIO
PGe5
RB5
NDCGRR
PR 50
BIPS-Cop
0,2808 2x
0.7576:1
6.60999
0.2758ar
0.4582176
0.43999
0.875025
0.0228
0.8788
UPPS
0.7742-34
0.6274-16"
04757-55
04576:8-
0.9120-31-
D.0250-5
0.917447m"
DX
0.2670-2:
0.56366414
0,255
0.1700es
0.891
0.02200666
0.85
MinNarDR
0.
0.5989=14-*
0.4525
0.270424m7
04443429
0.4137
0.8640
0.0235:22
0.8657
ShrrinkageDRR
0.2697
0.7226
0.5713:55-
0.2895197"
0.4799
0.4526.6
0.8778
0.0239
0.8
UIPSDR
0.2721-11
0.7294-1
0.5750
0.2946
0.4854:3.
0.4647
0.8849
0.0242:44
0.8896
p-value (LIPSDDR)
1e
26
16-1
76
5em
26-3
46"
4e
3x
p-value (UIPS)
12
61
1e
UIPS and the best two baselines on off-policy evaluation estimator (i.e., Min and Shrinkage based on the results in Table Salleeaama aadd Table 4 to doubly robust setting using the same imputation model.
Table 7 and Table g report the empirical performance of the learned policy on the synthetic datasets and three real-world datasets respectively. For case of comparison, we also include the experiment results of BIPS-Cap and UIPS on each dataset in these two tables. Two p-values are also provided: (1) p-value (UIPSDR): The p-value under the t-test between UIPSDR and the best DR baseline on each dataset; (2) p-value (UIPS): The p-value under the t-test between UIPS and the best DR baseline on each dataset. From Table 7 and Table 8, we can first observe that DR cannot consistently outperform BIPS-Cap: It outperformed BIPS-Cap on the Coat and KuaiRec dataset, while achieving much worse performance on the synthetic datasets and Yahoo dataset. This is because the imputation model also plays a very important role in gradient calculation as shown in Eq. [2). Its accuracy greatly affects policy learning. When the imputation model is sufficiently accurate, for example, on the Coat dataset with only 300 actions, incorporating the DM estimator not only led to better performance of DR over IPS, but also improved performance of UIPSDR over UIPS. And in particular, in this situation UIPSDR performed better than DR with the gain being statistically significant. When the imputation model is not accurate enough, for example, on the RuaiRec dataset with a large action space but sparse reward feedback, DR is still worse than UIPS, and UIPSDR also performs worse than UIPS due to the distortion of the imputation model.
immutaali
7.5 Difference against DICE-type algorithms.
The DICE line of work 26 47 is proposed for off-policy correction in the multi-step RL setting with the environment following the Markov Decision Process (MDP) assumption. Although the DICE line of work does not require the knowledge of the logging policy, it fundamentally different from our work. Given a logged dataset D == {(Se, Gt. Fs $++1)} collected from an unknown logging policy 3 (a.lse). DICE-type algorithms propose to directly estimate the discounted stationary distribution correction Wz/D(#t. (8c a)) = d (s..as) to replace the product- off-policy correction
(s,,as)
(.)))) which suffers high variance due to the series of products. While the estimation of W*/D(Se; ar) is agnostic to the logging policy, it highly depends on two assumptions: (1) Environment follows MDP, i.c., S1+1 ~ T(s,, with T(--)) denoting the state transition function; (2) Each
weight II, a(a,)s.).
logged sample should be of a caate-action-neet -ex---tttteeee tuple (St, ae, oe S141) that contains state transition information.
18

---

Table 9: Empirical performance of DICE-S S synthetic datasets.
Algorithm
P@5
R@5
NDCGes
R@5
N
NDCGe5
BIPS-Cap
0.5515+2:"
0.1553
=5
0.603 =
0.5526e2:
0.1561#6r**
0.601661."
0,54009a
0.15
0
DICES
0.541644"
0.1520
4.5
0.158343 05550
0.601
4.54084mm"
0,1526-7e
0.5903-1
UIPS
0.5589
0
0.6095
0.357243
0.6074+2
0,5432aa
0.1534
0.5946=b
Table 10: Empirical performance of DICE-S on real-worke datasets.
Yahoo
Coat
KuaiRee
Algoestim
Pia
Res5
NOCGeS
Pors
NDCGRES
R0500
BIPS-Cap
0.280822-"
0.757
0.609958"
0.778
0.4582476
0.4399
0,770
0.0238477"
0.8788
DICESS
0.26 16
0,7010
0. 0.5627.9c
0.2686156
0.4422.6
0.426545-7
0.8842
0.0241 ame 0.8908 se
UIPS
08288822-"
0,7742a5
0.6274256
0.287733"
0.4757
0.457658."
0.9120
0.0250
09174477
We further inspected how DICE-type algorithms would work in the contextual bandit setting, which can be taken as a one-state MDP. We take DualDICE [1] as an example for illustration, and sim- ilar conclusions can be drawn for other DICE-type algorithms. We can easily derive that in the contextual bandit setting, DuaIDICE degenerates to the IPS estimator that approximates the un- known ground-truth logging policy 3 (als) with its empirical estimate from the given logged dataset D = ((5; at, I's as..a:) V E [N]], which inherits all limitations of IPS estimator, such as high variance on instances with low support in D.
More specifically, recall that DuaIDICE estimates the discounted stationary distribution correction by optimizing the following objective function (8) in (26):
min u: =:SAAACC
E (o a)² E( (x(s, a)],
with the optimizer x² z=(s,a) a) Wx ( a). In a multi-step RL setting, one cannot directly calculate the second expectation as d= (s, a) is inaccessible, thus DuaIDICE takes the change-of-variable trick
to address the above optimization problem. However, in the contextual bandit setting, let p(s) denote the state distribution, d' (s, a) ((ls) and d (P(ss) a) = (as))*(als)) The optimization problem can be rewritten as
[ Fa- (x)s)) a)²] Fanas(al [o( (ol))) [x(
min USSxA-C
Easple)
With the logged dataset D, the empirical estimate of above optimization problem is:
min =-SAACC
Σ No
Σ No. x(s,a)² 2N,
Σ x(als))(ss
where N, and N..a denote the number of logged samples with 8; S and (s; = s, a; a) respectively. This actually equivalent to the IPS estimator with N..o/N, as the estimate of 3r (als). We refer to the above estimator as DICE-S, and Table 9 and T the empirical performance of the policy learned through DICE-S real-world datasets respectively. Similar as BIPS-Cap described in Section 4 we also clip propensity scores control variance. One observe from Table 9 than BIPS- Cap in all datasets except the KuaiRec dataset. Additionally, DICE-S underperforms compared to UIPS in all datasets. This is due to the fact that although DICE-S is unbiased, it only becomes accurate with numerous logged samples, and suffers high variance when logged samples are limited, resulting in its poor performance in our experiments.
T(ass)) =(a
x² a)
the synthetic and
and Table Toble[TOtha that DICE-S performs worse
7.6 Comparison against work on direct propensity estimation.
In addition to DICE, several other works 34
propose methods to directly estimate the propensity ratio without requiring a behavior policy. These methods then use the propensity estimates to prioritize instances in the replay buffer for better TD learning. To compare its effectiveness, we also included new baseline called IPS-LFIW, which implements the approach proposed in [1] to directly estimate the propensity ratio for off- aff-policy learning.
21
The average performance and standard deviations of IPS-LFIW and UIPS three synthetic datasets with different t are reported in Table [T] Recall that smaller 7 indicates a more skewed ground- truth logging policy. The p-value under the t-test between UIPS and IPS-LFIW is also provided to
19

---

Table 11: Empirical performance of IPS-LFIW and UIPS on synthetic datasets
Algorithm
P@S
RØ5
NDCO@5
RØ5
NDCG@5
NDCG@5
IPS-LIIW
0.5542
0,1568 sde
0.6033ate
0.5472
0.154
0.3975
0.5255
0.1485ate
a.576
UIPS
0.5608=2
0.188
0.611342
0,5572:2-
0.157
0.6074:2
0.5432
0.1534
0.5946:22
p-value
2c
56
2n
2c
Je
4c"
8c
le
investigate the significance of improvements. Notably. UIPS consistently outperformed IPS-LFIV. with statistically sigmificant improvements. One major reason for the worse performance of IPS-LFIW is that it does not consider the accuracy of the estimated propensity ratio, in a direct analogy to failing handle uncertainty in the estimated logging probabilities in existing IPS-type algorithms.
7.7 Comparison against distributionally robust off-policy evaluation and learning.
Our work is fundamentally different from the line of work on distributionally robust off-policy evaluation and learning [32 17 44 This results in different objectives that guide the use of min-max optimization.
Specifically, the work in B2 deployment environments, such as user preference drift or unforeseen events during policy execution. Thus they choose to maximize the policy value (e.g., Virs(r)) in the worst environment within an uncertainty set around the training environment,
assumes unknown changes exist between their training and
max min u
(Ir)
As a result, their uncertainty set is created by introducing small perturbation to the training environment. For example, the work in [32 17 searches the worst environment Poo in the o-close perturbed environments around the training environment Po (Iq.(1) in (17):
u(a) (Pi Pı << Po
and DRz(Pil(Po) 5o).
And the work in 44 adversarially perturbs the known ground-truth logging policy to(-l)) in searching for the worst case (4) in 44)):
Tu (ala)) mo(ala)) <u(a]z) Tu (alz) S cd).
u(a:) (N max 0,2
max
In contrast, UIPS assumes the training and deployment environments stay the same, but the ground- truth logging policy is unknown. To control the high bias and high variance caused by inaccurately and small estimated logging probabilitics, UIPS explicitly models the uncertainty in the estimated logging policy by incorporating per-sample weight dz,a as discussed in Eq. 4). In order to make VUIPS(TT) (To) as accurate as possible despite the unknown ground- -trtth logging policy 3* (-I-), UIPS solves a min-max optimization problem in Eq.(8). This optimization problem seeks to find the optimal 6..a that minimizes the upper bound of the mean squared error (MSE) of Vuirs to its ground-truth value, within an uncertainty set of the unknown ground-truth logging policy (-l-))). The closed-form solution for the min-max optimization is also derived as in Theorem 3.2
Furthermore, observing that work in 44 also performs optimization over uncertainty set of the logging policy, we further adapted their method to handle the inaccuracy of the estimated logging policy, by taking To n-(---) as the estimated logging policy, i.c.. To (-I-) = (-I-). We name the adapted methods IPS-UN. Table 12 demonstrates the performance of the learned policy under IPS-UN on three synthetic datasets. The results suggest that directly applying IPS-UN to handle inaccurately estimated logging probabilities is not be feasible solution to our problem. One important reason for the worse performance of IPS-UN is that strives to optimize for the worst potential environment, which might not be the case in our experiment datatsets. On the other hand, UIPS assumes the training and deployment environments stay same and strives to identify the optimal policy with an unknown ground-truth logging policy.
7.8 Theoretical Proofs.
Proof of Proposition 2.1
20

---

Table 12: Empirical performance of IPS-UN synthetic datasets.
Alporithm
P68-5
R
NDCGes
P@8
R
NDCG@S
R65
NDCGes
BIPS-Cap 0,5515=0:"
0.1553
0.603--a-*
0
0.6016s1e"
0.5400
0.1 1529aa
=
IPS-UN 0.4099.2"
0.1152
0,99669>"
0,3911:3-1
0.1 0.1
04754:3
0,3599
1009
UIPS 0.3589.2:"
0.158549:"*
0.6005-3"
0
0.
0.607Ae5:
0.3432e3
1334.
0,3946=2
Proof. Because of the linearity of expectation, we have Ep (VEIes(TT)) -gg-
[a(ake)
and
B(a
thus:
Bias (VBIPS(TT))
En
(TT)
V(TT))
To (a(a)))
To
(a a
Es--
B(aaz)
Tana
E.
5 (a| (x)z))
Tana
To (a(a (a/ax)
(a((a())
Eg-
Tana
-1
B(alaz)
(a(ax) B(aaz)
-1 -
Ex
Twra
(13)
Since samples independently sampled from logging policy, the variance be computed as:
Varn (VrIPS(TO))
To TT(aa22)
Varg.
Tm.a
N
((aa2z)
By re-scaling, get:
To xa)( 3(((ar) lr))
N Varp (VBIPS(TO)) Varg
(14)
2
)
Te (a (x))
E,3-
Esa
Tanaa
B(alzz)
To(a|æ) (a(x))
(a)xx)
8 (a(a=)
E
E
Ma )2
m,a
3(aazz)
This completes the proof.
Proof of Theorem 3.1
Proof. We can get:
MSE (Vinps(TO)) ED (VuIps(TO) V(TO)) (V(om))))(TTT
Ep VUIPS(TO) ((TO)) ))
+ VarD (VUIPS(TO) - V(TO))
(En VUIPS(TT)) V(Ta) 2
+ Varn (VUIPS(TO))
Bias (iss(Vurps(To)) Var(Vunps(To)).
21

---

We first bound the bias term:
Bias (VU(P())S)TT)) EE
VUIPs (TO) ((TT))
Th (a [+)
Es
D Ta
V(TO)
((a(z)
(a(x))
To (aaa x))
Eg.
3(a(z))
33 (a (z)
Tmno.
Ta.o (a(a))
(alx)
Eg-
Por,a
3 (a x
(2)
To (a(z))
(
(+((ap)) B(alzz)
1)
E
T
Ez-
Oz
-1)
(al
Step (1) follows the linearity of expectation and step (2) is due to the Cauchy- Schwarz inequality. We then bound the variance term:
1 Ta(a
Var(Veirs(Ta)
Varg
Un,aTan Tana
N
3(a)zz) xx)
1
xa(x)))
To (alx))
Dn az 1)
E3
Pa.a w.
E3
N
)2
3(aa(0)
1
(a(a)))
Jo (a)22)
Eg
2² (aaa=)2
S E
N
m.a
3(a|zz)2
Combining the bound of bias and variance completes the proof.
Proof of Theorem 3.2
Proof. We first define several notations:
Th Ba,a) = AES-
( ((aal)) De.a 1)²
27 + Eg--
(a(aa)))
02
]
B[aja]2
max EBe. T(Qe,a Ba,a) denotes the maximum value of inner optimization problem.
T(pa.a)
T min T()x,a) mill,e.. max T(ox,as Px.a) denote the optimal min- max value. And H2,a arg min ((
B 2exp(- (alax), and B 2 expliUuna B(a(z))
We first find the maximum value the inner optimization problem, i.e., T (dm,a) for any fixed dn.a- And there are three cases shown in Figure 4
Case I: When Blala) dz,a 2 B T( achieves the maximum value at Ba,a B In other
words, T(dm,a) T( B when an.a B(alm)
B A(aaa) B i.e. 2' exp((>Umm)) Hnna
2' expirUmaa) then T()m,))
Case H: When Bz
ox,a
2
will be the maximum between T(δ B and T( B+ B
More specifically, when 3(alz)
Bao Bho i.e., Un,a
2δ(a(0)
7 (Hmma) T(hm,a; B
Pe.e
a Bu.."
Otherwise when ón.a
2δ(a(w)
T(Qna)) T(Qn, B
B + B
22

---

850
Poolo)
8in
82x
8in
Case
Case
Case III
Figure 4: Three cases for maximizing the inner optimization problem.
Case III: When Px.0
(ala), Ba,a
implying ((ll=)
dz.a I BBuaa T(o,,o) T(o B B
Overall, we get that:
T(o Beaa):
óa,a E (-00, 23(a(a)
T(oxa)=
(15)
T(
Bi,a) Ona E
28(0(2)) 00)
B B
Next we try to find the minimum value (d We first observe that without considering constraint Øn.a. when
B 80(olz)2 ((a
((aa=)
T(oz,:: B+,a) achieves the global minimum value. However, ot I
B(a|m)
28(a)
B
B B..
which implies when &x
B B x0) the minimum value of T(o Bi,a) is achieved at
28(alm)
20(a))) B Be.
the other hand, without considering any constraint on dx.a the global minimum value of T( BT,a) is achieved at:
A
(16)
a,a
X Bn.a B(a(ze)
+ (a(a)))
Ba,a
Thus if Φū.a S 25(a(z)
&2.a a since T( BE,a) I T( 25(a(x) B Bea)) B Be..
B Be.."
T( 23(a(w)
B a. Otherwise, when Ó Bh. Ba.a" 28(a(z) B B...
20(a(x) the minimum value of T(Qx, B B is
B B
also achieved
implying Φi.aa Bh.ttB..'
28(a(m)
Overall,
(3(a)z)
0 min
(17)
X Bna B(aaz)
+ [a(am))
B B
Let 11 = Z"
z
we can get
X
2n
0- = min
(18)
exp (->Um.a) + [(aaa]² exp exp(-7Ue.d)
exp (YUm, + exp (-7Uzaa)
23

---

Note that E [exp(- (oxp(->Usmmn) exp(>U,ux)), since 2 expp Texp(-nU.1nn)
z
En exp(fe (a'[x)) I Z exp(U
This completes the proof.
Proof of Corollary 3.3
Proof. Following the similar procedure in Theorem 3.1
can derive the mean squared error (TTa) is upper bounded as follows:
(MSE) between VIIPS (Ta) and ground-truth estimator
MSE ((BIPS(TO)) = ED (VBIPS(TT) - (TTT))
( ( B(alzr)
27
(a(a)))
-1
< E
r B" (1|2z)
E,--
Egg
B(alaz))
When 8 (a(x)) E aa B with B 2 expp(=U2a) 2 M(lla)) MSE (Virrs (TT)
2 expl (exp(>)Uaw)) ((alar) and B
can be further upper bounded follows.
For ease illustration, we A Ex ra,0
xa(aw) and (a(a))
[
-1)
To(a|z)2 B(alar) Pza
Ti 3a,a) ABz-
(Blalaa)
Paza -
E.--
Let Tips denote the upper bound of MSE
( then we can derive that
T(1, (5,)
((a(z) B B
Thips
(19)
T(1, B(alæ)
B B 2
Recall that in Theorem 3.2
show that the upper bound of MSE (VUIPs(TO)) is as follows:
T(o B
tz.a 22((a=))
TUIPS
B B
(20)
T( 28(a)))
B a 2 B Ba,
29(a)z))
Ba,
where oz is defined in Eq.
16 Next we show that Tüpps TRips
When (a(xx) <
B + BB.
we can get THIPS = T(1, B and 28(a2z)
< 1.
Ba Ba.
If 2z
28(a(()
then Turrs T(o (e.a) T( 25( (m)
B
B Bana'
B B
T( 2ā(a œ))
B
S T(1, ( Br.)). And if 2
23(a(a)
TuPs
B B
B B..+Ba..
T( B B
28(a
B+ T(1,
s.a)
When (())x)
B+ + B we can get THIP T(1, Br,a) and 23(a|=)
> 1.
B Ba.
25(a(z)
then Ttips = T( B=a) S T(1, B B=.a), since $= global
Pæ.a
B B
minimum. Otherwise when & > B. B
25(a(z)
> 1, Tüpps T(
251a x)
B =
B..a Ba,
T( 28(a æ)
B B a.
B B...
In both cases, we have Tüirs S Tirs. thus completing the proof.
24

---

Lemma 7.1. Under fixed ne xa(a(a) x)) and B(a)2r), and aza V have the following observations:
x1-1) xp²
exp(-27Ua 22mmma)) we
211
If
(o(=) B(a(z)
2n/ (exp(>Ua,a)) + exp(-xUus
Otherwise &z,a
A/ exp (-aaa)) + Bela exp( exp(->Va..)) ]
(To(ala)²
In other words, 2z,0 2nj always holds.
If Onro S To(a|=) and ma(al=) < Vd. larger Un. brings larger Vz.a0
B(ak))
Ba.a
Otherwise 2z,a decreases as Un.a increases.
Proof. The following inequality validates the first observation:
21 exp (7U2,0) exp (->U
$ exp (~>Uma) + Ba(a eUU(
For the second and third observations, anaa (ala) we can have:
Let L(u) 2/2 3exp(-nu)
B[a[m)² exp(-ru))
A Vul(u) = - exp( (u) + 11 ( x)2
exp(yu)
[a)
To make VnC(u) 2 0, we need 2 log (x ), 2i.n will decrease Un. increases; otherwise as Un. increases, &z also log ( increases.
(X ())((aa)
This implies when Un. >
More specifically, when Czz,a
[a(alx) 3(a/m)
we have:
1 U2. S y
VA (
Ta(a(x)
To(a|æ) VA ((aax)
log
V
exp(-UUx.a).
B
7
In other words, for these samples, higher uncertainty implies smaller value of T/8, and UIPS tends to boost such safe sample with higher &".a--
In other cases, o% decreases Un.a increases. This completes the proof.
7.9 Convergence Analysis
Next we provide the convergence analysis of policy improvement under UIPS. Definition 7.2. A function f Rdd L-smooth when |/V [xx(() vf(w)l2 < L||: - u/12. for
all x. Rd
We first state and prove general result, which serves as the basis to complete our convergence analysis of policy improvement under UIPS. The proof special case of convergence proof of stochastic gradient descent with biased gradients in [3]. Suppose we have differentiable function f: IRd R. which L-smooth, and attains a finite minimum value f == minzeR fz)
Suppose we cannot directly assess the gradient fx(). Instead we can only assess a noisy but unbiased gradient (xx) E Rd at the given x of the function f(x).
Let b(z) f(()) fxx)) denote the difference between Vf(x) and Vf(x), and 6(x) = [(x)
V fx(x) denote the noise in gradients. We assume that:
[[(()]] < [x)]] and E[((2)) 0 and |[| < ME]IV + (21)
where the constants ep and M satisfy 4 < and M 2 0 respectively. When running stochastic gradient descent algorithms, i.c. T++1 = 2g ( ). we have the following guarantee on the convergence of to approximate stationary point of f.
25

---

Theorem 7.3. Suppose f(-) is differentiable and L-smooth, and the assessed approximate gradient
meets the conditions in Eq. (21) with parameters (Øk (Ps) at iteration k. Denote maxx maxk Ok and fmax max; lpk- Set the stepsizes {mx} to ak minf (M+1)L: 1/ v K)), after K
iterations, the stochastic gradient descent satisfies:
-1( [[V <
2(1(21) 12) max
+ L+ (1-9max) vK
K(1 pmax
Proof.
With 4/ S (M+IJI we have:
f(1441) S [(()) (zx) 2x+1 mR) + L ak+1 xull
(22)
=f(x)) - N V f (Tx) ((xx)) + Life
2 [[xx2)
L 11(xx) + b(xx) + (2(x2)11
= =f(x)) n ( (Tx) 6(z)) + b(xx)) + vx((x))) +
2
By taking expectations on both side, we have:
L
S ||C
V
BB|l ((x)) + b(Tw) + V((x)))
2
(1)
_ [[](+x)] // (m)
LTf
(B]
2
LAT
< (B/
((M + [
2
2 B[S(+x)] Thk (--2((/ (xxxx)) (b(x)) v[(xa))]]
L o%
2
Lafe
s BIS((x)] + ?e E[(-IV\/(>x) [b(x)]11]]
2 o
& B[S(+N))
+ The (px /) + L o% 2
2
where the inequality labeled as (1) is due to B]](=]] = 0, incquality labeled as (2) is due to Th I (as+1)z. and inequality labeled as (3) is due to [lb(xx))] S VxIlV
By summing over iterations & = 1,2, K and re-arranging the terms, we obtain:
1 Σ (1 PP E < f(z)) E[f(xx+1)]
L
Σ no
2
2
K
S f(1)) f +
2
where the last inequality follows from f(*x+1) 2 f Since min (M+1)T. omax VK J. Vk
1. ..... K, obtain:
K
(1 Panas)) 17
2(())))))))))()))-)))))))) + LKn max
Dividing both sides of the above inequality by Kmp (1 (max)), we obtain the following,
2(f(z1) - 1*) LK m 2 max
Kml (1 )max))
2(f(21) - -() max L, Fmax VKJ } + 2 mnax VK
1
K(1 - )maxx)
( (x1) - -8²) + [+ 2(((z1) pr)
Tmax
K(1 Pmax)
(1 pmax)
VK
26

---

Given this general result, we can now prove Theorem 3.4 by showing that the gradient in UIPS meets the requirements in Theorem 7.3
Proof of Theorem 3.4
Proof. UIPS aims to maximize the expected return (TT)). Therefore, we can utilize Theorem 7.3 by setting f = = Since f max and the expected reward is always non-negative, follows that f(11) f mmax.
We first introduce some additional notations. Let p (2. a) =o(a|=)
("(a denote the propensity score
under ground-truth logging policy, and )o(2z ma(a)
3(a/=) Pz.a represet the propensity score of
UIPS. Recall that 2 is derived through solving the optimization problem in Eq 8 Let ga(2,
(aa()) The true off-policy policy gradient is computed as follows:
00
VV(T))
Eg [p"rgø],
For UIPS, the approximate policy gradient in each batch with batch size as B is:
B
VUMPS(TTO) B
perago
==1
which is an unbiased estimate of:
VCCPs((TO) = (prgg]
To utilize Theorem 7.3
we set V = (VT)), Vj = V (Vurs((Ta) and = (TOIPS(TT). We
will now demonstrate that the assumptions in Eq. 21 can be satisfied.
Let se max
(a..)) (2,0)
We first have:
[|b(0]] VUIPs((T)) - VV(T))]
P
||ا [(p p² )rgelll = |[ 1or -1)rgoll
s u |. 10 rrllll
(23)
And next we show that 00 1.
{
po(xx. a) (2)
-1 max
(alx))
Pi.a -1 -11
Pa = max
(24)
B(alx)
Recall from Eq.
17 in proof of Theorem 3.2 we have
2.((a(z))
2n min
B B(alm)
xa(a|=)² B(ala)
B Br.
where B Bea-" 2exp(-xUa.a) M (r), and B 2expinUnal
(alar). Thus we have:
3d (alx)
2
Sn min
(25)
B(alx))
B (ala)
xalal=)²
B
B=
(a(aa)
(=(o)
B xe)
Since B+ 2 8d (a/zz), thus 0 <
(a(a)) B(a x)
2, implying 0 Po 1.
Also, since ViVIES (To) is unbiased estimate of V VUIPS(TT), have:
[()) E
VVCIPS( ((VUSST(TT)
0
(26)
27

---

Finally, we have the following.
27
- B[]b(0)11 - | (T) - (VOIPs(TT)) |12
E
(peragh - E3- (orgbrrgl))
B
==1
B
27
B
$ B
E
Σ
liárg - Eg (prgell]
S
E
li - Eg [prgol1?
B
< E3 Illèrgo Es. Jørgo] [1
Eg. [llèrgo [| ||E [ōrgø]]
$ 33 ||| proe [|
G
(27)
where the equality labeled as (1) due to E E| E11 1 Hence, by applying Theorem
we have:
K
2LV max
2V
Giax V V VK
(To, 2
+
1. +
(28)
K(1 maxx
(1 m
28


Reviews:
[{"review_id": "6HDMcr97Oy", "reviewer": "Reviewer_ha2F", "summary": "This paper proposes UIPS, a method that models the uncertainty of the estimated logging policy to improve off-policy learning. It assigns weights to each observation instance instead of simply dropping those with high uncertainty. The paper deduces the optimal form of weights from minimizing the upper bound of the resulting estimator’s MSE. Then it gets the improved policy by a two-step iterative optimization. This method is evaluated on both synthetic data and three real-world datasets in which UIPS outperforms multiple baselines.", "questions": "1. How many iterations and how much time does the algorithm run in the evaluation? Does the result verify Theorem 3.4?\n2. For Figure 1, the conclusion \"items with lower frequencies in the logged dataset have lower estimated logging probabilities\" is not a universal trend but only applies for frequency less than 7. How do you explain this observation, and does this affect your other results?", "limitations": "The authors are upfront about their limitations and listed future directions to address them.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper addresses an important problem in policy optimization and proposes an innovative way to handle the uncertainty in the logged data. It derives a closed-form solution for the upper bound of MSE and proves the convergence of the method. It also conducts extensive evaluation on synthetic and real-world dataset to demonstrate the effectiveness of UIPS.", "weaknesses": "1. For both synthetic and real-world data, although UIPS achieves the best results, it does not outperform the second-best method by a significant extent. It's not clear how this method will be useful in application.\n2. The paper lacks a more detailed study and comparison with existing work on handling uncertainty. More explanation is needed on why UIPS is better compared to other methods.\n3.  Some deduction is not clear. For example, in-between steps are needed to show the \"log trick\" used in formula (2). The figure illustration is not very clear either. For example, it's confusing to use ``Log(item freq)\" on the X-axis. In Tables 3 and 4, the metrics are not very clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Reply to  Reviewer ha2F\n\nWe appreciate the reviewer's positive feedback, insightful questions, and suggestions for improving the paper. We will incorporate the suggested revisions, including providing a detailed derivation step for the 'log trick' and offering further explanations on the metrics used.\n\n>[Q1] \"Performance difference to the best baseline\".\n\nPlease find our answer to CQ3 in the general response to all reviewers. \n\n>[Q2] \"The paper lacks a more detailed study and comparison with existing work on handling uncertainty. \"\n\nTo the best of our knowledge, our work is the first to explicitly model uncertainty in the estimated logging policy for improved off-policy learning. We have noticed that some work on offline RL also utilizes uncertainties to address the OOD issues or extrapolating errors. But the main idea of those studies is to penalize states/state-action pairs with high uncertainties, which is fundamentally different from the principle in UIPS. Please also refer to our answer in [CQ1].\n\nTo understand the impact of these different choices in leveraging uncertainty, we introduced the baseline UIPS-P, which always penalizes samples with high uncertainty, and UIPS-O, which always boosts samples with high uncertainty. The clearly worse performance of UIPS-P and UIPS-O suggests that blindly reweighting through uncertainties is not effective, regardless of the scale of propensity scores.\n\nIf the reviewer is aware of any other relevant work that leverages the uncertainty of estimated logging policy for off-policy learning, please let us know. We are more than happy to discuss this further. \n\n\n> [Q3] \" Use Log(item freq)\" on the X-axis in Figure 1.\"\n\nThe range of values for X is immensely broad in the real-world KuaiRec dataset, spanning multiple orders of magnitude. Consequently, we employ a logarithmic scale to ensure the readability of the figure.\n\n> [Q4] In Tables 3 and 4, the metrics are not very clear.\n\nLet us first briefly recap the motivation behind the experiments in Table 3. UIPS is divided into two steps: \n\n- Derive the optimal instance weight $\\phi_{\\boldsymbol{x},a}$, so that $\\hat{V}\\_{\\rm UIPS}(\\pi_{\\boldsymbol{\\vartheta}})$ in Eq. (4) approaches the ground-truth $V(\\pi_{\\boldsymbol{\\vartheta}})$ as closely as possible.\n- Update $\\pi_{\\boldsymbol{\\vartheta}}$ by maximizing $\\hat{V}\\_{\\rm UIPS}(\\pi_{\\boldsymbol{\\vartheta}})$.\n\nThus, Table 3 evaluates the mean square error (MSE) of $\\hat{V}_{{\\rm UIPS}}$ and the estimators used in the related baselines in approximating the ground-truth $V$. A smaller MSE indicates a higher accuracy. The results reveal that incorporating uncertainty makes the UIPS estimator the most accurate.\n\nIn Table 4,  we employed widely adopted offline metrics in recommendation algorithms, namely Recall@K, NDCG@K, and Precision@K, to evaluate the learnt policy $\\pi_{\\vartheta}$ for recommendation. Their definitions are described in line 233-235, with provided references.\nDue to space constraints, we are unable to present the detailed definitions here. However, we are more than willing to discuss further details during the discussion stage if the reviewer expresses interest.\n\n>[Q5]\"How many iterations and how much time does the algorithm run in the evaluation? Does the result verify Theorem 3.4?\"\n\nThe objective of Theorem 3.4 is to demonstrate the optimality of the learned policy, rather than its convergence rate. The theorem suggests that even without direct access to the true policy gradient (due to the unknown ground-truth logging policy), UIPS converges to a stationary point where the true policy gradient approaches zero.\n\nThe computational complexity of UIPS is discussed in Section 7.1 in appendix.  Notably, both the estimated logging policy and its associated uncertainty can be pre-computed, resulting in no additional computational cost during the off-policy learning process of UIPS. Empirically, we also found that UIPS achieved the optimal performance using approximately the same number of epochs as in the BIPS-Cap baseline.\n\n>[Q6] \"For Figure 1, the conclusion \"items with lower frequencies in the logged dataset have lower estimated logging probabilities\" is not a universal trend but only applies for frequency less than 7. How do you explain this observation, and does this affect your other results?\"\n\nProposition 2.1 in the paper suggests that samples with either **high estimation uncertainty** or **small estimated probability** tend to introduce large errors in off-policy learning.  And Figure 1 suggests that these two factors are usually accompanied, exacerbating such errors. \nHowever, we should also emphasize that UIPS does not have any threshold to define what is small in the estimated logging probability, or assume any monotonic relation among a sample’s estimation uncertainty, estimated logging probability, and observation frequency. The estimated uncertainty is leveraged in Eq (8) for policy learning, and a particular way for uncertainty estimation provided in line 162 to 170. Hence, the reviewer’s observation in Figure 1 does NOT affect the application or performance of UIPS. \n\nOn the other hand, there could be many reasons why we did not see a universal trend in Figure 1. For example, in the model's learnt embedding space, some lower frequency items might be similar to some high frequency ones and therefore their estimated logging probabilities are not smaller than those with higher observation frequencies (e.g., around log frequency 7). But again, as long as we can quantify the associated estimation uncertainty, the proposed UIPS solution can be applied. \n\n"}, {"review_id": "vioqi1P4xK", "reviewer": "Reviewer_QiPS", "summary": "This paper proposes an Uncertainty-aware Inverse Propensity Score estimator (UIPS) for off-policy learning, taking into account the uncertainty in the estimated logging policy. The authors demonstrate that the commonly used method of estimating the logging policy can lead to biased estimators, particularly for samples with small estimated logging probabilities. UIPS addresses this issue by reweighting the propensity scores based on the uncertainty of the estimated logging policy. The paper provides a theoretical analysis of the convergence properties of UIPS and presents experimental results on synthetic and real-world recommendation datasets, comparing against state-of-the-art baselines.", "questions": "1.How is this paper related to behavior-agnostic methods [1,2,5]? With a GAN-like estimator, these methods no longer reconstruct all those behavior policies. They may also be regarded as baselines to compare with.\n2.Why are the probabilities $\\beta^*(a|x)$ not recorded in the data? With stochastic logging policies, it is easy to store probabilities together with state and actions when generating data. With deterministic logging policies, a common practice is to sample actions from a Gaussian distribution, with policy output as mean and a certain standard deviation. The action probability will also be available.\n3.Why do UIPS-O and UIPS-P lead to poor performance?\n\n[5] Nachum, Ofir, et al. \"Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections.\" Advances in neural information processing systems 32 (2019).", "limitations": "The usage of off-policy correction and uncertainty-based reweighting is limited to policy-based techniques based on the REINFORCE trick. Such techniques can have higher variance than value-based techniques such as TD3 and SAC, and may lead to unstable training.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "● The paper addresses an important problem in off-policy learning and proposes a novel method, UIPS, to improve the quality of the discovered policy.\n● The authors provide a comprehensive theoretical analysis of UIPS, including a convergence guarantee.\n● The experimental results demonstrate the effectiveness of UIPS compared to some baselines on both synthetic and real-world datasets.", "weaknesses": "● There remain some issues unsolved in the paper, such as the availability of the logging policy. See the questions for details.\n● There are some related works that are not mentioned in this paper. In off-policy RL, several papers work on behavior-agnostic instance reweighting [1,2]. They compute the prioritization weight without the need of obtaining a behavior policy. There are also papers that discuss the importance ratio term when applying RL to recommendation systems [3,4].\n● Introducing another neural network to estimate $\\beta^*$ will increase the system complexity and the computational cost during training and testing. This may hinder the practical application of the algorithm.\n● The synthetic dataset and the offline evaluation can give biased evaluation results of the algorithms.\n\n[1] Sinha, Samarth, et al. \"Experience replay with likelihood-free importance weights.\" Learning for Dynamics and Control Conference. PMLR, 2022.\n[2] Liu, Xu-Hui, et al. \"Regret minimization experience replay in off-policy reinforcement learning.\" Advances in Neural Information Processing Systems 34 (2021).\n[3] Cai, Qingpeng, et al. \"Reinforcing User Retention in a Billion Scale Short Video Recommender System.\" arXiv preprint arXiv:2302.01724 (2023).\n[4] Chen, Minmin, et al. \"Off-policy actor-critic for recommender systems.\" Proceedings of the 16th ACM Conference on Recommender Systems. 2022.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer QiPS\nWe thank the reviewer for valuable suggestions provided, which help clarify important arguments and enhance the overall quality of the paper.\n\n> [Q1] \"Why are the probabilities not recorded in the data?\"  \n\nThe absence of ground-truth logging probabilities and taking the estimated logging policy for off-policy learning have been a long-standing assumption in the off-policy learning literature [6-8]. There are several reasons that hinder the recording of logging probabilities.\n\n First, in many situations, such as the healthcare domain discussed in [6] or industrial recommender systems as discussed in [7], access to the ground-truth logging policy is not feasible.\n\nAnother important reason is due to legacy issues, i.e., the probabilities were not logged when collecting data (e.g., space efficiency was prioritized when designing the users' interaction logging system). However, even if one is willing to bear the high costs in time and resources to re-collect data with “everything” logged, relying solely on newly-collected data provides only a partial depiction of users' preferences afterwards. Hence, in order to gain a clearer understanding of users, leveraging their historical interaction logs becomes crucial, necessitating the estimation of logging probabilities.\n\nMoreover, in certain cases, there may be security concerns where individuals/companies are unwilling to disclose the logging policy to prevent potential adversarial attacks, while these public resources may hold significant value. As a result, estimating the logging policy is still an important and necessary effort in practice. \n\n[6] Raghu et al. \"Behaviour policy estimation in off-policy policy evaluation: Calibration matters.\" arxiv 2018\n\n[7] Chen et al. Top-k off-policy correction for a REINFORCE recommender system. WSDM 2019.\n\n[8] Strehl et al. Learning from logged implicit exploration data. NeurIPS 2010.\n\n\n> [Q2]\"Comparison with the behavior-agnostic methods[1,2]\". \n\nThe main goal of work in [1,2] is to prioritize instances in the replay buffer for better TD learning, rather than accounting for uncertainty in the estimated logging policy for improved off-policy learning. However, we do acknowledge that their proposed solution for directly estimating the propensity ratio has the potential benefit of avoiding estimating the logging policy. To compare its effectiveness, we also included a new baseline called IPS-LFIW, which implements the approach proposed in [1] to directly estimate the propensity ratio for off-policy learning.\n\nThe average performance and standard deviations of  IPS-LFIW and UIPS on three synthetic datasets are reported in **Table 1 in the PDF attached in the global response**.\n\nNotably, UIPS consistently outperformed IPS-LFIW with statistically significant improvements.  \nOne major reason for the worse performance of IPS-LFIW is that it does not consider the accuracy of the estimated propensity ratio, in a direct analogy to failing to handle uncertainty in the estimated logging probabilities in existing IPS-type algorithms.\n\nFurthermore, another advantage of UIPS over the work in [1,2] is that UIPS provides a theoretical guarantee regarding the performance of the learnt policy (Theorem 3.4). In contrast, the behavior-agnostic methods in [1,2] do not offer such a guarantee.\n\n \n> [Q3] \"Difference between UIPS and the DICE line of work.\"\n\nThe difference has been discussed in Section 7.5 in appendix. To briefly recap, we demonstrated that in the contextual bandit setting, DualDICE degenerates to the IPS estimator that approximates the unknown ground-truth logging policy with its empirical estimate from the given logged dataset.\n\nDenoting the adapted algorithm from DualDICE as DICE-S, we compared its performance against UIPS in Table 9 and 10 in appendix. We found DICE-S underperformed UIPS significantly in all datasets. \n\n> [Q4] \"The relevant papers on RL for recommendation systems [3-4].\"\n\nWe will incorporate the discussion of them in the related work section. However, it is worth noting that none of the aforementioned works attempt to account for the inaccuracy of the estimated logging policy. In particular, Chen et al. [4] directly used the estimated logging probabilities as the ground-truth in their IPS estimator.\n\n> [Q5] \"Introducing another neural network to estimate $\\beta^*$ will increase the system complexity and the computational cost during training and testing.\"\n\nWe thank the reviewer for pointing out the place that unfortunately caused misunderstanding. \nFor UIPS, both the estimated logging policy and its associated uncertainty can be pre-computed. The uncertainty can be directly estimated using the same model employed for estimating the logging policy (line 162 to 170), with no requirement for an additional neural network.\n \nDuring training, with the precomputed logging probabilities and uncertainties, UIPS calculates the per-sample weight in O(1) time, and thus it incurs no additional computational cost and does not require an extra network. The evaluation is performed on the learnt policy. Further details regarding the computational cost can be found in Section 7.1.\n\n> [Q6] \"The synthetic dataset and the offline evaluation can give biased evaluation results of the algorithms.\"\n\nWhile training under non-uniform training datasets (collected under a specific logging policy), all algorithms are evaluated on the **unbiased test dataset**, either from randomized controlled trials (Yahoo & Coat) or a full-observed interaction dataset (KuaiRec, synthetic datasets). \nConsequently, all algorithms are evaluated in an unbiased manner. And such evaluation setting is one of the referred procedures in off-policy learning. \n\nIf the reviewer has any further concerns, please let us know. We are more than willing to engage in further discussion.\n\n\n> [Q6] \"Why do UIPS-O and UIPS-P lead to poor performance?\"\n\nPlease find our answer to CQ1 in the general response to all reviewers. \n"}, {"review_id": "dIrVLAKPS3", "reviewer": "Reviewer_YnY8", "summary": "The paper considers a scenario in off-policy evaluation where we don't have access to the action probabilities of the logging policy, which we need to compute the propensities in IPS. Prior work would estimate these probabilities from data, but would ignore the uncertainties associated with these estimates. In this work the authors propose to re-weight the propensities based on thess uncertainties. The exact form of the weights is derived by minimizing an upper bound on the MSE. The resulting method consistently beats SOTA baselines on both toy and real datasets.", "questions": "How sensitive is the method to the uncertainty estimation approach? Does something simple like MC-Dropout produce similar results?\n\nAlso see a few questions in the weaknesses section.", "limitations": "Little discussion of limitations: e.g. what about additional cost due to having to estimate uncertainties? Limited societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "A novel IPS variant that is grounded in and backed by theory (i.e. is derived by minimizing the MSE of the estimator), and is designed to solve a concrete problem in existing methods. \n\nSolid experimental methodology, sufficient details on the experimental setup to enable reproducibility.\n\nStrong results: the proposed method beats a broad list of SOTA baselines on both toy and real datasets.", "weaknesses": "I have doubts re. the importance of the problem that the method is solving: we can simply log the propensities, right? How common is it in practice that these propensities are not available?\n\nAt the same time, I see that in some experiments the method improves upon using GT propensities. This would be a good selling point of the method, but it goes against the initial motivation. How can a method that takes uncertainty into account be better than having _no_ uncertainty? This warrants more discussion in the paper, and makes me wonder if there are alternative explanations to why the method works.\n\nIn general, I've found the manuscript to be rather dense and hard to read in places. I would've liked to see more intuition and/or pedagogical examples to understand what the method does exactly. E.g. on line 158: \"UIPS assigns them with an increasing weight [..] as uncertainty increases\" -- why does it make sense?\n\nThe quality of the write-up could be improved: a few grammar mistakes, figure captions could be more informative, some opaque references to prior work could be expanded to make the paper more self-contained. \n\nThe related work could be stronger: lines 301 - 320 largely repeat the introduction. What about other methods in on-policy/off-policy that exploit the uncertainties? UCB in bandits, for example?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to  Reviewer YnY8\n\nWe thank the reviewer for the positive comments on our work and valuable suggestions. We have clarified several important arguments as outlined below. And we will diligently address other suggestions by further polishing our paper, making the figure captions more informative, and enhancing the references accordingly.\n\n> [Q1] \" How common is it in practice that these logging propensities are not available?\"\n\nThe absence of ground-truth logging probabilities and taking the estimated logging policy for off-policy learning has been a long-standing practice in the off-policy learning literature [1-3]. \nThere are several reasons that hinder the recording of logging probabilities.\n\nFirst, in some situations, such as the healthcare domain discussed in [1] or industrial recommender systems as discussed in [2], access to the ground-truth logging policy is not feasible.\n\nAnother important reason is due to legacy issues, i.e., the probabilities were not logged when collecting data (e.g., space efficiency was prioritized when designing the logging system). However, even if one is willing to bear the high costs in time and resources to re-collect data with “everything” logged, relying solely on newly-collected data provides only a partial depiction of users' preferences afterwards. Hence, in order to gain a clearer understanding of users, leveraging their historical interaction logs becomes crucial, necessitating the estimation of logging probabilities.\n\nMoreover, in certain cases, there may be security concerns where individuals/companies are unwilling to disclose the logging policy to prevent potential adversarial attacks, while these public resources may hold significant value. As a result, estimating the logging policy is still an important and necessary effort in practice. \n\n[1] Raghu et al. \"Behaviour policy estimation in off-policy policy evaluation: Calibration matters.\" arxiv 2018\n\n[2] Chen et al. Top-k off-policy correction for a REINFORCE recommender system. WSDM 2019.\n\n[3] Strehl et al. Learning from logged implicit exploration data. NeurIPS 2010.\n\n\n\n> [Q2] \"Why do UIPS improve upon using GT propensities ?\"\n\nPlease find our answer to CQ2 in the general response to all reviewers. \n\n> [Q3] \"More intuition and/or pedagogical examples to understand what UIPS does exactly.\"\n\nPlease find our answer to CQ1 in the general response to all reviewers. We will make further revisions to enhance the readability of the corresponding section.\n\n\n> [Q4] \" What about other methods in on-policy/off-policy that exploit the uncertainties? UCB in bandits, for example?\"\n\nIn the context of on-policy RL/bandits, the use of uncertainty aims to strike a balance between exploration and exploitation by adopting an optimistic approach (i.e., UCB in bandits). On the other hand, most research on off-policy RL/bandits tends to be more conservative, employing techniques such as Lower Confidence Bounds (LCB) in bandits or penalizing samples with high uncertainty. But those principles are fundamentally different from what we developed in UIPS, which directly minimize the mean square error of off-policy evaluation. The closed-form solution of the resulting per-instance weight in UIPS reflects how uncertainty contributes to the policy evaluation error.  \n\nOur UIPS-O and UIPS-P baselines leverage uncertainties using the two aforementioned general principles respectively. However, empirical findings indicate that blindly penalizing or boosting instances based on uncertainty leads to inferior performance compared to UIPS, as they do not directly suggest how uncertainty in the estimated logging probability is related to policy evaluation.\n\nWe thank the reviewer once again for your suggestion regarding the related work. We will incorporate the aforementioned discussion to enhance the related work section.\n\n> [Q5] \"How sensitive is the method to the uncertainty estimation approach? Does something simple like MC-Dropout produce similar results?\"\n\nOur framework is agnostic to the uncertainty estimation methods, as long as the estimated uncertainty is reliable. In the paper, we conducted experiments using the uncertainty estimation framework described in [4] due to its computational efficiency and theoretical soundness. But alternative methods for estimating uncertainties can be readily incorporated into our framework. Inspecting the impact of different uncertainty estimation methods on the quality of the policy evaluation as well as the resulting policy optimization in UIPS is an important and interesting future direction.\n\n[4] Xu P, Wen Z, Zhao H, et al. Neural Contextual Bandits with Deep Representation and Shallow Exploration. ICLR 2021.\n\n\n> [Q6] \"what about additional cost due to having to estimate uncertainties?\"\n\nThe computational complexity of UIPS is discussed in Section 7.1 in appendix. Given the logged dataset containing $N$ samples, $A$ actions and latent dimension $d$, the computational cost of precomputing uncertainties of the logging probabilities is  $O(Nd^2 + d^3)$, where $O(d^3)$ is for matrix inverse and $O(Nd^2)$ is for calculating uncertainties in samples. \n\nNote that calculating logging probability for each sample, which is essential for both UIPS and all IPS-type algorithms, takes $O(NAd)$ time. But considering that the dimension $d$ is typically much smaller than the action size $A$ and sample size $N$, and with precomputed logging probabilities and uncertainties, UIPS can efficiently calculate the sample weight in $O(1)$ time during off-policy learning. Therefore,  we can conclude that  **UIPS does not introduce significant computational overhead compared to the original IPS**.\n\n"}, {"review_id": "y6OtA0QGBf", "reviewer": "Reviewer_19wU", "summary": "This paper delves into the issue of off-policy learning, the objective of which is to devise a new action selection policy based solely on the logged feedback derived from a logging policy. The paper pays particular attention to scenarios in which the logging policy remains unidentified and its estimation proves challenging. Under these conditions, common estimators, like IPS, may lose beneficial attributes such as unbiasedness. To address this complication, the paper introduces a new off-policy learning (OPL) approach called Uncertainty-aware off-policy learning. This new framework aims to optimize the uncertainty-aware objective function by employing a novel weighting scheme that is tuned by minimizing an upper bound of MSE in estimation. A local convergence based on the proposed method is also shown. Experimental results indicate that this proposed framework outperforms a range of benchmark methods on both semi-synthetic and real-world recommendation datasets.", "questions": "- How do baseline methods perform in the experiments when they are combined with a calibrated logging policy estimator? Some additional results about this would be useful.\n\n\n- Could you provide the results relative to the performance of the (true) logging policy? This enables us to see how much improvements the methods bring compared to the logging policy.\n\n\n- When does UIPS become really crucial? That is, are there any situations where UIPS performs well while all other methods do not work satisfactory. In the current experiments, the second-best methods perform very similarly to UIPS in all datasets and metrics. Moreover, CE performs reasonably and stably for a range of metrics and datasets, which makes it a really good choice in practice indeed.\n", "limitations": "The paper touches on the tightness of the bound as a limitation and future work in the last section.\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper addresses the practically relevant problem of dealing with uncertainty in logging policy estimation in off-policy learning.\n\n\n- The paper proposes a reasonable and conceptually straightforward method to handle the issue of uncertain logging policies, providing theoretical guarantees regarding estimation and local convergence.\n\n\n- The paper presents comprehensive experiments, not just basic performance comparisons, but also experiments on off-policy evaluation (OPE) and critical hyperparameters (some of which are included in the appendix).\n", "weaknesses": "- Given that several papers already exist on the topic of distributionally robust off-policy learning (OPL), as discussed in the paper, the formulation of a problem addressing the uncertainty of logging policies may not be groundbreaking, even though I understand that their motivations differ somewhat.\n\n\n- In the experiments, the issue might also be tackled by simply applying calibration during the estimation of the logging policy, as seen in the following paper:\n\nAniruddh Raghu, Omer Gottesman, Yao Liu, Matthieu Komorowski, Aldo Faisal, Finale Doshi-Velez, and Emma Brunskill. Behaviour Policy Estimation in Off-Policy Policy Evaluation: Calibration Matters. https://arxiv.org/pdf/1807.01066.pdf \n\n\n- In most of the experiments, CE performs quite well and is not substantially outperformed by UIPS. Therefore, considering the current experiment results, I may not use UIPS in practice and would rather rely on CE, which is much easier to implement (there is no need to estimate the logging policy when using CE), and does not require the tuning of additional hyperparameters as with UIPS.\n\n\n- Related to the previous point, in most experiments, the second-best methods for each metric and dataset perform very similarly to UIPS. I am not sure how essential it truly is to address uncertainty in logging policy estimation. I understand that the results are statistically significant, but results can be deemed significant even with a slight performance difference if the sample size is sufficient. In this context, my focus is on the performance difference.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Reply to  Reviewer 19wU\n\nWe thank the reviewer for pointing out the related work on calibration, and for posing valuable questions that have assisted in clarifying crucial arguments. \n\n\n> [Q1] \"Difference between UIPS and the line work of distributionally robust off-policy learning (OPL).\"\n\nIn Section 7.6, we highlighted the distinct differences between UIPS and the line of work on distributionally robust RL in terms of the source of uncertainty, the motivation for utilizing uncertainty, and the techniques employed to handle uncertainties. Furthermore, the experiments conducted in Section 7.6 demonstrate that directly adapting methods from distributionally robust OPL to handle inaccurately estimated logging probabilities leads to bad performance, thus it is not a preferred and suited solution.\n\n> [Q2] \"Comparison to Calibration Methods.\"\n\nThe paper [1] found that the accuracy of off-policy evaluation (OPE) strongly depends on the calibration of the estimated logging probabilities. The research specifically highlights that AppoxKNN exhibits the lowest calibration error, leading to the most accurate OPE. However, the paper does not explore how to calibrate the estimated logging policy models for better OPE.\n\nFollowing the reviewer’s suggestion, we include two new baselines: 1) ApproxKNN following [1]; 2) IPS-C-TS: IPS that combined with calibrated logging probabilities via temperature scaling [1]. We adopted temperature scaling for calibration for two reasons: 1) The logging policy is inherently a probability distribution over actions, and 2) It has been widely acknowledged as one of the most effective calibration methods in multiple classification settings. \n\nThe average performance and standard deviations of ApproxKNN, IPS-C-TS and UIPS on both real-world and synthetic datasets are reported in **Table 2 and 3 in the PDF attached in the global response**.\n\nWe found that both ApproxKNN and IPS-C-TS generally achieved better performance than BIPS-Cap, implying the effectiveness of calibration. However, UIPS still consistently outperformed both ApproxKNN and IPS-C-TS, particularly on real-world datasets.\n\nThe main reason is that calibration primarily focuses on adjusting the predicted probabilities to ensure **on average** the model's predictions are reliable and accurate. In contrast, UIPS specifically handles the impact from each individual sample in policy learning. Moreover, a perfectly calibrated model is clearly beneficial for IPS, but a perfect model for IPS is not necessarily calibrated: a scaled version of ground-truth logging model is well-suited for IPS, but terrible in calibration. Hence, small calibration error could lead to big IPS error and therefore a poorly learnt policy.\n\n[1] Raghu A, Gottesman O, Liu Y, et al. Behaviour Policy Estimation in Off-Policy Policy Evaluation: Calibration Matters[J].\n[2] Guo C, Pleiss G, Sun Y, et al. On calibration of modern neural networks. ICML 2017.\n\n\n> [Q3] \"CE performs quite well and is not substantially outperformed by UIPS.  \"\n\nWe first want to clarify that UIPS consistently exhibits strong performance over CE, particularly on the real-world datasets. The following table shows the relative improvement ratio of UIPS over CE on three real-world datasets regarding Recall@K, Precison@K and NDCG@K. \n\n|                                  | Yahoo | Coat | KuaiRec |\n|----------------------------------|-------|------|---------|\n| improvement ratio on Recall@K    | 1.7%  | 2.8% | 3.6%    |\n| improvement ratio on Precison@K | 1.9%  | 3.0% | 4.2%    |\n| improvement ratio on NDCG@K     | 3.3%  | 1.0% | 4.1%    |\n|                                  |       |      |         |\n\nWe can observe that on KuaiRec dataset, characterized by a large action space and sparse interactions (which is common in real-world scenarios), UIPS achieves approximately a 4% improvement over CE in terms of Recall@K, NDCG@K, and Precision@K metrics. \n\nAs shown by recent literature [2,3,4]  referred in answer to CQ3, an improvement at this scale is regarded as being significant for our adopted metrics. In particular, an improvement ratio of around 2% in these offline metrics can lead to enhanced online performance for algorithms, resulting in increased GMV /transactions or longer user staytime.\n\n> [Q4] \"Performance difference to the best baseline.\"\n\nPlease find our answer to CQ3 in general response to all reviewers. \n\n\n> [Q5] \"Performance of the (true) logging policy.\"\n\nPlease find our answer to CQ2 in the general response to all reviewers. \n\n\n> [Q6] \"When does UIPS become really crucial? That is, are there any situations where UIPS performs well while all other methods do not work satisfactory.\"\n\nThank the reviewer for posing this intriguing question. Empirically, Table 1 and Table 4 demonstrate that UIPS offers distinct advantages in scenarios where the ground-truth logging policy is skewed (indicated by smaller $\\tau$ values) or when dealing with larger action spaces and sparse interactions (such as the KuaiRec dataset). This is primarily due to the fact that in such scenarios, the accurate estimation of logging probabilities becomes challenging, amplifying the adverse impact of inaccurate logging policies on overall performance. Considering that in most real-world scenarios, the logging policy tends to be skewed, accompanied by large action spaces and sparse interactions, UIPS holds practical applicability and relevance.\n\nAbove empirical observation is also supported by theoretical findings presented in Theorem 3.4.\nThis theorem suggests that with small and inaccurate estimated logging probabilities,  particularly when $\\beta^*(a|\\boldsymbol{x}) \\geq 2 \\hat{\\beta}(a|\\boldsymbol{x})$, UIPS can still be guaranteed to converge to a stationary point with the ground-truth policy gradient being zero. \nHowever, the convergence of BIPS is unknown.\n\n\n\n\n"}]

Author rebuttal:
# General Response

We thank all reviewers for their insightful comments and suggestions, which will significantly help us  strengthen our paper. In the following, we will first respond to the common suggestions from all reviewers, and then respond to each reviewer individually.

> [CQ1] "Explain what UIPS exactly does and why do UIPS-O and UIPS-P lead to poor performance?"

UIPS minimizes the mean square error of the estimated value of a learnt policy, via estimating a per-sample weight $\phi\_{\boldsymbol{x},a}$ using bi-level optimization defined in Eq (8). Eq (8) nicely leads to a closed-form of $\phi\_{\boldsymbol{x},a}$ (in Theorem 3.2), with very intuitive and insightful physical meanings (in line 155 to 161): 

-  For samples whose largest possible propensity scores are under control: i.e., $ \frac{\pi_{\boldsymbol{\vartheta}}(a|\boldsymbol{x})}{\min 
 \boldsymbol{B}_{\boldsymbol{x},a}} < \sqrt{\lambda}$, higher uncertainty in the estimated logging probability implies smaller values of $\pi / \hat{\beta}$ and even smaller values of $\pi(a|\boldsymbol{x})$. 
This suggests samples of this type with positive rewards are underestimated, and the degree of underestimation increases with larger uncertainty. 
 UIPS thus chooses to increase their weights as uncertainty increases, to emphasize these long-tail positive samples.
-  Conversely, for samples with large propensity scores, UIPS decreases the weights of these samples as the uncertainty increases, so as to prevent their distortion in policy learning.

We should emphasize that these insights were purely extracted by the closed-form solution of $\phi\_{\boldsymbol{x},a}$, rather than manually injected beforehand.  

The learning problem induced by UIPS also has a theoretical guarantee on the learnt policy (Theorem 3.4), which suggests that with a high probability UIPS can converge to a stationary point where the ground-truth policy gradient is zero.

In contrast, UIPS-P and UIPS-O blindly penalize or boost samples based on uncertainties, without considering their impact on the accuracy of the resulting estimator and the learnt policy. 
As a result, they either overlook long-tail positive samples with high uncertainty or become distorted by samples with high uncertainties. This ultimately leads to their inferior performance.

> [CQ2]"Provide the results relative to the performance of the (true) logging policy, and explain why UIPS improves upon using GT propensities on some datasets."

We have included the IPS-GT baseline in our evaluation on synthetic datasets, which represents the performance of an IPS estimator utilizing the ground-truth logging probabilities. 

We can observe from Table 1 that UIPS achieved similar and even better performance than IPS-GT when the ground-truth logging policy is skewed, specifically when $\tau=0.5$ and $\tau=1$. This is because IPS-GT suffers from high variance due to small logging probabilities associated with a skewed ground-truth policy. However, UIPS achieves a better bias-variance trade-off by effectively controlling the negative impact of these high-variance samples. 

When the ground-truth logging policy is smoother (e.g., $\tau=2$), the variance of the IPS estimator becomes much smaller, and off-policy correction with the ground-truth logging probabilities leads to better model performance. But UIPS still outperformed all baselines without accessing the ground-truth logging policy.

> [CQ3] “Clarification on the performance.”

To evaluate the significance of improvement, we performed a t-test between the performance of UIPS and the best baseline on all datasets over 10 random trials created by distinct random seeds. Note that the hypothesis testing was conducted at the trial level rather than the instance level. 

Table 1 (synthetic datasets) and Table 4 (real-world datasets) demonstrate that **the best baseline varies across datasets** and also **under different metrics**, i.e., no consistent best baselines. In contrast, **UIPS consistently outperformed the best baseline across all metrics with a high level of statistical significance.** This proves the practical generality and applicability of UIPS.
 
Furthermore, the adopted offline metrics, namely Recall@K, NDCG@K, and Precision@K, have been demonstrated to align well with the online performance of recommendation algorithms [1]. As shown in recent literature [2,3,4], similar improvements on these offline metrics as UIPS has achieved, already suggest enhanced  online performance, such as increase in GMV/transactions or longer staytime.

Finally,  the benefit of UIPS is also been theoretically guaranteed (Theorem 3.4).

[1]Wang X, et al. How well do offline metrics predict online performance of product ranking models? SIGIR2023.

[2]Zheng et al. "Multi-Objective Personalized Product Retrieval in Taobao Search. KDD2021

[3]Li et al. Embedding-based product retrieval in taobao search. KDD2021

[4]Zhang et al. Disentangled Representation for Diversified Recommendations. WSDM2023



Meta-review: The authors proposed to improve the standard IPS estimator via taking the estimation error of the propensity score into consideration. It is achieved by introducing an instance weight to the estimator and optimizing the instance weight to minimize the mean square error of the newly proposed estimator. All of the reviewers found the proposed method sound and easy to follow and hence I recommend an acceptance. However, I still hope the authors can include several more discussions on the related work. For example, I believe for the stochastic bandit case, IPS estimator is minimax optimal, and I hope the authors can make more explicit comparison on the constant terms between the newly proposed estimator and IPS estimator to demonstrate the effectiveness on these simple cases. The discussion on the differences between the proposed estimator and doubly robust estimator is also encouraged.
Decision: Accept (poster)