Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning

Authors: otmane  sakhi
imad  aouali
pierre  alquier
nicolas  chopin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 18:19:57

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.

Main paper: 
 introduction: 
 In decision-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 we possess logged data summarizing an agent's past interactions [10] . These interactions, typically captured as context-action-reward tuples, hold valuable insights into the underlying dynamics of the environment. Each tuple represents a 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 a reward that depends on 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 is 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.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 (OPL) [55] . OPE estimates the risk: the negative of expected reward that a target policy would achieve, essentially predicting its performance if deployed. OPS selects the best-performing policy from a 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.A 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 decision-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 a 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 et 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 a pre-defined risk estimator, often chosen to simplify the analysis. We propose a different approach: we derive general concentration bounds applicable to a broad class of regularized IPS estimators and then identify the estimator within this class that achieves the tightest concentration bound. This leads to a tailored estimator, named Logarithmic Smoothing (LS). LS enjoys several desirable properties. It concentrates at a sub-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-art 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 2 introduces the necessary background. In Section 3, we provide unified risk bounds for a 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 6 provides concluding remarks.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 in the offline contextual bandit setting, describes our method and claims its superiority compared to 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 in 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
setting and background: 
 Offline contextual bandit. Let X ⊂ R d be the context space, which is a compact subset of R d , and let A = [K] be a finite action set. An agent's actions are guided by a stochastic and stationary policy π ∈ Π within a policy space Π. Given a context x ∈ X , π(•|x) is a probability distribution over the action set A; π(a|x) is the probability that the agent selects action a in context x. Then, an agent interacts with a contextual bandit over n rounds. In round i ∈ [n], the agent observes a context x i ∼ ν where ν is a distribution with support X . After this, the agent selects an action a i ∼ π 0 (•|x i ), where π 0 is the behavior policy of the agent. Finally, the agent receives a stochastic cost c i ∈ [-1, 0] that depends on the observed context x i and the taken action a i . This cost c i is sampled from a cost distribution p(•|x i , a i ). This leads to n-sized logged data, D n = (x i , a i , c i ) i∈ [n] , where tuples (x i , a i , c i ) for i ∈ [n] are i.i.d. The expected cost of taking action a in context x is c(x, a) = E c∼p(•|x,a) [c] , and the costs are negative because they are interpreted as the negative of rewards. The performance of a policy π ∈ Π is evaluated through its risk, which aggregates the expected costs c(x, a) over all possible contexts x ∈ X and taken actions a ∈ A by policy π, such asEQUATIONThe main goal is to use logged dataset D n 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 Rn (π) of the risk R(π) of a fixed target policy π and study its deviation, aspiring for Rn (π) to concentrate well around R(π). Second, OPS focuses on selecting the best performing policy πS n from a predefined and finite collection of target policies {π 1 , . . . , π m }, effectively seeking to determine argmin k∈[m] R(π k ). Third, OPL aims to find a policy πL n within the potentially infinite policy space Π that achieves the lowest risk, essentially aiming to find argmin π∈Π R(π). In general, both OPS and OPL 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(π), 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 π 0 ,EQUATIONwhere for any (x, a) ∈ X × A , w π (x, a) = π(a|x)/π 0 (a|x) are the IWs. IPS is unbiased under the coverage assumption (see for example Owen [39, Chapter 9] ). However, it can suffer high variance, which tends to scale linearly with IWs [57] . This issue becomes pronounced when there is a significant discrepancy between the target policy π and the behavior policy π 0 . To mitigate this, a common strategy consists in applying a regularization function h : [0, 1] 2 × [-1, 0] → (-∞, 0] to π(a|x), π 0 (a|x) and c. This function is designed to reduce the estimator's variance at the cost of introducing some bias. Formally, the function h needs to satisfy the condition (C1), that is defined by h satisfies (C1) ⇐⇒ ∀(p, q, c) ∈ [0, 1] 2 × [-1, 0], pc/q ≤ h(p, q, c) ≤ 0.(C1) With such function h, the regularized IPS estimator readsEQUATIONwhere h i = h (π(a i |x i ), π 0 (a i |x i ), c i ). We recover standard IPS in (2) when h(p, q, c) = pc/q. Numerous regularization functions h were studied in the literature. For example, h(p, q, c) = min(p/q, M )c , M ∈ R + =⇒ Clipping [10] , (4) h(p, q, c) = pc/q α , α ∈ [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 (C1), we can derive our core result: a family of high-probability bounds that hold for regularized IPS.(1 + λx) ≥ λx 1+λx/2 , ∀x ≥ 0. 3. The use of -π(a i |x i )c i ≤ 1, ∀i ∈ [n].The two first inequalities are loose when λ ∼ 1/ √ n is not too small, which means that LS will be much better in problems with few samples. The third inequality is loose when π is not a peaked policy or the cost is way less than 1. Even if 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.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We provide the limitations of our method in Appendix A and discuss ways to mitigate them in future work. Guidelines:• The answer NA means that the paper has no 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 a 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 of 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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-probability upper bounds to assess any policy'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).Let λ > 0, π ∈ Π, and h satisfying (C1), we defineEQUATIONEQUATIONwhere Mh,ℓ n (π) is the empirical ℓ-th moment of regularized IPS Rh n (π), and ψ λ : R → R is a contraction function satisfying ψ λ (x) ≤ x for any x ∈ R. Then, we state our first result. Proposition 1 (Empirical moments risk bound). Let π ∈ Π, L ≥ 1, δ ∈ (0, 1], λ > 0, and h satisfying (C1). Then it holds with probability at least 1 -δ thatEQUATIONwhere ψ λ and Mh,ℓ n (π) are both defined in (5) , and recall that ψ λ (x) ≤ x.In Appendix F.1, we provide detailed proof, leveraging Chernoff bounds with a careful analysis of the moment-generating 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 (C1), enabling the design of a tailored h 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 λ, higher values of L yield tighter bounds, though potentially at the cost of increased computational complexity as we would need to compute higher order moments. This is formally stated as follows.Proposition 2 (Impact of L). Let π ∈ Π, δ ∈ (0, 1], λ > 0, L ≥ 1, and h satisfying (C1). Then,EQUATIONFrom (7) , the bound U λ,h L (π) in ( 6) becomes a decreasing function of L when λ ≤ min i∈[n] (1/|h i |), suggesting that for sufficiently small λ, the tightest bound is achieved as L → ∞. 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 = 1 can be always improved by increasing L. Proposition 3 (Comparison of our bounds). Let π ∈ Π, and λ > 0, we defineEQUATIONwith the minimum taken over h satisfying (C1). Then, for any λ > 0, it holds that for any L > 1,EQUATIONProposition 3 shows that, irrespective of the value of λ, the bound with L = 1 can be always improved by bounds of increased moment order L, evaluated at their optimal regularizer h * ,L . This result encourages us to study bounds with high moment order L, especially if we can derive their optimal regularizers h * ,L . To this end, we examine two cases: L = 1, which results in an empirical secondmoment bound, and L → ∞, yielding a 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 L → ∞ motivates a novel logarithmic smoothing estimator. We begin by analyzing our empirical moment risk bound at L = 1.Corollary 4 (Empirical second-moment risk bound with L = 1). Let π ∈ Π, δ ∈ (0, 1], λ > 0, and h satisfying (C1). Then it holds with probability at least 1 -δ thatEQUATION)This is a direct consequence of (6) when L = 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 * ,1 writes h * ,1 (p, q, c) = -min(p|c|/q, 1/λ) .(11) In particular, if we assume that costs are binary, c ∈ {-1, 0}, then h * ,1 corresponds to clipping in (4) with parameter M = 1/λ. This is because -min(|c|p/q, 1/λ) = min p/q,1 λ c when c 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 1 for binary costs. In general, the cost should also be clipped (as in (11) ). Finally, with a suitable choice of λ = O(1/ √ n), our bound in Corollary 4, using clipping (i.e., h = h * ,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 * ,1 and formal comparisons with empirical Bernstein are provided in Appendix F.5. In the next section, we study our general bound when we set L → ∞.Corollary 5 (Empirical infinite-moment bound with L → ∞). Let π ∈ Π, δ ∈ (0, 1], λ > 0, and h satisfying (C1). Then it holds with probability at least 1 -δ thatEQUATIONAppendix F.6 provides detailed proof. Setting L → ∞ in (6) results in the bound in Corollary 5, which has different properties than Corollary 4. The resulting bound has a 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 no additional computational complexity. As the bound is increasing in h, the function h * ,∞ that minimizes this bound is h * ,∞ (p, q, c) = pc/q. This corresponds to the standard IPS in (2). This differs from the L = 1 bound in Corollary 4 that favored clipping. This shows the impact of the moment order L on the optimal function h. For any π ∈ Π, applying the bound in Corollary 5 with the optimal h * ,∞ leads to U λ ∞ (π), of the following expression:EQUATION)Even if we set h * ,∞ (p, q, c) = pc/q (without IW regularization), U λ ∞ (π) can be seen as a risk upper bound of a novel regularized IPS estimator (satisfying (C1)), called Logarithmic Smoothing (LS): The LS estimator in ( 14) is defined for any non-negative λ ≥ 0, with its bound in (13) holding for any positive λ > 0. Notably, λ = 0 retrieves the standard IPS estimator in (2), while λ > 0 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/λ. A Taylor expansion of our estimator around λ = 0 yieldsEQUATIONRλ n (π) = Rn (π) + ∞ ℓ=2 λ ℓ-1 ℓ 1 n n i=1 (w π (x i , a i )c i ) ℓ .Thus, LS is a pessimistic estimator by design, implicitly implementing a form of Sample All Moments Penalization, which generalizes the Sample Variance Penalization [55] . To examine the statistical properties of our estimator, we introduceEQUATIONwhich quantifies the discrepancy between π and π 0 . Notably, S λ (π) is always smaller than the second moment of the IW, effectively interpolating between a weighted first moment (λ ≫ 1) and the second moment (λ = 0) of IPS. This quantity S λ characterizes the concentration properties of the LS estimator akin to the coverage ratio for IX estimator [21] . With S λ defined, we proceed by bounding the mean squared error (MSE) of our estimator, specifically bounding its bias and variance. Proposition 6 (Bias-variance trade-off). Let π ∈ Π and λ ≥ 0. Let B λ (π) and V λ (π) be respectively the bias and the variance of the LS estimator. Then we have that0 ≤ B λ (π) ≤ λS λ (π) , and V λ (π) ≤ S λ (π) n .Moreover, it holds that for any λ > 0, the variance is finite asV λ (π) ≤ |R(π)|/λn ≤ 1/λn.We observe that both the bias and variance are controlled by S λ (π). Particularly, λ = 0 recovers the IPS estimator in (2), with zero bias and a variance bounded by E w 2 (x, a)c 2 /n. When λ > 0, a bias-variance trade-off emerges. The bias is always non-negative and is capped at λS λ (π), which diminishes to zero when λ is small and goes to |R(π)| as λ increases. Conversely, the variance decreases with a higher λ. Notably, λ > 0 ensures finite variance bounded by 1/λn, 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 λ = O(1/ √ n) ensures that our LS estimator enjoys a sub-Gaussian concentration [38] .Proposition 7 (Sub-Gaussianity and comparison with Metelli et al. [38] ). Let π ∈ Π, δ ∈ (0, 1] and λ > 0. Then the following inequalities holds with probability at least 1 -δ:R(π) -Rλ n (π) ≤ ln(2/δ) λn , and Rλ n (π) -R(π) ≤ λS λ (π) + ln(2/δ) λn .In particular, settingEQUATIONThus, a particular choice of λ * ensures that Rλ * n (π) is sub-Gaussian, with a variance proxy σ 2 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 3 already showed that U λ ∞ (π), the bound of LS is tighter than U λ 1 (π), the bound in Corollary 4 evaluated at the Global clipping function h * ,1 . 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. [21] ). Let π ∈ Π, δ ∈]0, 1] and λ > 0, the IX bound from [21] states that we have with probability at leastEQUATION)Let U λ IX (π) be the upper bound of (17), we have for any λ > 0:EQUATIONThis result states that no matter the scenario, for any evaluated policy π, and any chosen λ > 0, the LS bound will be always tighter than IX. The gap between the LS and IX bounds increases when n is small, or when the evaluated policy π is 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-policy selection and learningQuestion: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• 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 or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are 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. 
off-policy selection: 
 Let Π S = {π 1 , ..., π m } be a finite set of policies. In OPS, the goal is to find π S * ∈ Π S that satisfiesEQUATIONAs we do not have access to the true risk, we use a data-driven selection strategy that guarantees the identification of policies of performance close to that of π S * . Precisely, for λ > 0, we search forEQUATION)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 Rλ n (π), 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 π 0 . As we show next, it also ensures low suboptimality. Proposition 9 (Suboptimality of our selection strategy in (20) ). Let λ > 0 and δ ∈ (0, 1]. Then, it holds with probability at least 1 -δ thatEQUATIONwhere S λ (π), π S * and πS n are defined in (15) , (19) and (20) .The derived suboptimality bound only requires coverage of the optimal actions (support of the optimal policy π s * ), 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 λ s n = 2 ln(2|Π S |/δ)/n for LS, we achieve a suboptimality scaling ofEQUATIONwhich ensures finding the optimal policy with sufficient samples. Additionally, the multiplicative constant is smaller when π 0 is close to π S * , confirming the known observation that it is easier to identify the best policy if it is similar to the behavior policy π 0 .Similar to how we extended the evaluation bound in Corollary 5 (which applies to a single fixed target policy) to OPS (where it applies to a finite set of target policies), we can further derive bounds for an infinite policy class Π, enabling OPL. Several approaches have been proposed in previous work, primarily based on replacing the finite union bound over policies with more sophisticated uniform-convergence arguments. This was used by [55] , which derived a 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 λ, toEQUATIONwhere C(Π) is a complexity measure [61] . This learning strategy is straightforward because it involves a 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(Π) 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-Bayesian 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(Θ) = {f θ : X → [K], θ ∈ Θ} be a set of parameterized predictors that associate the context x with the action f θ (x) ∈ [K]. Let P(Θ) be the set of all probability distributions on Θ. Each distribution Q ∈ P(Θ) defines a policy π Q by setting the probability of action a given context x as the probability that a random predictor f θ ∼ Q maps x to action a, that is,EQUATION)This characterization is not restrictive as any policy can be represented in this form [49] . Deriving PAC-Bayesian generalization bounds with this policy definition requires the regularized IPS to be linear in the target policy π [35, 5, 21] . 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 asEQUATIONwhich smooths the impact of the behavior propensity π 0 instead of the IWs π/π 0 . We provide in the following a core result of this section, the PAC-Bayesian bound that defines our learning strategy.Proposition 10 (PAC-Bayes learning bound for Rλ-LIN n ). Given a prior P ∈ P(Θ), δ ∈ (0, 1] and λ > 0, the following holds with probability at least 1 -δ:EQUATIONwhere KL(Q||P ) is the Kullback-Leibler divergence from P to Q.PAC-Bayes bounds hold uniformly for all distributions Q ∈ P(Θ) and replace the complexity measure C(Π) with the divergence KL(Q||P ) 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, it is typically set to the distribution inducing the behavior policy π 0 , meaning P satisfies π 0 = π P . 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 π 0 .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-Bayesian bounds can be found in Appendix E.4. For a fixed λ and a fixed prior P , we derive a learning strategy that minimizes the upper bound for a subset L(Θ) ⊆ P(Θ) of distributions, seekingEQUATIONEQUATION(27) is 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 * = argmin Q∈L(Θ) R(π Q ).Proposition 11 (Suboptimality of the learning strategy in ( 27)). Let λ > 0, P ∈ L(Θ) and δ ∈ (0, 1].Then, it holds with probability at least 1 -δ thatEQUATIONwhere S LIN λ (π) = E π(a|x)c 2 /(π 2 0 (a|x) -λπ 0 (a|x)c) and πL n is defined in (27) .Our suboptimality bound only requires coverage of the support of the optimal policy π Q * . This bound matches the minimax suboptimality lower bound of pessimistic learning with deterministic policies [28] . Appendix G. 0 ≤ R(π L n ) -R(π Q * ) ≤ (2S LIN λ l n (π Q * ) + KL(Q * ||P ) + ln(2/δ))/ √ n.By setting the reference P to the distribution inducing π 0 , we find that the learning suboptimality is reduced when the behavior policy π 0 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 π 0 is close to π Q * . 
