On Well-posedness and Minimax Optimal Rates of Nonparametric $Q$-function Estimation in Off-policy Evaluation⁰⁰footnotetext: Author names are sorted alphabetically

In recent years, there is a surging interest in studying batch reinforcement learning (RL), which utilizes previously collected data to perform sequential decision making (Sutton & Barto, 2018) 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 (Liao et al., 2018), robotics (Pinto & Gupta, 2016), digital marketing (Thomas et al., 2017) and precision medicine (Kosorok & Laber, 2019), 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 (Levine et al., 2020).

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 (Stone, 1982; Tsybakov, 2009). 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ölder 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., Liu et al. (2018)) in the off-policy setting.

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 2 implies that $|r(S_{t},A_{t})|\leq R_{\max}$ for all $t\geq 0$. 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., Chen & Christensen (2015, 2018).

To estimate $Q^{\pi}$, by Assumptions 1 and 2, 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 (1) 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\geq 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\leq 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 1-3 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

The corresponding expectation with respect to $\bar{d}^{\pi^{b}}_{T}$ is denoted by $\overline{\mathbb{E}}$. We further let $q^{\pi}_{t}(s^{\prime},a^{\prime}\,|\,s,a)$ be the $t$-step visitation probability density function induced by a policy $\pi$ at $(s^{\prime},a^{\prime})$ given an initial state-action pair $(s,a)\in{\cal S}\times{\cal A}$.

Notation: For generic sequences $\{\varpi(N)\}_{N\geq 1}$ and $\{\theta(N)\}_{N\geq 1}$, 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^{\prime})$ or $(S,A,S^{\prime})$ to represent some generic transition tuples, where the transition probability density is $q$. Lastly, we introduce the Hölder 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, $\lfloor p\rfloor$ denotes the integer no larger than $p$ for any $p>0$, a non-negative vector $\alpha=(\alpha_{1},\alpha_{2},\cdots,\alpha_{d})$ and

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., Ai & Chen (2003); Newey & Powell (2003); Blundell et al. (2007)). 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 (1), we consider the following special form of a NPIV model with Assumptions 1-3 for $Q$-function estimation:

for $0\leq t\leq T-1$, where

We also write $h^{\pi}(s,a,s^{\prime};Q)$ as $h^{\pi}(Q)(s,a,s^{\prime})$ 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 (1). Therefore Model (3) 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^{\prime})$ 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^{\prime})\to L^{2}(S,A)$, i.e., for every $(s,a)\in{\cal S}\times{\cal A}$,

and in particular,

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 1, under Assumptions 1, 3 and 4, 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^{\prime}_{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 2 and 3, 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 (Stone, 1982). 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 (3) as a reformulation of Bellman equation, we now adopt the idea from for example Blundell et al. (2007); Chen & Christensen (2018) 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 Huang et al. (1998); Chen (2007)). The construction of wavelet bases can also be found in Appendix B. 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 (3), 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^{\prime})=\psi^{J}(s,a)-\gamma\psi_{\pi}^{J}(s^{\prime})$, and correspondingly $\Gamma_{\pi}=\Psi-\gamma G_{\pi}.$ We also denote $\kappa_{Jj}^{\pi}(s,a,s^{\prime})=\psi_{Jj}(s,a)-\gamma\int_{a^{\prime}\in{\cal A}}\pi(a^{\prime}\mid s^{\prime})\text{d}a^{\prime}\psi^{\pi}_{Jj}(s^{\prime},a^{\prime})$ for each element of $\kappa_{\pi}^{J}(s,a,s^{\prime})\in\mathbb{R}^{J}$. Then the sieve 2SLS estimator for $Q^{\pi}$ can be constructed as