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

Otmane Sakhi
Criteo AI Lab, Paris, France
<EMAIL_ADDRESS>
Imad Aouali
CREST, ENSAE
Criteo AI Lab, Paris, France
<EMAIL_ADDRESS>Pierre Alquier
ESSEC Business School, Singapore
<EMAIL_ADDRESS>Nicolas Chopin
CREST, ENSAE
<EMAIL_ADDRESS>
###### 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 smooths_ large importance weights. The
bound for LS is provably tighter than all 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.

##  1 Introduction

In decision-making under uncertainty, offline contextual bandit [15, 46]
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 [9]. 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) [15], off-
policy selection (OPS) [31], and off-policy learning (OPL) [57]. 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 [23, 15, 16, 17, 62, 18, 55, 56, 37, 31, 44]. These
estimators rely on importance weighting to address the discrepancy between the
target policy and the behavior policy. While unbiased under mild conditions,
IPS induces high variance. To mitigate this, regularization techniques have
been proposed for IPS [9, 37, 56, 5, 20] 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 [9, 48, 14] or finite sample [31, 20], 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 [26].

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
[57, 34, 31, 49, 5, 61, 20]. Examples for OPS include Kuzborskij et al. [31]
who employed an Efron-Stein bound for self-normalized IPS, or Gabbianelli et
al. [20] that based their analysis on an upper bound constructed with the
Implicit Exploration estimator. Focusing on OPL, Swaminathan and Joachims [57]
exploited the empirical Bernstein bound [35] alongside the Clipping estimator
to motivate sample variance penalization. This work was recently improved by
either modifying the penalization [61] or analyzing the problem from the PAC-
Bayesian lens [34]. The latter was further explored by Sakhi et al. [49],
Aouali et al. [5], Gabbianelli et al. [20] resulting in tight, tractable PAC-
Bayesian bounds that can be directly optimized.

Existing _pessimistic_ OPE, OPS, and OPL approaches often involve analyzing
the concentration properties of a pre-defined risk estimator. We propose a
different approach: deriving concentration bounds for a broad class of
regularized IPS estimators and then identifying the estimator with the best
concentration properties. This allows us to design a tailored estimator, named
Logarithmic Smoothing (LS), which achieves the tightest concentration
inequality. LS enjoys several desirable properties. It concentrates at a sub-
Gaussian rate and has a finite variance, and these benefits are achieved
without requiring the estimator itself to be bounded. Its concentration upper
bound allow 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. [20], and achieves state-of-the-art learning guarantees for
OPL when analyzed within the PAC-Bayesian framework akin to [34, 49, 5, 20].

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.

##  2 Setting and background

Offline contextual bandit. Let $\mathcal{X}\subset\mathbb{R}^{d}$ be the
_context space_ , which is a compact subset of $\mathbb{R}^{d}$, and let
$\mathcal{A}=[K]$ be a finite _action set_. An agent’s actions are guided by a
_stochastic_ and _stationary_ policy $\pi\in\Pi$ within a policy space $\Pi$.
Given a context $x\in\mathcal{X}$, $\pi(\cdot|x)$ is a probability
distribution over the action set $\mathcal{A}$; $\pi(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\in[n]$, the agent
observes a context $x_{i}\sim\nu$ where $\nu$ is a distribution with support
$\mathcal{X}$. After this, the agent selects an action
$a_{i}\sim\pi_{0}(\cdot|x_{i})$, where $\pi_{0}$ is the _behavior policy_ of
the agent. Finally, the agent receives a stochastic cost $c_{i}\in[-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(\cdot|x_{i},a_{i})$. This
leads to $n$-sized logged data,
$\mathcal{D}_{n}=(x_{i},a_{i},c_{i})_{i\in[n]},$ where tuples
$(x_{i},a_{i},c_{i})$ for $i\in[n]$ are i.i.d. The expected cost of taking
action $a$ in context $x$ is $c(x,a)=\mathbb{E}_{c\sim
p(\cdot|x,a)}\left[c\right]$, and the costs are negative because they are
interpreted as the negative of rewards. The performance of a policy
$\pi\in\Pi$ is evaluated through its _risk_ , which aggregates the expected
costs $c(x,a)$ over all possible contexts $x\in\mathcal{X}$ and taken actions
$a\in\mathcal{A}$ by policy $\pi$, such as

$\displaystyle R(\pi)$
$\displaystyle=\mathbb{E}_{x\sim\nu,a\sim\pi(\cdot|x),c\sim p(\cdot\mid
x,a)}\left[c\right]=\mathbb{E}_{x\sim\nu,a\sim\pi(\cdot|x)}\left[c(x,a)\right]\,.$
(1)

The main goal is to use logged dataset $\mathcal{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 $\hat{R}_{n}(\pi)$ of the risk $R(\pi)$ of a fixed _target policy_
$\pi$ and study its deviation, aspiring for $\hat{R}_{n}(\pi)$ to concentrate
well around $R(\pi)$. Second, OPS focuses on selecting the best performing
policy $\hat{\pi}_{n}^{\textsc{s}}$ from a _predefined_ and _finite_
collection of target policies $\pi_{1},\ldots,\pi_{m}$, effectively seeking to
determine $\operatorname*{argmin}_{k\in[m]}R(\pi_{k})$. Third, OPL aims to
find a policy $\hat{\pi}_{n}^{\textsc{l}}$ within the _potentially infinite
policy space $\Pi$_ that achieves the lowest risk, essentially aiming to find
$\operatorname*{argmin}_{\pi\in\Pi}R(\pi)$. 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 [23]. IPS approximates the risk of a policy $\pi$, $R(\pi)$, 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 $\pi$ to its probability under the behavior policy
$\pi_{0}$,

$\displaystyle\hat{R}_{n}(\pi)=\frac{1}{n}\sum_{i=1}^{n}w_{\pi}(x_{i},a_{i})c_{i}\,,$
(2)

where for any
$(x,a)\in\mathcal{X}\times\mathcal{A}\,,w_{\pi}(x,a)=\pi(a|x)/\pi_{0}(a|x)$
are the IWs. IPS is unbiased under the coverage assumption (see for example
Owen [38, Chapter 9]). However, it can suffer high variance, which tends to
scale linearly with IWs [59]. This issue becomes particularly pronounced when
there is a significant discrepancy between the target policy $\pi$ and the
behavior policy $\pi_{0}$. To mitigate this, a common strategy consists in
applying a regularization function
$h:[0,1]^{2}\times[-1,0]\rightarrow]-\infty,0]$ to $\pi(a|x)$, $\pi_{0}(a|x)$
and $c$. This function $h$ 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) defined as

$\displaystyle h\,\text{satisfies
{(C1)}}\iff\forall(p,q,c)\in[0,1]^{2}\times[-1,0],\quad pc/q\leq h(p,q,c)\leq
0.$

With such function $h$, the regularized IPS estimator reads

$\displaystyle\hat{R}^{h}_{n}(\pi)=\frac{1}{n}\sum_{i=1}^{n}h\left(\pi(a_{i}|x_{i}),\pi_{0}(a_{i}|x_{i}),c_{i}\right)=\frac{1}{n}\sum_{i=1}^{n}h_{i}\,,$
(3)

where $h_{i}=h\left(\pi(a_{i}|x_{i}),\pi_{0}(a_{i}|x_{i}),c_{i}\right)$. We
recover standard IPS in (2) when $h(p,q,c)=pc/q$. Numerous regularization
functions $h$ were studied in the literature. For example,

$\displaystyle
h(p,q,c)=\min(p/q,M)c\,,M\in\mathbb{R}^{+}\implies\text{Clipping
\cite[citep]{[\@@bibref{Number}{bottou2013counterfactual}{}{}]} }\,,$ (4)
$\displaystyle
h(p,q,c)=pc/q^{\alpha}\,,\alpha\in[0,1]\implies\text{Exponential Smoothing
\cite[citep]{[\@@bibref{Number}{aouali23a}{}{}]}}\,,$ $\displaystyle
h(p,q,c)=pc/(q+\gamma)\,,\gamma\geq 0\implies\text{Implicit Exploration
\cite[citep]{[\@@bibref{Number}{gabbianelli2023importance}{}{}]}}\,.$

Other IW regularizations include Harmonic [37] and Shrinkage [56]. By imposing
(C1) on $h$, we ensure that our estimator implements a form of pessimism [26]
that holds in expectation, as we have

$\displaystyle h\,\text{satisfies
{(C1)}}\implies\forall\pi\in\Pi,\,R(\pi)\leq\mathbb{E}[\hat{R}^{h}_{n}(\pi)]\,.$
(5)

This ensures regularized IPS covers the true risk in expectation, and it’s the
only requirement to derive our result: a family of high-probability bounds
that hold for regularized IPS with $h$ satisfying (C1).

##  3 Pessimistic off-policy evaluation

OPE often relies on point estimates of risk, which is insufficient in critical
applications, where it is also essential to measure the confidence level of
our estimation. Pessimistic OPE addresses this by using high-probability upper
bounds to assess the worst-case risk of policies [9, 14, 31]. This section
focuses on deriving tight upper bounds on the risk. We achieve this by
analyzing a general family of bounds applicable to regularized IPS in (3) with
any $h$ satisfying (C1).

###  3.1 Preliminaries and unified risk bounds

Let $\pi\in\Pi$, we define the empirical $\ell$-th moment of regularized IPS
$\hat{R}^{h}_{n}(\pi)$ as

$\displaystyle\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}h_{i}^{\ell}\,.$ (6)

Moreover, for $\lambda>0$, we define the function $\psi_{\lambda}:\to$ as

$\displaystyle\psi_{\lambda}(x)=\left(1-\exp(-\lambda x)\right)/\lambda\,.$
$\displaystyle\text{In particular, }\,\psi_{\lambda}(x)\leq x\,\text{ for any
}\,x\in\,.$ (7)

######  Proposition 1.

(Empirical moments risk bound). Let $\pi\in\Pi$, $L\geq 1$, $\delta\in(0,1]$
and $\lambda>0$. Then it holds with probability at least $1-\delta$ that

$\displaystyle
R(\pi)\leq\psi_{\lambda}\Big{(}\hat{R}^{h}_{n}(\pi)+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}\,,$ (8)

where $\psi_{\lambda}$ and $\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)$ are defined
in (7) and (6), respectively, and recall that $\psi_{\lambda}(x)\leq x$.

We provide detailed proof in Section F.1, leveraging Chernoff bounds with a
careful analysis of the moment-generating function. This leads to the first
empirical, high-order moment bound for offline contextual bandits, offering
several advantages. First, the bound applies to any regularization function
$h$ that meets the mild condition (C1). This allows us to design a tailored
regularization function $h$ that minimizes the bound. Second, this bound does
not assume the existence of theoretical moments since it only incorporates
empirical ones. Third, it is fully empirical and tractable, enabling efficient
implementation of pessimism. Finally, the value of $L$ controls the number of
moments used, allowing us to balance bound tightness and computational cost.
Precisely, for sufficiently small values of $\lambda$, higher values of $L$
lead to tighter bounds. However, this can come at the cost of increased
computational complexity for evaluating the bound. This is stated formally as
follows.

######  Proposition 2 (Impact of $L$ on the bound’s tightness).

Let $\pi\in\Pi$, $\delta\in(0,1]$, $\lambda>0$, and $L\geq 1$. Let
$U^{\lambda,h}_{L}(\pi)=\psi_{\lambda}\big{(}\hat{R}^{h}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)\big{)}$
be the bound in Equation 8. Then,

$\displaystyle\lambda\leq\min_{i\in[n]}\left\\{\frac{2L+2}{(2L+1)|h_{i}|}\right\\}\implies
U^{\lambda,h}_{L+1}(\pi)\leq U^{\lambda,h}_{L}(\pi)\,.$ (9)

From (9), the bound in Equation 8, $U^{\lambda,h}_{L}(\pi)$, becomes a
decreasing function of $L$ when $\lambda\leq\min_{i\in[n]}(1/|h_{i}|)$,
suggesting that for sufficiently small $\lambda$, the tightest bound is
achieved by taking $L\to\infty$. That said, we focus particularly on two
instances, $L=1$ resulting in an empirical second-moment bound, and
$L\rightarrow\infty$ which yields a tight bound motivating our novel
estimator.

###  3.2 Global clipping

######  Corollary 3 (Empirical second-moment risk bound with $L=1$).

Let $\pi\in\Pi$, $\delta\in(0,1]$ and $\lambda>0$. Then it holds with
probability at least $1-\delta$ that

$\displaystyle
R(\pi)\leq\psi_{\lambda}\left(\hat{R}^{h}_{n}(\pi)+\frac{\lambda}{2}\hat{\mathcal{M}}^{h,2}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\right)\,.$ (10)

This is a direct consequence of Equation 8 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

$\displaystyle h_{*,1}(p,q,c)=-\min(p|c|/q,1/\lambda)\,.$ (11)

In particular, if we assume that costs are binary, $c\in\\{-1,0\\}$, then
$h_{*,1}$ corresponds to Clipping in (4) with parameter $M=1/\lambda$. This is
because $-\min(|c|p/q,1/\lambda)=\min\left(p/q,\frac{1}{\lambda}\right)c\,$
when $c$ is binary. This motivates the widely used Clipping estimator [9].
However, this also suggests that the standard way of clipping (as in (4)) is
only optimal111Here, optimality of a function $h$ is defined with respect to
our bound with $L=1$ (Corollary 3). for binary costs. In general, the cost
should also be clipped (as in (11)). Finally, with a suitable choice of
$\lambda=\mathcal{O}(1/\sqrt{n})$, our bound in Corollary 3, using clipping
(i.e., $h=h_{*,1}$), outperforms the existing empirical Bernstein bound [57],
which was specifically derived for clipping. Therefore, Corollary 3 not only
applies to a broad range of regularization functions $h$, but also provides
tighter concentration guarantees than specialized bounds. Section F.3 gives
the the proof to find $h_{*,1}$ and formal comparisons are provided in Section
E.2.1.

###  3.3 Logarithmic smoothing

######  Corollary 4 (Empirical infinite-moment bound with $L\to\infty$).

Let $\pi\in\Pi$, $\delta\in(0,1]$ and $\lambda>0$. Then it holds with
probability at least $1-\delta$ that

$\displaystyle
R(\pi)\leq\psi_{\lambda}\left(-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)+\frac{\ln(1/\delta)}{\lambda n}\right)\,.$ (12)

Setting $L\to\infty$ in Equation 8 results in the bound in Corollary 4, which
has different properties than Corollary 3. This result can also be derived by
applying [1, Lemma 1.3]. In Section F.5, we prove that the function
$h_{*,\infty}$ that minimizes this bound is $h_{*,\infty}(p,q,c)=pc/q$. This
corresponds to the standard (non-regularized) IPS in (2). This differs from
the $L=1$ bound in Corollary 3 that favored clipping. This shows the impact of
the moment order $L$ on the optimal function $h$. Applying the bound in
Corollary 4 with the optimal $h_{*,\infty}$ leads to the following empirical
upper bound of $R(\pi)$

$\displaystyle
R(\pi)\leq\psi_{\lambda}\left(\hat{R}^{\lambda}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\right)\,.$ (13)

While we set $h_{*,\infty}(p,q,c)=pc/q$ (no initial IW regularization), a
novel regularized IPS (satisfies (C1)), called Logarithmic Smoothing (LS),
still emerges as

$\displaystyle\hat{R}^{\lambda}_{n}(\pi)=-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
w_{\pi}(x_{i},a_{i})c_{i}\right)\,.$ (14)