experiments: 
 Our experimental setup follows the standard multiclass-to-bandit 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) a with context (features) x is modeled as Bernoulli with probabilityp x = ϵ + 1 [a = ρ(x)] (1 -2ϵ), where ρ(x) be the true label of features x, and ϵ is a noise parameter. In particular, the true label ρ(x) represents the action with the highest average reward for context x. This setup ensures an average reward of 1 -ϵ for the optimal action ρ(x) and ϵ for all others, constructing a logged bandit feedback dataset in the form {x i , a i , c i } i∈ [n] , where c i = -r i is the associated cost.For both evaluation and selection, we adopt the same experimental design as [32] to facilitate the comparison. We consider exponential target policies π(a|x) ∝ exp( 1 τ f (a, x)), with τ a temperature controlling the policy's entropy and f (a, x) the score of the item a for the context x. We use this to define ideal policies as π ideal (a|x) ∝ exp( 1τ I{ρ(x) = a}), and also create faulty, mismatching policies for which the peak is shifted to another, wrong action for a set of faulty actions F ⊂ [K]. To recreate real world scenarios, we also consider policies directly learned from logged bandit feedback, of the formπ θ IPS (a|x) ∝ exp( 1 τ x t θ IPS a ) and π θ SN (a|x) ∝ exp( 1 τ x t θ SN a ), with their parameters learned (OPE) Tightness of the bounds. Evaluating the worst case performance of a policy is 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 U (π) with a small relative radius |U (π)/R(π) -1|. We compare our newly derived bounds (cIPS-L=1 for U λ 1 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-EB: Empirical Bernstein for Clipping [55] and the recent IX: Implicit Exploration bound [21] . The first experiment uses the kropt dataset with ϵ = 0.2, collects bandit feedback with faulty behavior policy (with τ = 0.25) to evaluate an ideal policy (τ = 0.1), and explores how the relative radiuses of the considered bounds shrink while varying the number of datapoints. Table 1 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 (τ 0 ∈ {0.2, 0.25, 0.3}) and different noise levels (ϵ ∈ {0., 0.1, 0.2}) to evaluate ideal policies with different temperatures (τ ∈ {0.1, 0.2, 0.3, 0.4, 0.5}), defining ∼ 500 different scenarios to validate our findings. We plot in Figure 2 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 in 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. In practice, we are interested in finding policies that improve on π 0 and avoid policies that perform worse than π 0 . To replicate real world scenarios, we design an experiment where π 0 is a faulty policy (τ = 0.2), that collects noisy (ϵ = 0.2) interaction data, some of which is used to learn π θ IPS , π θ SN , and that we add to our discrete set of policies Π k=4 = {π 0 , π ideal , π θ IPS , π θ SN }. The goal is to measure the ability of our selection strategies to choose from Π k=4 , better performing policies than π 0 . We thus define three possible outcomes: 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 110 scenarios. We plot in Figure 2 the percentage of time each method selected the best policy, a better or a worse policy than π 0 . While risk estimators can identify the best policy, they are unreliable as they can choose worse performing policies than π 0 , a 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) can be found in Appendix H.1.3.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- 7 ) as in [49, 5] and adopt the LGP: Linear Gaussian Policies [49] as our class of parametrized policies. For each dataset, we use behavior policies trained on a small fraction of the data in a supervised fashion, combined with different inverse temperature parameters α ∈ {0.1, 0.3, 0.5, 0.7, 1.} 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, we minimize the empirical upper bounds U (π) directly and obtain the learned policy as the bound's minimizer πL n (as in ( 27)). With πL n obtained, we are interested in two quantities: The guaranteed risk by the bound, which is the value of the bound U (π L n ) 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 of the bound R(π L n ) 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-LIN learning strategy in (27) to strategies based on 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 2 where we compute:cIPS cvcIPS ES IX LS-LIN (Ours) rI(U (π L n ))rI(x) = (R(π 0 ) -x)/(R(π 0 ) -R(π * )) = (R(π 0 ) -x)/(R(π 0 ) + 1) ,the improvement over R(π 0 ) achieved by minimizing the different bounds in terms of x ∈ {U, R} (guaranteed risk and true risk respectively), relative to 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-Bayesian 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-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, a 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, it 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 in 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.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Our experiments can be conducted in small machines and do not require heavy compute, this is detailed in Appendix H.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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:• 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper tackles theoretical questions for decision-making, the data used for the experiments is openly accessible in UCI repository. We do not believe that our work poses such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a 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 use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• 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. 
 
 Appendix: 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 in 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 is valid in 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.Our work contributes to the development of theoretically grounded and practical pessimistic approaches for the offline contextual bandit setting. The derived algorithms can improve the robustness of decision-making processes by prioritizing safety and minimizing uncertainty associated risks. By leveraging pessimistic strategies, we ensure that decisions are made with a 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.Offline contextual bandits. Contextual bandit is a widely adopted framework for online learning in uncertain environments [33] . However, some real-world applications present challenges for existing online algorithms, and thus offline methods that leverage historical data to optimize decisionmaking 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-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 a predefined finite set (off-policy selection (OPS)) or the optimal policy overall (off-policy learning (OPL)).Off-policy evaluation. In recent years, OPE has experienced a noticeable surge of interest, with numerous significant contributions [16-18, 60, 19, 54, 38, 32, 45, 47, 26] . The literature on OPE can be broadly classified into three primary approaches. The first, referred to as the direct method (DM) [26, 6] , involves the development of a model designed to approximate expected costs for any context-action pair. This model is subsequently employed to estimate the performance of the policies. This approach is often designed for specific applications such as large-scale recommender systems [47, 26, 4] . 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 is 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. In contrast, in OPL, DM either deterministically selects the action with the highest estimated reward or constructs a distribution based on these estimates. IPS and DR, on the other hand, employ gradient descent for policy learning [55] , updating a parameterized policy denoted by π θ as θ t+1 ← θ t -∇ θ R(π θ ) for each iteration t.Since the true risk R is unknown, ∇ θ R(π θ ) 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 OPL. However, point estimators can deviate from the true value of the risk, rendering them unreliable for decision-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, 21] , aim to evaluate a policy'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-Stein bound for the self-normalized IPS estimator, while [21] anchored their analysis on a bound constructed with the Implicit Exploration estimator. Shifting focus to OPL, [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 introduction) 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-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 OPL. This perspective was further explored by [20, 49, 5, 7, 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 i within logged data and defines the risk estimator asRMIPS n (π) = 1 n n i=1 π (e i | x i ) π 0 (e i | x i ) c i = 1 n n i=1 w (x i , e i ) c i ,where the logged data D n = {(x i , a i , e i , r i )} n i=1 now includes action embeddings for each data point. The marginal importance weightw(x, e) = π(e | x) π 0 (e | x) = a p(e | x, a)π(a | x) a p(e | x, a)π 0 (a | x) is 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] explored non-parametric evaluation and learning of continuous action policies using kernel smoothing, while [13] investigated the semi-parametric setting. Recently, [59] leveraged the smoothing approach from [31] to extend their discrete OPL method to continuous actions. Our work can either use the densities directly, or be similarly extended to continuous actions through a well-defined discretization of the space. Imagine a scenario with infinitely many actions, where policies are defined by density functions. For any context x, π(a | x) represents the density function that maps actions a to probabilities. 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 Π K (for a finite number of actions K). Each policy within Π K approximates a policy in Π through a smoothing process.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 π 0 , as in:E [Z] = E x∼ν,a∼π0(•|x),c∼p(•|x,a) [Z] .A lot of the results derived in the paper are based on the use of the well known Chernoff Inequality, that we state below for a sum of i.i.d. random variables: Lemma 12 (Chernoff Inequality for a sum of i.i.d. random variables.). Let a ∈ R, n ∈ N * and {X i , i ∈ [n]} a collection of n i.i.d. random variables. The following concentration bounds on the right tail of i∈[n] X i hold for any λ ≥ 0:P   i∈[n] X i > a   ≤ (E [exp (λX 1 )]) n exp(-λa)This result is classical in the literature [23] and we 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 L ≥ 1 and f L be the following function:f L (x) = log(1 + x) - L ℓ=1 (-1) ℓ-1 ℓ x ℓ (-1) L x L+1 .We have that f L is a decreasing function in R + for all L ∈ N * .Proof. Let L ≥ 1 and f L be the following function:f L (x) = log(1 + x) - L ℓ=1 (-1) ℓ-1 ℓ x ℓ (-1) L x L+1.Let x ∈ R + , we have the following identity holding ∀t > 0 and ∀n ≥ 0:EQUATION)Recall the integral form of the log function:log(1 + x) = x 0 1 1 + t dt.We integrate both sides of the Equality (29) and show that the numerator of f L (x) is equal to:log(1 + x) - K k=1 (-1) k-1 k x k = (-1) K x 0 t K 1 + t dt.This result enables us to rewrite the function f L as:f L (x) = 1 x L+1 x 0 t L 1 + t dt.Using the change of variable t = ux, we obtain:f L (x) = 1 0 u L 1 + xu dtwhich is clearly decreasing for in R + . This ends the proof.Finally, we also state the important change of measure lemma:Lemma 14 (Change of measure). Let g be a function of the parameter θ and data D n , for any distribution Q that is P continuous, for any δ ∈ (0, 1], we have with probability 1 -δ :EQUATION)withΨ g = E Dn E θ∼P [e g(θ,Dn) ].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 Ψ g .For any π ∈ Π, let U λ,h L (π) be the upper bound of Proposition 1:U λ,h L (π) = ψ λ Rh n (π) + ln(1/δ) λn + 2L ℓ=2 λ ℓ-1 ℓ Mh,ℓ n (π) .One can observe that the bound U λ,h L depends on three parameters, the regularized IPS function h, the free parameter λ and the moment order L. We choose a dataset (balance-scale) with n = 612, and evaluate a policy π with R(π) = -0.93 to evaluate our bound for different parameters. We fix λ = 1/n and plot the value of U λ,h L for different values of the moment order L ∈ {1, 2, 3, 4, 6, 8, ∞} and for 4 different regularization functions, namely IPS, clipped IPS (M = √ n), Implicit Exploration (IX) (λ = 1/n) and Exponential Smoothing (ES) (α = 1 -1/n). The results are shown in Figure 3 . One can observe from the plot that The decreasing nature of U λ,h L depends on λ and the regularization function h. Indeed, Proposition 2 states that λ < min i∈[n] 1/|h i | implies that the bound is decreasing w.r.t L. Which means that once this condition is not verified, we do not know if the bound will keep decreasing with L. If the bound seems decreasing for CIPS and IX, One can observe that for both IPS and ES, the bound increased from L = 4 to L = 8, but achieved its minimum at L = ∞, with IPS being optimal for this value. This highlights the connection between L, the value of λ and the regularizer h.Recall the form of the Logarithmic Smoothing estimator, defined for any λ ≥ 0:EQUATIONOur estimator Rλ n (π), is defined for a non-negative λ ≥ 0. In particular, λ = 0 recovers the unbiased IPS estimator in (2) and λ > 0 introduces a bias variance trade-off. This estimator can be interpreted as Logarithmic Soft Clipping, and have a similar behavior than Clipping of Bottou et al. [10] . Indeed, 1/λ plays a similar role to the clipping parameter M , as for any i ∈ [n], we have:w π (x i , a i )c i ≪ 1 λ =⇒ - 1 λ log (1 -λw π (x i , a i )c i ) ≈ w π (x i , a i )c i . w π (x i , a i )c i < M =⇒ min (w π (x i , a i ), M ) c i = w π (x i , a i )c i .LS can be seen as a smooth, differentiable version of clipping. We plot the graph of the two functions in Figure 4 . One can observe that once λ > 0, LS exhibits a bias-variance trade-off, with a declining bias with λ → 0. This is different than Clipping as no bias is suffered once M is bigger than the support of w π , this comes however with the price of suffering the full variance of IPS. In the following, we study the bias-variance trade-off that emerges with the new Logarithmic Smoothing estimator. We begin by defining the bias and variance of Rλ n (π):EQUATION)Moreover, for any λ ≥ 0, we define the following quantityEQUATIONthat will be essential in studying the properties of this estimator akin to the coverage ratio used for the IX-estimator [21] . In the following, we study the properties of our estimator Rλ n (π) in ( 14). We start with bounding its mean squared error (MSE), which involves bounding its bias and variance.Proposition (Bias-variance trade-off). Let π ∈ Π and λ ≥ 0. Then we have that 0 ≤ B λ (π) ≤ λS λ (π) , and V λ (π) ≤ S λ (π)/n . Moreover, it holds that for any λ > 0:V λ (π) ≤ |R(π)| nλ ≤ 1 nλ .Proof. Let us start with bounding the bias. We have for any λ ≥ 0:B λ (π) = E Rλ n (π) -R(π) = E - 1 λ log(1 -λw π (x, a)c) -w π (x, a)c (IPS is unbiased).Using log(1 + x) ≤ x for any x ≥ 0 proves that the bias is positive. For its upper bound, we use the following inequality log(1 + x) ≥ x 1+x holding for x ≥ 0:B λ (π) = E - 1 λ log(1 -λw π (x, a)c) -w π (x, a)c ≤ E w π (x, a)c 1 -λw π (x, a)c -w π (x, a)c = λE (w π (x, a)c) 2 1 -λw π (x, a)c = λS λ (π).Now focusing on the variance, we have:V λ (π) = E Rλ n (π) -E Rλ n (π) 2 ≤ 1 nλ 2 E log(1 -λw π (x, a)c) 2 .We use the following inequality log(1 + x) ≤ x/ √ x + 1 holding for x ≥ 0 to obtain our result:V λ (π) ≤ 1 n S λ (π).Notice that once λ > 0, we have:S λ (π) = E w π (x, a) 2 c 2 1 -λw π (x, a)c ≤ 1 λ E [w π (x, a)|c|] = |R(π)| λ ,resulting in a finite variance whenever λ > 0:V λ (π) ≤ |R(π)| nλ ≤ 1 nλ .λ = 0 recovers the IPS estimator in (2), with zero bias and variance bounded by E w 2 (x, a)c 2 /n. When λ > 0, a bias-variance trade-off emerges. The bias is always non-negative as we still recover an estimator that verifies (C1). The bias is capped at λS λ (π), which diminishes to zero when λ is small and goes to |R(π)| as λ increases. Conversely, the variance decreases with a higher λ. Notably, λ > 0 ensures finite variance bounded by 1/λn, despite the estimator being unbounded. This is different from previous regularizations that relied on bounded functions to ensure finite variance.While prior evaluations of 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.Proposition (Sub-Gaussianity). Let π ∈ Π, δ ∈ (0, 1] and λ > 0. Then the following inequalities holds with probability at least 1 -δ:R(π) -Rλ n (π) ≤ ln(2/δ) λn , and Rλ n (π) -R(π) ≤ λS λ (π) + ln(2/δ) λn .In particular, setting λ = λ * = ln(2/δ)/nE [w π (x, a) 2 c 2 ] yields thatEQUATIONProof. Let π ∈ Π, λ > 0 and δ > 0. To prove sub-Gaussianity, we need both upper bounds and lower bounds on R(π) using Rλ n (π). For the upper bound, we can use the bound of Corollary 5, and recall that ψ λ (x) ≤ x for all x. We then obtain with a probability 1 -δ:R(π) ≤ ψ λ Rλ n (π) + ln(1/δ) λn =⇒ R(π) -Rλ n (π) ≤ ln(1/δ) λn .For the lower bound on the risk, we go back to our Chernoff Lemma 12, and use the collection of i.i.d. random variable, that for any i ∈ [n], are defined as:Xi = - 1 λ log (1 -λw π (x i , a i )c i ) .This gives for a ∈ R:P   i∈[n] Xi > a   ≤ E exp λ X1 n exp(-λa) P   i∈[n] Xi > a   ≤ E 1 1 -λw π (x, a)c n exp(-λa)Solving for δ = E P   1 n i∈[n] Xi > 1 λ log E 1 1 -λw π (x, a)c + ln(1/δ) λn   ≤ δThe complementary event holds with at least probability 1 -δ:Rλ n (π) ≤ 1 λ log E 1 1 -λw π (x, a)c + ln(1/δ) λn ,which implies using the inequality log(x) ≤ x -1 for all x > 0:Rλ n (π) -R(π) ≤ 1 λ log E 1 1 -λw π (x, a)c -R(π) + ln(1/δ) λn ≤ 1 λ E 1 1 -λw π (x, a)c -1 -R(π) + ln(1/δ) λn ≤ E w π (x, a)c 1 -λw π (x, a)c -w π (x, a)c + ln(1/δ) λn ≤ λE w π (x, a) 2 c 2 1 -λw π (x, a)c + ln(1/δ) λn = λS λ (π) + ln(1/δ) λn ,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 at least This means that setting λ = λ * = ln(2/δ)/nE [w π (x, a) 2 c 2 ] yields a sub-Gaussian concentration:|R(π) -Rλ * n (π)| ≤ 2 E [w π (x, a) 2 c 2 ] ln(2/δ) n .This ends the proof.From (34) , Rλ * n (π) is sub-Gaussian with variance proxy σ 2 = 2E ω(x, a) 2 c 2 /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σ 2 H = (2+ √ 3) 2 3 E ω(x, a) 2 c 2 /n, giving σ 2 < σ 2H .Let us begin by stating results from the IX work [21] . Recall that the IX estimator is defined for any λ > 0, by:Rλ-IX n (π) = 1 n n i=1 π(a i |x i ) π 0 (a i |x i ) + λ/2 c i .Let Π S = {π 1 , ..., π m } be a finite set of predefined policies. In OPS, the goal is to find π S * ∈ Π S that satisfiesπ S * = argmin π∈ΠS R(π) = argmin k∈[m] R(π k ) .for λ > 0, the selection strategy suggested in Gabbianelli et al. [21] was to search for:EQUATION)Proposition 15 (Suboptimality of the IX selection strategy). Let λ > 0 and δ ∈ (0, 1]. Then, it holds with probability at least 1 -δ thatEQUATIONwhereC λ (π) = E π(a|x) π 2 0 (a|x) + λπ 0 (a|x) |c| .Both suboptimalities (LS and IX) have the same form, they only depend on two different quantities (S λ and C λ respectively). For a π ∈ Π and λ > 0, If we can identify when S λ (π) ≤ C λ/2 (π), then we can prove that the sub-optimality of LS selection strategy is better than the one of IX. Luckily, this is always the case, and it is stated formally below.Proposition 16. Let π ∈ Π and λ > 0. We have:EQUATIONProof. Let π ∈ Π and λ > 0, we have:C λ/2 (π) -S λ (π) = E π(a|x) π 2 0 (a|x) + λ 2 π 0 (a|x) |c| - w π (x, a) 2 c 2 1 -λw π (x, a)c = E π(a|x) π 2 0 (a|x) + λ 2 π 0 (a|x) |c| - π(a|x) 2 c 2 π 2 0 (a|x) -λπ 0 (a|x)π(a|x)c = E π(a|x)|c| 1 π 2 0 (a|x) + λ 2 π 0 (a|x) - π(a|x)|c| π 2 0 (a|x) + λπ 0 (a|x)π(a|x)|c| = E π(a|x)|c| π 2 0 (a|x) (1 -π(a|x)|c|) + λ 2 π 0 (a|x)π(a|x)|c| (π 2 0 (a|x) + λ 2 π 0 (a|x))(π 2 0 (a|x) + λπ 0 (a|x)π(a|x)|c|) ≥ 0.This means that the suboptimality of LS selection strategy is 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 to 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 context x), this estimation minimax sample complexity is proved by Li et al. [34] and is of the rate O(E[w π * (x, a) 2 c 2 ]), with π * being the optimal policy. Our bound matches the lower bound proved by Li et al. [34] , as:S λ (π * ) = E w π * (x, a) 2 c 2 1 -λw π * (x, a)c ≤ E w π * (x, a) 2 c 2 ,which is not the case for the suboptimality of IX, that only matches it in the deterministic setting with binary costs, as:C λ (π * ) = E π * (a|x) π 2 0 (a|x) + λπ 0 (a|x) |c| ≤ E π * (a|x) π 2 0 (a|x) |c| = E π * (a|x) π 0 (a|x) 2 c 2 ,with the last inequality only holding when π * is deterministic and the costs are binary. For deterministic policies and the general contextual bandit, we invite the reader to see a formal proof of the minimax lower bound of pessimism in Jin et al. [28, Theorem 4.4] , matched for both IX and LS.As it is easier to work with linear estimators within the PAC-Bayesian framework, we define the following estimator of the risk Rp-LIN n (π), with the help of a function p : R → R as:Rp-LIN n (π) = 1 n n i=1 π(a i |x i ) p(π 0 (a i |x i )) c iwith the only condition on p to be {C LIN 1 : ∀x, p(x) ≥ x}. This condition helps us control the impact of actions with low probabilities under π 0 . This risk estimator encompasses well known risk estimators depending on 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 our empirical high order bound expressed in the following: Proposition 17 (Empirical High Order PAC-Bayes bound). Let L ≥ 1. Given a prior P on F Θ , δ ∈ (0, 1] and λ > 0, the following bound holds with probability at least 1 -δ uniformly for all distribution Q over F Θ :EQUATIONwith:Mp-LIN,ℓ n (π Q ) = 1 n n i=1 π Q (a i |x i ) p(π 0 (a i |x i )) ℓ c ℓ i ψ λ = x :→ 1 -exp(-λx) λ .Proof. Let L ≥ 1, we have from Lemma 13, and for any positive random variable X ≥ 0 and λ > 0:EQUATION(-1) ℓ-1 ℓ (λX) ℓ (λX) 2Lwhich is equivalent to:2L ℓ=1 (-1) ℓ-1 ℓ (λX) ℓ ≤ log(1 + λX) ⇐⇒ exp 2L ℓ=1 (-1) ℓ-1 ℓ (λX) ℓ ≤ 1 + λX =⇒ E exp 2L ℓ=1 (-1) ℓ-1 ℓ (λX) ℓ ≤ 1 + E [λX] =⇒ E exp 2L ℓ=1 (-1) ℓ-1 ℓ (λX) ℓ ≤ exp (log(1 + E [λX])) ,which implies that:E exp λ(X - 1 λ log(1 + E [λX])) + 2L ℓ=2 (-1) ℓ-1 ℓ (λX) ℓ ≤ 1.For any X ≤ 0, we can inject -X ≥ 0 to obtain:EQUATIONLet:d θ (a|x) = 1 [f θ (x) = a] , ∀(x, a) ∈ X × A ,it means that:π Q (a|x) = E θ∼Q [d θ (a|x)] ,∀(x, a) ∈ X × A .Let λ > 0. The adequate function g we are going to use in combination with Lemma 14 is:g(θ, D n ) = n i=1 λ - 1 λ log(1 + λR p-LIN (d θ )) - d θ (a i |x i ) p(π 0 (a i |x i )) c i - 2L ℓ=2 1 ℓ λ d θ (a i |x i ) p(π 0 (a i |x i )) c i ℓ = n i=1 λ - 1 λ log(1 + λR p-LIN (d θ )) - d θ (a i |x i ) p(π 0 (a i |x i )) c i - 2L ℓ=2 d θ (a i |x i ) ℓ λ p(π 0 (a i |x i )) c i ℓ .By exploiting the i.i.d. nature of the data and exchanging the order of expectations (P is independent of D n ), we can naturally prove using (39) that:Ψ g = E P n i=1 E exp λ - 1 λ log(1 + λR p-LIN (d θ )) -X i (θ) - 2K k=2 1 k (λX i (θ)) k ≤ 1,as we have :X i (θ) = d θ (a i |x i ) p(π 0 (a i |x i )) c i ≤ 0 ∀i.Injecting Ψ g in Lemma 14, rearranging terms and using that Rp-LIN n (π) has positive bias concludes the proof.Similarly to the OPE section, we use this general bound to obtain a PAC-Bayesian Empirical Second Moment bound and the PAC-Bayesian LS-LIN bound. That we state directly below:Empirical second moment bound. With L = 1, we obtain the following:Corollary 18 (Second Moment Upper bound). Given a prior P on F Θ , δ ∈ (0, 1] and λ > 0.The following bound holds with probability at least 1 -δ uniformly for all distribution Q over F Θ :EQUATION)Log Smoothing PAC-Bayesian Bound. With L → ∞, we obtain the following:Proposition 19 ( Rλ-LIN n PAC-Bayes bound). Given a prior P on F Θ , δ ∈ (0, 1] and λ > 0, the following bound holds with probability at least 1 -δ uniformly for all distribution Q over F Θ :EQUATIONwith:Rλ-LIN n (π) = - 1 n n i=1 π(a i |x i ) λ log 1 - λc i π 0 (a i |x i ).Following the same proof schema as of the OPE section, we can demonstrate that the Log Smoothing PAC-Bayesian bound dominates the Empirical Second moment PAC-Bayesian bound L = 1. However, we use the bound of L = 1 as an intermediary to state the dominance of the Log Smoothing PAC-Bayesian bound.Indeed, we can 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 Bernstein bound of Sakhi et al. [49] holding for the (linear) cIPS (p : x → max(x, τ )). For a policy π Q and a λ > 0, we have:R(π Q ) ≤ Rτ n (π Q ) + KL(Q||P ) + ln 4 √ n δ 2n + KL(Q||P ) + ln 2 δ λn + λg (λ/τ ) V τ n (π Q ). R(π Q ) ≤ Rτ n (π Q ) + KL(Q||P ) + ln 1 δ λn + λ 2 Ŝτ n (π Q ). (L = 1)We can observe that the previously derived conditional Bernstein bound has several terms that make it less tight:• It has an additional, strictly positive square root KL divergence term.• The multiplicative factor g(λ/τ ) is always bigger than 1/2, and diverges when τ → 0.• With enough data (n ≫ 1), we also have:Ŝτ n (π Q ) ≈ E π Q (a|x) max{π 0 (a|x), τ } 2 c(a, x) 2 ≤ E π Q (a|x) max{π 0 (a|x), τ } 2 ≈ V τ n (π Q ).These observations confirm that the new bound derived with L = 1 is tighter than what was previously proposed for cIPS, especially when n ≫ 1. As our bound can work for other estimators, we also compare it to a recently proposed PAC-Bayes bound in Aouali et al. [5] for the exponentially-smoothed estimator (p : x → x α ) with α ∈ [0, 1]:R(π Q ) ≤ Rα n (π Q ) + KL(Q||P ) + ln 4 √ n δ 2n + KL(Q||P ) + ln 2 δ λn + λ 2 V α n (π Q ) + Ŝα n (π Q ) . R(π Q ) ≤ Rα n (π Q ) + KL(Q||P ) + ln 1 δ λn + λ 2 Ŝα n (π Q ). (L = 1)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. In addition, computing our bound does not rely on expectations under π 0 (contrary to the previous bounds that have V n ) which alleviates the need to access the logging policy and reduce the computations.This demonstrates the superiority of L = 1 compared to existing variance sensitive PAC-Bayesian bounds. It means that L → ∞ 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) ≥ x 1+x/2 for all x ≥ 0, we have for any P, Q ∈ P(Θ) and λ > 0:ψ λ Rλ-LIN n (π Q ) + KL(Q||P ) + ln 1 δ λn ≤ Rλ-LIN n (π Q ) + KL(Q||P ) + ln 1 δ λn ≤ - 1 n n i=1 π Q (a i |x i ) λ log 1 - λc i π 0 (a i |x i ) + KL(Q||P ) + ln 1 δ λn ≤ 1 n n i=1 π Q (a i |x i ) π 0 (a i |x i ) -λc i /2 + KL(Q||P ) + ln 1 δ λn ≤ Rλ-IX n (π Q ) + KL(Q||P ) + ln 1 δ λn , (IX-bound)with the last implication leveraging that the cost is always bigger than -1/ This proves that our bound is better than the IX bound. This means that our PAC-Bayesian bound is better than all existing PAC-Bayesian off-policy learning bounds.Let us begin by stating results from the IX work [21] . Recall that the IX estimator is defined for any λ > 0, by:RIX-λ n (π) = 1 n n i=1 π(a i |x i ) π 0 (a i |x i ) + λ/2 c i ,and that we used the linearized version of the LS estimator, LS-LIN defined as:Rλ-LIN n (π) = - 1 n n i=1 π(a i |x i ) λ log 1 - λc i π 0 (a i |x i ) .Let Θ be a parameter space and P(Θ) be the set of all probability distribution on Θ. Our goal is to find the best policy in a chosen class L(Θ) ⊂ P(Θ):π Q * = argmin Q∈L(Θ) R(π Q ).For λ > 0 and a prior P ∈ P(Θ), the PAC-Bayesian learning strategy suggested in Gabbianelli et al. [21] is to find in L(Θ) ⊂ P(Θ):πIX Qn = argmin Q∈L(Θ) RIX-λ n (π Q ) + KL(Q||P ) λn .This learning strategy suffers from a suboptimality bounded in the result below:Proposition 20 (Suboptimality of the IX PAC-Bayesian learning strategy from [21] ). Let λ > 0 and δ ∈ (0, 1]. Then, it holds with probability at least 1 -δ that0 ≤ R(π IX Qn ) -R(π Q * ) ≤ λC λ/2 (π Q * ) + 2 (KL(Q * ||P ) + ln(2/δ)) λn ,whereC λ (π) = E π(a|x) π 2 0 (a|x) + λπ 0 (a|x)|c| .Similarly for PAC-Bayesian learning, both suboptimalities (LS and IX) have the same form, they only depend on two different quantities (S LIN λ and C λ respectively). For a π ∈ Π and λ > 0, If we can identify when S LIN λ (π) ≤ C λ/2 (π), then we can prove that the sub-optimality of LS PAC-Bayesian learning strategy is better than the one of IX in certain cases. Luckily, this is always the case, and it is stated formally below.Proposition 21. Let π ∈ Π and λ > 0. We have:EQUATIONProof. Let π ∈ Π and λ > 0, and recall that:S LIN λ (π) = E π(a|x)c 2 π 2 0 (a|x) -λπ 0 (a|x)c.We have:C λ/2 (π) -S LIN λ (π) = E π(a|x) π 2 0 (a|x) + λ 2 π 0 (a|x) |c| - π(a|x)c 2 π 2 0 (a|x) -λπ 0 (a|x)c = E π(a|x)|c| 1 π 2 0 (a|x) + λ 2 π 0 (a|x) - |c| π 2 0 (a|x) + λπ 0 (a|x)|c| = E π(a|x)|c| π 2 0 (a|x) (1 -|c|) + λ 2 π 0 (a|x)|c| (π 2 0 (a|x) + λ 2 π 0 (a|x))(π 2 0 (a|x) + λπ 0 (a|x)|c|) ≥ 0.Similarly, this means that the suboptimality of LS-LIN 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, in the case of deterministic optimal policies is of the rate O(1/ √ nC * ) with inf x∈X π 0 (π * (x)|x) > C * . Our bound as well as IX bound match this minimax lower bound, as:S LIN λ (π * ) = E x,c c 2 π 0 (π * (x)|x) -λc ≤ 1 C * C λ (π * ) = E x,c |c| π 0 (π * (x)|x) + λ ≤ 1 C * .One can see that for both, selecting aλ * = 2 (KL(Q * ||P ) + ln(2/δ)) C * n ,gets you the desired bound, matching this minimax rate.F.1 Proof of high order empirical moments bound (Proposition 1)Proposition (Empirical moments risk bound). Let π ∈ Π, L ≥ 1, δ ∈ (0, 1], λ > 0 and h satisfying (C1). Then it holds with probability at least 1 -δ thatR(π) ≤ ψ λ Rh n (π) + 2L ℓ=2 λ ℓ-1 ℓ Mh,ℓ n (π) + ln(1/δ) λn ,where ψ λ and Mh,ℓ n (π) are defined in (5) , respectively, and recall that ψ λ (x) ≤ x.Proof. Let L ∈ N * , λ > 0 and X ≥ 0 a positive random variable. We have 2L -1 ≥ 1, and with the decreasing nature of f (2L-1) (Lemma 13), we also have:EQUATION(-1) ℓ-1 k (λX) ℓ (λX) 2L ⇐⇒ 2L ℓ=1 (-1) ℓ-1 k (λX) ℓ ≤ log(1 + λX) ⇐⇒ exp 2L ℓ=1 (-1) ℓ-1 ℓ (λX) ℓ ≤ 1 + λX =⇒ E exp 2L ℓ=1 (-1) ℓ-1 ℓ (λX) ℓ ≤ 1 + λE [X] =⇒ E exp 2L ℓ=1 (-1) ℓ-1 ℓ (λX) ℓ ≤ exp ((log(1 + λE [X])) =⇒ E exp λ(X - 1 λ log (1 + λE [X])) + 2L ℓ=2 (-1) ℓ-1 ℓ (λX) ℓ ≤ 1.For any X ≤ 0, we can inject -X ≥ 0 to obtain:EQUATION)The result in Equation ( 43) will be combined with Chernoff Inequality (Lemma 12) to finally prove our bound. Let λ > 0, for our problem, we define the random variable X i to use in the Chernoff Inequality as:X i = - 1 λ log (1 -λE [h]) -h i - 2L ℓ=2 1 ℓ (λh i ) ℓ .For any a ∈ R, this gives us the following: 43))P   i∈[n] X i > a   ≤ (E [exp (λX 1 )]) n exp(-λa) P   - n λ log (1 -λE [h]) - i∈[n] h i + 2L ℓ=2 1 ℓ (λh i ) ℓ > a   ≤ (E [exp (λX 1 )]) n exp(-λa) P   - n λ log (1 -λE [h]) - i∈[n] h i + 2L ℓ=2 1 ℓ (λh i ) ℓ > a   ≤ exp(-λa) (Use of Equation (Solving for δ = exp(-λa), we get:P   - n λ log (1 -λE [h]) - i∈[n] h i + 2L ℓ=2 1 ℓ (λh i ) ℓ > ln(1/δ) λ   ≤ δ P   - 1 λ log (1 -λE [h]) - 1 n i∈[n] h i + 2L ℓ=2 λ ℓ ℓ h ℓ i > ln(1/δ) λn   ≤ δ P - 1 λ log (1 -λE [h]) -Rh n (π) - 2L ℓ=2 λ ℓ-1 ℓ Mh,ℓ n (π) > ln(1/δ) λn ≤ δ P - 1 λ log (1 -λE [h]) > Rh n (π) + 2L ℓ=2 λ ℓ-1 ℓ Mh,ℓ n (π) ln(1/δ) λn ≤ δ.This means that the following, complementary event will hold with probability at least 1 -δ:- 1 λ log (1 -λE [h]) ≤ Rh n (π) + 2L ℓ=2 λ ℓ-1 ℓ Mh,ℓ n (π) ln(1/δ) λn .ψ λ being a non-decreasing function, applying it to the two sides of this inequality gives us:E [h] ≤ ψ λ Rh n (π) + 2L ℓ=2 λ ℓ-1 ℓ Mh,ℓ n (π) + ln(1/δ) λn .Finally, h satisfies (C1), this means that the bound is also an upper bound on the true risk, giving:R(π) ≤ ψ λ Rh n (π) + 2L ℓ=2 λ ℓ-1 ℓ Mh,ℓ n (π) + ln(1/δ) λn ,which concludes the proof.F.2 Proof of the impact of L on the bound's tightness (Proposition 2)Proposition (Impact of L on the bound's tightness). Let π ∈ Π, δ ∈ (0, 1], λ > 0, L ≥ 1 and h satisfying (C1). LetU λ,h L (π) = ψ λ Rh n (π) + ln(1/δ) λn + 2L ℓ=2 λ ℓ-1 ℓ Mh,ℓ n (π)be the upper bound in Equation (6) . Then,EQUATION)which implies that:λ ≤ min i∈[n] 1 |h i | =⇒ U λ,h L (π) is a decreasing function w.r.t L.Proof. We want to 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:λ ≤ min i∈[n] 1 |h i | =⇒ ∀L ≥ 1, λ ≤ min i∈[n] 2L + 2 (2L + 1)|h i | =⇒ ∀L ≥ 1, U λ,h L+1 (π) ≤ U λ,h L (π) (Using (44)) =⇒ U λ,hL (π) is a decreasing function w.r.t L. Now let us prove the implication in (44) . We have for any L ≥ 1:U λ,h L+1 (π) ≤ U λ,h L (π) ⇐⇒ 2L+2 ℓ=2L+1 λ ℓ-1 ℓ Mh,ℓ n (π) ≤ 0 ⇐⇒ λ 2L n n i=1 h 2L+1 i 1 2L + 1 + λh i 2L + 2 ≤ 0As h i ≤ 0, we can ensure this inequality by choosing a λ that verifies:∀i ∈ [n], λ ≤ 2L + 2 (2L + 1)|h i | ⇐⇒ λ ≤ min i∈[n]2L + 2 (2L + 1)|h i | which concludes the proof.We compare the bounds evaluated in their optimal regularisation function h. We start by stating the proposition and proving it.Proposition. Let π ∈ Π, and λ > 0, we define:U λ L (π) = min h U λ,h L (π).Then, for any λ > 0, it holds that for any L > 1:EQUATIONProof. Let π ∈ Π, λ > 0 andU λ L (π) = min h U λ,h L (π).We can prove (see Appendix F.4) that:U λ 1 (π) = U λ,h * ,1 1 (π) = ψ λ Rh * ,1 n (π) + λ 2 Mh * ,1,2 n (π) + ln(1/δ) λn with: h * ,1 (p, q, c) = -min(|c|p/q, 1/λ),and that (see Appendix F.7):U λ ∞ (π) = ψ λ Rλ n (π) + ln(1/δ) λn .From Proposition 2, we have that for any h:λ ≤ min i∈[n] 1 |h i | =⇒ U λ,h L (π) is a decreasing function w.r.t L.It appears that the optimal function h * ,1 respects this condition, as by definition:min i∈[n] 1 |(h * ,1 ) i | ≥ λ, meaning that: U λ,h * ,1 L (π) is a decreasing function w.r.t L.This result suggests that the Empirical Second Moment bound, evaluated in its optimal function h * ,1 , is always bigger than bounds with additional moments (evaluated in the same h * ,1 ). This leads us to the result wanted, as for any L > 1:U λ L (π) = min h U λ,h L (π) ≤ U λ,h * ,1 L (π) ≤ U λ,h * ,1 1 (π) = U λ 1 (π).In particular, we get:U λ ∞ (π) ≤ U λ 1 (π), which ends the proof.This means that U λ ∞ is tighter than U λ 1 , and thus can also be tighter than empirical Bernstein.Proposition (Optimal h for L = 1). Let λ > 0. The function h that minimizes the bound for L = 1, giving the tightest result is:∀i, h i = h(π(a i |x i ), π 0 (a i |x i ), c i )) = -min π(a i |x i ) π 0 (a i |x i ) |c i |, 1 λThis means that when the costs are binary, we obtain the classical Clipping estimator of parameter 1/λ:h i = min π(a i |x i ) π 0 (a i |x i ) , 1 λ c i .Proof. We want to look for the value of h that minimizes the bound. Formally, by fixing all variables of the bound, this problem reduces to:argmin h∈(C1) Rh n (π) + λ 2 Mh,2 n (π) = argmin h∈(C1) 1 n n i=1 h i + λ 2 h 2 i .The objective decomposes across data points, so we can solve it for every h i independently. Let us fix a j ∈ [n], the following problem:argmin hj ∈R Rh n (π) + λ 2 Mh,2 n (π) = argmin hj ∈R h j + λ 2 h 2 j subject to h j ≥ π(a j |x j ) π 0 (a j |x j ) c jis strongly convex in h j . We write the KKT conditions for h j to be optimal; there exists α * that verifies:EQUATIONEQUATIONEQUATIONWe study the two following two cases:Case 1: h j ≤ -1 λ : we have α * = 1 + λh j ≤ 0 =⇒ α * = 0, meaning that:h j = - 1 λCase 2: h j > -1 λ : we have α * = 1 + λh j > 0, which combined to condition (36) gives:h j = π(a j |x j ) π 0 (a j |x j ) c j .The two results combined mean that we always have:h j ≥ - 1 λ, and wheneverh j > - 1 λ =⇒ h j = π(a j |x j ) π 0 (a j |x j ) c j .We deduce that h j has the following form:EQUATIONEQUATIONThese values verify the KKT conditions. As the problem is strongly convex, h j has a unique possible value and must be equal to equation (38) . The form of h j is a global clipping that includes the cost in the function as well. In the case where the cost function c is binary:∀i c i ∈ {-1, 0},we recover the classical Clipping with parameter 1/λ as an optimal solution for h:h j = min π(a j |x j ) π 0 (a j |x j ) , 1 λ c j .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 a parameter M > 0:RM n (π) = 1 n n i=1 min π(a i |x i ) π 0 (a i |x i ) , M c i .We also give below the Empirical Bernstein Bound applied to this estimator:Proposition (Empirical Bernstein for Clipping of [55] ). Let π ∈ Π, δ ∈ (0, 1] and M > 0.Then it holds with probability at least 1 -δ thatEQUATIONwith V M n (π) the empirical variance of the clipping estimator.We are usually interested in the case where π and π 0 are different, leading to substantial importance weights. In this practical scenario, the variance and the second moment are of the same magnitude of M . Indeed, one can see it from the following equality:V M n (π) O(M ) = MM,2 n (π) O(M ) -RM n (π) 2 O(c 2 ) ≈ MM,2 n (π) O(M ) (M ≫ c2 = o(1).)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 (C1), we give the Second Moment Upper of Corollary 4 with Clipping below:ψ λ RM n (π) + λ 2 MM,2 n (π) + ln(1/δ) λn ≤ RM n (π) + λ 2 MM,2 n (π) + ln(1/δ) λn (ψ λ (x) ≤ x, ∀x) ≤ RM n (π) + λ 2 MM,2 n (π) + ln(1/δ) λn .Choosing a λ ≈ 2 ln(1/δ)/(n MM,2 n (π)) gives us an upper bound that is close to:RM n (π) + λ 2 MM,2 n (π) + ln(1/δ) λn ≈ RM n (π) + 2 MM,2 n (π) ln(1/δ) n ≈ RM n (π) + 2 V M n (π) ln(1/δ) n ≤ RM n (π) + 2 V M n (π) ln(2/δ) n + 7M ln(2/δ) 3(n -1) . F.6 Proof of the L → ∞ bound (Corollary 5)Proposition (Empirical Logarithmic Smoothing bound with L → ∞). Let π ∈ Π, δ ∈ (0, 1] and λ > 0. Then it holds with probability at least 1 -δ thatR(π) ≤ ψ λ - 1 n n i=1 1 λ log (1 -λh i ) + ln(1/δ) λn .Taking the limit of L naively recovers this form of the bound, but imposes a condition on λ for the bound to converge. We instead, take another path of proof that does not impose any condition on λ, 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:X i = - 1 λ log (1 -λE [h]) -h i - 2L ℓ=2 1 ℓ (λh i ) ℓ ,combined with Chernoff Inequality (Lemma 12) to prove our bound. If we take the limit L → ∞ for our random variable, we obtain the following random variable:Xi = - 1 λ log (1 -λE [h]) + 1 λ log (1 -λh i ) = 1 λ log 1 -λh i 1 -λE [h].We use the random variable Xi with the Chernoff Inequality. For any a ∈ R, we have:P   i∈[n] Xi > a   ≤ E exp λ X1 n exp(-λa) P   - n λ log (1 -λE [h]) + i∈[n] 1 λ log (1 -λh i ) > a   ≤ E exp λ X1 n exp(-λa)On the other hand, we have:E exp λ X1 = E [1 -λh i ] 1 -λE [h] = 1.Using this equality and solving for δ = exp(-λa), we get:P   - n λ log (1 -λE [h]) + i∈[n] 1 λ log (1 -λh i ) > ln(1/δ) λ   ≤ δ P   - 1 λ log (1 -λE [h]) + 1 n i∈[n] 1 λ log (1 -λh i ) > ln(1/δ) λn   ≤ δThis means that the following, complementary event will hold with probability at least 1 -δ:- 1 λ log (1 -λE [h]) ≤ - 1 n n i=1 1 λ log (1 -λh i ) + ln(1/δ) λn .ψ λ being a non-decreasing function, applying it to the two sides of this inequality gives us:E [h] ≤ ψ λ - 1 n n i=1 1 λ log (1 -λh i ) + ln(1/δ) λn .As h satisfies (C1), we obtain the required inequality:R(π) ≤ ψ λ - 1 n n i=1 1 λ log (1 -λh i ) + ln(1/δ) λn .and conclude the proof.Proposition (Optimal h for L → ∞). Let λ > 0. The function h that minimizes the bound for L → ∞, giving the tightest result is:∀i, h i = h(π(a i |x i ), π 0 (a i |x i ), c i )) = π(a i |x i ) π 0 (a i |x i ) c iProof. The proof of this proposition is quite simple. The function:f (x) = -log (1 -λx)is increasing. This means that the lowest possible value of h i ensures the tightest result. As our variables h i verifies (C1), we recover IPS as an optimal choice for this bound.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 [21] ). Let π ∈ Π, δ ∈]0, 1] and λ > 0, the IX bound from [21] states that we have with at least probability 1 -δ:EQUATIONwith:Rλ-IX n (π) = 1 n n i=1 π(a i |x i ) π 0 (a i |x i ) + λ/2 c i .Let U λ IX (π) be the IX upper bound defined above, we have for any λ > 0:EQUATIONProof. Let π ∈ Π, δ ∈]0, 1] and λ > 0. Recall that U λ ∞ (π) = ψ λ Rλ n (π) + ln(1/δ) λn . We have:ψ λ Rλ n (π) + ln(1/δ) λn ≤ Rλ n (π) + ln(1/δ) λn (∀x, ψ λ (x) ≤ x) ≤ - 1 n n i=1 1 λ log (1 -λw π (x i , a i )c i ) + ln(1/δ) λn .Using the inequality log(1 + x) ≥ x 1+x/2 for all x > 0, we get:U λ ∞ (π) ≤ - 1 n n i=1 1 λ log (1 -λw π (x i , a i )c i ) + ln(1/δ) λn ≤ 1 n n i=1 w π (x i , a i ) 1 -λw π (x i , a i )c i /2 c i + ln(1/δ) λn log(1 + x) ≥ x 1 + x/2 ≤ 1 n n i=1 π(a i |x i ) π 0 (a i |x i ) -λπ(a i |x i )c i /2 c i + ln(1/δ) λn ≤ 1 n n i=1 π(a i |x i ) π 0 (a i |x i ) + λ/2 c i + ln(1/δ) λn (-π(a i |x i )c i ≤ 1 and c i ≤ 0) ≤ RIX-λ n (π) + ln(1/δ) λn = U λ IX (π), which ends the proof.The result states the dominance of the LS bound compared to IX. The proof of this result also gives us insight on when the LS bound will be much tighter than IX. Indeed, to obtain the IX bound, LS bound is loosened through 3 steps:1. The use of ψ λ (x) ≤ x, ∀x.G.1 OPS: Proof of suboptimality bound (Proposition 9) Proposition (Suboptimality of our selection strategy in (20) ). Let λ > 0 and δ ∈ (0, 1]. Then, it holds with probability at least 1 -δ that0 ≤ R(π S n ) -R(π S * ) ≤ λS λ (π S * ) + 2 ln(2|Π S |/δ) λn ,where π S * and πS n are defined in (19) and (20) , andS λ (π) = E (w π (x, a)c) 2 / (1 -λw π (x, a)c) .In addition, our upper bound is always finite as:λS λ (π) = λE (w π (x, a)c) 2 1 -λw π (x, a)c ≤ min |R(π)|, λE (w π (x, a)c) 2 ≤ |R(π)|.Proof. To prove this bound on the suboptimality of our selection method, we need both an upper bound and a lower bound on the true risk using the LS estimator. Luckily, we already have derived them in ?? . For a fixed λ, taking a union of the two bounds over the cardinal of the finite policy class |Π s |, we get the following holding with probability at least 1 -δ for all π ∈ Π s :EQUATIONRλ n (π) -R(π) ≤ λS λ (π) + ln(2|Π s |/δ) λn .As πS n ∈ Π s and by definition of πS n (minimizer of Rλ n (π)), we have:R(π S n ) ≤ Rλ n (π S n ) + ln(2|Π s |/δ) λn ≤ Rλ n (π S * ) + ln(2|Π s |/δ) λn .Using the lower bound on the risk of R(π S * ), we have:R(π S n ) ≤ Rλ n (π S * ) + ln(2|Π s |/δ) λn ≤ R(π S * ) + λS λ (π S * ) + 2 ln(2|Π s |/δ) λn .which gives us the suboptimality upper bound:0 ≤ R(π S n ) -R(π S * ) ≤ λS λ (π S * ) + 2 ln(2|Π S |/δ) λn .Note that: ). Given a prior P ∈ P(Θ), δ ∈ (0, 1] and λ > 0, the following holds with probability at least 1 -δ:λS λ (π) = λE (w π (x, a)c) 2 1 -λw π (x,∀Q ∈ P(Θ), R(π Q ) ≤ ψ λ Rλ-LIN n (π Q ) + KL(Q||P ) + ln 1 δ λn Proof.To prove this proposition, we can either take the path of High Order Empirical moments as for Pessimistic OPE, or we can prove it directly. We provide here a simple proof of this proposition using ideas from Alquier [1, Corollary 2.5]. Let:EQUATIONit means that:π Q (a|x) = E θ∼Q [d θ (a|x)] ,∀(x, a) ∈ X × A .Recall that to prove a PAC-Bayesian generalization bound, one can rely on the Change of measure Lemma (Lemma 14). For any λ > 0, the adequate function g to consider is:g(θ, D n ) = n i=1 -log(1 -λR(d θ )) + log 1 -λ d θ (a i |x i )c i π 0 (a i |x i ) = n i=1 log   1 -λ d θ (ai|xi)ci π0(ai|xi) 1 -λR(d θ )   .By exploiting the i.i.d. nature of the data and exchanging the order of expectations (P is independent of D n ), we can naturally prove that:Ψ g = E P   n i=1 E   exp   log   1 -λ d θ (ai|xi)ci π0(ai|xi) 1 -λR(d θ )         = E P   n i=1 E   1 -λ d θ (ai|xi)ci π0(ai|xi) 1 -λR(d θ )     = E P n i=1 1 -λR(d θ ) 1 -λR(d θ ) = 1.Injecting Ψ g in Lemma 14, gives:E θ∼Q [-log(1 -λR(d θ )] ≤ 1 n n i=1 E θ∼Q -log 1 -λ d θ (a i |x i )c i π 0 (a i |x i ) + KL(Q||P ) + ln 1 δ n ≤ 1 n n i=1 E θ∼Q -d θ (a i |x i ) log 1 -λ c i π 0 (a i |x i ) + KL(Q||P ) + ln 1 δ n ≤ - 1 n n i=1 π Q (a i |x i ) log 1 -λ c i π 0 (a i |x i ) + KL(Q||P ) + ln 1 δ n ≤ λ Rλ-LIN n (π Q ) + KL(Q||P ) + ln 1 δ n .From the convexity of x → -log(1 + x), we have:- 1 λ log (1 -λR(π Q )) ≤ 1 λ E θ∼Q [-log(1 -λR(d θ )] ≤ Rλ-LIN n (π Q ) + KL(Q||P ) + ln 1 δ λn .Applying the increasing function ψ λ of Equation ( 5) to both sides concludes the proof.G.3 OPL: Proof of PAC-Bayesian suboptimality bound (Proposition 11)Proposition (Suboptimality of the learning strategy in ( 27)). Let λ > 0, P ∈ L(Θ) and δ ∈ (0, 1]. Then, it holds with probability at least 1 -δ that0 ≤ R(π Qn ) -R(π Q * ) ≤ λS LIN λ (π Q * ) + 2 (KL(Q * ||P ) + ln(2/δ)) λn ,whereS LIN λ (π) = E π(a|x)c 2 π 2 0 (a|x) -λπ 0 (a|x)c.In addition, our upper bound is always finite as:λS LIN λ (π) ≤ min |R(π)|, λE π(a|x)c 2 π 2 0 (a|x) ≤ |R(π)|.Proof. To prove this bound on the suboptimality of our learning strategy, we need both a PAC-Bayesian upper bound and a lower bound on the true risk using the LS-LIN estimator. Luckily, we already have derived an upper bound in Proposition 10, that we linearize here as ψ λ (x) ≤ x:∀Q ∈ P(Θ), R(π Q ) ≤ Rλ-LIN n (π Q ) + KL(Q||P ) + ln 1 δ λn .For the lower bound, we rely a second time on the Change of measure Lemma (Lemma 14). For any λ > 0, we choose the following function g:g(θ, D n ) = n i=1 - 1 λ log 1 -λ d θ (a i |x i )c i π 0 (a i |x i ) -R(d θ ) -λS LIN λ (d θ ) .By exploiting the i.i.d. nature of the data and exchanging the order of expectations (P is independent of D n ), we can prove that:Ψ g = E P   n i=1   exp -λ(R(d θ ) + λS LIN λ (d θ )) E   1 1 -λ d θ (a|x)c π0(a|x)       ≤ E P   n i=1   exp   -λ(R(d θ ) + λS LIN λ (d θ )) + E   1 1 -λ d θ (a|x)c π0(a|x)   -1       ≤ E P n i=1 exp -λ(R(d θ ) + λS LIN λ (d θ )) + E λd θ (a|x)c π 0 (a|x) -λd θ (a|x)c ≤ E P n i=1 exp -λ(R(d θ ) + λS LIN λ (d θ )) + E λd θ (a|x)c π 0 (a|x) -λc (d θ is binary.) ≤ E P n i=1 exp -λ 2 S LIN λ (d θ ) + E λd θ (a|x)c π 0 (a|x) -λc -λ d θ (a|x)c π 0 (a|x) ≤ E P n i=1 exp -λ 2 S LIN λ (d θ ) + λ 2 S LIN λ (d θ ) ≤ 1,giving by rearranging terms, the following PAC-Bayesian bound:∀Q ∈ P(Θ), Rλ-LIN n (π Q ) ≤ R(π Q ) + λS LIN λ (π Q ) + KL(Q||P ) + ln(2/δ) λn .Now we take a union of the the two bounds, for them to hold with probability at least 1 -δ for all Q. By definition of πQn (minimizer of the upper bound), we have:R(π Qn ) ≤ Rλ-LIN n (π Qn ) + KL(Q n ||P ) + ln(2/δ) λn ≤ Rλ-LIN n (π Q * ) + KL(Q * ||P ) + ln(2/δ) λn .Using the lower bound on the risk of R(π Q * ), we have:R(π Qn ) ≤ Rλ-LIN n (π Q * ) + KL(Q * ||P ) + ln(2/δ) λn ≤ R(π Q * ) + λS LIN λ (π Q * ) + KL(Q * ||P ) + ln(2/δ) λn .which gives us the PAC-Bayesian suboptimality upper bound:0 ≤ R(π Qn ) -R(π Q * ) ≤ λS LIN λ (π Q * ) + 2 (KL(Q * ||P ) + ln(2/δ)) λn .Concluding the proof.All our experiments were conducted on a machine with 16 CPUs. The PAC-Bayesian learning experiments require a moderate amount of computation due to the handling of medium-sized datasets. However, our experiments remain reproducible with minimal computational resources.H.1 Off-policy evaluation and selectionFor 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 . Additional details. For these experiments, as we only use oracle policies (faulty policies to log data and we evaluate ideal policies), we use the full 11 datasets without splitting them. The faulty policies are defined exactly as described in the experiments of Kuzborskij et al. [32] . For each datapoint, the behavior (faulty) policy plays an action and we record a cost. The triplets datapoint, action and cost constitute our logged bandit dataset, with which we can compute our estimates and bounds. As we have access to the true label, the original dataset can be used to compute the true risk of any policy.Detailed results. Evaluating the worst case performance of a policy is 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 a small relative radius |U (π)/R(π)-1|. We compare our newly derived bounds (cIPS-L=1 for U λ 1 and LS for U λ ∞ both with λ = 1/ √ n) to 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 (τ 0 ∈ {0.2, 0.25, 0.3}) and different noise levels (ϵ ∈ {0., 0.1, 0.2}) to evaluate ideal policies with different temperatures (τ ∈ {0.1, 0.2, 0.3, 0.4, 0.5}), defining ∼ 500 different scenarios to 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 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 . Policy selection aims at identifying the best policy among a set of finite candidates. In practice, we are interested in finding policies that improve on π 0 and avoid policies that perform worse than π 0 . To replicate real world scenarios, we design an experiment where π 0 is a faulty policy (τ = 0.2), that collects noisy (ϵ = 0.2) interaction data, some of which is used to learn π θ IPS , π θ SN , and that we add to our discrete set of policies Π k=4 = {π 0 , π ideal , π θ IPS , π θ SN }. The splits for these experiments are the following: 70% of the data is used to create bandit feedback (20% is used to train π θ IPS , π θ SN and 50% is used to evaluate policies based on estimators/upper bounds.) the rest is used to evaluate the true value of the policies. The goal is to measure the ability of our selection strategies to choose from Π k=4 , better performing policies than π 0 . 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 to the commonly used estimators IPS and SNIPS. The hyperparameters of all bounds (the clipping parameter M and λ) are set to 1/ √ n. The comparison is conducted on the 11 datasets with 10 different seeds resulting in 110 scenarios. In addition to the plot in Figure 2 , we collect the number of times each method selected the best policy (π S * ), a better (B) or a worse (W) policy than π 0 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 π 0 , 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 of 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. 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 l (of size n l ) to train the logging policy π 0 , another split D c (of size n c ) to generate the logging feedback with π 0 , and finally a test split D test (of size n test ) to compute the true risk R(π) of any policy π. In our experiments, we split the training split D train (of size N ) of the four datasets considered into D l (n l = 0.05N ) and D c (n c = 0.95N ) and use their test split D test . The detailed statistics of the different splits can be found in Table 7 . Recall that K is the number of actions and p the number of features. In the PAC-Bayesian Learning paradigm, we are interested in the definition of policies as mixtures of decision rules:EQUATIONWe use the Linear Gaussian Policy of Sakhi et al. [49] . To obtain these policies, we restrict f θ to:EQUATIONThis results in a parameter θ of dimension d = p × K with p the dimension of the features ϕ(x) and K the number of actions. We also restrict the family of distributionsQ d+1 = {Q µ,σ = N (µ, σ 2 I d ), µ ∈ R d , σ > 0}to independent Gaussians with shared scale. Estimating the propensity of a given x reduces the computation to a one dimensional integral:π µ,σ (a|x) = E ϵ∼N (0,1)   a ′ ̸ =a Φ ϵ + ϕ(x) T (µ a -µ a ′ ) σ||ϕ(x)||  with Φ the cumulative distribution function of the standard normal.Contrary to previous work, our method does not require tuning any loss function hyperparameter over a hold out set. We do however need to choose parameters to optimize the policies.The logging policy π 0 . π 0 is trained on D l (supervised manner) with the following parameters:We use L 2 regularization of 10 -4 . This is used to prevent the logging policy π 0 from being close to deterministic, allowing efficient learning with importance sampling. We use Adam [30] with a learning rate of 10 -1 for 10 epochs.Parameters of the bounds. cIPS and cvcIPS: The clipping parameter τ is fixed to 1/K with K the action size of the dataset and cvcIPS is used with ξ = -0.5 (the values used in Sakhi et al. [49] ). ES: The exponential smoothing parameter α is fixed to 1 -1/K.Optimizing the bounds. We use Adam [30] with a learning rate of 10 -3 for 100 epochs. The gradient of LIG policies is a one dimensional integral, and is approximated using S = 32 samples.π µ,σ (a|x) = E ϵ∼N (0,1)   a ′ ̸ =a Φ ϵ + ϕ(x) T (µ a -µ a ′ ) σ||ϕ(x)||   ≈ 1 S S s=1 a ′ ̸ =a Φ ϵ s + ϕ(x) T (µ a -µ a ′ ) σ||ϕ(x)|| ϵ 1 , ..., ϵ S ∼ N (0, 1).For all bounds, instead of fixing λ, we take a union bound over a discretized space of possible parameters Λ of size n Λ = 100 and for each iteration j of the optimization procedure, we take λ j ∈ Λ that minimizes the estimated bound and proceed to compute the gradient w.r.t µ and σ with λ j .In addition to the results of Table 2 , we also provide a more detailed view of the results here. For each α and dataset, we average both {GR, R} over the 10 seeds and plot them in Figure 6 and Figure 5 . Note that the error bars are too small σ/ √ 10 ≈ 0.001 and all our results in these graphs are significant. We observe that the LS PAC-Bayesian bound improves substantially on its competitors in 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. 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 NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Here, optimality of a function h is defined with respect to our bound with L = 1 (Corollary 4).The code can be found at https://github.com/otmhi/offpolicy_ls.This means that in practical scenarios, and with a good choice of λ ∼ O(1/ √ n), 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 in practice. This also confirms that the Logarithmic smoothing bound is even tighter, because it is smaller than the Second Moment bound as stated in Proposition 3. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Can you explain why you did not follow the protocol and reported values of [31]?
limitations: limitations: na
paper_summary: paper_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.
strength_weakness: strength_weakness: - **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.

- **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.

(Metelli et al. 2021) Subgaussian and Differentiable Importance Sampling for Off-Policy Evaluation and Learning. Alberto Maria Metelli, Alessio Russo, Marcello Restelli. NeurIPS, 2021.

(Su et al. 2020) Doubly robust off-policy evaluation with shrinkage. Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, Miroslav Dudík. ICML, 2020.
questions: questions: - What are the connections with Metelli et al. 2021? (See weaknesses for the detailed comments.)

- 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: limitations: Missing connection with a similar idea. See the weaknesses for the details.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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). 

