Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning
Authors: Aurelien Bibaut
Nathan Kallus
Maria Dimakopoulou
Antoine Chambaz
Mark van der Laan
Venue: NeurIPS 2021 Poster (2021)
Keywords: empirical risk minimization
maximal inequality
metric entropy
fast rates
policy learning
empirical process theory
adaptively collected data

Abstract: Empirical risk minimization (ERM) is the workhorse of machine learning, whether for classification and regression or for off-policy policy learning, but its model-agnostic guarantees can fail when we use adaptively collected data, such as the result of running a contextual bandit algorithm. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class and provide first-of-their-kind generalization guarantees and fast convergence rates. Our results are based on a new maximal inequality that carefully leverages the importance sampling structure to obtain rates with the good dependence on the exploration rate in the data. For regression, we provide fast rates that leverage the strong convexity of squared-error loss. For policy learning, we provide regret guarantees that close an open gap in the existing literature whenever exploration decays to zero, as is the case for bandit-collected data. An empirical investigation validates our theory.

Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning
Aurélien Bibaut Netflix abibaut@netflix.com
Nathan Kallus
Maria Dimakopoulou Netflix
Cornell University and Netflix
kallus@cornell.o edu
addimakkoooullu@@etfll... com
Antoine Chambaz
Mark van der Laan
Université de Paris
University of California, Berkeley
antoine. chambaz&u saataazuuuparii..a. fr
laan@stat berkeley. edu
Abstract
Empirical risk minimization (ERM) is the workhorse of machine learning, whether for classification and regression or for off- off-policy policy learning, but its model- agnostic guarantees can fail when we use adaptively collected data, such the result of running contextual bandit algorithm. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over hypothesis class and provide first-of-theirkiie generalization guarantees and fast convergence rates. Our results are based on a new maximal inequality that carefully leverages the importance sampling structure to obtain rates with the good dependence on the exploration rate in the data. For regression, provide fast rates that leverage the strong convexity of squared-error loss. For policy learning, we provide regret guarantees that close an open gap in the existing literature whenever exploration decays to zero, as is the case for bandit-collected data. An empirical investigation validates our theory.
1 Introduction
Adaptive experiments, wherein intervention policies are continually updated as in the case contex- tual bandit algorithms, offer benefits in learning efficiency and better outcomes for participants in the experiment. They also make collected data dependent and complicate standard machine learning approaches for model-agnostic risk minimization, such empirical risk minimization (ERM). Given a loss function and a hypothesis class, ERM seeks the hypothesis that minimizes the sample average loss. This can be used for regression, classification, and even off- off-policy policy optimization. An extensive literature has shown that, for independent data, ERM enjoys model-agnostic, best-in-class risk guarantees and even fast rates under certain convexity and/or margin assumptions [e.g. [ 6 35 among others]. However, these guarantees fail under contextull-aandit-con bandit-collected data, both because of covariate shift due to using context-depente context-dependent logging policy and because of the policy's 's data- adaptive evolution as more data are collected. straightforward and popular approach to deal with the covariate shift is importance sampling (IS) weighting. whereby we weight samples by the inverse of the policy's probability of choosing the observed action. Unfortunately. applying standard maximal inequalities for sequentially dependent data study guarantees of this leads poor dependence on these weights, and therefore incorrect rates whenever exploration is decaying and the weights diverge infinity, as happens when collecting data using contextual bandit algorithm.
In this paper, we provide a thorough theoretical analysis of IS weighted ERM (ISWERM: pronounced "ice worm") that yields the correct rates the convergence of excess risk under decaying exploration. To achieve this, we present a novel localized maximal inequality for weighted sequential empirical
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

processes (Section 2 that carefully leverages their IS structure to avoid bad dependence on the size of IS weights, compared applying standard results to an IS weighted process (Remark (
We then apply this result to obtain generic slow rates for ISWERM for both Donsker-like and non- Donsker-like entropy conditions, as well as fast rates when variance bound applies (Section ( We instantiate these results for regression (Section ! and for policy learning (Section 5), where we can express entropy conditions in terms of the hypothesis class and obtain variance bounds from convexity and margin assumptions. In particular, our results for policy learning close an open gap between existing lower and upper bounds in the literature (Remark 3). We end with an empirical investigation of ISWERM that sheds light theory (Section
1.1 Setting
We consider data consisting I" observations, Or (O)..... OT), where each observation consists of a state, action, and outcome, O, = (X,, Ar, Yi) E O = X' x A x y. The spaces A, are general measurable spaces, each endowed with base measure Ax, ÀA Ay; in particular, actions can be finite or continuous (e.g., , Ad can be counting or Lebesgue). We assume the data were generated sequentially stochastic-contetuus bandit fashion. Specifically, we assume that the distribution of Or has density D(T)) with respect to (wrt) 2 (Ax dA dy) which can be decomposed as
T
p (ōT)
II 1=1
px (at I 01,00-11 11 (ye Ie. oz);
where write 0; (3) 01: Ve), using lower case for dummy values and upper case for random variables, We define ge x)) (a x, Oz-1) so that St represents the random mm-s-measurable context-dependent policy that the agent has devised at the beginning round t, which they then proceed to employ when observing X,. Since we run the adaptive experiment, we assume that 9r is known, as it is actually computed stage of the experiment. We do not assume that Jr known.
Remark (Counterfactual interpretation). We can also interpret this data collection from a coun- terfactual perspective. At the beginning of each round, (X,, (Y)(a) : E AA}) is drawn from some stationary (i.e, time-independent) distribution P", X2, is revealed, and after acting with a non-anticipatory action A,, meaning only depends on past data, we observe Y, = (A,). This corresponds to the above with px being the marginal of X, under Pa and pr 2, a) the conditional distribution (a) given X, = T.
1.2 Importance Sampling Weighted Empirical Risk Minimization
Consider a class of hypotheses F, loss function f: F x O R. and some fixed reference ga x.), any function, for example, conditional density. As we will see in Examples I to below we will often simply use g" (a x) 1. Define the population reference risk as
R (f) = E x xpy [((S = / | (x, o, (yy I,, 2,,)g"( (a (x))do)) v.
We are interested in finding ff with low risk R' (f). We consider doing so using ISWERM, which is ERM where weight each term by the density ratio between the reference and the policy time t:
T (A,
Xe) 11:000 X₂)
fr E argmin JEF
RT(()) = T
(A,
Example 1 (Regression). Consider = R ( RR.. and ((f, (y far a))² Then if with small R' (f) is good at predicting outcomes from context and action. In particular, for any g", we have that μ1z, a) ypy (y x, a dd (y) solves μ E argmin p A R (f). And, we can write (f) R (H) xx [(f A)].
Consider the counterfactual interpretation in Remark f(X, (19 (r (a)) For example, if [A| < DC, da is the counting measure, and g" (x a) 1, then R (f) Ep.4Ep.111 (Y f(X, a) is the total counterfactual pre- diction error. Alternatively, if (a x) 1(a a²) and given some H C [X' + y) we let F == (Jn(1, a) = h(x)= h E H), then we have R(((()) Epp (E-(((((a)) ) - h(X))²), that is, the regression risk for predicting the counterfactual outcome Y(a)) from X.
1 Then R*()) = =f (E-((((()))

---

Example 2 (Classification), In the same setting as Example 1 suppose y' = (=1). Then pxx a)
2py z, a) And, if we restrict S [X A - {+1]], Tetting ((f - 2f a) leads to
(J) being misclassification rate, an unrestricted minimizer of which is sign(u((z, a)). Focusing on
misclassification of sign (f( a)) for F [X x A + RR, we can also use a ttassificationncaiiraat loss [6] such as logistic o) = lo + exp( 1aap(-yf(ee -f a))), hinge {(S xf)z)= = (1 yf a))+ etc..
Example 3 (Policy learning). Consider y - R. F C ff a). Then R2* (ʃ) /pv x, (d)dAy(v) the average outcome under a policy f. If we interpret outcomes as costs (or, negative rewards), then secking to minimize R (f) means to seek a policy with least risk (or, highest value).
x) 1 and {(f.)
())dh((epp(()dddxie = Epx x / xpy [y] is
Consider in particular the counterfactual interpretation in Remark [ with |A] c0. Consider deterministic policies: given H. C [X + Al, let F = {fx = [(((z) a) h E H}. Then we have R (fn) = Er. (()()))), that is, the average counterfactual outcome.
1.3 Related Literature
Contextual bandits. A rich literature studies how to design adaptive experiments to optimize regret, simple regret, or the chance of identifying best interventions [see [2 36 and biblioraphies therein]. Such adaptive experiments can significantly improve upon randomized trials (aka A/B tests), which is why they are seeing increased use in practice in a variety of settings, from e-commerce 533. However, while randomized trials produce iid data, adaptive experiments do not, complicating post-experiment analysis, which motivates our current study. Many stochastic contextual bandit algorithms (stochastic meaning the context and response models are stationary, as in our setting) need to tackle learning from adaptively collected data to fit regression estimates of mean reward functions, but for the most part this is based on models such as linear 7 23 37 or Hölder class [26] 47 47], rather than on doing model-aggostie risk minimization and nonparametric learning with general function classes as do here. Foster and Rakhlin [99 use generic regression models but require online oracles with guarantees for adversarial sequences of data. Simchi-Levi and Xu (50) use offline least-squares ERM but bypass the issue of adaptivity by using epochs of geometrically growing size in each of which data are collected iid. Other stochastic contextual bandit algorithms are based on direct policy learning using ERM 18
to policymaking 1 4 29 32
37
43
44
20]; by carefully designing exploration strategies, they obtain good regret rates that are even better than the minimax optimal guarantees given only the exploration rates, as we obtain (Remark B).
Inference with adaptive data. A stream of recent literature tackles how to construct confidence intervals after adaptive experiment. While standard estimators like inverse- wverse-propensity weighting (IPW) and doubly robust estimation remain unbiased under adaptive data collection, they may no longer be asymptotically normal making inference difficult. To fix this, Hadad et al. 24 use and generalize a stabilization trick originally developed by Luedtke and van der Laan (38 for a non- adaptive setting with different inferential challenges. Their stabilized estimator, however, only works for data collected by non-contextual bandits. Bibaut et al. [9] extend this to a contextual-bandie setting. Our focus is different from these: risk minimization and guarantees rather than inference.
Policy learning with adaptive data. Zhan et al. [58] study policy learning from contextual- bandit data by optimizing a doubly robust policy value estimator stabilized by deterministic lower bound on IS weights. They provide regret guarantees for this algorithm based on invoking the results of Rakhlin et al. [45). However, these guarantees do not match the algorithm-agnosie lower bound they provide whenever the lower bounds on IS weights decay to zero, as they do when data are generated bandit algorithm with an exploration
by bandit algorithm. For example, for epsilon-greet rate of e, t ビー their lower bound expected regret is (1 (1-8/2)) while their upper bound is ((T-(1/2-8)) B)). We close this gap by providing an upper bound of ( for our simpler IS weighted algorithm. See Remark 3 Our results for policy learning also extend to fast rates under margin conditions, non- Non-Donsker-like policy classes, and learning via convex surrogate losses.
IS weighted ERM. The use of IS weighting to deal with covariate shift, including when induced by a covariate- dependent policy, is standard. For estimation of causal effects from observational data this usually takes the form of inverse propensity weighting 288 The same is often used for ERM for
covariate-dependent
regression [5 22 48 and for policy learning [34 52
59 When regressions are plugged into causal
effect estimators, weighted regression with weights that depend on IS weights minimize the resulting
estimation variance over hypothesis class [3 18
30 31 49) All of these approaches however
3

---

have been studied in the independent-datte setting where historical logging policies do not depend on the same observed data available for training. guarantees under which is precisely our focus herein.
Sequential maximal inequalities. There are essentially two strands in the literature on maximal inequalities for sequential empirical processes. One expresses bounds in terms of sequential brack- eting numbers as introduced by van de Geer (55), generalizing of standard bracketing numbers. Another uses sequential covering numbers, introduced by Rakhlin et al. [46]. These are in general not comparable. Foster and Krishnamurthy (20). Zhan et al. (58] use sequential L. and Lp covering numbers, respectively, to obtain maximal inequalities. van de Geer [55] Chapter 8] gives guarantees for ERM over nonparametric classes of controlled sequential bracketing entropy. However, applying her generic result as-is IS weighted processes provides bad dependence on the exploration rate in the case of larger-than -oon-r hypothesis classes (see Remark 2). We also use sequential bracketing numbers, but we develop a new maximal inequality specially for IS weighted sequential empirical processes, where we use the special structure when truncating the chaining to avoid a bad dependence on the size of the IS weights. Equipped with our new maximal inequality, we obtain first-of-their kind guarantees for ISWERM, including fast rates that have not been before derived in adaptive settings.
2 A Maximal Inequality for IS Weighted Sequential Empirical Processes
A key building block for results is a novel maximal inequality for IS weighted sequential empirical processes. For any sequence of objects (21)(21 we introduce the shorthand F1.T to denote the sequence (xt)²= We say that a sequence of random variables Ç1:T is O -reddiidieebble if, for every t E [T] (I....,)). & is -.es-uuuurr,ble, i.e., is some function of Öt-1-
IS weighted sequential empirical processes. Let Pg denote the distribution on O X AxxAx) with density w.r.t. Ax x AY x dy given by px Xy and let us use the notation Pa Pyh(o) := (()ddl Let also define the norm ||bl|p. processes of the form Ey == { (E f E F} where, for every E F, {fr is an Öur predictable sequence of O + R functions. The IS- wS-weighted sequential empirical process induced by Ey is the F-indexed random process
(P)()))) Consider sequence of F-indexed random
T
gf (A X1))
Mf(f) = T
(s:())(O)) - (s(()) 00,11)
(A Xx))
T
(G(6))
Σ T
(5o. - Pai)
gt
Sequential bracketing entropy. For any -u:-prreiccaall sequence sequence (1:r of functions O R. we introduce the pseudonorm PT.g. (LIT) == ----TTT- ET (KGell2...)
We say that a collection of 2N 2ammany Pred-itedit sequences of O - TR. functions (A U U1,T) E [N]] is an (e, PT, )-squential bracketing of Er, if (a) for every f E F, there exists h E [N]
(k)
such that ( < {f( < vz (k) Vt E [T] and (b) for every &s [N], PT.g" (k) ( I We denote by Mij(c,Er,Pr.
the minimal cardinality of an (c, PT. )-sequential bracketing of Er.
The special case of classes of classes of deterministic functions. Consider the special case f.()) == {(f,, where == {E(f): : E F) is a class of functions where for every f E F. {(f) is deterministic O + R function. Observe that for fixed function Ç O + I. letting C. := we have that PT. (SI.T) = |<|l..g' Therefore, Ni: (e, PT. the (e, PT.g ) -sequentia bracketing number Er. reduces to Nn, E. [12.g ). the usual e-bracketing number 3 in the || lla.9* norm.
The maximal inequality. Our maximal inequality will crucially depend on the decay rate of the the IS weights, that is, the exploration rate of the adaptive data collection.
Assumption 1. There exists deterministic sequence of positive numbers (1x) such that, for any 1 2 1, l1g" /gll S 7hs almost surely. Define 7/ avg = ----"-- Yt. and y := max Tt.
For example, if the data were collected under an 6, e--reedy contextual bandit algorithm then have 7t- 6, If we have e -ー for B (0, 1) then 7/ max
0(TT²) O(I²). Note that

---

having It < oo in Assumption I does restrict us to contextual bandit algorithms that are conditionally random, such as e-greedy and Thompson sampling, and rules out algorithms with deterministic policies given the history, such as UCB.
Theorem 1. Consider Er := (fa(s) : FF as defined above. Suppose that Assumption 7 holds, and that there exists B > such that maXte(T) sup IIE: lxx S B. the special case where {x( = E(f), E1.T E ET, are deterministic functionn, we let 7T == mr Otherwise, in the general case, we let "/- :- 'T max Let r > O. Let Fry(r) ;= {s E F pr (f): S r). For any
r- E /2), and any x > 0, it holds with probability at least - 2e that
sup Mr()) /EFr(r)
YT T
V Log(11 + +iilis Er.Pr. d)de
VT
B T
log(1 + NN),,,;
+
TT T
Byrax T
Remark 2 (Leveraging IS structure). Theorem is based on a finite-depth adaptive chaining device, in which we leverage the wS-weighted structure carefully bound the size of the tip of the chains. In contrast, applying Theorem 1.13 of van de Geer (55) to the IS weighted sequential empirical process would lead suboptimal dependence on 7/. The crucial point
work with IS- WS-weighted chains of the form (g" / ((f) = (g" /9. ((E())- - w + Σ/ Σj=o (wi-/ w + v where the wi-S are upper brackets of the unweighted class E, at scales 61 > .... > eJ (we simplify here bit the chaining decomposition for ease of presentation compared with the proof). In adaptive chaining, the tip is bounded by the Ln norm of the corresponding bracket. In our case, denoting Id.f the lower bracket corresponding to u wd.,, the tip is bounded by Pg. (g" [u - - = Pg- /u - 1.11, in which we integrate out the IS ratio, thereby paying no price for it. Applying directly Theorem 8.13 of van de Geer [55] we would be working with bracketing of the IS weighted class (9.""/e))(0) (())=(():= f E F). When working with generic Ly brackets of the weighted class, the IS- wS-weighting structure is lost, and cannot do better than bounding the L1 of the tip by its L2 norm, which depends on %v. Since in sequential settings, "t generally diverges to oo, good dependence is paramount to obtaining tight, informative results. Our proof technique otherwise follows the same general outlines those of van de Geer [55] Theorem 8. 13] and van Handel [57] Theorem A.4] (or, 40 Theorem 6.8 in the iid setting). Like these, we too leverage adaptive chaining device, pioneered by Ossiander (1]
3 Applications to Guarantees for ISWERM
We now return to ISWERM and use Theorem D obtain generic guarantees for ISWERM. We will start with so-called slow rates that give generic generalization results and then present so-called fast rates that will apply in certain settings, where a so-called variance bound available. Let Si be minimizer of the population risk R² over F, that is fi E argmin JEF R²(J).
Assumption (Entropy on {(F). Define {(F) == {((f.-) : f FFF.. There exist an envelope function A O + R.. of ((F), and 0 such that, for any 0,
log (e ((F), (2..9) S
The case p 2 corresponds the Donsker case, and p 2 2 to the (possibly) non-Donsker case.
Assumption 3 (Diameters ((F)). There exist bn 0 and Po 0 such that
sur [|((f.)- (0n-))(((fi.)))) (ff Ia bollA||2.9., supjer [[(({,)) E(hi 112.00 S PollA|12..0
Theorem 2 (Slow Rates for ISWERM). Suppose Assumptions 7 10 3 hold. Then for any ō E (0, 1/2). we have that, with probability at least 8.
R (fT) inf Rf) FEF
2 ||Al|2.- X
Po
T
P0
p/2
+
(188
T
{0o" + +log(1/6)}
p< 2,
+ po V 7
log (1/))
+
bo max
{05 + +log(1/8)}
p> 2.
5

---

For 2 the bound is similar to the second case but with polylog terms; for brevity we omit the p 2 in this paper. Theorem 2 suggests that the excess risk of ISWERM converges at the rate of (7T)//) A For example, if TT O and < 2, we obtain - For 3 = 0 this matches the familiar slow rate of iid settings. However, many cases we can obtain faster rates.
ave
Assumption 4 (Variance Bound). For some E (0, 1J. we have
[Ie(,-) (lun-))-((i,--) 112 X 11A|22.0
VFEF.
|
As will see in Lemmas 2 and
ensure Assumption 4 holds for least-squares regression and for policy learning with a margin condition.
Assumption (Convexity). F is convex and l(., O) is almost surely convex.
Theorem (Fast Rates for ISWERM). Suppose Assumptions 7 1o hold with p 2. Then for any
ō E (0, 1/2), we have that, with probability at least 1 - 6,
a8 TT
2-a-po/2
DuTT max
Itpa/2
R (fr) Rd (fi) 2 |All2.g x
T
T
TT log(1/0)
ave
I
TT log (L/8)
T
T
The entropy condition. Assumption] 2 assumes an entropy bound on the loss class ((F). For many loss functions, we easily satisfy this condition by assuming an entropy condition on J itself. Assumption 6 (Entropy on F). There exists O and an envelope function F of F such that
log Ngg[e(/FF1l2. : F.
1l2.5))
Lemma (Lemma 4 in Bibaut and van der Laan [0O). Suppose that (E(:,): E O} is a set of R > R unimodal functions that equi- -qui-Lipschitz. Then Assumption 6 implies Assumption
There are many examples of F for which bracketing entropy conditions are known. The class of 3-Hölder smooth functions (meaning having derivatives of orders up to 6 supfi E Z : < B) and the b-order derivatives are (3 b)-Hööder continuous) on a compact domain in Rd has = d/3 compact domain in Rd has p 4/2 [56] Corollary 2.7.10]. The class of monotone functions on IR has
[56] Corollary 2.7.2]. The class of convex Lipschitz functions
[56] Theorem 2.7.5]. If F (o; 0) 0 E θ), {o; 0) is Lipschitz in 0, and θ C RRd is compact, then any p 0 holds [56] Theorem 2.7.11]. The class of càdlåg functions [0, 1] -> R with sectional variation norm (aka Hardy- Krause variation) no larger than M > O has envelope- scaled bracketing entropy O(c-1 (lo)(1/c)(22d) 2(d-1)) [10, so Assumption G holds with any > 1 (or, we can track the log terms). Since trees with bounded output range and finite depth fall in the class of càdlág functions with bounded sectional variation norm, decision tree classes also satisfy Assumption 6 with any p >> 1.
4 Least squares regression using ISWERM
We now instantiate ISWERM for least squares regression. Consider y =
1-I---IiMMM---- /VM VM], for some M > 0, F C [X' x A + V.. and É(S, o) = (y f(x a))² If F is convex, strongly convex losses such always yield variance bound with respect to any population risk minimizer over F (see e.g. lemma 15 in (6) Let f1 E argmin ye R² (f) be such a population risk minimizer. We present
in the lemma below properties relevant for application of theorems 2 and
Lemma 2 (Properties of the square loss.). Consider the setting of the current section. The square loss É over F x O satisfies the following variance bound:
[[((,-) - {(', (,,.,))l2,,, V12.95
- -
and the following Lispchitz property:
(e(f.o) ((f".o)) s f

---

Theorem 4 (Least squares regression). Suppose Assumption 2 holds. Suppose Assumption 6 holds for the envelope taken to be constant equal to VM, the runge of the regression functions. Then for any 8 (0, 122), we have that, with probability at least 6,
149/2
79
max log(1/6)
if 2,
R - (Fr) (F)
T
T
24
log(1/5)
DT
log(1/8
if
T
T
5 Policy Learning using ISWERM
We next instantiate ISWERM for policy learning. Consider y- [
as in Example 3 Let o) = yz a) and ga x) = so that P,- = E xxxx [7] Epx aa ((xX,))(XX,)) a)] is exactly the average outcome under a policy I (or, its negative value), where we define ulzz a) J (y x, (v).
We first give specification-agnssiie slow rates, which also close an open gap in the literature.
Theorem 5 (ISWERM Policy Learning: slow rates). Suppose Assumption 7 holds and suppose that Assumption (6 holds withe envelope constant equal to (which is the maximal range of policies). Then for any 5 E (0, 1/2), we have that, with probability at least 1 6,
log (1/0 +
max
log (1/8)
p < 2,
Rd (fr) - inf R M JEF
log( 1/5) + log(1/0) p> 2.
Remark 3 (Comparison to Zhan et al. (58)) Given a deterministic policy class (fx(2, ((((z) a)), H S [x + AA) with a Natarajan dimension, Zhan et al. (58) show a lower bound of U((T (T) on the expected regret of any policy-learning algorithms for some logging policy satisfying Assumption [ (see their Theorem 1), that is, Q(TT when 1/ () Zhan al. (58) also provide an upper bound of 0 7T for their partieular algorithm (see their Corollary 2.1), that is, O(T-1/2+0) when 7/7 O assuming that log Nir H) S cP for p < 1, where NH is the Hamming covering number, which would be implied by having Natarajan dimension. This is a potentially significant gap in the regret rate in T when exploration is diminishing,
3 > O, as is often the case with bandit-collected data. For example, for B = 1/2, this yields vanishing lower bound and a non-vanishing upper bound.
In comparison, our Theorem 5 gives the rate ((~)) -11/)) the expected regret of policy learning with ISWERM in the case of p < 2 (given by integrating the tail inequality in Theorem 5). that is, O(T-(1-9)/2) when > avz = OTT)) This matches the rate of the lower bound of Zhan et al. (58). seemingly closing the gap. While Natarajan dimension, Hamming covering entropy with p 1, and bracketing entropy with p < 2 are generally incomparable conditions (aside from the first implying the second), they all generally hold for policy classes parametrized by finite diiteeddiiniinnal parameters and tree policy classes, for which we definitely close gap. It remains an open question how to close the gap for general policy classes that only satisfy a Hamming covering entropy condition.
The gap arose from the specific technical route Zhan et al. 58 followed (not their algorithm). For the sake of exposition, give explanation of the phenomenon in non-sequential i.i.d. setting, under stationary logging policy gl, and under our own notation. The same phenomenon translates to the sequential setting. Since they use a symmetrization and covering-basee approach, they need to work with uniform covering -tpe entropies of the form supo log [c, H. L2 (Q)) for certain class H. where the supremum is over all finitery supported distributions. Their approach amounts to taking H to be the weighted loss class {(g" /g. { While for Q = Py.. it holds that Il'' /9:) ((()((()) ((T))))) p, I 71 1/2 (((()())))))) ((T'))l,, I 71 1/2 ( T'). for a general Q, the best bound is |1(" //1) (E(T) (a)))ll S 7 ( n²), where du is the Hamming distance. By contrast, when working with bracketing entropy, one only needs to control the size of brackets in terms of (2( ). that the L2 Ln-norm under the distribution of the data P... This allows to save a
'See van der Vaart and Wellner (56 Chapter 2.3] for an explanation of why uniform covering entropy is natural for bounding symmetrized Rademacher processes.
7

---

vn factor. Our results also show that simple IS weighting algorithm suffices to obtain optimal rates, and the stabilization by yi employed by Zhan al. [58], which is inspired by the stabilization employed by Hadad et al. [24]. Luedtke and van der Laan [8 for inference purposes, may not be necessary for policy learning purposes. The doubly-robust-style centering may still be beneficial in practice for reducing variance but it does not affect the rate.
Remark 4 (Comparison to (20)). Foster and Krishnamurthy (20). albeit in a slightly different setting, derive maximal inequality under sequential covering entropy that also exhibits the correct dependence on the exploration rate as ours. This shows in particular that the suboptimal dependence on the exploration rate of Zhan et al. [58] is not necessary consequence of using sequential covering entropy. Analogously to us, Foster and Krishnamurthy (0) exploit the specific IS- weigthed structure of the loss process, and work with covers of the unweighted policy class directly. Using an Loc sequential cover of the unweighted class and using Holder's 's inequality, they are able to factor out the Li norm of the IS ratios. This allows them circumvent the type of sequential cover of the weighted class that Zhan et al. [58] need, and yields optimal 7 scaling. One caveat of this approach is that the entropy integral in the corresponding bound is expressed in terms of Too sequential covering entropy, which makes it hard to obtain fast rates via localization. Indeed, while variance bounds that allow for localization in L2 norm are common, it in general much harder to obtain localization in Loo norm.
In well-specified cases, much faster rates of regret convergence are possible. We focus on finitely- many actions, |A|| < co. Define μ² (X) minae aa and fix a" (X) with μ a (X)) jx" (X).
Assumption 7 (Margin). For a constant v E [0, oo), we have for all 2 Pryx (min)e))) ((X, a) - p²(x)= S Mu) 1/v Su,
where we define 01/00- 0 and 2/1/00- for x E 1).
This type of margin condition was originally considered in the case of binary classification The condition we use is more similar that used in multi-arm contextual bandits (25 26 42 The
39
54
condition controls the density of the arm gap near zero. It generally holds with v = 1 for sufficiently well-behaved μ and continuous X and with v/ oo for discrete X [see, e.g. (2 Lemmas 4 and 5].
Lemma 3. Suppose Assumption 7 holds and minjer R (f) = Epx 1²t (X). Then Assumption holds for a = 11/v + 1) and A o - M.
Theorem 6 (ISWERM Policy Learning: fast rates), Suppose Assumptions ! 6 Iand hold with p <<> 2 and minjez R (J) = Exxx' (X). Then for any E (0, 1/2), with probability at least 5,
11r 241
Rd (fr) px n²
avg TT
17
T+0(++//3)
T
Liv
TT log (1/8)
avg
2+0
'T
max log (1/8)
T
T
Remark 5 (Classification using ISWERM). The above results can easily be rephrased for the classification analogue to the regression problem in Section where {+1} and we want classifier based on features a to minimize misclassification error. Because the policy learning problem is both of greater interest and greater generality, we focus our presentation on policy learning.
6 Empirical Study
Next, we empirically investigate various risk minimization approaches using data collected by a contextual bandit algorithm, including both ISWERM and unweighted ERM among others. We take 51 different mutli-calss classification datasets from OpenML-CCC1 8 [1] and transform each into a multi-arm contextual bandit problem (following the approach of [15 17 51). We then run an epsilon greedy algorithm for T 100000, where explore uniformly with probability 6, t 1/3 and otherwise pull the arm that maximizes an estimate of p( a) based on data so far. Details are given in Appendix F.
We then consider using this data to regress Y, on X,, A, using different methods where each observation is weighted by wy using different schemes: (1) Unweighted ERM: w, 1; (2) ISWERM:
8

---

Unweighted ERM
ISFioorWERM
SqrtISWERM
SqriiFFlorWERM
MADRINERM
MRDRFloorWERU
ca
28
08
SWERM
4
64
04
24
0.4
04
00
0.2
0.0
30
00
0.0
06
0.2
(a) LASSO outcome model with cross cross-validaton validated regularization parameter.
Unweighted ERM
iSllor WERM
SqriSSWERM
SyRUSFluorWERM
MADRWERM
MRDAFloo WERM
15WERM
0.2
07
6.0
0.0
0.0
0.0
0.0
0.0
cross-validated Ridge outcome model with cross-vaas validated regularization parameter.
Unweightad
IFFaorWERM
SqrtISWERM
SqrtisFloorWERM
MRDRWERM
MADRF FoOrFRO
1.25
1.25
1.75
1.23
1.25
1.00
1.00
1.00
15WERM
0.50
0:0
0.50
0.50
2.0
0.23
2.2
0125
0.2
0.25
0.45
0.00
0.00
0.0
0.00
5.00
0.00
(c) CART outcome model with unrestricted depth.
data. Each dot is one of 51 OpenML-CCI8 datasets. Lines denote #1 standard error. Dots are blue when ISWERM clearly better, red when clearly worse, and black when indistinguishable within one standard error.
Figure 1: Comparison of weighted regression run contextual-bandit-oo
wy 9: 'A, X,): (3) ISFloorWERM: we YT', wcere-inspinee by 158 we weight by the
inverse (nonrandom) floor 7: = / |A] of the propensity scores; (4) SqrUSWERM: Wi = 9:
(A,
Xt). which applics the stabilization of 24 38 to ISWERM; (5) SqrdSFIlorWERM:: w, %
1/2
(A. which are the weights used by Farajtabar et al. 18 (7) (6) MRDRWERM: w=t) xx,)
MRDRFFlOrWERM: w(l) ست which is like MRDRWERM but uses the propensity score
floors %r. With these sample weights, we run either Ridge regression, LASSO, or CART using sklearn's (cv LassoCV
or Decisi eeciissonTreeeeggeee euTreeeegresoo, each with default parameters. For Ridge and LASSO we pass as features the intercept intercept-augmented contexts {(1, (1) XT) concatenated by the product of the one-hot encoding of arms { {Ar)T with the intercept-augmennte contexts {(1, X.) For CART, use the concatenation of the contexts {X,) with the one-hot 1000 rounds using uniform exploration policy, 9" (a x:) 1/K, and record the mean-squares error (MSE) of the regression fits on this data, We repeat the whole process 64 times and report estimated average MSE and standard error in Fig.
(cv=4),
encoding of arms {Ar)²= To evaluate, we play our bandit anew for Test
Results. Figures Ia and Tb show that ISWERM clearly outperforms unweighted ERM and all other Weeighted-ERRM schemes for linear regression, with ISWERM's advantage being even more pronounced for LASSO. Intuitively, since a linear model is misspecified, this can be attributed to ISWERM's ability to provide agnostic best-in-class risk guarantees. In contrast, for better specified model such as CART, all ERM methods perform similarly, as seen in Fig. Tc We highlight that our focus is not necessarily methodological improvements, and the aim of our experiments is to explore the implications our theory, not provide state-of-the- results. We provide additional empirical results in Appendix F2 the conclusions from which qualitatively the same.

---

7 Conclusions and Future Work
We provided trss-of-their-king guarantees for risk minimization from adaptively collected data using ISWERM. Most crucially, our guarantees provided good dependence on the size of IS weights leading to correct convergence rates when exploration diminishes with time, as happens when we collect data using contextual bandit algorithm. This made possible by for IS weighted sequential empirical processes. There are several important avenues for future work. We focused on fixed hypothesis class. One important next question is how to do effective model selection in adaptive settings. We also focused on IS weighted regression and policy learning, but recent work in the iid setting highlights the benefits of using doubly-robust-style centering 21 33 These benefits are most important to avoid rate deterioration when IS weights are estimated, while our IS weights are known, but there are still benefits in reducing the loss variance the leading constant. Therefore, exploring such methods in adaptive settings is another important next question.
maximal inequality specifically
8 Societal Impact
Our work provides guarantees for learning from adaptively collected data. While the methods (IS weighting) are standard, our novel guarantees lend credibility to the use of adaptive experiments. Adaptive experiments hold great promise for better, more efficient, and even more ethical experiments. At the same time, adaptive experiments, especially when all arms are always being explored (Yt < oo) even if at vanishing rates (7x w())). must still be subject to the same ethical guidelines classic randomized experiments regarding favorable risk-benefit ratio of any arm, informed consent, and other protections of participants. There are also several potential dangers to be aware of in supervised and policy learning generally, such as the training data possibly being unrepresentative of the population to which predictions and policies will be applied leading to potential disparities well the focus on average welfare compared to prediction error or policy value on each individual or group. These remain concerns in the adaptive setting, and while ways tackle these challenges in non-adaptive settings might be applicable adaptive ones, a rigorous study of applicability requires future work.
References
[1] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference Machine Learning, pages 1638-1646. PMLR, 2014.
[2] Susan Athey and Stefan Wager. Policy learning with observational data. Econometrica, 89(1): 133-161, 2021.
[3] Susan Athey, Sarah Baird, Julian Jamison, Craig McIntosh, Berk Özler, and Dohbit Sama. A se- quential and adaptive experiment increase the uptake of long-acting reversible contraceptives in cameroon, 2018. URL http::/pubdocss.... wor worlddbnn.... wtt.///aaaa..ooo/////o//01111110 hatdo//-ooooooo-llapaaa-eeeeeeee
on- wtt.:p/pww...ooooooooooooooooaaa
pdf
Study protocol.
[4] Eytan Bakshy, Lili Dworkin, Brian Karrer, Konstantin Kashin, Benjamin Letham, Ashwin Murthy, and Shaun Singh. Ae: A domain-agnostic platform for adaptive experimentation. In Workshop on System for MI. 2018
[5] Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics, 3394):1497-1537, 2005.
[6] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. bounds. Journal of the American Statistical Association, 101(473): 138-156, 2006.
Convexity, classification, and risk
[7] Hamsa Bastani and Mohsen Bayati. Online decision making with high- digh-simmenional covariates. Operations Research, 68(1):276-294, 2020.
[8] A. Bibaut, A. Chambaz, and M. van der Laan. Generalized policy elimination: an efficient algorithm for nonparametric contextual bandits, 2020.
10

---

[9] Aurelien Bibaut, Maria Dimakopoulou, Nathan Kallus, Antoine Chambaz, and Mark van der Laan. Post-contextual-baie bandit inference for policy evaluation. 2021.
[10] Aurélien F Bibaut and Mark van der Laan. Fast rates for empirical risk minimization over cădlăg functions with bounded sectional variation norm. arXiv preprint 190Xx:990.009240 2019.
[11] Bernd Bischl, Giuseppe Casalicchio, Matthias Feurer, Frank Hutter, Michel Lang, Rafael G Mantovani, Jan N van Rijn, and Joaquin Vanschoren. Openml benchmarking suites. arXiv preprint arXiv: 7000.00000000 03731, 2017.
[12] Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret analysis of stochastic and hasstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
ISSN 1935-8237. doi: 10. 00.1561/2000000024
[13] Weihua Cao, Anastasios A Tsiatis, and Marie Davidian. Improving efficiency and robustness of the doubly robust estimator for population mean with incomplete data. Biometrika, 96(3): 723-734, 2009.
[14] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourleenth International Conference Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proceedings, 2011.
[15] Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Estimation consider- ations in contextual bandits. arXiv preprint 1rXiv:1711.07000 2017.
[16) Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. arXiv preprint arXiv:1106.2369, 2011.
[17] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485-55 2014.
[18] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference Machine Learning, pages 1447-1456. PMLR, 2018
[19] Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference Machine Learning, pages 3199-3210. PMLR, 2020.
[20] Dylan Foster and Akshay Krishnamurthy, Contextual bandits with surrogate losses: Margin bounds and efficient algorithms. arXiv preprint arXiv:1806. 10745, 2018.
[21] Dylan J Foster and Vasilis Syrgkanis. Orthogonal statistical learning. arXiv preprint arXiv: 1et.:-991.0000 2019.
[22] David A Freedman and Richard A Berk. Weighting regressions by propensity scores. Evaluation Review, 32(4):392-409, 2008
[23] Alexander Goldenshluger and Assaf Zeevi. A linear response bandit problem. Stochastic Systems, 311):200-261, 2013.
[24] Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence intervals for policy evaluation in adaptive experiments. arXiv preprint arXiv: 1..07668, 2019.
[25] Yichun Hu, Nathan Kallus, and Xiaojie Mao. Fast rates for contextual linear optimization. arXiv preprint arXiv:2011.030300 2020.
[26] Yichun Hu, Nathan Kallus, and Xiaojie Mao. Smooth contextual bandits: Bridging the paramet- ric and non-differentiable regret regimes. In Conference Learning Theory, pages 2007-2010, 2020.
(27] Yichun Hu, Nathan Kallus, and Masatoshi Uehara. Fast rates for the regret of offline reinforce- ment learning, In Conference on Learning Theory, 2021.

---

[28] Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
[29] Nathan Kallus and Madeleine Udell. Dynamic assortment personalization in high dimensions. Operations Research, 68(4):1020-10377 2020.
[30] Nathan Kallus and Masatoshi Uchara. Intrinsically efficient, stable, and bounded off-policy evaluation for reinforcement learning. In Advances in neural information processing systems, 2019.
[31] Nathan Kallus, Yuta Saito, and Masatoshi Uehara. Optimal off-policy evaluation from multiple logging policies. In International Conference on Machine Learning, 2021.
[32] Maximilian Kasy and Anja Sautmann. Adaptive treatment assignment in experiments for policy choice. Econometrica, 19(1):113-1322 13-132, 2021.
[33] Edward H Kennedy, Optimal doubly robust estimation of heterogeneous causal effects, arXiv preprint arXiv:2004. 14497, 2020.
[34] Toru Kitagawa and Aleksey Tetenov. Who should be treated? empirical welfare maximization methods for treatment choice. Econometrica, 86(2):591-616, 2018.
[35] Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities in risk minimiza- tion. Annals of Statistics, (4(6):2593-265)) 2006.
[36] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[37] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandt approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[38] Alexander R. Luedtke and Mark J. van der Laan. Statistical inference for the mean outcome under possibly non-unique optimal treatment strategy. The Annals of Statistics, 44(2):713- 742, 2016. doi: 10. (0.1214/15-AOSI1
[39] Enno Mammen and Alexandre B Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6); 1808-1829, 1999.
[40] Pascal Massart.
Concentration inequalities and model selection. 2007.
[41] Mina Ossiander. A central limit theorem under metric entropy with 1_2 bracketing. Annals of probability, 15(3):897-9199 1987.
[42] Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Annals of Statistics, 4 41(2):693-721, 2013.
[43] Sheng Qiang and Mohsen Bayati. Dynamie pricing with demand covariates. arXiv preprint 1604.0:600.000
2016.
[44] Simon Quinn, Alex Teytelboym, Maximilian Kasy, Grant Gordon, and Stefano Caria. A sequen- tial and adaptive experiment to increase the uptake of long-acting reversible contraceptives in cameroon, 2019. http://pww.......oaaaaaaaaaeaera httpr////isaiiooorrrrrraaa/////s Study registration.
[45] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. 2013.
[46] 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-14 2015.
[47] Philippe Rigollet and Assaf Zeevi. Nonparametric bandits with covariates. arXiv preprint 1630, 2010.
12

---

[48] James M Robins, Miguel Angel Hernan, and Babette Brumback. Marginal structural models and causal inference epidemiology, 2000.
[49] Daniel Rubin and Mark van der Laan. Empirical efficiency maximization: Improved locally efficient covariate adjustment in randomized experiments and survival analysis. The International Journal of Biostaristics, 4(1), 2008.
[50] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Available at SSRN, 2020.
[51] Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims. Cab: Continuous adaptive blending for policy evaluation and learning. In International Conference on Machine Learning, pages 6005-6014. PMLR, 2019.
[52] Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16(1): 1731-1755, 2015.
[53] Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. In Mobile Health, pages 495-517. Springer, 2017.
[54] Alexander Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166, 2004.
[55] Sara van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
[56] Aad W van der Vaart and Jon Wellner. Weak convergence and empirical processes. Springer, 1996.
[57] Ramon van Handel. On the minimal penalty for markov order estimation. Probability theory and related fields, 150(3-4):709-733 2011.
[58] Ruohan Zhan, Zhimei Ren, Susan Athey, and Zhengyuan Zhou. Policy learning with adaptively collected data, arXiv preprint arXiv:2 200.020405 2021.
[59] Yingqi Zhao, Donglin Zeng, John Rush, and Michael Kosorok. Estimating individual- ized treatment rules using outcome weighted learning. Journal of the American Statistical Association, (074499):100-11111 2012.
13


Reviews:
[{"review_id": "fbHct87QvAV", "reviewer": "Reviewer_q5vX", "summary": "The paper provides a nice technical contribution; the topic of the paper is relevant. I appreciate the technical contribution of the paper and some extensions of the empirical process theory. However, as a referee, I need to answer if the paper is interesting to the audience and whether it should be presented at the conference. Overall, it looks like an example paper where too much technical content shadows the paper's conceptual message. Also, it seems that once Theorem 1 is established, all applications, including fast rates, become very standard.\n\nHere are my main comments: \n\n1) The authors claim that their results capture the correct dependence on the exploration rate. Does it mean that previous results on weighted ERM could not achieve this? Or is it only related to the recent work Zhan et al. ? It seems that van de Geer (who used sequential bracketing inequalities) did not study weighted ERM.\n\n2) A few remarks in the main text look too specialized/technical. For example, Remarks 2, 3, 4 occupy a significant part of the main text but discuss relatively subtle technical details appearing in the previous papers. Moreover, the assumptions and models in these previous papers are different. In particular, I found a claim that the authors match the lower bound of Zhan et al. 21 closing the existing gap quite confusing: the lower bound of Zhan et al. 21 is in a different setup involving the Natarajan dimension of the policy class and so on (while the authors prefer non-parametric (even non-Donsker) functional classes).\n\n3) The results are based on the bracketing entropies. It is quite restrictive for parametric classes. In particular, for some \"small\" classes like VC-subgraph/Natarajan classes, bracketing entropies can behave very poorly and thus, standard parametric rates cannot be recovered using this technique. This is also relevant when comparing with previous \"parametric\" papers.\n\n4) It seems that fundamental results on sequential empirical processes (Theorem 1) are more suitable for specialized journals rather than ML conferences, where the technical aspects of the proofs cannot be properly verified/appreciated. As I mentioned, apart from this contribution, other technical parts of the paper are standard. If Theorem 1 is of such an interest, it is better to make a more detailed comparison with previous results ( at least write van de Geer's bound explicitly). \n\nOverall, I think it is a good piece of research, but I could not recommend it for acceptance in the present form.\n\nTechnical comments.\n\n1) What is the definition of \\| \\|_{2, g*} norm first appearing in line 146?\n2) Lines after line 621 - missing brackets.\n3) Typo after line 628.\n4) How is the proof of Theorem 6 based on Theorem 6 itself in line 661?", "questions": "", "limitations": "", "rating": 5, "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": "The paper is a nice technical contribution and the topic of the paper is relevant. I appreciate the technical contribution of the paper and some extensions of the empirical process theory. However, as a referee, I need to answer if the paper is interesting to the audience and should be presented at the conference. Overall, it looks like an example paper where too much technical content shadows the paper's conceptual message. Once Theorem 1 is established, all applications, including fast rates become very standard.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "QHlsMp5UYPe", "reviewer": "Reviewer_P7T1", "summary": "In this paper, Importance Sampling Weighted ERM (ISWERM) is studied for the use of adaptively collected data to minimise the average of a loss function over an hypothesis class to get generalisation guarantees and fast convergence rates. The main result to achieve this is a novel maximal inequality for importance sampling weighted empirical processes. The authors then apply this result to obtain slow rates for certain entropy condition and fast rates under variance bounds; and they apply this to regression and policy learning. The authors conclude with an empirical evaluation of ISWERM against many variations on this approach, using contextual bandit data. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "The paper is well-written and pleasant to read. The structure is very clear. There is a thorough comparison with related literature.\n\nThe main theoretical contribution is a maximal inequality for importance sampling weighted sequential empirical processes (theorem 1). I'm not an expert in this area, so I am unable to judge the depth of this result. It seems a sound result. The result can be used to obtain generic guarantees for ISWERM: slow rates under certain entropy conditions, and, as to be expected, fast rates in the presence of variance bounds. ISWERM is instantiated to regression and policy learning, which shows applicability to important problems for which ERM is commonly used (for iid data), so the scope of these results is satisfying. Also, the comparison (remark 3 and 4) with existing literature is very nice, as is the empirical evaluation - where ISWERM is compared to other weighting methods from the literature and performed with ridge, lasso regression and cart - also very useful methods, so: good choice.\n\nIt the other reviewers have a better estimation of the importance/impact of the results, I'm happy to lower or higher my score. \n\nSome minor remarks:\nline 80: bilbioraphies -> bibliographies\n\nVan der Laan, Van de Geer, Van Handel, Van der Vaart: \nLike many Dutch names, these surname consists of two or three words: 'Van de Geer'. The article 'Van' is capitalised, except when directly preceded by a given name or initials. Although 'Van de' always precedes 'Geer', in an alphabetical list, this name should be listed according to 'Geer' only. Inline it should thus look like: \"Van de Geer [55]\" and in the bibliography it should be sorted according to the letter G and look like: \"Sara van de Geer ...\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did address some concerns, but maybe the limitations could be addressed a bit more. On the other hand, they show that the results apply to some commonly used settings and methods. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 "}, "extra_text": {}}, {"review_id": "PC3RzM7mlfV", "reviewer": "Reviewer_5gHo", "summary": "This work studies ERM for adaptively collected data with a generic importance sampling weighted risk. The main contribution is theoretical, where the authors claim to provide first-of-their-kind generalization guarantees and fast convergence rates. Technically, the results rely on a new maximal inequality the authors derive by leveraging the importance sampling structure. A short experiment is also provided to validate the theory.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The paper seems to contain new theoretical insights which might be interesting. However, the current version is technically dense and not very reader friendly. I think it is very hard to appreciate the results (note: this could be due to my lack of relevant background, so I would leave the experts to comment on the technical depth). The paper has extensive citations on prior work and it seems to require a fairly broad and detailed understanding of the literature. Often, the results are missing enough intuition/explanation. It is not easy to understand that beyond the mathematical equations, what the theory would imply and how the general audience should interpret it. Some of the assumptions are assumed without further explanation and hence, it is not clear whether they are assumed solely for the technical proof or there are deep connections to the problem. Overall,  I would suggest to revise the paper to improve the readability. Also, there are some notable typos (e.g., lines 145 and 151) that can be fixed.    ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2h"}, "extra_text": {}}, {"review_id": "HCWvBnB1qc7", "reviewer": "Reviewer_kdLu", "summary": "This paper considers the problem of empirical risk minimization when the data are adaptively collected and are thus non i.i.d. The data can have been sampled from a sequential contextual bandit procedure for instance. Theoretical guarantees for classical empirical risk minimization fail in this case. This paper analyses the empirical risk minimizer reweighed via importance sampling (ISWERM). For non-parametric classes of functions, the authors provide upper-bound on its excess risk. The latter is expressed in terms of a sequential bracketing entropy of the class of function. When the data is i.i.d., one retrieves the classical slow rate of convergence for non-parametric risk minimization. The authors also show faster rates under additional assumptions (variance bound, square loss, margin condition). In the case of policy learning with epsilon-greedy as the sampling policy, the upper-bound matches the known lower bound closing thus an important gap. Finally, ISWERM is shown to empirically outperform standard unweighted ERM and other weighted versions of ERM.", "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": "To my opinion, this paper brings a significant contribution to the community. ERM is widely used and having simple versions of it that come with theoretical guarantees when the data is non i.i.d. but adaptively sampled is surely interesting. Furthermore, the analysis seems nontrivial and requires sophisticated technical tools from empirical process maximization and I think that matching the lower-bound for policy learning was a challenge. \n\n\nOn the other hand, the writing of the document is sometimes very technical with many notations and requires a lot of concentration to be understood. I wonder if a preliminary section that highlights the results and provides sketches of proofs for finite classes of functions (or parametric, so that bracketing entropy is not necessary) might not help in understanding the proof and the results. It could be also interesting to recall some classes of functions and losses where the ISWERM can be efficiently estimated. \n\nOther comments:\n1. As mentioned in the conclusion, I agree that it would surely be interesting to extend the analysis to variance reduction of IPS, such as doubly robust since IPS can be very unstable. If the analysis is surely technical and can be left for future work, I think that It could be of interest to add for instance a doubly robust version in the experiments? I am a bit surprised that standard IPS seems to outperform more sophisticated versions that were designed to be more stable such as ISFloorWERM (and others). What are the advantages of such methods then?\n2. I would also find it interesting to analyze a clipped version of IPS when the weights get too large. For some bandit algorithms, gamma_t can grow very quickly. Clipping might be helpful in this case to reduce the variance.\n3. Experiments with synthetic data that show the rates of convergence indeed obtained by ISWERM and ERM could also be of interest.\n4. After Thm.1, I would emphasize that this bound is very close to what is known in probability theory as\nDudley’s entropy integral, a useful tool to upper bound the expectation of a centered stochastic process with subgaussian increments. And that it is often key to derive risk bounds on empirical risk minimizers in statistical learning.\n5. What about the case p=2 in Thm. 2, 4,... Sometimes, the two cases do not match when p-> 2, is it normal? \n\n\nMinor remarks and typos:\n- section 1.2: sometimes $g^*(x|a)$ instead of $g^*(a|x)$\n- l145: sequence sequence\n- l146: I would define the norm $\\|| \\cdot \\||_{2,g}$ there\n- Ass 2: the notation of the paper is already heavy, I do not understand why you need to introduce the envelope function Λ when you always use $\\||\\Lambda\\||_{2,g}$ which could be introduced by the existence of a positive number only.\n- l233: withe\n- l300: multi-calss", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "7cPv2xR6dmp", "reviewer": "Reviewer_ZSG9", "summary": "This paper develops theoretical guarantees for importance-weighted empirical risk minimization on adaptively collected data. They characterize the risk of their method compared to the population risk minimizer in the form of a high probability bound. This type of bound can be used for guaranteeing risk minimization for policy learning on adaptively collected data.", "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": "The bound presented in this paper is an important result for how statistical methods for i.i.d. data can be modified for adaptively collected data, which includes all types of data collected with bandit algorithms. It is the first bound of its kind for adaptively collected data.\n\nI think the authors should discuss the following limitation in the discussion section: It is not clear that importance weighted empirical risk minimization is necessarily better than unweighted empirical risk minimization (or ERM with different weights) on adaptively collected data. This agrees with Figure 1 (c) where unweighted ERM empirically outperforms importance weighted ERM. \n\nI found significant portions of the text difficult to read, e.g., some of the notation is not explicitly defined in the text.\n-\tLine 140: Did not define what script O is yet.\n-\tLine 147: I got very confused thinking that k denoted an exponent. Perhaps put parentheses around k.\n-\tLine 282: What is the mu function here?\n\nFrom reading the main text of the paper, it is very difficult to interpret the simulation results. It would be useful to provide some more information in the main text.\n-\tWhat is g^* in your simulations?\n-\tExplicitly say what the axes represent in Figure 1 in caption.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See discussion in main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This looks like a strong paper that makes significant contributions. Simultaneously, the current presentation is very technically dense; this was the conclusion of absolute experts and so is not to be taken lightly. Consequently, despite the strength of the results in this work, the results will have a tough time being appreciated even by general readers in learning theory (and definitely going outside of learning theory). Also, there is no space in the current version to add anything, and so it is implausible that the authors would be able to add in things like proof sketches without a major revision of the paper. On that note, the authors mentioned that they do not believe the paper needs a major rewrite (the reviewers and I disagree), and a major revision would require another round of reviewing in any case.

Therefore, and I admit the decision is not easy, I really do feel that this paper should not be accepted in the current form. My feeling is that a resubmit to a conference like ALT, which is more generous with space and would allow for considerable improvements to the narrative (plus proof sketches, etc.) would be in service to the authors by letting their work be better appreciated by the field. On that note, I advise the authors to consider the reviewer feedback about significantly changing the presentation in their paper. It’s their choice whether or not to rewrite the paper, but to get it accepted somewhere, I (and evidently many reviewers) really think this is needed.

In the rest of this meta-review, I highlight some of the positive aspects that came out in the reviews, as well as some specific negative aspects.

On the positive side, the bound presented in this paper is the first of its kind for adaptively collected data. There certainly is novelty here, and the result is significant. The analysis is highly non-trivial (i.e., quite sophisticated). Based on the author response to some of the reviews and the paper itself, there also is interesting follow-up work. 

On the negative side, the paper could really use more intuition (by way of informal statements) and proof sketches. However, there simply isn't space in the current form of the paper; it’s incredibly dense in terms of filling the space as it is. The authors disagree about reducing the lengthy, highly technical comparisons with previous papers (they seem unwilling to do a serious rewrite), even though several reviewers mentioned that this would be a good idea. Especially the fundamental result Theorem 1 should be given more justice/attention in the paper. In addition, one technical weakness is that a continuing concern about the comparison with the VC/Natarajan setup of the lower bound of Zhan et al. (when the authors claim that they have matched the lower bound). It sounds like the authors simply need to technically qualify in what way they match, and so I hope they clarify this in any future version.
Decision: Accept (Poster)