1 Introduction↩︎

In various decision-making problems, estimating the value, the expected reward of a policy is a crucial question that needs to be addressed. Online evaluation requiring a comprehensive evaluation of policy value can be expensive and may not be applicable to multiple target policies.

Alternatively, off-policy evaluation (OPE) refers to a technique that estimates the value of a target policy by utilizing log data generated from a different logging policy. This approach has attracted considerable interest in the domains of contextual bandits (CB) [1], [2] and reinforcement learning (RL) [3]–[5].

Several off-policy evaluation algorithms [1], [6]–[9] currently in use rely on having complete knowledge of the logging policy in order to utilize inverse probability weighting (IPW). However, in situations where information about the data logger is not available, such as when using human decision data, it becomes necessary to estimate the logging policy. Applying existing estimators directly to cases where the logging policy is unknown can compromise the desired properties of these methods, as they fail to take into account the impact of logging policy estimation.

In this paper, we present a novel efficient estimator called DRUnknown, which simultaneously estimate both the logging policy model and the value function model. Our proposed approach, without the need for external data, effectively captures the interdependency between the two models.

In the field of conventional statistics, [10] employs the influence function to estimate parameters in the doubly-robust (DR) estimator for population means when there are missing observations. The study focused on situations where data is incomplete and the missing mechanisms are unknown and estimated. To advance this concept, we utilized the influence function approach to address the OPE problem. Here, we treat the rewards of unselected actions as missing values and estimate the unknown logging policy. This enables us to derive the asymptotic variance of the OPE estimator and estimate the parameters that minimize it.

The proposed OPE estimator estimates both the logging policy model and the value function model, and is referred to as doubly-robust due to its consistency if either the model for the logging policy or the value function is correctly specified. When the logging policy is correctly specified, the proposed estimator is the most efficient among the class of DR OPE estimators with an estimated logging policy, and is at least as efficient as existing methods. Moreover, if the value function model is correctly specified, the estimator locally efficient, achieving the semiparametric lower bound for asymptotic variance and is asymptotically optimal. In order to demonstrate the effectiveness of the proposed estimator, we conducted simulation experiments to compare its performance with previous methods in contextual bandits and reinforcement learning problems.

The main contributions of this paper are as follows:

• We present a new DR OPE estimator for Markov decision process, for the case where both the logging policy and the value function are unknown. The proposed estimator is consistent when either the logging policy model or the value function model is correctly specified.

• We propose a method to estimate both the logging policy model parameter \(\hat{\phi}\) and the value function model parameter \(\hat{\beta}\) simultaneously. We use the maximum likelihood estimator (MLE) for \(\hat{\phi}\) and minimize the asymptotic variance to estimate \(\hat{\beta}\), accounting for the impact of estimating \(\hat{\phi}\).

• The proposed estimator has the smallest asymptotic variance among estimators using MLE for \(\hat{\phi}\) when the logging policy model is correctly specified. When the value function model is also correctly specified the proposed estimator is optimal, as its asymptotic variance reaches the semiparametric lower bound.

• Simulations on contextual bandits and reinforcement learning problems show that the proposed estimator consistently shows smaller mean-squared errors compared to the benchmarks methods.

2 Problem Setup↩︎

In this paper, we model the decision-making problem as a reinforcement learning framework in which the learner’s interaction with the system is represented as a Markov Decision Process (MDP). In this section, we provide definitions of MDP and the corresponding off-policy evaluation problem for our study.

2.1 Markov Decision Processes↩︎

An MDP is defined as a tuple (\(\mathcal{X}\), \(\mathcal{A}\), \(R, P, P_0, \gamma\)), where \(\mathcal{X}\) and \(\mathcal{A}\) represent the state and the finite action spaces with \(|\mathcal{A}|=K\), \(R(x, a)\) denotes the distribution of the random variable \(r(x, a)\) of the bounded immediate reward of taking action \(a\) in state \(x\), \(P(\cdot|x, a)\) is the transition probability distribution. \(P_0 : X \rightarrow [0, 1]\) is the initial state distribution, and \(\gamma \in [0, 1]\) is the discounting factor. The learner utilizes a policy \(\pi : \mathcal{X}\times \mathcal{A}\rightarrow [0, 1]\), a stochastic mapping from states to actions. Here, \(\pi(a|x)\) represents the probability of taking action \(a\) in state \(x\).

Let \(\mathcal{H}_{T}\) = \(\{(x_t, a_t, r_t)\} _{t=0}^{T-1}\) represent a \(T\)-step trajectory containing state-action-rewards generated by policy \(\pi\). Denote \(R_{t_1:t_2} = \sum\limits_{t=t_1}^{t_2} \gamma^{t-t_1} r_t\) as the sum of discounted return of from time step \(t_1\) to \(t_2\). Our goal is to estimate the policy value, the expected return of trajectories generated by policy \(\pi\), i.e., \(V^{\pi,T}= \text{\mathbb{E}}_{\pi} [R_{0:T-1}]\). Here \(\text{\mathbb{E}}_{\pi}\) denotes the expectation over the trajectory sampled from \(\pi\). We also define the value function of a policy \(\pi\) at state \(x\) and at state-action pair \((x,a)\) from time step \(t\) by \(V^{\pi,t}(x)=\text{\mathbb{E}}_{\pi} [R_{t:T-1}|x_t = x]\) and \(Q^{\pi,t}(x,a)=\text{\mathbb{E}}_{\pi} [R_{t:T-1}|x_t = x, a_t=a]\), respectively.