Since 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. 

For example, I would have liked to see a discussion on (possibly even in graphs): 
- 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? 
- Is $h*$ (the tightest choice) better than all of the above? 
- Does this hold for all hyperparameter choices, e.g. $\lambda$ and $L$?
- How does the computational complexity of calculating the bounds in Prop 1, Cor 3, Cor 4 hold up relative to their competitors? 
- Exactly how does this lead to downstream policy learning improvements?

Lastly, I found the overall technical presentation to be relatively poor, and I'll give a few examples: 
- 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.  
- Shouldn't (11) be framed in, e.g., a lemma environment? 
- 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).
questions: 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?


**References**

Wang, 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.

Xie, 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: limitations: I do not believe the authors have fully discussed the limitations of their method (see "Weaknesses").
paper_summary: paper_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.
The 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.
strength_weakness: strength_weakness: 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.

2. 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?

3. Performance seems very close to that of IX

4. 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?

5. 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)

Typo:
line 98: one of the brackets is reversed in the definition of h
questions: questions: See above.
limitations: limitations: N/a

Comments: title: Response
comment: Thank you for your feedback. However, we strongly disagree with the reviewer's assessment. The comment that our bounds "may be" tighter than existing ones and that the paper "does not make this argument convincingly" seems to overlook the rigorous evidence we provided. We demonstrated the tightness of the LS bound (and our other bounds) through both theoretical analysis (in the paper) and empirical validation (in the OPE experiments and in the rebuttal), going beyond the typical approach of relying solely on one or the other.

