# A Theory of Learnability for Offline Decision Making: Instance-Dependent and
Nearly Minimax Optimal

Chenjie Mao<EMAIL_ADDRESS>
Shanghai Artificial Intelligence Laboratory
Qiaosheng Zhang<EMAIL_ADDRESS>
Shanghai Artificial Intelligence Laboratory

###### Abstract

We study the problem of offline decision making, which focuses on learning
decisions from datasets only partially correlated with the learning objective.
While previous research has extensively studied specific offline decision
making problems like offline reinforcement learning (RL) and off-policy
evaluation (OPE), a unified framework and theory remain absent. To address
this gap, we introduce a unified framework termed _Decision Making with
Offline Feedback_ (DMOF), which captures a wide range of offline decision
making problems including offline RL, OPE, and offline partially observable
Markov decision processes (POMDPs). For the DMOF framework, we introduce a
hardness measure called the _Offline Estimation Coefficient_ (OEC), which
measures the learnability of offline decision making problems and is also
reflected in the derived minimax lower bounds. Additionally, we introduce an
algorithm called Empirical Decision with Divergence (EDD), for which we
establish both an instance-dependent upper bound and a minimax upper bound.
The minimax upper bound almost matches the lower bound determined by the OEC.
Finally, we show that EDD achieves a fast convergence rate (i.e., a rate
scaling as $1/N$, where $N$ is the sample size) for specific settings such as
supervised learning and Markovian sequential problems (e.g., MDPs) with
partial coverage.

##  1 Introduction

_Offline decision making_ studies learning decisions from a logged dataset
that, in most cases, is only _partially correlated_ with the learning
objective. The possible partial correlation between the dataset and the
learning objective distinguishes offline decision making from _supervised
learning_ [Vapnik, 1998, Shalev-Shwartz and Ben-David, 2014], making it a
promising subject capturing a wide range of real-world problems. Examples of
offline decision making include _offline reinforcement learning_ (Antos et al.
[2006], Lange et al. [2012], Levine et al. [2020]; offline RL) and _off-policy
evaluation_ (Li et al. [2011], Thomas and Brunskill [2016], Farajtabar et al.
[2018], Uehara et al. [2022]; OPE), both of which are trendy areas in recent
years. Specifically, in the former, the dataset is a logged interaction
between the environment and the so-called behaviour policy while the learning
objective is to learn a good policy that differs from the behaviour policy. In
the latter, the dataset is usually generated from a policy differing from the
one to be estimated. A crucial consideration in the offline decision making
problem is _learnability_ , which refers to the ability to learn a desired
policy from the logged dataset.

On one hand, although the research in offline decision making has advanced
rapidly, most theoretical results about learnability have been tied to
specific problem structures, such as Markovian transition, tabular state-
action space (e.g., tabular Markov decision processes (MDPs [Puterman, 1994]);
Rashidinejad et al. [2021], Xie et al. [2021b], Li et al. [2022]), and low-
rank features (e.g., linear MDPs; Jin et al. [2020], Huang et al. [2023],
Xiong et al. [2023]), with assumptions like independently sampled data from a
data distribution covering some policies [Chen and Jiang, 2019, Liu et al.,
2020, Xie and Jiang, 2020, Xie et al., 2021a]. These results often differ in
their formulations and rely on different assumptions for derivation. This
diversity in problem structures and underlying assumptions not only obstructs
a unified understanding of the offline decision making problem but also poses
challenges in transferring theoretical results from one problem to another. In
the presence of these issues, we want to ask:

_Can we study offline decision making in a unified framework and extract a
measure summarizing the learnability of offline decision making problems?_

On the other hand, in the context of interactive (online) decision making,
Foster et al. [2021a] introduced a concept, known as the _Decision Estimation
Coefficient_ (DEC), that captures the learnability and statistical complexity
of interactive decision making problems (which contains classical bandit and
reinforcement learning as exceptional cases). They also developed a unified
algorithm design principle named Estimation-to-Decision (E2D). The regret
associated with E2D can be bounded by a function of the DEC and nearly attains
the information-theoretic lower bound for regret. Inspired by their
theoretical advancements in online decision making and the lack of
corresponding theories in offline settings, we also want to ask:

_Whether these insights can be transferred to, and potentially enhanced
within, the offline setting._

This paper positively answers the two posed questions. We first introduce a
unified framework for offline decision making, named _Decision Making with
Offline Feedback_ (DMOF). We then present certain measures that summarize the
learnability and statistical complexity in DMOF, along with an algorithm that
achieves nearly instance-optimal regret as well as certain fast converge
rates. We detail our contributions as follows.

  1. 1.

We propose a measure—called _Offline Estimation Coefficient_ (OEC, Definition
2)—that can encapsulate the hardness of an offline decision making problem. On
top of this, we further provide an information-theoretic lower bound for the
regret of any algorithm, expressed as a function of the OEC (Theorem 1).

  2. 2.

We present a simple yet powerful algorithm named Empirical Decision with
Divergence (EDD; Eq. 3), which enjoys the following advantage.

     * •

(Theorem 2) It has an _instance-dependent_ upper bound that can adjust to the
different choices of the real model.

     * •

(Theorem 3) We also derive a minimax upper bound for EDD based on the
instance-dependent bound. The minimax upper bound nearly matches the lower
bound determined by the OCE in Theorem 1. This means that EDD is also nearly
minimax optimal.

     * •

(Theorems 4 and 5) It attains the fast convergence rate (namely the rate in
$1/N$ where $N$ is sample size) to the sub-optimality gap in the presence of
more concrete correlation assumptions. For example, it attains this rate in
supervised learning (Definition 4) and in Markovian sequential problems
(Definition 5) with partial coverage, where the latter include Markov decision
processes as a special case.

A summary of the main contributions of this paper is presented in Table 1.

Table 1: A summary of the main contributions of this paper. The “Assumptions” column lists assumptions required by the result other than the DMOF framework (Section 3). “Inst.” means instance-dependent. “SL” means supervised learning (Definition 4), and “Sequential” means Markovian sequential problems (Definition 5). The entries in the “Value” column are the bounds of the loss (or return for Proposition 2). We strip some terms away for simplicity. Type | Value/Gap | Location | Assumptions | Description
---|---|---|---|---
Lower Bound | $\textup{{OEC}}_{4B}(\mathcal{M},A)$ | Theorem 1 | None |
Upper Bound (For EDD Eq. 3) | Inst. | $\min_{\lambda\geq 0}\textup{{EOEC}}_{\lambda}(M^{\star},\mathcal{M},\mathcal{D}^{\star})$ | Theorem 2 | None |
Minimax | $\min_{\lambda\geq 0}[\textup{{OEC}}_{\lambda}(\mathcal{M},\mathcal{M})+2\lambda\cdot\log(|\mathcal{M}|/\delta)]$ | Theorem 3 | None |  directly follows from Theorem 2
Minimax | $3\min_{\pi\in\Pi}\mathcal{L}(M^{\star},\pi)+\log(|\mathcal{M}|/\delta)/N$ | Theorem 4 |  SL, Assumption 1
Minimax | $\min_{\pi\in\Pi}\big{[}\mathcal{L}(M^{\star},\pi)\big{]}+\log(|\mathcal{M}|/\delta)/N$ | Proposition 1 |  SL, Assumption 1
Minimax | $3\mathcal{L}(M,\widebar{\pi})+C_{\widebar{\pi}}\log\big{(}|\mathcal{M}|/\delta\big{)}/N$ | Theorem 5 |  Sequential, Assumptions 2 and 3
Minimax | $J_{M_{\texttt{rl}}^{\star}}^{\star}-C_{\pi^{\star}}\log\big{(}|\mathcal{M}|/\delta\big{)}/N$ | Proposition 2 |  RL, Assumptions 2 and 3

###  1.1 Related Works

#### General Function Approximation in Offline Decision Making

General function approximation [Bertsekas and Tsitsiklis, 1996, Vapnik, 1998,
Shalev-Shwartz and Ben-David, 2014] formulates the statistical learning
problem with a generic function class, and studies the learnability of the
problem in terms of the complexity of the function class. General function
approximation is extensively studied in offline decision making, typically in
the subjects like offline RL [Chen and Jiang, 2019, Liu et al., 2020, Xie and
Jiang, 2020, Foster et al., 2021b, Xie et al., 2021a, Cheng et al., 2022, Zhan
et al., 2022] and OPE [Uehara et al., 2019, Jiang and Huang, 2020, Huang and
Jiang, 2022]. In these works, function classes are considered as another
crucial aspect of learnability beyond the data coverage. Particular examples
of these function classes include the value function class, the policy
function class, the density ratio function class [Liu et al., 2018, Uehara et
al., 2019], and the model class [Uehara and Sun, 2021, Bhardwaj et al., 2023].
General function approximation is widely preferred since it is more adaptable
to complex real-world scenarios (both for function approximators and for the
state-action space) and can be applied directly to specialized settings (e.g.,
linear and tabular MDPs) with only minor modifications. Recently, Di et al.
[2023] proposed an algorithm named Pessimistic Nonlinear Least-Square Value
Iteration for nonlinear function classes and get a minimax optimal instance-
dependent regret when specialized to the linear setting. However, their
results require the uniform coverage over the dataset which is fairly strong
in the offline setting.

#### Instance-Dependent Bounds in Offline Decision Making

Despite the rapid progress in the development of minimax bounds, instance-
dependent analyses in offline decision making are still under development,
possibly due to the obstacle presented by the partial correlation. The most
studied instance hardness measures are the variance and gap [Xu et al., 2021,
Simchowitz and Jamieson, 2019, He et al., 2021] in the optimal value function,
where the latter is defined as the difference of the values between the
optimal action and sub-optimal ones across the state space. Nevertheless, the
gap-based instance-dependent bound seems less intuitive since it prefers
problems with a large gap, but selecting sub-optimal actions with a small gap
should also yield satisfactory results. Specifically in the offline setting,
there are only several works presenting instance-dependent bounds, and all of
them focus on special settings like linear MDPs [Duan and Wang, 2020, Yin et
al., 2022a, Min et al., 2022, Nguyen-Tang et al., 2023] and tabular MDPs
[Pananjady and Wainwright, 2020, Yin and Wang, 2021, Wang et al., 2022], with
certain strong assumptions like uniform policy coverage [Hu et al., 2021, Yin
et al., 2022c, Di et al., 2023].

#### Works Related to DEC

This paper is influenced by the DEC paper for interactive (online) decision
making [Foster et al., 2021a], but it also introduces significant developments
rather than being a simple adaptation. For example, we use a fixed parameter
$\lambda$, and we propose EDD that achieves an instance-dependent bound as
well as a fast convergence rate for some particular problems such as
supervised learning and Markovian sequential problems with partial coverage.
On the other hand, after the initial publication of Foster et al. [2021a],
there have been subsequent works trying to enhance their result [Foster et
al., 2023c, b, Chen et al., 2024] and expand it to other settings [Foster et
al., 2022, 2023a], but none of them studies for offline decision making.
Conclusively, we hope that our work can fill this gap and further inspire the
development of DEC in the online setting.

###  1.2 The Problem of Learnability in Offline Decision Making

The problem of whether we can learn a good decision (i.e., the problem of
learnability) can be factorized into two aspects: the correlation between the
dataset and the loss, together with the structure of the learning problem. For
the former, classic studies in offline decision making make the coverage
assumption, assuming that the dataset covers some specific policies we want to
compare. The correlation can then be built, typically (for the example of
offline RL) through the simulation lemma, the performance difference lemma,
and so forth. The latter explains how the dataset is logged and how the
decision is evaluated; one example is the Markov decision process framework.

###  1.3 Organization of This Paper

We first introduce the concept of $f$-divergence in Section 2, and then
present the DMOF framework for offline decision making in Section 3. Section 4
introduces the hardness measure OEC and establishes a lower bound for offline
decision making. As a complement to the lower bound, we propose the EDD
algorithm in Section 5 and provide two upper bounds for EDD. We further expand
the upper bounds in Section 6 by showing some fast convergence results under
certain correlation assumptions. Finally, we will conclude this paper with
some discussion of the results of this paper and the expectation for further
work in Section 7.

##  2 Preliminaries on $f$-Divergence

We briefly introduce the concept of _$f$ -divergence_ in this section, and
refer the interested readers to Section $7$ in Polyanskiy and Wu [2022] for a
more detailed explanation. We assume that we operate on a _measurable space_
$(E,\mathcal{E})$ (e.g., the set of _real numbers_ $\mathbb{R}$ and its _Borel
sets_), and we have access to a _dominating measure_ $\nu$ (e.g., the
_Lebesgue measure_).

For two probability measures $\mathbb{P}$ and $\mathbb{Q}$, we denote the
_Radon-Nikodym derivative_ of $\mathbb{P}$ w.r.t. $\mathbb{Q}$ as
$\frac{d\mathbb{P}}{d\mathbb{Q}}$. We also use lowercase letters to denote the
Radon-Nikodym derivative w.r.t. $\nu$ (e.g., $p\coloneqq d\mathbb{P}/d\nu$ and
$q\coloneqq d\mathbb{Q}/d\nu$).

######  Definition 1 ($f$-divergence).

Given a function $f:(0,\infty)\to\mathbb{R}$ and two probability measures
$\mathbb{P}$ and $\mathbb{Q}$, let $A\coloneqq\\{x\in E|q(x)>0\\}$ and
$f^{\prime}(\infty)\coloneqq\lim_{x\to 0}xf(1/x)$, with the agreement that the
$f^{\prime}(\infty)\mathbb{P}(E\setminus A)$ is $0$ if $\mathbb{P}(E\setminus
A)=0$, we define

$\displaystyle
D_{f}(\mathbb{P}\|\mathbb{Q})\coloneqq\int_{A}f\Big{(}\frac{p(x)}{q(x)}\Big{)}q(x)d\nu(x)+f^{\prime}(\infty)\mathbb{P}(E\setminus
A)$

as the $f$-divergence between $\mathbb{P}$ and $\mathbb{Q}$ if $f$ is convex
and $f(1)=0$.

In short, the $f$-divergence measures the difference between two probability
measures given a convex function $f$. Examples of several frequently used
f-divergences are listed below:

  * •

the _KL divergence_ , where $f(x)=x\log(x)$:
$\textup{{KL}}(\mathbb{P}\|\mathbb{Q})\coloneqq\mathbb{E}_{\nu}\big{[}p\log(p/q)\big{]}$;

  * •

the _squared Hellinger distance_ , where $f(x)=(1-\sqrt{x})^{2}$:
$\texttt{H}^{2}(\mathbb{P},\mathbb{Q})\coloneqq\mathbb{E}_{\nu}\big{[}(\sqrt{p}-\sqrt{q})^{2}\big{]}$;

  * •

the _total variation_ , where $f(x)=0.5|x-1|$:
$\textup{{TV}}(\mathbb{P},\mathbb{Q})\coloneqq\mathbb{E}_{\nu}|p-q|/2$.

##  3 Framework: Decision Making with Offline Feedback (DMOF)

Inspired by the _decision making with structured observation_ (DMSO) framework
for online decision making problems [Foster et al., 2021a], we introduce a
general framework for offline decision making, which is referred to as
_Decision Making with Offline Feedback_ (DMOF). The DMOF framework includes an
observation space $\mathcal{O}$, a model space $\mathcal{M}$, a decision space
$\Pi$, and a loss function $\mathcal{L}:\mathcal{M}\times\Pi\to[0,B]$ for a
constant $B>0$.

The learner interacts with the DMOF according to the following protocol.

  1. 1.

Problem Setup: there is an unknown _real model_ $M^{\star}\in\mathcal{M}$
specified ahead, under which we observe a dataset
$\mathcal{D}^{\star}\in\mathcal{O}$ such that
$\mathcal{D}^{\star}\sim\mathbb{P}_{M^{\star}}$ (we will slightly abuse the
notation and denote $\mathcal{D}\sim M$ when considering the dataset
generating).

  2. 2.