Throughout this paper, we fix the trajectory length as \(T\). We also omit the \(\pi\) from \(V^{\pi,t}(s)\) and \(Q^{\pi,t}(s,a)\) to simplify them as \(V^t(s)\) and \(Q^t(s,a)\), respectively, since we are only interested in the value of \(\pi\). Note that, unlike the case with \(T=\infty\), where the \(Q\) and \(V\) value functions remain unchanged, the value functions \(Q^{t}\) and \(V^{t}\) can vary for each time step \(t\) in general.

The contextual bandits (CB) is a special case of the MDP, in which the trajectory length \(T\) equals to \(1\), and the transition dynamics \(P\) do not exist. In CB, the state is represented as the context, and the action is called as the arm.

2.2 Off-Policy Evaluation Problem↩︎

In an OPE problem, we are given a dataset \(\mathcal{D}_n = \{\mathcal{H}_{T}^{(i)}\}_{i=1}^n\) comprising \(n\) independent \(T\)-step trajectories drawn from a logging policy \(\mu\). We use the superscript \((i)\) to refer to the data from the \(i^{\text{th}}\) trajectory, denoted as \(\mathcal{H}_{T}^{(i)}\). The objective is to estimate the policy value \(V^{\pi}\) of a separate target policy \(\pi\). We define the importance ratio \(\rho_{t}=\pi(a_t|x_t) / \mu(a_t|x_t)\), and the cumulative importance ratio from time step \(t_1\) to \(t_2\) between \(\mu\) and \(\pi\) as \(\rho_{t_1: t_2}= \Pi_{t=t_1}^ {t_2} \rho_t\). In cases where \(t_1 > t_2\), we define \(\rho_{t_1:t_2}\) to be 1. Similarly, we denote the estimated importance ratio as \(\hat{\rho}\), where the probability of the logging policy \(\mu(a|x)\) is replaced with its estimated version \(\hat{\mu}(a|x;\hat{\phi})\) for the logging policy model \(\hat{\mu}(\cdot;\phi)\).

The policy value \(\widehat{V}\) is a point estimator, and there are various metrics to assess the quality of the provided estimator. One commonly used is the mean squared error (MSE), defined as \(\text{MSE}(\widehat{V}) = \text{\mathbb{E}}_{\mu}[{(\widehat{V}- V^{\pi})^2}]\) with the expectation taken with respect to the data sampled from \(\mu\). MSE quantifies the performance of a given estimator in finite samples. Another measure is the asymptotic variance, which assesses the efficiency of an estimator with a large number of samples. The estimator \(\widehat{V}\) is called asymptotically linear if there exists a function \(\psi\) of trajectory \(\mathcal{H}_{T}\) such that \[\widehat{V}- V^{\pi} = \frac{1}{n}\sum_{i=1}^n \psi(\mathcal{H}_{T}^{(i)}) + o_p(\frac{1}{\sqrt{n}}).\] with \(\text{\mathbb{E}}_{\mu}{[\psi(\mathcal{H}_{T})]}=0\) and \(\mathrm{Var}_{\mu}{[\psi(\mathcal{H}_{T})^2]} < \infty\). The quantity \(\mathrm{Var}_{\mu}{[\psi(\mathcal{H}_{T})^2]}\) is denoted as the asymptotic variance of \(\widehat{V}\), and the function \(\psi(\mathcal{H}_{T})\) is referred to as the influence function. In our study, we derive the specific form of the influence function for OPE estimators and conduct an analysis to minimize the asymptotic variance.

For our analysis, we use the following standard regularity assumptions for OPE problem.

Assumption 1 is crucial in order to avoid an infinite IPW and the OPE estimators which employ IPW are well-defined. Assumption 2 is necessary to guarantee that estimators utilizing the IPW method have finite variance.

3 Previous Methods for Off-Policy Evaluation↩︎

The doubly-robust type estimator for the OPE problem was first proposed by [1]. The estimator depends on a regression model for value function that is estimated using a separate independent dataset, which may not always be available.

The works of [6] and [7] introduce estimators that improve efficiency by modifying the IPW component of the DR OPE estimator. These methods still require the independently estimated value function using external data. [8] employed the idea of [11], which estimates the value function model by minimizing the estimation variance without external dataset. All these methods assume that the true logging policy is known and do not require estimation.

Several studies [12]–[15] have proposed the IPW estimators for OPE utilizing the estimated logging policy and examined their theoretical and numerical properties of these estimators. However, these methods do not consider the value function, making them not doubly-robust and suboptimal in terms of asymptotic variance.

3.1 Standard Methods for Off-Policy Evaluation↩︎

There are three standard approaches to estimate \(V^{\pi}\) in OPE problem, and we provide a brief overview of these methods.

The first method is direct method (DM) [1], [16], which directly approximates the state-action value function \(Q(x,a)\) of the target policy. The DM does not use the information from the logging policy \(\mu\) and relies heavily on the accuracy of the prediction of the value function. While the DM estimators often exhibits low variance, it is not guaranteed to be unbiased.