The LS estimator in (14) is defined for any non-negative $\lambda\geq 0$, and
its bound in (13) holds for any positive $\lambda>0$. In particular,
$\lambda=0$ recovers the standard (non-regularized) IPS estimator in (2) and
$\lambda>0$ introduces a bias-variance trade-off by smoothing logarithmically
the IWs. This estimator can be interpreted as a soft, differentiable variant
of clipping with parameter $1/\lambda$. Precisely, once the IWs are small
compared to $1/\lambda$, we recover the IPS estimator. Even if the LS
estimator is not bounded, $\lambda>0$ ensures a finite variance and sub-
Gaussianity of LS (Section E.1 discusses the properties of this estimator). We
focus in this section on the tightness of the resulting bound in (13). Recall
that when $\lambda$ is small enough, the bound is decreasing in $L$
(Proposition 2). Thus the bound with $L\to\infty$ is smaller than the bound
with $L=1$. In fact, this condition on $\lambda$ is not necessary when
comparing the bounds evaluated at their optimal regularization function $h$,
as stated in the following proposition.

######  Proposition 5.

Let $U^{\lambda}_{L}(\pi)=\min_{h}U^{\lambda,h}_{L}(\pi)$ for any $\pi\in\Pi$.
Then, for any $\lambda>0$, it holds that for any $L\geq
1\,,\,U^{\lambda}_{L}(\pi)\leq U^{\lambda}_{1}(\pi)$. In particular, for any
$\lambda>0$, it holds that $U^{\lambda}_{\infty}(\pi)\leq
U^{\lambda}_{1}(\pi)$.

Section F.6 proves this result. Note that the bound of LS in (13) corresponds
to $U^{\lambda}_{\infty}(\pi)$. Thus Proposition 5 shows that, irrespective of
the value of $\lambda$, bound of LS is tighter than that obtained with the
optimal $h$ when $L=1$ (i.e, the bound in Corollary 3 evaluated at the
clipping function $h_{*,1}$). It is also provably tighter than existing bounds
in the literature (Section E.2). That said, we use it to derive our
pessimistic OPS and OPL strategies.

##  4 Off-policy selection and learning

###  4.1 Off-policy selection

Let $\Pi_{\textsc{s}}=\\{\pi_{1},...,\pi_{m}\\}$ be a finite set of policies.
In OPS, the goal is to find $\pi_{*}^{\textsc{s}}\in\Pi_{\textsc{s}}$ that
satisfies

$\displaystyle\pi_{*}^{\textsc{s}}=\operatorname*{argmin}_{\pi\in\Pi_{\textsc{s}}}R(\pi)=\operatorname*{argmin}_{k\in[m]}R(\pi_{k})\,.$
(15)

As 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 $\pi_{*}^{\textsc{s}}$. Precisely, for $\lambda>0$, we search for

$\displaystyle\hat{\pi}_{n}^{\textsc{s}}=\operatorname*{argmin}_{\pi\in\Pi_{\textsc{s}}}\hat{R}^{\lambda}_{n}(\pi)=\operatorname*{argmin}_{k\in[m]}\hat{R}^{\lambda}_{n}(\pi_{k})\,.$
(16)

To derive our strategy in (16), we minimize the bound of LS in (13), employing
pessimism [26]. Fortunately, in our case, this boils down to minimizing
$\hat{R}^{\lambda}_{n}(\pi)$, since the other terms in the bound are
independent of the target policy $\pi$. This allows us to avoid computing
complex statistics [57, 31] and does not require access to the behavior policy
$\pi_{0}$. As we show next, it also ensures low suboptimality.

######  Proposition 6.

(Suboptimality of our selection strategy in (16)).Let $\lambda>0$ and
$\delta\in(0,1]$. Then, it holds with probability at least $1-\delta$ that

$\displaystyle 0\leq
R(\hat{\pi}_{n}^{\textsc{s}})-R(\pi_{*}^{\textsc{s}})\leq\lambda\mathcal{S}_{\lambda}(\pi_{*}^{\textsc{s}})+\frac{2\ln(2|\Pi_{\textsc{s}}|/\delta)}{\lambda
n}\,,$ (17)

where
$\mathcal{S}_{\lambda}(\pi)=\mathbb{E}\left[(w_{\pi}(x,a)c)^{2}/\left(1-\lambda
w_{\pi}(x,a)c\right)\right]$, $\pi_{*}^{\textsc{s}}$ and
$\hat{\pi}_{n}^{\textsc{s}}$ are defined in (15) and (16).

$\mathcal{S}_{\lambda}(\pi)$ measures the discrepancy between $\pi$ and
$\pi_{0}$. As for the IX selection strategy [20], our derived suboptimality
bound only requires coverage of the optimal actions (support of the optimal
policy $\pi^{s}_{*}$), and improves on IX suboptimality, matching the minimax
suboptimality lower bound of pessimistic methods [33, 26, 27]. Section G.1
provides a proof of this suboptimality bound, and we discuss in Section E.3
how this suboptimality improves upon existing strategies. By selecting
$\lambda^{s}_{n}=\sqrt{2\ln(2|\Pi_{\textsc{s}}|/\delta)/n}$ for LS, we achieve
a suboptimality scaling of $\mathcal{O}(1/\sqrt{n})$,

$\displaystyle 0\leq
R(\hat{\pi}_{n}^{\textsc{s}})-R(\pi_{*}^{\textsc{s}})\leq\left(1+\mathcal{S}_{\lambda^{s}_{n}}(\pi^{\textsc{s}}_{*})\right)\sqrt{2\ln(2|\Pi_{\textsc{s}}|/\delta)/n},$
(18)

which ensures finding the optimal policy with sufficient samples.
Additionally, the multiplicative constant is smaller when $\pi_{0}$ is close
to $\pi_{*}^{\textsc{s}}$, confirming the known observation that it is easier
to identify the best policy if it is similar to the behavior policy $\pi_{0}$.

###  4.2 Off-policy learning

Similar to how we extended the evaluation bound in Corollary 4 (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
$\Pi$, 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 [57], which
derived a variance-sensitive bound scaling with the covering number [63].
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 $\lambda$, to

$\displaystyle\hat{\pi}_{n}^{\textsc{l}}=\operatorname*{argmin}_{\pi\in\Pi}\hat{R}^{\lambda}_{n}(\pi)+\frac{\mathcal{C}(\Pi)}{\lambda
n}=\operatorname*{argmin}_{\pi\in\Pi}\hat{R}^{\lambda}_{n}(\pi).$ (19)

where $\mathcal{C}(\Pi)$ is a complexity measure [63]. 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 $\mathcal{C}(\Pi)$ varies depending on the policy class
considered, is often intractable [49] and can only be upper bounded with
problem dependent constants [27].

Instead of the method described above, we derive PAC-Bayesian generalization
bounds [36, 10] 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 [34]. Specifically, let
$\mathcal{F}(\Theta)=\\{f_{\theta}:\mathcal{X}\rightarrow[K],\theta\in\Theta\\}$
be a set of parameterized predictors that associate the context $x$ with the
action $f_{\theta}(x)\in[K]$. Let $\mathcal{P}(\Theta)$ be the set of all
probability distributions on $\Theta$. Each distribution
$Q\in\mathcal{P}(\Theta)$ defines a policy $\pi_{Q}$ by setting the
probability of action $a$ given context $x$ as the probability that a random
predictor $f_{\theta}\sim Q$ maps $x$ to action $a$, that is,

$\textstyle\pi_{Q}(a|x)=\mathbb{E}_{\theta\sim
Q}\left[\mathbbm{1}\left[f_{\theta}(x)=a\right]\right]\,,$
$\textstyle\forall(x,a)\in\mathcal{X}\times\mathcal{A}\,.$ (20)

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
$\pi$ [34, 5, 20]. Our estimator LS in (14) is non-linear in $\pi$. Therefore,
for this PAC-Bayesian analysis, we introduce a linearized variant of LS,
called LS-LIN, and defined as

$\displaystyle\hat{R}^{\lambda\textsc{-lin}}_{n}(\pi)=-\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{\lambda}\log\left(1-\frac{\lambda
c_{i}}{\pi_{0}(a_{i}|x_{i})}\right),$ (21)

which smooths the impact of the behavior propensity $\pi_{0}$ instead of the
IWs $\pi/\pi_{0}$. We provide in the following a core result of this section,
the PAC-Bayesian bound that defines our learning strategy.

######  Proposition 7.

(PAC-Bayes learning bound for $\hat{R}^{\lambda{\textsc{-lin}}}_{n})$. Given a
prior $P\in\mathcal{P}(\Theta)$, $\delta\in(0,1]$ and $\lambda>0$, the
following holds with probability at least $1-\delta$:

$\displaystyle\forall Q\in\mathcal{P}(\Theta),\quad
R(\pi_{Q})\leq\psi_{\lambda}\left(\hat{R}^{\lambda{\textsc{-lin}}}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}\right)\,,$ (22)

where $\mathcal{KL}(Q||P)$ is the Kullback-Leibler divergence from $P$ to $Q$.

PAC-Bayes bounds hold uniformly for all distributions
$Q\in\mathcal{P}(\Theta)$ and replace the complexity measure
$\mathcal{C}(\Pi)$ with the divergence $\mathcal{KL}(Q||P)$ from a reference
_prior_ distribution $P$. Extensive research focuses on identifying the best
strategies for choosing this prior $P$ [39]. While these bounds hold for any
fixed prior $P$, in practice, it is typically set to the distribution inducing
the behavior policy $\pi_{0}$, meaning $P$ satisfies $\pi_{0}=\pi_{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
$\pi_{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 IX [20], resulting
in the tightest known generalization bound in OPL. Section 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 $\lambda$ and a fixed prior $P$, we derive
a learning strategy that minimizes the upper bound for a subset
$\mathcal{L}(\Theta)\subseteq\mathcal{P}(\Theta)$ of distributions, seeking

$\displaystyle
Q_{n}=\operatorname*{argmin}_{Q\in\mathcal{L}(\Theta)}\left\\{\hat{R}^{\lambda\textsc{-lin}}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)}{\lambda
n}\right\\}\,,\quad\text{and setting
}\hat{\pi}_{n}^{\textsc{l}}=\pi_{Q_{n}}\,.$ (23)

(23) 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,
$\pi_{Q^{*}}=\operatorname*{argmin}_{Q\in\mathcal{L}(\Theta)}R(\pi_{Q})$.

######  Proposition 8.

(Suboptimality of the learning strategy in (23)). Let $\lambda>0$,
$P\in\mathcal{L}(\Theta)$ and $\delta\in(0,1]$. Then, it holds with
probability at least $1-\delta$ that

$\displaystyle 0\leq
R(\hat{\pi}_{n}^{\textsc{l}})-R(\pi_{Q^{*}})\leq\lambda\mathcal{S}^{{\textsc{lin}}}_{\lambda}(\pi_{Q^{*}})+\frac{2\left(\mathcal{KL}(Q^{*}||P)+\ln(2/\delta)\right)}{\lambda
n},$ (24)

where
$\mathcal{S}^{{\textsc{lin}}}_{\lambda}(\pi)=\mathbb{E}\left[\pi(a|x)c^{2}/(\pi^{2}_{0}(a|x)-\lambda\pi_{0}(a|x)c)\right]$
and $\hat{\pi}_{n}^{\textsc{l}}$ is defined in (23).

Our suboptimality bound only requires coverage of the optimal actions (support
of the optimal policy $\pi_{Q_{*}}$). This bound matches the minimax
suboptimality lower bound of pessimistic learning with deterministic policies
[27]. Section G.3 provides a proof of Proposition 8, while Section E.5
discusses the suboptimality bound further and proves that it is better than
the IX learning strategy of [20, Section 5]. Setting
$\lambda^{l}_{n}=2/\sqrt{n}$ guarantees us a suboptimality that scales with
$\mathcal{O}(1/\sqrt{n})$ as

$\textstyle 0\leq
R(\hat{\pi}_{n}^{\textsc{l}})-R(\pi_{Q^{*}})\leq(2\mathcal{S}^{{\textsc{lin}}}_{\lambda^{l}_{n}}(\pi_{Q^{*}})+\mathcal{KL}(Q^{*}||P)+\ln(2/\delta))/{\sqrt{n}}.$

