The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
65,168 characters
On Well-posedness and Minimax Optimal Rates of Nonparametric $Q$-function Estimation in Off-policy EvaluationAuthor names are sorted alphabetically
\def\spacingset#1{\renewcommand{\baselinestretch}
{#1}\small\normalsize} \spacingset{1}
\if00
{
\title{\bf On Well-posedness and Minimax Optimal Rates of Nonparametric $Q$-function Estimation in Off-policy Evaluation\footnotetext{Author
names are sorted alphabetically}}
\author{Xiaohong Chen\thanks{Cowles Foundation for Research in Economics, Yale University. \texttt{[email removed]}}
\quad \quad Zhengling Qi\thanks{Department of Decision Sciences, George Washington University. \texttt{[email removed]}}
}
\maketitle
} \fi
\begin{abstract}
We study the off-policy evaluation (OPE) problem in an infinite-horizon Markov decision process with continuous states and actions. We recast the $Q$-function estimation into a special form of the nonparametric instrumental variables (NPIV) estimation problem.
We first show that under one mild condition the NPIV formulation of $Q$-function estimation is well-posed in the sense of \textit{$L^2$-measure of ill-posedness} with respect to the data generating distribution, bypassing a strong assumption on the discount factor $\gamma$ imposed in the recent literature for obtaining the $L^2$ convergence rates of various $Q$-function estimators. Thanks to this new well-posed property, we derive the first minimax lower bounds for the convergence rates of nonparametric estimation of $Q$-function and its derivatives in both sup-norm and $L^2$-norm, which are shown to be the same as those for the classical nonparametric regression \citep{stone1982optimal}. We then propose a sieve two-stage least squares estimator and establish its rate-optimality in both norms under some mild conditions.
Our general results on the well-posedness and the minimax lower bounds are of independent interest to study not only other nonparametric estimators for $Q$-function but also efficient estimation on the value of any target policy in off-policy settings.
\end{abstract}
\baselineskip=21pt
\section{Introduction}
In recent years, there is a surging interest in studying batch reinforcement learning (RL), which utilizes previously collected data to perform sequential decision making \citep{sutton2018reinforcement} and
does not require interacting with task environment or accessing a simulator.
The batch RL techniques are especially attractive in many high-stake real-world application domains where it is too costly or infeasible to access a simulator, such as
mobile health \citep{liao2018just}, robotics \citep{pinto2016supersizing}, digital marketing \citep{thomas2017predictive} and precision medicine \citep{kosorok2019precision}, and others.
Nevertheless, the batch setting still posits several theoretical challenges that tamper the generalizability of many RL algorithms in practice. Among them, one central challenge is the \textit{distributional mismatch} between the data collecting process and the target distribution for evaluation \citep{levine2020offline}.
Motivated by these, we study the off-policy evaluation (OPE) problem, which is considered one of fundamental problems in batch RL. The goal of OPE is to leverage pre-collected data generated by a so-called behavior policy to evaluate the performance (e.g., value) of a new/target policy. In particular, we investigate theoretical property of nonparametric estimation of $Q$-function in the setting of infinite-horizon Markov decision processes (MDPs) (with discounted rewards, continuous states and actions).
We make several important contributions to the existing literature. Motivated by Bellman equation, we formulate $Q$-function estimation under the framework of a nonparametric instrumental variable (NPIV) model.
We first show that, under mild regularity conditions, the NPIV formulation of $Q$-function estimation is well-posed in the sense of \textit{$L^2$-measure of ill-posedness} with respect to the data generating distribution. This essentially justifies the valid use of the $L^2$-norm of Bellman error/residual to measure the accuracy of $Q$-function estimation in the batch setting. Next, we derive the minimax lower bounds for the convergence rates in sup-norm and in $L^2$-norm for the estimation of $Q$-function and its derivatives. Thanks to the general well-posedness result, the lower bounds are shown to be the same as those for the nonparametric regression estimation in the i.i.d. setting \citep{stone1982optimal,Tsybakov2009}. Thus the nonparametric $Q$-function estimation could be as easy as the nonparametric regression in terms of the worst case rate. Using the NPIV formulation, we also propose sieve 2SLS estimators to estimate the $Q$-function (and its derivatives) and establish their convergence rates in both sup-norm and $L^2$-norm. In particular, B-spline and wavelet 2SLS estimators are shown to achieve the sup-norm lower bound for H\"older class of $Q$-functions (and the derivatives), and many more linear sieve (such as polynomials, cosines, splines, wavelets) 2SLS estimators are shown to achieve the $L^2$-norm lower bound for Sobolev class of $Q$-functions (and the derivatives). Our results on $L^2$-norm convergence rates under mild conditions are particularly useful for obtaining efficient estimation and optimal inference on the value (i.e., the expectation of the $Q$ function) of a target policy.
To the best of our knowledge, ours are the first minimax results for non-parametrically estimating $Q$-function of continuous states and actions in the off-policy setting.
The general results on the well-posedness and the minimax lower bounds (in sup-norm and in $L^2$-norm)
are of independent interest to study properties of other nonparametric estimators for $Q$-function and the related estimators of the marginal importance weight (see, e.g., \cite{liu2018breaking}) in the off-policy setting.
\subsection{Closely Related Work}
Estimation of $Q$-function for a fixed policy is a key building block for many RL algorithms. There is a growing literature on nonparametric estimation of $Q$-function in the infinite-horizon and off-policy setting. See some recent theoretical development in \cite{farahmand2016regularized,shi2020statistical,uehara2021finite} among many others. Specifically, \cite{farahmand2016regularized} established $L^2$ error bound for Bellman error of their $Q$-function estimator. \cite{shi2020statistical,uehara2021finite} derived that $L^2$-norm convergence rates and error bounds for their respective nonparametric $Q$-function estimators under
a strong assumption that is essentially equivalent to restricting the discount factor $\gamma$ to be close to zero.
Our well-posedness result implies that their $L^2$-norm convergence rates of their respective estimators for $Q$-function remain valid without their strong assumption on the discount rate $\gamma$.
See Section \ref{sec: well-posed} and Remark \ref{rm:Shi} for more detailed discussions.
The connection of estimating $Q$-function in Bellman equation to instrumental variables estimation, to the best of our knowledge, has been first pointed out by \cite{bradtke1996linear} for their celebrated least-squares temporal difference (LSTD) method for parametric models. Recently, the relation between nonparametric $Q$-function estimation and nonparametric instrumental variables (NPIV) estimation has also been observed by some applied work (such as \cite{chen2021instrumental}) and theoretical work (such as \cite{duan2021optimal} that focuses on the on-policy setting). The NPIV model has been extensively investigated in econometric literature; see, e.g.,
\cite{newey2003instrumental,ai2003efficient,HH2005,blundell2007semi,DFFR2011,chen2011rate,chen2013optimal} for earlier reference. However, there is some subtle difference between the nonparametric $Q$-function estimation and the NPIV one. It is known that a generic NPIV model with continuous endogenous variables is a difficult ill-posed inverse problem in econometrics, but we show that estimation of a nonparametric $Q$-function of continuous states and actions can be well-posed under mild regularity conditions that are typically assumed in batch RL literature. Our well-posedness result implies that nonparametric estimation and inference on OPE and related batch RL problems could be much simpler than the difficult ill-posed NPIV problems studied in the existing econometric literature.
\begin{comment}
\citep{uehara2020minimax,yin2021near} established statistical efficiency for their OPE methods in the tabular case and \citep{kallus2019double,kallus2019efficiently,shi2020statistical} in the framework of semi-parametric statistics.
Most existing work were focused on developing $L^2$ convergence rates of their $Q$-function estimators. In particular, to obtain desirable rates, \citep{shi2020statistical,uehara2021finite} made a strong assumption on the discount factor $\gamma$ so that the minimum eigenvalue of some matrix is bounded away from $0$, together with the so-called \textit{coverage} assumption (See detailed discussion in our Section \ref{sec: well-posed}). Based
The goal of OPE is to leverage pre-collected data generated by a so-called behavior policy to evaluate the performance (e.g., value) of a new/target policy, which is a key building block for many batch policy learning methods such as \citep{ernst2005tree,kumar2020conservative,liao2020batch,jin2021pessimism}.
In this paper, we focus on theoretical properties of the so-called direct method in OPE problem,
(e.g, \cite{antos2008fitted,farahmand2016regularized,le2019batch,liao2019off,shi2020statistical} among others), which essentially make use of Bellman equation (e.g., \cite{bertsekas1995dynamic,sutton2018reinforcement}) to estimate the $Q$-function.
On the theoretical development of OPE, \citep{uehara2020minimax,yin2021near} established statistical efficiency for their OPE methods in the tabular case and \citep{kallus2019double,kallus2019efficiently,shi2020statistical} in the framework of semi-parametric statistics. In addition, .
which has also been observed by the recent applied work such as \citep{chen2021instrumental} and theoretical work such as \citep{duan2021optimal} that focused on the on-policy setting. In addition, we also notice that least-squares temporal difference (LSTD) method has been connected with the classical instrumental variable estimation \citep{bradtke1996linear}.
In the exiting literature on the non-parametric estimation of $Q$-function such as \citep{shi2020statistical,uehara2021finite}, the convergence rates in $L^2$-norm have been established under a strong assumption that some minimum eigenvalue is bounded away from $0$, together with the so-called \textit{coverage} assumption (See detailed discussion in our Section \ref{sec: well-posed}). They also developed a sufficient condition for this minimum eigenvalue assumption satisfied that basically requires the discount factor $\gamma$ to be small (See Lemma 2 of \citep{kallus2019efficiently}, or Section C.1 of \citep{shi2020statistical}). However, such condition is hardly satisfied in practice as $\gamma$ is often chosen to be close to $1$ in order to evaluate the long-term effect of a policy. More importantly, this sufficient condition limits their OPE methods from evaluating a target policy that is very different from the behavior one, therefore weakening the generalizability of their OPE algorithms. By recasting the $Q$-function estimation as a special form of NPIV problem, we show that the nonparametric $Q$-function estimation is in general well-posed in the sense of \textit{ $L^2$-measure of ill-posedness} with respect to the data generating distribution under the coverage assumption, demonstrating that the existing condition on either the minimum eigenvalue or the discount factor $\gamma$ is not needed.
\end{comment}
The rest of the paper is organized as follows. Section \ref{sec: prelim} presents the framework of infinite-horizon MDPs and some necessary notations. In Section \ref{sec: well-posed}, we show that the nonparametric $Q$-function estimation in sup-norm and in $L^2$-norm are both well-posed. Section \ref{sec: lower bound} establishes the minimax lower bounds for the rates of convergence for nonparametric estimation of $Q$-function in sup-norm and in $L^2$-norm respectively.
In Section \ref{sec: NPIV}, we propose sieve 2SLS estimation of the $Q$-function and its derivatives. Under some mild condition, we establish their rates of convergence in both sup-norm and $L^2$-norm, which coincide with the lower bounds. Section \ref{sec: conclusion} briefly concludes. Most proofs are given in the appendix.
\section{Preliminaries and Notation}\label{sec: prelim}
Consider a single trajectory $\{(S_{t},A_{t},R_{t})\}_{t \geq 0}$ where $(S_{t},A_{t},R_{t})$ denotes the state-action-reward triplet collected at time $t$. Let ${\cal S}$ and ${\cal A}$ be the state and action spaces, respectively. We assume both state and action are \textit{continuous} (as the discrete and finite spaces are easier).
A policy associated with this trajectory defines an agent's way of choosing the action at each decision time $t$. In this paper, we focus on using the batch data to evaluate the performance of a stationary policy denoted by $\pi$, which is a function mapping from the state space ${\cal S}$ to a probability distribution over ${\cal A}$. In particular, $\pi(a \, | \, s)$ refers to the probability density function of choosing action $a \in {\cal A}$ given the state value $s \in {\cal S}$. In addition, let ${\cal S} \times {\cal A} \subseteq \mathbb{R}^{d}$ for some $d \geq 2$, and ${\cal B}({\cal S})$ be the family of Borel subsets of ${\cal S}$.
The main goal of this paper is to estimate the so-called $Q$-function of a target policy $\pi$ using the batch data. Specifically, given a stationary policy $\pi$ and any state-action pair $(s, a) \in {\cal S} \times {\cal A}$, we define $Q$-function as
\begin{eqnarray*}
Q^{\pi}(s,a)=\sum_{t=0}^{+\infty} \gamma^t \mathbb{E}^{\pi} (R_{t}|S_{0}=s, A_{0}=a),
\end{eqnarray*}
where $\mathbb{E}^{\pi}$ denotes the expectation assuming the actions are selected according to $\pi$, and $0 \leq \gamma<1$ denotes some discounted factor that balances the trade-off between immediate and future rewards. We consider the framework of a time-homogeneous MDP and hence make the following two assumptions, which are foundation of many $Q$-function estimations.
\begin{assumption}\label{ass: Markovian}
There exists a transition kernel $P$ such that for every $t\geq 1$, $s \in {\cal S}$, $a \in {\cal A}$ and any set $B \in {\cal B}({\cal S})$,
$$
\Pr(S_{t+1} \in B \, | \, S_t = s, A_t = a, \left\{S_j, A_j, R_j\right\}_{0 \leq j < t}) = P(S_{t+1} \in B \, | \, S_t = s, A_t = a),
$$
In addition, there exists a probability density function $q$ for the transition kernel $P$.
\end{assumption}
\begin{assumption}\label{ass: reward}
For every $t \geq 0$, $R_t = {\cal R}(S_t, A_t, S_{t+1})$, i.e., a measurable function of $(S_t, A_t, S_{t+1})$.
In addition, there exists a finite constant $R_{\max}$ such that $|R_t| \leq R_{\max}$ for all $t \geq0$.
\end{assumption}
Let $r(s, a) = \mathbb{E}\left[R_{t} \, | \, S_{t} = s, A_{t} = a\right]$ for every $t \geq 0$, $s \in {\cal S}$ and $a \in {\cal A}$. Assumption \ref{ass: reward} implies that $|r(S_t, A_t)| \leq R_{\max}$ for all $t \geq0$.
We note that the uniformly bounded reward assumption is imposed for simplicity only, and can be replaced by assuming existence of higher order conditional moments of $R_t$ given $(S_t,A_t)$; see, e.g., \cite{chen2015optimal,chen2013optimal}.
To estimate $Q^\pi$, by Assumptions \ref{ass: Markovian} and \ref{ass: reward}, one approach is to solve the following Bellman equation, i.e.,
\begin{align}\label{eq: Bellman equation for Q}
Q^\pi(s, a) = \mathbb{E}\left[R_t + \gamma \int_{a' \in {\cal A}} \pi(a' \, | \, S_{t+1})Q^\pi(S_{t+1}, a')\text{d}a' \, | \, S_t = s, A_t = a\right],
\end{align}
for any $t\geq 0$, $s \in {\cal S} $ and $a \in {\cal A}$. Throughout this paper, we assume the integration with respect to $\pi$ in \eqref{eq: Bellman equation for Q} can be exactly evaluated as long as the integrand is known. In practice, one can use Monte Carlo method to approximate this integration since the target policy $\pi$ is known.
Now suppose the given batch data consist of $N$ trajectories, which correspond to $N$ independent and identically distributed copies of $\{(S_{t},A_{t},R_{t})\}_{t\ge 0}$. For $1 \leq i \leq N$, data collected from the $i$th trajectory are represented by $\{(S_{i,t},A_{i,t},R_{i,t},S_{i,t+1})\}_{0\le t< T}$. We then aim to leverage this batch data to estimate $Q$-function of a target policy $\pi$. Before presenting our theoretical results and methods, we make one additional assumption on the data generating process. Let $\pi^b$ be a stationary policy and $\pi^b(a \, | \, s)$ refers to the conditional probability density of choosing the action $a$ given the state value $s$.
\begin{assumption}\label{ass: DGP}
The batch data ${\cal D}_N = \{(S_{i,t},A_{i,t},R_{i,t},S_{i,t+1})\}_{0\le t< T, 1 \le i \le N}$ are generated by the policy $\pi^b$.
\end{assumption}
Assumptions \ref{ass: Markovian}-\ref{ass: DGP} are standard in the literature of batch RL. Note that in the literature the policy $\pi^b$ is often called the behavior policy and mostly different from the target one $\pi$. Next, we introduce the average visitation probability measure. Let $q^{\pi^b}_t(s, a)$ be the marginal probability density of a state-action pair $(s, a)$ at the decision point $t$ induced by the behavior policy $\pi^b$. Then the average visitation probability density across $T$ decision points is defined as
$$
\bar d^{\pi^b}_T(s, a) = \frac{1}{T}\sum_{t = 0}^{T-1}q^{\pi^b}_t(s, a).
$$
The corresponding expectation with respect to $\bar d^{\pi^b}_T$ is denoted by $\overline \mathbb{E}$. We further let $q^\pi_t(s', a' \, | \, s, a)$
be the $t$-step visitation probability density function induced by a policy $\pi$ at $(s', a')$ given an initial state-action pair $(s, a) \in {\cal S} \times {\cal A}$.
\textit{Notation}: For generic sequences $\{\varpi(N)\}_{N\geq1}$ and $\{\theta(N)\}_{N\geq1}$, the notation $\varpi(N) \gtrsim \theta(N)$ (resp. $\varpi(N) \lesssim \theta(N)$) means that there exists a sufficiently large constant (resp. small) constant $c_1>0$ (resp. $c_2>0$) such that $\varpi(N) \geq c_1 \theta(N)$ (resp. $\varpi(N) \leq c_2 \theta(N)$). We use $\varpi(N) \asymp \theta(N)$ when $\varpi(N) \gtrsim \theta(N)$ and $\varpi(N) \lesssim \theta(N)$. For matrix and vector norms, we use $\|\bullet\|_{\ell_q}$ to denote either the vector $\ell_q$-norm or operator norm induced by the vector $\ell_q$-norm, for $1 \leq q < \infty$, when there is no confusion. $\lambda_{\min}(\bullet)$ and $\lambda_{\max}(\bullet)$ denote the minimum and maximum eigenvalues of some square matrix, respectively. For any random variable $X$, we use $L^q(X)$ to denote the class of all measurable functions with finite $q$-th moments for $1 \leq q \leq \infty$. Then the $L^q$-norm is denoted by $\|\bullet\|_{L^q(X)}$. When there is no confusion in the underlying distribution, we also write it as $\|\bullet\|_{L^q}$ or $\|\bullet\|_{q}$. In particular, $\|\bullet\|_\infty$ denotes the sup-norm. In addition, we use Big $O_p$ and small $o_p$ as the convention. We often use $(S, A, R, S')$ or $(S, A, S')$ to represent some generic transition tuples, where the transition probability density is $q$. Lastly, we introduce the H\"older class of functions $g: {\cal X} \subseteq \mathbb{R}^d \rightarrow \mathbb{R}$ with smoothness $p > 0$ as
\begin{align*}\label{def: holder class}
&\Lambda_\infty(p, L) \triangleq & \left\{g \quad \mid \sup_{0 \leq \|\alpha\|_{\ell_1} \leq \floor p} \|\partial^\alpha g\|_\infty \leq L, \quad \sup_{\alpha: \|\alpha\|_{\ell_1} = \floor p} \sup_{x, y \in {\cal X}, x \neq y} \frac{\left|\partial^\alpha g(x) - \partial^\alpha g(y)\right|}{\|x - y\|_{\ell_2}^{\alpha-\floor p}} \leq L \right\},
\end{align*}
where ${\cal X} = {\cal S} \times {\cal A} \subset \mathbb{R}^{d}$ is a compact rectangular support with nonempty interior, $\floor p$ denotes the integer no larger than $p$ for any $p >0$, a non-negative vector $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_d)$ and
$$
\partial^\alpha g(x) = \frac{\partial^\alpha g(x) }{\partial x_1^{\alpha_1} \partial x_2^{\alpha_2}\cdots \partial x_d^{\alpha_d}}.
$$
We let $\Lambda_2(p, L)$ be the Sobolev space of smoothness $p$ with radius $L$ and support ${\cal X}$, where the underlying measure is Lebesque measure.
\section{A Special Form of NPIV Models: Well-posedness}\label{sec: well-posed}
In this section, we formulate $Q$-function estimation under the framework of a nonparametric instrumental variables (NPIV) model, which has been extensively studied in econometrics (e.g., \cite{ai2003efficient,newey2003instrumental,blundell2007semi}). A generic NPIV model takes the expression as
\begin{equation}\label{Model:NPIV}
Y = h_0(X) + U, \quad \text{with} \quad \mathbb{E}[U | W] = 0,
\end{equation}
where $h_0$ is an unknown function to estimate, $X$ is called endogenous variables, $W$ is called instrumental variables, and $U$ represents some random error.
Motivated by Equation \eqref{eq: Bellman equation for Q}, we consider the following special form of a NPIV model with Assumptions \ref{ass: Markovian}-\ref{ass: DGP} for $Q$-function estimation:
\begin{align}\label{Model: NPIV on $Q$-function}
R_t = h^\pi(S_t, A_t, S_{t+1};Q^\pi) + U_t, \quad \text{with} \quad \mathbb{E}[U_t | S_t, A_t] = 0
\end{align}
for $0 \leq t \leq T-1$, where
\[h^\pi(s, a, s';Q) = Q(s, a) - \gamma\int_{a' \in {\cal A}}\pi(a' | s') Q(s', a')\text{d}a'.
\]
We also write $h^\pi(s, a, s';Q)$ as $h^\pi(Q)(s, a, s')$ and $h_0^\pi = h^\pi(Q^\pi)$ when there is no confusion. By requiring $\mathbb{E}[U_t | S_t, A_t] = 0$ for $0 \leq t \leq T-1$, we recover the Bellman Equation \eqref{eq: Bellman equation for Q}. Therefore Model \eqref{Model: NPIV on $Q$-function} can be used to estimate $Q^\pi$ nonparametrically, where $S_{t+1}$ can be understood as endogenous variables and $(S_t, A_t)$ as instrumental variables under the framework of the NPIV model.
Let $L^2(S, A)$ be the space of square integrable functions against the probability measure with density $\bar d^{\pi^b}_T$ and $L^2(S, A, S')$ against the probability measure with density $\bar d^{\pi^b}_T \times q$.
Denote the conditional expectation operator by ${\cal T}: L^2(S, A, S') \to L^2(S, A)$, i.e., for every $(s, a) \in {\cal S} \times {\cal A}$,
\[
{\cal T} f(s, a) = \mathbb{E}[f(S, A, S')|S = s, A = a]\,
\]
and in particular,
\[
{\cal T} h^\pi(Q)(s,a) = \mathbb{E}[h^\pi(S, A, S'; Q)|S = s, A = a]\,.
\]
\subsection{Well-posedness in sup-norm}
In this subsection, we show that $Q$-function estimation is in general well-posed in sup-norm given by the following lemma.
\begin{lemma}\label{lm: contraction}
For any discount factor $0 \leq \gamma < 1$ and any uniformly bounded function $Q$ defined over $({\cal S}, {\cal A})$, the following inequalities hold.
\begin{align}\label{eq: link Q to Bellman operator to TD}
\frac{1}{1+\gamma }\|h^\pi(Q- Q^\pi)\|_\infty \leq \|Q - Q^\pi\|_\infty \leq \frac{1}{1-\gamma}\|{\cal T} h^\pi(Q - Q^\pi)\|_\infty \leq \frac{1}{1-\gamma}\|h^\pi(Q- Q^\pi)\|_\infty.
\end{align}
\end{lemma}
\begin{proof}
It is sufficient to show that $\|Q - Q^\pi\|_\infty \leq \frac{1}{1-\gamma}\|{\cal T} h^\pi(Q - Q^\pi)\|_\infty$, while other inequalities can be readily seen. It can be observed that
\begin{align}
\|Q - Q^\pi\|_\infty & \leq \|{\cal T} h^\pi(Q - Q^\pi)\|_\infty + \gamma \|\mathbb{E}^\pi\left[(Q- Q^\pi)(S', A') \, | \, S = \bullet, A = \bullet \right]\|_\infty \label{eqn: temp1}\\[0.1in]
& \leq \|{\cal T} h^\pi(Q - Q^\pi)\|_\infty + \gamma\|Q- Q^\pi\|_\infty \label{eqn: temp2},
\end{align}
where the first line follows the triangle inequality. This immediately implies
\begin{align}\label{eqn: temp inequality}
\|Q - Q^\pi\|_\infty & \leq \frac{1}{1-\gamma}\|{\cal T} h^\pi(Q - Q^\pi)\|_\infty.
\end{align}
\end{proof}
Lemma \ref{lm: contraction} implies that to obtain the sup-norm rate for $\wh Q^\pi$, it is sufficient to focus on $
\|h^\pi(\wh Q^\pi- Q^\pi)\|_\infty$, which is the sup-norm of so-called \textit{temporal difference} error. One key reason of having such an inequality is the fact that Bellman operator is $\gamma$-contractive with respect to the sup-norm (from \eqref{eqn: temp1}-\eqref{eqn: temp2}). However, it is hard to develop an estimator that minimizes the sup-norm of Bellman error in the batch setting so as to directly bound the sup-norm. Instead most existing methods are focused on minimizing the $L^2$-norm of Bellman error. This motivates us to study the well-posedness in $L^2$-norm below.
\subsection{Well-posedness in $L^2$-norm}\label{subsec: well-posed in L2}
Lemma \ref{lm: contraction} in general may not hold for $L^2$-norm with respect to the data generating process (e.g., $\bar d^{\pi^b}_T$) due to the distributional mismatch between the behavior policy and the target one, which is one fundamental barrier in analyzing OPE problem in the literature as discussed in the introduction.
To characterize the difficulty of $L^2$-estimating $Q^\pi$ under Model \eqref{Model: NPIV on $Q$-function}, we define a \textit{$L^2$-measure of ill-posedness} as
\begin{equation}\label{def: Lp measure of ill-posedness}
\overline \tau = \sup_{Q \in L^2(S, A)} \frac{\|h^\pi(Q)\|_{L^2(S, A, S')}}{\|{\cal T} h^\pi(Q)\|_{L^2(S, A)}}\,.
\end{equation}
It can be seen that $\overline \tau \geq 1$ and could be arbitrarily large in general, which can be used to quantify the level of ill-posedness in estimating $Q^\pi$.
We impose the following mild assumption to ensure the well-posedness in $L^2$-norm
in the sense of $\overline \tau \lesssim 1$.
\begin{assumption}\label{ass: L2 well-posed}
(a)~There exist positive constants $p_{\min}$ and $p_{1,\max}$ such that the average visitation probability density function $\bar d^{\pi^b}_T$ satisfies $p_{\min} \leq \bar d^{\pi^b}_T(s, a) \leq p_{1, \max} $ for every $(s, a) \in {\cal S} \times {\cal A}$.
(b)~ The target policy $\pi$ is absolutely continuous with respect to $\pi^b$ and $q^\pi(s', a' \, | \, s, a) \leq p_{2, \max}$ for some positive constant $p_{2, \max}$.
\end{assumption}
Let $p_{\max} = \max(p_{1, \max}, p_{2, \max})$.
In general, boundedness assumption on the data generating probability density in Assumption \ref{ass: L2 well-posed}~(a)
is standard in the classical non-parametric estimation such as \cite{huang1998projection,chen2015optimal}. In our setting, that the average visitation probability density is uniformly bounded away from $0$ is also called \textit{coverage} assumption frequently used in RL literature such as \cite{precup2000eligibility,antos2008fitted,kallus2019efficiently} among many others. We use this standard assumption as we consider any target policy for OPE. This assumption can be relaxed to the so-called \textit{partial coverage} if one is willing to impose some structure assumption on $Q^\pi$. See recent studies in \cite{duan2020minimax,xie2021bellman,agarwal2021theory,uehara2021pessimistic}. Assumption \ref{ass: L2 well-posed}~(b) imposes one mild identification condition on the target policy. It essentially states that our batch data are able to identify the value of the target policy.
Lastly, we remark that when both ${\cal S}$ and ${\cal A}$ are discrete and finite, Assumption \ref{ass: L2 well-posed}~(b) is automatically satisfied because of Assumption \ref{ass: L2 well-posed}~(a).
In the following, we use $\|\bullet\|_{2, \nu}$ to denote $L^2$-norm with respect to some probability distribution/density $\nu$.
Now we are ready to present a key theorem in this paper, which can not only be used to establish the minimax-optimal sup-norm and $L^2$-norm rates for estimating $Q^\pi$, but also provide a foundation for many existing OPE estimators.
\begin{theorem}\label{thm: well-posed}
For any policy $\pi$, discount factor $0 \leq \gamma < 1$, and any two square integrable functions $Q_1$ and $Q_2$ defined over $({\cal S}, {\cal A})$ with respect to $\bar d_T^{\pi^b}$, under Assumptions \ref{ass: Markovian}, \ref{ass: DGP} and \ref{ass: L2 well-posed}, the following inequalities hold.
\begin{align}\label{eq: L2 error bound}
\sqrt{\frac{p_{\min}}{p_{\max}}}(1-\gamma)\|Q_1 - Q_2\|_{2, \bar d_T^{\pi^b}} \leq \|{\cal T} h^\pi(Q_1 - Q_2)\|_{2, \bar d_T^{\pi^b}} \leq \|h^\pi(Q_1- Q_2)\|_{2, \bar d_T^{\pi^b}\times q}.
\end{align}
In particular,
the $L^2$ measure of ill-posedness
$$
\overline \tau \lesssim \frac{\sqrt{p_{\max}(1+\frac{p_{\max}\gamma^2}{p_{\min}})}}{\sqrt {p_{\min}}(1-\gamma)} \lesssim 1.
$$
\end{theorem}
\begin{proof}
For the first statement of Theorem \ref{thm: well-posed}, it is enough to focus on the first inequality, while the second one is given by Jensen's inequality. Let ${\cal I}$ be the identity operator and ${\cal P}^\pi$ be the operator such that ${\cal P}^\pi f (s, a) = \mathbb{E}^\pi\left[f(S_{t+1}, A_{t+1}) \, | \, S_t = s, A_t = a \right]$ for any $t \geq 0$.
By induction, we can show that $({\cal P}^\pi)^{k} f (s, a) = \mathbb{E}^\pi\left[f(S_{t+k}, A_{t+k}) \, | \, S_t = s, A_t = a \right]$. For some integer $\bar t$, which will be specified later, we have
\begin{align*}
\|Q_1 - Q_2\|_{2, \bar d_T^{\pi^b}} \leq \underbrace{\|\left({\cal I} - \gamma^{\bar t} ({\cal P}^\pi)^{\bar t}\right)\left(Q_1 - Q_2\right)\|_{2, \bar d_T^{\pi^b}}}_{(I)} + \gamma^{\bar t} \underbrace{\| ({\cal P}^\pi)^{\bar t}\left(Q_1 - Q_2\right)\|_{2, \bar d_T^{\pi^b}}}_{(II)}.
\end{align*}
We first focus on deriving an upper bound for $(II)$. By Jensen's inequality, we can show that
\begin{align*}
\{(II)\}^2 & \leq \int_{s \in {\cal S}, a \in {\cal A}} \mathbb{E}^\pi\left[(Q_1 - Q_2)^2(S_{\bar t}, A_{\bar t}) \, | \, S_0 = s, A_0 = a\right] \bar d_T^{\pi^b}(s, a) \text{d}s \text{d}a \\
& = \int_{s \in {\cal S}, a \in {\cal A}} \int_{s' \in {\cal S}, a' \in {\cal A}} (Q_1 - Q_2)^2(s', a')q^\pi_{\bar t}(s', a' \, | \, s, a) \text{d}s' \text{d}a' \bar d_T^{\pi^b}(s, a) \text{d}s \text{d}a\\
& = \int_{s' \in {\cal S}, a' \in {\cal A}} (Q_1 - Q_2)^2(s', a') \widetilde{q}^{\pi^b;\pi}_{T;{\bar t}}(s', a')\text{d}s' \text{d}a'\\
& = \int_{s' \in {\cal S}, a' \in {\cal A}} (Q_1 - Q_2)^2(s', a') \frac{\widetilde{q}^{\pi^b;\pi}_{T;{\bar t}}(s', a')}{\bar d_T^{\pi^b}(s', a')}\bar d_T^{\pi^b}(s', a')\text{d}s' \text{d}a'\\
& \leq \frac{p_{\max}}{p_{\min}}\|Q_1 - Q_2\|_{2, \bar d_T^{\pi^b}}^2,
\end{align*}
where $\widetilde{q}^{\pi^b;\pi}_{T;{\bar t}}(s', a')$ refers to the marginal probability density function by composition between $\bar d_T^{\pi^b}$ and $q_{\bar t}^\pi$. The last equation holds because $\widetilde{q}^{\pi^b;\pi}_{T;{\bar t}}$ is absolutely continuous with respect to $\bar d_T^{\pi^b}(s', a')$ by Assumption \ref{ass: L2 well-posed}. The last inequality is also given by Assumption \ref{ass: L2 well-posed} since $\widetilde{q}^{\pi^b;\pi}_{T;{\bar t}}(s', a') = \overline{\mathbb{E}}\left[q^\pi_{\bar t}(s', a' \, | \, S, A)\right] \leq p_{\max}$ for every $(s, a) \in {\cal S} \times {\cal A}$ (As long as one-step transition density is bounded above, $\bar{t}$-step will also be bounded above.). Now for any $\varepsilon > 0$, we can choose $\bar t$ sufficiently large such that
$$
\gamma^{\bar t} \sqrt{p_{\max}/p_{\min}} \leq \varepsilon,
$$
which implies that $\gamma^{\bar t} \times (II) \leq \varepsilon \|Q_1 - Q_2\|_{2, \bar d_T^{\pi^b}}$. This further shows that
\begin{align*}
\|Q_1 - Q_2\|_{2, \bar d_T^{\pi^b}} \leq (1-\varepsilon)^{-1} \times (I).
\end{align*}
In the following, we derive an upper bound for $(I)$. Let $g = ({\cal I} - \gamma {\cal P}^\pi)(Q_1 - Q_2)$. By a similar argument as before, we have
\begin{align*}
(I) & = \|\left({\cal I} - \gamma {\cal P}^\pi +\gamma {\cal P}^\pi - \gamma^2 ({\cal P}^\pi)^2 + \cdots + \gamma^{\bar t-1}({\cal P}^\pi)^{\bar t-1} - \gamma^{\bar t} ({\cal P}^\pi)^{\bar t}\right)\left(Q_1 - Q_2\right)\|_{2, \bar d_T^{\pi^b}}\\
& \leq \sum_{k = 0}^{\bar t-1}\gamma^{k}\|({\cal P}^\pi)^{k}({\cal I} - \gamma {\cal P}^\pi)(Q_1 - Q_2)\|_{2, \bar d_T^{\pi^b}}\\
& = \sum_{k = 0}^{\bar t-1}\gamma^{k}\|({\cal P}^\pi)^{k}g\|_{2, \bar d_T^{\pi^b}}\\
& \leq \sum_{k = 0}^{\bar t-1}\gamma^{k}\sqrt{\frac{p_{\max}}{p_{\min}}}\|g\|_{2, \bar d_T^{\pi^b}}\\
& \leq \frac{1-\gamma^{\bar t}}{1-\gamma}\sqrt{\frac{p_{\max}}{p_{\min}}}\|g\|_{2, \bar d_T^{\pi^b}}.
\end{align*}
Summarizing together, we can obtain that
\begin{align*}
\|Q_1 - Q_2\|_{2, \bar d_T^{\pi^b}} &\leq \frac{(1-\varepsilon)^{-1}(1-\gamma^{\bar t})}{1-\gamma}\sqrt{\frac{p_{\max}}{p_{\min}}}\|{\cal T} h^\pi(Q_1 - Q_2)\|_{2, \bar d_T^{\pi^b}},
\end{align*}
where we note that ${\cal T} h^\pi(Q_1 - Q_2) = g$. Since $\varepsilon$ is arbitrary, let $\varepsilon$ go to $0$, we have
$$
\|Q_1 - Q_2\|_{2, \bar d_T^{\pi^b}} \leq \frac{1}{1-\gamma}\sqrt{\frac{p_{\max}}{p_{\min}}}\|{\cal T} h^\pi(Q_1 - Q_2)\|_{2, \bar d_T^{\pi^b}}
$$
In the remaining proof, we show $\overline \tau$ is bounded above. Note that for any $Q \in L^2(S, A)$,
\begin{align*}
\|h^\pi(Q)\|^2_{L^2(S, A, S')} &= \overline\mathbb{E}\left[\left(Q(S, A) - \gamma \int_{a' \in {\cal A}} \pi(a' \, | \, S')Q(S', a')\text{d}a'\right)^2\right]\\
&\lesssim 2 \overline\mathbb{E}\left[(Q(S, A))^2\right] + \frac{2p_{\max}\gamma^2}{p_{\min}}\int Q^2(s, a) \bar d^{\pi^b}_{T}(s, a)\text{d}s\text{d}a\\
&\lesssim (1 + \frac{p_{\max}\gamma^2}{p_{\min}}) \|Q\|^2_{2, \bar d^{\pi^b}_T},
\end{align*}
where the first inequality is given by AM-GM, Jensen's inequalities and Assumption \ref{ass: L2 well-posed} by noting that $\bar d^{\pi^b}_{T+1}(s, a) \lesssim p_{\max}$ for any $s \in {\cal S}$ and $a \in {\cal A}$. Then by the first inequality given in \eqref{eq: L2 error bound}, we can show that
$$
\overline \tau \lesssim \frac{\sqrt{p_{\max}(1+\frac{p_{\max}\gamma^2}{p_{\min}})}}{(1-\gamma)\sqrt {p_{\min}}},
$$
which concludes our proof.
\end{proof}
Theorem \ref{thm: well-posed}
rigorously justifies the validity of using $L^2$-norm to measure the Bellman error, which has been widely adopted in the existing literature for constructing various estimators for the $Q$-function. To see this, let $Q_1 = Q^\pi$ and $Q_2 = \widetilde Q$ in Theorem \ref{thm: well-posed}, where $\widetilde Q$ denotes some estimator for $Q^\pi$. Then the first inequality in \eqref{eq: L2 error bound} with Bellman equation \eqref{eq: Bellman equation for Q} implies that
$$
\|\widetilde Q- Q^\pi\|_{2, \bar d_T^{\pi^b}} \lesssim \|r + (\gamma {\cal P}^\pi - {\cal I})\widetilde Q \|_{2, \bar d_T^{\pi^b}},
$$
where the right hand side of the above inequality is called Bellman error (or residual) and recall that $r$ is the reward function defined in Assumption \ref{ass: reward}. Therefore $L^2$-norm of Bellman error of any $Q$-function estimator provides a valid upper bound for the $L^2$ error bound of this estimator to the true $Q^\pi$. Many existing estimators such as \cite{antos_learning_2008,farahmand2016regularized,uehara2019minimax,feng2020accountable} indeed are based on minimizing the $L^2$-norm of Bellman error. Therefore our Theorem \ref{thm: well-posed} provides a theoretical guarantee for their procedures.
Notice that Theorem \ref{thm: well-posed} is established without imposing any restriction on the structure of $Q$-function, it can be used to obtain $L^2$ error bounds for many different non-parametric estimators of $Q$-function obtained using different models and/or methods such as LSTD, kernel methods or neural networks. For example, combining our Theorem \ref{thm: well-posed} with Theorem 11 of \cite{farahmand2016regularized} immediately gives $L^2$-error bound for their estimator to the true $Q^\pi$. Applying our Theorem \ref{thm: well-posed} to Example 6 of \cite{uehara2021finite} one can obtain $L^2$-error bound for their neural network estimator to $Q^\pi$.
We also remark that the well-posed result in Theorem \ref{thm: well-posed} can be extended to other metrics such as $L^1$-norm, based on which one may develop a new estimator for $Q$-function by minimizing the empirical approximation of $L^1$-norm of Bellman error. We conjecture that such an estimator could achieve robustness compared with the existing ones, especially when the reward distribution is heavy tailed. Lastly, there is a very recent work \citep{wang2021projected}, which developed a sufficient and necessary condition for establishing the well-posedness of Bellman operator in $L^2$-norm. Besides they also developed a similar condition as our Assumption \ref{ass: L2 well-posed} in establishing this well-posedness.
\section{Minimax Lower Bounds}\label{sec: lower bound}
In this section, we establish minimax lower bounds in both sup-norm and in $L^2$-norm for estimation of nonparametric $Q$-function in OPE problem. The well-posedness property essentially indicates that non-parametric $Q$-function estimation is as easy as the classical non-parametric regression in the i.i.d. setting in terms of the worst case rate.
Recall that by Theorem \ref{thm: well-posed}, under Assumptions \ref{ass: Markovian}, \ref{ass: DGP} and \ref{ass: L2 well-posed}, for any square integrable function $Q$ defined over ${\cal S} \times {\cal A}$, we have
\begin{align}\label{eqn: well-posed operator}
\sqrt{\frac{p_{\min}}{p_{\max}}}(1-\gamma)\|Q\|_{2, \bar d^{\pi^b}_T} \leq \|{\cal T} h^\pi(Q)\|_{2, \bar d^{\pi^b}_T} \leq \|h^\pi(Q)\|_{2, \bar d^{\pi^b}_T \times q} \lesssim \|Q\|_{2, \bar d^{\pi^b}_T}.
\end{align}
Denote a generic transition tuple as $\{S_{i, t}, A_{i, t}, R_{i, t}, S'_{i, t}\}$ indexed by $(i, t)$. Then we have the following lower bound results for estimating $Q^\pi$ and its derivative in terms of the sup-norm.
\begin{theorem}\label{thm: lower bound}
Let $d^{\nu}$ be the average visitation probability density defined over ${\cal S} \times {\cal A}$ induced by some policy $\nu$ such that Assumption \ref{ass: L2 well-posed} holds with $\bar{d}^{\pi^b}_T$ and $\pi^b$ replaced by $d^\nu$ and $\nu$ respectively. Suppose the data ${\cal D}_N =\{S_{i, t}, A_{i, t}, R_{i, t}, S'_{i, t}\}_{1 \leq i \leq N, 0 \leq t \leq T-1}$ are $i.i.d.$ from Model \eqref{Model: NPIV on $Q$-function}, where the probability density of $(S_{i, t}, A_{i, t})$ is $d^{\nu}$ with the transition probability density $q$ and for every $0 \leq t\leq T- 1$ and $1 \leq i \leq N$, $\mathbb{E}[U_{i, t}^2 \, | \, S_{i, t}, A_{i, t}] \geq \sigma^2$, where $\sigma$ is some positive constant, then we have for any $0 \leq \|\alpha\|_{\ell_1} < p$,
\begin{align}
\liminf_{NT \rightarrow \infty}\inf_{\wh Q} \sup_{Q \in \Lambda_\infty(p, L)}{\Pr}^Q\left(\|\partial^\alpha \wh Q - \partial^\alpha Q\|_\infty \geq c (\log(NT)/NT)^{(p-\|\alpha\|_{\ell_1})/(2p+d)}\right) \geq c' >0,
\end{align}
for some constants $c$ and $c'$, where $\inf_{\wh Q}$ denotes the infimum over all estimators using ${\cal D}_N$,
and $\Pr^Q$ denotes the joint probability distribution of ${\cal D}_N$ with $h^\pi = h^\pi(Q)$ in Model \eqref{Model: NPIV on $Q$-function}.
\end{theorem}
The following theorem provides lower bound results in terms of $L^2$-norm.
\begin{theorem}\label{thm: L2 lower bound}
Under all conditions in Theorem \ref{thm: lower bound}, for $0 \leq \|\alpha\|_{\ell_1} < p$, we have
\begin{align}
\liminf_{NT \rightarrow \infty}\inf_{\wh Q} \sup_{Q \in \Lambda_2(p, L)}{\Pr}^Q\left(\|\partial^\alpha \wh Q - \partial^\alpha Q\|_2 \geq \bar c (NT)^{(\|\alpha\|_{\ell_1} - p)/(2p+d)}\right) \geq \bar c' >0,
\end{align}
for some constant $\bar c$ and $\bar c'$.
\end{theorem}
As we can see from Theorems \ref{thm: lower bound} and \ref{thm: L2 lower bound}, the minimax lower bounds for the rates of estimating $Q$-function and its derivatives are the same as those for nonparametric regression in the i.i.d setting \citep{stone1982optimal}. To the best of our knowledge, these are the first lower bound results for nonparametrically estimating $Q$-function and its derivatives in the infinite-horizon MDP. In the following section, we proposed simple estimators that match these lower bounds.
\section{Sieve 2SLS Estimation of $Q$-function}\label{sec: NPIV}
Given the NPIV Model \eqref{Model: NPIV on $Q$-function} as a reformulation of Bellman equation, we now adopt the idea from for example \cite{blundell2007semi,chen2013optimal} to construct a sieve 2SLS estimator for $Q^\pi$. Define two sieve basis functions as
\begin{align}\label{eq: sieve basis function}
&\psi^J(s, a) = (\psi_{J1}(s, a), \cdots, \psi_{JJ}(s, a))^\top,\\
&b^K(s, a) = (b_{K1}(s, a), \cdots, b_{KK}(s, a))^\top,
\end{align}
to model $Q^\pi$ and the space of instrumental variables respectively. Let $\Psi_J = \text{closure}\{\Psi_{J1},\ldots,\Psi_{JJ}\} \subset L^2(S, A)$ and $B_K = \text{closure} \{b_{K1},\ldots,b_{KK}\}\subset L^2(S, A)$ denote the sieve spaces for $Q^\pi$ and instrumental variables, respectively. Here the underlying probability measure of $L^2(S, A)$ is $\bar d^{\pi^b}_T$. Examples of basis functions include splines or wavelet bases (See more examples in \cite{huang1998projection,chen2007large}). The construction of wavelet bases can also be found in Appendix \ref{sec: lower bound}. We remark that the numbers of basis functions $J$ and $K$ are allowed to grow with either $N$ or $T$, but require that $J \leq K \leq cJ$ for some $c \geq 1$. Due to the special structure of Model \eqref{Model: NPIV on $Q$-function}, it also makes sense to simply let $K=J$ and $\psi^J =b^K$.
Additionally, we let $\psi^J_\pi(s) = (\int_{a\in {\cal A}}\pi(a | s)\psi_{J1}(s, a)\text{d}a, \cdots, \int_{a\in {\cal A}}\pi(a | s)\psi_{JJ}(s, a)\text{d}a)^\top$. Correspondingly, a sample version of all these functions can be defined as
\begin{align*}
&\Psi = \left(\psi^J(S_{1, 0}, A_{1, 0}) \cdots, \psi^J(S_{N, T-1}, A_{N, T-1})\right)^\top \in \mathbb{R}^{(NT) \times J},\\
&B = (b^K(S_{1, 0}, A_{1, 0}),b^K(S_{1, 1}, A_{1, 1}) \cdots, b^K(S_{N, T-1}, b_{N, T-1}))^\top \in \mathbb{R}^{(NT) \times K},\\
& G_\pi = (\psi^J_\pi(S_{1, 1}),\psi^J_\pi(S_{1, 2}) \cdots,\psi^J_\pi(S_{1, T}), \psi^J_\pi(S_{2, 1}), \cdots, \psi^J_\pi(S_{N, T}))^\top \in \mathbb{R}^{(NT) \times J}.
\end{align*}
For notational simplicity, let
$
\kappa_\pi^J(s, a, s') = \psi^J(s, a) - \gamma \psi_\pi^J(s')$, and correspondingly $ \Gamma_\pi = \Psi - \gamma G_\pi.
$
We also denote $\kappa_{Jj}^\pi(s, a, s') = \psi_{Jj}(s, a) - \gamma \int_{a' \in {\cal A}}\pi(a' \mid s')\text{d}a' \psi^\pi_{Jj}(s', a')$ for each element of $\kappa_\pi^J(s, a, s') \in \mathbb{R}^J$.
Then the sieve 2SLS estimator for $Q^\pi$ can be constructed as
\begin{align}\label{eqn: sieve estimator}
&\wh Q^\pi(s, a) = \psi^J(s, a)^\top \wh c \nonumber, \\
& \text{with}\quad \wh c = \left[\Gamma_\pi^\top B(B^\top B)^{-}B^\top \Gamma_\pi\right]^{-}\Gamma_\pi^\top B(B^\top B)^{-}B^\top \mathbf R,
\end{align}
where $(Z)^{-}$ denotes the generalized inverse of some matrix $Z$ and $\mathbf R = (R_{1, 0},R_{1, 1} \cdots, R_{N, T-1})^\top \in \mathbb{R}^{NT \times 1}$. The corresponding estimator for the derivatives of $Q^\pi$ is denoted by $\partial^\alpha \wh Q^\pi$ for any vector $\alpha$. Here $\wh c$ can be understood as a minimizer of the following optimization problem.
\begin{align*}
\underset{c \in \mathbb{R}^{J}}{minimize} \quad \|B(B^\top B)^{-1}B^\top(\mathbf R - \Gamma_\pi c)\|^2_{\ell_2}.
\end{align*}
Note that the sieve 2SLS estimator given in \eqref{eqn: sieve estimator} becomes the solution of the modified Bellman residual minimiazion in \cite{farahmand2016regularized} when their function spaces are modeled by sieve ones.
\subsection{Sieve measure of ill-posedness in NPIV}
An important quantity related to a generic NPIV model \eqref{Model:NPIV} is called \textit{sieve $L^2$ measure of ill-posedness}, which characterizes the difficulty of non-parametrically estimating $h_0$ using the sieve estimation. Here a similar measure of ill-posedness can be defined under Model \eqref{Model: NPIV on $Q$-function}.
Let $\Theta^\pi_{J} = \{h^\pi(Q) \in L^2(S, A, S'): Q \in \Psi_J\}$. Adapting from the {sieve $L^2$ measure of ill-posedness} in \cite{blundell2007semi}, we define an average \textit{sieve $L^2$ measure of ill-posedness} across $T$ decision points under Model \eqref{Model: NPIV on $Q$-function} as
\begin{equation}\label{def: sieve measure of ill-posedness}
\tau_J = \sup_{h \in \Theta^\pi_J : h \neq 0} \frac{\|h\|_{L^2(S, A, S')}}{\|{\cal T} h\|_{L^2(S, A)}}\,.
\end{equation}
It can be seen that $\tau_J \geq 1$.
Basically $\tau_J $ measures how much information has been smoothed out by the conditional expectation operator ${\cal T}$ over the space $\Theta^\pi_J$. For a generic NPIV model \eqref{Model:NPIV}, $\tau_J$ grows to infinity as $J$ goes to infinity; see, e.g. \citep{blundell2007semi,chen2013optimal}.
By definition we have $ \tau_J \leq \overline{\tau} \lesssim 1$ for all $J \geq 1$. Thus Theorem \ref{thm: well-posed} directly implies that the NPIV Model \eqref{Model: NPIV on $Q$-function} is also well-posed under the $L^2$ sieve measure of ill-posedness defined in \eqref{def: sieve measure of ill-posedness}.
Based on this result, minimax-optimal sup-norm and $L^2$-norm rates for the sieve 2SLS estimator of $Q^\pi$ can be established in the following subsections.
\begin{comment}
We further define
$$
\omega_J = \lambda_{\min}(\overline\mathbb{E}[\psi^J_\pi(S, A)\psi^J_\pi(S, A)^\top]),
$$
and allow $\omega_J$ to converge to $0$ as $J$ increases.
We have the following corollary to bound $e_J$, which will appear in our bound.
\begin{corollary}\label{coro: sieve well-posed}
For any policy $\pi$, under Assumption \ref{ass: Markovian}, \ref{ass: DGP} and \ref{ass: L2 well-posed}, we have
$$
e_J \gtrsim \frac{p^2_{\min}}{p_{\max}}(1-\gamma)^2\omega_J \quad \text{and} \quad \tau_J \leq \overline{\tau} \lesssim \frac{p_{\max}\sqrt{(1+\frac{p_{\max}\gamma^2}{p_{\min}})}}{\sqrt{p_{\min}}(1-\gamma)}\, ,
$$
for every $J \geq 1$.
\end{corollary}
\begin{proof}
Since $\tau_J \leq \overline{\tau}$ by the definition, we can immediately show the above inequality on $\tau_J$. It then suffices to show the lower bound for $e_J$.
By definition,
$$
e_J = \lambda_{\min}\left\{\overline\mathbb{E}\left[\left(\psi^J(S, A) - \gamma \psi_\pi^J(S')\right)\left(\psi^J(S, A) - \gamma \psi_\pi^J(S')\right)^{\top}\right]\right\}\omega_J.
$$
Applying Theorem \ref{thm: well-posed} with $Q_1(s, a) = (\psi^J(S, A))^\top x$ and $Q_2(s, a) = 0$ for every $s \in {\cal S}$ and $a \in {\cal A}$ (recall that the sieve space is a subset of $L^2(S, A)$), we have
\begin{align*}
& x^\top \overline\mathbb{E}\left[\left(\psi^J(S, A) - \gamma \psi_\pi^J(S')\right)\left(\psi^J(S, A) - \gamma \psi_\pi^J(S')\right)^{\top}\right]x\\
\geq & x^\top \overline\mathbb{E}\left[\left(\psi^J(S, A) - \gamma \mathbb{E}\left[\psi_\pi^J(S')\mid S, A\right]\right)\left(\psi^J(S, A) - \gamma \mathbb{E}\left[\psi_\pi^J(S')\mid S, A\right]\right)^{\top}\right]x\\
= & \|(\psi^J(S, A) - \gamma \mathbb{E}\left[\psi_\pi^J(S')\mid S, A\right])^\top x\|^2_{2, \bar d_T^{\pi^b}}\\
\geq & \frac{p_{\min}}{p_{\max}}(1-\gamma)^2 \|(\psi^J(S, A))^\top x\|_{2, \bar d_T^{\pi^b}}^2 \geq \frac{p_{\min}}{p_{\max}}(1-\gamma)^2\omega_J\|x\|_{\ell_2}^2,
\end{align*}
where the first inequality is given by Jensen's inequality and the last inequality is by the definition of $\omega_J$.
\end{proof}
We remark that in \citep{shi2020statistical}, which used sieve LSTD method to estimate $Q^\pi$, they defined a similar quantity as $e_J$ here. One can show that their minimum singular value is no larger than the square root of ours. Since $\sqrt{e_J}$ characterizes the difficulty of the sieve estimation (as shown in Theorem \ref{thm: sup-norm rate}), it demonstrates the potential benefits of using two different basis functions (i.e., $b^K$ and $\Psi^J$) by noting that our method may degenerate to theirs when $\Psi^J = b^K$. Moreover, one can relax the coverage assumption in Assumption \ref{ass: L2 well-posed} by allowing $p_{\min}$ to converge to $0$ in terms of $J$. As the dimension of the state and action spaces increases, the coverage of whole state-action space may become less likely. In this case, $\tau_J$ could increase in terms of $J$ and our sieve estimation becomes ill-posed. {\color{red}{Shall we actually define our own ill-posedness case? As we need $p_{\min}$ decreases when $d$ increases.}} For example, if $p_{\min} \lesssim J^{-\varsigma/d}$ for some constant $\varsigma$, $\tau_J \lesssim J^{\varsigma/d}$, which is the \textit{mildly ill-posed} scenario considered in a NPIV model \citep{blundell2007semi}. Similarly, if $p_{\min} \lesssim \exp({-J^{\varsigma/d}})$, one can have that $\tau_J \lesssim \exp({J^{\frac{1}{2}\varsigma/d}})$, which is called \textit{severely ill-posed} proposed in a NPIV model \citep{blundell2007semi}.
\end{comment}
\subsection{ Sup-norm Convergence Rates}\label{sec: sup-norm rate}
In this subsection, we establish the sup-norm convergence rate of $\wh Q^\pi$ to $Q^\pi$. We first introduce an additional assumption on the data generating process.
\begin{assumption}\label{ass: stationary}
The stochastic process $\{S_t, A_t\}_{t\geq 0}$ induced by the behavior policy $\pi^b$ is a stationary, exponentially $\boldsymbol{\beta}$-mixing stochastic process, i.e., the $\boldsymbol{\beta}$-mixing coefficient at time lag $k$ satisfies that $\beta_k \leq \beta_0 \exp(-\beta_1 k)$ for $\beta_0 \geq 0$ and $\beta_1 > 0$. The induced stationary density is denoted by $d^{\pi^b}$.
\end{assumption}
Assumption \ref{ass: stationary} is imposed to characterize the dependency among observations over time because the observed data modeled by MDP are \textit{not} i.i.d. and transition tuples are dependent. Most of previous works assume transition tuples are independent, which is stronger than this assumption. The $\boldsymbol{\beta}$-mixing coefficient at time lag $k$ basically means that the dependency between $\{S_t, A_t\}_{t \leq j }$ and $\{S_t, A_t\}_{t \geq (j+k) }$ decays to 0 at an exponential rate with respect to $k$. See \cite{bradley2005basic} for the exact definition of the exponentially $\boldsymbol{\beta}$-mixing. A fast mixing rate is imposed here mainly for technical simplicity and our sup-norm and $L^2$-norm convergence rates are not affected by the mixing coefficients. Indeed, Assumption \ref{ass: stationary} can be relaxed to stationary with certain algebraic $\beta$-mixing, and by using the matrix Bernstein inequality for general $\beta$-mixing of \cite{chen2015optimal} one may obtain the same convergence rates as those in Theorems \ref{thm: sup-norm rate} and \ref{thm: L2 variance+bias bound} below. We can also relax the strictly stationary assumption with some extra notation. Since this is not our focus, we do not impose the weakest possible assumptions on the temporal dependence in this paper. When both Assumptions \ref{ass: L2 well-posed} and \ref{ass: stationary} hold, the average visitation probability density $\bar d^{\pi^b}_T$ used in Assumption \ref{ass: L2 well-posed} becomes the induced stationary density $d^{\pi^b}$. We will omit $\nu$ in $\|\bullet\|_{2, \nu}$ when $\nu = d^{\pi^b}$. Throughout the remaining of this section, unless otherwise specified, $(S, A)$ has the probability density $d^{\pi^b}$ and the density of $(S, A, S')$ is $d^{\pi^b} \times q$.
Define $L_{2,h^\pi}(S, A, S') = \left\{h^\pi(Q): Q \in L^2(S, A) \right\}$.
Let $\Pi_J: L_{2, h^\pi}(S, A, S') \to \Theta^\pi_J$ denote the $L_{h^\pi}^2(S, A, S')$ mapping onto $\Theta^\pi_J$, i.e., $\Pi_J h_0^\pi = h_0^\pi(\overline \Pi_J Q^\pi)$, where $\overline \Pi_J Q^\pi = \mathrm{arg}\min_{Q \in \Psi_J} \|Q^\pi - Q\|_{L^2(S, A)}$, and let $\Pi_K :L^2(S, A) \to B_K$ denote the $L^2(S, A)$ orthogonal projection onto $B_K$.
Let $\widetilde \Pi_J h_0^\pi = \mathrm{arg}\min_{h \in \Theta^\pi_J} \|\Pi_K {\cal T}(h_0^\pi - h)\|_{L^2(S, A)}$ denote the sieve 2SLS projection of $h_0^\pi$ onto $\Theta^\pi_J$. Let $\Theta_{J, 1}^\pi = \{h \in \Theta_{J}^\pi \, | \, \|h\|_{2} = 1 \}$.
We make one additional assumption below for controlling the approximation error of using the sieve bases.
\begin{assumption}\label{ass: approx}
(a) $\sup_{h \in \Theta^\pi_{J, 1}}\|(\Pi_K {\cal T} - {\cal T})h\|_{L^2(S, A)} = o_J(1)$, where $o_J(1)$ refers to a quantity that converges to $0$ when $J \rightarrow \infty$; (b) $\|\widetilde{\Pi}_J (h^\pi_0 - \Pi_J h^\pi_0) \|_\infty \leq C_1\times \|h^\pi_0 - \Pi_J h^\pi_0\|_{\infty}$ for some constants $C_1$.
\end{assumption}
Assumption \ref{ass: approx}~(a) is a mild condition on approximating $\Theta^\pi_J$ by a sieve space $B_K$. For fixed $J$ (and $K$), $\sup_{h \in \Theta^\pi_{J, 1}}\|(\Pi_K {\cal T} - {\cal T})h\|_{L^2(S, A)}$ can be interpreted as an inherent Bellman error (for a fixed policy $\pi$), which is widely used in the literature of RL such as the analysis of fitted-q iteration (See Assumption 4.2 of \cite{agarwal2019reinforcement}).
Assumption \ref{ass: approx}~(b) is also mild because that $\|\widetilde \Pi_J (h_0^\pi - \Pi_J h_0^\pi)\|_{L^2(S, A)} \leq \| h_0^\pi - \Pi_J h_0^\pi\|_{L^2(S, A)}$ holds automatically by the projection property. Here we strengthen it in terms of the sup-norm.
To derive the sup-norm convergence rate, following the proof of \cite{chen2013optimal}, we split $\|\wh Q^\pi - Q^\pi\|_\infty$ into two terms. Let $
\widetilde Q^\pi(s, a) = \psi^J(s, a)^\top \widetilde c ~~\mbox{ with }~~ \widetilde c = [\Gamma_\pi^\top B(B^\top B)^-B^\top\Gamma_\pi]^- \Gamma_\pi^ \top B (B^\top B)^- B^\top H_0,
$
where
$$
H_0 = (h_0^\pi(S_{1, 0}, A_{1, 0}, S_{1, 1}),h_0^\pi(S_{1, 1}, A_{1, 1}, S_{1, 2}), \ldots, h_0^\pi(S_{N, T-1}, A_{N, T-1}, S_{N, T}))^\top \in \mathbb{R}^{NT}.
$$
Then by triangle inequality, we have $\|\wh Q^\pi - Q^\pi\|_\infty \leq \|\wh Q^\pi - \widetilde Q^\pi\|_\infty + \|Q^\pi - \widetilde Q^\pi\|_\infty$. The first term $\|\wh Q^\pi - \widetilde Q^\pi\|_\infty$ can be interpreted as an estimation error, while the second term $\|Q^\pi - \widetilde Q^\pi\|_\infty$ can be understood as the approximation error. Denote $ G^\pi_{\kappa,J} = \mathbb{E}[\kappa^J_\pi(S, A, S')\kappa^J_\pi(S, A, S')^\top]$ and $e_J = \lambda_{\min}(G^\pi_{\kappa,J})$.
Let
\begin{align*}
\zeta^\pi_{\kappa} & = \sup_{s, a, s'} \|[G^\pi_{\kappa, J}]^{-1/2} \kappa^J_\pi(s, a, s')\|_{\ell^2} & & G_b = \mathbb{E}[b^K(S, A)b^K(S, A)^\top] \\
\xi_{\psi} & = \sup_{s, a} \|\psi^J (s, a)\|_{\ell^1} && \zeta_{b} = \sup_{s, a} \|G_b^{-1/2} b^K(s, a)\|_{\ell^2}
\end{align*}
for each $J$ and $K$ by omitting their dependence on $J$ and $K$ for notation simplicity, and define $\zeta = \max\{\zeta_{b}, \zeta^\pi_{\kappa}\}$. In the following lemma, we derive bounds for the aforementioned two terms.
\begin{lemma}\label{lm: variance+bias bound}
(1) Let Assumptions \ref{ass: Markovian}-\ref{ass: stationary}, and Assumption \ref{ass: approx}(a) hold. If $ \zeta^2\sqrt{\log (NT)/NT}= O(1)$, then we have the following sup-norm bound for the estimation error.
\begin{align}\label{eqn: std error}
\|\wh Q^\pi - \widetilde Q^\pi\|_\infty = O_p \Big(\xi_{\psi} \sqrt{(\log J)/(NT e_J)}\Big).
\end{align}
(2) Let Assumptions \ref{ass: stationary}-\ref{ass: approx} hold. If $\zeta^2\sqrt{\log(J)\log (NT)/NT}= O(1)$ then the approximation error can be controlled by
\begin{align}\label{eqn: approximation error bound}
\|Q^\pi - \widetilde Q^\pi\|_\infty = O_p(\|Q^\pi- \overline \Pi_JQ^\pi \|_\infty).
\end{align}
\end{lemma}
By examining the proof of Lemma \ref{lm: variance+bias bound}, it is possible to derive the finite sample error bounds for
both $\|\wh Q^\pi - \widetilde Q^\pi\|_\infty$ and $\|Q^\pi - \widetilde Q^\pi\|_\infty$. We omit them for brevity.
\begin{theorem}\label{thm: sup-norm rate}
Let Assumptions \ref{ass: Markovian}-\ref{ass: approx} hold and $Q^\pi \in \Lambda_\infty(p,L)$ for some $L$. Suppose that the sieve space $\Psi_J$ is spanned by a B-spline or wavelet basis of \cite{cohen1993wavelets} with regularity larger than $p$, and $B_K$ is spanned by a wavelet, spline or cosine basis. If $J\sqrt{\log(J)\log (NT)/NT} = O(1)$, then we have:
\begin{equation}\label{eqn: h error}
\| \wh Q^\pi - Q^\pi \|_{\infty} = O_p \big(J^{-p/d} + \sqrt{J(\log J)/(NT)}\big).
\end{equation}
Further, by choosing $ J \asymp (\frac{NT}{\log(NT)})^{d/(2p+d)}$ and assuming $2p > d$ , we have for all $0\leq \|\alpha\|_{\ell_1} < p$,
\begin{equation}\label{eqn: derivatives Q error}
\| \partial^\alpha \wh Q^\pi - \partial^\alpha Q^\pi \|_{\infty} = O_p\left(\left(\frac{\log(NT)}{NT} \right)^{(p - \|\alpha\|_{\ell_1})/(2p+d)} \right).
\end{equation}
\end{theorem}
The smoothness parameter $p$ in Theorem \ref{thm: sup-norm rate} represents the smoothness level of the true $Q$-function and characterize the size of the functional class that the true $Q$-function belongs to. We require $2p > d$ in Theorem \ref{thm: sup-norm rate} mainly for deriving the sup-norm rate in order to achieve the optimality when considering H\"older class of functions. Theorem \ref{thm: sup-norm rate} shows that in terms of the batch data sample size of $NT$, the sup-norm rate of our 2SLS estimator $\widehat{Q}^\pi$ to $Q^\pi$ is the same as the optimal one in the classical non-parametric regression estimation \citep{stone1982optimal} using B-splines.
The sup-norm convergence rate of $\wh Q^\pi$ can be useful to develop uniform confidence bands (UCBs) for the $Q$-function using results in \cite{chen2013optimal} for example. Such UCBs may be incorporated into the framework of pessimistic RL algorithms such as \citep{jin2021pessimism,xie2021bellman}. In addition, we can also show that the sup-norm bounds on the constant factor $\gamma$ is of order $(1-\gamma)^{-3}$.
Finally, the results on the sup-norm rates for estimating the derivatives of the $Q$-function may be useful to some actor-critic algorithms such as \cite{silver2014deterministic,kallus2020statistically,xu2021doubly}.
\subsection{$L^2$-norm Convergence Rates}\label{subsec: L2 norm rates}
In this subsection we present the $L^2$ convergence rates of our 2SLS estimator for the $Q$-function. We do not require Assumption \ref{ass: approx}~(b) as the $L^2$-stability condition holds automatically.
\begin{theorem}\label{thm: L2 variance+bias bound}
Let Assumptions \ref{ass: Markovian}-\ref{ass: approx}~(a) hold. If $\zeta\sqrt{\log (NT)\log(J)/NT} = o(1)$, then:
\begin{align}\label{eqn: L2 std error+ approximation}
\|\wh Q^\pi - Q^\pi\|_2 = O_p \Big( \sqrt{J/(NT)} + \|Q^\pi - \overline \Pi_J Q^\pi\|_2\Big).
\end{align}
If $Q^\pi \in \Lambda_2(p,L)$ with $p>0$, and $\Psi_J$ and $B_K$ are spanned by some commonly used bases such as polynomials, trigonometric polynomials, splines and wavelets with regularity greater than $p$, by choosing $J \asymp (NT)^{d/(2p+d)}$, we have: for all $0\leq \|\alpha\|_{\ell_1} <p$,
\begin{equation*}\label{eqn: L2 Q error}
\| \partial^\alpha \wh Q^\pi - \partial^\alpha Q^\pi \|_{2} = O_p\left(\left(NT\right)^{( \|\alpha\|_{\ell_1} - p)/(2p+d)} \right).
\end{equation*}
\end{theorem}
According to Theorem \ref{thm: L2 variance+bias bound}, the sieve 2SLS estimator $\wh Q^\pi$ achieves the minimax optimal $L^2$-norm convergence rate to $Q^\pi$ under conditions much weaker than those for the optimal sup-norm convergence rate. Let $F$ be a known marginal distribution. It is well-known that one can estimate the value of a target policy $\pi$
\[
v^{\pi}=\int_{s \in {\cal S}}[\int_{a \in {\cal A}} \pi(a \, | \, S=s)Q^\pi(s, a)\text{d}a]F(\text{d}s)
\]
by the following simple plug-in sieve 2SLS estimator
\[
\wh v^{\pi}=\int_{s \in {\cal S}}[\int_{a \in {\cal A}} \pi(a \, | \, S=s) \wh Q^\pi(s, a)\text{d}a]F(\text{d}s).
\]
Theorem \ref{thm: L2 variance+bias bound} is particularly useful in establishing the asymptotic normality of $\sqrt{NT} (\wh v^{\pi}- v^{\pi})$.
\begin{remark}\label{rm:Shi}
(1) Recently \cite{shi2020statistical} presented a sieve LSTD estimator for $Q^\pi$ and obtained the $L^2$-norm rate of convergence (See (E.46) in appendix of their paper for more details) under some conditions including their Assumption (A3.) or a small discount factor $\gamma$ condition. They then apply their $L^2$-norm convergence rate to establish the $\sqrt{NT}$-asymptotic normality of plug-in sieve LSTD estimator for the value $v^{\pi}$. Note that their sieve LSTD is a special case of our sieve 2SLS with $B_K=\Psi_J$ and $K=J$, and the sieve LSTD automatically satisfies our Assumption \ref{ass: approx}~(a). Our Theorem \ref{thm: L2 variance+bias bound} establishes the $L^2$-norm convergene rate for their sieve LSTD estimator without the need to impose the strong condition of a small discount factor $\gamma$. Thus we may require weaker conditions for establishing the asymptotic normality of the plug-in sieve 2SLS estimator for the value. We leave details to the longer version of the paper.
(2) In this paper, to obtain the optimal rates of convergence in $L^2$-norm (and sup-norm) of our sieve 2SLS estimator for the $Q^\pi$ function, we assume strictly stationary data for simplicity. We note that \cite{shi2020statistical} did not impose this strict stationarity in their $L^2$-norm rate and asymptotic normality calculation. However, they need to assume the distribution of the initial state $S_{i,0}$ in the batch data is bounded away from $0$ uniformly in $i$. Indeed it is possible to replace the strict stationary condition in our Assumption \ref{ass: stationary} by imposing the geometric ergodicity and using the truncation argument to obtain the same sup-norm and $L^2$-norm convergence rates for our sieve 2SLS estimator. We leave it for the future work.
\end{remark}
\section{Conclusion}\label{sec: conclusion}
In this paper, we consider nonparametric estimation of $Q$-function of continuous states and actions in the OPE setting.
Under some mild conditions, we show that the NPIV model \eqref{Model: NPIV on $Q$-function} for estimating $Q$-function nonparametrically is well-posed in the sense of $L^2$-measure of ill-posedness, bypassing the need of imposing a strong condition on the discount factor $\gamma$ in the recent literature. The well-posedness property effectively implies that the minimax lower bounds for nonparametric estimation of $Q$-function coincide with those for a nonparametric regression in sup-norm and in $L^2$-norm under the i.i.d. setting. Under mild sufficient conditions, we also establish that the sup-norm and the $L^2$-norm rates of convergence of our proposed sieve 2SLS estimators for $Q$-function achieve the lower bounds, and hence are minimax-optimal. These rate results are useful for optimal estimation and inference on various functionals, such as the value, of the $Q$-function by plugging in our sieve 2SLS estimators. In particular, one can easily develop uniform confidence bands (UCBs) for the $Q$-function by slightly modifying the UCBs result in \cite{chen2013optimal} for a NPIV function estimated via a spline or wavelet sieve 2SLS. We leave this to future work due to the length of the paper.
In this paper we focus on the direct method of using Bellman equation to nonparametrically estimate $Q$-function in the OPE setting.
In the existing literature, there are two additional approaches to perform OPE. One is using the recently proposed marginal importance sampling for the infinite horizon setting such as \cite{liu2018breaking, nachum2019dualdice,xie2019towards,uehara2020minimax,zhang2020gendice,zhang2020gradientdice}. The other approach combines the direct method and marginal importance sampling to construct the so-called doubly robust estimators for the value of the target policy (see, e.g., \cite{kallus2019efficiently, tang2019doubly,shi2021deeply} among many others). Our results on the well-posedness and the minimax lower bounds for $Q$ function estimation should be useful to establish theoretical properties of these alternative approaches under conditions that are weaker than the existing ones.
Finally, since OPE serves as the foundation of many RL algorithms, our results on $Q$-function estimation of a target policy can also be useful to other policy learning methods such as those proposed in \cite{ernst_tree-based_2005,antos_learning_2008,le2019batch,liao2020batch,jin2021pessimism,zanette2021provable}. We leave details to future work.
\newpage