We offer a theoretical characterization of off-policy evaluation (OPE) in reinforcement learning using function approximation for marginal importance weights and $q$-functions when these are estimated using recent minimax methods. Under various combinations of realizability and completeness assumptions, we show that the minimax approach enables us to achieve a fast rate of convergence for weights and quality functions, characterized by the critical inequality [6]. Based on this result, we analyze convergence rates for OPE. In particular, we introduce novel alternative completeness conditions under which OPE is feasible and we present the first finite-sample result with first-order efficiency in non-tabular environments, i.e., having the minimal coefficient in the leading term.

§ INTRODUCTION

Off-policy evaluation (OPE) is the problem of estimating the expected return in an unknown Markov decision process (MDP) of a given decision policy, known as the evaluation policy, using transition data generated by another policy, known as the behavior policy [39, 42, 7].
OPE is especially important in applications where experimentation is particularly costly, such as in medicine. Recently, the first-order efficiency bound for OPE was derived by 28 for time-varying MDPs
and by 27 for time-homogeneous MDPs (which we focus on and simply call MDPs).
That is, the smallest-possible coefficient of the leading $1/\sqrt{n}$ term $C$ in the estimation error $\ts C/\sqrt{n} + o(1/\sqrt{n}).$

In the time-varying tabular setting, the bounds coincides with that of 24, and
52 showed that the model-based estimator achieves it. However, the achievability of the lower bound in general settings is unclear.

Among the approaches to OPE, many of them rely on estimating the $q$-function (representing long-term value) or the $w$-function (representing density ratios), under the so-called realizability (a.k.a well-specification) and/or completeness (a.k.a hypothesis class closed under Bellman operators; 3, 8) assumptions.
For example, the $q$-function can be estimated via Fitted-Q Iteration
(FQI; 15), and the $w$-function is central to recent methods based on the idea of marginalized importance sampling [32, 19].

In this paper, we study minimax estimators of $q$- and $w$-functions and its implications for OPE. These estimators take the form of solutions to zero-sum games between $q$ and $w$. Related estimators have been proposed for $w$- [36, 53, 43] and $q$-functions [3, 17], but their statistical properties are not well understood or tightly characterized.
Here, we develop fast rates of convergence for these estimators under a variety of realizability and completeness conditions, many of which are new.
Furthermore, we show how this leads to OPE with finite-sample guarantees that enjoy first-order efficiency, meaning having the minimal leading term.

We next give a brief overview of our results, also summarized in <ref>:

* (1 in  <ref>: <ref>) Under $q$- and $w$-realizability, we derive rates of convergence of the minimax approach by refining the analysis of [43].

* (2,3,4,5 in  <ref>: <ref>) Under a variety of completeness assumptions, we show the minimax approach enables us to achieve a fast rate of convergence for $q$- and $w$-functions, characterized by the critical inequality [6]. This is the first finite-sample result obtaining a fast rate for $w$-functions and it introduces novel completeness assumptions. We apply these results to derive the rate for OPE, which is generally slower than the case in 1.

* (6 in <ref>: <ref>) Under both and completeness of both $w$- and $q$-functions, we present the first finite sample result that indicates the first-order lower bound is achieved in non-tabular environments. Our result covers a tabular case as a special case.[Strictly speaking, our tabular result is also a new result since 52 discusses a model based estimator on time-varying MDPs. Our setting is time-homogeneous MDP.]

Note all of the proofs are in <ref>. Comparison to other work is discussed in <ref>.

The rates of our finite-sample bounds on $|\hat J^{\MIL}-J|$ under different assumptions.
The hypothesis classes $\Wbbb_1,\Qbbb_1$ are used to estimate $w_{\epol}$ and $\Wbbb_2,\Qbbb_2$ to estimate $q_{\epol}$.
We summarize our conclusions for the cases of VC classes or
Sobolev balls $H^{\alpha,d}$ of $\alpha$-times differentiable functions of $d$-dimensional inputs.
Dependence on $1/(1-\gamma),C_{w},R_{\max},C_{\xi},\log(1/\delta)$ are polynomial, where $C_w$ is a distribution mismatch coefficient. “Sta" refers to whether we use stabilizers. Note the rate in 6 is faster than the one in 1, which is faster than the ones in 2, 3, 4, 5.

Main Assumptions       Sta     Rates  (ignoring $\log n$)      Note
1     $w_{\epol}\in \Wbbb_1,\,q_{\epol}\in \Qbbb_1$  or  $w_{\epol}\in \Wbbb_2,\,q_{\epol}\in \Qbbb_2$       No      $n^{-1/2}~~(\mathrm{VC})$$\max(n^{-1/2},\,n^{-\alpha/d})~~(H^{\alpha,d} )$
2*2        $q_{\epol}\in \Qbbb_2$  $C_{\xi}T_{\gamma}(\Qbbb_2-q_{\epol})\subset\Wbbb_2$      No       $n^{-1/4}~~(\mathrm{VC})$$\max(n^{-1/4},\,n^{\frac{-\alpha}{2d}})~~(H^{\alpha,d})$        We obtain a guarantee for $\|\Bcal\hat q-\hat q\|_2$.
The condition and rate (with sta) are the same as FQI.

Yes      $n^{-1/2} (\mathrm{VC})$$\max(n^{-1/2},\,n^{-\frac{\alpha}{2\alpha+d}})~~(H^{\alpha,d})$
3          $q_{\epol}\in \Qbbb_2$,$C_{\xi}(\Qbbb_2-q_{\epol})\subset T'_{\gamma}\Wbbb_2 $      Yes/No        Same as the above          We obtain a guarantee for $\|\hat q-q_{\epol}\|_2$.
4      $w_{\epol}\in \Wbbb_1$,$C_{\xi}(\Wbbb_1-w_{\epol})\subset T_{\gamma}\Qbbb_1 $       Yes/No        Same as the above         We obtain a guarantee for $\|\hat w-w_{\epol}\|_2$
5         $w_{\epol}\in \Wbbb_1$,$C_{\xi}T'_{\gamma}(\Wbbb_1-w_{\epol})\subset \Qbbb_1$     Yes/No         Same as the above         We obtain a guarantee for $\|\Bcal'\hat w-\hat w\|_2$
6      $q_{\epol}\in \Qbbb_2,\,w_{\epol}\in \Wbbb_1$,$C_{\xi}T_{\gamma}(\Qbbb_2-q_{\epol})\subset \Wbbb_2$,$C_{\xi} T'_{\gamma}(\Wbbb_1-w_{\epol})\subset\Qbbb_1$      Yes      $n^{-1/2}~~(\mathrm{VC})$$\max(n^{-1/2},\,n^{\frac{-2\alpha}{2\alpha+d}})~~(H^{\alpha,d})$
Our OPE error bound is first-order efficient in the cases where the rate is $n^{-1/2}$.

§ PROBLEM SETUP AND THE MINIMAX ESTIMATORS

A (discounted) MDP is specified by a

state space $\Scal$, action space $\Acal$, transition density $P_{S'|S,A}(s'|s,a)$, reward density $P_{R|S,A}(r|s,a)$, and discount factor $\gamma \in [0,1)$. We assume the reward support is contained in $[0,R_{\max}]$.

An MDP, a policy $\pi(a|s)$, and an initial-state density $d_0(s_0)$ together determine a density over trajectories $s_0,a_0,r_0,\cdots$, where $s_0\sim d_0,a_t\sim \pi(a_t|s_t),r_t\sim P_{R|S,A}(r_t|s_t,a_t),s_{t+1}\sim P_{S'|S,A}(s_{t+1}|s_t,a_t)$ for $t\geq 0$.

Our goal is to estimate the normalized discounted return under a given initial-state density $d_0$ and the evaluation policy $\pi_e$:

\begin{align*}\ts
\end{align*}

The policy value $J$ also has an alternative representation

\begin{align}\label{eq:is}\ts
J=\E_{(s,a)\sim d_{\epol,\gamma},r\sim P_{R|S,A}(r|s,a)}[r],
\end{align}

where $d_{\epol,\gamma}$ is the discounted occupancy density, $\ts d_{\epol,\gamma} \coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}d_{\epol,t}$, and $d_{\epol,t}$ is the density of $(s_t,a_t)$ under policy $\epol$ and initial-state density $d_0$.

We define the $q$-function with respect to $\epol$ as

\begin{align*}\ts
q_{\epol}(s,a) \coloneqq\E_{\epol}[\sum_{t=0}^{\infty}\gamma^{t}r_t|s_0=s,a_0=a].
\end{align*}

The corresponding state-value function is $v_{\epol}(s)=q_{\epol}(s,\epol)$, where for any $f:\mathcal S\times\mathcal A\to\mathbb R$ we define $f(s,\epol)\coloneqq \E_{a\sim \epol(a|s)}[f(s,a)]$.
We also define the MDP's transition and (forward) Bellman operators on functions $f:\mathcal S\times\mathcal A\to\mathbb R$, respectively:

\begin{align*}\ts
\Tcal:~f(s,a) \mapsto \E_{s'\sim P_{S'|S,A}(s'|s,a)}[f(s',\epol)],\quad
\Bcal:~f(s,a) \mapsto \gamma \Tcal f+\E_{r\sim P_{R|S,A}(r|s,a)}[r].
\end{align*}

Offline policy evaluation

