Non-asymptotic Confidence Intervals of Off-policy Evaluation:  Primal and Dual Bounds 
Authors: Yihao Feng
Ziyang Tang
na zhang
qiang liu
Venue: ICLR 2021 Poster (2021)
Keywords: Non-asymptotic Confidence Intervals
Off Policy Evaluation
Reinforcement Learnings

Abstract: Off-policy evaluation (OPE) is the task of estimating the expected reward of a given policy based on offline data previously collected under different policies. Therefore, OPE is a key step in applying reinforcement learning to real-world domains such as medical treatment, where interactive data collection is expensive or even unsafe. As the observed data tends to be noisy and limited, it is essential to provide rigorous  uncertainty quantification, not just a point estimation, when applying OPE to make high stakes decisions. This work considers the problem of constructing non-asymptotic confidence intervals in infinite-horizon  off-policy evaluation, which remains a challenging open question. We develop a practical algorithm through a primal-dual optimization-based approach, which leverages the kernel Bellman loss (KBL) of Feng et al. 2019 and a new  martingale concentration inequality of KBL applicable to time-dependent data with unknown mixing conditions. Our algorithm makes  minimum assumptions on the data and the function class of the Q-function,  and works for the behavior-agnostic settings where the data is collected under a mix of arbitrary unknown behavior policies.  We present empirical results that clearly demonstrate the advantages of our approach over existing methods.


Published as a conference paper at ICLR 2021
NON-ASYMPTOIE CONFIDENCE INTERVALS OF OFF- POLICY EVALUATION: PRIMAL AND DUAL BOUNDS
Yihao Feng',. , Ziyang Tang"
Na Zhang
University of Texas at Austin {yihao, ztang)@cs wtw.aa.eee..oo.. edu
Tsinghua University
zhangna@pbost tsinghua edu.
Qiang Liu
University of Texas at Austin iqiangêes utexas. edu
ABSTRACT
Off-policy evaluation (OPE) is the task of estimattnn the expected reward of given policy based on offline data previously collected under different policies. Therefore, OPE is key step in applying reinforcement learning to real-world domains such as medical treatment, where interactive data collection expensive or even unsafe. As the observed data tends to be noisy and limited, it is essential to provide rigorous uncertainty quantification, not just a point estimation, when applying OPE to make high stakes decisions. This work considers the problem of constructing non- asymptotic confidence intervals in infinite-horizon off-policy evaluation, which remains a challenging open question. We develop practical algorithm through a primal-dual optimization srasedettio--seed approach, which leverages the kernel Bellman martingale concentration inequality
loss (KBL) of Feng et al. (2019) and KBL applicable to time-dependent data with unknown mixing conditions. Our algorithm makes minimum assumptions the data and the function class of the O-function, and works for the Dehavior-agnostic settings where the data is collected under a mix of arbitrary unknown behavior policies. We present empirical results that clearly demonstrate the advantages of our approach over existing methods.
INTRODUCTION
Off-policy evaluation (OPE) seeks to estimate the expected reward of target policy in reinforcement learnings (RI.) from observational data collected under different policies (e.g., Murphy et al.. [00T]
Fonteneau et al. 2013 Jiang Li 2016 Liu al. 2018a). OPE plays a central role in applying reinforcement learning (RL) with only observational data and has found important applications in areas such as medicine, self-driving, where interactive "on-policy" data expensive or even infeasible to collect. A critical challenge in OPE is the uncertainty estimation, bounds essential for making high-stakes decisions. providing non-asymptotic confidence intervals of the expected value of the target policy. Our method allows us to rigorously quantify the uncertainty of the prediction and hence avoid the dangerous case of being overconfident in making costly and/or irreversible decisions.
having reliable confidence
this work, we aim to tackle this problem by
However, off- policy evaluation per se has remained a key technical challenge in the literature (c.g..
Precup 2000 Thomas & Brunskill] 2016 Jiang & Li 2016 Liu et al. 2018a), 1et alone gaining rigorous confidence estimation of it. This is especially true when 1) the underlying RL problem is long infinite horizon, and 2) the data is collected under arbitrary and unknown algorithms (a.k.a. behavior-agnostic). As a consequence, the collected data can exhibit arbitrary dependency structure, which makes constructing rigorous non-asymptotic confidence bounds particularly challenging. Traditionally, the only approach to provide -symmttti confidence bounds in OPE is to combine importance sampling (IS) with concentration inequalities (c.g.. Thomas et al. 2015a b). which,
however, tends to degenerate for long/infinite horizon problems (Liu et al. 2018a) Sa). Furthermore,
"Equal contribution.

---

