Estimating Optimal Policy Value in Linear Contextual Bandits Beyond Gaussianity
Authors: Jonathan Lee
Weihao Kong
Aldo Pacchiano
Vidya Muthukumar
Emma Brunskill
Venue: Accepted by TMLR ()

Abstract: In many bandit problems, the maximal reward achievable by a policy is often unknown in advance. We consider the problem of estimating the optimal policy value in the sublinear data regime before the optimal policy is even learnable. We refer to this as $V^*$ estimation. It was previously shown that fast $V^*$ estimation is possible but only in disjoint linear bandits with Gaussian covariates. Whether this is possible for more realistic context distributions has remained an open and important question for tasks such as model selection. In this paper, we first provide lower bounds showing that this general problem is hard. However, under stronger assumptions, we give an algorithm and analysis proving that $\widetilde{\mathcal{O}}(\sqrt{d})$ sublinear estimation of $V^*$ is indeed information-theoretically possible, where $d$ is the dimension. We subsequently introduce a practical and computationally efficient algorithm that estimates a problem-specific upper bound on $V^*$, valid for general distributions and tight for Gaussian context distributions. We prove our algorithm requires only $\widetilde{\mathcal{O}}(\sqrt{d})$ samples to estimate the upper bound. We use this upper bound in conjunction with the estimator to derive novel and improved guarantees for several applications in bandit model selection and testing for treatment effects. We present promising experimental benefits on a semi-synthetic simulation using historical data on warfarin treatment dosage outcomes.

Published in Transactions on Machine Learning Research (2/2024)
Estimating Optimal Policy Value in Linear Contextual Bandits Beyond Gaussianity
Jonathan N. Lee Stanford University
jnlöstanford.cm edu
Weihao Kong Google Research
weilaooknng@ggongl.ccom
Aldo Pacchiano Boston University
pacchion @bu. edu
Vidya Muthukumar
wmadhukkmar3Sgaaeehh.. edu
Georgia Institute of Technology
Emma Brunskill
ebrun @brun@cs.sttnfoor.ccm edu
Stanford University
Reviewed on OpenReview: https: // openrevee. net/ forum? id= IDU87
Abstract
In many bandit problems, the maximal reward achievable by a policy often unknown in advance. We consider the problem of estimating the optimal policy value in the sublincar data regime before the optimal policy is even learnable. We refer to this as V estimation. It was previously shown that fast V estimation is possible but only in disjoint linear bandits with Gaussian covariates. Whether this is possible for more realistic context distributions has remained an open and important question for tasks such as model selection. In this paper, we first provide lower bounds showing that this general problem is hard. However, under stronger assumptions, we give an algorithm and analysis proving that O(Vd) sublincar estimation of V* is indeed subsequently introduce practical and computationally efficient algorithm that estimates problem-specific upper bound on V' valid for general distributions and tight for Gaussian context distributions. We prove our algorithm requires only Ö samples to estimate the upper bound. We use this upper bound in conjunction with the estimator to derive novel and improved guarantees for several applications in bandit model selection and test- ing for treatment effects. We present promising experimental benefits on semi-synthetic simulation using historical data warfarin treatment dosage outcomes.
thweaaaiiio---eoeiiilllllll possible, where d is the dimension. We
1 Introduction
Classic paradigms in multi-armed bandits (MAB), contextual bandits (CB), and reinforcement learning (RL) consider a plethora of objectives from best-policy identification regret mininization. The meta-objective is typically to learn an explicit, near-optimal policy from samples. The best achievable value by a policy in our chosen policy class, typically denoted as the optimal value V is often unknown ahoad of time. This quantity may depend in complex ways on the nature of the context space, the action space, and the class of function approximators used to represent the policy class. In many applications, the impact of these properties and design choices is often unclear a priori.
In such situations, would be useful if it were possible to quickly estimate V and assess the target per- formance value, in order to decide whether to adjust the problem specification model before spending

---

