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.cm edu
addimakkoooullu@@etfll... com
Antoine Chambaz
Mark van der Laan
Université de Paris
University of California, Berkeley
antoine. chambaz&u saataazuuuprrii..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---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 [((. = / | (x, o, (yy | 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 R²) 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 I 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 btassificationncaibraat 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, ( 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- 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 -oan-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 -.e--uuuurrable, 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 2mmmany 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.p
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 71 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-f 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 //:))))) 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]
f E F).
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-))(((f..)))))) (f 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(,-) (lin-))-((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(/FF122. : 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---IMMMM---- /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:
[[((,-) - {(', (,,.,))ll,,, 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, a) ((((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. (7 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 1and 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 FoOWERO
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-ooo
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 rrceissonTreeeeggeee Reggresss,,,,rr each with default parameters. For Ridge and LASSO we pass as features the intercept intercept-augmented contexts {(1, (11x))) 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 trsstof-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//o//01111110 hrtiyyy-rroooooo--taaaeeeeeeeeee -et.oo---Apptiie-epepeeee 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.:-911.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 registration.
Study
[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 1631, 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 (atn:2/05.02344 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": "oyUYSKYVBb1", "reviewer": "Reviewer_beVp", "summary": "This paper considers a generic importance sampling weighted ERM algorithm for minimizing the loss over a hypothesis class when the data are adaptively collected (i.e., previous choices and their respective feedback received affect subsequent choices). Such adaptively collected data are the result of data collected from a contextual bandit algorithm, for example. The paper provides generalization guarantees for the proposed method and fast convergence rates under some extra assumptions. The technical derivations are based on a new maximal inequality that obtains a better dependence on the exploration rate of the data than prior work. The paper shows the applications of the method for the convergence rates on least squares and policy learning. Finally, it provides empirical results comparing the proposed method with related ones.\n", "questions": "", "limitations": "", "rating": 6, "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": "===== After Rebuttal =====\n\nI'm thankful to the authors for their response and for providing clarifications to my questions! I remain positive towards the paper but would like to stress once more that, as a non-expert in the area, it was sometimes hard to evaluate the significance of the paper. Please incorporate the suggestions that myself and others included in their reviews, and hopefully, this will make the paper more accessible to non-experts.\n\n======================\n\n\nEvaluation.\nThe paper is pretty much outside of my area of expertise. Below is my best effort to evaluate whatever I could understand from the paper. \n* The method of reweighting the importance sampling in order to account for changes in the data looks like something that people have already thought about. I am not sure about prior work related to the present paper, but there are certainly bandits settings (even non contextual ones) where the better regret rates are obtained just by carefully reweighting with the appropriate distribution.\n* That said, it seems that the topic (i.e., identifying ways to reweigh the ERM so as to achieve generalization bounds when the data is adaptively collected) is very interesting and broadly applicable. It is also nice that the paper closes previous gaps existent in the literature and that it shows the applicability of the method in the regression and policy learning settings. \n* It was nice that the paper has remarks and explanations in various places that explain connections and differences with prior work. \n* One limitation that I see from the general setting is that it seems to require perfect knowledge of the algorithm (or at least the process) used to collect the data (see also my first question below). \n\nQuestions.\n* This is pretty fundamental and I am sorry if it is obvious but in order to do this reweighting don’t you need to know the density p^{(T)} but also the decomposition to p_X, \\tilde{g}, and p_Y? Why is this an okay assumption in this line of work? It would seem to me that it is restraining since you need to know exactly the process by which the dataset was generated. Or is the paper saying that just by having access to \\bar{O}_T you can compute p^{(T)}?\n* It is claimed in at least two places (see Lines 9 and 170) that the dependence on \\gamma_t from Theorem 1 is the “right” or the “optimal” one. But how do we know this? I could not find a lower bound in the paper. Is there a result in the literature that establishes it? Is it due to the lower bound of Zhan et al. [58]?\n* I understand that the paper acknowledges that the empirical results are not intended to provide state-of-the-art methods. That said, I am sorry to say that I am a bit confused regarding the usefulness of the method since it doesn’t outperform other methods dramatically. Also, could you please comment on the runtimes for the methods?\n\nAdditional comments.\n* What is \\tilde{g} referring to in Line 43? Is it the probability that action a_t was chosen given context x_t and the history of past outcome tuples?  \n* What is the “following” referring to in the citations in Line 301?\n* Is \\alpha also <=1 in Assumption 4? I was trying to figure out which one is the dominant term in the last equation of Page 5, to see the difference with Theorem 2. \n* Structurally, I think since Sections 4 and 5 are applications of the main theorems of section 3, I would suggest that you have them as subsections in Section 3, rather than standalone sections.\n* Regarding the limitations question in the checklist, you do list carefully all the assumptions under which your theorems work, but I think it would be nice to include a small paragraph about more model-specific/high-level limitations. For example, if indeed p^{(T)} is assumed to be known in this work, I would consider this a potential limitation.\n\nTypos.\n* Line 80: “biblioraphies” → “bibliographies”\n* Line 151: “of classes of classes” → “of classes”\n* Line 156: “rate of the the IS” → “rate of the IS”\n* Line 233: “withe envelope constant” → “with the envelope constant”\n* Line 300: “different mutli-calss classification dataset” → “different multi-class classification datasets”\n* Line 661: I think that the instantiation is on Theorem 3, not Theorem 6.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Overall yes. I have added a comment regarding the limitations in my main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10-11"}, "extra_text": {}}, {"review_id": "jntHriG4i1", "reviewer": "Reviewer_7ciX", "summary": "The paper considers empirical risk minimization when data is generated from a markov decision process.\nTheir particular framework, called stochastic-contextual-bandit, covers several applications such as e-commerce and policy making.\nThe paper is mostly theoretical: a uniform bound on empirical sums over classes of functions with controlled bracketing numbers is given. Then this general result is applied to two different loss functions (least squares regression and one other related to policy learning).  In both settings, slow and fast rates are obtained depending on certain assumptions on the model.", "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": "Let me say from the start that I like this paper very much. It is well written, the results are interesting and novel, and the mathematics are well-educated. I have several questions and concerns that I hope will help the authors to improve their work.\n\n\n1. I am not sure the context of Markov decision process is useful in their proof of Theorem 1. Would it be possible to extend their results? In a more general context where the triplet O = (x,a,y) would no longer be necessary. In this way, (a) the proof’s arguments could become clearer  and (b) I also think that a more general framework could help in including more examples such as importance sampling (see for instance eq. (6) in Portier and Delyon. \"Asymptotic optimality of adaptive importance sampling.\" NeurIPS. 2018, which seems to fall in the authors framework). Finally, the application to the context of Markov decision process would become less obvious than in the current version where Theorem 2 and 3 are direct corollary of Theorem 1.\n\n2. It is difficult to see how the proposed bound compares with known basic results. For instance, if one is interested in the simple case when the class of functions is made of one single element, what would the authors recommend to use instead of their bound? How would it compare to their bound? In the same line of remarks, what is the closest results to their results in the iid setting?\n\n3. While the literature review seems to have been done seriously, it is difficult to understand because it is written at an expert level. The framework described by the authors seems to be valid to post-process the data. Is this context different from standard online policy estimation such as in the classical reinforce algorithm? Being not very familiar with the contextual bandit framework, I had some issues in understanding the context clearly. I would suggest the authors be more specific about the applications.\n\n4. The process xi_t is hard to understand and I believe it is not needed in the applications of their results. I would suggest simplifying the paper by removing to the supplement everything that is related to this process. If I am wrong and xi_t is useful then some remarks and examples should be given. In the event that xi_t is useless, then I would recommend simply writing f(O) rather than xi(f)(O).\n\n5. The statement of Th1 is a bit strange due to the definition (or rather assertion), concerning gamma_T tilde inside the theorem. I suppose another way is possible.\n \n6. Include a discussion about the validity of assumption 1. It seems to be related to the exploration in bandits algorithm but it is difficult to understand for non specialists. The behavior in T^beta of g^* / g_T is a claim that I cannot verify. Since this is used later in the paper to compare with the existing literature, I would recommend to give mode details;\n\n7. The simulation study shows an advantage of ISWERM (over competitor) when using the LASSO and no significant difference for other considered methods. ISWERM is implemented with g^* = 1 and the model is then evaluated with the same g^*, I wonder what the role of that choice is. More generally, I believe that the role of g^* could have an impact on the outcome. Could the authors comment on this point? In example 1 and 2, the choice of g^* seems to be arbitrary but it certainly influences the results. Is there any recommendation to choose it?\n\n8. The variance bound, Assumption 4, is given without any explanation or references, contrary to the margin assumptions.\n\nTypos:\nTH1 There is an epsilon in the bound of Th1 which should be an r I guess.\nline 156 the the\nline 151 classes of classes\n\n##############SUPLEMENT###############\n\nThe supplementary material is well organized.\nAs far as I can check, the proof is valid.\n\nI would suggest giving more details in some places such as:\n- at the beginning of the proof, the authors combine Markov inequality and some properties of their function psi without saying it.\n- Page 16, the given chaining decomposition is confusing because of the presence of two different index s and t (one of them seems to be useless).\n- The definition of u^{j,f} equal to v^{j,k(j,f)} is surprising as the index t has been removed. Is it a short cut?\n- The definition of Delta (indexed by t rather than s) is also surprising.\n- I think the authors could be clearer on the meaning of their inequalities between functions (such as in the definition of tau), I\n- Perhaps some explanations on the use of tau in the proof would be welcome\n- When adding up the bounds, check they all are correct.\n- At the beginning of the proof of Th2, there is some redundancy in saying that the diameter assumption is used.", "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": "8"}, "extra_text": {}}, {"review_id": "8wB9fKHeVpg", "reviewer": "Reviewer_BwZs", "summary": "The paper studies the excess-risk rate of (importance weighted) ERM when data is collected adaptively (e.g. by a bandit algorithm). The authors argue that current excess-risk bounds are sub-optimal when the exploration rate of the data-collection process converges to zero. They then derive tighter bounds for this problem using a new maximal inequality for an importance-weighted empirical process. The results are instantiated for least-squares regression where it is shown that fast rates are achievable due to the properties of the square loss. Excess risk rates of the importance weighted ERM are also presented for policy learning, closing an open question around achievable rates in this setting. Illustrative experiments are also presented.", "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": " In many modern applications, data is indeed collected adaptively (using a bandit algorithm for example) and it is important to be able to learn from such data. Therefore, this paper's topic is very important in machine learning. The paper also strengthens our theoretical understanding of generalization when learning from adaptively collected data by providing \"state of the art\" excess risk rates of importance weighted ERM (ISWERM). From a practical standpoint, this justifies the use of ISWERM instead of other alternatives. \n\nThe results of the paper are based on a new maximal inequality for Martingale Difference Sequences (MDS) in Theorem 1. I wonder if the same type of result---with the right dependence in \\gamma---can be derived more easily using concentration inequalities for MDS; for example, using Freedman's inequality (e.g. see Lemma 12 in http://proceedings.mlr.press/v125/wei20a/wei20a.pdf). The fact that Freedman's inequality has a variance term in the bound, would also allow the cancellation of the g_t(A_t |X_t) in the denominator of the importance weight. Freedman's inequality can be extended to the case where the process is index by f, where f is in some function class F. Can you explain why such a method would not work?\n\nThe paper is in general well written and has only minor typos.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussion provided in the paper seems adequate.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "7Vp5QEfjitw", "reviewer": "Reviewer_G8uS", "summary": "This paper studies how to perform risk minimization when the training data is adaptively collected. The main example that the authors refer to is the setting where the data is collected while running a contextual bandit algorithm. That data is certainly not i.i.d., so empirical risk minimization (ERM) will not necessarily generalize well. A popular alternative approach is to employ importance sampling (IS), where the samples are weighted by the inverse of the policy’s probability of choosing the observed action. However, the authors write that the existing analyses of IS are not well-suited for data collected via a contextual bandit algorithm, where the rate of exploration is decaying, so the IS weights will diverge to infinity. From my understanding, the authors provide a new analysis of “IS-weighted ERM” (ISWERM) which allows them to provide a bound on excess risk that has a better dependence on the exploration rate. For policy learning, with this new analysis, they match a lower bound by Zhan et al. [arXiv‘21].", "questions": "", "limitations": "", "rating": 6, "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": "This paper studies a very important, practical problem where we want to optimize over a hypothesis class using adaptively collected data. The main downside is that as a non-expert reviewer (but with expertise in related areas), I had trouble seeing the forest for the trees. It was difficult for me to understand the core technical contribution (the new “maximal inequality” described in Section 2) because of how technical it was—the entire paper could *really* benefit from some interpretation for the reader. Here are some specific examples:\n-\tLines 53: What do you mean by a reference policy g*? How is it chosen, and how does it relate to g_t? Are there reasons why we’d use a different reference policy than the deterministic one suggested in line 53 (g*(x | a) = 1)?\n-\tLine 144: The function M_T(f) seems to be an important definition. It’s always important to not only provide the mathematical definition, but also describe what it is in words.\n-\tLine 147: Can you provide some interpretation of the sequential bracketing entropy, in addition to defining it formally?\n-\tTheorem 1: This is difficult for me to parse. Can you provide some intuitive interpretation of this bound? Most importantly, intuitively, how will it help you provide better rates for ISWERM?\n-\tAssumptions 1-7: There are a quite a few assumptions that are stated quite formally. Perhaps these are common (for example, from lines 285-288, it seems like Assumption 7 is common), but as someone who is not familiar with the related research, it’s a bit hard for me to grasp whether they’re reasonable assumptions to make. If you could provide more context around the assumptions and explain why they might be reasonable, that would help a lot.\n\nMore detailed comments:\n-\tLine 51: What is a “non-anticipatory action”?\n-\tLine 80: “biblioraphies\" -> “bibliographies”\n-\tLine 145: “sequence sequence” -> “sequence”\n-\tLine 146: I am not familiar with what it means for g* to be in the subscript of the norm notation. Could you please define this?\n-\tLine 147: It seems that lambda is overloaded.\n-\tLine 151: “of classes of classes” -> “of classes”\n-\tLine 233: “withe” -> “with”\n-\tLine 300: “mutli-calss” -> “multi-class”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe that the authors have sufficiently described the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thanks for the strong submission. After discussion, the reviewers were unanimously in favor of acceptance, although are concerned that the paper is difficult to read for readers even a little bit outside of the target area: we suggest a revision for clarity. 
Decision: Accept (Poster)