By setting the reference $P$ to the distribution inducing $\pi_{0}$, we find
that the learning suboptimality is reduced when the behavior policy $\pi_{0}$
is close to the optimal policy $\pi_{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 $\pi_{0}$ is close to $\pi_{Q^{*}}$.

##  5 Experiments

Our experimental setup follows the classical multiclass to bandit conversion
used in most prior studies [17, 57]. We consider a contextual bandit problem
such that for every context $x$, its true label in the classification dataset
is denoted by $\rho(x)\in[K]$, and represents the action with the highest
average reward. The reward $r$ for playing action $a$ for context $x$ is
modelled as Bernoulli with probability
$p_{x}=\epsilon+\mathbbm{1}\left[a=\rho(x)\right](1-2\epsilon)$, with
$\epsilon$ a noise parameter. This ensures an average reward of $1-\epsilon$
for the optimal action and $\epsilon$ for all other actions. This procedure
helps us build a logged bandit feedback dataset of the form
$\\{x_{i},a_{i},c_{i}\\}_{i\in[n]}$, where $c_{i}=-r_{i}$ is the corresponding
cost.

Table 1: Bound’s tightness $(\lvert U(\pi)/R(\pi)-1\rvert)$ with varying number of samples of the kropt dataset. Number of samples | SN-ES | cIPS-EB | IX |  cIPS-L=1 (Ours) |  LS (Ours)
---|---|---|---|---|---
$2^{8}$ | 1.000 | 0.917 | 0.373 | 0.364 | 0.362
$2^{9}$ | 1.000 | 0.732 | 0.257 | 0.289 | 0.236
$2^{10}$ | 0.794 | 0.554 | 0.226 | 0.240 | 0.213
$2^{11}$ | 0.649 | 0.441 | 0.171 | 0.197 | 0.159
$2^{12}$ | 0.472 | 0.327 | 0.126 | 0.147 | 0.117
$2^{13}$ | 0.374 | 0.204 | 0.062 | 0.077 | 0.054
$2^{14}$ | 0.257 | 0.138 | 0.041 | 0.049 | 0.035

###  5.1 Off-policy evaluation and selection experiments

For both evaluation and selection, we adopt the same experimental design as
[31] to facilitate the comparison. We consider exponential target policies
$\pi(a|x)\propto\exp(\frac{1}{\tau}f(a,x))$, with $\tau$ 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
$\pi^{\texttt{ideal}}(a|x)\propto\exp(\frac{1}{\tau}\mathbb{I}\\{\rho(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\subset[K]$. To recreate
real world scenarios, we also consider policies directly learned from logged
bandit feedback, of the form
$\pi_{\theta^{\texttt{IPS}}}(a|x)\propto\exp(\frac{1}{\tau}x^{t}\theta_{a}^{\texttt{IPS}})$
and
$\pi_{\theta^{\texttt{SN}}}(a|x)\propto\exp(\frac{1}{\tau}x^{t}\theta_{a}^{\texttt{SN}})$,
with their parameters learned by respectively minimizing the IPS [23] and SN
[58] empirical risks. More details on the definition of the different policies
are given in Appendix H. Finally, 11 real multiclass classification datasets
are chosen from the UCI ML Repository [7] (See Table 3 in Section H.1.1) with
various number of samples, dimensions and action space sizes to conduct our
experiments.

(OPE) Tightness of the bounds. Evaluating the worst case performance of a
policy is done through evaluating risk upper bounds [9, 31]. This means that a
better evaluation will solely depend on the tightness of the bounds used. To
this end, given a policy $\pi$, we are interested in bounds with a small
relative radius $\lvert U(\pi)/R(\pi)-1\rvert$. We compare our newly derived
bounds (cIPS-L=1 for $U^{\lambda}_{1}$ and LS for $U^{\lambda}_{\infty}$ both
with $\lambda=1/\sqrt{n}$) to empirical evaluation bounds of the literature:
SN-ES: the Efron Stein bound for Self Normalized IPS [31], cIPS-EB: Empirical
Bernstein for Clipping [57] and the recent IX: Implicit Exploration bound
[20]. The first experiment uses the kropt dataset with $\epsilon=0.2$,
collects bandit feedback with faulty behavior policy (with $\tau=0.25$) to
evaluate an ideal policy ($\tau=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 log smoothing
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 ($\tau_{0}\in\\{0.2,0.25,0.3\\}$) and different noise levels
($\epsilon\in\\{0.,0.1,0.2\\}$) to evaluate ideal policies with different
temperatures ($\tau\in\\{0.1,0.3,0.5\\}$), defining $\sim 300$ different
scenarios to validate our findings. We plot in Figure 1 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 Section 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 $\pi_{0}$ and avoid
policies that perform worse than $\pi_{0}$. To replicate real world scenarios,
we design an experiment where $\pi_{0}$ is a faulty policy ($\tau=0.2$), that
collects noisy ($\epsilon=0.2$) interaction data, some of which is used to
learn $\pi_{\theta^{\texttt{IPS}}},\pi_{\theta^{\texttt{SN}}}$, and that we
add to our discrete set of policies
$\Pi_{k=4}=\\{\pi_{0},\pi^{\texttt{ideal}},\pi_{\theta^{\texttt{IPS}}},\pi_{\theta^{\texttt{SN}}}\\}$.
The goal is to measure the ability of our selection strategies to choose from
$\Pi_{k=4}$, better performing policies than $\pi_{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 [23]
and SN [58]. The comparison is conducted on the 11 UCI datasets with 10
different seeds resulting in 110 scenarios. We plot in Figure 1 the percentage
of time each method selected the best policy, a better or a worse policy than
$\pi_{0}$. While risk estimators can identify the best policy, they are
unreliable as they can choose worse performing policies than $\pi_{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 Section H.1.3.

Figure 1: Results for OPE and OPS experiments.

###  5.2 Off-policy learning experiments

We follow the successful off policy learning paradigm based on directly
minimizing PAC-Bayesian risk generalization bounds [49, 5] as it comes with
guarantees of improvement and avoids hyper-parameter tuning. For comparable
results, we use the same 4 datasets (described in Section H.2, Table 7) as in
[49, 5] and adopt the LGP: Linear Gaussian Policies [49] as our class of
parametrized policies. For each dataset, we use behavior policies trained on a
small fraction of the data in a supervised fashion, combined with different
inverse temperature parameters $\alpha\in\\{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 $UB_{n}$ directly and obtain the
learned policy as the bound’s minimizer $\hat{\pi}_{UB_{n}}$ (as in (23)).
With $\hat{\pi}_{UB_{n}}$ obtained, we are interested in two quantities: The
guaranteed risk $\mathcal{GR}_{UB_{n}}=UB_{n}(\hat{\pi}_{UB_{n}})$ by the
bound. It is the value of the bound $UB_{n}$ at its minimizer
$\hat{\pi}_{UB_{n}}$. This quantity reflects the worst case performance of the
learned policy. A lower value implies stronger guarantees on the policy’s
performance. We are also interested in the true risk of the minimizer of the
bound $R(\hat{\pi}_{UB_{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 (23) to
strategies based on minimizing off-policy PAC Bayesian bounds from the
literature: clipped IPS (cIPS) and Control Variate clipped IPS (cvcIPS) in
[49], Exponential Smoothing (ES) in [5] and Implicit Exploration (IX) in [20].
The results are summarized in Table 2 where we compute:

$\textstyle
rI(x)=(R(\pi_{0})-x)/(R(\pi_{0})-R(\pi^{*}))=(R(\pi_{0})-x)/(R(\pi_{0})+1)\,,$

the improvement of $R(\pi_{0})$ achieved by minimizing the different bounds in
terms of $x\in\\{\mathcal{GR},R\\}$, 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. More
detailed results can be found in Section 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).

Table 2: OPL: Relative Improvement of $\mathcal{GR}$ and $R$ of the bounds averaged over 200 scenarios. | cIPS | cvcIPS | ES | IX |  LS-LIN (Ours)
---|---|---|---|---|---
$rI(\mathcal{GR}_{UB_{n}})$ | 14.48% | 21.28% | 7.78% | 24.74% | 26.31%
$rI(R(\hat{\pi}_{UB_{n}}))$ | 28.13% | 33.64% | 29.44% | 36.70% | 36.76%

##  6 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.

## References

  * Alquier [2006] Pierre Alquier.  _Transductive and Inductive Adaptative Inference for Regression and Density Estimation_.  Theses, ENSAE ParisTech, December 2006.  URL https://pastel.hal.science/tel-00119593.
  * Alquier [2024] Pierre Alquier.  User-friendly introduction to PAC-Bayes bounds.  _Foundations and Trends® in Machine Learning_ , 17(2), 2024.
  * Aouali et al. [2022a] Imad Aouali, Amine Benhalloum, Martin Bompaire, Achraf Ait Sidi Hammou, Sergey Ivanov, Benjamin Heymann, David Rohde, Otmane Sakhi, Flavian Vasile, and Maxime Vono.  Reward Optimizing Recommendation using Deep Learning and Fast Maximum Inner Product Search.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , KDD ’22, page 4772–4773, New York, NY, USA, 2022a. Association for Computing Machinery.  ISBN 9781450393850.  doi: 10.1145/3534678.3542622.  URL https://doi.org/10.1145/3534678.3542622.
  * Aouali et al. [2022b] Imad Aouali, Achraf Ait Sidi Hammou, Sergey Ivanov, Otmane Sakhi, David Rohde, and Flavian Vasile.  Probabilistic Rank and Reward: A Scalable Model for Slate Recommendation, 2022b.
  * Aouali et al. [2023] Imad Aouali, Victor-Emmanuel Brunel, David Rohde, and Anna Korba.  Exponential Smoothing for Off-Policy Learning.  In _Proceedings of the 40th International Conference on Machine Learning_ , pages 984–1017. PMLR, 2023.
  * Aouali et al. [2024] Imad Aouali, Victor-Emmanuel Brunel, David Rohde, and Anna Korba.  Bayesian off-policy evaluation and learning for large action spaces.  _arXiv preprint arXiv:2402.14664_ , 2024.
  * Asuncion and Newman [2007] A. Asuncion and D. J. Newman.  UCI machine learning repository, 2007.  URL http://www.ics.uci.edu/$∼$mlearn/{MLR}epository.html.
  * Bang and Robins [2005] Heejung Bang and James M Robins.  Doubly robust estimation in missing data and causal inference models.  _Biometrics_ , 61(4):962–973, 2005.
  * Bottou et al. [2013] Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson.  Counterfactual reasoning and learning systems: The example of computational advertising.  _Journal of Machine Learning Research_ , 14(11), 2013.
  * Catoni [2007] Olivier Catoni.  PAC-Bayesian supervised classification: The thermodynamics of statistical learning.  _IMS Lecture Notes Monograph Series_ , page 1–163, 2007.  ISSN 0749-2170.  doi: 10.1214/074921707000000391.  URL http://dx.doi.org/10.1214/074921707000000391.
  * Chen et al. [2019] Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H. Chi.  Top-K Off-Policy Correction for a REINFORCE Recommender System.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , WSDM ’19, page 456–464, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450359405.  doi: 10.1145/3289600.3290999.  URL https://doi.org/10.1145/3289600.3290999.
  * Chernozhukov et al. [2019] Victor Chernozhukov, Mert Demirer, Greg Lewis, and Vasilis Syrgkanis.  Semi-parametric efficient policy learning with continuous actions.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Cief et al. [2024] Matej Cief, Jacek Golebiowski, Philipp Schmidt, Ziawasch Abedjan, and Artur Bekasov.  Learning action embeddings for off-policy evaluation.  In _European Conference on Information Retrieval_ , pages 108–122. Springer, 2024.
  * Dai et al. [2020] Bo Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvari, and Dale Schuurmans.  Coindice: Off-policy confidence interval estimation.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 9398–9411. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper_files/paper/2020/file/6aaba9a124857622930ca4e50f5afed2-Paper.pdf.
  * Dudík et al. [2011] Miroslav Dudík, John Langford, and Lihong Li.  Doubly robust policy evaluation and learning.  In _Proceedings of the 28th International Conference on International Conference on Machine Learning_ , ICML’11, page 1097–1104, 2011.
  * Dudík et al. [2012] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li.  Sample-efficient nonstationary policy evaluation for contextual bandits.  In _Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence_ , UAI’12, page 247–254, Arlington, Virginia, USA, 2012. AUAI Press.
  * Dudik et al. [2014] Miroslav Dudik, Dumitru Erhan, John Langford, and Lihong Li.  Doubly robust policy evaluation and optimization.  _Statistical Science_ , 29(4):485–511, 2014.
  * Farajtabar et al. [2018] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh.  More robust doubly robust off-policy evaluation.  In _International Conference on Machine Learning_ , pages 1447–1456. PMLR, 2018.
  * Flynn et al. [2023] Hamish Flynn, David Reeb, Melih Kandemir, and Jan Peters.  PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(12):15308–15327, 2023.  doi: 10.1109/TPAMI.2023.3305381.
  * Gabbianelli et al. [2023] Germano Gabbianelli, Gergely Neu, and Matteo Papini.  Importance-Weighted Offline Learning Done Right.  _arXiv preprint arXiv:2309.15771_ , 2023.
  * Gilotte et al. [2018] Alexandre Gilotte, Clément Calauzènes, Thomas Nedelec, Alexandre Abraham, and Simon Dollé.  Offline a/b testing for recommender systems.  In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_ , pages 198–206, 2018.
  * Hagerup and Rüb [1990] Torben Hagerup and Christine Rüb.  A Guided Tour of Chernoff Bounds.  _Inf. Process. Lett._ , 33(6):305–308, 1990.  URL http://dblp.uni-trier.de/db/journals/ipl/ipl33.html#HagerupR90.
  * Horvitz and Thompson [1952] Daniel G Horvitz and Donovan J Thompson.  A generalization of sampling without replacement from a finite universe.  _Journal of the American statistical Association_ , 47(260):663–685, 1952.
  * Ionides [2008] Edward L Ionides.  Truncated importance sampling.  _Journal of Computational and Graphical Statistics_ , 17(2):295–311, 2008.
  * Jeunen and Goethals [2021] Olivier Jeunen and Bart Goethals.  Pessimistic reward models for off-policy learning in recommendation.  In _Fifteenth ACM Conference on Recommender Systems_ , pages 63–74, 2021.
  * Jin et al. [2021] Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is pessimism provably efficient for offline rl?  In _International Conference on Machine Learning_ , pages 5084–5096. PMLR, 2021.
  * Jin et al. [2023] Ying Jin, Zhimei Ren, Zhuoran Yang, and Zhaoran Wang.  Policy learning "without” overlap: Pessimism and generalized empirical Bernstein’s inequality, 2023.
  * Kallus and Zhou [2018] Nathan Kallus and Angela Zhou.  Policy evaluation and optimization with continuous treatments.  In _International conference on artificial intelligence and statistics_ , pages 1243–1251. PMLR, 2018.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Krishnamurthy et al. [2020] Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins, and Chicheng Zhang.  Contextual bandits with continuous actions: Smoothing, zooming, and adapting.  _Journal of Machine Learning Research_ , 21(137):1–45, 2020.
  * Kuzborskij et al. [2021] Ilja Kuzborskij, Claire Vernade, Andras Gyorgy, and Csaba Szepesvári.  Confident off-policy evaluation and selection through self-normalized importance weighting.  In _International Conference on Artificial Intelligence and Statistics_ , pages 640–648. PMLR, 2021.
  * Lattimore and Szepesvari [2019] Tor Lattimore and Csaba Szepesvari.  _Bandit Algorithms_.  Cambridge University Press, 2019.
  * Li et al. [2015] Lihong Li, Remi Munos, and Csaba Szepesvari.  Toward Minimax Off-policy Value Estimation.  In Guy Lebanon and S. V. N. Vishwanathan, editors, _Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics_ , volume 38 of _Proceedings of Machine Learning Research_ , pages 608–616, San Diego, California, USA, 09–12 May 2015. PMLR.  URL https://proceedings.mlr.press/v38/li15b.html.
  * London and Sandler [2019] Ben London and Ted Sandler.  Bayesian counterfactual risk minimization.  In _International Conference on Machine Learning_ , pages 4125–4133. PMLR, 2019.
  * Maurer and Pontil [2009] Andreas Maurer and Massimiliano Pontil.  Empirical Bernstein bounds and sample variance penalization.  _arXiv preprint arXiv:0907.3740_ , 2009.
  * McAllester [1998] David A. McAllester.  Some PAC-Bayesian theorems.  In _Proceedings of the Eleventh Annual Conference on Computational Learning Theory_ , COLT’ 98, page 230–234, New York, NY, USA, 1998. Association for Computing Machinery.  ISBN 1581130570.  doi: 10.1145/279943.279989.  URL https://doi.org/10.1145/279943.279989.
  * Metelli et al. [2021] Alberto Maria Metelli, Alessio Russo, and Marcello Restelli.  Subgaussian and differentiable importance sampling for off-policy evaluation and learning.  _Advances in Neural Information Processing Systems_ , 34:8119–8132, 2021.
  * Owen [2013] Art B. Owen.  _Monte Carlo theory, methods and examples_.  https://artowen.su.domains/mc/, 2013.
  * Parrado-Hernández et al. [2012] Emilio Parrado-Hernández, Amiran Ambroladze, John Shawe-Taylor, and Shiliang Sun.  PAC-Bayes Bounds with Data Dependent Priors.  _Journal of Machine Learning Research_ , 13(112):3507–3531, 2012.  URL http://jmlr.org/papers/v13/parrado12a.html.
  * Peng et al. [2023] Jie Peng, Hao Zou, Jiashuo Liu, Shaoming Li, Yibao Jiang, Jian Pei, and Peng Cui.  Offline policy evaluation in large action spaces via outcome-oriented action grouping.  In _Proceedings of the ACM Web Conference 2023_ , pages 1220–1230, 2023.
  * Robins and Rotnitzky [1995] James M Robins and Andrea Rotnitzky.  Semiparametric efficiency in multivariate regression models with missing data.  _Journal of the American Statistical Association_ , 90(429):122–129, 1995.
  * Sachdeva et al. [2020] Noveen Sachdeva, Yi Su, and Thorsten Joachims.  Off-policy bandits with deficient support.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 965–975, 2020.
  * Sachdeva et al. [2023] Noveen Sachdeva, Lequn Wang, Dawen Liang, Nathan Kallus, and Julian McAuley.  Off-policy evaluation for large action spaces via policy convolution.  _arXiv preprint arXiv:2310.15433_ , 2023.
  * Saito and Joachims [2022] Yuta Saito and Thorsten Joachims.  Off-Policy Evaluation for Large Action Spaces via Embeddings.  _arXiv preprint arXiv:2202.06317_ , 2022.
  * Saito et al. [2023] Yuta Saito, Qingyang Ren, and Thorsten Joachims.  Off-policy evaluation for large action spaces via conjunct effect modeling.  In _international conference on Machine learning_ , pages 29734–29759. PMLR, 2023.
  * Sakhi [2023] Otmane Sakhi.  _Offline Contextual Bandit : Theory and Large Scale Applications_.  Theses, Institut Polytechnique de Paris, December 2023.  URL https://theses.hal.science/tel-04417936.
  * Sakhi et al. [2020a] Otmane Sakhi, Stephen Bonner, David Rohde, and Flavian Vasile.  BLOB: A Probabilistic model for recommendation that combines organic and bandit signals.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 783–793, 2020a.
  * Sakhi et al. [2020b] Otmane Sakhi, Louis Faury, and Flavian Vasile.  Improving Offline Contextual Bandits with Distributional Robustness, 2020b.
  * Sakhi et al. [2023a] Otmane Sakhi, Pierre Alquier, and Nicolas Chopin.  PAC-Bayesian Offline Contextual Bandits with Guarantees.  In _International Conference on Machine Learning_ , pages 29777–29799. PMLR, 2023a.
  * Sakhi et al. [2023b] Otmane Sakhi, David Rohde, and Nicolas Chopin.  Fast Slate Policy Optimization: Going Beyond Plackett-Luce.  _Transactions on Machine Learning Research_ , 2023b.  ISSN 2835-8856.  URL https://openreview.net/forum?id=f7a8XCRtUu.
  * Sakhi et al. [2023c] Otmane Sakhi, David Rohde, and Alexandre Gilotte.  Fast Offline Policy Optimization for Large Scale Recommendation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 37(8):9686–9694, Jun. 2023c.  doi: 10.1609/aaai.v37i8.26158.  URL https://ojs.aaai.org/index.php/AAAI/article/view/26158.
  * Seldin et al. [2011] Yevgeny Seldin, Peter Auer, John Shawe-taylor, Ronald Ortner, and François Laviolette.  PAC-Bayesian analysis of contextual bandits.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24. Curran Associates, Inc., 2011.  URL https://proceedings.neurips.cc/paper/2011/file/58e4d44e550d0f7ee0a23d6b02d9b0db-Paper.pdf.
  * Seldin et al. [2012] Yevgeny Seldin, Nicolò Cesa-Bianchi, Peter Auer, François Laviolette, and John Shawe-Taylor.  Pac-bayes-bernstein inequality for martingales and its application to multiarmed bandits.  In Dorota Glowacka, Louis Dorard, and John Shawe-Taylor, editors, _Proceedings of the Workshop on On-line Trading of Exploration and Exploitation 2_ , volume 26 of _Proceedings of Machine Learning Research_ , pages 98–111, Bellevue, Washington, USA, 02 Jul 2012. PMLR.  URL https://proceedings.mlr.press/v26/seldin12a.html.
  * Shrivastava and Li [2014] Anshumali Shrivastava and Ping Li.  Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS).  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.  URL https://proceedings.neurips.cc/paper_files/paper/2014/file/310ce61c90f3a46e340ee8257bc70e93-Paper.pdf.
  * Su et al. [2019] Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims.  Cab: Continuous adaptive blending for policy evaluation and learning.  In _International Conference on Machine Learning_ , pages 6005–6014. PMLR, 2019.
  * Su et al. [2020] Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík.  Doubly robust off-policy evaluation with shrinkage.  In _International Conference on Machine Learning_ , pages 9167–9176. PMLR, 2020.
  * Swaminathan and Joachims [2015a] Adith Swaminathan and Thorsten Joachims.  Batch learning from logged bandit feedback through counterfactual risk minimization.  _The Journal of Machine Learning Research_ , 16(1):1731–1755, 2015a.
  * Swaminathan and Joachims [2015b] Adith Swaminathan and Thorsten Joachims.  The self-normalized estimator for counterfactual learning.  _advances in neural information processing systems_ , 28, 2015b.
  * Swaminathan et al. [2017] Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miro Dudik, John Langford, Damien Jose, and Imed Zitouni.  Off-policy evaluation for slate recommendation.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Taufiq et al. [2024] Muhammad Faaiz Taufiq, Arnaud Doucet, Rob Cornish, and Jean-Francois Ton.  Marginal density ratio for off-policy evaluation in contextual bandits.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Wang et al. [2023] Lequn Wang, Akshay Krishnamurthy, and Aleksandrs Slivkins.  Oracle-efficient pessimism: Offline policy optimization in contextual bandits.  _arXiv preprint arXiv:2306.07923_ , 2023.
  * Wang et al. [2017] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudık.  Optimal and adaptive off-policy evaluation in contextual bandits.  In _International Conference on Machine Learning_ , pages 3589–3597. PMLR, 2017.
  * Zhou [2002] Ding-Xuan Zhou.  The covering number in learning theory.  _J. Complex._ , 18(3):739–767, sep 2002.  ISSN 0885-064X.  doi: 10.1006/jcom.2002.0635.  URL https://doi.org/10.1006/jcom.2002.0635.

##  Appendix A Limitations

This work develops theoretically grounded and practical pessimistic approaches
for the offline contextual bandit setting. Even if the proposed algorithms are
general, and provably better than competitors, they still suffer from the
intrinsic limitations of importance weighting estimators. Specifically, our
method, as presented, will perform poorly in _extremely_ large action spaces.
However, these limitations can be mitigated by incorporating additional
structure as in Saito and Joachims [44], Saito et al. [45]. 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.

##  Appendix B Broader impact

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.

##  Appendix C Extended related work

Offline contextual bandits. Contextual bandit is a widely adopted framework
for online learning in uncertain environments [32]. However, some real-world
applications present challenges for existing online algorithms, and thus
offline methods that leverage historical data to optimize decision-making have
gained traction [9]. Fortunately, large datasets summarizing past interactions
are often available, allowing agents to improve their policies offline [57].
Our work explores this offline approach, known as offline (or off-policy)
contextual bandits [15]. 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 [15, 16, 17, 62, 18, 55,
56, 37, 31, 44, 47, 25]. The literature on OPE can be broadly classified into
three primary approaches. The first, referred to as the direct method (DM)
[25, 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, 25, 4]. The
second approach, known as inverse propensity scoring (IPS) [23, 16], 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 [42]. In response to the variance issue, various
techniques have been introduced, including clipping [24, 9], shrinkage [56],
power-mean correction [37], implicit exploration [20], self-normalization
[58], among others [21]. The third approach, known as doubly robust (DR) [41,
8, 15, 17, 18], 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 [57], updating a
parameterized policy denoted by $\pi_{\theta}$ as
$\theta_{t+1}\leftarrow\theta_{t}-\nabla_{\theta}R(\pi_{\theta})$ for each
iteration $t$. Since the true risk $R$ is unknown,
$\nabla_{\theta}R(\pi_{\theta})$ 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 [9,
48, 14] or finite sample [31, 20], aim to evaluate a policy’s worst-case
performance, adhering to the principle of _pessimism in face of uncertainty_
[26]. 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 [57, 34, 31, 49, 5, 61]. Consider
OPS: [31] leveraged an Efron-Stein bound for the self-normalized IPS
estimator, while [20] anchored their analysis on a bound constructed with the
Implicit Exploration estimator. Shifting focus to OPL, [57] combined the
empirical Bernstein bound [35] with the clipping estimator, motivating sample
variance penalization for policy learning. Recent advancements include
modifications to the penalization term [61] to be scalable and efficient.

PAC-Bayes extension. The PAC-Bayesian paradigm [36, 10] (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, 53]. It is just recently
that these tools were adapted to the offline contextual bandit setting, with
[34] that introduced a clean and scalable PAC-Bayesian perspective to OPL.
This perspective was further explored by [19, 49, 5, 20], 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 [44]
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 as

$\displaystyle\hat{R}_{n}^{\text{MIPS}}(\pi)=\frac{1}{n}\sum_{i=1}^{n}\frac{\pi\left(e_{i}\mid
x_{i}\right)}{\pi_{0}\left(e_{i}\mid
x_{i}\right)}c_{i}=\frac{1}{n}\sum_{i=1}^{n}w\left(x_{i},e_{i}\right)c_{i}\,,$

where the logged data
$\mathcal{D}_{n}=\left\\{\left(x_{i},a_{i},e_{i},r_{i}\right)\right\\}_{i=1}^{n}$
now includes action embeddings for each data point. The marginal importance
weight

$\displaystyle w(x,e)=\frac{\pi(e\mid x)}{\pi_{0}(e\mid
x)}=\frac{\sum_{a}p(e\mid x,a)\pi(a\mid x)}{\sum_{a}p(e\mid x,a)\pi_{0}(a\mid
x)}$

is a key component of this approach. Compared to IPS and DR, MIPS achieves
significantly lower variance in large action spaces [44] 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 [40, 43, 13], or loosen this assumption
[60, 45]. 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$ [11]. Recent work [51, 50] solve this by leveraging
fast maximum inner product search [54, 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 [28, 12, 61]. For example, [28] explored non-parametric
evaluation and learning of continuous action policies using kernel smoothing,
while [12] investigated the semi-parametric setting. Recently, [61] leveraged
the smoothing approach from [30] 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$, $\pi(a\mid 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 $\Pi$ into an OPL problem
defined by a discrete, mass-based policy class $\Pi_{K}$ (for a finite number
of actions $K$). Each policy within $\Pi_{K}$ approximates a policy in $\Pi$
through a smoothing process.

##  Appendix D Useful lemmas

In the following, and for any quantity $Z$, all expectations are computed
w.r.t to the distribution of the data when playing actions under the behaviour
policy $\pi_{0}$, as in:

$\mathbb{E}\left[Z\right]=\mathbb{E}_{x\sim\nu,a\sim\pi_{0}(\cdot|x),c\sim
p(\cdot\mid x,a)}\left[Z\right].$

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

(Chernoff Inequality for a sum of i.i.d. random variables.) Let
$a\in\mathbbm{R}$, $n\in\mathbbm{N}^{*}$ and $\\{X_{i},i\in[n]\\}$ a
collection of $n$ i.i.d. random variables. The following concentration bounds
on the right tail of $\sum_{i\in[n]}X_{i}$ hold for any $\lambda\geq 0$:
$\displaystyle
P\left(\sum_{i\in[n]}X_{i}>a\right)\leq\left(\mathbbm{E}\left[\exp\left(\lambda
X_{1}\right)\right]\right)^{n}\exp(-\lambda a)$

This result is classical in the literature [22] 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 10.

Let $L\geq 1$ and $f_{L}$ be the following function:
$f_{L}(x)=\frac{\log(1+x)-\sum_{\ell=1}^{L}\frac{(-1)^{\ell-1}}{\ell}x^{\ell}}{(-1)^{L}x^{L+1}}.$
We have that $f_{L}$ is a decreasing function in $\mathbbm{R}^{+}$ for all
$L\in\mathbbm{N}^{*}$.

###### Proof.

Let $L\geq 1$ and $f_{L}$ be the following function:

$f_{L}(x)=\frac{\log(1+x)-\sum_{\ell=1}^{L}\frac{(-1)^{\ell-1}}{\ell}x^{\ell}}{(-1)^{L}x^{L+1}}.$

Let $x\in\mathbbm{R}^{+}$, we have the following identity holding $\forall
t>0$ and $\forall n\geq 0$:

$\displaystyle\frac{1+(-1)^{n}t^{n+1}}{1+t}=\sum_{k=0}^{n}(-1)^{k}t^{k}\iff\frac{1}{1+t}=\sum_{k=0}^{n}(-1)^{k}t^{k}+\frac{(-1)^{n+1}t^{n+1}}{1+t}.$
(25)

Recall the integral form of the log function:

$\log(1+x)=\int_{0}^{x}\frac{1}{1+t}dt.$

We integrate both sides of the Equality (25) and show that the numerator of
$f_{L}(x)$ is equal to:

$\log(1+x)-\sum_{k=1}^{K}\frac{(-1)^{k-1}}{k}x^{k}=(-1)^{K}\int_{0}^{x}\frac{t^{K}}{1+t}dt.$

This result enables us to rewrite the function $f_{L}$ as:

$f_{L}(x)=\frac{1}{x^{L+1}}\int_{0}^{x}\frac{t^{L}}{1+t}dt.$

Using the change of variable $t=ux$, we obtain:

$f_{L}(x)=\int_{0}^{1}\frac{u^{L}}{1+xu}dt$

which is clearly decreasing for in $\mathbbm{R}^{+}$. This ends the proof. ∎

Finally, we also state the important change of measure lemma:

######  Lemma 11.

Change of measure. Let $g$ be a function of the parameter $\theta$ and data
$\mathcal{D}_{n}$, for any distribution Q that is P continuous, for any
$\delta\in(0,1]$, we have with probability $1-\delta$ :
$\displaystyle\mathbbm{E}_{\theta\sim
Q}[g(\theta,\mathcal{D}_{n})]\leq\mathcal{KL}(Q||P)+\ln\frac{\Psi_{g}}{\delta}$
(26) with $\Psi_{g}=\mathbbm{E}_{\mathcal{D}_{n}}\mathbbm{E}_{\theta\sim
P}[e^{g(\theta,\mathcal{D}_{n})}]$.

Lemma 11 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 [10]. With this
result, the recipe of constructing a generalisation bound reduces to choosing
an adequate function $g$ for which we can control $\Psi_{g}$.

##  Appendix E Additional results and discussions

###  E.1 A study of logarithmic smoothing estimator

Recall the form of the Logarithmic Smoothing estimator, defined for any
$\lambda\geq 0$:

$\displaystyle\hat{R}^{\lambda}_{n}(\pi)=-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
w_{\pi}(x_{i},a_{i})c_{i}\right)\,.$ (27)

Our estimator $\hat{R}^{\lambda}_{n}(\pi)$, is defined for a non-negative
$\lambda\geq 0$. In particular, $\lambda=0$ recovers the unbiased IPS
estimator in (2) and $\lambda>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. [9]. Indeed, $1/\lambda$ plays a
similar role to the clipping parameter $M$, as for any $i\in[n]$, we have:

$\displaystyle w_{\pi}(x_{i},a_{i})c_{i}\ll\frac{1}{\lambda}$
$\displaystyle\implies-\frac{1}{\lambda}\log\left(1-\lambda
w_{\pi}(x_{i},a_{i})c_{i}\right)\approx w_{\pi}(x_{i},a_{i})c_{i}.$
$\displaystyle w_{\pi}(x_{i},a_{i})c_{i}<M$
$\displaystyle\implies\min\left(w_{\pi}(x_{i},a_{i}),M\right)c_{i}=w_{\pi}(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 2. One can observe that once $\lambda>0$,
LS exhibits a bias-variance trade-off, with a declining bias with
$\lambda\rightarrow 0$. This is different than Clipping as no bias is suffered
once $M$ is bigger than the support of $x$, 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.

Figure 2: Comparison of Logarithmic Smoothing and Clipping.

We begin by defining the bias and variance of $\hat{R}^{\lambda}_{n}(\pi)$:

$\displaystyle\mathcal{B}^{\lambda}(\pi)=\mathbb{E}\left[\hat{R}^{\lambda}_{n}(\pi)\right]-R(\pi)\,,$
$\displaystyle\mathcal{V}^{\lambda}(\pi)=\mathbb{E}\left[\left(\hat{R}^{\lambda}_{n}(\pi)-\mathbb{E}\left[\hat{R}^{\lambda}_{n}(\pi)\right]\right)^{2}\right]\,.$
(28)

Moreover, for any $\lambda\geq 0$, we define the following quantity

$\displaystyle\mathcal{S}_{\lambda}(\pi)=\mathbb{E}\left[\frac{w_{\pi}(x,a)^{2}c^{2}}{1-\lambda
w_{\pi}(x,a)c}\right]\,,$ (29)

that will be essential in studying the properties of this estimator akin to
the coverage ratio used for the IX-estimator [20]. In the following, we study
the properties of our estimator $\hat{R}^{\lambda}_{n}(\pi)$ in (14). We start
with bounding its mean squared error (MSE), which involves bounding its bias
and variance.

######  Proposition 12 (Bias-variance trade-off).

Let $\pi\in\Pi$ and $\lambda\geq 0$. Then we have that $\displaystyle
0\leq\mathcal{B}^{\lambda}(\pi)\leq\lambda\mathcal{S}_{\lambda}(\pi)\,,\quad\text{and}\quad\mathcal{V}^{\lambda}(\pi)\leq\mathcal{S}_{\lambda}(\pi)/n\,.$
Moreover, it holds that for any $\lambda>0$:
$\mathcal{V}^{\lambda}(\pi)\leq\frac{\lvert
R(\pi)\rvert}{n\lambda}\leq\frac{1}{n\lambda}.$

###### Proof.

Let us start with bounding the bias. We have for any $\lambda\geq 0$:

$\displaystyle\mathcal{B}^{\lambda}(\pi)$
$\displaystyle=\mathbb{E}\left[\hat{R}^{\lambda}_{n}(\pi)\right]-R(\pi)$
$\displaystyle=\mathbb{E}\left[-\frac{1}{\lambda}\log(1-\lambda
w_{\pi}(x,a)c)-w_{\pi}(x,a)c\right]\quad(\text{IPS is unbiased}).$

Using $\log(1+x)\leq x$ for any $x\geq 0$ proves that the bias is positive.
For its upper bound, we use the following inequality
$\log(1+x)\geq\frac{x}{1+x}$ holding for $x\geq 0$:

$\displaystyle\mathcal{B}^{\lambda}(\pi)$
$\displaystyle=\mathbb{E}\left[-\frac{1}{\lambda}\log(1-\lambda
w_{\pi}(x,a)c)-w_{\pi}(x,a)c\right]$
$\displaystyle\leq\mathbb{E}\left[\frac{w_{\pi}(x,a)c}{1-\lambda
w_{\pi}(x,a)c}-w_{\pi}(x,a)c\right]=\lambda\mathbb{E}\left[\frac{(w_{\pi}(x,a)c)^{2}}{1-\lambda
w_{\pi}(x,a)c}\right]=\lambda\mathcal{S}_{\lambda}(\pi).$

Now focusing on the variance, we have:

$\displaystyle\mathcal{V}^{\lambda}(\pi)$
$\displaystyle=\mathbb{E}\left[\left(\hat{R}^{\lambda}_{n}(\pi)-\mathbb{E}\left[\hat{R}^{\lambda}_{n}(\pi)\right]\right)^{2}\right]$
$\displaystyle\leq\frac{1}{n\lambda^{2}}\mathbb{E}\left[\log(1-\lambda
w_{\pi}(x,a)c)^{2}\right].$

We use the following inequality $\log(1+x)\leq x/\sqrt{x+1}$ holding for
$x\geq 0$ to obtain our result:

$\displaystyle\mathcal{V}^{\lambda}(\pi)$
$\displaystyle\leq\frac{1}{n}\mathcal{S}_{\lambda}(\pi).$

Notice that once $\lambda>0$, we have:

$\displaystyle\mathcal{S}_{\lambda}(\pi)$
$\displaystyle=\mathbb{E}\left[\frac{w_{\pi}(x,a)^{2}c^{2}}{1-\lambda
w_{\pi}(x,a)c}\right]\leq\frac{1}{\lambda}\mathbb{E}\left[w_{\pi}(x,a)\lvert
c\rvert\right]=\frac{\lvert R(\pi)\rvert}{\lambda},$

resulting in a finite variance whenever $\lambda>0$:

$\displaystyle\mathcal{V}^{\lambda}(\pi)$ $\displaystyle\leq\frac{\lvert
R(\pi)\rvert}{n\lambda}\leq\frac{1}{n\lambda}.$

∎

$\lambda=0$ recovers the IPS estimator in (2), with zero bias and variance
bounded by $\mathbb{E}\left[w^{2}(x,a)c^{2}\right]/n$. When $\lambda>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
$\lambda\mathcal{S}_{\lambda}(\pi)$, which diminishes to zero when $\lambda$
is small and goes to $|R(\pi)|$ as $\lambda$ increases. Conversely, the
variance decreases with a higher $\lambda$. Notably, $\lambda>0$ ensures
finite variance bounded by $1/\lambda 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. [37] 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 13.

(Sub-Gaussianity). Let $\pi\in\Pi$, $\delta\in(0,1]$ and $\lambda>0$. Then the
following inequalities holds with probability at least $1-\delta$:
$\displaystyle
R(\pi)-\hat{R}^{\lambda}_{n}(\pi)\leq\frac{\ln(2/\delta)}{\lambda
n}\,,\qquad\text{and}\qquad\hat{R}^{\lambda}_{n}(\pi)-R(\pi)\leq\lambda\mathcal{S}_{\lambda}(\pi)+\frac{\ln(2/\delta)}{\lambda
n}\,.$ In particular, setting
$\lambda=\lambda_{*}=\sqrt{\ln(2/\delta)/n\mathbb{E}\left[w_{\pi}(x,a)^{2}c^{2}\right]}$
yields that
$\displaystyle|R(\pi)-\hat{R}^{\lambda_{*}}_{n}(\pi)|\leq\sqrt{2\sigma^{2}\ln(2/\delta)}\,,$
$\displaystyle\text{where
}\,\sigma^{2}=2\mathbb{E}\left[w_{\pi}(x,a)^{2}c^{2}\right]/n\,.$ (30)

###### Proof.

Let $\pi\in\Pi$, $\lambda>0$ and $\delta>0$. To prove sub-Gaussianity, we need
both upper bounds and lower bounds on $R(\pi)$ using
$\hat{R}^{\lambda}_{n}(\pi)$. For the upper bound, we can use the bound of
Corollary 4, and recall that $\psi_{\lambda}(x)\leq x$ for all $x$. We then
obtain with a probability $1-\delta$:

$\displaystyle
R(\pi)\leq\psi_{\lambda}\left(\hat{R}^{\lambda}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\right)\implies
R(\pi)-\hat{R}^{\lambda}_{n}(\pi)\leq\frac{\ln(1/\delta)}{\lambda n}.$

For the lower bound on the risk, we go back to our Chernoff Lemma 9, and use
the collection of i.i.d. random variable, that for any $i\in[n]$, are defined
as:

$\bar{X}_{i}=-\frac{1}{\lambda}\log\left(1-\lambda
w_{\pi}(x_{i},a_{i})c_{i}\right).$

This gives for $a\in\mathbbm{R}$:

$\displaystyle
P\left(\sum_{i\in[n]}\bar{X}_{i}>a\right)\leq\left(\mathbbm{E}\left[\exp\left(\lambda\bar{X}_{1}\right)\right]\right)^{n}\exp(-\lambda
a)$ $\displaystyle
P\left(\sum_{i\in[n]}\bar{X}_{i}>a\right)\leq\left(\mathbbm{E}\left[\frac{1}{1-\lambda
w_{\pi}(x,a)c}\right]\right)^{n}\exp(-\lambda a)$

Solving for $\delta=\left(\mathbbm{E}\left[\frac{1}{1-\lambda
w_{\pi}(x,a)c}\right]\right)^{n}\exp(-\lambda a)$, we get:

$\displaystyle
P\left(\frac{1}{n}\sum_{i\in[n]}\bar{X}_{i}>\frac{1}{\lambda}\log\left(\mathbbm{E}\left[\frac{1}{1-\lambda
w_{\pi}(x,a)c}\right]\right)+\frac{\ln(1/\delta)}{\lambda n}\right)\leq\delta$

The complementary event holds with at least probability $1-\delta$:

$\displaystyle\hat{R}^{\lambda}_{n}(\pi)\leq\frac{1}{\lambda}\log\left(\mathbbm{E}\left[\frac{1}{1-\lambda
w_{\pi}(x,a)c}\right]\right)+\frac{\ln(1/\delta)}{\lambda n},$

which implies using the inequality $\log(x)\leq x-1$ for all $x>0$:

$\displaystyle\hat{R}^{\lambda}_{n}(\pi)-R(\pi)$
$\displaystyle\leq\frac{1}{\lambda}\log\left(\mathbbm{E}\left[\frac{1}{1-\lambda
w_{\pi}(x,a)c}\right]\right)-R(\pi)+\frac{\ln(1/\delta)}{\lambda n}$
$\displaystyle\leq\frac{1}{\lambda}\left(\mathbbm{E}\left[\frac{1}{1-\lambda
w_{\pi}(x,a)c}\right]-1\right)-R(\pi)+\frac{\ln(1/\delta)}{\lambda n}$
$\displaystyle\leq\mathbbm{E}\left[\frac{w_{\pi}(x,a)c}{1-\lambda
w_{\pi}(x,a)c}-w_{\pi}(x,a)c\right]+\frac{\ln(1/\delta)}{\lambda n}$
$\displaystyle\leq\lambda\mathbbm{E}\left[\frac{w_{\pi}(x,a)^{2}c^{2}}{1-\lambda
w_{\pi}(x,a)c}\right]+\frac{\ln(1/\delta)}{\lambda
n}=\lambda\mathcal{S}_{\lambda}(\pi)+\frac{\ln(1/\delta)}{\lambda 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 $1-\delta$:

$\displaystyle
R(\pi)-\hat{R}^{\lambda}_{n}(\pi)\leq\frac{\ln(2/\delta)}{\lambda
n}\,,\qquad\text{and}\qquad\hat{R}^{\lambda}_{n}(\pi)-R(\pi)\leq\lambda\mathcal{S}_{\lambda}(\pi)+\frac{\ln(2/\delta)}{\lambda
n}\,,$

which implies that:

$\displaystyle\lvert
R(\pi)-\hat{R}^{\lambda}_{n}(\pi)\rvert\leq\lambda\mathcal{S}_{\lambda}(\pi)+\frac{\ln(2/\delta)}{\lambda
n}\,\leq\lambda\mathbb{E}\left[w_{\pi}(x,a)^{2}c^{2}\right]+\frac{\ln(2/\delta)}{\lambda
n}\,.$

This means that setting
$\lambda=\lambda_{*}=\sqrt{\ln(2/\delta)/n\mathbb{E}\left[w_{\pi}(x,a)^{2}c^{2}\right]}$
yields a sub-Gaussian concentration:

$|R(\pi)-\hat{R}^{\lambda_{*}}_{n}(\pi)|\leq
2\sqrt{\frac{\mathbb{E}\left[w_{\pi}(x,a)^{2}c^{2}\right]\ln(2/\delta)}{n}}\,.$

This ends the proof. ∎

From (30), $\hat{R}^{\lambda_{*}}_{n}(\pi)$ is sub-Gaussian with variance
proxy $\sigma^{2}=2\mathbb{E}\left[\omega(x,a)^{2}c^{2}\right]/n$, which is
lower that the variance proxy of the Harmonic estimator of Metelli et al.
[37].

###  E.2 OPE: Formal comparisons of the bounds

####  E.2.1 Comparison with empirical Bernstein

We begin by comparing the Second Moment Bound with Swaminathan and Joachims
[57]’s bound as they both manipulate similar quantities. The bound of [57]
uses the Empirical Bernstein bound of [35] applied to the Clipping Estimator.
We recall its expression below for a parameter $M>0$:

$\hat{R}^{M}_{n}(\pi)=\frac{1}{n}\sum_{i=1}^{n}\min\left\\{\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})},M\right\\}c_{i}.$

We also give below the Empirical Bernstein Bound applied to this estimator:

######  Proposition.

[Empirical Bernstein for Clipping of [57]] Let $\pi\in\Pi$, $\delta\in(0,1]$
and $M>0$. Then it holds with probability at least $1-\delta$ that
$\displaystyle
R(\pi)\leq\hat{R}^{M}_{n}(\pi)+\sqrt{\frac{2\hat{V}^{M}_{n}(\pi)\ln(2/\delta)}{n}}+\frac{7M\ln(2/\delta)}{3(n-1)}\,,$
(31) with $\hat{V}^{M}_{n}(\pi)$ the empirical variance of the clipping
estimator.

We are usually interested in the case where $\pi$ and $\pi_{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:

$\displaystyle\underbrace{\hat{V}^{M}_{n}(\pi)}_{\mathcal{O}(M)}$
$\displaystyle=\underbrace{\hat{\mathcal{M}}^{M,2}_{n}(\pi)}_{\mathcal{O}(M)}-\underbrace{\left(\hat{R}^{M}_{n}(\pi)\right)^{2}}_{\mathcal{O}(\bar{c}^{2})}$
$\displaystyle\approx\underbrace{\hat{\mathcal{M}}^{M,2}_{n}(\pi)}_{\mathcal{O}(M)}\quad(M\gg\bar{c}^{2}=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 3 with Clipping below:

$\displaystyle\psi_{\lambda}\Big{(}\hat{R}^{M}_{n}(\pi)+\frac{\lambda}{2}\hat{\mathcal{M}}^{M,2}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}\ $
$\displaystyle\leq\hat{R}^{M}_{n}(\pi)+\frac{\lambda}{2}\hat{\mathcal{M}}^{M,2}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\quad(\psi_{\lambda}(x)\leq x,\forall x)$
$\displaystyle\leq\hat{R}^{M}_{n}(\pi)+\frac{\lambda}{2}\hat{\mathcal{M}}^{M,2}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}.$

Choosing a
$\lambda\approx\sqrt{2\ln(1/\delta)/(n\hat{\mathcal{M}}^{M,2}_{n}(\pi))}$
gives us an upper bound that is close to:

$\displaystyle\hat{R}^{M}_{n}(\pi)+\frac{\lambda}{2}\hat{\mathcal{M}}^{M,2}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}$
$\displaystyle\approx\hat{R}^{M}_{n}(\pi)+\sqrt{\frac{2\hat{\mathcal{M}}^{M,2}_{n}(\pi)\ln(1/\delta)}{n}}$
$\displaystyle\approx\hat{R}^{M}_{n}(\pi)+\sqrt{\frac{2\hat{V}^{M}_{n}(\pi)\ln(1/\delta)}{n}}$
$\displaystyle\leq\hat{R}^{M}_{n}(\pi)+\sqrt{\frac{2\hat{V}^{M}_{n}(\pi)\ln(2/\delta)}{n}}+\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\frac{7M\ln(2/\delta)}{3(n-1)}}.$

This means that in practical scenarios, and with a good choice of
$\lambda\sim\mathcal{O}(1/\sqrt{n})$, the Second Moment bound would be better
than the Empirical Bernstein bound, and this difference will be even greater
when $M\gg 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 5.

####  E.2.2 Comparison with the IX bound

We now attack the recently derived IX bound in Gabbianelli et al. [20] and
show that our newly proposed bound dominates it in all scenarios.

######  Proposition 14.

(Comparison with IX [20]) Let $\pi\in\Pi$, $\delta\in]0,1]$ and $\lambda>0$,
the IX bound from [20] states that we have with at least probability
$1-\delta$: $\displaystyle
R(\pi)\leq\hat{R}^{IX-\lambda}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda n}$ (32)
with:
$\hat{R}^{IX-\lambda}_{n}(\pi)=\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})+\lambda/2}c_{i}.$
Let $U^{\lambda}_{IX}(\pi)$ be the upper bound given of (32), we have for any
$\lambda>0$: $\displaystyle U^{\lambda}_{\infty}(\pi)\leq
U^{\lambda}_{IX}(\pi)\,.$ (33)

###### Proof.

Let $\pi\in\Pi$, $\delta\in]0,1]$ and $\lambda>0$. Recall that
$U^{\lambda}_{\infty}(\pi)=\psi_{\lambda}\Big{(}\hat{R}^{\lambda}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}$. We have:

