Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
65,179 characters · 12 sections · 63 citation commands
On Well-posedness and Minimax Optimal Rates of Nonparametric $Q$-function Estimation in Off-policy EvaluationAuthor names are sorted alphabetically
\def\spacingset#1{ {#1}} \spacingset{1} \if00 {
} \fi
\baselineskip=21pt
In recent years, there is a surging interest in studying batch reinforcement learning (RL), which utilizes previously collected data to perform sequential decision making 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 liao2018just, robotics pinto2016supersizing, digital marketing thomas2017predictive and precision medicine 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 distributional mismatch between the data collecting process and the target distribution for evaluation 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 $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 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., liu2018breaking) in the off-policy setting.
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 farahmand2016regularized,shi2020statistical,uehara2021finite among many others. Specifically, farahmand2016regularized established $L^2$ error bound for Bellman error of their $Q$-function estimator. 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) and Remark (ref) 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 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 chen2021instrumental) and theoretical work (such as duan2021optimal that focuses on the on-policy setting). The NPIV model has been extensively investigated in econometric literature; see, e.g., 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.
The rest of the paper is organized as follows. Section (ref) presents the framework of infinite-horizon MDPs and some necessary notations. In Section (ref), we show that the nonparametric $Q$-function estimation in sup-norm and in $L^2$-norm are both well-posed. Section (ref) 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), 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) briefly concludes. Most proofs are given in the appendix.
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 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
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.
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) 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., chen2015optimal,chen2013optimal.
To estimate $Q^\pi$, by Assumptions (ref) and (ref), one approach is to solve the following Bellman equation, i.e.,
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 (ref) 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$.
Assumptions (ref)-(ref) 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}$.
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
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.
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., ai2003efficient,newey2003instrumental,blundell2007semi). A generic NPIV model takes the expression as
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 (ref), we consider the following special form of a NPIV model with Assumptions (ref)-(ref) for $Q$-function estimation:
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 (ref). Therefore Model (ref) 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]\,. \]
In this subsection, we show that $Q$-function estimation is in general well-posed in sup-norm given by the following lemma.
Lemma (ref) 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 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 (ref)-(ref)). 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.
Lemma (ref) 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 (ref), we define a $L^2$-measure of ill-posedness as
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$.
Let $p_{\max} = \max(p_{1, \max}, p_{2, \max})$. In general, boundedness assumption on the data generating probability density in Assumption (ref) (a) is standard in the classical non-parametric estimation such as huang1998projection,chen2015optimal. In our setting, that the average visitation probability density is uniformly bounded away from $0$ is also called coverage assumption frequently used in RL literature such as 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 partial coverage if one is willing to impose some structure assumption on $Q^\pi$. See recent studies in duan2020minimax,xie2021bellman,agarwal2021theory,uehara2021pessimistic. Assumption (ref) (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) (b) is automatically satisfied because of Assumption (ref) (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.
Theorem (ref) 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), where $\widetilde Q$ denotes some estimator for $Q^\pi$. Then the first inequality in (ref) with Bellman equation (ref) 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). 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 antos_learning_2008,farahmand2016regularized,uehara2019minimax,feng2020accountable indeed are based on minimizing the $L^2$-norm of Bellman error. Therefore our Theorem (ref) provides a theoretical guarantee for their procedures. Notice that Theorem (ref) 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) with Theorem 11 of farahmand2016regularized immediately gives $L^2$-error bound for their estimator to the true $Q^\pi$. Applying our Theorem (ref) to Example 6 of 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) 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 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) in establishing this well-posedness.
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), under Assumptions (ref), (ref) and (ref), for any square integrable function $Q$ defined over ${\cal S} \times {\cal A}$, we have
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.
The following theorem provides lower bound results in terms of $L^2$-norm.
As we can see from Theorems (ref) and (ref), 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 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.
Given the NPIV Model (ref) as a reformulation of Bellman equation, we now adopt the idea from for example blundell2007semi,chen2013optimal to construct a sieve 2SLS estimator for $Q^\pi$. Define two sieve basis functions as
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 huang1998projection,chen2007large). The construction of wavelet bases can also be found in Appendix (ref). 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 (ref), 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
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
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.
Note that the sieve 2SLS estimator given in (ref) becomes the solution of the modified Bellman residual minimiazion in farahmand2016regularized when their function spaces are modeled by sieve ones.
An important quantity related to a generic NPIV model (ref) is called 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 (ref). 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 blundell2007semi, we define an average sieve $L^2$ measure of ill-posedness across $T$ decision points under Model (ref) as
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 (ref), $\tau_J$ grows to infinity as $J$ goes to infinity; see, e.g. blundell2007semi,chen2013optimal. By definition we have $ \tau_J \leq \overline{\tau} \lesssim 1$ for all $J \geq 1$. Thus Theorem (ref) directly implies that the NPIV Model (ref) is also well-posed under the $L^2$ sieve measure of ill-posedness defined in (ref). 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.
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.
Assumption (ref) is imposed to characterize the dependency among observations over time because the observed data modeled by MDP are 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 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) can be relaxed to stationary with certain algebraic $\beta$-mixing, and by using the matrix Bernstein inequality for general $\beta$-mixing of chen2015optimal one may obtain the same convergence rates as those in Theorems (ref) and (ref) 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) and (ref) hold, the average visitation probability density $\bar d^{\pi^b}_T$ used in Assumption (ref) 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.
Assumption (ref) (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 agarwal2019reinforcement). Assumption (ref) (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 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
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.
By examining the proof of Lemma (ref), 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.
The smoothness parameter $p$ in Theorem (ref) 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) mainly for deriving the sup-norm rate in order to achieve the optimality when considering H\"older class of functions. Theorem (ref) 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 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 chen2013optimal for example. Such UCBs may be incorporated into the framework of pessimistic RL algorithms such as 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 silver2014deterministic,kallus2020statistically,xu2021doubly.
In this subsection we present the $L^2$ convergence rates of our 2SLS estimator for the $Q$-function. We do not require Assumption (ref) (b) as the $L^2$-stability condition holds automatically.
According to Theorem (ref), 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) is particularly useful in establishing the asymptotic normality of $\sqrt{NT} (\wh v^{\pi}- v^{\pi})$.
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 (ref) 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 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 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., 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 ernst_tree-based_2005,antos_learning_2008,le2019batch,liao2020batch,jin2021pessimism,zanette2021provable. We leave details to future work.