The second method is called inverse probability weighting (IPW) estimator [17], which utilize the importance ratio term to correct the discrepancy between the target and logging policies. The IPW estimator is unbiased in case the logging policy is known, but it can exhibit a large variance when there is a significant difference between the logging and target policies and the importance ratio have large value. The Assumption 1 is required in order for the IPW estimator to be well-defined: one cannot know about the pair \((x,a)\) never explored by the logging policy.

The third approach, named doubly-robust (DR) estimator [1], [5], [18], [19], combines the DM and IPW, leveraging their respective strengths to obtain favorable characteristics. The IPW estimator is a special case of DR with the value function fixed to zero. Our work focuses on the DR type estimators, as our main objective is to introduce an efficient method for simultaneously estimating the logging policy and the value function model.

3.2 Doubly-Robust Off-Policy Evaluation with Unknown Logging Policy↩︎

The standard DR OPE estimator with known logging policy is given by \[\widehat{V}^{\text{DR}} = \frac{1}{n} \sum\limits_{i=1}^n\sum\limits_{t=0}^{T-1}\gamma^{t} \rho_{0:{t-1}}^{(i)} \bigl[\rho_t^{(i)}[r_t^{(i)} - \widehat{Q}(x_t^{(i)}, a_t^{(i)};\beta)] + \widehat{V}(x_t^{(i)};\beta)\bigr],\]

where \(\widehat{Q}(\cdot ;\beta)\) is a value function model of the state-action value function parameterized by \(\beta\), and \(\widehat{V}(x ;\beta) = \sum_{a \in \mathcal{A}} \pi(a|x) \widehat{Q}(x,a ;\beta).\)

Here, \(\widehat{Q}\) depends solely on the state-action pair. However, as mentioned in Section 2.1, the \(Q^t(x,a)\) may vary for different time steps, even if the state-action pair remains the same when the horizon length \(T\) is finite. Hence, we cannot ensure that the model \(\widehat{Q}\) can express the \(Q^t\) for all \(t\) in the OPE problem with a finite \(T\). To address this issue, we utilize the function class \(\widehat{Q}(t,x,a)\), which incorporates \(t\) as an input parameter in practice. Also, to ensure that the class of DR OPE estimator contains the IPW estimator, we assume that the class of \(\widehat{Q}\) contains the constant functions. This can be easily satisfied by bringing the parameters \(\nu_0, \nu_1 \in \mathbb{R}\) to extend the function class by \(\nu_0 + \nu_1 \widehat{Q}\).

The DR OPE estimator [eq:DR] utilizes the importance ratio using the true probability of the logging policy. When the logging policy \(\mu\) is unknown we use the logging policy model \(\hat{\mu}(\cdot ;\hat{\phi})\) to approximate the unknown \(\mu\). We say that the model \(\hat{\mu}\) is correctly specified if there exists a value of \(\phi\) such that \(\hat{\mu}(x,a;\phi)=\mu(x,a)\) for all \(x\) and \(a\). The correct specification of \(\hat{\mu}\) is necessary for the consistent estimation of the policy value \(V^{\pi}\), as correctly specifying the value function model \(\widehat{Q}\) is difficult in many OPE problems.

In the following sections, our focus will be on the DR OPE estimator, which estimates both the logging policy parameter \(\phi\) and the value function parameter \(\beta\). Our goal is to build an efficient OPE estimator that exhibits lower asymptotic variance compared to existing methods.

4 Proposed Method: DRUnknown↩︎

In this section, we present our class of DRUnknown estimators. The central concept of DRUnknown is to first estimate the unknown logging policy parameter \(\hat{\phi}\) for the IPW component of the DR estimator, and then learn the value function parameter \(\hat{\beta}\) to minimize the asymptotic variance of the estimator. We utilize the influence function of the estimator to derive a feasible objective function to minimize the asymptotic variance of DRUnknown.

4.1 DRUnknown for Contextual Bandits↩︎

We first present the DRUnknown for contextual bandits problem with \(T=1\). Consider a logging policy model \(\hat{\mu}(x,a ; \phi)\) parameterized by \(\phi\). Let \(\Delta_{a}^{(i)}\) represent the indicator for an action \(a\) chosen in trajectory \(i\), and denote the partial derivative of \(\hat{\mu}\) with respect to \(\phi\) as \(\dot{\hat{\mu}} (a|x; \phi)\). The maximum-likelihood estimator (MLE) \(\hat{\phi}= \hat{\phi}_n\) is given by the solution of the estimating equation \(U_n(\phi)\) given by \[U_n(\phi)=\sum\limits_{i=1}^n\sum\limits_{a \in \mathcal{A}}\Delta_{a}^{(i)} \frac{\dot{\hat{\mu}} (a|x^{(i)}; \phi)}{\hat{\mu}(a|x^{(i)}; \phi)}=0.\] If the logging policy model is correctly specified, the estimating equation is unbiased, and \(\hat{\phi}\) is consistent for \(\phi\).