Learning: given the knowledge of $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$
as well as the observed dataset $\mathcal{D}^{\star}$, we wish to find a
decision $\widehat{\pi}\in\Pi$ that minimizes the loss
$\mathcal{L}(M^{\star},\widehat{\pi})$. We sometimes also learn a stochastic
decision characterized by a distribution $p\in\Delta(\Pi)$, of which the loss
is defined as $\mathcal{L}(M^{\star},p)\coloneqq\mathbb{E}_{\pi\sim
p}[\mathcal{L}(M^{\star},\pi)]$.

This framework is carefully crafted for offline decision making problems,
capturing broad settings such as offline RL, off-policy evaluation, and
offline POMDPs. Example 1 provides a detailed explanation of how the DMOF
framework is explicitly applied to the offline RL problem.

######  Example 1 (DMOF in Offline RL).

Let us consider the general framework of offline RL (see Appendix A for a more
concrete introduction) with a realizable model class
$\mathcal{M}_{\texttt{rl}}$ that contains $M_{\texttt{rl}}^{\star}$. In such
setting, DMOF follows that:
$\mathcal{M}=\\{M=(M_{\texttt{rl}},d^{\mathcal{D}},N)|M_{\texttt{rl}}\in\mathcal{M}_{\texttt{rl}}\\}$
where $\mathcal{M}_{\texttt{rl}}$ is the set of MDPs, $d^{\mathcal{D}}$ is the
data distribution on the state-action space, and $N$ is the sample size; $\Pi$
is the set of policies ($\Pi_{\texttt{rl}}$); $\mathcal{O}$ is the set of all
possible dataset with size $N$; and
$\mathcal{L}((M_{\texttt{rl}},d^{\mathcal{D}},N),\pi)$ is the gap between the
optimal expected return of $M_{\texttt{rl}}\in\mathcal{M}_{\texttt{rl}}$ and
the expected return of policy $\pi$.

Algorithms (denoted as $\mathfrak{A}$) are mappings from
$(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ and the observed dataset
$\mathcal{D}^{\star}$ to a (distribution of) decision $\pi\in\Pi$. Since the
elements $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ are always fixed, we will
only specify $\mathcal{D}^{\star}$ in most cases. We now outline some
advantages of the DMOF framework in the following.

####  $\mathcal{M}$ as an Information Representor

The complexity of $\mathcal{M}$ reflects the information available in advance,
and additional side information can help to prune $\mathcal{M}$. For any
assumptions made or any information provided, we can always infer a model
class $\mathcal{M}$ representing all necessary details. For instance, in
offline RL, assuming having a value function class $\mathcal{Q}$ that contains
the optimal value function is equivalent to assuming having a model class
containing the real model, which is composed of all possible models whose
optimal value function is contained by $\mathcal{Q}$ [Mao et al., 2024].

#### On the Variation of the Loss Function $\mathcal{L}$

It is worth noting that we do not put any constraints on the loss function
$\mathcal{L}$. It can be any function taking a model and a decision as input,
and can even be irrelevant to its inputs. Thus, one can specify $\mathcal{L}$
to adapt to various scenarios. _Essentially, the weak correlation between the
loss function $\mathcal{L}$ and the observation $\mathcal{D}^{\star}$ forms
one of the biggest differences between DMOF (i.e., offline decision making)
and standard supervised learning problems._

#### On the Data Distribution

While prior works on offline decision making typically make many assumptions
about the data generating process, these assumptions are made mainly for the
ease of analysis and may not be necessary for learning a good policy in
practice. DMOF circumvents the over-explanation of data assumptions by the
model class $\mathcal{M}$, which we will show in the following sections is
ultimately enough for summarizing the problem and its learnability.

##  4 Offline Estimation Coefficient and Lower Bounds

This section introduces the Offline Estimation Coefficient (OEC) and presents
a lower bound (Theorem 1) for the problem of the learnability of DMOF as a
function of the OEC. We defer the proofs for this section to Appendix C.

We define the OEC as a trade-off between the similarities of the
representation and the difference in learning objectives for models from DMOF,
which are captured in a $\max\min\max$ form.

######  Definition 2.

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$, _its_ OEC w.r.t. a
set of probability $A\subseteq\Delta(\mathcal{O})$ and a parameter
$\lambda\geq 0$ is defined as

$\displaystyle\textup{{OEC}}_{\lambda}(\mathcal{M},A)\coloneqq\max\limits_{\rho\in
A}\min\limits_{p\in\Delta(\Pi)}\max\limits_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,p)-\lambda\cdot\textup{{H}${}^{2}$}(\rho,M)\Big{]}.$
(1)

where $\textup{{H}${}^{2}$}(\rho,M)$ is the squared Hellinger distance between
$\rho$ and $\mathbb{P}_{M}$.

Below, we provide an interpretation of the formulation and the operational
meaning of OEC. Technically, the first $\max_{\rho\in A}$ part in OEC sets a
point in the model class $\mathcal{M}$ where the real model possibly lies,
suggesting that the real model should be similar to $\rho$. The
$\min_{p\in\Delta(\Pi)}$ indicates that there is a learner pessimistically
chooses a stochastic policy $p\in\Delta(\Pi)$, with the knowledge of $\rho$
but without knowing the real model $M\in\mathcal{M}$. The last
$\max_{M\in\mathcal{M}}$ part means that an adversary selects the worst-case
real model $M$ that is similar to $\rho$ after knowing the stochastic policy
$p$.

The OEC summarizes the learnability property of a DMOF problem: as will be
presented in Theorem 1, it implies a lower bound for learning; moreover, the
OEC is also involved in the upper bound presented in Theorem 3.

######  Remark 1.

As a further development, the squared Hellinger distance in Eq. 4 can be
replaced by other $f$-divergences provided they satisfy a refined change of
measure property (introduced in Appendix F). Such $f$-divergences include the
total variation distance, the KL divergence, and so forth. We will discuss
them in more detail in Appendix F.

###  4.1 Lower Bounds via OEC without Further Assumptions

This subsection presents a lower bound on the loss of any algorithm, which is
specifically expressed as a function of the OEC with $\lambda=4B$. Here, we do
not make any assumption on the problem—e.g., assumptions on structure of the
problem (like sequential or Markovian) or on the coverage of the
dataset—except the DMOF framework. Our result on the lower bound is
encapsulated in the subsequent theorem.

######  Theorem 1.

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$, for any algorithm
$\mathfrak{A}$, there exists an $M\in\mathcal{M}$ such that the expected loss
of the algorithm under model $M$ is lower bounded as follow:

$\displaystyle\mathbb{E}_{\mathcal{D}\sim
M}\Big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\Big{]}\geq\frac{1}{3}\textup{{OEC}}_{4B}(\mathcal{M},A),$
(2)

where $A$ can be chosen as any subset of $\Delta(\mathcal{O})$.

An interesting observation is that the set $A$ can be any set of distributions
on $\mathcal{O}$, which, while of course including $\mathcal{M}$ itself, are
not limited to models from DMOF. For instance, in the context of time-
inhomogenious Markov decision processes, offline RL often makes independent
assumptions on samples [Chen and Jiang, 2019, Liu et al., 2020, Rashidinejad
et al., 2021, Xie et al., 2021a], whereas $\Delta(\mathcal{O})$ can contain
distributions that are correlated. This contrasts somewhat with the typical
approach to proving lower bounds: to find a lower bound from a problem set
$\mathcal{M}$, we typically construct a subset of $\mathcal{M}$ and verify the
hardness of the subset.

As discussed above, the purpose of the first $\max$ part is merely to serve as
a guide for pinpointing the real model. The lower bound becomes tightest when
$A$ is taken as $\Delta(\mathcal{O})$, but computing the exact value of OEC
for $A=\Delta(\mathcal{O})$ may require significant effort. When computing the
lower bound, one can choose an appropriate $A$ that balances accuracy with
computational complexity.

##  5 Algorithm: Empirical Decision with Divergence (EDD)

This section presents an algorithm named _Empirical Decision with Divergence
(EDD)_ and presents two upper bounds for it: one (Theorem 2) is instance-
dependent and adapts to different real models; the other (Theorem 3) is stated
with OEC in the minimax case and can be compared with the lower bound (Theorem
1). Both results are attained without further assumptions other than the DMOF
framework. As an expansion, we will further explain the guarantees of EDD
under certain representative learning assumptions in Section 6. We defer the
proofs for this section to Appendix D for a clean presentation.

Given a dataset $\mathcal{D}^{\star}$ generated by the real model $M^{\star}$,
together with a model class $\mathcal{M}$ standing as the information we can
access, EDD outputs the policy in the following form:

$\displaystyle\widehat{p}(\mathcal{D}^{\star})=\operatorname*{argmin}_{p\in\Delta(\Pi)}\max_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,p)+\lambda\log(\mathbb{P}_{M}(\mathcal{D}^{\star}))\Big{]},$
(3)

where $\lambda\geq 0$ is a hyper-parameter, and
$\log(\mathbb{P}_{M}(\mathcal{D}^{\star}))$ is the log-likelihood of observing
$\mathcal{D}^{\star}$ under model $M$. In short, EDD selects the policy that
is universally good (reflected by $\mathcal{L}(M,\pi)$ in Eq. 3) among
possible real models (reflected by $\log(\mathbb{P}_{M}(\mathcal{D}^{\star}))$
Eq. 3), but in a more unified way comparing the E2D algorithm from Foster et
al. [2021a] for the online setting, which first estimates the real model then
pessimistically select a good policy.

###  5.1 Guarantees of EDD

This subsection elaborates on the upper bounds achieved by EDD. Before this,
we first introduce a new concept called _Empirical Offline Estimation
Coefficient_ (EOEC).

######  Definition 3.

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ and a dataset
$\mathcal{D}$, the EOEC w.r.t. a model $M\in\mathcal{M}$ and a parameter
$\lambda\in\mathbb{R}$ is defined as

$\displaystyle\textup{{EOEC}}_{\lambda}(M,\mathcal{M},\mathcal{D})\coloneqq\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},p)+\lambda\cdot\log(\mathbb{P}_{M^{\prime}}(\mathcal{D})/\mathbb{P}_{M}(\mathcal{D}))\big{]}.$
(4)

Compared with OEC, EOEC replaces the squared Hellinger distance with the
“data-based” log-likelihood ratio, which corresponds to the name “empirical.”
We then state our first upper bound for EDD with the help of EOEC.

######  Theorem 2.

For any real $M^{\star}\in\mathcal{M}$ and $\mathcal{D}^{\star}\sim
M^{\star}$, EDD (Eq. 3) with a proper choice of its hyper-parameter has its
loss bounded as

$\displaystyle\mathcal{L}(M^{\star},\widehat{p}(\mathcal{D}^{\star}))\leq\min_{\lambda\geq
0}\textup{{EOEC}}_{\lambda}(M^{\star},\mathcal{M},\mathcal{D}^{\star}).$ (5)

This upper bound is instance-dependent and adapts automatically to different
choices of $M^{\star}$ and even to the different occurrences of the dataset we
encountered. As a complement, the following theorem relates EOEC with OEC,
showing that EDD is nearly optimal in the minimax perspective.

######  Theorem 3.

For any DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ and model
$M\in\mathcal{M}$, with probability at least $1-\delta$ over $\mathcal{D}\sim
M$,

$\displaystyle\textup{{EOEC}}_{\lambda}(M,\mathcal{M},\mathcal{D})\leq$
$\displaystyle\textup{{OEC}}_{\lambda}(\mathcal{M},\\{M\\})+2\lambda\cdot\log(|\mathcal{M}|/\delta).$

Consequently, for any DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ and
real $M^{\star}\in\mathcal{M}$, EDD (Eq. 3) with a proper choice of its hyper-
parameters has its loss bounded, with probability at least $1-\delta$ over
$\mathcal{D}^{\star}\sim M^{\star}$, as

$\displaystyle\mathcal{L}(M^{\star},\widehat{p}(\mathcal{D}^{\star}))\leq$
$\displaystyle\min_{\lambda\geq
0}\big{[}\textup{{OEC}}_{\lambda}(\mathcal{M},\\{M^{\star}\\})+2\lambda\cdot\log(|\mathcal{M}|/\delta)\big{]}$
(6) $\displaystyle\leq$ $\displaystyle\min_{\lambda\geq
0}\big{[}\textup{{OEC}}_{\lambda}(\mathcal{M},\mathcal{M})+2\lambda\cdot\log(|\mathcal{M}|/\delta)\big{]},$
(7)

where $|\mathcal{M}|$ denotes the cardinality of $\mathcal{M}$.

######  Remark 2.

As usual, the cardinality $|\mathcal{M}|$ in the above theorem can be replaced
by other complexity measures like the covering number and the Rademacher
complexity with minor modifications.

###  5.2 Comparing the Upper Bound and the Lower Bound

Apart from the OEC term appearing in the lower bound (Eq. 36), the upper bound
(Eq. 7) also contains an additional $2\lambda\cdot\log(|\mathcal{M}|)$. For a
converging result, one must set $\lambda$ to a sufficiently small value
compared with the constant value in Eq. 36, which still makes sense as we will
explain in the next section.

Notably, until now, we have not made any assumptions such as “independent and
identically distributed” (i.i.d.) or the coverage assumption, except for the
framework depicted by DMOF. Thus, we can expect that either the lower bound
(Eq. 36) only occurs in extreme cases and may not accurately reflect the
tightness of the upper bounds (Eqs. 5 and 7), or that the upper bounds can be
significantly improved with certain appropriate assumptions.

Similar observations (the additional $\lambda\cdot\log(|\mathcal{M}|/\delta)$
and the scale of $\lambda$) also occur for the PAC bound in the online setting
in the spectrum works of DEC [Foster et al., 2023b], which is regarded as an
unsolved problem. An interesting point for the regret bound in the online
setting is that, while the addition term remains, we do not have the problem
of setting $\lambda$ to be too small [Foster et al., 2021a, 2023b]. This is
because every distribution (or interaction) has a loss appearing in the
regret, which allows us to more moderate values. We refer the interested
reader to the original papers for more detail.

##  6 Fast Convergence Rates for EDD under I.I.D. and Correlation

This section shows that EDD (Eq. 3) attains the fast convergence rate (namely,
rates in $1/N$ where $N$ is the sample size) to the sub-optimality gap under
the correlation and i.i.d. assumptions, which is the first place we consider
additional assumptions other than the DMOF. We defer the proof of this section
to Appendix E.

More specifically, we investigate the correlation in two types of problems in
the offline setting: _supervised learning_ and _Markovian sequential
problems_. In the former, the correlation arises from the sample-based loss
function, while in the latter, it stems from the partial coverage assumption.

###  6.1 Supervised Learning and Sample-based Full Correlation

This subsection shows that, in the case we instantiate _supervised learning_
[Vapnik, 1998, Shalev-Shwartz and Ben-David, 2014] in the DMOF framework, EDD
(Eq. 3) achieves a fast convergence rate compared with the optimal loss.