Published as a conference paper at ICLR 2021
neither can this approach be applied the behavior-agnostic settings, nor can it effectively handle the complicated time dependency structure inside individual trajectories. Instead, it requires to use a large number of independently collected trajectories drawn under known policies.
In this work, we provide a practical approach for Behavior-agnose Off-policy, uninite-horizon, oon-asympooii, Confidence intervals based arbitrarily Dependent data (BONDIC). Our method is motivated by a recently proposed optimization-ban
(or variational) approach to estimating OPE confidence bounds (Feng et al. (020), which leverages a tail bound of kernel Bellman statistics (Feng) et al. 2019). Our approach achieves a new bound that is both an order-of-magniuude tighter and computationally efficient than that of et al. (2020). Our improvements are based on two pillars 1) developing a new primal-dual perspective on the non-asymptotic OPE confidence bounds, which is value estimation [Liu et al. 2018a| Nachum et al. 2019a Tang et al.] 2020a] Mousavi et al. 2020): and 2) offering new tight concentration inequality on the kernel Bellman statistics that applies to behavior-agnostic off- off-policy data with arbitrary dependency between transition pairs. Empirically, we demonstrate that our method can provide reliable and tight bounds on a variety of well-established benchmarks.
connected a body of recent works on unfinie-hhrrizn
Related Work Besides the aforementioned approach based on the combination of IS and concen- tration inequalities (e.g.. (e.g..(Tomm) Thomas et al. 22) bootstrapping methods have also been widely used in off-policy estimation (e.g., White & White 2010 [Hanna et al. 2017: Kostrikov & Nachum 2020). But the latter is limited to asymptotic bounds. A hernatively Bayesian methods (e.g. Engel et al.) 2005, Ghavamzadeh et (0166) offers a different way to estimate the uncertainty in RL, but fails to guarantce frequentist coverage. In addition, Distributed RL (Bellemare et al. (017) seeks to quantify the intrinsic uncertainties inside the Markov decision process, which orthogonal to the estimation of uncertainty that we consider.
OPE, including Liu et al.] (2)T8a); Feng et al.] (2019);)))))) Tang et al. (2020a): Mousavi et al. (2020), well as the DICE-family (e-g.. Nachum et al. 201 /Zhang et al.] 2000aa) Yang et al. al.] 2020b). In partieular, our method can be viewed extending the minimax framework of the infinite- -ooizonn OPE in the infinite
Our work is built upon the recent advances in behavior aggnosic
data region by Tang et al. 2020a); Uchara et al. (2020): Jiang & Huang (2020) to the non-asymptotic
finite sample region.
Outline For the rest of the paper, we start with the problem statement in Section 2 and an overview on the two dual approaches infinite-horizon OPE that are tightly connected to our method in Section We then present our main approach in Section Iaaioonnannd and perform empirical studies in Section 5 The proof and an abundance of additional discussions can be found in Appendix.
BACKGROUND, DATA ASSUMPTION, PROBLEM SETTING
Consider an agent acting in an unknown environment, At each time step t, the agent observes the current state s; in a state space S. takes an action a, ~ 7(- st) an action space A according to a given policy π, then, the agent receives a reward r; and the state transits to s = $1+1, following an unknown transition/reward distribution (rt, 8t+1) ~ P(- 8t; ar). Assume the initial state sp is drawn from an known initial distribution Dg. Let 7 E (0, 1) be a discount factor. In this setting, the
expected reward of π is defined as J/s := EE, D 7're so Do which is the expected total discounted rewards when we execute starting from Do for steps. In this work, we consider the infinite-hrrizz case with T - +00.
Our goal is to provide an interval estimation of Jr for a general and challenging setting with significantly released constraints on the data. In particular, we assume the data is behavior-agnostic and off-policy, which means that the data can be collected from multiple experiments, each which execute mix of arbitrary, unknown policies, or even follow non-fixed policy. More concretely, suppose that the model P is unknown, and we have set of transition pairs D,, (si, 0s, rı, $() collected from previous experiments in a sequential order, such that for each data point i, the (re, $ drawn from the model P(- s; a;), while (s,, a;) is generated with an arbitrary black box given the previous data points. We formalize both the data assumption and goal as below.
2

---

Published as a conference paper at ICLR 2021
Assumption 2.1 (Data Assumption). Assume the data D,, (si; a4 Pi, s() is drawn from ar- bitrary joint distribution, such that for each I,..., n, conditional on Dzi == (8), 05, rj. ". 33)ssss (st Qi), the subsequent local reward and next state (r., are drawn from P(- a:).
Goal Given a confidence level E (0, 1), we want to construct an interval JJ] C IR based on the data Dn, such that Pr(J= E [+) 2 1 - 6, where Pr(.) is w.r.t the randomness of the data.
The partial ordering on the data points is introduced to accommodate the case that 8141 equals s' for some i. The data assumption only requires that (r,,5) is generated from P(- 8t, az), and imposes no constraints on how (si, as) is generated. This provides great flexibility in terms of the data collection process. In particular, we do not require (Ng, at);== to be independent always assumed in recent works (Liu et al. 2018a; Mousavi et al. (2020).
crucial fact is that our data assumption actually implies a martingale structure on the empirical Bellman residual operator of the Q-function, As we will show in Section this enables us to derive a key concentration inequality underpinning our non- -onmatypttoiic confidence bounds.
Here, we summarize a few notations that will simplify the presentation in the rest of work. First of all, we append each (st, at Tss s() with an action de x( s{)) following s/. This can be done for free as long as is given (See the Remark in Section 3. Also, we write 24 = (8i, (8i,0:), na (6(, a²), and y/4 = (1'; r;) = (s², a',, rz). Correspondingly, defiee X S x A to be the state-action space and Y' = X' x IR. Denote P (y æ²) P(s', r x r) s'). In this way, the observed data can be written as pairs of y: Vi J= and Assumption 2.1 is equivalent to saying that yı P (- an:)) given Dei.
which is similar to supervised learning setting. We equalize the data D, with its empirical measure D = Ei= b2.w:/n, where ó is the Delta measure.
TWO DUAL APPROACHES TO INFINITE- OFF-POLICY ESTIMATION
The deficiency of the traditional IS methods on long-finfinite-horizo RL problems (a.k.a. the curse of horizon (Liu et al.
2018a) Sab) has motivated a line of work on developing efficient infinite- horizon
value estimation (c. (e.g.. Liu al., 2018a Feng et al. 2019 Nachum al., 2019a Zhang al.) 2020a
Mousavi et al. 2020 Tang et al. 2020a). The main idea is to transform the value estimation problem
into estimating either the Q-function or the visitation distribution (or its related density ratio of the policy æ. This section introduces and reinterprets these two tightly connected methods, which serves to lay out a foundation for our main confidence bounds from a primal and dual perspective.
Given policy π. its Q-function is defined as (z) = E. Et= 7-rx Zo = x]. where the expecta- tion is taken when we execute ग initialized from a fixed state-action pair (sp, (n) = 2o = x. Let Dr.. be the distribution of (Iz, yt) = (st, ax2 5;; d/, rt) when executing policy æ starting from ~ Do for t steps. The visitation distribution of π is defined as D = Er D'xx,e- Note that D integrates to 1/(1 - 7), while we treat it as probability measure in the notation.
The expected reward can be expressed using either 4a or D2 as follows:
J = Ex
rr 1=
Er [r] = Eew (9x (z)],
where 7 ~ Dar (resp. I ~ D .) denotes sampling from the r-(resp. x-) marginal distribution of D (resp. o), Eq. L plays a key role in the infinite-horizon value estimation by transforming the estimation of Jr into estimating either frr or D
Value Estimation via Q Function Because Dr.u(2) Do J Do(s) (als) is known, we can estimate J by EE [ with any estimation & of the true fuuuctio q the expectation under x ~ D can be estimated to any accuracy with Monte Carlo. To estimate Jr, consider the empirical and expected Bellman residual operator:
Rq(x, y) = g(z) 7q(x')-=)))))))))>)))))) -r,
Rx9(z) = Ey- a) [ w)
(2)
It is well-known that yz is the unique solution of the Bellman equation R. O. Since yı (-(+))
for each data point in D,,, if q gr, then Ry(2,, w:), 1, .. all zero-mean random variables.
3

---

Published as a conference paper at ICLR 2021
Let be any function from X' to R. then E, Rg n.. Ye (z, also has zero mean. This motivates the
following functional Bellman loss (Feng et al. 2019 2020; Xie & Jiang 2020).
1
Lw(q: Dn): == sup
Ri(es ())(()))
(3)
WEW
where W is set of functions w: X R. To ensure that the sup is finite, W is typically set be an unit ball of some normed function space Wo. such that W = fw E Wo: ||ll I 1}. Feng et al. (2019) considers the simple case when W taken to be the unit ball K of the reproducing kernet Hilbert space (RKHS) with positive definite kernel k: X' x X -> R, in which case the loss has simple closed form solution:
1 Σ 65=1
Li D,)
Rq(2,, (y) Rq(zs,
(4)
Note that the RHS of Eg. is the square roor of the kernel Bellman V-statistics in Feng al. (2019). Feng al. 2019) showed that, when the support of data distribution D,, covers the whole space (which may require an infinite data size) and is an integrally strictly positive definite kernel, Lic(;; D,) = 0 iff On Therefore, one can estimate by minimizing Lx, D..)
Remark The empirical Bellman residual operator R can be extended to R4(x; y) = ((z) - r 7 E==1(ss', q(s',a)), af), where {a() are i.i.d. drawn from t (-|s'). As m increases, this gives lower variance estimation of R, If m = +oo, we have Rz(z, y) = (xx) which coincides with the operator used the expected SARSA (Sutton & Barto 1998). In fact,
- <t) [g ('),,a))
without any modification, all results in this work can be applied to Rq for any m.
Value Estimation via Visitation Distribution Another way to estimate J in Eq. is to approx- imate D with a weighted empirical measure of the data (Liu et al., 2018a| Nachum et al.) 2019a] Mousavi et al. 2020 Zhang et al. 2220a)). The key idea is to assign an importance weight w (x;) to each data point x; in D,, We can choose the function w: X' R properly such that D, and hence Jx can be approximated by the w-eegttted empirical measure of D,, as follows:
Jx = J. := E. [r]
1 Σ wI))). n
D D
Σ
(5)
72
Intuitively, w can viewed as the density ratio between Dj and D,, although the empirical measure Dn may not have well-defined density. Liu et al. 20) Mousavi et al. (2020) proposed to estimate w by minimizing a discrepancy measure between D and D,. To see this, note that = D, if and only if A(D, 4) for any function y. where
A(D, q) = Ep (ool)(x') {xx)] - ED, (ng(x') - ((x)]
(6) using the fact that E.p, h79(2') - ((x) = .ED,,, [g(x)] (Theorem 1, Liu et al. 2018a). Also note
Ep (g(4') {(x)] + (gD.ol((2)))
that the RHS of Eq. (6) can be practically calculated given any D and y without knowing D,, Let Q be a set of functions X + R. One can define the following loss for wt
Io(w; D..)) sup
A(D .)
Similar to Lw(z; D,)) when Q is a ball in RKHS, To(w; D,)) also has a bilinear closed form analogous to Eq. 44); see Mousavi et al. (2020) and Appendix F As we show in Section 4 To (w; D.) and Lw(4; D,,)) are connected to the primal and dual views of confidence bounds, respectively.
4 MAIN APPROACH
Let Q be a large enough function set including the true Q-function 4a. that is, 4x E Q. Following Feng et al. 2020), a confidence interval [J Jt wl of Ja can be constructed as follows:
j = sup qEe
{ (ED,oly s.l. Tw(g; Dm)) S En }
(8)
4

---

The bound Eq. is guaranteed to be a 1 d confidence bound only when the maximization in Eq. (8) is solved to global optimality. With a large n, this leads to a high computational cost, even when choosing Q as the RKHS. [Feng et al.) (2020) solved Eq. (8) approximately using random feature technique, but this method suffers from a gap between the theory and practice. In Section 4.2, we address this problem by presenting a dual form of Eq. (8). which sidesteps solving the challenging global optimization in Eq. (8p. Moreover, the dual form enables us to better analyze the tightness of the confidence interval and issues regarding the choices of Q and W. Published as a conference paper at ICLR 2021
and Jo. is defined in similar way by replacing sup on q E Q with inf.
The idea here is to seek the extreme function with the largest (resp. smallest) expected values in set == on {g: (x; D.) S ). Therefore, Eq. (8) would be a 1 - 8 confidence interval if qn is included F. with at least probability - 6, which is ensured when 4x Q and
Pr(Iw(1r: D.)) S E.) 1 -
(9)
Feng et al. (020) showed that in the RKHS case when W = K. Eq. (9) can be achieved with
1og(1/0) (1/6)
1
En
20 Nb
(10)
n 71
when n is an even number, where Cg. & sup, y
Rg (z. kk x). This was proved using Hoeffd- ing's s inequality for U-statistics (Hoeffding) [963). To solve Eq. (8) efficiently, Feng et (2020) took Q to be ball in RKHS with random feature approximation. Unfortunately, this method as described by Eq. 10P has two major disadvantages:
1) Bound Needs to Be Tightened (Section sub-optimal in rate. In Section 4.1 we improve it by En Onn-1/2) bound under the mild Assumption 2.1] which gets rid of the independence requirement between the transition pairs. Our tightened bound is achieved by firstly noting Martingale structure on the empirical Bellman operator under Assumption 2.1. and then applying an inequality in Pinelis (1992).
4.1
The bound of E. O(n-1/4) in Eq. is
2) Dependence on Global Optimization (Section 4.2)
4.1 A TIGITER CONCENTRATION INEQUALITY
In this section, we explain our method to improve the bound in Eq. (10) by giving a tighter concen- tration inequality for the kernel Bellman loss in Eq. (4). We introduce the following semi-expected kernel Bellman loss:
1 n
Le D..)
Σ
R ((:())))(( (. R,)
(11)
in which we replace the empirical Bellman residual operator Rg in Eq. (3) with its expected counter- part R,g, but still take the empirical average over (a; ) in D,, For more general function set W. we can similarly define Lw D,,)) by replacing Rq with R, q in Eq. (3). Obviously, we have Lw(g; D,,) = 0 when g = 4--
Theorem 4.1 below shows that Tx<[;; D,,) concentrates around T. (g: D.) with an 0 error under Assumption 2.1
first glance, may seem surprising that the concentration bound is able to hold even without any independence assumption between } ). An easy way to make sense of this by recognizing that the randomness in y) conditional on x; is aggregated through averaging, even when ) are deterministic. As Assumption 2.1 does not impose any (weak) independence between {æ:). we cannot establish that Li(g: D.)) concentrates around its mean ED, [Lx( (q: D,.)] (which is a full expected kernel bellman loss), without introducing further assumptions.
Theorem 4.1. Assume K. is the unit ball of RKHS with a positive definite kernel k(-,,) .). Let Cg.k = co. Under Assumption 2.1 for any 8 E (0, 1), with SUPzeX (R((, R=
5

---

Published as a conference paper at ICLR 2021
least probability 1 8, we have
Lxc(1 D.)) Licl;; Dm) S 2c log(2/0)
(12)
n
In particular, when Qr we have Car.k = sups,y (R x (cc, y)) 2k( and
22 log(2/6)
Lx(1ri Dn)= I
(13)
n
Intuitively, to see why we can expect an O(n bound, note that Lx, D..)) consists of the square root of the product of two Rq terms, each of which contributes O(n O(n-1/2) 1/2) error w.r.t. R,
Technically, the proof is based key observation: (x:( 1,...,W7 forms a martingale difference sequence w.r.t {Dcr: Vi .,..., n) in the sense that Z Dei]= = 0, Ví. See Appendix B for details. The proof also leverages special property of RKHS and applies a Hoeffding-like inequality the Hilbert spaces as in Pineliss (992
Assumption 2.1 ensures that Z, := RQ( y/s
(see Appendix B). For other more general function sets W, we establish in Appendix E a similar bound by using Rademacher complexity, although it yields less tight bound than Eq. 12 when W I.
4.2
DUAL CONFIDENCE BOUNDS
We derive dual form of Eq. { that sidesteps the need for solving the challenging global optimization in Eq. (8). To do so, let us plug the definition of Lw(g: D,)) into Eq. (3) and introduce Lagrange multiplier:
J sup inf inf ED,, [g] -
h(:;) Ra En
(14)
ge NEW X20
n1
suu inf 9E0 WEW.
ED lal
((x en |kellm
(15)
n
where we use ((x) Xh(x). Exchanging the order of min/max and some further derivation yields the following main result.
Theorem 4.2. I) Let W be the unit ball of normed function space W.. We have
Je. s (T(w) = =o [r] + To(w; D.)) + en Wkll Vo E Wo,
(16)
Ja. 2 [o(w)= = :B [r] - 1- l-w D..) en Wwll. Vw E W.,
where -Q (-9: Q} and hence I- ((w; Dn) = Iolw: D.) 1 Further, we have Jo.w inf (w) and Jo.w = supwew, Fo (w) if is convex and there exists a E Q that satisfies the strict feasibility condition that Lw(g; D.)) < En-
II) For D, and ê E 10, assume W., and En E R satisfy Eq. (9) (e.g., via Theorem 4.1 Then for any function set 2 with q= 2, and any function w Wo (the choice of Q, W4, w- can depend on D, arbitrarily), we have
Pr Jxx [o(w-), F ($(+)) 2 1-6.
(17)
Theorem 4.2 transforms the original bound in Eq. 8 framed in terms of and Lw(g: D,)), into
form that involves the density-rabe -ratio and the related loss Lo(w; D.). The bounds in Eq. (66 can be interpreted assigning an error bar around the w-based estimator J. E [r] in Eq. with the error bar of [=Q(w; D..) en ||wlw, Specifically, the first term L= D,.)) measures the discrepancy between Dy and D, as discussed in Eq. (7) whereas the second term captures the randomness in the empirical Bellman residual operator Ry

---

Published as a conference paper at ICLR 2021
Compared with Eq. (8) the global maximization on q E Q is now transformed inside the [w D,)) term, which yields a simple closed form solution in the RKHS case (see Appendix [F). In practice, we optimize w- and w to obtain the tightest possible bound (and hence recover the primal bound) by minimizing/maximiziiii
Fo (w) and F (w), but is not necessary to solve the optimization to global optimality. When Wo is an RKHS, by the standard finite representer theorem (Scholkopt & Smola, 2018), the optimization on w reduces a finite dimensional optimization, which can be sped up with any favourable approximation techniques. We elaborate on this in Appendix [
Length of the Confidence Interval The form in Eq. I66 also makes it much easier to analyze the tightness of the confidence interval. Suppose w W4 and Q - 2. the length of the optimal confidence interval is
length([J f(wl) inf {2le(w; Dn) + 25 |Wlll. weW.
Given En is O(n-1/3) we can make the overall length of the optimal confidence interval also O(n-1/2), as long as W. is rich enough to include good density ratio estimator w that satisfies To(w"; Da) O(n and has a bounded norm ||w'.w..-
We can expect to achieve Lo(w"; D.)) = (/221/2) when (1) Q has an
sequential Rademacher complexity (Rakhlin et al. 2015) (e.g., a finite ball in RKHS); and (2) D, is collected following Markov chain with strong mixing condition and weakly converges to some limit distribu- tion D whose support is X. and therefore we can define w' as the density ratio between D and De Refer to Appendix [for more discussions. Indeed, our experiments show that the lengths of practically constructed confidence intervals do tend decay with an (1/2) rate.
Choice of W and Q To ensure the concentration inequality in Theorem 4.1 is valid, the choice of W. cannot depend on the data D,.. Therefore, we should use a separate holdout data to construct data-dependent W. In contrast, the choice of Q depend the data D, arbitrarily, since it is part of the optimization bound Eq. (8) but not in the tail bound Eq. (9). In this light, one can construct the best possible Q by exploiting the data information in the most favourable way. For example, we can construct an estimator of q R ! based on any state-of-the-an method (e.g.. Q-learning or
model-based methods), and set Q to be ball centering around q such that qa Ô E Q. This enables post-hoc analysis based on prior information on qa. as suggested in Feng et al. (020)).
Mis-specification of and Oracle Upper/Lower Estimates Our result relies on the assumption that O- E Q. However, as with other statistical estimation problems, there exists no provably way to empirically verify the correctness of model assumptions such as Qa E Q. Because empirical data only reveals the information of the unknown function (in our case gn)) conclusion can made on the unseeing data points without imposing certain smoothness assumption. Typically, what we can do is the opposite: reject (- E Q when the Bellman loss Lw(4; D,)) of all in Q is larger than the threshold E..
finite number data points, but no
We highlight that, even without verifying Jn E Q, our method can still be viewed as a confidence interval of a best possible (oracle) upper and lower estimation given the data D,, plus the assumption that 9x E 2, defined as
J suup q
ED
s.t. Rq(
Rg vi), Vi = 1, 1,....n
(18)
In fact, it is impossible derive empirical upper bounds lower than J3. as there is no way to distinguish g and gn if Rq(x;, vi) = Rg (x,, yi) for all i. But our interval [Jo,x, - provides 1 - confidence outer bound of [J J once Eq. (9 holds, regardless if 4a E holds or not.
Hence, is of independent interest to further explore the dual form of Eq. 18 which another starting point for deriving
bound. We have more discussion in Appendix
Lastly, we argue that it is important to include the Q the bound. Proposition G.I in Appendix shows that removing the q Q constraint in Eq. (18) would lead to infinite upper bound,
7

---

Published as a conference paper at ICLR 2021
KBL BONDIC (Oum)
1.0
(Interval length)
Reward
10P.
Reward
0.5
0.5
0
10-1
0.0
066
000
10a
10
10
80% 90%
98%
(a) Transitions, n
(b) Transitions, n
(c) 1
(d) 8
Figure I: Results on Inverted-Penduluee (a) The confidence interval (significance level 5 = 0.1) of our method
(green) and that of Feng et al. (2020) (blue) when varying the data size (b) The length of the confidence intervals (8 0.1) of our method scaling with the data size n.. (c) The confidence intervals when vary the significance level (data size n 5000). (d) The significance level ò vs. the empirical failure rate of capturing the true expected reward by confidence intervals (data size 5000). We average over 50 random trials for each experiment.
unless the {St, s from D, almost surely covers the whole state space S in the sense that (s E {8,, s11=1 1.
EXPERIMENTS
We compare our method with a variety of existing algorithms for obtaining asymptotic and non- asymptotic bounds a number of benchmarks. We find our method can provide confidence interval that correctly covers the true expected reward with probability larger than the specified success probability 8 (and is hence safe) across the multiple examples we tested. In comparison, the non-asymptotic bounds based on IS provide much wider confidence intervals. On the other hand, the asymptotic methods, such as bootstrap, despite giving tighter intervals, often fail capture the true values with the given probability in practice.
Environments and Dataset Construction We test our method on three environments: Inverted- Pendulum and CartPole from OpenAI Gym (Brockman et al. 2016). and a Type-1 Diabetes medical treatment simulator We follow a similar procedure as Feng et al. (020)) to construct the behavior and target policies. more details on environments and data collection procedure are included in Appendix H.I
Algorithm Settings We test the dual bound described in our paper. Throughout the experiment, we always set W = K., the unit ball of the RKHS with positive definite kernel k; and set Q = roK, the ball of radius re in the RKHS with another kernel k. We take both kernels to be Gaussian RBF
kernel and choose To and the bandwidths of and using the procedure in Appendix H22
We use
fast approximation method to optimize w in F+(w) (w) and F (w) as shown Appendix D Once is
found, we evaluate the bound in Eq. (16) exactly to ensure that the theoretical guarantee holds.
Baseline Algorithms We compare our method with four existing baselines, including the IS-based non-asymptotic bound using empirical Bernstein inequality by Thomas al. (2015b), the IS-based bootstrap bound of Thomas (2013), the bootstrap bound based on fitted Q evaluation (FQE) by Kostrikov Nachum (2020). and the bound in Feng al. (2020) which is equivalent to the primal bound in (8) but with looser concentration inequality (they e., -(/4) threshold).
Results Figure [ shows method obtains much tighter bounds than Feng et al. (222)). which because we use a much tighter concentration inequality, even the dual bound that we use can be slightly looser than the primal bound used in [eng et al. (2020). Our method is also more computationally efficient than that of Feng et al. 2020) because the dual bound can be tightened
8

---

Published as a conference paper at ICLR 2021
15 (Thomas et el,2015b)
(Bootstrap, Thomaas(2155)
BONDIC (Ours)
KBL [Feng et al,2020)
FQE (Bootstrap. Kostrikov and Nachom((2000)
KooesstrapKKosttkoo
5.0
10
Policy Reward
2
2.5
0-
0.0
-25
-5
10
500
10000 Number of Transitions, X
1000
5000
500
1000
5000
10000
1000 5000 10000
Number of Transitions,
Number of Transitions,
(a) Pendulum
(b) CartPole
(c) Type diabetes
Figure 2: Results different environments when use significance level of 6 0.1. The colored bars represent the confidence intervals of different methods (averaged over 50 random trials); the black crror bar represents the stand derivation of the end points of the intervals over the 50 random trials.
approximately while the primal bound requires to solve global optimization problem. Figure (b) shows that we provide increasingly tight bounds as the data size n increases, and the length of the interval decays with an O(n 112) rate approximately. Figure Ic) shows that when we increase the significance level 8, our bounds become tighter while still capturing the ground truth. Figure (d) shows the percentage times that the interval fails to capture the true value in a total of 100 random trials (denoted as as we vary 6. We can see that å remains close to zero even when is large, suggesting that bound is very conservative. Part of the reason is that the bound is constructed by considering the worse case and we used a conservative choice of the radius re and coefficient Cqr.k k in Eq. 13 (See Appendix (..2).
In Figure we compare different algorithms on more examples with 5 = 0.1. We can again see that method provides tight and conservative interval that always captures the true value. Although FQE (Bootstrap) yields tighter intervals than our method, it fail to capture the ground truth much more often than the promised 8 0.1 (e.g., it fails all the random trials in Figure (a)).
We conduct more ablation studies on different hyper-parameter and data collecting procedure. See Appendix H.2 and H.3 for more details.
CONCLUSION
develop a dual approach to construct high confidence bounds for off off-policy evaluation with an improved rate over over et al. (2020). Our method can handle dependent data, and does not require global optimization get valid bound. Empirical results demonstrate that our bounds is tight and valid compared with range of existing baseline. Future directions include leveraging our bounds for policy optimization and safe exploration.
REFERENCES
Sylvain Arlot, Gilles Blanchard, Etienne Roquain, et al. Some nonasymptotic results on resampling in high dimension, confidence regions. The Annals of Statistics, 38(1):51-82, 2010.
Kavosh Asadi, Evan Cater, Dipendra Misra, and Michael L Littman. Equivalence between wasserstein and value-aware loss for model-based reinforcement learning. arXiv preprint 1rXiv:1806.01265. 2018.
Marc G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. International Conference on Machine Learning, pp. 458, 2017.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv: 2016.

---

Published as a conference paper at ICLR 2021
Bo Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvári, and Dale Schuurmans. Coindice: Off-policy confidence interval estimation. In Advances in Neural Information Processing Systems, 2020.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off- off-policy evaluation with linear function approximation. In International Conference on Machine Learning, 2020.
Yaakov Engel, Shie Mannor, and Ron Meir. Reinforcement learning with Gaussian processes. In Proceedings of the 22nd international conference on Machine learning, pp. 201-208, 2005,
Yihao Feng, Lihong Li, and Qiang Liu, A kernel loss for solving the Bellman equation. In Advances in Neural Information Processing Systems, pp. 15456-15467,2011 2019.
Yihao Feng, Tongzheng Ren, Ziyang Tang, and Qiang Liu, Accountable off-policy evaluation with kemel Bellman statistics. In International Conference on Machine Learning, 2020.
Raphael Fonteneau, Susan A. Murphy, Louis Wehenkel, and Damien Ernst. Batch mode reinforcement learning based on the synthesis of artificial trajectories. Annals of Operations Research, 208(1): 383 336.416,22 2013.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian reinforcement learning: A survey. arXiv preprint 1rXiv:1609.044.00 2016a.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian reinforcement learning: A survey. arXiv preprint arXiv: arXiv:1609.0444 1609.0446, 2016b.
Josiah P Hanna, Peter Stone, and Scott Niekum. Bootstrapping with models: Confidence intervals for off-policy evaluation. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Botao Hao, Yaqi Duan, Hao Lu, Csaba Szepesvári, Mengdi Wang. et al. Bootstrapping statistical inference for off off-policy evaluation. arXiv preprint wxXiv:2102003607 2021.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
Nan Jiang and Jiawei Huang. Minimax confidence interval for off off-policy evaluation and policy optimization. In Advances in Neural Information Processing Systems, 2020.
Nan Jiang and Lihong Li. Doubly robust off-policy evaluation for reinforcement learning. In Proceedings of the 23rd International Conference on Machine Learning, pp. 652-661, 2016.
Iyya Kostrikov and Ofir Nachum. Statistical bootstrapping for uncertainty estimation in off-policy evaluation. arXiv preprint arXiv:2007.13609 2020.
Soumendra Nath Lahiri. Resampling methods for dependent data. Springer Science & Business Media, 2013.
Nevena Lazic, Dong Yin, Mehrdad Farajtabar, Nir Levine, Dilan Gorur, Chris Harris, and Dale Schuurmans. A maximum -entropy approach to off-pooicy evaluation in average-reward MDPs. In Advances in Neural Information Processing Systems, 2020.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5356- 5366, 2018a.
Yao Liu, Omer Gottesman, Aniruddh Raghu, Matthieu Komorowski, Aldo Faisal, Finale Doshi- Velez, and Emma Brunskill. Representation balancing MDPs for off-policy policy evaluation. In Advances in Neural Information Processing Systems 31 (NeurIPS), pp. 2649-2658, 2018b.
Yao Liu, Pierre-Luc Bacon, and Emma Brunskill. Understanding the curse horizon in off- policy evaluation via conditional importance sampling. In International Conference Machine Learning, 2020.
Ali Mousavi, Lihong Li, Qiang Liu, and Denny Zhou. Black-box off oof-co estimation for infinite- horizon reinforcement learning. In International Conference on Learning Representations, 2020.
10

---

Published as a conference paper at ICLR 2021
Susan A. Murphy, Mark van der Laan, and James M. Robins. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96(456):1410-1433 1423, 2001.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Bchavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pp- 2318-2328, 2019a.
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02000 2019b.
Yurii Nesterov, Introductory lectures on convex optimization: A basic course, volume 87. Springer
Science & Business Media, 2013.
Daniel Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods. Electron. J. Probab, 1037 2015.
losif Pinelis. An approach to inequalities for the distributions of infiniteddimensional martingales. In Probability in Banach Spaces, Proceedings of the Eighth International Conference, pp. 128-134. Springer, 1992.
Doina Precup. Eligibility traces for off- policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 2000.
Doina Precup. Temporal abstraction in reinforcement learning. ProQuest Dissertations and Theses, 2001.
Doina Precup, Richard S. Sutton, and Satinder P. Singh. Eligibility traces for off-policy policy evaluation. In Proceedings of the 17th International Conference Machine Learning, pp. 759- 766, 2000.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability Theory and Related Fields, 161(1-2):111-1) 2015.
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators, Journal of Machine Learning Research, I 11(,), 2010.
Bernhard Scholkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. Adaptive Computation and Machine Learning series, 2018.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06777 2017.
Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions. In Algorithmic learning theory, pp. 13-31. Springer, 2007.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, March 1998. ISBN 0-260- 19398-1.
Ziyang Tang, Yihao Feng, Lihong Li. Dengyong Zhou, and Qiang Liu. Doubly robust bias reduction in infinite horizon off off-policy estimation. In International Conference on Learning Representations (ICLR), 2020a.
Ziyang Tang, Yihao Feng, Na Zhang, Jian Peng, and Qiang Liu. Off-policy interval estimation with lipschitz value iteration. In Advances in Neural Information Processing Systems, 2020b.
Philip S Thomas. Safe reinforcement learning. PhD thesis, University of Massachusetts, 2015.
Philip S. Thomas and Emma Brunskill. Data-efficient off off-policy policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2139- 2148, 2016.
11

---

Published as a conference paper at ICLR 2021
Philip S. Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High confidence policy improvement. In Proceedings of the 32nd International Conference on Machine Learning, pP- 2380-2388, 2015a.
Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off-policy evaluation. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015b.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q- q-function learning for off-policy evaluation. Proceedings of the 37th International Conference on Machine Learning. 2020.
Junfeng Wen, Bo Dai, Lihong Li, and Dale Schuurmans. Batch stationary distribution estimation. In International Conference on Machine Learning, 2020.
Martha White and Adam White. Interval estimation for reinforeement-leaming algorithms in continuous-state domains. In Advances in Neural Information Processing Systems, pp. 2433- 2010.
Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. Conference on Uncertainty Artificial Intelligence (UAI), 2020.
Tengyang Xie, Yifei Ma, and Yu- Ei-Xiang Wang. Towards optimal off off-policy evaluation for rein- forcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, pp. 9668-9678, 2019.
Mengjiao Yang, Bo Dai, Ofir Nachum, George Tucker, and Dale Schuurmans. Offline policy selection under uncertainty. arXiv preprint arXiv:2012.06919, 2020a.
Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized Lagrangian. In Advances in Neural Information Processing Systems, 2020b.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforce- ment learning. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTA7'), 2020.
Ming Yin, Yu Bai, and Yu- Yu-Xiang Wang. Near optimal provable uniform convergence in off-policy evaluation for reinforcement learning, arXiv preprint arXiv:2007.03766) 2020.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. International Conference on Learning Representations, 2020a.
Shangtong Zhang, Bo Liu, and Shimon Whiteson. Gradientdice: Rethinking generalized offline
estimation of stationary values. In International Conference Machine Learning. 2020b.
12

---

Published as a conference paper at ICLR 2021
A PROOF OF THE DUAL BOUND IN THEOREM 4.2
Proof. Introducing Lagrange multiplier, the bound in (8) is equivalent to
Jew max min dE@ A20
max NeW n
(xx, Rii, 1o)---a- -n
max min min ge@ X20 NEW
ED..olul
-
h (2r Rig En
71
n Σ
max min DEQ wEW.
ED.
w(x, Rq( ui) + en Iwllwo
where we use Xh(x), such that À is replaced by |Wwlw. Define
M(q, wi D.) = ED, Bbo.olal [g] Σ Ru, vi + en 1ell..
11b ADD, z) en wwllw
Then have
max Míg, w; Dn) = (r] + max A(D; q) + en Wwlw.. qeQ
gE@
= b + Tolw; D,)) + en Wwllw.
= (w).
Therefore,
j max min M(g, w; D,) TEo wEW,
S min max M(g, wa D,)
wEW, rE
min weW, (w).
The lower bound follows analogously. The strong duality holds when the Slater's condition is satisfied (Nesterov 2013), which amounts to saying that the primal problem in 8 is convex and strictly teasible; this requires that Q convex and there exists at least one solution q E Q that satisfy that constraint strictly, that is, Lw(g; D,) < exi note that the objective function Q is linear on and the constraint function Lw(g D,) is always convex g (since it is the sup set of linear functions on q following
B PROOF OF CONCENTRATION BOUND IN THEOREM 4.1
Our proof require the following Hoeffding inequality on Hilbert spaces by Pinelis (Theorem 3, 1992): see also Section 2.4 of Rosasco et al. (2010).
Let be a Hilbert space and { is a Martingale sequence in H that satisfies sup; [ n almost surely. We have for any > 0.
Lemma B.1. (Theorem 3, Pinelis 1992)
nc²
Pr
fo
2 E
2exp
n
20
Therefore, with probability at least 8, we have
foll 5
20 log(2/))
13

---

Published as a conference paper at ICLR 2021
Lemma B.2. Let ((xxx)) be positive definite kernel whose RKHS is Hk. Define
f((-) = Rg(2,, (2(22,9))(z,,
(2,,((2)))(sss)))) )).
Assume Assumption 2. holds, then { is a Martingale difference sequence in Hy w.r.l. Tei= = (z 83 Bj)jcs U (z)). That is, E [f (-) T<al = 0. In addition.
1
1 n
Σ
Rg(zi, R (z)) (Rq(zz,))) Reg(xz)))
==1
and [lfallze S c. Vi I.
Proof of Theurem 4.7 Following Lemma B.1 and Lemma B.2, since (i) is Martingale differ- ence sequence in HR with [l Gg.A almost surely, we have with probability at least 6
2c & log (2/6)
Rg( mi Rx)())) k((r)))))) zny) (Rq(1z, R.n(las))
xj=1
712
Using Lemma B.3 below, we have
Lx(g; D.)) Licls D.) -
20 k log(2/0)
ft
This completes the proof.
Lemma B.3. Assume kio,, x') ) is a positive definite kernel. We have
Txc(y D..)- Tic(: Dm)) 2
n
R vs) - RTq((a)) M1) (Rg(os, v.) RT((1;))
1==1
Proof. Define
1 a
n s(.) Σ 7
g(-)
Σ
(ikkm,))(((.))))))
R (<xx)))((
n
Then we have
|
Rq(a, 25,
Lx(g; D.))
H.
n²
1j=1
R R. Lie(:; Bn),
n²
1f=1
ll@
g g
1
Σ
Rq((2, v:) Re((2s)) 25)) (Rq(25, Uz) - Rxg(2;))
n
11=1
The result then follows the triangle inequality ||l@| 11llmnl S l1@ - =9l
B. CALCULATION OF Cg...k
The practical calculation of the coefficient Cy. & the concentration inequality was discussed in Feng et al. (2020), which we include here for completeness.
Lemma B.4. (Feng et al. (020) Lemma 3. Assume the reward function and kernel function is bounded with sup,, [r()] Tmax and sup (6(x22)) & Kmaxs we have:
4 maax 2
max
sup zEX
71-
In practice, we get access to K Kmax from the kernel function that we choose (c.g., Kmax for RBF kernels), and Fmax from the knowledge the environment.
14

---

Published as a conference paper at ICLR 2021
C MORE ON THE TIGHTNESS OF THE CONFIDENCE INTERVAL
The benefit of having both upper and lower bounds that we can empirically access the tightness of the bound by checking the length of the interval [Fa (w_), ), o (w))]. However, from the theoretical perspective, it is desirable to know priori that the length of the interval will decrease with fast rate
as the data size increases. We now show that this is the case if Wo is chosen to be sufficiently rich so that it includes w E W. such that D ~ D
Theorem C.I. Assume W. is sufficiently rich to include a "good" wn in Wo with D Dr in that
D (Bg(z;z'.r) -ED. ED [Rq(; x' r)) na
sup qc@
(19)
where e and a are two positive coefficients. Then we have
max fJew Jz, Jr 4-JJew
Jāw] s no + En |w'
Assumption (99) holds if D, is collected following a Markov chain with certain strong mixing condition and weakly converges to some limit discussion Dx whose support is X, for which we can define w (x) = D2 (2) (1)). In this case, if Q is finite ball in RKHS, then we can achieve (19)
with a 1/2,, and yields the overall bound of rate O(n-1/2), For more general function classes, a depends on the martingale Rademacher complexity of function set RQ = [Rq(æ, y): q E Q)
Rakhlin al. (2015). In empirical reults, observe that the gap of the practically constructed bounds tend to follow the On 1/2) rate.
Proof. Note that
Jx E., = ED., [r].
and
Tolw; D.) = sup
{ Ro (Ta(x') [(x)] - ED, (10(=a)=((x))) a(xx)]]
=E@
Because w'
W, have
Wi.e - Jx S (w" J
-Bo,!1 [r] ED, [r] Ie(wni Dm) + on www
sup { Eo: w) ED, [ } en Iw r
e lww.
n
The case of lower bound follows similarly.
D OPTIMIZATION ON W.
Consider the optimization of w in W.
20g & log(2/8)
(+)
rww(x;) To(w; B.)) w|llww,
(20)
Assume W, is the RKHS of kernel k(x,, .), that is, W, = He. By the finite representer theorem of RKHS (Smola et al. 2007). the optimization of in RKHS H4 can reduced to finite dimensional optimization problem. Specifically, the optimal solution of (20) can be written into a form of w(x) Σr - k(x, 22)a with |Woliz Ei k(z,, 2aya, for some vector [a.] e R
Write K = [k(=,,,;)] 2,),, and [n.]a_. The optimization of reduces finite dimensional optimization on ac
L Ka + lo(K; D.)) vakay oER" "
20 & log log(2/0)
min
71
15

---

(-) with averages over small nini-batches; this would Published as a conference paper at ICLR 2021
where
1 =TTq) Ka ED. [g] +
10 (Kx;; Dn) max sE
and Tg = [tq()t) - q( When Q is RKHS, we can calculate (o(K;; Dx)) using (2) in section F
This computation can be still expensive when n is large. Fortunately, our confidence bound holds for any w; better w only gives tighter bounds, but it is not necessary to find the global optimal w. Therefore, one can use any approximation algorithm to find w, which provides a trade-off of tightness and computational cost. We discuss two methods:
1) Approximating a The length of a can be too large when is large. To address this, we assume a; = g 0). where g is any parametric function (such neural network) with parameter 0 which can be much lower dimensional than a. We can then optimize @ with stochastic gradient descent, by approximating all the data averaging n >>=
introduce biases in gradient estimation, but it is not an issue when the goal is only to get reasonable approximation.
2) Replacing kernel & Assume the kernel k yields random feature expansion: k(z,ā) Eg [0(.. 3)o(z, 3)], where 6(x,3) B) is a feature map with parameter 3 and x distribution of B. We draw {Be 1 i.d. from 9T, where m is taken to be much smaller than n. We replace & with m Em Φ(1, (i),B,)), B,) and Hy with Hi. That is, we consider to solve
k(,,,)= = 1
[w( = -= 1 n
2c y & log (2/0)
jo.w min WE
Σ ras + low; D.) + |wllaa V
is known that any function w in Hgg can be represented as w(x) = m E. wrp(z, B.), for some |w,]m= E Rm and satisfies || 1 E wa.. In this way, the problem reduces optimizing an mn-dimensional vector w, which can be solved by standard convex optimization techniques.
E CONCENTRATION INEQUALITIES OF GENERAL FUNCTIONAL BELLMAN LOSSES
When K" a general function set, one can still obtain a general concentration bound using Rader- macher complexity. Define Rg W := {h(x,y) Rq(x, ())()): w W}. Using the standard derivation in Radermacher complexity theory in conjunction with Martingale theory (Rakhlin et al. 2015). have
Rg((s, vi) - (wx < 2Rd W) + /
2c, log(2/0)
sup NEW
where Rad e K)) is the sequential Radermacher complexity defined in Rakhlin et al. 2015). A triangle inequality yields
Lx(q: D..) - Lx(g; D sup WEW
Rg vi) - R. -Rng(xx))((x)))
n
Therefore,
Lw(g: Dm)) Twlg: D..) & Rad o W) 2c, log(2/8)
(21)
n
where W. supwew supp.. (Rq(z,)) 2=)( When W equals the unit ball IC of the RKHS related to kernel k, we have C, = Cg and hence this bound is strictly worse than the bound in Theorem 4.1
16

---

Published as a conference paper at ICLR 2021
F CLOSED FORM OF Iolw; DR)) WHEN Q IS RKHS
Similar to Lx:(;; Da), when Q is taken to be the unit ball R of the RKHS a positive definite kernel k(r, F), can be expressed into a bilinear closed form shown in Mousavi et al. 20200:
Lo(w; D,)² = A - 2B + C.
(22)
where
A (a,,a) x [k(x,, B)] E (0,a) D
B (x,))
were Txf(x) = (((()) f(x); in TeT F), we apply T and Th sequential order by treating i as function of and then of x..
G MORE ON THE ORACLE BOUND AND ITS DUAL FORM
The oracle bound (18) provides another starting point for deriving optimization-bant confidence bounds. We derive its due form here. Using Lagrangian multiplier, the optimization in (8 can be rewritten into
o. = max min M(q, w; D.).
(23)
where M. w; Dm)) ED. [a] - 1 w(xx) (Rq(zs,)) Ry (1 21))
where ws serves the Lagrangian multiplier. By the weak duality, we have [e)((w) (w) = o [r] - Loww D.,) + R(ws, gr). Vw.
J2 S F
known
unknown
and
R(w, (x)
Σ wla (a (1.)
The derivation follows similarly for the lower bound. So for any E Wo. we have 1 Jo.a S (e..(()) (w), (w))
Here the first two terms of Prt (w) can be empirically estimated (it is the same as the first two terms of (I6)), but the third term R(w;, qx)) depends on the unknown gs and hence need to be further upper bounded.
Our method can viewed as constraining w in W, which is assumed to the unit ball Wo, and applying worst case bound:
(w)
= E [r] + Io(w; D,) + R(w, gx),
Vw E W.
< oy [r] + To(u; D.)) + |wll,, sup R(h, gx), Vo E W. neW
s Eo [r] + Io(w; D.)) + |wlll.. Lw(gx, Dn), Vi e W.
w.p116
B [r] + Lo(w; D.))) + ||lllw.
Yo W.
(w).
where the last step applies the high probability bound that Pr(Lw(gn: 5 2 derivation the lower bound counterpart gives
Similar
([r,,(w), (w) c (w(w), (((W) 2 1-6.
Therefore, our confidence bound [w)(w), (+(W)) is - confidence outer bound of the oracle bound بم... Jt,J1 (w), [w)(
17

---

Published as a conference paper at ICLR 2021
Introducing Q is necessarily Our method does not require any independence assumption between the transition pairs, the trade-off is that that we have to assume that On falls into a function set Q that imposes certain smoothness assumption. This is necessary because the data only provide information regarding (+ on a finite number of points, and fr can be arbitrarily non-smooth outside of the data points, and hence reasonable upper/llwer bound be obtained without any smoothness condition that extend the information on the data points to other points in the domain.
Proposition G.1. Unless PIenDr.ols & (( = O. for any u R. there exists a function q: S A + IR such that
ED [g] u, Rq(a,, Ui) Rq (Ii vi), Vi I....,n.
Proof. Let Quull be the set of functions that zero {8:: 8 s that is,
Suull {g: S x A- g(s,a) = O, vs E & a A}.
Then we have
R (fm (yx
+ (x), 3/) R. yi);
Vi
and
ED.. 1xx + + = ED. pla00 + ED. [g] = Jn + ED. l9]. Taking g(),a) 2I1(s $ {s;, (/))) where is any real number. Then have
DD 10x g] Jr + =Pr,,DD, (s & {
Because Pra-De,o (s $ {si, 41)=1)) + O, we can take to be arbitrary value to make ED, o (gx + g] to take arbitrary value.
18

---

Published as a conference paper at ICLR 2021
log, 1o (interval length)
2
100
Reward
scale=1
*
scale=10
scale=100
-2
10-1
102
10a
10
10a
10a
10*
(a) Number of transitions, 7
(b) Number of transitions n
Figure 3: Ablation study on the radius TO the function class Q. The default collecting procedure
uses horizon length of H 50. The discounted factor is y 0.95 by default.
H ABLATION STUDY AND EXPERIMENTAL DETAILS
H.1 EXPERIMENTAL DETAILS
Environments and Dataset Construction We test our method on three environments: Inverted- Pendulum and CartPole from OpenAl Gym (Brockman et al. 2016), and a Type-1 Diabetes medical treatment simulator. For Inverted-Pendulum we discretize the action space be {-1, - 0.3, 0.2, 0.2, 1}. The action space of CartPole and the medical treatment simulator both discrete.
Policy Construction We follow similar setup Feng (2020) to construct behavior and target policies. For all of the environments, we constraint our policy class to be softmax policy and use PPO (Schulman al. 2017) to train good policy æ,, and use different temperatures of the softmax policy to construct the target and behavior policies (we set the temperature = 0.1 for target policy and r to get the behavior policy, and in this way the target policy is more deterministic than the behavior policy). We consider other choices of behavior policies in Section H.3
For horizon lengths, We fix 7 = 0.95 and set horizon length H 50 for Н 100 for CartPole, and H 50 for Diabetes simulator.
Throughout the experiment, always set W = K., unit ball of RKHS with kernel k(.-). -. We set Q = roK, the zero-centered ball of radius ro in RKHS with kernel k).,).. ). We take both & and i to be Gaussian RBF kernel. The bandwidth of k and & are selected to make sure the function Bellman loss not large on validation set. The radius is selected to be sufficiently large to ensure that q- is included in Q. To ensure a sufficiently large radius, we use the data approximate a so that its functional Bellman loss small than en Then we set re = 10 |lâl We optimize w using the random feature approximation method described in Appendix D Once W4 and w are found, we evaluate the bound in Eq. (16) exactly, to ensure the theoretical guarantee holds.
Algorithm Settings We test the bound in Eq. 16
H.2 SENSITIVITY
SEPPER-ARRAMTTES
We investigate the sensitivity of our algorithm to the choice of mainly depends on how we choose our function class Q and W.
The parrret
Radius of Q Recall that we choose Q to ball in RKHS with radius ro, that is,
Q = r (res KE
where K the unit ball of the RKHS with kernel ic Ideally, we want to ensure that rg 2 11g.lle so
that q. E Q.
19

---

H.3 SENSITIVITY TO THE DATA COLLECTION PROCEDURE Published as a conference paper at ICLR 2021
2.0
Interval length
2
1.5
-
hg 0.1
Reward
11 0.5
-
1.0
3y 0.7
-+
N1 1.0
0.5
hg 5.0
-2-
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
Temperature
Bandwidth of W.
(a) Varying temperature
(h) Varying the bandwidth of kernels in W. and Q.
Figure 4: Ablation studies on Inverted-Pendulume
change the temperature the behavior policies in (a).
and change the bandwidth of the kernel & of W. and the kemel ie of Q (denoted by hg in (b)).
Since it is hard to analyze the behavior of the algorithm when q. is unknown, we consider synthetic environment where the true q. is known. This done by explicitly specifying a inside K and then infer the corresponding deterministic reward function r(æ: by inverting the Bellman equation:
r(æ) = (x)) PP (H)))ll
Here is deterministic function, instead of random variable, with an abuse of notation. In this way, we can get access to the true RKHS norm of q.:
p = 19-lle
For simplicity, we set both the state space S and action space A to be IR and set a Gaussian policy (als) exp(f(s, a)/T), where is a positive temperature parameter. We set 0.1 target policy and = as behavior policy.
ssows the results tightness of the bound is affected significantly by the radius when the number n of samples is very small. However, the number n of samples grow (e.g., n 2 2 10 in our experiment), the length of the bounds become less sensitive to the changing of the predefined norm of Q.
set re be p", 10p" and 100p", respectively. We see that the
Similarity Between Behavior Policy and Target Policy We study the performance of changing temperature of the behavior policy. We test on Penduuuum environment previous described. Not surprisingly, we can see that the closer the behavior policy to the target policy (with temperature 0.1), the tighter our confidence interval will be, which is observed in Figure a).
Bandwidth of RBF kernels We study the results as we change the bandwidth in kernel and for W and Q. respectively. Figure 4b) shows the length of the confidence interval when different bandwidth pairs in the Inverted-Pendulun environment. We can see that we get relatively tight confidence bounds long as bandwidth of & in [0.1, 0.5), the bandwidth of k in [0.5,3) 3))
the bandwidth in reasonable region (e.g., we set the
We investigate the sensitivity of our method we use different behavior policies to collect the dataset
D,
Varying Behavior Policies We study the effect of using different behavior policies. We consider the following cases:
1. Data is collected from a single behavior policy of form T. = au + (1 - a) where и is the target policy and is another policy. We construct и and mo to be Gaussian policies of form (aass) x exp(f(e (s) with different temperature т, where temperature for target policy is 0.1 and temperature for To is 1.
20

---

Published as a conference paper at ICLR 2021
log t0 (interval length)
-0.35
-1050
-0.5
* 100
-0.40
-10
0=066
000
-1.00
--- n=200
-6- n=400
-0.50
-1125
n-600
-15
dm02
ne 1000
0.0
-2.0
multi-poliie
-0.60
-1.175
10a
mumber of transitions,
Trajectory length T
Trajectory length
(a) Varying fixed 7 0.95
(h) Varying n, T, fixed = 0.95 (c)Varying n, o, fixed 0.99
Figure 5: Ablation studies on the data collection procedure, as we (a) change the behavior policies, and (b)-(c)
change the trajectory lengths. The other settings the same that Figure 3
2. The dataset D the combination of the data collected from multiple behavior policies of form Ta defined as above, with a E {0.00 0.2, 0.4, 0.6, 0.8).
We show in Figure 5)a) that the length of the confidence intervals by our method as we vary the number of transition pairs and the mixture rate We can that the length of the interval decays with the sample size for all mixture rate a. Larger a yields better performance because the behavior policies closer to the target policy.
Varying Trajectory Length T in D As we collect D,,, we can either have a small number of long trajectories, or a larger number of short trajectories. In FigureB(tb-(ee we vary the length T of the trajectories collect D,,, while fixing the total number of transition pairs. In this way, the number of trajectories in each D, would be n/T. We can that the trajectory length does not impact the results significantly, especially when the length is reasonably large (e.g.. T 2 20).
21

---

Published as a conference paper at ICLR 2021
1 MORE RELATED WORKS
We give a more detailed overview of different approaches for uncertainty estimation in OPE.
Sinite-Horizon Importance Sampling (IS) Assume the data is collected by rolling out a known behavior policy To up to trajectory length T. then we estimate the finite horizon reward by changing Ex to TE [Ex.P[]] with importance sampling(e.g) Precup et al. 2000, Precup 2001 Thomas al.) 20155a b). Taking the trajectory-wiss importance sampling as example, assume collect set of independent trajectories T; {s), oi. rr) .,..., up to trajectory length T by unrolling a known behavior policy To- When T is large, we can estimate J. by a weighted averaging:
j
m Σ (T.))((T))) m
1
where ((T.)
T-1 {(glss)) To (a(a)))))
II
((.)) = Σ Yr
(24)
One can construct non con-ssympootic confidence bounds based on jäS using variants of concentration inequalities (Thomas) 2015 Thomas et al.] 20155). Unfortunately, a key problem with this IS estimator is that the importance weight ((::) a product of the density ratios over time, and hence tends to cause explosion in variance when the trajectory length T is large. Although improvement can be made by using per-step and ceff-normalize weights (Precup) 2001). or control variates (Jiagg & Li 2016 Thomas & Brunskill, 22166) the curse of horizon remains to be key issue to the classical ba-based estimators (Liu et al. 2018a)..
Moreover, due to the time dependency between the transition pairs inside each trajectory, the non- asymptotic concentration bounds can only be applied on the trajectory level and hence decay with the number of independent trajectories in ((1//m) rate, though m be small in practice. We could in principle apply the concentration inequalities of Markov chains (e.g.. Pa.lin 2015) to the dime-dependent transition pairs, but such inequalities require to have upper bound of certain mixing coefficient of the Markov chain, which is unknown and hard to construct empirically. Our work addresses these limitations by constructing non-asymptotic bound that decay with the number = mT of transitions pairs, while without requiring known behavior policies and independent trajectories.
Infinite-Horzon, Behavior-Agnoste OPE Our work is closely related the recent advances in horiioe- and behavior-agnoste OPE, including, for example, Liu et al. (201 8a); Feng et al. Tang al. (2020a); Mousavi al. (2000): Liu al. (2020); Yang et al. (2020b) ; Xic et al.
(2019):
(2019): Yin & Wang (2020), as well as the DICE-famil (e.g.. Nachum et al.) 2019a Val b Zhang et al.
(2020a Wen et 2020 Zhang et al. 2020b). These methods are based on either estimating the value
function, or the stationary visitation distribution, which is shown to form primal-dus relation (Tang
ct al.
2020a; Uehara et al. 2020 Jiang & Huang 2020) that we elaborate depth in Section
Besides Feng et al. (2020) which directly motivated this work, there has been recent surge of interest
in interval estimation under infinite-horizon OPE (e-g.. [iu et al. [00 Jiang Huang 2020 Duan
ct al. 2020 Dai et a 2020; Feng et al.) 2020 Tang et al. |020bb Yin al. 2020 Lazic al. 2020 For example, Dai et al. 2020) develop an asymptotic confidence bound (CoinDice) for DICE estimators with an i.i.d assumption
the off-policy data; Duan et al. (2020) provide a data dependent confidence bounds based on Fitted Q iteration (FQI) using linear function approximation when the off-policy data consists of set of independent trajectories; Jiang & Huang 2020) provide minimax method closely related to our method but do not provide analysis for data error; Tang et al. (2020b) propose fixed point algorithm for constructing deterministic intervals of the true value function when the reward and transition models are deterministic and the true value function has bounded Lipschitz norm.
Jiang
Model-Based Methods Since the model P is the only unknown variable, can construct an estimator P of P using maximum likelihood estimation other methods, and plug it into Eq. obtain plug-in estimator j = J. This yields the model-based approach to OPE (e.g., Jiang
Li 2016: Liu et al. 2018b). One can also estimate the uncertainty in J= by propagating the
uncertatinty in P (e.g.. Asadi al. 2018 Duan al. 2020), but it is hard obtain non-asymptotic
22

---

Published as a conference paper at ICLR 2021
and computationally efficient bounds unless is assumed to be simple linear models. In general, estimating the whole model P can be an unnecessarily complicated problem as an intermediate step of the possibly simpler problem of estimating J.P..
Bootstrapping, Bayes, Distributional RL As a general approach of uncertainty estimation, boot- strapping has been used in interval estimation in RL various ways (e.g.. White & White 2010 Hanna et al. 2017, Kostrikov & Nachum 2020; Hao et al., 2021). Bootstrapping is simple and highly flexible, can be applied to time-dependent data (as appeared in RL) using variants block bootstrapping methods (e.g.. Lahiri 2013) White & White 2010). However, bootstrapping typically only provides asymptotic guarantees; although non-asymptotic bounds of bootstrap exist (e.g., Arlot al. 2010), they sophistic and difficult to use in practice and would require to know the mixing condition for the dependent data. Moreover, bootstrapping is time consuming since requires to repeat the whole off- off-policy evaluation pipeline on a large number of resampled data.
Bayesian methods (e.g., Engel et al., 2005 Ghavamzadeh et al., 2016b; Yang et al., 2020a) offer another general approach to uncertainty estimation in RL, but require to approximate inference algorithms and do not come with non-asymptotic frequentist guarantees. In addition, distributional RI (e.g., [ellemare al. 2017) seeks quantify the intrinsic uncertainties inside the Markov decision process, which is orthogonal to the epistemic uncertainty that we consider in off-policy evaluation.
23


Reviews:
[{"review_id": "WAVAlCI27ib", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 work constructs non-asymptotic confidence intervals for off-policy evaluation. This is achieved by assuming that the reward at any given time only depends on the state action pair, leveraging that assumed structure to define the difference between the empirical and estimated bellman residual operators as a Martingale difference sequence. This, in turn, then allows the authors to apply a Hoeffding-like concentration inequality which applies to Hilbert spaces. The authors then provide a derivation of the confidence bounds by considering the divergence between policies. The work improves on the rate of prior work from $O(n^{-\\frac{1}{4}})$ to $O(n^{-\\frac{1}{2}})$ and allows for estimation without the need of global optimality via the dual formulation, both of which are very nice additions to the literature. Experimental evaluation backs up the authors’ claims, showing very strong performance with respect to prior art. \n\n\nI found this paper to be very well written and presented, with impressively thorough theoretical results and good empirical validation. \nA couple of minor questions:\n\n(1) Performance of the proposed method when the functions don’t lie in an RKHS. It appears that the formulation in appendix E provides a bound which uses Rademacher complexity and doesn’t rely on an RKHS. Can the authors provide intuition around how much worse we would expect this to be in practice? \n\n(2) Proposition G.1 makes a case for the necessity of assuming a smoothness condition in the absence of an independence between transition pairs. Under a milder condition on transition pair independence, e.g. a mixing condition, are similar bounds to those presented in the current work attainable?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "V_FdNLfYuM-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "**General overview**\nThe paper studies an off-policy evaluation (OPE) problem for Markov decision processes (MDPs). It suggests an optimization-based method that can construct a non-asymptotic confidence interval, for a given confidence level, for the value function of a policy starting from a fixed initial distribution. The paper builds on the works of Feng et al. (2019, 2020); the main advantages of the current work with respect to the previous methods are that the suggested approach guarantees a faster convergence rate, it does not require full independence between transition pairs, and it does not need the global optimal solution of the underlying optimization problem, in order to construct guaranteed confidence intervals. The authors present some theoretical results about the construction, including a discussion on the special case of using RKHS approaches, and also present numerical experiments on benchmark problems, such as the inverted-pendulum, cartpole and type-1 diabetes.\n\n**Strengths of the paper**\n-- In general, constructing confidence regions for value functions of RL policies is an important problem (however, the paper only addresses a restrictive special case of this problem, see below).\n-- The presented method is a clear improvement over a recent OPE confidence interval construction with fewer conditions and better rate (for this special case of OPE).\n-- The properties of the method are analyzed theoretically, \"primal\" and \"dual\" bounds are given.\n--  Illustrative numerical experiments are also presented on benchmark RL problems. \n\n**Weaknesses of the paper**\n-- The paper is obscurely written, for example, several objects are not precisely defined. It is not clear from the description on page 2 whether the state and action spaces of the MDP are finite or they can be more general (for example, Borel spaces). If the state space is finite, then using RKHS approaches (at least theoretically) seems unnecessary. On the other hand, if the state space can be infinite, then some structural assumptions are needed, for example, about its measurability.\n-- It is also not clear how should the quantity I_Q(omega, hat{D}_n) computed in practice. \n-- The precise interpretation of the theoretical results, such as Theorem 4.2, is not obvious, either.\n-- A major drawback of this work is that it only considers the OPE problem from a fixed, known initial distribution of the states. This is no more general than solving the problem for only one particular starting state. A much more interesting problem would be to have a confidence region for the entire value function, under some structural assumptions on the problem.\n-- The claim in the \"Experiments\" part that \"Our method is safe (always captures the true value) and tight [...], while the other methods are either too lose or often fail to capture the ground truth\" is dubious, as the goal (see also on page 2) is not to \"always\" capture the true value, but to capture it *with a given probability*. Also, increasing this probability will make the resulting interval less tight. Mathematically, the Type I and II errors are traded off against each other.\n\n**Minor comments**\n-- Some more explanations and motivations would be needed for the concept of \"functional\" Bellman loss.\n-- In the sentence below equation (8) \"sup\" and \"inf\" should be used instead of \"min\" and \"max\" (or some argument should be given that the maximum and minimum can be actually obtained).\n-- It would be better to cite the 2018 extended 2nd edition of Sutton and Barto's classical RL book, instead of its 1st edition published in 1998.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7QoGg0wLa3Q", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 proposes an approach to construct confidence intervals using finite samples for off-policy evaluation. The paper improves the bound of a previous paper from $O(n^{-1/4})$ to $O(n^{-1/2})$ and avoids solving global optimum by introducing the dual. It is also noted that the results do not only apply to independent data. The authors further show the advantage of their method as compared to existing baselines in simulations, where their approach demonstrates good coverage and tight bound. The paper is well written. \n\nI have some comments/thoughts as below:\n- how would point estimation of the policy value be derived using such an approach? In many cases, it's also desirable to give a point estimation so that we can compute mse , etc.\n- it may be worth mentioning the findings (or some intuition) of the ablation study in Appendix H in the main body to be more educational, such as how the overlap between behavior policy and target policy influences the results.  \n\nPlease address and clarify these points above. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "0EPsQrMrEjH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "The objective of this paper is to provide a method to produce tighter confidence intervals for off-policy evaluation. The paper claims to develop a new primal-dual perspective on OPE confidence intervals and a tight concentration inequality. It develops both theoretical and empirical evidence to support its claims. \n\nPrevious methods (Feng et al. 2020) estimate the high upper confidence bound on the bellman residual for q_pi given a set of data and then perform a global optimization procedure to find the largest q function with an empirical error less than the upper bound on the residual. This paper proposes to estimate instead of a confidence interval for the expected bellman error over the empirical data set for any q function. The dual approach from other OPE estimators is then leveraged to create high confidence bounds on the objective function. \n\nThis paper's strengths are that the presented method could significantly improve confidence intervals for off-policy evaluation with a moderate length horizon and when an RKHS can represent the q function. There is both theory and empirical data to gain insights into the effectiveness of the method and show it a possible solution. \n\nAlthough the method appears to be effective, I cannot yet recommend it for acceptance due to some of the unsubstantiated claims and a lack of clarity in the paper's writing. There are also some ways that the experiments should be improved. \n\nThis paper claims to produce a tight concentration inequality, but this is not proven. The claim may be a confusion of the wording and that it is intended to mean that the presented method is only a relative improvement over existing methods. Can the authors clarify the intended scope of this claim? If the claim is to be a tight concentration inequality, then a proof showing it cannot be improved is required. \n\nAdditionally, it is stated that this work is a \"substantial extension of [dual form OPE] to the non-asymptotic region, and therefore is both of theoretical and practical significance.\" However, it is unclear what problem this paper overcomes in previous methods to make this a substantial extension to the non-asymptotic region. The formulation and the use of the dual form do not appear substantial as it is currently presented because, as the authors point out, many others have proposed this form. What is the source of this substantial extension?\n\nIn the definition of c_{q,k}, the supremum over x,y is used, but it is unclear if this is over the empirical data or any possible x,y. Can the authors clarify this?\n\nNotes about experiments:\nThe results look very promising for the method, and the ablation studies in the appendix help understand some of its properties. However, there is significant room for improvement in experimental design. The main component lacking in the experiments is a demonstration of the limitations of the method. The only thing I can take away from these results is that this method worked on these problems. I do not doubt that this method is more effective than PDIS for moderate length horizons, but cannot predict when it will be useful. \n\nHorizons of length 50 and 100 were used, but the discount factor was set to 0.95, making the effective horizon only 20. I do not see why this is an effective choice for demonstrating the capabilities of the method. Furthermore, all of these environments are typically simulated with much longer horizons (at least a thousand steps for cart-pole, inverted pendulum, and the diabetes simulator). It would be helpful to see this method's capabilities in a more typical experimental setup. \n\nAnother shortcoming of the experiments is that the behavior policy is only a high-temperature version of the evaluation policy. Typically, when off-policy estimation is performed, it is not to reduce the policy's noise but evaluate a different policy altogether. Since this work makes no claims or assumptions about the policy used to generate the data, it would make sense to demonstrate that the confidence intervals are accurate and reliable when using significantly different behavior policies or multiple behavior policies. \n\n\nWriting notes:\nOverall, the paper's writing indicates that it was written for experts who already know and understand the paper's concepts. It would be more useful to the ICLR and RL communities if the paper were written for a more general audience. \n\nMinor notes: \nIn Section 2, the objective function is called the expected reward, which implies an average reward setting, but this is not the objective function's formulation. The wording is confusing here. \n\nThere is a missing reference to proof of theorem 4.2 in the appendix. \nThe term IS is used for importance sampling, but the formulation is actually per decision importance sampling (PDIS). Specifying this would add clarity to the paper. \n\nFigure 1 (c) is not described.\n\n--EDIT-- updated score to 7 after the author's response to questions and changes to the paper. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces new tighter non-asymptotic confidence intervals for off-policy evaluation, and all reviewers generally liked the results. I recommend acceptance of this paper. Some concerns of Reviewer2 and Reviewer3 are not fully addressed in your rebuttal. Please make sure to address all remaining issues.
Decision: Accept (Poster)