&\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}\}\\
&\geq \kappa\{\Xi_n(\hat w_{\MIL};q_{\hat w_{\MIL}})- \Xi(w_{\epol};q_{\hat w_{\MIL}})\} -2\kappa^2\lambda\|q_{\hat w_{\MIL}}(s,a)-\gamma q_{\hat w_{\MIL}}(s',\epol)\|^2_{2,n}.
\end{align*}

Here, we use $\kappa q_{\hat w_{\MIL}}\in \Qbbb$. Then, from <ref>,

\begin{align*}
\kappa^2\|-q_{\hat w_{\MIL}}(s,a)+\gamma q_{\hat w_{\MIL}}(s',\epol)\|^2_{2,n} & \lesssim \kappa^2\{ 1.5\|-q_{\hat w_{\MIL}}(s,a)+\gamma q_{\hat w_{\MIL}}(s',\epol)\|^2_{2}+\eta^2\} \\
&\lesssim \eta^2. \tag{From $\|-q_{\hat w_{\MIL}}(s,a)+\gamma q_{\hat w_{\MIL}}(s',\epol)\|^2_{2}\lesssim \|q_{\hat w_{\MIL}}\|^2_2$, which will be explained soon. }\
\end{align*}

\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}\}\}\geq \kappa\{\Xi_n(\hat w_{\MIL};q_{\hat w_{\MIL}})- \Xi(w_{\epol};q_{\hat w_{\MIL}})\} -2\lambda \eta^2.
\end{align*}

Observe that