$\displaystyle\psi_{\lambda}\Big{(}\hat{R}^{\lambda}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}$
$\displaystyle\leq\hat{R}^{\lambda}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\quad(\forall x,\psi_{\lambda}(x)\leq x)$
$\displaystyle\leq-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
w_{\pi}(x_{i},a_{i})c_{i}\right)+\frac{\ln(1/\delta)}{\lambda n}.$

Using the inequality $\log(1+x)\geq\frac{x}{1+x/2}$ for all $x>0$, we get:

$\displaystyle U^{\lambda}_{\infty}(\pi)$
$\displaystyle\leq-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
w_{\pi}(x_{i},a_{i})c_{i}\right)+\frac{\ln(1/\delta)}{\lambda n}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\frac{w_{\pi}(x_{i},a_{i})}{1-\lambda
w_{\pi}(x_{i},a_{i})c_{i}/2}c_{i}+\frac{\ln(1/\delta)}{\lambda
n}\quad\left(\log(1+x)\geq\frac{x}{1+x/2}\right)$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})-\lambda\pi(a_{i}|x_{i})c_{i}/2}c_{i}+\frac{\ln(1/\delta)}{\lambda
n}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})+\lambda/2}c_{i}+\frac{\ln(1/\delta)}{\lambda
n}\quad\left(-\pi(a_{i}|x_{i})c_{i}\leq 1\text{ and }c_{i}\leq 0\right)$
$\displaystyle\leq\hat{R}^{IX-\lambda}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}=U^{\lambda}_{IX}(\pi),$

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