In supervised learning, there is an input space $\mathcal{X}_{\texttt{sl}}$,
an output $\mathcal{Y}_{\texttt{sl}}$, a dataset
$\mathcal{D}=\\{(x_{\texttt{sl},i},y_{\texttt{sl},i}\\}_{i\in[N]}$111$[N]$
denotes the set of integers $\\{1,2,3,\dots,N\\}$. that contains i.i.d. random
variables from the distribution
$d\in\Delta(\mathcal{X}_{\texttt{sl}}\times\mathcal{Y}_{\texttt{sl}})$. While
the distribution $d$ is _unknown_ , we are given a hypothesis class
$\mathcal{H}\subseteq(\mathcal{X}_{\texttt{sl}}\to\mathcal{Y}_{\texttt{sl}})$
together with a dataset $\mathcal{D}$ and wish to find a
$\widehat{h}\in\mathcal{H}$ that minimizes

$\displaystyle\mathbb{E}_{\mathcal{D}}\sum_{(x_{\texttt{sl},i},y_{\texttt{sl},i})\in\mathcal{D}}L(\widehat{h}(x_{\texttt{sl},i}),y_{\texttt{sl},i})=\mathbb{E}_{(X_{\texttt{sl}},Y_{\texttt{sl}})\sim
d}L(\widehat{h}(X_{\texttt{sl}}),Y_{\texttt{sl}}),$ (8)

where $L\in(\mathcal{Y}_{\texttt{sl}}\times\mathcal{Y}_{\texttt{sl}}\to[0,B])$
is the loss function.

Supervised learning is a special instance of the DMOF with full correlation.
We explain supervised learning with the DMOF in the following definition.

######  Definition 4 (Supervised Learning).

Let $\mathcal{X}$ be a feature space, $\ell:\mathcal{X}\times\Pi\to[0,B]$ be a
point-wise loss function, and $N$ be the size of the dataset. We can overload
the DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ by letting
$\mathcal{O}\coloneqq\mathcal{X}^{N}$ be the set of ensembles of samples, and
$\mathcal{M}\subseteq\Delta(\mathcal{X}^{N})$ be a set of data distributions.
We define the loss function as

$\displaystyle\mathcal{L}(M,\pi)\coloneqq\mathbb{E}_{\mathcal{D}\sim
M}\Big{[}\frac{1}{N}\sum_{x\in\mathcal{D}}\ell(x,\pi)\Big{]}.$

We refer to this framework as the DMOF _over the supervised learning problem_
($\mathcal{X}$, $\ell$, $N$).

######  Remark 3.

Here we explain the correspondence of the above definition and supervised
learning: the space
$\mathcal{X}=\mathcal{X}_{\texttt{sl}}\times\mathcal{Y}_{\texttt{sl}}$
consists of two parts (the input space and the output space),
$\Pi=\mathcal{H}$ is the hypothesis class, and
$\ell(x,\pi)=L(\pi(x_{\texttt{sl}}),y_{\texttt{sl}})$ is the sample-based loss
function.

Like supervised learning, we can make the i.i.d. assumption for DMOFs over
supervised learning problems.

######  Assumption 1 (I.I.D. Assumption).

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ over a supervised
learning problem ($\mathcal{X}$, $\ell$, $N$), the i.i.d. assumption assumes
that any $M\in\mathcal{M}$ is an $N$-letter product distribution of $\Phi(M)$
(i.e., $M=\Phi(M)^{\otimes N}$) where $\Phi(M)\in\Delta(\mathcal{X})$ can be
any distribution over $\mathcal{X}$. Namely, for any $M\in\mathcal{M}$, its
dataset $\mathcal{D}=\\{x_{n}\\}_{n\in[N]}$ is drawn in an i.i.d. manner from
$\Phi(M)$.

Combining the correlation introduced by supervised learning and the i.i.d.
assumption, we can obtain our first fast convergence result, as presented in
the following theorem.

######  Theorem 4.

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ over a supervised
learning problem ($\mathcal{X}$, $\ell$, $N$) that meets Assumption 1, for any
$M\in\mathcal{M}$, with probability at least $1-\delta$ over $\mathcal{D}\sim
M$, we have

$\displaystyle\textup{{EOEC}}_{4B/N}(M,\mathcal{M},\mathcal{D})\leq$
$\displaystyle
3\min_{\pi\in\Pi}\big{[}\mathcal{L}(M,\pi)\big{]}+\frac{8B}{N}\cdot\log(|\mathcal{M}|/\delta).$
(9)

As a consequence, by choosing $\lambda$ as $4B/N$, EDD has its loss bounded,
with probability at least $1-\delta$ over $\mathcal{D}^{\star}\sim M^{\star}$,
as

$\displaystyle\mathcal{L}(M^{\star},\widehat{p})\leq$ $\displaystyle
3\min_{\pi\in\Pi}\big{[}\mathcal{L}(M^{\star},\pi)\big{]}+\frac{8B}{N}\cdot\log(|\mathcal{M}|/\delta).$
(10)

There is a blowing up of the loss in the right hand side of Eq. 10. However,
as long as there is a $\pi\in\Pi$ that gives a small value of
$\mathcal{L}(M^{\star},\pi)$, this bound would be valuable. Moreover, this
blowing up can be easily mitigated by subtracting the optimal loss from
$\mathcal{L}(M,\pi)$ in the algorithm.

######  Proposition 1.

Under the same context as Theorem 4, by overloading the function
$\mathcal{L}(M,\pi)$ by
$\mathcal{L}(M,\pi)-\min_{\pi^{\prime}\in\Pi}\mathcal{L}(M,\pi^{\prime})$ in
EDD, choosing $\lambda$ as $4B/N$ ensures with probability at least $1-\delta$
over $\mathcal{D}^{\star}\sim M^{\star}$ that, EDD has its loss bounded as

$\displaystyle\mathcal{L}(M^{\star},\widehat{p})-\min_{\pi\in\Pi}\big{[}\mathcal{L}(M^{\star},\pi)\big{]}\leq\frac{8B}{N}\cdot\log(|\mathcal{M}|/\delta).$
(11)

The only crucial point to prove Proposition 1 is to show
$\mathcal{L}(M,\pi)-\min_{\pi^{\prime}\in\Pi}\mathcal{L}(M,\pi^{\prime})\in[0,B]$,
which is straightforward from the definition. With this, we can replace the
$\mathcal{L}$ in Theorem 4 and get Proposition 1.

#### Fast Convergence Rate in Supervised Learning

The fast convergence rate of supervised learning has been built in various
ways [Vapnik, 1998, Tolstikhin and Seldin, 2013], and thus the result is not
surprising. Nevertheless, as the focus of this paper is the partially
correlated offline decision making, we think that Theorem 4 is inspiring and
shows the power of the simple algorithm EDD.

###  6.2 Sequential Problems and Coverage Assumptions

This subsection derives the fast convergence rate for offline decision making
problems that are based on Markovian sequential problems, a typical example of
which is the Markov decision process (MDP), a.k.a. the general framework of
offline RL and OPE. The key distinguishing property of a Markovian sequential
problem is that its loss can be decomposed into a sequential form.

######  Definition 5 (Markovian Sequential Problems).

We say that a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ is over a
sequential problem
$(\mathcal{P},\mathcal{M},\\{\mathcal{S}_{h}\\}_{h\in[H]},\\{\mathcal{A}\\}_{h\in[H]},\Pi,\ell,N)$
if the following holds.

  1. 1.

Given $\pi\in\Pi$ and $M\in\mathcal{M}$, there exists a stochastic process
$\\{(s_{h},a_{h})\\}_{h\in[H]}$ from the space
$\mathcal{S}\otimes\mathcal{A}\coloneqq{(\mathcal{S}_{1}\times\mathcal{A}_{1})\times(\mathcal{S}_{1}\times\mathcal{A}_{1})\times\dots(\mathcal{S}_{H}\times\mathcal{A}_{H})}$
such that $s_{1}\sim\mathcal{P}(\cdot|M,1)$, and for all $h\in[H]$,
$a_{h}\sim\pi(\cdot|h,\\{s_{i},a_{i}\\}_{i\in[h-1]},s_{h})$,
$s_{h+1}\sim\mathcal{P}(\cdot|M,h,s_{h},a_{h})$. We denote the margin of
$(s_{h},a_{h})$ w.r.t. the process as $\mathcal{T}(\cdot|M,\pi,h)$, and the
probability of the whole process as $\mathcal{T}(\cdot|M,\pi)$.

  2. 2.

The loss is defined as
$\mathcal{L}(M,\pi)\coloneqq\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\ell(\\{(s_{h},a_{h})\\}_{h\in[H]},\pi)$,
where $\ell\in((\mathcal{S}\otimes\mathcal{A})\times\Pi\to[0,B])$.

In such a case, we call $H\geq 0$ the _horizon_ of this Markovian sequential
problem. We will also add the subscript $M$ when indicating concepts from a
specific $M$.

######  Remark 4 (A Comparison Between Markovian Sequential Problems and
MDPs).

Markovian sequential problem is a generalization of MDPs and enjoys the
following comprehensiveness:

  * •

its policy is non-Markovian and can be based on the whole history;

  * •

instead of the summation of scalar rewards across the trajectory in MDPs, its
loss (namely, reversed return) can be any function on the whole history (we
merge the reward into the state space $\mathcal{S}$). It can even be a
function of the policy, which is typically useful in some settings like risk-
sensitive offline RL [Urpí et al., 2021, Rigter et al., 2023].

Based on the above definition, we now make the i.i.d. assumption for _the
whole trajectories_ in the dataset. Note that we only assume i.i.d. across
trajectories, and samples from one trajectory still can be dependent.

######  Assumption 2 (I.I.D. Assumption on a Sequential Problem).

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ over a Markovian
sequential problem
$(\mathcal{P},\mathcal{M},\\{\mathcal{S}_{h}\\}_{h\in[H]},\\{\mathcal{A}_{h}\\}_{h\in[H]},\Pi,\ell,N)$,
the i.i.d. assumption assumes that for all $M\in\mathcal{M}$, its dataset
$\mathcal{D}\sim M$ consists of $N$ sequences
$\\{(s_{h,n},a_{h,n},s_{h,n}^{\prime})\\}_{h\in[H],n\in[N]}$ that are drawn in
an i.i.d. manner from $\Phi(M)$ for all $n\in[N]$ and
$s_{h,n}^{\prime}\sim\mathcal{P}(\cdot|M,\pi,s_{h,n},a_{h,n})$. We denote the
margin of $(s_{h,n},a_{h,h})$ as $d^{\mathcal{D}}_{h}(\cdot|M)$.

######  Remark 5.

There are similar assumptions but made for MDPs (e.g., Rashidinejad et al.
[2021], Xie et al. [2021a], Cheng et al. [2022], Zhan et al. [2022], Huang et
al. [2023]) in offline decision making literatures, which is simply an
specification Assumption 2. Some of them (e.g., Li et al. [2022], Xiong et al.
[2023], Di et al. [2023]) further require that $s_{h+1,n}=s_{h,n}^{\prime}$
and each trajectory from the dataset is an interaction generated by a fixed
policy, which is more stringent compared with ours.

We then define the coverage assumption, which confirms that the dataset can
explain the behaviour of a policy.

######  Assumption 3 (Coverage Assumption).

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ over a Markovian
sequential problem
$(\mathcal{P},\mathcal{M},\\{\mathcal{S}_{h}\\}_{h\in[H]},\\{\mathcal{A}_{h}\\}_{h\in[H]},\Pi,\ell,N)$
and real model $M^{\star}\in\mathcal{M}$ that meet Assumption 2, The coverage
assumes that there are a policy $\widebar{\pi}\in\Pi$ and a constant
$C_{\widebar{\pi}}\geq 0$ such that

$\displaystyle\max_{h\in[H]}\Big{\lVert}\frac{\mathcal{T}(\cdot|M^{\star},\widebar{\pi},h)}{d^{\mathcal{D}}_{h}(\cdot|M^{\star})}\Big{\rVert}_{\infty}\leq
C_{\widebar{\pi}}.$ (12)

######  Remark 6.

The overage assumption is standard offline decision making, and can be found
in a wide range of works (e.g., Rashidinejad et al. [2021], Chen and Jiang
[2022], Zhan et al. [2022], Li et al. [2022], Huang et al. [2023]).

######  Remark 7.

Thought the paper, we do not assume that the models from $\mathcal{M}$ share
the same “underlying distribution,” which is widely done in offline decision
making. On the other hand, we only assume the coverage assumption about
$M^{\star}$.

As a consequence of the above assumptions, we will have the following fast
convergence theorem for Markovian sequential problems.

######  Theorem 5.

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ over a Markovian
sequential problem $(\mathcal{P}$, $\mathcal{M}$,
$\\{\mathcal{S}_{h}\\}_{h\in[H]}$, $\\{\mathcal{A}_{h}\\}_{h\in[H]}$, $\Pi$,
$\ell,N)$ and $M^{\star}\in\mathcal{M}$ that meet Assumption 2 and Assumption
3 w.r.t. the policy $\widebar{\pi}$ and the constant $C_{\widebar{\pi}}$, with
probability at least $1-\delta$ over $\mathcal{D}^{\star}\sim M^{\star}$, we
have that

$\displaystyle\textup{{EOEC}}_{\frac{400BC_{\widebar{\pi}}\log(2H)}{N}}(M^{\star},\mathcal{M},\mathcal{D}^{\star})\leq
3\mathcal{L}(M,\widebar{\pi})+\frac{1200BC_{\widebar{\pi}}\log(2H)}{N}\cdot\log\big{(}3H\cdot|\mathcal{M}|/\delta\big{)}.$

As a consequence, by choosing $\lambda$ as
$\frac{400BC_{\widebar{\pi}}\log(2H)}{N}$ in EDD, with probability at least
$1-\delta$ over $\mathcal{D}^{\star}\sim M^{\star}$, EDD has that

$\displaystyle\mathcal{L}(M^{\star},\widehat{p})\leq
3\mathcal{L}(M,\widebar{\pi})+\frac{1200BC_{\widebar{\pi}}\log(2H)}{N}\cdot\log\big{(}3H\cdot|\mathcal{M}|/\delta\big{)}.$
(13)

We further specify the above theorem in offline RL in the following
proposition, which is a direct consequence of the it.

######  Proposition 2.

Let us consider the setting introduced in Appendix A,222We overload the
notation as done in Example 1. by setting
$\mathcal{L}(M,\pi)=J_{M_{\texttt{rl}}}^{\star}-J_{M_{\texttt{rl}}}(\pi)$,
under the same context of Theorem 5, by choosing $\lambda$ as
$\frac{400BC_{\widebar{\pi}}\log(2H)}{N}$, with probability at least
$1-\delta$ over $\mathcal{D}^{\star}\sim M^{\star}$, EDD has that

$\displaystyle
J_{M^{\star}_{\texttt{rl}}}^{\star}-J_{M^{\star}_{\texttt{rl}}}(\widehat{p})\leq
3(J_{M^{\star}_{\texttt{rl}}}^{\star}-J_{M^{\star}_{\texttt{rl}}}(\widebar{\pi}))+\frac{1200BC_{\widebar{\pi}}\log(2H)}{N}\cdot\log\big{(}3H\cdot|\mathcal{M}|/\delta\big{)}.$
(14)

In case we have optimal coverage (i.e., $\widebar{\pi}=\pi^{\star}$), by
choosing $\lambda$ as $\frac{400BC_{\widebar{\pi}}\log(2H)}{N}$, with
probability at least $1-\delta$ over $\mathcal{D}\sim M^{\star}$, EDD has that

$\displaystyle
J_{M^{\star}_{\texttt{rl}}}^{\star}-J_{M^{\star}_{\texttt{rl}}}(\widehat{p})\leq\frac{1200BC_{\pi^{\star}}\log(2H)}{N}\cdot\log\big{(}3H\cdot|\mathcal{M}|/\delta\big{)}.$
(15)

#### Compensating the Existing Bounds in Toy Settings

Let us compare our bound with the ones in some specific settings. While there
have already been lower bounds in offline tabular RL and offline linear RL
with $1/\sqrt{N}$ convergence rates [Xie et al., 2021b, Xiong et al., 2023],
this does not contrast our fast convergence results. Concretely, in offline
tabular, we can forge a model class with covering number approximately
$\exp(S^{2}AH)$ and thus conclude the $\mathcal{O}(S^{2}AHC_{\pi^{\star}}/N)$
upper bounds with Theorem 5 (namely, the
$\mathcal{O}(S^{2}AHC_{\pi^{\star}}/\epsilon)$ sample complexity where
$\epsilon$ is the sub-optimality rate), which, compared with the
$\sqrt{H^{4}SC_{\pi^{\star}}/N}$ lower bound in offline tabular RL (i.e., the
$\mathcal{O}(H^{4}SC_{\pi^{\star}}/\epsilon^{2})$ sample complexity), enjoys
its own significant.333$S$ is the number of the state, $A$ is the number of
action, and $H$ is the horizon. As for the linear RL, our coverage assumption
(Assumption 3) differs from the coverage measure designed for the linear
setting [Yin et al., 2020], which disentangles our results from the lower
bound and the bounds are thus incomparable. After all, we would like to
emphasize the novelty of the fast convergence rate when we have a large
dataset.

#### Compare with Results in Model-based Offline RL with General Function
Approximation

