Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning
Authors: Otmane Sakhi
Imad Aouali
Pierre Alquier
Nicolas Chopin
Venue: NeurIPS 2024 spotlight (2024)
Keywords: offline contextual bandit
off-policy evaluation
off-policy selection
off-policy learning
pessimism
Primary area: reinforcement_learning
TL;DR: We propose a novel, pessimistic off-policy estimator that logarithmically smoothes the importance weights, leading to improved policy evaluation, selection and learning strategies.

Abstract: This work investigates the offline formulation of the contextual bandit problem, where the goal is to leverage past interactions collected under a behavior policy to evaluate, select, and learn new, potentially better-performing, policies. Motivated by critical applications, we move beyond point estimators. Instead, we adopt the principle of _pessimism_ where we construct upper bounds that assess a policy's worst-case performance, enabling us to confidently select and learn improved policies. Precisely, we introduce novel, fully empirical concentration bounds for a broad class of importance weighting risk estimators. These bounds are general enough to cover most existing estimators and pave the way for the development of new ones. In particular, our pursuit of the tightest bound within this class motivates a novel estimator (LS), that _logarithmically smoothes_ large importance weights. The bound for LS is provably tighter than its competitors, and naturally results in improved policy selection and learning strategies. Extensive policy evaluation, selection, and learning experiments highlight the versatility and favorable performance of LS.

Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning
Otmane Sakhi
Imad Aouali CREST, ENSAE Criteo Al Lab, Paris, France i aouali@criteo. com
Criteo Al Lab, Paris, France o sww.sahhhiooo @criteo.rr...... com
Pierre Alquier ESSEC Business School, Singapore alquierdessec.ee edu
Nicolas Chopin CREST, ENSAE
nicolas cww.in@essoo....cccccooo fr
Abstract
This work investigates the offline formulation of the contextual bandit problem, where the goal is to leverage past interactions collected under a behavior policy evaluate, select, and learn new, potentially setter-performing, policies. Motivated by critical applications, principle of pessimism where we construct upper bounds that assess policy's 's worst- case performance, enabling to confidently select and learn improved policies. Precisely, we introduce novel, fully empirical concentration bounds for a broad class of importance weighting risk estimators. These bounds general enough cover most existing estimators and pave the way for the development of new ones. In particular, our pursuit of the tightest bound within this class motivates novel estimator (LS), that logarithmically smooths large importance weights. The bound for LS is provably tighter than its competitors, and naturally results in improved policy selection and learning strategies. Extensive policy evaluation, selection, and learning experiments highlight the versatility and favorable performance of LS.
move beyond point estimators. Instead, we adopt the
Introduction
In decision-maie making under uncertainty, offline contextual bandit [16] presents a practical framework for leveraging past interactions with an environment to optimize future decisions. This comes into play when possess logged data summarizing agent's past interactions [10]. These interactions, typically captured as of the environment. Each tuple represents single round of interaction, where the agent observes a context (including relevant features), takes an action according to its current policy, often called behavior policy, and receives reward that depends both the observed context and the taken action. This framework is prevalent in interactive systems like online advertising, music streaming, and video recommendation. In online advertising, for instance, the user's profile the context, the recommended product is the action, and the click-through rate (CTR) is the expected reward. By learning from past interactions, the recommender system tailors product suggestions to individual preferences, maximizing engagement and ultimately, business success.
ceatttactiionewwaann tuples, hold valuable insights into the underlying dynamics
To optimize future decisions without requiring real-time deployments, this framework presents us with three tasks: off-policy evaluation (OPE) [16], off-policy selection (OPS) [32], and off-policy learning (OPI.) [55]. OPE estimates the risk: the negative of expected reward that targel policy would achieve, essentially predicting its performance if deployed. OPS selects the best-performing
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