Plugging in the estimated value of \(\hat{\phi}\), we obtain the following class of DR OPE estimator \[\widehat{V}^{\text{DR}}(\beta, \hat{\phi}) = \frac{1}{n} \sum\limits_{i=1}^n\Bigl[ \frac{\pi^{(i)}}{\hat{\mu}^{(i)}} (r^{(i)} - \widehat{Q}^{(i)}(\beta)) + \widehat{V}^{(i)}(\beta) \Bigr]\] where the notations \(\pi^{(i)}, \hat{\mu}^{(i)}, \widehat{Q}^{(i)}(\beta)\) and \(\widehat{V}^{(i)}(\beta)\) denote the \(\pi(a^{(i)}|x^{(i)})\), \(\hat{\mu}(a^{(i)}|x^{(i)};\hat{\phi})\), \(\widehat{Q}(x^{(i)}, a^{(i)}; \beta)\) and \(\widehat{V}(x^{(i)}; \beta)\) respectively. Henceforth in the paper, if there is no ambiguity, we simplify terms containing \(x^{(i)}\) and \(a^{(i)}\) by using only the superscript \((i)\).

The expression of the bias and variance of the estimator \(\widehat{V}^{\text{DR}}(\beta, \hat{\phi})\) is not simple in general, even for a fixed \(\beta\). The estimator is not a mean of the independent and identically distributed (i.i.d) variables, due to the estimated \(\hat{\phi}\) in the denominator. Consequently, estimating the regression parameter \(\beta\) to minimize the MSE of the proposed estimator poses challenges. Hence, we instead aim to find \(\hat{\beta}\) minimizing the asymptotic variance of the estimator.

To attain this, we derive the influence function asymptotically equivalent to \(\widehat{V}\), through a Taylor expansion with respect to \(\phi\) and \(\beta\). Denote the new regression function \(F\), the product of the target policy \(\pi\) and the \(\widehat{Q}\) with an additional estimating effect term of \(\phi\), given by \[F(x,a;\beta, c, \phi)=\pi(a|x)\widehat{Q}(x,a;\beta) + c^{\top} \dot{\hat{\mu}}(a|x;\phi),\] for \(\beta\) and \(c \in \mathbb{R}^{\text{dim}(\phi)}.\) The influence function of \(\widehat{V}^{\text{DR}}(\hat{\beta},\hat{\phi})\) with arbitrary estimator \(\hat{\beta}\) can be formulated employing \(F\), as described in the following proposition.

As the value of the vector \(c(\beta^*)\) is unknown, we estimate both \(\beta\) and \(c\) that minimize the variance of \(\widetilde{V}(\beta,c)\). Denote the vector \(\vec{F}(x; \beta,c,\phi)=(F(x, a; \beta,c,\phi))_{a \in \mathcal{A}}\) and \(\pi\vec{Q}(x) = (\pi(a|x) Q(x,a))_{a \in \mathcal{A}}\), and the gradient matrix \(f(x;\beta,c,\phi) =\displaystyle\frac{\partial \vec{F}}{\partial(\beta,c)}.\) By the law of total variance, the variance of \(\widetilde{V}^{\text{DR}}(\beta,c)\) can be expressed as the square of stochastic seminorm added by a constant independent of \(\beta\) and \(c\).

The Proposition 2 tells minimizing the square of seminorm \[\label{eq:bandit95seminorm} \text{\mathbb{E}}_{\mu}{\left\Vert \vec{F}(x;\beta,c,\phi)- \pi \vec{Q}(x)\right\Vert _{M_{\mu}}^2}\tag{1}\] with respect to \(\beta\) and \(c\) is equivalent to minimizing the variance of the \(\widetilde{V}(\beta,c)\). Denote the minimizer of 1 by \((\beta_{\text{opt}}, c_{\text{opt}})\), the zero of its gradient \[\label{eq:bandit95gradient} \begin{align} \text{\mathbb{E}}_{\mu} \bigl[ f^{\top}(x;\beta,c,\phi) M_{\mu} (\vec{F}(x;\beta,c,\phi)- \pi \vec{Q}(x)) \bigr]= 0. \end{align}\tag{2}\] We can observe that the solution satisfies \(c_{\text{opt}}=c(\beta_{\text{opt}})\), so that the variance of \(\widetilde{V}(\beta_{\text{opt}},c(\beta_{\text{opt}}))=\widetilde{V}(\beta_{\text{opt}},c_{\text{opt}})\) is minimized at \((\beta_{\text{opt}}, c_{\text{opt}})\). Therefore by Proposition [prop:influence], the smallest asymptotic variance of DR OPE estimator \(\widehat{V}^{\text{DR}}(\hat{\beta},\hat{\phi})\) under the correctly specified \(\hat{\mu}\), is achieved by \(\hat{\beta}\) converging in probability to this \(\beta_{\text{opt}}\).The following estimating equation \(S_n(\beta,c)\) is a tractable equation that jointly solves for \((\beta,c)\), with its solution \(\hat{\beta}\) consistent for \(\beta_{\text{opt}}\): \[\label{eq:bandit95gradient95data} S_n(\beta,c)= \sum\limits_{i=1}^nf^{(i) \top}(\beta,c) M^{(i)} \bigl( F^{(i)}(\beta,c) - \operatorname{diag}(\pi(a|x^{(i)}))_{a \in \mathcal{A}} ~ \vec{r}^{(i)}\bigr)= 0\tag{3}\] for \(M^{(i)}=\displaystyle\operatorname{diag}(\hat{\mu}(a|x^{(i)})^{-1})_{a \in \mathcal{A}} - J_K\) and the pseudo reward \(\vec{r}^{(i)} = \displaystyle\bigl(\frac{\Delta_a^{(i)}}{\hat{\mu}(a|x^{(i)})} r^{(i)}\bigr)_{a \in \mathcal{A}}\). Plugging in the solution \(\hat{\beta}\) of \(S_n(\beta,c)=0\) as \(\widehat{V}^{\text{DR}}(\hat{\beta}, \hat{\phi})\), we obtain our proposed estimator, DRUnknown. The \(c\) serves as an auxiliary parameter that adjusts for the effect of estimating \(\hat{\phi}\), and does not have a direct role in the final estimator \(\widehat{V}^{\text{DR}}(\hat{\beta}, \hat{\phi})\).