Our works in this subsection share similarities with Uehara and Sun [2021],
Bhardwaj et al. [2023], but enjoy a substantial improvement. On the one hand,
both their results converge in $\mathcal{O}(\sqrt{\log(M)/N})$, which is the
square root of ours.444Note that for a convergence, we would always want
$\sqrt{\log(M)/N}\leq 1$. On the other hand, our setting is based on Markovian
sequential problems which is more general.

#### Faster Convergence Rate in Sequential Problems

There are only a few works in offline decision making concerning faster
convergence rate compared with $1/\sqrt{N}$ as we are aware. They either adapt
the gap of optimal value function into the performance [Hu et al., 2021, Wang
et al., 2022, Nguyen-Tang et al., 2023], or assume specific structures for the
problem (e.g., deterministic dynamics [Uehara et al., 2021, Yin et al.,
2022b]). In contrast, our fast convergence applies to all Markovian sequential
problems without the need for the gap, which yields a more satisfactory
theory.

##  7 Conclusion

This paper introduces a general framework named Decision Making with Offline
Feedback (DMOF) for offline decision making, together with a complexity
measure named offline estimation coefficient (OEC). We introduce an
information-theoretic lower bound with OEC for DMOF, and also propose an
algorithm named Empirical Decision with Divergence (EDD) in response. We show
that EDD has an instance-dependent bound, which matches the lower bound in the
minimax case. Moreover, we show EDD can achieve the fast convergence rate of
$1/N$ in some specific settings like supervised learning and Markovian
sequential problems.

Here we highlight some possible further directions from this paper. Firstly,
while this paper is an offline work influenced by Foster et al. [2021a] in the
online setting, results in this paper can also have its online extension and
may enhance the results for DEC. Additionally, as our results in this paper
are based on model-based general function approximation, it would be
interesting to concretize our result, and extend it to model-free functions
and to special settings like POMDPs. Finally, there is a blowing up in the
loss in Theorem 5, which we mitigate with optimal coverage assumption. More
work is needed to understand if there is a way to relieve this blowing up for
any covered policy $\widebar{\pi}$.

## References

  * Alquier [2023] Pierre Alquier.  User-friendly introduction to pac-bayes bounds, 2023.
  * Antos et al. [2006] András Antos, Csaba Szepesvari, and Rémi Munos.  Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path.  _Machine Learning_ , 71:89–129, 2006.
  * Bertsekas and Tsitsiklis [1996] Dimitri Bertsekas and John N Tsitsiklis.  _Neuro-dynamic programming_.  Athena Scientific, 1996.
  * Bhardwaj et al. [2023] Mohak Bhardwaj, Tengyang Xie, Byron Boots, Nan Jiang, and Ching-An Cheng.  Adversarial model for offline reinforcement learning, 2023.
  * Chen et al. [2024] Fan Chen, Song Mei, and Yu Bai.  Unified algorithms for rl with decision-estimation coefficients: Pac, reward-free, preference-based learning, and beyond, 2024.
  * Chen and Jiang [2019] Jinglin Chen and Nan Jiang.  Information-theoretic considerations in batch reinforcement learning.  _ArXiv_ , abs/1905.00360, 2019.
  * Chen and Jiang [2022] Jinglin Chen and Nan Jiang.  Offline reinforcement learning under value and density-ratio realizability: the power of gaps.  2022\.
  * Cheng et al. [2022] Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal.  Adversarially trained actor critic for offline reinforcement learning.  _ArXiv_ , abs/2202.02446, 2022.
  * Di et al. [2023] Qiwei Di, Heyang Zhao, Jiafan He, and Quanquan Gu.  Pessimistic nonlinear least-squares value iteration for offline reinforcement learning, 2023.
  * Duan and Wang [2020] Yaqi Duan and Mengdi Wang.  Minimax-optimal off-policy evaluation with linear function approximation, 2020.
  * Farajtabar et al. [2018] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh.  More robust doubly robust off-policy evaluation, 2018.
  * Felipe [2016] Felipe.  Prove the countable additivity of lebesgue integral.  Mathematics Stack Exchange, 2016.  URL https://math.stackexchange.com/q/668958.  URL:https://math.stackexchange.com/q/668958 (version: 2016-04-05).
  * Foster et al. [2021a] Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making, Aug. 7 2021a.
  * Foster et al. [2021b] Dylan J. Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu.  Offline reinforcement learning: Fundamental barriers for value function approximation.  In _Annual Conference Computational Learning Theory_ , 2021b.
  * Foster et al. [2022] Dylan J. Foster, Alexander Rakhlin, Ayush Sekhari, and Karthik Sridharan.  On the complexity of adversarial decision making, 2022.
  * Foster et al. [2023a] Dylan J. Foster, Dean P. Foster, Noah Golowich, and Alexander Rakhlin.  On the complexity of multi-agent decision making: From learning in games to partial monitoring, 2023a.
  * Foster et al. [2023b] Dylan J. Foster, Noah Golowich, and Yanjun Han.  Tight guarantees for interactive decision making with the decision-estimation coefficient, 2023b.
  * Foster et al. [2023c] Dylan J. Foster, Noah Golowich, Jian Qian, Alexander Rakhlin, and Ayush Sekhari.  Model-free reinforcement learning with the decision-estimation coefficient, 2023c.
  * He et al. [2021] Jiafan He, Dongruo Zhou, and Quanquan Gu.  Logarithmic regret for reinforcement learning with linear function approximation.  In _International Conference on Machine Learning_ , pages 4171–4180. PMLR, 2021.
  * Hu et al. [2021] Yichun Hu, Nathan Kallus, and Masatoshi Uehara.  Fast rates for the regret of offline reinforcement learning.  _arXiv preprint arXiv:2102.00479_ , 2021.
  * Huang and Jiang [2022] Audrey Huang and Nan Jiang.  Beyond the return: Off-policy function estimation under user-specified error-measuring distributions.  _ArXiv_ , abs/2210.15543, 2022.
  * Huang et al. [2023] Audrey Huang, Jinglin Chen, and Nan Jiang.  Reinforcement learning in low-rank mdps with density features.  _ArXiv_ , abs/2302.02252, 2023.
  * Jiang and Huang [2020] Nan Jiang and Jiawei Huang.  Minimax value interval for off-policy evaluation and policy optimization.  _arXiv: Learning_ , 2020.
  * Jin et al. [2020] Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is pessimism provably efficient for offline rl?  In _International Conference on Machine Learning_ , 2020.
  * Lange et al. [2012] Sascha Lange, Thomas Gabel, and Martin A. Riedmiller.  Batch reinforcement learning.  In _Reinforcement Learning_ , 2012.
  * Levine et al. [2020] Sergey Levine, Aviral Kumar, G. Tucker, and Justin Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _ArXiv_ , abs/2005.01643, 2020.
  * Li et al. [2022] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei.  Settling the sample complexity of model-based offline reinforcement learning.  _ArXiv_ , abs/2204.05275, 2022.
  * Li et al. [2011] Lihong Li, Wei Chu, John Langford, and Xuanhui Wang.  Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms.  In _Proceedings of the fourth ACM international conference on Web search and data mining_ , WSDM’11. ACM, February 2011.  doi: 10.1145/1935826.1935878.  URL http://dx.doi.org/10.1145/1935826.1935878.
  * Liu et al. [2018] Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou.  Breaking the curse of horizon: Infinite-horizon off-policy estimation.  In _Neural Information Processing Systems_ , 2018.
  * Liu et al. [2020] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill.  Provably good batch reinforcement learning without great exploration.  _ArXiv_ , abs/2007.08202, 2020.
  * Mao et al. [2024] Chenjie Mao, Qiaosheng Zhang, Zhen Wang, and Xuelong Li.  On the role of general function approximation in offline reinforcement learning.  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=JSS9rKHySk.
  * McAllester [1998] David A. McAllester.  Some pac-bayesian theorems.  _Machine Learning_ , 37:355–363, 1998.
  * McAllester [1999] David A. McAllester.  Pac-bayesian model averaging.  In _Annual Conference Computational Learning Theory_ , 1999.
  * Min et al. [2022] Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu.  Variance-aware off-policy evaluation with linear function approximation, 2022.
  * Nguyen-Tang et al. [2023] Thanh Nguyen-Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora.  On instance-dependent bounds for offline reinforcement learning with linear function approximation, 2023.
  * Ohnishi and Honorio [2020] Yuki Ohnishi and Jean Honorio.  Novel change of measure inequalities with applications to pac-bayesian bounds and monte carlo estimation, 2020.
  * Pananjady and Wainwright [2020] Ashwin Pananjady and Martin J. Wainwright.  Instance-dependent $\ell_{\infty}$-bounds for policy evaluation in tabular reinforcement learning, 2020.
  * Polyanskiy and Wu [2022] Yury Polyanskiy and Yihong Wu.  Information theory: From coding to learning.  Cambridge University Press, 2022.  URL https://people.lids.mit.edu/yp/homepage/data/itbook-export.pdf.
  * Puterman [1994] Martin L. Puterman.  Markov decision processes: Discrete stochastic dynamic programming.  In _Wiley Series in Probability and Statistics_ , 1994.
  * Rashidinejad et al. [2021] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart J. Russell.  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  _IEEE Transactions on Information Theory_ , 68:8156–8196, 2021.
  * Rigter et al. [2023] Marc Rigter, Bruno Lacerda, and Nick Hawes.  One risk to rule them all: A risk-sensitive perspective on model-based offline reinforcement learning, 2023.
  * Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning - From Theory to Algorithms._ Cambridge University Press, 2014.  ISBN 978-1-10-705713-5.
  * Shawe-Taylor and Williamson [1997] John Shawe-Taylor and Robert C. Williamson.  A pac analysis of a bayesian estimator.  In _Annual Conference Computational Learning Theory_ , 1997.
  * Simchowitz and Jamieson [2019] Max Simchowitz and Kevin G Jamieson.  Non-asymptotic gap-dependent regret bounds for tabular mdps.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Stroock [2011] Daniel W. Stroock.  Essentials of integration theory for analysis.  _Graduate Texts in Mathematics_ , 2011.
  * Thomas and Brunskill [2016] Philip S. Thomas and Emma Brunskill.  Data-efficient off-policy policy evaluation for reinforcement learning, 2016.
  * Tolstikhin and Seldin [2013] Ilya O Tolstikhin and Yevgeny Seldin.  Pac-bayes-empirical-bernstein inequality.  In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 26. Curran Associates, Inc., 2013.  URL https://proceedings.neurips.cc/paper_files/paper/2013/file/a97da629b098b75c294dffdc3e463904-Paper.pdf.
  * Uehara and Sun [2021] Masatoshi Uehara and Wen Sun.  Pessimistic model-based offline reinforcement learning under partial coverage.  In _International Conference on Learning Representations_ , 2021.
  * Uehara et al. [2019] Masatoshi Uehara, Jiawei Huang, and Nan Jiang.  Minimax weight and q-function learning for off-policy evaluation.  In _International Conference on Machine Learning_ , 2019.
  * Uehara et al. [2021] Masatoshi Uehara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie.  Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency.  _arXiv preprint arXiv:2102.02981_ , 2021.
  * Uehara et al. [2022] Masatoshi Uehara, Chengchun Shi, and Nathan Kallus.  A review of off-policy evaluation in reinforcement learning, 2022.
  * Urpí et al. [2021] Núria Armengol Urpí, Sebastian Curi, and Andreas Krause.  Risk-averse offline reinforcement learning.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=TBIzh9b5eaz.
  * Vapnik [1998] Vladimir N. Vapnik.  _Statistical Learning Theory_.  Wiley-Interscience, 1998.
  * Wang et al. [2022] Xinqi Wang, Qiwen Cui, and Simon S Du.  On gap-dependent bounds for offline reinforcement learning.  _arXiv preprint arXiv:2206.00177_ , 2022.
  * Xie and Jiang [2020] Tengyang Xie and Nan Jiang.  Batch value-function approximation with only realizability.  _ArXiv_ , abs/2008.04990, 2020.
  * Xie et al. [2021a] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  In _Neural Information Processing Systems_ , 2021a.
  * Xie et al. [2021b] Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai.  Policy finetuning: Bridging sample-efficient offline and online reinforcement learning.  In _Neural Information Processing Systems_ , 2021b.
  * Xiong et al. [2023] Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang.  Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game, 2023.
  * Xu et al. [2021] Haike Xu, Tengyu Ma, and Simon Du.  Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap.  In _Conference on Learning Theory_ , pages 4438–4472. PMLR, 2021\.
  * Yin and Wang [2021] Ming Yin and Yu-Xiang Wang.  Towards instance-optimal offline reinforcement learning with pessimism, 2021.
  * Yin et al. [2020] Ming Yin, Yu Bai, and Yu-Xiang Wang.  Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning, 2020.
  * Yin et al. [2022a] Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang.  Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism, 2022a.
  * Yin et al. [2022b] Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang.  Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism.  _International Conference on Learning Representations_ , 2022b.
  * Yin et al. [2022c] Ming Yin, Mengdi Wang, and Yu-Xiang Wang.  Offline reinforcement learning with differentiable function approximation is provably efficient, 2022c.
  * Zhan et al. [2022] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D. Lee.  Offline reinforcement learning with realizability and single-policy concentrability.  _ArXiv_ , abs/2202.04634, 2022.

##  Appendix A A Short Introduction to Offline Reinforcement Learning

This section would shortly introduce offline reinforcement learning (offline
RL), i.e., learning with offline Markov decision processes (MDP). To
distinguish offline RL from DMOF, we would add the subscript rl when the
notations collapse.

For the pre-learning interaction part, we consider the time-inhomogeneous MDP.
Suppose that we have a MDP

$\displaystyle
M_{\texttt{rl}}\coloneqq(\\{\mathcal{S}_{h}\\}_{h\in[H]},\\{\mathcal{A}_{h}\\}_{h\in[H]},d_{1},\\{R_{h}\\}_{h\in[H]},\\{P_{h}\\}_{h\in[H]},\\{\Pi_{\texttt{rl},h}\\}_{h\in[H]}),$

where $\\{\mathcal{S}_{h}\\}_{h\in[H]}$ is the state spaces,
$\\{\mathcal{A}_{h}\\}_{h\in[H]}$ is the action spaces,
$d_{1}\in\Delta(\mathcal{S}_{1})$ is the initial state distribution,
$\\{R_{h}\\}_{h\in[H]}$ is the reward functions, $\\{P_{h}\\}_{h\in[H]}$ is
the transition kernel, $\\{\Pi_{h}\\}_{h\in[H]}$ is the policy space, and $H$
is the horizon. For simplicity, we further denote
$\mathcal{S}\coloneqq\\{\mathcal{S}_{h}\\}_{h\in[H]}$,
$\mathcal{A}\coloneqq\\{\mathcal{A}_{h}\\}_{h\in[H]}$,
$P\coloneqq\\{P_{h}\\}_{h\in[H]}$, and
$\Pi_{\texttt{rl}}\coloneqq\\{\Pi_{\texttt{rl},h}\\}_{h\in[H]}$.

In the model-based setting, there will be a model $\mathcal{M}_{\texttt{rl}}$
being a set of MDPs which only differ in $\\{P_{h}\\}_{h\in[H]}$ and
$\\{R_{h}\\}_{h\in[H]}$ (mostly only $\\{P_{h}\\}_{h\in[H]}$).

Given a police $\pi\coloneqq\\{\pi_{\texttt{rl},h}\\}_{h\in[H]}$ where
$\pi_{\texttt{rl},h}\in\Pi_{\texttt{rl},h}$ for $h\in[H]$ and a real model
$M^{\star}_{\texttt{rl}}$, we would interact with the MDP according to the
following protocol.

  * •

We first sample a initial state $s_{1}$ from $d_{1}$.

  * •

for every $h\in[H]$, we would take the action
$a_{h}\sim\pi_{\texttt{rl},h}(s_{h})$, receive the reward
$R_{h}^{\star}(s_{h},a_{h})$ and transit to the next state $s_{h+1}\sim
P^{\star}_{h}(\cdot|s_{h},a_{h})$; at the step $h=H$, we will
deterministically transfer to the ending state $s_{H+1}$. Both $R^{\star}$ and
$P^{\star}$ come from $M_{\texttt{rl}}^{\star}$.