Published in Transactions on Machine Learning Research (2/2024)
valuable resources learning to optimize the desired objective. For example, prior work that used online policy search to optimize educational activity selection has sometimes found that some of the educational activities contribute little to student success (Antonova et al. 2016). In such settings, if the resulting performance is inadequate, knowing this early could enable a system designer to halt and then explore improvements, such as introducing new actions or treatments (Mandel et al.] 2017), refining the state representation to enable additional customization (Keramati & Brunskill, 2019) or exploring alternate model classes. These efforts can change the system in order to more effectively support student learning.
A related objective is the problem of on-the-fly online model selection in bandit and RL settings Fostee From theoretical perspective, a large number of recent attempts at model sclection leverage type of V**estimation (or closely related gap estimation) subroutine (Agarwal et al., 2017 Foster
ctt al.
2019).
some
jet al. 2019: Chatterji et al., 20200 Pacchiano et al.) 2020b; Lee et al.) 2021). In particular, Lee et al.
p show that significantly improved model selection regret guarantoes would be possible if one could hypothetically estimate V faster than the optimal policy. Despite these important practical and theoretical implications, the amount of data needed to estimate V* is not well understood in real-world settings. A naive approach would be to attempt to estimate an optimal policy from samples and then plug-in an estimate of V*; however, this may necossitate a full algorithm deployment and a prohibitive number of samples in high-stakes applications.
(2021)
In this work, we pursue a more ambitious agenda and ask: is it possible to estimate the optimal value V faster than learning on optimal policy? Prior work suggests that this is surprisingly possible but only in a quite restricted setting: Kong et al. (2020) show that, with disjoint linear contextual bandits with Gaussian contexts and known covariances, it is possible to estimate V accurately with only Ö(K Vd/e)) samples, substantial improvement over the Ö(d/e²) samples required to learn a good policy in high dimensional settings (Chu et al. 2011) Unfortunately, the strong distribution assumptions make the Gaussian-spociffc algorithm impractical for many scenarios and inapplicable to other theoretical problems like model selection that deal with much richer distributions.
The purpose of this work is twofold. (1) We aim provide an information-theorrtie characterization of V estimation for linear contextual bandits under much more general distributional assumptions that are more realistic in practice and comparable to typical scenarios of online learning and bandits. In particular, we aim to understand under what conditions sublinear V estimation is and is not possible. (2) We aim to devise practical mothods to achieve sublincar estimation and in turn realize significant improvements in problems such as model selection and hypothesis testing.
1.1 Contributions
As our first contribution, we make progress towards an information--heerrlicc characterization of the V estimation problem (Section 3.2 We prove lower bounds showing that, without structure, cannot hope to estimate V accurately with sample complexity smaller than Q(d) in general. Despite this, our first major positive result (Algorithm and Theorem D shows that V estimation with sample complexity that scales as vd is still infornatiio--hhoreticlll distributional assumptions when lower-order moments are known. In particular, we give an algorithm that achieves ((20k//vd//) sample complexity While the bound is not without undesirable features owing the exponential dependence on -1 and CkK, the significance of the result lies in the proof that estimating V* is possible in the sublincar regime in d. In particular, suppose that K is constant (small) and is constant larget accuracy. Our result shows that the number of samples needed to gel the desired fixed targel accuracy scales with only the square root of the problem size d, meaning that sometimes we may need fewer samples than there are parameters to achieve constant accuracy. This is in contrast to a naive plug-in approach of trying to estimate directly, a guarantee that requires the number of samples to be at least d to say anything non-trivial.
possible beyond the Gaussian-context setting given some mild
Herr, Ö omits polylogarithmic factors and lower order terms. d is the dimension, is the target accuracy, and K is the number of actions.
2C2 is constant that depends only K see Corollary 3.5 for details. For all intents and purposes, we will consider this bound only when K and are constant, (e.g. 2 and O.T).
2

---

Published in Transactions on Machine Learning Research (2/2024)
Our second key contribution is a computationally and statistically efficient algorithm that estimates informa-
tive upper bounds on V* with sample complexity ((va/e)) (Algorithm 2 and Theorem 2 This algorithm avoids the exponential dependence and holds with weaker requirements.
We first leverage upper bounds on V to tighten the bandit model selection guarantee of Foster et al. (2019) in the large-action setting from O(K1/3) to O'Vlog K) (Theorem 3). Second, we show that upper bounds on V can be used to develop provably efficient tests for treatment effects to decide whether we should expand our set of treatments from www-sstae--bttliimiie
set, to a more ambitious treatment set that may be costly to implement (Theorem 4 and provide experimental evidence on synthetic domain and on semi-synthetic simulation using historical data on warfarin treatment dosage.
1.2
Related Work
One can show (sce Proposition A.1 that in the MAB setting, estimating V is no casier than solving best
arm identification task Bubeck et al.
(2009);
Audibert et al. (2010); Gabillon et al.
(001))
Karnin et al.
2013
Jun et al.
20166
: Even-Dar et al.
(2006);
Maron & Moore (1994): Mnih et al.
2008
Jamieson et al.
(0014:
Katz-Sammell & Jamieson (2020) In the linear setting (Hoffan et al. 2014 Soare et al. 2014]
Karnin 2016 Tao ct al.] 2018 Xu et al. 2018 Ficz et al.] 2019 Jodra & Prouticre 2020 as well as in the
non-disjoint linear contextual bandit setting (Chu el. al. 2011). there is signilicantly more shared structure
across actions: all the unknown information in the problem is encapsulated in one unknown, d-dimensional parameter. Surprisingly little work has been spent on estimating V* even though we do know that certain functionals of the unknown parameter, such as the signal-to-noise ratio (Verzelen et al. 2018 Dicker 2014
Kong & Valiant 2018) are estimable the fast Ö ) rate. The V cssimattin problem was first proposed
by Kong et al. (2020) who showed estimation is possible with Ö - samples. However, the algorithmic tools are highly specialized to Gaussian context distributions. Thus, we require novel approaches to handle
Ō(vāK)
more general context distributions. We are able to show that V estimation is possible under significantly
broader distribution models with many practical implications.
A particularly critical application of V* estimation arises in online model selection in CB. Multiple approaches to model selection make use of estimators of V to weed out misspecified models (Agarwal et al.] 2017 Lee
2021 Pacchiano et al., 2020a Foster et al. 2019: Chatterji et al. 2020: Pacchiano ct al.] 2020b Lee et al.
ct al.
2022a bj Muttuukunar & Krishnamurthy 2022 Ghosh et. al.) 2021] In our current work, we leverage
our faster estimators of V to improve the model selection results of Foster et al. (2019) in the linear CB
setting. Our more sophisticated approaches to V cstimation imply logarithmic O OVylog K) scaling on the leading term in the regret, exponentially improving upon the OK11/3) of the original work.
2 Preliminaries
Notation. We use = (l....,, for n E N. For any vector V E Rd, |||||| = ||ll/2- For any matrix M E Rdxd || denotes the operator norm and || p the Frobenius norm. When M 2 O, [|u]la == vo Me. We denote the d-dimensional unit sphere s {u Rd ||||| = =}. We call ((v)) the set of s-combinations of [n] and use the symbol Ta to denote the d x d identity matrix. We use C, Ci, C2.... to refer to absolute constants independent of problem parameters. Throughout, we use the failure probability 8 < l/e. The inequality a S. b implies a S cb for some constant. C C>0 O. For a random variable Z, we denole the variance as var(Z) and || == 2 Z is said to be nub-Gaussian if there exists > 0 such that E |/]p//// < LovD for all 2 1 and we define || as the smallest such a: |2 == supp21 1 p------ 1/2g [|2/1)// We also use Z subG(a²) to denote that || aa. A random vector Z is sub- Gabb-Gassiinn if there exists such that |Z := sup |l (Z,u) ll a.
Setting. We consider the stochastic contextual bandit problem with a set of contexts X' and a finite set of actions A= = [K] (with K = |Al). At each timestep, a context-reward pair (X,, is sampled i.id from a fixed distribution D, where X, E X' and Y, E K is a reward vector indexable by actions from A. Upon sceing the context Xz, the learner chooses an action A, and collects reward (A)). Let r r"(x," a) = E( and let, xt be the optimal policy such that n" (Ir) arg max r" (2.
3

---

Published in Transactions on Machine Learning Research (2/2024)
The quantity of interest throughout this paper is the average value of the optimal policy, defined as
V = EY Ex maxue r" (X
(1)
For an arbitrary policy т X + A, we define v E (x))). A typical objective in contextual bandits is to minimize regret (egr("1:2) = Eietry V' V While our focus will be estimation of the quantity V*. we will consider the regret problem in applications of our results (Section 4.1
We restrict our attention to the linear contextual bandit, which is well-studied sub-class of the general setting described above (Auer 2002 Chu et al. 2011 Abbasi- Yadkori et al. 2011). We assume that there is known feature map Φ X'xAA + Rd and unknown parameter vector 0 E R such that r"(xxa) a) = (Ø(x, a), 0) for all x E X' and a E A. As in standard CB settings, we consider the case where |x] is prohibitively large (i.e. infinite) and d < | but d can still be very large (e.g. on the order of T). As is standard, we assume that the noise v/aa= == (a) (X,)) a) is independent of X and sub- with || S = ((1, and the features o(X, a) are Gau-Gaussiaa with (O(X,))lle === O(1). We will assume that B[o(X, a)] for any fixed E A. For the results of Section B. this is easily relaxed; however, for Section 4 there are a number of potential ways to deal with non-zero mean arms that may be lead to varying degrees of approximation error. We maintain mean zero for simplicity and defer further discussion to the relevant sections. Finally, in order
to enable non-trivial results (see justification in Section 3.1 we will consider well-conditioned distributions.
A Assumption 1.
The covariance matrices given by En == Ex (Xx)) and
o(x, En.'' = Ex -(x, (Ø(X. -
o(x,a'))
for a F a' are known. The minimum cigenvalue of the average covariance matric of all actions E [K] is bounded below by a positive constant Amin (E) 2 > 0 where Σ = K Ene(K] La.
The assumption that the covariances are known is made for simplicity of the exposition, as many of our results continue to apply if the covariances are unknown but there is access to O(d) samples of unlabeled contexts X, which allows for sufficiently accurate estimation of the necessary covariances. We provide thorough details F This is common in many applications where there exist data about the target context population (such as customers or patients), but with no actions or rewards e.g. in bandits (Zanette et al.) 2021 Kong et al.] 2020) and active and semi-supervised learning (Hanncke) 2014] Singh et al. 2008). Interestingly, for our model selection results, no additional unlabeled data required at all (sce Theorem 3 and Appendix D.1
and derivations of this extension in Appendix
3 Information- Theoretic Results
Our first order of business is to make progress towards sample complexity characterization of the formal V estimation problem. We are interested in understanding under what conditions it is possible to achieve sample complexity that scales sublinearly as vd in an infornationn-teorrtie sense. Kong et al. (2020) showed that Q(Kvdfe) samples were necessary even in the Gaussian case, but our general setting is a major departure from their work. We will find that in general the lincar structure and well-conditioning (Assumption [ are essentially necessary to avoid linear dependence on d. We will then move on to our first major result, a moment-basod algorithm that achieves O(2kk/<V//c) sample complexity, resolving affirmatively and constructively the question of whether sublinear estimation in d is information--hhoretiillll possible in these general distributions.
While the exponential dependence on c- is undesirable and we ultimately provide more practical approx- imation in Section 3 we believe the sample complexity result of this section is important to characterize for two reasons. (1) The results provide first steps a characterization the exact problem of estimating V' to arbitrary accuracy rather than approximations of it. (2) The algorithm and thcorem serve as theoretical evidence that sublinear estimation of V* is possible in the first place. Prior to this, it was not clear whether this was possible, regardless of dependence. This can serve stepping stone towards improved analyses.
4

---

Published in Transactions on Machine Learning Research (2/2024)
Algorithm Moment-Based Estinator
Input: Number of samples n, failure probability 6, degree t, coefficients {ca (oals of polynomial approx- imator Pt-
2: Define = 48 log 1/6), m ". initialize empty datasets D D D
3: Whiten features with o(.) = > -/26(())
for h ......... . do
for i= ,...,... do
Sample independently of D and at ~ Un. Receive reward vf-
Set of = o( ((xf.a0 )
8: Add tuple (of v to D
9: end for
10: end for
11: for a such that 8 8 |a| S l
12: Compute independent moment estimators Ak :.:
gk m,a
=
Ex
( (x o( ((x,
(2)
(m)
(E(!ml)
sc(s)
13: Set Sn, median(S 1
14: end for
15: Return S. = Ea lalse Co Sn.a.
3.1 Hardness Results
A natural starting point is the classical K-armed bandit problem where r"(x,, a) is independent of (and for this part only we assume that the means are non-zero). It. not immediately clear whether one can estimate V with better dependence the bandit must also be learnable. See Appendix A for formal statement. Proposition 3.2 shows M(d) samples necessary for linear contextual bandits when Assumption is violated.
either K or Proposition 3.1 implies that, for V to be estimable,
Proposition 3.1. [informal] There exists a class of K Karrmed bandit problems such that any algorithm that returns an c-optimal estimate of V* with constant probability must use ((//e²) samples.
Proposition 3.2. There exists a class of linear contextual bandit problems with @ X x A + Id and 2 d such that Assumption is violated and any algorithm that returns an c-optimal estimate of V with probability al least 2/3 must use M(d/e²) samples. Under the same assumplion, there exisls class of problems with K 2 ond an absolute constant c, such that any algorithm that returns c-optimal estimate of V with probability at least 2/3 must use Q(d) samples.
These lower bounds suggest that, without more structure, V estimation is no easier than learning the optimal policy itself. One might wonder then if a sublinear in d sample complexity is possible at all without a Gaussian assumption. In the following section, we answer this affirmatively.
3.2 A Moment-Basse Estimator
We present, to knowledge, the first algorithm that achieves sublinear sample complexity in by leveraging the well-conditioning of the covariance matrices (Assumption D. We remark that the method of Kong et al. (2020) crucially leveraged a Gaussian assumption which meant the problem could be specified solely by a mean and covariance matrix, thus easing the task of estimation. Such steps are unfortunately insufficient to generalize beyond Gaussian cases, where we are likely to be dealing with distributions that are far more rich than what can be specified by a covariance matrix alone. These limitations motivate a fundamentally new approach, which present here.
5

---

Published in Transactions on Machine Learning Research (2/2024)
We present the full algorithm for V estimation with general distributions in Algorithm I The main idea is to first consider Ith-order K-variate polynomial approxination of the K-variate max function, and reduce the problem to estimating the expectation of the polynomial. We define such an approximator generically as in the definition to follow.
As an important note, while we will state all bounds terms of to explicitly showcase dependencies this section, we will generally assume K small or constant when discussing the significance of results.
Definition 3.3. Consider a t-degree polynomial Pt [-1, + R written as pe(2i....,,2k) Ejaret Ca [LoE[K] 2q where: z E [-1,1]K, a a multiset given by a (ok for as E N, and we denote |a| = =ueik]] Ota- We say that Pt is a (C, (mux))-ollymomia approzimator of the K-variate max function on a given CB instance if it salisfies the following conditions:
=x(x)H S where za - (6, ((x,)2)))) and 2. |cal S Cmax for all mullisets a with la] S.
1. suPzex ())
-
Many such polynomial approximators exist and we will discuss several examples shortly with various trade- ofls. Algorithm D proceeds by estimating the quantity Ex ([, Φ(X, a)) which is guaranteed to be Ç-close to V if Pt satisfies Definition 3.3 We achieve this by estimating individual a-moments between the {(0, ()),((X))))ee JaEA random variables using Equation
2 The intuition is that there are (ja) ways to
construct independent unbiased estimators of f in a single term. This step turns out to be crucial for the proof as we show that only sublinear in d samples are sufficient to get accurate estimation of each S, (Theorem 5 in Appendix B). This follows from a novel variance bound on the individual estimators (Lenuna B.1 Before proceeding, we state several technical assumptions specific the guarantee of this estimator.
Assumption 2. There erists a constant I, > 0 such that for any u; u E Rdd
E ())
s L. [(0(x, R ((b(X,)),
for all A. Assumption 3. For all a E and x E X, it holds that (d(x, a) E 1-1,1
Assumption [ which also made in linear regression (Kong & Valiant 2018 is a Bernstein- like condition which says that the fourth moments are controlled by the second moments. However, it is milder as we do not require all moments to be controlled. It can also be easily shown to follow from standard hypercontractive conditions (Bakshi & Prasad 2021 Assumption 3 is simple boundedness assumption that is almost universal in bandit studies. We furthermore assumee that all moments up to degree t of (ø(X, -), v) for any E 1 are known or can be computed. Such knowledge could come from large collection of unlabeled or non con-interaction batch data (as we demonstrate in Section 4.1.2). Our main technical result of this section, stated below, shows that it is indeed possible to estimate V to accuracy up to the polynomial approximation with sample complexity that scales as Vd using Algorithm 1
Theorem 1. Let Assumptions let S. be the output of Algorithm Suppose that n 2 1o10g(1/ There is a constant C > O, depending only on T, a, and L, such that with probability at least i(ett K + +e) e)K5, -V-S,, is bounded by
and hold. Let Pt be a t-degree (S. -poyyooool approzimator and
Ç Cmaxt (et/ K + e)* K E._ (ce'va log(1/8)) 8/2
The crucial aspect to note in the bound of Theorem I is that d only appears in terms that are polynomial in va in costrast to the typical d n rates required for estimating 0 itself or learning the optimal policy (Chu et al. 2011). h. As we will see in examples, this readily translates to a sample complexity bound whose dependence
NNot that in 22 for the multiset a of size = |a| and j E [s), we use ag) to mean the action azy) = max(a' : Eveo S
1). That is say, considered the tuple (6(X, 1)...,,.((.)) 1), (x,2)). 2)..... o(x,)) 2).................. ((X, K)) where &(X, a) is repeated Gg times, o(X agy) refers the jth element of this tuple.
6

---

Published in Transactions on Machine Learning Research (2/2024)
on d is only vd and dependence on and K depends the instantiation of the polynomial approximator Pt Another interesting observation is that, as far as estimation error is concerned, we have avoided exponential dependence on f, which is an easy pitfall because the variance of monomials can easily pick up order (22²). Here, this is avoided as long as n 2 / VVloo(1//)) which makes cach term in the summation less than 1 and thus they are smaller for larger E [4] The factor 1/ne/² acts as a modulating effect for any lerms that also pick up exponential in 2 dependence. Our solution to this is one of the primary technical novelties of the proof and is a critical consequence of Lemma B.1 This makes Theorem | & fairly modular result: we may plug-in polynomial approximators to observe problem-specific trade-offs between Ç and Cmax.
We will now use Theorem 1 to prove that it is indeed possible to estimate V in the unlcarnable regime with sample complexity sublinear in d in general cases. Specifically, it is possible to estimate V* even when d > n, iee for nigh-dimensional problems. We do this by instantiating several example polynomial approximators. We start with the most general version of this result, which does not rely on any additional structure in the bandit problem beyond what's needed in Theorem 1
Example 3.4. Consider a generic contertual bandit satisfying the assumptions of Theorem 7 There crists a t-degree polynomial approzimator PL (named after Bagby et al. (2002)) satisfying Definition 3.3 with
Sx and Cmax = (2et)2X41221 where CK is a constant that depends only on K (see Lemma B. for a formal existence statemenl).
Ç ==
KK
Corollary 3.5. The estimator Sn generated by Algorithm 1 with polynomial pf salisfies IV Sal S for c << with probability at least 1 - 6, t = =20k/e, and sample complenity
( CK Ke
K
KVd llog
Ck co
o
20x2..
Corollary 3.5 has only a vd dependence in the sample complexity of the estimation task, showing sublinear Vd sample complexity is possible in the unlearnable regime when d >> n, broader set of situations. The exponential dependence on e1, K, and Cg is undesired, but still illustrates that interesting behavior is possible. In particular, consider the case where K and 6- are constant (and thus CK is also constant) such as K- = 2 and e = 0.1. Our result suggests that, for large d, it is possible to estimate V* to within 0.1 accuracy in fewer samples than there are parameters. Recall that a plug-in estimator would require at lenst d samples to achieve a non-trivial guarantee even if K and -1 are constant. An alternative view is to consider the asymptotic regime, as n + 0o, in which we require only that vd/n + ensures convergence in probability, while classical bounds would require that d/n- +
One might wonder if K and e1 dependence can be substantially improved while maintaining the same level of generality. One possible solution is to ask if a better polynomial approximator exists since Theorem 1 should be sufficient as long as Cmax and Ç can be properly controlled in Definition 3.3 Unfortunately, for the most general polynomials it is well-known that the 2 order of Cmax is essentially tight even for K = 1 (Markov 1892 Sherstov] 2012). While we conjecture that this is in general unimprovable, it remains an important open question to understand. The intuition developed here may serve as possible stepping-off point for future work to resolve it.
Despite exponential dependence in this most general setting, can actually achieve much stronger results by employing better polynomial approximators in interesting special cases. Our next example shows that certain contextual bandits can be handled by special case polynomials that have tighter bounds on the coefficients. In this case, we have sublinear Vd dependence and purely polynomial dependence on 1/e which comes as a result of the refined polynomial approximator.
Example 3.6. Consider a CB problem satisfying the conditions of Theorem where 0 E Rd is vector of all zeros except at some unknown coordinate i, where tg, = w E [-1,1] and |ea| = =1(1). Furthermore, (x a) E (-1,0, 1}, where &² denoles the ith coordinate of &, and for each (i, (i, a) luple, there is another a' such that Φi (a, a) = - (x, a'). Then, there exists a K Kdeegre polynomial bēn satisfying Definition 3.3 on this instance with Ç =0 and Cmax = -w|-K
Corollary 3.7. On the class of problems in Example 3.0 Sn with pk bin satisfies V - -Sal S e for < 1 with probability at least 1 - a and sample complexily O K822K va +/4
log ( (2x)

---

Published in Transactions on Machine Learning Research (2/2024)
Estimatioo Error
07
Approx
LR-reg
03
Moment
0.
Samples
Figure 1: Estimation error of Algorithm (Moment) is shown in red simulated high-dimensional CB domain with d 300. The blue dashed line (Approx) represents the bias due to the polynomial approximation. Moment greatly outperforms plug-in baselines (LR in orange and LR-reg in green). Error bars represent standard error over 10 trials.
Numerical Experiments. While the results of this section are meant to be purely ietommmtion-thhoretee we investigate its practical efficacy to provide a deeper understanding. Exact details can be found in Ap- pendix H We consider a simulated high-dimensional CB setting where K = 2 and d = 300 in the "unlearnable regime" ? where n < 100 is much smaller than We set the degree t = 2 and did not split the data. The error of Algorithm [ in red (Moment) is shown in Figure | compared to linear and ridge regression (regular- ization À 1) plug-in basclines. Though computationally burdensome, Algorithm is surprisingly effective. These observations suggest that. V* estimatiion could be a valuable tool for quickly assessing models before committing to large number of samples to learn the optimal policy.
4 An Efficient Procedure: Estimating Upper Bounds on the Optimal Policy Value
The information-theoreiicc results so far have suggested that there are potentially sizable gains to be realized even in the unlearnable regime, but we seek practically useful method. In this section, we address this problem by proposing a method (Algorithmm2) 2 that instead approximates V* with an upper bound and then estimates this upper bound efficienlly. The new estimator is both statistically and computationally efficient, achieving a O(vd/22 rate. Moreover, we show it has immediate important applications. The procedure is given in Algorithm 2 Our main insight to view {(0, ø(X, [))]]e[[]] as a general stochastic process and then majorize it using& Gaussian process [Za]ae[K] (0, for some covariance matrix A S that has approximately the same increments || (o(X,a), (o(X,a'),, l as the original process By majorize, we mcan that E max, Ze 2 V*. Then we attempt to estimate this Gaussian process from data, which is significantly easier than estimating higher moments. To do this, the data is split it into two halves. Each half generates parameter estimators I and O' and we construct the increment estimator Sa 0 where we recall that Σg,a' Ex Ex[(o(X,a) o(X, (o(X,
a') from Assumption 1 From here, we can find a covariance matrix Á that nearly achieves these increments by solving a simple optimization problem (Line 14). This fully specifies our estimate of the majorizing Gaussian process 2 ~ (), from which we can compute its expected maximun by Monte-Carlo sampling, We show that, with infinite data, this quantity is exactly an upper bound on V* (under mild conditions) and the aforementioned estimation procedure can estimate this quantity at a sublincar rate. Specific to this section, we first make the following technical assumption on the process.
Assumption 4. There exists an absolule constant Lo such that, for all E Sd-1 and a, E [K], |l ()(X,)),)) - ("(XXa'), llas < Loll (), (ő(X, a²), l1..
Assumption 4 can be thought of joint sub- Gaussianity assumption on the sequence of random variables () hes (in the sense of Vershynin (2018)). This assumption is still fairly general, including
'Despite similar terminology, Algorithm 2 is distinet from Gausslan process regression. Rather than modeling a reward function with prior and kernel, are majorizing reward process with a generic Gaussian process.
8

---

Published in Transactions on Machine Learning Research (2/2024)
Algorithm 2 Estimator of Upper Bound on V*
1: Input: Number of interactions failure probability 5.
2: Set m = 2.2
3: Initialize empty dataset D.
4: Whiten features with a(.) = --1/26(-).
for i 1......n . do
Sample independently 24 DD and a, Kn. Receive reward ys
Add tuple (Iz, ag 9s) to D
8: end for
Split dataset D evenly into {ax, a, helmm and fa/ d4 3 hemm
10: Compute estimators θ = m Eielm Vo a:) and / 1 m Eie(m) 8/O(1), of)
11: for a, E [K] such that a + do
12: Set Ba,a' := 0 E
13: end for
14: A= arg minxess maxafa Da + Aa',a' - 2)a,a' - Baral
15: Return 0 E max where 2 ~~NO0 (O,,A)
Gaussian processes, symmotric Bernoulli processes, and spherical distributions in RdK as well as all rota- tions and linear combinations. There are indeed counterexamples, but, they involve specialized couplings of {(((X, a), } based on hard truncations that are unlikely to be generated in linear CB setting (see Appendix C.2 for details).
Theorem 2. Under Assumptions 1 and 4 there are absolute constants C₁ C2 > 0 and Gaussian process (Za)σE|K] with U = E max, Zo such that V* < CC-U < C2.V** Vlog K. Purthermore, for 8 < 1/e, Algorithm (og( 22/4 (0g2/3(/100) If the Va
produces Ö such that with probability at least 1 - 6, IU - 0 O
process ((X,-) hoppens to be Gaussian, we have V* U and Ô estimates V exactly.
The proof of Theorem is contained in Appendix
C.1 Despite the fact that the majorizing process Z is unknown due to 8 being unknown, we show that our novel procedure of estimating the increments 8a, at a last rate is sufficient. The norm ||0]] is problen-dependdet (and may be 0 see Section 4.1. Note that is an adaptive upper bound: it is exactly V whenever ((X,)) is a Gaussian process, so we are able to enactly estimate V* in the Gaussian and nou-disjoint setting. The tightness of the bound changes with the quality of the Gaussian approximation. A notable case when the approximation might be poor is in the symmetric Bernoulli case oxX, a) Uni and 0 (1,0,...,,)
in which case V e(1) but U = O(Vlog K). Here our estimation is loose by a vlog K factor. Thcorem 2 shows that this symmetric Bernoulli example is the worst case, and U itself' is al worst bounded by O(V* log K). In Appendix C.3 we discuss possible ways of relaxing the assumption that the features have zero mean.
4.1 Applications
To demonstrate the usefulness of upper bounds on V and the estimator of Section 4 consider several important applications. We emphasize that the remaining results will all hold for unknown covariance matrices estimated from data alone.
4.1.1 Model Selection with Many Actions
Model selection for linear contextual bandits is attracting recent interest (Agarwal et al. 2017 Foster et al. 2019). Lee et al. (2021) posited that fast V* estimators could improve model selection regret guarantecs. Wo now show how Theorem 2 can be assist this goal. Following a similar setup to that of Foster el al. (0019) we consider two nested linear function classes Fi and F2 where F, = ((s, a) + (o.(s,
0 E Rd
Here, &i maps to Rd: where dj < d2, and the first d, components of Φi are identical to d2: aka the function classes are nested, i.c. F, S Fz. The objective is minimize regret, as defined in the Preliminarics, over T online rounds. We assume that Fa realizes r" Tf Fi also realizes r* we would ideally like the regret to scale
9

---

Published in Transactions on Machine Learning Research (2/2024)
Algorithm 3 Treatment Effect Test
1: Input: Number of interactions failure probability 6, unlabeled contexts (āyhet
2: Set n' = 2.
Compute Σ. 1 Ei= 0(2),0))(2,,0) for all a A2.
Compute Eu,a' 1 -
for all a, a' E As with a + d'
Compute Σ
AP Ei=1 EnEd, a)
piipp
6: Initialize empty dataset D
for i i do
Sample independently 24 D and a, Unif A1. Receive reward yi
Add tuple (I,, a1 9/3 to D
10: end for
11: Split dataset D evenly into {ar, at, Yt heen' and {0t at, v viheeln..
12: Compute estimators -= --11 Eielin uobfas a:)) and 0' 5:-1 Eielon v(
13: for a. E [K] such that # a' do
14: Set Ba,a' : 0 Ea.
15: end for
16: arg minxesk maxaşa Daa + 'al,a' - 2)a,a' - Paaal
17: Return Ú = E max 7 where 7 ~ ~N(OAA)
with d. :- di instead of d2, as di d2 potentially. If does not realize r", then we accept regret scaling with d, d2. Since the class of minimal complexity that realizes r" is unknown, model selection algorithms aim to automatically learn this online. Our improved estimators for upper bounds on V imply improved rates for model selection and are particularly attractive in their leading dependence on K.
Our algorithm, given in Algorithm 4 in Appendix D resembles that of Foster et al. (2019) where we in- terleave rounds of uniform exploration and rounds of running Exp4-IX (Neu 2015) with chosen model class. The key difference is statistical: we rely on hypothesis test that reframes estimation of the value gap between the two model classes lows. Let Vf* and V denote the maximal achievable policy values under Fi and F2 respectively. Define 0g arg mingeR& (LEa(((((T,)),)) a) (x.a))² a) We show that the gap between the two values is bounded
V* estimation problem. The high-level intuition is fol-
V Vi < {mmax (02(X,a),6, (0), + max (02(X, a), (0 -02)
(4)
The key observation that the summands on the right are just. V values but for a new CB problem where the parameter the difference of optimal parameters of the original CB. Thcorem 2 shows that we can find a majorizing Gaussian process and an upper bound U on each summand We can then conclude that Vir ---v, VV* < 2U. Now consider the case where Fi realizes r". If this is true, then the V of the new CB problem is equal to zero. Consequently Theorem 2 would imply that U = 0 too. Thus, if we can estimate U at fast rate, we can decide quickly whether F realizes r* This is precisely what the second part of Theorem
2 allows us to do. In the end, Theorem shows our dependence on K in the leading term is only logarithmic in the leading term, which improves exponentially on the poly(K) factor in Foster et al. (0019
Theorem 3. With probability at least
Algorithm 4 achieves
Regr O (d! 2//33//3 log 3/2 / log (2 + (Vd.KTlog(d, log(d.) log(d.T(//))
(5)
4.1.2 Testing for Treatment Effect
When designing experiments, one must often determine which treatments, actions, to include in given problem. In many cases, such as Mandel et. al. (2017): Chaiyachati et al. (2018). choosing from a certain
3In this case, the upper bound V happens the same for both summands.
10

---

Published in Transactions on Machine Learning Research (2/2024)
Probwhillty of detection giver no treatment effect
Probansity detection given nout va treatmert offect
Warfarin data requared to detert gop
337-
.R
Proabil of ditocctoon
Probabi decoctto
0
0330
Marrbe lebaeedd
3479
0290
04-
3890
Samples
Samples
Cap
Figure 2: A comparison between our proposed test for treatment effect in Section 4.1.2 and a test based on a linear regression baseline (LR) with d = 600 and p = 2000. The left figure shows the case where there is no treatment effect, A = 0 (closer to (closer to is better). Our test is more sensitive to real effects as shown in the middle figure, while remaining comparable in terms of the fraction of false positives. Error bands represent standard error 1000 replicates. The right figure demonstrates the estimator warfarin dosage data. The objective is to determine if an optimal policy, which can select from two dosages to administer to patients, would significantly improve outcomes over simply administering a fixed dosage to all patients. The z-axis shows the ground truth average effect gap (up to noise) of policy that incorporates the second dosage over the baseline dosage (e.g. (medium, high} over just (medium))). The y-axis shows the number of labeled samples required to detect the given effect gap. ND denotes that the effect was not detected given the available labeled data, A good estimator should quickly detect larger effect sizes (drop to zero along the r-axis) but may remain uncertain when the effect size is negligible. The effect gap sizes are ordered from least to greatest in the following order: {med, high}, {med, low], (low, high}, (low, med), (high, med), (high, low).
better). The middle figure shows the case where A = 0.133 > 0
treatment set As might lead to far better outcomes and thus larger values of V for given problem than what is achievable by a base set Ai. However, since A is more ambitious in scope, it also may be significantly more costly for the experiment designer to implement and collect data for a variety of reasons. Thus, if the improvement in V* of using all treatments Ai U over just an inexpensive subset Ai negligible, would be more cost-effective to simply use Ai.
We refer to this problem as testing for treatment effect. We assume that both A1 and A share known control action do such that r" (xr an) = 0 for all x E X. We say that A has zero additional treat effect over the control dg if E max.EA, (Ø(X, = O. We do not assume that the covariance matrices are known. Rather, the designer has p unlabeled contexts. Typically, >> n.
We show the method in Algorithm 3 and sketch the main idea. First, define Vf == max.eA, (Ø(X, a).0) O) and V/2 := E max (ø(X, a), 0). We prove that the gap can be bounded by the V value of a new CB problem over just the action set A2: V V1" Emax,eA: (ø(X,a) a), 0). Then, we simply apply Theorem 2 to test if U 0. We then estimate U by the procedure outlined in Algorithm 2 but this time using the unlabeled data to estimate the covariance matrices. Leveraging Thcorem
2 we show there exists test statistic Ú output from Algorithm 3 and test, v = 0 if Ú $ 0 (Ve a'/4
vol and V = otherwise, with a low chance of false positives but also good chance of detecting small effects with limited data.
Theorem 4. Let = |A1 Agl be the total number of actions and let A == - V1" be the gap. Suppose that the size of the unlabeled dalaset is p= ==pp2ddle ((ddog(K/á)) Then the following conditions are brue each with probability at least 1- (1) When there is no additional treatment effect of A2 over the control, then the d//4 /Vn,, then the test correctly outputs V 11
test correctly outputs 0. (2) A
To achieve the same guarantee with a plug-in estimator as a lest statistic, we would only be able to detect a gap A of size O( dd/)) or equivalently, it would require at least n 2 d datapoints to estimate anything non-trivial, and the plug-in estimator accuracy would be going at much slower rate. Note our bound in Theorem 4 is never worse than ②( /d/n) since a constant fraction of the labeled data can always be treated unlabeled data.
11

---

Published in Transactions on Machine Learning Research (2/2024)
Synthetic Testing Experiments. To demonstrate the effectiveness and practicality of our proposed method for testing treatments, we conducted numerical experiments comparing our test with a plug-in linear regression (LR) baseline. We simulated a high-dimensional contextual bandit learning setting with [Ail= = 3 actions and [A2] = 2 and = 600 features. Note that this remains in the sublinear regime due to the fact that the number of samples n never exceeds d.
We first evaluated the methods in the no-effect setting -A= 0) where coordinates of 0 were set to 0 as to limit any advantage gained from Ag. We then sampled 0 with positive value of A and ran the same experiment. Figure 2 shows ours performs strictly better than plug-in in regression baseline at detecting effects while still maintaining a comparable false positive rate when there is no effect. Details to reproduce the experiments can be found in Appendix
Testing for Warfarin Treatment Effect. In this section, we apply our method to the problem of testing for treatment effect in warfarin dosages. Warfarin is anticoagulant drug that is commonly prescribed to patients at risk of blood clots. It is important to get the correct dose of warfarin because incorrect dosages can lead to serious side effects. The Pharmacogenetics and Pharmacogenomies Knowledge Base (PharmGKB) provides a publicly available dataset of patient covariates as well as their final dosages, which might be noisy or slightly suboptimal. In this experiment, the doscs were grouped into discrete actions of low, medium, and high based on the original data. We viewed the contextual bandit as giving a reward of +1 if the learner selects the correct dose for patient from A = {low, medium, high} and +0 otherwise. We consider the following simplified testing problem. Given fixed bascline action E A, does incorporating another target action a' E A such that a a' significantly improve outcomes on average over simply applying to all patients? Note that this question asks more than just whether a' is better than a if applied uniformly to all patients. This is because a' could be applied to only some patients who would significantly benefit from a' over a while others are still able to receive a, thus boosting the overall effectiveness.
To evaluate this, we considered each baseline action in E A and paired it with a target action a' E A to evaluate if more can be gained form a'. There are 3! such permutations. We computed (approximately) the ground truth improvement A under linear model (which may be misspecified for this real world data). Note that A will always be non-negative (up to noise), but it may be very small. This dataset happens to induce a disjoint linear bandit; however, we must still deal with the issuc of sub-Gaussian features. We ran both a naive linear regression and our algorithm to estimate the effect size, varying the amount of labeled data given 4560 unlabeled samples. The right plot in Figure shows the number of labeled samples required before the effect is detected for a given effect size. Recall that the effect size is determined by the selection of the bascline a and target a'. If a method does not detect the effect with the labeled data, it denoted by ND. We include dashed vertical lines indicating the effect sizes that were evaluated. Ideally, we should see points in the top left corner when there is no effect, and then points converging to the bottom right corner (casy to detect large effect sizcs). Our method can detect the effects significantly faster by leveraging the more sensitive test and unlabeled data. We caution that these results are proof-of-coneet concept and should not be misconstrued to suggest that a single dosage of warfarin is adequate for all patients.
5 Discussion
In this paper, studied the problem of estimating the optimal policy value in a linear contextual bandit in the unlearnable regime. We considered this beyond the Gaussian case and presented estimators for both V and informative upper bounds on V*. In particular, we showed information-thhoreliiall that a sublinear in sample complexity of (122k////// is possible for estimating V directly, given lower-order moments.
To circumvent the exponential dependence, we also gave an efficient Ō(Vd/c²) algorithm for estimating upper bounds and demonstrated its utility by achieving novel guarantees for model selection and testing, There are several open questions for future work. We conjectured that the exponential dependence on e in Corollary 3.5 is unimprovable in general; however, remains a difficult open problem to verify this. It would also be interesting to explore how the sample complexity degrades if some quantities were estimated without unlabeled data.
12

---

Published in Transactions on Machine Learning Research (2/2024)
Acknowledgments
J.N.L. acknowlodges support from the NSF GRFP. A.P. would like to thank the support the Eric and Wendy Schmidt, Center at the Broad Institute of MIT and Harvard. This work was supported in part by funding from the Eric and Wendy Schmidt Center the Broad Institute of MIT and Harvard. V.M. acknowledges support from the NSF (through CAREER award CCF-2239151 and award IIS-2212182), an Adobe Data Science Research Award, an Amazon Research Award, and Google Research Collabs Award. This work was also supported by NSF #2112926.
References
Yasin Jobasi-Yadkortt Dávid Pál, and Csaba Szepesvári. Improved algorithms for lincar stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312 2320, 2011.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling band of bandit algorithms. In Conference on Learning Theory, pp. 12-38. PMLR, 2017.
Rika Antonova, Joe Runde, Min Hyung Lee, and Emma Brunskill. Automatically learning to teach to the lcarning objectives. In Proceedings of the third (2016) ACM conference on learning@ scale, pp. 317-320, 2016.
Yves Audibert, Sebastien Bubeck, and Remi Munos. Best arm identification in multi-armed bandits. In Conference Learning Theory (COLT), 2010.
Peter Auer. Using confidence bounds for exploitatiion-colloratonn trade-offs. Journal of Machine Learning Research, 3(N77 422, 2002.
Thomas Bagby, Len Bos, and Norman Levenberg. Multivariate simultancous approximation. Constructive approzimation, 18(4):569-51 2002.
Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceed- ings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pp. 102-115, 2021.
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits problems. In Internaiional Conference on Algorithmic Learning Theory, 2009.
Krisda Chaiyachati,, Rebecca Hubbard, Alyssa Yeager, Brian Mugo, Stephanie Lopez, Elizabeth Asch, Catherine Shi, Judy A Shea, Roy Rosin, and David Grande. Association of rideshare-based transportation services and missed primary care appointments: a clinical trial. JAMA internal medicine, 178(3):383 389, 2018.
Sourav Chatterjee. An error bound in the sudakov-fernique inequality. ar preprinl malh/0510424, 2005.
Niladri Chatterji, Vidya Muthukumar, and Peter Bartlett. Osom: A simultaneously optimal algorithm for multi-armed and linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pp. 1844 1854, 2020.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourleenth International Conference on Arlificial Intelligence and Stalislics, pp. 208 214. JMLR Workshop and Conference Proceedings, 2011.
Lee H Dicker. Variance estimation in high-dimensional linear models. Biometrika, 101(2):269 284, 2014.
Eyal Even-Dar, Shic Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 2006.
Tanner Fiez, Lalit Jain, Kevin Jamicson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. Xix preprint 1906::90660000 2019.
13

---

Published in Transactions on Machine Learning Research (2/2024)
Dylan Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. arXiv preprinl Xrx: 1900i.1900.000 005600 2019.
Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified
approach to fixed budget and fixed confidence. In Neural Information Processing Systems (NeurIPS), pp- 3212 3220, 2012.
Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Model selection for generic contextual bandits. arXiv preprint arXiv:2107.03455, 2021.
Steve Hanneke. Theory of active learning. Foundations and Trends in Machine Learnäng, 7(2-3), 2014.
David Lee Hanson and Farroll Tim Wright. A bound on tail probabilities for quadratic forms in independent random variables. The Annals of Mathematical Statistics, 42(3):1079-10883, 1971.
Matthew Hofiman, Bobak Shahriari, and Nando Freitas. On correlation and budget constraints in model- based bandit optimization with application to automatic machine learning. In Artificial Intelligence and Slalistics, pp. 365-374 2014.
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil'ucb: An optimal exploration algorithm for multi-armed bandits. In Conference Learning Theory, pp. 423 439, 2014.
Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 33, 2020.
Kwang-Sung Jun, Kevin Jamieson, Robert Nowak, and Xiaojin Zhu. Top arm identification in multi-armed bandits with batch arm pulls. In Artificial Intelligence and Statistics, pp. 139-148. PMLR, 2016.
Zohar Karnin. Verification based solution for structured mab problems. In Proceedings of the 30th Interna- tional Conference on Neural Information Processing Systems, pp. 145-153, 2016.
Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning (ICML), 2013.
Julian Katz-Samuels and Kevin Jamieson, The true sample complexity of identifying good arms. In Inter- national Conference on Artificial Intelligence and Statistics, pp. 1781-1791. PMLR, 2020.
Ramtin Keramati and Emma Brunskill. Value driven representation for human-in-the-loop reinforcement learning. In Proceedings of the 27th ACM Conference on User Modeling, Adaptation and Personalization, pp. 776-180.20 ACM, 2019.
Weihao Kong and Gregory Valiant. Estimating learnability in the sublinear data regime. Advances in Neural Information Processing Systems, 31:5455 5464, 2018.
Weihao Kong, Fmma Brunskill, and Gregory Valiant. Sublinear optimal policy value estimation in contextual bandits. In International Conference on Artificial Intelligence and Stotistics, pp. 4377 4387. PMLR, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, 2018
Jonathan Lee, Aldo Pacchiano, Vidya Muthukumar, Weihao Kong, and Emma Brunskill. Online model selection for reinforcement learning with function approximation. In International Conference on Artificial Intelligence and Statistics, pp. 3340 3348. PMLR, 2021.
Jonathan Lee, George Tucker, Ofr Nachum, and Bo Dai. Model selection in batch policy optimization. In International Conference on Machine Learning, pp. 12542 12569. PMLR, 2022a.
Jonathan N Lee, George Tucker, Ofir Nachum, Bo Dai, and Emma Brunskill. Oracle incqualities for model selection in oflline reinforcement learning. arXiv preprint or orXiv:2211.00 1.02016, 2022b.
Travis Mandel, Yun-En Liu, Emma Brunskill, and Zoran Popović. Where to add actions in human in- in-the-loop reinforcement learning. In Thirly- First AAAT Conference on Artificial Intelligence, 2017.
14

---

Published in Transactions on Machine Learning Research (2/2024)
Teodor Vanislavov Marinov and Julian Zimmert. The pareto frontier of model selection for general contextual bandits. Advances in Neural Information Processing Systems, 34, 2021.
VA Markov. On functions of least deviation from zero in given interval. St. Petersburg, 892, 1892.
Oded Maron and Andrew W Moore. Hoeffding races: Accelerating model selection search for classification and function approximation. In Newral Information Processing Systems (NeurIPS), pp. 59 66, 1994.
Volodymyr Mnih, Csaba Szepesvári, and Yves Audibert. Empirical bernstein stopping. In Proceedings of the 25th international conference on Machine learning, pp. 672 679, 2008.
Vidya K Muthukumar and Akshay Krishnamurthy. Universal and data-adaptive algorithms for model se- lection in linear contextual bandits. In International Conference on Machine Learning, pp. 16197-16222.
PMLR, 2022.
Gergely Neu. Explore more: Improved high-probability regret bounds for non-stochastic bandits. arxiv preprint Xrx::11506.00 03271, 2015.
Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett. Regret bound balancing and elimi- nation for model selection in bandits and rl. arXiv preprint arXiv:2012. 1e2122130444 13045, 2020a.
Aldo Pacchiano, My Phan, Yasin Abbasi- Yadkori, Amup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. arXiv preprint arxi::2003.01 01704, 2020b.
Mark Rudelson, Roman Vershynin, et al. Hanson-wright inequality and sub- sub-gaussian concentration. Elec- tronic Communications in Probability, 18, 2013.
Alexander A Sherstov. Making polynomials robust to noise. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 747 758, 2012.
Aarti Singh; Robert Nowak, and Jerry Zhu. Unlabeled data: Now it helps, now it doesn't. Advances in neural information processing systems, 21:1513 1520, 2008.
Marta Soare, Alessandro Lazarie, and Rémi Munos. Best-arm identification in linear bandits. arXiv preprinl arXiv:1409.611 10, 2014.
Michel Talagrand. The generic chaining: upper and lower bounds of stochastic processes. Springer Science & Business Media, 2006.
Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in lincar bandits with linear dimension dependency. In International Conference on Machine Learning, pp. 4877-4886. PMLR, 2018
Kevin Tian, Weihao Kong, and Gregory Valiant. Learning populations of parameters. arXiv preprint EXXi:1109.02700 2017.
Roman Vershynin. digfs-dimensoonl probability: An introduction with applications in data science, vol- une 47. Cambridge university press, 2018.
Nicolas Verzelen, Flisabeth Gassiat, et al. Adaptive estimation of high-dimensional signal-uo-noise ratios. Bernoulli, 24(4B))3683 3710, 2018.
Liyuan Xu, Junya Honda, and Masashi Sugiyama. A fully adaptive algorithm for pure exploration in linear bandits. In International Conference on Artificial Intelligence and Statistics, pp. 843-851, 2018.
Krzysztof Zajkowski. Bounds on tail probabilities for quadratic forms in dependent sub-gaussian random variables. Statistics & Probability Letters, 167:108898, 2020.
Andrea Zanette, Kefan Dong, Jonathan Lee, and Emma Brunskill. Design of experiments for stochastic contextual linear bandits. Advances in Neural Information Processing Systems, 34, 2021.
Yinglun Zhu and Robert Nowak. Pareto optimal model selection in linear bandits. arxiv preprint arXiv:2102.06503 2021.
15

---

Published in Transactions on Machine Learning Research (2/2024)
A Proofs of Results in Section 3
A.1 Formal Analysis of Multi-Armed Bandit Lower Bound
In an effort to prove sublinear sample complexity bounds for V estimation in bandit problems, a natural starting point is the classical K-armed bandit problem where r"(x, a) independent of (and for this part only we assume that the mcans are non-zero), equivalently represented a mean vector p E R The feedback is the same: ((a) = Pa 7/a)- In this case, V* is defined V max, Pa-
One might ask whether it is possible to estimate V with better dependence on either K or than what is typically required to, for example, identify the best arm or identify an e-optimal arm. The following proposition asserts that such a result is not possible.
Proposition A.1. There erists class of K-armed bandit problems satisfying || O(1) such that any algorithm that returns an e-oplimal estimate of V* with probability at least 2/3 must use Q(K/e²) samples.
The result fairly intuitive: since there is no shared information between any of the arms, the learner must. essentially sample each arm sufficiently accurately determine the maximal value.
Proof. The proof the lower bound for the K-armed bandit problem follows a standard argument via Le Cam's method. Let Vn denote the output of a fixed algorithm A after n interactions with the bandit that achieves IV, V* S with probability least 2/3. We let v and v denote two separate bandit instances, determined by their distributions.
For shorthand, P, and Per denote measures under these instances for the fixed, arbitrary algorithm (and similarly expectations E, and B.r). Na denotes the (random) number of times the fixed algorithm sampled arm a.
We let y be distributed as (M 1) for all a where μ (c, ....,)).,))
0). Then, define a' E arg min Eg [Ta] and let v' be distributed as N(ra: 1) where pla = Pa for all a + a' and 1' = 4c. We define the successful events E, = (Vn E [0,2e] 2:]} and E = (V, E [3e,
By Le Cam's lemma and Pinsker's inequality,
Po(EE) + (E,) (KL(Pr,P Po)
(6)
where (Pu,Pe,Pa)) ( nc of the successful event is bounded as
Lattimore & Szepesvári
2018
It then follows that the probability
ne2
(F()) (P(E)))+ + +C
(7)
K
TE22
S PP((E)) + +C1/
(8)
K-1
nE²
$ $3 + CV K-1 C
(9)
for some constant C> 0. Thus, in order for (Fx) 2 2/3 it must be that n 2 (K-1)
9042- It follows that any
algorithm that achieves such a condition must incur sample complexity ((K/e²).
A.2 Proposition 3.2
Proof. Proof of the first lower bound. Fix algorithm A for the linear contextual bandit problem. Then consider the class of d
2 --arned bandit problem with means voctors satisfying || = O(1). From this class,
we construct the following class of linear contextual bandits. Let 0 =
1 E Rdd. The set contexts is
-1
16

---

Published in Transactions on Machine Learning Research (2/2024)
X (1,2) and the feature map is defined
Ó(x, a) = --6
1100
co
x =
(10)
2
where (el,...,edl C R denotes the set of standard basis vectors. Then, X = I and X 2 each with probability 3. This ensures that Eø(X, = 0 for any fixed action a. Furthermore, ||aall @(1). Note that V Emxx, (0(X,a) a), 0) max, Ma.
Now construct the reduction by specifying algorithm B for the ş-armed bandit. At each round, B samples X ~ Unif and queries A for an arm A. Upon observing feedback Y(A) = μa + m(A), B feeds (A) back to A if X = 1 and (A) if X = 2. This process is repeated for rounds and A outputs an estimate Vn, which B also outputs. A outputs V. such that VV, - V* S for any given instance in the linear contextual bandit. then Va is also an e-oplimal estimate of max, Pa- Therefore, to satisfy |V, - - S e, it follows that (dd/e)).
Proof of the second lower bound. Here prove the second statement of the proposition that even for K = 2, it takes (dd) samples to estimate V* up to small constant additive error c. The proof simply follows from the hard instance for signal-noise-ratio (SNR) estimation problem in Theorem 3 of Kong & Valiant 2018).
. In. Vn) such that (0,0, ~ P. ~ NO, y1 = xz + Th. Th ((,00²), Let the null distribution Po satisfics 0, Σ Id, 0² almost surcly.
Let Qn be the distribution of (I1, y1....
We define the alternative data distribution (P)) as follows. First let rotation matrix R be drawn from
II
0
Haar measure over orthogonal matrices in (dd++1) Given R, define matrix M = R
R Then
0
0
we draw n i.idd samples 21, ; En from Gaussian distribution N(0, M), and let x; 1ed be the first d coordinate of 24 and, y: = 2i,d be the last coordinate z,. This definition will implicitly define a distribution over M, 0, a which is called Pt.
Now we show that (2v (Pi)) S 0.27 when n d/8.
Lemma A.2. Define product distribution Do = N(0, Ta)@n, and D1 = N)) where M
R -4-1 0
R and R is drawn from a Haar measure over orthogoal matrices in Rddd Then drv (Do, D1) S
0
0.27 when n S d/8.
Proof. Since the covariance M randomly rotated, suffice compute the total variation distance between the Bartlett decomposition of Dg and Di. The Bartlett decomposition A puxa of Do has
1 2 Xa-i+1 Vi [n]
N(0, 1) Vi <j
1 Vi Vidj
The Bartlett decomposition ( E RRax of Dj has
A ~ Xa=; Vi E
4 ~ (0,1) Vi
A ~ Vidj
Therefore
drv Di) d ... x X2 X2 x
17

---

Published in Transactions on Machine Learning Research (2/2024)
To establish total variation distance bound, we will first bound the chi-square divergence
x ... ...
Xa Xd-n+1: X2-1 x x x²-n)
(x2 X² ..... (1 +1)
2(u 1)/2(((d 1)/2)
2
2(d=n;/2T(() (((d-n)) ? (dd (d-1) .......... (d- n) 1)...
24/2l(d/2)
2(d=n+1)/21(( ((d- nn- 1)/2)
(2d n2/22 (d 1)-1).... nd- n
2 (d/2)
WLOG, assume that d is a multiple of 4 and that n is a multiple of Then
(P(ddn)//2 (d - 1)........ (d - n) -1
(d/2()
(d 1)(d 2) (d n)
(d - 2) 1)2 (d n)²
(d 1)(d -3) ... (d n 1)
(d - 2) - 4) 4)...(() n)
(1 +
d --22 2 (1 +
d. (1 + d
$ (1 + d/2
n/2 v 1/4 - 1.
Now using the fact that
(Dv $ (D,(D,,Do)
2
We get
drv(Di,Do) S Vel/4 1/2 S 0.27
Under Pi, y is a linear function of x almost surely, and the variance is R8+1 Since Rat1 is an entry of unit norm random vector, for sufficiently large d, it holds that R2+1,041 2 0.99 with probability 0.99.
We construct the alternative bandit instance using (0, o, 2) ~ PI, and for each arm a E [2]. define o(X,a) (O, Σ), (a)) = 0 (XX,)) a). It easy to see that this case, EV = f2(1). The other bandit instance is a simple "pure noise" example where a(X,a) NO, I,), (a) N 1), and clearly EV" 0 since 0 0. For any bandit algorithm for estimating V*, after d/16 rounds, arm gets pulled) are shown to the algorithm the total variation distance is between the two example is still bounded by 1/3 through Lemma for estimating V* with probability at least 2/3 when n c- d where e = 1/16.
if all the rewards (regardless of which
A.2 Therefore, conclude any bandit algorithm must incur ?((1) error
B Proofs of Results in Section 3.2
B.1 Proof Mechanism
We give a brief sketch of the proof of Theorem 1 As mentioned, we reduce the problem to just estimating
Ex (1,,, ((X,a)) aae which gives us a (-accurate approximation of V* via Definition 3.3 Note that
Ex [p (0, db (x))) haea)l Ejager 6a II. Ex (d(X,a), is just linear combination of all the a- moments
S. = Ex II. (0(X, a), 0) Recall that m is the sample size of the split datasct. In Lemma B.2 we show that S6 in Algorithm is unbiased estimator of S.. We then show that the variance is bounded.
18

---

Published in Transactions on Machine Learning Research (2/2024)
Lemma B.1. There erist constants C' >>> 0 that var(S mCs where |a]-
The proof of this variance bound is non-trivial and, as one might guess, Lemma B.1 does most of the heavy- lifting the proof Theorem Observe that this step is where the vd/n n rate is achieved (since n R m up to logarithmic factors). To achiove this, we must be careful not to leak vd factors into the variance bound through, for example, hasty applications of Cauchy-Schwaal or sub-Gaussian bounds. This achieved through a Hanson- Hanson-Wrighte Wright-like inequality (Lemma B.3). Also, prevent any exponential blow-ups in the degree of the polynomial, we must ensure that any exponential terms in the numerator can be modulated by m² in the denominator. This comes down to a careful counting argument. The last steps of the proof revolve around using the variance bound to prove concentration.
B.2 Understanding the influence of polynomial approximation
Theorem 1 aand Lemma B.1 provide some interesting observations about the influence of the polynomial ap-
proximation. One of the key terms to understand is the summation. Each term looks like [Cvvd log(1/0)
8/2
CI (oPVllo(1//1 (og(1/0), this term is less than one and thus we have Let us take K = 0(1) for case of exposition. Recall that the first term (C) is the approximation error of the polynomial while the second term can be interpreted as the effect of variance. The estimation error can be made small by by taking
for each [t]. This means that as long
V S,1 S o ( Cmaxt (et/K + e)* cr CPV/log(118)
n = - - Vdlog(1/0)
The approximation error can made Ç ~ 5 small by choosing stronger polynomial approximators. However, this is where the trado-off occurs. To obtain better polynomial approximators, we typically require that the degree / increases accordingly. The magnitude of the coelficients Cnax typically also increase (for very general polynomial approximators). This means that there is chance the sample complexity significantly if t and Cmax are functions of the accuracy While this does not affect the dependence on vd (and thus the results remain sublinear), it can lead to worse e-dependence. See Corollaries 3.5 and 3.7 for instantiations.
increase
B.3 Proof of Theorem i
First note that the data-whitening pre-processing step does not contribute more than constant to the sample complexity since we reframe the problem as
r (x a) (0(x,)),0 (000,,))0))(x--1220000) (1--1/2((r,)) E)22))
Observe || & ||o|| since o(X,a) subG(r²) with - O(1). Also X'1/2 subG(r2/p) where T2/p 0(). Note that this means must also linearly transform Σ, and En.' for a, E A, but an identical calculation shows that they are similarly unaffected to constants. Therefore, without loss of generality, we may simply take = Id.
Next, we verily that S m. for & = I,..., [48 log(1/5) are unbiased estimators of the moments of interest.
Lemma B.2. Given Sk a defined in (2), it holds that ED m = Ex Iaeeg (0, 6(X, a.
19

---

Published in Transactions on Machine Learning Research (2/2024)
Proof. We drop the superseript k notation denoting which of the datasets is being used as the argument is identical. Fix & E ((ml) as s-combination of the indices [n]]. Since the data in D is i.i.d, we have that
EnEx II
(ue, 6xx (()) Ex II jE[s]
(ED [ve,ar, (6(x(((a)))
(11)
jE[s
Ex II
(0, 6(, a()))
(12)
]E(+
Ex
II (0, ax)
(13)
[E[K]
where the second equality uses the fact that Eppaa Ta- for all i [m].
0
Next, establish bound on the variance in preparation apply Chebyshev's inequality. Lemma B.1. There crist constants so that var(S S E. Eu=((Cs (C's vd)" where s la).
Proof. As before, we will drop the superscript notation as the argument identical for each independent estimator. Let s= |a
By definition, the variance is given by
var D
(mma = ED
$2 m,
ED
Sm,
S
12
(14)
where
$2 Sm,a
Ex.x'
II 6(X, a()))
II bex
(15)
(m))
2
E,e"
KE(e]
ED Sn.o
Ex II (0, 6(
II (0, 6(''
(16)
where again i and l' are s-combinations [n]. Similar to Kong & Valiant 2018 as individual terms in the sum over E and L::
can analyze the variance
EDExx
(ue ((X, (X,(()) <E($]
II
II ue M('' o(.'aa)))
(17)
jE(s]
- Ex.x II (0,6(X,))) a)) 9. II (0, ((.'(Xa))))
(18)
There are two important cases consider: (1) when and & do not share any indices and (2) when there is partial or complete overlap of indices.
1. No intersection of l and E In this case, we may see that there is no contribution to the variance for this term due to independence:
EDEXX
II RE(s]
(Ve,T ((x 6(X,a())
II
Ve ue 6(X o()))
(19)
KE(s)
Ex,x,
II *E(s]
(0, < XX, (()))
II
(0, (0.6(X',app (())
(20)
SE(e]
Ex,x II
(0,
o X, a))a
II
(0, 60'' a())
(21)
This term simply cancels with E Sm.a 2
20

---

Published in Transactions on Machine Learning Research (2/2024)
2. Partial complete intersection of l and l'
In this case, there are some samples that appear twice. Let B {(i,)) 4= be the set of indices that refer to the same sample in D. Also define 7,7 c [s] as the subsets of indices of l and respectively that are not shared.
The left-hand side of this term can be then be written
EDEx,x
II iElel
(Ue, 0e, o(X, (()) II
De pe. 6x" (x)aa))) an))
(22)
sE
Ex.x
II Ep, [u (de,, ((x a()) (Øe, 6(X' , am))] (K,)))
(23)
x II iET
(((())))))))
II (1' KET
(24)
To proceed, we require the following critical lemma which bounds separate moments in the factors that come from shared indices. The proof given in Section G
Lemma B.3. Let p 2 1 be an integer and define M = ED, [3, 01, TT]. There a constant such that
(Ex,x)((X, Mø(X', ap))) SC. pr +110113/aa
(25)
Through standard sub-Ganssian arguments, we also have that, for p 2 holds that (B) (0, of,,( (())) pP) 1/p < CT for some constant C 0. And the same holds for the X' factors.
For convenience, let (o² + 2| and let |8| < be the size of the overlap. By the generalized Holder incquality, the term in 23 is upper bounded by
1/2s
II (x)x)((X, (A.))R
II
Exxx11
20
(26)
SET
1/2s
Il Ex Exx (0,' ,()))) 22 YEy
(27)
1/28
II Exxxlo(X,,ap) MØ(X' a())) (1,E)
(28)
(Co (2s)7">Vd))
(29)
(30)
where we have used Assumption g and Co. C1 > O are constants.
In summary, we have shown that there no contribution the variance when no indices are shared between and l' and the contribution to the variance when m indices shared is bounded by ((dw/2). It suffices to count the terms to see the total contribution for each = 1,....
It can be checked that the number of terms where the size of the intersection = |3] is
m
5
m
(31)
since there are s elements I, u of which may have an intersoction, and a remaining s a elements to be chosen for l' that are not shared with 8 (recall that m > 2s). Counting all of these contributions up, this
21

---

Published in Transactions on Machine Learning Research (2/2024)
implies that the variance can be bounded
var D
Sm,a
S
m
m -
Cis 22
(32)
m
u
(m-a)
0f 8th 7 du/2
(33)
Now, will bound the factor involving binomial coefficients. First note that we have
m s
(m 8)8-u (s u)!
m
(m
+ 1)2
S
and
and
2
(34)
ud
2
s!
Therefore,
m
8
m 8
8 smmm (m - s)=="s!
(35)
1
u!(s u u)!(m - 1)*
s"
(36)
(m 8)
(2s)a
(37)
m"
2es
VA
(38)
m
where in the third line, we have used the fact that m (o//4/)g((//) 21 2 2s. Then, we conclude that the variance is bounded
(m,,a S Σ (O25")2yd1122"
(39)
where C2 > constant. Since was assumed that t, 0², and ||0]| are O(1), the final claim follows.
The error bound result on the median of the estimators follows almost immediately.
Theorem 5. There erists a constant C O(1) for all k such that, with probability at least 2/3,
S
IES m.al S e(m, d, s)
(40)
where
<mm, d, s): = Σ Vd u/2
(41)
Furthermore, defining Sn.a = median A
m, k=1 with probability - 6,
SS I.S. LES S e(m, s)
(42)
Proof. The first statement follows immediately from Chebyshev's inequality and the second applies the median of means trick for the independent estimators ( given the choice of Kong et. al. (2020) 0
B.3.1
Final Bound
We now combine the estimation and approximation error bounds to derive the final result, which is repro- duced here.
22

---

Published in Transactions on Machine Learning Research (2/2024)
Theorem 1. Let Assumptions and 3 hold. Let Pt be t-degree (5. Cmax) (max))-ollyommal approzimator and let. Sn. be the oulput of Algorithm Suppose that 2 96 96 /8)t. There is constand C > 0, depending only on o, and L, such that with probability at least 1 - s(et///000 K + e)* IV* Sal is bounded by
Ç Cuaxx (et/K + te)* E.=
ct'vd log log(1/0))
8/2
Proof. We first start by bounding the full estimation error [x (1 o(X, a)) JaEA)] For convenience, let us denote Ex (0, (XX, a)) )eEA)] The degree and degree moments are already known exactly; thus we may consider S s S t. By the union bound and triangle inequality combined with the result of Theorem with probability at least 1- -((et//K 8)
S-- 1 Sal5
Σ xE[2.4]
ca CalSna ES
(43)
a : |a|=
(nax
(44)
For each 8, there are K-1 S (es/K + e)* monomials for possible choices of a. Therefore, the good event implies that
$ - S.1 S &t + e)* Caax c(n//////// d,
(45)
Next, may apply the approximation error. By the triangle inequality
E max (0, (0.((Xaa)) - 3,1 s
+ e)* Cmax e(n/qq,,8)
(46)
B.4 Generic Polynomial Approximator in Example 3.4
Throughout this subsection only, we will use Pt to refer to pbbl.
Lemma B.4. Let f []-1,1] - R be defined as f(z) max, Za. There crists degree-t polynomial Pr p=:[11,1] + R of the form in Defonition 3.3 such that
sup ( =x) Pe( xx)1 Ck =E[o,1j
(47)
for some constant CK that only depends on K. Furthermore, for t K, Ical (2et)28122) such that loo| < t.
KR Cmax for all
Proof. It follows from Lemma 2 of Tian et al. 2017 that, for any 1-Lipschitz g supported on [0, 1]K polynomial ((2) = Ea Jalge &a II 5" exists satisfying (47] with |cal I (2t)kg = êmax and constant Cx. The max function g is 1-Lipschitz and thus satisfies this condition. Let g(2) = max, Ea and 2o +1 Note that & [o, 1 by this definition and f(=) 23( polynomial such that p(z) = -jalee Co Iluea z". Therefore, for any z, [f(z) - p(2) S Ck/t.
2-
Furthermore p(2) 2q( degree
The coefficients Ca are different from &₂ Ei (*t--l) < (t ()(t//K + e) < 2t(2et/K)* terms. Therefore Ic,,1 < (2e0)28+1gs The value of CK is given in equation (13) of Bagby et al. (2002).
result of the change of variables. Note that there are
K
Corollary 3.5. The estimator Sn generated by Algorithm 1 with polynomial pt BAL for with probability least
satisfies IV -åal $
6, 2Ck/e, and sample complenity
o
(
Ck Ke
K
KVd
Ck ed
20k/c.
loog
(3)
23

---

Published in Transactions on Machine Learning Research (2/2024)
Proof. To ensure that each term in the sum of Theorem 1 is at most 2. it suffices to take
n 2 maxt (et/K t)2k. C
(48)
for some constant C C>> 0. Then, choose / = max K}. Therefore,
n - (oCorrnnx (tex/eatttt Vdlog(1/0)
(49)
From the definition Cmax: this leads to
(4cC (
(4cCk|)))k+3210ck CCx(4eCk/e)a vdlog(1/0)
o K2K
To ensure this event occurs with probability at least 8' we apply a change of variables with
8' = t(et/(/KKK (e) 2Cx(2eCk/eR' te)
Therefore the total sample complexity is
Kvd (4eCk/e)(K+2220 Cx(4eCC/ee2
12x 22x(2eeK/eK + +
log
K2R
c
e8'
with probability at least 1 8'.
B.5 Binary Polynomial Approximator in Example 3.6
Throughout this subsection only, we will use pk to refer to PK
Lemma B.5. There crists a polynomial pk satisfying the conditions of Example 3.6
Proof. From the description of the CB problem, have that
V Ex max (X(XX1), 0) ...., ()),
(50)
where
Ba E [K] s.t. (d(X,a),0/u)
max ())
()))),,))))
otherwise
= [ol ([X,))(()))))/11)))
Note that the right side is simply K-degree polynomial function of [Ø((z a), 0)} which denote by Px there is zero approxination error. Furthermore, it can be easily seen that bound the largest coefficient is W due to the product of terms.
We now prove the corollary.
Corollary 3.7. On the class of problems in Example 3.0 Sn with bin satisfies VV* Snl s -S-
for < 1 with
probability al least - å and sample complexity O K822K
va z
log (2k)
24

---

Published in Transactions on Machine Learning Research (2/2024)
Proof. The proof is essentially identical application of Theorem as in the previous corollary. In this case, we have = K as the degree. Then, it suffices to choose
n cmax (et/ K e)ax Ct VF
to ensure the error of each lerm at most e/l. Then, with e max S | and K and the change of variables to 8' t(et/ K e) 8, we get that the total sample complexity is
8,
o (w) K 2k
Vd
(K log d'
with probability at least 1
B.6
Definition of Cк
Bagby et al. (2022) define Cx via the restriction of a holomorphic function to RK given by g: R - R. particular, their Lemma A defines the quantity
K
Ro. / (w]) (w)
1s
for the restriction function In our case, we have k = 1 (due to Lipschitzness). It is sufficient in their t upper bounds the following quantity:
Theorem to ensure that 41 and thus Cx !
CR(IR 1)(2R)) ( (((22+1)))
where C' an absolute constant (see their Lemma A), R is the Loo length of the box (in this case R = 1), and such that /2(2R 1) 1, and we recall that t the degree of the polynomial approximator,
C Proofs of Results in Section 4
C.1 Proof of Theorem 2
Perhaps surprisingly, The result makes use of a combination of Talagrand's comparison inequality (which arises from Talagrand's fundamental "generic chaining" approach in empirical process theory Talagrand (2006)) and some techniques from Kong et al. 2020 Here, we state a version of Talagrand's comparison inequality that appears in Vershynin (2018).
Lemma C.1. Let (Wa, [Wa)ee[K] be mean zero sub Gaussian process and (Za)ae[K) a mean zero Goussian process sotisfying I|W,- War 12 $ 111 Zo l|... Then,
E max Wa S E max Za aE[K]
(51)
KE[K]
By Assumption 4 note that
| (oXx)))@(Xxd)) (x,''')) 11 < 1.31 ((x
(52)
Thus, can define a Gaussian process Z AO) that satisfies the condition in Talagrand's inequality by choosing its mean to be zero and its covariance matrix to match the increment of the original sub-Gaussian process of o(X,.)) .). Note that such process trivially exists since can let A satisfy:
Ag,e' cov( cov Zwr) E [(o(X, a). 0) (6(X. a'),
(53)
Then, the first inequality in the theorem is satisfied with U = E max Za- The proof of the second inequality is deferred to Section C.I.I
Since 0 unknown, our goal now is estimate the increment (6 a) -((X a') 1|2 from samples. Specifically, aim to estimate the following quantity:
25

---

Published in Transactions on Machine Learning Research (2/2024)
For all a, a' E [K] such that a + a', Sa.a' == E (o(x,a))o(X,d))) = -aaaa where Ea,a' = [((((x,a) - x(X, (o(() o(x, o(x,a')) ]-
We can construct fast estimators for these quantitics using similar techniques as those developed in Kong & Valiant (2018). While similar final result is obtained in that paper by Chebyshev's 's inequality and counting, here present version that is carried out with a couple simple applications of Bernstein's s inequality. Algorithm 2 specifies the form of the estimator and the data collection procedure.
Lemma C.2. Fiz a, a' E [K] such that a # d' and define 5² ( + o²). Let ó S 1/c. Given the dalasel Dr = {a,, ai Vi with probability at least 36,
Ed/2112 C2m2 log logoo' (2d/6)
BBa - Ba S V
log(2/0)
(54)
Cim
for absolule constants C2 O.
Something to nole about this result is that it depends on ||0||- This is fairly common in sample complexily results and bandits where the size of f is akin to the scale of the problem. However, it is problem-dependert Interestingly, the applications of Section 4.1 make use of the special case when
Proof. Consider an arbitrary pair a, a' and covariance matrix Ea,a' For convenience, we drop the subscript notation and just write Σ. The argument will be the same for all pairs, including when a a'. The dataset Dn split into two independent datasets Dm and D of size m 2. Let Φ; == ((32, as shorthand and the same for o,
First, verify that Ba is indeed an unbiased estimator of Ba,a:
E 0 2 = [u.s/ Eoy = 0 200
(55)
which follows by independence of the datasets Dw and D'm and the fact that the covariance matrix under the uniform data collection policy is the identity. By adding and subtracting and then applying the triangle inequality, we have
E0' -0 = 0 D - 0 1
D +
TT
0 Vσ'
(56)
Term
Torm II
and we focus on bounding each term individually. We start with the first. Note that |10 "odle I || and ll I /= Therefore, we have that the term &l.%/ is sub sub-exponenne ex-oneentnial with parameter welll <T||E0| ~ + + E||S}||, where recall that we have defined g² = (7210000 +z²) Then,
by Bernstein's inequality,
o -oLish T 2 s <exp (-Cmin min
nt?
nt
Pr
(57)
71
|200|222
|
3E|m]
for some absolute constant probability. This implies
C
0, and the negative event occurs with the same upper bound on the
2 2
Σ 0 Ed'h - 00 Σ S +E[m)
log(2/0)
(58)
Cm
For the second term, condition on the data in D' and then apply the same calculations. The difference is that | I ||| and so the bound becomes
2 11122111 1og(2/8)
Σ (E(m)
no
00' 0
S
(59)
m
Cm
26

---

Published in Transactions on Machine Learning Research (2/2024)
with probability at least 1- 8.
It suffices now to obtain a high probability bound on [|0'],, showing that it is close in value to ||@|| Let df and 02 denote the kth elements of of and O2, respectively. Similar to the previous proof, we have that
I SE
(60)
by multiplication of the sub-Gaussial random variables. By Bernstein's incquality, with probability - 8, for all k E [d],
E / Cm
E -0l
Lunh
log (2d/0)
(61)
kE(m]
for some constant C 0. Under the same event,
dea
0 O1l
log(22/0)
(62)
Cm
by standard norm inequalities. The triangle incquality then yields
dEa
| |10|| +
log(2d/8)
(63)
Cm
Finally, we are able to put these three events together:
2 12
S 12
0 Σδ - TT E0
000
S
log(2/0) +
Cm log(2/8)
(64)
Cm
22
2c 2 log(2/0)
log +
(65)
C'
Cm
25 [E|[d llog
(2d/())
(66)
Cim²
88 | log(2/0) +V
2511
loo (2d/8)
(67)
C2m
C2m²
with probability at least 35 by the union bound over the three events.
Define Ba,a Aa.a + Astaa - 2d and ~ (0, Å) where Á is the result of the projection onto s using 3 as defined in Line 13 of Algorithun 2 Since A is positive semidefinite, the fact that
|Ba. Baarl So log(//)) Vd. log loKg(dK/))
(68)
VTi
n1
and the optimality of Á in Algorithm 2 we have
Vd. log" (dK/8) ||0|| log(K/8
Baw Baarl so
(69)
Vn
n
Triangle inequality then immediately implies the following element- wise error bound on the increment
18a, Baarl 50 [10]] log(K/0)
Vd log (dKK/)
+
(70)
Vn
with probability at least 1-8. 5.
Now we apply the following error bound due to Chatterjee 2005
27

---

Published in Transactions on Machine Learning Research (2/2024)
Lemma C.3 (Theorem 1.2, Chatterjee 2005 Let W and W be two Goussion random vectors with EW EWa for all a E [K]. Define Va.a Then,
W War liž. and Ta.a' = I|. Wo Wo.lli, and r = maxa,a Hia,a Va,a" /.
E max Wa E max Wal S Vllog K aE|K]
(71)
aE[K]
Therefore, by the union bound over at most K² terms Ba, the final bound becomes
(
Logg/o n/44
d/4 log 3/2 (dK//)
U E max Zal so [E(K]
(72)
Vn
with probability at least 1-6 8.
C.1.1 Proof of the second inequality
Here we prove the second inequality in the theorem stalement that vlog K V 2 U
Lemma C.4. Let (Wa)ae [K] be mean zero sub-Gause Gaussian process such that |Wo Wor 1p S IW - Wa Welle then
max W. 2 max
||
War 1|
(73)
[E[K]
a,a a.a' E(K]
Proof. Let random variable Wo, Wy achieve the maximum for ma IWa Wo
E [ Wa 2 E max (W, Wo) Define Z = Wy Wo, then
Emax(Ws, Wy)
=E s Pr| < k] 2|2
2Z 02
=E|Wi|Z < - <0 Pr 0| E|Z Pr 0]
=E[W]] E > P|Pr
=E|ZI > Pr|Z > 0]
Since E > 0) Pr 2 0 Pr < 0] 0, have
E Z 0) Pr 0 /1
(74)
Thus, we just need to lower bound Z|] Due to the Gaussian assumption on Z, it holds that for a constant Ko,
2
Pr Pr( exp(
Ko 2 12
Let C be constant such that
t2
texp(
dt
Kol
|
1.a
C2
=KollZ1122 exp(
Ko
= =|2112//20
28

---

Published in Transactions on Machine Learning Research (2/2024)
Then,
1 =2 % tPr(1Z] > t)dt
C1171122
2
/Pr(1 t)dt +2
[Pr( > l)dt
CI
C1121122
12
le2
[Pr(1 1)dt +2
texp(
)t
0
O1121122
Ko | 1/
S
<201|ZI112
Pr(IZ] > t)dt + 1111/2/110
s
2C L2 [|] + /
This implies that [[|2]] 2
20c LZ Combining with Equation 74 yields
E max Wa 2 IW Woll aE[K]
Proposition C.5. Let (Za)aE(K) be a mean zero Gaussian process, then
E max Za S log K max [[
- Ze- 112
(75)
K
Proof- This is simple corollary of Sudakov-Fernique's inequality (see Theorem 7.2.11 in Vershynin (018))- ) Define mcan zero Gaussian process Ya, [K] such that each Y. is sampled independently from NO, aa Ie Za 11,2). By Ferniqussernique's inequality, it holds that
E max Za S E max Ya. KEKK]
a[[K]
We conclude the proof by combining with classical fact that
max Y, S Vlog K max o,a
1 Zo 112
aE[K]
Applying Lemma C.4 on V+ yields
max || (Ø(X, - a(X,a'), 0) lea.. a.a'E [[E]]
By the definition of the Gaussian process Z, its increment is bounded by
max a. [.K'E(K]
()(x))) d(X,a') u|
(76)
therefore applying Proposition for U yields
S log max || (o(() o(X,a')))) 11...
a.''E[K]
This concludes the proof.
29

---

Published in Transactions on Machine Learning Research (2/2024)
C.2 A marginally Sub-Gaussian bandit instance that does not satisfy Assumption
Given constant C, let define bandit instance with K 2 follows:
((X,1) ~ 1)
(77)
(xX2) { - ir -X(X1)
1(x,1)
if lo S C; C.
(78)
Since the marginal distribution of o(X. 1) and (X,2) 2) are both NO, 1), it is easy to see that sub-Gaussian
assumption of the Preliminaries (Section 2 is satisfied. To see how Assumption ffall to hold, we compute the sub-Gaussian norm and Le norm of == ((X, and thus | vl @(1). For the L2 norm, note that | ZlIL, O 1² exx((=t)ddt) = O(C² exp(-C") which be made arbitrarily small by choosing large C. Therefore for any constant T., there exist bandit instance such that the marginal sub-Gaussian assumption holds but Assumption does not.
o(X, 2). Notice that Z has Gaussian tail when |2| > 20,
C.3 Comments on zero-mean features
We have originally assumed each arm has zero-mean features so that E (o((Xa)) [Ø[(X, a)] = 0 for all a A for simplicity. To deal with the non-zero case, it is not sufficient to simply estimate the individual means and subtract them off, as it would yield an incorrect estimate since we aim to estimate the expected max of a random process. If the true process is indeed Gaussian, we can estimate the means and set the estimated Gaussian process Z have the estimated means. However, doing so with non-Gaussian processes would require more sophisticated version of Talagrand's comparison inequality, and this kind. There are less refined alternatives such adding back the maximum estimated mean using centered Gaussian process Z with large enough increments to subsume the means. Both would guarantce an upper bound on V*, but could affect the tightness of the bound in different ways.
unaware of results of
D Model Selection
The algorithm that achieves the regret bound in Theorem g presented in Algorithm 4 exposition, we first present this result assuming known (identity) covariance. Unknown covariance is handled Appendix D.I. Here, we provide some further comparisons with existing literature. State-of-the-art model selection guarantees have typically exhibited tension between either worse dependence on d, worse dependence on T' For example, Foster al. (2019) Lee et al. (2021) and our work all pay leading factor of T2/3 while maintaining optimal dependence on d.. In contrast, Pacchiano et al. (2020b) gave an algorithm that gets the correct /T regret but pays da dependence. It has been shown that this lension is essentially necessary Marinov & Zimmert (2021); Zhu & Nowak (2021), except in special cases (e.g. with constant gaps Lee al. (2021)) or in cases that assume full realizability. Thus, our improved model selection bound contributes to the former line of work that maintains good dependence on d, at the cost of slightly worse dependence on T.
For ease of
30

---

Published in Transactions on Machine Learning Research (2/2024)
Algorithm 4 Model Selection with Gaussian Process Upper Bound
Input: Rounds T, failure probability 8 I 1/c, constants Cu. C1 2: if Ea, Ea,a' E are known for all a, a' E [K] such that + a' then Set lmii = Co // (T log T/
4: Set ar C1 d//1 2 (Kd21/8)
1/3
else
Set Emin Co (1+ 3/2 (Tlog KT/0) S (d2 +
Log log(K/00) + d2 log(K())))
7: Set C1 dan (d,T/)) + C2 d: (KdT110))
11/2
0/3
8: end if
9: Initialize exploration dataset So = {}
10: Initialize algorithm Algi t (xi)
11: Sampler Bernoulli Ze ber(t-1/3) for all [T]
12: for = ,,..,, T do
13: Sample independently 2t D and
14: if Zi =1 then
15:
Sample a, ~ Uni[[K], observe Y)t
16:
Add to dataset: S = (Iz, at 4t U S
17:
= T-
18:
clse
19:
Sample a from Alg observe yt
20:
Update Alg, with (Ze, ae, Vt)
21:
S. = S
22:
= Ut] Tz-1
23:
Alg.+1 t Alg,
24:
end
Estimate Ü, from exploration data S, and covariate data Te (if unknown covariance matrices)
25:
26: if t 2 min and U, > 20, then
27: Set algorithm Alg4+1 (xp4-IX(Fz)
28: end if
29:
end for
The main idea is that the algorithm starts with model class Fi, the simpler one, and runs Exp4-like algorithm under Fi. However, it will randomly allocate some timesteps for exploratory actions where the uniform random policy is applied. From the exploration data, if it is detected that the gap is non-zero with high confidence, then the algorithm switches to Fg. The critical component of the algorithm is in detecting the non-zero gap and then bounding the worst-case performance when the gap is non-zero but it has not been detected yet.
We require several intermediate results in order prove the regret bound. The first is a generic high probability regret bound for variant of Exp4-IX given by Algorithm 4 of Foster et al. (2019), which is modification of the algorithm proposed by Neu 2015 In particular, define
0, := arg min BERd
Σ aE(R]
Ex
K
01
0un = 0₂
and
V == max V
0
=ell;
where II; : for + arg max, (2, TOTO : E Rdd the induced policy class. Let Ty, be the argmaxx policy induced by 9:. Note that the policy тe, may not be the same the policy that maximizes value.
31

---

Published in Transactions on Machine Learning Research (2/2024)
Lemma D.1 Foster et al. 2019 model class F; salisfies
Lemma 23).
With probability at least - 6, for any E [T], Exp4-IX for
00 V Ta. V 1=
(o ditt log(d)))((; log(TK/6))
(79)
The second result we require high probability upper and lower bounds on the mumber of exploration samples we should expect to have any time i e [T]. We appeal to Lemma of Lee al. (2021) as the exploration schedules are identical.
Lemma D.2 (Lee el al. (2021) Lemma 2). There are constants C1, C2 > O such thal, with probability 1- 8, C,22/3 < S S C2t2/3 for t Co (Tllg T/6).
The last intermediate result leverages the upper bound estimator from Theorem We will define Gaussian process, which we prove will act as upper bound on the gap in value between the model classes. Let Z (0,,A) where
Na,a' =B [K a), Oai)) (ø(X, ('),,'), a'), 0am))
(80)
01
The following lemma establishes these upper bounds and shows that we can estimate E max Za at a fast rate. The critical property of this upper bound that it is 0 when
for all a' E [K] and Oai = 02
Fi satisfies realizability.
A simple transformation of the feature vectors allows us to apply the results from before. For datapoints
0
(o,, Qg Wi) collected by the uniform random policy, the following is an unbiased estimator of 02
0
yi (((2(1r)) p (vi(sr) y1 (02(zz)) - (o)((r..a)))) = Yi (ddsds (Ix, an)
((
(81)
where Odadd denoles the bottom d2 - dj coordinates of the feature map s. As shorthand, we de- fine (z) ddiid, (x. Note that l S and this feature vector still satisfics the con- ditions of Assumption 4 as we can simply zero the top coordinates. Furthermore, define Ea. E (Ø(X, a) - a(X,a') (Ø(X,a) o(X,a') for a # a'. The estimators for this transformed problem are then
0 1
y:
(82)
m
0' 1
(83)
m
And, as before, the quadratic form estimators are analogously
Baa = 0 TT E'
(84)
Lemma D.3. There is a constont C such that the Gaussian process Z
V F < 20 max Za KE[K]
(85)
and, with probability al least 1 55, for all n E (T], the eslimator Ó definedd in Algorithm 4 samples satisfies
with n independent
V100 log(TT()) (KK/5)
//4 log
3/2 3/2 (dg
E max Z. - 5 [E[K]
(86)
n/4
/n
32

---

Published in Transactions on Machine Learning Research (2/2024)
Proof. It is immediate that
V
max V V
(87)
sell.
since 01 E F by definition and To, is an argmax policy.
This gap can then be bounded as
V' t = 1800 - V
(88)
E (d2(X, To, (X)). E (X2(X, no, (X)). 82)
(89)
E (d2(X, To, (X)).02)
(d2(X, To, (X)). B2)
(90)
E (81 (X, no. (X)),01
(X, no. (X)), 01)
(91)
[6]]
E Φ2 no, (x)).
[0]
+
Φ (X, na (x)),
[0]
82
(92)
[0:] [0]]
[0]
E max aE[k]
(22(X, a).
+E max aE[K]
(2((X, a)
02
(93)
The Gaussian process Z (0, A) satisfies the conditions Lemma upper bound on both of the above terms and, thus, the first claim.
C.1 which implies the Gaussian process
Now prove the estimation error bound. We apply Algorithm with the constructed fast estimators for quadratic forms 0 Fa. Oaitt for all a' E [K]. Let 7 ~ N(O, A). We can apply Theorem 2 and get
[V]lQur) ( 1/4
(og(K(0)
d2 1/4 log 3/2 (d2K/8)
E max Za E max Za 1 aE[K]
(94)
aE|K]
Vn
Sctting Ū E max Za gives the result.
Lemma D.4. Let Ú be the estimate of E maxae[K] La from Lemma probability 1 8,
D.3 using the same method. Then, with
E max Zu S CÚ Colog" (/gg o (110sg01111 dz 1/44) log( (d2K/8) log (2((K)
(95)
vn
for some constant C' 0.
Proof. Here we let C represent an absolute constant, which may change from line to line. For this, we require a multiplicative error bound, which is stated formally in Theorem 6 It is similar to the additive
one developed in the proof of Theorem 2 From Theorem 6 and applying the union bound over all pairs of actions in [K], we have with probability at least - K28, for all * a.
Ba.a' 2c
01 + d) log (d2/8)
|Ba.'' -Baarl <
+0
(96)
n
where we simply prepend 1//2 A and the estimators and c 2 be chosen later.
With this concentration, we now show that if Ó =E [maxae[K] Z. is small, then this must mean that ma Ba is also small.
( (0)² N E max Z.
(97)
[K]
C
1| 11.2
(98)
a. a."' agta'
Ban'
a(l1aamnl + vdz) log (d2/0)
=
max Ba.a a,"'
(99)
2c
n
33

---

Published in Transactions on Machine Learning Research (2/2024)
for absolute constant C. The second line uses Lemma c The third line uses the concentration above. Choosing large enough (dependent only on absolute constants), we get
(110aurll log) (d22())))
max aza
Ba,a' S 200
(100)
n
Then, from Proposition
C,5
we get the statement:
max Ba,a' CÚ Vlgg O (110air) 1|/2 + d3 log(d2/0) /d) log (K) aFa
U C /og K
(101)
n
Changing the variable 8' = =//K² gives the result.
Armed with these facts, we can prove the regret bound. Tet E Fn n R2 O Fg 0 E4 denote the good event that satisfies the conditions laid out in the intermediate results where
Ej is the event that EOEr ToH, v S0 (VV log(TK/))) for any interval of times
up I T.
Eg is the event that C/8/3 |S | I C2t/33 for 2 fiin
3. Eg is the event that the following incquality is satisfied for all tiin S
v VIlaaul log(TK/0)
d log (dgK
E max Za aE[K]
(102)
f2/6
f1/
4. E₁ is the event that the following is satisfied for all émin St5
V v CÙ. log (2((K) O (110ame)) ) log (d2 (T2K/////))
dz/44
log log (K)
(103)
/l/
Proof of Theorem with known covariance matrices. First note that event E holds with probability at least - 46 via an application of the union bound (over 7') and the intermediate results. We now work under the assumption that E holds. The proof is divided into cases when Fi does and does not satisfy realizability.
First, we bound the instantancous regret incurred during the exploration rounds. Note that the average value of the uniform policy is zero and V* < O ([1o)]/lo K) by standard maximal inequalities. This establishes the bound on the instantaneous regret for these rounds.
When Fi satisfies realizability, the algorithm already running Exp4-IX with model class Fi from the beginning, so we are left with verifying that a switch to F2 never occurs in this setting. This can be shown by realizing that E ma Zo whenever F, satisfics realizability. Thercfore las 0 and, under the good event, we have that
1/4 log (d2K18)) O, S C
(104)
12/3
for a some constant C' > 0. Therefore, for C1 chosen large enough, Ú, < 20g for all 2 tmin and thus a switch never occurs. In this case, the regret incurred
Regr < 2ō log log (2()) VdiTK (oTTKoogdd log(di) log (og(TK(8)) (min
(105)
where the first term is due the upper bound on the number of exploration rounds in Eg and the second term is due to the regret bound for Exp4-IX under model Fi.
34

---

Published in Transactions on Machine Learning Research (2/2024)
2. In the second case when Fi does not satisfy realizability must bound the regret when the algorithm is still using Fi. The regret may therefore be decomposed as
Regr S -Voe)) to
V V Σ - V
(106)
EE|L]
where 1a is the timestep that the switch detected. From ix onward, the algorithm runs Exp4-IX with F2, so this last term simply bounded by O(vd2KT) under event E. The same is true for the middle term.
Note that before the switch occurs it must be that Úr,-1 S a1,-1. Therefore, from event E,
[[10ase]] 1/2 d//'t) Kog(d2KT/8) log (
V vao S 10000oog//100 (KK) +0
(107)
1\/
1/4 log
3/2 log3/2 (d2KT/8) log (K)
0
(108)
///3
for f t= =t 1. The final regret bound for this case is then
Regr S o do 2//4722/3 3/2
/ (d2KT/0) log' log' (2())
(109)
+ ( (vd, (oTTKl (Tg(TK/8) + v log(d)) log(TK/6) + (min
(110)
D.1 Contextual Bandit Model Selection with Unknown Covariance Matrix and Completed Proof of Theorem 3
Here we consider a modification of Algorithm and the proof of the previous section in order to handle the case where the covariance matrix unknown. The addition is small and follows essentially by showing that the estimated covariance matrix close to the true one while contributing negligibly to the regret. Throughout, we assume that Σ pl for some constant p and p 2(1), which is also assumed by Foster et al. 2019). We will use the fact that O(1) and ||0. O(1).
Let the time & be fixed for now. The covariance matrices are estimated from all previous data during non- exploration rounds. Let T, denote the times up to time for which a non-exploration round occurred as defined in the a algorithm (i.e. 2, = 0 for s S T,) For o d', we have
Σ
K
sETr.a
Σ = K
Σ
Φ2(x,, a) a))
SE TET..a
E..
Σ
(dla,, a) - GlIs, a'
(6((),))))) (o(xs,a')(((( "((
Tr
RE
Ean
Σ (l.,, a) a) RE
We also define Σ, E', and En,e' is defined before. Note that for t C1 for some constant C 0, event Eg ensures that ITal 1. Proposition 12 of Foster et al. (2019) ensures that the following conditions are satisfied with probability at least 1 8
1 1-6 < 1/2 . 1111,, 11) < 1/2 1/2
x 1/12 $1+ te
35

---

Published in Transactions on Machine Learning Research (2/2024)
for all e {1,2} where 5 50r2 do+tog(8K2// and thus we will require that P7l
T² Imin- Co (i log (T KT/0) + P (d2 log(8K27/00) d2 log log(KT(8)
(111)
for a sufficiently large constant Co > 0. For here on, we will assume that 2 mii-- Note that this new choice does not impact the regret bound significantly since Eiin does not influence the regret under model class Fi and under model class Fe it contributes factor linear in d2 but only logarithmic in T. Observe that this choice of min for sufficiently large Co ensures that 1/2 in the above concentration result.
For convenience, we let 1,,1 denote the di-dimensional features while os,2 denotes the dz-dimensional features at time s < t. Note that St is the set of past times of uniform exploration to point time t. We split the dataset S; randomly evenly into and let S, and S₁ denote the time indices of each dataset of size 18 We consider the following estimators:
02-
E-1
Σ
c as)yss
(112)
m7
sES.
0, = E-1
Σ
Φn (x aslvs
(113)
sES:
and the difference
0aif
222
h-1
S-1
0)
Σ
2u.200
eES.
Σ-
aaf
Eng
E [de.
and we analogous definitions to define 8lr and Gaut with the other half of the data S. Proposition F.1 ensures the following holds.
Proposition D.5. For fized t with Iiin S STST, T with probability at least 1 - 5, for all a',
0T o O'asr
( O 12/3
[og (og((dd2T/0)
Vd2 log (ogg(K))T/8) -0 (de (ddd)-oo((d/77 log(Kd2T/0))
-10 110desf2a.oo 0 O
and
TT Tiss O's
S <C2 aag 0 + O log(Kd2T/0) +
Vilg 12/3
log (Kd:T//)))) + +0 d2 log (d2T/5) 20
t
for absolute constants C1, C2 0.
Proof. The proof follows almost immodiately from the general result in Proposition F.1 with dataset S.. Recall that event. E2 asserts that
2/3 < 1S S 2/3
We then have that that [T and therefore O ( (i/tlg((//)) for all covariance matrices with
probability at least 1 - 26. We also set = Saws, consisting of [Tll samples. It remains to find such that || Âll 6p and verify that eg ((1) for sufficiently large A covering argument suffices.
36

---

Published in Transactions on Machine Learning Research (2/2024)
Let N()) denote the y-net of the unit ball in d2. Then,
A - All S (1 27)
max yEN(1)
(A - (1)..)
(114)
Note that [N())] Odd for some constant C, setting 7 = 1/4. For all E N(7), by applying Bernstein's inequality, we have
v- (A= (d d2 log(1/0) +
Σ y (A SET:
(115)
T
t
for all y E N(6) with probability at least 8. Therefore, we ensure that eo - O(1) for t = M(d2 log(1/6)),
which accounted for in the new definition of min-- Applying the union bound over these events and a change of variable 8' = 10K28 gives the result.
Using this new concentration result, we can immediately replace Lemma D.4 with the case when the covari- ance matrices are estimated from data.
Let Ej and Eg be the same events as E and Eg defined before. Then define the following new events:
Eig the event that, for all such that min SIST,
(
Vdl log (d2T/8)
d//4 log 3/2 (K (d2T//)
U, S + V Ba log K + +0
t1/2
1/3
2. E4 is the event that, for all such that tiin StST,
(d2 (d2TT/))
d
1/4 3/2 (KdTT/8)
U S Uio + KO
t1/2
f1/3
Finally, we define the intersection E" = E N Ey Lemma D.6. E' holds with probability at least 45.
Proof. Events Ej and Eg each fail with probability at most ô as demonstrated in the previous section. Now we handle Eg. Let Ba, = TTg Oaif and lot Ba = - E.. & denote its estimator at time t.
Lemma C
shows that
UU+ +
max Baa''t Baal log K a,a'
Baya log K 0 Vil2 log( Kd2T/5) log K aaa
1/4 log (og(Kd2T/)))/)
$ U
max
V
11/2
(1/3
where the second line fails for any Imin StS with probability at most by Proposition D.5 and a union bound.
For event Ey. may follow the proof of Lemma D.4 but instead leveraging Proposition D.5 and lower bound Ū, with
(ti) max Ba, -0 a,a"
0 d2 log loggoKK22]1 Kd2)/)) d log (Kd2T/O)
ldglog(())))
12/3
37

---

Published in Transactions on Machine Learning Research (2/2024)
where the last line fails for any mmin St T with probability at most 8 following union bound. Applying Proposition
C.5
U /ogK K.
Ymax Paga
Nogg+O/ (dssbbo(kk)//1 log K d log (Kd2T/8) /olog//////// K
0 Vlog K +0
22/3
which implics E
Proof of Theorem with unknown covariances. The remainder proof of Theorem 3 is now identical to the known covariance matrix case except that there is an estimation penalty of Ô Vdz/t) which is incorporated
into the test via the updated definition of a and the slightly larger value of bmin- This contributes only a factor of O (Vd2T) to the regret in the case where F2 is the correct model.
E Testing for Treatment Effect
E.1 Setting and Algorithm
Here, we describe in more detail the treatment effect setting Section 4.1.2 As further motivation for this setting, consider the studiod problem of dociding whether to issue rido-sharing services for primary care patients
reduce missed appointments. A priori, it is unclear what interventions (e.g. lext message reminders, ride-share vouchers, etc.) might actually be effective based on characteristies of a patient. In such cases, we would be interested in developing sample-efficient test to determine this.
We maintain the assumption throughout. that r" a) (o(x,a)))) The primary difference between the models that we may either use all actions A-UA2 (which may be costly from a practical perspective) or just the basic set actions in Ai. There is a known control action ag in both Ai and A such that Φ(x; ag) We will assume throughout that |Aq Agl K. We assume that there is at least one action other than the control ag in A2. That is, |A2l 2 2. Since there are potentially two action sets, there is now ambiguity in the definition of Σ. Here, we use Σ [ Eoes, Eø(X,, (X,a) and assume Amin (E) > p 0. However, we could just easily define it with respect A A2 and then the algorithm would change by taking samples uniformly from Ai U A2.
More specifically, we define the lest as
0 0 0SC111
dlog (dK/ C2
d//4 log 2
P
/n
herwise
for sufficiently large constants C1, C2 > 0.
E.2 Analysis
Lemma E.1. Let A V VT. There exists a constand C > such that
A C Ex max Zn
aελz
where Z (O, is a Gaussian process with covariance matrix A and
Aa,a' = TE ())
Ana TE,0
for a, A and + d'.
38

---

Published in Transactions on Machine Learning Research (2/2024)
Proof. Define the following alternative feature mapping e A1 U A2 - R
Φ(z, a)
(xx, a) =
ATEAA
((x,a)
Note that we still have ex(x, ao) = for the control action. Furthermore, it readily seen that r" a)
(0(2, a), (122))) a):
for all X and a E A U A2. Then, the gap can be bounded above by
0
A
Ex
max
a),
max aeAi
(x(X,) a), (e(X,,) a), (0)
AEALUA2
Ex
max
((X, a),
max aEA:ULAs
[0] a))
< Ex
max
0EALUA2
$ Ex max (Ø(X, 0) AEA=
where the second line follows because have assumed that dg E A1 and thus value of 0 is always attainable in Ai. The last line follows for similar reason since do A2 also. We may apply our result in Theorem 2
which guarantees that the Gaussian process Z majorizes {o(X.-) with Ex maX a), - C
E max Za for some constant C' > 0.
Proof of Theorem No additional treatment effect
First, we consider the case where there is no additional treatment effect by A2. That is, by definition Ex maXaEda (6(X, a), Lemma C.4 ensures that
max
|| (Ø(X,
0) |1 Ex
Ex max (),X aeAz
0, agtan
Since 0 TT Ea = (6(X,a) ((X, 0) I|. we have that U = E mmxx Zu = 0. It remains to show that &
concentrates quickly to U. For this, we leverage Proposition F.1 First, we must verify that [Fa Sin ||-
An identical covering argument in the proof of Proposition D.5 shows that || Ea = O(1) with probability least - 8 for p dllo((166).
Proposition 12 of Foster et al. (019 ensures that the following conditions satisfied with probability
least 1
1/2 - <
(3-1/35X-112)
1/2 (I-1/285-122) max
S 1 +e
min
(
(v
where < 0
dotl0/(8/8)
Therefore Proposition F.1 yields
P
dlog(dK/8))
(dK (dK/5)
Eu.o 0 + Ø Va.a S TE
P
n
= [dlggddK0) (dlo/((KK/))
and
[dlog(dK/0)
Valog (dKK/)
0T 00 2 En.00 0
(116)
P
n
(117)
39

---

Published in Transactions on Machine Learning Research (2/2024)
for all a' E A2 with # d' with probability at least 1 - 8. Therefore, under this event, conclude that
0 +U+
max 13,,' l llg K
(118)
V
0,a'
(v dlog
dz/1 log (dK/6) dlogg (dK/6)
=0
(119)
p
vn
By the definition of the test, this implics that v 0 with probability at 5 when there is no additional treatment effect with A2
Additional treatment effect Next, we consider the case where there is an additional treatment effect. Following the proof Lemma D.4 and leverage the result of (166,, we have that
d log( dlog(dK/0 (dK/6)
0
max a,a' EAa t'
fa.a
C3
C4
p
71
for sufficiently large constants C1 C2 > 0. Therefore
A SSU
(logg(dK)) + C2
d²/4 log (dKK/))
Ú -.VIog K Csp
Vni
In other words,
A Vlog K
dlog(dK/8)
d log'lo < Ō
Csp
C4
/n
p
Therefore, for A =2 (V
d Ing ( (ak/a) /logg (dK/8)
we can guarantee that the left side is least
/n
Ci dlogg (dK/8) + C2 d'/4 2/3 (dK/6)
ensuring that V =
Vn
F
Unknown Covariance Matrix Case
Our goal in this section will be to extend the results developed in the latter half of the paper to the case where the covariance matrix is unknown. The first subsection is dedicated to establishing strong concentration guarantees for estimating quadratic forms in general regression setting. Following the general analysis, we will demonstrate an application to contextual bandits.
F.1 General estimation
In this section, we consider the abstract regression selting where we observe features and responses (Φ) y) where @ E R is a random vector and e satisfies @ T + 17 for some unknown parameter 0 e Rd and zero-mean noise 7).
As before, we assume that subG(72) and 7~ (a2. We assume access to two independent datasets of E N samples given by D (Ør, vi [i)emm) D' (0/, v/ [e[m)- Furthermore, we consider features g((1) E Rd which are the top di coordinates of o where di < d. We also consider third dataset of size m { hiemi where Rd and 2; subG(C72) for some constant C > 0.
40

---

Published in Transactions on Machine Learning Research (2/2024)
Define the following notation:
Σ [00 J = P
) (00 T =p
((1) arg min E
(0 -
y)²
6ER91
((1)
Oaa 0
0
(E(1)-1 0
R E-
0
0
(Sa)
Rt = ---1
A = Eziz
Å 1
Σ 2,22
m vE(m)
where E and 5(1) are estimates of E and ()) (independent of D and D' and {zi)) satisfying
e S 1/2 Σー 1/2 112) <
1/2 (5-1/285-1/2) 11+c
(120)
and the same for {(1) and (() where < < 1/2. We will further assume that ||A - Âll S 6n for some Eu > for Eo = (1). Note that this setting also subsumes the case where d1 = 0. Here, we must just make the adjustment. that g = 0 and define its inverse to also be zero. The remaining calculations are agnostic
this.
Our objective in this section will be derive general high-probability error bound on the difference between Tig AOint and 0 Ti A dif where we define the estimators
Rt
Σ
(121)
m vE[m)
1
0
R
(122)
diff
m
ve(m)
Proposition F.1. With probability at least 8,
1og(2/8)
Vd log (2d/8)
R 2 Go0g
+ + +
(123)
t
m
and
i B & C20 C2 o log(2/0)
Vd log log2(2d/)))
+ + +
t
m
for conslants C1, C2 0
Proof. We first make the important observation that Rd Φ.8; is an unbiased estimator of Oan- It therefore suffices to show concentration of & to its mean and then bound the error between ft and Rt. We must also bound the error due to the difference between À and A.
41

---

Published in Transactions on Machine Learning Research (2/2024)
For convenience, also define i := 1. EiElml Psys and Ø == Eielm) 0'34 and μ E [ddy]
E8. We will
achieve this goal by series of applications of the triangle inequality:
ATAARR Adn = PTR pt p AR
(124)
R A
(125)
+ A0am - AOnn
(126)
We will bound each of the three terms individually.
Second Term
TRARR' - =M ARAR μ AR
(127)
( ( Eiaaa' a: fV' (..)) Ea p..))
(128)
(ft n²) Aftt A p.
RRt (Rt - - p.11)
(129)
< || l6t - -Re (1 pill |lall + 11 -Rill (1A ulll |all
(130)
$ ||ÂR* ulll + || plll
(131)
where the last inequality applies Proposition 13 of Foster et al. 2019 equivalent steps. Note that
Bounding the negative follows
JÅA ÅRt All $ ||p|| || Rt ||l||
(132)
< || cc
(133)
Therefore, the prior display can now be bounded as
e || ull + |l se e (1ÂRt || + fe-IIARtNll
(134)
S 2 + 0 AOnn
(135)
for some constant c > to be chosen later. Here, we have used the AM-GM inequality and the fact that | All co- (()) Throughout, have used the fact
| R| -ート
Se
(136)
which follows from Proposition 13 of Foster et al. 2019
First Term A bound on the first term follows from a concentration argument.
R < JA R - p R + I0 A A A
(137)
Now again, we deal with both terms individually. Note that we have E [oyy]] p and for any vector v, I|o deyillon S <T[|b|| (T||0-]| a) E||o|]|
Let R( R0p. By Bernstein's inequality and independence of the data and covariance matrices,
|l10| (elll) log(2/0)
(v
+ El|a|| log(2/5)
I
(138)
with probability at least 1 - 8. Then, note that
|| = R A pill
(139)
< R
(140)
42

---

Published in Transactions on Machine Learning Research (2/2024)
Furthermore
| - 11 0(p
(141)
| & |A + E O(1)
(142)
Then, we can say that
Au 1112 log((/))
+C2 || (et μlll 1og(2/6)
In
(143)
m
m
(IA1/3R1 All +1) 1log228))))))
+
(144)
4c
m
for constants C₁, C2 > where the last line applies the AM-GM inequality. For the other term, we have similar upper bound by defining E Rt AR i::
1612 log (2g()/6)
| log(2/8)
P -
$0
(145)
m
And the norm is bounded
||6|| = | All
(146)
(1+1) |A
(147)
Furthermore,
|ÅR p AR $ |A || m
Σ
0. - ml
(148)
E2d
0
|
log(2d/0)
(149)
where the last inequality follows from Lemma
C.2 with probability at least - 8. Therefore,
A All + (IARN)
Edd m log log (2d/6)
1/p+1 |0|| S |ARAAl &
(150)
This yields the bound
1011 12g(2/8)
| (2/5)
MTRARE-TTAANN
150 00
m
77
| 2 log (2/6))
m
AA12 Pet 10ll
log (2/8) +
d dlog"(2d/2 m²
00
m
A
Rt
pll
Vd m
O
log (2d/8)
4c
where the last line applies the AM-GM inequality.
43

---

Published in Transactions on Machine Learning Research (2/2024)
Therefore, in total, the first term is bounded as
(1AV330U11+ +1) 1og((/6)
n TRARR
-
(151)
2c
Va
0
1log((2d)))
(152)
R
AR'
Vd log (2d/
μ
O
(153)
2c
where we have used the fact that // μ 01) under the good events.
Term III For the third term, aim to show that 0 Ada is close to 0 AQai and lever- age Assumption and Bernstein's 's inequality for bounded random variables to do so. Define W; = din (02(Is, (2 a²)) 2zz, Oaift. Note that we have [W,] < C for some constant C > 0 by Assump- tion 3 Therefore var(W,) I EW? S E[W;] since W, is non-negative. By Bernstein's inequality, we have
AQ OTIHT Aauul I
Σ W. EW,
var (W)) 12g()/5)
1og(2/8)
S C1
+
m
E B[W:]
(og((/00)
2c
o AB
+ o (log(2/0)
2c
for some constant to be chosen later with probability least 6. The last inequality follows from applying the AM-GM incquality.
Collecting all terms Now that we have shown bounds on each the terms, we are ready to prove the proposition:
From the bound on the first term, we have
THARD''S 1+ 2c P TRARR Va loo (2d/6)
(154)
From the bound on the second term,
# T Rt R P S ? (1+!) A
(155)
From the bound on the third term,
1
AanaAaaa O ( (log(2/0)
Adg $ 1+
(156)
2c
Therefore, for sufficiently large choice of e > 0 (not dependent on problem parameters), we have
Vd
+ + + log(2/0)
ATAIRR & A0an + o
looo log?(2d/0)
(157)
m
44

---

Published in Transactions on Machine Learning Research (2/2024)
For the other direction, have
1
Rd RRAAA AR' 0 0
Vd (v/
log (2d/6)
(158)
2c
m
d ABait 2 22--0 - Vdl
1
llog" log2(2d/6))
(159)
2c
m
1
(log(2/0) - 6² - -0 O
(
Vdd
Aai
log l (2d/6)
(160)
2c
m
Taken logether, the necessary events occur with probability at least. 1 106 by the union bound.
G Supporting Lemmas
The following is a proof of the moment bound in Lemma B.3
0g
M
Proof of Lemma
B.
For convenience, define (() = Φ(X, a()) and the same for ((y- Define A
0g
02
X (1) X (e)
M M
and Z
Note that z AZ MXx1 and A
By Lemma
G.3
Z
0g
Od]
subG(Cor2). Furthermore, EZ = 0 and EZZT L.- The remaining proof utilizes variation of the Hanson-
Wright incquality due to Zajkowski (2020). stated in Lemma G.1
By this incquality, there exists constant
C >>> 0 such that
Pr (IZT AZ - E E AZ 2 E) S exp
(-C ('min
* >*||A|| ))
E
(161)
By direct calculation, we have that E T AZ = tr A = and by Lemma G.2 |||| S vd(lo² + L][0|13). To bound the moment, we use the tail-sum-ccppecattio for non-negative random variables. For convenience, define σ₁ = r'||A||e.
000
ElZ AZ
Pr (IZ AZ 2 u) du
(162)
pu
Pr (IZ AZ 2 v)
du
(163)
100
puR-1 max
G=2 e
e
Cu
du
(164)
00
Ce2
pu le of du
p
l de
(165)
The first incquality used Lemma G.1 Consider the second term first. Let r Cu/o1. Then, by a change of variables,
( p 3p(o,/C)p
p- 1 du = p(o,//pp
(166)
CCriicalll, Lemma G.1 applics quadratic forms of sub-Gaussia Gaussian,, dependent random variables, rather than requiring the
coordinates of Z to be independent the traditional Hanson-Wiid -right incquality Rudelson ct 2013 Hanson & Wright 1971). As consequence, the second in the minimum the above tail bound dependa on || as opposed the operator A|]. Further discussion may he found in Zajkowski (020)
45

---

Published in Transactions on Machine Learning Research (2/2024)
where we have used the Gamma function inequality So r 3p" Vershynin (2018). Consider the
first term. Let r = Cvu /of. Like the previous part, we may apply change of variables.
[ pu -o -
/
e
dr
(167)
2 0
C
rc
o
/
000
r
1
rr
(168)
2
C
$
3p
o
(2/2)
(169)
Taking these two together,
$
1/8
[R|Z AZI2) 1/8 < 3y(ai/C) of
3p 2
of c
(1/22)0022
(170)
Vp),
(171)
for some other constant C' since // is bounded by a constant. Since we only consider p 2 1, the claim follows.
Lemma G.1 (Restatement of Corollary 2.8 of Zajkowski 2020 Let X ~ subG(??) be a centered random vector in IRd and A E Rdxdd Then, there exists a constant > 0 such that
Pr (x - E [XTAX]]] S exp (-Cmin
g²
)
(172)
where 1ee is the Frobenéus norm.
Lemma G.2. Let (d,y) be generaled under the uniform-rundom policy- Define M = EE [T] and A =
0. M Under Assumption 2 ||||| < L|1011 + o² and ||||E S /d[L[1012+0??
0a Oa}
Proof. By definition || sup, || AT sup,. [|]|== u7 M
| where in denotes
M A
0g
the first d coordinates of v. The first equality follows since A A = semi-definite,
Since M is positive
0g
O&
|| =
sup
v Mv
(173)
vERd
||
sup E [32 T 2)
(174)
vERd
||||=1
sup
E [ T (o 0)² +E (00 ?)
(175)
vERe
||||=1
(176)
The second term is simply E,i² o² since EdgT Tla and Φ and n are independent. The first term may be bounded EE u)) T) < L-E E (o u) first claim. For the second, note that ||| tr A A = tr M M < d||M|| and the second claim follows by applying the first.
E ( TTT20 0)2 -| by Assumption This concludes the
X Y
Lemma G.3. Let X, Y subG(r2) be two independent hab-Gausiian vectors in Rd. Then, Z subG(Cor2) for some conslant Co 0.
46

---

Published in Transactions on Machine Learning Research (2/2024)
v1 U2
Proof. Let v
E I2dd where v1, U2 Rd and | = 1. Then, v = oj + u Y is the sum of
independent sub- Gaussian variables where vs ~ subG([|v (Br²) and 02 ~ subG[[|<21 where both ||vill I and ||22|12 S 1. Therefore T ~ subG(Co77) for a constant Co > Since v was arbitrary, the statement follows.
G.1 Multiplicative Error Bound for Estimating Norms
In this section, we prove multiplicative error bound for estimating ||0]|,, which can potentially be faster. The key an application of the AM-GM incquality, similar to the work of Fostor et al. (2019). As before, we will consider a dataset n samples split evenly into D -(b.. and D' = (%, v/3 each of size m 2 Define
0
deyi
(177)
m
EE
mm)
0'
d%
(178)
m .E[m]
Then, we estimate O with Ô
Theorem 6. Let 8 S 1/e and let > 1 a constant. With â and O' defined above with total samples, the following error bound holds with probobility at least 1 ō:
c((10| + Vd) max {) log (d/6)
10 0 TT
+0
(179)
2c
n
Proof. Similar to the proof of Theorem 2 we apply the triangle inequality use Bernstein's inequality bound two terms individually with high probability.
The decomposition becomes
1 0T S
0T
0T 0T ŌT
(180)
We start with the first term. By Bernstein's inequality there a constant > 0 such that
Pr (1 - o 22) S exp (CC min
me²
me
(181)
|10|202
|0]|
since y& is sub-exponential with ll xelles $ Eli@], before. Rearranging, we have that with proba-
bility at least. - 5,
| log(1/6)
|oll log(1/))
1000 - 0
(182)
Cm
Cm
|10|
cfa
log(118)
<||0|| log(1/8)
(183)
4c
Cm
Om
where the second line follows from the AM-GM inequality. Similarly, conditioned on the dataset D, the second term in the triangle inequality may be bounded as
10 log(1/0) Cm
10
10 - 0 S
(184)
Cm
|101- (v
(522 log(1/0) Cm
log(11/)
(185)
Cm
47

---

Published in Transactions on Machine Learning Research (2/2024)
with probability at least 1 --6 8. Finally the proof Theorem
2
shows that, with probability 1-6,
d52 Cm
|10|| - ||o|| +
V
log(2d/0)
(186)
Under both of these events, have
|0 lo/(1/6)
|| log((10))
10 - 0
(187)
Cm
Cm
vdt² 22g"/2(2d/)) (2d/6)
vde² log (2d/0))
+
(188)
Om
(Cm))a/2
1012 +
< log(1/0)
||0|| log(1/0)
(189)
4c
Cm
Cm
vdt² 3/2 (2d/6)
vdg² (ogg((2d//)
(190)
Cm
(Cm)33/2
where the second line again uses the AM-GM inequality. Putting all three events together and applying the union bound, we have with probability 36,
|011
[||0|| m {) log(1/5)
cv (2d/5)
ØT 0
+
(191)
m
m
Simplifying the error term gives the result.
0
H Experiment details
H.1 Section 3.2 Experiments
We simulated a high-dimensional CB learning setting with K actions and d 300 dimensions. The problem is high-dimensional in the sense that the number of samples E {10,20,... .0..... 100} is significantly smaller than d. The contexts X are generated such that the ith coordinate of the features is distributed as independent Rademacher random variable (X))(Xa) ~ Unif(-1,1} for E [K] and we select 0 E Rd uniformly at random from the unit ball. To reduce the computational burden, we set the degree t = 2 and did not split the data =-1.
Algorithm 1 shown red (Moment). Additionally, we implemented several plug-in baselines based on linear regression: one that solves minimun-norm least squares problem (LR) and another that ridge regression with regularization X 1 (LR-reg). Figure I shows the absolute value difference between the estimated /* values of the three methods and the true value of V*, Error bars represent standard error over 10 trials.
We evaluated the estimated values of all three methods by empirically evaluating them. LR, L.-rre, and Approx were evaluated with 4000 samples. Moment was evaluated with 1000 samples since more computationally burdensome. We note that these difference in evaluation number should only affect the variance.
We approximated the max function with polynomial of degree t 2 by minimizing an & loss under randomly 2000 uniformly randomly generated points in 2_ Note that this is a convex optimization problem and can be solved efficiently. This procedure can be done without any samples from the environment. The noise for the problem was generated uniformly randomly from the set 1//2,1//]]
Comparison with Kong et al. (2020) As discussed, the algorithm of Kong et al. (020)) assumes Gaussianity, mcaning that we expect it to have significant bias in settings where the process (((X, , a), (.)}}
is not Gaussian. In this part, we demonstrate one such illustrative instance empirically. The setting is the same before except that set 0 to be 1-sparse with 0,, 10 for unknown index i, and 0 0 for all
48

---

Published in Transactions on Machine Learning Research (2/2024)
(eg
Mommett
1.22
12/1
Samp
Figure A comparison with the algorithm of Kong et al. 2020 in similar setting to Figure except that 0 is 1-sparse. Kong et. al. (2020) exhibits significant bias due to assuming that the reward process is Gaussian.
ii. We may also generate better fitting polynomials in the sparse case by concentrating the optimization problem around relevant points encountered by the reward process such -00 and 10. Figure 3 shows the same evaluation as Figure] but in this setting instead.
Note that if we take 0 to be random from the unit ball, we will typically end up with components that are all roughly of the same size meaning that the inner product (Ø(X, a), will look approximately Gaussian via something close to the central limit theorem. In such cases, the algorithm of Kong et al. (2020) may be competitive. However, this special case. In many other structured scttings like the sparse sctting above, the Gaussianity assumption becomes problematic.
H.2 Section 4.1.2 Experiments
Simulations. We constructed another simulated high-dimensional CB setting where |A1 and |Ag 2 where both Ai and Az contain control action dg where 60x, op) O for all We set d 600 and considered E (50, 75, 100, 150, 200, 250, 300} which are all smaller than d. For feature vectors, we used similar approach as the previous experiments. For a E A with a * we chose contexts with (2)) a) 1ni for the ith coordinate. For the non-control action in Ag we chose e( (2, a) ~ Uni for the first & coordinates and then choose (1) a) for the last half. We set p 2000 unlabeled samples.
We generated 0 by first sampling from the unit ball in Rd. Then, in the effect setting, set the first d coordinates to zero. This ensures that Ag does not contribute to the reward under the optimal policy 2 and thus A = 0 between the two action sets. To evaluate the case with treatment elfect, we just let 0 keep its original value. Thus A will be positive (empirically found to be so 0.133, in this case). To calculate all expected maxes, we empirically evaluated them over 2000 samples. For cach n, we rogenerated the dataset 100 times. The lines Figure represent the averages over those 100 samples and the bands represent standard error.
The tests for both methods were follows. For our method,
o Ó 5.2 (V
41/4 vn
otherwise
and for the linear regression (I.R) plug-in method, it was
0 w 0.33
v
otherwise
W is defined as follows. Using an 80/20 split of the n samples into datasets and D' of sizes | = n4n and D' Nout, we compute
0
Σ deyl
Thin
sE(min]
49

---

Published in Transactions on Machine Learning Research (2/2024)
with the majority of the data and then evaluate the difference
max Σ
aEAz (o(o), a)),
nout
sE(nuut)
The lines in Figure 2 represent the means of the test outcomes over 100 repeated, independent samplings of the dataset of labeled points and p unlabeled points.
H.2.1 Warfarin experiments
Warfarin data. We first evaluated the ground-truth effect sizes, which we take to the difference between the average value attained by a single baseline action and the average value attained by a lincar model that greedily chooses actions, when trained the dataset with the same features. Note that, due to noise and misspecification
real world data, this might not be the true effect size, but demonstrates what is achievable with linear model the full dataset. As discussed in the main text, the reward is modeled +1 if the correct dose is applied and 0 otherwise.
The data is structured as rows representing each patient with covariate features as well as a dosage of warfarin that is assumed have succeeded for the patient (up to noise) given a rate measurement of mg/ week. We divide the doses into three categories:
Low for less than 21 mg/ week
Medium for 21 mg/ week
High for more than 59 mg/week week
For patient covariates, we omitted "Medications' and 'Comorbidities' since they are difficult to featurize. We also dropped rows with missing data in the 'Age', 'Height' and 'Weight' categories. For discrete features with missing data, we simply introduced another category. The baseline performance of each single action the entire dataset is given below:
Low: 0.32
Medium: 0.56
High: 0.12
To account for non-zero means of each in this dataset and the particular structure of the features of the patients, consider slight reformulation disjoint bandit. We denote the features of patient by ((x) E IRd where d = 193. Then, assune the reward has the following model:
r' (x, Mr. (6(2).
(192)
for unknown vectors (fa)aeA and unknown values Pa. Recall that we use to denote the baseline action and a' to denote the target action. Similarly, use A (a,a') to denote the target action set.
For the linear regression baseline, we perform standard unregularized linear regression on the training dataset to learn both úa and 02 for the candidate actions. We then deploy the learned model on the validation set to estimate the expected difference:
max {par + (6(x). Ha E'A
(193)
As this relies on accurate estimation 0a, the threshold for detection scales approximately as d/nn where d is the dimension and is the number of training samples.
50

---

Published in Transactions on Machine Learning Research (2/2024)
For method, split the training set into two equal parts, randomly. Both are used to learn the parameters fla and Pe and 0a and Og. Using the validation data, we estimate the centered feature covariance matrix E. We the form the covariance matrix:
0 E0.
A
(194)
0 '0
which, we project onto the set of positive semi-definite matrices. In practice this step was not necessary since the resulting covariance matrices already had this property, but they are not guarnatced to. We then consider the normal distribution given by ((, A) and compute the difference between its expected maximum and the baseline: Ez max Za Pa: where ~ ((, A). Here, the threshold follows the rate vd/p + d where d the dimension, n the number of labelod training samples and p the number of unlabeled evaluation samples.
H.3 Hardware
The experiments of Section experiments of Section 4.1.2 were conducted on standard personal laptop with 16GB of memory and an Intel Core 17 processor.
3.2 were run on a slandard Amazon Web Services EC2 c5.xlarge instance. The
Broader Impact
While this work primarily theoretical, there are several conceivable applications of this theory that could have societal implications. Firstly, this work is meant to assist in the development of effective algorithms for contextual bandits. As result, any applications of contextual bandit research are potentially influenced by this work such as health care, ads, education, recommender systems, and dynamic pricing. Specific to this paper, we mention applications in health care and lesting for treatment elfect, specifically for the efficient algorithm in Section 4 The algorithms presented here may be useful health care settings to determine if it worthwhile to pose a problem as contextual bandit before conducting any procedures that might affect patients, even if only limited data available. Our meetinnggfo--rratteennleeeee application also has the potential to lower the sample complexity for clinical trials that evaluate the effectiveness of interventions. We advise practitioners to take note of the assumptions made here that may may not hold in practice, such as realizability and sub- Gaussianity.
51


Reviews:
[{"review_id": "LARYbCwegu", "reviewer": "Reviewer_QdYW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The author provides both lower and upper bounds for estimating the magnitude of the optimal value function, denoted as $V^*$, and demonstrates that estimating $V^*$ might be easier than finding the optimal policy.\n\n2. Experimental results substantiate the performance of the proposed algorithm.\n\nWeaknesses:\n\n1. The paper doesn't clearly establish the significance of estimating the magnitude of the optimal value function $V^$ with an error up to $\\epsilon$. While it's true that many algorithms may need to select parameters based on the magnitude of $V^$, estimating $V$ within the same order, such that $V \\leq V^* \\leq C \\cdot V$, introduces only a constant factor in performance. It may not be reasonable to learn $V^$ with such a high level of accuracy when $\\epsilon \\ll V^$.\n\n2. The sample complexity for Algorithm 1 exhibits an exponential dependency on both $K$ and $\\epsilon, which is impractical. It is not clear why the author discusses Algorithm 1 when Algorithm 2 offers significantly improved performance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The primary focus of this paper centers on estimating the magnitude of the optimal value function, denoted as $V^*$, within the context of linear contextual bandits. Specifically, the authors establish a theoretical lower bound, indicating that a sample complexity of at least $\\Omega(d)$ is inevitable in general cases. In contrast, the authors introduce an algorithm that, given lower-order moments, achieves a sample complexity of $O(\\sqrt{d}/\\text{poly}(\\epsilon))$. By leveraging these estimation techniques in various applications, the authors enhance the performance of several previous methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weaknesses.", "broader_impact_concerns": "There is no concern about the broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wTGaw9x5z7", "reviewer": "Reviewer_D4ff", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well-structured, and its claims are supported by convincing mathematical arguments.\n- Motivation and contribution are well explained.\n- The topics of this paper, e.g., the separation of complexities of $V^*$ estimation and of best-policy identification, would be of interest to learning theory communities.\n\nWeaknesses:\n\n- For me, I did not find any major weaknesses.\nI would appreciate it if the authors could take a look at Requested Changes and reflect them accordingly.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of estimating the maximum expected reward $V^*$ for an optimal policy achieves in contextual linear bandits.\nIn particular, it focuses on the question of whether estimating $V^*$ can more efficient than learning the optimal policy itself,\nin terms of the dependency on the dimensionality $d$ of the unknown parameter.\nThe main theoretical contributions are threefold:\n\n- It is shown to be impossible to estimate $V^*$ accurately with sample complexity smaller than $\\Omega(d)$ in general.\n- An algorithm for $V^*$ estimation (Algorithm 1) is proposed, which achieves sample complexity of $O( \\sqrt{d} )$,\nunder the assumption that the fourth moments of context distributions are bounded with the second moments (Assumption 2)\nas well as the condition that the number of actions and the target accuracy are constant.\n- An algorithm for estimating an upper bound for $V^*$ (Algorithm 2) is proposed, which works well under a kind of the joint sub-Gaussian assumption (Assumption 4).\n\nIn addition to these, applications to model selection and numerical experimental evaluations are given.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In Section 2 of problem setting, it is stated that the assumption that $\\mathbb{E}[\\phi(X, a)] = 0$ is easily relaxed.\nI would appreciate an explanation or reference as to how exactly this can be relaxed.\n- In Theorem 1, $C$ is described as an \"absolute constant\", but the proof suggests that it actually depends on parameters such as $\\sigma$ and $\\tau$ given in Section 2 and $L$ given in Assumption 2.\nIs this understanding correct?\nIf so,\nI don't think it is standard terminology to say that C is an absolute constant.\nI recommend to state that $C$ depends on parameters $\\sigma$, $\\tau$ and $L$.\n\nMinor typos:\n- The first sentence of Section 1.1: the $V^*$ problem $\\leftarrow$ the $V^*$ estimation problem\n- The last sentence in Page 2: (Theorem 4 $\\leftarrow$ (Theorem 4) (close bracket)\n- Equation (33): $\\zeta$ $\\leftarrow$ a typo for $\\gamma$?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "20lTq4pSew", "reviewer": "Reviewer_m8CN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The non-trivial theoretical contribution is a clear strength of the paper - the authors combine a range of state of the art techniques to derive and analyse their estimators, and I cannot find fault with the theoretical work that I have had the time to check (I must admit it has not been possible to verify all of it to the standard I might like, as the supplementary material is extensive. However, the most critical aspects seem accurate to me).\n\nThe experimental study is also sensibly chosen and well documented. It provides a nice accompaniment to the theoretical work. I think that the work as a whole is likely to be of interest to many in the learning theory and bandits communities.\n\nIt seems to me to be a weakness that all of the results focus on a setting where the underlying reward model assumes covariates can be mapped to sub-Gaussian features which interact with the regression parameters - what if the generally distributed contexts were combined directly with the regression parameters in the expected reward calculation? Would this be yet more challenging? Perhaps this is a very standard construction, that is not worth comment which I am just unaware of, but it is perhaps worth comment. \n\nA further potential weakness is the dependence on the desired level of accuracy $\\epsilon$. For your main moment based estimator of $V^*$, there remains the question of whether this $\\epsilon^{-5}$ dependence is optimal.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of estimating the expected value of an optimal linear contextual bandit policy ($V^*$), while playing the associated linear contextual bandit problem. Previous work has derived effective schemes for such a problem but under a restrictive Gaussian assumption on the context distribution. This paper considers the more challenging setting where contexts are allowed to follow a general distribution. \n\nThe authors provide two main theoretical results: 1. that under full generality of the context distributions, the problem of estimating $V^*$ to within a tolerance $\\epsilon$ is information theoretically hard, and 2. that under stronger assumptions (of boundedness and on the relationship between second and fourth moments) $V^*$ can be estimated using $\\tilde{O}(\\sqrt{d}/\\epsilon^5)$ observations, where $d$ is the dimension of the context. The authors also derive an estimator with this property and verify its effectiveness in an empirical study.\n\nThe authors also derive a scheme to estimate an upper bound on $V^*$ which is provably more efficient (it has improved order wrt $\\epsilon$) at estimating the upper bound than the regular algorithm is at estimating $V^*$ itself.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Title/terminology: I found the use of the phrase 'General Linear contextual bandit' potentially confusing, as it is so close to generalized linear which of course means something quite different, I wonder whether there is an alternative phrasing that would be less loaded? \n\nClarity around the importance of the sub-Gaussian feature map: I don't necessarily request a change, but would encourage the authors to provide some discussion in the rebuttal phase as to whether there does exist a more challenging unaddressed framework where the features are also general, and consider if such clarification would be beneficial in the paper.\n\nIn the Warfarin experiment, it seems that the only context considered are the features $\\phi(x)$ themselves, so by assumption, the features/contexts are sub-Gaussian? Therefore, could the method of Kong et al. (2020) not be compared to also? This ties in to the previous point and it may be possible to address them together. However, I would suspect I'm not the only reader that may get confused about this point, so it may be worth some effort to clarify.", "broader_impact_concerns": "I think these are adequately addressed by the remarks in Section I.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: At the end of the discussion, two out of three reviewers were happy to support acceptance of the paper. The third reviewer raised some concerns about the strength of the performance guarantees of Algorithm 1. This reviewer did not engage in further discussion about the paper, and in particular did not comment on the authors' response. Based on my own reading of the paper, I can understand where the original question of said reviewer may have come from, but I find the authors' response to be satisfactory. I recommend that the authors clarify the purpose of including Algorithm 1 in the final version of the paper so that future readers will be less likely to share the concern of reviewer QdYW.

Overall, in light of the otherwise positive reviews and my own evaluation of the paper, I believe that this is a strong submission that is definitely worthy of being published by TMLR.
Decision: Accept (poster)