The proposed DRUnknown is doubly-robust within the statistical context, as it remains consistent if either the logging policy model \(\hat{\mu}\) or the value function model \(\widehat{Q}\) is correctly specified. We have addressed the scenario with the correct logging policy model above. Regarding the second scenario, the minimizer of 1 is \((\beta_{\text{opt}},c_{\text{opt}})=(\beta_0, 0)\) since \(\Gamma(\beta_0)=0\), where \(\beta_0\) is the true value of the parameter satisfying \(Q(\cdot)=\widehat{Q}(\cdot;\beta_0).\) Consequently, the solution of 3 converges to \((\beta_0, 0)\), establishing the consistency of DRUnknown. This observation can be summarized as the following proposition.

4.1.1 Intuitive Understanding of DRUnknown for CB: extended function class↩︎

For an intuitive understanding of DRUnknown for contextual bandits, suppose that the target policy \(\pi\) always have a nonzero value. Then, \(F\) can be rewritten as \(F(x,a;\beta,\phi) = \pi(a|x)\widetilde{Q}(x,a;\beta,c)\) for the extended function class \[\widetilde{Q}(x,a;\beta,c)=\widehat{Q}(x,a;\beta,c) + c^{\top} \displaystyle\frac{\dot{\hat{\mu}}(a|x;\phi)}{\pi(a|x)}.\] The objective function 1 we aim to minimize in DRUnknown can then be expressed as \[\text{\mathbb{E}}_{\mu}{\left\Vert \bigl( \pi(a|x)[\widetilde{Q}(x,a;\beta,c) - Q(x,a)] \bigr)_{a \in \mathcal{A}} \right\Vert _{M_{\mu}}^2}.\] The additional linear term \(\displaystyle c^{\top}\frac{\dot{\hat{\mu}}(a|x;\phi)}{\pi(a|x)}\) from \(\widetilde{Q}\) can be seen as the projection of \(Q^{\pi}\) onto the inverse probability tangent space, the linear space spanned by the score function of \(\hat{\phi}\).

Hence, the proposed estimator can be seen as employing a linear parameter \(c\) within the expanded function class \(\widetilde{Q}\) to remove the effect of estimating \(\hat{\phi}\), while seeking the optimal \(\hat{\beta}\) for \(\widehat{Q}\) that minimizes the asymptotic variance.

4.2 DRUnknown for Reinforcement Learning↩︎

The proposed DRUnknown for RL is constructed similarly to the case of CB. However, its analysis is more complex, as the estimator is expressed as a weighted sum of terms observed from time step \(0\) to \(T-1\). Below, we introduce the construction of DRUnknown for RL, commencing with the estimation of \(\hat{\phi}\).

The MLE \(\hat{\phi}_n = \hat{\phi}\) of \(\phi\) for RL is given by the solution of \[U_n(\phi)=\sum\limits_{i=1}^n\sum\limits_{t=0}^{T-1}\sum\limits_{a \in \mathcal{A}}\Delta_{a,t}^{(i)} \frac{\dot{\hat{\mu}}(a|x_t^{(i)}; \phi)}{\hat{\mu}(a|x_t^{(i)}; \phi)}=0,\] where \(\Delta_{a,t}^{(i)}\) is the indicator variable for selected action at time step \(t\) from trajectory \(i\). Substituting the MLE \(\hat{\phi}\) into the DR estimator [eq:DR], the estimator is given by \(\widehat{V}^{\text{DR}}(\beta,\hat{\phi}) = \displaystyle\sum\limits_{t=0}^{T-1}\gamma^{t} \widehat{V}_{t}(\beta,\hat{\phi}),\) with \[\widehat{V}_{t}(\beta,\hat{\phi}) = \frac{1}{n} \sum\limits_{i=1}^n\hat{\rho}_{0:{t-1}}^{(i)} \bigl[\hat{\rho}_t^{(i)}[r_t^{(i)} - \widehat{Q}^{(i)}(\beta)] + \widehat{V}^{(i)}(\beta)\bigr].\] The estimator of the value at each time step \(t\), \(\widehat{V}_t(\beta,\hat{\phi})\), takes the same form of DRUnknown for CB, weighted by \(\hat{\rho}^{(i)}_{0:{t-1}}\). However, additional analysis is needed in the case of RL, as the \(\widehat{V}_t\) for each \(t\) are stochastically correlated. Now, as done in CB, we define the value regression function \(F_t(x,a;\beta,c,\phi)\) for each \(t\), given by \[F_{t}(x,a;\beta, c,\phi) =\rho_{0:t-1}\pi(a|x)\widehat{Q}(x,a;\beta) + \gamma^{-t} c^{\top} \dot{\hat{\mu}}(a|x;\phi).\] and we derive the influence function of the proposed estimator as stated in the following proposition.