Our goal is to maximize the cumulative reward, namely,
$J_{M_{\texttt{rl}}^{\star}}(\pi)\coloneqq\mathbb{E}\sum_{h\in[H]}R_{h}(s_{h},a_{h})$
(we will broadcast this definition to other
$M_{\texttt{rl}}\in\mathcal{M}_{\texttt{rl}}$). We assume
$J_{M_{\texttt{rl}}}(\pi_{\texttt{rl}})\in[0,B]$ for all
$M_{\texttt{rl}}\in\mathcal{M}_{\texttt{rl}}$ and
$\pi_{\texttt{rl}}\in\Pi_{\texttt{rl}}$. Given a distribution $p$ over $\Pi$,
we define $J_{M_{\texttt{rl}}}(p)\coloneqq\mathbb{E}_{\pi_{\texttt{rl}}\sim
p}J_{M_{\texttt{rl}}}(pi_{\texttt{rl}})$. We further denote
$\pi^{\star}_{\texttt{rl},M}\coloneqq\operatorname*{argmax}_{\pi_{\texttt{rl}}\in\Pi_{\texttt{rl}}}J_{M_{\texttt{rl}}}(\pi_{\texttt{rl}})$
and $J^{\star}_{M_{\texttt{rl}}}\coloneqq
J_{M_{\texttt{rl}}}(\pi^{\star}_{\texttt{rl},M})$.

For the offline learning part, we are given with the dataset
$\mathcal{D}_{\texttt{rl}}^{\star}\coloneqq\\{(s_{h,n},a_{h,n},r_{h,n},s_{h,n}^{\prime})\\}_{h\in[H],n\in[N]}$
where $N$ is the number of samples, and aim to learn a policy
$\pi_{\texttt{rl}}$ to maximize $J_{M_{\texttt{rl}}^{\star}}(\pi)$. Typically
we will have that $r_{h,n}=R_{h}^{\star}(s_{h,n},a_{h,n})$ and
$s^{\prime}_{h,n}\sim P_{h}^{\star}(\cdot|s_{h,n},a_{h,n})$.555Note that some
works also assume that $s_{h+1,n}=s_{h,n}^{\prime}$, which can be achieved by
specifying the above framework. To gain a converging result, offline RL always
makes the i.i.d. assumption, namely, there is a data distribution
$d^{\mathcal{D}}\coloneqq\\{d^{\mathcal{D}}_{h}\\}_{h\in[H]}$ that for all
$n\in[N]$, we have $(s_{h,n},a_{h,n})\sim d^{\mathcal{D}}_{h}$, and
$(s_{h,n},a_{h,n},r_{h,n},s_{h,n}^{\prime})$ are independent of each other
across $n\in[N]$ for all $h\in[H]$.

##  Appendix B Some Useful Results in Probability and Statistics

######  Lemma 3.

Given a measurable space $(\Omega,\mathcal{E})$, and two measures $\phi$ and
$\nu$ such that $\phi$ is absolutely continuous w.r.t. $\nu$, for any real
valued measurable function $f$ on $\Omega$,

$\displaystyle\int f(x)\frac{d\phi(x)}{d\nu(x)}\nu(dx)=\int f(x)\phi(dx).$

###### Proof.

We can prove the case that $f$ is _simple_ , and the extension to the other
cases should be straightforward due to the definition of the Lebesgue
integral.666We follow the definitions from Stroock [2011].

Defining the set $\mathcal{B}\coloneqq\\{f^{-1}(y)|y\in\mathbb{R}\\}$, we must
have $\bigcup_{B\in\mathcal{B}}=\Omega$. $\mathcal{B}$ is countable and
consists of disjoint measurable sets since $f$ is simple and measurable. For
$B\in\mathcal{B}$, we denote $f(B)$ as the value of $f$ for any element
belonging to $B$. Due to the definition of the Lebesgue integral,

$\displaystyle\int f(x)\phi(dx)=$
$\displaystyle\sum\limits_{B\in\mathcal{B}}f(B)\phi(B)$ $\displaystyle=$
$\displaystyle\sum\limits_{B\in\mathcal{B}}f(B)\int_{B}\frac{d\phi(x)}{d\nu(x)}\nu(dx)$
$\displaystyle=$
$\displaystyle\sum\limits_{B\in\mathcal{B}}\int_{B}f(x)\frac{d\phi(x)}{d\nu(x)}\nu(dx)$
$\displaystyle=$ $\displaystyle\int f(x)\frac{d\phi(x)}{d\nu(x)}\nu(dx).$

The last equality is justified by the additivity of the Lebesgue integration
[Felipe, 2016]. This completes the proof. ∎

###  B.1 Change of Measure Properties

One of the main properties of the $f$-divergence exploited in this paper (as
done in Foster et al. [2021a]) is the _change of measure_ property.
Concretely, the change of measure property is concerned with changing the
probability measure underlying an expectation, with the cost of a divergence
between the probabilities, plus a possible variation on the function in the
expectation. The change of measure inequalities of $f$-divergences are
essential in learning theory, especially in fields like PAC-Bayesian learning
[Shawe-Taylor and Williamson, 1997, McAllester, 1998, 1999, Alquier, 2023].

We briefly state some results about change of measure properties in this
subsection, and would like to refer interested readers to Ohnishi and Honorio
[2020] for a more comprehensive review of the change of measure inequalities.
Also note that this paper would focus on some refined change of measure
properties, which would be explained in more detail in Appendix F.

We first state the classic _Donsker and Varadhan variational formula_ in the
following lemma.

######  Lemma 4 (Donsker and Varadhan’s Formula).

Let $X$ be a real-valued random variable (r.v.) over $\mathcal{X}$,
$h:\mathcal{X}\to\mathbb{R}$ be a real-valued function, and $\rho,\pi$ be
probability measures over $\mathcal{X}$, we have that

$\displaystyle\textup{KL}(\rho\rVert\pi)=\max_{h}\Big{[}\mathbb{E}_{X\sim\rho}[h(X)]-\log\mathbb{E}_{X\sim\pi}[\exp(h(X))]\Big{]}.$
(16)

The following shows the change of measure property of the total variation
distance.

######  Lemma 5.

Given a measurable space $(\Omega,\mathcal{E})$, two probabilities
$\mathbb{P}$ and $\mathbb{Q}$, and a positive number $\beta>0$, for any real-
valued measurable function $f$ on $\Omega$ with range $[0,\beta]$,

$\displaystyle\big{|}\mathbb{E}_{\mathbb{P}}[f]-\mathbb{E}_{\mathbb{Q}}[f]\big{|}\leq
2\beta\textup{{TV}}(\mathbb{P},\mathbb{Q}).$

###### Proof.

Take $\nu\coloneqq\mathbb{P}+\mathbb{Q}$ as the dominating measure, we have
that

$\displaystyle\textup{{TV}}(\mathbb{P},\mathbb{Q})=$
$\displaystyle\frac{\int\Big{|}\frac{d\mathbb{P}}{d\nu}-\frac{d\mathbb{Q}}{d\nu}\Big{|}d\nu}{2}$
$\displaystyle=$
$\displaystyle\frac{\int\beta\Big{|}\frac{d\mathbb{P}(x)}{d\nu(x)}-\frac{d\mathbb{Q}(x)}{d\nu(x)}\Big{|}\nu(dx)}{2\beta}$
$\displaystyle\geq$ $\displaystyle\frac{\int
f(x)\Big{|}\frac{d\mathbb{P}(x)}{d\nu(x)}-\frac{d\mathbb{Q}(x)}{d\nu(x)}\Big{|}\nu(dx)}{2\beta}$
$\displaystyle=$
$\displaystyle\frac{\int\Big{|}f(x)\frac{d\mathbb{P}(x)}{d\nu(x)}-f(x)\frac{d\mathbb{Q}(x)}{d\nu(x)}\Big{|}\nu(dx)}{2\beta}$
$\displaystyle\geq$
$\displaystyle\frac{\Big{|}\int\Big{(}f(x)\frac{d\mathbb{P}(x)}{d\nu(x)}-f(x)\frac{d\mathbb{Q}(x)}{d\nu(x)}\Big{)}\nu(dx)\Big{|}}{2\beta}$
(Jensen’s inequality) $\displaystyle=$
$\displaystyle\frac{\Big{|}\int\big{(}f(x)\frac{d\mathbb{P}(x)}{d\nu(x)}\big{)}\nu(dx)-\int\big{(}f(x)\frac{d\mathbb{Q}(x)}{d\nu(x)}\big{)}\nu(dx)\Big{|}}{2\beta}$
$\displaystyle=$
$\displaystyle\frac{\big{|}\mathbb{E}_{\mathbb{P}}[f]-\mathbb{E}_{\mathbb{Q}}[f]\big{|}}{2\beta}$
(Lemma 3)

The fifth inequality is due to Jensen’s inequality and the fact that the
absolute value function is convex.

This completes the proof. ∎

Also, there is a similar result for the squared Hellinger distance.

######  Lemma 6 (Trimmed Lemma A.11 in Foster et al. [2021a]).

Let $\mathbb{P}$ and $\mathbb{Q}$ be probability measures on
$(\mathcal{X},\mathcal{F})$, for all $g:\mathcal{X}\to[0,B]$,

$\displaystyle\mathbb{E}_{X\sim\mathbb{P}}[g(X)]\leq
3\mathbb{E}_{X\sim\mathbb{Q}}[g(X)]+4B\cdot\textup{{H}}^{2}(\mathbb{P},\mathbb{Q}).$

###### Proof.

See Foster et al. [2021a]. ∎

##  Appendix C Missing Proofs in Section 4

###  C.1 Proof for Theorem 1

This subsection provides a proof for Theorem 1. The proof is simple yet
instructive, which mainly depends on two techniques:

  * •

the refined change of measure property of the squared Hellinger distance,
i.e., the difference of the expected value of a function on a random variable
can be bounded by the squared Hellinger distance (Lemma 6); we summarize this
property in Appendix F.

  * •

the trick from Foster et al. [2021a]—if the distribution of the input of the
algorithm is prefixed, we can replace the algorithm’s output with a term from
$\Delta(\Pi)$.

###### Proof of Theorem 1.

Fix $A\subseteq\Delta(\mathcal{O}$). For any algorithm $\mathfrak{A}$, we can
rewrite its worst case performance as

$\displaystyle\max\limits_{M\in\mathcal{M}}\mathbb{E}_{\mathcal{D}\sim
M}\big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\big{]}$ (17)
$\displaystyle=$ $\displaystyle\max\limits_{\rho\in
A}\max\limits_{M\in\mathcal{M}}\mathbb{E}_{\mathcal{D}\sim
M}\big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\big{]}$ (18)
$\displaystyle\geq$ $\displaystyle\frac{1}{3}\max\limits_{\rho\in
A}\max\limits_{M\in\mathcal{M}}\Big{[}\mathbb{E}_{\mathcal{D}\sim\rho}\big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\big{]}-4B\cdot\textup{{H}${}^{2}$}(\rho,M)\Big{]},$
(19)

where the last inequality follows from Lemma 6, for which we take the whole
$\mathcal{L}(M,\mathfrak{A}(\cdot))$ as a function. We can then apply the
trick from Foster et al. [2021a]: _as the algorithm only takes the dataset
generated by $\rho$ as input, the distribution of the output policy would be
fixed given $\rho$ and $\mathfrak{A}$._ More precisely, given
$\mathcal{D}\sim\rho$, let $\widehat{\pi}$ denotes the output policy, we will
have that

$\displaystyle\widehat{\pi}\sim\mathfrak{A}(\mathcal{D})$

regardless of the choice of $M\in\mathcal{M}$. This means that we can insert a
$\min$ on the distribution of policies after $\max_{\rho\in A}$. Denoting the
distribution of $\widehat{\pi}$ as $\widehat{p}(\rho)$, we have that

$\displaystyle\max\limits_{M\in\mathcal{M}}\mathbb{E}_{\mathcal{D}\sim
M}\big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\big{]}$ (20)
$\displaystyle\geq$ $\displaystyle\frac{1}{3}\max\limits_{\rho\in
A}\max\limits_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,\widehat{p}(\rho))-4B\cdot\textup{{H}${}^{2}$}(\rho,M)\Big{]}$
(21) $\displaystyle=$ $\displaystyle\frac{1}{3}\max\limits_{\rho\in
A}\min\limits_{p\in\Delta(\Pi)}\max\limits_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,p)-4B\cdot\textup{{H}${}^{2}$}(\rho,M)\Big{]}$
(22) $\displaystyle=$
$\displaystyle\frac{1}{3}\textup{{OEC}}_{4B}(\mathcal{M},A).$ (23)

This completes the proof. ∎

##  Appendix D Missing Proofs in Section 5

###  D.1 Some Helper Lemmas

The following lemma presents a relation between the log-likelihood and the
squared Hellinger distance.

######  Lemma 7 (Union Bound of the Log-Likelihood).

Let $\mathcal{P}$ be a set of probability measures, and $\mathcal{D}$ be a
dataset where $\mathcal{D}\sim p^{\star}$ for some $p^{\star}\in\mathcal{P}$.
Then, with probability at least $1-\delta$ over $\mathcal{D}\sim p^{\star}$,
for all $p\in\mathcal{P}$,

$\displaystyle-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+\textup{{H}}^{2}(p^{\star},p)\leq
2\log(|\mathcal{P}|/\delta).$

###### Proof.

We first fix $p\in\mathcal{P}$, and take

$\displaystyle
L(\mathcal{D})\coloneqq-\frac{1}{2}\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))-\log{\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\star}}\big{[}\sqrt{p(\mathcal{D}^{\prime})/p^{\star}(\mathcal{D}^{\prime})}\big{]}}.$

We have the moment generating function of $L(\mathcal{D})$ be $1$ at the value
$1$,

$\displaystyle\mathbb{E}_{\mathcal{D}\sim
p^{\star}}\Big{[}\exp\big{(}L(\mathcal{D})\big{)}\Big{]}=$
$\displaystyle\mathbb{E}_{\mathcal{D}\sim
p^{\star}}\Big{[}\exp\big{(}-\frac{1}{2}\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))-\log{\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\star}}\big{[}\sqrt{p(\mathcal{D}^{\prime})/p^{\star}(\mathcal{D}^{\prime})}\big{]}}\big{)}\Big{]}$
$\displaystyle=$ $\displaystyle\frac{\mathbb{E}_{\mathcal{D}\sim
p^{\star}}\Big{[}\exp\big{(}-\frac{1}{2}\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))\big{)}\Big{]}}{\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\star}}\big{[}\sqrt{p(\mathcal{D}^{\prime})/p^{\star}(\mathcal{D}^{\prime})}\big{]}}$
$\displaystyle=$ $\displaystyle 1.$

We can then apply the Chernoff bound, which yields that

$\displaystyle\mathbb{P}_{\mathcal{D}\sim
p^{\star}}\big{(}L(\mathcal{D})\geq\epsilon\big{)}\leq$
$\displaystyle\frac{\mathbb{E}_{\mathcal{D}\sim
p^{\star}}\Big{[}\exp\big{(}L(\mathcal{D})\big{)}\Big{]}}{\exp(\epsilon)}=\exp(-\epsilon).$

Further, by the definition of the squared Hellinger distance,

$\displaystyle\mathbb{P}_{\mathcal{D}\sim
p^{\star}}\big{(}-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+\textup{{H}}^{2}(p^{\star},p)\geq\epsilon\big{)}$
$\displaystyle=$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim
p^{\star}}\big{(}-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+2-2\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\star}}\big{[}\sqrt{p(\mathcal{D}^{\prime})/p^{\star}(\mathcal{D}^{\prime})}\big{]}\geq\epsilon\big{)}$
$\displaystyle=$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim
p^{\star}}\big{(}-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+2-2\exp\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\star}}\big{[}\sqrt{p(\mathcal{D}^{\prime})/p^{\star}(\mathcal{D}^{\prime})}\big{]}\geq\epsilon\big{)}$