In OPE, we have access to transition tuples generated in the same MDP where the actions are chosen by $\bpol$. Namely, we want to estimate $J$ and our data consists of $n$ independent and identically distributed quadruplets $\{(s^i,a^i,r^i,s'^i)\}_{i=1}^{n}$ following

\begin{align*}\ts
s\sim P_{S}(s), a\sim \bpol(a|s), r\sim P_{R|S,A}(r|s,a),s'\sim P_{S'|S,A}(s'|s,a).
\end{align*}

Here, $P_{S}(\cdot)$ is some exploratory state density that covers the state space (in a technical sense to be formalized). We refer to the joint density over $(s,a,r,s')$ or its marginal on $(s,a)$ as $P_{S,A,R,S'}(\cdot)$ and $P_{S,A}(\cdot)$.
We define the stationary and instantaneous density ratios, respectively, as

$$\ts w_{\epol}(s,a)\coloneqq \frac{d_{\epol,\gamma}(s,a)}{P_{S,A}(s,a)},\qquad\eta_{\epol}(s,a)\coloneqq \frac{\epol(a\mid s)}{\bpol(a\mid s)}.$$

We will use $\E[\cdot]$ to denote the expectation wrt $P_{S,A,R,S'}(\cdot)$, and use $\E_n[\cdot]$ as the empirical average over the $n$ data points. We define $\|f\|_2=(\E[f^2(s,a,r,s')])^{1/2}$ and $\|f\|_{2,n}=(\E_{n}[f^2(s,a,r,s')])^{1/2}$.

There are three general approaches to OPE in this infinite-horizon setting. The direct method (DM) approach is $(1-\gamma)\E_{s\sim d_0}[\hat q(s,\epol)]$, where $\hat q$ is an estimator for $q_{\epol}$, such as FQI. The infinite-horizon importance sampling (IS) approach [32] is $\E_n[\hat w(s,a)r]$, where $\hat w$ is an estimator for $w_{\epol}$.
Compared to IS with sequential density ratios [39, 24], IS using $w$-functions avoids the exponential-in-horizon variance of the former.
The infinite-horizon doubly robust (DR) approach [27] is $(1-\gamma)\E_{s\sim d_0}[\hat q(s,\epol)]+\E_n[\hat w(s,a)(r-\hat q(s,a)+\gamma \hat q(s',\pi_e))].
All of these rely on some $q$- and/or $w$-estimates.

§.§ Minimax Offline RL

We now define the estimators we will study. Given function classes $\Wbbb_1,\Wbbb_2,\Qbbb_1,\Qbbb_2$ on $\Scal\times \Acal$ and stabilization coefficients $\lambda,\lambda'\geq0$ we define the minimax indirect learning (MIL) estimators:

\begin{align*}
\ts  \hat w_{\MIL} &=  \ts \argmin_{w \in \Wbbb_1}\max_{q \in \Qbbb_1}\E_n[w(s,a)\{-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{s_0\sim d_0 }[v(s_0)]-\lambda \|\Jcal q\|^2_{2,n},\\
\ts  \hat q_{\MIL}&=  \ts \argmin_{q\in \Qbbb_2}\max_{w \in \Wbbb_2}\E_n[w(s,a)\{r-q(s,a)+\gamma v(s')\}]-\lambda' \|w\|^2_{2,n},
\end{align*}

where $v(s)=q(s,\epol),\mathcal{J} q=-q(s,a)+\gamma v(s')$.

Intuitively, $\Wbbb_1,\Wbbb_2$ are hypothesis classes for $w$ and $\Qbbb_1,\Qbbb_2$ for $q$. When there is no confusion, we often write $\Wbbb$ for $\Wbbb_1,\Wbbb_2$ and $\Qbbb$ for $\Qbbb_1,\Qbbb_2$.
We let $C_{\Qbbb},C_{\Wbbb}$ be some constants such that $\|q\|_{\infty}\leq C_{\Qbbb},\forall q\in \Qbbb,\|w\|_{\infty}\leq C_{\Wbbb},\forall w\in \Wbbb$. For simplicity, we assume these function classes are symmetric ($\Wbbb_1=-\Wbbb_1$, etc.).
The stabilizer terms related to $\lambda,\lambda'$ will be key to obtaining fast rates. These estimators are inspired by and in some sense unify the various proposals in 3, 8, 43, 53, 35, 17, 41; we discuss the details in <ref>. We analyze another minimax approach related to 23, 36, which we term minimax direct learning (MDL), in <ref>.

Given these estimators for $w$ and $q$, we consider the resulting DM, IS, and DR estimators for $J$:

\begin{align*}
\ts  \hat J^{\MIL}_{q}&=\ts \E_{s_0 \sim d_0}[\hat q_{\MIL}(s_0,\epol)],\qquad\hat J^{\MIL}_{w}=\ts \E_n[\hat w_{\MIL}(s,a)r],\\
\ts \hat J^{\MIL}_{wq}&=\ts \E_n[\hat w_{\MIL}(s,a)\{r-\hat q_{\MIL}(s,a)+\gamma \hat q_{\MIL}(s',\epol)\}]+(1-\gamma)\E_{s_0\sim d_0}[\hat q_{\MIL}(s_0,\epol)].
% \\
% \ts  \hat w_{\MIL} &=  \ts \argmin_{w \in \Wbbb_1}\max_{q \in \Qbbb_1}\E_n[w(s,a)\{-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{s_0 \sim d_0}[v(s_0)]-\lambda \|-q(s,a)+\gamma v(s')\|^2_n,\\
% \ts  \hat q_{\MIL}&=  \ts \argmin_{q\in \Qbbb_2}\max_{w \in \Wbbb_2}\E_n[w(s,a)\{r-q(s,a)+\gamma v(s')\}]-\lambda' \|w\|^2_n,
\end{align*}

§.§ Concentrability and the Adjoint and Backward Operators

We assume the following throughout.
Letting $P_{S'}(\cdot)$ denote the density of $s'$ under $P_{S,A,R,S'}(\cdot)$,

\begin{align*}
\ts    \|w_{\epol}\|_{\infty}\leq C_w,\quad    \|\eta_{\epol}\|_{\infty}\leq C_{\eta},\quad \|P_{S'}(\cdot)/P_{S}(\cdot)\|_{\infty} \leq C_m.
% \footnote{The assumption $\|P_{S'}(\cdot)/P_{S}(\cdot)\|_{\infty} \leq C_m$ is required to ensure the boundedness of the transition operator. Then, the adjoint operator of the transition operator is well-defined. This assumption holds when the batch data is drawn from the stationary distribution.}
\end{align*}

The first and second assumption are standard in offline RL [3]. Besides, the third assumption is reasonable noticing that if $P_{S}(\cdot)$ is invariant (stationary) under the Markov kernel $\pi_b(a\mid s)P_{S'\mid S,A}(\cdot\mid s,a)$ then $P_{S}(\cdot)=P_{S'}(\cdot)$ and we can take $C_m=1$.

Under this assumption, there uniquely exists the adjoint transition operator (see <ref>):

$$\Tcal':~\E[f(s,a)\Tcal g(s,a)]=\E[\Tcal'f(s,a)g(s,a)]~~\forall f,g: \|f\|_2,\|g\|_2<\infty$$

We also define the backward Bellman operator:

$$\ts \Bcal':~f(s,a) \mapsto \gamma \Tcal'f+(1-\gamma)\frac{d_{0}(s)\epol(a|s)}{P_{S,A}(s,a)}.$$

In RL, $\Tcal,\Bcal$ are natural for describing $q$-functions.
$\Tcal',\Bcal'$ can be understood as the analogues for $w$-functions. Then next lemma establishes both the $q$- and $w$-Bellman equations.

By letting $\Tcal_{\gamma} \coloneqq\gamma \Tcal-I,\Tcal'_{\gamma} \coloneqq\gamma \Tcal'-I$, we have

\begin{align*}\ts
(\Bcal-I)q=\Tcal_{\gamma}(q-q_{\epol})\;\forall q,\qquad(\Bcal'-I)w=\Tcal'_{\gamma}(w-w_{\epol})\;\forall w.
\end{align*}

In particular, we have $\Bcal q_{\epol}=q_{\epol},\,\Bcal' w_{\epol}=w_{\epol}$.

§.§ Notation and Definitions

We write $A \lesssim B$ to mean $A\leq c_0B$, where $c_0$ is a universal constant, that is, one independent of $(1-\gamma)^{-1},R_{\max},C_w,C_{\eta},C_m,\lambda,C_{\Qbbb},C_{\Wbbb},C_{\eta},C_{\iota},C_\xi,\log(1/\delta)$. The quantities $C_{\eta},C_{\iota},C_\xi$ are defined later.
We also write $A\lesssim_\delta B$ to mean $\mathbb P(A\leq c_0B)\geq1-\delta$, where $c_0$ is also independent of $\delta$.

Any constants denoted $c_0,c_1,\dots$ are universal but may be different in each appearance, unless noted otherwise.

The empirical localized Rademacher complexity of a class $\Gcal$ of function $V\to [-C_2,C_2]$ for a given set of samples $v_1,\dots,v_n$ is defined as

\begin{align*}\ts
\Rcal_n(\eta;\Gcal)=\E_{\epsilon}\bracks{\sup_{g\in \Gcal: \|g\|_{2,n}\leq \eta }\frac{1}{n}\sum_i \epsilon_i g(v_i)},
\end{align*}

where $\E_{\epsilon}$ is shorthand for $\frac1{2^n}\sum_{\epsilon\in\{-1,1\}^n}$, , expectation over independent Rademacher variables (not marginalizing other randomness).

The empirical Rademacher complexity of $\Gcal$ is $\Rcal_n(\Gcal)=\Rcal_n(\infty;\Gcal)$. A critical radius of $\Gcal$ is any solution $\eta$ to $\Rcal_n(\eta;\Gcal)\leq \eta^2/C_2$ when $\|\Gcal\|_{\infty}\leq C_2$.
Let $\Ncal(\tau,\Fcal,\|\cdot\|)$ denote the $\tau$-covering number of $\Gcal$ wrt the norm $\|\cdot\|$, ,
the minimal number of $\tau$-radius $\|\cdot\|$-balls needed to cover $\Gcal$. We call a set $S$ star-shaped if there exists a point $z_0\in S$ s.t. $\forall z\in S,\forall \alpha\in[0,1],z_0\alpha+z(1-\alpha)\in S$. We denote the spectrum of a matrix $A$ by $\sigma(A)$ and its maximum singular value by $\sigma_{\max}(A)$.

§ FINITE SAMPLE ANALYSIS WITHOUT STABILIZERS: SLOW RATES AND INEFFICIENCY

In this section we analyze the MIL estimators without stabilizers ($\lambda=\lambda'=0$).
We do this mostly for thoroughness and comparison. We will obtain stronger results in <ref>, establishing fast rates for $w$- and $q$-estimation and first-order optimality for OPE.

§.§ Finite Sample Analysis Under $w$- and $q$-realizability

First we consider the case where we assume that $\Wbbb$ and $\Qbbb$ each contain the true $w$- and $q$-functions, respectively, which we call $w$- and $q$-realizability. The below is adapted from <cit.>, but also extended to $\hat  J^{\MIL}_{wq}$ (and phrased using empirical complexities). More crucially, going beyond 43, we will proceed to analyze the error terms to also obtain a rate.

We set $\lambda=\lambda'=0$. Define

\begin{align*}
\ts \Gcal(\Wbbb,\Qbbb)& \ts\coloneqq \{w(s,a)(-q(s,a)+\gamma q(s',\epol)):w\in\Wbbb,\,q\in\Qbbb\}\\
\ts   \mathrm{Err}_{\MIL,w} & \ts\coloneqq\Rcal_n(\Gcal(\Wbbb_1,\Qbbb_1))+C_{\Wbbb_1}(R_{\max}+C_{\Qbbb_1})\sqrt{\log(c_0/\delta)n^{-1}},\\
\ts   \mathrm{Err}'_{\MIL,w}& \ts\coloneqq R_{\max}\Rcal_n(\Wbbb_1)+R_{\max}C_{\Wbbb_1}\sqrt{\log(c_0/\delta)n^{-1}},\\
\ts  \mathrm{Err}_{\MIL,q}& \ts\coloneqq R_{\max}\Rcal_n(\Wbbb_2)+\Rcal_n(\Gcal(\Wbbb_2,\Qbbb_2))  +C_{\Wbbb_2}(R_{\max}+C_{\Qbbb_2})\sqrt{\log(c_0/\delta)n^{-1}},\\
\ts   \mathrm{Err}_{\MIL,wq}& \ts\coloneqq \Rcal_n(\Gcal(\Wbbb_1,\Qbbb_2))+C_{\Wbbb_1}(R_{\max}+C_{\Qbbb_2})\sqrt{\log(c_0/\delta)n^{-1}}
\end{align*}

* If $w_{\epol}\in \Wbbb_1,q_{\epol}\in \Qbbb_1$, then $\ts|\hat  J^{\MIL}_w-J| \lesssim_\delta \mathrm{Err}_{\MIL,w}+\mathrm{Err}'_{\MIL,w}$.

* If $w_{\epol}\in \Wbbb_2,q_{\epol}\in \Qbbb_2$, then $\ts   |\hat  J^{\MIL}_q-J| \lesssim_\delta \mathrm{Err}_{\MIL,q}$.

* If either $w_{\epol}\in \Wbbb_1,q_{\epol}-\Qbbb_2 \subset \Qbbb_1$ or $w_{\epol}-\Wbbb_1 \subset \Wbbb_2,q_{\epol}\in \Qbbb_2$, then $\ts
|\hat  J^{\MIL}_{wq}-J|\lesssim_\delta \max(   \mathrm{Err}_{\MIL,w},  \mathrm{Err}_{\MIL,q} )+\mathrm{Err}_{\MIL,wq}$.

Crucially, $\hat w_{\MIL},\hat q_{\MIL}$ might not actually converge to $w_{\epol},q_{\epol}$, and irrespective of that, we can still ensure that the MIL OPE estimators converge.
When $\Wbbb=\Wbbb_1=\Wbbb_2$, $\Qbbb=\Qbbb_1=\Qbbb_2$, all of the error terms are equivalent and the dominating term is $\Rcal_n(\Gcal(\Wbbb,\Qbbb))$, suggesting that in this case all MIL estimators have essentially the same error.

Analysis of the error term  We investigate the error terms in <ref>.

The detailed analysis is in <ref>.
To simplify the presentation, we focus on the order wrt the sample size. The dependence on the other problem dependent quantities are still polynomial.

The estimator $\hat J^{\MIL}$ is one of $\hat J^{\MIL}_w,\hat J^{\MIL}_q, \hat J^{\MIL}_{wq}$ assuming $\Wbbb_1=\Wbbb_2=\Wbbb,\Qbbb_1=\Qbbb_2=\Qbbb$.

[VC-subgraph classes]
Let $V(\Wbbb),V(\Qbbb)$ be the VC-subgraph dimension (pseudodimension) of $\Wbbb,\Qbbb$, respectively <cit.>. For example,  $\Wbbb=\{\theta^{\top}\phi :\theta \in \Rl^d\}$ has VC-subgraph dimension $d+1$.

Let $O(\cdot)$ be the order for $n,V(\Wbbb),V(\Qbbb)$.

\begin{align*}
\ts \Rcal_n(\Gcal(\Wbbb,\Qbbb))= O(\sqrt{\max(V(\Wbbb),V(\Qbbb) )/n}).
\end{align*}

[Nonparametric models]
Many common function classes such as , Sobolev and Besov balls do not fall under the above but their metric entropy can still be characterized [30]. E.g., when $\Wbbb$ is contained in a  ball with smoothness $\alpha$ and input dimension $d$ then, $\log \Ncal(\tau,\Wbbb,\|\cdot\|_{\infty})=O((1/\tau)^{d/\alpha})$ <cit.>.

Suppose $\log \Ncal(\tau,\Wbbb,\|\cdot\|_{\infty})=O((1/\tau)^{\beta_1}),\log \Ncal(\tau,\Qbbb,\|\cdot\|_{\infty})=O((1/\tau)^{\beta_2})$ for $\beta_1,\beta_2>0$. Letting $\beta=\max(\beta_1,\beta_2)$, with probability $1-\delta$, $\Rcal_n(\Gcal(\Wbbb,\Qbbb))$ is (1) $ O(n^{-1/2})\,,\beta<2 $, (2) $ \tilde O(n^{-1/2}),\beta=2 $, (3) $ O(n^{-1/\beta}),\beta>2$,
where $O(\cdot)$ is the order for $n$.

The error is decided by the worst $\tau$-entropy of two function classes. Thus, if at least one function class is non-Donsker  $(\beta\geq 2)$, we cannot ensure that the final error rate is $O(n^{-1/2})$.

[Neural networks]

Neural networks that grow with the sample size can approximate some nonparametric models [50]. We consider neutral networks with a ReLU activation function that approximate the Sobolev ball $H^{\alpha}_K([0,1]^d)$ with input dimension $d$ and order $\alpha$ and norm $K$. Since the function class grows with $n$, it is not suitable to directly assume realizability on $\Wbbb,\Qbbb$. Instead, assuming $w_{\epol},q_{\epol}\in H^{\alpha}_K([0,1]^d)$, we have the following theorem.

Suppose $\Wbbb=\Qbbb=\Fcal_{NN}$ and $w_{\epol},q_{\epol}\in H^{\alpha}_K([0,1]^d)$.
Let $\Fcal_{NN}$ the set of neural networks with ReLU activations, $L=O(\log \Omega)$ layers, and $\Omega=O(n^{d/(2\alpha+d)})$ weight parameters. Then with probability $1-\delta$, $|\hat J^{\MIL}-J|= \tilde O(n^{-\frac{\alpha}{2\alpha+d}})$.

In <ref> and <ref>, assuming $q_{\epol}\in \Qbbb, \,w_{\epol}\in \Wbbb$, we can apply <ref>. On the other hand, since we cannot use this assumption in this example, we cannot directly apply <ref>. We need a theorem agnostic to $q_{\epol}\in \Qbbb,\,w_{\epol}\in \Wbbb$, that is, robust up to $L^{\infty}$- type of model-misspecification, which will be discussed in <ref>. We also discuss an overparameterization case in <ref>.

§.§ Finite Sample Analysis Under $w$- and $q$-completeness

We have so far assumed $w$, $q$-realizability. We now show other conditions are also sufficient to obtain convergence rates. One of the conditions, $w$-completeness, is a novel condition.

When $\lambda=\lambda'=0$,

*  If $w_{\epol}\in \Wbbb_1,C_{\xi}(\Wbbb_{1}-w_{\epol})\subset \Tcal_{\gamma}\Qbbb_{1}$ then  $\ts  \|\hat w_{\MIL}- w_{\epol}\|_2\lesssim_\delta \sqrt{C^{-1}_{\xi}\mathrm{Err}_{\MIL,w}}$,

*  If $w_{\epol}\in \Wbbb_1,C_{\xi}\Tcal'_{\gamma}(\Wbbb_{1}-w_{\epol})\subset \Qbbb_{1} $ then  $ \ts \|\hat w_{\MIL}-\Bcal'\hat w_{\MIL}\|_2\lesssim_\delta \sqrt{C^{-1}_{\xi}\mathrm{Err}_{\MIL,w}}$,

*  If
$q_{\epol}\in \Qbbb_2,C_{\xi} \Tcal_{\gamma}(\Qbbb_{2}-q_{\epol})\subset \Wbbb_{2} $ then  $\ts  \|\hat q_{\MIL}-\Bcal\hat q_{\MIL} \|_2\lesssim_\delta \sqrt{C^{-1}_{\xi}\mathrm{Err}_{\MIL,q}}$,

*  If
$q_{\epol}\in \Qbbb_2,C_{\xi}(\Qbbb_{2}-q_{\epol})\subset \Tcal'_{\gamma}\Wbbb_{2} $, then  $ \ts \|\hat q_{\MIL}-q_{\epol} \|_2\lesssim_\delta  \sqrt{C^{-1}_{\xi}\mathrm{Err}_{\MIL,q}}$.

Whereas <ref> provided bounds directly on OPE (and $\hat q^{\MIL},\hat w^{\MIL}$ may well be inconsistent),
<ref> provides convergence rates for estimating $q$ and $w$ themselves.
We will discuss the implications for OPE below in <ref>.
Notice the $\mathrm{Err}_{\MIL}$ terms in the bounds are in a square-root. In this sense, the rates are slow, for example of order $O(n^{-1/4})$ for VC-subgraph classes.

This will also correspond to slow rates for OPE.

Generally, the norms $\|\Bcal q-q\|_2$ and $\|q-q_{\epol}\|_2$ (or, $\|\Bcal' w-w\|_2$ and $\|w-w_{\epol}\|_2$) are not equivalent. [We define two norms $\|x\|_{A}$ and $\|x\|_{B}$ on $x\in \mathcal{X}$ are equivalent when there exist constants $c_1,c_2$ s.t. $c_1\|x\|_{B}\leq \|x\|_{A}\leq c_2\|x\|_{B}\,\forall x\in \mathcal{X}$.]  When $\gamma$ is small they are, however, necessarily equivalent.

When $\gamma \sqrt{C_mC_{\eta}}<1$, (1) $\|\Bcal q-q\|_2$ and $\|q-q_{\epol}\|_2$ are equivalent, (2) $\|\Bcal w-w\|_2$ and $\|w-w_{\epol}\|_2$ are equivalent.

$q$-completeness and adjoint $q$-completeness The condition in <ref> is essentially equivalent to the completeness condition of FQI when $\Wbbb_2=\Qbbb_2$ since $\Tcal_{\gamma}(\Qbbb_2-q_{\epol})=(\Bcal -I)\Qbbb_2$. Thus, we call this condition $q$-completeness. In linear MDPs [25], it is known that this condition holds when using linear classes <cit.>. The condition in <ref> is a flipped version of $q$-completeness, which we call adjoint $q$-completeness. This condition also holds under some additional assumptions, as we show below. In particular, in the tabular case, we can use unrestricted classes $\Wbbb,\Qbbb$; and $q$-and adjoint $q$-hold.

For $\phi:\mathcal S\times\mathcal A\to\mathbb R^d$, suppose $P_{S'|S,A}(s'|s,a)=\theta(s')^{\top}\phi(s,a)$, $\E_{r\sim P_{R|S,A}}[r\mid s,a]=\theta^{\top} \phi(s,a)$.
Let $\Qbbb\coloneqq \{(s,a)\mapsto\beta^{\top} \phi(s,a):\beta\in \mathbb{R}^d\}$. Then:
(1) $ q_{\epol}\in\Qbbb$, (2) $\Tcal_{\gamma}(\Qbbb-q_{\epol})\subset \Qbbb$, (3) Letting $M_{\epol}$ be s.t. $\Tcal (\beta^{\top}\phi)=(M_{\epol}\beta)^{\top}\phi$ (which exists), if $1/\gamma \notin \sigma(M_{\epol})$ and $\E[\phi\phi^{\top}]$ is non-singular, then $(\Qbbb-q_{\epol})\subset \Tcal'_{\gamma}\Qbbb $, (4) if the state and action spaces are finite, $\ts P_{S,A}(s,a)>0\,\forall (s,a)\in \Scal\times \Acal$, and $\phi$ is the standard basis in $\mathbb R^{|\mathcal S||\mathcal A|}$, then $\ts \Tcal_{\gamma}(\Qbbb-q_{\epol})\subset \Qbbb,\,(\Qbbb-q_{\epol})\subset \Tcal'_{\gamma}\Qbbb$.

When the feature vector $\phi$ in <ref> is “stochastic” as defined in <ref> [5], we can guarantee $M_{\epol}$ is a stochastic matrix and $\sigma_{\max}(M_{\epol})\leq 1$ so that adjoint q-is ensured.

Similarly, when $P_{S'|S,A}(s'|\cdot)\,P_{R|S,A}(r|\cdot)$ belong to  or Sobolev balls, the $q$-completeness holds by taking $\Wbbb_2$ and $\Qbbb_2$ to be  or Sobolev balls.

$w$-and adjoint $w$- We refer to the condition in <ref>, which is equivalent to $C_{\xi}(\Bcal-I)\Wbbb_1\subset \Qbbb_1$, as $w$-.
Its flipped version in <ref>, we call adjoint $w$-. Both $w$-and adjoint $w$-hold in a tabular case. Beyond a tabular setting, these conditions are still reduced to simple conditions.

For $\psi:\mathcal S \to\mathbb R^d$, suppose $P_{S,A|S'}(s,a|s')=\theta(s,a)^{\top}\psi(s')$, $d_{0}(s)/P_{S}(s)=\theta^{\top} \psi(s)$, where $P_{S,A|S'}(s,a|s')$ is a posterior density of $(s,a)$ given $s'$. Assume $P_{S'}=P_S$, , the batch data comes from $\pi_b$'s stationary distribution.
Let $\Wbbb\coloneqq \{ (s,a)\mapsto\beta^{\top}\psi(s)\eta_{\epol}(s,a):\beta \in\mathbb{R}^d\}.$
(1) $w_{\epol}\in\Wbbb$;
(2) $\Tcal'_{\gamma}(\Wbbb-w_{\epol})\subset \Wbbb$;
(3) Letting $M'_{\epol}$ be s.t. $\Tcal'(\beta^{\top}\eta_{\epol}\psi)=(M'_{\epol}\beta)^{\top}\eta_{\epol}\psi$ (which exists), if $1/\gamma \notin \sigma(M'_{\epol})$ and $\E[\psi\psi^{\top}]$ is non-singular, then $(\Wbbb-w_{\epol})\subset \Tcal_{\gamma}\Wbbb$.

If the state and action spaces are finite, $P_{S,A}(s,a)>0\,\forall (s,a)\in \Scal\times \Acal$, $\Wbbb=\{\beta^{\top}\phi(s,a):\beta\in\mathbb{R}^d\}$, where $\phi(s,a)$ is the standard basis in $\mathbb R^{|\mathcal S||\mathcal A|}$, then $\Tcal'_{\gamma}(\Wbbb-w_{\epol})\subset \Wbbb,\,(\Wbbb-w_{\epol})\subset \Tcal_{\gamma}\Wbbb$.

The stationarity assumption is reasonable if the data is generated by long trajectories.

Notice that compared to a linear MDP, here the linearity assumption is agnostic to the reward and is imposed on the posterior transition density rather than the transition density.
Again, when the feature vector is “stochastic” as defined in <ref>, we will have $\sigma_{\max}(M'_{\epol})\leq 1$ and satisfy (3) in <ref>.

§.§ Application to Policy Value Estimation

We now show how <ref> can be translated into an error bound for OPE.
When $\lambda=\lambda'=0$,

* If $w_{\epol}\in \Wbbb_1$, and either $C_{\xi}\Tcal'_{\gamma}(\Wbbb_1-w_{\epol})\subset \Qbbb_1$ or $C_{\xi}(\Wbbb_{1}-w_{\epol})\subset \Tcal_{\gamma}\Qbbb_{1}$, then $\ts |\hat J^{\MIL}_w-J|\lesssim_\delta \mathrm{Err}'_{\MIL,w}+C_{\Qbbb}\sqrt{C^{-1}_{\xi}\mathrm{Err}_{\MIL,w}}$.

* If $q_{\epol}\in \Qbbb_2$, and either $C_{\xi}\Tcal_{\gamma}(\Qbbb_2-q_{\epol})\subset \Wbbb_2$ or $C_{\xi}(\Qbbb_2-q_{\epol})\subset \Tcal'_{\gamma}\Wbbb_2$,  then $\ts |\hat J^{\MIL}_q-J |\lesssim_\delta  C_{\Wbbb}\sqrt{C^{-1}_{\xi}\mathrm{Err}_{\MIL,q}}$.

*  If any one of the four conditions above hold, then
|\hat J^{\MIL}_{wq}-J |\lesssim_\delta  \mathrm{Err}_{\MIL,wq}+C^{-1/2}_{\xi}\max(\break C_{\Qbbb}\sqrt{\mathrm{Err}_{\MIL,w}},\,C_{\Wbbb}\sqrt{\mathrm{Err}_{\MIL,q}}).

While the conditions do not require both $w$-realizability and $q$-realizability,
the rates in <ref> are slower than the ones of <ref>. <Ref> is a double robustness result: it says that the estimator is consistent as long as $w$-and $w$-or $q$-and $q$-holds. We can also have a doubly robustness result by replacing completeness with adjoint completeness.

§ FINITE SAMPLE ANALYSIS WITH STABILIZERS UNDER W-COMPLETENESS OR Q-

In this section, we show MIL with stabilizers ($\lambda>0,\lambda'>0$) attains fast rates under completeness. This gives the first result for a fast rate of estimating $w$-functions in a general function approximation setting. For $q$-functions, this allows us to obtain fast rates using MIL of the same order as FQI (see <ref> regarding FQI).
We then study implications for OPE and compare to results without stabilizers  ($\lambda=\lambda'=0$) .

§.§ Fast Rates for $w$- and $q$-function Estimation

Let $\eta_n$ be an upper bound on the critical radii of $\Gcal_{w1}$ and $\Gcal_{w2}$, where

\begin{align*}
\Gcal_{w1}&\coloneqq \{(s,a,s')\mapsto  (q(s,a)-\gamma q(s',\epol)): q\in \Qbbb_1 \}, \\
\Gcal_{w2}&\coloneqq  \{(s,a,s')\mapsto ( w(s,a)-w_{\epol}(s,a))(-q(s,a)+\gamma q(s',\epol)) : w\in \Wbbb_1,q\in \Qbbb_1 \}.
\end{align*}

Suppose $w_{\epol}\in \Wbbb_1$, $C_{\xi}\Tcal'_{\gamma}(\Wbbb_1-w_{\epol}) \subset \Qbbb_1$, and that $\Qbbb_1$ is star shaped.

\begin{align*}
\ts   \|\Bcal' \hat w_{\MIL}-\hat w_{\MIL}\|_2\lesssim_\delta C^{*}_w \eta_w,C^{*}_w= 1+\frac{\lambda^2+C^2_{\Wbbb_1}}{\lambda}+C_{\Wbbb_1}+\gamma \sqrt{C_mC_{\eta}}C_{\Wbbb_1}+\frac{1}{C_{\xi}},\,\eta_w= \eta_n+c_0\sqrt{\frac{\log(c_1/\delta)}{n}}.
\end{align*}

Let $\eta_n$ be an upper bound on the critical radii of $\Wbbb_2$ and $\Gcal_q$, where

\begin{align*}
\Gcal_q:=\{(s,a,s')\mapsto (-q(s,a)+q_{\epol}(s,a)+\gamma q(s',\epol)-\gamma q_{\epol}(s',\epol)) w(s,a):q \in \Qbbb_2,w\in \Wbbb_2\}.
\end{align*}

Suppose $q_{\epol}\in \Qbbb_2$, $C_{\xi}\Tcal_{\gamma}(\Qbbb_2-q_{\epol})\subset \Wbbb_2$, and that $\Wbbb_2$ is star shaped. Then,

\begin{align*}\ts
\|\Bcal \hat q_{\MIL}-\hat q_{\MIL} \|_2\lesssim_\delta C^{*}_q\eta_q, C^{*}_q=1+R_{\max}+C_{\Qbbb_2}+\frac{\lambda'^2+(R_{\max}+C_{\Qbbb_2})^2}{\lambda'}+\frac1{C_{\xi}},\eta_q=\eta_n+c_0\sqrt{\frac{\log(c_1/\delta)}{n}}.
\end{align*}

These theorems state that MIL with stabilizers converge at fast rates when we assume and completeness.

Similar bounds can be obtained for $\|\hat w_\MIL-w_{\epol}\|_2$ and
$\|\hat q_\MIL-q_{\epol}\|_2$ under corresponding and adjoint conditions (<ref>).

Analysis of critical radius We next analyze $\eta_q$ for several function classes, focusing on the rate wrt $n$. Again, the dependence on the other problem dependent quantities are polynomial.
For the details refer to <ref>. The rate $\eta_w$ is similarly calculated.

[VC-subgraph classes]
Let $V(\Wbbb_2),V(\Qbbb_2)$ be the VC-subgraph dimension of $\Wbbb_2,\Qbbb_2$.

Let $\tilde O(\cdot)$ be the order wrt $V(\Wbbb_2),V(\Qbbb_2),n$. Then,
$\ts \eta_q=\tilde O(\sqrt{\max(V(\Wbbb_2),V(\Qbbb_2) )/n}). $

[Nonparametric Models]
As in <ref>, we consider nonparmetric models.

Assume $\log\Ncal(\tau,\Wbbb_2,\|\cdot\|_{\infty})=(1/\tau)^{\beta_1},\log\Ncal(\tau,\Qbbb_2,\|\cdot\|_{\infty})=(1/\tau)^{\beta_2}$ for $\beta_1,\beta_2>0$. Then, letting $\beta=\max(\beta_1,\beta_2)$ and $O(\cdot)$ be the order wrt $n$,  $\eta_q$ is (1) $O(n^{-1/(2+\beta)}),\beta <2$,(2) $ \tilde O(n^{-1/4}),\,\beta=2$, (3) $ O(n^{-1/(2\beta)}),\,\beta>2.$

Note the rate in the case of $\beta<2$ is the minimax optimal rate for regression <cit.>. The rate in the case of $\beta\geq 2$ is typically improved by more careful analysis depending on the function classes as in the next example.

[Neural Networks]
As in <ref>, we consider using neural networks with an ReLU activation function. The notation $O(\cdot)$ is the order wrt $n$. Since $\Qbbb_2,\Wbbb_2$ grow with $n$, we impose the and on the Sobolev ball $H^{\alpha}_K([0,1]^d)$. Then, with probability $1-\delta$, we have $\|\Bcal \hat q_{\MIL}-\hat q_{\MIL}\|_2= \tilde{O}(n^{-\alpha/(2\alpha + d)})$. Regarding the details, refer to <ref>.

§.§ Application to the Policy Value Estimation

We next translate the above analysis into the error bounds for OPE.

(1) Under the conditions of <ref>,  $ \ts |\hat J^{\MIL}_w-J|\lesssim_\delta \|q_{\epol}\|_2\eta_wC^{*}_w+\mathrm{Err}'_{\MIL,w}$. (2)  Under the conditions of <ref>,  $\ts |\hat J^{\MIL}_q-J |\lesssim_\delta  \|w_{\epol}\|_2\eta_qC^{*}_q.$

Let us compare to <ref> by focus on the case of $\hat J^{\MIL}_q$.

For VC classes, both <ref> give $\tilde O(n^{-1/2})$. and <ref> gives $O(n^{-1/4})$.
For nonparametric models as in <ref> with $\beta<2$, <ref> gives $O(n^{-1/2})$, <ref> gives $O(n^{-1/4})$, and <ref> gives $O(n^{-1/(2+\beta)})$.

For $\beta\geq 2$, <ref> gives $O(n^{-1/(\beta)})$ and both <ref> give $O(n^{-1/(2\beta)})$ (when $\beta=2$, we have $\tilde O$).
Therefore, the rate in <ref> is fastest in each case and <ref> the slowest, while <ref> coincides with the best and worst in different cases.
This is interesting because it highlights the differences between the tasks of OPE and of estimating $w$- and $q$-functions.

§ FIRST-ORDER EFFICIENCY UNDER $W,Q$-REALIZABILITY AND $W,Q$-

When we only assume $w$- and $q$-realizability, the dependence on several problem dependent quantities is generally poor. When the classes $\Wbbb,\Qbbb$ are finite hypothesis classes, the first-order term of the error $|\hat J^{\MIL}_{wq}-J|$ wrt $n$ can be upper-bounded by Bernstein's inequality: with probability $1-\delta$,

\begin{align}\ts\label{eq:finite}
|\hat J^{\MIL}_{wq}-J|\leq\sqrt{\frac{32\sup_{w\in\Wbbb,q\in \Qbbb}\var[w(s,a)\{r-q(s,a)+\gamma q(s',\epol)\}]\times \log(|\Wbbb||\Qbbb|/\delta) }{n}}+O\prns{\frac{\log(|\Wbbb||\Qbbb|/\delta) }{n}}.
\end{align}

This first-order term ($\sqrt{1/n}-$term) might incur an error characterized by the worst variance term. In this section, we prove that the first-order term is further improved under more conditions in that $\sup_{w\in\Wbbb,q\in \Qbbb}\var[w\{r-q+q(s',\epol)\}]$ is surprisingly replaced with $\var[w_{\epol}\{r-q_{\epol}+\gamma q_{\epol}(s',\epol)\}]$. In addition, $\log(|\Wbbb||\Qbbb|/\delta)$ is replaced with $\log(c/\delta)$, where $c$ is some universal constant.
The strategy is localizing around the true $w_{\epol},q_{\epol}$ by assuming both realizability and completeness.
This is crucial as it means the first-order term matches the asymptotic efficiency bounds of 27, thus we obtain the first finite-sample bound with first-order efficiency in non-tabular environments.

We analyze a sample-splitting (double reinforcement learning) version of $\hat J^{\MIL}_{wq}$ as in 27 but using MIL estimators for $w$ and $q$: we randomly split the data into two even folds, we estimate $\hat w_{\MIL}^{(1)},\hat q_{\MIL}^{(1)}$ using data only from the first and $\hat w_{\MIL}^{(2)},\hat q_{\MIL}^{(2)}$ using the second, then when computing $\hat J^{\MIL}_{wq}$, which is defined as a sample average, whenever we average over a data point in the first fold we use the estimates from the second fold and vice versa. (For details see <ref>.) The sample-splitting simplifies the analysis of the stochastic equicontinuity term [38] in the error.

Assume the conditions in <ref> hold. Suppose there exists $C_{\iota}$ s.t. $\|q-q_{\epol}\|_2\leq C_{\iota}\|\Bcal q-q\|_2\,\forall q\in \Qbbb_2$ and $\|w-w_{\epol}\|_2\leq C_{\iota}\|\Bcal'w-w\|_2\,\forall w\in \Wbbb_1$. Then, with probability $1-(\delta+10\delta')$, we have, for some universal constant $c_0$,

\begin{align}
\ts  |\hat J^{\MIL}_{wq}-J|& \ts \leq \sqrt{\frac{2\E[w^2_{\epol}(s,a)\{r-q_{\epol}(s,a)+v_{\epol}(s')\}^2]\log(1/\delta)}{n}} \label{eq:firstfirst}\\
&\ts +c_0\braces{\eta_{w}\eta_qC^{*}_{w}C^{*}_{q}C_{\iota}+(C^{*}_{w}\eta_w+C^{*}_q\eta_q\sqrt{1+C_{\eta}C_m})C_{\iota}\sqrt{\frac{\log(1/\delta')}{n}}+\frac{C_{\Wbbb_1}C_{\Qbbb_2}(\log(1/\delta)+\log(1/\delta'))}{n}}. \nonumber
\end{align}

This theorem implies that the rate wrt $n$ is $\max(\eta_w\eta_q,O(n^{-1/2}))$ under $w$- and $q$-, $w$- and $q$-completeness, and the assumption $\|q-q_{\epol}\|_2\leq C_{\iota}\|\Bcal q-q\|_2$, $\|w-w_{\epol}\|_2\leq C_{\iota}\|\Bcal'w-w\|_2$, which we call the recovery assumption.

Consider the case of <ref>, and suppose for $w$-functions we use neural networks approximating the Sobolev ball $H^{\beta_1}_{k_1}([0,1]^{d_1})$ and for $q$-functions neural networks approximating the Sobolev ball $H^{\beta_2}_{k_2}([0,1]^{d_2})$. Then the rate is

$$\ts \max(n^{-\frac{\beta_1}{2\beta_1+d_1}-\frac{\beta_2}{2\beta_2+d_2} },n^{-1/2}).$$

This shows that even if one of the function class is non-Donsker, i.e., $d_j/\beta_j\geq 2$, we can still obtain a parametric rate $O(n^{-1/2})$ as long as $\frac{\beta_1}{2\beta_1+d_1}+\frac{\beta_2}{2\beta_2+d_2}\geq\frac12$. On the other hand, when we only assume $w$- and $q$-realizability in <ref>, if one function class is non-Donsker, we cannot ensure the error bound is $O(n^{-1/2})$, per <ref>.

Whenever $\eta_w\eta_q=o(n^{-1/2})$ (e.g., $\frac{\beta_1}{2\beta_1+d_1}+\frac{\beta_2}{2\beta_2+d_2}>\frac12$ in the neural network example), the first-order term is just the first term in <ref>, which is much tighter than both <ref>. Ignoring the terms related to $\delta'$, the first term now is the tail of a Gaussian with variance

\begin{align}\ts   \label{eq:bound}
\mathrm{EB}=\E[w^2_{\epol}(s,a)\{r-q_{\epol}(s,a)+v_{\epol}(s')\}^2],
\end{align}

which is precisely the asymptotic efficiency bound derived by <cit.>.[The asymptotic efficiency bound has two meanings. First, it is the minimum limiting variance of $\sqrt{n}(\hat J-J)$ among regular estimators $\hat J$ <cit.>. Second, it is a locally minimax lower bound on $\sqrt{n}\E[(\hat J-J)^2]$ among all estimators <cit.>. In parametric models, such as when the MDP is tabular, it coincides with the Cramér-Rao lower bound.] Although 27 showed this lower bound can be achieved asymptotically by a general meta-algorithm, their result is asymptotic and assumes estimators are given satisfying certain rates. Ours is a finite sample result, and we give explicit estimators.

In <ref>, we need the aforementioned recovery assumption to translate Bellman residual errors into $L^2$-errors. As in <ref>, when $\gamma \sqrt{C_mC_{\eta}}< 1$, we have $C_{\iota}=1/(1-\gamma \sqrt{C_mC_{\eta}})$. By utilizing the structure of function classes, the recovery assumption holds even if $\gamma \sqrt{C_mC_{\eta}}\geq 1$ under mild assumptions. In particular, it holds in the tabular case.

Consider linear models $\Wbbb_1=\Wbbb_2=\Qbbb_1=\Qbbb_2=\{\beta^{\top}\phi(s,a);\beta\in \mathbb{R}^d \}$, and define $X \coloneqq \E[\phi(s,a)\phi(s,a)^{\top}]$. (1) Suppose $q_{\epol}\in \Qbbb_2$, and there exists a matrix $M_{\epol}$ s.t. $\Tcal (\beta^{\top}\phi)=(M^{\top}_{\epol}\beta)^{\top}\phi$. If $\bar  M_{\epol}, X$ are non-singular, where $\bar M_{\epol}=\gamma M^{\top}_{\epol}-I$,
the recovery assumption holds with
$$\ts C_{\iota}=\{\sigma_{\max}((\bar  M_{\epol} X\bar M^{\top}_{\epol})^{-1/2}X(\bar  M_{\epol} X\bar M^{\top}_{\epol})^{-1/2})\}^{1/2}.$$
(2) Suppose $w_{\epol}\in \Wbbb_1$ and there exists a matrix $M'_{\epol}$ s.t. $\Tcal'(\beta^{\top}\phi)=(M'_{\epol}\beta)^{\top} \phi$. If  $\bar M'_{\epol}$, $X$ are non-singular, where $\bar M'_{\epol}\coloneqq \gamma M'^{\top}_{\epol}-I$, the recovery assumption holds with
$$\ts C_{\iota}=\{\sigma_{\max}((\bar M'_{\epol}X(\bar M'_{\epol})^{\top})^{-1/2}X(\bar M'_{\epol}X(\bar M'_{\epol})^{\top})^{-1/2})\}^{1/2}.$$

The existence of $M_{\epol},M'_{\epol}$ essentially implies the completeness. <Ref> ensure the existence in linear MDPs and when the posterior transition density is linear.
As in <ref>, the non-singularity of $\bar M_{\pi},\bar M'_{\pi}$ is ensured if the feature vectors are stochastic.

[First-order efficiency in a tabular case]
In a tabular setting, all of the assumptions in <ref> are satisfied from the following lemma. Thus, the first-order lower bound is achieved.
If $|\mathcal S|<\infty$, $|\mathcal A|<\infty$, and $P_{S,A}(s,a)>0\,\forall (s,a)\in \Scal\times \Acal$, then,  $\bar M_{\epol},\bar M'_{\epol},X$ in <ref> are non-singular by taking $\phi(s,a)$ as the standard basis vector in $\mathbb{R}^{|\Scal||\Acal|}$.

We can also obtain the asymptotic statement. This clearly show the first-order bound is achieved.

Assume the conditions in <ref>. Suppose $\eta_w\eta_q=o(n^{-1/2})$. Then, $ \sqrt{n}(\hat J^{\MIL}_{wq}-J)$ weakly converges to a Gaussian distribution with mean $0$ and variance  $\mathrm{EB}$ in (<ref>).

§ COMPARISON TO OTHER WORK

FQI FQI is a method to estimate q-functions by iterating regression so that the one-step bellman residual error is minimized [15, 34, 8]. FQI gives the same rate as $\hat q_\MIL$ with stabilizers wrt $n$ under $q$-and -realizability. Since most of the work discusses the analysis in policy optimization, we need to modify their analysis for policy evaluation. Refer to <ref>.

Modified BRM and DICE papers Modified BRM (Modified Bellman Residual Minimization;

3) is equivalent to $\hat q^{\MIL}$ with $\lambda=0.5$. 16 obtained the fast rate when $\Wbbb_2,\Qbbb_2$ are nonparametric classes by assuming smoothness of the transition operators instead of completeness. We deal with more general function classes. In addition, the analysis is substantially different since the assumption is different.
The series of DICE papers consider several minimax RL estimators with stabilizers [53, 35]. They typically obtain a rate $O(1/\sqrt{n})$ for the policy value assuming the function classes have finite VC dimensions. In our work, we show how the rate will be changed depending on the various assumptions of $\Wbbb,\Qbbb$. To the authors' best knowledge, they do not discuss our main results: $w$-completeness, fast rates for $q$- and $w$-estimation, and first-order efficiency.

Tabular and linear cases
51, 52 analyzed the finite sample error bound of model-based estimators in a tabular time-varying MDP and showed that the the first-order lower bound is achieved. Our result is much more general since it allows any function approximation, includes a tabular case, and applies to the more common time-homogeneous case. 14, 21, 46 considered linear models, and showed upper and lower bounds, but their results are specialized to the linear function approximation setting.

Bandit setting

In the bandit setting, similar results to <ref> are obtained by 18, 40. The RL setting is much more complicated in that we need to take dynamics and therefore completeness into account. The proof idea of <ref> is inspired by 13, which studies the minimax estimation of instrumental variable problems. The adaption to our setting is not straightforward since the problem for estimating $w_{\epol}$ is not characterized by a conditional moment equation.

§ SUMMARY AND FUTURE WORK

We have analyzed the rates of MIL estimators under four cases: (1) $w$- and $q$-realizability, (2) $w$-realizability and -completeness, (3) $q$-realizability and -completeness, (4) $w$- and $q$-realizability and $w$- and $q$-completeness. Settings (2) and (4) are particularly novel setting. And, in (4) with a recovery assumption, we establish the first finite-sample bound with first-order efficiency in general settings.

The next important question is the lower bound under each assumption. The first-order efficiency bound is an asymptotic notion and only concerns the leading term in $n$. Crucially, our finite-sample bounds also establish nice, polynomial dependence on horizon and other parameters in the higher-order terms. Corresponding non-asymptotic lower bounds for each setting, showing whether the dependence in all terms is optimal, is therefore important future work. Recent work [46, 2] has shown exponential-in-horizon lower bounds with only $q$-realizability. Additionally assuming either $w$-realizability or $q$-completeness, our bounds are polynomial in horizon, therefore there is a gap that needs to be filled.

[1]
Agarwal, A., N. Jiang, and S. M. Kakade (2019).
Reinforcement learning: Theory and algorithms.
Technical report, Technical Report, Department of Computer Science,
University of Washington.

[2]
Amortila, P., N. Jiang, and T. Xie (2020).
A variant of the wang-foster-kakade lower bound for the discounted
arXiv preprint arXiv:2011.01075.

[3]
Antos, A., C. Szepesvári, and R. Munos (2008).
Learning near-optimal policies with bellman-residual minimization
based fitted policy iteration and a single sample path.
Machine Learning 71, 89–129.

[4]
Armstrong, T. B. and M. Kolesár (2017).
Finite-sample optimal estimation and inference on average treatment
effects under unconfoundedness.
arXiv preprint arXiv:1712.04594.

[5]
Barreto, A. M. S., J. Pineau, and D. Precup (2014).
Policy iteration based on stochastic factorization.
The Journal of artificial intelligence research 50,

[6]
Bartlett, P. L., O. Bousquet, and S. Mendelson (2005, 08).
Local rademacher complexities.
Annals of Statistics 33(4), 1497–1537.

[7]
Bibaut, A., I. Malenica, N. Vlassis, and M. Van Der Laan (2019).
More efficient off-policy evaluation through regularized targeted
In Proceedings of the 36th International Conference on Machine
Learning, Volume 97, pp.  654–663. PMLR.

[8]
Chen, J. and N. Jiang (2019).
Information-theoretic considerations in batch reinforcement learning.
In Proceedings of the 36th International Conference on Machine
Learning, Volume 97, pp.  1042–1051.

[9]
Chen, X. (2007).
Chapter 76 large sample sieve estimation of semi-nonparametric
Handbook of Econometrics 6, 5549–5632.

[10]
Chernozhukov, V., D. Chetverikov, M. Demirer, E. Duflo, C. Hansen, W. Newey,
and J. Robins (2018).
Double/debiased machine learning for treatment and structural
Econometrics Journal 21, C1–C68.

[11]
Chernozhukov, V., W. Newey, and R. Singh (2018).
De-biased machine learning of global and local parameters using
regularized riesz representers.
arXiv preprint arXiv:1802.08667.

[12]
Debnath, L. (2005).
Hilbert spaces with applications (3rd ed. ed.).
Amsterdam ; Boston: Elsevier/Academic.

[13]
Dikkala, N., G. Lewis, L. Mackey, and V. Syrgkanis (2020).
Minimax estimation of conditional moment models.
arXiv preprint arXiv:2006.07201.

[14]
Duan, Y., Z. Jia, and M. Wang (2020).
Minimax-optimal off-policy evaluation with linear function
In Proceedings of the 37th International Conference on Machine
Learning, Volume 119 of Proceedings of Machine Learning Research, pp.   2701–2709.

[15]
Ernst, D., P. Geurts, and L. Wehenkel (2005).
Tree-based batch mode reinforcement learning.
Journal of Machine Learning Research 6, 503–556.

[16]
Farahm, A., , M. Ghavamzadeh, C. Szepesvári, and S. Mannor (2016).
Regularized policy iteration with nonparametric function spaces.
Journal of Machine Learning Research 17(139), 1–66.

[17]
Feng, Y., L. Li, and Q. Liu (2019).
A kernel loss for solving the bellman equation.
In Advances in Neural Information Processing Systems,
Volume 32, pp.  15456–15467.

[18]
Foster, D. J. and V. Syrgkanis (2019).
Orthogonal statistical learning.
arXiv preprint arXiv:1901.09036.

[19]
Gelada, C. and M. G. Bellemare (2019).
Off-policy deep reinforcement learning by bootstrapping the covariate
In The Thirty-Third AAAI Conference on Artificial
Intelligence, AAAI 2019, pp.  3647–3655.

[20]
Golowich, N., A. Rakhlin, and O. Shamir (2018).
Size-independent sample complexity of neural networks.
In Conference On Learning Theory, pp.  297–299. PMLR.

[21]
Hao, B., Y. Duan, T. Lattimore, C. Szepesvári, and M. Wang (2020).
Sparse feature selection makes batch reinforcement learning more
sample efficient.
arXiv preprint arXiv:2011.04019.

[22]
Hirshberg, D. and S. Wager (2019).
Augmented minimax linear estimation.
arXiv preprint arXiv:1712.00038.

[23]
Jiang, N. and J. Huang (2020).
Minimax confidence interval for off-policy evaluation and policy
arXiv preprint arXiv:2002.02081.

[24]
Jiang, N. and L. Li (2016).
Doubly robust off-policy value evaluation for reinforcement learning.
In Proceedings of the 33rd International Conference on
International Conference on Machine Learning-Volume, 652–661.

[25]
Jin, C., Z. Yang, Z. Wang, and M. I. Jordan (2020).
Provably efficient reinforcement learning with linear function
In Proceedings of Thirty Third Conference on Learning Theory,
Volume 125 of Proceedings of Machine Learning Research, pp.  2137–2143.

[26]
Kallus, N. (2018).
Balanced policy evaluation and learning.
In Advances in Neural Information Processing Systems, pp.  8895–8906.

[27]
Kallus, N. and M. Uehara (2019).
Efficiently breaking the curse of horizon: Double reinforcement
learning in infinite-horizon processes.
arXiv preprint arXiv:1909.05850.

[28]
Kallus, N. and M. Uehara (2020).
Double reinforcement learning for efficient off-policy evaluation in
markov decision processes.
Journal of Machine Learning Research 21(167), 1–63.

[29]
Klaassen, C. A. J. (1987).
Consistent estimation of the influence function of locally
asymptotically linear estimators.
The Annals of Statistics 15, 1548–1562.

[30]
Korostelev, A. P. and O. Korosteleva (2011).
Mathematical statistics: asymptotic minimax theory, Volume 119
of Graduate Studies in Mathematics.
Providence, R.I: American Mathematical Society.

[31]
Le, H., C. Voloshin, and Y. Yue (2019).
Batch policy learning under constraints.
In Proceedings of the 36th International Conference on Machine
Learning, pp.  3703–3712.

[32]
Liu, Q., L. Li, Z. Tang, and D. Zhou (2018).
Breaking the curse of horizon: Infinite-horizon off-policy
In Advances in Neural Information Processing Systems 31, pp.  5356–5366.

[33]
Mendelson, S. (2002).
Improving the sample complexity using global data.
IEEE transactions on Information Theory 48(7),

[34]
Munos, R. and C. Szepesvári (2008).
Finite-time bounds for fitted value iteration.
Journal of Machine Learning Research 9, 815–857.

[35]
Nachum, O., Y. Chow, B. Dai, and L. Li (2019).
Dualdice: Behavior-agnostic estimation of discounted stationary
distribution corrections.
Advances in Neural Information Processing Systems 2019 (To

[36]
Nachum, O., B. Dai, I. Kostrikov, Y. Chow, L. Li, and D. Schuurmans (2019).
Algaedice: Policy gradient from arbitrary experience.
arXiv preprint arXiv:1912.02074.

[37]
Nakada, R. and M. Imaizumi (2020).
Adaptive approximation and generalization of deep neural network with
intrinsic dimensionality.
Journal of Machine Learning Research 21(174), 1–38.

[38]
Newey, W. K. and D. L. Mcfadden (1994).
Large sample estimation and hypothesis testing.
Handbook of Econometrics IV, 2113–2245.

[39]
Precup, D., R. Sutton, and S. Singh (2000).
Eligibility traces for off-policy policy evaluation.
In Proceedings of the 17th International Conference on Machine
Learning, 759–766.

[40]
Smucler, E., A. Rotnitzky, and J. M. Robins (2019).
A unifying approach for doubly-robust $\ell_1$ regularized estimation
of causal contrasts.
arXiv preprint arXiv:1904.03737.

[41]
Tang, Z., Y. Feng, L. Li, D. Zhou, and Q. Liu (2020).
Harnessing infinite-horizon off-policy evaluation: Double robustness
via duality.
ICLR 2020.

[42]
Thomas, P., G. Theocharous, and M. Ghavamzadeh (2015).
High confidence policy improvement.
In F. Bach and D. Blei (Eds.), Proceedings of the 32nd
International Conference on Machine Learning, Volume 37 of Proceedings
of Machine Learning Research, pp.  2380–2388.

[43]
Uehara, M., J. Huang, and N. Jiang (2020).
Minimax weight and q-function learning for off-policy evaluation.
In Proceedings of the 37th International Conference on Machine
Learning, pp.  9659–9668.

[44]
van der Vaart, A. W. (1998).
Asymptotic statistics.
Cambridge, UK: Cambridge University Press.

[45]
Wainwright, M. J. (2019).
High-Dimensional Statistics : A Non-Asymptotic Viewpoint.
New York: Cambridge University Press.

[46]
Wang, R., D. P. Foster, and S. M. Kakade (2020).
What are the statistical limits of offline rl with linear function
arXiv preprint arXiv:2010.11895.

[47]
Wong, R. K. W. and K. C. G. Chan (2018).
Kernel-based covariate functional balancing for observational
Biometrika 105(1), 199–213.

[48]
Xie, T. and N. Jiang (2020).
Q* approximation schemes for batch reinforcement learning: A
theoretical comparison.

[49]
Yang, M., O. Nachum, B. Dai, L. Li, and D. Schuurmans (2020).
Off-policy evaluation via the regularized lagrangian.
arXiv preprint arXiv:2007.03438.

[50]
Yarotsky, D. (2017).
Error bounds for approximations with deep relu networks.
Neural Networks 94, 103–114.

[51]
Yin, M., Y. Bai, and Y.-X. Wang (2020).
Near optimal provable uniform convergence in off-policy evaluation
for reinforcement learning.
arXiv preprint arXiv:2007.03760.

[52]
Yin, M. and Y.-X. Wang (2020).
Asymptotically efficient off-policy evaluation for tabular
reinforcement learning.
In Proceedings of the Twenty Third International Conference on
Artificial Intelligence and Statistics, pp.  3948–3958.

[53]
Zhang, R., B. Dai, L. Li, and D. Schuurmans (2020).
Gendice: Generalized offline estimation of stationary values.
In International Conference on Learning Representations.

[54]
Zhang, R., M. Imaizumi, B. Schölkopf, and K. Muandet (2020).
Maximum moment restriction for instrumental variable regression.
arXiv preprint arXiv:2010.07684.

§ NOTATION

We summarize the notations in <ref>.

$\Scal,\Acal,\Xcal$     State space, action space, $\Scal\times \Acal$

$d_0(\cdot)$     Initial state density

$\gamma$      Discounting factor

$P_{R|S,A}(r|s,a),P_{S'|S,A}(s'|s,a)$     Reward density, transition density

$J(\pi)$     Policy value

$\epol,\bpol$        Evaluation policy, Behavior policy

$d_{\epol,t}$     Distribution of $(s_t,a_t)$ under policy $\epol$

$q_{\epol}(s,a),\,v_{\epol}(s)$     Q-function, value function (for evaluation policy)

$d_{\epol,\gamma}(s,a)$     Discounted occupancy measure

$P_{S,A,R,S'}(s,a,r,s')$     Density for the batch data

$\E[f(s,a,r,s')]$     $\E_{d_{\bpol}}[f(s,a,r,s')]$

$\|f\|_2$     $\E[\{f(s,a,r,s')\}^2]^{1/2}$

$\|f\|_{\infty}$     $\max_{x}|f(x)|$

$w_{\epol}(s,a)$     True weight function $d_{\epol,\gamma}(s,a)/d_{\bpol}(s,a)$

$\eta_{\epol}(s,a)$     $\epol(a|s)/\bpol(a|s)$

$C_W,C_{\eta}$     Constants s.t. $\|w_{\epol}(\cdot)\|_{\infty}\leq C_W,\|\eta(\cdot)\|_{\infty}\leq C_{\eta}$

$\Wbbb,\Qbbb,\Wbbb_1,\Qbbb_1,\Wbbb_2,\Qbbb_2$      Function classes

$V(\Qbbb)$     VC dimension

$C_{\Wbbb},C_{\Qbbb}$      Constant envelopes for the function classes

$C_{\xi}$     Values appearing in the closedness assumptions

$C_{m}$     $\|P_{S'}(\cdot)/P_{S}(\cdot)\|_{\infty}\leq C_m$

$C_{\iota}$     $ \|\hat q-q_{\epol}\|_2\leq C_{\iota}\|\Bcal \hat q-\hat q\|_2$

$\lesssim $     Inequality up to problem dependent values

$\lesssim_{\delta} $     Inequality up to problem dependent values  with probabilitty $1-\delta$

$\mu$     Baseline measure

$\Tcal,\Tcal'$       Transition operator, adjoint operator of the transition operator

$\Bcal,\Bcal'$      Forward Bellman operator, backward Bellman operator

$\Jcal$     $\Jcal q=-q(s,a)+\gamma v(s')$

$\Rcal_n(\Gcal)$     Rademacher complexity of the function class $\Gcal$

$\Rcal_n(\eta,\Gcal)$     Localized Rademacher complexity of the function class $\Gcal$

$\Ncal(\tau,\Gcal,\|\cdot\|_{\infty})$     Covering number of $\Gcal$ wrt $\|\cdot\|_{\infty}$

$\lambda,\lambda'$     Parameters wrt stabilizers

$c_0,\cdots$     Universal constants

$H^{\alpha}(I^d)$     Sobolev ball

$\Lambda^{\alpha}(I^d)$      ball

§ DETAILED LITERATURE REVIEW

We briefly review several batch RL minimax estimators

MIL approach
We have defined the MIL estimators:

\begin{align*}
\ts  \hat J^{\MIL}_{w}&=\ts \E_n[\hat w_{\MIL}(s,a)r],\,\hat J^{\MIL}_{q}=\ts \E_{d_0}[\hat v_{\MIL}(s_0)],\hat v_{\MIL}=\hat q_{\MIL}(s,\epol),\\
\ts \hat J^{\MIL}_{wq}&=\ts \E_n[\hat w_{\MIL}(s,a)\{r-\hat q_{\MIL}(s,a)+\gamma \hat v_{\MIL}(s')\}]+(1-\gamma)\E_{d_0}[\hat v_{\MIL}(s_0)],\\
\ts  \hat w_{\MIL} &=  \ts \argmin_{w \in \Wbbb_1}\max_{q \in \Qbbb_1}\E_n[w(s,a)\{-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{d_0}[v(s_0)]-\lambda \|-q(s,a)+\gamma v(s')\|^2_{2,n},\\
\ts  \hat q_{\MIL}&=  \ts \argmin_{q\in \Qbbb_2}\max_{w \in \Wbbb_2}\E_n[w(s,a)\{r-q(s,a)+\gamma v(s')\}]-\lambda' \|w\|^2_{2,n},
\end{align*}

This form is the unification of many estimators. When $\lambda=0.5$, $\hat q_{\MIL}$ is modified BRM (modified Bellman Residual Minimization) [3, 48]. When $\lambda=0$, $\hat w_{\MIL}$ is MWL in 43. When $\lambda'=0$, $\hat q_{\MIL}$ is MQL in 43.

This unification is different from 49. In their formulation, $\lambda \|\mathcal{J}q\|^2_{2,n}$ is $\lambda \|q(s,a)\|^2_{2,n}.$ In this case, when $\lambda=1$, it is reduced to GenDICE [53]. At the same time, 49 use more general norm rather than $L^2$-norm for stabilizers. We can also extend our analysis to this case.

It is worthwhile to note several related estimators have been proposed n a bandit setting [22, 54, 26, 47, 4, 11].

State-based MIL approach

We focus on the method using action-state value functions and action-state based ratio functions. Instead, 32, 17, 41 proposed the state-based methods:

\begin{align*}
\hat J^{\MIL}_{w,S} &=\E_n[\hat w_{\MIL,S}(s)\eta(s,a)r],\,    \hat J^{\MIL}_{v,S} =\E_{d_0}[\hat v_{\MIL,S}(s)],\\
\hat J^{\MIL}_{wv,S} &=\E_n[\hat w_{\MIL,S}(s)\eta(s,a)\{r-\hat v_{\MIL,S}(s)+\gamma \hat v_{\MIL,S}(s')\}]+(1-\gamma)\E_{d_0}[\hat v_{\MIL,S}(s_0)],\\
\hat w_{\MIL,S}&=\min_{w' \in \Wbbb_{S}}\max_{v' \in \Vbbb}\E_n[w'(s)\eta(s,a)\{-v'(s)+\gamma v'(s')\}]+(1-\gamma)\E_{d_0}[v'(s_0)]-\|-v'(s)+\gamma v'(s')\|^2_{2,n}, \\
\hat v_{\MIL,S}&=\min_{v' \in \Vbbb}\max_{w' \in \Wbbb_{S}}\E_n[w'(s)\eta(s,a)\{r-v'(s)+\gamma v'(s')\}]-\|w'\|^2_{2,n}.
\end{align*}

The estimator $\hat J^{\MIL}_{w,S}$ corresponds to 32, $ \hat J^{\MIL}_{v,S} $ corresponds to offline version of 17, $\hat J^{\MIL}_{wv,S}$ corresponds to 41. We can apply a similar analysis to these estimators as in the main text by some modification.

MDL approach

23, 36 proposed minimax estimators:

\begin{align*}
\ts \hat J^{\MDL}_{w1} &= \ts \min_{w \in \Wbbb}\max_{q \in \Qbbb}\E_n[w(s,a)\{r-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{d_0}[v(s_0)],\\
%J^{\MDL}_{w2} &= \ts \max_{q \in \Qbbb}\min_{w \in \Wbbb}\E_n[w(s,a)\{r-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{d_0}[v(s_0)],\\
\ts \hat J^{\MDL}_{q1} &=\ts \min_{q\in \Qbbb}\max_{w\in \Wbbb}\E_n[w(s,a)\{r-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{d_0}[v(s_0)],
\end{align*}

where $v(s)=q(s,\epol)$. We call these estimators as minimax direct learning (MDL) estimators. This estimator is analyzed in detail in <ref>.

§ ADJOINT TRANSITION OPERATORS

Existence and uniqueness of adjoint transition operator

When the domain space and range space are $L^2(\Xcal)$, where the inner product is defined as $\langle f,g\rangle=\E[fg]$, the operator $\Tcal$ is a bounded operator:

\begin{align*}
\|\Tcal\|=\sup_{u\in L^2(\Xcal)} \|\Tcal u\|_2/\|u\|_2\leq \sqrt{C_mC_{\eta}}.
\end{align*}

Then, the adjoint operator $\Tcal'$ is uniquely defined s.t.

\begin{align*}
\langle f,\Tcal g\rangle=  \langle \Tcal'f, g\rangle,\, \forall f,g\in  L^2(\Xcal).
\end{align*}

In addition,

\begin{align*}
\|\Tcal'\|=\|\Tcal\|\leq \sqrt{C_mC_{\eta}},\,(\Tcal')'=\Tcal.
\end{align*}

\begin{align*}
\|\Tcal u\|^2_2&=\|\E_{s'\sim P_{S'|S,A}(s'|s,a),a'\sim \epol(a'|s')}[u(s',a')]\|^2_2\\
&\leq \E_{s'\sim P_{S'|S,A}(s'|s,a),a'\sim \epol(a'|s'),(s,a)\sim P_{S,A}}[u(s',a')^2] \tag{Jensen}\\
&= \E_{ (s,a)\sim P_{S,A}}\bracks{\frac{P_{S'}(s)\epol(a|s)}{P_S(s)\bpol(a|s)} u(s,a)^2}\leq C_mC_{\eta}\|u\|^2_2.
\end{align*}

The rest of the statement is proved by following standard theory of Hilbert spaces <cit.>.

Specific form

We have

\begin{align*}
\Tcal': f(s,a) \mapsto \eta(s,a)\int \frac{P_{S'|S,A}(s|s',a')f(s',a')P_{S,A}(s',a')}{P_{S}(s)}\rd\mu(s',a').
\end{align*}

When $P_{S}(s)=P_{S'}(s)$,

\begin{align*}
\Tcal': f(s,a) \mapsto \eta(s,a)\int P_{S,A|S'}(s',a'|s)f(s',a')\rd\mu(s',a').
\end{align*}

The first statement is proved by

\begin{align*}\ts
\langle f,\Tcal g\rangle &=\ts \int f(s,a)\{\int g(s',a')\epol(a'|s')P_{S'|S,A}(s'|s,a)\rd\mu(s',a')\}P_{S,A}(s,a)\rd\mu(s,a) \\
&\ts =\int f(s,a)g(s',a')\epol(a'|s')P_{S'|S,A}(s'|s,a)P_{S,A}(s,a)\rd\mu(s,a,s',a')\\
&\ts =\int f(s',a')g(s,a)\epol(a|s)P_{S'|S,A}(s|s',a')P_{S,A}(s',a')\rd\mu(s,a,s',a')\\
&\ts =\int g(s,a)\epol(a|s)P_{S'|S,A}(s|s',a')f(s',a')P_{S,A}(s',a')\rd\mu(s,a,s',a')\\
&\ts =\int g(s,a)\frac{\epol(a|s)P_{S'|S,A}(s|s',a')f(s',a')P_{S,A}(s',a')}{P_{S,A}(s,a)}P_{S,A}(s,a)  \rd\mu(s,a,s',a')\\
&\ts =\int g(s,a)\frac{\epol(a|s)P_{S'|S,A}(s|s',a')f(s',a')p_{S,A}(s',a')}{P_{S}(s)\bpol(a|s)}P_{S,A}(s,a)  \rd\mu(s,a,s',a')\\
&\ts =\int g(s,a)\eta(s,a)\{\int \frac{P_{S'|S,A}(s|s',a')f(s',a')P_{S,A}(s',a')}{P_{S}(s)}\rd\mu(s',a')\}P_{S,A}(s,a)  \rd\mu(s,a)=     \langle \Tcal 'f, g\rangle.
\end{align*}

Here, we use the assumption $P_{S'}(s)\epol(a|s)/P_{S,A}(s,a)\leq C_mC_{\eta}$ for $\forall (s,a)\in \Xcal$ in <ref>.

Next, we use the assumption $P_{S}(s)=P_{S'}(s)$. Then, the second statement is proved by

\begin{align*}
\end{align*}

When we restrict $L^2(\Xcal)$ to more restricted finite dimensional classes, the operators $\Tcal,\Tcal'$ are represented by matrices. We define $a\cdot b=a^{\top}b$.

[Tabular model]
We use a matrix formulation. Let $\Xcal:=S\times A$, and also $\Pcal^\pi$ be an $|\Scal|| \Acal| \times |\Scal|| \Acal|$ matrix, where its $\Pcal^\pi_{s'a',sa} \coloneqq \Pr(s_{t + 1} = s', a_{t + 1} = a' | s_{t} = s, a_{t} = a, a_{t + 1} \sim \pi(\cdot|s_{t + 1}))$. Given a function $f(s,a)$ on $\Xcal$, we represents this $f(s,a)$ as a $|S||A|\times 1$ vector and denote it by $[f]:=(f(x_1),\cdots,f(x_{|S||A|}))^{\top}$.  In a tabular case, the feature vector $\phi(s,a)$ is given as $(I((s,a)=x_1),\cdots, I((s,a)=x_{|S||A|}))^{\top}$. Thus, $f(s,a)=[f]^{\top}\phi$. Note we often take

\begin{align*}
\Qbbb_2 =\Wbbb_2=\Qbbb_1=\Wbbb_1=\{\theta^{\top}\phi;\theta\in \mathbb{R}^{|S||A|}\}.
\end{align*}

Then, we have

\begin{align*}
& [ \Tcal f]=P^{\epol}[f],\,    [\{(\gamma \Tcal-I)f\}]=(\gamma P^{\epol}-I)[f],\\
& \Tcal \phi =(P^{\epol})^{\top}\phi,\,    (\gamma \Tcal-I)\phi=(\gamma P^{\epol}-I)^{\top}\phi.
\end{align*}

In addition, $\E[\phi\phi^{\top}]$ is a diagonal matrix whose $(i,i)$-th entry corresponding $x_i\in \Xcal$, is $\E[I((s,a)=x_i)]$, i.e., $P_{S,A}(x_i)$. This is non-singular when $P_{S,A}(s,a)>0\,\forall (s,a)\in \Xcal$ . Then, $\langle f,g \rangle=\E[fg]$ is

\begin{align*}
\langle f,g\rangle= [f]^{\top}\E[\phi\phi^{\top}][g].
\end{align*}

In addition, from

\begin{align*}
\langle \Tcal f,g \rangle =\{P^{\epol}[f]\}^{\top} \E[\phi\phi^{\top}][g]=[f]^{\top}\{P^{\epol}\}^{\top} \E[\phi\phi^{\top}][g]= [f]^{\top}\E[\phi\phi^{\top}]\{\E[\phi\phi^{\top}]^{-1} \{P^{\epol}\}^{\top}\E[\phi\phi^{\top}]\}[g],
\end{align*}

and $\langle \Tcal f,g \rangle=\langle f,\Tcal'g \rangle$, we have

\begin{align*}
&[\Tcal'f]=( \E[\phi\phi^{\top}]^{-1}(P^{\epol})^{\top} \E[\phi\phi^{\top}])[f],\,
[(\gamma \Tcal'-I)f]=(\E[\phi\phi^{\top}]^{-1}(\gamma P^{\epol}-I)^{\top} \E[\phi\phi^{\top}])[f],\\
& \Tcal'\phi=( \E[\phi\phi^{\top}]^{-1}(P^{\epol})^{\top} \E[\phi\phi^{\top}])^{\top}\phi=\E[\phi\phi^{\top}] P^{\epol}\E[\phi\phi^{\top}]^{-1} \phi.
\end{align*}

[Linear models -ver 1-]
Consider a $d$-dimensional feature vector $\phi$. For $f_1(s,a)=\theta^{\top}_1\phi,f_2(s,a)=\theta^{\top}_2\phi$, the inner product is defined as

\begin{align*}
\langle f_1,f_2 \rangle =\theta^{\top}_1\E[\phi \phi^{\top}]\theta_2.
\end{align*}

Then, suppose that we have a matrix s.t.

\begin{align*}\ts
\Tcal \phi=M^{\top}_{\epol} \phi,\,\Tcal (\theta\cdot \phi)= M_{\epol}\theta \cdot \phi.
\end{align*}

This matrix $M_{\epol}$ is referred to as a matrix mean embedding of the conditional transition operator [14]. In linear MDPs,  $M_{\epol}$ is explicitly calculated. See <ref>. We consider an adjoint operator of this operator. For $f_1(s,a)=\theta^{\top}_1\phi,f_2(s,a)=\theta^{\top}_2\phi$, then,

\begin{align*}
\langle \Tcal f_1,f_2\rangle =(M_{\epol}\theta_1)^{\top}\E[\phi \phi^{\top}]\theta_2=\theta^{\top}_1M_{\epol}^{\top}\E[\phi \phi^{\top}]\theta_2=\theta^{\top}_1\E[\phi \phi^{\top}]\{\E[\phi \phi^{\top}]\}^{-1}M_{\epol}^{\top}\E[\phi \phi^{\top}]\theta_2
\end{align*}

when $\E[\phi \phi^{\top}]$ is non-singular. From  $\langle \Tcal f_1,f_2\rangle=\langle f_1,\Tcal'f_2\rangle$,

\begin{align}\label{eq:linear_ver1}
\Tcal':f_2\to \{\E[\phi \phi^{\top}]\}^{-1}M_{\epol}^{\top}\E[\phi \phi^{\top}]\theta_2\cdot \phi.
\end{align}

\begin{align*}
\Tcal' \phi&=\{\{\E[\phi \phi^{\top}]\}^{-1}M_{\epol}^{\top}\E[\phi \phi^{\top}]\}^{\top}\phi\\
&=\E[\phi \phi^{\top}]M_{\epol}\E[\phi \phi^{\top}]^{-1}\phi\
\end{align*}

[Linear models -ver 2-]
Consider a $d$-dimensional feature vector $\phi$. For $f_1(s,a)=\theta^{\top}_1\phi,f_2(s,a)=\theta^{\top}_2\phi$, the inner product is defined as

\begin{align*}
\langle f_1,f_2 \rangle =\theta^{\top}_1\E[\phi \phi^{\top}]\theta_2.
\end{align*}

Then, suppose that we have a matrix s.t.

\begin{align*}\ts
\Tcal' \phi=M'^{\top}_{\epol} \phi,\, \Tcal' (\theta\cdot \phi)= M'_{\epol}\theta\cdot \phi
\end{align*}

In the case of <ref>,  $M'_{\epol}$ is explicitly calculated. See <ref>. We consider an adjoint operator of this operator. For $f_1(s,a)=\theta^{\top}_1\phi,f_2(s,a)=\theta^{\top}_2\phi$, then,

\begin{align*}
\langle \Tcal' f_1,f_2\rangle =(M'_{\epol}\theta_1)^{\top}\E[\phi \phi^{\top}]\theta_2=\theta^{\top}_1{M'_{\epol}}^{\top}\E[\phi \phi^{\top}]\theta_2=\theta^{\top}_1\E[\phi \phi^{\top}]\{\E[\phi \phi^{\top}]\}^{-1}{M'_{\epol}}^{\top}\E[\phi \phi^{\top}]\theta_2
\end{align*}

when $\E[\phi \phi^{\top}]$ is non-singular. From  $\langle \Tcal' f_1,f_2\rangle=\langle f_1,\Tcal f_2\rangle$,

\begin{align}\label{eq:linear_ver2}
\Tcal:f_2\to \{\E[\phi \phi^{\top}]\}^{-1}{M'_{\epol}}^{\top}\E[\phi \phi^{\top}]\theta_2\cdot \phi.
\end{align}

\begin{align*}
\Tcal \phi&=\{\{\E[\phi \phi^{\top}]\}^{-1}{M'_{\epol}}^{\top}\E[\phi \phi^{\top}]\}^{\top}\phi\\
&= \E[\phi \phi^{\top}]{M'_{\epol}}\E[\phi \phi^{\top}]^{-1}\phi.
\end{align*}

§ THEORETICAL ANALYSIS OF MDL ESTIMATORS

We analyze MDL approaches. First, we give an analogues result as <ref>. In 23, the only one-sided bound is given.

Assume $w_{\epol}\in \Wbbb,q_{\epol}\in \Qbbb$. Letting $ \Gcal(\Wbbb,\Qbbb)=\{(s,a)\mapsto w(s,a)\{-q(s,a)+\gamma q(s',\epol)\}; w\in \Wbbb,q\in \Qbbb\}$, then, with probability $1-\delta$,

\begin{align*}\ts
&|\hat  J^{\MDL}-J|\lesssim \mathrm{Err}_{\MDL},\,\mathrm{Err}_{\MDL}=R_{\max}\Rcal_n(\Wbbb)+\Rcal_n(\Gcal(\Wbbb,\Qbbb))+C_{\Wbbb}(R_{\max}+C_{\Qbbb})\sqrt{\log(c_0/\delta)n^{-1}}.
\end{align*}

where $\hat J^{\MDL}$ is one of $\hat J^{\MDL}_{w1},\hat J^{\MDL}_{q1}$.

Next, we give an analogues result as <ref>.

(1)  Suppose $w_{\epol}\in \Wbbb, C_{\zeta}\Tcal'_{\gamma}(\Wbbb-w_{\epol}) \subset (\Qbbb-q_{\epol})$. Then, with $1-\delta$, $\|\hat w_{\MDL}-\Bcal'\hat w_{\MDL}\|_2\lesssim  \sqrt{C^{-1}_{\zeta}\mathrm{Err}_{\MDL}}$, where $\hat w^{\MDL}$ is the argmin solution in $\hat J^{\MDL}_{w1}$. 2) Suppose  $q_{\epol}\in \Qbbb,\Tcal_{\gamma}(\Qbbb-q_{\epol})\subset(\Wbbb-w_{\epol})$. Then, with $1-\delta$, $\|\hat q_{\MDL}-\Bcal\hat q_{\MDL} \|_2\lesssim   \sqrt{C^{-1}_{\zeta}\mathrm{Err}_{\MDL}}$, where $\hat q^{\MDL}$ is the argmin solution in $\hat J^{\MDL}_{q1}$.

MDL requires more conditions to estimate $w$, $q$-functions than MIL. In fact, $w_{\epol}\in \Wbbb, (\Bcal'-I)\Wbbb \subset (\Qbbb-q_{\epol})$ automatically implies $q_{\epol}\in \Qbbb$. Thus, both $q$-and $w$-are required.

§ THEOREMS AGNOSTIC TO REALIZABILITY AND COMPLETENESS

We present the theorems agnostic to and . These theorems are useful to analyze sieve estimators and neural networks when $\Qbbb$ and $\Wbbb$ grow with $n$.

First, we discuss the extension of <ref>. We only present the result of $\hat J^{\MDL}_{w1}$ and $\hat J^{\MIL}_q,\hat J^{\MIL}_w,\hat J^{\MIL}_{wq}$.

\begin{align*}
|\hat J^{\MDL}_{w1}-J|\leq c_0\mathrm{Err}_{\MDL}+\min_{w\in \Wbbb}\max_{q \in \Qbbb}\E[(w-w_{\epol})\Tcal_{\gamma}(q-q_{\epol})]+\min_{q \in \Qbbb}\max_{w\in \Wbbb}\E[(w-w_{\epol})\Tcal_{\gamma}(q-q_{\epol})].
\end{align*}

When $\lambda=\lambda'=0$,

\begin{align*}
|\hat J^{\MIL}_q-J|&\leq c_0\mathrm{Err}_{\MIL,q}+\min_{w\in \Wbbb_2}\max_{q \in \Qbbb_2}\E[(w-w_{\epol})\Tcal_{\gamma}(q-q_{\epol})]+\min_{q \in \Qbbb_2}\max_{w\in \Wbbb_2}\E[w\Tcal_{\gamma}(q-q_{\epol})],\\
|\hat J^{\MIL}_w-J|&\leq c_0\mathrm{Err}_{\MIL,q}+\min_{w\in \Wbbb_1}\max_{q \in \Qbbb_1}\E[(w-w_{\epol})\Tcal_{\gamma}q]+\min_{q \in \Qbbb_1}\max_{w\in \Wbbb_1}\E[(w-w_{\epol})\Tcal_{\gamma}(q-q_{\epol})],\\
|\hat J^{\MIL}_{wq}-J|&\leq c_0\mathrm{Err}_{\MIL,q}+\min_{w\in \Wbbb_2}\max_{q \in \Qbbb_2,w'\in \Wbbb_1}\E[(w-w'-w_{\epol})\Tcal_{\gamma}(q-q_{\epol})]+\min_{q \in \Qbbb_2}\max_{w\in \Wbbb_2}\E[w\Tcal_{\gamma}(q-q_{\epol})],\\
|\hat J^{\MIL}_{wq}-J|&\leq c_0\mathrm{Err}_{\MIL,q}+\min_{w\in \Wbbb_1}\max_{q \in \Qbbb_1}\E[(w-w_{\epol})\Tcal_{\gamma}q]+\min_{q \in \Qbbb_1}\max_{w\in \Wbbb_1,q\in \Qbbb_2}\E[(w-w_{\epol})\Tcal_{\gamma}(q-q'-q_{\epol})],\\
\end{align*}

In <ref>, the term $ \min_{w\in \Wbbb_2}\max_{q \in \Qbbb_2}\E[(w-w_{\epol})\Tcal_{\gamma}(q-q_{\epol})]$ represents the discrepancy from the assumption $w_{\epol}\in \Wbbb_2$. The term $\min_{q \in \Qbbb_2}\max_{w\in \Wbbb_2}\E[(w-w_{\epol})\Tcal_{\gamma}(q-q_{\epol})]$ represents the discrepancy from the assumption $q_{\epol}\in \Qbbb_2$. A similar observation is made in <ref>.

Next, we present the extension of <ref>. We can similarly extend <ref>.

Let $\eta_n$ be an upper bound on the critical radius of $\Wbbb$ and $\Gcal_q$, where

\begin{align*}
\Gcal_q:=\{(s,a,s')\mapsto  \{-q(s,a)+q_{\epol}(s,a)+\gamma q(s',\epol)-\gamma q_{\epol}(s',\epol)\} w(s,a); q \in \Qbbb_2,w\in \Wbbb_2 \}.
\end{align*}

Assume   $\Wbbb_2$ is symmetric and star-shaped. By defining $\epsilon_n\coloneqq \max_{q \in \Qbbb_2}\min_{w\in \Wbbb_2}\|w-\Tcal_{\gamma}(q-q_{\epol})\|_2$, for any $q_{0}\in \Qbbb_2$, with probability $1-\delta$,

\begin{align*}
\|\Tcal_{\gamma}(\hat q- q_{\epol})\|_2\lesssim  (1+C_1+\lambda+C^2_1/\lambda)  \eta_q+\epsilon_n+\frac{\|\Tcal_{\gamma}(q_{\epol}- q_0)\|^2_2 }{\lambda \eta_q}+\|\Tcal_{\gamma}(q_{\epol}- q_0)\|_2,
\end{align*}

where $\eta_q=\eta_n+c_0\sqrt{\frac{\log(c_1/\delta)}{n}}$ for universal constants $c_0,c_1$.

When $q_0=q_{\epol}$ and $\epsilon_n=0$, this result is reduced to <ref>. In <ref>, $\|\Tcal_{\gamma}(q_{\epol}- q_{0})\|_2$ represents the discrepancy from the condition $q_{\epol}\in \Qbbb_2$. The term $\epsilon_n$ represents the discrepancy from the condition $\Tcal_{\gamma}(\Qbbb_2-q_{\epol})\subset \Wbbb_2$.

§ FAST RATES FOR $L^2$-ERRORS

In the main text, we show how to derive the fast rates in terms of Bellman residual errors. We show how to obtain the fast rates in terms of $L^2$-errors.

Let $\eta_n$ be an upper bound on the critical radius of $\Wbbb_2$ and $\Gcal_q$, where

\begin{align*}
\Gcal_q:=\{(s,a,s')\mapsto \{-q(s,a)+q_{\epol}(s,a)+\gamma q(s',\epol)-\gamma q_{\epol}(s',\epol)\} w(s,a); q \in \Qbbb_2,w\in \Wbbb_2\}.
\end{align*}

Assume $q_{\epol}\in \Qbbb_2,C_{\xi}(\Qbbb_2-q_{\epol})\subset \Tcal'_{\gamma}\Wbbb_2,\sup_{w\in \Wbbb_2}\|w\|/\|\Tcal'_{\gamma}w\|\leq C_{\iota}$, $\Wbbb_2$ is symmetric and star-shaped.  Then, with probability $1-\delta$,

\begin{align*}\ts
&\| \hat q_{\MIL}-q_{\epol} \|_2\lesssim  (1+C_1+C_1^2/\lambda'+C_{\Wbbb_2}(1+\gamma \sqrt{C_mC_{\eta}})+1/C_{\xi}+\lambda'\{1+C^2_{\iota}\} )\eta_{q}\,\\
C_1 &= C_{\Qbbb_2}+ (1-\gamma)^{-1}R_{\max},
\end{align*}

where $\eta_{q}=\eta_n+c_0\sqrt{\frac{\log(c_1/\delta)}{n}}$ for universal constants $c_0,c_1$.

Let $\eta_n$ be an upper bound on the critical radius of $ \Gcal_{w1},  \Gcal_{w2}$, where

\begin{align*}
\Gcal_{w1}:&=\{(s,a,s')\mapsto  \{q(s,a)-\gamma q(s',\epol)\}; q\in \Qbbb_1 \}, \\
\Gcal_{w2}:&=\{(s,a,s')\mapsto \{ w(s,a)-w_{\epol}(s,a)\}\{-q(s,a)+\gamma q(s',\epol)\} ; w\in \Wbbb_1,q\in \Qbbb_1 \}.
\end{align*}

Suppose  $w_{\epol} \in \Wbbb_1$, $C_{\xi}(\Wbbb_1-w_{\epol}) \subset \Tcal_{\gamma}\Qbbb_1,\,\sup_{q\in \Qbbb_1}\|q\|/\|\Tcal_{\gamma}q\|\leq C_{\iota}$, $\Qbbb_1$ is symmetric and star-shaped. Then, with probability $1-\delta$,

\begin{align*}
\|\hat w_{\MIL}-w_{\epol}\|_2\lesssim \braces{1+C^2_{\Wbbb_1}/\lambda+C_{\Wbbb_1}+C_{\Qbbb_1}+1/ C_{\xi}+\lambda\{1+C^2_{\iota}(1+C_mC_{\eta})\}}\eta_w
\end{align*}

where $\eta_w=\eta_n+c_0\sqrt{\frac{\log(c_1/\delta)}{n}}$ for universal constants $c_0,c_1$.

§ CALCULATION OF ERRORS BOUNDS FOR EACH MODEL

§.§ Section <ref> -under w-, and w--

We analyze the main error terms in MDL and MIL. We assume $\Wbbb_2=\Qbbb_2=\Wbbb_1=\Wbbb_2$ for simplicity. We consider a joint hypothesis set and investigate its covering number:

\begin{align*}
\Gcal(\Wbbb,\Qbbb) \ts &= \ts \{(s,a,s')\mapsto w(s,a)\{-q(s,a)+\gamma  q(s',\epol)\}; w\in \Wbbb,q\in \Qbbb \}.
\end{align*}

When we assume the assumptions in <ref> in this section, the error term $|\hat J^{\MIL}-J|$ is essentially upper-bounded by

\begin{align*}
\ts    R_{\max}\Rcal_n(\Wbbb)+\Rcal_n( \Gcal(\Wbbb,\Qbbb)),
\end{align*}

where $\hat J^{\MIL}$ is one of $\hat J^{\MIL}_w,\hat J^{\MIL}_q,\hat J^{\MIL}_{wq}$. The first term is upper-bounded following the usual argument in learning theory [45]. The careful analysis is required to analyze the second term. We often use the following lemma.

\begin{align*}
&\log \bN(\tau, \Gcal(\Wbbb,\Qbbb), \|\cdot\|_\infty) \\
&\leq \log \bN(0.5\tau/((1+\gamma) C_\Qbbb), \Wbbb, \|\cdot\|_\infty) + \log \bN(0.5\tau/(C_\Wbbb (1+\gamma)), \Qbbb, \|\cdot\|_\infty).
\end{align*}

[VC classes]
We consider VC classes <cit.>. Let $V(\Wbbb),V(\Qbbb)$ be the VC dimension of the set of subgraphs of functions in $\Wbbb,\Qbbb$. For example, letting $\theta_w$ be a $d$-dimensional weight vector and $\phi_w(s,a)$ be $\mathbb{R}^{d}$-valued map, when the model is a linear model $\Wbbb=\{\theta^{\top}_w\phi_w(s,a);\theta \in \Rl^d\}$, the VC dimension is $d+1$ <cit.>.

Assume the condition in <ref>.
Let $ O(\cdot)$ be the order w.r.t $n,V(\Wbbb),V(\Qbbb)$.  Then, with probability $1-\delta$,

\begin{align*}
% \ts |\hat J^{\MIL}-J|=O(\log n\sqrt{\max(V(\Wbbb),V(\Qbbb) )/n}).
\ts |\hat J^{\MIL}-J|=O(\sqrt{\max(V(\Wbbb),V(\Qbbb) )/n}).
\end{align*}

[Nonparametric models]
We consider nonparametic models such as  balls and Sobolev balls. Refer to  45 regarding the covering number of these models. For instance, the covering number of  ball with an order $p$ and a dimension $d$ regarding $L^{\infty}$-norm is $\exp((1/\tau)^{d/p})$. Similarly, the covering number of Sobolev ball with an order $p$ and a dimension $d$ regarding $L^{\infty}$-norm is $\exp((1/\tau)^{d/p})$. Then, the error term is calculated as follows. Here, $O(\cdot)$ is an order w.r.t $n$.

Assume the condition in <ref>.
Assume $\log \Ncal(\tau,\Wbbb,\|\cdot\|_{\infty})=O((1/\tau)^{\beta_1}),\log \Ncal(\tau,\Qbbb,\|\cdot\|_{\infty})=O((1/\tau)^{\beta_2})$. Define $\beta=\max(\beta_1,\beta_2)$, we have with probability $1-\delta$,

\begin{align*}
|\hat J^{\MIL}-J|= \begin{cases}
&O(n^{-1/2}),\quad \beta<2 \\
&\tilde O(n^{-1/2}),\quad \beta=2 \\
&O(n^{-1/\beta}),\quad \beta>2.
\end{cases}
\end{align*}

The error is decided by the worst $\tau$-entropy of two function classes. Thus, if one function class is at least non-Donsker  $(\beta\geq 2)$, we can't ensure that the final error rate is $O(n^{-1/2})$.

[Linear Sieves] Infinite dimensional optimization is often difficult. Instead, we often use the tensor product of linear sieve spaces $\Qbbb,\Wbbb$, which are constructed as a tensor product of commonly used univariate linear approximating sieves like polynomials, trigonometric polynomial, splines or orthogonal wavelets <cit.>. Note $\Qbbb,\Wbbb$ depend on $n$. For example, polynomials are

\begin{align*}
\mathrm{Pol}(k_n)=\{\sum_{k=0}^{k_n}a_k x^k,x\in [0,1]:a_k\in \mathbb{R}\}.
\end{align*}

Let $\dim(\Qbbb)=\dim(\Wbbb)=k_n.$
Assume $\Qbbb,\Wbbb$ satisfy

\begin{align}
&\forall f\in \Lambda^p_c([0,1]^d),\exists g\in \Qbbb,\mathrm{s.t.} \|f-g\|_{\infty}= O(k^{-p/d}_n), \label{eq:sieve}\\
& \forall f\in \Lambda^p_c([0,1]^d),\exists g\in \Wbbb,\mathrm{s.t.}\,\|f-g\|_{\infty}=O(k^{-p/d}_n), \label{eq:sieve2}
\end{align}

where $ \Lambda^p_c([0,1]^d)$ is a  ball with an order $p$, a dimension $d$ and the norm $c$. This is in fact satisfied by the above sieve estimators. Refer to <cit.>.

For the analysis, we redefine $\Wbbb$ as $\min\{\Wbbb,C_w\}$. Similarly, we redefine $\Qbbb$ as $\min\{\Qbbb,(1-\gamma)^{-1}R_{\max}\}$. Then, we have the following result. Here, $O(\cdot)$ only focus on the term regarding $n$.

Suppose (<ref>),(<ref>). Assume $w_{\epol},q_{\epol}\in \Lambda^p_c([0,1]^d)$. Then, with probability $1-\delta$, $|\hat J^{\MIL}-J|\leq \tilde O(n^{-\frac{p}{2p+d}})$.

This rate is worse comparing to the rate when we directly optimize over $\Lambda^p_c([0,1]^d)$. Recall, in this case, the rate is $\max(1/2,n^{-p/d})$.

[Neural Networks]
We consider using neutral networks with an ReLU activation function. The covering number of these neural networks is calculated as follows.

Let $\Fcal_{NN}$ be a set of functions by a neural network with $L$ layers, $\Omega$ weights in $[-B,B]$, and $1-$Lipschitz continuous activation function
Then, for $\tau \in (0,1]$, we have

\begin{align*}
\log \Ncal(\tau, \Fcal_{NN}, \|\cdot\|_\infty) \leq \Omega \log \left( \frac{ 2LB^L (\Omega+1)^L}{\tau} \right).
\end{align*}

Besides, it is known that these  neural networks approximate the Sobolev ball.

Suppose $q_0$ belongs to the Sobolev ball with an order $\alpha$ with its input is $d$-dimensional.
Then, there exists the neural network with a ReLU activation function, which has at most $L=O(\log \Omega)$ layers and $\Omega$ parameters s.t.

\begin{align*}
\|q^* - q_0\|_\infty =\tilde{O}( \Omega^{-\alpha/ d}).
\end{align*}

We consider the case using neural networks. Neural networks grow with the sample size, and approximate some function spaces [50, 37]. In this work, we consider neutral networks with a ReLU activation function, which approximate a $d$-dimensional Sobolev ball $H^{\alpha}_K([0,1]^d)$ with an order $\alpha$ and the norm $K$. Since the function class grows with $n$, it is not suitable to directly assume $w$, $q$-on $\Wbbb,\Qbbb$. Instead, by assuming $w_{\epol},q_{\epol}\in H^{\alpha}_K([0,1]^d)$, we have the following theorem. Here, $O(\cdot)$ is an order w.r.t $n$.

Letting $\Fcal_{NN}$ be a set of functions by deep neural networks with a ReLU activation function, $L$ layers, and $\Omega$ parameters, suppose $\Wbbb=\Fcal_{NN},\Qbbb=\Fcal_{NN}$ and $w_{\epol},q_{\epol}\in H^{\alpha}_K([0,1]^d)$. Then, with probability $1-\delta$, $|\hat J^{\MIL}-J|= \tilde O(n^{-\frac{\alpha}{2\alpha+d}})$ by taking $L=O(\log n),\Omega=O(n^{d/(2\alpha+d)})$.

This result is derived by an extension of <ref>, which is agnostic to . Refer to <ref>.

For an overparameterization case, that is, there are numerous parameters in the neural network, we apply a different strategy to bound the error.
Instead of the huge number of parameters, we assume that the sum of their values are bounded, that is, we introduce an upper bound of a norm of the parameter matrix. The approximation error is guaranteed to be small enough by the large number of parameters. For the analysis, we apply the following seminal lemma by [20]. For a matrix $A$, let $\|A\|_F:= \sqrt{\sum_{i,j} A_{i,j}^2}$ be its Frobenius norm.

Let $\mathcal{F}_{NN}$ be a set of functions by a neural network with $L$ layers and activation function which is $1$-Lipschitz continuous and positive-homogeneous, that is, $\sigma(az) = a \sigma(z)$ holds with $a > 0$.
Further, let $A_\ell$ be a weight matrix of an $\ell$-th layers for $\ell = 1,...,L$ and assume that $\|A_\ell\|_{F} \leq M_F(\ell)$ with a bound $M_F(\ell)$.
Then, we have $\mathcal{R}_n(\mathcal{F}_{NN}) \leq \max_x\|x\|_2 (2\sqrt{\log L} + 1) \prod_{\ell=1}^L M_F(\ell)/\sqrt{n}$.

We obtain the following result by the universal approximation property of neural networks and the parameter norm bound.

Let $\mathcal{F}_{NN}$ be a set of functions by a neural network with $L$ layers and the ReLU activation function.
Suppose that $\Wbbb=\Fcal_{NN},\Qbbb=\Fcal_{NN}$, and for any $\varepsilon > 0$, there exists $w_0 \in \Wbbb, q_0 \in \Qbbb$ such that $\max \{\|w_{\epol} - w_0\|_\infty,\|q_{\epol} - q_0\|_\infty\} \leq \varepsilon$ holds.
Further, suppose there exists $M_F(\ell) \geq  0, \ell = 1,...,L$ such that $\|A_\ell\|_{F} \leq M_F(\ell)$ holds where $A_\ell$ be a weight matrix of an $\ell$-th layers.
Then, with probability $1-\delta$, $|\hat J^{\MIL}-J|= \tilde O(\varepsilon +  \sqrt{\log L} \prod_{\ell=1}^L M_F(\ell)/\sqrt{n})$.

§.§ <ref>: Calculation of Critical Radius

Recall that

\begin{align*}
\Gcal_q:=\{(s,a,s')\mapsto \{-q(s,a)+q_{\epol}(s,a)+\gamma q(s',\epol)-\gamma q_{\epol}(s',\epol)\}w(s,a); q \in \Qbbb_2, w\in \Wbbb_2 \}.
\end{align*}

We calculate the convergence rate of $\hat q^{\MIL}$. The convergence rate of $\hat w^{\MIL}$ is similarly calculated.

[VC classes]
We consider VC classes. Let $V(\Wbbb_2),V(\Qbbb_2)$ be the VC dimension of the sets of subgraphs of functions in $\Wbbb_2,\Qbbb_2$.

Suppose the assumptions in <ref>. Let $\tilde O(\cdot)$ be the order w.r.t $V(\Wbbb_2),V(\Qbbb_2),n$. Then,

$$ \|\Bcal \hat q^{\MIL}-\hat q^{\MIL}\|_2=\tilde O(\sqrt{\max(V(\Wbbb_2),V(\Qbbb_2) )/n}).$$

[Nonparametric models]
As in <ref>, let us consider nonparmetric models.

Suppose the assumptions in <ref>. Assume $\log\Ncal(\tau,\Wbbb_2,\|\cdot\|_{\infty})=(1/\tau)^{\beta_1},\\ \log\Ncal(\tau,\Qbbb_2,\|\cdot\|_{\infty})=(1/\tau)^{\beta_2}$. Then, letting $\tilde O(\cdot)$ be the order wrt $n$, by defining $\beta=\max(\beta_1,\beta_2)$,

\begin{align*}
\|\Bcal \hat q^{\MIL}-\hat q^{\MIL}\|_2=\begin{cases}
O(n^{-1/(2+\beta_1)})\quad \beta<2, \\
O(n^{-1/4})\quad \beta=2,\\
O(n^{-1/(2\beta_1)})\quad  \beta>2.
\end{cases}.
\end{align*}

Note the rate when $\beta<2$ is known as a minimax optimal rate in a bandit setting <cit.>.
When $\max(\beta_1,\beta_2)\geq 2$, it is not. This is because the Dudley integral is calculated for the global function class due to the limited information in <ref>.
The rate $\beta>2$ is typically improved by more careful analysis depending on the function classes as in the next example.

[Linear Sieves]

We consider the linear sieves $\Wbbb,\Qbbb$.

Assume  $q_{\epol}\in \Lambda^p_c([0,1]^d),P_{S'|S,A}(s'|\cdot)\in \Lambda^p_K([0,1]^d),$

\begin{align*}
& \forall f\in \Lambda^p_{c}([0,1]^d),\exists g\in \Qbbb_2,\|f-g\|_{\infty} =O(k^{-p/d}_n),\\
&\forall f\in \Lambda^p_{2\gamma KC_{\Qbbb}}([0,1]^d),\exists g\in \Wbbb'_2,\|f-g\|_{\infty}=O(k^{-p/d}_n),\\
&2\Qbbb_2+\Wbbb'_2\subset \Wbbb_2.
\end{align*}

Then, $\|\Bcal \hat q^{\MIL}-\hat q^{\MIL}\|_2=\tilde O(n^{-p/(2p+d)})$, where $\tilde O(\cdot)$ is the order wrt $n$.

Since $\Qbbb_2,\Wbbb_2$ grow with $n$, we impose and on the  balls rather than $\Qbbb_2,\Wbbb_2$ itself. Here, $P_{S'|S,A}(s'|\cdot)\in \Lambda^p_K([0,1]^d)$ is a condition to ensure of the  balls. Then, the above result is derived by the extension of <ref> in <ref>, which is agnostic to and , i.e, $q_{\epol}\in \Qbbb_2,\Tcal_{\gamma}(\Qbbb_2-q_{\epol})\in \Wbbb_2$.

[Neural Networks]

As in <ref>, we consider using neural networks with the ReLU activation function. The notation $O(\cdot)$ is the order w.r.t $n$

Let $\Qbbb_2$ be a set of functions by deep neural networks with the ReLU activation function, $L$ layers, and $\Omega$ parameters.  Also, let $\Wbbb'_2$ be a neural network with the same architecture of $\Qbbb_2$ and define $\Wbbb_2$ be with $L+1$ layers and $3\Omega + O(1)$ parameters, specifically, $\Wbbb_2 := \{w_1 + w_2 + w_3 : w_i \in \Wbbb'_2, i=1,2,3\}$.

Also, suppose $q_{\pi^e} \in H_K^\alpha([0,1]^d)$ and  $P_{S'|S,A}(s'|\cdot)\in H_K^\alpha([0,1]^d)$.
Then, we have
$$\|\Bcal \hat q^{\MIL}-\hat q^{\MIL}\|_2 =  \tilde{O}(n^{-\alpha/(2\alpha + d)})$$
by taking $L=O(\log n),\Omega=O(n^{d/(2\alpha+d)})$.

Since $\Qbbb_2,\Wbbb_2$ grow with $n$, we impose and on the Sobolev ball. Here, $P_{S'|S,A}(s'|\cdot)\in H_K^\alpha([0,1]^d)$ is a condition to ensure of the Sobolev balls. Then, the above result is derived by the extension of <ref> in <ref>, which is agnostic to and , i.e, $q_{\epol}\in \Qbbb_2,\Tcal_{\gamma}(\Qbbb_2-q_{\epol})\in \Wbbb_2$.

§ SAMPLE SPLITTING

We explain the sample-splitting procedure. This technique is traditionally used to analyze the plug-in type estimators such as the functional of nonparametric estimators [29, 44]. Recently, it has also been used a lot in the context of causal inference [10, 18]. In an RL context, 28 apply this technique to OPE. By sample splitting, we can easily analyze the terms called stochastic equicontinutiy terms.

Let be $\phi(s,a,r,s';w,q)\coloneqq w(s,a)\{r-q(s,a)+\gamma q(s',\epol)\}+\E_{d_0}[q(s_0,\epol)]$.

* Split the whole sample into half as $\Dcal_0$, $\Dcal_1$.

* Construct estimators $\hat w^{\MIL}_0,\hat q^{\MIL}_0$ using $\Dcal_0$, and define $\hat J_0=\frac{2}{n}\sum_{i\in \Dcal_1}\phi(s^i,a^i,r^i,s'^i;\hat w^{\MIL}_0,\hat q^{\MIL}_0)$.

* Construct estimators $\hat w^{\MIL}_1,\hat q^{\MIL}_1$ using $\Dcal_1$, and define $\hat J_1=\frac{2}{n}\sum_{i\in \Dcal_0}\phi(s^i,a^i,r^i,s'^i;\hat w^{\MIL}_1,\hat q^{\MIL}_1)$.

* Redefine $\hat J_{wq}=0.5(\hat J_0+\hat J_1)$.

§ COMPLETE ANALYSIS OF FQI FOR POLICY EVALUATION

The FQI has been analyzed in detail [34, 8] for policy optimization.
For policy evaluation, 31 analyze FQI in detail when the hypothesis classes are VC-classes. For the sake of completeness, we show the analysis when using general function classes. To make the analysis easier, we consider the sample splitting version of FQI:

* Set the number of iterations $T$, and split the whole $n$ sample into $T$ bins. We denote the $t$ th bin by $\zeta_t (t\in [1,\cdots,T])$.

* At the initial stage $t=0$, take some function $f_0$.

* Repeat the following from $t=1,\cdots,T$

\begin{align*}
f_t=\argmin_{q\in \Qbbb}\sum_{j\in \zeta_t}\{f_{t-1}(s'^j,\epol)+r^j-q(s^j,a^j)\}^2.
\end{align*}

* Define the estimator $\E_{d_0}[f_T(s_0,\epol)]$.

We set the critical radius of $\mathrm{star}(\Qbbb-q_{\epol})$ as $\eta_t$ at $t$-th stage, i.e., a solution to

\begin{align*}
\Rcal_{\zeta_t}(\eta;\Qbbb)\leq \eta^2/C_{\Qbbb}.
\end{align*}

where $\Rcal_{\zeta_t}(\eta;\Qbbb)$ is an empirical localized Rademacher complexity of $\Qbbb$ based on the data $\zeta_t$. Suppose $q_{\epol}\in \Qbbb,\Bcal\Qbbb\subset\Qbbb$. With probability $1-\delta$,

\begin{align*}
|\E_{s\sim d_0}[f_T(s, \epol)] - J| \lesssim \frac{(1 - \gamma^{T/2})}{\sqrt{1 - \gamma}}\|w_{\epol}\|_2 C_{\Qbbb}\eta_q + \gamma^{{T}/{2}}C_{\Qbbb},
\end{align*}

where $\eta_q=\max_{t\in [1,\cdots,T]}(\eta_{t}+\sqrt{c_0\log(c_1T/\delta)/n_t})$ for some universal constants $c_0,c_1$.

We directly combine the two lemmas, <ref>.

The critical radius $\eta_q$ is similarly calculated as in <ref>. For example, when $\Qbbb$ belongs to VC classes, and the VC dimension is $V(\Qbbb)$,  then,

\begin{align*}
\eta_q=O(\max_{t\in [1,\cdots,T]}(\sqrt{V(\Qbbb)/n_t}+\sqrt{c_0\log(c_1T/\delta)/n_t} )).
\end{align*}

The above theorem concludes that the error of FQI is roughly $\eta_q$ when we only focus on the sample size. This result is equivalent to the analysis of $\hat J^{\MIL}_q$ with stabilizers as in <ref>. Note that the dependence of $\|w_{\epol}\|_2$ is the same.

We set the critical radius of $\mathrm{star}(\Qbbb-q_{\epol})$ as $\eta_t$ at $t$-th stage, i.e., a solution to

\begin{align*}
\Rcal_{\zeta_t}(\eta;\Qbbb)\leq \eta^2/C_{\Qbbb}.
\end{align*}

Suppose $\Bcal \Qbbb\subset \Qbbb$. Then, with probability $1-\delta$, $\|f_t - \Bcal f_{t - 1}\|_{2} \lesssim C_{\Qbbb}\eta$
where $\eta=\eta_t+\sqrt{c_0\log(c_1/\delta)/n_t}$ for some universal constants $c_0,c_1$.

If we have $\|f_t - \Bcal f_{t - 1}\|_{2} \leq \varepsilon$  for any $T\geq t \geq 1$, then

\begin{align*}
|\E_{s\sim d_0}[(1-\gamma)f_T(s, \epol)] - J]| \leq \frac{\{1 - \gamma^{T/2}\}(1+\gamma^{1/2})}{\sqrt{1-\gamma}} \|w_{\epol}\|_2 \varepsilon + 2\gamma^{{T}/{2}}(1-\gamma)C_{\Qbbb}.
\end{align*}

§ PROOFS

\begin{align*}
&\E[w(s,a)(r-q(s,a)+\gamma q(s',\epol))+(1-\gamma)\E_{d_0}[q(s_0,\epol)]]\\
&=\E[\{ w(s,a)-w_{\epol}(s,a)\}\{-q(s,a)+q_{\epol}(s,a)+\gamma v(s')-\gamma v_{\epol}(s)\}]+J(\epol).
\end{align*}

\begin{align*}
&\E[w(s,a)\{r-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{d_0}[v(s_0)]-J(\epol)+J(\epol)\\
&=\E[w(s,a)\{r-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{d_0}[v(s_0)] \\
&-\{\E[w_{\epol}(s,a)\{r-q(s,a)+\gamma v(s')\}]+(1-\gamma)\E_{d_0}[v(s_0)]\}+J(\epol)\\
&=\E[w(s,a)\{r-q(s,a)+\gamma v(s')\}]-\E[w_{\epol}(s,a)\{r-q(s,a)+\gamma v(s')\}]+J(\epol)\\
&=\E[\{w(s,a)-w_{\epol}(s,a)\}\{-q(s,a)+q_{\epol}(s,a)+\gamma v(s')-\gamma v_{\epol}(s')\}]+J(\epol).
\end{align*}

§.§ Proof of  <ref>

First Statement $(\Bcal-I)q=\Tcal_{\gamma}(q-q_{\epol})$

\begin{align*}
(\Bcal-I)q&=\E_{P_{S'|S,A}(s'|s,a),P_{R|S,A}(r|s,a)}[r+\gamma q(s',\epol)-q(s,a)]\\
&=\E_{P_{S'|S,A}(s'|s,a)}[\gamma q(s',\epol)-\gamma q_{\epol}(s',\epol)-q(s,a)+q_{\epol}(s,a)]\\
&=(\gamma \Tcal-I)(q-q_{\epol})=\Tcal_{\gamma}(q-q_{\epol}).
\end{align*}

Second Statement $\Bcal q_{\epol}=q_{\epol}$
This is proved by

\begin{align*}
\Bcal q_{\epol}=\Tcal_{\gamma}(q_{\epol}-q_{\epol})+q_{\epol}=q_{\epol}.
\end{align*}

Third Statement $(\Bcal'-I)w=\Tcal'_{\gamma}(w-w_{\epol})$

We check

\begin{align*}\ts
-\frac{(1-\gamma)d_{0}(s)\epol(a|s)}{P_{S,A}(s,a)}=(\gamma \Tcal'-I)w_{\epol}.
\end{align*}

This is proved as

\begin{align*}
\ts (\gamma \Tcal'-I)\frac{d_{\epol,\gamma}(s,a)}{P_{S,A}(s,a)}&= \ts \gamma \eta_{\epol}(s,a)\int \frac{P_{S'|S,A}(s|s',a')d_{\epol,\gamma}(s',a')}{P_{S}(s)}\rd\mu(s',a')  -\frac{d_{\epol,\gamma}(s,a)}{P_{S,A}(s,a)} \\
&= \ts \gamma \epol(a|s)\int \frac{P_{S'|S,A}(s|s',a')d_{\epol,\gamma}(s',a')}{P_{S,A}(s,a)}\rd\mu(s',a')  -\frac{d_{\epol,\gamma}(s,a)}{P_{S,A}(s,a)} \\
&=\ts -\frac{(1-\gamma)d_{0}(s)\epol(a|s)}{P_{S,A}(s,a)}.
\end{align*}

We use Lemma 11 [43]:

\begin{align*}
\gamma \epol(a|s)\int P_{S'|S,A}(s|s',a')d_{\epol,\gamma}(s',a')\rd\mu(s',a')-d_{\epol,\gamma}(s,a)=-(1-\gamma)d_{0}(s)\epol(a|s).
\end{align*}

Thus, We have

\begin{align*}
(\Bcal'-I)w&=\gamma \Tcal' w+\frac{(1-\gamma)d_{0}(s)\epol(a|s)}{P_{S,A}(s,a)}-w\\
&=(\gamma \Tcal'-I)(w-w_{\epol})=\Tcal'_{\gamma}(w-w_{\epol}).
\end{align*}

Fourth Statement $\Bcal' w_{\epol}=w_{\epol}$
This is proved by

Proof for $J^{\MIL}_w$

Estimators for the weight functions in MIL are defined as

\begin{align*}
&\hat w=\argmin_{w\in\Wbbb_1}\max_{q\in \Qbbb_1}|\E_n[f_{\MIL_1}(s,a,r,s';w,q)]|,\\
& f_{\MIL_1}(s,a,r,s';w,q)=w(s,a)\{q(s,a)-\gamma q(s',\epol)\}-(1-\gamma)\E_{d_0}[q(s_0,\epol)].
\end{align*}

We write this solution to the above minimax optimization as $(\hat w,\hat q)$. Thus,

\begin{align*}
\hat q \coloneqq\argmax_{q\in \Qbbb_1}|\E_n[f_{\MIL_1}(s,a,r,s';\hat w,q)]|.
\end{align*}

We define $J^{\MIL}_w=\E[\hat w(s,a)r]$. Then, we have

\begin{align*}
|J^{\MIL}_w-J |\leq  \max_{q\in \Qbbb_1}|\E[\{\hat w-w_{\epol})\}\Tcal_{\gamma} q]|+\min_{q \in \Qbbb_1}|\E[\{\hat w-w_{\epol})\}\{\Tcal_{\gamma}(q-q_{\epol})\}]|.
\end{align*}

The following is the proof. We have for any $q\in \Qbbb_1$:

\begin{align*}
&|J^{\MIL}_w-J |=\E[\hat w(s,a)r]-J| \\
&=|\E[\hat w(s,a)r]-\E[\hat w(s,a)\{r-q_{\epol}(s,a)+\gamma v_{\epol}(s')\}]-(1-\gamma)\E_{d_0}[v_{\epol}(s_0)]| \\
&=|\E[\hat w(s,a)\{q_{\epol}(s,a)-\gamma v_{\epol}(s')\}]-(1-\gamma)\E_{d_0}[q_{\epol}(s_0,\epol)]| \\
&=|\E[\hat w(s,a)\{q(s,a)-\gamma v(s')\}]-(1-\gamma)\E_{d_0}[v(s_0)]| \\
&+|\E[\hat w(s,a)\{-q(s,a)+q_{\epol}(s,a)+\gamma v(s')-\gamma v_{\epol}(s')\}]-(1-\gamma)\E_{d_0}[q_{\epol}(s_0,\epol)-v(s_0)]| \\
&=|\E[\hat w(s,a)\{q(s,a)-\gamma v(s')\}]-(1-\gamma)\E_{d_0}[v(s_0)]|| \\
&+|\E[\{\hat w(s,a)-w_{\epol}(s,a)\}\{-q(s,a)+q_{\epol}(s,a)+\gamma v(s')-\gamma v_{\epol}(s')\}]|.
\end{align*}

Then, we have

\begin{align}
|J^{\MIL}_w-J |&\leq  \max_{q\in \Qbbb_1}|\E[\hat w(s,a)\{q(s,a)-\gamma v(s')\}]-(1-\gamma)\E_{d_0}[v(s_0)]| \nonumber \\
&+\min_{q\in \Qbbb_1}|\E[\{\hat w(s,a)-w_{\epol}(s,a)\}\{-q(s,a)+q_{\epol}(s,a)+\gamma v(s')-\gamma v_{\epol}(s')\}]|\nonumber \\
&\leq \max_{q\in \Qbbb_1}|\E[\{\hat w-w_{\epol}\}\Tcal_{\gamma} q]|+\min_{q \in \Qbbb_1}|\E[\{\hat w-w_{\epol}\}\{\Tcal_{\gamma}(q-q_{\epol})\}]|.  \label{eq:wqreal}
\end{align}

Here, we use $\E[w_{\epol}(s,a)\{q(s,a)-\gamma v(s')\}]-(1-\gamma)\E_{d_0}[v(s_0)]=0$ from 43.
Recall we have

\begin{align*}
\E[f_{\MIL_1}(w,q)]=\E[-(w-w_{\epol})\Tcal_{\gamma}q].
\end{align*}

Then, using $w_{\epol}\in \Wbbb_1,q_{\epol}\in \Qbbb_1$, from <ref>,

\begin{align*}
|J^{\MIL}_w-J| \leq  \max_{q\in \Qbbb_1}|\E[(\hat{w}-w_{\epol})\Tcal_{\gamma}q]|=  |\E[(\hat{w}-w_{\epol})\Tcal_{\gamma}\tilde q]|,
\end{align*}

\begin{align*}
\tilde  q= \argmax_{q\in \Qbbb_1}|\E[(\hat{w}-w_{\epol})\Tcal_{\gamma}q]|.
\end{align*}

As a first step, we bound  $|\E[(\hat w-w_{\epol})\Tcal_{\gamma}\hat q] |$:

\begin{align*}
&|\E[(\hat w-w_{\epol})\hat \Tcal_{\gamma}q]|=|\E[f_{\MIL_1}(\hat w,\hat q)]|=|\E[f_{\MIL_1}(\hat w,\hat q)]|-|\E[f_{\MIL_1}(w_{\epol},\hat q)]|\\
&=|\E[f_{\MIL_1}(\hat w,\hat q)]|-|\E_n[f_{\MIL_1}(\hat w,\hat q)]|+|\E_n[f_{\MIL_1}(\hat w,\hat q)]|-|\E_n[f_{\MIL_1}(w_{\epol},\hat q)]|\\
& \quad +|\E_n[f_{\MIL_1}(w_{\epol},\hat q)]|-|\E[f_{\MIL_1}(w_{\epol},\hat q)]|\\
&\leq |\E[f_{\MIL_1}(\hat w,\hat q)]|-|\E_n[f_{\MIL_1}(\hat w,\hat q)]|+|\E_n[f_{\MIL_1}(w_{\epol},\hat q)]|-|\E[f_{\MIL_1}(w_{\epol},\hat q)]|\\
&\leq 2\sup_{w\in \Wbbb_1,q\in \Qbbb_1}|(\E-\E_n)[ f_{\MIL_1}(w,q)]|.
\end{align*}

Here, we use $|\E_n[f_{\MIL_1}(\hat w,\hat q)]|\leq  |\E_n[f_{\MIL_1}(w_{\epol},\hat q)]|$ and $|\E[f_{\MIL_1}(w_{\epol},\hat q)]|=0$.

Second, we calculate the difference of $|\E[(\hat w-w_{\epol})\Tcal_{\gamma}\hat q] |$ and $|\E[(\hat w-w_{\epol})\Tcal_{\gamma}\tilde q] |$.

\begin{align*}
&|\E[(\hat w-w_{\epol})\Tcal_{\gamma}\tilde q] |-|\E[(\hat w-w_{\epol})\Tcal_{\gamma}\hat q] |= |\E[f_{\MIL_1}(\hat w,\tilde q)]|-|\E[f_{\MIL_1}(\hat w,\hat q)]|\\
&= |\E[f_{\MIL_1}(\hat w,\tilde q)]|- |\E_n[f_{\MIL_1}(\hat w,\tilde q)]|+ |\E_n[f_{\MIL_1}(\hat w,\tilde q)]|- |\E_n[f_{\MIL_1}(\hat w,\hat q)]| \\
& \quad +|\E_n[f_{\MIL_1}(\hat w,\hat q)]|-|\E[f_{\MIL_1}(\hat w,\hat q)]|\\
&\leq |\E[f_{\MIL_1}(\hat w,\tilde q)]|- |\E_n[f_{\MIL_1}(\hat w,\tilde q)]|+|\E_n[f_{\MIL_1}(\hat w,\hat q)]|-|\E[f_{\MIL_1}(\hat w,\hat q)]|\\
&\leq 2\sup_{w\in \Wbbb_1,q\in \Qbbb_1}|(\E-\E_n)[ f_{\MIL_1}(w,q)]|.
\end{align*}

Here, we use $|\E_n[f_{\MIL_1}(\hat w,\tilde q)]|\leq |\E_n[f_{\MIL_1}(\hat w,\hat q)]|$. Thus,

\begin{align*}
|\E[(\hat w-w_{\epol})\Tcal_{\gamma}\hat q]|\leq 4|\sup_{w\in \Wbbb_1,q\in \Qbbb_1}(\E-\E_n)[ f_{\MIL_1}(w,q)]|.
\end{align*}

In addition, with probability $1-\delta$,

\begin{align*}
|\hat J^{\MIL}_w- J^{\MIL}_w|\leq \sup_{w\in \Wbbb_1}|(\E_n-\E)[w(s,a)r]|.
\end{align*}

Combining all results together and using the uniform law of large numbers,  with probability $1-\delta$,

\begin{align*}
|\hat J^{\MIL}_w-J|&\leq \sup_{w\in \Wbbb_1}|(\E_n-\E)[w(s,a)r]|+4|\sup_{w\in \Wbbb_1,q\in \Qbbb_1}(\E-\E_n)[ f_{\MIL_1}(w,q)]| \\
&\lesssim R_{\max}\Rcal_n(\Wbbb_1)+R_{\max}\sqrt{\log(4/\delta)/n}+\Rcal_n(\Gcal(\Wbbb_1,\Qbbb_1)) +C_{\Wbbb_1}(C_{\Qbbb_1}+R_{\max})\sqrt{\log(4/\delta)/n}.
\end{align*}

Proof for $\hat J^{\MIL}_q$

Estimators for q-functions in MIL are defined as

\begin{align*}
\hat q=\argmin_{q\in\Qbbb_2}\max_{w\in \Wbbb_2}|\E_n[f_{\MIL_2}(s,a,r,s';w,q)]|,\,f_{\MIL_2}(s,a,r,s';w,q)=w(s,a)\{r-q(s,a)+\gamma v(s')\}
\end{align*}

We write this solution as $(\hat q,\hat w)$, i.e.,

\begin{align*}
\hat w=\argmax_{w\in \Wbbb_2}|\E_n[f_{\MIL_2}(s,a,r,s'; w,\hat q)]|.
\end{align*}

We have

\begin{align}\label{eq:mqlmql}
|\hat J^{\MIL}_q-J|&\leq  \max_{w\in \Wbbb_2}|\E[w(s,a)\Tcal_{\gamma}(\hat q-q_{\epol})]|+ \min_{w\in \Wbbb_2}|\E[(w-w_{\epol})\Tcal_{\gamma}(\hat q-q_{\epol})]|.
\end{align}

This is proved as follows. We have for any $w\in \Wbbb_2$:

\begin{align*}
|\hat J^{\MIL}_q-J|&=|(1-\gamma)\E_{d_0}[\hat q(s_0,\epol)]-\E[w_{\epol}(s,a)r]|\\
&=|\E[w_{\epol}(s,a)\{-\hat q(s,a)+\gamma \hat v(s')\}]-\E[w_{\epol}(s,a)r]|\\
&=|\E[w_{\epol}(s,a)\{r-\hat q(s,a)+\gamma \hat v(s')\}]|\\
&\leq |\E[w(s,a)\{r-\hat q(s,a)+\gamma \hat v(s')\}]|+|\E[(w-w_{\epol})\{r-\hat q(s,a)+\gamma \hat v(s')\}]|\\
&= |\E[w \Tcal_{\gamma}(\hat q-q_{\epol})]|+|\E[(w-w_{\epol})\Tcal_{\gamma}(\hat q-q_{\epol})]|.
\end{align*}

This concludes the proof of <ref>.

Then, recall

\begin{align*}
\E[ f_{\MIL_2}(s,a,r,s';w,q)]=\E[w\Tcal_{\gamma}(\hat q-q_{\epol})].
\end{align*}

Then, from the assumption and (<ref>), we have

\begin{align*}
|\hat J^{\MIL}_q-J|\leq \max_{w\in \Wbbb_2}|\E[w(s,a)\Tcal_{\gamma}(\hat q-q_{\epol})]|=|\E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|,
\end{align*}

\begin{align*}
\tilde w= \argmax_{w\in \Wbbb_2}|\E[w\Tcal_{\gamma}(\hat q-q_{\epol})]|.
\end{align*}

As a first step, we bound $|\E[\hat w\Tcal_{\gamma}(\hat q-q_{\epol})]|$:

\begin{align*}
& |\E[\hat w\Tcal_{\gamma}(\hat q-q_{\epol})]|=|\E[f_{\MIL_2}(\hat w,\hat q)]|=|\E[f_{\MIL_2}(\hat w,\hat q)]|-|\E[f_{\MIL_2}(\hat w,q_{\epol})]|\\
&=|\E[f_{\MIL_2}(\hat w,\hat q)]|-|\E_n[f_{\MIL_2}(\hat w,\hat q)]|+|\E_n[f_{\MIL_2}(\hat w,\hat q)]|-|\E_n[f_{\MIL_2}(\hat w,q_{\epol})]| \\
& \quad +|\E_n[f_{\MIL_2}(\hat w,q_{\epol})]|-|\E[f_{\MIL_2}(\hat w,q_{\epol})]|\\
&\leq |\E[f_{\MIL_2}(\hat w,\hat q)]|-|\E_n[f_{\MIL_2}(\hat w,\hat q)]|+|\E_n[f_{\MIL_2}(\hat w,q_{\epol})]|-|\E[f_{\MIL_2}(\hat w,q_{\epol})]|\\
&\leq 2|\sup_{w\in\Wbbb_2,q\in \Qbbb_2}(\E-\E_n)[f_{\MIL_2}(q,w)]|
\end{align*}

Here, we use $|\E_n[f_{\MIL_2}(\hat w,\hat q)]|\leq |\E_n[f_{\MIL_2}(\hat w,q_{\epol})]|$ and  $|\E[f_{\MIL_2}(\hat w,q_{\epol})]|=0$.

Second, we bound the difference of $ |\E[\hat w\Tcal_{\gamma}(\hat q-q_{\epol})]|$ and $ |\E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|$:

\begin{align*}
&|\E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|-|\E[\hat w\Tcal_{\gamma}(\hat q-q_{\epol})]|\\
& =|\E[f_{\MIL_2}(\tilde w,\hat q)]|-|\E[f_{\MIL_2}(\hat w,\hat q)]|\\
& =|\E[f_{\MIL_2}(\tilde w,\hat q)]|-|\E_n[f_{\MIL_2}(\tilde w,\hat q)]|+|\E_n[f_{\MIL_2}(\tilde w,\hat q)]|-|\E_n[f_{\MIL_2}(\hat w,\hat q)]|\\
& \quad +|\E_n[f_{\MIL_2}(\hat w,\hat q)]| -|\E[f_{\MIL_2}(\hat w,\hat q)]|\\
& \leq |\E[f_{\MIL_2}(\tilde w,\hat q)]|-|\E_n[f_{\MIL_2}(\tilde w,\hat q)]|+|\E_n[f_{\MIL_2}(\hat w,\hat q)]| -|\E[f_{\MIL_2}(\hat w,\hat q)]|\\
&  \leq 2|\sup_{w\in\Wbbb_2,q\in \Qbbb_2}(\E-\E_n)[f_{\MIL_2}(q,w) ]| .
\end{align*}

Here, we use $|\E_n[f_{\MIL_2}(\tilde w,\hat q)]|\leq |\E_n[f_{\MIL_2}(\hat w,\hat q)]|$. In the end,

\begin{align*}
&\E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|\\
&\leq |\E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|- |\E[\hat w\Tcal_{\gamma}(\hat q-q_{\epol})]|+|\E[\hat w\Tcal_{\gamma}(\hat q-q_{\epol})]|\\
&\leq  4|\sup_{w\in\Wbbb_2,q\in \Qbbb_2}(\E-\E_n)[f_{\MIL_2}(q,w)]|.
\end{align*}

This term is upper-bounded by $\Rcal_n(\Gcal(\Wbbb_2,\Qbbb_2))+C_{\Wbbb_2}C_{\Qbbb_2}\sqrt{\log(2/\delta)/n}$ up to universal constants.

Proof for $\hat J^{\MIL}_{wq}$

\begin{align*}
f(s,a,r,s';w,q)=w(s,a)\{r-q(s,a)+\gamma q(s',\epol)\}+(1-\gamma)\E_{d_0}[q(s_0,\epol)],
\end{align*}

we define

\begin{align*}
J^{\MIL}_{wq}=\E[f(s,a,r,s';\hat w,\hat q)].
\end{align*}

Here, we have

\begin{align*}
|\hat J^{\MIL}_{wq}-    J^{\MIL}_{wq}|\leq \sup_{w\in \Wbbb_1,q\in \Qbbb_2}|(\E-\E_n)[f(w,q)]|.
\end{align*}

Here, we have

\begin{align*}
\E[f(s,a,r,s';\hat w,\hat q)]-J=|\E[\{\hat w-w_{\epol}\}\{\Tcal_{\gamma}(\hat q-q_{\epol}\}] |.
\end{align*}

Case 1: when $q_{\epol}\in \Qbbb_2,w_{\epol}-\Wbbb_1\subset \Wbbb_2$
Thus, from a similar calculation as the above,

\begin{align*}
|  \E[f(s,a,r,s';\hat w,\hat q)]-J|&\leq \max_{w\in \Wbbb_2}|\E[w(s,a)\Tcal_{\gamma}(\hat q-q_{\epol}) ]|+\min_{w\in \Wbbb_2}|\E[\{w-w_{\epol}+\hat w\}\Tcal_{\gamma}(\hat q-q_{\epol}) ]|.
\end{align*}

The second term is $0$ from the assumption. The first term is calculated as before.

Case 2: when $w_{\epol}\in \Wbbb_1,q_{\epol}-\Qbbb_2\subset \Qbbb_1$
Thus, from a similar calculation as the above,

\begin{align*}
|  \E[f(s,a,r,s';\hat w,\hat q)]-J|&\leq \max_{q\in \Qbbb_1}|\E[(\hat w-w_{\epol})\Tcal_{\gamma}q]|+\min_{q\in \Qbbb_1}|\E[(\hat w-w_{\epol})\Tcal_{\gamma}\{q-q_{\epol}+\hat q\}]|.
\end{align*}

The second term is $0$ from the assumption. The first term is calculated as before.

Combining all things, with $1-\delta$,

\begin{align*}
|\hat J^{\MIL}_{wq}-J|&\leq \sup_{w\in \Wbbb_1,q\in \Qbbb_2}|(\E-\E_n)[f(w,q)]|\\
&+\max(4\sup_{w\in\Wbbb_1,q\in \Qbbb_1}|(\E-\E_n)[f_{\MIL_1}(q,w)]|, 4\sup_{w\in\Wbbb_2,q\in \Qbbb_2}|(\E-\E_n)[f_{\MIL_2}(q,w)]|)\\
&\lesssim  \mathrm{Err}_{\MIL,wq}+\max(\mathrm{Err}_{\MIL,w},\mathrm{Err}_{\MIL,q}).
\end{align*}

The proof is deferred to <ref>.

The proof is deferred to <ref>.

The proof is deferred to <ref>.

Convergence rate of w-functions regarding  $\|\hat w-w_{\epol}\|_2$

Estimators for the weight functions in MIL are defined as

\begin{align*}
&\hat w=\argmin_{w\in\Wbbb_1}\max_{q\in \Qbbb_1}|\E_n[f_{\MIL_1}(s,a,r,s';w,q)]|,\\
& f_{\MIL_1}(s,a,r,s';w,q)=w(s,a)\{q(s,a)-\gamma q(s',\epol)\}-(1-\gamma)\E_{d_0}[q(s_0,\epol)].
\end{align*}

We write this solution to the above minimax optimization as $(\hat w,\hat q)$. Thus,

\begin{align*}
\hat q \coloneqq\argmax_{q\in \Qbbb_1}|\E_n[f_{\MIL_1}(s,a,r,s';\hat w,q)]|.
\end{align*}

In addition, we have

\begin{align*}
\E[ f_{\MIL_1}(s,a,r,s';w,q)]=-\E[\Tcal'_{\gamma}(w-w_{\epol})q].
\end{align*}

What we want to bound is $\E[(\hat w-w_{\epol})^2]$:

\begin{align*}
&\E[(\hat w-w_{\epol})^2]\leq  \max_{q\in \Qbbb_1}|\E[C^{-1}_{\zeta}(\hat w-w_{\epol})\Tcal_{\gamma}q]|=  |\E[C^{-1}_{\zeta}\{(\hat w-w_{\epol})\}\Tcal_{\gamma}\tilde q ]|,
\end{align*}

\begin{align*}
\tilde  q= \argmax_{q\in \Qbbb_1}|\E[(\hat w-w_{\epol})\Tcal_{\gamma}q]|.
\end{align*}

Here, we use $C_{\zeta}(\Wbbb_1-w_{\epol})\subset \Tcal_{\gamma}\Qbbb_1$. Therefore, if we can bound $|\E[\Tcal'_{\gamma}(\hat w-w_{\epol})\tilde q ]|$, the convergence rate is obtained. This is bounded as in the proof of <ref>.  Thus, with probability $1-\delta$,

\begin{align*}
\E[\{\Tcal'_{\gamma}(\hat w-w_{\epol})\}^2]\leq C^{-1}_{\zeta}\mathrm{Err}_{\MIL,w}.
\end{align*}

Convergence rate of w-functions regarding $\|\Bcal'\hat w-\hat w\|_2$

What we want to bound is $\E[(\Bcal'\hat w-\hat w)^2]$. Since $\Bcal' w-w=\Tcal'_{\gamma}(w-w_{\epol})$, we bound $\E[\{\Tcal'_{\gamma}(\hat w-w_{\epol})\}^2]$:

\begin{align*}
&\E[\{\Tcal'_{\gamma}(\hat w-w_{\epol})\}^2]\leq  \max_{q\in \Qbbb_1}|\E[\{\Tcal'_{\gamma}(\hat w-w_{\epol})\}C^{-1}_{\zeta}q]|=  |\E[C^{-1}_{\zeta}\{\Tcal'_{\gamma}(\hat w-w_{\epol})\}\tilde q ]|,
\end{align*}

\begin{align*}
\tilde  q= \argmax_{q\in \Qbbb_1}|\E[\Tcal'_{\gamma}(\hat w-w_{\epol})q]|.
\end{align*}

Here, we use $C_{\zeta}\Tcal'_{\gamma}(\Wbbb_1-w_{\epol})\subset \Qbbb_1$. Therefore, if we can bound $|\E[C^{-1}_{\zeta}\Tcal'_{\gamma}(\hat w-w_{\epol})\tilde q ]|$, the convergence rate is obtained. This is bounded as in the proof of <ref>.  Thus, with probability $1-\delta$,

\begin{align*}
\E[\{\Bcal'\hat w-\hat w\}^2]\leq C^{-1}_{\zeta}\mathrm{Err}_{\MIL,w}.
\end{align*}

Convergence rate of q-functions regarding $\|\Bcal \hat q-\hat q\|_2$

Recall that estimators for q-functions in MIL are defined as

\begin{align*}
\hat q=\argmin_{q\in\Qbbb_2}\max_{w\in \Wbbb_2}|\E_n[f_{\MIL_2}(s,a,r,s';w,q)]|,\,f_{\MIL_2}(s,a,r,s';w,q)=w(s,a)\{r-q(s,a)+\gamma v(s')\}
\end{align*}

We write this solution to $(\hat q,\hat w)$, i.e.,

\begin{align*}
\hat w=\argmax_{w\in \Wbbb_2}|\E_n[f_{\MIL_2}(s,a,r,s';w,\hat q)]|.
\end{align*}

In addition, we have

\begin{align*}
\E[ f_{\MIL_2}(s,a,r,s';w,\hat q)]=\E[w\Tcal_{\gamma}(\hat q-q_{\epol})].
\end{align*}

What we want to bound is $\E[\{\Bcal \hat q-\hat q\})^2]$. Since $\Bcal q-q=\Tcal_{\gamma}(q-q_{\epol})$, we bound $\E[\{\Tcal_{\gamma}(\hat q-q_{\epol})\}^2]$:

\begin{align*}
&\E[\{\Tcal_{\gamma}(\hat q-q_{\epol})\}^2]\leq C^{-1}_{\zeta}\max_{w \in \Wbbb_2}|\E[w\Tcal_{\gamma}(\hat q-q_{\epol})]|=C^{-1}_{\zeta}| \E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|,
\end{align*}

\begin{align*}
\tilde w= \argmax_{w\in \Wbbb_2}|\E[w\Tcal_{\gamma}(\hat q-q_{\epol})]|.
\end{align*}

Here, we use $C_{\zeta}\Tcal_{\gamma}(\Qbbb_2-q_{\epol})\subset \Wbbb_2$. Therefore, if we can bound $|\E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|$, the convergence rate is obtained. This is bounded as in the proof of <ref>.  Thus, with probability $1-\delta$,

\begin{align*}
\E[\{\Bcal'\hat q-\hat q\}^2]\leq C^{-1}_{\zeta}\mathrm{Err}_{\MIL,q}.
\end{align*}

Convergence rate of q-functions regarding $\|\hat q-q_{\epol}\|_2$

We have

\begin{align*}
&\E[\{\hat q-q_{\epol}\}^2]\leq \max_{w \in \Wbbb_2}C^{-1}_{\zeta}|\E[\Tcal'_{\gamma}w(\hat q-q_{\epol})]|=C^{-1}_{\zeta}| \E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|,
\end{align*}

\begin{align*}
\tilde w= \argmax_{w\in \Wbbb_2}|\E[w\Tcal_{\gamma}(\hat q-q_{\epol})]|.
\end{align*}

Here, we use $C_{\zeta}(\Qbbb_2-q_{\epol})\subset \Tcal'_{\gamma}\Wbbb_2$. Therefore, if we can bound $|\E[\tilde w\Tcal_{\gamma}(\hat q-q_{\epol})]|$, the convergence rate is obtained. This is bounded as in the proof of <ref>.  Thus, with probability $1-\delta$,

\begin{align*}
\E[\{\hat q-q_{\epol}\}^2]\leq C^{-1}_{\zeta}\mathrm{Err}_{\MIL,q}.
\end{align*}

We prove

\begin{align*}
(1-\gamma \sqrt{C_mC_{\eta}})\|q-q_{\epol}\|_2 \leq   \|\Bcal q-q\|_2\leq (1+\gamma \sqrt{C_mC_{\eta}})\|q-q_{\epol}\|_2.
\end{align*}

\begin{align*}
\|\Bcal q-q\|_2&=\|(\gamma \Tcal-I)(q-q_{\epol})\|_2\\
&\leq \gamma\|\Tcal(q-q_{\epol})\|_2+ \|q-q_{\epol}\|_2\\
&\leq \gamma\sqrt{C_mC_{\eta}}\|q-q_{\epol}\|_2+\|q-q_{\epol}\|_2. \tag{\cref{lem:boundedness}}
\end{align*}

In addition,

\begin{align*}
\|q-q_{\epol}\|_2&\leq \|q-\Bcal q\|_2+\|\Bcal q-q_{\epol}\|_2= \|q-\Bcal q\|_2+\|\Bcal q-\Bcal q_{\epol}\|_2\\
&= \|q-\Bcal q\|_2+\gamma \|\Tcal(q-q_{\epol})]\|_2\\
&= \|q-\Bcal q\|_2+\gamma\sqrt{C_mC_{\eta}}\|q-q_{\epol}\|_2.
\end{align*}

This shows $\|q-q_{\epol}\|_2\{1-\gamma\sqrt{C_mC_{\eta}}\}\leq \|q-\Bcal q\|_2.$

We prove

\begin{align*}
(1-\gamma \sqrt{C_mC_{\eta}})\|w-w_{\epol}\|_2 \leq \|\Bcal w-w\|_2\leq  (1+\gamma \sqrt{C_mC_{\eta}})\|w-w_{\epol}\|_2.
\end{align*}

\begin{align*}
\|\Bcal w-w\|_2&\leq \|(\gamma \Tcal'-I)(w-w_{\epol})\|_2\\
&\leq \gamma \|\Tcal'w-\Tcal' w_{\epol}\|_2+\|w-w_{\epol}\|_2\\
&\leq (1+\gamma \sqrt{C_mC_{\eta}})\|w-w_{\epol}\|_2.   \tag{\cref{lem:boundedness}}
\end{align*}

\begin{align*}
\|w-w_{\epol}\|_2&\leq     \|w-\Bcal w\|_2+\|\Bcal w-\Bcal w_{\epol}\|_2\\
&\leq \|w-\Bcal w\|_2+\gamma \|\Tcal'w-\Tcal' w_{\epol}\|_2\\
&\leq \|w-\Bcal w\|_2+\gamma \sqrt{C_mC_{\eta}}\|w-w_{\epol}\|_2.
\end{align*}

Thus, $(1-\gamma \sqrt{C_mC_{\eta}})     \|w-w_{\epol}\|_2\leq  \|w-\Bcal w\|_2$.

Statement 1

\begin{align*}
\Tcal f(s,a)=\int f(s',\epol)P_{S'|S,A}(s'|s,a)\rd\mu(s').
\end{align*}

Thus, for any $q\in \Qbbb$, $\Bcal q$ belongs to $\Qbbb$. Noting $\Bcal q_{\epol}=q_{\epol}$, $q_{\epol}$ also belongs to $\Qbbb$. We write $q_{\epol}=\theta^{*}\phi$.

Statement 2

We show there exists $M_{\epol}$ s.t. $\Tcal(\beta^{\top}\phi)=(M_{\epol}\beta)^{\top}\phi$. This is proved by

\begin{align*}\ts
\Tcal(\beta^{\top}\phi)=\beta^{\top}\{\int \phi(s',\epol)\theta(s')^{\top}\rd\mu(s')\}\phi.
\end{align*}

Thus, for any $\theta \in \mathbb{R}^d$,

\begin{align*}
( \gamma \Tcal-I)\{(\theta-\theta^{*})^{\top}\phi\}&=\gamma (\theta-\theta^{*})^{\top} M^{\top}_{\epol}\phi-(\theta-\theta^{*})^{\top}\phi\\
&=\{(\gamma M_{\epol}-I)(\theta-\theta^{*}) \}^{\top}\phi.
\end{align*}

This implies $\Tcal_{\gamma}(\Qbbb-q_{\epol})\subset \Qbbb$. Recall $\Qbbb=\{\theta^{\top} \phi;\theta \in \mathbb{R}^d\}$.

Statement 3
From <ref> and (<ref>), given $f_2=\theta \cdot \phi$, we have

\begin{align*}
\Tcal'_{\gamma} f_2=\{\E[\phi\phi^{\top}]^{-1}(\gamma M^{\top}_{\epol}-I)\E[\phi\phi^{\top}] \}\theta \cdot \phi.
\end{align*}

Since $I-\gamma M^{\top}_{\epol}$ is invertible from the assumption $1/\gamma \notin \sigma(M_{\epol})$, for any $q-q_{\epol}=(\theta-\theta^{*})\cdot \phi\in \Qbbb-q_{\epol}$, we can take

\begin{align*}
q'=\{\E[\phi\phi^{\top}]^{-1}(\gamma M^{\top}_{\epol}-I)\E[\phi\phi^{\top}] \}^{-1}(\theta-\theta^*) \cdot \phi
\end{align*}

s.t. $\Tcal'_{\gamma} q'=q-q_{\epol}$
This implies $\Qbbb-q_{\epol} \subset \Tcal'_{\gamma}\Qbbb$

Statement 4
We use a matrix formulation following <ref>. In a tabular case, $M_{\epol}=P_{\epol}$. The spectrum of $P_{\epol}$ is less than or equal to $1$. Thus, $\Qbbb-q_{\epol} \subset \Tcal'_{\gamma}\Qbbb$ holds from the statement 3.

Let $\mathbf{1}$ be a $d$-dimensional vector. Assume $\mathbf{1}^{\top}\phi(s',\epol)=1,\int \theta(s')\rd(s')=\mathbf{1}$.
This assumption is used in - in a different context. Then,

\begin{align*}
\mathbf{1}^{\top}\{\int \phi(s',\epol)\theta(s')^{\top}\rd\mu(s')\}=\mathbf{1}^{\top}.
\end{align*}

Thus, $M^{\top}_{\epol}$ is a stochastic matrix. This implies $\sigma(M_{\epol})\leq \|M_{\epol}\|_{\infty}=1$.

From <ref>, recall

\begin{align*}
\Tcal' f(s,a)=\eta_{\epol}(s,a)\int f(s',a')P_{S,A|S'}(s',a'|s)\rd\mu(s',a').
\end{align*}

First, by using the assumption $P_{S,A|S'}(s',a'|\cdot)=\psi(\cdot)\cdot \theta(s',a')$, $ \Tcal' f$ belongs to

\begin{align*}
\Wbbb= \{\eta_{\epol}(s,a)\times (\psi(s)\cdot \beta);\beta \in \mathbb{R}^d\}.
\end{align*}

Especially, $\Tcal'\{\beta^{\top}\eta\psi\}=(M'_{\epol}\beta)^{\top}\eta\psi$ holds by taking $M'^{\top}_{\epol}$ s.t.

\begin{align*}
\int \eta_{\epol}(s',a')\psi(s')\theta^{\top}(s',a')\rd\mu(s',a').
\end{align*}

Statement 1
Noting $\Bcal' w=\gamma \Tcal'w+(1-\gamma)\frac{d_0(s)\epol(a|s)}{\bpol(a|s)p_{S}(s)}$ and the assumption $d_0(s)/p_{S}(s)$ belongs to $\{\psi(s)\cdot \beta);\beta \in \mathbb{R}^d \}$, for any $w$, $\Bcal' w$ belongs to $\Wbbb$. Since $\Bcal' w_{\epol}=w_{\epol}$, $w_{\epol}$ also belongs to $\Wbbb$.  We define $\theta^{*}$ s.t. $w_{\epol}=\eta \{\theta^{*}\}^{\top}\psi$.

Statement 2

For any $\theta\in \mathbb{R}^d$,

\begin{align*}
(\gamma \Tcal'-I)\{\eta\theta^{\top}\psi-\eta \{\theta^{*}\}^{\top}\psi\}=  (\gamma M'_{\epol}-I)(\theta-\theta^{*}) \cdot \eta\psi.
\end{align*}

Thus, $\Tcal'_{\gamma}(\Wbbb-w_{\epol})\subset \Wbbb$ is concluded.

Statement 3

From <ref> and (<ref>), for $f_2=\theta\cdot \eta\psi$ we have

\begin{align*}
\Tcal_{\gamma}f_2=\{\E[\psi\psi^{\top}]^{-1}(\gamma M'^{\top}_{\epol}-I)\E[\psi\psi^{\top}]\}\theta \cdot \eta\psi
\end{align*}

Since $(I-\gamma M'^{\top}_{\epol})$ is non-singular from the assumption $1/\gamma \notin \sigma(M_{\epol})$, for any $w-w_{\epol}=(\theta-\theta^{*})\cdot \eta\psi$, we can take $w'$

\begin{align*}
w'=\{\E[\psi\psi^{\top}]^{-1}(\gamma M'^{\top}_{\epol}-I)\E[\psi\psi^{\top}]\}^{-1}(\theta-\theta^{*})\cdot \eta\psi
\end{align*}

s.t. $w-w_{\epol}=\Tcal_{\gamma}w'$. This implies  $(\Wbbb-w_{\epol})\subset \Tcal_{\gamma}\Wbbb$.

Let $\mathbf{1}$ be a $d$-dimensional vector. Assume
$$\mathbf{1}^{\top}\eta_{\epol}(s',a')\psi(s')=1,\int \theta(s',a')\rd\mu(s',a')=\mathbf{1}.$$

\begin{align*}
\mathbf{1}^{\top}\int \eta_{\epol}(s',a')\psi(s')\theta^{\top}(s',a')\rd\mu(s',a')=    \mathbf{1}^{\top}.
\end{align*}

Thus, $M'^{\top}_{\epol}$ is a stochastic matrix. This implies $\sigma(M'_{\epol})\leq \|M'_{\epol}\|_{\infty}=1$.

We use a matrix formulation following <ref>. W-, $\Tcal_{\gamma}(\Wbbb-w_{\epol}) \subset \Wbbb$ , obviously holds. Thus, we prove adjoint w-. Recall $\E[\phi\phi^{\top}]$ is non-singular, and we have

\begin{align*}
[\Tcal'f]=( \E[\phi\phi^{\top}]^{-1}(P^{\epol})^{\top} \E[\phi\phi^{\top}])[f]
\end{align*}

\begin{align*}
[\Tcal_{\gamma}f]=[(\gamma \Tcal'-I)f]=(\E[\phi\phi^{\top}]^{-1}(\gamma P^{\epol}-I)^{\top} \E[\phi\psi^{\top}])[f].
\end{align*}

Thus, for given any $f\in \Wbbb-w_{\epol}$, we can take a vector
$$f':=\{ (\E[\phi\phi^{\top}]^{-1}(\gamma P^{\epol}-I)^{\top} \E[\phi\phi^{\top}])^{-1} [f]\}\cdot \phi$$

\begin{align*}
(\gamma \Tcal'-I)f'=f.
\end{align*}

Note $\gamma P^{\epol}-I$ is non-singular. Therefore, the adjoint w-, $(\Wbbb-w_{\epol}) \subset \Tcal'_{\gamma}\Wbbb$ holds.

First Statement
Define $J^{\MIL}_{w}\coloneqq \E[\hat w r]$. Then,

\begin{align*}
|J^{\MIL}_{w}-J| &=|\E[(\hat w-w_{\epol})\Tcal_{\gamma}q_{\epol}]|=|\E[\Tcal'_{\gamma}(\hat w-w_{\epol})q_{\epol}]|\leq \|\Tcal'_{\gamma}(\hat w-w_{\epol})\|_2\|\|q_{\epol}\|_2,\\
|J^{\MIL}_{w}-J|&=|\E[(\hat w-w_{\epol})\Tcal_{\gamma}q_{\epol}]|\leq \|(\hat w-w_{\epol})\|_2\|\|\Tcal_{\gamma}q_{\epol}\|_2.
\end{align*}

Thus, when $w_{\epol}\in \Wbbb_1,C_{\zeta}\Tcal'_{\gamma}(\Wbbb_1-w_{\epol})\subset \Qbbb_1$, with $1-\delta$,

\begin{align*}
|\hat J^{\MIL}_{w}-J|&\leq |\hat J^{\MIL}_{w}-J^{\MIL}_{w} |+| J^{\MIL}_{w}-J|\\
&\leq  |\hat J^{\MIL}_{w}-J^{\MIL}_{w} |+\|\Tcal'_{\gamma}(\hat w-w_{\epol})\|_2\|\|q_{\epol}\|_2\\
\end{align*}

Similarly,  when $q_{\epol}\in \Qbbb_2,C_{\zeta}(\Wbbb_1-w_{\epol})\subset \Tcal_{\gamma}\Qbbb_1$, with $1-\delta$, we have

\begin{align*}
|\hat J^{\MIL}_{w}-J|&\leq \Error'_{\MIL,w}+\sqrt{C^{-1}_{\xi}\Error_{\MIL,w}}\|\Tcal_{\gamma} q_{\epol}\|_2.
\end{align*}

Second Statement
When $q_{\epol}\in \Qbbb_2,C_{\zeta}\Tcal_{\gamma}(\Qbbb_2-q_{\epol})\subset \Wbbb_2$, with $1-\delta$, we have

\begin{align*}
|\hat J^{\MIL}_{q}-J|&=|\E[w_{\epol}\Tcal_{\gamma}(\hat q-q_{\epol})]|\leq \|w_{\epol}\|_2\|\|\Tcal_{\gamma}(\hat q-q_{\epol})\|_2\\
&\leq \|w_{\epol}\|_2\sqrt{C^{-1}_{\xi}\Error_{\MIL,q}}.
\end{align*}

When $q_{\epol}\in \Qbbb_2,C_{\zeta}(\Qbbb_2-q_{\epol})\subset \Tcal'_{\gamma}\Wbbb_2$, with $1-\delta$, we have

\begin{align*}
|\hat J^{\MIL}_{q}-J|&=|\E[\Tcal'_{\gamma}w_{\epol}(\hat q-q_{\epol})]|\leq \|\Tcal'_{\gamma}w_{\epol}\|_2\|\|(\hat q-q_{\epol})\|_2\\
&\leq \|\Tcal'_{\gamma}w_{\epol}\|_2\sqrt{C^{-1}_{\xi}\Error_{\MIL,q}}.
\end{align*}

Third Statement

We define
$$J^{\MIL}_{wq}\coloneqq \E[\hat w \{r-\hat q(s,a)+\gamma \hat q(s',\epol)\}+(1-\gamma)\E_{d_0}[\hat q(s_0,\epol)].$$

When we have $q_{\epol}\in \Qbbb_2, C_{\zeta}\Tcal_{\gamma}(\Qbbb_2-q_{\epol})\subset \Wbbb_2 $, with $1-\delta$,

\begin{align*}
|J^{\MIL}_{wq}-J|&=|\E[\{w_{\epol}-w\}\Tcal_{\gamma}(\hat q-q_{\epol})]|\leq \|w_{\epol}-\hat w\|_2\|\|\Tcal_{\gamma}(\hat q-q_{\epol})\|_2\\
&\leq \sup_{w\in \Wbbb_1}\|w-w_{\epol}\|_2 \|\Tcal_{\gamma}(\hat q-q_{\epol})\|_2\lesssim \sup_{w\in \Wbbb_1}\|w-w_{\epol}\|_2\sqrt{C^{-1}_{\xi}\Error_{\MIL,q}}
\end{align*}

When we have $w_{\epol}\in \Wbbb_1,C_{\zeta}\Tcal'_{\gamma}(\Wbbb_1-w_{\epol})\subset \Qbbb_1 $,   with $1-\delta$,

\begin{align*}
|J^{\MIL}_{wq}-J|&=  |\E[\Tcal'_{\gamma}(\hat w-w_{\epol})(\hat q-q_{\epol})]|\leq \|\Tcal'_{\gamma}(w_{\epol}-\hat w)\|_2\|\|\hat q-q_{\epol}\|_2\\
&\leq \sup_{q\in \Qbbb_1}\|q-q_{\epol}\|_2 \|\Tcal'_{\gamma}(\hat w-w_{\epol})\|_2\lesssim \sup_{q\in \Qbbb_2}\|q-q_{\epol}\|_2  \sqrt{C^{-1}_{\xi}\Error_{\MIL,w}}
\end{align*}

$|\hat J^{\MIL}_{wq}-J^{\MIL}_{wq}|\lesssim \Error_{\MIL,wq}$, the statement is proved as

\begin{align*}
|\hat J^{\MIL}_{wq}-J|\leq \Error_{\MIL,wq}+C^{-1}_{\xi}\max(\sup_{w\in \Wbbb_1}\|w-w_{\epol}\|_2\sqrt{\Error_{\MIL,q}}, \sup_{q\in \Qbbb_2}\|q-q_{\epol}\|_2  \sqrt{\Error_{\MIL,w}} ).
\end{align*}

This immediately implies

\begin{align*}
|\hat J^{\MIL}_{wq}-J|\leq \Error_{\MIL,wq}+C^{-1}_{\xi}\max(C_{\Wbbb}\sqrt{\Error_{\MIL,q}}, C_{\Qbbb}\sqrt{\Error_{\MIL,w}} ).
\end{align*}

Regarding the statement related to adjoint completeness, the statement similarly holds.

§.§ Proof of <ref>

In the following we will frequently invoke two key lemmas. First, recall that the empirical localized Rademacher complexity of the function class is $\Gcal:V\to [-c,c]$ for a given set of samples $S=\{v_i\}$ is defined as

\begin{align*}
\Rcal_n(\eta;\Gcal)=\E_{\epsilon}\bracks{\sup_{g\in \Gcal: \|g\|_{n}\leq \eta }\frac{1}{n}\sum_i \epsilon_i g(v_i)}.
\end{align*}

The critical radius of $\Gcal$ is defined as a solution to $ \Rcal_n(\eta;\Gcal)\leq \eta^2/c$.

Given a star-shaped and $b$-uniformly bounded function class $\Gcal$, let $\eta_n$ be any positive solution of the inequality $R_s(\eta;\Gcal)\leq \eta^2/b$. Then, for any $t\geq \eta_n$, we have

\begin{align*}
|\|g\|^2_n-\|g\|^2_2  |\leq 0.5\|g\|^2_2+0.5t^2, \forall g\in \Gcal.
\end{align*}

Consider a function class $\Fcal:X\to \mathbb{R}$ with loss $l:\mathbb{R}\times Z\to \mathbb{R}$.

Assume $\sup_{f\in \Fcal}\|f\|_{\infty}\leq c$ and pick any $f^{*}\in \Fcal$. We define $\eta$ be a solution to

\begin{align*}
\Rcal_n(\eta;\mathrm{star}(\Fcal-f^*))\leq \eta^2/c.
\end{align*}

Moreover, assume that the loss $l(\cdot,\cdot)$ is $L$-Lipschitz in the first argument. Then, with $1-\delta$,

\begin{align*}
|(\E_n[l(f(x),z)]-\E_n[l(f^{*}(x),z)])-(\E[l(f(x),z)]-\E[l(f^{*}(x),z)])|\leq L \eta_n (\|f-f^{*}\|_2+\eta_n),\,\forall f\in \Fcal,
\end{align*}

where $\eta_n=\eta+c_0\sqrt{\log(c_1/\delta)/n}$ for some universal constants $c_0,c_1$.

\begin{align*}
\Phi(q;w) &=\E[\{r-q(s,a)+\gamma q(s',\epol)\}w(s,a)],\\
\Phi_n(q;w) &=\E_n[\{r-q(s,a)+\gamma q(s',\epol)\}w(s,a)],\\
\Phi^{\lambda}_n(q;w) &= \Phi_n(q;w)-\lambda \|w\|^2_{2,n},\\
\Phi^{\lambda}(q;w) &=\Phi(q;w)-\lambda\|w\|^2_{2}.
\end{align*}

From <ref>, we have

\begin{align}\label{eq:martin_q}
\forall w\in \Wbbb,\,|\|w\|_{n}^2-\|w\|^2_2|\leq 0.5\|w\|^2_2+\eta^2
\end{align}

for our choice of $\eta:=\eta_n+\sqrt{c_0\log(c_1/\delta)/n}$ noting $\eta_n$ upper bounds the critical radius of $\Wbbb$.

First Step

By definition of $\hat q_{\MIL}$ and $q_{\epol}\in \Qbbb$, we have

\begin{align}\label{eq:obvious_def}
\sup_{w\in \Wbbb}   \Phi^{\lambda}_n(\hat q_{\MIL};w) \leq  \sup_{w\in \Wbbb}   \Phi^{\lambda}_n(q_{\epol};w)
\end{align}

From <ref>, with probability $1-\delta$,  we have

\begin{align}\label{eq:martin2_q}
\forall w\in \Wbbb: |  \Phi_n(q_{\epol};w) -\Phi(q_{\epol};w)   |\lesssim C_1\{\eta \|w\|_2+\eta^2\}.
\end{align}

Here, we use $l(a_1,a_2):=a_1a_2,a_1=w(s,a),a_2=r-q(s,a)+\gamma q(s',\epol) $ is $C_1$-Lipschitz with respect to $a_1$ by defining $C_1=R_{\max}+(1+\gamma)C_{\Qbbb}$.  More specifically,

\begin{align*}
|l(a_1,a_2)-l(a'_1,a_2)|\lesssim C_1|a_1-a'_1|.
\end{align*}

\begin{align}
\sup_{w \in \Wbbb } \Phi^{\lambda}_n(q_{\epol};w) &=    \sup_{w \in \Wbbb } \braces{ \Phi_n(q_{\epol};w) -\lambda \|w\|^2_{2,n}} && \text{Definition}\nonumber \\
&\leq   \sup_{w \in \Wbbb } \braces{ \Phi(q_{\epol};w)+C_1\eta \|w\|_2+ C_1\eta^2 -\lambda\|w\|^2_{2,n}} && \text{From \cref{eq:martin2_q}}\nonumber \\
&\leq    \sup_{w \in \Wbbb } \braces{ \Phi(q_{\epol};w)+C_1\eta \|w\|_2+C_1\eta^2 -0.5\lambda\|w\|^2_2+\lambda\eta^2} && \text{From \cref{eq:martin_q}} \nonumber \\
&\lesssim   \sup_{w \in \Wbbb }  \braces{\Phi(q_{\epol};w)+(C^2_1/\lambda+C_1+\lambda) \eta^2}.  \label{eq:help3}
\end{align}

In the last line, we use a general inequality, $a,b>0$:

\begin{align*}
\sup_{f \in F}(a\|f\|-b\|f\|^2 )\leq a^2/4b.
\end{align*}

\begin{align*}
\sup_{w\in \Wbbb}\{ \Phi^{\lambda}_n(\hat q_{\MIL};w) \}&=     \sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w)+ \Phi_n(q_{\epol};w) -\lambda \|w\|^2_{2,n}\}\\
&\geq     \sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w) - 2\lambda \|w\|^2_{2,n}\}+  \inf_{w\in \Wbbb}\{ \Phi_n(q_{\epol};w) +\lambda  \|w\|^2_{2,n}\} \\
&=     \sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w) - 2\lambda \|w\|^2_{2,n}\}+  \inf_{-w\in \Wbbb}\{ \Phi_n(q_{\epol};-w) + \lambda \|w\|^2_{2,n}\} \\
&=     \sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w) - 2\lambda \|w\|^2_{2,n}\}+  \inf_{-w\in \Wbbb}\{-\Phi_n(q_{\epol};w) + \lambda \|w\|^2_{2,n}\} \\
&=     \sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w) - 2\lambda \|w\|^2_{2,n}\}-  \sup_{-w\in \Wbbb}\{\Phi_n(q_{\epol};w)- \lambda \|w\|^2_{2,n}\} \\
& =     \sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w)-2\lambda \|w\|^2_{2,n}\}-\sup_{w\in \Wbbb}\Phi^{\lambda}_n(q_{\epol};w).
\end{align*}

Here, we use $\Wbbb$ is symmetric.  Therefore,

\begin{align*}
\sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w)-2\lambda \|w\|^2_{2,n} \}&\leq \sup_{w\in \Wbbb}\braces{\Phi^{\lambda}_n(q_{\epol};w)}+    \sup_{w\in \Wbbb}\{ \Phi^{\lambda}_n(\hat q_{\MIL};w) \}\\
&\leq 2\sup_{w\in \Wbbb}\Phi^{\lambda}_n(q_{\epol};w)\\
& \lesssim   \sup_{w \in \Wbbb }  \braces{\Phi(q_{\epol};w)+(C^2_1/\lambda+C_1+\lambda)\eta^2}\\
&= (C^2_1/\lambda+C_1+\lambda)\eta^2.
\end{align*}

Second Step

\begin{align*}
\end{align*}

Suppose $\|w_{\hat q_{\MIL}}\|_2\geq \eta$, and let $\kappa\coloneqq \eta/\{2\|w_{\hat q_{\MIL}}\|_2\}\in [0,0.5]$. Then, noting $\Wbbb$ is star-convex,

\begin{align*}
\sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w)-2\lambda \|w\|^2_{2,n} \}\geq \kappa\{\Phi_n(\hat q_{\MIL},w_{\hat q_{\MIL}})-\Phi_n(q_{\epol},w_{\hat q_{\MIL}})\}-2\kappa^2\lambda\|w_{\hat q_{\MIL}}\|^2_{2,n}.
\end{align*}

Here, we use $\kappa w_{\hat q_{\MIL}}\in \Wbbb$.

\begin{align*}
\kappa^2\|w_{\hat q_{\MIL}}\|^2_{2,n}& \lesssim \kappa^2\{1.5\|w_{\hat q_{\MIL}}\|^2_{2}+0.5\eta^2\}  \tag{ \cref{eq:martin_q}} \\
& \lesssim \eta^2.  \tag{Definition of $\kappa$}
\end{align*}

\begin{align*}
\sup_{w\in \Wbbb}\{ \Phi_n(\hat q_{\MIL};w)- \Phi_n(q_{\epol};w)-2\|w\|^2_{2,n} \}\geq \kappa\{\Phi_n(\hat q_{\MIL},w_{\hat q_{\MIL}})-\Phi_n(q_{\epol},w_{\hat q_{\MIL}})\}-2\lambda \eta^2.
\end{align*}

Observe that

\begin{align*}
\Phi_n(q,w_q)-  \Phi_n(q_{\epol},w_q)&=-\E_n[\{q(s,a)-q_{\epol}(s,a)-\gamma q(s',\epol)+ \gamma q_{\epol}(s',\epol)\}w_q(s,a)].
\end{align*}

Therefore, from <ref> noting $\eta$ upper-bounds the critical radius of $\Gcal_q$, for any $ q\in \Qbbb$,

\begin{align*}
&|\Phi_n(q,w_q)-  \Phi_n(q_{\epol},w_q)-\{\Phi(q,w_q)-  \Phi(q_{\epol},w_q)\}|\\
&=|\E_n[\{-q(s,a)+q_{\epol}(s,a)+\gamma q(s',\epol)- \gamma q_{\epol}(s',\epol)\}w_q(s,a)  ]\\ &-\E[\{-q(s,a)+q_{\epol}(s,a)+\gamma q(s',\epol)- \gamma q_{\epol}(s',\epol)\}w_q(s,a))  ]  |\\
&\leq (\eta\E[\{-q(s,a)+q_{\epol}(s,a)+\gamma q(s',\epol)- \gamma q_{\epol}(s',\epol)\}^2w^2_q(s,a)]^{1/2}+\eta^2)\\
&\lesssim (\eta C_1\|w_q\|_2+\eta^2).
\end{align*}

Here, we invoke <ref> by treating $l(a_1,a_2)=a_1,\,a_1= \{q(s,a)-q_{\epol}(s,a)-\gamma q(s',\epol)+ \gamma q_{\epol}(s',\epol)\}w_q(s,a)\}$.

\begin{align*}
\kappa\{\Phi_n(\hat q_{\MIL},w_{\hat q_{\MIL}})-  \Phi_n(q_{\epol},w_{\hat q_{\MIL}})\}& \geq  \kappa\{\Phi(\hat q_{\MIL},w_{\hat q_{\MIL}})-  \Phi(q_{\epol},w_{\hat q_{\MIL}})\}-\kappa(C_1\eta\|w_{\hat q_{\MIL}}\|_2+\eta^2). \tag{$\kappa\leq 0.5$} \\
& \geq\kappa\{\Phi(\hat q_{\MIL},w_{\hat q_{\MIL}})-  \Phi(q_{\epol},w_{\hat q_{\MIL}})\}-\kappa(C_1\eta\|w_{\hat q_{\MIL}}\|_2)-0.5\eta^2 \\
&\overset{\text{(a)}}= \kappa\E[w_{\hat q_{\MIL}}(s,a)\Tcal_{\gamma}(\hat q_{\MIL}-q_{\epol})(s,a)]-\kappa(C_1\eta\|w_{\hat q_{\MIL}}\|_2)-0.5\eta^2 \\
&= \frac{\eta}{2\|w_{\hat q_{\MIL}}\|}\{C^{-1}_{\xi}\|w_{\hat q_{\MIL}}\|^2_2-C_1\eta\|w_{\hat q_{\MIL}}\|_2\}-0.5\eta^2 \\
&\geq 0.5\eta \|\Tcal_{\gamma}(\hat q_{\MIL}-q_{\epol})\|_2-(0.5+C_1)\eta^2.
\end{align*}

For (a), we use

\begin{align*}
\Phi(\hat q_{\MIL},w_{\hat q_{\MIL}})-  \Phi(q_{\epol},w_{\hat q_{\MIL}})&=\E[w_{\hat q_{\MIL}}(s,a)\{-\hat q_{\MIL}(s,a)+q_{\epol}(s,a)+\gamma  \hat q_{\MIL}(s',\epol)- \gamma q_{\epol}(s',\epol)\}]\\
&= \E[w_{\hat q_{\MIL}}(s,a)\Tcal_{\gamma}(\hat q_{\MIL}-q_{\epol})(s,a)].
\end{align*}

Combining all results

Thus, $\|w_{\hat q_{\MIL}}\|\leq \eta$ or

\begin{align*}
\eta \|\Tcal_{\gamma}(\hat q_{\MIL}- q_{\epol})\|_2-(1+C_1+\lambda )\eta^2\lesssim (C_1+C_1^2/\lambda+\lambda)\eta^2.
\end{align*}

Therefore, we have

\begin{align*}
\|\Tcal_{\gamma}(\hat q_{\MIL}- q_{\epol})\|_2\leq C^{-1}_{\zeta}\eta
\end{align*}

\begin{align*}
\|\Tcal_{\gamma}(\hat q_{\MIL}- q_{\epol})\|_2\lesssim (1+C_1+\lambda+C^2_1/\lambda)  \eta.
\end{align*}

This concludes

\begin{align*}
\|\Tcal_{\gamma}(\hat q_{\MIL}- q_{\epol})\|_2\lesssim \prns{1+C_1+\lambda+C^2_1/\lambda+C^{-1}_{\xi}} \eta.
\end{align*}

\begin{align*}
\Xi(w,q)  &=\E[w(s,a)\{-q(s,a)+\gamma q(s',\epol) \}+(1-\gamma)\E_{d_0}[q(s_0,\epol)] ],\\
\Xi_n(w,q)&=\E_n[w(s,a)\{-q(s,a)+\gamma q(s',\epol) \}+(1-\gamma)\E_{d_0}[q(s_0,\epol)] ],\\
\Xi^{\lambda}(w,q) &=    \Xi^{\lambda}(w,q)-\lambda \|q(s,a)-\gamma q(s',\epol) \|^2_2,\\
\Xi^{\lambda}_n(w,q) &=    \Xi^{\lambda}_n(w,q)-\lambda\|q(s,a)-\gamma q(s',\epol) \|^2_{2,n}.
\end{align*}

From <ref>, we have

\begin{align}\label{eq:q_uni}
\forall q\in \Qbbb, |\|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n}-\|-q(s,a)+\gamma q(s',\epol)\|^2_2  |\leq 0.5\|-q(s,a)+\gamma q(s',\epol)\|^2_2+0.5\eta^2,
\end{align}

for our choice of $\eta:=\eta_n+c_0\sqrt{\log(c_1/\delta)/n}$ noting $\eta_n$ upper bounds the critical of $\Gcal_{w1}$.

First Step
By definition of $\hat w_{\MIL}$ and $w_{\epol}\in \Wbbb$, we have

\begin{align}\label{eq:help4}
\sup_{q\in \Qbbb}\Xi^{\lambda}_n(\hat w_{\MIL}; q)\leq     \sup_{q\in \Qbbb}\Xi^{\lambda}_n(w_{\epol}; q).
\end{align}

From <ref>, with probability $1-\delta$, we have

\begin{align*}
\forall q\in \Qbbb: |\Xi_n(w_{\epol};q)- \Xi(w_{\epol};q)|\lesssim C_{\Wbbb}\{\eta \|q(s,a)-\gamma q(s',\epol)\|_2 +\eta^2 \}.
\end{align*}

noting $\eta$ upper-bounds the critical radius of $\Gcal_{w1}$. Here, we use $l(a_1,a_2) (a_1=-q'(s,a)+\gamma q(s',\epol),a_2=w(s,a))$ is $C_{\Wbbb}$-Lipschitz with respect to $a_1$ noting $w(s,a)$ is in $[-C_{\Wbbb}, C_{\Wbbb}]$. More specifically,

\begin{align*}
| l(a_1,a_2)- l(a'_1,a_2) |\leq |a_1-a'_1|C_{\Wbbb}.
\end{align*}

\begin{align*}
\sup_{q\in \Qbbb}  \Xi^{\lambda}_n(w_{\epol},q)&=  \sup_{q\in \Qbbb}\{  \Xi_n(w_{\epol},q)-\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}\\
&\leq   \sup_{q\in \Qbbb}\{  \Xi(w_{\epol},q)+C_{\Wbbb}\{\eta \|-q(s,a)+\gamma q(s',\epol)\|_2 +\eta^2 \}  -\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}     \\
&\leq   \sup_{q\in \Qbbb}\{  \Xi(w_{\epol},q)+C_{\Wbbb}\{\eta \|-q(s,a)+\gamma q(s',\epol)\|_2 +\eta^2 \}  -0.5\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2}+\lambda \eta^2\}     \\
&\lesssim   \sup_{q\in \Qbbb}\{  \Xi(w_{\epol},q)+(\lambda +C^2_{\Wbbb}/\lambda+C_{\Wbbb})\eta^2\}.
\end{align*}

In the last line, we use a general inequality $a,b\geq 0$,

\begin{align*}
\sup_{f\in \Fcal}(a\|f\|-b\|f\|^2)\leq a^2/4b.
\end{align*}

\begin{align*}
&\sup_{q\in \Qbbb}  \Xi^{\lambda}_n(\hat w_{\MIL},q)\\
&= \sup_{q\in \Qbbb}\{\Xi_n(\hat w_{\MIL},q)-\Xi_n(w_{\epol},q)+\Xi_n(w_{\epol},q)-\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}\\
&\geq \sup_{q\in \Qbbb}\{\Xi_n(\hat w_{\MIL},q)-\Xi_n(w_{\epol},q)-2\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}+\inf_{q\in \Qbbb}\{\Xi_n(w_{\epol},q)+\lambda \|q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}\\
&= \sup_{q\in \Qbbb}\{\Xi_n(\hat w_{\MIL},q)-\Xi_n(w_{\epol},q)-2\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}+\inf_{-q\in \Qbbb}\{\Xi(w_{\epol},-q)+\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}\\
&= \sup_{q\in \Qbbb}\{\Xi_n(\hat w_{\MIL},q)-\Xi_n(w_{\epol},q)-2\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}+\inf_{-q\in \Qbbb}\{-\Xi_n(w_{\epol},q)+\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}\\
&= \sup_{q\in \Qbbb}\{\Xi_n(\hat w_{\MIL},q)-\Xi_n(w_{\epol},q)-2\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}-\sup_{-q\in \Qbbb}\{\Xi_n(w_{\epol},q)-\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}\\
&= \sup_{q\in \Qbbb}\{\Xi_n(\hat w_{\MIL},q)-\Xi_n(w_{\epol},q)-2\lambda \|-q(s,a)+\gamma q(s',\epol) \|^2_{2,n} \}-\sup_{q\in \Qbbb}\{     \Xi^{\lambda}_n(w_{\epol},q) \}.
\end{align*}

Here, we use $\Qbbb$ is symmetric. Therefore,

\begin{align*}
\sup_{q\in \Qbbb}\{\Xi_n(\hat w_{\MIL};q)- \Xi(w_{\epol};q)-2\lambda \| -q(s,a)+\gamma q(s',\epol)\|^2_{2,n}\}& \leq \{\sup_{q\in \Qbbb}  \Xi^{\lambda}_n(\hat w_{\MIL},q)\}+\sup_{q\in \Qbbb}\{     \Xi^{\lambda}_n(w_{\epol},q) \}\\
&\leq  2 \sup_{q\in \Qbbb}\{     \Xi^{\lambda}_n(w_{\epol},q) \}\\
&\leq  2 \sup_{q\in \Qbbb}\{     \Xi(w_{\epol},q)+(\lambda +C^2_{\Wbbb}/\lambda+C_{\Wbbb})\eta^2) \}\\
&= (\lambda +C^2_{\Wbbb}/\lambda+C_{\Wbbb})\eta^2.
\end{align*}

Second Step

Define $q_{w}=C_{\xi}\Tcal'_{\gamma}(w-w_{\epol})$. Suppose $\|q_{\hat w_{\MIL}}\|\geq \eta$, and let $\kappa=\eta/\{2\|q_{\hat w_{\MIL}} \|_2\}\in [0,0.5]$. Then, noting $\Qbbb$ is star-convex and $C_{\xi}\Tcal'_{\gamma}(\Wbbb-w_{\epol})\subset \Qbbb$,

\begin{align*}