Now, to derive the asymptotic variance of the proposed estimator for RL, we denote the vector \(\vec{F}_{t}(x; \beta,c, \phi)=(F_t(x, a; \beta,c, \phi))_{a \in \mathcal{A}},\) \(\pi \vec{Q}^t(x) = (\pi(a|x) Q^t(x,a))_{a \in \mathcal{A}}\) and the gradient matrix \(f_t(x;\beta,c, \phi) =\displaystyle\frac{\partial \vec{F}_t}{\partial(\beta,c)}.\)

The asymptotic variance of the DR OPE estimator for RL can be expressed with these notations as in the following proposition.

Similar to the case of CB, the proposition implies that minimizing the weighted sum of seminorms with respect to \(\beta\) and \(c\) is equivalent to minimizing the asymptotic variance of \(\widehat{V}^{\text{DR}}\). The solution \(\hat{\beta}\) of the following estimating equation is consistent for \(\beta_{\text{opt}}\), minimizing the asymptotic variance of \(\widehat{V}^{\text{DR}}\) by \(\sigma^2(\beta^*)=\mathrm{Var}_{\mu}{[\eta(\beta^*, c(\beta^*))]}\). \[\label{eq:RL95gradient95data} S_n(\beta,c)=\sum\limits_{i=1}^n\sum\limits_{t=0}^{T-1}\gamma^{2t} f_{t}^{(i) \top}(\beta,c,\hat{\phi}) M_t^{(i)}\bigl(\vec{F}_{t}^{(i)}(\beta,c) - \hat{\rho}_{0:t-1} \operatorname{diag}(\pi_t^{(i)})_{a \in \mathcal{A}} ~ \vec{r}_{t:T-1}^{(i)}\bigr)= 0,\tag{4}\] with the pseudo-reward \(\displaystyle{\vec{r}^{(i)}_{t:T-1}} = \bigl( \frac{\Delta_{a,t}^{(i)}}{\hat{\mu}(a|x_t^{(i)})} \bar{R}_{t:T-1}^{(i)} \bigr)_{a \in \mathcal{A}}\) for \(\bar{R}_{t:T-1}^{(i)} = r_t^{(i)} + \displaystyle\sum\limits_{\tau=t+1}^{T-1} \gamma^{\tau-t} \hat{\rho}_{t+1:\tau}^{(i)} r_{\tau}^{(i)},\) and \(M_t^{(i)}=\displaystyle\operatorname{diag}(\hat{\mu}(a|x_t^{(i)})^{-1})_{a \in \mathcal{A}} - J_K\).

5 Theoretical Properties↩︎

We now present the theoretical properties of the proposed estimator, with a focus on its asymptotic distribution. Combining Proposition [prop:influence], 2, 4 and 5, the DRUnknown has the following asymptotic normality for both contextual bandits and reinforcement learning problems.

To calculate the confidence interval of \(V^{\pi}\), one needs to estimate the unknown variance \(\sigma^2\). As we know that \[\begin{align} \sigma^2 &= \sigma^2(\beta^*, c(\beta^*), \phi) \\ &= \mathrm{Var}_{\mu}{[\widetilde{V}(\beta^*,c(\beta^*))]} = n \mathrm{Var}_{\mu}[\eta(\beta^*,c(\beta^*))], \end{align}\] we have \(\hat{\sigma}^2 (\beta, c(\beta^*), \phi) = \displaystyle\frac{1}{n} \sum\limits_{i=1}^n(\eta^{(i)}(\hat{\beta},\hat{c},\hat{\phi}) - \bar{\eta})^2\) is a consistent estimator for \(\sigma^2\), with \(\bar{\eta}=\displaystyle\frac{1}{n}\sum\limits_{i=1}^n\eta^{(i)}(\hat{\beta},\hat{c},\hat{\phi})\) the average of \(\eta^{(i)}\) and \(\hat{\beta}, \hat{c}\) are the solutions of 4 and the MLE \(\hat{\phi}\). By the Slutzky’s theorem, we have \[\hat{\sigma}^2 = \hat{\sigma}^2(\hat{\beta}, \hat{c}, \hat{\phi}) \xrightarrow{p} \sigma^2,\] and combining the result with the theorem we have the \((1-\alpha)\) confidence interval as \[\bigl[ \widehat{V}^{\text{DR}}(\hat{\beta},\hat{\phi}) - z_{\alpha/2} \frac{\hat{\sigma}^2}{\sqrt{n}}, \widehat{V}^{\text{DR}}(\hat{\beta},\hat{\phi}) + z_{\alpha/2} \frac{\hat{\sigma}^2}{\sqrt{n}} \bigr],\] with \(z_{\alpha/2}\) the \(\alpha/2\) standard Gaussian quantile.

When the value function model \(\widehat{Q}\) is also correctly specified, the proposed DRUnknown is asymptotically equivalent to the DR OPE estimator using the true logging policy and the value function, and is locally efficient.

Proposition 7 states that DRUnknown can be asymptotically optimal when the model \(\widehat{Q}\) is properly chosen. Also, for any choice of value function model, whether it is correct or not, the proposed estimator is asymptotically more efficient compared to existing OPE algorithms, including IPW, DR, and MRDR, in the OPE problem with an unknown logging policy.