Due to the fact that $\exp(x)\geq x+1$ for $x\in\mathbb{R}$, we further have

$\displaystyle\mathbb{P}_{\mathcal{D}\sim
p^{\star}}\big{(}-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+\textup{{H}}^{2}(p^{\star},p)\geq\epsilon\big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim
p^{\star}}\big{(}-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))-2\log{\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\star}}\big{[}\sqrt{p(\mathcal{D}^{\prime})/p^{\star}(\mathcal{D}^{\prime})}\big{]}}\geq\epsilon\big{)}$
$\displaystyle=$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim
p^{\star}}\big{(}L(\mathcal{D})\geq\epsilon/2\big{)}$ $\displaystyle\leq$
$\displaystyle\exp(-\epsilon/2).$

Taking $\delta=\exp(-\epsilon/2)$, we have $\epsilon=2\log(1/\delta)$. We can
conclude that with probability at most $\delta$ over $\mathcal{D}\sim
p^{\star}$,

$\displaystyle-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+\textup{{H}}^{2}(p^{\star},p)\geq
2\log(1/\delta).$

Thus, with probability at least $1-\delta$ over $\mathcal{D}\sim p^{\star}$,

$\displaystyle-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+\textup{{H}}^{2}(p^{\star},p)\leq
2\log(1/\delta).$

Finally, taking union bounds on $p\in\mathcal{P}$ yields that, with
probability at least $1-\delta$ on $\mathcal{D}\sim p^{\star}$, for all
$p\in\mathcal{P}$,

$\displaystyle-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+\textup{{H}}^{2}(p^{\star},p)\leq
2\log(|\mathcal{P}|/\delta).$

Since the above argument applies to any $p^{\star}\in\mathcal{P}$, we have
that for any $p^{\star}\in\mathcal{P}$, with probability at least $1-\delta$
over $\mathcal{D}\sim p^{\star}$, for all $p\in\mathcal{P}$,

$\displaystyle-\log(p^{\star}(\mathcal{D})/p(\mathcal{D}))+\textup{{H}}^{2}(p^{\star},p)\leq
2\log(|\mathcal{P}|/\delta).$

This completes the proof. ∎

###  D.2 Proof of Theorem 2

Fix the DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ and
$M^{\star}\in\mathcal{M}$. We further denote the log-likelihood ratio of a
model $M\in\mathcal{M}$ w.r.t. the dataset $\mathcal{D}$ as

$\displaystyle\textup{{LL}}(\mathcal{D},M)\coloneqq\log(\mathbb{P}_{M^{\star}}(\mathcal{D}))-\log(\mathbb{P}_{M}(\mathcal{D})).$

We have that

$\displaystyle\textup{{LL}}(\mathcal{D},M^{\star})=0$ (24)

for any $\mathcal{D}\in\mathcal{O}$, which directly comes from the definition.
Since $\log(\mathbb{P}_{M^{\star}}(\mathcal{D}^{\star}))$ is fixed given
$M^{\star}$ and $\mathcal{D}^{\star}$, EDD (Eq. 3 is equivalent to taking

$\displaystyle\widehat{p}(\mathcal{D}^{\star})=\min_{p\in\Delta(\Pi)}\max_{M\in\mathcal{M}}\Big{[}L(M,p)-\lambda\cdot\textup{{LL}}(\mathcal{D}^{\star},M)\Big{]}.$

Thus, the loss can be written as

$\displaystyle\mathcal{L}(M^{\star},\widehat{p}(\mathcal{D}^{\star}))$
$\displaystyle=$
$\displaystyle\mathcal{L}(M^{\star},\widehat{p}(\mathcal{D}^{\star}))-\lambda\cdot\textup{{LL}}(\mathcal{D}^{\star},M^{\star})+\lambda\cdot\textup{{LL}}(\mathcal{D}^{\star},M^{\star})$
$\displaystyle=$
$\displaystyle\mathcal{L}(M^{\star},\widehat{p}(\mathcal{D}^{\star}))-\lambda\cdot\textup{{LL}}(\mathcal{D}^{\star},M^{\star})$
$\displaystyle\leq$
$\displaystyle\max_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,\widehat{p}(\mathcal{D}^{\star}))-\lambda\cdot\textup{{LL}}(\mathcal{D}^{\star},M)\Big{]}.$

By the definition of EDD and EOEC, we have that

$\displaystyle\mathcal{L}(M^{\star},\widehat{p}(\mathcal{D}^{\star}))\leq$
$\displaystyle\max_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,\widehat{p}(\mathcal{D}^{\star}))-\lambda\cdot\textup{{LL}}(\mathcal{D}^{\star},M)\Big{]}$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,p)-\lambda\cdot\textup{{LL}}(\mathcal{D}^{\star},M)\Big{]}$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,p)+\lambda\log(\mathbb{P}_{M}(\mathcal{D}^{\star})/\mathbb{P}_{M^{\star}}(\mathcal{D}^{\star}))\Big{]}$
$\displaystyle=$
$\displaystyle\textup{{EOEC}}(M^{\star},\mathcal{M},\mathcal{D}^{\star}).$

This completes the proof.

###  D.3 Proof of Theorem 3

Fix $\lambda\geq 0$ and $M\in\mathcal{M}$. By the definition of the EOEC and
Lemma 7, with probability at least $1-\delta$ over $\mathcal{D}\sim M$,

$\displaystyle\textup{{EOEC}}_{\lambda}(M,\mathcal{M},\mathcal{D})=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},p)-\lambda\cdot\log(\mathbb{P}_{M}(\mathcal{D})/\mathbb{P}_{M^{\prime}}(\mathcal{D}))\big{]}\Big{]}$
$\displaystyle\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},p)-\lambda\cdot\textup{{H}${}^{2}$}(M,M^{\prime})\big{]}+2\lambda\cdot\log(|\mathcal{M}|/\delta)$
$\displaystyle=$
$\displaystyle\textup{{OEC}}_{\lambda}(\mathcal{M},\\{M\\})+2\lambda\cdot\log(|\mathcal{M}|/\delta),$

where the third equality follows from the definition of OEC. After this, Eq. 7
is simply a consequence of Theorem 2. This completes the proof.

##  Appendix E Missing Proofs in Section 6

###  E.1 Helper Lemmas

######  Lemma 8 (Subadditivity for the Squared Hellinger Distance; Trimmed
Lemma A.13 in Foster et al. [2021a]).

Let $\\{(\mathcal{X}_{i},\mathcal{F}_{i})\\}_{i\in[n]}$ be a sequence of
measurable spaces, $\mathcal{X}^{(i)}=\prod_{t=1}^{i}\mathcal{X}_{t}$, and
$\mathcal{F}^{(i)}=\bigotimes_{t=1}^{i}\mathcal{F}_{i}$. For each $i\in[n]$,
let $\mathbb{P}^{(i)}(\cdot|\cdot)$ and $\mathbb{Q}^{(i)}(\cdot|\cdot)$ be
probability kernels from $(\mathcal{X}^{(i-1)},\mathcal{F}^{(i-1)})$ to
$(\mathcal{X}_{i},\mathcal{F}_{i})$. Let $\mathbb{P}$ and $\mathbb{Q}$ be the
laws of $\\{X_{i}\\}_{i\in[n]}$ under
$X_{i}\sim\mathbb{P}^{(i)}(\cdot|\\{X_{t}\\}_{t\in[0,i-1]})$ and
$X_{i}\sim\mathbb{Q}^{(i)}(\cdot|\\{X_{t}\\}_{t\in[0,i-1]})$ respectively.
Then it holds that

$\displaystyle\textup{{H}${}^{2}$}(\mathbb{P},\mathbb{Q})\leq
10^{2}\log(n)\cdot\mathbb{E}_{\mathbb{P}}\Big{[}\sum_{i=1}^{n}\textup{{H}${}^{2}$}(\mathbb{P}(\cdot|\\{X_{t}\\}_{t\in[i-1]}),\mathbb{Q}(\cdot|\\{X_{t}\\}_{t\in[i-1]})\Big{]}.$

###### Proof.

See the original paper, namely, Foster et al. [2021a]. ∎

######  Lemma 9 (Union Bound of the Likelihood Under I.I.D.).

Let $\mathcal{P}$ be a set of probabilities, and
$\mathcal{D}=\\{X_{i}\\}_{i\in[N]}$ be the i.i.d. dataset drawn from
$p^{\otimes N}$ where $p\in\mathcal{P}$. For any $p\in\mathcal{P}$, with
probability at least $1-\delta$ over $\mathcal{D}\sim p^{\otimes N}$, for all
$p^{\prime}\in\mathcal{P}$,

$\displaystyle\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))+\textup{{H}}^{2}(p,p^{\prime})\Big{]}\leq
2\log(|\mathcal{P}|/\delta).$

###### Proof.

We first fix $p,p^{\prime}\in\mathcal{P}$, and take

$\displaystyle L(\mathcal{D})\coloneqq-\frac{1}{2}\log(p^{\otimes
N}(\mathcal{D})/(p^{\prime})^{\otimes
N}(\mathcal{D}))-\log\mathbb{E}_{\mathcal{D}^{\prime}\sim p^{\otimes
N}}\big{[}\sqrt{(p^{\prime})^{\otimes N}(\mathcal{D}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime})}\big{]}$

We have that

$\displaystyle\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\Big{[}\exp\big{(}L(\mathcal{D})\big{)}\Big{]}=$
$\displaystyle\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\Big{[}\exp\big{(}-\frac{1}{2}\log(p^{\otimes
N}(\mathcal{D})/(p^{\prime})^{\otimes
N}(\mathcal{D}))-\log{\mathbb{E}_{\mathcal{D}^{\prime}\sim p^{\otimes
N}}\Big{[}\sqrt{(p^{\prime})^{\otimes N}(\mathcal{D}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime})}\Big{]}}\big{)}\Big{]}$ $\displaystyle=$
$\displaystyle\frac{\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\Big{[}\exp\big{(}-\frac{1}{2}\log(p^{\otimes
N}(\mathcal{D})/(p^{\prime})^{\otimes
N}(\mathcal{D}))\big{)}\Big{]}}{\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\big{[}\sqrt{(p^{\prime})^{\otimes N}(\mathcal{D})/p^{\otimes
N}(\mathcal{D})}\big{]}}$ $\displaystyle=$ $\displaystyle 1$

We can then apply the Chernoff bound, which yields that

$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\big{(}L(\mathcal{D})\geq\epsilon\big{)}\leq$
$\displaystyle\frac{\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\exp\big{(}L(\mathcal{D})\big{)}}{\exp(\epsilon)}=\exp(-\epsilon).$ (25)

Further, by the definition of the squared Hellinger distance,

$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))+\textup{{H}}^{2}(p,p^{\prime})\Big{]}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))+2-2\mathbb{E}_{X\sim
p}\big{[}\sqrt{p^{\prime}(X)/p(X)}\big{]}\Big{]}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))+2-2\exp\log\mathbb{E}_{X\sim
p}\big{[}\sqrt{p^{\prime}(X)/p(X)}\big{]}\Big{]}\geq\epsilon\Big{)}.$

Due to the fact that $\exp(x)\geq x+1$ for $x\in\mathbb{R}$, we further have

$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))+\textup{{H}}^{2}(p,p^{\prime})\Big{]}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))-2\log\mathbb{E}_{X\sim
p}\big{[}\sqrt{p^{\prime}(X)/p(X)}\big{]}\Big{]}\geq\epsilon\Big{)}.$

On one hand, because of the i.i.d. assumption (Assumption 1), we obtain that

$\displaystyle\log\mathbb{E}_{\mathcal{D}^{\prime}\sim p^{\otimes
N}}\big{[}\sqrt{(p^{\prime})^{\otimes N}(\mathcal{D}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime})}\big{]}=$
$\displaystyle\log\mathbb{E}_{\mathcal{D}^{\prime}\sim p^{\otimes
N}}\Bigg{[}\sqrt{\prod_{X_{i}\in\mathcal{D}^{\prime}}p(X_{i})/\prod_{X_{i}\in\mathcal{D}^{\prime}}(p^{\prime})(X_{i})}\Bigg{]}$
$\displaystyle=$ $\displaystyle\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes
N}}\prod_{X_{i}\in\mathcal{D}^{\prime}}\big{[}\sqrt{p(X_{i})/(p^{\prime})(X_{i})}\big{]}$
$\displaystyle=$ $\displaystyle N\log\mathbb{E}_{X\sim
p}\big{[}\sqrt{p^{\prime}(X)/p(X)}\big{]}$ $\displaystyle=$
$\displaystyle\sum_{X_{i}\in\mathcal{D}^{\prime}}\log\mathbb{E}_{X\sim
p}\big{[}\sqrt{p^{\prime}(X)/p(X)}\big{]}.$

Thanks again to the i.i.d. assumption, we have that

$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))+\textup{{H}}^{2}(p,p^{\prime})\Big{]}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))\Big{]}-2\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes N}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime})}\big{]}\geq\epsilon\Big{)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}-\log\Big{(}\prod_{X_{i}\in\mathcal{D}}p(X_{i})/\prod_{X_{i}\in\mathcal{D}}(p^{\prime})(X_{i})\Big{)}-2\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes N}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime})}\big{]}\geq\epsilon\Big{)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}-\log(p^{\otimes N}(\mathcal{D})/(p^{\prime})^{\otimes
N}(\mathcal{D}))-2\log\mathbb{E}_{\mathcal{D}^{\prime}\sim p^{\otimes
N}}\big{[}\sqrt{(p^{\prime})^{\otimes N}(\mathcal{D}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime})}\big{]}\geq\epsilon\Big{)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}2L(\mathcal{D})\geq\epsilon\Big{)}$ $\displaystyle\leq$
$\displaystyle\exp(-\epsilon/2),$

where the last inequality follows from Eq. 25. Taking
$\delta=\exp(-\epsilon/2)$ (thus $\epsilon=2\log(1/\delta)$), we have that for
with probability at least $1-\delta$ over $\mathcal{D}\sim p^{\otimes N}$,

$\displaystyle\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))+\textup{{H}}^{2}(p,p^{\prime})\Big{]}\leq
2\log(1/\delta).$

Finally, taking union bounds on $p^{\prime}\in\mathcal{P}$ yields that, with
probability at least $1-\delta$ over $\mathcal{D}\sim p^{\otimes N}$, for all
$p^{\prime}\in\mathcal{P}$,

$\displaystyle\sum_{X_{i}\in\mathcal{D}}\Big{[}-\log(p(X_{i})/p^{\prime}(X_{i}))+\textup{{H}}^{2}(p,p^{\prime})\Big{]}\leq
2\log(|\mathcal{P}|/\delta).$

Note that the above arguments apply to all $p\in\mathcal{P}$, which will yield
the Lemma 9. This completes the proof. ∎

######  Lemma 10 (Union Bound of the Log-Likelihood Under I.I.D. with
Conditioning).

Let $\mathcal{P}$ be a set of probabilities on
$\mathcal{X}_{1}\times\mathcal{X}_{2}$, and $\mathcal{D}=\\{X_{1,n}\times
X_{2,n}\\}_{n\in[N]}$ be the i.i.d. dataset drawn from $p^{\otimes N}$ where
$p\in\mathcal{P}$. For any $p\in\mathcal{P}$, at least $1-\delta$ over
$\mathcal{D}$, for all $p^{\prime}\in\mathcal{P}$,

$\displaystyle\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))+\mathbb{E}_{X_{1}^{\prime}\sim
p^{\prime}}\big{[}\textup{{H}}^{2}(p(\cdot|X_{1}^{\prime}),p^{\prime}(\cdot|X_{1}^{\prime}))\big{]}\Big{]}\leq
2\log(|\mathcal{P}|/\delta).$

###### Proof.

Given the dataset $\mathcal{D}=\\{X_{1,n}\times X_{2,n}\\}_{n\in[N]}$, we
denote $\mathcal{D}_{1}\coloneqq\\{X_{1,n}\\}_{n\in[N]}$ and
$\mathcal{D}_{2}\coloneqq\\{X_{2,n}\\}_{n\in[N]}$. We first fix
$p,p^{\prime}\in\mathcal{P}$, and take

