Off-policy estimation with adaptively collected data: the power of online learning
Authors: Jeonghwan Lee
Cong Ma
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal inference
function approximation
learning theory
off-policy estimation
online learning
reinforcement learning
Primary area: causal_inference
TL;DR: We provide non-asymptotic guarantees of the AIPW estimator using the framework of online learning for estimation of the treatment effect. We then give a lower bound to demonstrate the instance-optimality of the proposed estimator.

Abstract: We consider estimation of a linear functional of the treatment effect from adaptively collected data. This problem finds a variety of applications including off-policy evaluation in contextual bandits, and estimation of the average treatment effect in causal inference. While a certain class of augmented inverse propensity weighting (AIPW) estimators enjoys desirable asymptotic properties including the semi-parametric efficiency, much less is known about their non-asymptotic theory with adaptively collected data. To fill in the gap, we first present generic upper bounds on the mean-squared error of the class of AIPW estimators that crucially depends on a sequentially weighted error between the treatment effect and its estimates. Motivated by this, we propose a general reduction scheme that allows one to produce a sequence of estimates for the treatment effect via online learning to minimize the sequentially weighted estimation error. To illustrate this, we provide three concrete instantiations in (1) the tabular case; (2) the case of linear function approximation; and (3) the case of general function approximation for the outcome model. We then provide a local minimax lower bound to show the instance-dependent optimality of the AIPW estimator using no-regret online learning algorithms.