6 Experimental Results↩︎

In this section, we compare the performance of the four estimators: (i) IPW [17] (ii) MLIPW [14] (iii) MRDR [8] and (iv) the proposed DRUnknown on CB and RL problems. IPW requires knowledge of the true logging policy \(\mu\) and cannot be applied in our experimental scenario. Therefore it serves as a baseline for the other three estimators, and we compare the relative MSE of each estimator.

6.1 Contextual Bandits↩︎

6.1.1 Simulation Data↩︎

We use the simulation environments described as follows. We generate \(N=100\) test datasets with size \(n\), given by \(D_{j} = \{(x_{i}^{j}, a_{i}^{j}, r_{i}^{j})\}_{i=1}^n,~j \in [N]\). The context \(x_{i}^{j}\) for \(i^{\text{th}}\) sample from \(j^{\text{th}}\) dataset contains \(d=5\) dimensional \(K=10\) vectors randomly sampled from uniform distribution \(U(-1/\sqrt{d},1/\sqrt{d})\). The rewards are generated from the Gaussian distribution with mean \(\exp (x_{i}^{j \top} \beta)\) and variance 1, where \(\beta\) is a fixed coefficient also sampled from the uniform distribution \(U(-1/\sqrt{d},1/\sqrt{d})\).

The logging policy \(\mu\) and target policy \(\pi\) follows the linear logistic model with random coefficients \(\phi_{\mu}\) and \(\phi_{\pi}\) as \(\mu(a|x) = \displaystyle \frac{\exp(x_a^{\top} \phi_{\mu})}{\sum\limits_{i=1}^K \exp(x_i^{\top} \phi_{\mu})}\) and \(\pi(a|x) = \displaystyle \frac{\exp(x_a^{\top} \phi_{\pi})}{\sum\limits_{i=1}^K \exp(x_i^{\top} \phi_{\pi})}.\) The logging policy model \(\hat{\mu}\) also follows the linear logistic model, while the value function model \(\hat{Q}\) is defined by the linear regression model. Consequently, only the logging policy model is correctly specified.

The Table 1 and Figure 1 reports the relative MSE values of MLIPW, MRDR and the proposed DRUnknown, calculated by dividing their MSE by the MSE of IPW, for the different sizes \(n\) of each dataset. The proposed estimator achieves the lowest relative MSE. Figure 2 displays boxplots representing the estimated values of four methods, each computed with \(N=100\) repeats and a dataset size of \(n=10000\).

6.1.2 UCI Machine Learning Repository Dataset↩︎

For the real data experiment, we transform six classification datasets of the UCI Machine Learning Repository into contextual bandit problems : glass, letter, zoo``image, iris and handwritten [20]–[25]. Assigning the data to each class is considered as pulling an arm in the bandit. When the class is correct the reward is 1 and otherwise 0.

We construct the logging policy \(\mu\) as follows: we train the policy \(\mu_0\) using a linear logistic model on a separate dataset, and mix the policy with a random policy \(\mu_{\text{random}}\) as \(\mu=\alpha \mu_0 + (1-\alpha)\mu_{\text{random}}\), for \(\alpha \in (0,1)\). The target policy \(\pi\) is constructed as in the simulation data experiment. The logging policy class is defined as \(\{\hat{\mu}=\alpha \mu_0 + (1-\alpha)\mu_{\text{random}}:\alpha \in (0,1)\}\), where \(\alpha\) serves as the parameter \(\phi\), and we use the constant value function model for \(\widehat{Q}\).

We generate \(N=100\) datasets, each with a size of \(n=10000\), by randomly sampling contexts from the original dataset and selecting arms using the logging policy \(\mu\). Table 2 displays the relative MSE values of MLIPW, MRDR, and our proposed DRUnknown. Additionally, Figure 3 depicts the log-relative MSE of each estimator on the glass dataset as a function of the logging policy parameter \(\alpha\). The DRUnknown consistently demonstrates the smallest relative MSE across all six datasets.

6.2 Reinforcement Learning↩︎

In this section, we provide the experimental results of OPE in the context of RL. We conducted the experiments on the ModelWin and ModelFail domains introduced in [6]. Detailed descriptions of these environments are available in the Appendix. As done in Section 6.1.2, we utilize a mixture of the separately trained optimal policy and the uniform random policy with a rate \(\alpha \in (0,1)\) as the logging policy \(\mu\). We employ a linear logistic policy for the target policy \(\pi\) and a linear model as the value function model \(\widehat{Q}\).

Table 4 displays the relative MSE of each estimator in ModelWin with \(T=20\) and ModelFail environments. The proposed DRUnknown attains the lowest relative MSE in most scenarios, if the number of sample \(n\) is large enough. Figure 4 illustrates the cumulative distribution function (CDF) of squared error values (larger is better) on the ModelWin domain with \(T=20\) and \(n=20\). The DRUnknown exhibits the highest CDF values, indicating that the estimated values are more concentrated around the true value with high probability.

6.3 Conclusion↩︎