\begin{align*}
\Xi_n( w;q_w)- \Xi(w_{\epol};q_w)=\E_n[(w(s,a)-w_{\epol}(s,a))(-q_{w}(s,a)+\gamma q_{w}(s',\epol))  ].
\end{align*}

Therefore, from <ref>, noting $\eta$ upper bounds the critical radius of $\Gcal_{w2}$,
regarding $l(a_1,a_2)=a_1,a_1=(w(s,a)-w_{\epol}(s,a))(q_{w}(s,a)-\gamma q_{w}(s',\epol)) $, for any $w\in \Wbbb$, we have

\begin{align*}
& |   \Xi_n( w;q)- \Xi_n(w_{\epol};q)-\{\Xi( w;q)- \Xi(w_{\epol};q)\}|\\
&\leq (\eta  \E[\{(w(s,a)-w_{\epol}(s,a))(q_{w}(s,a)-\gamma q_{w}(s',\epol))\}^{2}]^{1/2}+\eta^2)\\
&\lesssim (\eta  \E[\{q_{w}(s,a)-\gamma q_{w}(s',\epol)\}^2]^{1/2}C_{\Wbbb} +\eta^2)=(\eta  \|\{q_{w}(s,a)-\gamma q_{w}(s',\epol)\}\|_2C_{\Wbbb} +\eta^2)\\
&\leq (\eta  \{\|q_w(s,a)\|_2+\gamma\|q_w(s',\epol)\|_2 \}C_{\Wbbb}  +\eta^2)\\
&= (\eta  \{\|q_w(s,a)\|_2+\gamma \sqrt{C_mC_{\eta}}\|q_w(s,a)\|_2 \}C_{\Wbbb}  +\eta^2).
\end{align*}

We use

\begin{align*}
&\E[q^2_w(s',\epol)]=\E[\E_{a'\sim \epol(a'|s')}[q_w(s',a')]^2]\leq  \E[\E_{a'\sim \epol(a'|s')}[q^2_w(s',a')]] \tag{Jensen}\\
&=\E_{s'\sim p_{S'}(s),a'\sim \epol(a'|s')}[q^2_w(s',a')]]\\
&=\E_{s\sim p_{S}(s),a\sim \bpol(a|s)}[q^2_w(s',a')]]C_mC_{\eta}=\|q_w(s,a)\|^2_2C_mC_{\eta}. \tag{ $P_{S'}(s)/P_{S}(s)\leq C_m,\epol(a|s)/\bpol(a|s)\leq C_{\eta}$}
\end{align*}

\begin{align*}
&\kappa\{  \Xi_n(\hat w_{\MIL};q_{\hat w_{\MIL}})- \Xi_n(w_{\epol};q_{\hat w_{\MIL}})\}\\
& \geq \kappa\{\Xi(\hat w_{\MIL};q_{\hat w_{\MIL}})- \Xi(w_{\epol};q_{\hat w_{\MIL}})\}-\kappa(\eta  \|q_{\hat w_{\MIL}}\|_2 (1+\gamma \sqrt{C_mC_{\eta}})C_{\Wbbb} +\eta^2 )  && \\
&\geq \kappa\{\Xi( \hat w_{\MIL};q_{\hat w_{\MIL}})- \Xi(w_{\epol};q_{\hat w_{\MIL}})\}-\kappa\eta  \|q_{\hat w_{\MIL}}\|_2  (1+\gamma \sqrt{C_mC_{\eta}})C_{\Wbbb} -0.5\eta^2 && \text{Use $\kappa\leq 0.5$} \\
&\overset{(a)}{=} \kappa C^{-1}_{\xi}\|q_{\hat w_{\MIL}}\|^2_2    -\kappa\eta  \|q_{\hat w_{\MIL}}\|_2 (1+\gamma \sqrt{C_mC_{\eta}})C_{\Wbbb}  )-0.5\eta^2 && \\
&=\frac{\eta}{2\|q_{\hat w_{\MIL}}\|_2 }\{ C^{-1}_{\xi}\|q_{\hat w_{\MIL}}\|^2_2 -(1+\gamma \sqrt{C_mC_{\eta}})C_{\Wbbb} \eta \|\Tcal'_{\gamma}(\hat w_{\MIL}-w_{\epol})\|_2\}-0.5\eta^2 && \\
&=0.5 \eta  C^{-1}_{\xi}\|q_{\hat w_{\MIL}}\|_2  -\{(0.5+0.5\gamma \sqrt{C_mC_{\eta}})C_{\Wbbb}+0.5\}\eta^2 .
\end{align*}

Regarding (a), we use

\begin{align*}
\Xi( w;q_{ w})- \Xi(w_{\epol};q_{w})&=\E[(w(s,a)-w_{\epol}(s,a))(-q_{w}(s,a)+\gamma q_{w}(s',\epol))]\\
\end{align*}

Combining all results

Thus, $C_{\zeta}\|\Tcal'_{\gamma}(\hat w_{\MIL}-w_{\epol})\|_2=\|q_{\hat w_{\MIL}}\|_2\leq \eta$ or

\begin{align*}
C_{\xi}\eta  \|\Tcal'_{\gamma}(\hat w_{\MIL}-w_{\epol})\|_2-\{(1+\gamma \sqrt{C_mC_{\eta}})C_{\Wbbb}+1\}\eta^2 \lesssim  (\lambda+C^2_{\Wbbb}/\lambda+C_{\Wbbb})\eta^2.
\end{align*}

\begin{align*}
\|\Tcal'_{\gamma}(\hat w_{\MIL}-w_{\epol})\|_2\leq \braces{1+\lambda+C^2_{\Wbbb}/\lambda+C_{\Wbbb}+\gamma \sqrt{C_mC_{\eta}}C_{\Wbbb}+1/C_{\zeta}}\eta.
\end{align*}

The proof is deferred to <ref>.

The proof is deferred to <ref>.

The proof is done as in the proof of <ref>.

§.§ Proof of <ref>

Recall we use sample splitting. The estimator is defined as

\begin{align*}
\E_{n_1}[\phi(\hat w^{\MIL}_0,\hat q^{\MIL}_0)]+ \E_{n_0}[\phi(\hat w^{\MIL}_1,\hat q^{\MIL}_1)],
\end{align*}

where $\E_{n_1}$ is the empirical average over $\Dcal_1$ and $\E_{n_0}$ is the empirical average over $\Dcal_0$. We define $\phi(s,a,r,s';w,q)=w(s,a)(r-q(s,a)+\gamma q(s',\epol))+\E_{d_0}[q(s_0,\epol)]$. Then, we have

\begin{align}
|\E_{n_1}[\phi(\hat w^{\MIL}_0,\hat q^{\MIL}_0)]-J|&\leq |(\E_{n_1}-\E)[\phi(\hat w^{\MIL}_0,\hat q^{\MIL}_0)|\Dcal_0]-(\E_{n_1}-\E)[\phi(w_{\epol},q_{\epol})|\Dcal_0]| \label{eq:first}\\
&+|\E[\phi(\hat w^{\MIL}_0,\hat q^{\MIL}_0)-\phi(w_{\epol},q_{\epol})|\Dcal_0]| \label{eq:second}\\
&+|\E_{n_1}[\phi(w_{\epol},q_{\epol})]-J|. \label{eq:third}
\end{align}

Recall with probability $1-2\delta'$, we have

\begin{align*}
&\|\hat w^{\MIL}_0-w_{\epol}\|_2\lesssim \eta_{w}\times C_{\iota}C^{*}_w,\,\|\Tcal'_{\gamma}(\hat w^{\MIL}_0-w_{\epol})\|_2\lesssim \eta_{w}\times C^{*}_w,\\
&\|\hat q^{\MIL}_0-q_{\epol}\|_2\lesssim \eta_{q}\times C_{\iota}C^{*}_q,\,\|\Tcal_{\gamma}(\hat q^{\MIL}_0-q_{\epol})\|_2\lesssim \eta_{q}\times C^{*}_q.
\end{align*}

First Term

We analyze the first term (<ref>). For simplicity, we write $\hat w^{\MIL}_0,\hat q^{\MIL}_0$ as  $\hat w,\hat q$.

\begin{align}
&(\E_{n_1}-\E)[\phi(\hat w,\hat q)-\phi(w_{\epol},q_{\epol})|\Dcal_0] \nonumber\\
&=(\E_{n_1}-\E)[(\hat w(s,a)-w_{\epol}(s,a))(-\hat q(s,a)+\gamma \hat v(s')+q_{\epol}(s,a)-\gamma v_{\epol}(s') )|\Dcal_0] \label{eq:first_1}\\
&+(\E_{n_1}-\E)[(\hat w(s,a)-w_{\epol}(s,a))(r-q_{\epol}(s,a)+\gamma v_{\epol}(s')) |\Dcal_0] \label{eq:first_2} \\
&+(\E_{n_1}-\E)[w_{\epol}(s,a)\{-\hat q(s,a)+q_{\epol}(s,a)+\gamma \hat v(s')-\gamma v_{\epol}(s')\}|\Dcal_0]\label{eq:first_3}.
\end{align}

From Berstein's inequality, with probability $1-\delta'$, regarding the term <ref> (we can do since $\hat w$ only depend on $\Dcal_0$), we have

\begin{align*}
&(\E_{n_1}-\E)[(\hat w(s,a)-w_{\epol}(s,a))(-\hat q(s,a)+\gamma \hat v(s')+q_{\epol}(s,a)-\gamma v_{\epol}(s') )|\Dcal_0]\\
&\leq \sqrt{2\frac{\mathrm{var}[(\hat w(s,a)-w_{\epol}(s,a))(-\hat q(s,a)+\gamma \hat v(s')+q_{\epol}(s,a)-\gamma v_{\epol}(s') )]\log(1/\delta')}{n_1}}+\frac{2C_{\Wbbb_1}C_{\Qbbb_2}\log(1/\delta')}{3n_1}\\
&\lesssim \sqrt{2\frac{\|\hat w-w_{\epol}\|^2_2\{C_{\Qbbb_2}\}^2 \log(1/\delta')}{n_1}}+\frac{2C_{\Wbbb_1}C_{\Qbbb_2}\log(1/\delta')}{3n_1}.
\end{align*}

The second term (<ref>) is similarly upper-bounded. With probability $1-\delta'$, The third term (<ref>) is upper-bounded as follows:

\begin{align*}
&(\E_{n_1}-\E)[w_{\epol}(s,a)\{-\hat q(s,a)+q_{\epol}(s,a)+\gamma \hat v(s')-\gamma v_{\epol}(s')\}|\Dcal_0]\\
&\leq \sqrt{\frac{2\var[w_{\epol}(s,a)\{-\hat q(s,a)+q_{\epol}(s,a)+\gamma \hat v(s')-\gamma v_{\epol}(s')\}]\log(1/\delta')}{n_1}}+\frac{2C_{\Wbbb_1}C_{\Qbbb_2}\log(1/\delta')}{3n_1}\\
&\leq \sqrt{\frac{2\|\hat q-q_{\epol}\|^2_2C^2_{\Wbbb_1}(1+C_{\eta}C_m)\log(1/\delta')}{n_1}}+\frac{2C_{\Wbbb_1}C_{\Qbbb_2}\log(1/\delta')}{3n_1}.
\end{align*}

We use

\begin{align*}
&\var[w_{\epol}(s,a)\{-\hat q(s,a)+q_{\epol}(s,a)+\gamma \hat v(s')-\gamma v_{\epol}(s')\}|\Dcal_0]\\
&\lesssim C^2_{\Wbbb_1}\{\var[ -\hat q(s,a)+q_{\epol}(s,a) ]+\var[\gamma \hat v(s')-\gamma v_{\epol}(s')  ]\}\\
&\lesssim C^2_{\Wbbb_1}\{\var[ -\hat q(s,a)+q_{\epol}(s,a) ]+C_{\eta}C_m\var[ -\hat q(s,a)+q_{\epol}(s,a) ]\}.
\end{align*}

Finally, by combining the all arguments, with probability $1-3\delta'$,

\begin{align*}
&|(\E_{n_1}-\E)[\phi(\hat w,\hat q)-\phi(w_{\epol},q_{\epol})|\Dcal_0]| \nonumber\\
&\lesssim \sqrt{\frac{\{\|\hat w-w_{\epol}\|^2_2\{C_{\Qbbb_2}\}^2 +\|\hat q-q_{\epol}\|^2_2C^2_{\Wbbb_1}(1+C_{\eta}C_m)  \} \log(1/\delta')}{n_1}}+\frac{2C_{\Wbbb_1}C_{\Qbbb_2}\log(1/\delta')}{3n_1}\\
&\lesssim  (C^{*}_{w}C_{\Qbbb_2}C_{\iota}\eta_w+C^{*}_qC_{\Wbbb_1}C_{\iota}\eta_q\sqrt{1+C_{\eta}C_m})\sqrt{\frac{\log(1/\delta')}{n_1}}+\frac{C_{\Wbbb_1}C_{\Qbbb_2}\log(1/\delta')}{n_1}
\end{align*}

Second Term

We analyze the second term (<ref>). For simplicity, we write $\hat w^{\MIL}_0,\hat q^{\MIL}_0$ as  $\hat w,\hat q$. Then,

\begin{align*}
& |\E[\phi(\hat w,\hat q)-\phi(w_{\epol},q_{\epol})]|=|\E[(\hat w-w_{\epol})\Tcal_{\gamma}(\hat q-q_{\epol})]| \\
&\leq \|\hat w-w_{\epol}\|_2\|\Tcal_{\gamma}(\hat q-q_{\epol})\|_2 \leq \eta_{w}\eta_qC^{*}_{w}C^{*}_{q}C_{\iota}.
\end{align*}

Here, we use

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

Combining All terms
With probability $1-(\delta+10\delta')$ ($2\times 2\delta'+2\times 3\delta'+\delta$),

\begin{align*}
& \E_{n_1}[\phi(\hat w^{\MIL}_0,\hat q^{\MIL}_0)]+ \E_{n_0}[\phi(\hat w^{\MIL}_1,\hat q^{\MIL}_1)]\\
&\leq  \E_{n}[\phi(w_{\epol},q_{\epol})]-\E[\phi(w_{\epol},q_{\epol})]\\
&+ 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')}{n}}\\
&\leq \sqrt{2\frac{\mathrm{var}[\phi(w_{\epol},q_{\epol})]\log(1/\delta)}{n}}\\
&+ 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}}.
\end{align*}

for  some universal constant $c_0$.

Since $q_{\epol}\in \Qbbb_2$, for any $q\in \Qbbb_2$, there exists $\theta$ s.t. $q-q_{\epol}=\theta^{\top}\phi$. Then,
\Bcal q-q=\Tcal_{\gamma}(q-q_{\epol})=\theta^{\top}(\gamma \Tcal-I)\phi=\theta^{\top}(\gamma M^{\top}_{\epol}-I)\phi.$$

\begin{align*}
\frac{\|q-q_{\epol}\|^2_2}{\|\Bcal q-q\|^2_2}&\leq \sup_{\theta \in \mathbb{R}^d}\frac{\theta^{\top}\E[\phi(s,a)\phi^{\top}(s,a)]\theta}{\theta^{\top}(\gamma M^{\top}_{\epol}-I)\E[\phi(s,a)\phi^{\top}(s,a)](\gamma M^{\top}_{\epol}-I)^{\top}\theta}\\
&=\sup_{\theta\in \mathbb{R}^d}\frac{\theta^{\top}X\theta}{\theta^{\top}(\gamma M_{\epol}-I)X(\gamma M_{\epol}-I)^{\top}\theta}\\
&=\sup_{\theta\in \mathbb{R}^d}\frac{\theta^{\top}X\theta}{\theta^{\top}\bar M_{\epol}X (\bar M_{\epol})^{\top}\theta}\\
&\leq \sigma_{\max}(\{\bar M_{\epol}X (\bar M_{\epol})^{\top}\}^{-1/2}X\{M_{\epol}X (\bar M_{\epol})^{\top}\}^{-1/2}).
\end{align*}

Since $w_{\epol}\in \Wbbb_1$, for any $w\in \Wbbb_1$, there exists $\theta$ s.t. $w-w_{\epol}=\theta^{\top}\phi$. Then,
\Bcal'w-w=\Tcal'_{\gamma}(w-w_{\epol})=\theta^{\top}(\gamma \Tcal'-I)\phi=\theta^{\top}(\gamma M'^{\top}_{\epol}-I)\phi.$$

\begin{align*}
\frac{\|w-w_{\epol}\|^2_2}{\|\Bcal w-w\|^2_2}&\leq \sup_{\theta\in \mathbb{R}^d}\frac{\theta^{\top}X\theta}{\theta^{\top}(\gamma M'^{\top}_{\epol}-I)X(\gamma M'^{\top}_{\epol}-I)^{\top}\theta}\\
&=\sup_{\theta\in \mathbb{R}^d}\frac{\theta^{\top}X\theta}{\theta^{\top}\bar M'_{\epol} X (\bar M'_{\epol})^{\top}\theta}\\
&\leq \sigma_{\max}(\{\bar M'_{\epol} X (\bar M'_{\epol})^{\top}\}^{-1/2}X\{\bar M'_{\epol} X (\bar M'_{\epol})^{\top}\}^{-1/2}).
\end{align*}

Recall <ref>.  The matrix $\E[\phi\phi^{\top}]$, i.e., $X$, is defined as a matrix, whose $(i,i)$-th entry corresponding $x_i\in \Xcal$, is $\E[I((s,a)=x_i)]$, i.e., $d_{\bpol}(x_i)$. Besides,

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

All of matrices are non-singular. Thus, the assumptions in <ref> are satisfied.

Recall we use sample splitting. The estimator is defined as

\begin{align*}
\E_{n_1}[\phi(\hat w,\hat q)]+ \E_{n_2}[\phi(\hat w,\hat q)].
\end{align*}

We define $\phi(s,a,r,s';w,q)=w(r-q(s,a)+\gamma q(s',\epol))+\E_{d_0}[q(s_0,\epol)]$. Then, we have

\begin{align}
|\E_{n_1}[\phi(\hat w,\hat q)]-J|&\leq |(\E_{n_1}-\E)[\phi(\hat w,\hat q)|\Dcal_0]-(\E_{n_1}-\E)[\phi(w_{\epol},q_{\epol})|\Dcal_0]| \label{eq:first_final}\\
&+|\E[\phi(\hat w,\hat q)-\phi(w_{\epol},q_{\epol})|\Dcal_0]| \label{eq:second_final}\\
&+|\E_{n_1}[\phi(w_{\epol},q_{\epol})]-J|. \label{eq:third_final}
\end{align}

As in the proof of <ref>, it is proved that <ref> are $\op(1)$. From CLT, the third term weakly converges to a normal distribution

\begin{align*}\ts
\Ncal(0,\E[w^2_{\epol}(s,a)\{r-q(s,a)+q(s',\epol)\}^2]).
\end{align*}

From Slutsky's theorem, the final statement is concluded.

§.§ Proof of <ref>

§.§ Proof of <ref>

§.§ Proof of <ref>

§.§ Proof of <ref>

§.§ Proof of <ref>

* Add the following in <ref> "[<cit.> give different doubly robust estimators, which include cumulative importance ratios. 28 gives a doubly robust estimator for time-varying MDPs. 41 gives a closely related doubly robust estimator. We present this estimator in <ref>.] "   <ref>.

* Bring back the inference stuff and the sample splitting procedure from <ref> to <ref>.

* Write the norm theorem ($L^2$, Bellmaan residual errors) more explicitly.

* Write "This types of estimators are generally called sieve estimators <cit.>. We also present the results when using linear sieves such as polynomials and splines in <ref>".

* Bring back neural networks theorem.

* I need to add the following in <ref>

Note if we assume pseudo- instead of in <ref>, the rates of $L^2$-errors are directly obtained; thus, we don't need the recovery assumption. From <ref>, which imply pseudo hold in a tabular case, the efficiency in a tabular case is also proved from this direction.

* Need to add as follows in <ref>: We explain a general doubly robust meta-algorithm in 27, which includes MIL. Then, we introduce some operators. Doubly robust meta-algorithm was proposed in 27:

\begin{align*}
\ts  \hat J=\E_n[\hat w(s,a)\{r-\hat q(s,a)+\gamma \hat v(s')\}]+(1-\gamma)\E_{d_0}[\hat v(s_0)], \,\hat v(s)=\hat q(s,\epol),
\end{align*}

given any reasonable estimators for $\hat w(s,a)$ and $\hat q(s,a)$. MIL also takes this form, and they are regarded as specific cases. 27 proved that their meta algorithm is "doubly robust” in the sense that as long as $\hat w=w_{\epol}+\op(1)$ or $\hat q=q_{\epol}+\op(1)$, then $\hat J= J(\epol)+\op(1)$. However, this result does not exactly show "genuine double robustness” since we need more essential conditions beyond the realizability $w_{\epol}\in \Wbbb,q_{\epol}\in\Qbbb$ to state $\hat w=w_{\epol}+\op(1)$ or $\hat q=q_{\epol}+\op(1)$. For example, we need completeness regarding $\Qbbb$ to ensure $\hat q=q_{\epol}+\op(1)$ in FQI [34]. On the other hand, in a bandit setting, the is enough to ensure $\hat q=q_{\epol}+\op(1)$. The same argument is applied to  $\hat w=w_{\epol}+\op(1)$. This describes difficulties of OPE in RL comparing to a bandit setting. In our work, the goal is providing genuine sufficient conditions to estimate $J(\epol),w_{\epol},q_{\epol}$.

DICE methodsongoing

Comparison with DICE etc. notations will be fixed later for consistency

We now summarize the different methods of estimating Q-function and weight function. We present our comparison using the matrix formulation, where $q_\pi$ denotes the $|\Scal| \Acal| \times 1$ vector of Q-function and $w_\pi$ and $d_\pi$ denote the $1 \times |\Scal| \Acal|$ vectors of weight function and density function. Also let $\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}))$. We also use $D_\mu$ to denote an $|\Scal| \Acal| \times |\Scal| \Acal|$ diagonal matrix whose $s,a$-th diagonal element is $\mu(s,a)$.

Using this matrix formulation, we can write the Bellman function of $q_\pi$ and $d_\pi$ as follows, which is the first principle of estimating Q-function and weight function over all these methods,

\begin{align}
% \label{eq:dpiBE}
d_\pi (I - \gamma \Pcal^\pi) = &~ (1 - \gamma) d_0^\pi,  \tag*{[Bellman equation of $d_\pi$]}
\\
% \label{eq:qBE}
(I - \gamma \Pcal^\pi) q_\pi = &~ R^\pi.  \qquad  \tag*{[Bellman equation of $q_\pi$]}
\end{align}

When considering the the weight function $w_\pi$ ($\coloneqq d_\pi / \mu$), we have

\begin{align}
w_\pi \Dcal_\mu (I - \gamma \Pcal^\pi) = &~ (1 - \gamma) d_0^\pi.  \quad  \tag*{[Bellman equation of $w_\pi$]}
\end{align}

DualDICE [35] calculates $w_\pi$ by designing a objective whose gradient is connected with the Bellman residual on $w_\pi$. That is, if we define $\nu \coloneqq (I - \gamma \Pcal^\pi)^{-1} w_\pi^\top$, then we can rewrite the Bellman equation of $w_\pi$ as

\begin{align*}
\nu^\top (I - \gamma \Pcal^\pi)^\top \Dcal_\mu (I - \gamma \Pcal^\pi) = &~ (1 - \gamma) d_0^\pi.
\end{align*}

Note that, the equality holds if and only if $\nu$ is the stationary point of the following objective (gradient equals to zero), which is exactly the objective used in [35],

\begin{align*}
\Lcal_{\text{DualDICE}}(\nu) \coloneqq \frac{1}{2} \nu^\top (I - \gamma \Pcal^\pi)^\top \Dcal_\mu (I - \gamma \Pcal^\pi) \nu - (1 - \gamma) d_0^\pi \nu.
\end{align*}

GenDICE, GradientDICE, Policy-Evaluation Variant of SBEED or MSBO
This line of methods minimize the Bellman residual of $q_\pi$ or $w_\pi$ using Fenchel duality. Note that, although SBEED and MSBO are designed for policy optimization, they can be adopted to policy evaluation directly by changing the Bellman optimality operator to the Bellman operator.

The objective of GenDICE [53] is built over $D_\phi(w_\pi \Dcal_\mu \| \gamma w_\pi \Dcal_\mu \Pcal^\pi + (1 - \gamma) d_0^\pi)$, where $D_\phi$ is the $f$-divergence associated with a convex function $\phi$.

GradientDICE <cit.> extends GenDICE using a linear parametrization, which addresses the convergence issue in GenDICE. GradientDICE eliminates the nonlinearity in GenDICE by replacing the use of $f$-divergence GenDICE to an objective of a weighted 2-norm, and proposing an objective based on $\|w_\pi \Dcal_\mu - \gamma w_\pi \Dcal_\mu \Pcal^\pi - (1 - \gamma) d_0^\pi\|_{\Dcal_\mu^{-1}}$ (plus the regularization term).

SBEED <cit.>

MSBO [48]

MWL, MQL [43]