Log-Sum-Exponential Estimator for Off-Policy Evaluation and Learning
Authors: Armin Behnamnia
Gholamali Aminian
Alireza Aghaei
Chengchun Shi
Vincent Y. F. Tan
Hamid R. Rabiee
Venue: ICML 2025 spotlightposter (2025)
Keywords: off-policy learning
off-policy evaluation
log sum exponential
regret bound
estimation bound
concentration
bias and variance
robustness
heavy-tailed reward
Primary area: reinforcement_learning->batchoffline
TL;DR: Inspired by log-sum-exponential operator, we propose a novel estimator for off-policy learning and evaluation under heavy-tailed assumption on weighted reward.

Abstract: Off-policy learning and evaluation leverage logged bandit feedback datasets, which contain context, action, propensity score, and feedback for each data point. These scenarios face significant challenges due to high variance and poor performance with low-quality propensity scores and heavy-tailed reward distributions. We address these issues by introducing a novel estimator based on the log-sum-exponential (LSE) operator, which outperforms traditional inverse propensity score estimators. Our LSE estimator demonstrates variance reduction and robustness under heavy-tailed conditions. For off-policy evaluation, we derive upper bounds on the estimator's bias and variance. In the off-policy learning scenario, we establish bounds on the regret—the performance gap between our LSE estimator and the optimal policy—assuming bounded $(1+\epsilon)$-th moment of weighted reward. Notably, we achieve a convergence rate of $O(n^{-\epsilon/(1+\epsilon)})$ for the regret bounds, where $\epsilon\in[0,1]$ and $n$ is the size of logged bandit feedback dataset. Theoretical analysis is complemented by comprehensive empirical evaluations in both off-policy learning and evaluation scenarios, confirming the practical advantages of our approach. The code for our estimator is available at the following link: https://github.com/armin-behnamnia/lse-offpolicy-learning .