We would like to clarify that our tightness claims are made in the main text, with proofs provided in the Appendix. Redirecting readers to proofs in the Appendix is standard in the field, and we have explicitly stated our intention to include them along with additional discussions in the camera-ready version. This can be easily accommodated with the additional page, as other reviewers did not request major revisions.

Finally, it would have been helpful if the reviewer had specified which concerns remain unaddressed by our rebuttal. The statement "I do not feel that one round of revision is sufficient to address my concerns" lacks explanation, leaving us unsure of which parts of the rebuttal did not address the reviewer's concerns, as we aimed to thoroughly address all points raised in the initial review.
Thank you for your detailed response. It's plausible that the bounds in the paper are interesting contributions and may be tighter than existing ones. However, the submission in its current form does not make this argument convincingly. As it is the central tenet of the paper, I believe that all of the discussions, results, and comparisons above should be a central focus of the main body.  

Given the amount of content that I feel is omitted and worth analyzing more deeply, I do not feel that one round of revision is sufficient to address my concerns, and I stand by my original review.
Thank you for responding to my concerns, I will keep my score.

A small side note: the abbreviation LS is usually associated with Least Squares. If there is another sensible naming option it will probably help avoid confusing the two :)
Thank you for providing responses to the questions. After reading the rebuttals, the difference with the Harmonic estimator (especially the upper bound analysis) became clearer. I believe this paper is worth sharing with the community, and I would keep my initial evaluation.