Deep Jump Q-Evaluation for Offline Policy Evaluation in Continuous Action Space
Authors: Hengrui Cai
Chengchun Shi
Rui Song
Wenbin Lu
Venue:  (2021)
Keywords: Continuous action space
Deep learning
Multi-scale change point detection
Off-policy evaluation

Abstract: We consider off-policy evaluation (OPE) in continuous action domains, such as dynamic pricing and personalized dose finding. In OPE, one aims to learn the value under a new policy using historical data generated by a different behavior policy. Most existing works on OPE focus on discrete action domains. To handle continuous action space, we develop a brand-new deep jump Q-evaluation method for OPE. The key ingredient of our method lies in adaptively discretizing the action space using deep jump Q-learning. This allows us to apply existing OPE methods in discrete domains to handle continuous actions. Our method is further justified by theoretical results, synthetic and real datasets.


Under review as a conference paper at ICLR 2021
DEEP JUMP Q-EVALUATION FOR OFFLINE POLICY EVALUATION IN CONTINUOUS ACTION SPACE
Anonymous authors
Paper under double-blind review
ABSTRACT
We consider off-policy evaluation (OPE) in continuous action domains, such dynamic pricing and personalized dose finding. In OPE, one aims to learn the value under a new policy using historical data generated by different behavior policy. Most existing works on OPE focus on discrete action domains. To handle continuous action space, we develop a brand-new deep jump Q-evaluation method for OPE. The key ingredient of our method lies in adaptively discretizing the ac- tion space using deep jump Q-learning. This allows us apply existing OPE methods in discrete domains to handle continuous actions. Our method is further justified by theoretical results, synthetic and real datasets.
INTRODUCTION
Individualization proposes to leverage omni-channel data to meet individual needs. Individualized decision making plays vital role in wide variety of applications. Examples include customized pricing strategy in economics (Qiang & Bayati, 2016, Turvey| (017), individualized treatment regime in medicine (Chakraborty) 2013 Collins & Varmus 2013). personalized recommendation system in marketing (MeInemny et al. 2018)] Fong et al. 20188) etc. Prior to adopting any decision rule in practice, it is crucial to know the impact of implementing such a policy. In many applications, it is risky to run a policy online to estimate its value (see, e.g., Li et al. (001)) Off-policy evaluation (OPE) thus attracts lot of attention by learning the policy value offline using logged historical data.
Despite the popularity of developing OPE methods with a finite set of actions (see e.g., Dudík et al., 2011 2014 Swaminathan et al. 2017 Wang et al.) (0017). less attention has been paid continuous action domains, such as dynamic pricing (den Bocr & Keskin 2020) and personalized dose finding (Chn et al., 2016). Recently, a few OPE methods have been proposed to handle continuous actions KKlluss& & Zhou 2018 [onndi et al. 2020; Colangelo & Lee 2020). All these methods rely on the use kernel function to extend the inverse probability weighting (IPW) or doubly robust (DR) approaches developed in discrete action domains. They suffer from three limitations. First, the validity of these methods requires the conditional mean of the reward given the feature-action pair to be smooth function over the action space. This assumption could be violated in applications such as dynamic pricing, where the expected demand for a product has jump discontinuities as a function of the charged price (den Boer & Keskin 2020). Second, the value estimator could be sensitive to the choice of the bandwidth parameter in the kernel function. It remains challenging to select this hyperparameter. Kallus & Zhou| (2018) proposed tune this parameter by minimizing the mean squared error of the resulting value estimator. However, their method is extremely computationally intensive in moderate high-dimensional feature space; see Section [S] for details. Third, these kernel-based methods typically use a single bandwidth parameter. This is sub-optimal in cases where the second order derivative of the conditional mean function has an abrupt change in the action space; see the toy example in Section 3.1 for details.
To address these limitations, we develop a deep jump Q-evaluation (DIQE) method by integrating multi-scale change point detection (see e.g., [Fryzlewizz] 2014),, deep learning (LeCun et al. 2015) and OPE in discrete action domains. The key ingredient of our method lies adaptively discretizing the action space using deep jump Q-learning. This allows us to apply IPW or DR methods to handle continuous actions. It is worth mentioning that our method does not require kernel bandwidth selec- tion. Theoretically, function of the action (Theorems andd2) (2) and converges faster than kernel-based OPE (Theorem Empirically, we show it outperforms state-of-the-aar OPE methods in synthetic and real datasets.
show it allows the conditional mean to be either continuous piecewise

---

Under review as a conference paper at ICLR 2021
2
PRELIMINARIES
We first formulate the OPE problem. We next discuss the bernel-based OPE methods and multi- change point detection, since our proposal is closely related to them.
2.1 OFF-POLICY EVALUATION
The observed datasets can be summarized into {(X,, A4, Yi)Jsisn where O, = (X, Yi) de- notes the
triplet for the ith subject and n denotes the total sample size. We assume these data triplets are independent copies of some population variables (X, A, Y). Let X' and A denote the feature and action space, respectively. We focus the setting where A is one-dimensional, as in dynamic pricing and personalized dose finding. A deterministic policy T : X' + A determines the action to be assigned given the observed feature. We use b denote the behavior policy that generates the observed data. Specifically, 6( b(((z) denotes the probability density or mass function of A given X I, depending on whether A is continuous or not. Define the expected reward function conditional on the feature-action pair
Q a) = [E = x, A = a}.
We refer to this function as the Q-function, to be consistent with the literature on developing indi- vidualized treatment regime (Murphy 2003).
As standard the OPE and the causal inference literature (see e.g. Chen et al. 2016), we assume the stable unit treatment value assumption (SUTVA), no unmeasured confounders assumption, and the positivity assumption are satisfied. These assumptions guarantee that a policy's 's value is estimable from the observed data. Specifically, for given target policy æ,, its value can be represented by
V(T) = B[Q(XXx(X)))
The goal of the OPE is to learn the value V(r) based on the observed data.
2.2 KERNEL-BASED OPE
For discrete action, Zhang et al. (012) and Dudik al. (2011) proposed DR estimator of V(T) by
a >
2 xX.)) + T(A, xXx)) ((4,)x,)
(0, (,6)
(Y, m(x))) (xx,
(1)
where II denotes the indicator function, @ and t denote some estimators for the Q-function and the behavior policy. The second term (-'(A,,,,,
((X))) Q(x,, x (X,))) inside the bracket corresponds to an augmentation term. Its expectation equals zero when Q = Q. The purpose of adding this term is to offer additional protection against potential model misspecification of the O-function. Such an estimator is doubly-robust in the sense that its consistency relies on either Q or b to be correctly specified. By setting 0, equation | is reduced to the IPW estimator.
In continuous action domains, the indicator function II(A, = x(x)) equals zero almost surely. Consequently, naively applying equation [ yields the plug-in estimator Σ Ô(X,, 7 (X.))/nn. To address this concern, the kernel- based OPE proposed to replace the indicator function in equation with kernel function K ((A x(X.)//h} with some bandwidth parameter h, i...
Q(X,, K((A, (X.))/b} (Y. Q(X,=(X)))) )(A,)x,)
sb (O,,
Σ
The bandwidth h represents trade-off. The variance of the resulting value estimator decays with h. Yet, its bias increases with h. More specifically, it follows from Theorem of Kallus & Zhou 2018) that the leading term of the bias is equal to
2 K (u)du E
(Q(X)
2
On2
(x)
To ensure the term in decays to zero as h goes to O, it requires the expected second derivative of the Q-function to exist, and thus Q(I, a) needs to be smooth function of a. However, as commented in the introduction, this assumption could be violated in applications such dynamic pricing.
2

---

Under review as a conference paper at ICLR 2021
Table 1: The bias and the standard deviation (in parentheses) of the estimated values for V(1)
and V(2), using DIQE and kernel-based methods. Y = 100, X, ~ Unif(o, 11, YIX, A ~ [[Q(X, A), 13. The target policy is given by x(x) z.
Method
DJQE
Kernel (small h, = 0.8) Kernel (large h. h 2)
(x) 0.34 (0.13)
0.65 (0.17)
0.33 (0.09)
V(2 0.11 (0.33)
0.03 (0.32)
1.21 (0.12)
Oracie O-function
Fiose D
Renund
34
Action
0.6
0.8
1.0
00
02
08
12
Acoo
Left panel: example of piece-wise constant function in change point literature. Middle panel: the oracle Q-function on the feature-action space. Right Panel: the green curve presents the oracle Q-function (zx, π (z)) under policy (z) = xı; and the red curve is the fitted mean value by DIQE and the pink dash line corresponds to the 95% confidence bound.
Figure 1:
2.3 MULTI-SCALE CHANGE POINT DETECTION
The change point analysis considers an ordered sequence of data, Yim (Yi,... Y.). with un- known change point locations, 7 [...... .Tk) } for some unknown integer K. Here, is an integer between and
inclusive, and satisfies т; < Tj for i < j. These change points split the data into K +1 segment. Within each segments, the expected response is constant function (see the left panel of Figure [ for details). A number of methods have been proposed on estimating change points (see for example, [Boysen et al. 2009 Killick et al. 2012 Frick et al. 2014; Fryzlewicz, 2014 and the references therein), by minimizing a penalized objective function:
1 K+1 Σ
arg min T.K
(C + +イkg 1=1
where C is a cost function that measures the gooddess-of-tte--. of the constant function within each segment and yK penalizes the number of change points with some regularization parameter 7. We remark that all the above cited works focused on models without features. Our proposal goes beyond these works in that we consider models with features and use deep neural networks (DNN) to capture the complex relationship between the response and features.
3 DEEP JUMP Q-EVALUATIION
In section
we use a toy example to demonstrate the limitation of kernel-based methods. We present the main idea of our algorithm in Section 3.2 Details are given in Section 3.3
3.1
3.1 TOY EXAMPLE
As discussed in the introduction, existing kernel-based OPE methods use a single bandwidth to construct the value estimator. Ideally, the bandwidth h in the kernel K ((A, -XX,)) shall vary with T (X,) to improve the accuracy of the value estimator. To elaborate this, consider the Q-function Q(x, a) = 10 max(a² 0.25, 0) log(x + +2) for any x, a E [0, 1). By definition, the Q-function is smooth over the entire feature-action space. However, it has different "patterns" when the action belongs to different intervals. Specifically, for E [0. 0.5). Q(x, a) is constant as a function of a. For E (0.5, 1]. Q(x, a) depends quadratically in See the middle panel of Figure [ details.
Consider the target policy (ax) xr. We decompose the value V(x) into (() + (2) (IT) where ((1) (T) = EQ(X, π (X)) < 0.5) and (TT) = EQ(X, म (X))I(T(XX) > 0.5).
Similarly, denote the corresponding kernel-based value estimators by
3

---

Under review as a conference paper at ICLR 2021
1 (T)
- n th (O,, (. (x(.)( 0.5) and V (x)
1 (n n, Q (,0)I((((x)) 0.5).
Since Q(x, a) is a constant function of a E [0, 0.5), its second-order derivative @Q a)/Od² equals zero. In view 2 when (2x) I 0.5, the bias of h (7()))
(T)) will be small even with sufficiently large h. As such, a large h is preferred to reduce the variance of (T)) When π ((x > 0.5, a small is preferred reduce the bias of (2 (x)). See Table for details where we report the bias and standard deviation of 1/ (1) (TT) and 17 (2) (TT) with two different bandwidths.
Due to the use of a single bandwidth, the kernel-basee estimator suffers from either a large bias or a large variance. To overcome this limitation, we propose to adaptively discretize the action space into a union of disjoint intervals such that within each interval I, the Q-function (Q(x, a) a E I) can be well-approximated by some function QI(xr) that is constant in I. Based the discretization, one can apply IPW or DR to evaluate the value. The advantage of adaptive discretization is illustrated in the right panel of Figure I When a S 0.5, the Q-function is constant in a. It is likely that our procedure will not further split the interval [o, 0.5]. Consequently, the corresponding DR estimator for (() will not suffer from large variance. When > 0.5, our procedure will split (0.5, 1] into a series of sub-intervals, approximating Q by a step function. This guarantees the resulting DR estimator for ((2) (и) will not suffer from large bias. Consequently, the proposed value estimator achieves a smaller mean squared error than kernel-based estimators. See Table for details.
3.2 THE MAIN IDEA
For simplicity, we set the action space A = [0, 1]. From now on, we focus on a subset of intervals in [0, 1]. By interval always refer to those of the form [c, d) for some 0 I < d < 1, or [c, 1] for some 0 I c < 1, denoted as I. A discretization 'D for A is defined as a collection of mutually disjoint intervals that covers A. Let [D] denote the number of intervals in D and [Z] denote the length of the interval I. We aim to identify an "optimal"" discretization D such that for each interval I E D. Qx a) is approximately a constant function of a E I. The number of intervals in D represents trade-off. If [D] is too large, then D will contain many short intervals, the resulting IPW DR estimator might suffer from large variance. Yet, a smaller value of (D) might result in large bias. Our proposed method adaptively determines DD and its size [D] as illustrated below.
To begin with, we cut the entire action space A into m initial intervals: [o, 1 mm.[1/m 2/m), [m - 1)/m, 1]. The number m shall be sufficiently large such that the Q-function can be well- approximated by piecewise function on these intervals. In practice, we recommend to set the initial number of intervals m to be proportional to the sample size n.. Note the set of these initial intervals is not the final partition DD that we recommend, but only serve as the initial candidate intervals. We next adaptively combine some of these initial intervals to form the final partition D. As shown in our numerical studies (see Table (jin Appendix [B for more details), the size of the final partition [D] is usually much less than m.
More specifically, denote by B(m) as the set of discretizations D such that the end-points of each interval I E lie on the grid [j/m 0, m). We associate to each partition E B(m) collection of functions (Qz)ZED. These functions depend only features, not the action. They are used to produce a piecewise approximation of the Q-function such that Q(a, .) se Σx I(a e ()) We model these QI using deep neural networks, to capture the complex dependence between the response and features. When the Q-function is well-approximated, we expect the least
square loss EIED E ET -x((x)) will be small.
Consequently, D can be estimated by solving
arg min (D, (0z : IE D)) (Qre0))
Σ
1 I(A ED(Y -Q(x)) + +111))
(3)
IED
for some regularization parameter and DNN class @. Here, the penalty term >/2| in equation controls the total number of intervals in D, as in multi-scale change point detection. A large results in few intervals in D and potential large bias of the value estimator, whereas small
4

---

Under review as a conference paper at ICLR 2021
could procedure large number of intervals in D, leading to noisy value estimator. In practice, use cross- coossvvalidttion to select the regularization parameter y that minimizes the mean square error of the fitted Q-function. We refer to this step deep jump Q-learning. Details of this step given in the next section. Given D, one can apply IPW or DR (see equation
I to derive the value estimates.
To further reduce the bias of the value estimator, we employ a data splitting and cross cross-fitting strategy, which is commonly used in statisties (Romano DiCiccio 2019). That is, we use different subsets of data samples learn the discretization D and to construct the value estimator. A pseudocode summarizing our algorithm is given in Algorithm in Appendix A We present the details below.
3.3 THE COMPLETE ALGORITHM
We present the details for DIQE in this section. It consists of three steps: data splitting, deep jump Q-learning, and cross-fitting.
Step 1: Data Splitting: We divide all samples into L subsets of equal size, where L denotes the indices of samples in the ?th subset for 1, L. Let TL .., nn. - Tu as the complement of L.g
Step 2: Deep Jump Q-Learning: For each l 1,... L, we propose to apply deep jump
learning to compute a discretization 1x(t) and [=(() I D(O) by solving version of equation using the data subset in L, only. We next present the computational details for solving this op- timization. Our approach is motivated by the PELT method (Killick et al. 2012) in multi-scale
change point detection. Specifically, for any interval I, define Ti
=2) the minimizer of
1
arg min QIEQ L
Σ I(A I){I((,) Yi}" -Y) iEL;
(4)
where |واا| denotes the number of samples in L. Define the cost function C(O as the minimum
value of the objective function i.e, (I) [Lg Eiere T(A; E implementation, we set Q as the class of multilayer perceptrons (MLPs, see Figure 3 in Appendix for an illustration) with L hidden layers and H nodes each hidden layer. The above optimization can be solved via the MLP regressor implementation of Pedrregos et al. (201T).
I){ 4T (X,) v. In our
Computation of (e4) relies on dynamic programming (Friedrich et al. 2008 For any integer 1 S V* < m, denote by B(m, v²) the set consisting of all possible discretizations De- of [0, v² /m). Set B8m, m) B(m), we define the Bellman function
inf Bell(v*) D.. EB+,,)m
Σ cl (I) + +1D0--11-1) and Bell(0) -yy
IED
Our algorithm recursively updates the Bellman function based on the following formula,
Bell(v")= = min { vER..
(Bell(v) (lu(/// /m)m 7} Vo" 2 1,
(5)
where R.,- is the candidate change points list updated by
Ru--1U fn" - 1} Bell(u) (v) + (wr/m, -v" 1)/m)) < Bell(u* - 11)}
(6)
during each iteration with Ro {0}. The constraint listed in 6 is important as it facilitates the computation by discarding change points not relevant to obtain the final discretization, leading to linear computational cost (Killick et al. (012))
To solve equation we search the optimal change point location that minimizes Bell(u"). This requires to apply the MLP regressor to learn
((f) ///m,////) and (ly/f, v² (mm) for each v E Re... Let vt be the corresponding minimizer. We then define the change points list r(x") = (u'.7("'))))
This procedure is iterated to compute Bell(x.) and r(w") for 1² 1, m. The optimal partition
D(O is determined by the values stored in 7 (see Algorithm in Appendix A for details).
Step 3. Cross-Fitting: For each interval in the estimated optimal partition D(0, we estimate the generalized propensity score function Pr(A E Z|X x) via the MLP regressor using the train- ing dataset T.S. Let (I(x)) denote the resulting estimate. The final estimated value for V(T) is
5

---

Under review as a conference paper at ICLR 2021
constructed via cross-fitting, given by,
((=)= - - Σ -
E Σ
I(A, EZ)
(X) E D (Y- - / (x.) + I(A, E I) (xi)
(7)
(I)))
TI 8-1 IEDOn 1E
Note the samples used to construct V inside bracket are independent from those to estimate QT and D(e) This helps remove the bias induced by overfitting in the estimation of g3 879 and D(O)
(1)) (00
4 THEORY
We investigate the theoretical properties of the proposed estimator. For simplicity, let the support X' = [0, 1 We will show our estimator consistent when the Q-function is either a piecewise function or a continuous function of a. Specifically, consider the following two model assumptions.
Model (Piece-wise constant function). Suppose
Q(z, a)
Σ [x())l(a I), E V A, IEDa
(8)
for some partition Do of [0, 1] and a collection of continuous functions (Qz)zEDo.
Model 2 (Continuous function). Suppose Q is a continuous function of a and x.
We first consider the case where the value function takes the form of equation g We remark that sernel-based estimators will fail under this model assumption, as it requires the second-ord codder deriva- tive of the Q-function to exist. Without loss of generality, assume qı, * qr, for any two adjacent in- tervals I, In E Dp. This guarantees that the representation in equation i unique. For any partition D [10, m) [2),
[TK. 1]] use J(D) to denote the set of change points (TI,-.. .Kk ) We impose the following conditions to establish our theories.
Assumption 1. The number of layers L and the number of nodes in each hidden layer H diverge with n, in that HI. = (nn),, for some constant < < 1/2.
Assumption 2. Functions {4z (o)) Zebe: are uniformly bounded.
Assumption 1 is mild, as both H and L are parameters specify. The part that HL O(n) ensures that the stochastic error resulting from the parameter estimation in the MLP is negligible. Assumption 2 ensures that the optimizer would not diverge in the lor sense. Similar assumptions are commonly imposed in the literature to derive the convergence rates of DNN estimators (see e.g.. Fareel al. 2018). These two assumptions guarantee the uniform consistency of the DNN estimator 19z Bun- See Lemma I in Appendix D for details.
Theorem Suppose Model 1, Assumptions and 2 hold. Suppose m diverges to infinity with n. Then, there exists some constant "to such that long as 0 < Yo. the following events occur with probability approaching 1 (w.p.a.l),
(i) [D(0] = (Dol; (ii) maX+eJ(Da) m(Doe) 1f- o (iii) (TT) = V(TT) + (1) for any policy such that for any To J(Do), (r(T(X) [To -, To - c)) + 0 as - 0.
Theorem 1 establishes the properties of our method under settings where the Q(a x) is piecewise function in a. Results (i) imply that deep jump Q-learning correctly identifies the number of change points. Results in (ii) imply that any change point in Do can be consistently identified.
In particular, (()) corresponds to subset of {1/m, 2/m, (m 1)/m}. With sufficiently large m, for any true change point T in Do. there will be change point in D(f) that approaches т. Consequently, the change point locations can be consistently estimated. To ensure the consistency of the proposed value estimator, we require that the distribution of the random variable π (X) induced by the target policy does not have point-masses at the change point locations. This condition is also mild. For instance, automatically holds when N (X) has a density function on [0, 1].
Theorem Suppose Model 2, Assumptions I and hold. Suppose m diverges to infinity and ? decays to zero. Then we have
(i) ma suPaEI E ( (X) a2 o(1); (10) (TT) V(r) op(1) for any m.

---

Under review as a conference paper at ICLR 2021
Szelate
Kalan 270a
120
100
92 203
10e
100
Figure 2: The box plot of the estimated values of the optimal policy under the proposed DIQE and two kernel-based methods for Scenario 1-4.
Theorem 2 establishes the properties of our method under settings where Q continuous a. Results in (i) imply that ((() (o) can be used to uniformly approximate Q(a, for any a E I. The consistency of the value in (ii) thus follows.
Finally, we conduct in-depth theoretical analysis to demonstrate the advantage of our estimator. Due to space constraint, we present an informal statement below. Details are given in Appendix C
Theorem (Informal Statement)
(i) When the Q-function belongs to a class of piecewise constant functions of the action a, the minimax rate of convergence of the proposed value estimator (n In contrast, the minimax convergence rate of kernel-based estimator Op 1/3))
(ii) When the Q-function belongs to class of smooth functions of a, the minimax convergence rate of our estimator faster than kernel-basse -ased estimators if the bandwdith undersmoothes or over- smoothes the data.
EXPERIMENTS
In this section, we investigate the finite sample performance of the proposed DIQE the synthetic and real datasets, in comparison to two kernel-based methods. The computing infrastructure used is a virtual machine in the AWS Platform with 72 processor cores and 144GB memory.
5.1 SYNTHETIC DATA
Synthetic data are generated from the following model:
Y|X, A N(Q(X, 1), b(4[X)
Unif[O, 1] and x11),x (2)) ,.... x(x) did Unif[-1,11] 1].
where X (X ; , (rij. Consider the following different scenarios:
S1: Q(x, = (1+ ( 0.35) (1) (((,) < < 0.65) + (1- 0.65); S2: Q(2, II(a < 0.25) sin(2 (1) < a 0.5) ((z(1) -0.75) S
0.75) + 0.51l(a 2 0.75);
S3 (toy): Q(I,a) = 10 max 0.25, 0} log (x (2) + 2);
S4: Q(x = 0.2(
+ 4z - 2x) - 22) 2(1 + (1) + 0.5z - 2
The Q-function a piecewise function of under Scenarios and 2, and continuous under Sce- narios 3 (toy example considered in Section 3.1) and 4. We set the target policy to be the optimal policy that achieves the highest possible mean reward. We list the oracle mean value under the optimal policy for each scenario in the first column of Table fable/iin Appendix B
We apply the proposed DJQE and two kernel-based methods (Kallus Zhou 2018 Colangelo & Lee 2020) to Scenario 1-4 with 20-dimensional covariates (p = 20) and n E [50. 100, 200, 300 For the DIQE, we select 7 E (0.1, 0.2, 0.3, 0.4, n. based on five-fold cross-validation. Here, we set n/100 to achieve a good balance between the bias and the computational cost (see Figure in Appendix for the detailed computational cost of the DIQE and the resulting bias as a function of in Scenario I with n 100). We find it extremely computationally intensive to compute the optimal bandwidth '* using Kallus & Zhou (2018)'s method (see the detailed comparison of computational cost under different methods based Scenario I in Table 3). Thus, as suggested in Kallus & Zhou (2018). we first compute using data with sample size no = 50. To accommodate
data with different sample sizes n, we adjust h by setting h² (ng/n)0 00.2 To implement Colangelo
7

---

Under review as a conference paper at ICLR 2021
Table 2: The bias, the standard deviation, and the squared error of the estimated values under the optimal policy via the proposed DJQE and two kernel-basee based methods for the Warfarin data.
Methods
Bias
Standard deviation
Mean squared error
DIQE
0.259
0.416
0.240
Kallus & Zhou 2018)
0.662
0.742
0.989
Colangelo & Lee (202))
0,442
1.164
1,550
& Lee 2020''s estimator, we consider a list of bandwidths, given by h Ca A 0.2 with {0.5, 0.75, 1.0. 1.5] and の is the sample standard deviation the action. We then manually select the best bandwidth such that the resulting value estimator achieves the smallest mean squared error. The conditional mean value and generalized propensity score are fitted via the MLP regressor with 10 hidden layer and 10 neurons in each layer. The average estimated value and its standard deviation over 100 replicates are illustrated in Figure 2 for different methods, with detailed values reported in Table in Appendix B In addition, provide the size of the final estimated partition under the DJQE in Table 5 in Appendix which is much smaller than m in most cases.
It can be seen from Figure Figure@that that the proposed DJQE is very efficient and outperforms all competing methods in almost all cases. We note that the proposed method performs reasonably well even when the sample size is small (n = 50). In contrast, two kernel-based methods fail accurately estimate the value even in some cases when n = 300. Among the two kernel-based OPE approaches, we observe that the method developed by Kallus & Zhou 20188 performs better in general.
5.2 REAL DATA: PERSONALIZED DOSE FINDING
Warfarin is commonly used for preventing thrombosis and thromboembolism.. We the dataset provided by the International Warfarin Pharmacogenetics (Consortium) 2009) for analysis. We choose p 81 baseline covariates considered in Kallus & Zhou (2018). This yields a total of 3964 with complete records of baseline information. The response defined the absolute dis- tance between the international normalized ratio (INR, a measurement of the time it takes for the blood to clot) after the treatment and the ideal value 2.5, i.e, Y = - -INNR- - -2.5.. We use the min-max normalization to convert the range of the dose level into [0, 1].
To compare among different methods, we calibrate the dataset to generate simulated outcomes. Specifically, we first estimate the Q-function via a MLP regressor with 10 hidden layers and 50 neurons in each layer using the whole dataset. The goodness-of-the- fit of the fitted model un- der the MLP regressor is reported in Table 6 in Appendix B We next use the fitted Q-function Q(X,A) A) to simulate the data. Given randomly sampled feature-action pair Tz) from ((A1,11)
(An, X, we set the reward r, N N{ ay), where ē is the standard devi- ation of the fitted residual (Y, - Q(X,, A.) Given the simulated data ((I,, og ry) : 1ssjjj S n). we are interested in evaluating the optimal policy: n (X) = arg (a (( The oracle value under the optimal policy is V = -0.278.
We apply the DIQE the calibrated Warfarin data, against kernel-based methods. Due the extremely intensive computation in Kallus & Zhou (2018), we directly apply the estimated optimal bandwidth h" in their real data analysis. since they used the same dataset. Biases, standard devia- tions, and mean squared errors of the estimated values are reported in Table 2 over 20 replicates for sample size n 500 under different methods.
It can be observed from Table 2 that our proposed DIQE achieves much smaller mean squared error than the two kernel-based methods, when evaluating
optimal policy. Specifically, the DIQE yields bias as 0.259 with the standard deviation as 0..166, 16, in contrast to the large bias as 0.662 with the standard deviation as 0.742 under underKallus Kallus & Zhou (2018)'s iss method and the bias as 0.442 with the large standard deviation as 1.164 under Colangelo & Lee (2020)'s 's method. Therefore, our proposed DJQE for off-policy evaluation with continuous actions works better than the sernel-basee methods.
DISCUSSION
Currently, we focus settings with single decision point. It would be practically interesting to extend our proposal to sequential decision making. A potential drawback of our method that would be very computationally intensive for a large m the runtime increases linearly in
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Leif Boysen, Angela Kempe, Volkmar I Liebscher, Axel Munk, Olaf Wittich, et al. Consistencies and rates of convergence penpp-penllized least squares estimators. The Annals of Statistics, 37(1): 157-183, 2009.
Bibhas Chakraborty. Statistical methods for dynamic treatment regimes. Springer, 2013.
Guanhua Chen, Donglin Zeng, and Michael R Kosorok. Personalized dose finding using outcome weighted learning. Journal of the American Statistical Association, 111(516):1509-1555 1521, 2016.
Victor Chernozhukov; Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, and Whit- ney Newey. Double/debiaased/eeynn machine learning of treatment effects. American Economic Review, 107(5):261-66 2017.
Kyle Colangelo and Ying- Ying Lee. Double debiased machine learning nonparametric inference with continuous treatments. arXiv preprint arXiv:2004..38 03036, 2020.
Francis Collins and Harold Varmus. A new initiative precision medicine. New England of medicine, 372(9):993-795, 2015.
International Warfarin Pharmacogenetics Consortium. Estimation of the warfarin dose with clinical and pharmacogenetic data. New England Journal of Medicine, 365(8):553-76, 2009.
Arnoud V den Boer and N Bora Keskin. Discontinuous demand functions: estimation and pricing. Management Science, 2020.
Miroslav Dudik, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. arXiv
preprint arXiv:1103 4601, 2011.
Miroslav Dudík, Dumitru Erhan, John Langford, Lihong Li, al. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485-51) 511, 2014.
Max H Farrell, Tengyuan Liang, and Sanjog Misra. Deep neural networks for estimation and inference: Application causal effects and other semiparametric estimands. arXiv preprint (iXiv:1800.0953, 2018.
Christian Fong, Chad Hazlett, Kosuke Imai, et al. Covariate balancing propensity score for a con- tinuous treatment: Application to the efficacy political advertisements. The Annals of Applied Statistics, ((1):156-177)) 2018.
Klaus Frick, Axel Munk, and Hannes Sicling. Multiscale change point inference. J. R. Stat. Soc. Ser. B. Stat. Methodol. 76(3):495-580, 2014. ISSN 1369-7412. doi: 10.1111/rssb, 12047. With 32 discussions by 47 authors and rejoinder by the authors.
Felix Friedrich, Angela Kempe, Volkmar Liebscher, and Gerhard Winkler. Complexity penalized m- estimation: fast computation. Journal of Computational and Graphical Statistics, 17(1):001-224, 2008.
Piotr Fryzlewiez. Wild binary segmentation for multiple change- point detection. Ann. Statist., 42 (6):2243-223) -2811, 2014. ISSN 0090-5364. doi: 10. 1245.
Masaaki Imaizumi and Kenji Fukumizu. Deep neural networks learn non-smooth functions effec- tively. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 869-878777777 PMLR, 2019.
Nathan Kallus and Angela Zhou. Policy evaluation and optimization with continuous treatments. arXiv preprint arXiv: 1802.06037 2018.
Rebecca Killick, Paul Fearnhead, and Idris A Eckley. Optimal detection changepoints with a linear computational cost. Journal of the American Statistical Association, 157-500) 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553):436 444, 2015.

---

Under review as a conference paper at ICLR 2021
Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of contextual- bandit-based news article recommendation algorithms. Proceedings of the fourth ACM inter- national conference Web search and data mining, pp. 297-306, 2011.
James McInerney, Benjamin Lacker, Samantha Hansen, Karl Higley, Hugues Bouchard, Alois Gru- son, and Rishabh Mehrotra. Explore, exploit, and explain: personalizing explainable recommen- dations with bandits. In Proceedings of the 12th ACM Conference on Recommender Systems, pp- 31-39, 2018.
Susan A Murphy. Optimal dynamic treatment regimes. Journal of the Royal Statistical Society: Series (Statisticul Methodology). -3353, 2003.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Sheng Qiang and Mohsen Bayati. Dynamic pricing with demand covariates. Available at SSRN 2765257, 2016.
Joseph P Romano and Cyrus DiCiccio. Multiple data splitting for testing. Department of Statistics, Stanford University, 2019.
Chengehun Shi, Sheng Zhang, Wenbin Lu, and Rui Song. Statistical inference of the value function for reinforcement learning in infinite horizon settings. arXiv preprint arXiv:2001.04515, 2020.
Arjun Sondhi, David Arbour, and Drew Dimmery. Balanced off off-policy evaluation in general action spaces. In International Conference on Artificial Intelligence and Statistics, pp. 2012-411222222 --222,, 2020.
Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miro Dudik, John Langford. Damien Jose, and Imed Zitouni. Off-policy evaluation for slate recommendation. Advances in Neural Information Processing Systems, pp.
2017.
Ralph Turvey. Optimal Pricing and Investment in Electricity Supply: An Esay in Applied Welfare Economics. Routledge, 2017.
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evaluation in contextual bandits. In International Conference on Machine Learning, pp. 3589-3597, 2017.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Baqun Zhang, Anastasios A Tsiatis, Eric B Laber, and Marie Davidian. A robust method for esti- mating optimal treatment regimes. Biometrics, 68: 1010-1018, 2012.
10

---

Under review as a conference paper at ICLR 2021
A
MORE ON THE IMPLEMENTATION
We summarize algorithm in Algorithm| I
Global: data {(X,, Ar, hsssi number of initial intervals m; penalty term y target policy т. Local: an upper triangular matrix of cost C E R=(m+1)/2 Bellman function Bell E IR";; partitions D; DNN functions {Ộz, by : I D}; vector T E N"; set of candidate point lists R.
Output: the value estimator for target policy (TT).
I. Split all n samples into subsets as ( .b..) ( 00;
II. Initialize even segment on the action space with pieces:
{I} = {0, 1/m) m). [1/m, m, 2/m).... [(m 1)/m, 1]}:
III. For f - 1, L:
1. Set the training dataset as L = f1,2. ,n] Lei
2. Bell(0) + y;; D- = [0, 1]; + Null; R(0) + {0};
3. Collect cost function:
For = 1, ................................ m: For - 0. (r 1):
(i). Let I [l/m,r/m) if < m else I 11/m, 1];
(ii). Fit a MLP regressor: (z)-) 1(i E (g) T)Y, [(A, M)ML((X))
(iii). Calculate the cost: C(T) + EiELe I(A, E (zz Y:)
4. Apply the PELT method to get partitions: For Dr 1...., m:
(i).Bell(v") = min (Bel((u) + C(vv/m, v² /m)) +7]:
(ii). of <- arg vin
(Bell(r) + C(u/m, v² /m)) +73:
(iii). T(U)) + T(=))
(iv). R(v*) + {v E R(v [1) - 13 Bell( + C(v/m, (v* 11/mm) S Bell(v* 11);
5. Construct the DR value estimator: r m; 4 r|r]: While > 0:
(i) Let = 7/m, r/m) if m else I = [1/m, 1]: D DUI:
(ii) Recall fitted MLP: (-(-) t lii (A) E Σ]И, ~ 1(A, EIMML((X.)
(iii) Fit propensity score: bz((.) < I1(i E (L) E I(A, E MLPP((X;) -
(iv) r r 1;1
6. Evaluation using testing dataset Lei
(in+==Izet (EreL, I(A, E I) return (())nn
[[(X)) (x(T)
(Y: - (x.)) + (x)):
Algorithm 1: Deep Jump Q-Evaluation
A 6
100 6
A (()
Figure 3: Illustration of multilayer perceptron with two hidden layers and three nodes each hidden layer. Here μ is the input, A and b(0) denote the corresponding parameters to produce the linear transformation for the (1 ([-1)th layer.
11

---

Under review as a conference paper at ICLR 2021
Time Onei (Mimuse)
0.7
028
025
16
Intbal mumbber
Inibial number Interves
Figure 4: The bias of the estimated value and the computational cost (in minutes) under the DIQE with different initial number of intervals (m) when 100 in Scenario 1.
B ADDITIONAL EXPERIMENTAL RESULTS
We include additional experimental results in this section.
Table 3: The averaged computational cost (in minutes) under the proposed DIQE and two kernel-
based methods for Scenario 1.
Method
DJQE
Kallus & Zhou (0018)
Colangelo Lee 2020)
50
<1 1
365
n = 100
3
773
<
n 200
1440 (24 hours)
πt = 300
14
>> 2880 (48 hours)
<
Table 4: The bias and the standard deviation (in parentheses) of the estimated values of the optimal policy under the proposed DJQE and two sernel-based methods for Scenario 4.
n
50
100
200
300
Scenario
DJQE
0.445(0.381)
0.398(0.391)
(.253(0.269)
0.209(0.210)
1.33
Kallus & Zhou (0018)
0.656(0.787)
0.848(0.799)
1.163(0.884)
0.537(0:422)
Colangelo & Lee (2020)
1,285(1.230)
1.473(1.304
L.826(1.463)
0.934(0.730)
Scenario 2 V = 1.00
DIQE
0.696(0.376)
0.502(0.311)
0.400(0.219)
0.411(0.168)
Kallus & Zhou 2018)
1.061(1.124)
1.363(1.13))
1.679(1.032)
1.664(0.792)
Colangelo & Lee (2200)
1.827(1.371)
(.299(1)458)
2.429(1.541)
2.264(1 .062)
Scenario 3 4.86
DJQE
2.014(0.865)
1.410(09887)
1.184(0.967)
1.267(0.933)
Kallus & Zhou (2018)
2.196(2.369)
2.758(2.510)
3.573(2.862)
1.151(1.799
Colangelo & Lee (2020)
2.586(2.825)
3.172(3.027)
3.949(3.391)
1.367(2.
Scenario 4 1.60
DJQE
0.494(0.485)
0.412(0.426)
0.349(0.383)
0.321(0.315)
Kallus & Zhou
2018)
2.192(1.210)
(740(1)034)
3.354(1.324)
1.555(0.500)
Colangelo & Lee
(2020)
2.975(1.789)
3.282(1.525)
3.921(1.927)
1.853(0.751)
Table 5: The averaged size of the final estimated partition ((D) in comparison to the initial number of intervals (m) under the proposed DIQE for Scenario to 4.
D / m
n =50
n 100
n =200
n =300
Scenario 1
3 5
4 10
6 20
6 30
Scenario
475
6/
9/20
11/30
Scenario 3
4/5
6/ 10
8/20 2/20
10730 30
Scenario 4
4/5
6/ 10
8 8/20
10/
12

---

Under review as a conference paper at ICLR 2021
Table 6: The mean squared error (MSE the normalized root-mean--suurr--deeee -uuea----aaadeeeitioon (NRMSD f the mean absolute error (MAB and the normalized MAE (NMAE the fitted model under the MLP regressor, linear regression, and the random forest algorithm, via ten-foff cen-fold cross- poss-validation.
Method MLP Regressor Linear Regression Random Forest
MSE
0.06
0.09
0.08
NRMSD
0.13
0.16
0.15
MAE
0.19
0.23
0.22
NMAE
0.10
0.12
0.12
C ADDITIONAL. THEORETICAL RESULTS
In this section, we conduct in-depth theoretical analysis to compare the minimax convergence rate of the proposed value estimator with kernel-based value estimator.
We first briefly summarize our theoretical findings. When the Q-function belongs to a class of piecewise constant functions of the action a, the proposed estimator converges faster rate than basedl-based estimators. Specifically, the kernel-based OPE converges at rate of n n-1/3 whereas our estimator converges at rate of n 11/2
When the Q-function belongs to a class of Lipschitz continuous functions of a, our estimator con- verges rate of n -1/5 whereas kernel-based estimators converge a slower rate when the band- wdith undersmoothes or oversmoothes the data.
As we have commented, it remains extremely challenging tune the bandwidth of kernel-based OPE in practice, since OPE is an unsupervised problem. The use of a suboptimal bandwidth would lead slower rate of convergence for kernel-based estimators. In contrast, we develop a supervised learning algorithm to adaptively discretize the action space. The tuning parameters in our procedure can be selected via cross- vooss-valiittinn.
All the above findings are supported by our observations in the toy example (Section 3.1 and nu- merical experiments (Section 5) as well.
We next present our theoretical results. We first introduce some notations. classes Q-funtiions:
Define the following
Q = { Q(ax))= >--
Σ I(a E IT) max I, L.E
E/qr, (X) 9I, (X)P
(9)
IED
|Dol I C(.Q(a, E A(3, C2), Va}.
2 2 sup [Q(a1,)) Q(22 x) < C2. Q(a,)) E A(3, C2), Va 41,03.z
for some sufficiently small constant 0 and some sufficiently large constants C, C2 0 where A33 C2) denotes the class of B-smooth functions (see e.g., Section 3.1.1, Shi et al. 2020 By definition, the first set Qi consists of all piecewise constant functions of with at most C₁ change points. The second set 22 contains the class of Lipschitz continuous functions of a.
Finally, define the policy class II {T
: क (X)) has density function bounded by C4} for some sufficiently large constant C4 > 0. To simplify the analysis, we assume the behavior policy is
'MSE +E
See https::/ena https::/en.wwkippeee
error.
RNSSD
VMSE
See
https://eh..kkjpddds.or....t
mAX
Root-moan- squaro- cevviation
"MAE = Σ V Y.I.
See
Srror.
MAE deviatio m)
NNM AE
See
13

---

Under review as a conference paper at ICLR 2021
known such that i = "2 b. In addition, assume the conditional variance of Y given A and X is uniformly bounded away from zero.
Theorem Suppose 23 > p. Then for any π. E II and any Q E 21, with proper choice of and the MLP class, the minimax rate of convergence the proposed value estimator is Op(n= 1/2). In contrast, the minimax convergence rate of kernel-based estimator Op(n (1/5).
Suppose 43 > 3p. For any Q E Q2, with proper choice of r and the MLP class, the minimax rate of convergence of the proposed value estimator Op(n' (1/5) -1/5), up some logarithmic factors. In contrast, the minimax convergence rate of kernel-basse estimator is slower when h z n" "ffor some 1/5 or K. > 3/5.
We briefly comment on the condition 28 p. This condition allows that the MLP regressor to converge
faster than n 1/4 (see e.g., Imaizumi & Fukumizu 2019). Such condition is commonly assumed in the literature on evaluating average treatment effects (see e.g., -g.,[hhennozuuooy al., 2017 Farrell al., 2018). the second part of Theorem we further require the MLP regressor converge at rate faster than n -3/10
D TECHNICAL PROOF
Throughout the proof, we use c, C, co, C, etc., denote some universal constants whose values allowed to change from place to place. Let O, = {X; Yi} denote the data summarized from the ith observation. For any interval I, let b(I[x:) denote the integral Jaez b(a[z))d.
Proofs of Theorems T and 2 rely on Lemmas] I aandd 2 Specifically, Lemma eestablishes the uniform convergence rate of qr for any I whose length is no shorter than o(7) and belongs the set of intervals:
(m)
[[i//m, /2 f//m): for some integers and that satisfy 0 S < is < m}
U (fa/mm, 1] for some integers iz that satisfy 0 S ig < m)-
To state this lemma, first introduce some notations. For any such interval I, define the function (π(x) = A E I, = x). It is immediate to see that the definition of qz here is consistent with the one defined in equation g for any Do.
Lemma
The following holds when either the conditions in Theorem 7 or pr hold:
max E(lgz(X) IEJ(m),
(10) (10 (x)PNO)))t_ o0()),
for any posilive constant 0.
Lemma When either the conditions in Theorem or hold, minze [Z] 2 C7 w.p.a. for some constani C >
We first present the proofs for these lemmas. Next present the proofs for Theorems I and
D.1 PROOF OF LEMMA I
For any sufficiently small constant > 0, it suffices to show
(X)
L (X)) Ce?,
TE3(m),
w.p.a.l, for some constant C > 1 whose value will be specified later. The proof is divided into two parts. In the first part, we show there exist some constants {0+)r such that
max max (x((x) - MLP( 02) S. TeD(m) sEA
(10)
In the second part, we show
max 2222
M|ILP((X
- (x) (C-))
(11)
14

---

Under review as a conference paper at ICLR 2021
The proof is hence completed.
Part Under the step model assumption, for any To Do. qI, (o) is continuous. Since the support X' is compact, qIn (o) is uniformly continuous. Similarly, show b is uniformly continuous as well. For any Ims we have
Saez EIED, b(al)][(a E (x)da
(r(x)
b(Σlz)
It follows from the uniform continuity of 9I, b and the positivity assumption that qr continuous for any I E (m).
Similarly, under the model assumption in Theorem 2 we can show qr is continuous for any I E (mm) as well. Consequently, when either the conditions in Theorem or hold, we obtain that qr continuous for any (m).
By Stone-Woad Weierstrass theorem, there exists multivariate polynomial function or such that the ab- solute value of the residual qr ---3 97 is uniformly bounded by e/2. By Theorem I of Yarotsky (2017). there exists a feedforward neural network with bounded number of hidden units that uniformly approximates 92. with the approximation eгrоr uniformly bounded by c/2 in absolute value. By Lemma 1 of et al. (2018), such a feedforward network can be embedded into an MLP with bounded number hidden units. Since we allow H and to diverge, such an MLP can be further embedded into an MLP with L layers and the widths of all layers being proportional to H. This yields equation 10 The proof for Part thus completed.
Part 2. We aim show equation
holds. Under the boundedness assumption Y, (gz()) (EE are uniformly bounded. We first observe that MLP( 07) is a bounded function, by equation and the fact that (z()) is bounded.
Next, it follows from equation TO that
EI(A E I)(Y - MLP(X; 0 Pr(A I) I)
EI(A E INTY - E(YJAEI,
Pr(AEI)
(12)
EIT( A E [)(B( X) MLP(X;
ETT(A E ENLY E(Y]AEZZX))
+
Pr(A II)
Pr(AEET
By definition,
EIELe
- ML)(X;;0)} MUPX
Eie, T(A EA) MLP(XX;
(13)
Pr(A ZZ)
Pr(AET)
Suppose show
EIel, I(A, E -D0X=MMP(XX;00) I -ML(XXXX))))) Pr(AEI)
sup I 2ey
[L((P((A
(14)
0xE0*
=0,
where the set O" consists of all 0r such that sup, MLP(2;; 0z)l S M for some sufficiently large constant M such that both 0% and 0(0) satisfy this constraint. It thus follows from equation and equation 13 that
(A E Z)(Y - O
EY - B EII + Pr(AEI)
II
w.p.a.1. Similar to equation 12
we have
ET(A E (Y - MIP(X: 000)2² ET(A - ELYMAE
Pr(AEI)
Pr(AEI)
E I, MLP(X: O 1
Pr(AEI)
15

---

Under review as a conference paper at ICLR 2021
It follows that
EA((A e ZY E X) Of)
Z)
Pr(AEZ)
2c
Under the positivity assumption, sup, b(Z)))/Pr( E I) 2 2(c 1)-1 for some constant >>>> 1.
This yields equation [I
To complete the proof, it remains to show equation 14 holds.
Using similar arguments in Section A.2.2 of Farrell al. 2018). for any have with probability
at least 1 - 2 2exp(-7 that
EiEr I(A: E IIY,, - MLP((;;; 0z)3²
EI(A E I)SY MLP(X:
(L(Pr(A
Pr(AEI)
S M7 +V ZZ oI,
1 n
M OII 0r)
log
+ log
for some constant ē 0, where o² corresponds to the variance of
I(A E I) MLP(X;0)}²
Pr(A E I)
Under the positivity assumption, we have (I, 0) - 0(1) where ((1) denotes some positive constant. Consequently, for any I whose length greater than cy we have with probability at least 1 - 2exp( (5) that
Eier, 1(Ar E IY MLP(X;;Z))²
EI - 02)1²
L Pr
Pr(AEI)
M n
H (log 7 + logn)
< 80
ny
ny
for some constant ēσ > 0.
Note that the number of elements in (mm) is upper bounded by (m 1)2. Since m proportional to by setting 2 log for some constant ट" > O, we have 2(m + 1)2 exp(-7) - 1. Consequently, follows from Bonferroni's inequality that the following event occurs w.p.a. for any I (mm such that [Z] e%
EiEL, T(A (Y, 0L)(X;;0))²
EI(A E ED(Y 0L)(X;02)12
I E
Pr(AEZ)
(15)
M logn
log
2 n27
log 7
where ((1) denotes some positive constant. hence completed.
Under the given conditions, the RHS is (1). The proof
D.2 PROOF OF LEMMA 2
Consider given interval I D(t) We find some interval I' (m) n ((0) that adjacent I. Consequently, the interval I I' belongs to ((m as well. It follows that
Σ E [Le] FELL
10) (xx))²
(X,)²
L
iELe
(16)
I(A EZUT')Y -10 (X,)3 -00
L
SELL
16

---

Under review as a conference paper at ICLR 2021
A1) By definition, Ir minimizes the loss Eier, I(A, ETUT) G2 (X:))² It follows that
(( Σ I(A E - PI (X,)) < RE
Σ
IIA E EIT)(Y, - (X.))
iEL.
Combining this together with equation 16 yields that
Σ iEL,
I(A IDY; -0% (X:))²
(17)
d() As both Y and QT are uniformly bounded, have Y c|Lel- IlAc I) for some
constant c > 0. By Bernstein's ' inequality, we have for any t > 0 such that
T(A, ET) Pr 2) +4
(18)
EEL.
with probability 1 cxpppxxxp nt2 / + t)) for some constant >
Similar to equation 15 by setting t = co max(m I|n log n, n- log n) for some constant čg > O, we obtain w.p.a. that
Σ I(A, EI Pr(ee) tz. Le EE
for any E [m). Under the condition that is continuous and AA X' is compact, b bounded. Consequently, the probability Pr(A E Σ) is proportional to the length of T. In view of equation [8 for any I D(0), it shall satisfy
log
I log
log
S 2
n
n
n
for some constant ō > 0, w.p.a.l, where the last incquality follows from Cauchy-Schward inequal- ity. As y >> n= log n, we obtain [I] 2 7/02 for any I E Bit)) and some constant 8ة >> 0, w.p.a.l.
The proof is hence completed.
D.3 PROOF OF THEOREM
We begin with an outline of the proof. The proof is divide into four steps. In the first step, we show
Pr(1 < (Dz)) 1.
(19)
In the second step, we show
max min (Po) (D(()
1 T| < 6min-
(20)
where 8min minzer, [I//3. By the definition of 8mins this implies that
Pr(1500 Dz)) 1.
(21)
together with equation Theorem In the third step, we show
Combining equation 22
19 proves (i) in Theorem I
This proves (ii) in
max min TEJ((D) (D)())
| - = (1).
(22)
In the last step, we show (iii) holds. The proof is thus completed.
We detail the proof for each of the step.
Step 1. Assume (Dol > 1. Otherwise, equation 19 automatically holds. Consider the partition
D {[0. 1}} which consists of single interval and zero q-function [0.1 definition, we have
for any By
Σ I E D)(Y; (x,)) + D(0 S Σ Y, + LLl7
ZEDIO KLL
iEL.
17

---

Under review as a conference paper at ICLR 2021
Since Y is uniformly bounded and y o(1), the right-hand-side (RHS) is O(n). Consequently, obtain
[D(O] S coo
(23)
for some constant > 0.
Notice that
Σ II(A
(X)P Σ Σ
E Qx,))
ZEDIO ELLI
TEDI iELe
V1
E IEDIO IEL
Σ
I(A E -x (X,))
(24)
2
Σ
Σ
E(A.E qr (x.))))) (X,) oz(xx))
ZEDIO NEL
We next show 12. 77s = (1))
Consider 7/2 first. Under Lemma 2 we have w.p.a.l that
Σ
Σ
T(A E () -x))
7/2
IEL
We decompose the RHS by
Σ
L (X) (x(
I 12|20
Σ
Σ
I[A 1) (X.) 2x(x)))² - E(I(A 1) (x) (x))))(()))
IED 122
The first line is (n), by Lemma second term is upper bounded by
Using similar arguments in equation 15 we can show the
T
Σ
M logn
H2
IED 1II20y
for some constant č w.p.a.l. In view of equation 23 the above expression can be further bounded by
Co M logn
H log
log nn
H log
ōn
Σ IE
O(1)n
+
7n
n
ym
where O(1) denotes some positive constant and the second inequality follows from the Cauchy- Schwarz inequality. This yields that 7/2 (n).
Using similar arguments, we can show that 173 = (n). It follows that
Σ
Σ I(A E I)(Y o7 (xi)) 2 + (n).
(25)
ZEDin FEL,
18

---

Under review as a conference paper at ICLR 2021
Notice that
111 = Σ
Σ I(A E X,),,,,,,)) - -x(())}
IEDIU VELL
Σ
Σ
I(A, EDIY; - Q(4,,)))+ E
-x)
TED iELe
ZEDIO iELe
+ 2 Σ
Σ
I(A E I)(Y Q(A,, Q(4,X) -x())
(ED(O iEL.
Using similar arguments in bounding and r7s we can show 7/s (p and that
7/s = Lel
Σ
Eb( a) (x( (n))
TED
The first term on the RHS is greater than con ΣxeBOn Jr B)Q -zzzzzz(X0 (x) for some constant > 0. It follows that
mn 14 + TTe
Σ TEQ(X,,)
qz da op(n).
IEDO
Note that under the step model assumption, 77 can be rewritten as ΣTED, Eieta 1(A E I)(Y; (x.))] This together with equation 25 yields that
Σ Σ I(A, IY(; (X,))²
TED IELL
EIA - (xx))) + col Σ
/ EIQ((, (x( + op(()) IeBio JI
IEDo iEL.
For any integer & such that S < [Do let T be the change point location that satisfies TØ
i e/m for some integer and that To. T. < m -1 Denoted by D* the oracle partition formed by
the change point locations {To |Dul-1 Set TÚ.0 = 0, To,PPo = 1 and T -1.
for 1 < < |Dol and [r.k-1111] = [. [[1]]- Let A = [Tū Tú.x) n [To,k-1, )o for
1Sk < |Dol and Aypal = [o. [To, 1]a. The length each interval As is at
most m 1. It follows that
Σ ΣTAA, E (x:))
Σ
T(A I)(Y. -xx())]
IED KEL
IEPo EELI
PPol
(26)
1(A
A
sup sup 9 (x)
I[
k=
Using similar arguments in bounding the RHS of equation 17 in the proof of Lemma 2 show the RHS of equation 26 is (n),, as m diverges to infinity. Combining this together with equation 25 yields
Σ IED LEL
Σ I(AA
(2))
Σ
Σ
I(Ai ID(Y - (X.))
IED* VEL,
(27)
+col TTd
Σ -x((x))))gx(X)3222)) + op(
Ie:i:
By definition, we have
Σ Σ1A, I(A ET) - (0
1/ (x.)) + -()
IeDio 1EL
Σ IEP
Σ I(A I)(Y + |Lee//1
19

---

Under review as a conference paper at ICLR 2021
Since [D"] (Dul, it follows from equation 27 that
Σ
BIQ(X,a) qr( s - | + oz().
(28)
IEDIO
Note that the left-hand-side (LHR) is non-negative. As 7 > 0, we obtain that |D(0| - (Dol, w.p.a.l. This completes the proof for the first step.
Step 2. It follows from equation 28 that
Σ TEDiG)
B)Q(X,a) qI(X)) S >1(oo - 1) + o,))
and hence
E BIQ(X, da 2> 1}, IED
(29)
w.p.a.1. We aim to show equation holds under the event defined in equation 29 Otherwise, there
exists some To (Po) such that Tol 2 Smin. for all E (P).. Under the event defined in equation 29 we obtain that
+omin
EIQ(X, (x) S 27([Dol 1),
(30)
w.p.a.l. I. On the other hand, since ((X,a) is constant function on [To - -mins TO) or [To, To + dmin),
we have
6mmin
a))
(x)( -xr()))rp"Xpp
Smin
min (6min E M/ro To) (X) 9(x))2 2 + smin ro (X) x
Óminn
8miuto
E q mm) (X) a(70.T0 Amnn
(X)) )
2
where
Kg =
min Ii To
Elgz, (X) 91z, (X) 2/ >
2, and Σg are adjacent
This apparently violates equation 30 where S Ko (o 41). equation t0 holds w.p.a.
Step 3: Combining the results obtained in the first two steps yields that [D(0] = |Dul, w.p.a.l. It follows from equation 28 that
/ EEQ((X, IEDO)
Σ
(x()) ol)
Using similar arguments in Step 2, we can show maX)eJ((,) min (e I r| < e w.p.a.l, for any sufficiently small > 0. The proof hence completed.
Step 4: We begin with notations. For any æ, define random policy Tio according the partition (()) as follows:
b(aaz)
Bie (a/z) = Σ HT(x) E I, I}
b(I(r))
ICD
Note that l/' TBc (a|x)da EicōO I(x(z)) E I)- = 1 for any Consequently, Thc is "valid" random policy.
20

---

Under review as a conference paper at ICLR 2021
The proposed value estimator (0 is doubly-robust to V(T By Lemma 1 the estimated Q- function is consistent. Consequently, (0 is consistent to Bi Since the propose estimator is weighted average of (7(0, it suffices show ((T is consistent ((x). Note that
{ ((X,a)
6(a[X) da b(Z[X)
(TT EE
Σ
E
10.11
IÇD(
[( ET b(I Io (X)
RaIa (X)
Σ
Io
b(I[X)
InEDo
IçD:
Similarly, we can show
((T)= = Σ
Eqi. (X) E To}.
(31)
IgEDo
For each To Do, there exists interval I D such that [UU Iol/ 1. We use 10 to denote this interval. Under the given conditions, we have
((TT(c))
Σ
Eqr. (X)IIT(X)) 10 op(1).
IoEDo
In view of equation 31 the value difference ((T - V(=)| can be upper bounded by
Σ
Pr(a(X)
1 + Σ Pr(a(() E 7/(²) Io) op(1).
IoEDo
IoEDo
The first two terms decay to zero under the given conditions on x (X). The proof is hence completed.
D.4 PROOF OF THEOREM 2
We need the following lemma to prove Theorem
Lemma Assume conditions Theorem
2 hold. Then for any interval I E J(m) with [Z] >> y
and any interval I' E DD with I S I', we have w.p.a.l that
IE [x)g((X) qr (x) = =(1),
where the little-o term is uniform in I and I'
The rest of the proof divided into three steps. In the first step, we show Assertion (i) in Theorem holds. In the second step, we show Assertion (ii) in Theorem holds. Finally, we present the proof for Lemma
Step 1. Consider a sequence (dn)n, such that dn - and dn >>
We aim to show inf oET' Bl[Q(X, a) Tr (X) ( (1(,))tt)) (1) By Lemma it suffices show
7.
I'eD(o)
inf Te
aET' E)Q(X,a) qr (X) = o(1.
Suppose [T' 2 d, Then according to Lemma 3 we can find some I such that CI 0. (x) qr (2 (1). Since [Z] - 0 and II, it follows from the uniform continuity of the Q-function that (X) Q(X, a)] - 0. The assertion thus follows.
Next, suppose I' d,. Then I'l + O as well. It follows from the uniform continuity of the Q-function that infaez l (X) - (X,, a)l + The assertion thus follows. This completes the proof for the first step.
Step Using similar arguments in Step of the proof of Theorem 1 suffices show ((T (TT) (1). By definition,
b(alX)
V(TB:o)) - V(*)=
Σ BeD
(Q((x E
da [X()
b(I
(1(()) E I) b(a(X) da.
= Σ
B(Q(X,
b(I[x)
J
DEDiO
21

---

Under review as a conference paper at ICLR 2021
It follows that
((T(()) E I) b(a(X) da
(TTB)) - -(())
Σ
inf d'ET
BIQ(d,,)
b(Ilx)
IeDi
E
inf
[IQ x) Q(T((XX E
a'Ez
IEDio
inf
EIQ X) Q(d",
In Step of the proof, we have shown that inf OEIo E)Q(X or =x) o(1). It follows
that inf eI,'EZ,IeDi0 BIQ(X, Q(a', x) = (1) and hence inf a' EI, [
Q(a", X)1 = o(1). by Cauchy-Schware inequality. This completes the proof for the second step.
Step 3. For given interval I' E Di0,, the set of intervals I considered in Lemma be classified into the following three categories.
Category 1: I == I', It is immediate to that qr 92 and the assertion automatically holds.
Category There exists another interval I E 3(m that satisfies I' = I U Z. Notice that the partition (1)) DD0 u (I") UI- - (I'} corresponds to another partition. By definition, we have
LL Σ Σ
IIA, E Io)lY, - oz,(3,))² 7/150)
iE DRE
E
1(A E Io){Y ā.. (X.))) +
LL
iELl IoED()
and hence
Σ EA) (x))) + SEL
1 Σ E(A ब (X.))²
[eel
RELE
1 Σ
[L
SEL
It follows from the definition of q.- that
T(A - O. (X:)²² <
Σ -
T
Lel
IEL
Therefore, we obtain
T(A E(A, - -
Σ EV - (X.)) 7
(32)
Le
LL
BEL
IELI
Category 3: There exist two intervals I",I* E (m)) that satisfy =I=-UZZ Using similar
arguments in proving equation 32 we can show that
I(A, INY (x,))
Σ I(A I)(Y; (X,))² 2%
IEL
VEL,
Hence, regardless of whether I belongs to Category 2, or it belongs to Category 3, we have
T( - - LLe
Σ T(A (xx))))) 27.
(33)
LLe
VEL
KEL
Using similar arguments in equation 15 we can show w.p.a.l that
T(A I)(; ?z(x))) = IY (x())))(())ee ((11
L
RELL
Σ I(A: E (x,)) BII(A I) (r)) of /(ZZ))
L
seL
22

---

Under review as a conference paper at ICLR 2021
where the little-o terms are uniform in I and T'. Combining these together with equation 33 yields
[ [) qz (xx)
(A Σ)(Y (x)) 2y ol >(v)
for any I and I', w.p.a.1. Note that az satisfies E[[(A E I) [x( = We have
E E
2 B[[(A (x))
- (x) 2x + ol o(v>lI).
Consider the first term on the RHS. Note that
E[U(A (x)x(X) - Cr (X)) -/AA E) / (X) +E (Tr 9z (x))) ( E (X) qr (Tr (X) -r (x)
By Cauchy-Schwand inequality, the last term the RHS can be lower bounded by
B[[ (xx(()) (x)) 2E] TI (X) or (x)3
2
It follows that
E[I(A E (xxx(xx)=
B[ B [ (x))
(A (zr - -x (x))
and hence
EE IXar(X) - (xx)))X))) 22 ol oVV S B[U(A E I) (x))))))))
[A (gz (x)))) By Lemma 1 and the positivity assumption, the RHS is (Z) Note that the little-o terms are uniform in and T'. As [Z] 7 obtain that
([A(A E (X)( or (O))))))eee =
uniformly for any I and I', equivalently,
E
(gx(X) - gr (x)3 = op(1).
7
By the positivity assumption, we have
(X) qu (X))](0)))e o7)),,
uniformly for any I and I', or equivalently,
E(gr(X) - 9r (X)]² = op)
This yields that
Exgz(X) - 9T
uniformly for any I and I'. The proof is hence completed.
D.5 PROOF OF THEOREM 3
In the first two steps, we compare the minimax convergence rate when Q Q1. In the next two steps, we compare the minimax convergence rate when Q E Q2.
Step 1: We provide a lower bound for the minimax convergence of kernel-based OPE when Q Q1 in this step. Consider piecewise constant Q-function
{
{ 0, a < 1/2,
Q(a, x)) =
1, otherwise.
Apparently, we have Q E Qi when C2 2 2 Define a policy π such that the density function of a (X) equals
4/3, 1f4 < T(x) 1/2 else if 1/2 2 (σ) < 4/3, 0, otherwise.
2/3,
23

---

Under review as a conference paper at ICLR 2021
We aim to show for such Q and the best possible convergence rate of kernel-base estimator is 11/3
We first consider its variance. Since the conditional variance of Y|A, X is uniformly bounded away from 0 and 1, similar to Theorem of Colaangllo & Lee| (2020), we can show the variance is lower bounded by ((1)(n))~ where (1) denotes some positive constant.
We next consider its bias. Since the behavior policy is know. The bias is equal to
K ((A (X)))/m)
{Y - -(T((X)),, = K[(A- xX))//}
- (((x)))))
xb(A(x)
hb(A(x)
(())k/22
K { a (x-m(X)
{1u-
E
(T(=(X) 1/2 T $ 1/2 < =(X)))
h
Using the change of variable a = ht + π (X), ) the bias equals
1/2 ((O(T(((X) s < + ht) T(T((((xx))))))))))))( + hd - 1/2 < (()))
E
-1/2
Consider any 0 < h S for some sufficiently small >> 0. The bias is then equal to
4
1/2
1/2
((t)[((a 1/2 a ht) I(a + ht S 1/2 < a)
1/2-6/2
-1/2
2
1/240/2
1/2
+
11/2
(I(a S 1/2 < a ht) I[(a + ht S 1/2 )
Under the symmetric condition on the kernel function, the above quantity is equal to
2
1/2
1/2
2
/1/2-h/4
fu K(I)dlda
1/2
K(I)dida 2
1/2-N/2
20
1/2-h/2
(1-20)/22 h
2 1/2-h/4
f
1/2
f K(t)dt.
K(t)dtda
3 1/2-h/2
1/1
6
Consequently, the bias is lower bounded by O(1)h where O(1) denotes some positive constant.
To summarize, the root mean squared error of kernel based estimator is lower bounded by (11)(mn))-1/2 + h} where (11) denotes some positive constant. The optimal choice of that minimizes such lower bound would be of the order O(n Consequently, the convergence rate lower bounded by O11)n-1/3
We derive an upper bound for the minimax convergence rate of our estimator when Q Q in this step. Using similar arguments in the proof of Lemma [ (see Section [D.I] and the proof of Theorem D in Imaizumi & Fukumizu (2019), we can show that with proper choices of the MLP networks, the following holds with probability at least O(n for some sufficiently large
Step 2:
constant C' >>< 0,
max IE3(m)..7
(1) E -
dz (X)) ((1)Z))228/(2++++ 23/(28+d) log" n,
(34)
where / is defined in Q and Qz-
By equation 34 and the condition that 7 > 28/((22)+)) log² n, using similar arguments in Steps 1 and 2 of the proof of Theorem [ we can show that the estimated change point locations are
consistent and ( = Do with probability 1 O( C). Similar to equation 27 it follows from
equation 34 that
Σ ( (x() O(n (28/222()))) T
JI
up to some logarithmic factors. This further implies that the change point locations in ( converge rate of -(222/(())))) up some logarithmic factors.
24

---

Under review as a conference paper at ICLR 2021
We next establish the statistical properties of our value estimates. We first observe that when is known, our estimator is unbiased to the unverse-propente score weighted estimator
I(A E I) Σ Σ " t=1 IED() 1EL
T( X1) E EI) Y.
(35)
xiI
Consequently, its bias is equal
(T) (Q(A, ((Tx)))(((XX)))))
Σ
Σ
BI(AEI)
C
b(I[X)
1=1 IED(O
[(x(X) EI)
Σ
Σ IEDO)
XQ(a,X) qr (x)))(((
b(Z[))
AEI
Since b is bounded away from zero and infinity, and that sup, Pr(x(()) E II/lI C4, the absolute value the bias is upper bounded by
1 0(1) Σ
(xx(X)
EZ)
E
1Q(a, X) - (xx(X)ld
[I
JEEZ
1=1
IED
s 0
Σ
Σ IEDI))
sup Q(aa - (z(x))da,
L
JEZ z
(=1
where (1) denotes some positive constant. For each I D(t), we could find some Iy Do such that the lengths of I To and In are upper bounded by O(n 22/(2)))) up to some logarithmic factors. By definition, we have
(I(x)) SAET EINED, Malx)I(( E Io) (x)da
b([[x)
Consequently, sup= 14x (x)) - yz, (a:) 00nn22//20+))) up to some logarithmic factors. It follows that the absolute value of the bias of bias is upper bounded by (( up to some
logarithmic factors. As |D(2)] = (Dol s C₁ with probability tending 1, the absolute value of the bias is upper bounded by
O Op(n -28/(2++)))
(36)
up to some logarithmic factors.
We next consider the variance. The variance is of the order of magnitude of that of equation 35 Since finite, suffices to consider the variance
L
Σ I(A, E I(T(X,) E I) Y.
Σ
(37)
b(I)X;)
DED iEC,
The variance of equation
37 is upper bounded by
I(T(X) ET)
I(x(X) EI)
O(n-')E Σ I(AEI)
O
Σ EI(AEII
6(I
(2(
IED
I(T(X) E
= 1(n
E
O(n 0(n
b(I[X)
IEDiO
where the last equality is due to that is uniformly bounded way from zero and that Pr(T(X) e Z) < 0(1) Z for some positive constant O(1). As |D(0] Doo < C₁ with probability tending 1. the variance of equation 37 upper bounded by Op(n-1) Consequently, the variance of our value estimator is bounded by On as well. In addition, note this bound and the bias bound
25

---

Under review as a conference paper at ICLR 2021
in equation 36 is uniform in Q Q1 Q2 and π II. The proposed value converges rate of Op(n (2202)) up to some logarithmic terms. When 23/ + p) > 1/2, both the bias and the variance decay at rate of 1/2 up to some logarithmic factors. This completes the proof for the first part.
Step 3. We provide lower bound for the minimax convergence of kernel-based OPE when Q Q2 in this step. Similar to Step I, we can show its variance is lower bounded by O(n 0(n-1/1) h)))) When n for some x > 3/5, the root mean squared error is larger than or equal to O(n 1r--(1 (1-x)/2).
Consider the Q-function
a क ((:) Q = Ch K
h
for some constant C > O. With proper choice of C, we can show that such a choice of Q-function belongs 22- Using similar arguments in Step 1, show the bias equals
BC K² K2 [(A -ai)x((X)/))))))) C-'E K [ (X))/h}
1²b(A|X)
h
Using similar arguments in Step we can show the right- hand-side is lower bounded O(1),. When h x n=* for some к < 1/5, the root mean squared error is larger than or equal to O(n ")).
To summarize, when h n = for some 1/5 or K > 3/5, kernel-based OPE converges a rate of -x" for some x* 1/5.
Step 4. We provide an upper bound for the minimax convergence of our estimator when Q E Q2 in this step.
Consider its bias first. Using similar arguments in Step 2, the bias is upper bounded by O(C- E Eredo Saer sup, 1Q(a, y (x)]da. Similar to Lemma 3, we can show for any interval I E {(m) with [I] > and any interval I' E Die with C I', we have w.p.a. that
Exzz(X) 4z (x) 0(1)
(38)
T
provided that y is proportional n 28/(284p) up to some logarithmic factors. For any a, there exists an interval I whose length is proportional to 7 log that covers a. Since Q Q2, we have sup, (Q(a, x) (r(x) = OZI)). This together with equation 38 yields that
Σ
sup IQ(a, or S 0(1)
[
7
7
D'ED "ET'
of the Set I = 11/3, the bias is upper bounded by 0(1),1/3, Using similar arguments in Step 2 proof, the standard deviation upper bounded by El= c- upper bounded by O(n 1/22-1/2) By setting 7 to be proportional to -3/5 (this rate is achievable under the condition that 433 3p), obtain the rate of n 115
By equation It
26


Reviews:
[{"review_id": "wrMx81rtqN0", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper proposes a new method that adaptively merges intervals to form a discrete action space where on each interval Q_I values are learned via deep neural networks. Then it applies ready-methods designed for discrete action spaces to do off-policy evaluation.\n\n##########################################################################\n\nReasons for score: \n\nThe paper offers a new way to apply methods designed for discrete action spaces onto continuous action spaces and it seems to perform better than the two chosen baselines as seen from the experiment results. Although the authors mentioned problems with the baseline models quickly, it would be nice to see a more in-depth analysis in the experiments to demonstrate these problems that this paper has set out to overcome. It is also not very clear to me when and why DJQE performs better than the baselines (does it always perform better than the baselines?). I gave a conservative score 4 but I'm willing to change my evaluation if convinced.\n \n##########################################################################\n\nPros: \n\nThe paper provided theoretical support to the proposed method by proving its consistency under two reasonable assumptions. The method was tested on both synthetic data and simulated real world data. \n \n##########################################################################\n\nCons: \n\nOverall the paper is not very clear to me. It would be nice to see more in-depth theoretical analysis on the main advantages of DJQE compared to the baselines, the lack of which generates the following questions: \n - Will this method always achieve lower biases than baselines on new datasets? I'm not sure about the quality of evaluation from a simulation model on the personalized dose finding application. \n - What are the potential problems/limitations of DJQE if there are any?   \n (Although these questions are commonly raised on methods that rely on experimental proofs of their superior performance, they seem particularly relevant for this paper.)\n\n##########################################################################\n\nQuestions during rebuttal period: \n\n - How does the computational cost of DJQE scale with a decreasing maximum threshold of bias?\n\n - How accurate is the simulation model trained on Warfarin? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "ijamhv400s-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of paper: \nThe main contribution of this paper is a new algorithm to learn the expected reward function for a given target policy using the historical data generated by a different behavior policy in continuous action domains.  All current Offline-Policy Evaluation (OPE) methods for handling continuous action domains use a kernel function to extend Inverse Probability Weighting (IPW) or Doubly Robust (DR) approaches for discrete action domains.  The algorithm proposed in this work adaptively discretizes the action space by combining methods in multi-scale changepoint detection, multi-layer perceptron regression and OPE in discrete action domains.  The finite sample performance of the proposed method, known as Deep-Jump Q-Evaluation (DJQE), is compared to that of two kernel-based methods, one due to Kallus and Zhou (2018) and another due to Colangelo and Lee (2020), on synthetic as well as real-world data.  To generate synthetic data, four scenarios are considered, where in each case the Q-function is continuous in the action domain or is a piecewise function of the action.  In almost all of these cases, DJQE outperforms the two kernel-based methods.  Similarly, when applied to real-world Warfarin data (after calibration), DJQE outperforms the two kernel-based methods with respect to the bias, standard deviation and mean squared error, even when the sample size is small (n=50).  The average runtime of DJQE in each scenario (for synthetic or real-world data) is about 5 minutes. \n\nPlus points:\n- The experimental results seem to demonstrate quite convincingly that DJQE outperforms the two kernel-based methods in almost all cases.   \n- The methodology seems sound. \n- The theoretical results also appear correct and prove the soundness of the method for a fairly wide range of functions - those that are continuous in the feature space and action domain, as well as those that are piecewise constant.\n- The method can model jump discontinuities in the Q-function. \n\nQuestions:\n- Why is it reasonable to assume that the Q-function can be well-approximated using piecewise linear combinations of MLPs?\n- How is the performance of DJQE affected by the choice of the regularization parameter \\gamma?\n\nMinor comments/questions:\n\n- Page 2, line -2: exists -> to exist\n- Page 3, line 4 of Section 2.3: segments -> segment\n- Page 3, line -4: Was there a reason for choosing the logarithm function here?\n- Page 4, lines 12 to 13: Is there a theoretical justification for such a choice of m, or is it based on empirical observations?  Also, to what extent does the performance of DJQE depend on the initial choice of m?\n- Page 5, Equation (4): Could it be justified why the minimizer is unique?\n- Page 5, third line after Equation (4): Should it be Figure 3, Appendix A?  (There is no Figure A.)\n- Page 5, line -4: How is \\hat{Q} used in the solution of Equation (5)?\n- Page 6, Assumption 1: \"...number of nodes [in] each hidden layer...\"\n- Page 6, last line of the statement of Theorem 1: Should D be D_0?\n- Page 6, lines -7 to -6: I did not fully understand what this means; do the change points of \\hat{D}^{\\ell} vary with m?\n- Page 7, line -7: data -> dataset\n- Page 7, line -5: How was the exponent 0.2 chosen?\n- Page 7, last line, and Page 8, line 9 of Section 5.2: \"...with 10 hidden [layers]...\"\n- Fifth reference on Page 10: Double occurrence of \"Technical report\".\n\n* Update after reading author(s)' response: Thank you very much for the detailed answers to my questions (as well as the other reviewers' comments/questions).  I have upgraded my score; wishing you all the best. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Rp_wz1Lj40", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of off-policy evaluation with continuous actions. The main idea is to first using multi-scale change point detection to discretize the action space and then apply traditional IPW or DR methods to estimate the value. The DJQE method is theoretically analyzed under both the cases that the Q function is either a piecewise function or a continuous function. For continuous function, it is not surprising that as the number of splits m goes to infinity as n, the estimation is consistent, while additional results in Theorem 2 also shows that for limited m, the estimator can also be shown as a uniform approximation of the Q value. Experiments consider both a toy dataset and a real problem in personalized does finding, and the results show that the DJQE method is superior than existing methods for continuous Q evaluation.\n\nThe paper is clearly written and easy to follow. I only have a few comments:\n\n1. In the experiments, since computing the optimal bandwidth is very time consuming for the baseline methods, it would good to provide a detailed computation cost comparison. \n2. As mentioned in the method part, m is initially set to be proportional to n, and the final partition size is much smaller than m. Would the authors shows these detailed numbers in the experiments?\n3. It could be great if more real-world problems can be evaluated in the current experimental section, such as the dynamic pricing example introduced previously.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Dptt-8J09p4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis paper proposes a new method for offline evaluation when the action space is continuous, one dimensional. This overcomes the drawbacks of the kernel based method, which cannot be applied to non-smooth Q functions and requires heavy computation to optimize the bandwidth. The proposed method can be applied to discontinuous Q functions like step functions, and achieves smaller bias. This is made possible by the adaptive jump q learning method.\n\n\nPros\n\nWhile the kernel method requires a single bandwidth to control the bias and variance of the value estimator, the proposed method adapts to the shape of the Q function by dividing the action space in an adaptive way, so that the MLP fitted in each interval of the action space approximates well the real Q function. Hence, the intervals can have possibly different lengths according to the shape of the true Q function. A multi-scale change point detection method is used for determining the intervals, which requires only a linear computational cost. \n\nExperiment results are convincing.\n\nCons\n\n1) In Algorithm 1, “Collect cost function step” computes MLP regressor for every possible interval. Hence, computation will become heavy when the number of initial intervals (m) is large. Authors should add discussion about this point.\n\n2) Some notations are confusing\n\n\nMinor comments \n\n1) Gamma appears before it is defined.\n2) L is both the number of subsets and the numer of layers in neural networks.\nAre they meant to be the same (as they increase with n), or are they different? In the latter case, they should be distinguished.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the OPE problem under the contextual bandit model with continuous action.  They studied the model of a piecewise constant value function according to the actions.   The assumption is new, though still somewhat restrictive as it requires the piecewise constant partitions to be the same for all x.  The proposed algorithm estimates the partitions, and then used it to build a doubly robust estimator with stratified importance sampling (fitting an MLP for each partition separately).


The reviewers have mixed views about the paper.  The following is the AC's evaluation based on reading the paper and consolidating the reviewers' comments and the authors' responses.

Pros: 

- The algorithm is new and it makes sense for the new problem setup  (though computationally intractable)
- The experimental results outperform the baseline and reinforces the theory. But it's a toy example at best.

Cons:

- The method is called "Q-learning" but it is somewhat disappointing to see that it actually applies only to the contextual bandit model (without dynamics).  There is quite a bit of branding issues here. I suggest the authors to revise it to reflect the actual problem setup.

-  The estimator is assumed to be arg min, but the objective function is non-convex and cannot be solved efficiently in general, e.g., (3) involves searching over all partitions... and (4) involves solving neural network partitions.  In other words, the result applies to a hypothetical minimizer that the practical solvers may or may not obtain (the authors cited Scikit-Learn for the optimization algorithm and claims that the optimization problem can be solved, which is not the case ...  the SGD algorithm can be applied to solve it, but it does not necessarily find you the solution). 

- The theory is completely asymptotic and generic. There is no rate of convergence specified, and no dependence on the number of jumps |D_0| at all in Theorem 1.  

-  Theorem 3 is obnoxiously sloppy. The assumptions are not made explicit (do you need Assumption 1 and 2, what is the choice of \rho? ) The notion of "minimax rate" is not defined at all.   Usually the minimax rate is the property of problem setting,  i.e., Min over all algorithms, and Max over all problems with in a family.  However, in the way the authors described the results in Theorem 3,  it says the "the minimax convergence rate of kernel-based estimator is Op(n^{−1/3})."  which seems to be restricting the algorithms instead.  Such non-typical choices require clear definitions and justification.    Based on what is stated, it really appears that the authors are just comparing upper bounds of the two methods.

I looked at the appendix and while there is a "lower bound analysis", the bound is not information-theoretical, but rather a fixed example where an unspecified family of algorithms (I think it is a specific kernel smoothing method with a arbitrary choice of the bandwidth parameter h) will fail. 

Suggestions to the authors:

-  Instead of a piecewise constant (and uniformly bounded) function, why not consider the total variation class, which is strictly more general and comes with the same rate?

- For formalizing the lower bound, I suggest the authors to look into classical lower bounds for linear smoother, e.g., Donoho, Liu, MacGibbon (1990); which clearly illustrates that kernel smoothing-type methods do not achieve the minimax rates; and that wavelets-based approaches, locally adaptive regression splines, and fused lasso (You can think about the  Haar Wavelets as a basis function of piecewise linear functions ) do. 

The authors can improve the paper by ensuring that the theoretical parts are clearly and rigorously presented; and perhaps to iron out the more useful finite-sample analysis that depends on model parameters of interest.
Decision: Reject