In conclusion, our study has introduced \(\texttt{DRUnknown}{}\), a novel doubly-robust off-policy evaluation estimator for contextual bandits and reinforcement learning problems where both the logging policy and the value function remain unknown. Through a two-step estimation process, DRUnknown first estimates the logging policy using maximum likelihood estimator and subsequently estimates the value function model, aiming to minimize the asymptotic variance of the estimator while considering the impact of the logging policy estimation.

When the logging policy model is correctly specified, DRUnknown achieves the smallest asymptotic variance within the class that encompasses existing OPE estimators. Furthermore, if the value function model is also correctly specified, DRUnknown attains optimality by reaching the semiparametric lower bound for asymptotic variance.

To show the effectiveness of DRUnknown, we conducted experiments in both contextual bandits and reinforcement learning settings. The empirical results demonstrate the superior performance of DRUnknown compared to existing methods.

7 Broader Impact↩︎

This paper addresses the off-policy evaluation problem, aiming to contribute to the field of Machine Learning. It includes theoretical contributions and numerical experimental results, with no apparent societal or ethical issues that require further discussion.

8 Missing Proofs↩︎

8.1 Proof of Proposition [prop:influence]↩︎

8.2 Proof of Proposition 2↩︎

8.3 Proof of Proposition 4↩︎

8.4 Proof of Proposition 5↩︎

8.5 Proof of Proposition 7↩︎

8.6 Proof of Proposition 8↩︎

9 Estimation of \(\hat{\phi}\) with General Estimating Equation↩︎

The maximum likelihood estimator used to estimate \(\hat{\phi}\) in this work is most efficient in many situations. However, the theoretical results in this paper are applicable to other estimating equations as given below, \[U_n(\phi)=\sum\limits_{i=1}^n\sum\limits_{t=0}^{T-1}\sum\limits_{a \in \mathcal{A}}(\Delta_{a,t}^{(i)} -\mu(a|x_t^{(i)}) )h(x_t^{(i)},a;\phi)=0,\] for any smooth function \(h\). The equation \(U_n(\phi)=0\) is an unbiased estimating equation as long as the logging policy model is correctly specified. A possible choice is to assign more weight to the state-action pair with high probability in \(\pi\). This estimator remains consistent, satisfies the theoretical properties, and may be particularly useful for scenarios with a small-sized finite sample.

10 Descriptions on Experimental Settings↩︎

10.1 Simulation Data↩︎

To build the synthetic dataset for the simulation experiment, we generate elements for the context vectors \(x\) and the coefficient vector \(\beta\) from the uniform distribution \(U(-1/\sqrt{d},1/\sqrt{d})\). The reward mean is determined by the nonlinear function \(\exp(x^{t}\beta)\), making the linear value function model incorrectly specified.

For the logging policy \(\mu\) and the target policy \(\pi\), we generate the coefficients \(\phi_{\mu}\) and \(\phi_{\pi}\) from the uniform distribution \(U(-1/\sqrt{d},1/\sqrt{d})\) and \(U(-2/\sqrt{d},2/\sqrt{d})\), respectively.

10.2 UCI Dataset↩︎

The six datasets used in these experiments were initially designed for the classification problem. To transform the problem into a bandit setting, we interpret the assignment of the class label as the selection of an arm in a bandit, with a reward of 1 if the class is correct and 0 if incorrect. We train the classifier \(\mu_0\), which returns the probability of each class label given a context vector \(x\). We treat \(\mu_0\) as a policy and combine it with a uniform random policy with rates \(\alpha\) and \(1-\alpha\). The value function model is constant and can be regarded as an intercept value.

10.3 ModelWin and ModelFail↩︎

10.3.1 ModelWin↩︎

ModelWin consists of three states, starting from state \(s_1\). When choosing action \(a_1\), the agent moves to \(s_2\) with a probability of 0.6 and to \(s_3\) with a probability of 0.4. Conversely, action \(a_2\) leads to \(s_2\) with a probability of 0.4 and to \(s_3\) with a probability of 0.6. In states \(s_2\) and \(s_3\), both actions return the agent to \(s_1\) with a probability of 1. If the agent visits \(s_2\) or \(s_3\), it receives rewards of 1 and -1, respectively. The horizon is fixed at \(T = 20\).

10.3.2 ModelFail↩︎

ModelFail is an MDP with 4 states, but the learner cannot observe the current state of the agent. Starting from \(s_1\), action \(a_1\) leads to the upper middle state \(s_2\), and \(a_2\) to the lower middle state \(s_3\). From both, any action moves to the terminal state \(s_4\). If the transition is from the upper state, a reward of 1 is received; otherwise, a reward of -1. The horizon is always \(T = 2\).

For both environments, the target policy at \(s_1\) selects action \(a_1\) with a probability of 0.7 and \(a_2\) with a probability of 0.3. The logging policy chooses action \(a_1\) with a probability of 0.75 and \(a_2\) with a probability of 0.25. The parameter of the logging policy model \(\hat{\mu}\) for both environments is the probability of choosing \(a_1\), and the value function model \(\widehat{Q}\) is given by the linear model with intercepts.

11 Limiations↩︎

This paper primarily focuses on the asymptotic properties of the proposed estimator for the OPE problem with an unknown logging policy. We do not extensively explore the estimator’s behavior with a finite sample. This aligns with similar statistical works, such as [10], which addresses estimated missing mechanisms without providing finite-sample theory. Additionally, current DR OPE methods do not address scenarios with an unknown logging policy.

References↩︎