$\displaystyle L(\mathcal{D})\coloneqq-\frac{1}{2}\log(p^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1})/(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1}))-\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes N}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}^{\prime}_{2}|\mathcal{D}^{\prime}_{1})/p^{\otimes
N}(\mathcal{D}^{\prime}_{2}|\mathcal{D}^{\prime}_{1})}\big{]}.$

By the definition, we again have that

$\displaystyle\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\Big{[}\exp\big{(}L(\mathcal{D})\big{)}\Big{]}$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\Big{[}\exp\big{(}-\frac{1}{2}\log(p^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1})/(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1}))-\log{\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes N}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})/p^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})}\big{]}}\big{)}\Big{]}$
$\displaystyle=$ $\displaystyle\frac{\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\Big{[}\exp\big{(}-\frac{1}{2}\log(p^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1})/(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1}))\big{)}\Big{]}}{{\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes N}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})/p^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})}\big{]}}\big{)}}$
$\displaystyle=$ $\displaystyle\frac{\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\Big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1})/p^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1})}\Big{]}}{{\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes N}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})/p^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})}\big{]}}\big{)}}$
$\displaystyle=$ $\displaystyle 1.$

We can then apply the Chernoff bound, which yields that

$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\big{(}L(\mathcal{D})\geq\epsilon\big{)}\leq$
$\displaystyle\frac{\mathbb{E}_{\mathcal{D}\sim p^{\otimes
N}}\exp\big{(}L(\mathcal{D})\big{)}}{\exp(\epsilon)}=\exp(-\epsilon).$ (26)

Further, by the definition of the squared Hellinger distance,

$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Bigg{(}\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))+\mathbb{E}_{X_{1}^{\prime}\sim
p^{\prime}}\textup{{H}}^{2}(p(\cdot|X_{1}^{\prime}),p^{\prime}(\cdot|X_{1}^{\prime}))\Big{]}\geq\epsilon\Bigg{)}$
$\displaystyle=$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Bigg{(}\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))+2-2\mathbb{E}_{X\sim
p}\big{[}\sqrt{p^{\prime}(X_{2}|X_{1})/p(X_{2}|X_{1})}\big{]}\Big{]}\geq\epsilon\Bigg{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Bigg{(}\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))+2-2\exp\log\mathbb{E}_{X\sim
p}\big{[}\sqrt{p^{\prime}(X_{2}|X_{1})/p(X_{2}|X_{1})}\big{]}\Big{]}\geq\epsilon\Bigg{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Bigg{(}\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))-2\log\mathbb{E}_{(X_{1},X_{2})\sim
p}\big{[}\sqrt{p^{\prime}(X_{2}|X_{1})/p(X_{2}|X_{1})}\big{]}\Big{]}\geq\epsilon\Bigg{)},$

where the last inequality follows from the fact $\exp(x)\geq x+1$ for all
$x\in\mathbb{R}$. As a result of the i.i.d. assumption,

$\displaystyle\log\mathbb{E}_{\mathcal{D}^{\prime}\sim p^{\otimes
N}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime}_{2}|\mathcal{D}_{1}^{\prime})}\big{]}$
$\displaystyle=$ $\displaystyle\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes
N}}\Bigg{[}\sqrt{\prod_{(X_{1},X_{2})\in\mathcal{D}^{\prime}}\Big{(}p(X_{2}|X_{1})/(p^{\prime})(X_{2}|X_{1})}\Big{)}\Bigg{]}$
$\displaystyle=$ $\displaystyle\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{\otimes
N}}\prod_{(X_{1},X_{2})\in\mathcal{D}^{\prime}}\Bigg{[}\sqrt{\Big{(}p(X_{2}|X_{1})/(p^{\prime})(X_{2}|X_{1})}\Big{)}\Bigg{]}$
$\displaystyle=$ $\displaystyle N\log\mathbb{E}_{(X_{1},X_{2})\sim
p}\big{[}\sqrt{p^{\prime}(X_{2}|X_{1})/p(X_{2}|X_{1})}\big{]}.$

As a conclusion,

$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))+\mathbb{E}_{X_{1}^{\prime}\sim
p^{\prime}}\textup{{H}}^{2}(p(\cdot|X_{1}^{\prime}),p^{\prime}(\cdot|X_{1}^{\prime}))\Big{]}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Bigg{(}\sum_{(X_{1},X_{2})\in\mathcal{D}}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))-2\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{n}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime}_{2}|\mathcal{D}_{1}^{\prime})}\big{]}\geq\epsilon\Bigg{)}.$

Again we can apply the i.i.d. assumption,

$\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))+\mathbb{E}_{X_{1}^{\prime}\sim
p^{\prime}}\textup{{H}}^{2}(p(\cdot|X_{1}^{\prime}),p^{\prime}(\cdot|X_{1}^{\prime}))\Big{]}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}-\log(p^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1})/(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}|\mathcal{D}_{1}))-2\log\mathbb{E}_{\mathcal{D}^{\prime}\sim
p^{n}}\big{[}\sqrt{(p^{\prime})^{\otimes
N}(\mathcal{D}_{2}^{\prime}|\mathcal{D}_{1}^{\prime})/p^{\otimes
N}(\mathcal{D}^{\prime}_{2}|\mathcal{D}_{1}^{\prime})}\big{]}\geq\epsilon\Big{)}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}_{\mathcal{D}\sim p^{\otimes
N}}\Big{(}2L(\mathcal{D})\geq\epsilon\Big{)}$ $\displaystyle\leq$
$\displaystyle\exp(-\epsilon),$

where the last inequality follows from Eq. 26. Taking
$\delta=\exp(-\epsilon/2)$, we have that for all $p^{\prime}\in\mathcal{P}$,
with probability at least $1-\delta$ on $\mathcal{D}\sim p^{\otimes N}$,

$\displaystyle\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))+\mathbb{E}_{X_{1}^{\prime}\sim
p^{\prime}}\big{[}\textup{{H}}^{2}(p(\cdot|X_{1}^{\prime}),p^{\prime}(\cdot|X_{1}^{\prime}))\big{]}\Big{]}\leq
2\log(1/\delta).$

Finally, taking union bounds on $p^{\prime}\in\mathcal{P}$ yields that, for
any $p\in\mathcal{P}$, with probability at least $1-\delta$ over
$\mathcal{D}\sim p^{\otimes N}$, for all $p^{\prime}\in\mathcal{P}$,

$\displaystyle\sum_{(X_{1},X_{2})\in\mathcal{D}}\Big{[}-\log(p(X_{2}|X_{1})/p^{\prime}(X_{2}|X_{1}))+\mathbb{E}_{X_{1}^{\prime}\sim
p^{\prime}}\big{[}\textup{{H}}^{2}(p(\cdot|X_{1}^{\prime}),p^{\prime}(\cdot|X_{1}^{\prime}))\big{]}\Big{]}\leq
2\log(|\mathcal{P}|/\delta).$

This completes the proof. ∎

######  Lemma 11 (Refined Simulation Lemma).

Given a Markovian sequential problem $(\mathcal{P}$, $\mathcal{M}$,
$\\{\mathcal{S}_{h}\\}_{h\in[H]}$, $\\{\mathcal{A}_{h}\\}_{h\in[H]}$, $\Pi$,
$\ell,N)$ we have that

$\displaystyle\mathcal{L}(M,p)\leq$ $\displaystyle 3\mathcal{L}(M^{\prime},p)$
$\displaystyle\quad+4B\cdot
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,p)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,s_{i-1},a_{i-1}),\mathcal{P}(\cdot|M^{\prime},h,s_{i-1},a_{i-1})\Big{]},$

for any $M,M^{\prime}\in\mathcal{M}$ and $p\in\Delta(\Pi)$, where
$\mathcal{T}(\cdot|M,p)$ denotes the probability over
$\\{(s_{h},a_{h})\\}_{h\in[H]}$ that is sampled from
$\mathcal{T}(\cdot|M,\pi)$ where $\pi\sim p$.

###### Proof.

We first prove the case that $p$ is a singleton $\pi$. By Lemma 8,

$\displaystyle\textup{{H}${}^{2}$}(\mathcal{T}(\cdot|M,\pi),\mathcal{T}(\cdot|M^{\prime},\pi))$
$\displaystyle\leq$ $\displaystyle
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,\\{(s_{t},a_{t})\\}_{t\in[i-1]}),\mathcal{P}(\cdot|M^{\prime},h,\\{s_{t},a_{t}\\}_{t\in[i-1]})\Big{]}$
$\displaystyle\quad\quad\quad+10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\pi(\cdot|\\{(s_{t},a_{t})\\}_{t\in[i-1]},s_{i}),\pi(\cdot|\\{s_{t},a_{t}\\}_{t\in[i-1]},s_{i})\Big{]}$
$\displaystyle=$ $\displaystyle
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,\\{(s_{t},a_{t})\\}_{t\in[i-1]}),\mathcal{P}(\cdot|M^{\prime},h,\\{s_{t},a_{t}\\}_{t\in[i-1]})\Big{]}.$

Due to the Markovian property of $\mathcal{P}$, we have that

$\displaystyle
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,\\{(s_{t},a_{t})\\}_{t\in[i-1]}),\mathcal{P}(\cdot|M^{\prime},h,\\{s_{t},a_{t}\\}_{t\in[i-1]})\Big{]}$
$\displaystyle=$ $\displaystyle
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,s_{i-1},a_{i-1}),\mathcal{P}(\cdot|M^{\prime},h,s_{i-1},a_{i-1})\Big{]}.$

As a consequence,

$\displaystyle\textup{{H}${}^{2}$}(\mathcal{T}(\cdot|M,\pi),\mathcal{T}(\cdot|M^{\prime},\pi))$
$\displaystyle\leq$ $\displaystyle
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,s_{i-1},a_{i-1}),\mathcal{P}(\cdot|M^{\prime},h,s_{i-1},a_{i-1})\Big{]}.$

Thus, thanks to Lemma 6,

$\displaystyle\mathcal{L}(M,\pi)=$
$\displaystyle\mathbb{E}_{\\{s_{h},a_{h}\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\ell(\pi,\\{s_{h},a_{h}\\})$
$\displaystyle\leq$ $\displaystyle
3\mathbb{E}_{\\{s_{h},a_{h}\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M^{\prime},\pi)}\ell(\pi,\\{s_{h},a_{h}\\})+4B\cdot\textup{{H}${}^{2}$}(\mathcal{T}(\cdot|M,\pi),\mathcal{T}(\cdot|M^{\prime},\pi))$
$\displaystyle\leq$ $\displaystyle
3\mathbb{E}_{\\{s_{h},a_{h}\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M^{\prime},\pi)}\ell(\pi,\\{s_{h},a_{h}\\})$
$\displaystyle\quad\quad+4B\cdot
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,s_{i-1},a_{i-1}),\mathcal{P}(\cdot|M^{\prime},h,s_{i-1},a_{i-1})\Big{]}$
$\displaystyle=$ $\displaystyle 3\mathcal{L}(M^{\prime},\pi)$
$\displaystyle\quad+4B\cdot
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,s_{i-1},a_{i-1}),\mathcal{P}(\cdot|M^{\prime},h,s_{i-1},a_{i-1})\Big{]},$

which means

$\displaystyle\mathcal{L}(M,\pi)\leq$ $\displaystyle
3\mathcal{L}(M^{\prime},\pi)$ $\displaystyle\quad+4B\cdot
10^{2}\log(2H)\cdot\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M,\pi)}\Big{[}\sum_{i=1}^{H}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M,h,s_{i-1},a_{i-1}),\mathcal{P}(\cdot|M^{\prime},h,s_{i-1},a_{i-1})\Big{]}.$

Taking the expectation $\mathbb{E}_{\pi\sim p}$ on both sides yields the
desired result. This completes the proof. ∎

###  E.2 Missing Proof of Theorem 4

We first upper bound EOEC with the use of concentration inequalities. Let
$\mathbb{P}_{M}$ be the law of the data generating process under model $M$. By
the definition EOEC and the i.i.d. assumption (Assumption 1),

$\displaystyle\textup{{EOEC}}_{\lambda}(M,\mathcal{M},\mathcal{D})$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},p)+\lambda\cdot\log(\mathbb{P}_{M^{\prime}}(\mathcal{D})/\mathbb{P}_{M}(\mathcal{D}))\big{]}$
$\displaystyle\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},p)+\lambda\cdot\sum_{n\in[N]}\log(\mathbb{P}_{M^{\prime}}(X_{n})/\mathbb{P}_{M}(X_{n}))\big{]}$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},p)+\lambda\cdot\sum_{n\in[N]}\log(\Phi(M^{\prime})(X_{n})/\Phi(M)(X_{n}))\big{]}.$

By Lemma 9 as well as again the i.i.d. assumption (Assumption 1), with
probability at least $1-\delta$,

$\displaystyle\textup{{EOEC}}_{\lambda}(M,\mathcal{M},\mathcal{D})$
$\displaystyle\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},p)-\lambda\cdot
N\cdot\textup{{H}${}^{2}$}(\Phi(M^{\prime}),\Phi(M))\Big{]}+2\lambda\cdot\log(|\mathcal{M}|/\delta).$

We define $\ell(x,p)\coloneqq\mathbb{E}_{\pi\sim p}\ell(x,\pi)$. Due to the
definition of $\mathcal{L}$ and the i.i.d. assumption (Assumption 1),

$\displaystyle\mathcal{L}(M^{\prime},p)=\mathbb{E}_{\mathcal{D}^{\prime}\sim
M^{\prime}}\Big{[}\frac{1}{N}\sum_{x\sim\mathcal{D}^{\prime}}\ell(x,p)\Big{]}=\mathbb{E}_{x\sim\Phi(M^{\prime})}\Big{[}\ell(x,p)\Big{]}.$

Setting $\lambda$ to $4B/N$ yields that

$\displaystyle\textup{{EOEC}}_{\lambda}(M,\mathcal{M},\mathcal{D})\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathbb{E}_{x\sim\Phi(M^{\prime})}\Big{[}\ell(x,p)\Big{]}-4B\cdot\textup{{H}${}^{2}$}(\mathbb{P}_{M^{\prime}},\mathbb{P}_{M})\Big{]}+\frac{8B}{N}\cdot\log(|\mathcal{M}|/\delta)$
$\displaystyle\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}3\mathbb{E}_{x\sim\Phi(M)}\big{[}\ell(x,p)\big{]}\Big{]}+\frac{8B}{N}\cdot\log(|\mathcal{M}|/\delta)$
$\displaystyle\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}3\mathcal{L}(M,p)\big{]}+\frac{8B}{N}\cdot\log(|\mathcal{M}|/\delta)$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\big{[}3\mathcal{L}(M,p)\big{]}+\frac{8B}{N}\cdot\log(|\mathcal{M}|/\delta)$
$\displaystyle\leq$
$\displaystyle\min_{\pi\in\Pi}\big{[}3\mathcal{L}(M,\pi)\big{]}+\frac{8B}{N}\cdot\log(|\mathcal{M}|/\delta).$

On other hand, the second part of Theorem 4 is a consequence of the above
equation and Theorem 2. This completes the proof.

###  E.3 Missing Proof of Theorem 5

For any $M\in\mathcal{M}$, let $\mathbb{P}_{M}$ denotes the law of data
generating. Denoting
$\mathcal{D}^{\star}=\\{(s_{n,h},a_{n,h},s^{\prime}_{n,h})\\}_{h\in[H],n\in[N]}$,
by the definition of EOEC as well as the i.i.d. assumption of the dataset
(Assumption 2), we have that

$\displaystyle\textup{{EOEC}}_{\lambda}(M^{\star},\mathcal{M},\mathcal{D}^{\star})$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},p)+\lambda\cdot\log(\mathbb{P}_{M^{\prime}}(\mathcal{D}^{\star})/\mathbb{P}_{M^{\star}}(\mathcal{D}^{\star}))\big{]}$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},p)+\lambda\cdot\sum_{n\in[N]}\log(\mathbb{P}_{M^{\prime}}(\\{(s_{n,h},a_{n,h},s^{\prime}_{n,h})\\}_{h\in[H]})/\mathbb{P}_{M^{\star}}(\\{(s_{n,h},a_{n,h},s^{\prime}_{n,h})\\}_{h\in[H]}))\big{]}.$

