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.
106,832 characters · 14 sections · 60 citation commands
STEEL: Singularity-aware Reinforcement LearningAuthor names are sorted alphabetically. This work does not relate to the position at Amazon. We thank Elynn Chen, Xi Chen, Max Cytrynbaum, Lars Peter Hansen, Clifford M. Hurvich, Chengchun Shi, Jin Zhou and other seminar participants at LSE, UCL, Cambridge, NYU Stern, University of Chicago for useful comments.
\def\spacingset#1{ {#1}} \spacingset{1} \if00 {
} \fi \if10 {
} \fi
\baselineskip=21pt
We study batch reinforcement learning (RL), which aims to learn an optimal policy using the pre-collected data without further interacting with the environment. Arguably, the biggest challenge for solving such a problem is the distributional mismatch between the batch data distribution and those induced by some candidate policies levine2020offline.
To avoid the issue of distributional mismatch, prior works require absolute continuity assumption, e.g., there does not exist a non-overlapping region between the batch data distribution and the distribution induced by some policies, for finding an optimal policy. For example, classical methods such as antos_learning_2008 require the batch data to contain every possible state-action pair. Recent literature kumar2019stabilizing,jin2021pessimism has found that, by incorporating the idea of pessimism, the requirement on the batch data is relaxed to contain state-action pairs induced by an optimal policy. However, the absolute continuity is not known a priori and could be easily violated. In this case, singularity arises, e.g.,, there exists a non-overlapping region between the batch data distribution and the target distribution induced by some policy such as an optimal one, and all aforementioned methods fail. See formal definitions of absolute continuity and singularity in Section (ref).
To address the issue of singularity, in this paper, we propose an efficient and singularity-aware policy-iteration-type algorithm for finding an optimal policy under the framework of an infinite-horizon Markov decision process (MDP) with continuous states and actions. By saying an efficient algorithm, we refer to that the sample complexity requirement in finding an optimal policy is polynomial in terms of key parameters zhan2022offline. We call our algorithm STEEL: SingulariTy-awarE rEinforcement Learning.
Our algorithm is motivated by a new error analysis on off-policy evaluation (OPE), which has been extensively studied in the recent literature shi2020statistical. The goal of OPE is to use the batch data for evaluating the performance of other policies. By leveraging Lebesgue's Decomposition Theorem, we decompose the error of OPE into two parts: the absolutely continuous part and the singular one with respect to the data distribution. For the absolutely continuous part, which can be calibrated by the behavior policy using the change of measure, standard OPE methods can be applied for controlling the error. For the singular part, we use the maximum mean discrepancy and leverage distributionally robust optimization to characterize its worst-case error measured by the behavior policy. Once we understand these two sources of the OPE error induced by any given target policy, a new estimating method for OPE without requiring absolute continuity can be formulated, based on which a policy iteration algorithm with pessimism is proposed.
From theoretical perspective, we show that under some technical conditions, the regret of our estimated policy converges to zero at a satisfactory rate in terms of total decision points in the batch data even when singularity arises. This novel result demonstrates that our method can be more applicable in solving batch RL problems, in comparison to existing solutions. More specifically, when the distribution induced by the optimal policy is covered by our batch data generating process in the usual manner, we recover the existing theoretical results given by those pessimistic RL algorithms xie2021bellman,fu2022offline. In contrast, when absolute continuity fails, our algorithm is provable to find an optimal policy with a finite-sample regret warranty. To the best of our knowledge, this is the first finite-sample regret guarantee in batch RL without assuming any form of absolute continuity. In contrast, existing methods such as antos_learning_2008,chen2016personalized,kallus2020doubly can only allow singularity for certain state-action space and still require absolute continuity to some extent. For example, chen2016personalized,kallus2020doubly leverage kernel smoothing techniques to address the issue of singularity on the action space, which is known to suffer from the curse of dimensionality when the action space is large. Moreover, our work can provide theoretical guidance on the existing algorithms aiming to find a deterministic optimal policy in a continuous action space. For example, our STEEL method and the related theoretical results can be helpful for improving the understanding of the celebrated deterministic policy gradient method silver2014deterministic.
To further demonstrate the effectiveness of our algorithm, we consider a contextual bandit problem and conduct extensive simulation studies. We show that compared with two existing baseline methods, under a possible singularity, our algorithm has a significantly better finite-sample performance. In particular, we observe that our algorithm converges faster and is more robust when the singularity arises. We also apply our method to a personalized pricing application using the data from a US auto loan company, and find that our method outperforms the existing baseline methods.
Lastly, we propose a two-step adaptive STEEL that relieves the selection of several tuning parameters in the original STEEL. We conduct a simulation study to demonstrate its superior performance.
The rest of the paper is organized as follows. In Section (ref), we introduce our setup, the discrete-time homogeneous MDP with continuous states and actions. We introduce related notations and also the problem formulation. Then, an illustrative example on the contextual bandit problem is presented in Section (ref) for describing the challenge of policy learning under singularity. We also briefly introduce our solution in this section. In Section (ref), we formally introduce STEEL for finding an optimal policy and its adaptive version. A comprehensive theoretical study of our algorithm is given in Section (ref). Section (ref) demonstrates the empirical performance of our methods using both simulation studies and a (semi-)real data application. Section (ref) concludes this paper. In the appendix, we discuss our work related to the existing literature, present some additional discussions on the theoretical results and assumptions, show all technical proofs and provide more numerical results.
In this section, we briefly introduce a framework of the discrete-time homogeneous MDP, which is the foundation of many RL algorithms, and the related notations sutton1998introduction. Consider a trajectory $\{S_t, A_t, R_t \}_{t \geq 0}$, where $S_t$ denotes the state of the environment at the decision point $t$, $A_t$ is the action and $R_t$ is the immediate reward received from the environment. We use ${\cal S}$ and ${\cal A}$ to denote the state and action spaces, respectively. Throughout this paper, we assume both ${\cal S} \subseteq \mathbb R^{d_S}$ and ${\cal A}\subseteq \mathbb R^{d_A}$ are continuous and multi-dimensional. Specifically, let ${\cal A} = \bigotimes_{i = 1}^{d_A} {\cal A}_i$ with $d_A \geq 1$, where ${\cal A}_i$ is the space for $i$-th coordinate of the action. Under the setup of MDP, the following standard assumptions are imposed on the trajectory $\{S_t, A_t, R_t \}_{t \geq 0}$.
By Assumption (ref), we define a reward function as $r(s, a) = \mathbb{E}[R_t \, | \, S_t = s, A_t = a]$ for $t \geq 0$. The uniformly bounded assumption on the immediate reward $R_t$ is used to simplify the technical proofs and can be relaxed. We remark that one can implement hypothesis testings to justify the use of a time-homogeneous MDP to model the batch data shi2020does,li2022testing.
An essential goal of RL is to find an optimal policy that maximizes some utility. In this paper, we consider expected discounted sum of rewards to measure the performance of each policy. A policy is defined as a decision rule that an agent chooses her action $A_t$ based on the environment state $S_t$ at each decision point $t$. In this paper, we focus on the stationary policy $\pi$, which is a vector-valued function mapping from the state space ${\cal S}$ into a probability distribution over the action space ${\cal A}$. Specifically, $\pi = \bigotimes_{i = 1}^{d_A} \pi_i$, where $\pi_i$ is a function mapping from ${\cal S}$ into a distribution over ${\cal A}_i$. For each policy $\pi$, one can define a $Q$-function to measure its performance starting from any state-action pair $(s, a) \in {\cal S} \times {\cal A}$, denoted by
where $\mathbb{E}^\pi$ refers to the expectation that all actions along the trajectory follow the stationary policy $\pi$. We evaluate the overall performance of a policy by the so-called policy value defined as
where $\nu$ is some known reference distribution. Here, for any function $Q$ defined over ${\cal S} \times {\cal A}$, we define $Q(s, \pi(s)) = \int_{a \in {\cal A}}Q(s, a)\pi(a \, | \, s)da$. Our goal in this paper is to search for an in-class optimal policy $\pi^\ast$ such that
where $\Pi = \bigotimes_{i = 1}^{d_A} \Pi_i$ and $\Pi_i$ is some pre-specified class of stationary policies for $i$-th coordinate of ${\cal A}$. Some commonly used policy classes include linear decision functions, neural networks and decision trees. The sufficiency of focusing on the stationary policies is guaranteed by Assumptions (ref) and (ref). See Section 6.2 of puterman1994markov for the justification. We also remark that stationary policy does not rule out the deterministic policy, which is a function mapping from the state space ${\cal S}$ into the action space ${\cal A}$.
In this work, we focus on the batch setting, where the observed data consist of $N$ independent and identically distributed copies of $\{S_t, A_t, R_t\}_{t \geq 0}$ up to $T$ decision points. For the $i$-th trajectory, where $1 \leq i \leq N$, the data can be represented by $\{S_{i, t}, A_{i, t}, R_{i, t}, S_{i, t+1}\}_{0 \leq t < T}$. We aim to leverage the batch data to find an in-class optimal policy $\pi^\ast$ defined in (ref). The following standard assumption is imposed on our batch data generating process.
Next, we introduce the average visitation probability measure. Let $q^{\pi^b}_t$ be the marginal probability measure over ${\cal S} \times {\cal A}$ at the decision point $t$ induced by the behavior policy $\pi^b$. Then the average visitation probability measure across $T$ decision points is defined as $$ \bar d^{\pi^b}_T = \frac{1}{T}\sum_{t = 0}^{T-1}q^{\pi^b}_t. $$ The corresponding expectation with respect to $\bar d^{\pi^b}_T$ is denoted by $\overline \mathbb{E}$. Similarly, we can define the discounted visitation probability measure over ${\cal S} \times {\cal A}$ induced by a policy $\pi$ as
where $q_t^\pi$ is the marginal probability measure of $(S_t, A_t)$ induced by the policy $\pi$ with the initial state distribution $\nu$. For notation simplicity, we also use $\bar d^{\pi^b}_T$ and $d_\gamma^\pi$ to denote their corresponding probability density function when there is no confusion. Lastly, we use $\mathbb{Q} \ll \mathbb{P}$ when $\mathbb{Q}$ is absolutely continuous with respect to $\mathbb{P}$, and $\mathbb{Q} \perp \mathbb{P}$ when $\mathbb{Q}$ is singular to $\mathbb{P}$. More specifically, $\mathbb{Q} \ll \mathbb{P}$ means that if for any measurable set ${\cal F}$ such that $\mathbb{P}({\cal F}) = 0$, then $\mathbb{Q}({\cal F}) = 0$ as well. Lastly $\mathbb{Q} \perp \mathbb{P}$ means that there exists a measurable set ${\cal F}$ such that $\mathbb{Q}({\cal F}) = \mathbb{P}({\cal F}^c) = 0$.
Additional notations: For generic sequences $\{\varpi(N)\}$ and $\{\theta(N)\}$, 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. For any random variable $X$, we use $L^q_{\mathbb{P}}(X)$ to denote the class of all measurable functions with finite $q$-th moments for $1 \leq q \leq \infty$, where the underlying probability measure is $\mathbb{P}$. We may also write it as $L^q_{\mathbb{P}}$ when there is no confusion about the underlying random vectors. Then the $L^q$-norm is denoted by $\|\bullet\|_{L^q_{ \mathbb{P}}(X)}$. We use $\|\bullet\|_\infty$ to denote the point-wise sup-norm for a vector-valued function. For example, when $\pi$ is a deterministic policy, $\|\pi\|_{\infty}$ returns a vector with sup-norm on each coordinate for $\pi \in \Pi$. In addition, we often use $(S, A, R, S')$ or $(S, A, S')$ to represent a generic transition tuple. Lastly, we define the maximum mean discrepancy (MMD) between two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ as
where ${\cal H}_k$ is a reproducing kernel Hilbert space (RKHS) with the kernel $k$ and the corresponding norm is denoted by $\|\bullet\|_{{\cal H}_k}$.
{
In this section, we use the offline contextual bandit problem manski2004statistical as an example to illustrate the challenge of policy learning under singularity and our main idea to address it. Note that the contextual bandit problem is a special case of batch RL (i.e., $T = 0$).
Suppose we have a batch dataset ${\cal D}^0_N = \{S_{i, 0}, A_{i, 0}, R_{i, 0}\}_{1 \leq i \leq N}$ which contains i.i.d. copies from $(S_0, A_0, R_0)$, where $S_0 \sim \nu_0$ and $\nu_0$ is some unknown distribution. The target is to find an in-class optimal policy $\pi^\ast$ such that
Recall that $r(s, a) = \mathbb{E}\left[R_0 \, | \, S_0 = s, A_0 =a\right]$.
Most existing methods for solving (ref) rely on a key assumption that $\nu \times \pi \ll \nu_0 \times \pi^b$ for all $\pi \in \Pi$, under which one is able to use the batch data ${\cal D}^0_N$ to calibrate $\pi$ and evaluate its performance via estimating ${\cal V}_0(\pi)$ for all $\pi \in \Pi$. For instance, the regression-based approaches qian2011performance,bhattacharya2012inferring consider a discrete action space, and require (i) $\pi^b(a \, | \, s)$ is uniformly bounded away from 0 for all $s$ and $a$, and (ii) $\nu = \nu_0$. In this case, the absolute continuity holds. Meanwhile, the popular classification-based approaches zhao2012estimating, which crucially rely on the inverse propensity weighting formulation, also have the same requirement. However, due to the distributional shift induced by $\pi$, such absolutely continuous assumption may not hold in general. There is a recent streamline of research studying contextual bandits under the framework of distributionally robust optimization such as mo2021learning,qi2022robustness,adjaho2022externally,si2023distributionally and the reference therein. These works investigate policy learning in the presence of distributional shifts in the covariates or rewards when deploying the policy in the future. In particular, adjaho2022externally considered to use Wasserstein distance for quantifying the distributional shift and can allow the singularity for such a shift. However, none of them study the policy learning when there is a singularity issue in terms of the policy during the training procedure. For example, when $\pi^b$ refers to some stochastic policy used to collect the data and $\Pi$ is a class of deterministic policies, $\pi$ becomes singular to $\pi^b$, i.e., $\pi \perp \pi^b$ for all $\pi \in \Pi$. In this case, most existing methods may fail to find a desirable policy.
To address such singularity issue induced by the deterministic policy with respect to the stochastic one, existing solutions either adopt the kernel smoothing techniques on $\pi$ in order to approximately estimate ${\cal V}_0(\pi)$ chen2016personalized or impose some (parametric) structure assumption on the reward function $r$ chernozhukov2019semi. The first type of approaches requires the selection of kernel and the tuning on the bandwidth for approximating all deterministic policies, while the latter one could suffer from the model mis-specification due to the strong (parametric) model assumption. It is also well-known that the performance of the kernel smoothing deteriorates when the dimension of the action space increases. In addition, these methods cannot handle general settings such as that $\nu$ is also singular to $\nu_0$, i.e., there exists a covariate shift problem.
In the following, we briefly introduce our method for policy learning without requiring absolute continuity of the target distribution (i.e., $\nu \times \pi$) with respect to the data distribution (i.e., $\nu_0 \times \pi^b$) in this contextual bandit problem. The idea relies on the following observation. Consider a fix policy $\pi \in \Pi$. Let $\widetilde{r}$ be any estimator for the reward function. It can be easily seen that
By leveraging Lebesgue's Decomposition Theorem, we can always represent $\nu\times\pi$ as $$ \nu\times\pi = \widetilde \lambda_1^\pi + \widetilde \lambda_2^\pi, $$ where $\widetilde \lambda_1^\pi \ll (\nu_0\times\pi^b)$ and $\widetilde \lambda_2^\pi \perp (\nu_0\times\pi^b)$. Since $\widetilde \lambda^\pi_1$ and $\widetilde \lambda^\pi_2$ are finite measures, we normalize them and rewrite the above decomposition as $$ \nu\times\pi = \widetilde \lambda_1^\pi({\cal S} \times {\cal A}) \lambda_1^\pi + \widetilde \lambda_2^\pi({\cal S} \times {\cal A})\lambda_2^\pi, $$ where $\lambda^\pi_1$ and $\lambda^\pi_2$ are two probability measures. In particular, if $ \widetilde \lambda_i^\pi({\cal S} \times {\cal A}) = 0$, the corresponding $\lambda_i^\pi$ can be chosen as an arbitrary probability measure. See Theorem 5.6.2 of gray2009probability for more details. Given this decomposition, one can further show that
In order to have an accurate estimation of ${\cal V}_0(\pi)$, one needs to find an $\widetilde{r}$ such that the absolutely continuous and singular parts in the above equality are minimized. For the absolutely continuous part, since $\lambda_1^\pi$ is unknown, define ${\cal W}$ as some class of symmetric functions and assume $\lambda^\pi_1/(\nu_0\times\pi^b) \in {\cal W}$, we can show that
Then the right-hand side of the above inequality can be properly controlled using the batch data because $(S_0, A_0)$ now follows $\nu_0 \times \pi^b$. Essentially, one can find a good $\widetilde{r}$ that minimizes the right hand side of the above inequality so as to control the error induced by the absolutely continuous part. To handle the singular part, we adopt the idea of distributionally robust optimization rahimian2019distributionally with MMD. We can show that
Summarizing the above derivations together, we can quantify the error of using $\widetilde r$ for estimating ${\cal V}_0(\pi)$ as
where the last inequality is given by Lemma (ref) in the later section under some mild conditions. Moreover, it can be checked that if $\widetilde{r} = r$, the right-hand side of the above inequality vanishes. These facts motivate us to estimate the reward function $r$ and later ${\cal V}_0(\pi)$ via
It is remarked that the goal of analyzing or upper bounding the estimation error is to construct a valid loss function when there is a singularity issue. Moreover, $\widetilde \lambda_2^\pi({\cal S} \times {\cal A})$ and $\text{MMD}_k(\lambda_2^\pi, \nu_0 \times \pi^b)$ are irrelevant to $\tilde r$ and could be estimated when $\pi$ is known. Once we are able to provide a valid estimation for ${\cal V}_0(\pi)$, an optimization rountine can be implemented to estimate $\pi^\ast$, where we incorporate the idea of pessimism. Specifically, for each given $\widetilde{r}$, we first implement the kernel ridge regression using ${\cal D}_N^0$ for estimating $\mathbb{E}\left[R_0 - \widetilde{r} \, | \, S_0 = \bullet, A_0 = \bullet\right]$. Denote the resulting estimator by $\widehat \mathbb{E}\left[R_0 - \widetilde{r} \, | \, S_0 = \bullet, A_0 = \bullet\right]$. Note that $\widetilde{r}$ is some candidate reward function. Then we propose to compute the optimal policy via solving the maximin problem
where ${\cal R}$ is some pre-specified class of functions for modeling the true reward function $r$ and $\mathbb{E}_{N}$ refers to the empirical average over the batch data ${\cal D}^0_N$. Two constants $\varepsilon_1 >0$ and $\varepsilon_2 > 0$ are used to quantify the uncertainty for estimating $r$ and also control the degree of pessimism. We remark that the RKHS norm in (ref) can be computed explicitly when kernel ridge regression is used in estimating $\widehat \mathbb{E}\left[R_0 - \widetilde{r} \, | \, S_0 = \bullet, A_0 = \bullet\right]$. Under some technical conditions, with properly chosen $\varepsilon_1$ and $\varepsilon_2$, we can show that the true reward function $r$ always belongs to the feasible set of (ref). Therefore, by implementing the above algorithm, we search a policy that maximizes the most pessimistic estimation of its value ${\cal V}_0(\pi)$ within the corresponding uncertainty set. The proposed algorithm will produce a valid policy with regret guaranteed and without assuming absolute continuity.}
In this section, we consider policy learning in batch RL under the possible singularity, which generalizes the previous contextual bandit example. Our proposed algorithm for obtaining $\pi^\ast$ is motivated by the following analysis of OPE.
For any given policy $\pi$, the target of OPE is to use the batch data to estimate the policy value ${\cal V}(\pi)$ defined in (ref). Note that by the definition of the discounted visitation probability measure, we can show that $$ {\cal V}(\pi) = \int_{{\cal S} \times {\cal A}} r(s, a) d_\gamma^\pi(\text{d}s, \text{d}a). $$ A direct approach to perform OPE is via estimating $Q^\pi$ defined in (ref). Let $\widetilde{Q}$ be any estimator for $Q^\pi$ and define the corresponding estimator for the policy value as $\widetilde{{\cal V}}(\pi) = (1-\gamma) \mathbb{E}_{S_0 \sim \nu}[\widetilde Q(S_0, \pi(S_0))]$. Then we have the following lemma to characterize the estimation error of $\widetilde{{\cal V}}(\pi)$ to ${\cal V}(\pi)$.
Based on Lemma (ref), if $d_\gamma^\pi \ll \bar d^{\pi^b}_T$, then by change of measure and assuming that $\frac{d_\gamma^\pi}{\bar d^{\pi^b}_T} \in {\cal W}$, which is a symmetric class of functions, we can obtain that
This naturally motivates a minimax estimating approach to learn $Q^\pi$ and hence ${\cal V}(\pi)$, i.e., $$ \min_{\widetilde Q}\sup_{w \in {\cal W}} \overline \mathbb{E}\left[w(S, A)\left(R + \gamma \widetilde{Q}(S', \pi(S')) - \widetilde{Q}(S, A) \right)\right], $$ which has been used in the literature of OPE jiang2020minimax.
However, as discussed before, due to the potentially large state-action space, it is quite usual that some state-action pairs induced by the target policy $\pi$ are not covered by the batch data generating process, causing the issue of non-overlapping region. In addition, there are many applications where $\pi \in \Pi$ is a deterministic policy but the behavior one is stochastic silver2014deterministic,lillicrap2015continuous. In either of the two cases, $d_\gamma^\pi \ll \bar d^{\pi^b}_T$ fails to hold and singularity arises. Then the above min-max estimating approach may no longer be valid for OPE. To address this issue, with some abuse of notations, we first decompose $$ d_\gamma^\pi = \widetilde \lambda_1^\pi({\cal S} \times {\cal A}) \lambda_1^\pi + \widetilde \lambda_2^\pi({\cal S} \times {\cal A})\lambda_2^\pi, $$ where $\lambda^\pi_1$ and $\lambda^\pi_2$ are two probability measures, and $ \widetilde \lambda_i^\pi({\cal S} \times {\cal A}) >0$ with $\widetilde \lambda_1^\pi({\cal S} \times {\cal A}) + \widetilde \lambda_2^\pi({\cal S} \times {\cal A}) = 1$. Then we can decompose the OPE error as
The absolutely continuous part can be properly controlled by using the above min-max formulation. However, the singularity of $\lambda_2^\pi$ with respect to $\bar d^{\pi^b}_T$ is the major obstacle that makes most existing OPE approaches not applicable. To address this issue, one must rely on the extrapolation ability of $Q^\pi$. As the difficulty of OPE largely comes from the distributional mismatch between $d_\gamma^\pi$ and $\bar d^{\pi^b}_T$, we leverage the kernel mean embedding approach to quantifying the difference between $\lambda_2^\pi$ and $\bar d^{\pi^b}_T$ in order to control the singular part. See Lemma (ref) in the appendix for the existence of kernel mean embeddings, which follows from Lemma 3 of gretton2012kernel.
Next, we present our formal result in bounding the OPE error of $\widetilde {\cal V}(\pi)$. Define the Bellman residual operator as $$ {\cal T}^\pi\widetilde{Q}= {\cal B}^\pi{\widetilde Q}- \widetilde Q, $$ where ${\cal B}^\pi$ is the Bellman operator, i.e., $$ {\cal B}^\pi\widetilde Q(\bullet, \bullet) = \mathbb{E}[R + \gamma \widetilde{Q}(S', \pi(S')) \, | \, S = \bullet, A = \bullet] $$ for any transition tuple $(S, A, R, S')$. Since $\lambda_1^\pi \ll \bar{d}^{\pi^b}_T$, by the Radon-Nikodym Theorem, we can define the Radon-Nikodym derivative as $$ \omega^\pi(s, a) = \frac{\lambda_1^\pi(s, a)}{\bar d^{\pi^b}_T(s, a)}, $$ for every $(s, a) \in {\cal S} \times {\cal A}$. We have the following key lemma for our proposal. For notation simplicity, let $Z = (S, A)$ and denote ${\cal Z} = {\cal S} \times {\cal A}$.
Lemma (ref) provides an upper bound for the estimation error of OPE using any estimator $\widetilde{Q}$ for $Q^\pi$. It can be further checked that if $\widetilde{Q} = Q^\pi$, by Bellman equation, the RHS of (ref) becomes $0$, which demonstrates the validity of using it as an objective function to find $Q^\pi$. Since the first term on the right-hand-side of Equation (ref) can be calibrated by the data distribution due to absolute continuity, under some mild conditions, one can expect that it can be estimated efficiently. In contrast, the second term becomes hard to estimate, whose convergence rate is typically slower than the first one if consistent. Nevertheless, based on the above analysis, we propose to estimating $Q^\pi$ by solving the following minimax problem. Without loss of generality, assume that $\pm 1 \in {\cal W}$.
To use the above procedure for OPE, for each policy $\pi$, one needs to estimate $\widetilde \lambda_1^\pi({\cal S} \times {\cal A}), \widetilde \lambda_2^\pi({\cal S} \times {\cal A})$ and $\text{MMD}_k(\bar d^{\pi^b}_T, \lambda_2^\pi)$ first or find some constants that serve as upper bounds. This new method will serve as the foundation of our proposed algorithm developed below.
Recall that our goal is to leverage the batch data ${\cal D}_N$ to estimate the in-class optimal policy $\pi^\ast$. For any policy $\pi$, we can implement the empirical version of (ref) for obtaining the estimation of $Q^\pi$ and hence perform the policy evaluation. This motivates us to develop a pessimistic policy iteration algorithm for finding $\pi^\ast$.
Pessimism in batch RL serves as the main tool for efficient policy optimization by quantifying the uncertainty of the estimation and discouraging the exploration of the learned policy from visiting the less explored state-action pair in the batch data. The success of the pessimsitic-typed algorithms has been demonstrated in many applications kumar2019stabilizing,bai2022pessimistic. In terms of the data coverage, instead of the full-coverage assumption (i.e., $\bar{d}^{\pi^b}_T$ is uniformly bounded away from $0$) required by many classic RL algorithms, algorithms with a proper degree of pessimism only require that the in-class optimal policy $\pi^\ast$ is covered by the behavior one, which is thus more desirable. Adapting the pessimism idea to our setting without assuming absolute continuity, we expect to develop an algorithm that finds the optimal policy by at most requiring the data coverage assumption such that $\omega^{\pi^\ast} \in {\cal W}$. This requirement is much weaker than those needed by all existing RL algorithms.
Let ${\cal F}$ be some pre-specified class of functions over ${\cal S} \times {\cal A}$, which is used to model $Q^\pi$ with $\pi \in \Pi$. A key building block of our proposed algorithm is to construct the following two uncertainty sets for $Q^\pi$
where $\varepsilon^{(1)}_{NT} > 0$ and $\varepsilon^{(2)}_{NT} > 0$ are some tuning parameters possibly depending on $N$ and $T$, which will be specified later. Here
for any function $f$, and $\widehat{{\cal T}}^\pi$ is an estimator of ${\cal T}^\pi$ to be specified later.
Based on the defined uncertainty sets $\Omega_j, j = 1, 2$, we propose to estimate the in-class optimal policy $\pi^\ast$ via
i.e., maximizing the worst-case policy value within the uncertainty sets. Note that our optimization problem (ref) is free of $\widetilde \lambda_1^\pi({\cal S} \times {\cal A})$, $\widetilde \lambda_2^\pi({\cal S} \times {\cal A})$ and $ \text{MMD}_k(\bar d^{\pi^b}_T, \lambda_2^\pi)$, compared with OPE using (ref). Denote the resulting estimated policy as $\widehat{\pi}$. In Section (ref), we provide a regret guarantee for $\widehat{\pi}$ in finding $\pi^\ast$ under minimal data coverage assumption. The policy optimization problem (ref), in its original form, may be difficult to solve because of the constraint set for $Q$, especially when ${\cal F}$ and ${\cal W}$ are highly complex such as neural networks. In the following, we propose to solve it via the dual formulation of the inner minimization problem in (ref).
Let $\rho = (\rho_1, \rho_2)$ be dual variables (i.e., Lagrange multipliers). Define a Lagrangian function as
Based on the formulation of $L_{NT}(Q, \rho, \pi) $, we consider an alternative way to estimating the optimal policy by solving the equivalent optimization problem
where $\succeq$ refers to the component-wise comparison. Note that compared with (ref), Problem (ref) can be solved in a more efficient manner as the optimization with respect to the two dual variables can be easily performed.
Denote the resulting estimated policy given by (ref) as $\widehat{\pi}_{\text{dual}}$. By the weak duality, it can always be shown that
Therefore, solving Problem (ref) can also be viewed as a policy optimization algorithm with pessimism. However, the strong duality for the primal and dual problems may not hold as the primal problem is not convex with respect to $Q$, which therefore leads to that $\widehat{\pi} \neq \widehat{\pi}_{\text{dual}}$ in general. More seriously, the existence of the duality gap will result in a non-negligible regret of $\widehat{\pi}_{\text{dual}}$ in finding $\pi^\ast$. Nevertheless, in Section (ref) below, we show that under one additional mild assumption, $\widehat{\pi}_{\text{dual}}$ indeed can achieve the same regret guarantee as that of $\widehat{\pi}$.
Now, to solve (ref), we first estimate ${\cal T}$ via kernel ridge regression. Specifically,
with the regularization parameter $\zeta_{NT} > 0$. Denote
Thanks to the representer theorem, we can show that
where $I_{NT}$ is an identity matrix with the dimension $NT$.
Similarly, we use a RKHS to model ${\cal W}$. We set ${\cal W} = \{w \, \mid \, \|w\|_{{\cal H}_k} \leq C \}$ for some constant $C>0$. Based on the discussion after Lemma (ref), ideally $C =\text{MMD}_k(\bar d^{\pi^b}_T, d^{\pi^\ast}_\gamma)$, which is unknown in practice. But one can first enforce $\rho_1 = 0$ to compute a good estimated optimal policy and then approximate $\text{MMD}_k(\bar d^{\pi^b}_T, d^{\pi^\ast}_\gamma)$ by it. Once a suitable $C$ is determined, by the representer property, we can obtain a closed-form optimal value for $$ \max_{w \in {\cal W}}\overline\mathbb{E}_{NT}\left[w(S, A)\left(R + \gamma {Q}(S', \pi(S')) - {Q}(S, A) \right)\right], $$ which is given as $$ \frac{C}{NT} \sqrt{Y(\pi, Q)^\top K Y(\pi, Q)}. $$
With these two choices, (ref) is equivalent to
Lastly, if letting ${\cal F}$ and $\Pi$ be any pre-specified functional classes such as neural network architectures and RKHS, we can apply stochastic gradient decent to solve the primal-dual problem (ref) and obtain $\widehat \pi_{\text{dual}}$. See a pseudo algorithm of STEEL in Algorithm (ref).
\SetKwInput{KwData}{Input} \SetKwInput{KwData}{Input}
\SetCommentSty{mycommfont}
In this subsection, we propose an adaptive version of STEEL to finding the optimal policy under singularity. It consists of three steps. In the first step, we run STEEL by only considering the constraint set $\Omega_2(\pi, {\cal F}, \varepsilon^{(2)}_{NT})$ with a sufficiently large $\varepsilon^{(2)}_{NT}$. Essentially, we implement the algorithm without assuming any overlapping region between the behavior policy and the optimal one. Denote the resulting estimated policy as $\widehat \pi_0$ and the estimated $Q$-function as $\widehat Q$ after solving (ref) or (ref). In the second step, based on $\widehat \pi_0$, we aim to construct a single constraint set that takes account for both singularity and absolute continuity. Basically, we leverage the initially estimated policy $\widehat \pi_0$ to calibrate the absolutely continuous and singular parts with respect to the batch data distribution. To achieve this goal, we need to estimate several related quantities including $\widetilde \lambda_1^{\widehat \pi_0}, \widetilde \lambda_2^{\widehat \pi_0}, \lambda_1^{\widehat \pi_0}, \lambda_2^{\widehat \pi_0}, \delta^{\widehat \pi_0} = \text{MMD}(\lambda_2^{\widehat \pi_0}, \bar{d}_T^{\pi^b})$, and $\omega^{\widehat \pi_0}$. One can first estimate the behavior policy and transition probability using the batch data. Then $\bar{d}_T^{\pi^b}$ and $d_\gamma^{\widehat \pi_0}$ can be estimated correspondingly, where the estimators are denoted by $\widehat{d}_T^{\pi^b}$ and $\widehat {d}_\gamma^{\widehat \pi_0}$ respectively. To find $\omega^{\widehat \pi_0}$, one can solve the following minimization problem:
Denote the optimal solution as $\widehat \omega^{\widehat \pi_0}$. Based on the relationship that $\widetilde \lambda_1^{\widehat \pi_0}\times\lambda_1^{\widehat \pi_0} = \widehat \omega^{\widehat \pi_0} \times \bar{d}_T^{\pi^b}$, we can obtain an estimator of $\widetilde \lambda_1^{\widehat \pi_0}$ denoted by $\widehat{\widetilde \lambda_1^{\widehat \pi_0}} = \int_{{\cal S} \times {\cal A}} \widehat \omega^{\widehat \pi_0}(s,a) \times \widehat{d}_T^{\pi^b}(s, a)$ and an estimator of $\lambda_1^{\widehat \pi_0}(s, a)$ denoted by $\widehat \lambda_1^{\widehat \pi_0}(s, a) = \widehat \omega^{\widehat \pi_0}(s,a) \times \bar{d}_T^{\pi^b}(s, a)/\widehat{\widetilde \lambda_1^{\widehat \pi_0}}$. By the Lebesgue's Decomposition, we can find $\widetilde \lambda_2^{\widehat \pi_0}\times\lambda_2^{\widehat \pi_0} = d_\gamma^{\widehat \pi} - \widehat \omega^{\widehat \pi_0}\times \bar{d}_T^{\pi^b}$. Correspondingly, we can construct their estimators denoted by $\widehat{ \widetilde \lambda_2^{\widehat \pi_0}}$ and $\widehat \lambda_2^{\widehat \pi_0}$ correspondingly. Finally, an estimator of $\delta^{\widehat \pi}$ denoted by $\widehat \delta^{\widehat \pi_0}$ can be computed by standard methods such as gretton2012kernel. Based on the aforementioned quantities, we construct the following uncertainty set denoted by $\Omega$.
where the constant $\varepsilon_0$ is computed as follows.
Note that $\Omega$ does not rely on any tuning parameter. The last step is to run our proposed STEEL again with a single contraint set $\Omega$, which gives an adaptive policy $\widehat \pi_1$. The full algorithm can be found in Table (ref).
The performance of a policy optimization algorithm is often measured by the difference between the value of the (in-class) optimal policy and that of the estimated one, which is referred to as the regret. In our case, we evaluate the performance of any estimated policy $\widetilde{\pi} \in \Pi$ via the regret defined as
Clearly, $\text{Regret}(\widetilde{\pi}) \geq 0$. In this section, we aim to derive the finite-sample upper bounds for both $\text{Regret}(\widehat{\pi})$ and $\text{Regret}(\widehat{\pi}_{\text{dual}})$. We leave the theoretical analysis of adaptive STEEL as future work. To begin with, we list several important assumptions and discuss their corresponding implications. Other assumptions can be found in Appendix (ref).
Our batch data consist of multiple trajectories, where observations in each trajectory follow a MDP and thus are dependent. Assumption (ref) characterizes the dependency among those observations, instead of assuming transition tuples are all independent as in many previous works. This assumption has been used in recent works shi2020statistical,chen2022well. The upper bound on the $\boldsymbol{\beta}$-mixing coefficient at time lag $j$ indicates that the dependency between $\{S_t, A_t\}_{t \leq k }$ and $\{S_t, A_t\}_{t \geq (k+j) }$ decays to 0 at least exponentially fast with respect to $j$. See bradley2005basic for the exact definition of the exponentially $\boldsymbol{\beta}$-mixing. Recall that we have let $Z = (S, A)$ and denoted ${\cal Z} = {\cal S} \times {\cal A}$. Define an operator $T^\pi_{\zeta_{NT}}: {\cal F} \rightarrow {\cal H}_k$ such that
for every $Q \in {\cal F}$. Consider the following class of vector-valued functions as
where $Y(Q, \pi, s, a, s') = \widetilde{R}(s, a, s') + \gamma Q(s', \pi(s')) - Q(s, a)$. For $g \in {\cal G}$, we use $\|g\|_{{\cal H}_k, \infty}$ to denote $\sup_{(s, a, s') \in {\cal S} \times {\cal A} \times {\cal S}}\|g(s, a, s')\|_{{\cal H}_k}$. In the following, we quantify the complexities of function classes used in our policy optimization algorithm via the $\epsilon$-covering number. An $\epsilon$-covering number of a set $\Theta$ denoted by ${\cal N}(\epsilon, \Theta, \widetilde d)$ is the infimum of the cardinality of $\epsilon$-cover of $\Theta$ measured by a (semi)-metric $\widetilde d$. See definition of the $\epsilon$-covering number in (ref) of the appendix.
Assumption (ref) imposes metric entropy conditions on function classes ${\cal F}$, ${\cal W}$, $\Pi$ and ${\cal G}$. For simplicity, we consider uniformly bounded classes for deriving the exponential inequalities for both scalar-value and vector-value function classes van1996weak,park2022towards. In Assumption (ref) (ref), we only focus on the policy class which consists of the deterministic policies because there always exists an optimal policy that is deterministic. One can generalize Assumption (ref) to include more complicated function classes such as neural networks. See Lemma 5 of schmidt2020nonparametric for an example. We also remark that $v({\cal F})$, $v(\Pi)$ and $v({\cal G})$ could increase with respect to $N$ and $T$. In practice, one can specify ${\cal F}$, $\Pi$ and ${\cal W}$ and compute its corresponding complexity. In Appendix (ref), we provide a sufficient condition for computing $v({\cal G})$. The Lipschitz-typed condition in (ref) is imposed so that the $\epsilon$-covering number of the following class of functions:
could be properly controlled by the $\epsilon$-covering numbers of $\Pi_i$ for $1 \leq i \leq d_A$ and ${\cal F}$ van1996weak.
Next, let $\{e_j\}_{j \geq 1}$ be a non-increasing sequence of eigenvalues of the convolution operator defined in Appendix (ref) towards $0$ and $\{\phi_j\}_{j \geq 1}$ be orthonormal bases of $L^2_{d^{\pi^b}_T}({\cal Z})$. Define a space ${\cal H}_k^{2c}$ as
We impose the following assumption.
The first statement of Assumption (ref) is closely related to Bellman completeness, which has been widely imposed in the literature of batch RL antos_value-iteration_2007. This assumption will typically hold when the transition and the reward functions are smooth enough. Since ${\cal F}$ is closed under the limit operator, Assumption (ref) implies that $Q^\pi \in {\cal F}$ for $\pi \in \Pi$ by the contraction property of Bellman operator. In other words, there is no model misspecification error for estimating $Q^\pi$ for every $\pi \in \Pi$. Moreover, together with symmetry and closed under addition, Assumption (ref) also implies that for any $\pi \in \Pi$, any $Q \in {\cal F}$, ${\cal T}^\pi Q \in {\cal F} \subseteq {\cal H}_k^{2c}$. This further states that for any $\pi \in \Pi$, $Q \in {\cal F}$, there exists $g_{\pi, Q} \in L^2_{d^{\pi_b}}({\cal Z})$ such that ${\cal L}_k^cg_{\pi, Q} = {\cal T}^\pi Q$, where $L_k$ is an operator associated with the kernel $k$ and its definition can be found in Appendix (ref). In the standard literature of the kernel ridge regression smale2007learning,caponnetto2007optimal, for fixed $Q$ and $\pi$, the same type of the smoothness assumption is also imposed. $c \in (1/2, 3/2]$ is the range where the kernel ridge regression can adapt to the smoothness of the true function. Here we strengthen this smoothness assumption by considering for all $ \pi \in \Pi$ and $Q \in {\cal F}$, which is used for controlling the bias uniformly over ${\cal F}$ and $\Pi$ induced by the regularization in the kernel ridge regression (ref). See more discussion related to this in Remark 2 of Theorem (ref). It is worth mentioning that one can choose ${\cal F} = {\cal H}_k^{2c}$ and modify Assumption (ref) (ref) accordingly.
To derive the regret bounds for $\widehat{\pi}$ and $\widehat{\pi}_{\text{dual}}$, we first show that for every $\pi \in \Pi$, $Q^\pi$ is a feasible solution to the inner minimization problem of (ref) with a high probability. Let
Theorem (ref) is the key for establishing the regret bounds of our proposed algorithms. By showing (ref), we can guarantee that for every $\pi \in \Pi$, $Q^\pi$ is bounded below by the optimal value of the inner minimization problem in (ref) with a high probability. This verifies the use of pessimism in our algorithms, i.e., evaluating the value of each $\pi \in \Pi$ by a lower bound during the policy optimization procedure. Since we require $c \in (1/2, 3/2]$, the smallest value that $\varepsilon^{(2)}_{NT}$ can be set is of the order $\sqrt{\log(NT)}(NT)^{-1/4}$. Based on Theorem (ref), we have the following regret warranty for $\widehat{\pi}$.
Next, we develop a finite-sample regret bound for $\widehat{\pi}_{\text{dual}}$.
To proceed, we need one additional assumption.
In this section, we use Monte Carlo (MC) experiments to systematically study the proposed method in terms of the convergence of our algorithm, the effect of pessimism in finding the optimal policy, and the robustness to the covariate shift. For simplicity, we only consider the contextual bandit problem.
For all numerical studies, we compare our method with two popular continuous-action policy optimization methods. The regression-based approach first estimates the reward function $r(s,a)$ as $\hat{r}(s,a)$ by running a regression method, and then estimates the value of any given policy $\pi$ with the plug-in estimator $\mathbb{E}_{S_0 \sim \nu}\left[\hat{r}(S_0, \pi(S_0))\right]$, where the expectation is approximated via MC sampling of $\nu$. Recall that $\nu$ is known in advance. Given such a policy value estimator, we implement the off-the-shelf optimization algorithm to estimate the optimal policy within a given policy class. The kernel-based approach chen2016personalized, kallus2018policy is similar to the regression approach but first estimates the policy value using the inverse probability weighting with kernel smoothing. Specifically, we estimate the value of any given policy $\pi$ by $$ (Nh)^{-1} \sum_{i=1}^N \frac{K( (\pi (S_{i,0}) - A_{i,0}) / h)}{ \pi^b(A_{i, 0} \, | \, S_{i, 0})} \times R_{i,0}, $$ where $K(\cdot)$ is a kernel function, $h$ is the bandwidth parameter, and $\pi^b$ is referred as to the generalized propensity score in this setting.
Next, we describe the data generating process in our simulation study. We consider the mean reward function $r(s, a) = \big(a - \boldsymbol{B}s \big)^\top \boldsymbol{C} \big(a - \boldsymbol{B}s \big)$, where the state-value $s$ has dimension $d_s = 5$, the action-value $a$ has dimension $d_a = 4$, the parameter matrix $\boldsymbol{B} \in \mathcal{R}^{d_a \times d_s}$, and $\boldsymbol{C}$ is a $d_a \times d_a$ negative definite matrix. We randomly sample every entry of $\boldsymbol{B}$ from $\text{Uniform}(0,1)$. We construct $\boldsymbol{C} = - \boldsymbol{C}_0^\top \boldsymbol{C}_0$, where every entry of $\boldsymbol{C}_0$ is sampled from the standard normal. Our reward $R_0$ is generated following $R_0 = r(S_0, A_0) + \epsilon_0$, where the independent noise $\epsilon_0 \sim \mathcal{N}(0, 1)$. Therefore, the optimal policy $\pi^*(s) = s^\top \boldsymbol{B}$ for every $s \in {\cal S}$, regardless of the state distribution.
The training dataset $\{S_{i,0}, A_{i,0}, R_{i,0}\}_{1 \le i \le N}$ is generated as follows. The state $S_{i,0}$ is uniformly sampled from $[0,2]^{d_s}$, which is the same as the reference distribution. Except for the case where we study the effect of covariate shift, values of learned policies in this section are evaluated over the same distribution as the training distribution. The action is sampled following a behavior policy $\pi^b$ such that $A_{i,0} = \boldsymbol{B}S_{i,0} + \epsilon'$, where $\epsilon' \sim \mathcal{N}(0, \sigma_b^2 \boldsymbol{I}_{d_a})$. Therefore, a larger $\sigma_b$ indicates that the behavior policy is more different from the optimal one and also implies that the action space is explored more in the training data.
For all three methods, we search the optimal policy within the class of linear deterministic policies $\Pi = \{\pi \, \mid \, \text{for every $s \in {\cal S}$,}\,\, \pi(s) = \Tilde{\boldsymbol{B}}s \, \, \text{for some $\boldsymbol{\Tilde{B}} \in [-1,1]^{d_s \times d_a} $} \}$. For the kernel-based method, we assume the true value of the generalized propensity score $\pi^b$ is known, instead of plugging-in the estimated value. Although the latter is known to be asymptotically more efficient in the causal inference literature, we observe that its empirical performance is close or sometimes worse than the oracle version in the studied setting, given the challenge to estimating a multi-dimensional conditional density function (See Appendix (ref)). We tune the bandwidth for the kernel-based method and use the best one for it. To implement the optimization problems in two baseline methods, we adopt the widely used L-BFGS-B optimization algorithm following liu1989limited. Regarding estimating the reward function $r(s,a)$, we use a neural network of three hidden layers with $32$ units for each layer and ReLU as the activation function. \textcolor{black}{For STEEL, we use the Laplacian kernel $k(x, y) = \exp \big(-||x-y||_1 / \gamma \big)$ in both the kernel ridge regression and the modeling of $\omega$, where the bandwidth $\gamma$ is picked based on the popular median heuristic, i.e., set as the median of $\{||(S_{i,0}, A_{i,0}) - (S_{j,0}, A_{j,0}) ||_1\}_{1 \le i, j \le N}$. For the other tuning parameters, we set $\zeta_{NT} = 0.001$, $(\varepsilon^{(1)}_{NT})^2 = 300$, and $(\varepsilon^{(2)}_{NT})^2 = 600$. }
For each setting below, we run $100$ repetitions and report the average regret of each method as well as its standard error. Except for when we study the convergence of three methods in terms of the sample size, we fix $N = 200$ data points for each repetition.
Convergence. We first study the convergence of all three methods, by increasing the training sample size $N$. The results when $\sigma_b = 0.5$ are presented in Figure (ref). Overall, we observe that our method yields a desired convergence with the regret decaying to zero very quickly. The regression-based method also improves as the sample size increases, despite that the finite-sample performance is worse compare with ours. The kernel-based method suffers from the curse of dimensionality of the action space and the regret does not decay very significantly. Results under a few other settings are reported in the appendix, with similar findings.
Effect of pessimism. Next, recall that $\sigma_b$ controls the degree of exploration in the training data. It is known that a well-explored action space in the training dataset is beneficial for policy learning, in the sense that we can accurately estimate the values of most candidate policies. In contrast, when $\sigma_b$ is small (i.e., the behavior policy is close to the optimal one), although the value estimation of the optimal policy may be accurate, that of a sub-optimal policy suffers from a large uncertainty and by chance the resulting estimator could be very large, which leads to returning a sub-optimal policy. Our method is designed with addressing such a large uncertainty in mind, by utilizing the pessimistic mechanism.
In Figure (ref), we empirically study the effect of $\sigma_b$ on different methods. The results are based on $N = 200$ data points and different values of $\sigma_b$. It can be seen clearly that, our method is fairly robust, when the training data is either well explored or not. In contrast, the performance of the two baseline methods deteriorates significantly when $\sigma_b$ is small.
Performance of adaptive STEEL. In this section, we numerically study the performance of the adaptive version of STEEL, i.e., Algorithm (ref). Notice that the singularity can be caused by the covariate shift and the distance between the data and the target distributions will also increase with covariate shift, we design such a setting for our study. Specifically, the policy will be tested when the covaraites are sampled uniformly from $[\Delta x, 2 + \Delta x]^{d_s}$. A larger value of $\Delta x$ hence indicates a larger degree of covariate shift. We set a very large initial $\varepsilon^{(2)}_{NT} = 5000$, and report the performance of both the first-stage policy and the final policy from Algorithm (ref).
The results when $\sigma_b = 0.25$ and $N = 200$ are presented in Figure (ref). It can be seen clearly that adaptive STEEL, without further tuning, consistently shows robust and better performance than other algorithms. The first-stage outcome policy from Algorithm (ref), although still has decent performance, has significantly higher regrets that grow with the degree of covariate shift due to its lack of adaptiveness from appropriately constructed uncertainty set.
In this section, we apply our method to personalized pricing with a real dataset. The dataset is from an online auto loan lending company in the United States \footnote{The dataset is available at \nolinkurl{https://business.columbia.edu/cprm} upon request.}. It was first studied by phillips2015effectiveness and we follow similar setups as in subsequent studies ban2021personalized.
The dataset contains all auto loan records (208085 in total) in a major online auto loan lending company from July 2002 to November 2004. For each record, it contains some covariates (e.g., FIFO credit score, the term and amount of loan requested, etc.), the monthly payment offered by the company, and the decision of the applicant (accept the offer or not). We refer interested readers to phillips2015effectiveness for more details of the dataset.
The monthly payment (together with the loan term) can be regarded as the offered price (action) and the binary decision of the applicant reflects the corresponding demand. Specifically, we follow ban2021personalized and bastani2022meta to define the price as
which considers the net present value of future payments. Here, the prime rate is the interest rate that the company itself needs to pay. We filter the dataset to exclude the outlier records (defined as having a price higher than \$10,000), and $99.49\%$ data points remain in the final dataset.
In our notations, the price is hence the action $A_0$. Let the binary decision of the applicant be $D_0$. The reward is then naturally computed as $R_0 = D_0 \times A_0$. We use the same set of features which are identified as significant in ban2021personalized to construct our feature vector $S_0$: it contains the FICO credit score, the loan amount approved, the prime rate, the competitor's rate, and the loan term.
When running offline experiments for problems with discrete action spaces, to compared different learned policies, the standard procedure is to find those data points where the recorded actions are consistent with the recommendations from a policy $\pi$ that we would like to evaluate. However, with a continuous action space, such a procedure is typically impossible, as it is difficult for two continuous actions to have exactly the same value. Therefore, it is well acknowledged that, offline experiments without any model assumption is infeasible. We closely follow bastani2022meta to design a semi-real experiment, where we fit a linear demand function from the real dataset and use it to evaluate the policies learned by different methods. The linear regression uses the concatenation of $S_0$ (which describes the baseline effect) and $S_0 A_0$ (which describes the interaction effect) as the covariate vector. To evaluate the statistical performance of the three methods considered in Section (ref), we repeat for $100$ random seeds, and for each random seed we sample $N$ data points for policy optimization.
The implementation and tuning details of the three methods are almost the same with Section (ref). The main modification is that, for the reward function class used in our method and the regression-based method, we use the neural network to model the demand function (instead of the expected reward itself), which multiplies with the action (price) gives the expected reward. Such a modification utilizes the problem-specific structure. All covariates are normalized and we always add an intercept term. For tuning parameters, we set $\zeta_{NT} = 0.001$, $(\varepsilon^{(1)}_{NT})^2 = 13$, and $(\varepsilon^{(2)}_{NT})^2 = 16$.
In Figure (ref), we increase $N$ from $200$ to $12800$ and report the average regrets. We find that our method consistently outperforms the other two methods and its regret decays to zero. In Figure (ref), we zoom into the case where $N = 8000$, and report the values of the learned policies across the $100$ random seeds. We observe that, although the regression-based method can outperform the behaviour policy in about half of the random replications, it can perform very poor in the remaining replicates. In contrast, our method has an impressive performance and the robustness of our methods is consistent with our methodology design. The kernel-based method does not perform well in most settings. A deep dive shows that this is because this method over-estimates the values of some sub-optimal policies that assign many actions near the boundaries where we have few data points. The over-estimation is due to its poor extrapolation ability and the lack of the pessimism mechanism (i.e., it is not aware of the uncertainty).
Finally, we randomly pick a policy learned by our method (with the first random seed we used) and report its coefficient to provide some insights. Recall that we use a linear policy, mapping from the five features to the recommended price. The coefficients are overall aligned with the intuition: the learned personalized pricing policy offers a higher price when the FICO score is lower, the loan amount approved is higher, the prime rate (the interest rate that the company itself faces) is higher, the competitor's rate is higher (implying a consensus on the high risk of this loan), and the term is longer.
{1pt}
In this paper, we study batch RL in the presence of singularities and propose a new policy learning algorithm to tackle this issue. Our proposed method finds an optimal policy without requiring absolute continuity on the distribution of target policies with respect to the data distribution. Both theoretical guarantees and numerical evidence are presented to illustrate the superior performance of our proposed method, compared with existing works. In the current proposal, we leverage the MMD, together with distributionally robust optimization, to enable the extrapolation for addressing the singularity. Our idea can also be extended to other distances such as the Wasserstein distance or total variation distance. While these distances have some appealing properties, the related estimation becomes difficulty, showing a trade-off. Finally, it is also interesting to explore model-based solutions for addressing the singularity issue in batch RL.