Off estimation with adaptively collected data: the power of online learning
Jeonghwan Lee Department of Statistics The University of Chicago Chicago, IL 60637 jhlee97@uchicago.. edu
Cong Ma
Department of Statistics
The University of Chicago
Chicago, IL 60637
congm@uchicago. edu
Abstract
We consider estimation of a linear functional of the treatment effect from adaptively collected data. This problem finds a variety of applications including off-ppoicy evaluation in contextual bandits, and estimation of the average treatment effect causal inference. While certain class of augmented inverse propensity weighting (AIPW) estimators enjoys desirable asymptotic properties including the semi- parametric efficiency. much less is known about their non-asymptoti theory with adaptively collected data. To fill the gap. we first present generic upper bounds the mean-squared error of the class of AIPW estimators that crucially depends on sequentially weighted error between the treatment effect and its estimates. Mo- tivated by this, we propose a general reduction scheme that allows one to produce a sequence of estimates for the treatment effect via online learning to minimize the sequentially weighted estimation error. To illustrate this, we provide three concrete instantiations in (1) the tabular case; (2) the case of linear function approximation: and (3) the case of general function approximation for the outcome model. We then provide a local minimax lower bound to show the instance dependee optimality the AIPW estimator using no-regret online learning algorithms.
Introduction
Estimating a linear functional of the treatment effect is of great importance in both causal inference and reinforcement learning (RL). For instance, in causal inference, one is interested estimating the average treatment effect (ATE) [20] their weighted variants, and in the literature of bandits and
RI, one interested in estimating the expected reward of a target policy 38 challenges arise when tackling this problem:
37
Two main
Off-policy estimation: Oftentimes, one needs to estimate the linear functional based on obser- vational data collected from behavior policy. This behavior policy may not match the desired distribution specified by the linear functional 42):
increasingly common for observational data to be adaptively collected due to the use of online algorithms (e.g., via contextual bandit algorithms [60 in experimental design [67].
Adaptive data collection mechanism:
33 52
In this paper, we deal with two challenges simultaneously by investigating the estimation of linear functional of the treatment effect from observational data that are collected adaptively. When the observational data is collected non non-adaptively. i.e., an i.idd. manner, there is extensive line of
work [51 49 10 24 I 27 43
3 64 41 investigating the asymptotic and non-asymptotic theory of various estimators. Most notably are the study [6] that establishes the asymptotic efficiency of family of semi- mammmearaettri estimators, and a more recent study [42] that undertakes a finite-sample
6.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

analysis which uncovers the importance of a certain weighted f--norm when estimating the treatment effect. On the other hand, when it comes to adaptively collected data, most prior works [T6 67 focus on the asymptotic normality of the estimators, and do not discuss the finite-sample analysis of the estimators. In this paper, we aim fill in this gap.
1.1
Main contributions
More specifically, we make the following three main contributions in this paper:
First, present generic inite-sample upper bounds on the mean-squared error of the class of augmented inverse propensity weighting (AIPW) estimators that crucially depends on a sequentially weighted error between the treatment effect and its estimates. This sequentially weighted estimation error demonstrates a clear effect of history-dependent behavior policies:
Second, motivated by previous finding, we propose a general reduction scheme that allows one to form a sequence of estimates for the treatment effect via online learning minimize the sequentially weighted estimation error. To demonstrate this, we provide three concrete instantiations in (1) the tabular case; (2) the case of linear function approximation; and (3) the case of general function approximation for the outcome model;
In the end, we provide local minimax lower bound to showcase the instance-dependent optimality of the AIPW estimator using no-regret online learning algorithms in the large-sample regime.
1.2 Related works
Off-policy estimation with observational data Off-policy estimation in observational settings has been a central topic in statistics, operations research, causal inference, and RI. Here, we group few prominent off-policy estimators into the following three categories: (i) Model-based estimator: often dubbed as the direct method (DM), whose key idea is to utilize observational data to learn a regression model that predicts outcomes for each state-action pair, and then average these model predictions 129 10 9 39]. Due to model mis-specification, DM typically has low variance but might lead to highly biased estimation results. (ii) Inverse propensity weighting (IPW): for the OPE task, IPW uses importance weighting to account for the distribution mismatch between the behavioral policy and the target policy 55). If the behavioral policy differs significantly from the target policy, then IPW can have an overly large variance (known as the low overlap issue) 23 Typical remedies for this issue include propensity clipping [7 or self- normalliazziionn [99 58 (iii) Hybrid estimator: some off- off-policy estimators (e.g., the doubly-robust (DR) estimator 10 combine DM and IPW together to
64 A key asymptotic results in OPE is that the cross- fitted DR is /nn-consistent and asymptotically efficient (that is, it attains the lowest possible asymptotic variance), even for the case where nuisance parameters are estimated at rates slower than / /n-rates (6). However, these methods still might be vulnerable the low overlap issue especially for large or continuous action spaces. Thus, there has been a line of recent studies on OPE
blend their complementary strengths [48 10 9 59 12
56
for large action spaces [3 44 54
and OPE for continuous action space 28 35
Off-policy estimation with adaptively collected data A recent strand of works studied asymptotic theory of adaptive variants of the IPW and DR estimators (e.g., asymptotic normality, semi- parameera efficiency, and confidence intervals) 31 g 7 for adaptively collected data. However, in adaptive experiments, overlap between the behavioral policies and the target policy can deteriorate since the experimenter shifts the behavioral policies in response to what he/she observes (known as the dristing overlap) (67). It may engender unacceptably large variances of the IPW and DR estimators. To address this large variance problem, there has been a recent strand of works investigating variance reduction strategies for the DR estimator based on shrinking importance weights toward one [4] 644, (57 (56), local stabilization 40 69]. and adaptive weighting [17 67). Recent studies on policy learning with adaptively collected data [68 26 explored the adaptive weighting DR estimator for policy learning. In contrast with the majority of prior works on off pollcy estimation with adaptively collected data that focus on asymptotic results, this paper aims at establishing non-as non-asympootic theory of the problem. While several researchers have been recently explored non-asymptotic results of the problem with an emphasis uncertainty quantification 30 65 we focus on analyses of estimation procedures of the off-policy value. As a majority of existing standard objects for uncertainty quantification, such as a confidence interval (CD, take very static view of the world (e.g., it holds for fixed sample size and

---

is not designed for interactive/adaptive data collection procedures), the aforementioned two papers instead study a more suitable statistical tool for such cases called confidence sequence.
30 65
2
Problem formulation
We first formulate our problem using the language of contextual bandits: let X, A. and C R denote the context space, the action space, and the outcome space, respectively. Denote by 0 X A x Y the space of all possible mnntext-action-outcome triples. In an adaptive experiment, one observes n samples {(X, Ag, Y;) E 0 E [n]} produced by the following data generating procedure 266 68 At each stage i E [m].
(i) A context X; E X independently sampled from a fixed context distribution E+( (X))
(ii) There exists behavioral policy (I;(;-): x x 0'-1 + A(A) that selects the i-th action A, X,, O E [m]. As I (: [x,,, 0,-1) may depend on previous observations, { {(X,, A,, Y)) E [n]]
II; (- [X,, 0,-1), ) where O; := Ax, .,,, Y)) Of for
are longer Li.d.:
(iii) Given Markov kernel (* X x A A(Y), assume that the outcome is generated according to Y, I*t (-|X;, Az). Moreover, the conditional mean of the outcome Y; E Y is specified
E E ( ] / yr (dy (,) μ¹ (X,.
where the function ; x A the reward function (in bandit and RL literature). We note that the treatment effect μ² is not revealed to the statistician. We also define the conditional variance function o² :.
is called the treatment effect (in causal inference)
X x >> [0, +00 defined by o² (xr, a) == (Y p (X, A)) (X, A) = (ar (z,a) which is assumed to satisfy (1 a) < +o0 for every state-action pair (Ir, a) xxx A.
At this moment, assume the existence of -inite base measures (x( (-), and (x over X. A. and Y, resp., such that E-)-) & >xx(), 11; (-|x,, 0,-1) < (-)-) for every (x, 0;-1) E X x 0 and E [n]. and I (- (-(x,a) < Xx(+) for all state-action pairs (x,, a) E X A. Here, the notation << stands for the absolute continuity of measures. Our main goal is to estimate the off-policy value for any given target evaluation function -).
A E defined as
= (I*)= = Ex-z- [((X,)) (X,
where I I' (E", E I
A(X) (X x A + A AYY) defines our problem instance. Throughout the paper, we assume that the propensity scores [ (X:, O.-1; A.) i E [m]] are revealed, where o (x, 1;- == du
(-12,0.-1)
R.
aAx
As mentioned earlier in Section the estimation problem of linear functional of the treatment effect 1z" turns out to be useful in both causal inference and RL in the following sense:
Estimation of average treatment effects: We consider the binary action space A = {0, 1} equipped with the counting measure. The average treatment effect (ATE) our problem setting defined as the linear functional
ATE = Ez. [ML()) Y;()) Ex- 1A" (X,1) p. (X,
Once we take the evaluation function as g(I, a) = 2a 1, the ATE boils down to particular case of the equation (
Off-policy evaluation (OPE) for contextual bandits: Assume that a target policy IT X + A(A) is given such that narget (-Iz) < (.) for every context X. For simplicity, let larget (x,-) <1Iz))()))) denote the density function of the target policy for each context x e X. dA. If we take g(z, a) n tag a), then the linear functional T corresponds to the value of the target policy Marget This problem has been widely studied in the literature of bandits and RI, known the off-policy evaluation (OPE).
3

---

We conclude this section by introducing notations that will be useful in later sections: let F E A (0*) denote the law of the sample trajectory O under the sampling mechanism with problem instance I = (= E II, We denote the density function of Pzz E A (O*) with respect to the base measure
(Ax 2 da 8 Av) o by pz Of + R,. Lastly, we define the k-th weighted tn-norm for E [x] as
k (X;, A.) x2 (X,, As) (Ti) (X,, A::1:A)
Er- [s0lli2) = k
(2)
for any function (0(,,)) :X x A - R, together with the k-th weighted Ep-sea by
L(t = ((())) (X x
R) [| < +00
3 A class of AIPW estimators and non-asymptotic guarantees
The main objective of this section to develop a meta-algorithn to tackle the estimation problem of the off off-policy value ① followed by some key rationale of the proposed procedure variance- reduction scheme of the standard inverse propensity weighting (IPW) estimator.
3.1 How can we reduce the variance of the IPW estimator?
Akin to 42 we consider a class of two-stage estimators obtained from simple perturbations of the IPW estimator. Given any collection / := (Je: X x 0' x & + R : E [v]] of auxiliary functions,
we consider the following perturbed IPW estimator + (-) 0 + R:
9 (21, n1 T. O11;0)));
1
(o.))
fi (1i, 0, az) + (fs (I,, 0,-1,,) )) mz (xi, 0;
For each E [n], let E A x 0d11x A) denote the joint distribution of (X,; O,-1, A,) induced Then, we arrive at the following
by the adaptive data collection procedure described in Section 2 result whose proof deferred to Appendix [B.T]
Proposition 3.1. For any collection f == (Ss 122 (vs): E [ni] of auxiliary deterministic functions, we have Ey- [ (O,)) = T (I*). Furthermore, if
(I, ,. (x,, 03-1: 1)x, O, V(I,
(3)
for each E [ri]. then
n. Varz.
[+t (Ow))
= Varx=z [(((X, (X, (X, )aal +1all(n))
(4)
[ Ab) p² (X,, Ai) (g (Xi.)) n² (Xi 22x Sa (X,, O 0.-1, Ai) o. (X,, O; A.)
27
Er.
71
From the decomposition (4) of the variance of the perturbed IPW estimate #.f (On), one observes that the only term that depends on the collection of auxiliary functions ff is the third term. More importantly, the third term is equal to zero if and only if
Si (x, o, a) = S (I. a., (z, a) n² (x.a) (g(a, :), p ()x
(5)
mi (z, 0;01;
The collection of minimizing functions === (J² E 1 (vx) : [n]) yields the oracle estimator +f (+) 0 +R
9 (X,, A.) (Y, 1r" (X,, A:)
+ (g (Xi..) (Xi, (Xx:))>ae }
(On=
(6)
t5 (X,, O. As)
1=1
whose variance is given by n Varg-
2 (O,) = 2 Varx (xx +110l

---

Algorithm/ 1 Meta-algorithm: augmented inverse propensity weighting (AIPW) estimator.
Require: the dataset D {(X,, A,, Y.) 00:c E [n]] and an evaluation function 9 X R. 1: For each step i E [n], we compute an estimate fi; (O:-1) E (X x A + R) of the treatment effect based on the sample trajectory 0
1 up to the (i 1) step. // Implement Algorithn
as a subroutine;
2: Consider the AIPW estimator (a.k.a,, the doubly-robust (DR) estimator) F
#AIPW (+) 00" R:
AIIPW n
(on)
r, (o.).
(8)
where the objects being averaged are the AIPW scores f.(-) 0' + RR is defined by
(Ti, 02)
Pg (o:) == !h (24, 01)10 (4) {vr (o.-1) + (g (zt, ). : A (o.-1) (2 1))a
(9)
3: return the AIPW estimate AIPW (O,). 7
3.2 The class of augmented IPW estimators
Since the treatment effect ju" is not revealed to the statistician in (6). is impossible to exactly compute the oracle estimate */." (-) 0 + R using only the observational dataset O,, Therefore, a natural remedy would be the following two-stage procedure, which is referred to as the augmented inverse propensity weighting (AIPW) estimator or the doubly-robust (DR) estimator [10]50] 61 17 677 [2]:
(i) we first compute a sequence of estimates (Ar (O,-1) E (X + R) : E [n]] of the treatment effect ,²; and then (ii) we plug-in these estimates the equation 6 to construct approximation to the ideal estimate 7M." (On). We summarize this two-stage procedure in Algorithm |
We pause here to compare our problem setting and algorithms with the most relevant work We focus on off- off- policyliyyy estimation with adaptively collected data, which is technically more challenging compared to i.i.d. data considered in [2). In the case with i.i.d. data, 42 proposed a natural approach to construct class of two-stage estimators as follows: (a) compute an estimate jú of the treatment effect 14" utilizing part of the dataset; and (b) substitute this estimate the equation (6) of the oracle estimator. Note that the authors use the cross-fitting approach 5 6 which allows to make full use of data to maintain efficiency and statistical power of machine learning algorithms for estimation of nuisance parameters while reducing overfitting bias. However, the cross-fitting strategy heavily relies on the i...d. nature of the data collection mechanism and therefore one cannot use in the setting with adaptively collected data. Instead, we construct an estimate μı; of the treatment effect μ² based on the sample trajectory 0,-1 at each stage and then substitute these estimates in the equation (6). This is one of main contributions address the adaptive nature of our data generating mechanism. We will make use of the framework of online learning to construct a sequence of estimates for the treatment effect μ!"
3.3 Theoretical guarantees of Algorithm 1
In this section, we provide statistical guarantees for the class of AIPW estimators for dealing with the estimation problem of the off-policy value (I) The main result of this section can be summarized as the following non-asymptotic upper bound on the mean-squared error (MSE) of Algorithm [
Theorem 3.1 (Non-asymptotic upper bound on the MSE of the AIPW estimator), For any sequence of estimates (á, (O,-1) (X x A + R)= i [m]} for the treatment effect p", the AIPW estimator
8 has the MSE bounded above by
Ez-
{ AIPW (On)
T {1
1
1
n
g2 (Xi, Ai) (iee (0, 1) (X,, A.) n² (Xi, Ai))² (xt)² (X,, Ai)
(10)
E
n
n
Note that the non-asymptotic upper bound (10) on the MSE for the class of AIPW estimators ( consists of two terms, both of which have natural interpretations. The first term ve corresponds to the
5

---

Algorithm 2 Online non-parametric regression protocol for estimation of the treatment effect.
Require: the number of rounds N.
1: for = 1, 2, ... n. do
2: The learner selects a point Pr (O,-1) E (X A R) based on the sample trajectory O,-1;
3: The environment then picks a loss function 4.()) (X x & + R) - defined as
g² (x),A)) 4(H): : (xt)² (x,, O A.)
(Y, - (X,, A,))² E Ax (14)
4: end for
5: return the sequence of estimates {ū+ (0;-1) E (X x A + R) E [n]] of the treatment effect.
optimal variance
7
achievable by the oracle estimator, and the second term
g2 (X,, Az) (it (O,- (X,, A,) n² (X,, A.))²²
Rx.
(11)
72
(T;)² (X,, 0.
measures the average estimation error of the estimates {í: (0 E (X X - [n]] of Jr" Of primary interest to is subsequent upper bounding argument based the MSE bound (10) in the finite sample regime: in particular, to minimize the RHS of (TO), one needs to choose a sequence
of estimates (i, 10,-)) (X x A IR) : E [n]] which minimizes the second term
3.4 Reduction to online non non-parametric regression
Let us now focus on constructing sequence of estimates (0, (X the treatment effect and upper bounding the estimation error (11) in the MSE bound (TO). To this end,
: [n]] of
we borrow ideas from the literature of online non-parama con-parametric regression
45
To begin with, we consider an n-round turn-based game between the learner and the environment;
Algorithm 2 for the details. Then, can readily observe for any p(:;)) X A IR, we have
Ex- [4(1] (H,-1, X;) A+)l
g² Ai) (m1)² (x,, 0,-;;
(12)
(X,,
-p" -x,,,""",,,,, (X,,
In the current turn-based game, our natural goal is to minimize the learner's 's static regret against the best fixed action in hindsight belonging to a pre-specified function class F C (X x A R):
n 4((H).
Regret F:A) = Σ 4 (A: (0.-1)) inf HEF
(13)
where A denotes the learner's online non parameerii regression algorithm that returns a sequence of estimates (A: (O,-1): E [n]] for the treatment effect. Then, one can establish the following oracle
inequality that demystifies relationship between estimation problem of the off- off-policy value and the online non-parametric regression protocol. See Appendix [B. for the proof.
Theorem 3.2 (Oracle inequality for the class of AIPW estimators). The AIPW estimator 8 using
the sequence of estimates (iz (O.-1) E (x A - IR) i E [n]] of the treatment effect μ produced by the online non con-parametric regression algorithm A enjoys the following upper bound on the MSE:
Ex
( AIPP (O,) - (I
|
(15)
2² Ez- Regret (n, F; A)] + inf [1 p² : :
few remarks are in order. Apart from the optimal variance v2, the RHS of the bound 15 contains two additional terms: (i) the expected regret relative the number of rounds n, where the expected value is taken over O ~ (-) and (ii) the approximation error under the [1-Il(.)- -norm. Given any
fixed function class F C (X x A + R), if we consider the large sample size regime, i.c., the sample

---

size n is sufficiently large, then one can see that the asymptotic variance of the AIPW estimator is asymptotically the same as u.. +inf || -='l E FF. provided that the online non- non- par-mmeraeeic
regression algorithm exhibits no-regrer learning dynamics, i.e. Ez- Regret (n, F:A) = o(n) as n + oc. Consequently, the AIPW estimator (8) may suffer from an efficiency loss which depends on how well the unknown treatment effect μ can be approximated by member of the function
class J - (x x A + IR) under the [1-I(x.)-omm Hence, any contribution to the MSE bound of the
AIPW estimator in addition to the efficient variance v. primarily relies on the approximation error associated with approximating the treatment effect μ² utilizing a provided function class F.
3.5
Consequences for particular outcome models
The main goal of this section is illustrate the consequences of our general theory developed in Section 3|so far for several concrete classes of outcome models. Throughout this section, we consider the case for which Y 1-L, for some constant L (0,+ +o0), and impose the following condition:
Assumption 1 (Strict overlap condition). The likelihood ratios are uniformly bounded by universal constant (0, +oo), i.e., for every i E [n].
(X;, A.) a. (X,, 01-1; A.)
S B
PT- P- -lmost surely.
(16)
We note that Assumption T is often referred to as the strict overlap condition in the literature of causal
inference 20 32 66 336] [1]. At this point, emphasize that Assumption i necessary to produce main consequences the oracle inequality for the class AIPW estimators (Theorem 3.2) that we discuss in the ensuing subsections: Theorems
3.3 3.4
and the arguments throughout Appendix B.6
3.5.1 Tabular case of the outcome model
We embark on our discussion about the consequences of our theory established in Sections 3.3 and 3.4 for one of the simplest case of the outcome model satisfying the following assumption.
Assumption (Tabular setting of the outcome model). The state-action space X x is a finite set.
If we compute the gradient of the loss function
[4] we have
V4(u) = 2g² (X,, A.)
(m*)² O A.) {u (X,, A.) - YJ) &(),))) Vu XXA
(17)
where ((...A)) RRXA is the point-mass vector the i-th state-action pair in the sample trajectory, ie., ((x,,A) 1 if (x. a)= (X,, 6(x.,A)) (2, a) 0 otherwise.
Algorithm 3 Online gradient descent (OGD) algorithm for the finite state-action space.
Require:
the function class F C [- L, L) x the total number of rounds n E N, and a sequence of learning rates (7) E (0, +00) : i E In 1]}.
We first choose an initial point ف (Ø) F arbitrarily;
2: for i = 1,2, ... ,
do
3: Observe a triple (X,, A., Yz) E O:
4: Update iu+1 (O.) E F according to the following OGD update rule:
Pit1 (O,) = 11 [ū (0,-1) n. V4 {A, (0,-))
pu (0.1) (M,) (X,, O;-1;A,) (p: (0,-))- - -Y)) (() ]. = 11
2m, g² (X,, 41)
(18)
where 11 XxA F denotes the projection map of x onto the function space F.
5: end for
6: return the sequence of estimates (fr (0,-1) F :::i : [n] of the treatment effect p²
Now, it time to put forward an online contextual learning algorithm aimed at producing a sequence of estimates of µ" with a no-regret learning guarantee. For the tabular case, the online non- parametric
7

---

regression problem can be resolved through standard online convex optimization (OCO) algorithms. In particular, we employ the online gradient descent (OGD) algorithm (see Algorithm 3 as sub- routine of Algorithm|] By leveraging standard results on regret analysis of OCO algorithms, one can obtain the following regret bound, which guarantees a no-regret learning dynamies of Algorithm 3
Theorem 3.3 (Regret guarantee of Algorithm 3p.
Under Assumptions [and the OGD algorithm
(Algorithm with learning rates
{ 1/k :- ALB2Vi Vi
diami
:E [vl]] guarantees
Regret (ni, F; OGD) S 6LB'ddam(( vn P-.-olmostt surely.
(19)
where diam [F) == sup {1le112 μ E F} denotes the diameter of F FFC-- ! L] X
See Appendix B.4 for the proof of Theorem 3.3 Combining the regret guarantee (99) of Algorithm 3
together with the MSE bound (15) in Theorem 3.2 one can establish concrete upper bound on the
MSE of the AIPW estimator 8 by utilizing Al Algorithm to produce sequence of estimates for the treatment effect 1x".
3.5.2 Linear function approximation
We next move on to outcome models where the state-action space X x A can be infinite. We begin with the simplest case: the class of linear outcome functions. Let o(- X x A Rd be known feature map such that sup {l,([x, a)ll2 (xr, a) E X x A} S 1, and we consider the functions that are linear in this representation: fe -). X A - R. where fo fo a) := 0 o(I a) for some parameter vector 0 E IRd. Given radius R > 0, we define the function class
Fiin == { so(:)) E (X A - R) 0 e (0.; R)
(20)
where B (02; R) == {u Rd ||u|| I RJ. With this linear function approximation framework, let us consider the following OCO model: the i-th stage,
the learner first chooses a point 0 (0,-1) E EO; the environment then picks loss function L((+) O - + defined as
g² (X,,
{Y: -y-0 TT- (x), 10 E
())
(21)
(mt)² (X,, O 1 A.)
and our goal is to produce a sequence of estimates
تui (0. & E Fm : i [m]
for the treatment effect Jr after n rounds of the above-mentioned OCO model which minimizes the learner's regret against the best fixed action in hindsight:
Regret Frin A)
Σ 1 Lūs (O.-))) - inf Σ 4(x) M(F
Σ L, 0; ( (0.
inf
2,( 000)
where A is the learner's OCO algorithm whose output is sequence (0, (0 of parameters. we compute the gradient of the loss function [1]. one has
20² (X,, Ax)
VoL,(0)= (x;)² (X,, A,) {OT o (X,, (x,
A.) Y o Ax)
(22)
For the current linear function approximation setting, we implement the OGD algorithm (Algorithm))
sub-routine of Algorithm[1 [ By using the same arguments in Section 3.5.1 one can reproduce
the following regret guarantee of Algorithm whose proof is available at Appendix B.5]
Theorem 3.4 (Regret guarantee of Algorithm 4p. With Assumption
7 the OGD algorithm (Algorithm
4 with learning rates [T: BL(L : [n]] guarantees
Regret (n, Fin: OGD)= < 6B2 R(L+ + R) Pllmat surely.
(24)
8

---

Algorithm 4 Online gradient descent (OGD) algorithm for linear function approximation.
Require: the radius R. > 0 of the parameter space, the number of rounds N, and sequence of learning rates {77 E (0, +00) : E [n - 1
1: We first choose an arbitrary initial point 0 (2) E O, where é == B (Ous R);
2: for 1, ,
do 3: Observe a triple (X,, A,, Y;) E 00;
4: Update 0.+1 (O;) E è according to the following OGD update rule:
01+1 (O;) ITe (0;-1) " VoCC (0:
(23)
where [e]l:] : Rd + denotes the projection map nd onto the parameter space e.
5: end for
ji: (O.-1)
=(0: : @ Fin i [n] of the treatment effect.
6: return the estimates
General function approximation Lastly, we demonstrate the consequences of our general theory established in Sections 3.3 and 3.44 for the case of general function approximation: the function class F "C x A - L- ZJ) can be arbitrarily chosen. Our further discussion this case heavily relies on the basic theory online non-param parameettti regression from 45] whose technical details are rather long and complicated. So, we defer our detailed inspection on the case of general function approximation
Appendix [.6
4 Lower bounds: local minimax risk
We turn our attention to a local minimax lower bound for estimating the off-policy value 7" = T (T*) Here, aim establishing lower bounds that hold uniformly over all estimators that permitted to know both the propensity scores { (X,, Af) i E [n]} and the evaluation function g. We
assume the existence of constant K 2 1 and reference Markov policies {IL: X - A(A) : [m]]
such that II, (-1x)= < (-) for (x, i) E X [n]. and
ne (x. a)
SK
(25)
K प. (I,0,-1:0)
for all (I, 0,) E 01-1 x A, where ,. (z. dTT.(-a)) A - R, for each context x e X. dAg
Proximity of behavioral policies to certain Markov policies is often assumed under adaptive data collection procedures. For instance, Theorem of (67], the authors assumed that the sequence of behavior policies is eventually Markov; see the equation (8) therein.
4.1 Instance-dependent local minimax lower bounds
Given any problem instance I" (E r** I and error function 8: X A R., we consider the following local neighborhoods:
(E E (X) (3 < 1 ]
NT*)) [T' [X A + A(Y))
((")) (I, s 8(2,a), (xx EXxA),
where for any given r X x A + A (2) a) == fg yr (dyl x a) for each (z, E X X Our goal is to lower bound the following local minimax risk:
(Om) -10))
Mn (Cs (I"))
inf +=(-)00--
Ey IIC)
sup
(26)
+R
where Cs (I") (E*) x N (
CI We now specify some assumptions necessary for lower Prior to this, we introduce new important notation: given any defined on a probability space (R,F, PP., its (2, 4)-moment ratio
bounding the local minimax risk 26
random variable E L (Ω, F.
9
is defined as | 2-44 == B|

---

Assumption 3. Let h(x) == (g( -), (x, x) - Ex~=- (. x- We assumee that
112-4 == || VEx-s 1 (X)
+o0
Rxwe [X)
We next make assumption lower bound the local neighborhood size: Assumption 4. The neighborhood function -(.,))= X x A + R_ satisfies the lower bound
o (z),a) Vn. V (z) ||]]](m))
(27)
for all az), E [n).
We note that Assumptions and are analogues Assumptions (MR) and (LN) considered [2]. respectively, for the of adaptively collected data. Under these assumptions, one can prove the following lower bound on the local minimax risk over C. (I*):
Theorem 4.1. Under Assumptions
3 and 4
the local minimax risk over Cs (I*) is lower bounded by
Mn (Cx (I 2 C(K)
(28)
T
where C(K) >> O is a universal constant that only depends on the data coverage constant K 2 1 of the reference Markov policies (T, A(A) E [n]] defined in (25)
The proof of Theorem 4. can found in Appendix C.I
This result delivers a key message: the term "f including the sequentially weighted f2-norm is indeed the fundamental limit for estimating the linear functional based on adaptively collected data. Our results can be viewed as a generalization
of those developed in 42) for the case of i.i.d. data.
Acknowledgments and Disclosure of Funding
Jeonghwan Lee was partially supported by the Kwanjeong Educational Foundation. Cong Ma was partially supported by the National Science Foundation via grant DMS-2311127.
References
[1] Aman Agarwal, Soumya Basu, Tobias Schnabel, and Thorsten Joachims. Effective evaluation using logged bandit feedback from multiple loggers. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 687-696, 2017.
[2] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013.
[3] Timothy B Armstrong and Michal Kolesár. Finite-sample optimal estimation and inference on average treatment effects under unconfoundedness. Econometrica, 89(3):1141-1177 2021.
[4] Léon Bottou, Jonas Peters, Joaquin Quinonero-Candela, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14(11), 1), 2013.
[5] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, and Whitney Newey. Dabbleddebiaseddeemmmm machine learning treatment effects. American Economic Review, 107(5):261-265, 2017.
[6] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. Double/debiased machine learning for treatment and structural parameters, 2018.
[7] Thomas Cook, Alan Mishler, and Aaditya Ramdas. Semiparametric efficient inference in adaptive experiments. In Causal Learning and Reasoning, pages 1033-1064. PMLR, 2024.
10

---

[8] Jessica Dai, Paula Gradu, and Christopher Harshaw. Clip-ogd: An experimental design for adap- tive neyman allocation in sequential experiments. Advances Neural Information Processing Systems, 36, 2024.
[9] Miroslav Dudík, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. 2014.
[10] Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. arXiv preprint arXiv: 103. 4601, 2011.
[11] Alexander D' Amour, Peng Ding, Avi Feller, Lihua Lei, and Jasjeet Sekhon. Overlap in observational studies with high-dimensional covariates. Journal of Econometrics, 221(2):644- 654, 2021.
[12] Mehrdad Farajtahar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference Machine Learning, pages 1447-1456.
PMLR, 2018.
[13] Nicolò Felicioni, Maurizio Ferrari Dacrema, Marcello Restelli, and Paolo Cremonesi. Off- policy evaluation with deficient support using side information. Advances in Neural Information Processing Systems, 45:30250-30264 2022.
[14] Alison L Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review, 70(3):419-4355 2002.
[15] Evarist Giné and Joel Zinn. Some limit theorems for empirical processes. The Annals of Probability, pages 929-989, 1984.
[16] Vitor Hadad, David Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confi- dence intervals for policy evaluation in adaptive experiments." arxiv e-prints. arXiv preprint arXiv:1911.02768. 2019.
[17] Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence intervals for policy evaluation in adaptive experiments. Proceedings of the national academy of sciences, 11 118(15)) (88(1))e2014660) 201422221111111 18, 2021.
[18] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[19] Tim Hesterberg. Weighted average importance sampling and defensive mixture distributions. Technometrics, 37(2):185-194 1995.
[20] Keisuke Hirano, Guido W Imbens, and Geert Ridder. Efficient estimation of average treatment effects using the estimated propensity score. Econometrica, 71(4): 161-1189, 2003.
[21] Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47(260):663-685, 1952.
[22] Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055 1080, 2021.
[23] Guido W Imbens. Nonparametric estimation of average treatment effects under exogeneity: A review. Review of Economics and statistics, 86(1):4 29, 2004.
[24] Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
[25] Edward L Ionides. Truncated importance sampling. Journal of Computational and Graphical Statistics, 17(2):2953311 2008
[26] Ying Jin, Zhimei Ren, Zhuoran Yang, and Zhaoran Wang. Policy learning" without" overlap: Pessimism and generalized empirical bernstein's 's inequality. arXiv preprint arXiv:22 2,99000 2022.
11

---

[27] Nathan Kallus, Yuta Saito, and Masatoshi Uchara. Optimal off-policy evaluation from multiple logging policies. In International Conference on Machine Learning, pages 5247-5256. PMLR, 2021.
[28]
Nathan Kallus and Angela Zhou. Policy evaluation and optimization with continuous treatments. In International conference on artificial intelligence and statistics, pages 1243-1251. PMLR, 2018.
[29] Joseph DY Kang and Joseph L Schafer. Demystifying double robustness: A comparison of alternative strategies for estimating a population mean from incomplete data. 2007.
[30] Nikos Karampatziakis, Paul Mineiro, and Aaditya Ramdas, Off-policy confidence sequences.
In International Conference Machine Learning, pages 5301-5310. PMLR, 2021.
[31] Masahiro Kato, Takuya Ishihara, Junya Honda, and Yusuke Narita. Efficient adaptive ex-
perimental design for average treatment effect estimation. arXiv preprint arXiv:2002.05308, 2020.
[32] Shakeeb Khan and Elie Tamer. Irregular identification, support conditions, and inverse weight estimation. Econometrica, 78(6):2021-2044 2010.
[33] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4-22, 1985.
[34] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[35] Haanvid Lee, Jongmin Lee, Yunseon Choi, Wonseok Jeon, Byung-Jun Lee, Yung-Kyun Noh, and Kee-Eung Kim. Local metric learning for off-policy evaluation in contextual bandits with continuous actions. Advances in Neural Information Processing Systems, 35:3913-3925, 2022.
[36] Lihua Lei, Alexander D' Amour, Peng Ding, Avi Feller, and Jasjeet Sekhon. Distribution-fre free assessment of population overlap in observational studies. Technical report, Working paper, Stanford University, 2021.
[37] Gen Li and Weichen Wu. Sharp high-probability sample complexities for policy evaluation with linear function approximation. arXivorg. 2023.
[38] Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In Artificial Intelligence and Statistics, pages 608-616. PMLR, 2015.
[39] Roderick JA Little and Donald B Rubin. Statistical analysis with missing data, volume 793. John Wiley & Sons, 2019.
[40] Alexander R Luedtke and Mark Van Der Laan. Statistical inference for the mean outcome under possibly non-unique optimal treatment strategy. Annals of statistics, 44(2):713, 2016.
[41] Cong Ma, Banghua Zhu, Jiantao Jiao, and Martin Wainwright. Minimax off-policy evaluation for multi-armed bandits. IEEE Transactions on Information Theory, 68(8):5314-5333) 2022.
[42] Wenlong Mou, Martin Wainwright, and Peter I. Bartlett. Off-policy estimation of linear func- tionals: Non-asymptotic theory for semi- comi-parametric efficiency. arXiv preprint arXhv:2209.13075 2022.
[43] Yusuke Narita, Shota Yasui, and Kohei Yata. Efficient counterfactual learning from bandit feedback. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 4634 4641, 2019.
[44] Jie Peng, Hao Zou, Jiashuo Liu, Shaoming Li, Yibao Jiang, Jian Pei, and Peng Cui. Offline policy evaluation in large action spaces via outcome-oriented action grouping. In Proceedings of the ACM Web Conference 2023, pages 1220-1201 2023.
[45] Alexander Rakhlin and Karthik Sridharan. Online non- nor-marae regression. In Conference on Learning Theory, pages 1232-1264. PMLR, 2014.
12

---

[46] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 161:111-153, 2015.
[47] Sasha Rakhlin, Ohad Shamir, and Karthik Sridharan. Relax and randomize: From value to algorithms. Advances in Neural Information Processing Systems, 25, 2012.
[48] James Robins, Mariela Sued, Quanhong Lei-Gomez, and Andrea Rotnitzky. Comment: Per- formance of double-robuse estimators when" inverse probability" weights are highly variable. Statistical Science, 22(4):544-555 559, 2007.
[49] James M Robins and Andrea Rotnitzky. Semiparametric efficiency in multivariate regression models with missing data. Journal of the American Statistical Association, 10(429):122-129, 1995.
[50] James M Robins, Andrea Rotnitzky, and Lue Ping Zhao. Estimation of regression coefficients when some regressors are not always observed. Journal of the American statistical Association, 89(427):846-866 1994.
[51] James M Robins, Andrea Rotnitzky, and Lue Ping Zhao. Analysis of semiparametric regression models for repeated outcomes in the presence of missing data. Journal of the american statistical association, 90(429)) 06-121, 1995.
[52] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al. A tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[53] Yuta Saito and Thorsten Joachims. Off-policy evaluation for large action spaces via embeddings. arXiv preprint 20Xiv:2202.06317 2022.
[54] Yuta Saito, Qingyang Ren, and Thorsten Joachims. Off-policy evaluation for large action spaces via conjunct effect modeling. In international conference on Machine learning, pages 29734-29759. PMLR, 2023.
[55] Alex Strehl, John Langford, Lihong Li, and Sham M Kakade. Learning from logged implicit exploration data. Advances in neural information processing systems, 23, 2010.
[56) Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík, Doubly robust off-policy evaluation with shrinkage. In International Conference on Machine Learning, pages 9167-9176. PMLR, 2020.
[57] 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.
[58] Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. advances in neural information processing systems, 28, 2015.
[59] Philip Thomas and Emma Brunskill. Data-efficient off- off-policy policy evaluation for reinforce- ment learning. In International Conference on Machine Learning, pages 2139-2148. PMLR, 2016.
[60] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-29) 1933.
[61] Mark van der Laan. The construction and analysis of adaptive group sequential designs. 2008
[62] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[63] Lequn Wang, Akshay Krishnamurthy, and Alex Slivkins. Oracle-efficient pessimism: Offline policy optimization in contextual bandits. International Conference on Artificial Intelligence and Statistics, pages 766-774. PMLR, 2024.
[64] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evalua- tion in contextual bandits. International Conference on Machine Learning, pages 3589-3597. PMLR, 2017.
13

---

[65] Ian Seuudy-Smithe Lili Wu, Aaditya Ramdas, Nikos Karampatziakis, and Paul Mineiro. Anytime-vall valie off policy inference for contextual bandits. ACM/JMS Journal of Data Sci- ence, 13):1-442, 2024.
[66] S Yang and P Ding, Asymptotic inference of causal effects with observational studies trimmed by the estimated propensity scores. Biometrika, 105(2)4887-993, 03 2018.
[67] Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. In Proceedings the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 2125-2135, 2021.
[68] Ruohan Zhan, Zhimei Ren, Susan Athey, and Zhengyuan Zhou. Policy learning with adaptively collected data. Management Science, 2023.
[69] Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. Advances in neural information processing systems, 33:9818-99999 18-9829, 2020.
14

---

A Some elementary inequalities and their proofs
The following lemma is useful for the truncation arguments used in the proofs of our local minimax lower bounds. In particular, it enables to make small modifications on a pair of probability measures by conditioning on good events of each probability measure, without inducing an overly large change in the total variation distance.
Lemma A.I. Let (H, be a pair of probability measures defined on a common sample space (Ωt, F), and consider any two events A, B E F satisfying min (u(A), v (B) 2 1 - f.for some E [o, 1 Then, the conditional distributions (44[A) (-) E (S2, F) and (v) B) (+) A FD) defined by
11
(AAE) E) ((A)
and (B) = v (Bn B)
(B)
v(B)
for any event E F, satisfy the bound
TV (z) TV (n, m/ S 2e.
(29)
Proof of Lemma A.7 Due to the triangle inequality for the total variation (TV) distance, it follows
that
TV (H, TV (H, TV (VV
(30)
and
+ TV (v|A, S () (V, (V
(31)
At this point, one can easily observe that
TV (1A)) sup
(A)) TV (v, (BB) = sup (E) - (v] (E)
M(A); (32)
u(B) = - =B).
Putting the observation 32 into the inequalities (30 and 31p. the assumptions ((A)= S E and
1 - vBB) < establish the desired result.
B Proofs and omitted details for Section 3
B.1 Proof of Proposition 3.1
First, one can observe that
Ex.
[ (O.)
1
Σ
E
ET-
g (X,, A.)
f: (X;, A.)
T7 (X;, O1-1; Ai)
1=1
(fi (X,, O,-1, 1 (X,, O;-1; 1) (X,, H4-1]]]
1
(X,, A.) nr (Xi, Ai) fi (X,, 4,) + (fi (X,, 0.-1, (X,, 0, -))
E7.
T/ (Xi, O,);;A)
(g, 1r (x) 83 (X,, (X,, A.
Ez.
ET-
(33)
(Xi, 0;-1; Ai)
1=1
+ (fr (X,, O5-1,), (X,, 0;-1;))) 1)x, (4-1)1
/ n² (Xi, a) dA (a) - (fi (Xi, 0,-1,),,) , (Xi, O 11-1:)))
Ez.
+ (fi (X,, O;-1,)), m (X,, O 0):1;)))
=7 (I')
15

---

We now assume 3 and note that
g A,),
Varr-
(O,)
Varz
(x,, O,-1, A1)
n2
T (X,,
O,11;A)
9 g(i,,,,)
n²
COvI.
mi (Xi, O4-1iA4)
fi O(),AA),
(34)
Igi<jEn
(Xj, Tz (Xy, O)-1;Aj)
( 05-1:
One can reveal that
(Xi, Y - f: (X, 0(-1,A)
Varz
!T? (X;, O;-1i A.)
Ex. {
9 (Xi, A,)
- 0.11,
(X,, A,, H, (A.,
-
Ey-
f: (X;
(X,, O,-1;A) As)
(i) Ex. ( (X,, A., H4-1)l
Ex-
(T,)² 2 (X,, 0;-1; Ai)
2 (X,, 0; A,) (X,, Ai)
ET. (X, A, H4 f2 O, Ab) -1
mf (X,, 0;-1; A1)
gº (X,, A,) 0² A.) (T:)) (Xi, O;-1;
Ex-
{{ (g(,,, /1 Ab)
fo (X, (...0.11.11 21
+ Ex-
(35)
Ti (X,, A.)
(T (IT))²
oº (X A.) 0² (Xi,
Ez-
(TT)² (X,, 0,-1;A)
{ gX Ai) 1r" (X,,
+ Ez-
(g (Xi:)) 1 (X6 - (X,, O -1 A.)
7i (X,, O1-15 A1)
Ex-
(X.,)) ), pet (Xa, 139 133
(I
= Varx (X.
g² (X, A1) 0² Ai)
Ez-
(TT)² (Xi, Ai)
{ (9 (X,, As) 1¹ (X,, Ar) mi (X,, O;-1;A,)
Ex-
(g (Xa)), (X;: St (X,, O A.) 1.)
+ Varx~= [gg (X, ,
1e (x,-))
where the step (a) can be verified as follows:
9 XX, A:) nM (X,,
f. (X,, (X,,, (.1,)))))))))
Ez-
प. (Xi, Ai)
9 (X,, Ar) 1e (X,,
(X (i) 12 (X (x
Ez-
Ez-
TH (X,, 0;-1;
(X,,, Ab) 1ta (X,,
Ez-
Varz-
fa 0
(X,,
T/ (Xi, 12-1;Ai)
16

---

9 (X,, Ad) 10" Ax), - fo (X,, O,- (X,,
+ Br-
Ez-
(X,, Hi-11
Tf (Xi, O4-1;A))
9 (Xi, A:) n¹ (Xi,
(Xx-)))x--f(X 0 O Ai) /
Ez-
(X,:))),) (x, Ss (X,,
:i (X;, 01-1: At)
Ey-
(g (X+:)) ;,, 1e (Xs: -3a1
Next, compute Covz-
11. :X:,0:-1:A:) (X,, O,),,4)), a(X,,A,)
x11 (x,,
9 (Xi, Ai), Y;
9 AX,,,
Covz-
- (X,, A.),,
1j (X,, 05- 11 -x,,,,,,,,
T (X,, O;-1; A1)
9 (X2, A.) Y;
ET.
11 (X,, Ai))
T (X;, O;-1; A:)
81 (X,, 05-1, Ai) Oi-,) }1 -
9 (X,, j, A2) nr (X,; Ag)
(T (IT)}²
3j (X,, Oj-1;Aj)
g (X,, Ai) Y;
Ex-
ET-
81 (X,, 0i-1, A.)
(36)
T.. (X,, Oi-1; A.)
9 (X,, A₂) 1¹ (Xi.
11 0x A,-
(X,, - (T())]]
Tj (X,, O5)
9 (Xi, A.) Y,
(X,, 0;-1, A1) (X,,) A (X)))))221 ] - (IT)²
ET-
m3 (X,, 0;-1; A:)
g (X,, A1) Y;
f1 (X,, O 0.-11 (0 (Xgr)) (X),:)) Hz-1 ]] 1--1-tt (o (I'))²
EI-
Ex-
प.. (Xi, O;- Ai)
(b)
0,
where the step (b) holds due to the fact that X, independent of the historical data Hz-1, which immediately yields X,l H X3- E+).. Taking two pieces (35) and (36 collectively into the equation (34). one has
n Varz-
1 (O.))
g A,) (x,,A.)
Varx=s
((0(X,-), 10 (X, ))
+
Ez.
(TT)² (X,, 0,-1,4)
==1
{ g (X,, A:) 1² (Xi, Ar)
(g (X,,), (Xx, - fi (X,, O - (.) A.) 41) }
+Ez-
T. (Xi, 1:-1; Ar)
as desired.
B.2 Proof of Theorem 3.1
We first single out a key technical lemma throughout this section that plays a crucial role in the proof of Theorem 3.1
Lemma B.1. The following results hold:
17

---

[f.(O.) (Xi, (1-)) (g (X), 1e (Xs; (Xx; for all i [n]. There-
(i) It holds that Er. fore, one has
Exz Ti (0.) -Ry- Er. (O.) (Xi, (ii.Hi-i)]]
= -Ez. (o (Xx, ,), 12" (Xx
(37)
-I")
(ii) For every Si < n, we have COVI- (O.),,,, =0:
(iii) For every i E [n]]
Varz- [0:)]
(X,,, A.) 0² (X,, (m²)² (Xi, 0:-1; Ad)
= Va (/ (x, .), , (X, -)) xxx) + Ez-
(X)
+ -Ez- Varz-
(O (X,, A.) 11" (X;, A:) (X,,H-11)
T.. (X,, A;1;;A)
9² (X,, 0² (X,, (m²)² (Xis 0;-1; A.)
< Varx=='
[(0 (xx, ,,, (X,
xx.]
+ Ez-
g² (X,,, (ax (0,- (X,, A.) - 11" A.)) 2
+ Ex-
(m²)² (X,, A;)
(38)
Proof of Lemma B.1 (i) From the definition of f.) 0f - R in 99. we have
(X,, Ad)
Ex.
(o:) (x,, A,, H:-1)
{u² (X,, - A. (X)
a; (X,, 0,
(39)
+ (g (Xi, ) (0:-1) ()x
Thus, we obtain
Ez- (.,( (X,, Ho-i)
Ez. [T. (O:)) (Xi, Ai, Hi- 1)] (X Hi-
Ex-
/ mi (Xa, Oz1iaa))) fP" (X,,a) pa (0.-1) (X, a)) m5 (X,, da)))
(
(40)
(g () (O;-1) (1x
(g (X,,)) p² (X,, Aa
as desired.
(ii) One can reveal that
Covz-
f. (O.). (O.),f,(O,))
= =Ez.
(,,)) E
f, (0,) (X,, A,, H, H|-ر - (- (I+))²
Ez-
(O.)
TJ. (X,, A,) (ur (X,, A,) - A.
(0,-1)
+ (,) Mm 1m (7 (I*))²
(41)
18

---

9 (()),
Ex.
r. (0.) Ez-
(4" (Xz, Ag) - (X,
"ij (X,, --11; A,)
+ (x ). M (0
(X,, Su (Kz,Hz-11) {t (In)}
Ez.
(g (X), (I"
(
where the step (a) holds due to the facts that (O;) is Hj -eeauurbbee and X3 Il. Hz-1, together with the equation 37
(iii) It follows that
Tr (O.)
Varz-
[T.(O)) (Xi, (X., + Varr- Er (O.) (X,; Hi-1)
Ex
Varz-
( Ex.
Ez-
Varz-
[Oi( (X,, A., Ha-)
(X,, Hi-1)]
R-- [Oi) (x,, AG, (x H1-))
+ Pzz-
Vari-
(42)
+ Varxws* ()( m)
g2 (Xi, A,) o² (X,, Ai)
=Er-
(T+)² (X,, O A,)
(Xi,
{u" (X;, A.) A (O,-)) (X,, Ail (Xi, (1
+ Ez, Varz
Ti (Xi, 0;-1; A:)
+ Varx== (g)(X,)), (X, -)x,),,
as desired, where the step (b) follows from the fact (40)
Now, it's time finish the proof of Theorem 3.1
One can reveal that
Ex-
{
AIPW (Onig) - T (I)
[p.(O.:))
Varg-
(b)
g2 (X,, A,) (X,,
Varx~E (X.)) 14" (X, 1) ))xx +Ez.
2
(T;)) (X,, A4)
g2 (Xi, Ai) (u" (X,, A.) - jA (0--1) (Xi, A:))
+IEz-
(Tt)² (X,, At)
9² (X,, A,) (ps (O, (X,, A,) - 4³ (X,, A,)3 (m;)² (X,, Ai)
19
Ey.
where the step (a) holds from the part (ii) of Lemma B. the step (b) makes use of the inequality 388) and the step (c) follows from the definition of e in
B.3 Proof of Theorem 3.2
It holds due to the observation
12 that
Ex-
Σ 4: (0x (O,-
19

---

Rx- Pzz [1 (ig (O.-1)) A.)]
i=1
(X;;
02 (X,, (X;, A.) (Ax (0:-1) - 1i (X,, A:)3²)
ET.
(m²) (X,, 0;-1:A)
i=1
g² A.) {ās (0 (x, 1-" (X,, Ax)
=n 0
E
(n)
(mt) (X,, A,);
i=1
which establishes the following expression of the estimation error term
g (X,, A,) {iz (0,-1)
A.)
Ex
72
(x,)² (X,, O.
1
Er.
Σ
4: (is (0
||o11(m))
(43)
n
1
Ex-
[Regret (n; A)]
1 Ex-
inf Σ 44)):pe : F1
n
1|011
n
n
At this point, one can realize that
Ez-
inf
4(A):
UEF
n
i=
< inf
Ezz Σ k((1)
:EEF
inf
Ex.
Ex- [4(11]] (Hi-1, : M
(44)
inf
Ex
g² ())
(X,, (x) (X, (X..
:
(xt)² (X,, Oi- Ai)
||rl]())
+ inf
[Il 1e (n)) MEF].
where the step (a) holds by the fact
12). Taking two pieces 43 and 44
collectively, follows that
1
y² (X A.) Eas (0 (X,, A.) (X,, A,)3
Ez-
n
(xi)² (X,, 0,-1;A,
(45)
1
Ez-
[Regret (n; A)] + inf |Iua 10--p"pp 11 u MEF].
n
Hence, the upper bound 155 on the MSE of the AIPW estimator 8 is an immediate consequence of the inequality (45) by putting it into the bound (10) in Theorem 3.1
B.4
Proof of Theorem 3.3
One can easily observe from the equation for every μ E that
AX, A.)
Pn.-as.
[V(()) (m+)² (X,, A.):A) (Y, ( A;) S (
(46)
which holds due to Assumption together with the fact Y (- I, L]. So it turns out that the loss 47.3² P.. -ammost surely. Hence, the desired conclusion immediately follows by Theorem 3.1 in [18] with parameter G = 4LB².
function (14) Lipschitz continuous with parameter
20

---

B.5
Proof of Theorem 3.4
One can realize from the equation 22 that P--- almost surely,
Voc,(0)]
(T;) (X, O;)1;A) {o ( A.) -x.] (x,,
4g" (X;,A))
(47)
s 4B' {パУ! |0011 11 (X, 4 110 (X,, A.)12
$ 44 ( R)).
which holds by Assumption 1 together with the facts = -- , L] and (1.())))XXAA | a)ll2 S So, the loss function (2T) is Lipschitz continuous with parameter G == 2B² [ + R) P... -a.s. Hence,
the desired result follows by Theorem 3./ in [8] with parameter G = 2B² + R) and D = 2R.
B.6 Consequences for particular outcome models: general function approximation
Lastly, consider the most challenging setting where the estimation of the treatment effect p p² x A + IR is parameterized by general function classes. Under Assumption | one first observes from the MSE bound (TO) of the AIPW estimator Theorem 3.1 that
Pzz-
{ R
AIPW (O.)
(I'))
1
g² (X,, (Br (0,-1) (X,, A.) 1²" (X1,
E
7
(T/)² (X;, O;-1;A)
(48)
1
B
n
E
(O.-))) A.) p¹ (X Ai))
7
From the last term in the MSE bound (48) our aim becomes control upper bound of the term
(X, n² (X,, A.))
(49)
in the finite sample regime. Towards achieving this goal, we consider the online non-parametric
regression problem described in Algorithm 2 whose sequence (4(-): (X
A +
R)
R
e [m]]
of loss functions defined as (14) superseded by {4(+): (X x A + E) E [m]}. where
Tp(p)) == (Y; (X, A0P (( A (
R x [n].
(50)
It is straightforward to see for every i [ni] that
Ez- [4(44] (H,-1, A.)] = 0² (X,, + {u (X,, A.) - (X,, A.))
(51)
With this modified online non-parann con-paraettric regression problem, we now aim to minimize the learner's modified regret defined follows:
Regret (n. F;A)
Σ 7, (0,-1)) inf Ii():
(52)
where A denotes the learner's online non-parametric regression algorithm that returns a sequence of estimates (it (O,-1) (X A IR): : [n]] of the treatment effect based on interactions with the environment which selects modified loss functions {4(-) (X A R) - [m]]-
Theorem B.1. The AIPW estimator 8 based on sequence [ic
R) : [n]}
of estimates for the treatment effect pº produced by making use of an online non- non-parametric regres- sion algorithm A against the environment which chooses the sequence of modified loss functions
21

---

(4(): (X ([():(xxx
A + :RiEE [n]] defined in (50)
enjoys the following upper bound on the MSE:
Exz A (O..) - T (T')²²
-
2 +
Eg Regrert F;;
n
(53)
n (Xi, -x A.).
(x), =
+
inf
BI-
7
approximation error term.
Proof of Theorem B.1
It follows from the property (11 that
Ex.
Σ (āe (0.-1)3 1)
Ey-
[x
[ (iu
A.]]]
Σ Ez- 02 (X;, A.) + (Ax
A.) - -1- (X,, A.)3
i=1
n
Ex [o² (X,, A.)
Σ Er [1 (O, A.) - n² (Xi, A.))a]
which leads to the following expression of the estimation error term 49
Ex.
[ (X., Ab) - n² (Xi, A.))
n1
n Σ
EE
4 (0.-1)
Ex. [o2 (Xi,
(54)
n1 i=1
Ez.
Reegret An:
+ Ex-
inf > T(()) : MEF
(55)
n
Ex.
[02 (xi,
71
Here, one may observe that
1
Ex-
inf
Σ T(()
n
inf
Ex.
1:(H))
: :
EE [4(H4] X,, AJ]I :REF
inf
Ez-
X1,
(56)
i=1
Ez- (22 (X,, A.) + La (X),A)) - -4" (Xi, (x).)))) : : : F)
inf
1
Ez- [02 (X,, [x) + inf 1 Σ Ez. [[M(X,,A)) Ai) 1² (X..AA)P]:HEt)
k=1
22

---

where the step (a) holds by the fact (5T). Putting two pieces (54) and (56) together yields
1 Ez- (0:1)) (X,, Ad) 1e" (X,,A.))
im1
(57)
1 Er. Regret (n; A)] + inf
1
Br- [(x(X,,))) n² (X,, (.),)))] :
Hence, the desired result (53)
the MSE of the AIPW estimator
( is a strighttfforr wttp:/orrrwrooocnuuuuueeeeee consequence
of the inequality (57) by plugging it into the bound 48)
Here, we remark that aside from the optimal variance v2 the MSE bound (53) shows additional terms: (i) the expected regret relative to the number of rounds n, where the expectation is taken over
On PT. (-); and (ii) the approximation error term whose form is slightly different from the one
inf ||0 n² (l()) : 1 E F} appeared in the MSE bound 15 of Theorem 3.2
Non-asymptotic theory of online non-parametrie regression Before delving into the investiga- tion of the modified regret (52). we briefly recap the main results in 45 that establishes theoretical framework of online non-parametric regression. In contrast to most existing works of online regres- sion, the authors do NOT start from algorithm, but instead directly work with the minimax regret in [45). We will be able to extract a (not necessarily efficient) algorithm after taking closer look at denote an interleaved application of the operators inside
the minimax regret. Let us use {...> > repeated over n rounds. With this notation in hand, the minimax regret of the online non-parametric regression problem for estimation of the treatment effect can be written as
(F)
13
(58)
sup inf (x,, MEI L, y. L.
sup
U 91)²
inf NEF
Σ {a (x)) -y: im1
i=1
where A LJ) is pre-specified function class. One of the key tools in the study of estimators based on i.i.d. data is the symmetrization technique (15)62 Under the i.i.d. scenario, one can investigate the supremum of an empirical process conditionally on the data by introducing Rademacher random variables, which is NOT directly applicable given the adaptive nature of our main problem. In the online prediction scenario, such symmetrization technique becomes more subtle and it requires the notion of a binary tree, the smallest entity which captures the sequential nature of the problem in some sense. Towards achieving our goal in problem, let state some definitions.
Definition B.1.
Let S be a measurable state space. An S-valued tree of depth n is rooted complete binary tree with nodes labeled by elements of the state space S: the sequence s = ($1, $2, ($,,82, ... ..n) of
labeling functions s.(.): {+1)²= - S which provides the labels of each node. Here, E S is the label for the root of the tree, while s, for < i S the label of the node obtained by following the path of length 1 from the root, with +1 indicating right and -1 indicating left. A path of length is given by the sequence Eim = (E1, ... .,,,,, c..) E [=13". Given any measurable function (6-) : R. (()) is an R-valued tree of depth n with labeling functions (ø 8:) (.) {+13²-1 - IR for level i [n]] (or, in words, the evaluation of ((-) : S + R, (ss) on s). Lastly, we let Tree (S, n) denote the
set of all S-valued trees of depth n.
Here, may think of the sequence of functions (s)()) i E [n]] defined the underlying sample space as a predictable stochastic process with respect to the dyadic filtration {a (61:)) : E [r]]- Next, let us define the notion of sequential B-cover quantifies one of the key complexity measures of function class G C (S- - RR) evaluated on the predictable process: the sequential covering number.
Definition B.2 (Sequential covering numbers (46).
ii) Define the following random pseuio-metric between two R-valued trees u = (u [n]) and ( [n]) of depth for any (p, C1.n) +oo] x {+1}".
E lu: (E1.-1) v3 (Ela
i p < too; (59)
d 6i (u, v) =
max [u (C11-1) vi [n]) ifp= +00.
23

---

iii set V S Tree (R, n)) is called sequential 3-cover with respect lo no-nom of S ($ R) on a given s-valued tree s of depth n, where p t0,,
sup {inl { [ vu.v):
(1m) E g(()) x {+1}"} S 3 (60)
where ((s) = {g(s) 9 9) = Tree (R,
(iii The sequential 8-covering number with respect to ly-norm of a function class G C ( R) an S-valued tree of depth n, where p [1, [o0], defined by
NN (B, G) = min (IV) V C Tree (R. n)) is sequential 3-cover w.r.t. 1p-norm of G on s)
Let further define N2 (,) := sup (N₂ (3.9,s) Tree (S, n)) be the maximal sequential B-covering number with respect to lp-norm of G over S-valued trees of depth Now, we will refer to logN, (3, 9, n) as the sequential ( 3-metric entropy of 9 with respect to norm.
In particular, we are going to study the behavior of the minimax regret (F) for the case where the sequential metric entropy of S (X A [-L, LJ) w.r.t (2-norm grows polynomially as the scale 3 decreases:
log No (3. n) B-P for p E (0, +20).
(61)
Let us also consider the parametric "p 0" case when the sequential covering number of JF with respect to 12-norm itself behaves as:
N₂ (2, 8-d.
(62)
For instance, the function class JF := {fe(-) Rd + 0 for the linear regression problem in bounded measurable subset @ Rdd where the function fo Rd IR is given by fo(x) 0
for 0 E HRd satisfies the condition 62 By employing the main results (in particular, Theorem 2) in
45 one can establish the following conclusion:
Theorem B.2 (The rates convergence of the minimax regret). Given any function class F C
(X A L-L,)) with sequential metric entropy growth log N₂ (3,F, n) G- for p E (0, +00),
holds that
(i) for p E (2, +00), the minimax regret
58) bounded
24
V.(F)
<
4
Ln 1 8.
(63)
p
(ii) for E (0,2), the minimax regref 58 is bounded
V.(F) < 321² 4L
24L --p
n 2
(64)
(iii) for p the minimax regret 58 is bounded as
V. < (32L. + 4L+ vn logn.
(65)
(iv) for the parametric case 62 the minimax regret (58) is bounded as
Vx(F) < (161. 4L + 12) dlogn. n.
(66)
(v) if the function class F C (X x A --L, LI) finite set, the minimax regret (58) is bounded as
(x(F) 32L log |F.
(67)
24

---

It is shown in 45] that the upper bounds (i)-(iv) on the minimax regret (58) in Theorem B.2 are tight up to logarithmic factors. See Theorem therein for further details.
Although Theorem B.2 characterizes the rates of convergence of the minimax regret (58) in various scenarios statisttically, its proof is non-constructive in the sense that the regret bounds therein are established without explicitly constructing an algorithm. framework for the problem of online con-parametric regression, we follow the abstract relaxation recipe proposed in [47]. It was shown in [47 that if one can find a sequence of mappings from the observed data real numbers Reln, often called relaxation, satisfying some desirable conditions, then one can construct estimators based on such relaxations. To be specific, we search for a relaxation
order to provide a general algorithmic
Rel, (+-)) +k=
(X A)*
L-
L)*
that satisfies the following two conditions:
Assumption (Initial condition). The relaxation Rel, (.:)) :1o
(Xx
[X X A)
x x
satisfies
Rel, ((x, am N1.1) 2 - inf Σ {ur 1 (x, : EF E
(68)
where (x, a) == ((0g, i (+]) E (X x A.** and Y1.k == (U:iie [b}) E [-L,, 11j* for every
[n].
Assumption 6 (Recursive admissibility condition). The relaxation Rel, (:,-) satisfies
inf sup { (ūx yx)² Rel, ((x, 15 .yik)) S Rel, ((x, a)1k-1 Visk-1), (69) L,44 I.
for any l: [n] and any Th E X.
A relaxation Rel, (-.-) th (Xx A)* x [|- + R satisfying Assumptions 5 and is
said to be admissible. With an admissible relaxation Rel, (:,.) in hand, one can design an a algorithm for the online non -araameettii regression problem with the following associated regret bound (see Algorithm 5 for a detailed description):
Regret (n, F;; Alg.
22
Σ (Y, A. (0+-1) (X,
inf Σ (Yi 1Y-=H(2 (X., Ai)3 :
(70)
Rel, (2, Ø)
We further notice that if the function y/ E [- L + (j 2 Rel, (((x, a) ) (y1:111 1.))).
convex for every (g. X Xin- aim V1--1) E [-,, L] x X x Am x [-L, DJ1-1 and i E [n]. then
the prediction rules (7)) and (72) becomes much simpler, since the supremum over y: [-L, LJ is attained either L or L. The prediction rules then can be written as
Ai (0) a)
arg min { max {
(g- L)² Rel, L), +)² Rel, ((z,a), -)} (()) E E1-
(73)
and for i (2,3. ... m.] ,n..
A (00-0) az)
arg min { maxx { (0 L)) Rel, ((XX,)) (2, (Y ( L))
(74)
( + L)² Rel,, ((X,,)) A) (I, a)) (Y LL)) : E | [}}
One can easily observe that the prediction rules (73 and (74) can be further simplified as
Rel, ((z, a) L) Rel, ((x, a), -L)
(z) a) = XI-L,I1
(75)
4L
25

---

Algorithm 5 A generic forecaster based on the relaxation recipe proposed in 47
Require: a relaxation Reln (..)) Uh=
(x x
A)* x [-L, L1
R.
We first choose (:) (X x
+ R) as
(0 y1)² + Rel, ((x, : vel-L,111
(z)))
sup [1,LL
(11)
2: for = 2,3, n,, do
3: Observe a triple (X,, A4. Y.) E O;
4: We compute P. (0 (-1) E (X + R) according to the following rule:
Nas (Oi-1) (z)a)
E arg min
sup [.]
(0 y:)² Rel, (((X, A (Y w:))} : I-L, L]
(72)
5: end for
6: return the sequence of estimates (á, (0;-1) (X A + :i: [n]] of the treatment effect.
and for i E (2.3,....)
...,... ,n].
A (0;-1)
Rel, A) 1 ((x:,)))- (Y L)) Rel, A) 1x- (Y -D)
= X
4I.
(76)
where x1-2,41() :R - L] defines clip function onto the interval [-L, L). i.e.
i ي;
XI-L.L((x) = x
-
otherwise.
By directly using Lemma 16 in 45
obtain the following significant result:
Theorem B.3. The relaxation R. (:))) Whin (X A)* x
I-I,,
[1]*}
R defined as
Rn ((x, a) lsk V1:k)
sup E =e (2.m)
sup
iALe, {u (E1:511) m, (E1:-1)3
k-
(77)
- -y (z, (E1s)-1)) mm 13}2
Σ - w5} MEF
EF
where the pair (z, m) ranges over the set Tree (X A. n) Tree (R. n), an admissible relaxation. As a direct consequence of the regret bound (70), Algorithm as an input enjoys the regret bound of an offset Rademacher complexity:
Jusinn using the admissible relaxation RR, (::))
Regret (n, F; Alg. 5)
< Rr (Ø, 2)
= sup Uniil (x.m)
sup
ALe, (p(z) (E1g-1)) m, (E1:j-1)}
(78)
(2 (61:)-1)) - my (613-1)3² d E F
26

---

Since the upper bounds on the minimax regret (58) provided in Theorem B. B.2 are established by further upper bounding the offset Rademacher complexity R, (2, Ø), one can end up with the following corollary:
Corollary B.1. Consider any function class F C (X x A --L, L)) with sequential metric entropy
growth log N2 (3, n) -- for p E (0, +00). Then, Algorithm 5 using the admissible relaxation
R,, (:--) defined by (77 as an input enjoys the following regret bounds:
(i) for E (2, +00), it holds that
24
Regret
S
4
Int-j.
(79)
2
(ii) for E (0, it holds that
24L
Regret (n, Fi Alg. 5 S 32L + 4L +
1- pi
(80)
2-
(iii) for = 2, it holds that
Regret (n, F; Alg. 5 <
(32L² + Vog
(81)
(iv) for the parametric case 62 it holds that
Regret (n, Alg.
S (16L² + 4- + 12) dlog n.
(82)
(v) if the function class F
C [X x A + - L, L)) is finite set, it holds that
Regret (n, F; Alg. 327,2 log [F]-
(83)
Even though Corollary B.1 gives no-regret learning guarantees of Algorithm 5 with the admissible
relaxation R,, (:..) defined by (77) for various function classes F C (X x A [-L, it is still
NOT practical algorithm since the relaxation Rr (:: defined as 77 is not directly computable in
general. To address this problem, [5] provided generic schema for deriving implementable online
non-parametric regression algorithms. The schema can be described as follows:
(a) Find computable relaxation Rel, (+--) Ui (x A)* x 1-., R such that
R2 ((x, a) 2. . Y1:k) S Rel, ((x, a) 1 N1.k))
for every (k:, Xi:n; a1::: Vi:a) 10, 1,... m) X n x |- L, LJ", and the function
yk L, (U yk) Rel, ((xx, a) 1.))) (y1:6-1, yk)) E is convex for every (ý, XIm, alm y 1:k E L-L, LJ x x" x A x [-b, 1 and E [n];
(b) Next, we check the following condition:
(Egaware (By [vkd y6)² + Eyrnas [Rel, a) v1.))1]
sup (ex.o..n)eExxxxx((---1 < Rel,, ((x, a): V1:k-1)
for every (Xi:k-1, al:k- y1ck-1) E X A L1, and E [m]:
(c) Implement Algorithm 5 Jusing the relaxation Rel,, (:5-) as an input.
The authors proved that any computable relaxation Rel, (-..) satisfying conditions stated in (a) and (b) are admissible; see Proposition /7 therein. Consequently, any online non con-paraettric regression algorithm produced by the above generic schema always satisfies the regret bound (70). Moreover, the authors established a practical online non-parametric regression algorithm with no-regret learning guarantees based on the above schema for the finite function class C (X x A [- L., I.)) and the
online linear regression problem.
27

---

C Proofs for Section
C.1 Proof of Theorem
Theorem
4.1
can be established by taking the following two lemmas collectively:
Lemma C.1. Under Assumption
the local minimax risk over the class Cs (I*) is lower bounded by
Mn (C8 (I")) 2304
(1
1
Varx== [) (X,
(84)
V2
n
provided that n. Z 16H
Lemma C.2. Under Assumption the local minimax risk over the class Cs (I*) is lower bounded by
|
Mn (Cs (I*)) 2
1
(85)
SK n
C.2 Proof of Lemma
The proof relies Le Cam's two-point method by taking the outcome kernel I* X x A - AYY)
to be fixed, and perturbing the context distribution E-(- E ((X): we first construct a collection
of context distributions (-, (X) : +00) Later, we will choose the parameter s small enough so that E, E N (E*) and two distributions P (s..r") E A (O*) and P .r) ( E A (0") indistinguishable, but large enough such that the functional values (E,, [*) and (E*, r*) well-separated. Le Cam's two-point lemma (the equation (15.14) in (62)) guarantees that the local minimax risk Mn. (Cs (I*)) lower bounded
1 {1 TV TV (Pr..)))PPEr.)
Mn (Co (I')
- (")
(86)
4
provided that E, E (E*).
As the first step, upper bound the total variation distance TV (pm Pinsker-Caiszd--uuubbcc inequality, one has
pm Prs..r))
Thanks the
TV (P... $ KL P
(....))
P
(87)
We can find that the density function of the law P2 under the problem instance given by
(E.,) E (0") of the sample trajectory O (E e with respect to the base measure (Ax @ ds @ Ax) 8n is
1 (On) = P(E,r) (on) = II
LE (xi) m. (rx, 01-1; (36l xi, a:))
(88)
1=1
Using this fact, the Kl.-divergence KI.
pm
Pis..r,) can be computed as
KL
pm
r.)
pd
((-..-))
p
r., (0
= E(E.,r+))
log
p (E))))) (On)
(X,) के (X, 0,-1; X,, E. (X,) n3 (X,, 0,:1:)))4)) (X/ log
= -E(,,,)))
(89)
log Ea (X,)
E
Ex (X,)
(L.
28

---

So if one can show that E, E .V (E*), then the equation 89 guarantees that
KL (PE..r))) P P(s..r)) = n KL |= 1
which can be taken collectively with the bound (87) to produce the following conclusion:
1
TV (PE...y)PPP
(90)
V2
With the arguments thus far in place, it remains to construct a family {E, E 4 : a e (0,+ and then choose parameter such that =, E (E*) and the functional values (E,, r*) and
(=*, (*) are well-separated. To this end, we consider the function h(-)) X - IR defined by
[h(z) h(x) = sign (h(x)) EX-= [x)
h(x)] S 2212-12 Ex-= [}²(X]];
otherwise.
Since H22-4 2 1, one can easily find that [(x)) - [h(x)] for all X. Now for each s E (0, +o0),
we define the tilted probability measure E.(-) E (X) by
{,(r) = dE, (x) = 2(s)
5* (x) exp (sh(zr). Vor E X
(91)
ddx
where 2(s) == 5" (z) exp (sh((r) ddx(2x) = Ex~E= [exp (sh(x))
At this point, we note
for every æ E X that
exp (-s (-s|ib||
hh ) S exp (sñ(x)) s eexp (s (s (.)
(92)
which also immediately yields exp
-ss
h
S B(s) Ex~=- [exp (sh(x)) s exp (s||all))
(93)
Here, we choose 8 [ 0. Then, holds due to the fact | S 2/221 ||
for x E X that
H2-11 (a) 1 2/n
S
S g¹
(94)
4yn [
where the step (a) follows due to the assumption that 2 16H2 Now, it's time to prove that
E, E (E*) for the current choice of the parameter s >> 0. Due to Theorem 5 in [14, it follows that
KL (E. = log (1 + x² (E. })) S (E.1
(95)
So it suffices to upper bound the x² divvereene x² (E, E*). One can reveal that
(X)
(E.1 = Varx~=
(X)
1
Varx (exp (sn(x))
(s)
1
EX,E exp (sh(x)) - 11
(96)
(s)
| Ex [exp 22 (((x))) s2)((x))
exp (2s
- exp
4s
Exas' [x)())),
where the step (b) makes use of the fact (93) together with the elementary bound (exp(u) - 1 s exp (lu)), Vu E R,, and the step (c) follows from the fact [i(x)] S [b(x)), Vo X. we put
29

---

2 v into the bound 9
then we obtain from the fact
S
together with the
basic inequality (95) that
KL (E. (E, 25² 25
(97)
8n
which implies E, E V (E*) for the choice of the parameter $ = 4lth 2 Hence, the upper
bound on the total variation distance (90) turns out to be valid.
Next, we lower bound the gap between the functional values T (E., [*) and 7 (3*,T*) It holds that
(E,,, 1") T (E* Exax, (g(X, ). (X. m)) - (I*)
1 (x) exp (sh(z)) { ((((z, (ar (x, - (I")) dxx
2(5) 8x
h(x))
(98)
1 Exws' ((X) exp (sn(x))
2(s)
Ex-3' [h(X) exp (sh(x))
Ex~E- eex (sh(x))
Since h
S 5. we have sh(X) [- 1. #1 and therefore the simple inequality
1
lexp(u)
u², Vu
4
implies
Ex~=x [x(X) exp (sh(())
Ex~3 [x( +sEx-E [M(X)] [xx)]]]
Ex [M(X))²(()]
sEx=3 [iP(X)] - /Ex== [x2(X)] EEx= [NA(X)]
(99)
- (A2(X))
1 s Ex-E- [x2(X)] 5² 12-14 (Ex~z- [x)(x)))
2
| (
1 122-14
2n
We
16yn
where the step (d) holds due to the fact that sign (h(x)) = sign (h(z)). Vx E X, the step (c) makes
use of the property that [((z)] < [((x)), Yo E X, together with the Cauchy-Schwarz inequality, the step (f) follows due to Lemma in [2]. and the step (g) utilizes the assumption that n 2 16/4.... Putting the lower bound (9 into the equation (98) yields
|| [
( ||
T (=,,
16 TB
exp ss((x))
24
(100)
where the step (h) holds since Ex-== Finally, by taking three pieces (86).
exp ss(())
2. which follows by the fact sx) S $
900 and (T0) collectively, one completes the proof of Lemma
C.I
30

---

C.3 Proof of Lemma
The proof Lemma C.2 is also heavily relies on Le Cam'ss two-point method. For each (1, 8, 2) [n] x (0, +o0) x [ we consider the function (z(2))(..) X A + R defined by
(z(z)) a) = 4² (a, a) + 2sg(a, a)
a.(,,a) ( a), a(z,a) EX
(101)
Also, define the perturbed outcome kernel (zs)
Yas
(2(2)) (-12,a) a) == N (m,(z))(z, a) (z,
Then, due to Le Cam's two-point lemma, the local minimax risk over the class Co (I*) can be lower bounded by
TV Mn (Cs (I*)) 2 { (V Do
(102)
{t (E()),i,(s) 7 (E), (EE,))))))
provided that (=())) E Ns (T*) for E {#1}.
We first upper bound the total variation distance TV Beaker-Csizzzr-Kullbeee inequality, one has
P (E..,,))) P (E.r,-)) By employing the
TV PE- V
KL.
Pm (E (
(103)
The KL-divergence KL
P (PE).TiC))
P ((E.)((-)))
can be computed as
KI. P
(PE
P
(E:...(-)))
Pia)).((s)) (On)
= -
log
((E.I((-s)) (0n)
log E* (Xi) (X, 0,-;; (x) X1, A.)
(104)
E(rr).
(X,, म. (X, 0, (Y xi,
n(s) (Y/l A,) (-(5) (Y X,,
Σ ((TT))
log
Note that
(1)
log
71(-5) ( 2)
(y1 ( ((=) - fy- pil- (2,-s)
(105)
20 a)
sg(=,a) a)
(2y (s)((,) (z,=))
T, a)
By utilizing the fact 105). one can obtain from the equation 104) that
KL
((
P
pa ((E)):(-)))
sg (X;AA)
B(g))())))
{2Y: (2(s=)((s) (X,, A.) mi(-s) (X,, (x, Ph-2))
T., (X1, A,)
i=1
sg A.)
Σ E r.(())
(X,, Ai) {ur(s) (Xi, A.) - (-(-)) (X,, A0)
9² (Xi, Ar) 0² (X,, A:)
2
((r.))))) .I(())
(106)
? (X1, A:)
31

---

g² (Xi, A,) 0² (X,, A.)
=2
Rz-
bे (Xi, Ai)
1=1
22K 82
BT.
(
=2K2 (())
where the step (a) follows by the assumption (25). If put 2k (all(.) into the bound (106).
follows that KI. P (
P ((.))())))
S
So, by combining this conclusion together with
the basic inequality 1003
we arrive at
TV
PE Pa ((-)(()))) S
P
1
(107)
At this point, we should note for every (1, a) [n] {=1} X x A that
slg(1, a) (z a)
1 a) (x(s))(z,aa)
1 l0(2,a))o(
2VK
(nT. (
(108)
(b) 8(I, a)
2/K
W6 6(x, a),
where the step (b) holds due Assumption 4 and the step (c) utilizes the fact that K > 1, which establishes that (zs())) E Nos (I*) for 2 E { and thus the local minimax lower bound (I02 turns out be valid.
Next, we aim at establishing a lower bound on the gap between the functional values (E*, and (3", (-)s)). One observe that
7 (E*,T - -TE,,,,((-))
Ex-z-
H4( (X(-s)(X, x)x
9" (X,, o² (X,, dda (X
2s Ez--
T. (Xi,a) g² (X,,a) (X,,a) daa(aa)
(d) 2s
Ez-
(109)
K
TH (X,, 0,-1;a)
2s
9² (X,, Ai) o² Ax)
E7-
K
(TT)²² [x 1;-1:A)
(X,, A,) 0² (X,, AA)
Ez
K2 K2 (1
(Tt)² (X,, 0 O,-1:A,
where the step (d) holds due to the assumption 25 By taking three pieces (022). (177). and (099
collectively, we have
2 g2 (X,, Az) (x)) Ex.
1)
Mn (Cs (I')) 8K ||m
(110)
(T;)² (X, A,1;AA)
32

---

for every i E [n]. Hence, one can conclude by taking an average of the local minimax lower bound (10) over i [n] that
n Mn (Cs (I"))
Mn (Co (I))
Σ
1=1
1)
1
g² (X,, A.) 0² (Xi, (m;)² (Xi, 0;-1; Ac)
Ez-
8K sk1n2
[|al((m)
1=1
2
(111)
(X, A 0² (Xi,
Ez.
8k*m3 3
|001(00)
(T;)² (X,, 0:-1; AA)
[|all(m))
8K4
where the step (e) makes use of the Cauchy-Schward inequality.
33

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA]
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked use checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No] is perfectly acceptable to answer "[No] providee proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
.
Do not modify the questions and only use the provided macros for your answers.
1.
Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
The abstract and introduction provide good summary of our contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
34

---

Justification:
The main limitation lies in the lower bounds where we assume the existence of sequence of Markov policies that are close enough to the deeeordd behavioral policies.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We provide rigorous analysis of both the upper and lower bounds in paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
We don't have experimental results in this paper.
Guidelines:
35

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
We don't have experimental results in this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
stt.eeesubmmiiioooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https c/tpps.cc/public//uue
CodeeSumiiii wwabbbmmsssiinii ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
36

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: We don't have experimental results in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: We don't have experimental results in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
We don't 't have experimental results in this paper.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
37

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification: We don't 't see any violations.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is mostly theoretical, and is not tied to particular application.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
38

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We give full credit to the prior work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
39

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
40


Reviews:
[{"review_id": "ieBytLd9IQ", "reviewer": "Reviewer_AMTN", "summary": "This paper study the off-policy problem in the sequential decision setting with adaptively collected data. The authors propose to use augmented Inverse propensity weighting estimator to estimate the policy value and conduct extensive theoretical analysis on the estimator, including variance and mean square error. Based on the analysis, the authors propose the methods to learn the function estimator in AIPW estimators.", "questions": "The formulation of  perturbed IPW estimator in section 3.1 seems different with the doubly robust estimator.  Can the authors provide the connection between the perturbed IPW estimator and the doubly robust estimator in other papers. For example, the doubly robust estimators in [1].\n\n[1] Miroslav Dudik, John Langford, and Lihong Li. 2011. Doubly robust policy evaluation and learning. In International Conference on International Conference on Machine Learning. 1097–1104.", "limitations": "I think the discussion of the limitation in the paper is not sufficient.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper comprehensively analyze the property of the AIPW estimator, including the variance and MSE bound. Therefore, I think this is a theoretically solid paper. And the connection between theory and the method is smooth and well-grounded.", "weaknesses": "I am confused about the claim of \"adaptive\" and \"online learning\" in the title. The two words seems that the decision-maker can adaptively select the action during the decision process. However, it seems that the record (context, actions, outcomes) are passively observed in the problem. So I concern that the paper may be mis-positioned.\n\nTherefore, the technical distinction between the sequential decision setting and static setting is not clearly presented. It seem to be a trivial extention of the traditional policy evaluations problem in the static setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments. Below are our point-by point responses to better position our paper and explain our contributions. We hope the reviewer can increase the score if the confusion about the paper and its contributions has been resolved. \n\n1. Re \"I am confused about the claim of \"adaptive\" and \"online learning\" in the title.\"\n\na) Why \"adaptive\" in the title? We focus on off-policy evaluation (OPE): the problem of estimating the value function based on an offline dataset. In OPE, the word “adaptive” means that in the offline dataset, the actions could be adaptively chosen based on previous samples. This is in contrast to OPE with i.i.d. dataset in which actions are drawn depending only on the current context.\n\nb) Why \"online learning\" in the title? We use an “online learning” algorithm (or a no-regret learning algorithm) to iteratively learn the treatment effect function, and then use them in forming the AIPW estimator to solve the OPE problem; see Algorithm 1 in the paper. This is also different from OPE with i.i.d. dataset in which an “offline learning” algorithm such as the empirical risk minimization (ERM) is applied to learn the treatment effect. This gives rise to the term “the power of online learning” in the title.\n\n2. Re \"the technical distinction between the sequential decision setting and static setting is not clearly presented.\"\n\nWe hope the response above has already resolved some confusion about sequential vs static. We expand a bit on the challenge and our contributions here. \n \nWe view OPE as a static decision-making problem as the pre-collected offline dataset is already provided to the learner, and the learner's goal is to estimate the off-policy value. The major challenge here is that the offline data is adaptively collected, that is, in the sequence of observations of the form (context, action, outcome), the actions can be chosen depending on previous data. Focusing on OPE with adaptively collected data, we investigate finite-sample guarantees of the class of AIPW estimators, propose a specific AIPW estimator with a sequence of estimates of the mean reward function learned via an online learning algorithm, and show its near-optimality in a minimax sense. All of these are new to the literature.\n\n3. Re \"The formulation of the perturbed IPW estimator in Section 3.1 seems to be different from the doubly-robust (DR) estimator. \" \n\nThe AIPW estimator (i.e., the DR estimator) is a special case of the perturbed IPW estimator with the collection of auxiliary functions $f^*$ takes form as the equation (5) in our paper, and the treatment effect $\\mu^*$ is replaced by its empirical estimates. This will yield the DR estimator (cf. Eq (1)) in the paper “Doubly robust policy evaluation and learning” by Dudik et al.", "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": "", "extra_scores": {}}, {"review_id": "mqCHJ5mx4Y", "reviewer": "Reviewer_KnWJ", "summary": "The paper investigates the challenge of estimating a linear functional of the treatment effect from adaptively collected data, commonly found in contextual bandits and causal inference studies. It introduces finite-sample upper bounds for the mean-squared error (MSE) of augmented inverse propensity weighting (AIPW) estimators and proposes a reduction scheme to minimize these bounds. The method is illustrated through three concrete examples. Additionally, the paper establishes a local minimax lower bound, demonstrating the instance-dependent optimality of the AIPW estimator.", "questions": "See above.", "limitations": "Limitations have been discussed in the checklist.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-\tThe paper extends the non-asymptotic theory of AIPW estimators to adaptively collected data.\n-\tThe paper provides both an upper bound and a local minimax lower bound on the MSE of the off-policy value, which quantifies the similarity between a given target evaluation function $g$ and the treatment effect $\\mu^*$.", "weaknesses": "-\tAlthough the paper is primarily theoretical, it would be helpful if the authors could include some simulation experiments to verify the theoretical results. For example, it would be interesting to see how the regret converges in practice in the examples of Section 3.5.\n-\tIt would be beneficial if the authors could provide more explanations regarding certain definitions. For example, the off-policy value is defined as the expectation of the inner product between $g$ and $\\mu^*$, rather than, e.g., the expectation of $g$ itself. What is the rationale behind this definition? In addition, why is the perturbed IPW estimator considered over the traditional IPW estimator?\n-\tThe paper has generalized the theory developed for i.i.d. data to adaptively collected data and discussed the technical difficulties in Section 3.2. Could the authors compare the results for i.i.d. data with those for adaptively collected data? Is there any efficiency loss when the data is collected adaptively?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestions. Below are the point-by-point responses. We hope the reviewer can increase the score if the weakness listed in the review has been improved. \n\n1. Re  \"it would be helpful if the authors could include some simulation experiments to verify the theoretical results.\"\n\nWe provided preliminary experimental results to corroborate our theory. Please check the attached PDF file. We mostly followed the experimental set-up in the paper “Off-policy evaluation via adaptive weighting with data from contextual bandits” by Zhan et al. Our DR estimator using an online learning algorithm as a sub-routine performs competitively against other estimators, while at the same time enjoying provable finite-sample performance guarantees. We will add more numerical simulation results to understand the pros and cons of each estimator.\n\n2. Re \"It would be beneficial if the authors could provide more detailed explanations regarding certain definitions.\"\n\n2.1. Our formulation of the off-policy value using the inner product between the treatment effect $\\mu^*$ and the evaluation function $g$ is versatile: As elucidated in lines 109~121 in our paper, our definition of the off-policy value in the equation (1) recovers several important quantities of interest including the average treatment effect (ATE) or its weighted variants and the value function in contextual bandits.\n\n2.2. The perturbed IPW estimator reduces the variance of the standard IPW estimator. This can be observed from Proposition 3.1 in our paper. With a proper choice of the collection of auxiliary functions $f$, the perturbed IPW estimator has smaller variance.\n\n3. Re \"Could the authors compare the results for i.i.d. data with those for adaptively collected data?\"\n\nAs seen from both the upper bounds and lower bounds, the main difference lies in the measure of the size of noises: see the equations (7) and (2) in our paper. In an adaptive data collection model, the weighted $\\ell_2$-norm of the noise depends on time-varying history-dependent behavioral policies, while in the i.i.d. data collection model, the weight is fixed over time and history-independent: see the paper “Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency” by Mou et al.", "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": "", "extra_scores": {}}, {"review_id": "gVLhWFzs1v", "reviewer": "Reviewer_kxx3", "summary": "This paper presents an approach to estimating linear functionals of the reward function in contextual bandit settings from adaptively collected data. They consider the class of augmented inverse propensity weighted (AIPW) estimators and prove guarantees about the quality of the estimator in terms of the quality of the plugin estimator of the mean reward. Specifically, they characterize the finite sample MSE of the AIPW estimator on adaptively collected data. They quality of the estimator (in terms of low MSE) depends on the quality of the plugin estimator of the mean. They relate online learning of the plugin estimator of the mean reward to online non-parametric regression; they then prove a regret bound, where regret relates to the quality of the plug-in estimator learned online.\n\n***edited score based on rebuttal. See comment below***", "questions": "- In line 97, I do not understand why $\\mu$ is called a treatment effect. It is also called the \"reward model\" and appears to be the expected reward function (function of context and action). Why is this called a treatment effect? This is not what is \"commonly referred to\" as a treatment effect in the causal inference literature.\n- In line 107 you state that its assumed the propensities are \"revealed\", does this mean known?\n- Please define << notation used in 117", "limitations": "- A severe limitation of this work (especially compared to previous literature) is that they only provide guarantees about the mean squared error of the AIPW estimator and do not provide any approach to constructing confidence intervals for the quantities of interest. I would expect most people interested in using statistical inference methods on adaptively collected data (especially if data is small enough to warrant using a linear plug-in model or be in a tabular data setting) would care solely about estimation and not uncertainty quantification. As a result, the practical utility of this work is very limited. \n\n- There are no simulations demonstrating their approach in practice or comparing to other methods.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper's presentation is technically precise and seems mathematically thorough. The author's approach of relating the estimation problem online learning seems interesting and creative.", "weaknesses": "- There is significant missing discussion of relevant related work on finite sample approaches for off policy evaluation in contextual bandits. For example \"Anytime-valid off-policy inference for contextual bandits\" by Waubly-Smith et al., \"Off-Policy Confidence Sequences\" by Karampatziakis et al. and \"Optimal and Adaptive Off-policy Evaluation in Contextual Bandits\" by Wang et al., as some examples. I would recommend the authors compare to these papers both theoretically and ideally experimentally as well.\n\n- The main result the authors present that holds for general plug-in estimators of the mean is the derivation of the MSE upper bound for the AIPW estimator (Theorem 3.2) as a function of the \"regret\" of the plug-in estimator error. Beyond this the authors provide results for the plug-in estimators in tabular data settings (Theorem 3.3) and plug-in estimators that are linear models (Theorem 3.4). I feel this is a limited contribution in terms of the types of plug-in estimators the authors can provide guarantees for. \n\n- The main results presented in this work assume that the behavior has a constant exploration rate (Assumption 1). Other works on statistical inference after adaptive sampling generally can prove results when the exploration can decay.\n\n- The writing is technically precise but extremely dense and often lacks sufficient context. I give explicit examples below:\n\n(-) The final result in section 4 was extremely hard to parse. There is a mention of \"mis-specification\" in the section 4.1 title, but then there is no mention of mis-specification anywhere in the section itself. It is not easy to understand how the result presented in that section is related to mis-specification.\n\n(-) There was little discussion as to why the pertubed IPW estimator was introduced in section 3.1, rather than just starting with the AIPW estimator in 3.2 (since there were no examples discussed of the perturbed IPW estimator that were not some version of an AIPW estimator). Furthermore, if the discussion in 3.1 is kept, the connection between these two estimators presented in 3.1 and 3.2 respectively needs to be made more explicitly. For example, explicitly relating AIPW if for a certain choice of $f$ these two estimators are the same.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed reviews. Below are point-by-point responses. We hope the reviewer can increase the score if our responses address your concerns. \n\n1. Re \"There is significant missing discussion of relevant related work on finite sample approaches for off policy evaluation in contextual bandits.\"\n\nThank you for the suggested related works. We will discuss these in our paper. Our main goal is different from the suggested papers. The first two papers focus on constructing confidence intervals (or sequences) for the off-policy value, while our objective is in estimation of the off-policy value. The last paper (which we have cited in the paper) focuses on OPE with i.i.d. data, while our work focuses on OPE with adaptively collected data.\n\nEven if we translate the confidence intervals to prediction (in some way), it is hard to compare theoretically as no specific rate is provided for the confidence intervals in the paper “Anytime-valid off-policy inference for contextual bandits” by Waudby-Smith et al. Nevertheless, their methods are interesting, and we will try to compare our method with them empirically.\n\n2. Re \"The main result which holds for general plug-in estimators of the mean reward function.\" \n\nWe note that our main results (Theorems 3.1 and 3.2) hold in general: Theorem 3.1 holds for any sequence of estimates of the treatment effect, and Theorem 3.2 holds for estimates of the treatment effect resulting from any no-regret learning algorithm. Theorems 3.3 and 3.4 are just two examples (i.e., corollaries) of Theorem 3.2 to demonstrate how to apply the framework of online learning for some concrete classes of outcome models. We also provide results for the case of general function approximation in Appendix B.6 that goes beyond the two examples on the tabular setting and linear designs (i.e., the case of linear function approximation).\n\n3. Re \"The main results presented in this paper assume that the behavioral policies have constant exploration rates (Assumption 1).\"\n\nSimilar to the response above, the strict overlap condition (Assumption 1) is imposed in the examples (Theorems 3.3 and 3.4, and Appendix B.6) of one of our main results---Theorem 3.2. Theorem 3.2 itself is applicable to cases with decaying exploration rates, but for simplicity we didn’t pursue this in this work. We leave this point as future work.\n\n4. Re \"The writing is technically precise, but extremely dense and often lacks sufficient context. \" \n\nThanks for the critique. We will revise the submission accordingly. Here, we give some clarifications on the terminologies “treatment effect” or “mean reward function.” These two terminologies are used separately in two communities: causal inference, and bandits and reinforcement learning. They can be related as seen in line 111 of our paper. This choice of terminology also aligns with a prior work “Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency” by Mou et al.\n\n5. Re \"A severe limitation of this work (especially compared to the existing literature) is that the authors only provide guarantees about the mean-squared error.\"\n\nWe cannot agree with the reviewer on this point. We view the estimation task as equally important as uncertainty quantification (e.g., constructing confidence intervals) from both theoretical and practical perspectives. Moreover, our proposal, the doubly-robust (DR) estimator using an online learning algorithm as a sub-routine, is new to the literature, and practically useful.\n\n6. Re \"There are no simulation results demonstrating their approach in practice or comparing against the other methods in the literature.\"\n\nWe provided preliminary experimental results to corroborate our theory. Please check the attached PDF file. We mostly followed the experimental set-up in the paper “Off-policy evaluation via adaptive weighting with data from contextual bandits” by Zhan et al. Our DR estimator using an online learning algorithm as a sub-routine performs competitively against other estimators, while at the same time enjoying provable finite-sample performance guarantees. We will add more numerical simulation results to understand the pros and cons of each estimator.", "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": "", "extra_scores": {}}]

Author rebuttal:
Please check the attached PDF file for preliminary experimental results to corroborate our theory in the paper.

Meta-review: This is a significant piece of theory work that presents finite sample bound for AIPW estimators. While concerns have been raised regarding related work, clarity of writing and lack of experimental evaluations, all of them have been addressed during the rebuttal period. Therefore I would recommend acceptance.
Decision: Accept (poster)