We can further expand the above equation by the definition of conditional
probability.

$\displaystyle\textup{{EOEC}}_{\lambda}(M^{\star},\mathcal{M},\mathcal{D}^{\star})$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\big{[}\mathcal{L}(M^{\prime},\pi)+\lambda\cdot\sum_{n\in[N]}\log(\mathbb{P}_{M^{\prime}}(\\{(s_{n,h},a_{n,h},s^{\prime}_{n,h})\\}_{h\in[H]})/\mathbb{P}_{M^{\star}}(\\{(s_{n,h},a_{n,h},s^{\prime}_{n,h})\\}_{h\in[H]}))\big{]}$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},\pi)$
$\displaystyle+\lambda\cdot\sum_{n\in[N]}\sum_{h\in[H]}\log(\mathbb{P}_{M^{\prime}}(s_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]})/\mathbb{P}_{M^{\star}}(s_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]}))$
$\displaystyle+\lambda\cdot\sum_{n\in[N]}\sum_{h\in[H]}\log(\mathbb{P}_{M^{\prime}}(a_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]},s_{n,h})/\mathbb{P}_{M^{\star}}(a_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]},s_{n,h}))$
$\displaystyle+\lambda\cdot\sum_{n\in[N]}\sum_{h\in[H]}\log(\mathbb{P}_{M^{\prime}}(s^{\prime}_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]},s_{n,h},a_{n,h})/\mathbb{P}_{M^{\star}}(s^{\prime}_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]},s_{n,h},a_{n,h}))\Big{]}.$

We then exchange the summation above, and get

$\displaystyle\textup{{EOEC}}_{\lambda}(M^{\star},\mathcal{M},\mathcal{D}^{\star})$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},p)$
$\displaystyle+\underbrace{\lambda\cdot\sum_{h\in[H]}\sum_{n\in[N]}\log(\mathbb{P}_{M^{\prime}}(s_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]})/\mathbb{P}_{M^{\star}}(s_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]}))}_{(\textup{I})}$
$\displaystyle+\underbrace{\lambda\cdot\sum_{h\in[H]}\sum_{n\in[N]}\log(\mathbb{P}_{M^{\prime}}(a_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]},s_{n,h})/\mathbb{P}_{M^{\star}}(a_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]},s_{n,h}))}_{(\textup{II})}$
$\displaystyle+\underbrace{\lambda\cdot\sum_{h\in[H]}\sum_{n\in[N]}\log(\mathbb{P}_{M^{\prime}}(s^{\prime}_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]},s_{n,h},a_{n,h})/\mathbb{P}_{M^{\star}}(s^{\prime}_{n,h}|\\{s_{n,i},a_{n,i},s^{\prime}_{n,i}\\}_{i\in[h-1]},s_{n,h},a_{n,h}))}_{(\textup{III})}.$

At this point, we can now apply the concentration inequality. Thanks to Lemma
9, the i.i.d. assumption (Assumption 2), and the union bound, with probability
at least $1-\delta\cdot H$,

$\displaystyle(\textup{I})$ (27) $\displaystyle\leq$
$\displaystyle-\lambda\cdot\sum_{h\in[H]}\sum_{n\in[N]}\mathbb{E}_{\\{(s_{i},a_{i},s_{i}^{\prime})\\}_{i\in[h]}\sim\Phi(M^{\star})\\}}\textup{{H}${}^{2}$}(\mathbb{P}_{M^{\star}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]}),\mathbb{P}_{M^{\prime}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]}))+\lambda\log(|\mathcal{M}|/\delta)$
(28) $\displaystyle\leq$ $\displaystyle\lambda\log(|\mathcal{M}|/\delta).$
(29)

Moreover, again due to Lemma 10, the i.i.d. assumption (Assumption 2) and the
union bound, with probability at least $1-\delta\cdot H$,

$\displaystyle(\textup{II})\leq$
$\displaystyle-\lambda\cdot\sum_{h\in[H]}\sum_{n\in[N]}\mathbb{E}_{\\{(s_{i},a_{i},s_{i}^{\prime})\\}_{i\in[h]}\sim\Phi(M^{\star})\\}}\Big{[}$
(30)
$\displaystyle\quad\quad\quad\textup{{H}${}^{2}$}(\mathbb{P}_{M^{\star}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]},s_{h}),\mathbb{P}_{M^{\prime}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]},s_{h}))\Big{]}+\lambda\log(|\mathcal{M}|/\delta)$
(31) $\displaystyle\leq$ $\displaystyle\lambda\log(|\mathcal{M}|/\delta).$
(32)

For the same reason, we have that with probability at least $1-\delta\cdot H$,

$\displaystyle(\textup{III})\leq$
$\displaystyle-\lambda\cdot\sum_{h\in[H]}\sum_{n\in[N]}\mathbb{E}_{\\{(s_{i},a_{i},s_{i}^{\prime})\\}_{i\in[h]}\sim\Phi(M^{\star})\\}}\Big{[}$
(33)
$\displaystyle\quad\quad\quad\textup{{H}${}^{2}$}(\mathbb{P}_{M^{\star}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]},s_{h},a_{h}),\mathbb{P}_{M^{\prime}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]},s_{h},a_{h}))\Big{]}\Big{]}+\lambda\log(|\mathcal{M}|/\delta).$
(34)

Combining Eqs. 29, 32 and 34 as well as the union bound yields that, with
probability at least $1-\delta\cdot 3H$,

$\displaystyle\textup{{EOEC}}_{\lambda}(M^{\star},\mathcal{M},\mathcal{D}^{\star})$
$\displaystyle\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},p)+3\lambda\log(|\mathcal{M}|/\delta)-\lambda\cdot\sum_{h\in[H]}\sum_{n\in[N]}\mathbb{E}_{\\{(s_{i},a_{i},s_{i}^{\prime})\\}_{i\in[h]}\sim\Phi(M^{\star})\\}}\Big{[}$
$\displaystyle\quad\quad\quad\textup{{H}${}^{2}$}(\mathbb{P}_{M^{\star}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]},s_{h},a_{h}),\mathbb{P}_{M^{\prime}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]},s_{h},a_{h}))\Big{]}\Big{]}$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},p)+3\lambda\log(|\mathcal{M}|/\delta)-\lambda
N\cdot\sum_{h\in[H]}\mathbb{E}_{\\{(s_{i},a_{i},s_{i}^{\prime})\\}_{h\in[H]}\sim\Phi(M^{\star})\\}}\Big{[}$
$\displaystyle\quad\quad\quad\textup{{H}${}^{2}$}(\mathbb{P}_{M^{\star}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]},s_{h},a_{h}),\mathbb{P}_{M^{\prime}}(\cdot|\\{s_{i},a_{i},s^{\prime}_{i}\\}_{i\in[h-1]},s_{h},a_{h}))\Big{]}\Big{]}$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},p)+3\lambda\log(|\mathcal{M}|/\delta)-\lambda
N\cdot\sum_{h\in[H]}\mathbb{E}_{(s_{h},a_{h})\sim
d^{\mathcal{D}}_{h}(\cdot|M^{\star})\\}}\Big{[}$
$\displaystyle\quad\quad\quad\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M^{\star},h,s_{h},a_{h}),\mathcal{P}(\cdot|M^{\prime},h,s_{h},a_{h}))\Big{]}\Big{]}.$

The subsequent arguments in this proof will be based on this high probability
event. Further due to the concentration assumption (Assumption 3), we have
that

$\displaystyle\textup{{EOEC}}_{\lambda}(M^{\star},\mathcal{M},\mathcal{D}^{\star})$
$\displaystyle\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},p)+3\lambda\log(|\mathcal{M}|/\delta)-\frac{\lambda
N}{C_{\widebar{\pi}}}\cdot\sum_{h\in[H]}\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M^{\star},\widebar{\pi},h)\\}}\Big{[}$
$\displaystyle\quad\quad\quad\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M^{\star},h,s_{h},a_{h}),\mathcal{P}(\cdot|M^{\prime},h,s_{h},a_{h}))\Big{]}\Big{]}$
$\displaystyle=$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},p)+3\lambda\log(|\mathcal{M}|/\delta)-\frac{\lambda
N}{C_{\widebar{\pi}}}\cdot\sum_{h\in[H]}\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M^{\star},\widebar{\pi},h)\\}}\Big{[}$
$\displaystyle\quad\quad\quad\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M^{\prime},h,s_{h},a_{h}),\mathcal{P}(\cdot|M^{\star},h,s_{h},a_{h}))\Big{]}\Big{]}.$

Setting $\lambda$ to $\frac{400BC_{\widebar{\pi}}\log(2H)}{N}$, we can then
apply the refined simulation lemma (Lemma 11), we can conclude that

$\displaystyle\textup{{EOEC}}_{\frac{400BC_{\widebar{\pi}}\log(2H)}{N}}(M^{\star},\mathcal{M},\mathcal{D}^{\star})$
$\displaystyle\leq$
$\displaystyle\min_{p\in\Delta(\Pi)}\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},p)+\frac{1200BC_{\widebar{\pi}}\log(2H)}{N}\log(|\mathcal{M}|/\delta)$
$\displaystyle-4B\cdot
10^{2}\log(2H)\cdot\sum_{h\in[H]}\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M^{\star},\widebar{\pi},h)\\}}\Big{[}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M^{\prime},h,s_{h},a_{h}),\mathcal{P}(\cdot|M^{\star},h,s_{h},a_{h}))\Big{]}\Big{]}$
$\displaystyle\leq$
$\displaystyle\max_{M^{\prime}\in\mathcal{M}}\Big{[}\mathcal{L}(M^{\prime},\widebar{\pi})+\frac{1200BC_{\widebar{\pi}}\log(2H)}{N}\log(|\mathcal{M}|/\delta)$
$\displaystyle\quad\quad\quad-4B\cdot
10^{2}\log(2H)\cdot\sum_{h\in[H]}\mathbb{E}_{\\{(s_{h},a_{h})\\}_{h\in[H]}\sim\mathcal{T}(\cdot|M^{\star},\widebar{\pi},h)\\}}\Big{[}\textup{{H}${}^{2}$}(\mathcal{P}(\cdot|M^{\prime},h,s_{h},a_{h}),\mathcal{P}(\cdot|M^{\star},h,s_{h},a_{h}))\Big{]}\Big{]}$
$\displaystyle\leq$ $\displaystyle
3\mathcal{L}(M^{\star},\widebar{\pi})+\frac{1200BC_{\widebar{\pi}}\log(2H)}{N}\cdot\log(|\mathcal{M}|/\delta).$

Setting the $\delta$ above to $\delta/(3H)$ can yield the first part of
Theorem 5. On the other hand, Eq. 13 is a consequence of the above equation
and Theorem 2. This completes the proof.

##  Appendix F OEC with Other $f$-divergences

This section shows that one can replace the squared Hellinger distance in OEC
with another divergence that satisfies a refined change of measure property
and still attain a similar lower bound result. We first state the refined
change of measure property in the following.

######  Definition 6 (Refined Change of Measure Property).

We say that an $f$-divergence $D$ satisfies the refined change of measure
property with coefficients $\gamma_{D,1}$ and $\gamma_{D,2}$ if

$\displaystyle\mathbb{E}_{X\sim\mathbb{P}}[g(X)]\geq\gamma_{D,1}\Big{[}\mathbb{E}_{X\sim\mathbb{Q}}[g(X)]-\gamma_{D,2}\cdot
B\cdot D(\mathbb{P},\mathbb{Q})\Big{]}.$

for any function $g$ with range $[0,B]$,

Lots of the classic $f$-divergences satisfy the above property:

  * •

the total variation distance with $\gamma_{\textup{{TV}},1}=1$ and
$\gamma_{\textup{{TV}},2}=2$ (from Lemma 5).

  * •

the squared Hellinger distance with
$\gamma_{\textup{{H}${}^{2}$},1}=\frac{1}{3}$ and
$\gamma_{\textup{{H}${}^{2}$},2}=4$ (from Lemma 6).

  * •

the KL divergence with $\gamma_{\textup{{KL}},1}=\frac{1}{3}$ and
$\gamma_{\textup{{KL}},2}=4$ (from Lemma 6 and the fact that
$\textup{{KL}}(\mathbb{P},\mathbb{Q})\geq\textup{{H}${}^{2}$}(\mathbb{P},\mathbb{Q})$).

With an $f$-divergence $D$ satisfying the refined change of measure property,
we can further define the generalized offline estimation coefficient as
follows.

######  Definition 7.

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$ and $f$-divergence
$D$ satisfying the refined change of measure property (Definition 6), _its_
OEC w.r.t. a set of probability $A\subseteq\Delta(\mathcal{O})$ and a
parameter $\lambda\geq 0$ is defined as

$\displaystyle\textup{{OEC}}_{\lambda,D}(\mathcal{M},A)\coloneqq\max\limits_{\rho\in
A}\min_{p\in\Delta(\Pi)}\max\limits_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,p)-B\cdot
D(\rho,M)\Big{]}.$ (35)

######  Theorem 6.

Given a DMOF $(\mathcal{M},\Pi,\mathcal{O},\mathcal{L})$, and an
$f$-divergence $D$ that satisfies the refined change of measure property
(Definition 6), for any algorithm $\mathfrak{A}$, there exists an
$M\in\mathcal{M}$ such that the expected loss of the algorithm under model $M$
is lower bounded as follow:

$\displaystyle\mathbb{E}_{\mathcal{D}\sim
M}\Big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\Big{]}\geq\gamma_{D,1}\cdot\textup{{OEC}}_{\gamma_{D,2}\cdot
B,D}(\mathcal{M},A),$ (36)

where $A$ can be chosen as any subset of $\Delta(\mathcal{O})$.

###### Proof.

Fix $A\subseteq\Delta(\mathcal{O})$. For any algorithm $\mathfrak{A}$, we can
rewrite its worst case performance as

$\displaystyle\max\limits_{M\in\mathcal{M}}\mathbb{E}_{\mathcal{D}\sim
M}\big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\big{]}$ (37)
$\displaystyle=$ $\displaystyle\max\limits_{\rho\in
A}\max\limits_{M\in\mathcal{M}}\mathbb{E}_{\mathcal{D}\sim
M}\big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\big{]}$ (38)
$\displaystyle\geq$ $\displaystyle\gamma_{D,1}\max\limits_{\rho\in
A}\max\limits_{M\in\mathcal{M}}\Big{[}\mathbb{E}_{\mathcal{D}\sim\rho}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))-\gamma_{D,2}\cdot
B\cdot D(\rho,M)\Big{]},$ (39)

where the last inequality follows from Definition 6, for which we take the
whole $\mathcal{L}(M,\mathfrak{A}(\cdot))$ as a function. We can apply the
same trick used in Section C.1, and get

$\displaystyle\max\limits_{M\in\mathcal{M}}\mathbb{E}_{\mathcal{D}\sim
M}\big{[}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))\big{]}$ (40)
$\displaystyle\geq$ $\displaystyle\gamma_{D,1}\max\limits_{\rho\in
A}\max\limits_{M\in\mathcal{M}}\Big{[}\mathbb{E}_{\mathcal{D}\sim\rho}\mathcal{L}(M,\mathfrak{A}(\mathcal{D}))-\gamma_{D,2}\cdot
B\cdot D(\rho,M)\Big{]}$ (41) $\displaystyle\geq$
$\displaystyle\gamma_{D,1}\max\limits_{\rho\in
A}\min_{p\in\Delta(\Pi)}\max\limits_{M\in\mathcal{M}}\Big{[}\mathcal{L}(M,p)-\gamma_{D,2}\cdot
B\cdot D(\rho,M)\Big{]}$ (42) $\displaystyle\geq$
$\displaystyle\gamma_{D,1}\textup{{OEC}}_{\gamma_{D,2}\cdot
B,D}(\mathcal{M},A).$ (43)

This completes the proof. ∎