The use of $\psi_{\lambda}(x)\leq x,\forall x$.

  2. 2.

The use of $\log(1+\lambda x)\geq\frac{\lambda x}{1+\lambda x/2},\forall x\geq
0$.

  3. 3.

The use of $-\pi(a_{i}|x_{i})c_{i}\leq 1,\forall i\in[n]$.

The two first inequalities are loose when $\lambda\sim 1/\sqrt{n}$ is not too
small, which means that LS will be much better in problems with few samples.
The third inequality is loose when $\pi$ 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.

###  E.3 OPS: Formal comparison with IX suboptimality

Let us begin by stating results from the IX work [20]. Recall that the IX
estimator is defined for any $\lambda>0$, by:

$\hat{R}^{IX-\lambda}_{n}(\pi)=\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})+\lambda/2}c_{i}.$

Let $\Pi_{\textsc{s}}=\\{\pi_{1},...,\pi_{m}\\}$ be a finite set of predefined
policies. In OPS, the goal is to find
$\pi_{*}^{\textsc{s}}\in\Pi_{\textsc{s}}$ that satisfies

$\textstyle\pi_{*}^{\textsc{s}}=\operatorname*{argmin}_{\pi\in\Pi_{\textsc{s}}}R(\pi)=\operatorname*{argmin}_{k\in[m]}R(\pi_{k})\,.$