policy from finite set of options, and OPL finds the optimal policy within an infinite class of policies. In general, OPE is an intermediary step for OPS and OPL since its primary goal is policy comparison.
significant amount of research in OPE has centered around Inverse Propensity Scoring (IPS) estimators [24, 16-18, 60, 19, 54, 38, 32, 45]. These estimators rely on importance weighting to address the discrepancy between the target and behavior policies. While unbiased under some conditions, IPS induces high variance. To mitigate this, regularization techniques have been proposed for IPS [10, 38, 54, 5. 21] trading some bias for reduced variance. However, these estimators can still deviate from the true risk, undermining their reliability for pecision-making especially in critical applications. In such scenarios, practitioners need estimates that cover the true risk with high confidence. To address this, several approaches focused on constructing either asymptotic [10, 48, 15] or finite sample [32, 21]. high probability, empirical upper bounds on the risk. These bounds evaluate the performance of policy in the worst-case scenario, adopting the principle of pessimism [27].
If this principle is used in OPE, it is central in OPS and OPL, where strategies are inspired by, or directly derived from, upper bounds on the risk [55, 35, 32, 49, 5, 59, 21]. Examples for OPS include Kuzborskij et al. [32] who employed an Efron-Stein bound for self-normalized IPS, or Gabbianelli al. [21] that based their analysis on an upper bound constructed with the Implicit Exploration estimator. Focusing on OPL, Swaminathan and Joachims [55] exploited the empirical Bernstein bound [36] alongside the Clipping estimator to motivate sample variance penalization. This work was recently improved by either modifying the penalization [59] or analyzing the problem from the PAC-Bayesian lens [35]. The latter direction was further explored by Sakhi et al. [49], Aouali et al. [5, 7], Gabbianelli et al. [21] resulting in tight PAC-Bayesian bounds that can be directly optimized.
Existing pessimistic OPE, OPS, and OPL approaches involve analyzing the concentration properties of pre-defined risk estimator, often chosen to simplify the analysis. We propose different approach: we derive general concentration bounds applicable to broad class of regularized IPS estimators and then identify the estimator within this class that achieves the tightest concentration bound. This leads to tailored estimator, named Logarithmic Smoothing (LS). LS enjoys several desirable properties. It concentrates at a Sab-Gaussian rate, and has a finite variance without being necessarily bounded. Its concentration upper bound allows us to evaluate the worst-case risk of any policy, enables us to derive a simple OPS strategy that directly minimizes our estimator akin to Gabbianelli et al. [21], and achieves state-of-the-ard learning guarantees for OPL when analyzed within the PAC-Bayesian framework akin to [35, 49, 5, 7, 21].
This paper is structured as follows. Section introduces the necessary background. In Section 3, we provide unified risk bounds for broad class of regularized IPS estimators, for which LS enjoys the tightest upper bound. In Section 4, we analyze LS for OPS and OPL, and we further extend the analysis within the PAC-Bayesian framework. Extensive experiments in Section 5 highlight the favorable performance of LS, and Section provides concluding remarks.
2 Setting and background
Offline contextual bandit. Let X' C. Idd be the context space, which is a compact subset of Rd, and let A = [K] be a finite action set. An agent's actions are guided by stochastic and stationary policy π E II within a policy space II. Given a context x E X, (-1xx) is probability distribution over the action set A: x (a] is the probability that the agent selects action in context Then, an agent interacts with a contextual bandit over n rounds. In round é E [n]. the agent observes a context 34 D where v is a distribution with support X. After this, the agent selects an action ag ~ T (-((a)). where To is the behavior policy of the agent. Finally, the agent receives a stochastic cost C [-1,0] that depends on the observed context x; and the taken action dz. This cost e is sampled from a cost distribution p(-12; a.). This leads to n-sized logged data, D,, = (x,, a, c: Ca)ie(m) where tuples (Ii,, as, C:) for i E [n]] are i.i.d. The expected cost of taking action a in context x is c(z, a) Ee-pt-la,a)) [c), and the costs are negative because they are interpreted as the negative of rewards. The performance of a policy क E II is evaluated through its risk, which aggregates the expected costs c(x, a) over all possible contexts & E X' and taken actions a E A by policy म, such as
R(T) (/ [c] E E [c(2, a)]
(1)
The main goal is to use logged dataset D, to enhance future decision-making without necessitating live deployments. This often entails three tasks; OPE, OPS, and OPL. First, OPE is concerned

---

with constructing an estimator (T) of the risk R(T) of fixed target policy и and study its deviation, aspiring for R., (T)) to concentrate well around R(TT). Second, OPS focuses selecting the best performing policy "i from a predefined and finite collection of target policies {TI..... Tn effectively seeking to determine argminke[m R( Third, OPL aims to find a policy R within the potentially infinite policy space II that achieves the lowest risk, essentially aiming to find argmin.ent R( In general, both OPS and rely on OPE's initial estimation of the risk.
Regularized IPS. Our work focuses on the inverse propensity scoring (IPS) estimator [24]. IPS approximates the risk of a policy π. R((T). by adjusting the contribution of each sample in logged data according to its importance weight (IW), which is the ratio of the probability of an action under the target policy æ to its probability under the behavior policy no.
Rg (T)
1 - n i=1
Σ
Wn (2is a;);,
where for any (z, a) X' x A, w. (1, (z, a) TT T(ll)) / are the IWs. IPS is unbiased under the coverage assumption (see for example Owen [39. Chapter 9I). However, it can suffer high
variance, which tends to scale linearly with IWs [57]. This issue becomes pronounced when there is significant discrepancy between the target policy and the behavior policy To. To mitigate this, a common strategy consists in applying a regularization function h : [0. 1]2 [-1,0] + (-00, 0] to (a|z), To [a] 2) and c. This function is designed to reduce the estimator's 's variance at the cost of introducing some bias. Formally, the function h needs to satisfy the condition (C1), that defined by
h satisfies (C1) > V(p, q, c) E [0, 112 x [-1,0], pe/9 S h(p, c) s O.
(C1)
With such function h, the regularized IPS estimator reads
( = 7 Σ h (T(a)))))) oo(a, c/) 71
n
1
h4
(3)
where h4 = h (x(((a)))) To ()))) We recover standard IPS in (2) when hp,g,c) pc/4.
Numerous regularization functions h were studied in the literature. For example,
h(p, c) min(p/q. M)c, M E R+ = Clipping [10]
(4)
h(p, q.c pc/4 E [0,1] = Exponential Smoothing [5].
h(p, q, c) pc/(q+ 0 = Implicit Exploration [21].
Other IW regularizations include Harmonic [38] and Shrinkage [54]. With h satisfying (CI), we can
derive our core result: a family of high-probability bounds that hold for regularized IPS.
Pessimistic off-policy evaluation
Standard OPE directly uses estimates of the risk, without capturing their associated uncertainty. This limits its effectiveness in critical applications. Pessimistic OPE addresses this issue by relying on finite sample, high-probabillty upper bounds to assess any policy's 's worst-case risk [15, 32]. This section contributes to this effort and focuses on providing novel, finite sample, tight upper bounds on the risk. This is achieved by deriving general bounds applicable to regularized IPS in (3).
3.1 Preliminaries and unified risk bounds
Let >> 0, E 11, and l satisfying (CI), we define
(=) 1 a h
and
(x(x)) = (1 exp(-Xr)), Vo R,
(5)
where MM)((T)) (IT) is the empirical ε-th moment of regularized IPS (T). and d/h : R + is a
contraction function satisfying (x) S for any R. Then, we state first result.
Proposition (Empirical moments risk bound). Let क II, 2 1, 8 (0, 1], X > 0, and satisfying (C1). Then it holds with probability at least - 8 that
2L
X-1
h.e (T) + In(1/01), (6)
R(T) & (T), with U2 - 1i
+
An
2=2
where ub and M (TT) are both defined in (5), and recall that xx(x)= S
3

---

In Appendix F.1, we provide detailed proof, leveraging Chernoff bounds with careful analysis of the moment- -oenertgenneaating function. This results in the first empirical, high-order moment bound for offline contextual bandits, with several advantages. First, the bound applies to any regularization function h that satisfies the mild condition (CT), enabling the design of a tailored that minimizes the bound. Second, it relies solely on empirical moments, without assuming the existence of theoretical moments. Third, the bound is fully empirical and tractable, facilitating efficient implementation of pessimism. Lastly, the parameter L controls the number of moments used, allowing a balance between bound tightness and computational cost. Specifically, for sufficiently small values of X, higher values of L yield tighter bounds, though potentially at the cost of increased computational complexity would need to compute higher order moments. This is formally stated as follows.
Proposition 2 (Impact of L). Let π E II, 5 E (0, 1]. X > 0, L 2 1, and h satisfying (CI). Then,
2L + 2 (2L + 1)
U (T) ( S u (T).
A min sE(m]
From (7), the bound U.A (x) in (6) becomes a decreasing function of L when À S min (1/[kx)) suggesting that for sufficiently small X, the tightest bound is achieved -- xo. This condition on À also depends on the values of h. highlighting the importance of the regularizer choice h. In fact, once we evaluate our bounds at their optimal regularizer function h, this condition on À becomes unnecessary when comparing some of the optimal bounds. Specifically, we demonstrate in the following proposition that the bound with L can be always improved by increasing L. Proposition 3 (Comparison of our bounds). Let π E II, and X > O, we define
(²) = min (
U (r), and hz.7 = argmin UZ,
(8)
is
with the minimum taken over h satisfying (C1). Then, for any X > 0, it holds that for any L >>> (T( s UU) In particular. for any X >> 0,
1,
U ( S (T)).
(9)
Proposition 3 shows that, irrespective of the value of X, the bound with L - 1 can be always improved by bounds of increased moment order L, evaluated their optimal regularizer h.,,.- This result encourages us to study bounds with high moment order L, especially if we can derive their optimal regularizers L. To this end, we examine two cases: L which results in an empirical second- moment bound, and L + oc, yielding tight bound that does not require computing high-order moments. For each case, we identify the function h that minimizes the bound. If the minimizer for L= 1 is a variant of the clipping estimator [10], minimizing I. - oc motivates a novel logarithmic smoothing estimator, We begin by analyzing our empirical moment risk bound at I. =
3.2 Global clipping
Corollary (Empirical second-moment risk bound with L = 1). Let v E II, de h satisfying (C1). Then it holds with probability at least 1 - 5 that
E (0, 11, x> > 0, and
R(*) S Φb (1t (T) + 2 M (T) 1n(1/0))
(10)
Xn
This is direct consequence of (6) when I. = 1. The bound holds for any h satisfying (C1). Thus we search for a function h.,1 that minimizes bound in (10). This function h-, writes
(p, 9, c) = - min(p cl/g. 1/A).
(11)
In particular, if we assume that costs are binary, in (4) with parameter M = 1/A. This is because miin(ccpp//a 1/A) = min (p/g. 1) e when is binary. This motivates the widely used clipping estimator [10]. However, this also suggests that the standard way of clipping (as in (4)) is only optimal' for binary costs. In general, the cost should also be clipped (as in (11)). Finally, with a suitable choice of X = ((1/v)) our bound in Corollary 4, using clipping (i.e., h ht.1). outperforms the existing empirical Bernstein bound [55]. which was specifically derived for clipping. This confirms the strength of our general bound, as minimizing it results in a bound with tighter concentration than specialized bounds. Appendix F.4 gives the the proof to find h. and formal comparisons with empirical Bernstein are provided in Appendix F.5. In the next section, we study our general bound when we set + Do.
{-1, 0). then h.,1 corresponds to clipping
Here, optimality of function / is defined with respect our bound with L =1 (Corollary 4).

---

3.3 Logarithmic smoothing
Corollary (Empirical infinite-mone moment bound with L 20). Let π II. Ee (0. 11, 0, and
satisfying (C1). Then it holds with probability at least 1 - 8 that
log (1 Xh.) In(1/0)
R(T) db
(12)
An
Appendix F.6 provides detailed proof. Setting L + 0o in (6) results in the bound in Corollary 5, which has different properties than Corollary 4. The resulting bound has simple expression that does not require computing high order moments. This means that we can obtain the best of both worlds, a tight concentration bound with additional computational complexity. As the bound is increasing in h, the function ha, that minimizes this bound is he (p. q. pe/q. This corresponds to the standard IPS in (2). This differs from the L = 1 bound in Corollary that favored clipping. This shows the impact of the moment order L on the optimal function h. For any E II, applying the bound in Corollary with the optimal ho leads to U (TT), of the following expression:
Im(1/6))
(x) = 15 (T)
(13)
An Even if we set h. h. (p. c) = pc/q (without IW regularization), U (TT) can be seen as a risk upper bound of novel regularized IPS estimator (satisfying (CI)), called Logarithmic Smoothing (LS):
log (1 (1;, (s)ee)
(14)
The LS estimator in (14) is defined for any non-nneativee X 2 0. with its bound in (13) holding for any positive > No- tably, À = O retrieves the standard IPS estimator in (2), while introduces a bias-variance trade-off by logarithmically smoothing the IWs (Figure 1). This estimator acts as a soft, differentiable variant of clipping with parameter 1/2. A Taylor expansion of our estimator around À 0 yields
IFS Clipping M
-.
L5, A 0.05
20
n2 " (w (wx(en)a))))) n2
("
(T) R. (T)
0
10 20
30 40
50
Importance Weight at.
Thus, LS is pessimistic estimator by design, implicitly im- plementing a form of Sample All Moments Penalization, which generalizes the Sample Variance Penalization [55]. To examine the statistical properties of our estimator, introduce
Figure 1: LS with different As.
(wa (z, a)c)²
Sx(T) E
(15)
(1
(w, (J))
which quantifies the discrepancy between т and Tо- Notably, SX(T) is always smaller than the second moment of the IW, effectively interpolating between weighted first moment (A >>>>> 1) and the second moment (A 0) of IPS. This quantity SX characterizes the concentration properties of the LS estimator akin the coverage ratio for estimator [21]. With Sy defined, we proceed by bounding the mean squared error (MSE) of our estimator, specifically bounding its bias and variance.
Proposition 6 the bias and the variance of the LS estimator. Then we have that
trade-off). Let क E II and X 2 0. Let B* (T) and (*)) be respectively
0 < B* (TT) (T)) and V²TT) S SA(T)
n
Moreover, it holds that for any X > O, the variance is finite as V* S [R(T)]/An S 1/2n.
We observe that both the bias and variance are controlled by (T(.). Particularly, X = recovers the IPS estimator in (2), with zero bias and variance bounded by E [w²(x, ax) /n. When
0, bias-variance trade-off emerges. The bias is always non- non-negative and is capped at AS)(T), which diminishes to zero when À is small and goes to [R(T] as À increases. Conversely, the variance decreases with a higher X. Notably, À > ensures finite variance bounded by 1/ /An, despite the estimator being unbounded. This is different from previous estimators that relied on bounded functions to ensure finite variance. We also prove in the following that a good choice of = ((1 ensures that our LS estimator enjoys sub- Gaussian concentration [38].
5

---

Proposition 7 Guub-Gausiiaitty and comparison with Metelli et al. [38]). Ler IT E II, á E (0, 1] and À >>0 O. Then the following inequalities holds with probability at least 1 8:
In(2/0) An
and (T) R(T)) S ASX(T) + In(2/0)
R(T)) (T)
An
In particular, setting = X, = vI(2/0)/nBB (1x (I, a) yields that
[R( ( S v 2x ln(66))
(T)
where o² 21 [w (x. a)2 /n.
(16)
Thus, a particular choice of X ensures that RA (TT) is sub- Gaussian, with a variance proxy o² that improves on that obtained for the Harmonic estimator of Metelli et al. [38]. We refer the interested reader to Appendix E.2 for further discussions and proofs.
Next, we focus on the tightness of the LS upper bound in (13) as it will motivate our selection and learning strategies. Proposition already showed that U (x)). the bound of LS is tighter than (*). the bound in Corollary 4 evaluated at the Global clipping function h-,1- I- In this section, we compare the LS bound to the already tight IX bound presented by Gabbianelli et al. [21] and demonstrate in the following that the LS bound dominates it in all scenarios.
Proposition 8 (Comparison with IX of Gabbianelli et al. [2IJ). Let T E II, 8 EjO, 1] and À > 0, the IX bound from [21] states that we have with probability least - 5
1n(1/8) An
π <(a; (x:) To To(a; (24) + X/2
R(x) $ RA-1X (T) +
with R (T)
Cz.
(17)
Let (T) be the upper bound of (17), we have for any X >>> 0:
U S (T))
(18)
This result states that no matter the scenario. for any evaluated policy æ, and any chosen À >> the LS bound will be always tighter than IX. The gap between the LS and IX bounds increases when is small, or when the evaluated policy stochastic, as demonstrated and developed in Appendix F.8. These findings further validate the effectiveness of our approach, enabling us to identify the LS estimator, with an empirical bound that improves upon the tightest existing bounds. Consequently, we leverage the LS bound in the next section to derive our pessimistic OPS and OPL strategies.
4 Off Off-policy selection and learning
4.1 Off-policy selection
Let IIs {Ti ... 3m3 be finite set of policies. In OPS, the goal is to find πद E IIs that satisfies
π = argmin R(T) = argmin ((T)).
(19)
Elll,
ké(m)
As we do not have access to the true risk, we use data-driven selection strategy that guarantees the identification of policies of performance close to that of π². Precisely, for X > O, we search for
n = argmmi (x) = argmin R (TR)..
(20)
=Ell.
kE(m)
To derive our strategy in (20), we minimize the bound of LS in (13), employing pessimism [27]. Fortunately, in our case, this boils down to minimizing (T)),, since the other terms in the bound are independent of the target policy т. This allows us to avoid computing complex statistics [55, 32] and
does not require access to the behavior policy Tp. As we show next, it also ensures low suboptimality.
Proposition 9 (Suboptimality of our selection strategy in (20)). Let X > 0 and ō E (0, 1]. Then, it holds with probability at least å that
2 2 (21(2
0 < R(# R(x2) < (SA +
(21)
An
where SX(T), nhe and R are defined in (15), (19) and (20).

---

The derived suboptimality bound only requires coverage of the optimal actions (support of the optimal policy π"), and improves on IX suboptimality [21], matching the minimax suboptimality lower bound of pessimistic methods [34, 27, 28]. Appendix G.1 provides proof of this suboptimality bound, and we discuss how this suboptimality improves upon existing strategies in Appendix E.3. By selecting A = (2 for LS, we achieve a suboptimality scaling of O(//Vn).
0 M R(*)) - R(m)) - (1 + 1Sx (x.)) v (2
(22)
which ensures finding the optimal policy with sufficient samples. Additionally, the multiplicative constant smaller when To is close to n. confirming the known observation that it is easier to identify the best policy if it is similar to the behavior policy To.
4.2 Off-policy learning
Similar to how we extended the evaluation bound in Corollary 5 (which applies to single fixed target policy) to OPS (where applies to a finite set of target policies), we can further derive bounds for an infinite policy class II, enabling OPI. Several approaches have been proposed in previous work, primarily based on replacing the finite union bound over policies with more sophisticated uniform-convergene arguments. This was used by [55], which derived variance-sensitive bound scaling with the covering number [61]. Since these approaches incorporate a complexity term that depends only on the policy class, the resulting pessimistic learning strategy (which minimizes the upper bound) would be similar to the selection strategy adopted earlier, leading, for a fixed X, to
C(TT) An
# = argmin (T)
+
argmin (T). #Ell
(23)
#Ell
where C(II) is a complexity measure [61]. This learning strategy is straightforward because involves smooth estimator that can be optimized using first-order methods and does not require second-order statistics. However, analyzing this approach is more challenging because the complexity measure C(IT) varies depending on the policy class considered, is often intractable [49] and can only be upper bounded with problem dependent constants [28].
Instead of the method described above, we derive PAC-Bayesioe generalization bounds [37, 11] that apply to arbitrary policy classes. This framework has been shown to provide strong performance guarantees for OPL. in practical scenarios [49, 5]. The PAC-Bayesian framework analyzes the performance of policies by viewing them as randomized predictors [35]. Specifically, let F(O)- =
(Ja X + [K].0 0 E θ} be a set of parameterized predictors that associate the context x with the action fo(x) E [K]. Let P(O) be the set all probability distributions on O. Each distribution
Q E P()) defines policy mo by setting the probability of action a given context x as the probability that a random predictor fe ~ Q maps x to action a, that is,
(alx)) = Ea-q [1 [f( a]]
V(r a) E A.
(24)
This characterization is not restrictive as any policy can be represented in this form [49]. Deriving PAC- BiCC-Baesian generalization bounds with this policy definition requires the regularized IPS to be linear in the target policy [35, 5, 21J. Our estimator LS in (14) is non-linear in Therefore, for this PAC-Bayesian analysis, we introduce a linearized variant of LS, called LS-LIN, and defined as
π T
(Ta) log
Ac;
RA-LIN n
(25)
n
To (a, (x:)
which smooths the impact of the behavior propensity no instead of the IWs /T. We provide in the following a core result of this section, the PAC- MAC-Bayesian bound that defines our learning strategy.
Proposition 10 (PAC-Bayes learning bound for ReA LIN), Given a prior P E P(O), 5 E (0, 1] and > 0, the following holds with probability at least 8:
KC(Q]IP)+ + )
YQ E P(O), R(TQ) S 1bx (R) (T4)+ +
(R.
(26)
An
where KC(Q))P) is the Kullback-Leible divergence from P to Q.
7

---

PAC-Bayes bounds hold uniformly for all distributions Q E P(0) and replace the complexity measure (II)) with the divergence KC(Q]IP) from a reference prior distribution P. Extensive research focuses on identifying the best strategies for choosing this prior P [40]. While these bounds hold for any fixed prior P. in practice, is typically set to the distribution inducing the behavior policy no. meaning P satisfies To T. This leads to an intuitive learning principle: by minimizing the upper bound, we seek policies with good empirical risk that do not deviate significantly from wo-
Our bound can also be obtained using the truncation method from Alquier [1, Corollary 2.5]. This bound surpasses the already tight PAC-Bayesian bounds derived for Clipping [49], Exponential Smoothing [5], and Implicit Exploration [21], resulting in the tightest known generalization bound in OPL. Appendix G.2 gives formal proof of this bound and comparisons with existing PAC-Bay -ay-ssan bounds can be found in Appendix E.4. For fixed À and a fixed prior P. we derive a learning strategy that minimizes the upper bound for subset (()) C P(0) of distributions, seeking
KCCQQ
Qn
argmin QEC(O)
RA-LIN (TQ)+
and setting # =Q_..
(27)
An
(27) tractable and can be efficiently optimized for various policy classes [49, 5]. Below, we analyze its suboptimality compared to the best policy in the chosen class, "Q- argmingec(e)) R(Tq).
Proposition 11 (Suboptimality of the learning strategy in (27)). Let 0, P L(0) and 8 (0, 1]. Then, it holds with probability at least 1 -5 that
2 ((KC(Q"))P) + In(288))
0 Σ [(#)))) - R(TQ-) s (TT))) +
(28)
An
where Sy (T) = E (r(alr)c>(<$B(a)))
XTo(a|x))c] and ft is defined in (27).
Our suboptimality bound only requires coverage of the support of the optimal policy TQ.. This bound matches the minimax suboptimality lower bound of pessimistic learning with deterministic policies [28]. Appendix G.3 provides a proof of Proposition 11, while Appendix E.5 discusses the suboptimality bound further and proves that improves on the IX learning strategy of [21, Section 5]. Setting X₂ = // guarantees us a suboptimality that scales with ((1/V)) as
R(#5)) R(mQ-) < (2S (TQ-)) KC(Q" + ln(2/6))
By setting the reference P to the distribution inducing we find that the learning suboptimality is reduced when the behavior policy To is close to the optimal policy тQ-. This is similar to the suboptimality for our selection strategy. The suboptimality upper bound reflects a common intuition in the OPL literature: pessimistic learning algorithms converge faster when To is close to sQ*
5 Experiments
Our experimental setup follows the standard mullicllas--t-bbaddee conversion used in prior studies [18, 55]. Each multi-class dataset has features and labels and we convert it to contextual bandit problems where contexts correspond to features and actions to labels. Precisely, the reward r for taking action (label) with context (features) x is modeled as Bernoulli with probability Ps =
+ 1 = p(x)] (1 2e), where p(x) be the true label of features x, and is noise parameter. In particular, the true label p(x) represents the action with the highest average reward for context æ. This setup ensures average reward of 1 for the optimal action p(x) and for all others, constructing a logged bandit feedback dataset the form { 0g G Jejj), where 6 = -r;; is the associated cost.
5.1 Off-policy evaluation and selection experiments
For both evaluation and selection, we adopt the same experimental design as [32] to facilitate the comparison. We consider exponential target policies x <aaxz) x fxp() with J temperature controlling the policy's entropy and f(a, 2) the score of the item for the context z. We use this to define ideal policies as zideal (ala)) x exp(=T(p(x)) = a)), and also create faulty, mismatching policies for which the peak is shifted to another, wrong action for set of faulty actions F C [K]. To recreate real world scenarios, we also consider policies directly learned from logged bandit feedback, of the form ayue (a|z) exp 2 and Ta (a|z) x exp( x (8M), with their parameters learned
8

---

Table 1: Bound's tightness ((U(T)/((T) - 1|) with varying number of samples of the kropt dataset.
Number of samples
SN-ES
cIPS-EB
IX
cIPS-L=1 (Ours)
LS (Ours)
2
1.000
0.917
0.373
0.364
0.362
29
1.000
0.732
0.257
0.289
0.236
2
0.794
0.554
0.226
0.240
0.213
2
0.649
0.441
0.171
0.197
0.159
212
0.472
0.327
0.126
0.147
0.117
213
0.374
0.204
0.062
0.077
0.054
214
0.257
0.138
0.041
0.049
0.035
by respectively minimizing the IPS [24] and SN [56] empirical risks. More details on the definition of the different policies are given in Appendix H. Finally, 11 real multiclass classification datasets are chosen from the UCI ML Repository [8] (See Table 3 in Appendix H.1.1) I.) with various number of samples, dimensions and action space sizes conduct experiments".
(OPE) Tightness of the bounds. Evaluating the worst case performance of policy is done through evaluating risk upper bounds [10, 32]. This means that better evaluation will solely depend on the tightness of the bounds used. To this end, given a policy т, we are interested bounds (Tr) with a small relative radius IU/ (T) (R() - 1/. We compare our newly derived bounds (cIPS- for U/ and LS for U* both with À 1//n) to empirical evaluation bounds of the literature: SN-ES: the Efron Stein bound for Self Normalized IPS [32], cIPS-ER -B: Empirical Bernstein for Clipping [55] and the recent IX: Implicit Exploration bound [21]. The first experiment uses the kropt dataset with e = 0.2, collects bandit feedback with faulty behavior policy (with T = 0.25) to evaluate an ideal policy (r 0.1), and explores how the relative radiuses of the considered bounds shrink while varying the number of datapoints. Table I compiles the results of the experiments and suggest that the LS bound is tighter than its competitors no matter the size of the feedback collected. The second experiments uses all 11 datasets, with different behavior policies (To E {0.2, 0.25, 0.3}) and different noise levels E (0., 0.1, 0.2)) to evaluate ideal policies with different temperatures (r E {0.1, 0.2, 0.3. 0.4, 0.5)), defining ~ 500 different scenarios to validate our findings. We plot in Figure the cumulative distribution of the relative radius of the considered bounds. We observe that while cIPS-L=1 and IX can be comparable, the LS bound is tighter than all its competitors. We also provide detailed results Appendix H.1.2 that further confirm the superiority of the LS bound.
(OPS) Find the best, avoid the worst policy. Policy selection aims at identifying the best policy among a set of finite candidates. practice, we are interested in finding policies that improve on To and avoid policies that perform worse than To. To replicate real world scenarios, we design an experiment where To faulty policy (7 0.2). that collects noisy (E 0.2) interaction data, some of which is used to learn Tgms, Tg and that we add to our discrete set of policies I= = {ao, π ideal Tgar,, Tge).. The goal is to measure the ability of our selection strategies to choose from I,,,,, better performing policies than a strategy can select worse performing policies, better performing or the best policy. Our goal in these experiments is to empirically validate the pitfalls of point estimators while confirming the benefits of using the pessimism principle. To this end, we compare pessimistic selection strategies to policy selection using the classical point estimators IPS [24] and SN [56]. The comparison is conducted on the 11 UCI datasets with 10 different seeds resulting in I 110 scenarios. We plot in Figure 2 the percentage of time each method selected the best policy, better
We thus define three possible outcomes:
worse policy than To. While risk estimators can identify the best policy, they are unreliable as they can choose worse performing policies than no. catastrophic outcome in critical applications. Pessimistic selection is more conservative, as it avoids poor performing policies completely and empirically confirms that tighter upper bounds result in better selection strategies: LS upper bound is less conservative and finds best policies the most (comparable to SN) while never selecting poor performing policies. Fine grained results (for each dataset) be found in Appendix 1.1.3.
5.2 Off-policy learning experiments
We follow the successful off policy learning paradigm based on directly minimizing PAC-Bayesian risk generalization bounds [49, 5] as it comes with guarantees of improvement and avoids hyper-
The code can be found at https: hww.h///.../oottoooooooooleeeooe

---

OPE: Comparing Tightness the Bounds of Pessimistic Methods
.PPS: Performance of Selected Policies Compared to Logging Policies
1.0
100
SN-ES
Percentage Worse, Better and Best
Warse
CPS-EB
Better
0.8
80
Dest
Cunulative Probability
CPS L-1 (Ours)
L5 (Durs)
0.6
60
0.4
40
0.2
20
8.00
0.4
0.6
0.8
1.o
SN-ES cIPS-EB
ciPS-1=1
Tightness Upper (Relative Radius)
Selection Strategy (cIPS-L-1 LS are Ours)
Figure 2: Results for OPE and OPS experiments.
cIPS
cvcIPS
ES
IX
LS-LIN (Ours)
14.48%
21.28%
7.78%
24.74% 36.70%
26.31 %
rI(((
28.13%
33.64%
29.44%
36.76% %
Table 2: OPL: Relative Improvement of guaranteed risk and true risk averaged over 200 scenarios.
parameter tuning. For comparable results, we use the same 4 datasets (described in Appendix H.2, Table 7) as in [49, 5] and adopt the LGP: Linear Gaussian Policies [49] as our class of parametrized policies. For each dataset, use behavior policies trained on small fraction of the data in super- vised fashion, combined with different inverse temperature parameters a E {0.1, 0.3, 0.5, 0.7, 1.3 to cover cases of diffused and peaked behavior policies. These policies generate for 10 different seeds, 10 logged bandit feedback datasets resulting in 200 different scenarios to test our learning approaches. In the PAC-Bayesian OPL paradigm, directly and obtain the learned policy as the bound's s minimizer f (as in (27)). With hh obtained, we interested in quantities: The guaranteed risk by the bound, which is the value of the bound U(+ at its minimizer. This quantity reflects the worst case performance of the learned policy, a lower value implies stronger performance guarantees. We are also interested in the true risk of the minimizer the bound R(*).) as it translates the performance of the obtained policy acting on unseen data. As this learning paradigm is based on optimizing tractable, generalization bounds, we only compare our approach to methods that provide them. Precisely, we compare our LS-LII learning strategy in (27) strategies based minimizing off-policy PAC Bayesian bounds from the literature: clipped IPS (cIPS) and Control Variate clipped IPS (cvcIPS) [49], Exponential Smoothing (ES) [5] and Implicit Exploration (IX) [21]. The results are summarized in Table where we compute:
minimize the empirical upper bounds (x)
rI(x) (R(m)) (R)()) R(**)) (R(m)) 2)) =))(R()o) + 1),
the improvement over R(TO) achieved by minimizing the different bounds in terms of x E (U, R} (guaranteed risk and true risk respectively), relative an ideal improvement. This metric helps us normalize the results, and we report its average over 200 different scenarios, with results in bold being significantly better. Fine grained results can be found in Appendix H.2.4. We observe that the LS-LIN PAC-Bayesia bound improves substantially on its competitors in terms of the guaranteed risk, and also obtains the best performing policies (on par with the IX PAC- PAC-Bayesian bound).
Conclusion
Motivated by the pessimism principle, we have derived novel, empirical risk upper bounds tailored for the regularized IPS family of estimators. Minimizing these bounds within this family unveiled Logarithmic Smoothing, simple estimator with good concentration properties. With its tight upper bound, LS confidently evaluates a policy, and shows provably better guarantees for both selecting and learning policies than all competitors. Our upper bounds remain broadly applicable, only requiring negative costs. While this condition does not impact importance weighting estimators, does not hold for doubly robust estimators. Extending our approach to derive empirical bounds for this type of estimators presents a nontrivial, yet interesting task to explore future work. Another potential extension would be to relax the i.i.d. assumption of the contextual bandit problem to address, the general offline Reinforcement Learning setting. This direction will introduce a more challenging estimation task and requires developing new concentration bounds.
10

---

References
[1] Pierre Alquier. Transductive and Inductive Adaptative Inference for Regression and Density Esti- mation. Theses, ENSAE ParisTech, December 2006. URL https: /ttp://paatet...ee...eeee hal sci science/ te1-00119593.
[2] Pierre Alquier. User-friendly introduction to PAC-Bayes bounds. Foundations and Trends@ in Machine Learning, 17(2), 2024.
[3] Imad Aouali, Amine Benhalloum, Martin Bompaire, Achraf Ait Sidi Hammou, Sergey Ivanov, Benjamin Heymann, David Rohde, Otmane Sakhi, Flavian Vasile, and Maxime Vono. Reward Optimizing Recommendation using Deep Learning and Fast Maximum Inner Product Search. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, page 4772-4773, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 150393553 doi: 10.1 02.114/333467883544260 3542622.
URL http:: /doi org/10...0. 1145/
[4] Imad Aouali, Achraf Ait Sidi Hammou, Sergey Ivanov, Otmane Sakhi, David Rohde, and Flavian Vasile. Probabilistic Rank and Reward: A Scalable Model for Slate Recommendation, 2022.
[5] Imad Aouali, Eemannel Brunel, David Rohde, and Anna Korba. Exponential Smoothing for Off-Policy Learning. In Proceedings of the 40th International Conference Machine Learning, pages 984-1017, PMLR, 2023.
[6] Imad Aouali, Victor-Emmanuel Brunel, David Rohde, and Anna Korba. Bayesian off-policy evaluation and learning for large action spaces. arXiv preprint arXiv:2402. 14664, 2024.
[7] Imad Aouali, Victor-Emmanuel Brunel, David Rohde, and Anna Korba. Unified PAC-Bayesian Study of Pessimism for Offline Policy Learning with Regularized Importance Sampling. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024. URL htte/forumm2dddd//HHHHTTT
[8] A. Asuncion and D. J. Newman, UCI machine learning repository, 2007. URL http://www ics uci. edu/ sissmmleearn/ haamamnleeaan//MMMeeaepsse tory. html.
[9] Heejung Bang and James M Robins. Doubly robust estimation in missing data and causal inference models. Biometrics, 61(4):962-973, 2005.
[10] Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela. Denis Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 2013.
[11] Olivier Catoni. PAC-Bayesian supervised classification: The thermodynamics of statistical learning, IMS Lecture Notes Monograph Series, page 1-163, 2007. ISSN 0749-2170. doi: 10. 22140079911777000000331 URL. http::tt//// /xxx fx.xdd. doi. org/ 1141111111//777270000000000
[12] Minmin Chen, Alex Beutel, Paul Covington. Sagar Jain, Francois Belletti, and Ed H. Chi. Top-K Off-Policy Correction for a REINFORCE Recommender System. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM '19, page 456 464, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 97814503594455. doi: 3290999.
10.1145/3289600.299999 URL ntttps://dol org/ /0.
[13] Victor Chernozhukov, Mert Demirer, Greg Lewis, and Vasilis Syrgkanis. Semi perimperaettric efficient policy learning with continuous actions. Advances in Neural Information Processing Systems, 32, 2019.
[14] Matej Cief, Jacek Golebiowski, Philipp Schmidt, Ziawasch Abedjan, and Artur Bekasov. Learning action embeddings for off-policy evaluation. European Conference on Information Retrieval, pages 108-122 Springer, 2024.

---

[15] Bo Dai, Ofrr Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvari, and Dale Schu- urmans. Coindice: Off-policy confidence interval estimation. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural In- formation Processing Systems, volume 33, pages 9398-9411. Curran Associates, Inc., 2020. URL. https: pttppe///proceeddngs ingurr neurips.ccmmmmm
[16] Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML'1I, 11, page 1097-1104, 2011.
[17] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li. Sample-efficient nonstationary policy evaluation for contextual bandits. In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, 121' page 247-254, Arlington, Virginia, USA, 2012.
AUAI Press.
[18] Miroslav Dudik, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485-511 2014.
[19] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference on Machine Learning, pages 1447-1456.
PMLR, 2018.
[20] Hamish Flynn, David Reeb, Melih Kandemir, and Jan Peters. PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison. JEEE Transactions on Pattern Analysis and Machine Intelligence, 15302)):5308-13222 2023. doi: 10.1109//PAMI.2223333055
[21] Germano Gabbianelli, Gergely Neu, and Matteo Papini. Importance-weighted offline learning done right. In Proceedings of The 35th International Conference on Algorithmic Learning Theory, volume 237 of Proceedings of Machine Learning Research, pages 614-634. PMLR, 25 Feb 2024. URL https:: h/tp:ss://pccceiiggss. .mlr............mm.............. press/ press/v237/ v237/ http///33///b///// aatT//aabaaeel1222... html.
[22] Alexandre Gilotte, Clément Calauzènes, Thomas Nedelec, Alexandre Abraham, and Simon Dollé. Offline A/B testing for recommender systems. In Proceedings of the Eleventh ACM International Conference Web Search and Data Mining, pages 198-206, 2018.
[23] Torben Hagerup and Christine Rüb. A Guided Tour of Cherooff Bounds. Inf. Process. Lett., 33 (6):305-308, 1990. URL http://dblp mnitriier.. .aleerdde/ie de/db/ purnals/ipl/ippe html# HagerupR90.
[24] Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47(260);663-655, 1952.
[25] Edward L Ionides. Truncated importance sampling. Journal of Computational and Graphical Statistics, 17(2):295-311 2008.
[26] Olivier Jeunen and Bart Goethals. Pessimistic reward models for off-policy learning in recom- mendation. In Fifieenth ACM Conference on Recommender Systems, pages 63-74, 2021.
[27] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
[28] Ying Jin, Zhimei Ren. Zhuoran Yang, and Zhaoran Wang. Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's 's inequality, 2023.
[29] Nathan Kallus and Angela Zhou. Policy evaluation and optimization with continuous treatments. In International conference on artificial intelligence and statistics, pages 1243-1251. PMLR, 2018.
[30] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[31] Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, and Chicheng Zhang. Contextual bandits with continuous actions: Smoothing, zooming, and adapting. Journal of Machine Learning Research, 21(137):1-45, 2020.
12

---

[32] Iija Kuzborskij, Claire Vernade, Andras Gyorgy, and Csaba Szepesvári. Confident off-policy evaluation and selection through self-normalized importance weighting. In International Conference Artificial Intelligence and Statistics, pages 640-648. PMLR, 2021.
[33] Tor Lattimore and Csaba Szepesvari. Bandit Algorithms. Cambridge University Press, 2019.
[34]
Lihong Li, Remi Munos, and Csaba Szepesvari. Toward Minimax Off-policy Value Estimation. In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Fighteenth International Conference on Artificial Intelligence and Statisties, volume 38 of Proceedings of Machine Learning Research, pages 608-616, San Diego, California, USA, 09-12 May 2015. PMLR. URL https: http://:///cccennggee// mlr. ppwss/v38/11151 html.
[35] Ben London and Ted Sandler. Bayesian counterfactual risk minimization. In International Conference on Machine Learning, pages 1125-4133 PMLR, 2019.
[36] Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.37440, 2009.
[37] David A. McAllester. Some PAC-Bayesing theorems. In Proceedings of the Eleventh Anmual Conference on Computational Learning Theory. COLT 98, page 230-234, New York, NY, USA. 1998. Association for Computing Machinery. ISBN 1581 130570. doi: 10. 10.1145/279943.279990 URL. https:: org/10 10. 1145/279943... 279989.
[38] Alberto Maria Metelli, Alessio Russo, and Marcello Restelli. Subgaussian and differentiable importance sampling for off-policy evaluation and learning. Advances in Neural Information Processing Systems, 34:81 19-8132, 2021.
[39] Art B. Owen. Monte Carlo theory, methods and examples. https://artowen su. domains/ nc/,2013
[40] Emilio Farrado-Heráánte Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun. PAC- Bayes Bounds with Data Dependent Priors. Journal of Machine Learning Research, 13(112): 3507-3531, 2012. URL http:// //jp:///mmmrr///// wwtpmiorr...a....e........ haapprs/v11/pparraaaaaaa
html.
[41] Jie Peng, Hao Zou, Jiashuo Liu, Shaoming Li, Yibao Jiang, Jian Pei, and Peng Cui. Offline policy evaluation in large action spaces via outcome-oriented action grouping. In Proceedings of the ACM Web Conference 2023, pages 1220- 1230, 2023.
[42] James M Robins and Andrea Rotnitzky. Semiparametric efficiency in multivariate regression models with missing data. Journal of the American Statistical Association, 90(429): 1995.
[43] Noveen Sachdeva, Yi Su, and Thorsten Joachims. Off-policy bandits with deficient support. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 965-975, 2020.
[44] Noveen Sachdeva, Lequn Wang. Dawen Liang. Nathan Kallus, and Julian McAuley. Off- policy evaluation for large action spaces via policy convolution. In Proceedings of the ACM Web Conference 2024, WWW '24, page 3576-3585, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400701719. http:::/doo...g//// http////..////../... /111/1159944..5551111
doi: 10. 10.1145/5893334364555 URL
[45] Yuta Saito and Thorsten Joachims. Off-policy evaluation for large action spaces via embeddings. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 11089-191122. PMLR, 17-23 Jul 2022. URL https://proceeding: mlr pross/v162/saiiei
html.
[46] Yuta Saito, Qingyang Ren, and Thorsten Joachims. Off-policy evaluation for large action spaces via conjunct effect modeling. In international conference Machine learning, pages 29734-29759, PMLR, 2023.
[47] Otmane Sakhi, Stephen Bonner, David Rohde, and Flavian Vasile. BLOB: Probabilistic model for recommendation that combines organic and bandit signals. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 783-793, 2020.
13

---

[48] Otmane Sakhi, Louis Faury, and Flavian Vasile. Improving Offline Contextual Bandits with Distributional Robustness, 2020.
[49] Otmane Sakhi, Pierre Alquier, and Nicolas Chopin. PAC-Bayesian Offline Contextual Bandits with Guarantees. In International Conference on Machine Learning, pages 29777-29799. PMLR, 2023.
[50] Otmane Sakhi, David Rohde, and Nicolas Chopin. Fast Slate Policy Optimization: Going Beyond Plackett-Luce. Transactions Machine Learning Research, 2023. ISSN 2835-8856. URL http:::/ http///ppeeeeeieeee/eeeeeeeeeeee
[51] Otmane Sakhi, David Rohde, and Alexandre Gilotte. Fast Offline Policy Optimization for Large Scale Recommendation. Proceedings of the AAAI Conference on Artificial Intelligence, 37 (8):9686-966)) Jun. 2023. doi: 10. 10.1/09aaaii.o.. wwt.aaaaa.vv...... 13778.221158 index.phpl http:/AAT//aaa Awt.///tatteeeeeeae////aaaaaaa//
URL https://ojs. aaai org/
[52] Yevgeny Seldin, Nicolò Gesa-Bianchi, Peter Auer, François Laviolette, and John Shawe-Taylor PAC-Bayes-Bernster Inequality for Martingales and its Application to Multiarmed Bandits. In Dorota Glowacka, Louis Dorard, and John Shawe-Taylor, editors, Proceedings of the Workshop on On-line Truding of Exploration and Exploitation 2, volume 26 of Proceedings of Machine Learning Research, pages 1111 Bellevue, Washington, USA, 02 Jul 2012. PMLR. URL mlr prwss/v2//sssseeeeeepeeee http://////seeeeeeeeeeee html.
[53] Anshumali Shrivastava and Ping Li. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, Curran Associates, Inc., 2014. URL
neurips. pppappr_fllespppaeeeeeeee 201/:f/iie..o0octc005446666ee600 Paper.pdf.
[54] Yi Su, Maria Dinakopoulou, Akshay Krishnamurthy, and Miroslav Dudík. Doubly robust off off-policy evaluation with shrinkage. In International Conference on Machine Learning, pages 9167-9176. PMLR, 2020.
[55] Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16(1); 1731-1755, 2015.
[56] Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. advances in neural information processing systems, 28, 2015.
[57] Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miro Dudik, John Langford, Damien Jose, and Imed Zitouni. Off- Off-policy evaluation for slate recommendation. Advances in Neural Information Processing Systems, 30, 2017.
[58] Muhammad Faaiz Taufiq, Arnaud Doucet, Rob Cornish, and Jean-Francois Ton. Marginal density ratio for off-policy evaluation in contextual bandits. Advances in Neural Information Processing Systems, 36, 2024.
[59] Lequn Wang, Akshay Krishnamurthy, and Aleksandrs Slivkins. Oracle-efficient pessimism: Offline policy optimization in contextual bandits. arXiv preprint arXiv:2306.0792. 2023.
[60] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudık. Optimal and adaptive off-policy evalua- tion in contextual bandits. In International Conference on Machine Learning, pages 3589-3597, PMLR, 2017.
[61] Ding-Xuns Xuan Zhou. The covering number in learning theory. J. Complex. 18(3):739-766 sep 2002. ISSN 0885-064X. doi: 10.1006/jcom 2..0000/jcom.20020663.... 2002.0635. URL htttps://do org 1006/ jcom.2002.00 2002. 0635.
14

---

Table of Contents for Supplementary Material
A Limitations
16
Broader impact
16
C Extended related work
16
Useful lemmas
18
Additional results and discussions
19
E.1 Plots of the empirical moments bounds (Proposition 1)
19
E.2
The study Logarithmic Smoothing estimator and proofs
19
E.3 OPS: Formal comparison with IX suboptimality
23
E,4
OPL: Formal comparison of PAC-Bayesian bounds
24
E.5
OPL: Formal comparison with IX PAC-Bayesian learning suboptimality
27
Proofs OPE
29
F.1
Proof of high order empirical moments bound (Proposition 1).
29
F2 Proof of the impact of L the bound's tightness (Proposition 2)
31
F3
Comparisons of the bounds U. (Proposition 3)
31
F.4
Proof of the optimality of global clipping for Corollary 4
32
F55
Comparison with empirical Bernstein
................................
34
F6
Proof of the L + oc bound (Corollary 5)
................................
35
F.7
Proof of the optimality of IPS for Corollary 5
36
F8
Comparison with the IX bound (Proposition
36
Proofs OPS and OPI.
37
G.1 OPS: Proof of suboptimality bound (Proposition 9)
37
G.2 OPL: Proof of PAC-Bayesian LS-LIN bound (Proposition .0..............................
38
G.3 OPL: Proof of -ay-Baye suboptimality bound (Proposition .
39
Experimental design and detailed experiments
40
H.1 Off-policy evaluation and selection
40
H.1.1
Datasets
40
H.1.2 (OPE) Tightness of the bounds
40
H.1.3
(OPS) Find the best, avoid the worst policy
41
H.2
Off-policy learning
42
H.2.1
Datasets
42
H.2.2
Policy class
42
H.2.3
Detailed hyperparameters
42
H.2.4
Detailed results
43
15

---

A Limitations
This work develops theoretically grounded and practical pessimistic approaches for the offline contextual bandit setting. Even if the proposed algorithms are general, and provably better than competitors, they still suffer from the intrinsic limitations of importance weighting estimators. Specifically, our method, as presented, will perform poorly in extremely large action spaces. However, these limitations can be mitigated by incorporating additional structure as Saito and Joachims [45], Saito et al. [46]. Another limitation arises from the offline contextual bandit setting itself, which assumes i.i.d. observations. While this assumption valid simple scenarios, it becomes unsuitable once we want to capture the long term effect of interventions. Extending our results to the more general, reinforcement learning setting would be an interesting research direction as it comes with a challenging estimation task and will require developing new concentration bounds.
B Broader impact
Our work contributes to the development of theoretically grounded and practical pessimistic ap- proaches for the offline contextual bandit setting. The derived algorithms can improve the robustness of decision- processes by prioritizing safety and minimizing uncertainty associated risks. By leveraging pessimistic strategies, we ensure that decisions are made with conservative bias, thereby potentially improving outcomes in high-stakes environments where the cost of errors is substantial. Although our framework and algorithms have broad, potentially good applications, their specific social impacts will solely depend on the chosen application domain.
C Extended related work
Offline contextual bandits. Contextual bandit is widely adopted framework for online learning in uncertain environments [33]. However, some real-world applications present challenges for existing online algorithms, and thus offiin methods that leverage historical data optimize decision- making have gained traction [10]. Fortunately, large datasets summarizing past interactions are often available, allowing agents to improve their policies offline [55]. Our work explores this offline approach, known as offline (or off-policy) contextual bandits [16]. In this setting, off off-policy evaluation (OPE) estimates policy performance using historical data, mimicking real-time evaluations. Depending on the application, the goal might be to find the best policy within predefined finite set (off- (off-policy selection (OPS)) or the optimal policy overall (off-policy learning (OPL)).
Off-policy evaluation. In recent years, OPE has experienced noticeable surge of interest, with numerous significant contributions [16-18, 60, 19, 54, 38, 32, 45, 47, 26). The literature OPE can be broadly classified into three primary approaches. The first, referred to as the direct method (DM) [26, 6]. involves the development of model designed approximate expected costs for any context-action pair. This model is subsequently employed to estimate the performance of the policies. This approach often designed for specific applications such as large-scale recommender systems [47, 26, 4J. The second approach, known as inverse propensity scoring (IPS) [24, 17], aims to estimate the costs associated with the evaluated policies by correcting for the inherent preference bias of the behavior policy within the dataset. While IPS maintains its unbiased nature when operating under the assumption that the evaluation policy absolutely continuous with respect to the behavior policy, it can be susceptible to high variance and substantial bias when this assumption is violated [43]. In response to the variance issue, various techniques have been introduced, including clipping [25, 10], shrinkage [54], power-mean correction [38], implicit exploration [21], self-normalization [56], among others [22]. The third approach, known as doubly robust (DR) [42, 9, 16, 18, 19], combines elements from both the direct method (DM) and inverse propensity scoring (IPS). This work focuses on regularized IPS.
Off-policy selection and learning. as in OPE, three key approaches dominate: DM, IPS and DR in OPS and OPL. In OPS, all these methods share the same core objective: identifying the policy with the highest estimated reward from a finite set of candidates. However, they differ in their reward estimation techniques, as discussed in the OPE section above. contrast, in OPL, DM either deterministically selects the action with the highest estimated reward or constructs distribution based on these estimates. IPS and DR, on the other hand, employ gradient descent for policy learning [55], updating parameterized policy denoted by T as o++1 t- 0g VoR(TT) for each iteration t.
16

---

Since the true risk R is unknown, VoR(TT) is unknown and needs to be estimated using techniques like IPS or DR.
Pessimism in offline contextual bandits. Most OPE studies directly use their point estimators of the risk in OPE, OPS and OPI.. However, point estimators can deviate from the true value of the risk, rendering them unreliable for pecision-making Therefore, and to increase safety, alternative approaches focus on constructing bounds on the risk. These bounds, either asymptotic [10, 48, 15] or finite sample [32, 21I, aim to evaluate a policy's 's worst-case performance, adhering to the principle of pessimism in face of uncertainty [27]. The principle of pessimism transcends OPE, influencing both OPS and OPL. In these domains, strategies are predominantly inspired by, or directly derived from, upper bounds on the true risk [55, 35, 32, 49. 5. 59]. Consider OPS: [32] leveraged an Efron- IPS estimator, while [21] anchored their analysis on bound
Stein bound for the self- constructed with the Implicit Exploration estimator. Shifting focus to OPI., [55] combined the empirical Bernstein bound [36] with the clipping estimator, motivating sample variance penalization for policy learning. Recent advancements include modifications to the penalization term [59] to be scalable and efficient.
PAC-Bayes extension. The PAC-Bayesian paradigm [37, 11] (see Alquier [2] for a recent intro- duction) provides a rich set of tools to prove generalization bounds for different statistical learning problems. The classical (online) contextual bandit problem received a lot of attention from the PAC- PAC-Bayesian community with the seminal work of Seldin et al. [52]. It is just recently that these tools were adapted to the offline contextual bandit setting, with [35] that introduced a clean and scalable PAC-Bayesian perspective to OPI. This perspective was further explored by [20, 49, 5, 21], leading to the development of tight, tractable PAC-Bayesian bounds suitable for direct optimization.
Large action space extension. While regularization techniques can improve IPS properties, they often fall short when dealing with extremely large action spaces. Additional assumptions regarding the structure of the contextual bandit problem become necessary. For example, Saito and Joachims [45] introduced the Marginalized IPS (MIPS) framework and estimator. MIPS leverages auxiliary information about the actions in the form of action embeddings. Roughly speaking, MIPS assumes access to embeddings e, within logged data and defines the risk estimator as
π (e:
x.) (e: 23)
AMIPS (T)
Σ w (Iz, ex) C+.
To
1=1
where the logged data D, (z as e22 (3) r=) now includes action embeddings for each data point. The marginal importance weight
M(e (x)
Eaple ar, a,)))(aa
w(x e) To x)) Elele x, a))o(aa x)
a key component of this approach. Compared to IPS and DR, MIPS achieves significantly lower variance in large action spaces [45] while maintaining unbiasedness if the action embeddings directly influence costs c. This necessitates informative embeddings that capture the causal effects of actions on costs. However, high-dimensional embeddings can still lead to high variance for MIPS, similar to IPS. Additionally, high bias can arise if the direct effect assumption is violated and embeddings fail to capture these causal effects. This bias is particularly present when performing action feature selection for dimensionality reduction. Recent work proposes learning such embeddings directly from logged data [41, 44, 14], or loosen this assumption [58, 46). Our proposed importance weight regularization can be potentially combined with these estimators under their respective assumptions on the underlying structure of the contextual bandit problem, extending our approach to large action spaces, and we posit that this will be beneficial when, for example, the action embedding dimension is high. Another line of research in large action spaces is more interested with the learning problem, precisely solving the optimization issues arising from policies defined on large action spaces. Indeed, naive optimization tends to be slow and scales linearly with the number of actions K [12]. Recent work [51, 50] solve this by leveraging fast maximum inner product search [53, 3] in the training loop, reducing the optimization complexity to logarithmic in the action space size. These methods however require a linear objective on the target policy. Luckily, our PAC-Bayesian learning objective is linear in the policy and its optimization is amenable to such acceleration.
Continuous action space extension. While research has predominantly focused on discrete action spaces, a limited number of studies have tackled the continuous case [29, 13, 59]. For example, [29]
17

---

explored non parametric evaluation and learning of continuous action policies using kernel smoothing, while [13] investigated the paramettrii setting. Recently, [59] leveraged the smoothing approach from [31] to extend their discrete OPI. method to continuous actions. Our work can either use the densities directly, be similarly extended to continuous actions through well-defined discretization of the space. Imagine a scenario with infinitely many actions, where policies are defined by density functions. For any context x, π x) represents the density function that maps actions to probabil- ities. The discretization process transforms the original contextual bandit problem characterized by the density-based policy class into an OPL problem defined by a discrete, mass-based policy class I (for finite number of actions K). Each policy within IIx approximates policy in II through smoothing process.
D Useful lemmas
In the following, and for any quantity Z, all expectations are computed w.r.t to the distribution of the data when playing actions under the behaviour policy To, as in:
E 2 Em- (t).)op((laaa [Z].
lot of the results derived in the paper are based on the use of the well known Chernoff Inequality, that we state below for sum of i.i.d. random variables:
Lemma 12 (Chernoff Inequality for sum of i.i.d. random variables.). Let E R. E N and {X,, & [n]] a collection of n i.d.d random variables. The following concentration bounds on the right tail of Eie(x) X hold for any X 2 0:
P
Σ RE
x;
S EE exp (AX,)))) exp(-Aa)
This result is classical in the literature [23] and omit its proof. We will also need the following lemma, that states the monotonous nature of a key function in our analysis, and that we take the time to prove.
Lemma 13. Let 2 and ft. be the following function::
f((x) log(1 + x) - E/_ (-1)2-1
(-1)
We have that f is decreasing function in R for all L E N*
Proof. Let and fz be the following function:
log(1 - x) -
(-1)--1
fr(())
Let IR+, we have the following identity holding V and Vn 2
1 + (-1)am++1
(-1)at1p-1
-
Σ 1)
(29)
1+t
T+t
1+1
Recall the integral form of the log function:
log(1 + x:) 1" 1+t dt.
We integrate both sides of the Equality (29) and show that the numerator of fL(x) is equal to:
k
(-1)k-1
= (-1) /-' tk
log(1 + x)-
l dt.
dt.
k
18

---

This result enables us to rewrite the function fL as:
th
f1(x) x++1 Jn
I 1+1 dt.
Using the change of variable 1 = ur, we obtain:
fz(2) /.-
u dt
1 zu
which is clearly decreasing for in RR This ends the proof.
Finally, we also state the important change of measure lemma:
Lemma 14 (Change of measure). Let be a function of the parameter and data for any distribution Q that is P continuous, for any ō (0, 1], we have with probability
V
Ba-qlo(O,P.). KC(Q)) +
(30)
5
with v, = EE,, Ear F (wW)
Lemma 14 is the backbone of a multitude of PAC-Bayesian bounds. It is proven in many references, see for example [2] or Lemma 1.1.3 in [11]. With this result, the recipe of constructing a generalization bound reduces to choosing an adequate function g for which we can control V/ g.
E
Additional results and discussions
E.1 Plots of the empirical moments bounds (Proposition 1)
For any x E II, let (x) be the upper bound of Proposition 1:
In(1/8) 3 (T) cix (T)
2D x-11
Miil(T)
An
l
2=2
One can observe that the bound U depends on three parameters, the regularized IPS function the free parameter \ and the moment order T.. We choose a dataset (balance-scale) with n = 612, and evaluate policy æ with R(x) -0.93 to evaluate our bound for different parameters. We fix X VI/n and plot the value of AA for different values of the moment order L E {1, 2, oc} and for 4 different regularization functions, namely IPS, clipped IPS (M /n), Implicit Exploration (IX) (A VI/n) and Exponential Smoothing (ES) (a = 1 - V1/n). The results are shown in Figure 3. One can observe from the plot that The decreasing nature of U depends on À and the regularization function h. Indeed, Proposition 2 states that À < min, 1/[hg] implies that the bound is decreasing w.r.t L. Which means that once this condition is not verified, do not know the bound will keep decreasing with If the bound seems decreasing for CIPS and IX, One can observe that for both IPS and ES, the bound increased from 4 L 8, but achieved its minimum at L = oo, with IPS being optimal for this value. This highlights the connection between L, the value of À and the regularizer h.
E.2 The study of Logarithmic Smoothing estimator and proofs
Recall the form the Logarithmic Smoothing estimator, defined for any 2 0:
(T)
log (1 - >ww oz)ce)
(31)
Our estimator R2A, (T)), is defined for a non-negative À 2 0. particular, recovers the unbiased
IPS estimator in (2) and À > 0 introduces a bias variance trade-off. This estimator can be interpreted
19

---

R(T) = -0.93, n 612
-0.52
0.56
0.60
-0644
CIPS
-066
IX
ES
0.72
2
6
+00
Values of L
Figure 3: Proposition for different values of and with different regularized IPS h.
as Logarithmic Soft Clipping, and have similar behavior than Clipping of Bottou et al. [10]. Indeed, 1/A plays similar role the clipping parameter M, as for any [n]]. have:
(ni as)c < X
log Xw (2a, az) ax)e)) w. (24, a.)..
Wx (x,, a.jc. M min (w, a.), M) wx (x,, a.)c.
LS can be in Figure 4. One can observe that once À > 0, LS exhibits a bias bias-variance trade-off, with a declining bias with À 0. This is different than Clipping the support wn, this comes however with the price of suffering the full variance of IPS. In the following, study the bias-variance trade-off that emerges with the Logarithmic Smoothing estimator.
smooth, differentiable version of clipping. We plot the graph of the two functions
bias is suffered once M is bigger than
IPS
Clipping, M
LS, 0.1
LS, = 0.05
LS. = 0.01
10
20
30
40
50
Importance Weight W,
Figure 4: Comparison of Logarithmic Smoothing and Clipping.
We begin by defining the bias and variance of (T)::
B (A E [.. R(T),
V (T) = (A)( E [RRmm)
(32)
Moreover, for any O, define the following quantity
W (x, a)22
(x E
(33)
Aw (z.a)c
that will be essential in studying the properties this estimator akin the coverage ratio used for the IX Ix-estimator [21]. J. In the following, we study the properties of our estimator R2) (m)) in (14). We start with bounding its mean squared error (MSE), which involves bounding its bias and variance.
20

---

Proposition (Bras-variance trade-off), Let π E II and X 2 0. Then have that
0 5 S ASx(T), and (² S (x(m)/n. Moreover, it holds that for any À >> 0:
R(T) 1
V^ (T)
nd nd
Proof. Let us start with bounding the bias. We have for any À 2
(T) = E (T) R(x)
1
E
log(1 1 Aw (I, Wn (x
(IPS is unbiased).
Using log(1 + x) I x for any x 2 proves that the bias is positive. For its upper bound, we use the following inequality log(1 + x) holding for x 2 0:
B
E
log(1
Aw, (s, wx (x
Wr(xr, a)c (xx AEE
(w (2, a)c} Xw (x, a)c
S 1 Xw (I, a)c
(T))
Now focusing on the variance, we have:
D^(T)= =E E (RA(TT) -E E [1) (m
1
< nd2
E [log(1 - xw (z. a)c)
We use the following inequality log(1 + x) S //evv + holding for x 2 0 to obtain our result:
1 SA))) (TT - n
Notice that once > 0, we have:
Wx (I, a 22
[[(T)] X
S2 (T) E
< E [w (2,
Aw (z, a)c
resulting in finite variance whenever O:
R(T)) 1 nd
(T)
nn
recovers the IPS estimator in (2), with zero bias and variance bounded by [w² a)c² /n. When À >> 0, a bias-variance trade-off emerges. The bias is always non-negative an estimator that verifies (C1). The bias is capped at (S)) which diminishes to zero when is small and goes to [[(T)] as À increases. Conversely, the variance decreases with a higher X. Notably, > 0 ensures finite variance bounded by 1/An, despite the estimator being unbounded. This is different from previous regularizations that relied bounded functions to ensure finite variance.
still recover
While prior evaluations estimators often relied on bias and variance analysis, Metelli et al. [38] argued for studying the non-asymptotic concentration rate of the estimators, advocating for sub- Gaussianity as a desired property. Even if our estimator is not bounded, we prove in the following that it is sub-Gaussian
21

---

Proposition (Sub- Saab-Gassiannty).. Let E 11, d E (0, 1] and 0. inequalities holds with probability at least 8:
Then the following
1n(2/5) R(T)) - (T) f An
(A) R(T) S (T) 1n(2/0)
and
An
In particular, setting X, /ln(2/))//////// [w (z. a)2c²1 yields that
RR(x) - R (T) S 20 l2(26),
where o² = 2E Ww' (z, a)2
/n.
(34)
Proof. Let π E x >> 0 and 5 > 0. To prove sub-Gaussianity, we need both upper bounds and lower bounds on R(T)) using f2 (T). For the upper bound, can use the bound of Corollary 5, and recall that 1b (x S for all x. We then obtain with a probability 1- d:
In(1/8)
In(1/6)
R(a) S AA (T)
R(m)
R (T) S
An
An
For the lower bound the risk, go back our Chernoff Lemma 12, and use the collection of Li.d. random variable, that for any i E [n]. are defined as:
1
X; log (1 Xw (xi,a;)))))
This gives for E R:
Σ
X1 > a
s (I lexp (AXI)])" exp(-Aa)
iE(m)
Xw Xwa [je 1) exp(->a)
1
P
X; >
E
iE|m)
1)
Solving for
E
-- Xwa (2,a00)
eexp(- Xa), we get:
Aw (I, a)c 1
In(1/6) An
Σ
X
log
E
71
kE[m]
The complementary event holds with at least probability 1- 8:
1
Aw l (z, a)c 1
In(1/0)
log
E
An
which implies using the inequality log(z) (x) I r 1 for all x >0 0:
Xwi (Ir, afc aycl 1) -R((T) + In(1/8)
1
(T)T)) - R(TT) - X
log
1b
An
-1) -R(T) + In(1/5)
< X
IE
(e, a)c
An
W (x, a)e
+ In(1/5)
< E
Wx (I, (z,
Xw (II, alc
An
We (x, 2)262
ln(1/))
(T) + In(1/8)
< XIE
Xu (x", a)e
An
An
which proves the lower bound on the risk. As both results hold with high probability, we use a union argument to have them both holding for probability least 1 8:
(2/6 Xn
R)(T) - R(x) s (TA(T) + In(2/0)
R(T) (T) <
and
An
22

---

which implies that:
[((T) - (T)) 5 ASX(T) + Im(2/6)
Im(2/6)
S All
[w (z, (2,,) c +
An
An
This means that setting À = >= vIn(2/5)/no) //B [w (z. c)2c yields sub- Gaussian concentration:
E W (x, 22 l2(26))
R(T) - R (=) s 22
This ends the proof.
From (34), - (T) is sub-Gaussiae with variance proxy o² = 2E [w(x;, a)²c²] /n, which is lower that the variance proxy of the Harmonic estimator of Metelli et al. [38]. Indeed, the Harmonic estimator has a slightly worse variance proxy of o (2+v3) [w( a)?c²] /n. giving o² o
E.3
OPS: Formal comparison with IX suboptimality
Let us begin by stating results from the IX work [21]. Recall that the IX estimator is defined for any 0, by:
((g To(a,(1;) + A/2 Cs.
RA-
(T)
Let 11, {TI,..., Jmh be finite set of predefined policies. In OPS. the goal is to find n e IIs that satisfics
argmin,eet. R(x) argmin R(Tx).
for X > the selection strategy suggested in Gabbianelli et [21] was to search for:
A... argmin R
RA-IX (x)) = arrgmn R (x))
(35)
TEIT,
kE[m]
Proposition 15 (Suboptimality of the IX selection strategy). Ler X > and 8 E (0, 1). Then, holds with probability least that
21
R( R(x
AC)/2(==))
(36)
where
π (aax>) <p(aa Amo
Cx(x) E
|c
Both suboptimalities (LS and IX) have the same form, they only depend on two different quantities (S) and C2 respectively). For π e II and X > 0, If we can identify when (x(7) (T)) then we can prove that the sub-optimality of LS selection strategy is better than the one of IX. Luckily, this always the case, and is stated formally below.
Proposition 16. Let II and > 0. We have:
(T( < Cx)2(T).
(37)
23

---

Proof. Let π E II and X > O, we have:
π (a)x)
[c| Wx (2( a)
-SxTT) =E
<0(a|x) (T(2))
Xw (2, a)c
[c] no(a|z) x(alx)
E
<o(o|x) {
\To(alZ)T((())))
E
<)(aax) To(a()
< Amo(a)))((a))))
= E
(mp(a|x) + 3 ( + (=((())))(al))(())
2
This means that the suboptimalitty of LS selection strategy better bounded than the one of IX. Our experiments confirm that the LS selection strategy is better than IX in practical scenarios.
Minimax optimality of our selection strategy. As discussed in Gabbianelli et al. [21], pessimistic algorithms tend have the property that their regret scales with the minimax sample complexity of estimating the value of the optimal policy [27]. For the case of multi-armed bandit (one con- text x), this estimation minimax sample complexity proved by Li et al. [34] and of rate OEEw, (z, c)), with x being the optimal policy, Our bound matches the lower bound proved by Li et al. [34], as:
Wx- (z, a)² Aw (I, a)c
SX(T)) =
S E (I,
which is not the case for the suboptimality of IX, that only matches it the deterministic setting with binary costs,
x (a(x) To (a(x) + Auo (a
n (a|x) T (alar)
(x) To (a
Cx(=T) =E
< E
|c|
-E
2
with the last inequality only holding when n² is deterministic and the costs binary. For deter- ministic policies and the general contextual bandit, we invite the reader to see a formal proof of the minimax lower bound of pessimism in Jin al. [28, Theorem 4.4), matched for both IX and LS.
E,4 OPL: Formal comparison of PAC-Bayesian bounds
As it is easier to work with linear estimators within the PAC-Bayesian framework, we define the following estimator of the risk Rgg. - (T), with the help function p IR -
1 Σ
<(ap<z;)
Rep LIN (T)
p(Too ((Tro(a (((l):))
with the only condition p to be [CLIN p(x) 2 2). This condition helps control the impact actions with low probabilities under To. This risk estimator encompasses well known risk estimators depending the choice of p.
Now that we defined the family of estimators covered by our analysis, we attack the problem of deriving generalization bounds. We derive empirical high order bound expressed in the following:

---

Proposition 17 (Empirical High Order PAC-Bayes bound). Let L' 1. Given prior P on Fe, ô E (0, 1] and À > O, the following bound holds with probability at least uniformly for all distribution Q over Fe:
(2 + KL(QIIP) + In
2L
X
R(TT)= s vx
Mrh
I.N.
(38)
An
(=2
with:
(gg-LIN.((TQ)
1
To (1:
p( Too as (2:))
n
exp(- -Xxx
S
Proof. Let L 2 1, we have from Lemma 13, and for any positive random variable X 2 0 and À > 0:
-EPLT 22L-1(1 (-1)--1 (AX)
1 2T.
2 f21-1(AX) log(1 + AX)
(2L-1(0)
(1X2L
which is equivalent to:
2L 1 (AX) S +og(1+
21 Σ
(-1)
f. (xx))) SI+AX
= exp
2L
(-1)-11
(xx)e)
E
S +1+E|AX]
A=
(-1) (ax)()
E
exp
exxp (log(1 + E [AX])),
which implies that:
21
(-1)e-1
(xxee)
E
exp
A(X
A log( 1 + E
+ Σ
1
E
t=2
For any X < O, inject-
X > O to obtain:
XX < O,
E
exp x (-1
1 log(1 + E[AX]] x)
- k
2K
(x))+)
1
(39)
Let:
da(a))) 1 [[f((x) a]
it means that:
(a(ar) = Rg- (d)xa) ((,,a) E X x A.
Let O. The adequate function we going to use in combination with Lemma 14 is:
da(a,)z;)
2F.
1
de(a))z))
((0,D,) = Σ - log(1 + ARE (da)) p(mo(as(=)))
Σ
Ci
p(Tr((as(zee)
2=
(4) log(1 + -R
LIN da(as(
24 do(as(ore)
A
A
Ci p(Fo(a:(=:))
22))
1=1
2
25

---

By exploiting the i..d. nature of the data and exchanging the order of expectations (P is independent of D,), we can naturally prove using (39) that:
A (=(2)) log(1 + ARP - xx(0))
Σ (xx, ][ 1
2k
y Ep
II
exp
as we have
do(a; (x:) x((0)
(a (z+)) C: S 0 Vi.
Injecting Vg in Lemma 14, rearranging terms and using that feg. LIN (T) has positive bias concludes the proof.
LIN(TT
Similarly the OPE section, use this general bound obtain PAC- BAC-Bayesian Empirical Second Moment bound and the PAC-Bayesian LS-LIN bound. That we state directly below:
Empirical second moment bound.
With L 1, obtain the following:
Corollary 18 (Second Moment Upper bound). Given a prior P on Fe, E (0, 1] and > The following bound holds with probability least - uniformly for all distribution Q over Fe:
R(TQ)= S sha (REG(T))= KL(QIIP) + In
An MM
A ME
LIN.LIN (
(40)
2
Log Smoothing PAC-Bayesian Bound.
With L + oo, we obtain the following:
Proposition 19 (RN-LIN PAC-Bayes bound). Given a prior P on Fe, E (0, 1] and À > 0, the following bound holds with probability at least 8 uniformly for all distribution Q over Fe:
KCC(QIPP) + In
R(TQ)= S vix (A-LI((TQQ) +
(41)
An
with:
RA-LIN (TT) = (a))) log
Ac;
To (a:aa
Following the same proof schema as of the OPE section, can demonstrate that the Log Smoothing PAC-Bayesian bound dominates the Empirical Second moment PAC-Bayesian bound L = 1. How- ever, we use the bound of L as an intermediary state the dominance of the Log Smoothing PAC-Bayesian bound.
Indeed, easily compare the result obtained with L 1 to previously derived PAC-Bayesian bounds for off-policy learning. We start by writing down the conditional Bersstein bound of Sakhi al. [49] holding for the (linear) cIPS (p max(x, r)) For policy so and À > have:
R(TQ)= S (TQ) + KC(Q][P) + In AVT A
KCCO In (N(T)
+
2n
An
KC(Q]|P)+Hr +
A (TQ))
R(TQ) S (T +
(L == 1)
An
We can observe that the previously derived conditional Bernstein bound has several terms that make less tight:
It has additional, strictly positive square root KL divergence term.
26

---

The multiplicative factor ((/TT) is always bigger than 1/2, and diverges when 7 - 0.
With enough data (n >>>>> 1), we also have:
o (a|z)
( (o T = (%(TT)
(TQ) = EE
max c(a,, x)
x))
S E
These observations confirm that the new bound derived with proposed for cIPS, especially when > 1. As our bound can work for other estimators, also compare it to a recently proposed PAC-Bayes bound in Aouali et al. [5] for the exponentially-smoonl estimator (p + x²)) with [0, 1]:
is tighter than what was previously
KL(QUIP) + A/"
KC(QIIP)
+ In
R(TQ)= & R (TQ) +
+
+
(V)(T)) + 5% (TQ)
2n
An
2
R(TQ)= S (TQ) + KC(QIIP) + + S
(L=1)
An
We can clearly see that the previously proposed bound for the exponentially smoothed estimator has two additional positive quantities that makes it less tight than our bound. addition, computing our bound does not rely on expectations under (contrary to the previous bounds that have V,) which alleviates the need to access the logging policy and reduce the computations.
This demonstrates the superiority of bounds. It means that L - oo is even better. We can also prove that the Log smoothing PAC-Bayesian Bound is better than the one of IX in Gabbianelli et al. [21]. Indeed, using log(1 + x) 2 142/2 for all O, have for any P, Q P(()) and À > 0:
compared to existing variance sensitive PAC- MAC-Bayesian
R. R + KC(QIIP) + In
KC(Q][P)+ I
R.. P (TQ)
An
An
To
Ac;
KC(QQ]))) + In
log
1
+
To(as/2;))
An
To (a: .ra))
KLLIQ P)
+
In
To (0) - Acs/2
An
(Tq)) + KC((]IP) +
(IX-bound)
An
with the last implication leveraging that the cost is always bigger than - 1/ This proves that our bound better than the IX bound. This means that our MAC-Bayesian bound better than all existing PAC-Bayesian off-policy learning bounds.
E.5
OPL: Formal comparison with IX PAC-Bayesian learning suboptimality
Let us begin by stating results from the IX work [21]. Recall that the IX estimator is defined for any 0, by:
T(a,(zs) Co To ..)) + X/2
RIX 2 (T)
and that we used the linearized version of the LS estimator, LS-LIN defined as:
n
T(a:/=:)) log (1
Ac;
RA-IIN ④
mo (a: (xs)
Let θ be parameter space and P()) be the set of all probability distribution on θ. Our goal is to find the best policy in chosen class L(O) P()):
gQ* = argmin R(TQ).
QEC(e)
27

---

For À > 0 and prior P E P()), the PAC-Bayesian learning strategy suggested in Gabbianelli et al. [21] to find in (()) P(O):
KL(QIIP)
argmin
(mQ) +
An
QEC(E)
This learning strategy suffers from suboptimality bounded in the result below:
Proposition 20 (Suboptimality of the PAC-Bayesian learning strategy from [2I].. Let >> 0 and ö E 10. Then, it holds with probability al least å that
2 (XCCQQ')P)) + In(2/6))
0 (( R((Q=)= S XCx/2(F0-)
An
where
π (aax)) m (a(x)) (
(T) E
|c
Similarly for PAC-Bayesian learning, both suboptimalities (LS and IX) have the same form, they only depend on two different quantities (SLIN and Cλ respectively). For a x E and À > 0, If we can identify when S (x) & (T), then we can prove that the sub-optimality of LS PAC-Bayesian learning strategy better than the one of IX in certain cases. Luckily, this always the case, and it is stated formally below.
Proposition 21. Let E II and X > 0. We have:
(T) S Cx/2(TT.
(42)
Proof. Let i E and
0, and recall that:
xaaxx)c²
s (T) = E
n (a(a))) ATo(a|z)
We have:
π (a(x))
C2/2(T) - -x(N((T))
E
|d| (g(a
m (a(z)
+ 2 (u(a))
(To((ax))
lel
E
T [a|a:|/
TH(aax) T <5(a + Amo((ax))
x)(a)z) (c) + (
E
T(a|x)/c
(ng(alx) ( + \mo(a())lc))
1. 0.
Similarly, this means that the suboptimality of LS-LIN PAC- PAC-Bayesian learning strategy is also, better bounded than the one of IX.
Minimax optimality of our learning strategy. From Jin et al. [28, Theorem 4.4] we can state that the minimax suboptimality lower bound, the case deterministic optimal policies is of the rate O(1V/nC' with infaex 70(T (x))x) > C Our bound as well as IX bound match this minimax lower bound, as:
SLIN (x') Eng.
<
na n (x) Ae
C
lc|
1
Cx(x*) = Er..
$
TT( (x=]ax)
C
28

---

One can see that for both, selecting
2(CC(Q))P)) - In(2/6)) C
gets you the desired bound, matching this minimax rate.
Proofs of OPE
F.1 Proof of high order empirical moments bound (Proposition 1)
Proposition (Empirical moments risk bound). Let E IT, I. 2 1, (0, 11, X >> a h satisfying (C1). Then holds with probability at least 5 that
26 X-1 +
In(1/5))
R(x) S 2A
(
Σ e 2=2
(T)++)++++
An
where 1 and M are defined in (5), respectively, and recall that (x( S
Proof. Let E,EN and 2 0 positive random variable. We have 27 1 2 1, and with
the decreasing nature of f(2L-1) (Lemma 13), also have:
1
log(1 1 + AX)
-E (-1)--1
h (AX)*
f(2)-1((0) 2 f2L-1(AX)
2L
(1X)21
2L
(-1)
(AX) log(1 +AX)
k
2h
(-1)
Σ
(xx)() SI+I5
exp
L
1=1
(-1)e-1 (Ax)²)
exp
< <1+AE|X]
2L
1)- (xx)e)
)
IF
exp
S exp Eexp((1p (Glog( + (FF
log (1 AE (X]) + Σ (-1) 8-1
21
(-)aax)))) S
E
A(X
2=2
For any X < O, we can inject
X 2 O to obtain:
A (- log XE x) Σ -
2L
VX < 0,
E
exp
1
(43)
The result in Equation (43) will be combined with Chernoff Inequality (Lemma 12) to finally prove our bound. Let À > O, for our problem, we define the random variable X; to use in the Cheroof Inequality as:
2L
X, T log (1 AE [b]] - h3 -
Σ 7 (Ah.)
2
29

---

For any a E R, this gives us the following:
P
Σ iE/n]
Xi
>
E
exp
(AX1))))
exp(-Aa)
21
P
71
log (1 AE (x])
Σ
h4 +
(Ahi))
>
$ (E [exp (AX)))) exp(-Aa)
A
RE(n)
2=
21
P
71
log (1 AE (h])
Σ
h4
+
> a
$ exp( (-xa)
(Use of Equation (43))
2=2
Solving for exp(->a), we get:
2L
In(1/6)
log (1 - (A)
Σ
hi +
(Ahs))
S
8
X
A
iE[m]
8=2
- Σ
21
X
In(1/8)
log (1 - (E(h)) À
h4
+
11
n2
An
iE/n|
2=2
21
x-11
In(1/5)
X log (1 - (M)) (T)
Σ
M
5
An
1=2
2L
X p-1
In(1/5) An
P
log (1 - [k) > (T)
Mh
S 6.
2=
This means that the following, complementary event will hold with probability at least 1 - 5:
2L x-1
In(1/5) An
log (1 AE (E < (T)
Σ
Mh).((T
d being non-decreasing function, applying it to the two sides of this inequality gives us
2L x-1
In(1/0)
E M < A
(T) +
Σ
Mhe
(T) +
An
2=2
Finally, h satisfies (C1), this means that the bound is also an upper bound on the true risk, giving:
2L.
f-1
In(1/0)
R(T) S // (T) +
Σ
M
(T)
+
An
t=2
which concludes the proof.
30

---

F.2 Proof of the impact of L on the bound's tightness (Proposition 2)
Proposition (Impact of on the bound's tightness). Let q E II, d (0.11 and h satisfying (C1), Let
In(1/8) An
21 f-1
U ( (T)
tb (T) +
( (T)
8=2
be the upper bound in Equation (6). Then,
A min iE(n]
2L + (2L 1) h4g
(T) U
(44)
which implies that:
U.A (T) is decreasing funcetioo w.r.t L.
min M
Proof. We want prove the implication (44) from which the condition on the decreasing nature of our bound will follow. Indeed, Let us suppose that (44) is true, we have:
2L + 2
A S min k
1L
A min EE
hh:
(2I. 1)14,]
7L 1, U U²
(Using (44))
U (I)) is a decreasing function w.r.t L.
Now let us prove the implication in (44). We have for any L 2 1:
2L+2
1-1
U S U.
Σ
M
(T) 50
{=21+1
2
1
Xh;
24+1
n
2L +
2L + 2
As h; S 0, we can ensure this inequality by choosing À that verifies:
2L +2 (2L + 1)|ba]
2L +
Vi [n], A
min iE
(2L + 1)
which concludes the proof.
F.3 Comparisons of the bounds U2 (Proposition 3)
We compare the bounds evaluated in their optimal regularisation function h. We start by stating the proposition and proving it.
Proposition.
Let II, and X > define:
U²((x) = min U (T).
Then, for any X > 0, it holds that for any L > 1:
UZ(T)) < (T)
In particular, AA > 0:
U2 < (T))T).
(45)
31

---

Proof.
Let v E II, À > 0 and
U2(x) min Ur A.h (T).
We can prove (see Appendix F.4) that:
X z 2 (x) In(1/8)
(+(T) - U.A.A. (T) = 1//2 (fe (T)
An
with:
h (p,1(p,,, = minn(c/p//. 1/2),
and that (see Appendix F.7):
In(1/8)
(2) = xbx (T) +
An
From Proposition 2, we have that for any h::
min 1
U (TT) is decreasing function w.r. L.
It appears that the optimal function h,,1 respects this condition, as by definition:
min iE[n] (ha,1) 2 X
meaning that:
U... (T)) decreasing function w.r.t L.
This result suggests that the Empirical Second Moment bound, evaluated in its optimal function h..1 always bigger than bounds with additional moments (evaluated in the same h,,1). This leads us to the result wanted, for any L>> 1:
U2(T) = min U.A 2.h (x) s UAA h. (T) s UUA.A. A.b. (T) = (T).
In partieular, get:
U2 (T) S (T)
which ends the proof.
This means that UA is tighter than U/. and thus can also be tighter than empirical Bernstein.
F4 Proof of the optimality of global clipping for Corollary 4
Proposition (Optimal h for L 1). Let À O. The function h that minimizes the bound for
1, giving the tightest result is:
Vi, h4 = h(m(aa)))))) mo(a) = =- =-min { क (asl1z;)
1 } x
Icals (a (x,)
This means that when the costs are binary, we obtain the classical Clipping estimator of parameter 1/x:
(aas(z))) (a: (rs)' X Ci.
h4 min
Proof. We want to look for the value that minimizes the bound. Formally, by fixing all variables of the bound, this problem reduces
argmin R4 + > MM) argmin Σ EE(CI)
h +
AC(CI)
2
32

---

The objective decomposes across data points, so we can solve it for every h; independently. Let us fix j [n], the following problem:
argmin (T) + (x) argmin AyER
h 2 h2
b En
2
(a, [z)) Co To (ag (z))
subject to
h
is strongly convex in hy. We write the KKT conditions for hy to be optimal; there exists a* that verifies:
1 + Ahy - a =0 0
(46)
a² 2 0
(47)
[(aglar)) [rz)
a²
Cj hi 0 To(a (m)))
(48)
x (aa xz)) Cj
h no a (z))
(49)
We study the two following two cases:
Case 1: hj - - we have a =1 -h Nh 5 = a 0, meaning that:
hy
Case 2: h1 > -
we have a* = + Xh₃ > O, which combined to condition (36) gives:
x(az (z))) h To(a) (x,)) Cj.
The two results combined mean that we always have:
h5 x(a,lx)) (z))
hy 2 X and whenever hy
To ( Cj.
We deduce that hy has the following form:
h = )(](a]/);;) mo( = min x(aglaz))
1cyl, (a
(50)
T (a,) T (x,) |cs1 X
a" = =
(51)
These values verify the KKT conditions. As the problem is strongly convex, h2 has a unique possible value and must be equal to equation (38). The form of hy global clipping that includes the cost in the function as well. In the case where the cost function e is binary:
Vi C E (-1,0).
recover the classical Clipping with parameter 1/> optimal solution for h:
π ( (2y) mu(a; (r.) X
h = min
33

---

E55 Comparison with empirical Bernstein
We begin by comparing the Second Moment Bound with Swaminathan and Joachims [55]'s bound as they both manipulate similar quantities. The bound of [55] uses the Empirical Bernstein bound of [36] applied to the Clipping Estimator. We recall its expression below for parameter M > 0:
x (a, (wx) (a; (x:)
R
(T)
min
M Ct.
We also give below the Empirical Bernstein Bound applied to this estimator:
Proposition (Empirical Bernstein for Clipping of [55]). Let π E II, 8 E (0, and M > Then it holds with probability at least
8 thal
2V M TT (2/0))
7M (2(2/))
R(x) S R (T)
(52)
3(n 1)
with V.M (x) the empirical variance of the clipping estimator.
We are usually interested in the case where π and To are different, leading to substantial importance weights. In this practical scenario, the variance and the second moment of the magnitude of M. Indeed, one can see it from the following equality:
2
M.M
M.M.((T) (T)
[R (T))
O(M)
O(M)
O(02)
M M. (T)
(M =o())
O(M)
This means that in practical scenarios, the empirical variance and the empirical second moment are approximately the same. Recall that the Second Moment Bound works for any regularizer h, As Clipping satisfies (CI), we give the Second Moment Upper of Corollary 4 with Clipping below:
X 2 di (N (T) + 2
In(1/0)) An
A MM.((T) + In(1/8)
< (MT
(TT) +
(1x(2) S xx, Vx)
2
An
In(1/8)
( (it) + (T)
An
Choosing X = v (1 (Tt) gives us an upper bound that is close to:
X M.. +
In(1/0)
2MM M. (T) In (1/8))
R. (T) +
R. (T) +
An
n
2VM (TT) In(1/8)
~ RRM (T)
2VM (T) In(2/5)
7M
$ RM (T)
3(n 1)
This means that in practical scenarios, and with good choice of À ~ 0(1 the Second Moment bound would be better than the Empirical Bernstein bound, and this difference will be even greater when M > 1. This is aligned with our experiments, where we see that the new Second Moment bound is much tighter practice. This also confirms that the Logarithmic smoothing bound even tighter, because it is smaller than the Second Moment bound stated in Proposition 3.
34

---

F.6 Proof of the L - oo bound (Corollary 5)
Proposition (Empirical Logarithmic Smoothing bound with + oo), Let E ó (0.1] and À > O. Then it holds with probability at least 1 5 that
a
log (1 -h1) + In(1/6)
R(TT) A>
An
Taking the limit of L naively recovers this form of the bound, but imposes condition on À for the bound to converge. We instead, take another path of proof that does not impose any condition on A, developed below. The main idea is to take the limit of L to recover the variable to use along Chernoff.
Proof. Recall that for the proof of the Empirical moments bounds, we used the following random variable defined with À > 0:
2L
X, x log (1 AIE [h]) h,
1
Σ (Ah.)*
E=2
combined with Chernoff Inequality (Lemmaa 12) to prove our bound. we take the limit - oo for random variable, we obtain the following random variable:
X; log (1 XIE [b]) X
log (1 (1-AM (1-Ah;)
1 1 Ah4
A log
AE [h]
We use the random variable X, with the Chernoff Inequality. For any a E R, we have:
exp (Ax,)))) exp(->a)
P
X,
>
I E
kE(n)
n log (1
AIE [4]) +
Σ
} 1ox (1 - Miri) >
< E exp (2x:)))* exp((-a)
<e(m)
On the other hand, we have:
F. 1 Aha] AE [h)
E
exp
(xx;))
=1 1.
Using this equality and solving for == cexp(->dut we get:
P
n
log (1 XE + Σ
(1
log (1 -Whh))
In(1/5)
5
sEin]
1 P log (1 - (k) +
Σ
1 log (1 Aha)
In(1/8)
< 8
X
An
kE[n]
This means that the following, complementary event will hold with probability least 8:
In(1/8)
log (1 AE [b)
log Ah.) +
An
di being non-decreasing function, applying it to the two sides of this inequality gives us: E hh Φ (- i=1
In(1/5)
log (1 - -h-)
An
As satisfies (C1), we obtain the required inequality:
In(1/8)
R(T) < أ
log (1 -hhs) + An
and conclude the proof.
35

---

E.7 Proof of the optimality of IPS for Corollary 5
Proposition (Optimal h for - oo). Let À > The function h that minimizes the bound for L + 00, giving the tightest result is:
h4 = (( mo(a;)))) c)) T(a (.)) Vi,
To(as z23) Co
Proof. The proof of this proposition is quite simple. The function:
f(x) log (1 Az)
is increasing. This means that the lowest possible value of h;; ensures the tightest result. As our variables h; verifies (CI), we recover IPS as an optimal choice for this bound.
F8 Comparison with the IX bound (Proposition 8)
We now attack the recently derived IX bound in Gabbianelli et al. [21] and show that our newly proposed bound dominates it in all scenarios.
Proposition (Comparison with IX (2I). Let E II, 5 E|o, 1] and X > 0, the IX bound from [21] states that we have with at least probability 6: In 1/ (x)
R(T)= S R
(53)
An
with:
Ta, xx,)
RA-I TT)
To,a,/=,) + X/2 Cs.
Let (T) be the IX upper bound defined above, have for any X > 0:
U2 (T) s (N)
(54)
Proof. Let v E II, 8 Ee00, 1] and À > 0. Recall that U UZ) = Ui (R)(TT) + 1m(2/0))
We have:
An
1b (T) + In(1/o)) < R (T) + In(1/8)
v2(x)) 5x)
An
An
log (1 (en, + In(1/8)
An
==1
Using the incquality log(1 + x)
for all x 0. get:
It2/2
log (1 Xw (t)e) + In(1/5)
(2)( (TT) <
An
12
Wx (x,, az)
C4 In(1/0)
log(1 + +x) 2 1T+ w//2
Xu (Ti, 03/3
An
T(a (T:)
In(1/8)
To(a; AM (T(aa))));11 C4
n
An
7(a (x:)
In(1/8)
+
(-x(a:)a:)c S and - 0)
To(as(2:) X/2 An In(1/0)
(T)++
(T)
An
which ends the proof.
36

---

The result states the dominance of the LS bound compared to IX. The proof of this result also gives us insight on when the bound will be much tighter than IX. Indeed, to obtain the IX bound, LS bound is loosened through 3 steps:
1. The of 4/x x, Vx.
2. The use of log(1 λz) 2 1+xx/22 Vx 2
3. The use of (a: S 1, [n].
The two first inequalities are loose when 1/vn not small, which means that LS will be much better in problems with few samples. The third inequality is loose when is not peaked policy or the cost is way less than Even LS bound is always smaller than IX, LS will give way better result if the number of samples is small, and/or the policy evaluated is diffused.
G Proofs of OPS and OPL
G.1 OPS: Proof of suboptimality bound (Proposition 9)
Proposition (Suboptimality of our selection strategy in (20)). Let X >> 0 and E (0, 11. Then, holdy with probability least 1 8 that
S R( R(xx) S ASA(T))+ 21n 2ln(2
An
where n and R desined (19) and (20), and
Sx(x) = [[ a)c)² / (1 (1,(
In addition, upper bound is always finite (w, a)c)²
(T) AE
S min [[[(=]], AE [1 (r) [R(T))-
Xw (2, a)e
Proof. To prove this bound on the suboptimality of our selection method, we need both an upper bound and lower bound on the true risk using the LS estimator. Luckily, we already have derived them in ?? For fixed X, taking union of the two bounds over the cardinal of the finite policy class [[L]]. we get the following holding with probability at least 8 for all π E II.:
R(T) - - I1/2)
(.) - R(x) S ASA(T) 11
and
An
An
As # E 1l, and by definition of म. (minimizer of i2); (TT), we have:
( + In(2 < R (++)+ In(2
R(*
An
An
Using the lower bound on the risk of R(AS), we have:
R(#))) R (n (11/0)
2 (2
R( (S)) +
An
which gives us the suboptimality upper bound:
2 2 11 0 < ((( - R(x3) s (T)) +
An
Note that:
(w 2)c)
XS = AE
< min ([RT), AE
[w (z, a)c)
1 Xw (2,, a)c
always ensuring finite bound.
37

---

G.2 OPL: Proof of PAC-Bayesian LS-LIN bound (Proposition 10)
Proposition (PAC-Bayer learning bound for ) Given prior P E P(0). 8 e (0,1] and À > 0, the following holds with probability at least 6:
vQ E P(O), R(FQ)= S 4> (R (mQ)+ + KL(QIII) + In
An
Proof. To prove this proposition, we can either take the path of High Order Empirical moments as for Pessimistic OPE, we can prove it directly. We provide here simple proof of this proposition using ideas from Alquier [1, Corollary 2.5]. Let:
(a(x) 1 - Ex
(55)
it means that:
To (a/z) = @ [de(a]=) (a, xxx.
Recall that prove PAC-Bayesian generalization bound, rely on the Change of measure Lemma (Lemma 14). For any > 0, the adequate function g to consider is:
7
de do(a:) 24)c; No (a: (z1))
((,
Σ
log((1 AR(do)) log
[ X
i=1
n
1
do(a:1z;)es >
Σ
log
Ro(ai (a.))
XR(do)
By exploiting the i..d. nature of the data and exchanging the order of expectations (P is independent of D,),, we can naturally prove that:
x dola, lar,)es mo(ag(z))
V
Ep
E
exp
log
AR(da)
du dalaslar:)c
1
To(a.12.]
Er
IF
AR(do)
XR(do) AR(do)
Ep
=
Injecting Vg in Lemma 14, gives:
1 x do(a: (a(a
]
ICL(QIIP) + +
1E [- log(1 - AR(dd))] <
Ean
log
To To(a: (o;)
Ee-Q
- (ask(o)))) log
( (1-
Gi
)
KC(Q) + In
To TT( (255
1=1
n n
KC[(Q) + Im
<
T (a(ailx;) log 1
Ci
To (a(a;(1;)
n
< LIN (TQ) + KC(Q + In
From the convexity of + log(1 1 x), we have:
À log (1 (R(TQ))
< X Eanq |- log(1 XR(do)] < RA (A-LIN
1
KC(Q)) + In
An Applying the increasing function t of Equation (5) to both sides concludes the proof.
38

---

G.3 OPL: Proof of PAC-Bayesian suboptimality bound (Proposition 11)
Proposition (Suboptimality of the learning strategy in (27)). Ler X > O, L()) and 5 E (0, 1]. Then, it holds with probability at least 1 - 6 that
2 (XLCQQT)) + In(2/6))
0 S R(#q..)) - R((qq) - x (mQ-)
An
where
x(a22)c
SX
T ( (TT(aa
In addition, our upper bound is always finite as:
T(a|x)22 Tz(a|z))
AS & min
[R(T)) AE
[R(x)).
Proof. To prove this bound on the suboptimality of our learning strategy, we need both a PAC- Bayesian upper bound and lower bound the true risk using the LS-LIN estimator. Luckily, already have derived an upper bound in Proposition 10, that we linearize here as thx S x
(T)) KC(QIIP) + In An For the lower bound, we rely a second time on Change of measure Lemma (Lemma 14), For any O, choose the following function g:
AQ P(O), R(TQ)=
1 1 1 dolaslazi)ss) R(ds) (.S (do) To(as(244)
(,) = Σ (-x
log
1=1
By exploiting the i..dd nature of the data and exchanging the order of expectations (P is independent of D,,,, we can prove that:
V = Ep
II
exp (-X(((ds) + (do))) E
(a ma(a(a)
< Ep
exp
-A(R(da) + ASTTH + EE
A da(a)z)
matala)
Xdg(a|x)c
< Ep
exp
-((((d)) + ASKT
mo(alr) - Adg(a|z)e
<a(aar)) - Ac 1))
Ado (alaa)
Ep
exp
-((R(do) + (.ox))
E
(do is binary.)
Ado(a(z)
do(alz)) To(akx)
< Ep
exp
-X3SSTIX( (do) (a(a)))) - dc
n
(exp (-X2 SLIN (do) + 22 (da))) < 1,
< Ep
giving by rearranging terms, the following PAC-Bayesian bound:
AQ E P(O), (T S R(TQ) + (TO) KC(Q)
+ In(2/5)
An
Now we take union of the the two bounds, for them to hold with probability at least 1 5 for all Q. By definition मं.. (minimizer the upper bound), we have:
KC(Q2. P)) + ln(2/6) < AA, (II
KC(Q") + ln(2/8)
R( ((QQ.)) S A 22-L1n (fQ.))
An
An
39

---

Using the lower bound on the risk of R(TQQ-) we have:
R(f1Q.) S R2 LIN (TQ.)) KC(Q"1IP) +
1n((2))))+n((20) In(2/6)
An
S <((QQ)) (TTO)) (TQ.)) KL(QT)))) + ln(2/)
An
which gives us the PAC-Bayesian suboptimality upper bound:
2 ((CC(Q))))) + ln(2/)))
0 s R(fq.)) R(TQ-) S A (mQ-) +
An
Concluding the proof.
H
Experimental design and detailed experiments
All our experiments were conducted on machine with 16 CPUs. The PAC-Bayesian learning experiments require a moderate amount computation due the handling of medium-sized datasets. However, our experiments remain reproducible with minimal computational resources.
H.1 Off-policy evaluation and selection
H.1.1
Datasets
For both our OPE and OPS experiments, we use 11 UCI datasets with different sizes, action spaces and number of features. The statistics of all these datasets are described in Table 3.
Table 3: OPE and OPS: 11 Datasets used from OpenML [8].
Datasets
N
ecoli arrhythmia
336
8
452
13
279
micro-mass
571
20
1300
balance-scale
625
3
cating
945
6373
vehicle
846
4
18
yeast
1484
10
page-blocks
5473
5
10
optdigits
5620
10
64
satimage
6430
6
36
kropt
28 056
18
H.1.2 (OPE) Tightness of the bounds
only oracle policies (faulty policies log data and we evaluate ideal policies), we use the full 11 datasets without splitting them. The faulty policies defined exactly described in the experiments of Kuzborskij et al. [32]. For each datapoint, the behavior (faulty) policy plays an action and we record cost. The triplets datapoint, action and cost constitute our logged bandit dataset, with which can compute our estimates and bounds. As have access to the true label, the original dataset can be used to compute the true risk of any policy.
Additional details. For these experiments,
Detailed results. Evaluating the worst case performance policy done through evaluating risk upper bounds [10, 32]. This means that a better evaluation will solely depend on the tightness of the bounds used. To this end, given a policy æ,, we are interested in bounds with small relative radius (U(T)) RT)) 1/. We compare our newly derived bounds (cIPS-L=1 for U and LS for U both with 1= SNIPS-ES: the Efron Stein bound for Self Normalized IPS [32], cIPS-EB: Empirical Bernstein for Clipping [55] and the recent IX: Implicit Exploration bound [21]. We use all 11 datasets, with different behavior policies (To (0.2, 0.25, 0.33) and different noise levels E (0., 0.2)) to evaluate ideal policies with different temperatures (r 10. 0.2, 0.3, 0.4, 0.5)). defining 500 different scenarios validate our findings. In addition to the cumulative distribution of the relative radius of the considered bounds of Figure 2. We give two tables in the following: the average relative
40

---

Table 4: OPE: Average relative radius for each datasets
Datasets
SN-ES
cIPS-EB
IX
CIPS-L=1
LS
ecoli
1.00
1.00
0.676
0.752
0.573
arrhythmia
1.00
1.00
0.677
0.707
0.548
micro-mass
0,962
0.840
0.394
0.346
0.311
balance-scale
1.00
0.950
0.469
0.550
0.422
eating
0.930
0.734
0.318
0.337
0.265
vehicle
0.981
0.867
0.409
0.482
0.358
yeast
0,861
0,660
0.307
0,311
0.254
page-blocks
0.760
0,547
0.371
0,447
0.312
optdigits
0.468
0,323
0.148
0.139
0.113
satimage
0.506
0.336
0.171
0.184
0.140
kropt
0.224
0.161
0.087
0.066
0.060
radius of our bounds for each dataset, compiled in Table 4, and the average relative radius of our bounds for each policy evaluated, compiled in Table 5. One can observe that LS always gives the best results no matter the projection. However, the cIPS-L=1 bound is sometimes better than IX, especially when it comes to evaluating diffused policies, see Table 5.
Table 5: OPE: Average relative radiuses for each target policies (ideal policies with different T)
SN-ES
cIPS-EB
IX
cIPS-I=1
LS
T 0.1
0.783
0.630
0.332
0.400
0.308
T 0.2
0.781
0.630
0.326
0.390
0.295
0.3
0.782
0.668
0.353
0.389
0.297
r 0.793
0.706
0.385
0.385
0.301
0.5
0.810
0.735
0,432
0.397
0.323
H.1.3 (OPS) Find the best, avoid the worst policy
Policy selection aims at identifying the best policy among set of finite candidates. In practice, we are interested in finding policies that improve on To and avoid policies that perform worse than To. To replicate real world scenarios, we design experiment where To is a faulty policy (r = 0.2), that collects noisy (c = 0.2) interaction data, some which is used to learn Taps, Tgas, and that add to discrete set of policies IT;=4 {Tu, π ideal Tarss, Tgee). The splits for these experiments are the following: 70% of the data used to create bandit feedback (20% is used to train Tooe,, TTges and 50% is used evaluate policies based on estimators/upper bounds.) the rest used to evaluate the true value of the policies. The goal is to measure the ability of our selection strategies choose from IT;,4, better performing policies than mo- We thus define three possible outcomes: a strategy can select worse performing policies, better performing or the best policy. We compare selection strategies based on upper bounds the commonly used estimators IPS and SNIPS. The hyperparameters of all bounds (the clipping parameter M and A) are set to 1/ The comparison is conducted on the datasets with 10 different seeds resulting plot in Figure 2, we collect the number of times each method selected the best policy (T²), better (B) or worse (W) policy than Tu for all datasets in Table 6. We can see that risk estimators can be unreliable, especially in small sample datasets, as they can choose worse performing policies than To- a catastrophic outcome in highly sensitive applications. Selecting policies based on upper bounds is more conservative, as it avoids completely poor performing policies. In addition, the tighter the bound, the better its percentage time it selects the best policy: LS upper bound is less conservative and can find best policies more than any other bound, while never selecting poor performing policies.
110 scenarios. In addition the
41

---

Table 6: OPS: Number of times the worst, better or best policy was selected for each dataset.
Dataset
IPS
SEIPS
SU-ES
CIPS-EB
cIPS-L-1
W
B
W
B
x
W
x:
W
m²
W
B
x
W
B
x
W
B
ecoli
4
0
3
10
0
0
arrbythmia
0
10
10
0
7
3
0
10
0
0
micro-mass
3
10
0
10
0
0
10
0
0
10
0
0
10
balance-scale
0
10
0
6
10
0
0
cating
3
2
2
10
10
0
6
0
8
2
0
vehicle
3
5
10
yeast
0
2
2
10
0
10
0
2
8
7
3
0
page-blocks
10
10
optdigits
0
0
10
10
0
10
0
9
3
7
0
satimage
10
7
kropl
0
10
0
0
10
10
0
10
0
10
0
0
10
0
0
10
H.2
Off-policy learning
H.2.1
Datasets
As described in the experiments section, we follow exactly the experimental design of Sakhi et al. [49], Aouali et al. [5] to conduct our PAC-Bayesian Off-Policy learning experiments. We however take the time to explain it in details. In this procedure, we need three splits: D; (of size nt) to train the logging policy To, another split D. (of size n))) to generate the logging feedback with mo, and finally test split Dtest (of size Tltea)) to compute the true risk R(xx) of any policy In our experiments, we split the training split Dtrasn (of size N) of the four datasets considered into Dj (ny = 0.05.) and De (ne 0.95N) and use their test split Drest- The detailed statistics of the different splits can be found in Table 7. Recall that K is the number of actions and the number of features.
Table 7: OPL: Detailed statisties of the splits used.
Datasets MNIST
N
11g
Altest
K
p
60 000
3000
57 000
10 000
10
784
MNSSi
60 000
3000
57 000
10 000
10
784
EMNIST-b
112 800
5640
107 160
18 800
47
784
NUS-WIDE-128
161 789
8089
153 700
107 859
81
128
H.2.2 Policy class
In the PAC- BAC-Bayesian Learning paradigm, we are interested in the definition of policies as mixtures of decision rules:
(a|x)) = Eso~ [1 [fo(x) = a]]
V(r,a) E x A.
(56)
We use the Linear Gaussian Policy of Sakhi et al. [49]. To obtain these policies, we restrict fo to:
Vz E X, fo(x) argmax (x'0w.}
(57)
a'EAA
This results in a parameter 0 of dimension d p K with p the dimension of the features d(x) and K the number actions. We also restrict the family of distributions 2s+1 = {Qu.o N (1, μ E Rd, a > 0} to independent Gaussians with shared seale. Estimating the propensity of given reduces the computation to one dimensional integral:
II + (c+ olx) (R, Har) -Ha)) a'
H
Tu. (alx)) = (E..)(
al(o(1)]
with & the cumulative distribution function of the standard normal.
H.2.3 Detailed hyperparameters
Contrary to previous work, our method does not require tuning any loss function hyperparameter over hold out set. We do however need to choose parameters to optimize the policies.
The logging policy ma. wa is trained on D; (supervised manner) with the following parameters: We use L2 regularization of 10-1. This is used to prevent the logging policy xo from being close to deterministic, allowing efficient learning with importance sampling. We use Adam [30] with learning rate of 1 for 10 epochs.
42

---

Parameters of the bounds. cIPS and eveIPS: The clipping parameter 7 is fixed to 1/K with K the action size of the dataset and evelPS is used with 0.5 (the values used Sakhi et al. [49]). ES: The exponential smoothing parameter is fixed to -
Optimizing the bounds. We use Adam [30] with learning rate of 10-3 for 100 epochs. The gradient of LIG policies is one dimensional integral, and is approximated using 5 = 32 samples.
II + (et o(z) Mo.) a'zaa
(1)o) = Be-N((0.))
al([(x)|1
8
II + ce 6(x)² -oo) a al(ø(x))
2 S
Σ sml a'
61, eg (1.
For all bounds, instead of fixing X, we take a union bound over a discretized space of possible parameters A of size nA = 100 and for each iteration j of the optimization procedure, we take X5 A that minimizes the estimated bound and proceed to compute the gradient w.r.t μ and with Aj.
H.2.4 Detailed results
In addition to the results of Table 2, we also provide a more detailed view of the results here. For each a and dataset, we average both {GR, R} over the 10 seeds and plot them in Figure and Figure Note that the error bars are too small o o/v10 ze 0.001 and our results in these graphs are significant. We observe that the LS BAC-Bayesian bound improves substantially its competitors terms of the guaranteed risk, especially on MNIST and FashionMNIST and also obtains the best performing policies, on par with the IX bound in the majority of scenarios.
OPL: Guaranteed Risk Given by different Bounds FashionMRiST
Guaranteed Risk of Different Bounds GR
MNIST
-0.3
-33
-0.4
eXIPS
0.10
0.15
-0.7
-0.8
-0.30
parameter
Figure 5: OPL: Guaranteed Risk given by the different bounds. We observe that our LS-LIN dominates all other bounds. IX comes close, especially on EMNIST and nuswide
OPL: obtained policies EMNIST
MNNST
FashionMNiST
nuswide
-305
True tisk of Obtaredd Phikies
-0.55
0.55
CVCPS
IX
-0.2
LS UN
-3.20
-0.3
-3.25
-0.00
0.75
0.35
0.2 0.6
0.6
3.0
0.6
0.5
1.0
0.6
0.8
1.0
0.4
0.6
0.8
3.0
temperatureeeeeeeoeoeooeoo parameter
lemuerarure romnetrr
parametee
Figure 6: OPL: True risk of obtained policies after minimizing the PAC-Bayesian bounds. We observe that LS-LIN and IX are hardly distinguishable, they both give the best policies the majority of scenarios.
43

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction scopes our work the offline contextual bandit setting, describes our method and claims its superiority compared existing work. We provide both strong theoretical and empirical evidence in the paper to defend the claim.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: provide the limitations our method Appendix A and discuss ways to mitigate them in future work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
44

---

Answer: [Yes]
Justification:
All our results are proven in the paper and all assumptions are discussed.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Our paper follows the classical off-policy experimental design, and all details to reproduce them are given in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
45

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All data used is accessible UCI Repository, the code is also given in the supplementary material reproduce all experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
wwt.sSuwwmmssioooooooooooooooooe Plylc))lllll. for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. httpppubllccceeee wwwlcc/ggge///eeee SondeSubmissiioPooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental settings are detailed Section and Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
with multiple seeds and for different scenarios and datasets. Some graphs do not need error bars (cumulative distributions or selection strategies), for the other results, we have very small error bars (Appendix H.2), making our results significant.
Justification: All our experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
46

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiments can be conducted in small machines and do require heavy compute, this is detailed in Appendix H.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpp::////urippee wttphhewwws...uuuu..eeee cccpublic//eeeececcceeccceeeeeee htte//Ethiiiiiiiee csGuidelines"
Answer: [Yes]
Justification:
Our paper is of theoretical nature, presents ideas to increase safety in decision making, uses publicly available data for the experiments and conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The paper discusses both the positive and negative impacts in Appendix B.
Guidelines:
47

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Our paper tackles theoretical questions for decision- decision-making, the data used for the experiments is openly accessible in UCI repository. We do believe that our work poses such risks.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our experimental design is inspired from the code base of some papers that we cite, and all data used is openly accessible in UCI repository.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
48

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi paperswithcode thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not release new assests, but we give the code to reproduce the experi- ments in the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
49

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
50


Reviews:
[{"review_id": "W3rUllaga2", "reviewer": "Reviewer_VVmk", "summary": "Policy evaluation, selection and optimization are considered in the context of offline contextual bandits, where i.i.d. data with a known behavior policy is given. The authors set out to study a generalization of importance weighted policy evaluation; for this they start from a general formulation that computes a value for all data observations, which are then averaged. The free \"parameter\" here is $h$, the function that assigns a value given an observation (of a context, associated action, and cost). A tight, general, high probability upper bound on the expected cost of a fixed target policy is derived first. Specific choices for the map $h$ are then derived based on minimizing this upper bound. Two practical solutions to this optimization problem are studied in more details: Global clipping and \"logarithmic smoothing\". Results are then derived for both policy selection and optimization.", "questions": "Can you explain why you did not follow the protocol and reported values of [31]?", "limitations": "na", "rating": 10, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Novel ideas, novel results, good empirical results.", "weaknesses": "Despite saying  that the methodology of paper [31] is adopted, this is only partially done. Why deviate from the evaluation in [31]? I expected an explanation of this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we would like to thank you for your positive feedback acknowledging the quality of our work, and we hope that our response addresses your question.\n\nIn our paper, we adopt the experimental design of [31] for both pessimistic policy evaluation and selection. The authors of [31] identified technical errors in their derivations after the publication of the paper, which they corrected by making stronger assumptions (one-hot rewards) and changing their proof technique. These changes resulted in loosened bounds and experimental results that were inconsistent with their initial findings. For more details, please refer to Appendix A of the updated arXiv version of [31].\n\nThese modifications are also reflected in the official GitHub repository of [31], which we used for part of our experiments. Due to these discrepancies, we reran all experiments from scratch for better reproducibility. Our code is included in the supplementary material and can be run to reproduce our results.\n\n\n\n[31] Ilja Kuzborskij, Claire Vernade, Andras Gyorgy, and Csaba Szepesvári. Confident off-policy evaluation and selection through self-normalized importance weighting. In International Conference on Artificial Intelligence and Statistics, pages 640–648. PMLR, 2021.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "UKM8OYEx31", "reviewer": "Reviewer_J96t", "summary": "This paper studies log-algorithmic smoothing of importance weight for off-policy learning. The proposed smoothing technique can be seen as a differentiable variant of clipping, which is useful for variance reduction for OPL. The paper also analyzes the PAC-Bayes learning bound of the proposed OPL method, characterized by the KL divergence with the logging policy, showing that the proposed method achieves a tighter bound than baselines, including simple clipping. The experiment also shows that the proposed method has tighter bounds than baselines and enables more accurate off-policy selection.", "questions": "- What are the connections with Metelli et al. 2021? (See weaknesses for the detailed comments.)\n\n- How does OPL work with the varying performance of the behavior policy? In my understanding, the policy will be pessimistic in out-of-distribution, but seeing how it works in experiments would be informative for readers.", "limitations": "Missing connection with a similar idea. See the weaknesses for the details.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- **Reasonable formulation based on theoretical analysis**: The proposed method is derived from a tight upper bound of the policy's risk. Also, the proposed method has an interpretation as soft, differentiable clipping. The technique is well-motivated and is reasonable to interpret.\n\n- **PAC-Bayes learning bound**: A sub-optimality form is derived, and it is also easy to interpret as a pessimistic approach, which should be acknowledged.\n\n- **Experiments on various tasks**: The paper evaluates the proposed approach in upper bound derivation, off-policy selection, and off-policy learning. The experiment results show the wide applicability of the proposed method in many OPE/OPL-related tasks.", "weaknesses": "- **Connection to Metelli et al. 2021 is not clear**: Metelli et al. 2021 also considers the importance of weight differential and shows that the proposed method achieves a Subgaussian rate. Similar to the reviewed paper, Metelli et al. 2021 also have a KL divergence term in the theoretical analysis. While the proposed method adequately differs from Metelli et al. 2021, and the paper does cite it, the paper does not mention Metelli et al. 2021 in the related work in detail. Since the motivation and contributions are similar, a detailed discussion on the advantages and the differences would be appreciated.\n\n- **Baselines in the experiments**: As mentioned above, Metelli et al. 2021 propose a similar idea that can be used as a baseline in experiments. Comparing with advanced regularization techniques such as shrinkage (Su et al. 2020) would also be informative.\n\n(Metelli et al. 2021) Subgaussian and Differentiable Importance Sampling for Off-Policy Evaluation and Learning. Alberto Maria Metelli, Alessio Russo, Marcello Restelli. NeurIPS, 2021.\n\n(Su et al. 2020) Doubly robust off-policy evaluation with shrinkage. Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, Miroslav Dudík. ICML, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we would like to thank you for your positive review, and we hope that our response addresses your questions and clears up any misunderstandings.\n\n**(1) Connection to Metelli et al. 2021**\n\nOur Logarithmic Smoothing (LS) estimator and the Harmonic estimator of Metelli et al. (2021) share similarities in how they avoid hard clipping on importance weights while obtaining sub-Gaussian concentration. However, they differ in several key aspects, which we list below:\n- **The motivation:** Metelli et al. (2021) introduced the Harmonic estimator specifically to mitigate the heavy tail of IPS and focused their study on it. In contrast, LS is motivated differently. We begin by deriving a high-probability upper bound that applies to a large family of regularized IPS estimators, including the Harmonic estimator. We then identify the estimator within this family that achieves the tightest possible bound. This turns out to be LS, a novel estimator that logarithmically smooths the importance weights. While the Harmonic estimator can be used with our bounds, the LS estimator provides tighter results.\n- **No empirical upper bound for the Harmonic estimator:** Metelli et al. (2021) study the properties of the Harmonic estimator and derive a concentration inequality (Theorem 5.1) that, in the case of contextual bandits, involves the divergence\n$$I_{\\alpha}(\\pi, \\pi_0) = \\mathbb{E}_{x \\sim \\nu, a \\sim \\pi_0(\\cdot|x)} \\left[  \\left(\\frac{\\pi(a|x)}{\\pi_0(a|x)} \\right)^\\alpha \\right],$$\nbetween the target policy $\\pi$ and the behavior policy $\\pi_0$. This quantity makes the upper bound **intractable** because it requires computing an expectation under the unknown distribution of contexts $\\nu$. Consequently, the derived concentration provides insight into the estimator's behavior but cannot be used to implement **pessimism** as it is not empirical. This contrasts with our fully empirical bounds that can be used directly for efficient pessimism.\n- **The LS estimator enjoys a better concentration:** Equation (2) (Page 5) of Metelli et al. (2021) proves the sub-Gaussian concentration of the Harmonic estimator. We also prove the sub-Gaussian property of the LS estimator in Proposition 13 in Appendix E.1 and briefly compare it to Metelli et al. (2021). Our findings show that the LS estimator enjoys a better sub-Gaussianity constant than the Harmonic estimator.\n- **Metelli et. al. 2021 do not have a KL term:** Metelli et al. (2021) only provide the concentration property of the Harmonic estimator and did not analyze the estimator in off-policy learning. Their concentration uses $I_{\\alpha}(\\pi, \\pi_0)$, which simplifies to the theoretical second moment of the importance weights when $\\alpha = 2$. This differs from the KL divergence between the distributions inducing the policies, which is proper to the PAC-Bayesian analysis of off-policy learning [5, 20, 48].\n\n**(2) Baselines in the experiments**\n\nIn our experiments, we aim to compare the ability of estimators to implement efficient **pessimism**. Therefore, we only include estimators from the literature that come with **empirical/tractable** upper bounds. This is why we include clipped IPS, SNIPS, and IX, but not Harmonic and Shrinkage, as these do not provide **empirical/tractable** upper bounds for pessimism.\n\n**(3) How does OPL work with the varying performance of the behavior policy?**\n\nThese experiments are given in Appendix H.2.4. Specifically, we conducted OPL experiments while varying the inverse temperature $\\alpha$ of the behavior policy. Changing $\\alpha$ interpolates between a uniform policy and a good behavior policy, resulting in different performance levels of the behavior policy. The main body of the paper presents aggregated results for ease of exposition, while detailed performance for each value of $\\alpha$ can be found in Appendix H.2.4. Generally, the performance of the learned policy for all methods decreases as the behavior policy's performance decreases. Overall, the performance gap between LS and the baselines widens as the behavior policy's performance gets lower.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "XF5XfQZfAG", "reviewer": "Reviewer_PPYn", "summary": "The authors propose empirical concentration inequalities for off-policy evaluation that apply to several forms of (smoothed) IPS, which are claimed to be tighter than the results in existing works. These bounds are then used to derive policy learning guarantees that inherit the properties of the concentration inequalities.", "questions": "In addition to the ones in \"Weaknesses,\" I have a specific question about Proposition 6. The gold standard in offline policy selection is a bound in the form of $R(\\pi) - R(\\widehat\\pi) \\le \\lambda S(\\pi) + \\varepsilon$ for any comparator policy $\\pi$ rather than the optimal one $\\pi^*$ (see [26] and [Wang 2024] and [Xie 2021]). The former is strictly more general -- can you write your bound in such a form?\n\n\n**References**\n\nWang, L., Krishnamurthy, A., & Slivkins, A. (2024, April). Oracle-efficient pessimism: Offline policy optimization in contextual bandits. In International Conference on Artificial Intelligence and Statistics (pp. 766-774). PMLR.\n\nXie, T., Cheng, C. A., Jiang, N., Mineiro, P., & Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34, 6683-6694.", "limitations": "I do not believe the authors have fully discussed the limitations of their method (see \"Weaknesses\").", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "I appreciate that the authors have applied their method to OPE, OPS, OPL, and also provided some experiments. \n\nI did not read the appendix nor check the correctness of the analysis in detail, but from a quick glance it appears that the authors were careful to provide rigorous and well-organized proofs.", "weaknesses": "My biggest criticism is that the authors have not justified *in the main body* their claim that \"LS is provably tighter than its competitors\" (L12) for any of the results, including the concentration inequalities (Prop 1, Cor 3, Cor 4) and the policy learning guarantee (e.g., Prop 6). \n\nSince these claims are the whole premise for the paper, their justification should be a central pursuit and only stating \"x is in Appendix y\" (L147, 178, 195) is hugely insufficient. \n\nFor example, I would have liked to see a discussion on (possibly even in graphs): \n- For the choices of $h$ described in (4), when do the bounds in Prop 1, Cor 3, and Cor 4 improve over the bounds from their respective papers? \n- Is $h*$ (the tightest choice) better than all of the above? \n- Does this hold for all hyperparameter choices, e.g. $\\lambda$ and $L$?\n- How does the computational complexity of calculating the bounds in Prop 1, Cor 3, Cor 4 hold up relative to their competitors? \n- Exactly how does this lead to downstream policy learning improvements?\n\nLastly, I found the overall technical presentation to be relatively poor, and I'll give a few examples: \n- The condition (C1) from Section 2 (\"Regularized IPS\") that all results depend on is never explicitly defined, and it should be an assumption that is called in every proceeding proposition/theorem statement.  \n- Shouldn't (11) be framed in, e.g., a lemma environment? \n- The term \"pessimism\" is overloaded, e.g., for \"high-probability upper bounds\" in L111 but also for an in-expectation variant in Eq. (5), which is slightly unusual (and I'm pretty sure not the way it's used in [26]) but not recalled again in the main body so I'm not sure what it's for (perhaps the proof of Prop 1).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we would like to thank you for your review and we hope that our response answers your questions and clears out misunderstandings. We think that your comments can be completely addressed and we hope this will lead you to increase your score.\n\n**Answer to the main criticism** \n\nFirst, we want to clarify that our claim \"LS is provably tighter than its competitors\" is theoretically proved by comparing (Eq. (13), Corollary 4) to existing bounds. This discussion was included in the Appendix and will be moved to the main text in the revised version as we will have additional space. This claim is also supported empirically by plotting the bounds (see answer below).\n\nSecond, there are many other equally important contributions central to the paper. We derive novel, high-probability empirical upper bounds applicable to a large family of \"regularized IPS\". These bounds are analyzed, compared, and minimized to obtain a new estimator, Logarithmic Smoothing (LS), which has favorable properties. Its empirical bound (Eq. (13), Corollary 4) is tighter than those of competitors, and the estimator is pessimistic by design, showing excellent performance in extensive OPE, OPS, and OPL experiments.\n\n**Answers to the points raised**\n\n**1-** For the choices of described in (4), when do the bounds in Prop 1, Cor 3, and Cor 4 improve over the bounds from their respective papers?\n\nFirst, to clear up any misunderstanding, we did not claim that our bounds are better than existing ones for any choice of $h$. We claimed that the LS bound (Eq. (13): Corollary 4, evaluated at its minimizer) is tighter than the existing bounds derived for their respective estimators.\n\nNow to address this question, we focus on the choices in (4): Clipping, Exponential Smoothing (ES), and Implicit Exploration (IX). Harmonic and Shrinkage do not come with empirical upper bounds, so they are omitted from this comparison. From the paper, we __theoretically__ prove:\n\n- Our bound with $L = 1$ (Cor 3) with $\\lambda \\sim \\mathcal{O}(1/\\sqrt{n})$ applied to Clipping is tighter than the empirical Bernstein bound for Clipping [56], especially when $\\pi$ is different from $\\pi_0$ (Appendix E.2.1).\n- ES only provides a PAC-Bayesian bound, which is proven to be worse than ours when applied to ES, for any $\\lambda$ (see Appendix E.4, starting line 818).\n- The LS bound $L = \\infty$ (Cor 4), evaluated at $h_{*, \\infty}$ (Eq. (13)), is tighter than the IX bound for any $\\lambda$ (Appendix E.2.2).\n\n\n**2-** Is $h^*$ better than all of the above? \n\n__Theoretically__, we can prove:\n\n- The bound of LS ($h_{*, \\infty}$) with any $\\lambda$ is tighter than the IX bound (Appendix E.2.2).\n- The bound of Global Clipping ($h_{*, 1}$) with $\\lambda \\sim \\mathcal{O}(1/\\sqrt{n})$ is tighter than the empirical Bernstein bound (Appendix E.2.1).\n- The bound of LS ($h_{*, \\infty}$) with any $\\lambda$ is tighter than the bound of Global Clipping (Proposition 5).\n- Thus, the LS bound is better than all known evaluation bounds: LS is better than IX and Global Clipping for any $\\lambda$. Since Global Clipping is tighter than empirical Bernstein when $\\lambda \\sim \\mathcal{O}(1/\\sqrt{n})$, LS is also better than empirical Bernstein for these values of $\\lambda$.\n- For learning, the PAC-Bayesian bound of LS ($h_{*, \\infty}$) is tighter than all known PAC-Bayesian bounds, for any $\\lambda$ (Appendix E.4).\n \n\n__Additional plots.__ The claims in __1-__ and __2-__ above are supported __empirically__ (see global response). These plots support even stronger claims such as showing that LS bound is better than empirical Bernstein for any $\\lambda$. In these plots, we compare Proposition 1 with different $L$ for different choices of $h$. We also compare our bounds (Global Clipping and LS) to Proposition 1 (for different $L$) evaluated in Clipping and IX and to their respective bounds (empirical Bernstein and the IX bound). Finally, a comparison of the bounds for different values of $\\lambda$ is provided. In particular, these plots also address your third point __3-__ Does this hold for all hyperparameter choices, e.g.  $L$ and $\\lambda$?\n\n**4-** How does the computational complexity of calculating the bounds in Prop 1, Cor 3, Cor 4 hold up relative to their competitors? \n\nOur bounds are tractable, in contrast to many existing studies that provide intractable bounds (e.g., [37, 56]). Tractable bounds do exist in the literature, with the IX bounds being the most computationally efficient. Cor 4 has a similar complexity to the IX bound, as it only requires computing the LS estimator without any additional high-order terms. \n\n**5-** Exactly how does this lead to downstream policy learning improvements?\n\nTighter bounds lead to policy selection and learning strategies with provably better regret/suboptimality. For example, the suboptimality derived for the LS estimator is tighter than that of the IX estimator in all scenarios (Appendix E.3 for OPS and Appendix E.5 for OPL). This typically translates into better empirical results, as supported by our experiments.\n\n**The technical presentation**\n\n- Condition **(C1)** is explicitly defined in line 100. We will refer to this condition in our propositions.\n- Eq. (11) is the derived minimiser of Cor 3 and was not framed as a proposition to ease reading.\n- The in-expectation pessimism is indeed used to prove Proposition 1, and we will drop its naming to offload the term 'pessimism'.\n\n**Subotimality with a comparator** $\\pi$ **instead of** $\\pi^*$ \n\nThe technique used to derive the suboptimality does not rely on any specific property of $\\pi^*$ and can be directly applied to prove the bound for any $\\pi$ by replacing $\\pi^*$ with $\\pi$. We will add this more general result to the Appendix. We aim to identify the optimal policy $\\pi^*$, which is why the suboptimalities are expressed w.r.t. $\\pi^*$. This is common in the literature [26, 27].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "BhxU3IfIqu", "reviewer": "Reviewer_j8sh", "summary": "The paper considers the offline contextual bandit problem. The authors consider a class of reward estimators for this setting that is a regularization of Inverse Propensity Scoring (IPS - aka importance sampling). A general concentration result is provided for this class of estimators. This is used to provide a tight result for an existing clipping IPS estimator and to construct a new Logarithmic Smoothing (LS) estimator. The resulting estimator is pessimistic by design, making it immediately applicable to the offline contextual bandit problem.\nThe authors use it to derive bounds for policy evaluation and selection and also for policy learning in the Bayesian setting. Experimental results also support the usefulness of the estimator.", "questions": "See above.", "limitations": "N/a", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I am only broadly familiar with this line of research making it hard for me to properly contextualize its contributions.\n\n1. The proposed estimator is novel and has nice properties.\n2. As the name suggests, the estimator is smooth making it potentially easy to optimize.\n3. The application to contextual bandits is interesting.\n4. The experimental results are positive.\n5. The overall writing is good and clear.", "weaknesses": "1. A more explicit comparison with existing concentration\\contextual bandit bounds is missing. The authors explain that their bound is better but this is somewhat vague, especially if the reader is not already an expert in this field.\n\n2. In line 155 the authors explain that their result can be derived from [1, Lemma 1.3]. Does this mean that the LS estimator has previously been suggested or only that an alternative proof technique exists for its concentration bound?\n\n3. Performance seems very close to that of IX\n\n4. The main body of the paper does not include any explanation of the techniques used. This can be a proof sketch for the concentration bound or a discussion comparing your approach to existing techniques. Can you provide such an explanation in your response?\n\n5. The notation U(pi) appears without definition in line 281. I assume it's defined in one of the references but should also be defined in this paper for completeness. (Please include an explanation in your response)\n\nTypo:\nline 98: one of the brackets is reversed in the definition of h", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank you very much for your positive review acknowledging the quality of our work. We hope our response addresses your questions and increases your confidence in our work. We will consider the points raised when updating the manuscript.\n\n**(1) Bound Comparisons**\n\nGiven the 9-page limit for the submitted paper, the tightness claim is thoroughly defended in the Appendix. We directed the reader to the full, explicit comparisons and discussions in the Appendix whenever a statement is made. Specifically:\n\n- **Appendix E.2 for OPE**:\n  - Comparison of the global clipping bound ($U^\\lambda_1$) with the empirical Bernstein bound for clipping (Appendix E.2.1).\n  - Comparison of the LS bound ($U^\\lambda_\\infty$) with the IX bound (Appendix E.2.2).\n\n- **Appendix E.4 for OPL**:\n  - Comparison of the PAC-Bayesian LS bound with the conditional Bernstein bound, the exponential smoothing bound, and the IX bound (Appendix E.4).\n\nAll these comparisons show that our bounds are tighter. \n\nTo respect the 9-page limit, the paper focuses on presenting the methodology, introducing the new estimator, and proving the versatility of the approach. With the additional page available in the camera-ready version, we will move these comparisons to the main text.\n\n**(2) Alternative Proof**\n\nThis is the first time the LS estimator has been proposed, with [1, Lemma 1.3] only providing an alternative proof of its concentration bound. We chose our proof technique for its generality, which is appealing for two reasons. First, it yields a family of empirical upper bounds for a wide range of regularized IPS estimators, such as clipping. Second, within this family, the LS estimator emerged as the one achieving the tightest bound. This strongly motivates the LS estimator, in contrast to defining it in advance (without a clear rationale for its selection) and applying [1, Lemma 1.3] for its concentration.\n\n**(3) Performance Close to IX**: \n\nOur experiments demonstrate the superiority of LS compared to IX in OPE and OPS. Even in OPL, LS has a better guaranteed risk than IX, and they are only comparable in terms of the risk of the learned policy. Morevoer, a formal comparison of the LS bound with IX is provided in Appendix E.2.2, showing that LS consistently outperforms IX (for any $\\lambda$, in any scenario). It also highlights that the LS bound significantly outperforms the IX bound when the target policy $\\pi$ is not deterministic and/or in the low data regime (starting from line 746). This is further confirmed by the detailed results in Appendix H.1.2.\n\n**(4) Proof Technique Used**\n\nIn the main text (line 121), we state that we use the Chernoff bound with a careful analysis of the moment generating function. Specifically, we prove the monotonicity of the logarithm's residual (the difference between the logarithm function and its Taylor expansion) to derive our results. Our approach differs from existing bounds by using the residual function in combination with the Chernoff bound.\n\n**(5) The Notation $U(\\pi)$ and Typo**\n\nThank you for pointing this out. $U(\\pi)$ refers to a generic bound evaluated for the target policy $\\pi$. We will include its explanation in the updated manuscript. We also thank you for highlighting the typo.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We are very grateful to the reviewers and AC for their valuable time. We attach to our rebuttal additional plots comparing the properties of the bounds for three different datasets and supporting empirically our theoretical findings, showing that the LS bound is tighter than its competitors.

**Figure 1- Comparison of Proposition 1 for different IPS regularisation functions $h$ and different $L$.**

For this plot, $\lambda$ is fixed to $1/\sqrt{n}$ while we vary the regularization function $h$ and the moment order $L$. We observe that the performance of the bound differs depending on the choice of $h$ and $L$. Additionally, the optimality of a regularization function $h$ depends on the value of $L$. For example, on the balance-scale dataset where the difference between methods is more apparent, Clipping (orange curve) is better than IPS without any regularization (blue curve) for finite values of $L$, while IPS becomes better when $L \to \infty$. This is why, in our paper, we seek the minimizer $h$ for our bounds to obtain the tightest results specific to values ($L = 1$ and $L \to \infty$), finding theoretically that the minimizer for $L=1$ differs from that for $L \to \infty$. These empirical bound plots confirm this aspect of our theory.

**Figure 2- Comparison with Clipping and its empirical Bernstein bound.**

For this plot, $\lambda$ is fixed to $1/\sqrt{n}$ and $M = \sqrt{n}$ (where $M$ is the hyper-parameter of Clipping as shown in Eq. (4)). We observe that Proposition 1 applied to Clipping, as well as our other bounds (Global Clipping and LS), outperform Clipping and its empirical Bernstein bound in all scenarios.

**Figure 3- Comparison with IX and its bound.**

For this plot, $\lambda$ is fixed to $1/\sqrt{n}$. We observe that our Proposition 1 evaluated in IX does not perform well compared to the specialized IX bound. Global Clipping is comparable to the IX bound and is tighter in scenarios with sufficient data (2nd and 3rd plot). Finally, our LS bound is always tighter than the IX bound, as proven theoretically in our paper (Appendix E.2.2).

**Figure 4- Comparison of the bounds for different values of $\lambda$.**

For this plot, we set $M = 1/\lambda$ for the empirical Bernstein bound of Clipping and vary $\lambda$ for all our bounds. As already proven in our paper, the LS bound is better than both Global Clipping (Proposition 5) and the IX bound (Appendix E.2.2) in all scenarios, for all values of $\lambda$. We also observe that all our bounds outperform the empirical Bernstein bound of Clipping, especially in the region of $\lambda \sim \mathcal{O}(1/\sqrt{n})$, as shown theoretically in Appendix E.2.1.

Meta-review: This paper gives strong results for off-policy policy evaluation using importance sampling, where the importance ratios can be transformed using a class of functions to navigate the bias-variance tradeoff. The formulation makes the result quite general and the authors give a variety of examples for typically used transformation functions which fit their conditions, as well as use the resulting bounds to identify near-optimal choices. They further study the impacts of these ideas for policy learning, and evaluate their results empirically.
The results presented here are very nice, but the presentation could use a fair bit of improvement. This is reflected in several reviewers having difficulty understanding parts of the paper. Particularly the writing around the logarithmic smoothing and its optimality needs to be improved so that it is very clear that the optimality claim is rigorous. 
There are questions about the empirical evaluation as well, and I encourage the authors to address any discrepancies between the setup of [31] and their work.
Decision: Accept (spotlight)