Soog--um-Expooatiaal Estimator for Off-Policy Evaluation and Learning
Armin Behnamnia
Gholamali Aminian 2 Alireza Aghaei Chengehun Shi Vincent Y. F. Tan
Hamid R. Rabiee
Abstract
1. Introduction
Off-pooicy learning and evaluation from logged data are important problems in reinforcement learning (RL). The logged bandit feedback (LBF) dataset represents interaction logs of system with its environment, recording context, action, propensity score (i.e., the probability of action se- lection for given context under the logging policy). and feedback (reward). It is used in many real applications, e.g., recommendation systems (Aggarwal 2016 Li et al.
Off-policy learning and evaluation leverage logged bandit feedback datasets, which contain context, action, propensity score, and feedback for each data point. These scenarios face significant challenges due to high variance and poor performance with low-quality propensity scores and heavy-tailed reward distributions. We address these issues by introducing novel estimator based the log-sum-exponential (LSE) operator, which outperforms traditional inverse propensity score estimators. Our LSE estimator demonstrates variance reduction and robustness under heavy-tailed conditions. For off-policy evaluation, we derive upper bounds the estimator's bias and variance. In the off-policy learning scenario, establish bounds on the regret-the performance gap between our LSE estimator and the optimal bounded (1 + e)-th moment of weighted reward. Notably, we achieve a convergence rate of O( for the regret bounds, where E [0, 1] and is the size of logged bandit feedback dataset. Theoretical analysis is complemented by comprehensive empirical evaluations in both off-policy learning and evaluation scenarios, confirming the practical advantages of our approach. The code for our es- timator is available at the following link: httpss 7/gi wwt.huu.commaaaaaaaaaaeaa behnamn 1se-of learning
2011
personalized medical treatments (Kosorok Laber
2019 Bertsimas et al. (017), and personalized advertising campaigns (Tang et al.) 2013) Bottou et al.) 2013). The literature has considered this setting from two perspectives, off- off-policy evaluation (OPE) and off-policy learning (OPL). In off-policy evaluation, we utilize the LBF dataset from logging (behavioural) policy and an estimator constructed via e.g.. inverse propensity score (IPS) weighting, to evalu- ate (or estimate) the performance of a different target policy, In off-policy learning, leverage the estimator and LBF dataset to learn improved policy with respect logging policy.
In both scenarios. OPL and OPE, the IPS estimator is pro- posed (Thomas et al. 2015: Swaminathan & Joachims/ 2015a). However, this estimator suffers from significant variance in many cases (Rosenbaum & Rubin 1983). To address this, some improved IPS estimators have been pro- posed, such as the IPS estimator with the truncated ratio of policy and logging policy (Ionides 2008b), IPS estimator with truncated propensity score (ttrhll et al. 2010). self-
normalizing estimator (Swaminathan & Joachims 201 5b).
exponential smoothing (ES) estimator (Aouali et al.
2023
implicit exploration (IX) estimator (Gabbianelli et al.
2023
and power-mean (PM) estimator (Metelli et al. 2021
In addition the significant variance issue of IPS estimators. there are more challenges in real problems: estimated propensity scores and heavy-tailed behaviour of weighted reward due to noise or outliers. Previous works such as Swaminathan & Joachims (2015a), Metelll et al. (202T), and Aouali et al. (2023) have made assumptions when dealing with LBF datasets. Specifically, these works assume that rewards subject perturbation (noise) and that true propensity scores available. However, these assumptions
"qqual contribution 'Department of Computer Engineering, Sharif University Technology "The Alan Turing Institute, Lon- don, UK 'Department of Computer Science, Stony Brook Uni- versity 'Department of Statistic. London School of Economies 'Department of Electrical and Computer Engineering, National University Singapore. Correspondence to: Gholamali Aminian <gaminian turing ac.uk>, uk>, Hamid R. Rabiee <rabice @ sharif. edu>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

LoggSSu--Exponentee Estimator for Off-Policy Evaluation and Learning
may not hold in real-world scenarios.
2. Log-Sum--Eppoeential Estimator
Noisy or heavy-tailed reward: three primary sources of noise in reward of LBF datasets can be identified as (Wang)
We adopt the following convention for random variables and their distributions in the sequel. A random variable is denoted by an upper-case letter (e.g., 2), an arbi- trary value of this variable is denoted with the lower-case letter (e.g., =), and its space of all possible values with the corresponding calligraphic letter (c.g., Z). This way, we can describe generic events like {z 2} for any 2 E Z, or events like {g(Z) S 5) for functions g : Z - R. Pz denotes the probability distribution of the random variable Z. The joint distribution of a pair of random variables (Z,, Z2) is denoted by Zz. The cardinality of set Z is denoted by |2]. We denote the set of integer numbers from to by [n] - {1.... .n.. natural logarithm, i.e., log(z) == log, (2)) For two prob- ability measures P and Q defined on the space Z and a probability measure P define on the space V/ the total vari- ation distance between two densities P and Q, is defined as TV(P,Q) Q) fz IP - ((dz). We also define the con- ditional total variation distance as TV TV Q2(r) := Sy Py-y Sz [Pz=s|y=y - Qz==|Y=y/ (dz)dy.
Notation:
et al. 2020): (1) inherent noise, arising from physical con- ditions during feedback collection; (2) application noise, stemming from uncertainty in human feedback; and (3) ad- versarial noise, resulting from adversarial perturbations in the feedback process. Furthermore, In addition to noisy (perturbed) rewards, heavy-tailed reward can be observed in many real-life applications, e.g., financial markets (Cont & Bouchaud] 2000) and web advertising (Park et al. 2013) the rewards do not behave bounded and follows heavy-tailed distributions where the variance is not well defined.
In this work, we consider the
The access to the exact values of the propensity scores may not be possible, for example, when human agents annotate the LBF dataset. In this situation, one may settle for training model to estimate the propensity scores. Then, the propensity score stored in the LBF dataset can be considered a noisy version of the true propensity score.
Noisy (estimated) propensity scores:
Therefore, there is need for an estimator that can effec- tively manage the heavy-tailed condition and noisy rewards or propensity scores in the LBF dataset.
operator with applications in multinomial linear regression, naive Bayes classifiers and tilted empirical risk (Calafiore et al.,
Main Idea: Inspired by the
2019
Murphy 2012 Williams & Barber 1998 Li et al.
1.1. Contributions
2023
we define the LSE estimator with parameter À <<< O,
In this work, we propose novel estimator for off- off-policy learning and evaluation from the LBF dataset that out- performs existing estimators when dealing with estimated propensity scores and heavy-tailed or noisy weighted re- wards. The contribution of our work is forde-fold.
LSEx(Z) log A
1
(I)
where Z } are samples from the positive random variable Z. The key property of the LSE operator is its robustness to noisy samples in limited number of data samples. Here a noisy sample, by intuition, is point with abnormally large positive 21. Such points vanish in the ex- ponential sum as lim e² = 0 for À < O. Therefore the LSE operator ignores terms with large values for neg- ative X. The robustness of LSE has also been explored in the context of supervised learning by Li et al. (2023) from a practical perspective. Furthermore, in Appendix (App) C we discuss the connection between the LSE and entropy regularization.
First, we propose a novel non-linear estimator based on the tog-sum-exponential (LSE) operator which can be applied to both OPE and OPL scenarios. This LSE estimator effec- tively reduces variance and is applicable to noisy propensity scores, heavy-tailed reward and noisy reward scenarios.
Second, we provide comprehensive theoretical guarantees for the LSE estimator's performance in OPE and OPL setup. In particular, we first provide bounds on the regret, i.e. the difference between the LSE estimator performance and the true average reward, under mild assumptions. Then, we stud- ied bias and variance of the LSE estimator and its robustness under noisy and heavy-tailed reward scenarios.
Motivating example: We provide a toy example to inves- tigate the behaviour of LSE as a general estimator and its difference from the Monte-Carlo estimator (a.k.a. simple average) for mean estimation. Suppose that Z is distributed as Pareto distribution with scale x'm and shape Ç. Note that for Z ~ Pareto (imm () as heavy-tailed distribution, fur
Third, we conducted a set of experiments on different datasets to show the performance of the LSE in scenar- ios with true, estimated propensity scores and noisy reward in comparison with other estimators. We observed im- provement in the performance of the learning policy using LSE in comparison with other state-of-the-art algorithms under different scenarios.
Let < = 1.5 and &m 1. then fim L. The objective is to estimate E[Z] with n independent samples drawn from the Pareto distribution. We set n E (10, 50, 100, 1000, 10000) and
we have fz(()) = x
we have [[|2] 5-1
2

---

Log-Suu-Exponential Estimator for Off-Policy Evaluation and Learning
compute the Monte-Carlo (a.k.a. simple average) and LSE estimation of the expectation of Z. Table 1 shows that LSE (with À -0.1) effectively keeps the variance and mean- square error (MSE), low without significant side-effects on bias. We also observe that the LSE estimator works well under heavy tail distributions.
shrinkage (Su et 2020 and Dr-Switch (Wagg et al. 2017
as other model-based estimators. Our approach differs from this area, as we do not estimate the reward function in the LSE estimator. A combination of the LSE estimator with the direct method is presented in App. G.3 In this work, we focus on model-free approach.
Unbounded rewards (or returns) have been observed in various domains, including finance (Lu) & Rong 2018 and robotics (Bohez et al., 2019). In the context of multi-arm bandit problems, unbounded rewards can emerge as a result of adversarial attacks on reward dis- tributions (Guan et al. 2020). Within the broader field of RL, researchers have investigated poisoning attacks on re- wards and the manipulation of observed rewards (Rakhsha)
Unbounded Reward:
Table 1: Bias, variance, and MSE of LSE (with 0.1) and Monte-Carlo estimators. We run the experiment 10000 times and report the variance, bias, and MSE of the estima- tions.
Estimator
50
100
1000
20000
Bizs
Mente-Carko
LSE
0,1575
0.0155
0.1606
0.0083
0.1616
0.0061
0.1624
0,1629
0.0044
Variance
Monte Carlo
0,1088
1,5406
000666
1.2299
0.1443
1,3299
0.0355
L0203
0,8384
020268
et 2020 2021 Rangi et al. 2022). These studies high- light the importance of considering unbounded reward see- narios in RL and bandits algorithms. In particular, in our work, we focus on off-policy learning and evaluation under heavy-tailed (unbounded reward) assumption, employing a bounded (1 + e)-th moment of weighted -eward assumption for c E [0, 1].
MSE
Monte-Care Carlo
LSE
0.1287
1.5409
0L0744
1,392
0.0704
1,229
0,0898
1,0003
0.0534
0.8384
3. Related Works
We categorize the estimators based on their approach to reward estimation. Estimators that incorporate reward esti- mation techniques are classified as masel- estimators. In contrast, those that work without reward estimation are termed model-free estimators. Below, we review model- based and model-free estimators. Furthermore, we study the estimators which are designed for unbounded reward (heavy-tailed) scenarios in RL.
4. Problem Formulation
Let X' be the set of contexts and A the set of actions. We consider policies as conditional distributions over actions, given contexts. For each pair of context and action (x, a) e X' x A and policy Ti E Ilg, where 1le is defined as the set of all policies (policy set) which are parameterized by 0 O, where θ is the set of parameters, e-g., the parameters of neural network. Furthermore, the mo(a( is defined as the conditional probability of choosing an action given context z under the policy Te M
In model-free estimators, c.g., IPS estimators, we have many challenges, including, high variance and heavy-tailed scenarios. Recently, many model- free estimators have been proposed for high variance prob-
Model-free Estimators:
lems in model-free estimators (Strchl et al. 2010 lonides
A reward function known, defines the expected reward (feedback) of each ob- served pair of context and action. In particular, r(z,a) a) E E
X' x A - R+,, which is un-
2008b
Swaminathan & Joachims, 2015b Aouali et al.
2023
Metelli et al.) 2021 Neu 2015 Aouali et al. 2023
Metelli et al.] 2021 Sakhi et al. 2024). However, un- der heavy-tailed or unbounded reward scenario, the per- formance of these estimators degrade. In this work, our proposed LSE estimator demonstrates robust performance even under heavy-tailed assumptions, backed by theoretical guarantees.
[R] where R E I is random reward and PRIxma,Amm is the conditional distribution of reward R given the pair of context and action, (I, Note that, in the LBF setting, we only observe the reward (feedback) for the chosen action a in a given context x, under the known logging policy To To(a)z) We have access to the LBF dataset S (N,, 0s Pt. r:) 72) with n i.i.d. data points where each
Model-based Estimators: The direct method for off- off-policy learning from the LBF datasets is based on the estimation of the reward function, followed by the application of a supervised learning algorithm to the problem. However, this approach does not generalize well, shown Beyggellrr & &Langford (2009). A different approach where the direct method and the IPS estimator are combined, i.e., doubly- robust, is introduced by Dudik et al. (2014). A different approach based on policy optimization and boosted base learner is proposed to improve the performance in direct methods (London et al. 2.23). Furthermore, the optimistic
'In more details, consider an action space A with a a-algehra and a o-finite measure For any policy π and context x, let < =([zz) be a probability measure on A that is absolutely continuous with respect to 14, with density =(-[x) dx=(ulz) where nee (a is absolute continuous with respect to μ.
"The reward can be viewed the opposite (negative) of the cost. Consequently. a low cost (equivalent to maximum reward) signifies user (context) satisfaction with the given action, and conversely. For the cost function, we have c(2,a) = -r(x, a) as discussed in (Swaminathan & Joachims 2015a
3

---

Log-Sum-Exxonentie Estimator for Off-Policy Evaluation and Learning
"data point' (iy, a4 Ps, Ps) rz) contains the context x, which is sampled from unknown distribution Px, the action 0; which
OPL scenario: Our objective in OPL scenario is find an optimal To-, one which maximize V(To), i.e.,
is sampled from the known logging policy To mo(-)a;), the
propensity score p; - (o(a;/24). and the observed feedback (reward) ri as a sample from distribution PR)X= under logging policy To (aga (z:).
arg max (mTo). mlllla
(4)
We define the estimation errot] as the difference between the value function and the LSE estimator for given learning policy Ty E He i.e.,
We define the expected reward of a learning policy, Te E IIg, which is called the value function evaluated at the learning policy, as
Est (TT) = ((Te) V.A
LsE (S, no)-
V (TT) = Px (B)r( [B x [R]]]
(2)
For the OPL scenario, also define Ta policy as the maxi- mizer of the LSE estimator for given dataset S,
= Ep [E (Ax,
We denote the importance weighted reward as (A, R) where (A, X) is the weight,
TT(S)
arg max V.A. moElle
LSE (S,To)
(6)
(A(X)
Finally, we define regret, as the difference between the value function evaluated at T and Tă.
we w X) = [A(A)
As discussed by Swaminathan & Joachims (2115)), the IPS estimator is applied over the LBF dataset S (Rosenbaum & Rubin 1983) to get an unbiased estimator of the value function by considering the weighted reward as,
Rx S) = V(TT.) ) (ST((S)).
(7)
More discussion regarding the LSE properties is provided in App. C
(TT,,
rawa(a,
(3)
5. Theoretical Foundations of the LSE Estimator
where wo(a;, 24:)
To (o(a:/2))) 2x
In this section, we study the regret, bias-variance and robust- ness of the LSE estimator. We compare our LSE estimator with other model-free estimators in Table [ details are deferred App
To (a (2))
The IPS estimator as unbiased estimator has bounded variance if the no (A is absolutely continuous with re- spect to To (A (Strehl et al. 2010 Langford et al. 22008).
All the proof
Otherwise, it suffers from a large variance.
Non- Non-linearity of LSE: model-free estimator with respect to the weighted reward or reward, which is different from linear model-free estimators. In particular, most estimators can be represented as the weighted average of reward (feedback).
The LSE estimator is non-linear
LSE in OPE and OPL scenarios: The LSE estimator is defined as
VA Lse (S, TT) = (S) = X log
e )
((TO, S) = Σ (ri, wo (a),
(8)
where À 0 is tunable parameter which helps to recover the IPS estimator for X + O. Furthermore, the LSE estimator is an increasing function with respect to A.
where 9 Rt X R - R is transformation of rawo (a;, 22) and is defined for each model-free estimator. For example, we have g(r, v) = ry in the IPS estimator, y( r M) in the truncated IPS estimator (Ion- ides 2008b), g(r, y) = r((11111 - ^)y² 2) in the PM esti- mator (Metelli et al. 2021)) g(r, y) ry" for a E (0, 1) in the ES estimator (Aouali et al. (202)) and g(r: y) = r Ty ""44 in the optimistic shrinkage (OS) (Su et al. 2020). For the ex-emmmattor with parameter r (Gabbianelli al. 2023). we
OPE scenario: One of the evaluation metrics for an estima- tor in OPE scenarios is the MSE which decomposed into squared bias and the variance of the estimator. In particu- lar, for the LSE estimator, we consider the following MSE decomposition in terms of bias and variance,
MSE( Lse (S, mT))= B( Lse (S, =² + V(VA use (S, B( B(VA VA (S, mT)) = E[ E A (S, me)],
V(V. is (S, m B[( 1.s (S, nT) B 1.sm (S, me )))]
"In statistical learning theory, the difference between the ex- pected value of a random variable and its empirical estimate is referred to as the estimation emror. When applied to learning algorithms, this gap- hetwen expected and empirical perfor- mance-is known as the generalization gap.
where B(VA Se (S, πO)) and v V(VA.e (S, πO)) are bias and variance of the LSE estimator, respectively.

---

Suu----ppoonntilal Estimator for Off-Policy Evaluation and Learning
have g(r,y) r x m+
Furthermore, recently a logarith-
coverage (overlap) assumption, Assumption 5. can be inter- preted as heavy-tailed assumption on reward. Furthermore under a bounded reward, Assumption [.1 would be equiv- alent with the heavy-tailed assumption on the (1 + e)-th moment of weight function, wi 2)). A more detailed theo- retical comparison is provided in App. D.I We also provide a comparison with other estimators under bounded reward assumption in App. D.1.7 where Assumption|5.1 heavy-tailed assumption weights.
mic smoothing (LSS estimator with parameter À is proposed by (aaki et al. (2024) where g(r; y) ā log(11 + Xry)- However, the LSE estimator is non-linear function with respect to whole set of weighted reward samples. There- fore, the previous techniques for regret and bias-variance analysis under linear estimators are not applicable.
to
Theoretical comparison with other estimators: The com- parison of our LSE estimator with other estimators, includ- ing. IPS, self-normalized IPS (Swaminathan & Joachims 2015b), truncated IPS with weight truncation parameter M, ES-estimator with parameter a (Aouali et al., 2023). IX- estimator with parameter 17. PM-estimator with parameter (Metelli et al. 2021), OS-sstimator with parameter x (Su
5.2. Regret Bounds
In this section, we provide an upper bound on the regret of the LSE estimator as discussed in the OPI. scenario. The following novel is helpful lemma to prove some results. Lemma 5.2. Consider the random variable Z > 0. For E [0, 1]. then V (c^Z)= S |A]*+ holds for X < O.
at 2020) and LS-estimator with parameter À (Sakhi et al.
2024
is provided in Table 2
Note that the truncated IPS (IPS-TR) (lonides 2008a) em- ploys truncation, resulting in con-differentiable estima- tor. This non-differentiabiiity complicates the optimization phase, often necessitating additional care and sometimes leading to computationally intensive discretizations (Pap- iii et al. 2019). Furthermore, tuning the threshold M in IPS-TR is sensitive (Aouali et al. 2023).
In the following Theorem, we provide an upper bound on the regret of learning policy under the LSE estimator.
Theorem 5.3 (Regret bounds). For any ? E (0, 1), given
Assumption 5.7 assuming finite policy set [lig] < oo and n 2 (21x)' ++ (-) log [8g]
for X < O, with probability at
3 >eexp(2Aut7u o1
least (1 8), the following upper bound holds on the regret of the LSE estimator,
In the following sections, we provide more details regarding heavy-tail assumption and theoretical results for the LSE estimator.
A
4(2 - 7) log 4|TTol
0 S Rx(FT, S) 5
1tt
3(1 7) nd exxexp(M (1
5.1. Heavy-tail Assumption
(2 7)
4|A|1+ry 4|lTa
8
In this section, the following heavy-tail assumption is made in our theoretical results.
(1 7)x
n mcxp(2Xu1/(1oo)
where Tg is defined in equation 6.
Assumption 5.1 (Heavy-tail weighted reward). The reward distribution P and Px @ (A(A are such that for all learning policy To (A(X) E Hh and some E [0, 1]. the
Sketch of Proof: Using Bernstein's inequality, Boucheron et al. 2013 and Lemma 5.2 we provide lower and upper bounds on estimation error for a fixed learning policy ma Then, we consider the following decomposition of regret,
(1 + e)-th moment of the weighted reward is bounded
E Epx a [(wo(A, (()o(A,)))) X)R) "1 S v.
(9)
V(TT)) - (TTT) = Estx (mO.)
(10)
We make a few remarks. First, in comparison with the bounded reward function assumption in literature, (Metelli ett al., 2021 Aouali al. (2023), in Assumption [5.] the reward function can be unbounded. Moreover, our assump- tions are weaker with respect the uniform overlap as- sumption [3] In heavy-tailed bandit learning (Bubeck et al. 2013] Shao et al.] 2018 Lu et al. 2019), similar assump- tion to Assumption 5.1 on (1 e)-th moment of reward for
+ D.A (S, TT-) ) - V (S, mT) Estx(Ta))
Note that, the second is negative. We can provide upper and lower bounds on estimation error (Theorem D.2 and Theorem D.3 in App. D.2), respectively.
As the regret bound in Theorem 5.3 depends on X, we need to select an appropriate À to study the convergence rate of regret bound with respect to n.
some e E [0, 1] is assumed. In contrast, in Assumption 5.1 we consider the weighted reward. Note that, under uniform
Proposition 5.4 (Convergence rate). Given Assumption 5.1
(2v+ log Ral and for any < y < 1, assuming 2 7² xxxx((221/000)
Wee assume unbounded (1 + x)-th moment weighted reward for N. >< e.
'In the uniform coverage (overlap) assumption, it is assumed that sup Axxx (o x) = Ue < co.
setting = -n 1.. then the overall convergence rate of the regret upper bound is -n(((/))))
5

---

Estimator for Off-Policy Evaluation and Learning
Table 2: Comparison of estimators. We consider the bounded reward function, i.e., Rmax =- sup (a r(a, x) for all estimators except LSE. BSN and VSN are the Bias and the Efron-Stein estimate of the variance of self- normalized IPS. For the ES-estimator, we have 7 = B + (L/I)
+ log(4/6)). where DKL (Te||=T) LA (a z) (Tg( [ ()) We also define power divergence as Pa [ := Sa no (o) [o(o)))(-a is the power divergence with order a. For the IX-estimator, (,((t) is the smoothed policy coverage ratio. We compare the convergence rate of the concentration (or regret bound) for estimators. B and C' are constants. For LS estimator, Sx (TT))) is the discrepancy between π and T0-
Esiinatio
Conseitaaion
Comeeggncee Rate
Heavy-tiked
Regret Bound
Noioy Rewsed
Diffccetiabilit
Suhgaussian Like Taal
IPS
B Pal
O//-1/23
SN-IPS Swaminstthnn Toechims
Reasel (BN
IPS-TR Jonides 2008
P Intssta
O(w-1/3)
x
IX (n 2 D).
Ra +
O//-1/23
/
Gabolanell et al. 2023
PM (5.6 00, 11)
Hussy Parsiin
1P)
Metelli et al.
irr
/ Dest 7.5
Avurli ct al. 2023
Sa et al. 2020
> 0)
(23
/
LS >x ()
O(s 19]
Stkhi al 2014
LSE (0
D.4)
Oji-11400
Discussion: Note that, if Assumption 5.1 holds for where the second moment of weighted reward is bounded, then we have the convergence rate of O(n-1/2). Moreover, if higher moments of the weighted reward are bounded, the second moment is also bounded, allowing our results for a bounded second moment to apply. Note that, our theoretical results on regret can be applied to unbounded and and other estimators can not guarantee the convergence rate of ((n=s/(++e)) under bounded (1 + e)-th moment of weighted reward.
5.3. Bias and Variance
In this section, we provide an analysis of bias and variance for the LSE estimator.
Proposition 5.5 (Bias bound). Given Assumption 5.1 the following lower and upper bounds hold on the bias of the LSE estimator with X < 0,
weighted reward under Assumption[5..1]
(n - 1) V(e (AX)))))
s B
VA LSE
(S, mb))
(I))
2n A1
Bounded reward:
Our results in Theorem 3 also holds
I+E +
1
V(e ((x
under bounded reward and heavy-tailed weights assumption. More discussion is provided in App. D.I.7.
2nd
Remark 5.6 (Asymptotically Unbiased). By selecting X as function of n, which tends to zero as n + oc. e.g. A(n) = - for some 5 > O, the bounds in Proposi- tion 5.5 becomes asymptotically zero. The overall conver- gence rate for upper bound is <<((<(((+))) by choosing < = T For example, if Assumption 5.1 holds for 1. then by choosing < 1/2, we have the convergence rate of
Finite policy set: The results in this section assumed that the policy set, I1g, is finite; this is for example the case in off-policy learning problems with a finite number of policies. If this assumption is violated, we can apply the growth func- tion technique which is bounded by VC-dimension (Vapnik 2013) or Natarajan dimension (Holden & Niranjan| 1995) as discussed in (Jin et al., 2021). Furthermore, we can ap- ply PAC-Bayesian analysis (Gabbianelli et al. (2023) for the LSE estimator. More discussion regarding the PAC- Bayesian approach is provided in App. [D6]
O(n -1/2) for the bias of the LSE estimator. Consequently, the LSE estimator is asymptotically unbiased.
For the variance of the LSE estimator, we provide the fol- lowing upper bound.
Subgaussian Concentration: We also study achieving sub- gaussian concentration for the LSE estimator where the
Proposition 5.7 E( E((wo (A, X)R)
(Variance Bound), Assume that < V/2 0 holds. Then the variance
dependency of regret on 6 is subgaussian o( [og(1/8]
in App. D.7
AAssumption 5.1 for e
6

---

Estimator for Off-Policy Evaluation and Learning
of the LSE estimator with x < O, satisfies,
Theorem 5.9. For any 7 (0, 1), given Assumption
5.7
Assumption 5.8 and assuming 2 (2/x)' ut ++ log 3 exxx((2xu
1 (((w(A, v(Vise LsE (8, TT)) S
1 -12 n
(12)
for < O, with probability at least (1 - 8), the following upper bound holds on the regret of the LSE estimator under noisy reward logged data,
Variance Reduction: We can observe that the variance of the LSE is less than the variance of the IPS estimator for all À < 0.
0 (5), S
+ 24(7) V (A)
1
Combining the results in Proposition 5.5 and Proposition 5.7 we can derive an upper bound on MSE of the LSE estimator using MSE. The bias and variance trade-off for the LSE estimator and the comparison of different estimators in terms of bias and variance are provided in App. D.I.I
+ 2A())C((A,m) + 2TV (PX,,,,, D(ū,V),
2²
log nol where A(r) (2-2) Ci(,,)) o1A
(1-7)'
D(ū,)) exp(A)p=/a1 PRIX.A)]
eepp(I)pp//1 - 3 -1100) Tg(SS is de-
5.4. Robustness of the LSE Estimator: Noisy Reward
fined in equation 14 and TV PRIx,A)
In this section section, we study the robustness of the LSE estimator under noisy reward. We also investigate the perfor- mance of the LSB estimator under noisy (estimated) propen- sity scores in the App. E To analyze the robustness of the LSE estimator, we extend the approach of tilted empirical risk introduced by Aminiin et al.] (2025), which provides generalization error bounds" (uddr distributional shifts in supervised learning scenario under tilted empirical risk. Our analysis leverages these tools quantify the robustness of the LSE to noisy rewards.
E
Data-driven X: For large number of samples, n - oo, the second and third terms in Theorem 5.9 become negligible. Thus, under a noisy reward setting, can be chosen using the following objective function.
|
It 2TVx(PRIX.A PRIX.A) D(D,v),
AND arg min
xE(-oo,0) 1+E
X2
where D(T, v) is defined in Theorem 5.9
Suppose that due to an outlier or noise in receiving the feedback (reward), the underlying distribution of the re- ward given a pair of actions and contexts, PRIX.A is shifted via the distribution of noise or outlier, denoted as PRIX.A- We model the distributional shift of reward via distribu- tion PRIX_A due to inspiration by the notion of influence function (Marceau & Rioux [001] Christmann & Steinwart 2004). Furthermore, we define the noisy reward LBF dataset as S with n data samples. For our result in this section, the following assumption is made.
The term (Ve(PRIX x.a) in the upper Xa
Robustness:
bound on the LSE regret under noisy reward scenario (The- orem (.9) can be interpreted as the cost of noise associated with noisy reward. This cost can be reduced by increasing |k| However, increasing |A| also amplifies the term | in the upper bound on regret. Therefore, there is a trade-off between robustness and regret, particularly for X < the LSE estimator. More discussion regarding the robustness of the LSE is provided in App. D.9.
I-c
Assumption 5.8 (Heavy-tailed Weighted Noisy Reward). The Px @ To (A) and noisy reward distribution PRIX,a are such that for all learning policy (AIX) E TT and some [0, 1]. the (1 + c)-th moment of the weighted reward is bounded,
6. Experiments
We present our experiments for OPE and OPL. Our aim is to demonstrate that our proposed estimators not only possess desirable theoretical properties but also compete with baseline estimators in practical scenarios. More details can be found in App
PP [w (A) "1 S E.
(13)
Under the noisy reward dataset, we derive the following leaming policy,
6.1. Off-policy Evaluation Baselines:
Tg T arg max Vi (TO, 5).
(14)
For our experiments in OPE setting, we con- sider truncated IPS estimator (Swaminathan & Joachims 2015a). PM estimator (Metelli et al.) 2021), ES estima- tor (Aouali et al., (023)) IX estimator (Gabbianelli et al. 2023), SNIPS (Swaminathan & Joachims 20155). LS-LIN and LS estimators (Sakhi et al.) 2024). and OS (shrink- age) (Su al. 2020) estimator as baselines.
Tells
In the following theorem, we provide upper bound the regret of (5) as the learning policy under the noisy reward LBF dataset.
"Generalization error is defined as difference hetween popula- tion and empirical risks supervised leamning scenario.
7

---

Estimator for Off-Policy Evaluation and Learning
Table 3: Comparison of different estimators LSE, PM, ES, IX, BanditNet, LS-LIN and OS accuracy for EMNIST with different qualities of logging policy (T E (1, and true/noisy (estimated) propensity scores with b E (5, 0.01) and noisy reward with Py E (0.1, 0.5). The best-performing result is highlighted in bold text, while the second-best result is colored in red for each scenario.
Dataset
b
Py
LSE
PM
ES
IX
BanditNet
LS-LIN
OS
Logging Policy
88.49+0.04
89.19:0.0s
88.61=0.06
0..3
66.58+0.39
88.70=0.02
88.71+0.20
88.08
5
89.16:20.8
88.94-0.05
88.4820.00 os
88.51 20.23
65.10:0.c9
88.38=0.18
88. 08.70+0.11
88.08
0.0
86.07710..0
85.62=0.10
85.71 os
81.39:
66.5513.11
84.64=0.17
84.5910.00
88.08
0.1
89.29 29.00
89. 89.08...00
88.45.10.00 oo
08.14:10.14
59.90.3378
88 88.30
78.74..0.00
88,08
0.5
88.72 0..002
88. 08.00
87.27 1010
87.08=0.144
56.95+33.06
87 07.20
88.06++0.00
88.08
EMNIST
88, 0.00
88.61+0.00
88.38
85.488a..13 87.4
88.56 88.58:0.08
86.88
79.43
5
88 02:007
88.49:20.07
88. 18.39220.1 10
88.39
84.90 10
88 88.23
86.00
79.43
10
0.01
82.
11:0..1
80.85
$1.07:20.0 or
27.49
27.02:1192
78.43
21.70:t..11
79.43
0.1
88 20.02
88.1910 os
87.93
84.89133.1
87.50 87.50
87,6810.10
79.43
0.5
88. 11..11
88.52
84,4210.34
83,25.33.4
63.35113.39
85.75=00.4
89.0911..0
79.43
Datasets: We conduct synthetic experiments to evaluate our proposed LSE estimator performance in the OPE setting. For this purpose, we consider an LBF dataset which has only a single context (state), denoted as zo. We consider the learning and logging policies as Gaussian distributions, TT(([zu)) ~ [M11, o²) and To(-|>0)) ~ N(u2, o²). The re- ward function is positive exponential function e eas" which is unbounded. We also set our parameters to observe differ- ent tail distributions. We fix μl = 0.5, p2 1, 0.25 and change the value of a which controls the tail of the weighted reward variable, a E {1.4, 1.6]. We also examine different values of a and the effect of a number of samples for a fixed a in App. G.I Moreover, we conduct similar experiment when logging and learning policies are Lomax distribution
Table 4: Bias, variance, and MSE of LSE, ES, PM, IX, and IPS-TR estimators. The experiment is run 10000 times with 1000 samples. The variance, bias, and MSE of the estima- tions are reported. The best-performing result is highlighted in bold text, while the second-best result is colored in red for each scenario.
1.1
1.4
Estimator
Bias
Variance
MSE
Bias
Variance
MSE
PM
0.004
0.063
0.063
-0.301
164.951
165.041
ES
-0.001
0.054
0.054
1.950
0.396
4.232
LSE
0.052
0.006
0.009
0.615
0.292
0.670
IPS-TR
0.020
0.052
0.052
0.053
133.688
133.691
IX 0.237
0.002
0.058
1.340
0.048
1.842
SNIPS
-0.005
0.059
0.059
-0,029
133.320
133. 521
LS-LIN
0.284
0.001
0.082
2.164
0.005
4.687
LS
0.082
0.007
0.013
0.564
0.458
0.776
8 in App. G.1
OS
0.521
0.020
0.292
0.623
23.589
23.977
Metrics: We calculate the bias, variance, and MSE of esti- mators by running the experiments for 10K times each one over 1000 samples.
Discussion: The results presented in Table 4 demonstrate that the LSE estimator has better performance in terms of both MSE and variance when compared to other baselines. We also conducted experiments for OPE under some UCI datasets in 1pI More experiments are provided in App. G.Il for comparison of LSE estimator with LS estima- tor.
et al. 2020).
Datasets: In off-policy learning scenario, we apply the standard supervised bandit transformation (Beygelzimer
& Langford 2009) on a classification dataset: Extended- MNIST (EMNIST) (Xiao et al.) (017) to generate the LBF dataset. We also run on FMNIST in App/G.] This trans- formation assumes that each of the classes in the datasets corresponds to an action. Then, a logging policy stochasti- cally selects an action for every sample in the dataset. For each data sample xr action a is sampled by logging policy. For the selected action, propensity score p determined by the softmax value of that action. If the selected action matches the actual label assigned to the sample, then we have r = 1, and O otherwise. So, the 4-tuple (2. (r) makes up the LBF dataset.
6.2. Off- Off-policy Learning
Baselines:
For experiments in OPL, we compare our LSE estimator against several non-regularized baseline esti-
mators, including, truncated IPS (Swaminathan & Joachims
2015a), PM (Metelli et al. 2021) ES (Aouali et al. 2023
IX (Gabbianelli et al.) (023). BanditNet (Joachims et al.
2018), L.S-LIN (Sakhi et al.
2024) and OS estimator (Su
'The Lomax distribution a Pareto Type II distribution which is a hcavy-tailed distribution.
Noisy (Estimated) propensity score: For noisy propensity score, motivated by Halliwell (2018) and the discussion in
8

---

Log-SSum-Exponentee Estimator for Off-Policy Evaluation and Learning
assume multiplicative inverse Gamma noise" on TD for b E TR.,, nn- t "0 where 7 ((a (r)) is the estimated propensity scores and U ~ Gamma(b, 6).
Apple B.1
narios involving estimated propensity scores or heavy-tailed weighted rewards. Results from our experimental evaluation demonstrate that our estimator, guided by our theoretical framework, performs competitively compared to most base- line estimators in off-policy learning and evaluation.
Noisy reward: Inspired by Metelli et al. 2021). we also consider noise in reward samples. In particular, we model noisy reward by a reward-switching probability Py E [o, 1] to simulate noise in the reward samples. For example, re- ward sample of may switch to with probability Py.
8. Future Works
In this section, outline several potential directions for future work based our LSE estimator.
To have logging policies with different performances, given inverse temperature [T E (1,10,, first, we train a linear softmax logging policy on the fully- labeled dataset. Then, when we apply standard supervised- to-bandit transformation on the dataset, the results obtained from the linear logging policy which are weights of each action according to the input, will be multiplied by the inverse temperature т and then passed to softmax layer. Thus, as the inverse temperature r Increases, we will have more uniform and less accurate logging policies.
Logging policy:
Using regularization for off- policy learning can improve the performance of estimators (Aminian et al. 2024 Metelli et al. 2021). As future works, we plan to study the effect of regularization on the LSSE estimator from both theoretical and practical perspectives.
LSE and Regularization:
LSE with Positive A: Inspired by the application of LSE operator in supervised learning for positive (A > 0 (Li et al. 2023), exploring the LSE estimator for positive À in scenarios where the logged dataset is imbalance in terms of rewards or actions, can be an interesting direction. Note that our current theoretical analysis can be applied to negative and is not applicable for positive X.
We evaluate the performance of the different esti- mators based on the accuracy of the trained model. Inspired by London & Sandler (2019), we calculate the accuracy for deterministic policy where the accuracy of the model based on the argmax of the softmax layer output for given context is computed.
Metric:
We envision extending the application of our estimator to more challenging reinforcement learning settings, such as those considered by Chen & Jiang (2022); Zanette et al.] (2021 Xie et al.] (2019a). where the i.i.d. assumption does not necessarily hold. In these scenarios, theoretical guarantees must be adapted account for depen- dencies in the data-for example, by extending the analysis to martingale difference sequences.
LSE and RL:
For each value of r, we apply the LSE estimator and observe the accuracy over three runs on EMNIST. The deterministic accuracies of LSE, PM, ES, IX, BanditNet, OS and LS-LIN for r E 10) are presented in Table 3
The results presented in Table 3 demonstrate that the LSE estimator achieves maximum accuracy (with less variance) in most scenarios compared to all base- lines. Furthermore, an experiment on a real-world dataset, KUAIREC (Gao et al., 2022). is provided in App. G.4. More discussion and experiments are provided in App. G
Discussion:
LSE and Missing reward: mulation, we assumed that we have access to reward for all logged samples. However, in some applications as dis- cussed (Aminian et al. 2024), for some data samples the reward (feedback) is missed. In future work, we extend the application of LSE function to these scenarios where the reward (feedback) is partially missed.
Note that, in our problem for-
7. Conclusion
In this work, inspired by the log-sum-exponenntial opera- tor, we proposed a novel estimator for off- off-policy learning and evaluation applications. Subsequently, we conduct a comprehensive theoretical analysis of the LSE estimator, including a study of bias and variance, along with upper bound regret under heavy-tailed assumption. Further- more we explore the performance of our estimator in sce-
A Acknowledgment
The authors thank the anonymous referees and the area chair for their insightful and constructive comments. For the purpose of Open Access, the authors note that a CC BY public copyright license applies any Author Accepted Manuscript version arising from this submission.
'If Z ga c -9
Gamma(a, G). then have fz(2)
Impact Statement
The inverse temperature T is defined as (a: esp(M(sa;)/-)
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
ET exp(h(s.aa)/))) where A(z, as) is the i-th input to the soft-
max layer for context x E X and action a, E A.
9

---

Seig-Sum-Exxppnntee Estimator for Off-Policy Evaluation and Learning
References
Bottou, L., Peters, J., Quihonero-Candela, J., Charles, D. X., Chickering, D. M., Portugaly, E.,, Ray, D., Simard, P., and Snelson, E. Counterfactual reasoning and learning sys- tems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
Agarwal, P., de Beaucorps, P., and de Charette, R. Goal- constrained sparse reinforcement learning for end-to-end driving, arXiv preprint arXiv:2103.0m 09199, 2021.
Aggarwal, C. C. Recommender Systems. Springer, 2016.
Boucheron, S., Lugosi, G., and Massart, P. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
Agnihotri,, A., Jain, R., Ramachandran, D., and Wen, Z. Online bandit learning with offline preference data, arXiv preprint arXiv:2406.00 095744 2024.
Bubeck, S., Cesa-Biancee N., and Lugosi, G. Bandits with heavy tail. IEEE Transactions Information Theory, 59 (11):7711-7117, 2013.
Alaa, A. M. and van der Schaar, M. Bayesian inference of in- dividualized treatment effects using multi-task Gaussian processes. Advances in Neural Information Processing Systems, 30, 2017.
Buckman, J., Gelada, C., and Bellemare, M. G. The impor- tance of pessimism in fixed-dataset policy optimization. In International Conference on Learning Representations, 2020.
Alquier, P. and Guedj, B. Simpler pac-bayesian bounds for hostile data. Machine Learning, 107(5):887-900)) 902, 2018.
Calafiore, G. C., Gaubert, S., and Possieri, C. Log-sum- exp neural networks and posynomial models for convex and log-log-conve data. IEEE transactions on neural networks and learning systems, 31(3):827-838, 2019.
Amini, A., Gilitschenski, I., Phillips, J., Moseyko, J., Baner- jee, R., Karaman, S., and Rus, D. Learning robust control policies for end-to-end autonomous driving from data- driven simulation. IEEE Roboties and Automation Let- fers, 5(2):1143-115) 2020. doi: 10.1100/1.R..2221 2966414.
Cardaliaguet, P., Delarue, F., Lasry, J.-M., and Lions, P.-
L. The master equation and the convergence problem in mean field games. Princeton University Press, 2019.
Aminian, G., Beehnamiia, A., Vega, R., Toni, L., Shi, C., Rabiee, H. R., Rivasplata, O., and Rodrigues, M. R. D. Semi-supervised batch learning from logged data, 2024.
Chen, J. and Jiang, N. Offline reinforcement learning under value and density-ratio realizability: the power of gaps. Uncertainty in Artificial Intelligence, pp. 378-388. PMLR, 2022.
Aminian, G., Asadi, A. R., Li, T., Beirami, A., Reinert, G., and Cohen, S. N. Generalization and robustness of the tilted empirical risk. International Conference on Machine Learning (ICML), 2025.
Chen, M., Gummadi, R., Harris, C., and Schuurmans, D. Surrogate objectives for batch policy optimization in one- step decision making. Advances in Neural Information Processing Systems, 32, 2019.
Aouali, I., Brunel, V.-E., Rohde, D., and Korba, A. Ex- ponential smoothing for off off-po learning. In 40th In- ternational Conference on Machine Learning (ICML), 2023.
Christmann, A. and Steinwart, I. On robustness properties convex risk minimization methods for pattern recog- nition. The Journal of Machine Learning Research, 5: 1007-1034, 2004.
Athey, S., Tibshirani, J., and Wager, S. Generalized random forests. The Annals of Statistics, 47(2): 1178 2019.
Cont, R. and Bouchaud, J.PP. Herd behavior and aggre- gate fluctuations in financial markets. Macroeconomic dynamics, 102:170, 2000.
Bertsimas, D., Kallus, N., Weinstein, A. M., and Zhuo, Y. D. Personalized diabetes management using electronic medical records. Diabetes Care, 40(2):210-217, 2017.
D' A'gostino Jr. R. B. Propensity score methods for bias reduction in the comparison of treatment to a non- randomized control group. Statistics in Medicine, 17 (19):2265-228) -2811, 1998.
Beygelzimer, A. and Langford, J. The offset tree for learn- ing with partial labels. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Dis- covery and Data Mining, pp. 129-138, 2009.
Dawood, M., Dengler, N., de Heuvel, J., and Bennewitz, M. Handling sparse rewards in reinforcement learning using model predictive control. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 879 885. IEFF, 2023.
Bohez, S., Abdolmaleki, A., Neunert, M., Buchli, J., Heess, N., and Hadsell, R. Value constrained model-free contin- uous control. arXiv preprint /0t:::/992044440 2019.
10

---

Mogg-Sum-Exponeniee Estimator for Off-Policy Evaluation and Learning
Deng, J., Dong, W., Socher, R., Li, L.-J,, Li, K., and Fei-Fei, L.. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. lcee, 2009.
Holland, M. Pac-bayes under potentially heavy tails. Ad-
vances in Neural Information Processing Systems, 32, 2019.
Hopkins, S. B. Sub-gaussian mean estimation in polynomial time. arXiv preprint arXiv:1809.0742: 120, 2018.
Dubey, A. et al. Cooperative multi-agent bandits with heavy tails. In International conference on machine learning, pp. 2730-2739. PMLR, 2020.
Huang, J., Zhong, H., Wang, L., and Yang. L. Tack-
ling heavy- ttiiltt rewards reinforcement learning with function approximation: Minimax optimal and instance- dependent regret bounds, Advances in Neural Information Processing Systems, 36, 2024.
Dudik, M., Erhan, D., Langford, J., and Li, L. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485- 511, 2014.
Huang. Y. and Zhang. Y. A new process uncertainty robust student'st based kalman filter for sins/gps integration. IEEE Access, 5:14391-14400 2017.
Farajtabar, M., Chow, Y., and Ghavamzadeh, M. More robust doubly robust off-policy evaluation. Interna- tional Conference on Machine Learning, pp. 1447-1456. PMLR. 2018.
Tonides, L. Truncated importance sampling. Journal of Computational and Graphical Statistics, 17(2):295-311 2008a. ISSN 10618600. URL http::/www. jstor
Gabbianelli, G., Neu, G., and Papini, M. Importance- weighted offline learning done right. arXiv preprint vrXiv:2309.15711 2023.
org stttsseee159410000
Ionides, L. Truncated importance sampling. Journal of
Gao, C., Li, S., Lei, W., Chen, J.. Li, B., Jiang, P., He, X., Mao, J., and Chua, T.-S. Kuairec: A fully- observed dataset and insights for evaluating recommender systems. In Proceedings of the 31st ACM Interna- tional Conference on Information & Knowledge Man- agement, CIKM '22, pp. 540-550, 2022. doi: 10. 1145/5511808.3557220, URL https:://oi..... 10.1145/351 205753111188888552200
Computational and Graphical Statistics, 17(2):295-311, 2008b.
Jin, Y., Yang, Z., and Wang, pessimism provably efficient for offline RL? In International Conference on Machine Learning, pp.
PMLR, 2021.
Jin, Y., Ren, Z., Yang, Z., and Wang, Z. Policy learning" without" withouu"overlaa overlap: Pessimism and generalized empirical Bernstein's inequality. arXiv preprint (.Xi::2222.099900 2022.
Georgiou, G., Tsakalides, P., and Kyriakakis, C. Alpha- stable modeling of noise and robust time-delay estimation in the presence of impulsive noise. IEEE transactions on multimedia, 1(3):291-30) 1999.
Joachims, T., Swaminathan, A., and De Rijke, M. Deep learning with logged bandit feedback. In International Conference on Learning Representations, 2018.
Guan, Z., Ji, K., Bucci Jr, J., Hu, T. Y., Palombo, J., Liston, M., and Liang, Y. Robust stochastic bandit algo- rithms under probabilistic unbounded adversarial attack. In Proceedings of the aaai conference on artificial intelli- gence, 2020.
Johansson, F,, Shalit, U., and Sontag, D. Learning represen- tations for counterfactual inference. In International Con- ference on Machine Learning. pp. 3020-3029, PMLR, 2016.
Kallus, N. Balanced policy evaluation and learning. Ad- vances in Neural Information Processing Systems, 31, 2018.
Haddouche, M. and Guedj, B. Pac-bayes generalisation bounds for heavy-tailed losses through supermartingales. arXiv preprint 2tt::2220000222 2022.
Kang, Y., Hsieh, C.-.,, and Lee, Low-rank ma- trix bandits with heavy-tailed rewards. arXiv preprint arXiv:2404. 17709, 2024.
Halliwell, J. The log-gamma distribution and non-normal error. Variance (Accepted for Publication). 2018
Hamza, A. B. and Krim, H. Image denoising: A nonlinear robust statistical approach. IEEE transactions on signal processing, 49( (11):23335-3055 2001.
Kennedy, E. H. Towards optimal doubly robust estima- tion of heterogeneous causal effects. arXiv preprint arXiv:2004.1 14497, 2020.
Holden, S. B. and Niranjan, M. On the practical applicability of ve dimension bounds. Neural Computation, 7265: 1288, 1995.
Kiran, B. R., Sobh, I., Talpaert, V., Mannion, P., Al Sal- lab, A. A., Yogamani, S., and Pérez, P. Deep reinforce- ment learning for autonomous driving: A survey. IEEE

---

LrassSu--Exponnttie Estimator for Off-Policy Evaluation and Learning
Trunsactions on Intelligent Transportation Systems, 23 (6):4909-492)) 2021.
Lugosi, G. and Mendelson, S. Mean estimation and regres- sion under heavy-tailed distributions: A survey. Founda- tions of Computational Mathematics, 1965):1155-1190 2019.
Kosorok, M. R. and Laber, E. B. Precision medicine. Annual Review of Statistics and Its Application, 6:263-286, 2019.
LUGOSI, G. and MENDELSON, S. Robust multivariate mean estimation: The optimality of trimmed mean. The Annals of Statistics, 2021.
Kuzhorskij, I. and Szepesvári, C. Effro-Stein PAC-Bayesian Inequalities, arXiv:1909.0193.1 2019.
Kveton, B., Szepesvari, C., Ghavanzadeh, M., and Boutilier, C. Perturbed-history exploration in stochastic linear ban- dits. arXiv preprint arXiv: 1xXiv:193..99 1903.0912, 2019.
Lugosi, G. and Neu. G. Generalization bounds via convex analysis. In Conference Learning Theory, pp. 3524 3546. PMLR, 2022.
Langford, J., Strehl, A., and Wortman, J. Exploration scav- enging. In Proceedings of the 25th International Confer- ence on Machine Learning, pp. 528-535. 2008.
Lugosi, G. and Neu, G. Online-to-par conversions: Gen- eralization bounds via regret analysis. arXiv preprint arXiv:2305.19674 2023.
Lee, B. K., Lessler, J., and Stuart, E. A. Improving propen- sity score weighting using machine learning. Statistics in Medicine, 29(3):337-346, 2010.
Marceau, É. and Rioux, J. On robustness in risk theory. Insurance: Mathematics and Economics, 2962):177-185, 2001.
Lee, B. K., Lessler, J., and Stuart, E. A. Weight trimming and propensity score weighting. PloS one, 6(3)7418174, 2011.
McCaffrey, D. F., Ridgeway, G., and Morral, A. R. Propen- sity score estimation with boosted regression for evaluat- ing causal effects in observational studies. Psychological methods, 9(4):403, 2004.
Lee, K. and Lim, S. Minimax optimal bandits for heavy tail rewards. IEEE Transactions Neural Networks and Learning Systems, 35(4):5280-522) 2022.
Medina, and Yang. S. No-regret algorithms for heavy- tailed linear bandits. In International Conference on Machine Learning, pp.
Li, L., Chu, W., Langford, J., and Wang, X. Unbiased offline evaluation of contextual- -aaiiaa---ani----ee based news article recommendation algorithms. In Proceedings of the fourth ACM International Conference on Web Search and Data Mining, pp. 297-306, 2011.
PMLR, 2016.
Metelli, A. M., Papini, M., Faccio, F, and Restelli, M. Policy optimization via importance sampling. 2018.
Metelli, A. M., Russo, A., and Restelli, M. Subgaussian and differentiable importance sampling for off- ool-polyy eval- uation and learning. Advances in neural information processing systems, 34:8119-8132, 2021.
Li, T. Beirami, A., Sanjabi, M., and Smith, V. On tilted losses in machine learning: Theory and applications. Journal of Machine Learning Research, 24(142):1-79, 2023.
Murphy, K. P. Machine learning: a presabillstccceeppetttieii
MIT press, 2012.
London, B. and Sandler, T. Bayesian counterfactual risk minimization. In International Conference on Machine Learning, pp. 4133.4133. PMLR, 2019. Preprint version arXiv: T.t.:1806.15555 1500.
Neu, G. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
London, B., Lu, L., Sandler, T., and Joachims, T. Boosted oof-yy learning. In International Conference on Arti- ficial Intelligence and Statistics, pp. (p14-514566) PMLR, 2023.
Nie, X. and Wager, S. Quasi-oracle estimation of hetero- geneous treatment effects. Biometrika, 108(2):299-319, 2021.
Papini, M., Metelli, A. M., Lupo, L., and Restelli, M. Opti- mistic policy optimization via multiple importance sam- pling. In International Conference on Machine Learning, pp. 4989-4999, PMLR, 2019.
Lu, H. and Rong, K. Unbounded returns and the possi- bility of credit rationing: A note on the stiglitz-weiss and arnold -iley models. Journal of Mathematical Eco- nomics, 75:67-70, 2018
Park, J. Y., Lee, K.-W., Kim, S. Y., and Chung, C.-W. Ads by whom? ads about what? exploring user influence and contents in social advertising. In Proceedings of the first ACM conference on Online social networks, pp. 155 155-164, 2013.
Lu. S., Wang, G., Hu, Y., and Zhang, L. Optimal algorithms for lipschitz bandits with heavy-tailed rewards. In inter- national conference on machine learning, pp. 4154-4163. PMLR, 2019.
12

---

Saas-Su--Exponntiil Estimator for Off-Policy Evaluation and Learning
Park, M., Lee, S. Y., Hong, S., and Kwon, N. K. Deep deterministic policy gradient-basee autonomous driving for mobile robots in sparse reward environments. Sensors, 22(24):9574, 2022.
Saito, Y., Ren, Q., and Joachims, T. Off-policy evaluation for large action spaces via conjunct effect modeling. In international conference on Machine learning, pp. 29734- 29759. PMLR, 2023.
Peng, J., Zou, H., Liu, J., Li, S., Jiang, Y., Pei, J., and Cui, P. Offline policy evaluation in large action spaces via outeome-oriented action grouping. In Proceedings of the ACM Web Conference 2023, pp. 1220-1230, 2023.
Sakhi, O., Alquier, P., and Chopin, N. Pac-bayesian offiine contextual bandits with guarantees. In International Con- ference on Machine Learning, pp. 2023.
PMLR,
Polyanskiy, Y. and Wu, Y. Information theory: From coding to learning, 2022.
Sakhi, O., Aouali, I., Alquier. P., and Chopin, N. Loga- rithmic smoothing for pessimistic off-policg evaluation, selection and learning. arXiv preprint wrXiv:2405.14335 2024.
Rakhsha, A., Radanovic, G., Devidze, R., Zhu, X., and Singla, A. Policy teaching via environment poisoning: Training-time adversarial attacks against reinforcement learning. In International Conference on Machine Learn- ing, pp. 7974-7984, PMLR, 2020.
Setoguchi, S., Schneeweiss, S., Brookhart, M. A., Glynn, R. J., and Cook, E. F. Evaluating uses of data mining techniques in propensity score estimation: a simulation study. Pharmacoepidemiolos) and Drug Safety, 17(6); 546-555, 2008
Rakhsha, A., Zhang, X., Zhu, X., and Singla, A. Reward poisoning in reinforcement learning: Attacks against un- known learners in unknown environments. arXiv preprint arXiv:2102.0844 084922 2021.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
Rangi, A., Xu, H., Tran-Thanh, L., and Franceschetti, M. Understanding the limits of poisoning attacks in episodic reinforcement learning. arXiv preprint arXiv:2208. 13663, 2022.
Shalit, U., Johansson, F. D., and Sontag, D. Estimating individual treatment effect: generalization bounds and algorithms. In International Conference on Machine Learning, pp. 3076-3085 PMLR, 2017.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. Bridging offline reinforcement learning and imita- tion learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 14:11702-11716, 2021.
Shao, H., Yu, X.,, King, I., and Lyu, M. R. Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoff's. Advances in Neural Information Processing Systems, 31, 2018.
Rashidinejad, P., Zhu, H., Yang, K., Russell, S., and Jiao, J. Optimal conservative offline rl with general function approximation via augmented lagrangian. In The Eleventh International Conference on Learning Representations, 2022.
Shi, C., Song, R., and Lu, W. Robust learning for optimal treatment decision with np-dimensionality. Electronic journal of statistics, 10:2894, 2016.
Ronchetti, E. M. and Huber, P. J. Robust statistics. John Wiley & Sons Hoboken, NJ, USA, 2009.
Shi, C., Blei, D., and Veitch, V. Adapting neural networks for the estimation of treatment effects. Advances in neural information processing systems, 32, 2019.
Rosenbaum, P. R. and Rubin, D. B. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41-55, 1983.
Strehl, A., Langford, J., Li, L., and Kakade, S. M. Learn- ing from logged implicit exploration data. Advances in Neural Information Processing Systems, 23, 2010.
Ruotsalainen, L., Kirkko-Jaakkola. M., Rantanen, J., and Mäkelä, M. Error modelling for multi-sensor measure- ments in infrastructure-free indoor navigation. Sensors, 18(2):590, 2018
Su, Y., Dimakopoulou, M., Krishnamurthy, A., and Dudík, M. Doubly robust off-policy evaluation with shrinkage. In International Conference on Machine Learning, pp. 9167-9177 PMLR, 2020.
Sachdeva, N., Wang, I.,, Liang, D., Kallus, N., and McAuley, Off-policy evaluation for large action spaces via policy convolution. arXiv preprint urXiv:2310. 15433, 2023.
Sugiyama, M., Nakajima, S., Kashima, H., Buenau, P., and Kawanabe, M. Direct importance estimation with model selection and its application to covariate shift adaptation. Advances in Neural Information Processing Systems, 20, 2007.
Saito, Y. and Joachims, T. Off-policy evaluation for large action spaces via embeddings. arXiv preprint arXiv:2202.063/7. 2022.
13

---

SeasSSu--xxponnne Estimator for Off-Policy Evaluation and Learning
Swaminathan, A. and Joachims, T. Batch learning from logged bandit feedback through counterfactual risk min- imization. The Journal of Machine Learning Research, 16(1):1731-1755, 2015a.
Xie, T., Ma, Y., and Wang, Y.-X. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32, 2019a.
Swaminathan, A. and Joachims, T. The self-normalizes estimator for counterfactual learning. Advances in Neural Information Processing Systems, 28, 2015b.
Xie, Y., Zhu, Y. Cotton, C. A., and Wu, A model averag- ing approach for estimating propensity scores by optimiz- ing balance. Statistical methods in medical research, 28 (1):84-101, 2019b.
Tang, I.., Rosales, R., Singh, A., and Agarwal, D. Auto- matic ad format selection via contextual bandits. In Pro- ceedings of the 22nd ACM International Conference on Information & Knowledge Management, pp. 1587-1594, 2013.
Xue, B., Wang, Y., Wan, Y., JI, and Zhang. L. Efficient al- gorithms for generalized linear bandits with heavy-tailed rewards. Advances in Neural Information Processing Systems, 36, 2024.
Yan, Y., Li, G., Chen, Y., and Fan, J. The efficacy of pes- simism asynchronous Q-learning IEEE Transactions on Information Theory, 2023.
Thomas, P., Theocharous, G., and Ghavamzadeh, M. High- confidence off-policy evaluation. Proceedings of the AAAI Conference on Artificial Intelligence, 2015.
Yin, M. and Wang, Y.-.. Towards instance-optimal offline reinforcement learning with pessimism. Advances in Neural Information Processing Systems, 34:4065-4078, 2021.
Tolstikhin, I. O. and Seldin, Pac-bayes-empirriall bernstein inequality. Advances in Neural Information Processing Systems, 26, 2013.
Tsiatis, A. A. Semiparametric theory and missing data. Springer, 2006.
Yu, X., Shao, H., Lyu, M. R., and King, I. Pure exploration of multi-armed bandits with heavy-tailed payoffs. In UAI, pp. 937-946, 2018.
Vakili, S., Liu, K., and Zhao, Q. Deterministic sequencing of exploration and exploitation for multi-armed bandit problems. IEEE Journal of Selected Topics in Signal Processing, 765):79--76,,25 2013.
Zanette, A., Wainwright, M. J., and Brunskill, Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34: 34:13626-13640, 2021.
Vapnik, V. The nature of statistical learning theory. Springer science & business media, 2013.
Zhang, T. Information--heorrticc upper and lower bounds for statistical estimation. IEEE Transactions on Information Theory, 52(4):1307-132 2006.
Wang, J., Liu, Y., and Li, B. Reinforcement learning with perturbed rewards. In Proceedings of AAAI conference artificial intelligence, 2020.
Zhang, X., Chen, J., Wang, H., Xie. H., and Li, H. Uncertainty-aware off-policy learning. arXiv preprint 0tti:23333003889 2023a.
Wang, Y.-X., Agarwal, A., and Dudik, M. Optimal and adaptive off-policy evaluation in contextual bandits. In International Conference Machine Learning, pp. 3589- 3597. PMLR, 2017.
Zhang, X., Chen, J., Wang. H., Xie, H., Liu, Y., L.i, C.,, and Li, H. Uncertainty instance reweighting for off- policy learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023b. URL https! //openreview. wttp:/iwwwwweeeeeeeeeeeeeeeeeeee fortst/fooommmmmmm www.oorwww.m...-ii..............
Weitzen, S.. Lapane, K. L., Toledano, A. Y.. Hume, A. L., and Mor, V. Principles for modeling propensity scores in medical research: systematic literature review. Pharma- coepidemiology and Drug Safety, 13(12):841-853, 2004.
Zhong, H., Huang, J., Yang, L.., and Wang, L. Breaking the moments condition barrier: No-regret algorithm for ban- dits with super heavy-tailed payoffs. Advances in Neural Information Processing Systems, 34:15710-15720 2021.
Williams, C. K. and Barber, D. Bayesian classification with gaussian processes. IEEE Transactions on pattern analysis and machine intelligence, 10412):134 1998.
Zhu, J., Wan, R., Qi Z., Luo, S., and Shi, C. Robust offline policy evaluation and optimization with heavy- tailed rewards. arXiv preprint 2310vv2211. 18715, 2023.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: weXiv:1708.0777 700.07777, 2017.
Zhu, J., Wan, R., Qi, Z., Luo, S., and Shi, C. Robust offline reinforcement learning with heavy-tailed rewards. In
14

---

TrrssSum-Exponenne Estimator for Off-Policy Evaluation and Learning
International Conference on Artificial Intelligence and Statistics, pp. 541-549. PMLR, 2024.
Zhuang. and Sui, Y. No-regret reinforcement learning with heavy-tailed rewards. In International Conference on Artificial Intelligence and Statistics, pp. 3385-3393. PMLR, 2021.
15

---

See-S-m--xpponiee Estimator for Off-Policy Evaluation and Learning
Appendix
Table of Contents
Other Related Works
17
B Preliminaries
B.1 Notations and Diagram
19
B.2 Definitions
20
Theoretical Tools
C Other Properties of the LSE estimator
23
C.I LSE estimator and KL Regularization
24
D Proofs and Details of Section
26
D.1 Details of Theoretical Comparison
................................
26
D.2
Proofs and Details of Regret Bounds
................................
30
Prools Details Bias Variance
................................
D.4
Proof and Details of Robustness of the LSE estimator: Noisy Reward
37
D.5
Data-driven selection of
38
D.6
PAC- PAC-Bayesian Discussion
D 7
Sub-Gaussian Discussion
41
D.8
Implicit Shrinkage
41
Robustness Discussion
D. 10 Relaxing the lower bound on n in the regret bound
42
E
Robustness of the LSE estimator: Estimated Propensity Scores
43
Gamma Noise Discussion
F Experiment Details
F1 Hyper-parameter Tuning
49
F2 Code
49
Additional Experiments
G.1
Off-policy evaluation experiment
52
G.2
Off-policy learning experiment
57
Model hased estimators
63
G.4
Real- World dataset
64
G.5
Sample number effect
65
G.6
Effeet
65
G.7
Data-independent Selection of X
66
G.8
Data-driven Selection
71
OPE with noise
73
G. 10
Distributional properties in OPF
74
More Comparison with LS Estimator
76
12 OPE on UCI datasets
76
G. 13 Connection between heavy taile led distributions and outlier modeling
80
16

---

Log-SSumEExponee Estimator for Off-Policy Evaluation and Learning
A. Other Related Works
In this section, we provide other related works.
Other Methods for OPL: A Balance-based weighting approach, which outperforms traditional estimators, was proposed by Kallus 2018). Other extensions of batch learning as a scenario for off-policy learning have been studied, Papini al., (2019) consider samples from different policies and (Sugiyama et al. (2077) propose Direct Importance Estimation, which estimates
weights directly by sampling from contexts and actions. [Chen et al. (2019) introduced convex surrogate for the regularized value function based on the entropy of the target policy,
The pessimism concept originally, introduced in offline RL-Buckman et al., 2020 Jin et al. )02T), ) aims to derive an optimal policy within Markov decision processes (MDPs) by utilizing pre-existing datasets (Rashidineaad al. 2022 202T Yin & Wang. 202T Yan et al., 2023). This concept has also been adapted to contextual
Pessimism Method and Off-policy RL:
specific MDP instance. Recently, 'design-basee based' version of the pessimism principle was proposed by Jin et al. (2022) who propose data-dependent and policy-dependent regularization inspired by a lower confidence bound (LCBB on the estimation uncertainty of the augmented- uugmented-inverse propensity---pooeoee propensity-weighreed weighted AIPW)-type estimators which also includes IPS estimators. Our work differs from that Jin et al.] (2022) as our estimator is non-linear estimator. Note that for our theoretical analysis, we consider heavy-tailed assumption for (1 + e)-th moment for some e E [o, 1]. However, (Jin
bandits, viewed
et al.
2022) also considers 3rd and 4th moments of weights bounded.
Action Embedding and Clustering: Due to the extreme bias and variance of IPS and doubly-robust (DR) estimators in large action spaces, /Saioo& & Joachims (2022) proposed using action embeddings to leverage marginalized importance weights and address these issues. Subsequent studies, including (Saito al., 2023 Peng al.) 2023 Sachdeva et al., (202), have introduced alternative methods to tackle the challenge of large action spaces. Our work can be integrated with these
approaches to further mitigate the effects associated with large action spaces. We consider this combination as future work.
The individual treatment effect aims to estimate the expected values of the squared difference between outcomes (reward or feedback) for control and treated contexts (Shalit et al., (017). In the individ- ual treatment effect scenario, the actions are limited two actions (treated/not treated) and the propensity scores
Individualized Treatment Effects:
unknown (Shalit et al. 2017 Johansson et al. 2016: Alaa & van der Schaar 2017 Athey et al. 2019 Shi et al.) 2019 Kennedy 2020 Nie & Wager 2021). Our work differs from this line of works by considering multiple action scenario and assuming the access to propensity scores in the LBF dataset.
Noisy/Corrupted Rewards: Agnihotri et al. 2024) utilized offline data with noisy preference feedback as a warm-up step for online bandit learning. In linear bandits. Kveton et al.] (2019) estimated a set of pseudo-rewards for each perturbed reward in the history and used it for reward parameter estimation, Lee & Lim (2022) assumes a heavy-tailed noise variable on the observed rewards and proposes two exploration strategies that provide minimax regret guarantees for the multi-arm bandit problem under the heavy-tailed reward noise. In the linear bandits, Kang al. (0244) Huang et al. (202)) tackles the issue of heavy-tailed noise on cost function by modifying the reward parameter estimation objective. The former one uses Huber loss for reward function parameter estimation and the latter one truncates the rewards. Zhong et al. (2021) and Xuel let al. (2024) propose the median of means and truncation to handle the heavy-tailed noise in the observed rewards. In this work, we study the performance of our proposed estimator, the LSE estimator, under noisy and heavy-tailed reward.
Estimation of Propensity Scores: We can estimate the propensity score using different methods, e.g., logistic regres- sion (D' Agostino Jr 1998 WWetzen al.) 2004), generalized boosted models (McCafirey et al.) 2004), neural networks (Se) loguchi et al. 2008 parametric modeling (Xie et al.) (019b) or classification and regression trees (Lee et al.) 2010 2011).
Note that, as discussed in (Tsiatis 2006, (Shi et al. 2016). under the estimated propensity scores (noisy propensity score), the variance of the IPS estimator is reduced. In this work, we consider both true and estimated propensity scores, where the estimated propensity scores are modeled via Gamma noise. Our work differs from the line of works on the estimation methods of propensity scores.
Bandit and Reinforcement Learning under Heavy-tailed Distributions: Some works discussed the heavy-tailed reward
in bandit learning (Medina & Yangl 2016; Bubeck et al., 2013 Shao et al. 2018 Lu et al.) 2019 Zhong ct al. 2021).
Furthermore, some works also discussed the heavy-tailed rewards in RL (Zhuang & Sui 2021 1 Zhu et al. (2024). However, off colico learning with the LBF dataset under a -taved distribution of weighted reward Is overlooked.
Mean-estimation under Heavy-tailed Distributions: In (Lugosi & Mendelson, 2019 LUGOSI & MENDELSON
2021 Hopkins 2018), the performance of median-of-means and trimmed mean estimators have been studied and the
17

---

LoggSSun-Exponentaa Estimator for Off-Policy Evaluation and Learning
sub- Gaussian behavior of these estimators are studied. However, median-of-meant estimator presents practical challenges in implementation: it requires additional computational resources for data partitioning and mean caleulations, while also introducing discontinuities that can prevent gradient-based optimization methods.
Generalization Error Bound under Heavy-tailed Assumption: There are also some works that studied the generalization bound - the difference between population risk and empirical risk- of supervised learning under unbounded loss functions, in particular, under heavy-tailed assumption via the PAC- PAC-Bayesian approach. Losses with heavier tails are studied by Allqier Guedj (2018) where probability bounds tnon-high probability) are developed. Using a different risk than empirical risk, PAC-Bayes bounds for losses with bounded second and third moments are developed by [Holland (2019). Notably, their bounds include term that increase with the number of samples Kuzborskij & Szepesvári (2019) and HHaddouche &
Guedj (022) also provide bounds for losses with a bounded second moment. The bounds in (Haddouche & Guedj, (022) rely on parameter that must be selected before the training data is drawn. Information-
bounds based on the second moment of loss function S (e, 2) - (h, 2)]l are also derived in (Lugosi & Neu 2022). Furthermore, in (Lugosi & Mendelson 2019, Section 4), the uniform bound via Rademacher complexity analysis over the Lg bounded function space is studied for the median-of-meane estimator. Furthermore, the generalization error of tilted empirical risk under heavy-tailed assumption studied by AAminian et al. (2025). In contrast, we focus on estimation bound and regret analysis of the LSE estimator non-linear estimator in OPL and OPE scenarios. For more detailed comparison between batch learning and supervised learning see (Swaminathan & Joachims 2015a Table 1).
Heavy-tailed Rewards in Bandits: Bandit learning with heavy-tailed reward distributions has been extensively studied. Bubeck et al. (013) proposed Robust UCB, and Vakili et al. (013) introduced DSEE as bandit algorithms with theoretical regret guarantees. Yu et al. (2018) proposed a bandit algorithm based on pure exploration with heavy-tailed reward distributions. Heavy-tailed reward distributions are also studied in the context of linear bandits (Shao et al.. 2018 Medina & Yang 2 Dubey al. (2020) proposed a decentralized algorithm for cooperative multi-agent bandits when the reward distribution heavy-tailed. Our work differs from this line of works by considering the heavy-tailed assumption on the weighted reward.
Heavy-tailed Rewards in RL: The challenge of heavy-tailed distributions in decision-making has been studied for more
than two decades (Georgiou et al. 1999 Hamza & Krim 2001; Huang & Zhang 2017 Ruotsalainen et al. 2018). There is a significant amount of study in RL dealing with heavy-tailed reward distribution (Zhu et al.) 2023 Zhuang & Sui 202 l
Huang al., 2024). Moreover, big sparse rewards are a prominent issue in reinforcement learning (Park et al. 2022
Agarwal al. 2021 Dawood et al. 2023). In such scenarios, there is far-reaching goal, possibly accompanied by sparse failure states in which the agent attains big positive and negative rewards respectively. For example in safe autonomous driving, accidents are so costly and, hence are assigned large negative rewards. They are also delayed and sparse, which means that they are observed after many steps with a lot of exploration in the environment (Kiran et al., 2021 Amini et al., 2020). This hinders the training and leads to an infeasible slow learning curve. A common approach to tackle this issue is reward shaping which inserts new engineered reward functions alongside the agent's trajectory to provide guidelines for the agent (Kiran et al. 202T). This strategy may fail because it biases the model into the strategy hinted by the new rewards, which may not be the optimal solution for the original problem. Moreover, the method of reward shaping will not necessarily avoid the low- cow-probability high-value rewards, because the imputed rewards are mostly small and high-value value rewards still happen with low probability. Therefore, handling lowpprobability large reward is one of the challenges in this field, which can be modeled by heavy-tailed distributions as discussed with more details in App. G.13
18

---

Sane-Sum-Exponettii Estimator for Off-Policy Evaluation and Learning
B. Preliminaries
B.1. Notations and Diagram
All notations are summarized in Table 5
An overview our main thcoretical results provided in Fig.
estimator
Oft-Policy Evalunsion
Robusines
Ofr-Polliyy Leaming
Bias
Variance
Noisy
Noisy propen- sily spure
Regret
Bound
Estimation
Bins Bounds (Proposition 5.5)
Variance Bound Prrousitioon 5.7)
Regret Bound [Therem 5.9)
Regret Bound heorem E.7)
Bounds
Regret Bounds Chorre 5.3)
(Teeree D.3
Figure Overview the main results
Table 5: Summary of notations in the paper
Notation
Definition
Notation
Definition
X
Context
Action
A(
Reward function
Reward
n
The number of logged data samples
Px
Distribution over context set
S
LBF dataset
Propensity score (No (a)l)));
Fe Vizz(S, (S, ms)
Learning policy
ma(AA))
weight (Ta(A)X))/sl)) (/))////(AA))
V
the LSE estimator
V(m)
Value of learning policy me Logging policy
2' Esty
Upper bound on (1 e)-th moment of weighted reward (Assumption
5.1
[a(a X)
Estimation error of the LSE estimator
(Tg
Regret of the LSE estimator
B( VA
Lsu
(S, (S, mo))
Bias the estimator
V(VA (S, mo))
Variance of LSE estimator
19

---

LoggSSum-Exponenteee Estimator for Off-Policy Evaluation and Learning
B.2. Definitions
We define the softmax function
softmax((1 22, ". [n) = (81, 82, 1 ,8n); ,
c
8;
w 1 isisn.
The diag function, diag(ai, 02, ,,n) IR=x defines diagonal matrix with a 02,". On elements its diagonal. Definition B.1. (Cardaliaguet et al. 2019) A functional U P(RR) + R admits a functional linear derivative if there is P(RR) R" R which continuous on P(R"), such that for all m, m' P( it holds that
SU
map 6m
U(m') (m) = =f" /
8U dm
(m a) (m' m)(da) dA,
where MA A(m' m).
B.3. Theoretical Tools
In this section, we provide the main lemmas which used in theoretical proofs.
Lemma B.2 Cantoroviic-RRueenee duality of total variation distance, see (Polyanskiy Wu 2022 The Kantorovich-
Rubenstein duality (variational representation) of the total variation distance as follows:
TV(m,, m2) = 2L
sup (Ez-m, [g(Z)] - E Ez [g (Z))),
(15)
where Gr = (g: 2 Rllll $ L}.
Lemma B.3 (Hoeffding Inequality, Boucheron et al. 2013). Suppose that Zi are sub-Gaussian independent random variables, with means μls and mub-Gaussian parameter o. then we have:
(2. us) 21
< exp
(16)
Tt 2
1= 05
Lemma B.4 (Bernstein's Inequality, [Boucheron et al. that Z2 -E[ S. R almost surely for all i, and (ZZ)
2013).
Suppose that S = [Z are i.i.d. random variable such Then the following inequality holds with probability at least
o²_
(1 - 8) under Ps-
2
1og(2/8)
(Rlog(2/8)
Z
Z
(17)
n1
n
3n.
The of the lemmas provided with proofs.
Lemma B.5 (Change of variables). Assume that the following equation holds,
A82
c= cxc
B + C5
for some positive parameters A, C, 2 0 and 0 < 5 1. Then, we have,
Clog
B log
8 <
+
A
A
Also, for some D O, A
log
+2DC log
then we have 8 < D.
17
20

---

Log-Sum-ENxe Suun-Exoonentill Estimator for Off-Policy Evaluation and Learning
Proof. We have,
= exp {
A8
++ A6 - C'log -o
13 log 1
0
B B Co
Given and solving the quadratic equation, we have,
C'log 1 + V C² 4AB log
C
log 1
log
log
1
B C
5 = 2A
+
4
2
A
A
log A
log
B
CV
+
A
C
C'log 1
B log
+
A
A
where the inequality derived from + b S va + vb. For the second part, similar argument works for V as the variable.
Clogg
B Blog
+
< Da V B log
C'log 2 0
A
A
which is satisfied if a is greater than the bigger root,
Blog + Blog 1 + 4DC log 1
a
2D
So,
2
log
+ 2DC log
V B log & + Blog & + 4DC log
A A
2
2D
8 a+t²² 2- 2 (2tb)² Hence if A > Blgg +2DC log is bigger than the largest root
where the last inequality comes from and the proposed inequality holds.
D
Lemma B.6. Assume A, B, C.t. For any R+ such that,
C
S 2AC B*
we have,
Ax + Bx C
(18)
Proof. Given Ar < C, equation equation 18 is equivalent to the following quadratic form.
2²,² - (B + 2AC) + C 2 0
Let 0 < r1 < T2 be the roots of the abovementioned quadratic form. X Tı, Ar C holds and the quadratic form positive. So have the following condition satisfy Equation 18
B + 2AC V(B 2ACY² -
20
x <
2
B+ 2AC V(B 2AC)+ C
Since,
2
202
2AC +
BAC + VB 4
the condition in the lemma is sufficient for equation 18 to hold.
21

---

Se----ummpppntttii Estimator for Off-Policy Evaluation and Learning
Lemma B.7. Let consider the functions hs(y) log(y) + z and (v) log(y) + z for < b. Then holy) and ha (y) are concave and convex, respectively.
Proof.
Taking the second derivative gives us the result, dy² (log(v) + By²) = + 2,3.
Lemma B.8. We have the following inequality for y < 0 and c [0, 1].
y llte
ex 1 + y +
(19)
1+e
Proof. For y = 0, equality holds. If suffices to prove that the derivative of LHSS of equation 19 is more than the derivative of RHS Vy i.e.,
Note that for -1, lu1 2 1 and the inequality trivially holds. For - -1, ly/ is minimized at = 1, so it is sufficient to prove the inequality only for e = 1, which is,
e - 0 2 2y+1
and holds Vy S
Remark B.9. Lemma 28 in (Lugosi Neu 2023 the following upper bound for y < and e [0,1] is proposed,
< 11 y + 1yyl
(20)
4+ instead of lyy l+c.
In contrast, Lemma B.8 is tighter via using
Lemma B.10. For positive random variable, Z 0, suppose E[Z < v, for some E [0, Then, the following inequality holds,
E z S 2/1++e)
Proof. Due to Jensen's inequality, we have,
E|Z| [(2 < E[Z s/(+te))
Lemma B.11. For a positive random variable, Z > suppose E[|Z+o] < oo for some E [0, 1). Then, following inequality for X < holds,
Z
log E|e22 2[2] 1+E 1
Proof. The left side inequality follows from Jensen's 's inequality on f(z) = log (z). For the right side, we have for 2 < 0,
1+z s1+zt
+ |z| 1t|
22

---

See-SSmm--xxpettee Estimator for Off-Policy Evaluation and Learning
Therefore, have,
1 log [[1
+ AZ + 1 1x
log 12e
A
1+6 E
π log
1
1 AIE|Z|
+ 1+E
| to B [z(tt]
2
+ 1+6"
| |1
E[z]
1+c
C. Other Properties of the LSE estimator
Proposition C.1 (LSE Asymptotic Properties), The following asymptotic properties of LSE with respect X holds,
1
lim 1.n (S)
Σ rowe (as, 2z))
lim VA "sse (S) = min r:w0 (a;, xz);
2--20
lim V (S) = max maxr,wy(a,, xz).
Proof. For the first limit, we use I'Hopital's rule:
Eis gdrcmglogee))
log
lim V V. (S)
lim X
n
x=
E ae (eppoogp
E edriuplesia))
lim
A
Σ n
(a; v3.) 1i=1 (a;
n
For the second limit for > -00 we have:
1
2i=1 Amiu, (ama(as
n (rraaa(a
m)
t * log
< X
log
A ri rewala
$
log
n
min rywo (ai, xii logg.
As both lower and upper tends to min, rawp(a; v.)) we conclude that:
Σn Aryws (a;
lim
log
min (, x.).
n
similar argument proves the third limit (A oo).
Remark C.2. As shown in Zhang 2006, Proposition 1.1), the LSE function is increasing function with respect to
23

---

IeasSuu--Exponente Estimator for Off-Policy Evaluation and Learning Derivative of the LSE estimator: The derivative of the LSE estimator can be represented as,
Va V LSE S, mp)
1
The -V (aw Ti).
(21)
Note that, in equation [1] we have a weighted average the gradient of the weighted reward samples. In contrast to the linear estimators for which the gradient a uniform mean of reward samples, in the LSE estimator, the gradient for large values of rowo (a;, m4). Vi [n] (small absolute value), contributes more the final gradient. It can be interpreted the robustness of the LSE estimator with respect the very large absolute values of ryw (a, Z4) (i.e. high wo(a, x)), Vi [n]].
It is interesting to study the sensitivity of the LSE estimator with respect to its values.
Lemma C.3. The gradient and hessian of the LSE estimator with respect to its values are as follows,
VVA
use (S, πa) = softmax(\rr #1), Ar Wog [n));
(22)
V V LsB (S) Adiag(S.) A
(23)
where Sn softmax(Ar1ug(01 z1). Ar, kn)). Also, LSE is convex when À > 0 and concave other- wise.
Proof: The two equations can be derived with simple calculations. About the convexity and concavity of V that for 2 0 the Hessian matrix is positive semi-definite. The proof for concavity for < 0 is similar.
we prove
n
zd 2 VA
LSE = (z" diag(Sn)z 2J 25 S =
Σ
Sn()
Σ
(1)(
T1 Esh(0)
Sy (1)zz
2 0.
Where the last incquality is derived from the Cauchy-Schwarz inequality.
show that V is convex for À 2 0 and concave for À < O. Applying Lemma that the derivative of the LSE estimator is positive and less than one, i.e.,
Using Lemma C.3
C.3
prove
0 S VVA To) S 1.
(24)
Furthermore, we prove equation 21 by applying Lemma C.3
C.1. LSE estimator and KL Regularization In this section, we will discuss the connection between the LSE estimator,
LSEx(Z) log
Σ ARi
(25)
and the KL regularization problem.
Consider the following KL-regularized expected minimization for X < 0,
1 1 A (KI(U)))n(()))
min PEA
Σ Piz:
(26)
where n- denotes the probability simplex and Uni(n) the discrete uniform distribution over n mass points. Note that O, and the KI. divergence is strictly convex with respect P. Therefore, the objective function in equation 26 is convex.
24

---

Log-Sum-Exponentie Estimator for Off-Policy Evaluation and Learning
Then, the solution of the regularized problem in equation 26
the Gibbs distribution follows,
exp(Az:)
p
vi e [n],
(27)
E exp(Ae;))
Using equation 27 in equation 26 we have,
exp(Az;) n j= exp(Azz)
exp(X2;)
(Az) log
Σ 7
exp exp()zi))
Σ j=1 exp()2z)
(28)
log ( Σ exp()zi))
Therefore, the final value of the KL-regularized minimization problem is the LSE estimator with À 0. Therefore, the LSE estimator with negative parameter can be interpreted KL-regularized expected minimization problem.
25

---

Ars-Suu--Exponetiial Estimator for Off-Policy Evaluation and Learning
D. Proofs and Details of Section 5
D.I. Details Theoretical Comparison
In this section, we compare our estimator with PM, ES, IX, LS and OS from a theoretical perspective in more detail.
D.1.I. BIAS AND VARIANCE COMPARISON
In this section, we present the bias and variance comparison of different estimators in T 6 We define power divergence as Pa ( == To(a (o([[=))) is the power divergence with order a. For fair comparison, consider the bounded reward function, i.e., Rmaxx = (e) r(a, æ:). Therefore, we have S R (Too(TT|| and 1 ( [T)) We can observe that LSE has the same behavior in comparison with other estimators.
12
Table 6: Comparison of bias and variance of estimators, IBSN and ySN are the Bias and the Efron-Stein estimate of the variance of self normalizdd IPS. For the ES-estimator, we have T B RS + DKL (Tol | mo) Ja =o(a(ar) log(To(ad ( (tol))/(////)) (/(aaaa)))d For the IX-estimator, Cipy (T)(T) is the smoothed policy coverage ratio. We compare the convergence rate of the estimation bounds for estimators. / and C' are constants, For LS estimator, Sj (TT) is the discrepancy between and To-
(Tel(a)) + log(4/5)). where
Estimator
Variance
Bias
R R_ PTT (To)
IPS
0
SN-IPS
R2 VSN max
Rmax BSN
Swaminathan & Joachims, 2015b
IPS-TR M > 0)
R2 max
PT(TT)
Rmax
P2(TollTT)) M
[Ionides 2008a
IX (n) 0)
Rmax Cn((To)
RmaxT
(Gabbianelli et al. 2023
PM (A E [0, 1)
R² max P2( (TT)
(Metelli et al. 2021
n
ES (ax E [0, 1)
Exp [T [ 1-20
R22
Rmax (1 - Eg [m]] ())
max
Aouali et al. 2023
n
OS (r > 0)
R² max
(TT (TO)
Po(TTol TT)
Rmax
(Su et al.
2020
7
LS ( > 0)
S (TT)
ASS(TT)
Sakhi et al. 2024
LSE (0 oc and e E [0, 1))
R PT [To)
1 Itc |\ Rite Pite TO)
(ours)
2n X
LSE Variance: Note that in variance comparison between IPS and LSE, the LSE variance is less than IPS, shown in Proposition 3.7 However in Table we use a looser upper bound to compare bounds in terms of the same parameter Rmax-
Bias and Variance Trade-off: Observe that for the bias and variance of the LSE estimator, there is a trade-off with respect < 0. Specifically, reducing À increases the bias of the LSE estimator,
B BA LeB (S, mO)) E[wo (A, -EV Lan (S, mo)).
(29)
26

---

Log-Sum-Exponentie Estimator for Off-Policy Evaluation and Learning This is consequence of the increasing property of the LSE with respect À (see Remark C.2 Additionally, for the variance, we have the following bound,
Var Var(V... LSE (S, mo)) & E ( LsE (S, xo))²]
(30)
It is important to note that decreasing À reduces the upper bound on the variance of the LSE estimator.
Therefore, by decreasing À < 0, the bias increases and the variance decreases.
D.1.2. COMPARISON WITH PM ESTIMATOR
In Metelli al. 2018), the authors proposed the following PM estimator for two
(Aps s),
1
(SM TO)
Σ ((1 >p)uo mi)" + Xp)
i=1
An upper bound on estimation error of PM estimator for (Ap, -1), is provided in Meteell et al. 2018 Theorem 5.1),
2Pa (To | - log
(S m²) |R v3)
(31)
3(a 1)2n
where (S nT) = (m²) - (S, and a E (1,2). In contrast to the bound presented in equation 31 which necessitates bounded reward, exhibits a dependence on log(1/5) and two hyper- syrem--arrmettr (s, Ap). our work offers several advancements. We derive both upper and lower bounds on estimation error, as detailed in Theorem D.3 and Theorem D.2 respectively. These bounds help us for our subsequent derivation of upper bound regret. Notably, bounds demonstrate a more favorable dependence of log(1 log(1/5))/3 /5)1/2, This improvement not only eliminates the requirement for bounded rewards but also provides a tighter concentration. Furthermore, we provide theoretical analysis for robustness with respect to both noisy reward and noisy propensity scores, and we just have one hyperparameter. Note that the assumption on Pa (To) for a = 1 + e (Metelli et al. 2018 similar to bounded (1 + e)-th moment of weight function, wa(a, x) for a bounded reward function.
1.3. COMPARISON WITH ES ESTIMATOR
The ES estimator (Aouali al. 2023 is represented as,
To (o(a; 2x) r3
V (T))
a E [0, 1]. To =o(ap=:)
(32)
(ouuai al. 2023
Theorem 4.1), an upper bound on concentration is derived via PAC-Bayesian approach for a E [0, 1].
(LI(
KLz(Fg)
(m V (TT))
+ (T2))
2n
nX
X
vo (TQ).
2
4
where KLI(Te) DKL. (Q[(P) (
+ In 8
and
4
(33)
KTa(m²) DRL. (Q[lP) In
8'
(T2)
E Ba (mr)) [al=((a(x)))
1
Ta(a|o;)
x (a; [x;) P8l3
V. (TTO)
En @o (1b,,)
+
To To(a (a/222))20
To (a )a
mm1
27

---

Log-Sum-Exxpneeni Estimator for Off-Policy Evaluation and Learning
where Q and IP are posterior and prior distributions over the of hypothesis, (TOg) is ES estimator and R(m)) is true risk. The ES estimator's bound exhibits several limitations. Primarily, it requires bounded reward. Moreover, the upper bound on the concentration (estimation error) of the ES estimator converges at rate of (log(n)) -1/2), which is suboptimal. A notable drawback is the presence of the term B (mQ). which remains constant for > 1 and does not decrease with increasing sample size n. In contrast, we derive an upper bound on the Regret with a convergence rate of ((n-1/2) under the condition of bounded second moment (e = 1) and can be extended for heavy-tailed scenarios under bounded reward. This improved rate not only eliminates the logarithmic factor but also demonstrates a tighter concentration. Furthermore, we have a theoretical analysis for robustness with respect to both noisy reward and noisy propensity scores. Finally, the noisy reward scenario is not studied under the ES estimator.
1.1.4. COMPARISON WITH IX ESTIMATOR
The IX estimator (Gabbianelli et al. 2023 is defined as for > 0,
(S, Te) == 1
ma (a; (z:)
(a (x,) + T/p
The following upper bound on regret of IX estimator is derived in (Gabbianelli et al. 2023
Theorem 1),
log(2 (lll00)
A(To-) ) S
(2 (TO.) 1),
(34)
n
where
Σ (a(a To (a +1 r r(X,a)
(TT) E
(35)
it assumed that reward is bounded. The term (To) can be large if is small. While a small v) desirable for reducing bias, it can simultaneously increase (TT)) potentially compromising the tightness of the bound. The bounded reward in [0, is needed for the proof of regret bound as R < R for R E [0, 1]. Moreover, the process of tuning in the IX estimator is particularly sensitive.
In equation 34
D.1.5. COMPARISON WITH LOGARITHMIC SMOOTHING
We provide a theoretical comparison with the Logarithmic Smoothing (LS) estimator (Sakhi et al.) 2024
The LS estimator is,
(T) = 1 x
log(1 + Aus(Fa a:)r:),
for Ā > 0. As mentioned in Sakhi et al. 2024 Taylor expansion of LS estimator around = 0 yields,
(x)= VV((T) +
(-1)
1
(wo(x,, a.)r.)
l
Furthermore, the authors introduced,
(wa (X,,X, (X, ))r)²
(T(T) = E
[11 + Xuo (X, AAr))
where in (Sakhi et al., 2024 Proposition 7), a bounded second moment is needed to derive the estimation error bound. Furthermore, for PAC- MAC-Bayesian analysis, the author proposed linearized version,
1 n (a,(2:)) log
År. To (a (2,))
Í-LLN (T)
1+
Note that, the linearized version of the LS estimator is bounded by IPS estimator due to log(1 + x)) I x inequality. Then, for the LS-LIN estimator the PAC- BCCyesss upper bound on the Regret of the LS-LIN estimator is derived in (Sakhi et al. 2024 Proposition 11) as follows,
28

---

See-SSm--xpponttiee Estimator for Off-Policy Evaluation and Learning
0 S ((f.)) - S (=))) 2(KL(Q])P) In(2/6))
An
where S (TT)
[[a p|r
[a]aa] Art [a|xxr)
Theoretical Comparison: The key distinction between the LS estimator and our LSE estimator that we explicitly assume the heavy-tailed weighted reward and can drive a better convergence rate.
In (Sakhi et al., 2024 Proposition 7), the authors demonstrate that under the assumption of bounded second moment of the weighted reward, the convergence rate is 0(1/ (1/vn).
However, if the second moment is not bounded, from (Sakhi et al. 2024) we only know that:
(w(X, 2)r 1 + dw X, A)r
(x())= = IE
min
E
[w X, BB [()(()
we replace (T) with L (X, A)r]
Sakhi et al.
2024 Proposition 7), we get O(1) as convergence rate. In contrast,
our analysis yields a convergence rate of
O(n~=/(--))
for bounded (1 + e)-th moment.
This result demonstrates that assumption is both precise and necessary to achieve the optimal convergence rate for regret under the heavy-tailed assumption.
D.1.6. COMPARISON WITH OPTIMISTIC SHRINKAGE
The OS estimator (Su et al. 2020 is represented as for r 2 0.
Two(ai, v4)) n (a), xz) + Ts.
1 Σ
VoS(TO)
(36)
In (Metelli al.) 2021
Theorem E.1), upper bound for the right tail of the concentration inequality for the OS estimator established, which depends on ( Consequently, this estimator fails to ensure reliable performance under heavy-tailed assumptions, even when the reward is bounded. Furthermore, due to applying the Bernstein inequality in the proof, theoretical results can not be extended to unbounded reward.
D. 1.7. COMPARISON UNDER BOUNDED REWARD ASSUMPTION
In this section, we compare different estimators by assuming bounded reward. Note that, under bounded reward assumption, R E [0, Rmax], our Assumption 5.1 would be simplified follows,
Assumption D.1. The Px & (A are such that for all learning policy To (A(X)) e ILg and some E [0, 1]. the (1+ +)th moment of the weight function is bounded,
E (T)())) (wo 1t9 $ K/o
(37)
Note that, under Assumption D.I our theoretical results hold by replacing with v., Bl+e In the following, we compare main estimators, PM, ES, IX, LS and OS with LSE under Assumption D.I
The PM estimator provides an upper bound on concentration inequality under Assumption D.I However, lower bound on estimation error (concentration inequality) not provided. Furthermore, for 0, we can have a bounded upper bound estimation error. However, (Metelli al. 2021 Theorem 5.1) infinite for
Note that Metelli et al. 2021), the authors consider E (1,2) where a = + and E (0. 1).
29

---

Log-Suu--Exponnttia Estimator for Off-Policy Evaluation and Learning
The ES estimator, does not support Assumption D.1 and assumption bounded Furthermore, the convergence rate of the estimation bound on the ES estimator is worse than ours c = 1.
Te for a (0, 1) is needed. "n
For the OS estimator, the bounded assumption on the third moment of the weight function needed. Therefore, it does not support Assumption D.I
The theoretical results for LS estimator do not need bounded (1 + e)-th moment of weight function, Assumption D.I not derive the optimal rate of regret, OnnTr) for E [0,1] under LS
However, under Assumption D.1 estimator.
For IX estimator, using the upper bound regret in (Gabbianelli et al. 2023 Theorem 7), requires bounded Co(TT.) ), which can impose stronger condition than Assumption D.I
D.1.8. COMPARISON WITH THE ASSUMPTION SWITCH ESTIMATOR
The switch estimator introduced (Wang et al. 2017) adaptively chooses between model-free estimation and an estimated reward function based on importance weights. While (Wang al. 2017) requires the existence of finite (2 + ē)-th moments (for 0) in their Assumption 1, our work operates under weaker condition. We only require bounded (1 c)-th moments for some E [0, 1]. This distinction is significant-our assumption (Assumption 5.1 encompasses cases where the second moment and (2 + 2)-th moment for ? >> 0) do not exist. In contrast, (Wang et al. 2017 Assumption 1), which requires the finiteness of the (2 + E)-th moments, imposes a strictly stronger condition on the underlying distribution. Therefore, we can
not apply the approach in (Wang et al. 2017) in our case.
D.2. Proofs and Details of Regret Bounds
Lemma 5.2 (Restated). Consider the random variable 7 For E [0, 1), the following upper bound holds on the variance of ex for À < O,
V (e²2) 1
(38)
Proof. We have,
fh AC1
Ae
leAZ -x01|=
dy
|^(= - -CjleCeeexxxxa.CCC S <|al|= Cil.
Then it holds that
v(E
min
E' [(e^z - -0001
= min LE' [le> - AG 1- - ccctptto]]
CiER
CiER
min EE [|e2 1 10 GG Cc
CieRt
< min E [[|]1 - -illt0 S |I| E(121t)))
CIER+
where the last inequality holds due to the fact that Je^Z - A0 1- 1.
Furthermore, we are interested in providing high probability upper and lower bounds on Esst((Te),
P(Estx(Tg) > (6. A)) < 8, and, P(Estx(Te) < g 6. A)) - 8.
where 0 < < and is the number of samples in LBF dataset. We first provide an upper bound on estimation error.
Theorem D.2. Given Assumption 5.7 with probability at least then the following upper bound holds on the estimation error the LSE for learning policy my E To
4|x|2tep log(2/0)
1og(2/0)
(TT) S
VA|Ev 1+
X
ncxp(2Xul/(1+e))
33 3>exp(\ul/0=o)m)
30

---

Log-Sum-Exponentee Estimator for Off-Policy Evaluation and Learning
Proof. To ease the notation, we consider X) (A, Using Bernstein's inequality (Lemma probability (1 5), have,
B.4 with
Σ ex)(AY(44, 4V(exp(AY(44x))) l2g
1lg(2/6))
Elexp(AY((A,)))
3n.
Using Lemma 5.2 \(exp(AY((4,x))) = | 1 we have,
Elexp(AY6(A, exp(AY)(a,,zz)) 4|1|2 log(2/0)
4 4log(2/6)
3n
As the log function is an increasing function, the following holds with probability at least (1 8),
4|11 +
4 4log(2/8)
Lsc (S, (S, 2 X
log B(cAYo(A.X]] +
3n
where recall that V Lss (S, m8) & log (+ - exp( (as, With probability at least (1 8), using the inequality log(æ + y) S log(x) + // for > 0,
V Lae (8) 2 x
1
log (1
+ 4 4/ 12g((20))
(2/5)
3n
(E(e\V((A.x))) + XB[edVo(A.X]]
1
4|1| + v log(2/8)
4 log(2/5)
log
Using Lemma B.11 we have with probability at least (1 - 8),
V Lan (S, > (()((A
1+6 (Y XX,
4|11 1 log (2/6)
4 1og(2/5)
XE(eA1((A.1)
3AIE ee (1,
n
> (|
(V (1, (A, 11
I
4| log
4 log(2/5)
XB(e2Xo(d.X)]
3AR l (Y.
n |||*++
4| loggt/))
4log(2/8)
2 E
Ite
X
nexp(2Aul/(tto))
+
33 3Xexp(Aul/(tc))m
The final result holds by by applying Lemma B.10 to E AAAXX))) 2 exp()ul(1too).
Next, we provide a lower bound on estimation error.
(2) イマ) log then there exists y E (0, 1) such 72 oxp(2
Theorem D.3. Güven Assumption 5.1 and assuming that with probability at least 8, The following lower bound on estimation error of the LSE a learning policy ag E Tlg holds
1|x log(2/6)
4 4log 3(1 - 7) exxp exxp(((u
Esta (TO) 2 X(1 7) V nexp(2Xul((4eo)
31

---

Log-Sum-Exponentie Estimator for Oft-Policy Evaluation and Learning
Proof. To ease the notation, we consider X) (X) Using Bernstein's inequality (Lemma B.4 with probability (1 5), have,
1 n
(V(exp(AT64,, log(2/6) 4 log(2/6)
7 Σ
oxp(AYo(a,,zz)) S
n
3n
Using Lemma 5.2
7(exp(AX((4,x)) & | , we have,
4|A|= log(2/0)
llg((2/))
E (44x - Σ ex)(AY S
3n
As the log function is an increasing function, the following holds with probability at least (1 - 8),
Lsn (S, (8) - x log B(CAYs(A.X]]
1
4/ log(2//)
4log(2/6)
3n
where recall that A (S, = log (+ Ei exp()yo(a,xzi))
Without loss of generality, we can assume that,
4|1 logg(22))
4log(2/8) =E(cAV((A.31]
(39)
n
3n
for some 7 (0, 1). Using the inequality log(z y) 2 log (2)
2 for y > and assuming = EleAVo(4.))) and
y
4 1 (2g(2/6)
log(2/5)
3n
and combining with equation then with probability (1 - 8), we have,
VA 180
(S, TO)
- x log
Eleavo(A.X]]
-
4 4|1 log(2/6)
4 (208(2/8)
3n
4 + log (2/8)
S log
[E|
A(1 - (
n
4log(2/0)
(1 733 (AYGAAXAA)
Equation 39 can be considered as quadratic equation in terms of Vn
Then, using lemma B.6 have,
(2|A|1+< + (7) log(2/0)
S
(40)
72 (1xp(2)x/(++
Using Lemma B.11 with probability at least (1 1 5) we have
a ( (S, TO) & [A,
1
2 log(2/0)
4 1og(2//)
X(1 E(eAA(()))] < [[
n
3(1 7)
1
4| 2 +t log(2/0)
4 1lo(22/0)
(1 - (lee))E(
"
3(1
[
4log(2/5)
E|,o(A,
X(1 - x)
(exp(2Xul/(tte)
3(1 3(1-o)XexpAAo/(t4e/))
The final result holds by applying Lemma B.10 E(cAx(( 2 exp()u!((tto))
32

---

Log-Sum-Exponentia Estimator for Oft-Policy Evaluation and Learning
Using the previous upper and lower bounds estimation error, can provide upper bound the regret of the LSE estimator.
Theorem 5.3 Restated). For any (0, 1), given Assumption 5.1
assuming finite policy set [Tog] < ec and
1o) with probability at least (1 8), the following upper bound holds the regret the LSE
32 expp (xpp(2At)( estimator,
log 4T o 3(1 - -2) nd (AAep(xul/(+t)) 1 +
(2 22-7)
4|A|++ log 1|1Ta
0 S RA( S) S)
v
(1-
(exp((2x1/(1+0))
Proof. We have,
V(To-) (TTT) = ((To-) V Lse
(S, (S, TT.
+ V.A LSE T0-
V. (S, mT))
+
V.
LaB (S, TT) -V(TT)
(41)
13
Using upper bound on estimation enror, Theorem D.2 and union bound (Shalev-Shwartz & Sen-David 2014) with probability at least 1 - 6, the following upper bound holds on term 41
V VTTT-) V Vi (S, TT-)
< sup V (TT)
V (S, mo)
me Ele
(42)
1 4/ log()1/])(( (og((2[1l//6)
A/
X nexp(2Aul((4te)) 3Xexp(\u\(1=0))
I+E
Using lower bound on estimation error. Theorem D.3 and union bound (Shalev-Shwartz & Ben-Dave 2014), with probability least 1 1- 8, the following upper bound holds on term 13.
Vi Lse (S, mT) ((TT))
VA LEE (S, TO) ((Ta)
sup TeElly
(43)
[og(2 A(1 - 7)
-1
4 log 2 TTl/8)
ncxp(2Xu1/(4tr))
3(1 - (xx))))xx(ee//(t)))
Note that the term T2 is negative the Ta is the maximizer of the LSE estimator over Tlg. Combining equation 42 and equation 43 with equation 41 and applying the union bound, completes the proof.
In the following, we provide full version of Proposition 5.4
(2x+ $7) log 72 exp(2p
Proposition 5.4 (Full Version). Given Assumption 5.1 for any 0 < 7 < 1, assuming >
and setting = -n for Ç E Rt, then the overall convergence rate of the regret upper bound is max(O(n=11))) ((n (c---)11)2) finite policy set.
Proof. Without loss of generality, we can assume that X 2 -1. Therefore, we have |A|1+e < and v 1/(+t)) 2 0, which (2++57) log 1 (2)x) ut 47) log
results in 2 expp 20171 oy
Using Theorem 5.3 with probability least (1 8), we have
2 exp(2Xul/(t1o)
RA S)
< |A| v 4(2 - log 4|m
(2 -3-7)
4|>|++ log 4|lTal
(44)
1 3(1 7)) nd exexp(2u (1-7)A}
eexp(2X
< a 4(2-7) log 4
(2 7)
4/21=e v log B
4|Taa
(45)
+ 3(1 77) nn mxcxp(Xu1/(+0))
(1 - 71 exp( (oopp(///(11+))
71
33

---

MoggSSum-Exponennn Estimator for Oft-Policy Evaluation and Learning
Since À 2 -I, have exp(Ael/(at)) 2 exp(-ol/((+)) (note that p2/(+t)) 2 0 and -1 < X < 0). Replac-
ing À with X -n- and exp (Aul/((+e)) with exp (-ul/((+e), then have the overall convergence rate of max(O(n=<5) O( -t ((n(-(-11/2)).
D.3. Proofs and Details of Bias and Variance
Proposition 5.5 Restated). Given Assumption 5.1 the following lower and upper bounds hold on the bias of the LSE estimator,
(n 1) ((d s (S TO)) S 1
1
u ((edua(A,X)B))
2n|2]
2nd
Proof. In the proof, for the sake of simplicity of notation, we consider Yx(A, = (Al For the lower bound we need to prove the following,
V (TTO) E
V 1.8m
(S, mO)
2
1 V (mmo(A.))))
n//|
Setting yo(a, (a;; xz4 rawa(a; 24), according Lemma B.7
for b f(z) = log (x) + 2²²² is concave. So have,
Ei
Ave (a (1))
(a).e)))))
1
n
log
log
n
2
n
n
yo (a))
1
Σ (ar.e))))))
2n
Hence,
Li=l (vo((a))))
E
log
E
yo (ai, 2ii) +
(0,
1
v
Avo(a 27
2nd
2X
Σ
1i=1 e
27
E
-E
2A
n
1
-i= e (x
=E(Y(A, X)]
E
E
27
1
v (<Nvo(..))
E [csraca.o3] 2)
EE(Y(A,
1F
2A
n
-EYA(A,) +
72
V
(2)1644:8))
2nA
Note that (4, = V(To).. It completes the proof for the lower bound.
For the upper bound, we need to prove the following
1
V(e AwalA.))
1 log B [cAYo(A.))))
[aa Lau
(S, mT)
(46)
2n
34

---

SargsSum-Exxponee Estimator for Off-Policy Evaluation and Learning
Note that, an upper bound on Dim Anring (o
holds. Now, we have,
E V
(S, _o]]
1
log
-i=1
ANo(as
72
-i=1 Aualare
Lim1 (xvo(ar))s))
1
2i== (xoo(a),
27
E
log
+
n
n
2
n
Lim eAyu(ariai)
Li= (dyolara))))
Σ ev (aaitt)) 27
2
log
E
B
2
71
92
1)
Σn
eAvolan,as)
log
E
V
2A
log
E
v
(eATo(A.x)).
2nd
where the first inequality is derived by applying Jensen inequality function
E
+ Di= (uvo(aaan)) 2
log
which is concave based on Lemma
B.7 for b 1. Then, we have,
log
E [x)o((1))))
E V LSE (S, mo)] S 2nd
& (e)ro(A.2)).
Finally, we combine the upper bound in equation 46
1 x log [ [<AV((A)))))
1 v (cAV((A2)).
E E Lee (S, mo)]
2
2nd
and the upper bound in Lemma B.11
log E (exo((AA)))) 2 E[
1
I+e
Therefore, we have,
B 180
2
1+c (4,
(47)
(cdmv(d.33R))
2nd
completes the proof.
Proposition 5.7
Assume that (A( ()))) < v2 (Assumption
5.1 for 1) holds. Then the variance of the
LSE estimator with X < 0, satisfies,
1 (WW
1
V(VA LsE (S, mO))
U2- n
(48)
n
Proof. Let YA,A, X)= = (A, R and y(e)
Yo(A, E[Yo (A, be the centered Yo X), We have,
DA In LsB (S, TT)
En edvi,o
1 In
Σn Atv?3 mo)
1
In
Σn
+ mg
n
where my E[Yo(A, X)).
Note that, we also have V(y(())==
=V(())
35

---

SuneSSu--xpoontiia Estimator for Off-Policy Evaluation and Learning
Now, setting Z Eis 1,
we have,
(1 log log&) Z
v(Vis (S, To))
Furthermore, using Jensen's 's inequality for < O, we have,
- i==1 Mi.0
log Z
n
Hence we have,
log 2 2)
V(V.
= (S,
LSE (S, mD)
log² 2 7
E
X²
(c)
27
i=
Vi
<
Σ 1= V1.0
(c)
(c)
Vi.8
+
n
n
(c)
E Vi.0
Y (c)
+ E
n
ii 1 Vi.0
+0
n
()) 1
V(Yo).
completes the proof.
For the moment of the LSE estimator, we provide the following upper bound.
Proposition D.4 (Moment bound). Given Assumption
5.1
the following upper bound hold on the moment of the
LSE estimator,
Σ
cdwolaraiir 1tc
E
log
S v.
(49)
Proof. Suppose that Z Eis e ( have,
Also set yi,o(a,, xx:) re(a;,2;)up0(0 For negative À 0 and Z > 0.
Vi (S, mp) = log Z)
LaB
Σn 1i (a;
Since log 7 < for < Z < 1, we have,
lte
1
ww (ai, 2;)r: 1+t
E
log Z
< E
i=l
E
Bllwa wa (A, X) [+]
14
where the second inequality holds due to Jensen inequality.
36

---

Log-Sum-Exponendte Estimator for Off-Policy Evaluation and Learning
D.4. Proof and Details of Robustness of the LSE estimator: Noisy Reward
Using the functional derivative (Cardaliaguet al. 2019), we can provide the following results.
Proposition D.5. Given Assumption then the following holds,
log(Ep, (exp(xexxxxxx)))]))
(ox(Ees/exp(Auua(A, X)))
TVc (PRX,AA PRIX.A)
exp((\/6t/1ate)) - -exp(p//pt/
(50)
X2
p2/(1+e) w1/(1te)
where P1 Px & (A @ Pax.AA and P2 Px & mo(A)) @ PRIXA.
Proof. We have that
log(Er, (A,)())
!. JRXXXA A (exp(Xeep
JENARA
exp(Aweg (x,(Awo(A,XX)4 (t)
Px & ( PRIX, (dxdxdddaa
(wwp (A, X) R)]
TVc (RIXAA PRIXIA)
(51)
(A, R) dy
Ep, (exp(Ao
(xp((A|///(+00)) ( cxp((A111((1tt)) D1/(1+e) w1/l1+e)
2 P
X
where P. = Px 8 (A & (PIX.A + (PMIX. PRIx,.)),, (a), (b) and (c) follow from the functional derivative and Lemma B.2 and censen-inequaliy
Combining Proposition D.3 with estimation error bounds, Theorem D.3 and Theorem D.2 we derive the upper bound on the regret under noisy reward scenario.
(2aas2 1s log log mal
Theorem 5.9
Given Assumption 5.1 Assumption 5.8 and assuming n
with probability
7 exp(2Xe'/
at least (1 6), then there exists E (0, such that the following upper bound holds on the regret of the LSE estimator under noisy reward logged data,
|1
0 (Tg( s 1
4(2 7)
log Mel
(2 7)
4|||+++ log Alll
3(1 7) nd e (1)
(1 7)X V
eexp (2X5
eexp(A/p2/114e)) - -exp(()p2//11=)))
2TV ( PRIX,A)
2²
-0/00-)-111000
where TT(3)= = arg ma VA (18, 5).
Proof. We have,
(TT. ) - V (TT( = V(TT.) - VA
LaB (3, (T.))
V.A (S, np.) - VA V. (3, T&a ())
(52)
V 1.sm (S, (5,5)((5) - V (TT((S))
1n
37

---

Log-SSum-Exponentee Estimator for Off-Policy Evaluation and Learning
Using upper bound on estimation error, Theorem D.2 and union bound (Shalev-Swwartz & Ben- David 2014), with probability least 1 5, the following upper bound holds term I,
(TTe)) - VA (S, TT-)
V(TTo)
log(EA (A,
1 log(Ers (exp(Awa A, Ri)) RR)))) - x log (exp(Awo R)))
1
1
(S,((S
(53)
1
1
TV (PRXX. PRIX.A)
-
4 (lgg(2116o/8)) nexp nexp(2A51/(1t0)) 3Aexp(Xe1(0to))))
Using lower bound on estimation error, Theorem D.3 and union bound (Shalev-Shwarz & Ben- David 2014), with probability least 1 5, the following upper bound holds on term Iz.
(3,, Tzl (5)) V (S)
1
Lan (S, TT (S))
ā log (Bg(E,, (exp(Aug(A,X))))
log Bss (exp (A A, R))) - log (Ep, [exp(AuggA, R))))
x
+ X log(Ep, (exp(Awg(( (A, - (5)(
(54)
-1
log
4 4
X(1 7)
mexp(2A61/4tt))
3(1 7) (xxx))))xxxxxttttx0
TVc(PRIX.A P PRIX.A) (xxp(lpp//att)) exp (xp((x X2
- 1/(+c)
Note that the term 12 is negative as the ( is the maximizer of the LSE estimator over 1lg. Combining equation 53 and equation 54 with equation 52 and applying the union bound, completes the proof.
D.5. Data-driven selection of A
In Theorem 5.3
we assume a fixed value of A. However, it is often important in practical applications to have a method for adjusting À dynamically based on the data.
Recall the following regret bound proposed by Theorem 5.3
+ 4(2 - 7) log
exp([)|u
RA 8) <
+
3(1
n A
(2 -777 7)
4 4|x|1+c 1+
log 4|la 3
cxp (xp(2/\/p1((14))
(1 >>
n
which is true for any y. y tends to zero, we have,
|I 8 (exp((X111(1tt))
log
AllLal 3
2
4|
4لlاa 3
exp(2)x\p\/(+e)
8)
1te 3
n|
38

---

Logg-Sum-Exponentee Estimator for Off-Policy Evaluation and Learning
Let the upper bound be Up and Vulttte, We have,
8
Sutte exp(xtiz) log 4
4v log allاl exp(2rTi2)
Ur
V
+ 2
(1+ cccuit
3
n1.
n(x i y vite) 1--
(55)
x
Sep((1 x::
log 1
4og
1|lba
exp(2x Tमx)
+
+ 2 8
6
(1+c)
T2. Itf
n1.
Finally, we assume that | S 1 and bound and replace the exponential exp(x ) by e. Minimizing the upper bound in equation 55] we derive the following optimum À for the optimization of the upper bound in Theorem 5.3
AD max {
(1)
-f(c)-
(56)
where [e) = - [(l++t (1 + v (1 2)2 +
Be 3a(1+c)
Note that, we can compute the empirical value of y based on
the available LBF dataset,
(wo x:)r:) (w)r)
1+c
(57)
11
Using empirical ú in equation 56 derive the value for data driven A. Note that, in experiments, consider 1. Data-driven À under noisy reward: As discussed in Section 5.4 we can also derive data-driven under noisy reward for asymptotic regime, where n - oc. For this purpose, we need to solve the following objective function,
arg min | xE(-00.0) I+E"
2T PRIX.A) exp(())2\/a+t)) - exp((X|=2((te)) D1/(++)) -177)--1110 =1((1tr)
X2
To solve this objective, the following estimation,
y
which is true when æ and y close. Using this estimation, replace the term (o([M))//0+0)-xxx//p (xppp [|)+)/(++
3 ppt/((4)) with
[}] exp((\|22/(++))) and estimate v with D, which observed from the data and we get a simplified objective function as,
arg min Al D xe(- 1+c
2T 2PRI.A PRIX.A)
AND
exp(11/2/(++0))
(58)
[A]
We further studied the performance of data-driven selection in App. G.7
D.6. PAC-Bayesian Discussion
In this section, we explore the PAC-Bayesian approach and application in extending our previous results. Given that the methodology for deriving these results closely resembles our earlier approach, we will outline the key steps in the derivation process rather than providing full detailed analysis.
For this purpose, we introduce several additional definitions inspired by Gabbianelli et al. (0023). For the PAC-Bayesian approach, we focus on randomized algorithms that output a distribution Qn E P(Iss) over policies. Our interest lies in performance guarantees that satisfy two conditions: (1) they hold in expectation with respect to the random selection of in ~ Qn. and (2) they maintain high probability with respect to the realization of the LBF dataset. For this purpose, we define the following integral forms of our previous formulation,
39

---

See-SSS-Exxpoontee Estimator for Off-Policy Evaluation and Learning
V(Q) / V(Ta)dQ(Ta) V LSE (S, / (S (T)
(59)
R(Q,5) / R(T, ()QTT))
These expressions capture relevant quantities evaluated in expectation under the distribution Q E P(1le) where P(llg) is the set of distributions over policy set. Let IP (P(Il)) a prior distribution over policy class.
We can relax the uniform assumption on (1 + e)-th moment Assumption 5.1 as follows,
Assumption D.6. The reward distribution PAx,A and Px @ (A(X) are such that for posterior distribution Q over the set of policies Hy and some E (0, 1], the (1 + +)-th moment of the weighted reward is bounded,
(wg ((0g #1 S V/-
(60)
In order to derive the upper bound on regret, we need to derive the upper and lower PAC-Bayesian bound on estimation error. For this purpose, we can apply the following bound from (Tolstikhin & Seldin 2013 Theorem 2) which holds with probability 5 and for a fixed cj 1,
Elexp(AYo(A,x))
exp(AYo(ar,
TaME
m n
(61)
(e (e- (e (KL +n
$ {1+
n
where Ya(a, 22) wa(a; rr and
1 Inc
(V
((-e2)) 2)n
In
4lm(1/0)
+1.
(62)
Similar to Theorem D.3 and Theorem D.2
we can replace (cxp(cx(AYY X)) with EY)4 Given Assumption D.6 the following upper bounds holds on estimation error,
1
(1+ (e - 22 [KL + In 20
(xo~g(EstA(TO)) < Ite 1
exp(2Xun 1/11+c) 8
(63)
For lower bound, given Assumption D.6 there exists no such that for n 2 and 7g E (0, 1) the following holds with probability (1 1--0 5).
(1 + c1) X(1 - (1)
(e- 2)|A|2+
E B Est (
(64)
exp(2Av 1/(+e)) n
we can derive an upper bound on R(Q,S) S) in similar approach to Theorem 5.3 under Assumption D.6 and assuming Qn arg max V (S, Q).
Combining equation 64 and equation
63
R( S) < Ite [ll (1 + c2) (2-22-2) - 7g)
(e - 2){ vy (KL(Q)P) +
(65)
- (g)7g)>
exp(2Xv 1/(1+c))
Note that, the PAC-Bayesian approach in (London & Sandler 2019 Sakhi et al. 2023 2024 Aouali et al. However, their PAC-Bayesian model can also be applied to our LSE estimator.
2023 different.
40

---

Estimator for Off-Policy Evaluation and Learning
D.7. Sub-Gaussian Discussion
In this section, we investigate the sub- uub-Gaussianity concentration inequality (estimation error) under LSE estimator. We first present the following general result.
(2++ lox 2 (exp(221/(4411)
log 2 and setting
Proposition D.7. Given Assumption 5.1 for any 0 < 7 < 1, assuming 2 max
log 2
T
X =
in
then with a probability at least (1 - 8) for 8 E (0, 1), the absolute of estimation error of the LSE estimator satisfies for fixed we llg.
(
4
1 log 2 Ifc 8
Estx (TO) - l+te (1-?) exp((1/((0))
Proof. Choosing n 2
20og 3
we have X 2 1, Da|t+e s
and
2 0, which results in 2
(20+ +r) log exp(2utte)
(2|x[=1<<+) log 3 e2p
Using Theorem D.2 and Theorem D.3 we have with probability at least (1 - 6),
Estx (TO))
1
4| log(2/5)
4 4log(2/8)
$ 1+E
X(1 - 7) V n (Xxp(22el((tte)) 3(1- - 7) (xxp))/xxxxxxx/((tt000 Al
(66)
Since A -1, have exp(Aulte) 2 exp(-utt:)) (note that 2 0). Replacing À with X exp (Aulte) with exp (ul+e), have,
log 3 pm
and
log 2 ifc 4
log 2 - n
l
n
3(1 7) exp(vl/(++0)
2
2 llog 3
(1 - 7) exp(vl/((+e)
n2
log
If=
+
I+E (1-7) explvl((++)
n
with probability at least (1 5). As the upper bound on absolute value of the estimation error holds.
Remark D.8. Suppose that the second moment of weighted reward is bounded which is equal to Assumption 5.1 with e 1. As result, using Proposition (.riitioonDDFffff for = 1, we can establish concentration inequality (estimation bound) for the LSE even in cases where the rewards unbounded.
D.8. Implicit Shrinkage
Su et al. 2020) proposed the optimistic shrinkage where the weights are less than the main weights of the IPS estimator. Other transformations of weights in other estimators are also lower bound the main weights of IPS estimators. For example, in TR-IPS, we have min(M, =)) which is lower bound we (a, x). Our LSE estimator is also lower bound to the IPS estimator,
X log
Σ exp(Aue(a,, x. )))r)) <
we wa(a, D.)r..
(67)
which can be interpreted as implicit shrinkage. Furthermore, note that the LSE is not separable with respect to the samples, so instead of per-sample shrinkage, we investigate ISEE' shrinkage effect on the entire output, which is the estimated

---

Log-Sum-Exxpnenne Estimator for Off-Policy Evaluation and Learning
average reward. It can be derived by simple calculation that for O,
1
Ei=1
A |
DKL (211m.. "", softmax(Ays))
log
where 1, is all-one vector with size n. Hereby we see that LSE shrinks the Monte-Carlo average by the KL-divergence between the uniform vector and softmax of the samples (with temperature 1/A). This way, when outlier values or large values are out of the normal range of the data are observed, the amount of shrinkage increases. Also when the variance high or have heavy-tailed distributions, the softmax of xy; goes further from the uniform vector and more shrinkage applied.
D.9. Robustness Discussion
In this section, we study the convergence rate LSE estimator under m outlier samples. Without loss generality, assume that PRIX,A- n+m PRIX,A A n+m Pno, where PRo is the distribution of outlier samples. Then, we have
TVR(PR)X.A: PRIX,A)= = / (PRIx.a(F) - PRIX.A(())(l
(68)
m
[ [Pnxx,(tr) - PRO
(69)
m
< m
TVo(PRIX.A. PRO)
(70)
2m
(71)
Note that D) cop(Aipp/ctt))-xxp/M
0(12)) Therefore, we have,
01/040-p1/000
2TV PrIX.A) ((0,)) -20))~((())) ~0 2m
X2
[>](n + m)
(72)
Choosing On we have the overall convergence rate of max (O(m=s/(++)),, 0
2mn 3mmn/((+))
))
Note that, for
n+m
m = and large enough n, we have the convergence rate of OO ((n=e/(1+)))
D.10. Relaxing the lower bound on in the regret bound
We can relax the lower bound on by selecting y appropriately. The lower bound on n, given > 0, becomes equivalent to the following inequality of 7,
B + / B + 4An
N
2n
2 1s log mml
log Mal exp(2x01/0=o))
where A
100((2u1/0-01 and B
B + VBa + 4.An
1>
2n
existence of such a is guaranteed. This is equivalent to,
Tp (2)x () log 5
exp (2x(())
Hence, setting B+ B which is O 2n
vn results in a lower bound on which is independent of y and is weaker
than the original lower bound for any 7. This only changes the regret bound at most by a constant factor since 2 2-7 < 2
and 1- 0
O
0(1), and remove the dependence of the bound on the extra parameter 7,
42

---

LeisSuun-Exponetiil Estimator for Off-Policy Evaluation and Learning
E. Robustness of the LSE estimator: Estimated Propensity Scores
In this section, we study the robustness of the LSE estimator with respect to estimated (noisy) propensity scores.
To model the estimated propensity scores, we consider To(alz) as the noisy version of the logging policy zo (o(a))) Similarly, we define V (5, mT) for the LSE estimator on the noisy data samples S, with estimated propensity scores. In this section, we made the following definitions.
Definition E.1 (Discrepancy metric). We define the general discrepancy metric between Bh (A, X) and wo XR with bounded + e-th moment as,
dx Ügg (A, un (A, == ( wa (A),
(73)
Definition E.2. The log-sum error of the noisy (or estimated) propensity score mo (a) .r) is defined as
A (mo: mo) = log Ep, (exp(A X))) - log Ep (A,
(74)
where (),
[x(A and where Pj Px @ No (A(X) & PRIXAA- [x(A
Definition H.2 captures notion of bias in the noise that is applied to the propensity score. It indicates the change in the population form of the LSE estimator. Similarly, for the Monte Carlo estimator, the change in the expected value shows the bias of the noise, and for additive noise, the zero-mean assumption ensures that in expectation, the noisy value is the same as the original value. For the LSE estimator instead, we require the exponential forms be close to each other. is also inspired by influence function definition and robust statistic (Ronchetti & Huber 2009 Christmann & Steinwart 2004).
We made the following assumption estimated propensity scores.
Assumption E.3 (Bounded moment under noise). The reward function r(A, X) and Px are such that for all learn- ing policy (A()) E TT. the moment of weighted reward is bounded under estimated propensity score scenario, 0 ( [( ( (A, X)) < D.
Remark E.4. Under Assumption E.3 and Assumption 5.1 and using Lemma B.10 it can be shown that the discrepancy metric in Definition
E.1 is bounded,
2/1+e) I drro (og X)R, (A, S 22/(1-))
(75)
We define the achieved policy under the estimated propensity scores as
TT(S)
arg max VA Le (8, no). T
In order to derive an upper bound on the regret under the noisy propensity score, the following results are needed.
Proposition E.5. Given Assumption 5.7 and Assumption
E.3
the following upper and lower bound hold on
A (To; TT).
1A/5D < S.n. (fu, To),
d (wo (A, (,
1+e
and,
[N/.v
A n0 (To,
To) < Itc
+ d (0 (A, (A,
Proof. It follows directly from applying Lemma B.11 to I log Ep, (Ax) and & log Ep, (exp(Axx(uu (A, and combining the lower and upper bounds. Then, we have,
W
[[(wa(A, A, X)= ())
1+6 < Ano (Tt, TO) <
+ E (A, wo(A,
1+
43

---

Mogg-Sum-Exponenin Estimator for Off-Policy Evaluation and Learning
Proposition E.6. Given Assumption
F.3 and assuming n
3 3/omn +4 log 3 Pmnn
where
Pmin
min ( abelaal)). then with probability at least (1 - 5) for a fixed va E Hg we have,
[ Lan (S, TTO) - V.A. Liw (S, TO) AT (To, To)L 20(d)
(esouaro)) edalaac
where, u(6)
log 1
+
log
3n
Proof. Set X) = we X),, (A) wo (A, un 3 (e -ehi-eh e (i) and vs (e00(0))))) - pd), where = (A. We have Then, using the one-sided Bernstein's 's inequality (Lemma B.4). and changing variables (Lemma B,5), we have:
H 3 and ( < ui S 5
civing (R0i
(1 (1- (1-1)
(1) log
V/ (eAVolA.X)) log
P
- - -((AX((A))))
n
log
y (eAKo(A.X) log 2
IP
Auo (...))) - [((ANo((A.))
3n
(1 (1-e cd (Ro. mo 1 log
V
(eAPolA.3) log
P
Al A (1.0
B
8,
3n
i=1
(osFola,x) log
ed (Ro. (R..0 log
P
e Ai
AY((..)) <
3n
Therefore, with probability at least 1 - 25, for < [[(d)E(d,,)) we have,
V
(3, TT)
V.A (S, T8)
LSB
7 log
Addoo (Fo00o) +21
<
log
E[edYolA.N)] 22
1 logg
de Elc + vi) - log [B(cAt(AA.2]] U22
-log
V1 log (2)2 Ele ((c + -0 (A.
log
22
Eleddood..))] -
V1
200 EledXo(A.X]]
ATO (To, To) +
2
11
U2
( TO)
+
Ele2Vo(A,X]]
44

---

Seu---umm---ptttii Estimator for Off-Policy Evaluation and Learning
where
V (esPocaxx)) log 1
(1 E(eAFo(A.X)]) log
v1 =
3n
BleAYald.X)]
log
V (edvo(A.))) log
U/
+
3n
Similarly, with probability at least 1 - 26 we have, given U/ < B[ee
V. (S m0) Visee (S, 2 ATo (To: TD)
2
v3
LSB
X [[.2)E(AA.3)] Ble2vo(a.3]]
where,
(AA)P log
(eABocA,)) log 4
03
3n
(1 E Ele (Yo( log t/
(odYolAA))) log
3n
Therefore, with probability at least 1 - 48 we have,
A (Tu, np) A [FeaAPod.x3]] +
Uy
V.A Vi xo)
(0)) - -VA VS, m8)
E[c2xo(A,3))
2 x
21
U2
< Ano no (50, To) +
+ Elexko(A.X]]
We have for i E [4],
log 2
log 1/2
0/ 5
+
3n
So, replacing 8 with 8/4, we have with probability at least (1 - 8).
VA LsB
(8,
V.A
LSE (S, TT)
Aoo (Tro mO)
2
4 log
log 1
1 BlesPo(A.x3] + Ble2vo(A.3]]
0
+
3n
2
log 3
log x
2e @DI/CO+)) edulsito)
3n
which is true given
log 3n
+
log 1
1/2 min [[]AAY(A..))] BjcAPo(A.))).
According to Lemma B.6 this is satisfied by
n
3 Panin
+4 4
4 log
n1 >
Puin
8
In the following theorem, we study the regret of the LSS estimator under (S)(S) policy.
45

---

Estimator for Off-Policy Evaluation and Learning
Theorem E.7. Suppose that,
TT(S) arg max V Ella
LaB (5, To):
where S is the data with noisy propensity scores. For any y (0,1). given Assumption 5.1 and E.3 and
3/Homint
1|lbal (a| $1) log ((A
simel 3
where Pmun = min (edu eADi)000))
assuming that 2 max
log
Pmnn
8
the following upper bound holds on the regret of the LSE estimator under Ty(S) with probability at least (1 - 8) for E (0,
2/116 v/ +
|N
( 5) -
1te 1+e
4(2 -7)
log 4
(2 (2-7)
4|||=++ log -
Allb
3(1 7) n2 exp (xxppA////11 (1 7) exx (exp(2Avl/(+te)
(76)
dx (Tgg(A, X)R, wa( A, x)RR + -7 (Tg (A, X)R, (A,
4u (
log $ 3n
log
where, v6))
Proof. Let 0 be.
T5(S) arg max V n Elll
1.sp (S, me).
We decompose the regret as follows,
R (TT: 5)
((T..) V (TT)
-5, Tz)) - V(TT))
(ise(S.. Tz²) + VA Vise (S, mz) + VA LaR (3, (g)
V. VS. mg) + Vi Vi (S, nT)) VAS mT) + VA tsse (S, kQ-)
(S, TT.) + V (TT-)).
Using the estimation error bounds at Theorem have,
D.3 and Theorem D.2 and using the union bound, with probability (1 5) we
VA LeB (S, nT) ( S X(1 - 7) V nexp(2Aul/(4+e))
1
(2g ll)/0)
4 1og(2
(77)
3(1 - (x1=2)Axx(Aul/((ee)
1
(log(2
- (S Tg-)
I+e |\
(78)
\
nexp(2Aul/(tto))
3xexp(Xu2/(0
In addition, using Proposition E.6 have,
20(0/Ilo) [al)
Vil LsB
(3, mT)
(S. Lsx (S, S
To) (TT
(To,
exbiratt exulRa-o
(79)
P use (S. - VA (S, s ArT (To, (To, no) + 20(8/Ilo) [lo))
@Abi/C+o +
(80)
A
@dul/(1-))
46

---

Log-Sum-EExponntte Estimator for Off-Policy Evaluation and Learning
As To is the maximizer of V LsE (S, TO), we have,
V LsE (5.
VA
(3, S 00 LSE
(81)
and as Te the maximizer of V. Lae (S, To) we have,
Lss(S, TT.
V. L (S, mT) S O.
(82)
So putting all together, using the union bound we have with probability at least 8,
4(2 -)) 7) log 4|1Ta
(2 (2-7)
4|111 4/1ba
((TT)) - V(TT=) ) 5
1 + 3(1- 7) ni mxeep(Axl/att))
(1-
nexp(2\ul/atte)
+ ng (To, m0)
Ang (To: To)
2 a|lia|
A eABUCT
where v (3TT11)) Ang (To mo).
log
1811
log
1871
The final result holds by applying Proposition E.S to Arg (To mo)
3n
72
(A in equation 76 can be interpreted as the cost of estimated propensity scores which is independent from n. Note that, we have the convergence rate of O(n O(n-s/(++)) for all remaining terms in equation 76
Discussion:
The term da. ( ())) + da. (A,
In the following Corollary, we discuss that the small range of variation of the noise gives an upper bound on the variance of the LSE estimator under estimated propensity score.
Corollary E.8. Under the same assumptions in Proposition E.6 then the following upper bound holds on the variance of the LSE estimator underestimated propensity scores with probability at least (1 - 8),
(T)) <24(VV Lse (S, TB)) + 2
where =
}
log 1 3n
log 1 V
and B
م + 2لud/(105)
Proof. As Ano (To, To) is a constant with respect to Vi (3, Te) and V (S, Te). then we have,
2Be 2
V(VA LsE (S, TD)
V Lss (S, 5
B²62.
Therefore,
V(VA USE (3,) (8, - DA (8, TT) + VA (S, T8))
-VVA Vis (S, 30) - VA VisE (8, TO)) + v(Vi LSB (S, TO))
+ +2Cov( (3,
(3, TT) - V (S, To), Vi (S. TT))
V(VA LSE (S, (8) PA LSe (S, πT) + V(V Lsg (S, mT))
2 (S, no) VA UsB (S, T0)
VA V (S, To))
V(VA ESE (S, (S, mo))
v(VA Log (8, mo) VA (S. mT)
VVVVV (S, + Be
< (S, TO)) + 22
47

---

Llg-SSu-Exponenni Estimator for Off-Policy Evaluation and Learning
we have an upper bound the variance of the LSE estimator underestimated propensity scores, in terms of the variance of the LSE estimator under true propensity scores. Therefore, if VVVV Use (S, xo) is bounded, then expect bounded V(V).
From Corollary E.8
1.s.. (S, m))).
E.1. Gamma Noise Discussion
For statistical modeling of the estimated propensity scores, as discussed in (Zhang et al. 2023b), suppose that the logging policy is a softmax policy with respect to a.
To (A = softmax(ffr (x, A)),
(83)
where fe is function parameterized by 9 that indicates the policy's function output before softmax operation and 0 is the parameter of this function for the true logging policy.
We have estimation of the function fe- (X, A), fg(X, A) and we model the error in the estimation of so (X, A) as random variable Z which is function of X and A,
(x A) fo- (X, A) Z(X,
Then we have,
To (oftmax(ff(XX,4l
softmax( fe. + Z)
x e² mo To-
Motivated by Halliwell (2018), we use negative log-gan -a-gaama distribution for Z, which results in an inverse Gamma multiplicative noise on the propensity scores. Negative log- gamma distribution is skewed towards negative values, resulting in inverse gamma noise on the logging policy which is skewed towards values less than one. This pushes the propensity scores He towards the higher variance, i.e., the logging policy near zero and the importance weight becomes large. No
In particular, we consider a model-based setting in which the noise is modelled with an inverse Gamma distribution. We use inverse gamma distribution I/U as a multiplicative noise, so we have,
uo = U To + Te (A. = (A.
which results in multiplicative gamma noise on the importance-weiggted reward. We choose U Gamma(b, b), so U = 1. Hence, the expected value of the noisy version is the same as the original noiseless variable.
U wol (A, (A, X)R = EEU]E[wo (A, X)R) = Elwo (A,X)) XR)..
Note that we have
E Amm(AA
EE
(T-Xool Xwoo A, X)R/b
Therefore, EleAUws(A.X)) converges to Eledwo(A for b
Furthermore, assume that for large value b, np (To, To) R 0 and using Proposition E.6 with probability at least (1 5), we have,
V Law (3, TT)
A (S, m²) S < (EEEAEOOAA))) +
(84)
B(eAAu(AxX)R)
The impact of inverse Gamma noise on the ISE estimator constrained when the noise's domain sufficiently small. This property ensures that the LSE remains relatively stable under certain noise conditions. Furthermore, we can reduce the deviation from the original noiseless LSE by increasing the size of the Logged Bandit Feedback (LBF) dataset. This relationship demonstrates the estimator's ''s robustness and scalability in practical applications.
48

---

Se----mm-ppponttii Estimator for Off-Policy Evaluation and Learning
Table 7: Statistics of the datasets used in our experiments. For image datasets the 2048-dimensional features from pretrained ResNet-50 are used.
DATA SET
IPS-TRAINING SAMPLES
TEST SAMPLES
NUMBER OF ACTIONS
DIMENSION
FMNIST
000000
10000
10
2048
EMNIST
60. 000 12,530,806
10000
10
2048
KUAIREC
4.676,570
10,728
1555
F. Experiment Details
Datasets: addition to dataset EMNIST, we also run our estimator over Fashion-MNIST (FMNIST) (Xiao et al. 2017)
Setup Details: We use mini-batch SGD as an optimizer for all experiments. The learning rate used for EMNIST and FMNIST datasets is 0.001. Furthermore, we early stopping in training phase and the maximum number of epochs is 300. For the image datasets, EMNIST and FMNIST, we use the last layer features from ResNet-50 model pretrained on the ImageNet dataset (Deng et al. 2009).
F.1. Hyper-parameter Tuning
All experiments can be categorised into 4 classes,
Bupervised2aandit OPI.
Synthetic OPE
Bupervised2Bandit OPE
Real-world OPL
From different aspects, experiments have different setups.
1. Evaluation: For OPE experiments, multiple instances of the experiment are conducted and the empirical average squared error of the estimator is calculated as the estimation of MSE. For OPL, a separate test set is used to evaluate the estimator's performance.
2. saper-parameter tuning: Each estimator may have one or no hyper-parameter. For all experiments except Super- vised2Bandit OPE, and the ones that the selection of hyperparameter is explicitly specified, the selection of this hyperparameter is conducted by grid-search. Other Table & indicates the search grid for each estimator. For super- vised2Bandit OPE, for the estimators that provided selection method (PM, LS, IX, OS, TR) we used their suggested value. For other estimators we used grid-search. For ES and LSE we used the following grids {0.0, 0.3, 0.5, 0.7, 1.0), and (0.0, 0.001, 0.01, 0.1, 1.0], respectively.
In order find the value for each eyper-parameter, we put aside part of the training dataset validation set and find the parameter that results in the highest accuracy on the validation set, and then report the method's performance on the test set. In order to tune we use grid search over the values in f0.01, 0.1, 1, 10, 100).
Tuning for PM, ES, and IX Estimators: For the PM, ES, and IX estimators, grid search will be used for hyper-parameter tuning. To tune the PM parameter X, we will use data-driven approach proposed in (Metelli et al. [202)) For the ES estimator, the parameter a will be varied across a E {0.1, 0.4, 0.7, 1}. For the IX estimator, the y parameter will be tested with values in the set {0.01, 0.1, 10, 1003.
F.2. Code
The code for this study is written in Python. We use Pytorch for the training of our model. The supplementary material includes zip file named rl_ without wtw_wttott_wwar...... reward.zip with the following files:
49

---

Estimator for Off-Policy Evaluation and Learning
Table 8: Hyperparameter of Different Estimators
Estimator
Grid
ES
a E (0,,,0.1,,04,0,,111
IX
" 0.1, 10.0, 100.0)
PM
Å (0.0,0.1,..3,0.3333.
OS
T (0.01,0.1,
IPS-TR
M E [2.0, 5.0, 5..0,,0,
LS
À {0.01, 1.0,1, Ae (-0.01, -0.1, -.0, 10.0, - 100.0}
LSE
preprocess raw dataset from model.py: The code to generate the base pre- pre-processed version of the datasets with
raw input values.
The data folder consists of any potentially generated bandit dataset (which can be generated by running the scripts in code).
The code folder contains the scripts and codes written for the experiments.
requirements.fxt contains the Python libraries required to reproduce our results.
readme.md includes the syntax different commands in the code.
aces: A folder containing the result reports of different experiments.
data.py code to load data for image datasets.
eval.py code to evaluate estimators for image datasets and open bandit dataset.
config: Contains different configuration files for different setups.
runs: Folder containing different batch running scripts.
loss.py: Script of our loss functions including LSE.
train logging policy.py: Script to train the logging policy.
train feiirrrrewardddd estimatur.py: Script to train the reward estimator for DM and DR methods.
create bandit dataset.py: Code for the generation of the bandit dataset using the logging policy.
main seiniissemiiaae _ttppi_________ Main training code which implements different methods proposed by our paper. eetirttmie_exeermeettt..e v3.py: Code for synthetic experiments.
motivation.ipynb: Code for motivating example.
OPE classifiifi; The codes for the OPE experiments real-world datasets from UCI repository.
train_on cacl_onnnuiiiii www_uc..ppyn::: Main code running experiments on UCI datasets.
The code for the faulty policy model for the logging and training polices. UCI: The folder containing UCI datasets used in the experiments.
The real_world folder contains the scripts and codes written for Kuai-Ree dataset.
preprocess satroocees_ddtaipyynb.. The code that preprocess the KuaiRec dataset and makes it ready for training.
run_ Awwuurre_eeppriimeeeee
The main code for real dataset experiments. contains the training of the logging
policy as well as the learning policy
eval.py: Code containing the implementation of the evaluation metrics.
To use this code, the user needs to download and store the dataset using preprocess raw hew__daaate__teee www.ffrommoooleoe script. All downloaded data will be stored in data directory. Then, to train the logging policy, the code/train mode/tran__oggiing_eo should be run. Then, by using code/create bandit dataset.py. the LBF dataset corresponding to the experiment setup, will be created. Finally, to train the desired estimator, the user should use code/main code/main_semii_e semi_ot.py script.
50

---

Log-Sun-EExpoentiaa Estimator for Off-Policy Evaluation and Learning
For OPE synthetic experiments, the code Setrretic__exermmeee___ss should be run. For real-world OPL experi- ments, the Kuairec (version 2) dataset should be downloaded and put in real wou__woold/Kuaiee 2.0/ folder and first real_ www_wooodd/ppppoceesss latprooccssssdta.ipppe data.ipynb notebook should be run and then train the estimators on Kuairec dataset. The code itself trains and stores a logging policy before the main training phase. For OPE real-world experiments, the notehook PFF__alassficaaion/raiin Laapaiiioonn_nttttteee onnuci.ipynb would train the estimators on the UCI datasets in the folder OPE [7F_ccassiffcaiion//CI The final version the code is available at the following link: https://githube com/ a armin wwwwaaniaaaaaccc..a.....aa.aa.ae of -earningnnng
code will
Computational resources: We have taken all our experiments using 3 servers, one with nvidia 1080 Ti and one with two nvidia GTX 4090, and one with three nvidia 2070-Super GPUs.
51

---

Log-Sum-EExponnnig Estimator for Off-Policy Evaluation and Learning
G. Additional Experiments
This section presents supplementary experiments to further validate our LSE approach in off-policy learning and evaluation. We extend our experiments follows:
1. Comparison with the Model-bases estimators: We conduct a series of experiments to assess the performance of model-based estimators comparison with our LSE estimator.
2. Combined method: We investigate the efficacy of combining the LSE estimator with the Doubly Robust (DR) estimator, exploring potential synergies between these methods.
3. Real-world application: To demonstrate the practical relevance of our approach, we apply our methods to real-world dataset, providing insights into their performance under real world datasets in off-policy learning scenarios.
4. A Effect: We study the effect of À in different scenarios.
5. Sample number effect: We study the performance of the LSE estimator with different number of samples n.
6. Off--ollice evaluation: We conduct more off- off-policy evaluation using Lomax distribution.
7. Off-policy learning: We run more experiments for off-policy learning scenarios under FMNIST dataset.
8. Selection of A: Different methods of the selection of X, data-driven selection of X and sensitivity of À are explored.
9. Distributional properties: In the OPE scenario under heavy-tailed assumption, the distributional properties of LSE are studied.
10. Comparison with LS estimator: More Comparison with the LS estimator in the OPE setting based choosing is provided.
These additional experiments aim to provide comprehensive evaluation of our proposed LSE estimator.
G.1. Off- Off-policy evaluation experiment
We conduct synthetic experiments to test our model's performance and behavior compared to other models and the effectiveness of our approach in the case of heavy-tailed rewards. We have different settings. Gaussian setting in which the distributions are Gaussian random variables, having exponential tails, and Lomax setting in which the distributions Lomax random variables, with polynomial tails. In all experiments we run 10K trials to estimate the bias, variance and MSE of each method, given MSE as the main criteria to compare the performance of different approaches. We conduct experiments on our method (LSE), power-mean estimator (PM) (Metelli et al.) 2021), exponential smoothing (ES) (Aouali) ctt al. 2023), IX estimator (Gabbianelli et al. 2023), truncated IPS (IPS-TR) (lonides 2008b), self-normalized IPS (SNIPS) (Swaminathan Joachims 20155), OS estimator (Su et al. 2020) and LS estimator (Sakhi et al., 2024). The number of samples changes in different settings. In each setting, we grid search the hyperparameter of each method with different values and select the one that leads to the least estimated MSE value. Note that the hyperparameter for each method is selected independently in each setting, but the candidate values are fixed throughout all settings.
Gaussian: In this setting, as explained in section 6 we have To T=(- ~ N (N1,, mo ~ N ((22 and r(zo, u)
mm? Given 2002 < 1, with simple calculations we have,
ando
Ez, [r]
200 exp
(85)
VI
2
ltc
(c(m) - ((2))11)((11))) + 200 )m1 (1+c + 200 ((02))12)
Em
Tt
ET. [r]] exp
(86)
20 2002)
We fix = 0.5, μ2 = 1, = 0.25, but we change a as it increases the 1 + e-moment of the weighted reward variable 2 and (given 1 > 0, < [n fi [ni-Pal or μ4 > (22) leads to unbounded + c-moment for a = 202 We report the experiment results in Tables and [O we can observe LSE effectively keeps the variance low without significant side-effects on bias, leading to an overall low MSE, making it viable choice with general unbounded reward functions.
as it tends to 1
52

---

Ser-Sum-Expoontiie Estimator for Off-Policy Evaluation and Learning
We also try different values for the number of samples, and observe the estimator's capability work well on small number of samples and their performance growth with the number of samples. For 1.4, the results of different methods for 100, 1K, 10K, 100K are illustrated in Table II
Discussion: We observe that either in small sample size or large sample size, LSE beats other methods with significant gap. Inspecting the bias of LSE through different sample sizes, the bias becomes fixed and doesn't 't decrease as the number of samples in the LBF dataset goes beyond IK. This is due to the fixed candidate set for the parameter À in LSE and the presence of in our derived bias upper bound in Proposition 5.5 This shows that the dependence of the bias on À that appears in the bias upper bound is tight and with fixed X, the bias doesn't vanish, no matter how much data we have and for large number of samples it is critical to select À function of n. Furthermore, effectively decreases as the number of samples increases. Here we can observe the decrease rate of 1/n in the variance, as it is proved in Proposition 5.7 under bounded function's 's growth becomes bigger PMM, IPS-TR, SNIPS, and OS suffer from a very large variance, while ES, LSE, IX, and LS-LIN manage to keep the variance relatively low. Among these ww-variance methods, LSE achieves the lowest bias, indicating a better bias-variance trade-off. We hypothesize that this is due to the fact that L.S-LIN, along LSS,, is the only method that not linear with respect to reward and compresses the reward besides the importance weight.
can that the variance of LSE
assumption. We also observe that as a increases and the reward
Lomax: In the Lomax setting, use Lomax distributions with scale 1 for the learning and logging policies, =o(u(220)) (ut1)==T; mo(u(zz) ~ [u+1)="FT Ot, a' > 0. We use polynomial function for the reward, r(u) = (1 + u)², > 0. The main difference in this setting compared to the Gaussian setting is that here the tails of the distributions are polynomial, in contrast to the Gaussian setting in which the tails are exponential. In this setting, for a > 3, we have,
Exp [r]
a
a - B*
+tc
) ltc
E
To
r = a
k (1+
no
To
a - 3
where &- = 3 and for the second inequality to hold we should have + c(1 - k) > 0. The condition a > B is sufficient for the weighted reward function to be e-heavy-tailed for some c >> 0 (either k < 1 < 1 to 0.5, 1, We also fix a aa-3 0.5, to keep the value function in an appropriate range. We change to get different values for a' k(ax- B) which determines the tail of the weighted reward variable. We set k 2, 4. The results are shown in
j We change the value of 3
Tables 13 and 14 We observe the superior performance of LSE compared to other methods.
Discussion: In Lomax experiments the LSE estimator has the best performance in most of the settings. In two settings, i.e., 3= and a' E (1.5, 2.0). IPS-TR does better than LSE with a very small margin, yet LSE is the second-best model in these two settings. Similar to the Gaussian setting, we also run the experiments for different numbers of samples to inspect the effect of the number of samples on the performance of the models. We fix a = 2.5, f = 2 and a' = 1.5 in this scenario. Table [15 reports the performance of LSE across different number of samples. The same conclusions as the Gaussian setting also observable in the Lomax setting. We can observe that LSE has better performance for 100, 10K, 100K.
In order to have an overall picture of our estimator's performance in OPE, for each estimator we report the number of experiments in which it becomes the first and second best persfreeforiin estimator. This is illustrated in Table I2
We observe that in 13 out of 25 experiments, the LSE estimator outperforms other estimators. Additionally, it ranks second in 11 of the remaining 12 experiments. The overall report shows that LSE and LS dominate other methods in OPE, and both perform well with LSE winning with a small margin.
G. HEAVY- DISTRIBUTION FAMILIES
To confirm our method's s superior performance in heavy-tailed scenarios, conduct experiments different families of heavy-tailed reward distributions. Other than Lomax, we test on Generalized Extreme Value (GEV), Frechet, and Student's / distributions. For GEV, we set e = -0.9, for Student's t distribution, we set df 1.2, for Frechet (inv-weibull) we set c = 1.2, and for Lomax we set a = 1 1.2. To keep the values positive, we consider the absolute value of the reward values. Note that this does not change the tail behavior of the distribution. Table TableTo]show To]shows compare the performance of LSE compared to other methods in OPE on these heavy-tailed reward distributions.
53

---

SeeSS-m--pppenttte Estimator for Off-Policy Evaluation and Learning
Table 9: Bias, variance, and MSE of LSE, ES, PM, IX, IPS-TR, SNIPS, LS-LIN, and OS estimators with Gaussian distributions for a 1.0, 1.2, estimations are reported. The best-performing result is highlighted in bold text, while the second-best result colored in red for each scenario.
1.2, 1.3. The experiment run 10000 times and the variance, bias, and MSE of the
Estimator
Bias
Variance
MSE
PM
0.037
0.004
0.006
ES
-0.001
0.006
0.006
LSE
0.021
0.003
0.003
IPS-TR
0.019
0.004
0.004
1.0
IX
0.168
0.001
0.029
SNIPS
-0.003
0.008
0.008
LS-LIN
0.151
0.001
0.024
LS
0.006
0.005
0.005
OS
0.505
0.005
0.260
PM
0.004
0.063
0.063
ES
-0.001
0.054
0.054
LSE
0.052
0.006
0. 009
IPS-TR
0.020
0.052
0.052
1.1
0.237
0.002
0.058
SNIPS
-0.005
0.059
0.059
LS-LIN
0.284
0.001
0.082
LS
0.082
0.007
0.0135
OS
0.521
0.020
0.292
PM
-0.033
0.435
0.437
ES
0.000
0.357
0.357
LSE
0.152
0.014
0.037
IPS-TR
0.024
0.353
0.354
1.2 IX
0.373
0.005
0.144
SNIPS
-0.003
0.366
0.366
LS-LIN
0.545
0.002
0.299
LS
0.183
0.016
0.050
OS
0.541
0.116
0.409
PM
0.121
1.731
1.746
ES
1.162
0.026
1.377
LSE
0.158
0.124
0.148
IPS-TR
0.030
1.404
1.405
1.3 IX
0.662
0.016
0.453
SNIPS
-0.000
1.491
1.491
LS-LIN
1.069
0.003
1.145
LS
0.155
0164
0.188
OS
0.463
56.581
56.796
54

---

SeeSS-u--pppetttte Estimator for Off-Policy Evaluation and Learning
Table 10: Bias, variance, and MSE of LSE, ES, PM, IX, IPS-TR, SNIPS, LS-LIN, and OS estimators with Gaussian distributions for a 1.4, 1.5, 1.6, 1.7. The experiment run 10000 times and the variance, bias, and MSE of the estimations are reported. The best-performing result is highlighted in bold text, while the second-best result colored in red for each scenario.
Estimator
Bias
Variance
MSE
PM
-0.301
164.951
165.041
ES
1.959
0.396
4.232
LSE
0.615
0.292
0.670
IPS-TR
0.053
133.688
133.691
1.4
IX
1.340
0.048
1.842
SNIPS
-0.029
133.520
133.521
LS-LIN
2.164
0.005
4.687
LS
0.564
0.458
0.776
OS
0.623
23.589
23.977
PM
-0.205
222.003
222.045
ES
3.850
1.505
16.324
LSE
2.132
0.645
5.190
IPS-TR
0.349
179.990
180.112
1.5
3.116
0.153
9.865
SNIPS
0.315
194.830
194.929
LS-LIN
4.682
0.009
21.927
LS
1.968
1.156
5.028
OS
1.096
504.001
505.205
PM
0.726
5095.725
5096.253
ES
9.420
22.685
111.416
LSE
7.541
1.233
58. 105
IPS-TR
1.903
4131.016
4134.636
1.6
IX
8.665
0.502
75.589
SNIPS
1.860
4426.166
4429.625
LS-LIN
11.547
0.015
133.349
LS
7.148
2.595
53.689
OS
3.669
1303.684
1317.146
PM
9.943
125126.550
125225. 418
ES
38.531
0.301
1484.959
LSE
32.107
2.244
1033.093
IPS-TR
12.880
101427.776
101593.680
1.7 IX
32.923
1.802
1085.753
SNIPS
12.704
102027.852
102188 250
LS-LIN
38.112
0.024
1452.556
LS
31.227
5.267
980.41 41
OS
29.171
17767.954
18618.899
55

---

Sae-SSm---xopeeee Estimator for Off-Policy Evaluation and Learning
Table 11: Bias, variance, and MSE of LSE, ES, PM, IX, IPS-TR, SNIPS, LS-LIN, and OS estimators with Gaus- sian distributions setup. The experiment was run 10000 times fixing a 1.4 and different number of samples E {100, 1000, 10000, 100000). The variance, bias, and MSE of the estimations are reported. The best-perforning result highlighted in bold text, while the second-best result is colored in red for each scenario.
72
Estimator
Bias
Variance
MSE
PM
0.1288
203.5015
203.5181
ES
1.9769
1.7696
5.6775
LSE
1.2210
0.5015
1.9925
IPS-TR
0.1617
164.9972
165.0234
100
IX
1.3459
0.4783
2.2897
SNIPS
0.0074
196.8881
196.8881
LS-LIN
2.1683
0.0568
4.7585
LS
1.1817
0.8115
2.2079
OS
0.7661
10.2588
10.8458
PM
0.1963
18.3363
18.3749
ES
1.9587
0.1694
4.0058
LSE
0.6030
0.2999
0.6635
IPS-TR
0.1007
14.8696
14.8798
1000
IX
1.3375
0.0486
1.8376
SNIPS
0.0594
15.0741
15.0776
LS-LIN
2.1646
0.0056
4.6910
LS
0.5640
0.4580
0.7761
OS
0.6432
8.7698
9.1835
PM
-0.2282
10.4458
10.4979
ES
1.9625
0.0285
3.8800
LSE
0.6159
0.0296
0.4089
IPS-TR
0.0464
8,4660
8.4681
10000
IX
1.3410
0.0048
1.8031
SNIPS
0.0435
8.5986
8.6005
LS-LIN
2.1644
0.0005
4.6852
LS
0.5606
0.0466
0.3609
OS
0.5564
4.8936
5.2032
PM
00.2505
1.8148
1.8775
ES
0.0246
1.4707
1.4713
LSE
0.6160
0.0029
0.3823
IPS-TR
0.0250
1.4706
1.4712
100000
IX
1.3408
0.0005
1.7982
SNIPS
0.0246
1.4757
1.4763
LS-LIN
2.1629
5.6014
4.6783
LS
0.5584
0.0049
0.3167
OS
0.5823
0.8251
1.1643
56

---

Log-Sum-Exxonennn Estimator for Off-Policy Evaluation and Learning
Table 12: Comparison of different estimators in terms of the number of best|second rank performances of all Lomax and Gaussian experiment setups in OPE scenario.
Estimator
Gaussian
Lomax
Total
LSE
7|5
6/6
13 11
OS
ojo
0j0
0
PM
oj0
0
0/0
ES
0
0
0,0
LS
5|7
6/6
11
IPS-TR
0J0
1|1
1|1
IX
0J0
0/0
0
G.2. Off-policy learning experiment
We present the results of our experiments for EMNIST and FMNIST in Table 18
As we can observe in the results for different scenarios and datasets, our estimator shows dominant performance among other baselines. The details of the number of best- pesffrreformingggg and second-ramt estimators provided in Table I7 We observe that in 21 out of 30 experiments, the LSE estimator outperforms other estimators. Additionally, it ranks second in 7 of the remaining 9 experiments.
In the noisy scenario, where noise robustness is critical, increasing the noise on the propensity scores by reducing the value results marked decrease the performance of estimators, with the notable exception of LSE, which exhibits superior noise robustness.
In all two datasets, without noise, increasing has negligible impact the estimators. However, in noisy scenarios, higher leads decreased performance. This happens because increases, the logging policy distribution approaches uniform distribution, making it easier for noise to affect the argmax value, thereby reducing the estimators' performance. Notably, the LSE estimator demonstrates better robustness compared to other estimators, consistently showing superior performance in all noisy setups when b = 0.01.
57

---

See-SSm--xpponttiee Estimator for Off-Policy Evaluation and Learning
Table 13: Bias, variance, and MSE of LSE, ES, PM. IX, IPS-TR, SNIPS, LS-LIN, and OS estimators with Lomax distributions setup for 3 = 0.5, 1.5. The experiment was run 10000 times with different values of o, a' and B. The variance, bias, and MSE of the estimations are reported. The best-performing result is highlighted in bold text, while the second-best result colored in red for each scenario.
Method
Blas
Variance
MSE
PM
0.0197
0.0197
0.0004
0.0197
0.0197
LSE
0.0361
0.0047
0.0060
IPS-TR
0.0004
0.0197
0.0197
1.0
0.6958
0.0001
0.4842
SNIPS
0.0004
0.0197
0.0197
LS-LIN
0.4475
0.0002
0.2005
LS
0.0266
0.0046
0.0053
OS
0.3332
0.0094
0.1204
PM
0.2191
0.0154
0.0634
ES 0.0145
0.2011
0.2013
LSE 0.1702
0.0117
0.0407
IPS-TR
0.1341
0.0146
0.0326
0.5
1.0
1.5
0.7815
0.0003
0.6111
SNIPS
0.0181
0.1668
0.1671
LS-LIN
0.5303
0.0011
0.2822
LS
0.0697
0.0346
0.0395
OS
0.7636
0,0007
0.5838
PM
0.4784
0.0084
0.2372
0.95541
0.0020
0.9147
LSE 0.1586
0.0801
0.1052
IPS-TR
0.2965
0.0171
0.1050
2.0 IX
0.8641
0.0006
0.7472
SNIPS
0.0580
1.1500
1.1533
LS-LIN
0.6106
0.0023
0.3751
LS
0.3086
0.0238
0,1190
OS
1.0176
0.0003
1,0358
PM
0.0823
0.0140
0.0508
ES
0.0006
0.0357
0.0357
LSE 0.0731
0.0092
0.0146
IPS-TR
0.0006
0.0357
0.0357
1.0
IX
1.0438
0.0002
1.0897
SNIPS
-.0003
0.0118
0.0418
LS-LIN
0.8513
0.0004
0.7252
LS
0.0429
0.0104
0.0122
OS
0.3566
0.0364
0.1635
PM
0.0167
0.7885
0.7888
ES
0.0167
0.7885
0,7888
LSE 0.1122
0.0820
0.0946
IPS-TR
0.0167
0.7885
0,7888
1.5
IX
1.1723
0.0006
1.3749
SNIPS
0.0167
0.7885
0.7888
LS-LIN
0.9551
0.0014
0.9136
LS
0.1183
0.0717
0.0857
OS
0.5122
0.6815
0.9439
PM
0.3839
0.3198
0.4672
ES
1.4337
0.0035
2,0589
LSE 0.2731
0.1353
0. 0.2099
IPS-TR
0.2280
0.2424
0.2944
2.0 IX
1.2957
0.0013
1.6801
SNIPS
0.0614
2.3202
2.3239
LS-LIN 1.0580
0.0030
1.1223
LSS
0L25-48
0.1785
0.2434
OS
1.2544
0.0059
1.5793
58

---

Log-Sum-Exppaa Exponeennnentall Estimator for Off-Policy Evaluation and Learning
Table 14: Bias, variance, and MSE of LSE, ES, PM, IX, IPS-TR, SNIPS, LS-LIN, and OS estimators with Lomax distributions setup for 3 The experiment was run 10000 times with different values of a, a' and B. The and MSE of the estimations are reported. The best-performing result is highlighted in bold text, while the second-best result colored in red for each scenario.
variance, bias,
B a'
Method
Bias
Variance
MSE
PM
0.2267
0.1913
0.2427
ES
0.0049
0.1540
0.1540
LSE
0.0304
0.0461
0.0471
IPS-TR
-0.0049
0.1540
0.1540
1.0
IX
1.7392
0.0007
3.0256
SNIPS
0.0100
0.1858
0.1859
LS-LIN
1.9231
0.0011
3.6995
LS
0.0819
0.0281
0.0348
OS
0.5571
0.0849
0.3953
PM
-0.2510
17.7398
17.8028
ES
2.2891
0.0024
5.2425
2.5
LSE 0.2266
0.1688
0.2201
IPS-TR
-0.0042
14.3693
14.3694
1.5
IX
1.9546
0.0018
3.8224
SNIPS
0.0062
14.4548
14.4549
LS-LIN
2.0374
0.0016
4.1529
LS
0.2330
0.1699
0.2242
OS
0.3995
13.5957
13.7553
PM
-0.2114
27.6307
27.6754
ES
2.3886
0.0113
5.7167
LSE
0.5334
0.2729
0.5574
IPS-TR
-0.0086
22.5415
22.5416
2.0 IX
2.1606
0.0035
4.6717
SNIPS
-0.0107
22.6954
22.6955
LS-LIN
2.1601
0.0034
4.6694
LS
0.4946
0.3696
0.61424
OS
0.5158
7.4515
7.7175
59

---

Log-Sum--xxpaa Exponexnnnettill Estimator for Off-Policy Evaluation and Learning
Table 15: Bias, variance, and MSE of LSE, ES, PM, IX, IPS-TR, SNIPS, LS-LIN, and OS estimators with Lomax distribu- tions setup. The experiment is conducted for 10000 times and different number of samples E {1000 1000, 10000, 100000}. The variance, bias, and MSE of the estimations the second-best result is colored in red for each scenario.
reported. The best-performing result is highlighted in bold text, while
Estimator
Bias
Variance
MSE
PM
-..2466
75.480
75.542
ES
2.2895
0.0244
5.2663
LSE
0.6217
0.4035
0.7900
100
IPS-TR
0.0021
61.140
61.140
IX
1.9546
0.0182
3.8388
SNIPS
00.031
67.583
67.583
LS-LIN
2.0369
0.0168
4.1660
LS
0.6339
0.5402
0.9421
OS
0.4287
61.159
61.343
PM
00.421
10.960
11.019
ES
2.2889
0.0024
5.2415
LSE 0.2245
0.1702
0.2206
1000
IPS-TR
0.0037
8.8781
8,8780
IX
1.9540
0.0018
3,8198
SNIPS
0.0010
9.0742
9.0742
LS-LIN
2.0375
0.0016
4.1531
LS
0.2330
0.1699
0.2242
OS
0.4345
8.8799
9.0687
-0.2317
0.6596
0.7132
ES
0.0131
0.5343
0.5345
LSE
0.2253
0.0171
0.0679
10000
IPS-TR
0.0131
0.5342
0.5345
IX
1.9539
0.0002
3.8180
SNIPS
0.0133
0.5364
0.5366
LS-LIN
2.0375
0.0002
4.1517
LS
0,2338
0.0171
0.0717
OS
0.4438
0.5345
0.7315
PM
0.2619
0.6546
0.7232
ES
0.0140
0.5302
0.5304
LSE
0.2267
0.0019
0.0533
100000
IPS-TR
0.0140
0.5302
0.5304
IX
1.9538
1.6977
3.8175
SNIPS
0.0137
0.5284
0.5286
LS-LIN
2.0374
1.6805
4.1509
LS
0.2351
0.0019
0.0572
OS
0.4166
0.5302
0.7038
60

---

Log-Sum--Nee Soum--xxonennial Estimator for Off-Policy Evaluation and Learning
Table 16: Bias, Variance, and MSE for different methods under heavy-tailed reward distributions.
Distribution
Metric
LSE
LS
IX
ES
PM
OS
SNIPS
IPS-TR
Bias
1.511
1.617
4.671
2.584
0.5677
4.778
0.1058
0.9616
Lomax
Variance
0.4641
0.5156
0.6819
84.07
187.6
0.3136
190.4
171.5
MSE
2.746
3.132
22.50
90.75
187.9
23.15
190.4
172.4
Bias
0.1204
0.2105
0.7073
2.861
0.2103
0.7220
6.751
5.4139
GEV
Variance
0.0004
0.0004
0.0657
722.1
43.68
0.0054
2209
1604
MSE
0.0149
0.0447
0.5660
730.2
43.72
0.5268
2255
1633
Bias
1.474
1.598
3.965
2.993
1.1863
5.309
0.2678
1.235
Frechet
Variance
0.4842
0.5161
10.31
29.80
92.08
0.1344
132.8
80.58
MSE
2.656
3.068
26.03
38.75
93.49
28.31
132.9
82.10
Bias
0.9914
1.072
3.688
2.086
0.7545
3.766
0.0029
0.7982
Student's t
Variance
0.3270
0.3647
0.1986
24.69
79.09
0.2374
205.6
61.42
MSE
1.310
1.513
13.80
29.04
79.66
14.42
205.6
62.06
Table 17: Comparison of different estimators in terms of the number of best second rank performances of all true propensity score/ reward, estimated (noisy) propensity scores and noisy reward experiment setups in OPL scenario.
Estimator
True PS & Reward
Noisy PS
Noisy Reward
Total
LSE
3/2
10
8/4
21/7
OS
1/2
1
3/3
5|5
PM
2
1/7
1|5
4|13
ES
0/0
0J3
0J0
0|4
LS-LIN
0
0
010
0
IX
0/0
0
0,0
0
61

---

Log-Sum-ENee Expon-eannential Estimator for Off-Policy Evaluation and Learning
Table 18: Comparison of different estimators LSE, PM, ES, IX, BanditNet, LS-LIN and OS accuracy for EMNIST and FMNIST with different qualities of logging policy (T {1, 10, 20}) and true estimated propensity scores with b E {5, 0.01} and noisy reward with P E {0.1, 0.5}. The best-performing result is highlighted bold text, while the second result colored in red for each scenario.
Datasel
Pr
LSE
PM
IX
BandilNel
LS-LIN
OS
Logging Policy
88. 19.49-. 0.01
89.19 + 0.03
88.61 = 0.06
88.33 1: 0.13
66.58 6.39
88.70 TU 0.02
88.71
0.26
8S.
88.48
1
0.01
86.07 + 0.01
0.10
85.71
0.01
81.39 + 1.02
06.55
3.11
81.61 0.17
81.59
0.09
85.08
0.1
89.29 +: 0.04
89.08 0.05
88.45 = 0.09
88.14 0.14
59.90
2 3.78
88.30
0.12
88.74 1 0.09
88.08
0.5
0.08 88.72
88.78 + 0.03
87.27 0.10
0.14 87.08
1 3.06 36.95
87.20
0.32
68.06
0.09
88.08
0.04 88.43
88.38
87.43
+ 0.19
85.48
3.13
0.34
79.43
88.12 0.07
88.39
86.39
0.06
84.90 3.10
23 0.27
86.00
0.37
79.43
EMNIST
10
0.01
82.15 +: 0.21
80.85 0.255+0..20 0.29
81.07 0.07
77.49 + 2.77
27.02 + 1.92
78.43 + 3.13
21.70 + 4.11
79.43
0.1
88.29 +: 0.06
88.22 0.02
88 19.19 = 0.08
87.93 + 0.35
84.80 3:21
87.50 0.17
87.68
0.16
79.43
0.5
0.16 88.71
88 88.52 0.07
81.22 =
83.25 +
63.35
.9
0.04 85.75
89.09
0.05
79.43
88.42 + 0.12
87.98 1 0.05
88.27 0.33
88.27 1 0.07
86.82 0.17
88.19 1 0.11
79.31 0.61
14.86
20
0.01
81.36 + 0.14
75.53 2 2.61
73.45 = 2.78
72.31 + 1.46
26.92 2.51
72.33 = 0.35
11.12 - 0.39
14.86
0.1
88.10 +: 0.05
87.93 1. 0.16
87.69 = 0.22
67.67776 0.18
81.73 3.09
87.08 0.14
82.95 0.31
14.86
1:
84.01
80.79
0.48
76.45 0.12
73.33 + 2.67
72.90
69.12 0.26
00.06
2.16
69. 0.19
77.77
0.09
78.38
73.20 2.43
75.07 0.27
70.38 2.59
70.80 + 2.38
22.11
1.50
69.33 0.20
77.57
0.10
78.38
1
0.01
74.08 +: 1.64
70.35 0.12
57.93 = 66
63.31 +: 3.61
30.20 = 8.17
63. 3.40
37.57 11.57:2:: 3.16
78.38
0.1
76.07 0.02
74.54 0.02
70.42 = 2.53
70.58 + 2.17
50.37 5.43
70.41 2.20
77.71 0.22 77.46
78.38
0.5
76.96 0.23
7..03
66.06
1.32 54.53
66.53 2.76
78.38
76.14 0.11
74.42 0.17
69.25 0.10
70.69 1 2.39
65.70
3.78
69.31 1. 0.24
74.89 0.96
21.43
5
75.42 +: 0.16
74.79 4 0.15
71.42 = 2.53
69.21
4 0.25
69.53 1 0.29
70.15 4: 2.53
72.87
0.47
21.43
FMNIST
10
0.01
74.04 +: 0.15
60.77
0.09
53.69 = 1.37
63.57 + 3.91
1.87 26.06
60.65 3.83
13.22 0.91
21.43
0.13
0.5
77.66 1: 0.17
74.02 0.05
61.46 4.72
62.60 0.16
2.83 43.33
61.35 1.83
77.52
0.26
21.43
75.12 0.03 0.03
0.12
09.26 0.09
72.46 2.14
64.922
3.882
72.86-5
2.32
65.78
1.10
14.84
5
75.13 +: 0.09
0.11
69.23 = 0.46
68.72 0.33 0.30
62.11 4.21
69.06 06 0.11
63.53 2: 1.70
14.81
20
0.01
69.16 0.22
55.20
80.91 = 2.75
61.11 4.92
28 2.18
61.46
1.95
13.04 4.76
14.84
0.1
75.48
7181 2.47
63.11
0.16 67.91
0.46
0.26
14.81
0.00 0.5
7.21
61.79 3.13
60.19 3.13
0.115
60.51 3.28
73.32 0.81
14.81
62

---

Estimator for Off-Policy Evaluation and Learning
Table 19: Comparison of different model- estimators DR, DR-OS, MRDR, SWITCH-DR, SWITCH-DR-LSE, DM and DR-LSE with LSE for EMNIST and FMNIST under a logging policy with T = 10, true estimated propensity scores with E (5, 0.01) and noisy reward with P E {0.1, 0.53. The best-performing result is highlighted bold text, while the second-best result colored in red for each scenario.
Dataset
b
DR-LSK
DR
DR-OS
MRDR
DR-Switch
DR-Switeb-L-E:
LSE
1M
Logging Pollcy
88.79 - 0.03
88.71
0.07
87.79 4: 0.36
80.57
1.00
79.10 5.21
87.73 0.31
88.59 0.03
76.52
2.68
79.13
5
88.67 + 0.04
88.49
0.13
87.83
+: 0.17
80.08
4.62
78.28 + 0.65
85,80
3.40
88.42 0.07
76.73 2: 4.96
79.43
EMNIST
0.01
83.30
+ 3.13
78.21 0.57
80.53
4: 0.32
10.00 0.01
74.81 1: 0.57
41.11 2.87
82.15 0.21
75.65 0.29
79.13
0.1
88.51 + 0.02
88.32
= 0.16
87.00
0.288
45.49 +: 9.14
76.28 +: 0.00
79.86 0.64
88 29
0.06
78.85
4: 2.60
79.43
85.88 2: 0.13
83.53 = 0.51
85.16 1: 0.73
7,01 = 1.18
72.76 1: 0.50
81.73 0.23
88.71
0 0.16
75.26
2: 2.39
79.43
80.15 0.09
68.70
5,12
63.06 + 0.39
$8.61 3.80
$4.20 + 6.27
34.47 + 0.02
76.14 0.11
$1.24-44.16
79.43
5
79.64 2: 0.05
66.67
5.50
64.80 -: 2,36
56.62 1.52
56.61 4: 7.37
29.59 5.83
75.42 0.16
39.65
3.13
79.43
FMNIST
0.01
55.10 = 0.25
52.19
3.84
60.92 + 1.81
10.00
+ 1.62
41.13 + 2.84
74.04 4: 0.15
38.94 4.18
79.43
79.91 4: 0.11
68.94
0.35
63.19 1.69
10.00 0.01
57.54 d: 3.05
52,79 d: 4.04
76.76 0.23
36.33
7.70
79.43
79.14 0.04
56.47
7.08
56.72 + 7.19
22.05 4.50
50.54 + 2.95
75.31 + 0.55
77.86 0.17
53.70
7.19
79.43
G.3. Model-based estimators
There are some approaches that utilise the estimation of reward. For example, in the direct method (DM), the reward is estimated from logged data via regression. In particular, an estimation of the reward function, F(ar, a), is learning from the LBF dataset S using regression. The objective function for DM can be represented as,
a To (()a
(87)
72
In the doubly-robust (DR) approach (Dudik et al. 2014) DM is combined with the IPS estimator and has promising performance in the off off-policy learning scenarios. The object function for doubly robust be represented,
mo(alc:)F(aa x:)) 1
To (a (ra) (rx - f(a,
(88)
To (r;))
i=1
There are also some improvements regarding the DR, including DR based on optimistic Shrinkage (DR-OS) (Su et al. 2020), DR-Switch (Wang et al. 2017) and MRDR (Farajtabar et al. 2018).
As these methods are based on the estimation of reward, consider them as model-based methods. Inspired by the DR method, combine the LSE estimator with the DM method (DR-LSE)
a M ne Ta(a)x;)F(a,z;) + log Σ
1
n
(> Te (a (a: (r: F(a, x.))))
exp
(89)
To (as (z.)
We also combine, LSE with DR-Switch as (DR-Switch-LSE) where the IPS estimator in DR-Switch replaced with LSE estimator.
In this section, we aim to show that the combination of our LSE estimator with the DR method as model-based method can improve the performance of these methods. For our experiments, we use the same experiment setup as described in App. F We compare model-based methods, DM, DR and DR-LSE, DR-Switch, DR-OS, and DR-Switch-LSE with our LSE We observed that DR-LSE outperforms the standard DR in many scenarios.
estimator. The results are shown in Table 19
63

---

Logg-Sum-Exponenii Estimator for Off-Policy Evaluation and Learning
G.4. Real-World dataset
We applied our method to real-world scenarios: one in recommendation systems and the other in Natural Language Processing.
G.4.1. RECOMMANDATION SYSTEMS
We applied our method to the Kuairec, public real-world recommendation system dataset ((Gao et al. 2022 This dataset gathered from the recommendation logs of the video-sharing mobile app Kuaishou. In each instance, user watches an item (video) and the watch duration divided by the entire duration of the video is reported. We use the same procedure as Zhang et al. 2023a) to prepare the logged bandit dataset. We also use the same architecture for logging policy and the learning policy, with some modifications the hidden size and number of layers of the deep models. We use separate models for the logging and learning policies. We first train the logging policy using cross-entropy loss and fix it to use the propensity score estimator for the training of the OPL models. We report Precision @ K, and NDCG@K K for K=1, 3, 5, 10. Recall @ K is very low for small K values because the number of positive items for each use of much more than K. For each method, we use grid search to find the hyperparameter that maximizes the Precision I in the validation dataset. The comparison of different estimators is presented Table 20 We can observe that in Precision @ 1, Precision Precision 10, NDCG@1. NDCG@3 and NDCG@ 10, we have the best performance.
Table 20: Comparison of different estimators LSE, PM, ES, IX, LS-LIN, OS and SNIPS in different metrics. The best-performing result is highlighted in bold text, while the second-best result is colored in red for each scenario.
Dataset
Estimator
Precision@1
Precision@3
Precision@10 Precision@5
NDCG@1
NDCG@3
NDCG@5
NDCG@
PM
0.8885
0.5723
0.5201
0.4275
0,8585
0.6551
0.5932
0.4988
SNIPS
0.0289
0.6177
015995
0.6462
0.0289
0.4981
0.5226
0.5830
0.8794
0.8794
0.6164
0.6410
0.6548
KuaiRec
0.8951
0.7495
0.7187
0.6644
0.8951
0.7787
0.7483
0.7006
OS
0.8093
0.3215
0,2015
U.1403
0.8993
U.4381
0.3227
0,2378
LS-LIN
0.8836
0.6680
0.7159
0.6904
0.8836
0.7159
0.7368
0.7108
LSE
0.9257
0.7534
0.6999
0.7206
0.9257
0.7917
0.7441
0.7431
G.4.2. NLP
We run experiments on PubMed 200K RCT dataset, which is collection of 200,000 abstracts of medical articles. Parts of each abstract are classified into one of the classes of BACKGROUND, OBJECTIVE, METHOD, RESULT, CONCLUSION. This is short text classification that can be viewed as a bandit problem. We apply the same conversion method as we did on image classification datasets in OPL experiments. In Table 21 we can observe the result of our method compared to other state-of-the-art methods.
Table 21: Comparison of different methods LSE, IX. LS, OS, ES, and PM under logging policies with 1, 10 on the PubMed RCT dataset. The best best-performing result is highlighted in bold text, while the second best result is colored in red for each scenario.
Dataset
T
LSE
LS
IX
ES
PM
OS
1
67.16
58.57
58.58
58.48
67.06
62.29
RCT
10
70.17
58.59
58.56
58.60
70.32
66.15
64

---

LLo--Sum-Exeee Slmm-xxoonnttal Estimator for Off-Policy Evaluation and Learning
T=1.=..P-
C- 10, 30.0-
Sareet bedetiin
914
064
(8) 7 =
(b) r = 10
Figure 2: Accuracy the LSE estimator over different values of À for true propensity score and reward. (a) (b) 10.
05
Butseeds
105
875
855
(a)
(b)
10
Figure 3: Plots of Accuracy of the LSE estimator over different values of for true propensity score and noisy reward with
Py = 0.5. (a) 7 = 1. (b) 7 = 10.
G.S. Sample number effect
We also conduct experiments on our LSE estimator and PM estimator to examine the effect of limited training samples in the OPL scenario. For this purpose, we considered different ratios of training LBF dataset, R, {1, 0.,0 0.2, 0.05). The results shown in Table 22 We observed that reducing R. decreased the accuracy for both estimators. However, our LSE estimator demonstrated robust performance under different ratios of training LBF dataset, R,, Therefore, for small-size LBF datasets, we can apply the LSE estimator for off- off-policy learning.
G.6. À Effect
G.6.1. OPL
The impact of À across various scenarios and values investigated using the experimental setup described in Appendix for the EMNIST dataset. Figure 2 illustrrate the accuracy of the LSE estimator for r E (1, 103. For 7 = 1, corresponding to logging policy with higher accuracy, an optimal À value of approximately -1.5 was observed. In contrast, for T 10, representing a logging policy with lower accuracy, the optimal À approached zero. Additionally, in scenarios with noisy and 7 = 10, we observed an optimal values larger 22. As for J = 1, the logging policy has higher accuracy, the effect of noisy reward should be canceled by larger [X]. However, for 10, we need smaller [X].
rewards Fig 3 both
65

---

SaesSSS--Expppeee Estimator for Off-Policy Evaluation and Learning
25
20
Lomax
MSE
GEV
15
T-Student
Frechet
0
44
-3
log (AD
Figure 4: The effect of İ on different families of distributions: GEV, Student's Frechet, and Lomax
G.6.2. OPE
We also conduct experiments to investigate the effect of À in OPE through the synthetic setup. In order to analyze the sensitivity w.r.t. À in OPE, we test on different hcavy-tailed distributions and keep the same setting as Section G.I.I Here we change [^] exponentially from 10-4 4 to 102 and observe the MSE of LSE with the selected value for A. Figure illustrates the MSE value over the different values of À for different families of distributions. As we can see, the trend MSE value different for GEV, and MSE monotonically decreases as À increases. However, in other distributions, higher values result in relatively worse performance, and there is an intermediate value (10-3) for which the lowest MSE is achieved. Nevertheless, 10 10-2 is acceptable choice of À for all distribution families.
G.7. Data-independent Selection of À
Although we use grid search tune the in our algorithm, inspired by Proposition 5.4 we can select the following value,
(90)
(/(+1)
where is the number of samples. This selection is independent of the data values and ensures only asymptotical guarantees. With such a selection we have regret rate of On ((n=t)()))) We test and evaluate our selection in OPL and OPE. We also examine a data-driven approach for selecting À in Section D.5
G.7.1. À SELECTION FOR OPI.
We have tested X* on EMNIST dataset. In OPL experiments we have truncated the propensity score 0.001 in order to avoid numerical overflow. Hence, our distributions are effectively heavy-tailed with e leading X* _1 We
V
66

---

Log-Sum-EExonentia Estimator for Off-Policy Evaluation and Learning
change 512, 256, 128, 64, 16 with corresponding values X (0.044, 0.0625, 0.088, 0. 125, 0.25} which its results stochastic gradient descent in training, here is the batch size. We
presented in the Table 23 Note that because observe that the suggested value of X t does not only have theoretical estimation bound of O Va (according to Proposition 5.4), but also achieves reasonable performance in experiments.
G.7.2. À SELECTION FOR OPE
We tested our À selection in the OPE setting with Lomax distributions. We changed the number of samples and set = 100, 500, 1K, 5K, 10K, 50K, 500K and tested all estimators as we as LSE with selected = X" The results are illustrated at Tables 24] and 25 The first observation is that in all settings, the selected X* outperforms all other estimators, except LS which loses in n < 5000 experiments with very small margin and is not significantly worse than the found by grid search.
Another critical observation is that as the number of samples increases, the selected works better than compared to other methods, even LSE with À found by grid-search. In 100K, not only X perform the best, but also the À found by grid-search falls behind IPS-TR and ES. This shows the significance of selective À when the number of samples is large.
The third observation is the lower performance of X* when we have very small number of samples, e.g. n = 100. This also conforms to our theoretical results, as upper and lower bounds on estimation and regret bounds in Theorem D.2 Theorem D.3 and Theorem 5.3 requires a minimum number of samples as an assumption.
67

---

Log-Sum-Exponentia Estimator for Off-Policy Evaluation and Learning
Table 22: Comparison of LSE and PM accuracy for EMNIST dataset with different ratio of training LBF dataset (Rn, (1. 0.5, 0.2, 0.05)) and true / best-performing result is highlighted in bold text.
estimated propensity scores with b (5, 0.01} and noisy reward with Py e (0.1, 0.5). The
Dataset
Rn
b
Pj
LSE
PM
Logging Policy
88.49 + 0.04
89.19 + 0.03
88.08
1
0.01
86.07 + 0.01
85.62 + 0.10
88.08
0.5
88.72 + 0.08
88.78 + 0.03
88.08
87.79 + 0.08
86.42 + 0.11
88.08
0.5
0.01
81.13 + 0.08
48.70 + 15.46
88.08
0.5
86.24 + 0.07
85.17 + 0.36
88.08
83.76 + 0.25
74.57 + 1.01
88.08
0.2
0.01
67.64 + 3.89
23.18 + 5.02
88.08
0.5
80.39 + 0.19
69.54 + 0.65
88.08
EMNIST
70.16 + 2.44
53.51 + 2.77
88.08
0.05
0.01
36.06 + 0.62
15.56 + 3.21
88.08
0.5
50.06 + 2.10
47.57 + 5.19
88.08
88.59 + 0.03
88.61 + 0.04
79.43
1
0.01
82.15 + 0.21
80.85 0.29
79.43
0.5
88.71 + 0.16
88.52 + 0.07
79.43
86.30 + 0.04
86.02 + 0.06
79.43
10
0.5
0.01
75.02 + 2.67
28.12 1.94
79.43
0.5
86.61 + 0.08
83.21 + 0.10
79.43
80.67 + 0.35
80.83 + 0.22
79.43
0.2
0.01
53.32 + 1.47
17.03 + 0.30
79.43
0.5
80.89 + 0.19
73.42 + 1.14
79.43
48.51 + 0.81
42.27 + 1.48
79.43
0.05
0.01
34.15 + 0.61
14.70 + 2.20
79.43
-
0.5
56.64 + 2.40
41.75 + 1.95
79.43
Table 23: Comparison of accuracy (%) for different values and sample sizes
X
16
64
128
256
512
0.01
92.83
0.10
91.52 + 0.01
90.26 0.02
88.71 + 0.26
85.43 + 0.44
0.1
92.83
0.01
91.45 0.01
90.37
0.02
88.93 0.10
85.50 0.58
92.66
0.01
91.66 + 0.02
90.76 0.02
89.54 0.01
87.79 0.01
10
9..03
19.48
88.86 0.05
$8.03
86.73
X"
9.078
90.38 0.05
8.002
85.09 0.51
68

---

See-Sum--xpponttie Estimator for Off-Policy Evaluation and Learning
Table 24: Summary of Bias, Variance, and MSE for Different Estimators for Lomax OPE experiments. We change the number of samples n 100, 500, 1K, 10K and report the metrics for PM, ES, LSE, LSE(X*), LS, LS-LIN, OS, IPS-TR, IX, SNIPS
Estimator
Bias
Var
MSE
-0.2623
30.6419
30.7106
ES
2.2894
0.0247
5.2662
LSE
0.6194
0.3967
0.7803
LSEOX)
0.9144
0.1952
1.0314
LS
0.6386
0.5336
0.9114
LS-LIN
2.0377
0.0167
4.1689
0.4485
22.7449
22.9461
IPS-TR
0.0144
24.8212
24.8214
IX
1.9517
0.0171
3.8264
SNIPS
0.0483
25.8348
25.8371
PM
0.2002
3.1605
3.2006
0.0415
2.5603
2.5620
LSE
0.2221
0.3375
0.3869
500
LSE(X*)
0.5542
0.0984
0.4055
0.2309
0.3449
0.3983
LS-LIN
2.0377
0.0033
4.1557
OS 0.42724
7.6075
7.7901
IPS-TR
0.0415
2.5603
2.5620
1.9536
0.0035
3.8200
SNIPS
0.0347
2.6865
2.6877
0,2379
4.8325
4.8891
ES
0.0076
3.9145
3.9145
LSE
0.2262
0.1720
0.2231
LSE(>*)
0.4335
0.0712
0,2591
LS
0.2270
0.1751
0.2266
LS-LIN
2.0368
0.0016
4.1502
0.4178
4.0538
4.2303
IPS-TR
0.0076
3.9145
3.9145
IX
1.9536
0.0018
3,8186
SNIPS
0.0040
4.0054
4.0054
PM
0.2428
3.7591
3.8180
0.0032
3.0449
3.0449
LSE 0.2277
0.0343
0. 0.0862
5000
LSE(**)
0.2448
0.0319
0.0919
LS
0.2334
0.03-12
0.0887
LS-LIN
2.0374
0.0003
4.1513
OS 0.4626
0.4477
0.6617
IPS-TR
0.0032
3.0141
3.0149
L.9535
0.0004
3.8166
SNIPS
0.0025
2.9976
2,9976
0.2318
0.4702
0.5239
ES
0.0131
0.3809
0.3811
LSE
0.2254
0.0171
0.0679
10000
LSE
0.1867
0.0212
0.0560
L.S
(12341
0.0173
0.0721
LSSLIN
2.0376
0.0002
4.1518
0.4336
0.5004
0.6884
IPS-TR
0.0131
0.3809
0,3811
IX
1.9536
0.0002
3.8168
SNIPS
0.0123
0.3830
0.3832
69

---

Log-Sum-Exxpaa Eeoon--xpnneniill Estimator for Off-Policy Evaluation and Learning
Table 25: Summary of Bias, Variance, and MSE for Different Estimators for Lomax OPE experiments. We change the number of samples = 50K, 100K and report the metrics for PM, ES, LSE, LSE(A*), LS, LS-LIN, OS, IPS-TR, IX, SNIPS
Estimator
Bias
Var
MSE
PM
0.2418
0.2152
0.2736
ES
0.0040
0.1743
0.1743
LSE
0.2261
0.0033
0.0544
50000
LSE(A*) 0.1020
0.0085
0.0189
LS 0.2324
0.0035
0.0574
LS-LIN
2.0374
0.0000
4.1512
OS 0.3872
5.0487
5.1987
IPS-TR
0.0040
0.1743
0.1743
IX
1.9538
0.0000
3.8172
SNIPS
0.0040
0.1745
0.1746
PM
0.2347
0.0633
0.1184
ES
0.0105
0.0513
0.0514
LSE
0.2267
0.0017
0.0531
100000
LSE(X*) 0.0790
0.0056
0.0119
LS 0,2338
0.0017
0.0564
LS-LIN
2.0375
0.0000
4.1516
OS 0.4294
0.2179
0.4021
IPS-TR
0.0105
0.0513
0.0514
IX
1.9538
0.0000
3.8172
SNIPS
0.0105
0.0515
0.0516
70

---

Log-Sum-Exponerie Estimator for Off-Policy Evaluation and Learning
G.8. Data-driven À Selection
In this section, we evaluate the effectiveness of our data-driven approach (presented Appendix D.5) under both clean and noisy reward conditions and provide strategy to select À based on data. Our approach automatically determines data-driven À parameter directly from the data, climinating the need for manual hyperparameter tuning.
G.8.1. DATA-DRIVEN FOR OPL
Data-driven À on normal setting: when the reward is observed without any error, we use the derived Ao suggested in A.5 We experimented with the EMNIST and FMNIST datasets for T = 1, 10. Table 26 compares the result of data driven Äp with optimal À found by grid-search.
Table 26: Accuracy of LSE and LSE-Ap on EMNIST and FMNIST datasets for T = 1, 10
Dataset
LSE
LSE-Ap
1.0
88.49 + 0.04
89.17 + 0.03 88.56 + 0.04
EMNIST
10
88.59 + 0.03
1.0
75.81 = 0.08
FMNIST
10
0.11
74.96 + 0.12
Data-driven À noisy setting: When the observed reward has errors, suggested AND in Equation 58 at App D.5 We experimented with the EMNIST dataset and 1 and different probabilities of noise Pf 0.2, 0.5, 0.8. Table 27
compares the result of data-driven AND with optimal À found by grid-search.
Table 27: Accuracy of LSE and LSE-AND on EMNIST for Py 0.2, 0.5, 0.8
Dataset
Pj
LSE
LSE-AND
0.2
88.82 = 0.05
88.85 + 0.09
EMNIST
0.5
87.65
0.10
87.5 + 0.06
0.8
91.86 + 0.05
83.96 + 0.22
As we can observe, the data-driven selection for X, keeps up with the good performance of grid-search, making it reliable strategy to choose the hyperparameter of our method, without the requirement of any additional experiments or search. The only exception is for the setting with Ps- = 0.8, in which we observe that the data-driven falls behind by a significant value. This is due to the high noise in the reward, which makes the estimations in the simplified objective for AND less accurate.
G.8.2. À SELECTION STRATEGY
In this section, provide general strategy for the selection of À based on experiments OPE. Since accurate and robust estimation of the average reward is necessary for appropriate training of the target policy, methods that can perform well in OPE and provide robust estimators in extreme and heavy-tailed scenarios are more reliable for OPL. We compare three different methods for the selection of X. First, À is found by grid search which provides the best MSE. Second, X" is found by the data-driven suggestion in App D.5 In the third method, we select uniformly randomly from [0, 1]. Uniform(0. (0, 1). This method shows the performance LSE by choosing random À as a hyperparameter. We test these methods on the Lomax scenario where we have the more challenging heavy-tailed (for + 1) condition. The MSE of each method for the same setting of parameters as in the original OPE experiments and for n 1K, 10K, 100K is reported in table 28
Our experimental results demonstrate that LSE with grid-searched À consistently achieves the lowest MSE across all experimental configurations. The data-driven À selection approach exhibits strong performance, ranking second in scenarios with larger sample sizes (n = 10K, 100K). For smaller samples (n = 1K), random À selection occasionally outperforms the data-driven approach. Notably, LSE maintains robust variance control under heavy-tailed distributions even with randomly selected À values. The performance gap between data-driven and random selection widens significantly as the

---

Sew---u---ppnttte Estimator for Off-Policy Evaluation and Learning
Table 28: MSE LSE with fine-tuned, data-driven and random for 3 = 1.0, 1.5, 2.0. The experiment was run 100000 times with different values of a, a', and B.
B
a'
Estimator
1K
n 10K
100K
LSE
0.006
0.0009
0.0001
1.0
LSE-X*
0.049
0.0076
0.0009
LSE-À
0.131
0.131
0.131
LSE
0.041
0.0.008
0.0039
0.5
1.0
1.5
LSE-X*
0.463
0.138
0.03
LSE-İ
0.449
0.449
0.449
LSE 0.105
0.033
0.026
2.0
LSE-X*
1.044
0.450
0.148
LSE-Ä
0.764
0.762
0.760
LSE
0.014
0.002
0.0003
1.0
LSE-X*
0.110
0.018
0.002
LSE-Ă
0.398
0.398
0.394
LSE
0.093
0.020
0.012
1.0
1.5
1.5
LSE-X*
1.042
0.311
0.067
LSE-À,
1.227
1.226
1.223
LSE
0.211
0.088
0.0754
2.0
LSE-X*
3.05
1.013
0.333
LSE-À
1.991
1.99
1.985
LSE 0.0463
0.005
0.0014
1.0
LSE-X*
0.3071
0.048
0.0054
LSE-
1.550
1.548
1.552
LSE
0.222
0.058
0.052
2.0
2.5
1.5
LSEEX*
2.894
0.864
0.187
LSE-
4.242
4.236
4.246
LSE
0.548
0.313
0.289
2.0
LSE-X*
6.530
2.817
0.928
LSE-Ä
6.534
6.531
6.535
72

---

Sae-SSm--Exoppee Estimator for Off-Policy Evaluation and Learning
FM
TR: PSICloped PS)
LSE tourSt
1400
SMPS
65 [Shintage)
LS-LIN
1300
0 1200
VG2
1100
1000
Log 30d
(a) PM. TR-IPS, SNIPS, OS
(b) LSE, LS-LIN, IX, ES
Figure 5: MSE of the PM, TR-IPS, SNIPS, OS, LS-LIN, IX, OS, ES, and LSE estimators over different values of log
sample size increases, suggesting clear strategy for parameter selection: while the estimator remains robust to arbitrary À choices, the data-driven approach becomes increasingly reliable with larger sample sizes.
If n small (e-g. n R 1000), we have fewer computational concerns, and grid search based on the performance on a validation set can find an appropriate À for our problem.
For larger values of n, we can hold to the data-driven proposal of À which gives a comparable performance with the grid-search method.
Another hint about the selection of À is that for problems where the variance of the importance weights of the unbounded behaviour of the reward function is not an issue, very small À (e.g. À = 0.01) can be better option because as À - O, LSE tends to vanilla IPS. For heavy-tailed problems, selecting bigger À values around can lead to better performance.
G.9. OPE with noise
Here we discuss the performance of estimators in OPE when reward noise is available. In all experiments, the number of samples is 1000 and the number of trials is 100K.
1.9.1. GAUSSIAN SETTING
We run the same experiments as mentioned Section 6.1 by adding noise to the observed reward. We add positive Gaussian noise,
R(S, R(S, A) W W ~N(,009).
where R(S, A) is noisy reward function. We increase from to 100 and observe the behaviour of different estimators under the noise. We report the MSE of different estimators. There is a discrepancy between the performance of different estimators. LSE, LS, LSE-LIN, IX, and ES demonstrated robust performance under high noise conditions, while PM, TR-IPS, SNIPS, and OS exhibited substantially higher MSE values, often differing by several orders of magnitude from the better-performing estimators. We draw the MSE of these two groups against log a in Figure We observe that ES, LSE, IX, and LS-LIN are better suited for the noisy scenario. Also, we observe that ES is more sensitive to the increase of the variance of the noise. We also investigate the distributional form of the estimators with the same levels of noise. Estimators other than LSE, LS-LIN, and IX keep proposing outlier estimations. But these three estimators stay stable in this setting and compared in Figure 6 for two levels of noise. Among these three estimators, LSE can keep low bias with almost the same variance in comparison to IX and LS-LIN, hence leading to the lowest MSE.
G.9.2. LOMAX SETTING
When we examine the Lomax setting, the estimators' performance deteriorates as we introduce heavier-tailed noise distributions. To test this, we add Pareto-distribtted (with parameter a) noise to the reward, varying the parameter a from 1.05 to 2.0. The parameter a controls the tail weight of the distribution, with values closer producing heavier tails. Our
73

---

Sae-SSum--xxppee Estimator for Off-Policy Evaluation and Learning
1750
158 (ours)
LSB (ours)
ISUN
LS
1250
2020
750
500
250
250
(a) small noise, o² = 1.82
(b) large noise, o²
20
Figure 6: The error distribution of the LS-LIN, LSE, and IX estimators
PM TRdPSCCiipoed IPS)
LSE (ouns)
ISUI
SMIPS DS (Shribage)
60000
20
40000
10
0
(a) PM. TR-IPS, SNIPS, OS,
(b) LSE, LS-LIN,
Figure 7: MSE of the PM, TR-IPS, SNIPS, OS, LS-LIN, IX, OS, ES, and LSE estimators different values of
results, shown in Figure 7 reveal a clear split in estimator performance. The estimators PM, ES, TR-IPS, OS, and SNIPS struggle significantly with the heavy-tailed noise and show poor performance based on their MSE contrast, the more robust estimators LSE, LS-LIN, and IX maintain better performance across different noise levels, similar what we observed in the Gaussian scenario.
Note that the IX estimator, despite having significantly less error than the poorly performing estimators, compared to LSE and LS-LIN is much worse in the tail of the noise.
For the distributional behavior of the estimators, we observe that except for LSE and LS-LIN, the estimators produce extreme outlier values. Error distribution the distribution of the difference between the estimated value and the true value, Hence, we plot the error distribution of the LSE and LS-LIN with respect noise in Figure X Here we see that in the small noise scenario LSE despite having more variance, is significantly less biased. Under large noise, LSE keeps the variance lower than LS-LIN, while showing the same bias. Hence, in both cases LSE achieves less MSE than LS-LIN and performs better in both small and large noise scenarios.
G.10. Distributional properties in OPE
In this section, investigate the enror distribution of different estimators. In both Gaussian and Lomax settings, SNIPS, TR-IPS, OS, ES, and PM show extreme outlier values, but LSS-LI,, LSE, and IX avoid outliers. In Figure we show the eиror distribution of these estimators. We can see the competitive performance of IX and LSE in the Gaussian scenario, while LS-LIN induces a relatively large bias in this setting. In the Lomax setting, LSE has a bigger variance than IX and LS-LIN, while having significantly less bias. LSE has the property that keeps bias significantly low while trading it for some small variance, leading to less MSE and better performance.
74

---

Log-Sum-Exxpe Exponexnnnettill Estimator for Off-Policy Evaluation and Learning
1SE (ours) US
1Se (ours)
US.U
2020
2000
1020
1000
(a) Small noise, a
(b) Large noise, a 1.05
Figure The error distribution of the LS-LIN and LSE estimators
1750
LSE (ours)
LSE toUrs)
3750
LSUN
LIN
1500
3250
1000
3000
750
750
530
250
250
(a) Gaussian Scenario
(b) Lomax Scenario
Figure 9: The error distribution of the L.S-LIN, IX, and LSE estimators
75

---

consider set Log-Suun-Exponetiaa Estimator for Off-Policy Evaluation and Learning
G.11. More Comparison with LS Estimator
We conduct experiments measure and compare the sensitivity of LSE and LS with respect the selection of X. To
measure the sensitivity, choose grid search method where test the following set of À E {0.001, 0.01, 0.1, 1.0, 5.0) in Table 29. adaptive method where A vn chosen, Table 30 and random method where Ả chosen uniformly random from [0, 1]. Table 31 Then we compare these two estimators among these different methods of selecting X. The results are reported below for Lomax setup.
Table 29: MSE LSE and LS estimators with grid-searched for À E 1..0 5.0 and , = 1.0, 1.5, 2.0. The experiment was run 100000 times with different values a, a', and [3.
B
a'
Estimator
Bias
Variance
MSE
LSE
0.0362
0.0047
0.0060
1.0
LS
0.0266
0.0047
0.0054
0.5
1.0
LSE
0.1693
0.0118
0.0404
1.5
LS
0.0697
0.0346
0.0395
LSE
0.1590
0.0813
0.1066
2.0
LS
0.3086
0.0238
0.1190
LSE 0.0728
0.0091
0.0144
1.0
LS
0.0429
0.0104
0.0122
1.0
1.5
LSE
0.1065
0.0829
0.0942
1.5
LS
0.1183
0.0717
0.0857
LSE
0.2726
0.1367
0.2111
2.0
LS
0.2548
0.1785
0.2434
LSE
0.0302
0.0452
0.0461
1.0
LS
0.0819
0.0281
0.0348
2.0
2.5
LSE
0.2245
0.1702
0.2206
1.5
LS
0.2330
0.1699
0.2242
LSE
0.5345
0.2645
0.5502
2.0
LS
0.4946
0.3696
0.6142
We can observe that in close competitions, using the grid search method, LSE outperforms in 4 out of experiments. With the adaptive method, LSE performs better in 7 out of experiments, and when using the random method, L.SE outshines in all 9 experiments.
G.12. OPE on UCI datasets
We evaluate our method's performance in OPE by conducting experiments on UCI classification datasets, as explained in Table 32
We the same supervised-te ta approach as in OPL experiments. Suggested by Sakhi et al. 2024 of softmax policies the target and logging policy. Consider ideal policy as a softmax policy peaked on the true label of the sample. Moreover, faulty policy is an ideal policy that has set of its actions shifted by 1, hence, doing mostly wrong on the samples from the shifted labels. For the logging policy, we use faulty policies on the first K/2 actions with temperatures To = (0.6, 0.7,0 0.8), and faulty policies on the last K/ actions with 7 = {0.1, 0.3, 0.5} as target policies, a total of different experiments for each dataset. We create a bandit dataset using the logging policy xo and estimate the
76

---

SeSS--u---ppntttee Estimator for Off-Policy Evaluation and Learning
Table 30: MSE of LSEX, and LSx.. estimators with data-driven A, Jn. for B 1.0, 1.5, 2.0 and n 1000. The experiment was run 100000 times with different values a, a', and 3.
B
α
a'
Estimator
Bias
Variance
MSE
LSEX,
0.0816
0.0029
0.0096
1.0
LSXB
0.1314
0.0028
0.0200
0.5
1.0
LSEAn
0.2756
0.0054
0.0814
1.5
LSXB
0.2841
0.0073
0.0880
LSEX, 0.4651
0.0063
0.2226
2.0
LSAB
0.4476
0.0099
0.2103
LSEx, 0.1596
0.0053
0.0308
1.0
LSA.. 0.2610
0.0052
0.0733
1.0
1.5
LSEXn 0.4857
0.0091
0.2449
1.5
LSXB 0.5129
0.0123
0.2754
LSE 0.7817
0.0100
0.6211
2.0
LSA.
0.7645
0.0159
0.6004
LSE
0.3652
0.0111
0.1445
1.0
LSX..
0.6177
0.0108
0.3924
2.0
2.5
LSEX.. 0.9792
0.0169
0.9757
1.5
LSX.
1.0722
0.0227
1.1723
LSEX1
1.4919
0.0180
2.2437
2.0
LSX.. X..
1.4952
0.0282
2.2637
77

---

LoggSSnm-Exponenig Estimator for Off-Policy Evaluation and Learning
Table 31: MSE of L and 3 estimators with random À for 3 1.0, 1.5, 2.0. The experiment was run 100000 times with different values of a, a', and B.
B
o
Estimator
Bias
Variance
MSE
LSE
0.3418
0.0139
0.1308
1.0
L
0.6779
0.0640
0.5236
0.5
1.0
LSE3 0.6516
0.0247
0.4493
1.5
LS
0.8335
0.0581
0.7528
LSE 0.8583
0.0262
0.7629
2.0
LSA
0.9635
0.0491
0.9775
LSE; 0.6019
0.0365
0.3987
1.0
LS
1.2196
0.1783
1.6656
1.0
1.5
LSE
1.0803
0.0594
1.2264
1.5
LS
1.4290
0.1521
2.1941
LSE
1.3890
0.0603
1.9898
2.0
LS
1.6017
0.1237
2.6890
LSEA
1.1942
0.1180
1.5442
1.0
LS₃
2.4803
0.6019
6.7537
2.0
2.5
LSE
2.0218
0.1686
4.2565
1.5
LS₁
2.7676
0.4797
8.1390
LSE
2.5258
0.1654
6.5451
2.0
LS
3.0074
0.3796
9.4239
Table 32: UCI datasets specifications. N is the number of samples, K is the number of actions, and p is the number of features.
Dataset
N
K
p
Yeast
1,484
10
Page-blocks
5,473
5
10
Optdigits
5,620
64
Satimage
6,430
6
36
Kropt
28.056
18
78

---

Log-SSum-Exponenin Estimator for Off-Policy Evaluation and Learning
expected reward of the ze which is calculated below,
V(Te) Σ To (vi(2s)
where Vi is the true label of the data sample Z;. We also add random uniform noise ~ Uniform(0, 1) to the policy logits before softmax. We ran each experiment in each setting 10 times and calculated the average MSE of each estimator over all 90 experiments. For hyperparameter selection, for LS, OS, IPS-TR, PM, and IX, we use their own proposals. For LSE and ES, we use 0.2 the dataset as a validation set find the hyperparameter with the lowest MSE by grid search and evaluate the method on the remaining 0.8 of the dataset. Table 33 illustrate this on the datasets for different estimators.
Table 33: MSE LSE, PM, ES, IX, OS, LS, IPS-TR and SNIPS estimators on 5 UCI classification datasets on the OPE task.
Dataset
PM
ES
IX
OS
LS
IPS-TR
SN-IPS
LSE
Yeast
0.237
0.0096
0.0573
0.0131
0.0146
0.0255
0.0088
0.0077
Satimage
0.0033
0.0066
0.0057
0.0035
0.0047
0.0043
0.0086
0.0028
Kropt
0.0160
0.0041
0.0056
0.0169
0.0208
0.0189
0.0256
0.0015
Optdigits 0.0079
0.0066
0.0150
0.0076
0.0083
0.0098
0.0110
0.0042
Bage-Blocks
0.0440
0.0002
0.0236
0.0487
0.0513
0.0445
0.0639
0.0008
79

---

SeSS--u---ppptttte Estimator for Off-Policy Evaluation and Learning
150
125
50
100
200
300
400
(a) Gaussian Distribution, (0)
(b) Lomax Distribution, C(15)
Figure 10: Histogram of 10K samples generated from Gaussian and Lomax distributions (we consider the absolute value of the Gaussian samples to focus on the tail of the distributions)
G.13. Connection between heave- distributions and outlier modeling
We illustrate how heavy-tailed distributions can model outlier samples. Consider two sets of observations, the first one from normal distribution (0, 2) which has exponential tail, and the second from Lomax distribution L(1.5), which is heavy-tailed with 0.5. Figure depicts the histogram of observed 10K samples from each distribution. We can observe that the Lomax distribution contains large, low-probability values (values around 400), but the total range for Gaussian observations is less than 10. The occurrence of sparse very low probability outlier values is possible by sampling from a heavy-tailed distribution like Lomax distribution. However, it does not hold for an exponential-tan -tailed distribution like Gaussian. Hence, heavy-tailed distributions seem to be able to model scenarios with sparse large rewards or outliers, which not possible using an exponential-taile distribution. In the following, we discuss the heavy-tailes reward scenario RL applications.
80


Reviews:
[{"review_id": "9ZFYjJjY80", "reviewer": "Reviewer_2WnN", "summary": "The paper proposes to use the log-sum-exponential operation as an off-policy estimator, proving bounds on the mean and variance of the estimates, as well as the performance gap between the optimal and learned policies in off-policy learning, and convergence rates. They follow this up with empirical evaluations.\n\nThe chosen estimator is chosen specifically to deal with the heavy-tailed distribution resulting from inverse propensity weights, so their analysis holds under heavy-tailed assumptions, which additionally holds for unbounded rewards, making the analysis applicable in a variety of domains.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below. \n \n> It seems that these results could potentially be related to a Bayesian setting with exponential family distributions. Have the authors thought about this? I'm curious about the results, and it would increase my (already positive opinion of) the paper, even though I don't think it needs to be included here.\n\n**R1:** We thank reviewer 2WnN for their insightful suggestion. An interesting direction for future work is to explore potential application of theoretical results in Bayesian inference frameworks, particularly through the lens of exponential family distributions and variational approximations. As the LSE can be interpreted as log-partition function in exponential family distribution, our methods can be applied in this field.", "claims_and_evidence": "There are two sets of claims to the paper.\n\nThe first is that the proposed estimator reduces variance, and has provable bounds on bias and variance with heavy tailed and noisy reward observations. Further, they provide regret bounds in the off-policy evaluation and learning setups, as well as the regret convergence under heavy-tailed settings which include unbounded reward. These claims are primarily and adequately supported by theoretical results.\n\nThe second set of claims is that the proposed estimator has competitive performance.", "methods_and_evaluation_criteria": "Yes, they do a standard setup (running various estimators with 10k trials of taking 1k samples, and calculating mean squared error and variance) for OPE on a synthetic data distribution and OPL on the EMNIST dataset.", "theoretical_claims": "Not carefully", "experimental_designs_or_analyses": "Yes, the experimental designs for OPE and OPL were checked", "relation_to_broader_scientific_literature": "They compare against several similar off-policy estimators", "essential_references_not_discussed": "None that I am aware of", "other_strengths_and_weaknesses": "The work is original as far as I know.\n\nThe work is significant, being applicable to a common setting and addressing a key problem of heavy-tailed rewards.\n\nThe paper is consistently clearly written.", "other_comments_or_suggestions": "none", "questions_for_authors": "It seems that these results could potentially be related to a Bayesian setting with exponential family distributions. Have the authors thought about this? I'm curious about the results, and it would increase my (already positive opinion of) the paper, even though I don't think it needs to be included here.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ScZrPxW1Y2", "reviewer": "Reviewer_Ve41", "summary": "The paper proposes an estimator based on the log-sum-exponential (LSE) operator designed for off-policy evaluation (OPE) and off-policy learning (OPL) in contextual bandit settings. The LSE estimator addresses the issue of high variance in inverse propensity score (IPS) estimators by introducing robustness to noisy propensity scores and heavy-tailed reward distributions. The authors provide theoretical guarantees on the bias, variance, and regret for this estimator, with particular focus on its performance under heavy-tailed assumptions on weighted rewards. Empirical results from synthetic experiments and real-world datasets validate the practical effectiveness of the proposed method compared to existing estimators like IPS and others.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below. \n\n> Novelty\n\n**R1:** We appreciate the reviewer’s feedback and the opportunity to clarify the novelty of our work. While it is true that we employ the log-sum-exponential (LSE) technique, one of our key contributions lies in the novel theoretical results we derive in the context of OPE/OPL. Specifically, our analysis establishes new insights that were not previously explored in the literature. These results go beyond a straightforward application of LSE, as we introduce a novel formulation and provide rigorous proofs that reveal deeper theoretical properties of the method in this setting under heavy-tailed assumptions.\n\nAdditionally, while LSE is a well-known technique/operator, its application to OPE/OPL presents unique challenges, which we address through our theoretical analysis. We believe these contributions offer a meaningful advancement in understanding  LSE for heavy-tailed applications.\n\nWe hope this clarification helps address the reviewer’s concern, and we would be happy to further elaborate on the specific theoretical novelties if needed.\n\n>  For instance, experiments involving different types of reward distributions and more real-world applications. Have you considered experimenting with a broader range of real-world datasets to assess the robustness of the LSE estimator in different domains?\n\n**R2:** We conducted more experiments on RCT dataset where the results can be found in the [**following link**](https://anonymous.4open.science/r/icml2025_response-F5FC/response_rct.md). In addition, additional experiments including multiple reward distributions are conducted. We fixed the distribution of the policies to be Gaussians with different locations. To test a variety of heavy-tailed distributions, we assume that we have a single state $s=s_0$ and when $a|s_0 \\sim \\pi_0$, the distribution of $r(s_0, a)$ is of a particular family. We considered Lomax, Generalized Extreme Value (GEV), T-student, and Fréchet distributions. We consider the absolute value of the samples to ensure the reward is positive. The table of the performance of our method compared to other methods is [**available here**](https://anonymous.4open.science/r/icml2025_response-FC68/response_Ve41_R2.md).\n\n>  Could you clarify how the smoothing parameter $\\lambda$ affects the performance of the LSE estimator?\n\n**R3:** The effect of $\\lambda$ for the supervised2bandit experiments where the reward is binary is investigated in App G.6, but for continuous heavy-tailed reward distributions, in the same setting mentioned in R2, we change $|\\lambda| = \\\\{10^i | -3 \\leq i \\leq 2, i\\in \\mathbb{Z}\\\\}$ observe the change of MSE of the LSE estimator. The graphs are available at [**this link**](https://anonymous.4open.science/r/icml2025_response-F5FC/response_Ve41_R2.md).\n\n>  inconsistencies in the References section\n\n\n**R4:** Thanks for pointing out. It is fixed now.", "claims_and_evidence": "The paper makes different claims, which seem to be supported by theoretical results and empirical evidence. \n\nFirst, it claims that the LSE estimator reduces variance and handles heavy-tailed reward distributions more effectively than the IPS estimator and its variants. This claim is supported by a detailed theoretical analysis, which includes bounds on bias, variance, and regret. \n\nEmpirically, the paper shows that the LSE estimator performs better in terms of mean squared error (MSE) and variance compared to competing methods in both synthetic and real-world experiments. This part, in my opinion, can be strengthened with an additional experiment.", "methods_and_evaluation_criteria": "The proposed LSE estimator is evaluated both theoretically and empirically. This is the usual way of evaluating OPE/OPL methods.", "theoretical_claims": "From what I could check, the theoretical claims in the paper seem well-supported.", "experimental_designs_or_analyses": "The experimental design appears sound, but there are some limitations in the scope of the experiments. The experimental setup could benefit from more diverse datasets and a wider range of experimental conditions. For instance, experiments involving different types of reward distributions and more real-world applications", "relation_to_broader_scientific_literature": "The paper is related to prior work in the area of off-policy evaluation and learning. \nAlso, it is related to heavy-tailed bandits, which is not typical in the OPE/OPL literature. I think that the authors did a good job in their related work sections, which position the paper with respect to specific related prior papers.", "essential_references_not_discussed": "I think that the authors did a good job in their related work sections and all the essential references are more or less present in the paper.", "other_strengths_and_weaknesses": "In my opinion, the main weakness of the paper (apart from the experimental section which could be expanded, a point already discussed) is the apparent lack of novelty. Essentially, the paper applies the well-known log-sum-exponential (LSE) technique to OPE/OPL\n\nHowever, despite this perceived lack of novelty, I believe the paper still meets the high standards of ICML due to its interesting theoretical analysis and the strong performance of the LSE estimator in the OPE/OPL domains. To the best of my knowledge, LSE has not previously been applied to OPE/OPL, and this work may represent the first contribution demonstrating that LSE can be a valuable addition to the OPE/OPL toolkit.", "other_comments_or_suggestions": "Very minor issue: there seem to be some inconsistencies in the References section", "questions_for_authors": "- Could you clarify how the smoothing parameter $\\lambda$ affects the performance of the LSE estimator?\n- Have you considered experimenting with a broader range of real-world datasets to assess the robustness of the LSE estimator in different domains?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HY1CpGi0QO", "reviewer": "Reviewer_6J3H", "summary": "The paper introduces a novel Log-Sum-Exponential (LSE) estimator for off-policy evaluation (OPE) and off-policy learning (OPL) in reinforcement learning, especially when dealing with logged bandit feedback datasets that may contain unbounded or heavy-tailed rewards. The paper analyzes the LSE estimator's regret bounds, bias, and variance, and it also explores its robustness to noisy rewards and propensity scores. The LSE estimator's performance is empirically compared against several baseline estimators, including truncated IPS, PM, ES, IX, Bandit-Net, LS-LIN, and OS, using both synthetic and real-world datasets. The document also offers theoretical insights into why the LSE estimator is well-suited for scenarios with heavy-tailed reward distributions and provides guidelines for selecting the estimator's parameter λ. The experimental code and data are also provided to support claims about its effectiveness.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, and generally positive assessment of the paper. We will address their concerns as detailed below. \n\n> The simulation experiments are comprehensive and convincing. That said, I think the experiments and validation could be stronger if data from RCTs can be used to evaluate the proposed LSE-based method. Can the authors use RCT data to validate the proposed method?\n\n**R1:** We appreciate the reviewer's suggestion for running experiments in RCT dataset. The result can be found in the [**following link**](https://anonymous.4open.science/r/icml2025_response-F5FC/response_rct.md).", "claims_and_evidence": "The claims of this paper are generally supported by the argument in this paper.", "methods_and_evaluation_criteria": "All evaluations are based on simulations. The results will be more convincing if data from randomized controlled trials can be used to validate the proposed method.", "theoretical_claims": "The theoretical claims and proofs of the paper are rigorous and valid.", "experimental_designs_or_analyses": "The simulation experiments are comprehensive and convincing. That said, I think the experiments and validation could be stronger if data from RCTs can be used to evaluate the proposed LSE-based method.", "relation_to_broader_scientific_literature": "The main contributions of this paper are three-fold. First, the authors develop a novel non-linear estimator based on the LSE operator, which substantially reduces the variance. Second, comprehensive theoretical performance guarantees of LSE-based OPE and OPL are provided. Third, simulated experiments show that the proposed estimator performs well compared with other SOTA algorithms.", "essential_references_not_discussed": "Not aware of.", "other_strengths_and_weaknesses": "I think the paper can be strengthened with evaluations based on experimental data.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "Can the authors use RCT data to validate the proposed method?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l7mMs1pJyl", "reviewer": "Reviewer_aZXo", "summary": "The paper introduces a Log-Sum-Exponential (LSE) estimator to address off-policy evaluation (OPE) and learning (OPL) in contextual bandit settings where rewards or propensity scores may be noisy or heavy-tailed. By applying a log-sum-exp transformation over importance-weighted rewards, this estimator improves robustness and variance control. The main theoretical contributions include a bound on the regret ($\\mathcal{O}\\left(n^{-\\frac{t}{1+\\varepsilon}}\\right)$) under a ($1+\\varepsilon$)-th moment assumption for the weighted reward and bias–variance analyses showing LSE can reduce variance compared to IPS. Experiments on synthetic data and supervised-to-bandit tasks (e.g., EMNIST) demonstrate lower MSE and higher accuracy than standard baselines (IPS variants, ES, PM, IX, etc.).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and comments on the paper. We will address their concerns as detailed below.\n\n> single-pass aggregator\n\n**R1:**  Thanks for raising this point. It is true that theoretically, LSE is not separable and should be applied to the whole dataset. But, due to the nice gradient form of LSE, complete stochastic optimization of LSE is also possible for large-scale datasets.\nSuppose that $x_1, ..., x_{kl}$ is the data of $k$ batches of size $l$. LSE is a quasi-arithmetic mean function. So we have,  \n$$\\\\mathrm{LSE}(x\\_1, ..., x\\_{kl}) = \\\\mathrm{LSE}\\\\left(\\\\mathrm{LSE}(x\\_1, ..., x\\_l), \\\\mathrm{LSE}(x\\_{l \\+ 1}, ..., x\\_{2l}), ..., \\\\mathrm{LSE}(x\\_{(k-1)l \\+ 1}, ..., x\\_{kl})\\\\right) \\\\\\\\   \n    =\\\\mathrm{LSE}\\\\left(A\\_1, A\\_2, ..., A\\_k\\\\right)  \n$$ \nNow we have,  \n$$\\\\nabla\\_{\\\\theta}\\\\mathrm{LSE}(x\\_1, ..., x\\_{kl}) \\= \\\\sum\\_{i=1}^{k}\\\\frac{d}{dA\\_i}\\\\mathrm{LSE}(A\\_1, ..., A\\_k)\\\\nabla\\_{\\\\theta}A\\_i \\= \\<\\\\mathrm{softmax}(\\\\lambda \\\\mathbf{A}), \\\\nabla\\_{\\\\theta}\\\\mathbf{A}\\>  \n$$ \nSo the gradient of the LSE on the entire data is a weighted average of the gradient of each batch, but these weights are not uniform as in the case of monte-carlo mean. We create the following procedure for SGD optimization.\n\nWe store a coefficient $c\\_i$ for each $A\\_i$. Our final objective is to find $c_i$ such that $c_1, ..., c_k$ are proportional to $\\\\mathrm{softmax}(\\\\lambda A\\_i)$. For this to happen, suppose we are at step $t \\+ 1$ and we have, $c_1, ..., c_t$ as the coefficients of $A_1, ..., A_t$. We now want to find $c_{t + 1}$ and apply GD on $c\\_{t \\+ 1}A\\_{t \\+ 1}$. It is sufficient to have the following equality,  \n$$ \\\\frac{e^{\\\\lambda A\\_{t \\+ 1}}}{e^{\\\\lambda A\\_{t}}} \\= \\\\frac{c\\_{t+1}}{c\\_t}  $$\nHence, at step $t$, we apply gradient descent this way:  \n$$ c\\_{t \\+ 1} = c\\_t e^{\\\\lambda(A\\_{t+1} \\- A\\_{t})}  \\\\theta^{(t \\+ 1)} = \\\\theta^{t} \\- \\\\eta c\\_{t \\+ 1}\\\\nabla\\_{\\\\theta}A\\_{t \\+ 1} \\\\\\\\  \n$$  \nwhere $\\\\eta$ is the learning rate and $c\\_1=1$. We will add this procedure for batch optimization as a discussion in the paper.\n> KUAIREC and real-world dataset\n\n**R2:** Thank you for the insightful comment. We agree that evaluating performance on production-scale datasets is crucial. KuaiRec’s 12M-interaction (big) dataset (7K users, 10K items) was used for training/validation, while a denser subset (small) was used for testing. The smaller subset was used solely for evaluation, given its density. We will clarify this in the final version to emphasize that our method has indeed been evaluated on a dataset of production-level scale. Furthermore, we conducted more experiments on more datasets, including the [**PubMed 200K RCT dataset**](https://anonymous.4open.science/r/icml2025_response-F5FC/response_rct.md). \n\n> Choosing $\\lambda$ in practical scenarios\n\n**R3:** We have 3 types of $\\lambda$ selection throughout the paper. One is based on validation data performance (gridsearch), one is data independent selection (App G.7), and the last one is data-driven selection (App G.8). The first method gives better performance and is recommended when it's computationally feasible, but for the large-scale datasets, the data-driven approach can work especially well, because it doesn't require any prior, or any heavy computations and can find a suitable $\\lambda$ according to the data.\n\n>  LSE in off-policy RL with trajectories\n\n**R4:** Thank you for the insightful suggestion. In principle, the LSE operator could be applied in off-policy reinforcement learning, potentially serving as an alternative to traditional importance sampling. However, it brings theoretical (e.g., requiring i.i.d. assumptions) and practical challenges (e.g., computational overhead in algorithms like PPO [1]). We consider this a promising direction and plan to explore it in future work.\n\n> LSE with direct reward modeling or a doubly robust approach\n\n**R5:** Thank you for the suggestion. Estimators that incorporate reward modeling fall under model-based approaches, while those that do not are considered model-free. In this work, we primarily focus on model-free estimators. However, we did explore combining our estimator with the doubly robust (DR) approach, as discussed in Appendix G.3, and found that the resulting DR-LSE variant outperforms other baselines. Importantly, the non-linear structure of LSE does not introduce significant complications in this integration. For a fair comparison, we did not explore reward modeling based directly on the LSE framework, as our definition of LSE is grounded in weighted rewards rather than direct reward estimation. Nonetheless, we find this direction promising and plan to consider it in future work.  \n\n---\n**References:**\n\n[1]- Schulman, John, et al. \"Proximal policy optimization algorithms.\"", "claims_and_evidence": "Major Claims\n- Lower variance and bias–variance trade-off: By taking a log-sum-exp over the weighted rewards, the estimator becomes less sensitive to large outlier samples.\n\n\n- Robustness under heavy-tailed reward distributions: They provide a theoretical analysis under a ($1 + \\varepsilon$)-th moment assumption, which accommodates unbounded or heavy-tailed random variables.\n\n\n- Favorable regret/convergence bounds in off-policy learning: They prove an $\\mathcal{O}\\left(n^{-\\frac{\\varepsilon}{1+\\varepsilon}}\\right)$ convergence rate, which interpolates between $\\mathcal{O}(n^{-1/2})$ and $\\mathcal{O}(n^0)$ depending on the bounding of higher moments.\n\n\n- Empirical gains: The authors demonstrate in synthetic and real-ish tasks (EMNIST or KUAIREC-like data) that the LSE estimator can outperform baselines in terms of MSE (in OPE) or final policy accuracy (in OPL).\n\nEvidence\n- Theory: Theorem 5.3 (regret bounds) and Propositions 5.5/5.7 (bounds on bias and variance) offer analytical proof that LSE yields guaranteed convergence rates and improved variance control, provided certain moment assumptions.\n\n\n- Experiments: On synthetic data, the LSE exhibits lower MSE and variance than standard IPS or other model-free estimators (PM, ES, IX, OS). On EMNIST-based bandit tasks, it achieves good accuracy even with noisy reward signals or estimated propensity scores.\n\nThese results collectively support the authors’ main claims. Some details (like data-driven choice of \\lambda) are shown in appendices, along with further ablations and real-data results.", "methods_and_evaluation_criteria": "Core method: \n- The LSE estimator, $V_{\\text{LSE}}^\\lambda$​, applies $\\frac{1}{\\lambda} \\log \\left(\\frac{1}{n} \\sum_{i=1}^{n} e^{\\lambda r_{i} w_{\\theta}\\left(a_{i}, x_{i}\\right)}\\right)$ with a tunable parameter $\\lambda<0$.\n\n\nEvaluation:\n- In OPE, they empirically compare MSE, variance, and bias across multiple estimators.\n\n\n- In OPL, a learned policy $\\pi_{\\theta}$ is optimized by maximizing the LSE-based objective. The main metric is regret or final classification accuracy after learning.\n\n\n- Baselines: The paper carefully compares against standard IPS variants (e.g., truncated IPS), exponent smoothing (ES), power-mean (PM), self-normalized IPS (SNIPS), and so on.\n\nAll these benchmarks and metrics (variance, MSE, accuracy, regret) align with accepted practice in bandit OPE/OPL research.", "theoretical_claims": "The authors present:\n\n- Regret Analysis (Theorem 5.3 & Proposition 5.4): Shows the LSE-based OPL converges at $\\mathcal{O}(n^{-\\tfrac{\\varepsilon}{1+\\varepsilon}})$ under a heavy-tailed assumption on weighted rewards. \n\n\n- Bias and Variance Bounds (Propositions 5.5 & 5.7): Provide an upper bound on LSE’s bias in terms of  $|\\lambda|^{\\varepsilon}$  and a straightforward variance bound that is no greater than that of IPS under second-moment assumptions.\n\n\n- Robustness: Theorem 5.9 addresses noisy reward distributions, bounding the regret to show that total variation distance from the clean distribution plus the LSE’s own hyperparameter $\\lambda$ determine the final bound.\n\nThese proofs are given at length in the appendices, citing standard concentration inequalities (Bernstein, etc.) and carefully handling non-linear transformations. The logic in the statements is consistent, and no major errors stand out in the derivations.", "experimental_designs_or_analyses": "- Synthetic OPE: They design heavy-tailed reward distributions (Pareto-like or exponential) and random logging vs. target policies, measuring bias/variance/MSE across 10K replications.\n\n\n- Supervised-to-bandit OPL: On EMNIST, the authors transform classification data into bandit feedback with partial logging. They vary logging policy quality (temperature \\tau) and introduce both noisy propensity scores (modeled via inverse Gamma) and flipping reward noise.\n\n\n- Baselines: They compare with up to 7–8 standard baseline methods.\n\n\n- Metrics: MSE in OPE; classification accuracy for learned policies in OPL.\n\n\n- Findings: LSE typically has lower MSE and variance than baselines in OPE, and yields better policy performance in OPL, especially under heavier reward tails or noisier propensity scores.\n\nThese experiment designs match the paper’s stated goals, although the authors might highlight more real-world scale tasks in future. The demonstration is nonetheless credible for a conference submission.", "relation_to_broader_scientific_literature": "- The paper extends model-free OPE approaches (IPS, truncated IPS, ES, PM, IX, etc.) by introducing a non-linear transformation that can handle outliers.\n\n\n- The approach is reminiscent of “robust mean estimation” under heavy tails (median-of-means, trimmed mean), but specialized to importance-weighted bandit feedback.\n\n\n- The results connect to well-known bandit or offline RL settings under “pessimistic” or distribution-shift assumptions, though here it focuses specifically on the LBF dataset with (potentially) heavy-tailed or noisy rewards.\n\nOverall, the authors do cite standard references (IPS, ES, PM, etc.) and situate their work among current OPE/OPL techniques. Additional connections to sub-Gaussian bounding and robust M-estimators are also discussed.", "essential_references_not_discussed": "The paper covers the most relevant prior model-free approaches to mitigate variance in off-policy evaluation (IPS, truncated, ES, PM, etc.). It also references works on heavy-tailed or robust bandit algorithms. No obviously critical references are missing. I believe the submission includes enough prior work for the standard context.", "other_strengths_and_weaknesses": "Strengths\n- This  log-sum-exp transformation is conceptually simple yet yields robust performance for unbounded or noisy data.\n\n\n- Theoretical thoroughness: They provide formal bias-variance bounds and regret guarantees that unify heavy-tailed analysis with a single hyperparameter $\\lambda$.\n\n\n- Robustness: The authors show how the LSE estimator can remain stable even with substantial reward noise or propensity mis-specification.\n\n\n- Empirical validations: They compare thoroughly to an array of baselines.\n\nWeaknesses\n- The paper discusses data-driven methods in the appendices, but real deployments might need more straightforward or adaptive selection heuristics.\n\n\n- The approach is a single-pass aggregator, so computational complexity is no worse than other OPE methods, but potential memory or tuning overhead for extremely large datasets is not deeply addressed.\n\n\n- They rely mostly on small to medium transformations (EMNIST or partial KUAIREC). The method’s performance in large, production-scale logs (with tens of millions of rows) is not tested.", "other_comments_or_suggestions": "See the above weaknesses section.", "questions_for_authors": "How does one best pick $\\lambda$ in practical scenarios? Is there a recommended cross-validation strategy you find most reliable?\n\nCould the LSE concept apply similarly in off-policy RL with trajectories? Are there any theoretical or practical obstacles?\n\nHave you tried combining LSE with direct reward modeling or a doubly robust approach? If so, does the non-linear structure complicate it?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes to use log-sum-exp (LSE) operation as off-policy estimator for both OPE and OPL and demonstrate its effectiveness both theoretically and empirically. The paper received positive scores across the board, where all the reviewers praise the novelty of using LSE in the context of OPE/OPL, as well as the solid technical and theoretical contribution. There were some minor concerns/clarifications which were largely resolved during the author-reviewer discussion phase. Given the overall very positive feedback, I am voting for accept.
Decision: Accept (spotlight poster)