for $\lambda>0$, the selection strategy suggested in Gabbianelli et al. [20]
was to search for:

$\displaystyle\hat{\pi}_{n}^{\textsc{s},IX}=\operatorname*{argmin}_{\pi\in\Pi_{\textsc{s}}}\hat{R}^{IX-\lambda}_{n}(\pi)=\operatorname*{argmin}_{k\in[m]}\hat{R}^{IX-\lambda}_{n}(\pi_{k})\,.$
(34)

######  Proposition 15.

(Suboptimality of the IX selection strategy. Let $\lambda>0$ and
$\delta\in(0,1]$. Then, it holds with probability at least $1-\delta$ that
$\displaystyle 0\leq
R(\hat{\pi}_{n}^{\textsc{s},IX})-R(\pi_{*}^{\textsc{s}})\leq\lambda\mathcal{C}_{\lambda/2}(\pi_{*}^{\textsc{s}})+\frac{2\ln(2|\Pi_{\textsc{s}}|/\delta)}{\lambda
n}\,,$ (35) where
$\mathcal{C}_{\lambda}(\pi)=\mathbb{E}\left[\frac{\pi(a|x)}{\pi^{2}_{0}(a|x)+\lambda\pi_{0}(a|x)}\lvert
c\rvert\right].$

Both suboptimalities (LS and IX) have the same form, they only depend on two
different quantities ($\mathcal{S}_{\lambda}$ and $\mathcal{C}_{\lambda}$
respectively). For a $\pi\in\Pi$ and $\lambda>0$, If we can identify when
$\mathcal{S}_{\lambda}(\pi)\leq\mathcal{C}_{\lambda/2}(\pi)$, 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 $\pi\in\Pi$ and $\lambda>0$. We have:
$\displaystyle\mathcal{S}_{\lambda}(\pi)\leq\mathcal{C}_{\lambda/2}(\pi).$
(36)

###### Proof.

Let $\pi\in\Pi$ and $\lambda>0$, we have:

$\displaystyle\mathcal{C}_{\lambda/2}(\pi)-\mathcal{S}_{\lambda}(\pi)$
$\displaystyle=\mathbb{E}\left[\frac{\pi(a|x)}{\pi^{2}_{0}(a|x)+\frac{\lambda}{2}\pi_{0}(a|x)}\lvert
c\rvert-\frac{w_{\pi}(x,a)^{2}c^{2}}{1-\lambda w_{\pi}(x,a)c}\right]$
$\displaystyle=\mathbb{E}\left[\frac{\pi(a|x)}{\pi^{2}_{0}(a|x)+\frac{\lambda}{2}\pi_{0}(a|x)}\lvert
c\rvert-\frac{\pi(a|x)^{2}c^{2}}{\pi^{2}_{0}(a|x)-\lambda\pi_{0}(a|x)\pi(a|x)c}\right]$
$\displaystyle=\mathbb{E}\left[\pi(a|x)\lvert
c\rvert\left(\frac{1}{\pi^{2}_{0}(a|x)+\frac{\lambda}{2}\pi_{0}(a|x)}-\frac{\pi(a|x)|c|}{\pi^{2}_{0}(a|x)+\lambda\pi_{0}(a|x)\pi(a|x)\lvert
c\rvert}\right)\right]$ $\displaystyle=\mathbb{E}\left[\pi(a|x)\lvert
c\rvert\left(\frac{\pi^{2}_{0}(a|x)\left(1-\pi(a|x)|c|\right)+\frac{\lambda}{2}\pi_{0}(a|x)\pi(a|x)\lvert
c\rvert}{(\pi^{2}_{0}(a|x)+\frac{\lambda}{2}\pi_{0}(a|x))(\pi^{2}_{0}(a|x)+\lambda\pi_{0}(a|x)\pi(a|x)\lvert
c\rvert)}\right)\right]$ $\displaystyle\geq 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. [20], pessimistic algorithms tend to have
the property that their regret scales with the minimax sample complexity of
estimating the value of the optimal policy [26]. For the case of multi-armed
bandit (one context $x$), this estimation minimax sample complexity is proved
by Li et al. [33] and is of the rate
$\mathcal{O}(\mathbb{E}[w_{\pi^{*}}(x,a)^{2}c^{2}])$, with $\pi^{*}$ being the
optimal policy. Our bound matches the lower bound proved by Li et al. [33],
as:

$\displaystyle\mathcal{S}_{\lambda}(\pi^{*})=\mathbb{E}\left[\frac{w_{\pi^{*}}(x,a)^{2}c^{2}}{1-\lambda
w_{\pi^{*}}(x,a)c}\right]\leq\mathbb{E}\left[w_{\pi^{*}}(x,a)^{2}c^{2}\right],$

which is not the case for the suboptimality of IX, that only matches it in the
deterministic setting with binary costs, as:

$\displaystyle\mathcal{C}_{\lambda}(\pi^{*})$
$\displaystyle=\mathbb{E}\left[\frac{\pi^{*}(a|x)}{\pi^{2}_{0}(a|x)+\lambda\pi_{0}(a|x)}\lvert
c\rvert\right]\leq\mathbb{E}\left[\frac{\pi^{*}(a|x)}{\pi^{2}_{0}(a|x)}\lvert
c\rvert\right]=\mathbb{E}\left[\left(\frac{\pi^{*}(a|x)}{\pi_{0}(a|x)}\right)^{2}c^{2}\right],$

with the last inequality only holding when $\pi^{*}$ 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. [27, Theorem 4.4], matched for both IX and LS.

###  E.4 OPL: Formal comparison of PAC-Bayesian bounds

As it is easier to work with linear estimators within the PAC-Bayesian
framework, we define the following estimator of the risk
$\hat{R}^{p-\textsc{LIN}}_{n}(\pi)$, with the help of a function
$p:\mathbbm{R}\rightarrow\mathbbm{R}$ as:

$\hat{R}^{p-\textsc{LIN}}_{n}(\pi)=\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{p(\pi_{0}(a_{i}|x_{i}))}c_{i}$

with the only condition on $p$ to be
$\\{\boldsymbol{C^{\textsc{LIN}}_{1}}:\forall x,p(x)\geq x\\}$. This condition
helps us control the impact of actions with low probabilities under $\pi_{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\geq 1$. Given a prior $P$ on $\mathcal{F}_{\Theta}$, $\delta\in(0,1]$
and $\lambda>0$, the following bound holds with probability at least
$1-\delta$ uniformly for all distribution $Q$ over $\mathcal{F}_{\Theta}$:
$\displaystyle
R(\pi_{Q})\leq\psi_{\lambda}\left(\hat{R}^{p-\textsc{LIN}}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{p-\textsc{LIN},\ell}_{n}(\pi_{Q})\right)$
(37) with: $\displaystyle\hat{\mathcal{M}}^{p-\textsc{LIN},\ell}_{n}(\pi_{Q})$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\frac{\pi_{Q}(a_{i}|x_{i})}{p(\pi_{0}(a_{i}|x_{i}))^{\ell}}c_{i}^{\ell}$
$\displaystyle\psi_{\lambda}$
$\displaystyle=x:\rightarrow\frac{1-\exp(-\lambda x)}{\lambda}.$

###### Proof.

Let $L\geq 1$, we have from Lemma 10, and for any positive random variable
$X\geq 0$ and $\lambda>0$:

$f_{2L-1}(0)=\frac{1}{2L}\geq f_{2L-1}(\lambda X)=-\frac{\log(1+\lambda
X)-\sum_{\ell=1}^{2L-1}\frac{(-1)^{\ell-1}}{\ell}(\lambda X)^{\ell}}{(\lambda
X)^{2L}}$

which is equivalent to:

$\displaystyle\sum_{\ell=1}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\leq\log(1+\lambda X)$
$\displaystyle\iff\exp\left(\sum_{\ell=1}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\right)\leq 1+\lambda X$
$\displaystyle\implies\mathbbm{E}\left[\exp\left(\sum_{\ell=1}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\right)\right]\leq 1+\mathbbm{E}\left[\lambda X\right]$
$\displaystyle\implies\mathbbm{E}\left[\exp\left(\sum_{\ell=1}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\right)\right]\leq\exp\left(\log(1+\mathbbm{E}\left[\lambda
X\right])\right)$
$\displaystyle\implies\mathbbm{E}\left[\exp\left(\lambda(X-\frac{1}{\lambda}\log(1+\mathbbm{E}\left[\lambda
X\right]))+\sum_{\ell=2}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\right)\right]\leq 1.$

For any $X\leq 0$, we can inject $-X\geq 0$ to obtain:

$\displaystyle\forall X\leq
0,\quad\mathbbm{E}\left[\exp\left(\lambda\left(-\frac{1}{\lambda}\log(1+\mathbbm{E}\left[\lambda
X\right])-X\right)-\sum_{k=2}^{2K}\frac{1}{k}(\lambda X)^{k}\right)\right]\leq
1.$ (38)

Let:

$\displaystyle
d_{\theta}(a|x)=\mathbbm{1}\left[f_{\theta}(x)=a\right]\,,\forall(x,a)\in\mathcal{X}\times\mathcal{A}\,,$

it means that:

$\displaystyle\pi_{Q}(a|x)=\mathbb{E}_{\theta\sim
Q}\left[d_{\theta}(a|x)\right]\,,$
$\displaystyle\forall(x,a)\in\mathcal{X}\times\mathcal{A}\,.$

Let $\lambda>0$. The adequate function $g$ we are going to use in combination
with Lemma 11 is:

$\displaystyle g(\theta,\mathcal{D}_{n})$
$\displaystyle=\sum_{i=1}^{n}\lambda\left(-\frac{1}{\lambda}\log(1+\lambda
R^{p-\textsc{LIN}}(d_{\theta}))-\frac{d_{\theta}(a_{i}|x_{i})}{p(\pi_{0}(a_{i}|x_{i}))}c_{i}\right)-\sum_{\ell=2}^{2L}\frac{1}{\ell}\left(\lambda\frac{d_{\theta}(a_{i}|x_{i})}{p(\pi_{0}(a_{i}|x_{i}))}c_{i}\right)^{\ell}$
$\displaystyle=\sum_{i=1}^{n}\lambda\left(-\frac{1}{\lambda}\log(1+\lambda
R^{p-\textsc{LIN}}(d_{\theta}))-\frac{d_{\theta}(a_{i}|x_{i})}{p(\pi_{0}(a_{i}|x_{i}))}c_{i}\right)-\sum_{\ell=2}^{2L}\frac{d_{\theta}(a_{i}|x_{i})}{\ell}\left(\frac{\lambda}{p(\pi_{0}(a_{i}|x_{i}))}c_{i}\right)^{\ell}.$

By exploiting the i.i.d. nature of the data and exchanging the order of
expectations ($P$ is independent of $\mathcal{D}_{n}$), we can naturally prove
using (38) that:

$\displaystyle\Psi_{g}=\mathbbm{E}_{P}\left[\prod_{i=1}^{n}\mathbbm{E}\left[\exp\left(\lambda\left(-\frac{1}{\lambda}\log(1+\lambda
R^{p-\textsc{LIN}}(d_{\theta}))-\frac{d_{\theta}(a_{i}|x_{i})}{p(\pi_{0}(a_{i}|x_{i}))}c_{i}\right)-\sum_{k=2}^{2K}\frac{1}{k}\left(\lambda\frac{d_{\theta}(a_{i}|x_{i})}{p(\pi_{0}(a_{i}|x_{i}))}c_{i}\right)^{k}\right)\right]\right]\leq
1,$

as we have :

$\frac{d_{\theta}(a_{i}|x_{i})}{p(\pi_{0}(a_{i}|x_{i}))}c_{i}\leq
0\quad\forall i.$

Injecting $\Psi_{g}$ in Lemma 11, rearranging terms and using that
$\hat{R}^{p-\textsc{LIN}}_{n}(\pi)$ 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 $\mathcal{F}_{\Theta}$, $\delta\in(0,1]$ and $\lambda>0$.
The following bound holds with probability at least $1-\delta$ uniformly for
all distribution $Q$ over $\mathcal{F}_{\Theta}$: $\displaystyle
R(\pi_{Q})\leq\psi_{\lambda}\left(\hat{R}^{p}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}+\frac{\lambda}{2}\hat{\mathcal{M}}^{p-\textsc{LIN},2}_{n}(\pi_{Q})\right).$
(39)

##### Log Smoothing PAC-Bayesian Bound.

With $L\rightarrow\infty$, we obtain the following:

######  Proposition 19.

$\hat{R}^{\lambda-\textsc{LIN}}_{n}$ PAC-Bayes bound:
Given a prior $P$ on $\mathcal{F}_{\Theta}$, $\delta\in(0,1]$ and $\lambda>0$,
the following bound holds with probability at least $1-\delta$ uniformly for
all distribution $Q$ over $\mathcal{F}_{\Theta}$: $\displaystyle
R(\pi_{Q})\leq\psi_{\lambda}\left(\hat{R}^{\lambda-\textsc{LIN}}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}\right).$ (40) with:
$\displaystyle\hat{R}^{\lambda\textsc{-lin}}_{n}(\pi)=-\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{\lambda}\log\left(1-\frac{\lambda
c_{i}}{\pi_{0}(a_{i}|x_{i})}\right).$

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\rightarrow\max(x,\tau)$). For a policy $\pi_{Q}$ and a $\lambda>0$,
we have:

$\displaystyle R(\pi_{Q})$
$\displaystyle\leq\hat{R}^{\tau}_{n}(\pi_{Q})+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\sqrt{\frac{\mathcal{KL}(Q||P)+\ln\frac{4\sqrt{n}}{\delta}}{2n}}}}+\frac{\mathcal{KL}(Q||P)+\ln\frac{2}{\delta}}{\lambda
n}+\lambda{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{g\left(\lambda/\tau\right)\mathcal{V}_{n}^{\tau}(\pi_{Q})}}.$
(c-Bern) $\displaystyle R(\pi_{Q})$
$\displaystyle\leq\hat{R}^{\tau}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}+\frac{\lambda}{2}\hat{\mathcal{S}}^{\tau}_{n}(\pi_{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(\lambda/\tau)$ is always bigger than $1/2$, and
diverges when $\tau\rightarrow 0$.

  * •

With enough data ($n\gg 1$), we also have:

$\hat{\mathcal{S}}^{\tau}_{n}(\pi_{Q})\approx\mathbbm{E}\left[\frac{\pi_{Q}(a|x)}{\max\\{\pi_{0}(a|x),\tau\\}^{2}}c(a,x)^{2}\right]\leq\mathbbm{E}\left[\frac{\pi_{Q}(a|x)}{\max\\{\pi_{0}(a|x),\tau\\}^{2}}\right]\approx\mathcal{V}_{n}^{\tau}(\pi_{Q}).$

These observations confirm that the new bound derived with $L=1$ is tighter
than what was previously proposed for cIPS, especially when $n\gg 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\rightarrow x^{\alpha}$) with $\alpha\in[0,1]$:

$\displaystyle R(\pi_{Q})$
$\displaystyle\leq\hat{R}^{\alpha}_{n}(\pi_{Q})+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\sqrt{\frac{\mathcal{KL}(Q||P)+\ln\frac{4\sqrt{n}}{\delta}}{2n}}}}+\frac{\mathcal{KL}(Q||P)+\ln\frac{2}{\delta}}{\lambda
n}+\frac{\lambda}{2}\left({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\mathcal{V}_{n}^{\alpha}(\pi_{Q})}}+\hat{\mathcal{S}}^{\alpha}_{n}(\pi_{Q})\right).$
($\alpha$-Smooth) $\displaystyle R(\pi_{Q})$
$\displaystyle\leq\hat{R}^{\alpha}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}+\frac{\lambda}{2}\hat{\mathcal{S}}^{\alpha}_{n}(\pi_{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 $\pi_{0}$ (contrary to the previous bounds that have
$\mathcal{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\rightarrow\infty$ 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. [20]. Indeed, using
$\log(1+x)\geq\frac{x}{1+x/2}$ for all $x\geq 0$, we have for any
$P,Q\in\mathcal{P}(\Theta)$ and $\lambda>0$:

$\displaystyle\psi_{\lambda}\left(\hat{R}^{\lambda-\textsc{LIN}}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}\right)$
$\displaystyle\leq\hat{R}^{\lambda-\textsc{LIN}}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}$
$\displaystyle\leq-\frac{1}{n}\sum_{i=1}^{n}\frac{\pi_{Q}(a_{i}|x_{i})}{\lambda}\log\left(1-\frac{\lambda
c_{i}}{\pi_{0}(a_{i}|x_{i})}\right)+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n}$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\frac{\pi_{Q}(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})-\lambda
c_{i}/2}+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda n}$
$\displaystyle\leq\hat{R}^{\lambda-\textsc{IX}}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)+\ln\frac{1}{\delta}}{\lambda
n},$ (IX-bound)

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

###  E.5 OPL: Formal comparison with IX PAC-Bayesian learning suboptimality

Let us begin by stating results from the IX work [20]. Recall that the IX
estimator is defined for any $\lambda>0$, by:

$\hat{R}^{\textsc{IX}-\lambda}_{n}(\pi)=\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})+\lambda/2}c_{i},$

and that we used the linearized version of the LS estimator, LS-LIN defined
as:

$\displaystyle\hat{R}^{\lambda\textsc{-lin}}_{n}(\pi)=-\frac{1}{n}\sum_{i=1}^{n}\frac{\pi(a_{i}|x_{i})}{\lambda}\log\left(1-\frac{\lambda
c_{i}}{\pi_{0}(a_{i}|x_{i})}\right).$

Let $\Theta$ be a parameter space and $\mathcal{P}(\Theta)$ be the set of all
probability distribution on $\Theta$. Our goal is to find the best policy in a
chosen class $\mathcal{L}(\Theta)\subset\mathcal{P}(\Theta)$:

$\pi_{Q^{*}}=\operatorname*{argmin}_{Q\in\mathcal{L}(\Theta)}R(\pi_{Q}).$

For $\lambda>0$ and a prior $P\in\mathcal{P}(\Theta)$, the PAC-Bayesian
learning strategy suggested in Gabbianelli et al. [20] is to find in
$\mathcal{L}(\Theta)\subset\mathcal{P}(\Theta)$:

$\displaystyle\hat{\pi}^{\textsc{IX}}_{Q_{n}}=\operatorname*{argmin}_{Q\in\mathcal{L}(\Theta)}\left\\{\hat{R}^{\textsc{IX}-\lambda}_{n}(\pi_{Q})+\frac{\mathcal{KL}(Q||P)}{\lambda
n}\right\\}.$

This learning strategy suffers from a suboptimality bounded in the result
below:

######  Proposition 20.

(Suboptimality of the IX PAC-Bayesian learning strategy from [20]. Let
$\lambda>0$ and $\delta\in(0,1]$. Then, it holds with probability at least
$1-\delta$ that $\displaystyle 0\leq
R(\hat{\pi}^{\textsc{IX}}_{Q_{n}})-R(\pi_{Q^{*}})\leq\lambda\mathcal{C}_{\lambda/2}(\pi_{Q^{*}})+\frac{2\left(\mathcal{KL}(Q^{*}||P)+\ln(2/\delta)\right)}{\lambda
n}\,,$ where
$\mathcal{C}_{\lambda}(\pi)=\mathbb{E}\left[\frac{\pi(a|x)}{\pi^{2}_{0}(a|x)+\lambda\pi_{0}(a|x)}\lvert
c\rvert\right].$

Similarly for PAC-Bayesian learning, both suboptimalities (LS and IX) have the
same form, they only depend on two different quantities
($\mathcal{S}^{\textsc{LIN}}_{\lambda}$ and $\mathcal{C}_{\lambda}$
respectively). For a $\pi\in\Pi$ and $\lambda>0$, If we can identify when
$\mathcal{S}^{\textsc{LIN}}_{\lambda}(\pi)\leq\mathcal{C}_{\lambda/2}(\pi)$,
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 $\pi\in\Pi$ and $\lambda>0$. We have:
$\displaystyle\mathcal{S}^{\textsc{LIN}}_{\lambda}(\pi)\leq\mathcal{C}_{\lambda/2}(\pi).$
(41)

###### Proof.

Let $\pi\in\Pi$ and $\lambda>0$, and recall that:

$\mathcal{S}^{{\texttt{LIN}}}_{\lambda}(\pi)=\mathbb{E}\left[\frac{\pi(a|x)c^{2}}{\pi^{2}_{0}(a|x)-\lambda\pi_{0}(a|x)c}\right].$

We have:

$\displaystyle\mathcal{C}_{\lambda/2}(\pi)-\mathcal{S}^{\textsc{LIN}}_{\lambda}(\pi)$
$\displaystyle=\mathbb{E}\left[\frac{\pi(a|x)}{\pi^{2}_{0}(a|x)+\frac{\lambda}{2}\pi_{0}(a|x)}\lvert
c\rvert-\frac{\pi(a|x)c^{2}}{\pi^{2}_{0}(a|x)-\lambda\pi_{0}(a|x)c}\right]$
$\displaystyle=\mathbb{E}\left[\pi(a|x)\lvert
c\rvert\left(\frac{1}{\pi^{2}_{0}(a|x)+\frac{\lambda}{2}\pi_{0}(a|x)}-\frac{|c|}{\pi^{2}_{0}(a|x)+\lambda\pi_{0}(a|x)\lvert
c\rvert}\right)\right]$ $\displaystyle=\mathbb{E}\left[\pi(a|x)\lvert
c\rvert\left(\frac{\pi^{2}_{0}(a|x)\left(1-|c|\right)+\frac{\lambda}{2}\pi_{0}(a|x)\lvert
c\rvert}{(\pi^{2}_{0}(a|x)+\frac{\lambda}{2}\pi_{0}(a|x))(\pi^{2}_{0}(a|x)+\lambda\pi_{0}(a|x)\lvert
c\rvert)}\right)\right]$ $\displaystyle\geq 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. [27, Theorem 4.4] we can state that the minimax suboptimality
lower bound, in the case of deterministic optimal policies is of the rate
$\mathcal{O}(1/\sqrt{nC^{*}})$ with
$\inf_{x\in\mathcal{X}}\pi_{0}(\pi^{*}(x)|x)>C^{*}$. Our bound as well as IX
bound match this minimax lower bound, as:

$\displaystyle\mathcal{S}^{\texttt{LIN}}_{\lambda}(\pi^{*})$
$\displaystyle=\mathbb{E}_{x,c}\left[\frac{c^{2}}{\pi_{0}(\pi^{*}(x)|x)-\lambda
c}\right]\leq\frac{1}{C^{*}}$ $\displaystyle\mathcal{C}_{\lambda}(\pi^{*})$
$\displaystyle=\mathbb{E}_{x,c}\left[\frac{\lvert
c\rvert}{\pi_{0}(\pi^{*}(x)|x)+\lambda}\right]\leq\frac{1}{C^{*}}.$

One can see that for both, selecting a

$\lambda^{*}=\sqrt{\frac{2\left(\mathcal{KL}(Q^{*}||P)+\ln(2/\delta)\right)C^{*}}{n}},$

gets you the desired bound, matching this minimax rate.

##  Appendix F Proofs of OPE

###  F.1 Proof of high order empirical moments bound (Proposition 1)

######  Proposition.

(Empirical moments risk bound). Let $\pi\in\Pi$, $L\geq 1$, $\delta\in(0,1]$
and $\lambda>0$. Then it holds with probability at least $1-\delta$ that
$\displaystyle
R(\pi)\leq\psi_{\lambda}\Big{(}\hat{R}^{h}_{n}(\pi)+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}\,,$ where $\psi_{\lambda}$ and $\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)$
are defined in (7) and (6), respectively, and recall that
$\psi_{\lambda}(x)\leq x$.

###### Proof.

Let $L\in\mathbbm{N}^{*}$, $\lambda>0$ and $X\geq 0$ a positive random
variable. We have $2L-1\geq 1$, and with the decreasing nature of $f_{(2L-1)}$
(Lemma 10), we also have:

$\displaystyle f_{(2L-1)}(0)\geq f_{2L-1}(\lambda X)$
$\displaystyle\iff\frac{1}{2L}\geq-\frac{\log(1+\lambda
X)-\sum_{l=1}^{2L-1}\frac{(-1)^{\ell-1}}{k}(\lambda X)^{\ell}}{(\lambda
X)^{2L}}$ $\displaystyle\iff\sum_{\ell=1}^{2L}\frac{(-1)^{\ell-1}}{k}(\lambda
X)^{\ell}\leq\log(1+\lambda X)$
$\displaystyle\iff\exp\left(\sum_{\ell=1}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\right)\leq 1+\lambda X$
$\displaystyle\implies\mathbbm{E}\left[\exp\left(\sum_{\ell=1}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\right)\right]\leq 1+\lambda\mathbbm{E}\left[X\right]$
$\displaystyle\implies\mathbbm{E}\left[\exp\left(\sum_{\ell=1}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\right)\right]\leq\exp\left(\left(\log(1+\lambda\mathbbm{E}\left[X\right]\right)\right)$
$\displaystyle\implies\mathbbm{E}\left[\exp\left(\lambda(X-\frac{1}{\lambda}\log\left(1+\lambda\mathbbm{E}\left[X\right]\right))+\sum_{\ell=2}^{2L}\frac{(-1)^{\ell-1}}{\ell}(\lambda
X)^{\ell}\right)\right]\leq 1.$

For any $X\leq 0$, we can inject $-X\geq 0$ to obtain:

$\displaystyle\forall X\leq
0,\quad\mathbbm{E}\left[\exp\left(\lambda\left(-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[X\right]\right)-X\right)-\sum_{\ell=2}^{2L}\frac{1}{\ell}(\lambda
X)^{\ell}\right)\right]\leq 1.$ (42)

The result in Equation (42) will be combined with Chernoff Inequality (Lemma
9) to finally prove our bound. Let $\lambda>0$, for our problem, we define the
random variable $X_{i}$ to use in the Chernoff Inequality as:

$\displaystyle X_{i}$
$\displaystyle=-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)-h_{i}-\sum_{\ell=2}^{2L}\frac{1}{\ell}(\lambda
h_{i})^{\ell}.$

For any $a\in\mathbbm{R}$, this gives us the following:

$\displaystyle
P\left(\sum_{i\in[n]}X_{i}>a\right)\leq\left(\mathbbm{E}\left[\exp\left(\lambda
X_{1}\right)\right]\right)^{n}\exp(-\lambda a)$ $\displaystyle
P\left(-\frac{n}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)-\sum_{i\in[n]}\left(h_{i}+\sum_{\ell=2}^{2L}\frac{1}{\ell}(\lambda
h_{i})^{\ell}\right)>a\right)\leq\left(\mathbbm{E}\left[\exp\left(\lambda
X_{1}\right)\right]\right)^{n}\exp(-\lambda a)$ $\displaystyle
P\left(-\frac{n}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)-\sum_{i\in[n]}\left(h_{i}+\sum_{\ell=2}^{2L}\frac{1}{\ell}(\lambda
h_{i})^{\ell}\right)>a\right)\leq\exp(-\lambda a)\quad(\text{Use of
Equation~{}\eqref{app:mgf_new}})$

Solving for $\delta=\exp(-\lambda a)$, we get:

$\displaystyle
P\left(-\frac{n}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)-\sum_{i\in[n]}\left(h_{i}+\sum_{\ell=2}^{2L}\frac{1}{\ell}(\lambda
h_{i})^{\ell}\right)>\frac{\ln(1/\delta)}{\lambda}\right)\leq\delta$
$\displaystyle
P\left(-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)-\frac{1}{n}\sum_{i\in[n]}\left(h_{i}+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell}}{\ell}h_{i}^{\ell}\right)>\frac{\ln(1/\delta)}{\lambda
n}\right)\leq\delta$ $\displaystyle
P\left(-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)-\hat{R}^{h}_{n}(\pi)-\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)>\frac{\ln(1/\delta)}{\lambda
n}\right)\leq\delta$ $\displaystyle
P\left(-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)>\hat{R}^{h}_{n}(\pi)+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)\frac{\ln(1/\delta)}{\lambda
n}\right)\leq\delta.$

This means that the following, complementary event will hold with probability
at least $1-\delta$:

$\displaystyle-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)\leq\hat{R}^{h}_{n}(\pi)+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)\frac{\ln(1/\delta)}{\lambda
n}.$

$\psi_{\lambda}$ being a non-decreasing function, applying it to the two sides
of this inequality gives us:

$\displaystyle\mathbbm{E}\left[h\right]\leq\psi_{\lambda}\Big{(}\hat{R}^{h}_{n}(\pi)+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}.$

Finally, $h$ satisfies (C1), this means that the bound is also an upper bound
on the true risk, giving:

$\displaystyle
R(\pi)\leq\psi_{\lambda}\Big{(}\hat{R}^{h}_{n}(\pi)+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}\,,$

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 $\pi\in\Pi$, $\delta\in(0,1]$, $\lambda>0$, and $L\geq 1$. Let
$U^{\lambda,h}_{L}(\pi)=\psi_{\lambda}\left(\hat{R}^{h}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}+\sum_{\ell=2}^{2L}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)\right)$
be the upper bound in Equation 8. Then,
$\displaystyle\lambda\leq\min_{i\in[n]}\left\\{\frac{2L+2}{(2L+1)|h_{i}|}\right\\}\implies
U^{\lambda,h}_{L+1}(\pi)\leq U^{\lambda,h}_{L}(\pi)\,.$ (43) which implies
that: $\lambda\leq\min_{i\in[n]}\left\\{\frac{1}{|h_{i}|}\right\\}\implies
U^{\lambda,h}_{L}(\pi)\text{ is a decreasing function w.r.t $L$.}$

###### Proof.

We want to prove the implication (43) from which the condition on the
decreasing nature of our bound will follow. Indeed, Let us suppose that (43)
is true, we have:

$\displaystyle\lambda\leq\min_{i\in[n]}\left\\{\frac{1}{|h_{i}|}\right\\}$
$\displaystyle\implies\forall L\geq
1,\quad\lambda\leq\min_{i\in[n]}\left\\{\frac{2L+2}{(2L+1)|h_{i}|}\right\\}$
$\displaystyle\implies\forall L\geq 1,\quad U^{\lambda,h}_{L+1}(\pi)\leq
U^{\lambda,h}_{L}(\pi)\quad(\text{Using \eqref{app_eq:K_increase}})$
$\displaystyle\implies U^{\lambda,h}_{L}(\pi)\text{ is a decreasing function
w.r.t $L$.}$

Now let us prove the implication in (43). We have for any $L\geq 1$:

$\displaystyle U^{\lambda,h}_{L+1}(\pi)\leq U^{\lambda,h}_{L}(\pi)$
$\displaystyle\iff\sum_{\ell=2L+1}^{2L+2}\frac{\lambda^{\ell-1}}{\ell}\hat{\mathcal{M}}^{h,\ell}_{n}(\pi)\leq
0$
$\displaystyle\iff\frac{\lambda^{2L}}{n}\sum_{i=1}^{n}h_{i}^{2L+1}\left(\frac{1}{2L+1}+\frac{\lambda
h_{i}}{2L+2}\right)\leq 0$

As $h_{i}\leq 0$, we can ensure this inequality by choosing a $\lambda$ that
verifies:

$\displaystyle\forall
i\in[n],\quad\lambda\leq\left\\{\frac{2L+2}{(2L+1)|h_{i}|}\right\\}\iff\lambda\leq\min_{i\in[n]}\left\\{\frac{2L+2}{(2L+1)|h_{i}|}\right\\}$

which concludes the proof. ∎

###  F.3 Proof of the optimality of global clipping for Corollary 3

######  Proposition.

Optimal $h$ for $L=1$:
Let $\lambda>0$. The function $h$ that minimizes the bound for $L=1$, giving
the tightest result is: $\displaystyle\forall i,\quad
h_{i}=h(\pi(a_{i}|x_{i}),\pi_{0}(a_{i}|x_{i}),c_{i}))=-\min\left\\{\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})}|c_{i}|,\frac{1}{\lambda}\right\\}$
This means that when the costs are binary, we obtain the classical Clipping
estimator of parameter $1/\lambda$:
$h_{i}=\min\left\\{\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})},\frac{1}{\lambda}\right\\}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:

$\displaystyle\operatorname*{argmin}_{h\in\text{{(C1)}}}\hat{R}^{h}_{n}(\pi)+\frac{\lambda}{2}\hat{\mathcal{M}}^{h,2}_{n}(\pi)$
$\displaystyle=\operatorname*{argmin}_{h\in\text{{(C1)}}}\frac{1}{n}\sum_{i=1}^{n}\left(h_{i}+\frac{\lambda}{2}h_{i}^{2}\right).$

The objective decomposes across data points, so we can solve it for every
$h_{i}$ independently. Let us fix a $j\in[n]$, the following problem:

$\displaystyle\operatorname*{argmin}_{h_{j}\in\mathbbm{R}}\hat{R}^{h}_{n}(\pi)+\frac{\lambda}{2}\hat{\mathcal{M}}^{h,2}_{n}(\pi)=\operatorname*{argmin}_{h_{j}\in\mathbbm{R}}\left\\{h_{j}+\frac{\lambda}{2}h_{j}^{2}\right\\}$
$\displaystyle\text{subject to}\quad
h_{j}\geq\frac{\pi(a_{j}|x_{j})}{\pi_{0}(a_{j}|x_{j})}c_{j}$

is strongly convex in $h_{j}$. We write the KKT conditions for $h_{j}$ to be
optimal; there exists $\alpha^{*}$ that verifies:

$\displaystyle 1+\lambda h_{j}-\alpha^{*}=0$ (44) $\displaystyle\alpha^{*}\geq
0$ (45)
$\displaystyle\alpha^{*}\left(\frac{\pi(a_{j}|x_{j})}{\pi_{0}(a_{j}|x_{j})}c_{j}-h_{j}\right)=0$
(46) $\displaystyle
h_{j}\geq\frac{\pi(a_{j}|x_{j})}{\pi_{0}(a_{j}|x_{j})}c_{j}$ (47)

We study the two following two cases:

##### Case 1:

$h_{j}\leq-\frac{1}{\lambda}:$
we have $\alpha^{*}=1+\lambda h_{j}\leq 0\implies\alpha^{*}=0$, meaning that:

$h_{j}=-\frac{1}{\lambda}$

##### Case 2:

$h_{j}>-\frac{1}{\lambda}:$

we have $\alpha^{*}=1+\lambda h_{j}>0$, which combined to condition (36)
gives:

$h_{j}=\frac{\pi(a_{j}|x_{j})}{\pi_{0}(a_{j}|x_{j})}c_{j}.$

The two results combined mean that we always have:

$h_{j}\geq-\frac{1}{\lambda},\text{ and whenever
}h_{j}>-\frac{1}{\lambda}\implies
h_{j}=\frac{\pi(a_{j}|x_{j})}{\pi_{0}(a_{j}|x_{j})}c_{j}.$

We deduce that $h_{j}$ has the following form:

$\displaystyle h_{j}$
$\displaystyle=h(\pi(a_{j}|x_{j}),\pi_{0}(a_{j}|x_{j}),c_{j})=-\min\left\\{\frac{\pi(a_{j}|x_{j})}{\pi_{0}(a_{j}|x_{j})}\left|c_{j}\right|,\frac{1}{\lambda}\right\\}$
(48) $\displaystyle\alpha^{*}$
$\displaystyle=1-\lambda\min\left\\{\frac{\pi(a_{j}|x_{j})}{\pi_{0}(a_{j}|x_{j})}\left|c_{j}\right|,\frac{1}{\lambda}\right\\}$
(49)

These 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:

$\forall i\quad c_{i}\in\\{-1,0\\},$

we recover the classical Clipping with parameter $1/\lambda$ as an optimal
solution for $h$:

$h_{j}=\min\left\\{\frac{\pi(a_{j}|x_{j})}{\pi_{0}(a_{j}|x_{j})},\frac{1}{\lambda}\right\\}c_{j}.$

∎

###  F.4 Proof of the $L\rightarrow\infty$ bound (Corollary 4)

######  Proposition (Empirical Logarithmic Smoothing bound with $L\to\infty$).

Let $\pi\in\Pi$, $\delta\in(0,1]$ and $\lambda>0$. Then it holds with
probability at least $1-\delta$ that $\displaystyle
R(\pi)\leq\psi_{\lambda}\Big{(}-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)+\frac{\ln(1/\delta)}{\lambda n}\Big{)}\,.$

Taking the limit of $L$ naively recovers this form of the bound, but imposes a
condition on $\lambda$ for the bound to converge. We instead, take another
path of proof that does not impose any condition on $\lambda$, developed
below.

###### Proof.

Recall that for the proof of the Empirical moments bounds, we used the
following random variable defined with $\lambda>0$:

$\displaystyle X_{i}$
$\displaystyle=-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)-h_{i}-\sum_{\ell=2}^{2L}\frac{1}{\ell}(\lambda
h_{i})^{\ell},$

combined with Chernoff Inequality (Lemma 9) to prove our bound. If we take the
limit $L\rightarrow\infty$ for our random variable, we obtain the following
random variable:

$\displaystyle\tilde{X}_{i}$
$\displaystyle=-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)+\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)$ $\displaystyle=\frac{1}{\lambda}\log\left(\frac{1-\lambda
h_{i}}{1-\lambda\mathbbm{E}\left[h\right]}\right).$

We use the random variable $\tilde{X}_{i}$ with the Chernoff Inequality. For
any $a\in\mathbbm{R}$, we have:

$\displaystyle
P\left(\sum_{i\in[n]}\tilde{X}_{i}>a\right)\leq\left(\mathbbm{E}\left[\exp\left(\lambda\tilde{X}_{1}\right)\right]\right)^{n}\exp(-\lambda
a)$ $\displaystyle
P\left(-\frac{n}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)+\sum_{i\in[n]}\left(\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)\right)>a\right)\leq\left(\mathbbm{E}\left[\exp\left(\lambda\tilde{X}_{1}\right)\right]\right)^{n}\exp(-\lambda
a)$

On the other hand, we have:

$\mathbbm{E}\left[\exp\left(\lambda\tilde{X}_{1}\right)\right]=\frac{\mathbbm{E}\left[1-\lambda
h_{i}\right]}{1-\lambda\mathbbm{E}\left[h\right]}=1.$

Using this equality and solving for $\delta=\exp(-\lambda a)$, we get:

$\displaystyle
P\left(-\frac{n}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)+\sum_{i\in[n]}\left(\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)\right)>\frac{\ln(1/\delta)}{\lambda}\right)\leq\delta$
$\displaystyle
P\left(-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)+\frac{1}{n}\sum_{i\in[n]}\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)>\frac{\ln(1/\delta)}{\lambda n}\right)\leq\delta$

This means that the following, complementary event will hold with probability
at least $1-\delta$:

$\displaystyle-\frac{1}{\lambda}\log\left(1-\lambda\mathbbm{E}\left[h\right]\right)\leq-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)+\frac{\ln(1/\delta)}{\lambda n}.$

$\psi_{\lambda}$ being a non-decreasing function, applying it to the two sides
of this inequality gives us:

$\displaystyle\mathbbm{E}\left[h\right]\leq\psi_{\lambda}\Big{(}-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)+\frac{\ln(1/\delta)}{\lambda n}\Big{)}.$

As $h$ satisfies (C1), we obtain the required inequality:

$\displaystyle
R(\pi)\leq\psi_{\lambda}\Big{(}-\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\lambda}\log\left(1-\lambda
h_{i}\right)+\frac{\ln(1/\delta)}{\lambda n}\Big{)}.$

and conclude the proof. ∎

###  F.5 Proof of the optimality of IPS for Corollary 4

######  Proposition.

Optimal $h$ for $L\rightarrow\infty$:
Let $\lambda>0$. The function $h$ that minimizes the bound for
$L\rightarrow\infty$, giving the tightest result is: $\displaystyle\forall
i,\quad
h_{i}=h(\pi(a_{i}|x_{i}),\pi_{0}(a_{i}|x_{i}),c_{i}))=\frac{\pi(a_{i}|x_{i})}{\pi_{0}(a_{i}|x_{i})}c_{i}$

###### Proof.

The proof of this proposition is quite simple. The function:

$f(x)=-\log\left(1-\lambda x\right)$

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

###  F.6 Proof of $U^{\lambda}_{\infty}$ tightness (Proposition 5)

######  Proposition.

Let $\pi\in\Pi$, and $\lambda>0$, we define:
$U^{\lambda}_{L}(\pi)=\min_{h}U^{\lambda,h}_{L}(\pi).$ Then, for any
$\lambda>0$, it holds that for any $L>1$: $U^{\lambda}_{L}(\pi)\leq
U^{\lambda}_{1}(\pi).$ In particular, $\forall\lambda>0$: $\displaystyle
U^{\lambda}_{\infty}(\pi)\leq U^{\lambda}_{1}(\pi)\,,$ (50)

###### Proof.

Let $\pi\in\Pi$, $\lambda>0$ and

$U^{\lambda}_{L}(\pi)=\min_{h}U^{\lambda,h}_{L}(\pi).$

We already proved that:

$\displaystyle
U^{\lambda}_{1}(\pi)=U^{\lambda,h_{*,1}}_{1}(\pi)=\psi_{\lambda}\Big{(}\hat{R}^{h_{*,1}}_{n}(\pi)+\frac{\lambda}{2}\hat{\mathcal{M}}^{h_{*,1},2}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}$

with:

$h_{*,1}(p,q,c)=-\min(|c|p/q,1/\lambda),$

and that:

$\displaystyle
U^{\lambda}_{\infty}(\pi)=\psi_{\lambda}\Big{(}\hat{R}^{\lambda}_{n}(\pi)+\frac{\ln(1/\delta)}{\lambda
n}\Big{)}.$

From Proposition 2, we have that for any $h$:

$\lambda\leq\min_{i\in[n]}\left\\{\frac{1}{|h_{i}|}\right\\}\implies
U^{\lambda,h}_{L}(\pi)\text{ is a decreasing function w.r.t $L$.}$

It appears that the optimal function $h_{*,1}$ respects this condition, as by
definition:

$\min_{i\in[n]}\left\\{\frac{1}{|(h_{*,1})_{i}|}\right\\}\geq\lambda,$

meaning that:

$U^{\lambda,h_{*,1}}_{L}(\pi)\text{ 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$:

$\displaystyle U^{\lambda}_{L}(\pi)=\min_{h}U^{\lambda,h}_{L}(\pi)\leq
U^{\lambda,h_{*,1}}_{L}(\pi)\leq
U^{\lambda,h_{*,1}}_{1}(\pi)=U^{\lambda}_{1}(\pi).$

In particular, we get:

$\displaystyle U^{\lambda}_{\infty}(\pi)\leq U^{\lambda}_{1}(\pi),$

which ends the proof. ∎

##  Appendix G Proofs of OPS and OPL

###  G.1 OPS: Proof of suboptimality bound (Proposition 6)

######  Proposition.

(Suboptimality of our selection strategy in (16)). Let $\lambda>0$ and
$\delta\in(0,1]$. Then, it holds with probability at least $1-\delta$ that
$\displaystyle 0\leq
R(\hat{\pi}_{n}^{\textsc{s}})-R(\pi_{*}^{\textsc{s}})\leq\lambda\mathcal{S}_{\lambda}(\pi_{*}^{\textsc{s}})+\frac{2\ln(2|\Pi_{\textsc{s}}|/\delta)}{\lambda
n}\,,$ where $\pi_{*}^{\textsc{s}}$ and $\hat{\pi}_{n}^{\textsc{s}}$ are
defined in (15) and (16), and
$\mathcal{S}_{\lambda}(\pi)=\mathbb{E}\left[(w_{\pi}(x,a)c)^{2}/\left(1-\lambda
w_{\pi}(x,a)c\right)\right].$ In addition, our upper bound is always finite
as:
$\displaystyle\lambda\mathcal{S}_{\lambda}(\pi)=\lambda\mathbb{E}\left[\frac{(w_{\pi}(x,a)c)^{2}}{1-\lambda
w_{\pi}(x,a)c}\right]\leq\min\left\\{|R(\pi)|,\lambda\mathbb{E}\left[(w_{\pi}(x,a)c)^{2}\right]\right\\}\leq|R(\pi)|.$

###### 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 Proposition 13. For a fixed
$\lambda$, taking a union of the two bounds over the cardinal of the finite
policy class $\lvert\Pi_{s}\rvert$, we get the following holding with
probability at least $1-\delta$ for all $\pi\in\Pi_{s}$:

$\displaystyle
R(\pi)-\hat{R}^{\lambda}_{n}(\pi)\leq\frac{\ln(2\lvert\Pi_{s}\rvert/\delta)}{\lambda
n}\,,\qquad\text{and}\qquad\hat{R}^{\lambda}_{n}(\pi)-R(\pi)\leq\lambda\mathcal{S}_{\lambda}(\pi)+\frac{\ln(2\lvert\Pi_{s}\rvert/\delta)}{\lambda
n}\,.$

As $\hat{\pi}_{n}^{\textsc{s}}\in\Pi_{s}$ and by definition of
$\hat{\pi}_{n}^{\textsc{s}}$ (minimizer of $\hat{R}^{\lambda}_{n}(\pi)$), we
have:

$\displaystyle
R(\hat{\pi}_{n}^{\textsc{s}})\leq\hat{R}^{\lambda}_{n}(\hat{\pi}_{n}^{\textsc{s}})+\frac{\ln(2\lvert\Pi_{s}\rvert/\delta)}{\lambda
n}$
$\displaystyle\leq\hat{R}^{\lambda}_{n}(\hat{\pi}_{*}^{\textsc{s}})+\frac{\ln(2\lvert\Pi_{s}\rvert/\delta)}{\lambda
n}.$

Using the lower bound on the risk of $R(\hat{\pi}_{*}^{\textsc{s}})$, we have:

$\displaystyle R(\hat{\pi}_{n}^{\textsc{s}})$
$\displaystyle\leq\hat{R}^{\lambda}_{n}(\hat{\pi}_{*}^{\textsc{s}})+\frac{\ln(2\lvert\Pi_{s}\rvert/\delta)}{\lambda
n}$ $\displaystyle\leq
R(\hat{\pi}_{*}^{\textsc{s}})+\lambda\mathcal{S}_{\lambda}(\hat{\pi}_{*}^{\textsc{s}})+\frac{2\ln(2\lvert\Pi_{s}\rvert/\delta)}{\lambda
n}.$

which gives us the suboptimality upper bound:

$\displaystyle 0\leq