Instance-optimal PAC Algorithms for Contextual Bandits
Authors: Zhaoqi Li
Lillian J Ratliff
Houssam Nassif
Kevin Jamieson
Lalit K Jain
Venue: NeurIPS 2022 Accept (2022)
Keywords: contextual bandits
active learning
reinforcement learning

Abstract: In the stochastic contextual bandit setting, regret-minimizing algorithms have been extensively researched, but their instance-minimizing best-arm identification counterparts remain seldom studied. In this work, we focus on the stochastic bandit problem in the $(\epsilon,\delta)$-PAC setting: given a policy class $\Pi$ the goal of the learner is to return a policy $\pi\in \Pi$ whose expected reward is within $\epsilon$ of the optimal policy with probability greater than $1-\delta$. We characterize the first instance-dependent PAC sample complexity of contextual bandits through a quantity $\rho_{\Pi}$, and provide matching upper and lower bounds in terms of $\rho_{\Pi}$ for the agnostic and linear contextual best-arm identification settings. We show that no algorithm can be simultaneously minimax-optimal for regret minimization and instance-dependent PAC for best-arm identification. Our main result is a new instance-optimal and computationally efficient algorithm that relies on a polynomial number of calls to a cost-sensitive classification oracle. 

Instance-optimal PAC Algorithms for Contextual Bandits
Zhaoqi Li Department of Statistics University of Washington zli9@uw edu
Lillian Ratliff
Department of Electrical and Computer Engineering University of Washington ratliffl@ue edu
Houssam Nassif
Kevin Jamieson
Amazon houssamn@amazon.coom com
Allen School of Computer Science & Engineering University of Washington
j jamieson@cs. www.eesooosssssssinsotoooooo edu
Lalit Jain
Foster School of Business University of Washington lalitj@ux edu
Abstract
In the stochastic contextual bandit setting, regret-minimizing algorithms have been extensively researched, but their instance-minimizing best-arm identification counterparts remain seldom studied. In this work, we focus on the stochastic bandit problem in the (c. 8) -)-PAC setting: given policy class II the goal of the learner is return policy
II whose expected reward is within e of the optimal policy with probability greater than 1 - 5. We characterize the first instance- dependent PAC sample complexity of contextual bandits through quantity Pn. and provide matching upper and lower bounds in terms of pn for the agnostic and linear contextual best-arm identification settings. We show that no algorithm can be simultaneously minimax-optimal for regret minimization and sestacc--depende PAC for best-arm identification. Our main result a new instance-optimal and computationally efficient algorithm that relies polynomial number of calls an argmax oracle.
Introduction
We consider the stochastic contextual bandit problem in the PAC setting. Fix distribution potentially countable" set of contexts C. The action space is A, and for computational tractability, assume |A] is finite. We have set of policies II of interest where each policy æ E II is map from contexts to an action space π C - A. The reward function is r : C x .A + R. At each arrives, the learner chooses action d, E A, and receives policy V(Tr) is the expected reward from playing action (c)) in context V(T) E (r(c, (c))]. Given collection of policies II, the objective is to identify the optimal policy т. := arg max V (T), with high probability. Formally, for any 0 and (0, 1), we seek characterize the sample complexity of
time f. 1.2.... context reward r: := (2(C,, a.) E IR with E[[a|Ce, ar) r(c,, at) E R. The value
Assuming the set of contexts is countable versus uncountable is for presentation purposes only, since it allow us the notational convenience of letting v. denote the probability of context arriving.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

identifying a policy π E II such that V(*) 2 V(T.) with probability at least 1 - 8. That is, we wish minimize the total amount of interactions with the environment to learn an e-optimal policy.
We study both the agnostic setting, where IT is an arbitrary set of policies with no assumed relationship with the reward function r(c, a); and the realizable setting, where the policy class and the reward function follow a linear structure, known as the linear contextual bandit problem. In both cases, we are interested in instance-dependent sample complexity bounds. That is, the upper and lower bounds we seek do not simply depend on coarse quantities like [II], |A|, and 1/e², but more fine- grained relationships between the context distribution V, geometry of policies II, and the reward function r C x A + R. Our motivation is that instance-dependee of a particular problem instance, allowing optimal algorithms to adapt to the true difficulty of the problem, whether easy or hard. We seek algorithms that take advantage of "casy" instances instead of optimizing for the worst-case
bounds describe the difficulty
2X
1.1 Related work
Minimax regret bounds for general policy classes
The vast majority of research in contextual bandits focuses on regret minimization. That is, for a time horizon T, the goal of the player is
to minimize E
T === r(c,, (c:)) - -r(e,,))) a The landmark algorithm EXP4 for non-stochastic
multi-armed bandits [ achieves a regret bound of VIATT (ol(T)))((()))... Unfortunately, the running time of EXP4 is linear in [I]] which is prohibitive for many problems of interest. The algorithms proposed in I achieve the same regret bound with a computational complexity that is only polynomial in T and IT]( Both approaches can be used to obtain an c-optimal policy with probability at least 1 - 8 using a sample complexity no more than LAI |A None of these works made any assumption on the connection between the reward function r and the policy class II (i.c. the agnostic setting).
Instance-dependent regret bounds for general policy classes The epoch-greeds algorithm of (26] achieved the first mnstance-dependee bounds on regret with a coarse guarantee depend- ing only on the minimum policy gap Apol == ((T.) ma (TT). In the pursuit of more fine-grained regret bounds achievable by computationally efficient algorithms,, many authors resort to the realizability assumption [6 B4] The learner knows hypothesis class H where each if E H is map f C x A - R. and there exists an f E H such that r(c, a) f (c, a) for all (c, E C A. Under this assumption, [T6] proves lower and upper bounds on the instance-dependent regret. Their bounds are in term of the uniform gap Auniform := mitteg minae r(c, n π. (c)) r( a). In general, for any policy class, they establish matching minimax lower and upper regret bounds of the form min LouutV/AA |AAlT log (H), [A]o
cool ). where Citl is the policy disagreement coefficient, a parameter depending on the geometry of H and the context distribution v. That is, these bounds hold with respect to a worst-case family of instances parameterized by Auniform and e Using the stan- dard online-to- to-bachh conversion, this translates to a sample complexity (i.e. the time required to find
Austerr
[A]g/](/ cPp. We show in Corollary 2.16 that this sample complexity is at least as large as our bounds. Further, unlike our bounds below, this sample complexity is unbounded as goes O. Recent work refines these kinds of regret bounds further, and provides minimax regret bounds in terms of the
an e-good policy with constant probability) of roughly e Aurifm
coefficient 177.
Regret bounds for linear contextual bandits A special case of the realizable case assumes linear structure for H. Assume there exists a known feature map Φ C x AA + Rd and an unknown 0, E Rd such that the true reward function is given as r(c, a) (Ó(c, a), 0.). For this setting, popular optimism-based algorithms like LinUCB [27] and Thompson sampling [33 achieve a regret bound of min (dvT, d²
Appealing to the online-to batch conversion, this translates
Anitoom
to PAC guarantee of A.nifrm instance-dependdnt lower bounds asymptotically as T + oo [19 36 These works are most similar to our setting and have qualitatively similar style algorithms. However, both approaches rely on asymptotics with large gooblem-dependee terms that may dominate the bounds in finite time. Our work is focused on upper bounds that nearly match lower bounds for all finite times.
More precise instance-dependen upper bounds on regret match
Recently, mnstance-dependee sample complexity results for reinforcement learning in the tabular and linear function approximation settings have appeared 39 40). As contextual bandits is a special case of finite-horizon reinforcement learning with horizon length of 1, their results immediately can
2

---

be applied here. However, the cost of this generality is that these algorithms have very large lower order terms (i.e., problem-dependent factors that multiply 1/ce term) making them far from optimal in our setting. Moreover, the leading order term of 39 cannot be related to our lower bounds.
PAC sample complexity for contextual bandits As will describe, all contextual bandits with an arbitrary policy class can be reduced to PAC learning for linear bandits. Once we made this reduc- tion, our sample complexity analysis draws inspiration from the nearly instance-optimal algorithm for linear best-arm identification [ The work in IC provides a simple regret bound assuming a kernel structure on the reward function, while their bound is minimax and they assume a lower bound on eigenvalues of the covariance matrix of the context distribution. PAC sample complexity of linear contextual bandits was also studied in 4 who shows a minimax guarantee sample complexity that d scales with 4 log(1/5). Similar to our work, [3] define their action sampling distribution as a convex
combination policies. Our sampling distribution, well the optimal sampling distribution, cannot be represented this way and is actually derived from the dual of the optimal experimental design objective.
Contributions. In this work, our contributions include:
1. In the agnostic setting, we introduce a quantity Pn that characterizes the instance destenee-dependent sample complexity of PAC learning for contextual bandits (see Equation D We show that Pn appears in information theoretic lower bound on the sample complexity of any PAC algorithm as -> in Theorem 2.2
To ground this, we describe it carefully in the setting of the trivial policy class (Section 2.2 and linear policy classes (Section
2. We construct an instance which any regret minimax- optimml algorithm necessarily has a sample complexity that scales quadratically with the optimal sample complexity (Theorem 2.6). This shows that no algorithm can be both regret minimax-optimet and instance-optimal PAC.
3. Finally, we propose Algorithm y whose sample complexity nearly matches the lower bound based on PII- By appealing an argmax oracle, this algorithm has a runtime polynomial in Pnl 1/e, (og()/5), [A], and log( II]), assuming a unit cost of invoking the oracle.
2 Problem statement and main results
More formally, define Fi (c1, a1, ........ Ct, at, Fr) as the natural o-algebra filtration capturing all observed random variables up to time t. For simplicity, we assume Gaussian noise in some of our analysis. At each time algorithm defines sampling rule Fe + A which defines a,+1, an (Fi):21 -ddapted stopping time r E N, and a selection rule Ft + II that is only called once at the stopping time
Fix E 2 0 and ó E (0. We say an algorithm is (c. 8 for contextual bandits with policy class II, if for every instance, at the stopping time E N with oc almost surely, the algorithm outputs रे E II satisfying (f) 2 max+en (=x - <) 2 1-8.
Definition 2.1.
The sample complexity of an (c, PAA algorithm for contextual bandits is the time at which the algorithm stops and outputs न. As we will discuss, the following quantity governs the sample complexity:
Eewe (nriic + "oitate) ((T,(c) + x()]]
PTL.
min P.EAA. VoEC xEIT(..
(1)
Rawu(r(e, n. (c)) r(c, (c))
Here, for any countable set X' we have that Ax= {p E RA Egex Pr = 1, Pr 2 0 Va E x) so that Pe for every e e C defines probability distribution over actions A. In addition we use the notation a V 6 := max(o, aa b). We begin with a necessary condition on the sample complexity for the particular case of exact policy identification (E 0).
Theorem 2.2 (Lower bound). Fix e = O and 5 & (0, 1). Moreover, fix a contextual bandit instance " = (v, r) and a collection of policies II. Then any 50,8)-PAC algorithm for contextual bandits
satisfies [ 2 PI.o log
The proof of the lower bound follows from standard information theoretic arguments 24 The lower bound implicitly applies to learners that know the distribution precisely. In practice, such knowledge would never be available however the learner may have a large dataset of offline data.
3

---

Assumption 1. Prior to starting the game, the learning algorithm is given a large dataset of contexts D {c+] where each at drawn IID from for all t E [T] and T
((pol((1/e, |A), (1)) lo)(
The above only assumes access to samples from the context distribution, not rewards or the value function. Importantly, since C could be uncountable, we do not assume 'D covers the support of v. Assumption Tis satisfied, for example, in an e-commerce setting where the context is the demographic information about visitors to the site for which massive troves of historical data may be available. Other works in PAC learning have made similar assumptions 200 We would like our algorithm to be computationally efficient in the sense that it makes polynomial number of calls what we refer to
as argmax oracle. Such an assumption is common in the contextual bandits literature [ 11 25
Definition 2.3 (Argmax oracle (AMO)). The oracle (MO {(c,, st)) is an algorithm that given contexts and cost vectors (c1, $1). ... (Cn. E C x R RIAI, returns arg max Σx= St (T (ct)).
well The constrained argmax oracle C-AMO, given an upper bound on the loss, returns arg max > 8t (Ir (c)) subject to >t 8t ( (c)) s l. IEl
In general we can implement AMO by calling to cost-sensitive classification 6 ||| and C-AMO through a Lagrangian relaxation and a cost-sensitive classification oracle 2 g Our algorithm uses an argmax oracle as a subroutine at most polynomially in E log(1/6), /6), |A| and log
(II) In this
sense, it is computationally efficient. The following sufficiency result holds for general
O.
Theorem 2.4 (Upper bound). Fix 2 O and ó E (0, Under Assumption ! there ex- ists a computationally efficient (c, (),8)-PAC algorithm for contextual bandits that satisfies т S Pn.c ITg( (1/)(//) log(1 / A.), where A. max min V(T.) V(T)). Further-
more, this sample complexity never exceeds [A]llg([]I]) (ogg())))))
The second part of the theorem follows from the first, since PIl. 2//A by taking Pe,a = 1/|.A for all (c, a) E C x A.
2.1 Inefficiency of low-regret algorithms
Computationally efficient algorithms are known to exist, such as ILOVETCCOBBANDTS KJ
which achieve a minimax-optimal cumulative regret of /T log (1g((1))8). Inspecting the proof in 3 one can extract a sample complexity of E L log([[[))) from such results (which is also minimax optimal for PAC). The previous section showed that the sample complexity of our algorithm, Theorem 2.4 nearly matches the instance-dependent lower bound Theorem 2.2 In other words, our algorithm achieves nearly optimal -nstance-dependent PAC sample complexity. However, it is natural to wonder if perhaps with a tighter analysis, the minimax regret optimal algorithm in B also obtains the instance-optimal PAC sample complexity. In this section, show that this is not the case. Indeed, we show that any algorithm that is minimax regret optimal must have a sample complexity that is at least quadratic in the optimal PAC sample complexity of some instance.
Definition 2.5 (Hard instance). Fix m E N, A (0, 1] and let C = [m] with uniform distribution, A= = (0.1) For 1,..., ,, let T. (j) = 1 = j} and define r(i,j) Aj = (1)). Then ((m)) = A and ((T.) = A(1 - 2/m) for all i E C (1)).
Note that for the hard instance, m |T] If observations are corrupted by N( 1) additive noise, then straightforward calculation shows that PILO = (25/m}z = mA for the hard instance.
4/m
Theorem 2.6. Fix 8 10, and A E (0. We say an algorithm is an a-minimax regret algorithm for some a > O and all T E N:
R maxE, a
((rleo t=1
max (Ta (c)) S VoLAT c,a
where the maximum is taken over all contextual bandit instances pl (V'r') and (T,
Et 1fc,- = c, c,a;- = a}. For any a-minimax regret algorithm, is (0, P) if at a stopping time it outputs the optimal policy n. w. p. at least 1 - 8. Any a-minimax regret algorithm that is (0, -PC satisfies [y]r] 2 m² A -2 log2 (1/2.48) 4cx for the instance μ (v.r) defined in 2.5

---

We point out that the minimax regret optimal rate takes a = log(m) = (I)). Thus, taking A = and 0 0.1, the minimax regret optimal algorithm has a PAC sample complexity of m² log(m); whereas the PAC sample complexity of our algorithm, Theorem 2.4 is just log(m). That is, algorithms with optimal minimax regret have a sample complexity that least nearly the optimal PAC sample complexity squared. This demonstrates that no algorithm can simultaneously be minimax regret optimal and obtain the optimal PAC sample complexity.
2.2 Trivial policy class
As a warm-up to discussing linear policy classes, let us consider the simplest policy class.
Definition 2.7 (Trivial policy class). Assume [C] < oo and let II = [T(c) a (c, EC that [||| = |A|
The trivial policy class has the flexibility to predict any action a E A individually for each c E C. This allows us to show that Pn,o S maxe Ve. En' A A- c,a' (see Appendix A.3). An immediate corollary of Theorem 2.4 is obtained by simply noting that [II| |A| CI.
Corollary 2.8 (Trivial class, upper). Fix >> 0 and ē (0, 1)- Let IT be the trivial policy class applied to some fixed C, A spaces. Then under Assumption 7 there exists a computationally efficient (c, P algorithu for contextual bandits that satisfies T I min maxe 1 v. Ea A [og([o)())))))) + log(1/ ())) log( log(1/A.) Le) where A. = max min V(T+) V(T)). Furthermore, this sample complexity never exceeds LAI(C) (o log(1/e).
Ignoring log factors, the minimax sample complexity of the trivial class is just c - - (001///
E[r]] This is actually somewhat surprising result, because it says limg=+0 [og(1/8] + - which is independent of (C]. To see why this result is somewhat remarkable, we played a best-arm identification algorithm for each of the |C] contexts, then this would lead to a sample complexity of --3IC] : |A] log(1/5) It is somewhat of a surprise that such a natural strategy is not optimal. For intuition for why can avoid the multiplicative [C], note that to identify just two policies (I, TT) using uniform exploration requires just e e-2 ||A log samples. When we have more than two policies, a union bound achieves the claimed result.
e-good policy among
The minimax sample complexity of Corollary 2.8 (i.e., the second statement) is nearly tight:
Theorem 2.9 (Trivial class, lower). Fix e > 0 and E (0, 1/6. Let II be the trivial policy class applied some fixed C, A spaces. Moreover, fix a contextual bandit instance μ (v,r) and collection of policies Il. Then any 8)-AC algorithm for contextual bandits satisfies [T [T] 2 maxe Ve En A-a 1og(1/2.40). Furthermore, sup, Ey 2 +[AA[[[C]+
+ log(1/6)).
2.3 Linear policy class
A particularly compelling model-class of policies is the set of linear policies.
Definition 20 (I (Linear policy class). Fix feature map Φ C x A Rd and assume it is known to the learner. Let IT (T()) arg max a). 0), vO E Rdd..
We can consider two settings: the agnostic setting and the realizable setting, In the agnostic setting, there is no assumed relationship between the true reward function r(c, a) and o C A - Rd. In this case, Theorem 2.4 applies directly by taking cover of IT.
Corollary 2.11 (Agnostic, upper bound). Fix e 2 and 8 E (), Let II be the linear pol- icy class in Rdd. Under Assumption there exists a computationally efficient (c, 8)PC) algo- rithm for contextual bandits that satisfies T S PIL. (dlog(1/e) + log(1/8)) (og(1/A.) where A. maxfe, min V (TT)) (T)). Furthermore, this sample complexity never exceeds [A ([dlog(1/))+oog(1//)) log(1/e).
Comparing to the lower bound of Theorem 2.2 the instance dependent upper bound of Corollary 2.11 matches up to a factor of the dimension and negligible log factors. In contrast to the "model-free" feel of the agnostic case, we can also consider "model-based" type setting, i.c. the realizable setting.
5

---

Definition 2.12 (Realizable). We say the linear policy class is realizable if there exists a 0, R such that r(c, a) (Ø(c, 0.) for all c E C and A. Thus, for any π II we have V(=) Be (r(, IT (c))] = Re (o(c, ((c)), 0.)] (#,, 0a) with Φr = Bew (o (())]. Finally, at the start of the game the learner knows this model.
The setting in Definition 2.12 is commonly referred to as the linear contextual bandit problem
1. Clearly, we have that T (c) arg max (0(c, 0.). We begin by defining a quantity fundamental to our sample complexity results:
1 2r. 0r.1l Eee. Re.oaaalaa.
Plin.e
min P.EDA, YOEC rell...
max
(0.. Ox 0.)2
Theorem 2.13 (Realizable, lower bound). Fixe and å (0.1). Let 11 be the linear policy class
in IR and assume it is realizable (see Definitions 2.10 and 2.12 Any (0, 8 algorithm in this setting satisfies E[r] 2 Plin,u log(1/2..45)
We now state our nearly matching upper bound. However, this case we note that the algorithm is not computationally efficient.
Theorem 2.14 (Realizable, upper bound). Fix e > 0 and 5 E 1). Let II be the linear policy class in IRd and assume it is realizable (see Defimitions 2. and 2. Under Assumption there exists an (e, PPC algorithm (see Algorithm 7 for this setling satisfying
T Plin.e (minnd log + log(1/6)) log(1/A.)
min Furthermore, this sample complexity never exceeds d(d (c. (0 (() 0.)3
where A. max min (Øx.- 10s.-Ox: 0.)} maxfs, x
We remark that the algorithm that achieves this upper bound is very different than popular optimism- based algorithms for linear contextual bandits e.g., UCB Thompson sampling [Л]. Indeed, our algorithm computes an experimental design and is related to instance-dependent linear bandit al- gorithms developed for best-arm identification [ 12
1 35 and regret minimization [1]] To our knowledge, Theorem 2. 2.14 provides the first instance- dependent sample complexity for the PAC setting of linear contextual bandits. The most relevant work to Theorem 2.14 is the work of []] which demonstrated a minimax sample complexity dl d log(1/8). Also, we remark that the lower and upper bounds in this section require additive Gaussian noise.
Remark 2.15 (Agnostic vs. Realizable). Contrasting the above results, we note that the sample complexity of the agnostic case is always bounded by |Ald/e2. whereas never exceeds d2 ee² for the realizable case. This matches the intuition that when the number of actions is much larger than the dimension, assuming realizability can significantly reduce the sample complexity.
2.4 Comparison to the Disagreement Coefficient
The work of [6 provides regret bounds in terms of instance-dependen quantities inspired by the disagreement coefficient, notion of complexity common in the active learning literature (18). The following corollary relates our sample complexity to these notions of disagreement coefficients.
Define the policy disagreement coefficient
[ E II, ((() + n. (c)
epol (cn) = sup
<zca
where II, == {IT II: : (T(() + n. (c)) < E) and the cost-sensitive disagreement coefficient
E Row 1 Fr (c) + n. (c), Reow r(c, n. x.. r(c())))))
( = sup
<0co
The AdaCB
achieves a regret of roughly Rr or Rr = (mins (5T, |A] [) (6))). Ob- serve that at time T, given the outputs IT, T2, ... br from AdaCB algorithm, one could return (randomized) policy which observing context, samples from the empirical distribution over
algorithm of
16
O (ingg AAuiifommm T. |A| (T)
Autifom

---

the outputs. By Markov's inequality we have म,, V(Tx) ( - O(e) with constant probability for e = Rr. Therefore, an upper bound on the regret translates to a PAC sample complexity of (Alog((!))) (E/ (enfforomm) or [og( CTT
cunttrr
Finally, Corollary 2.16 shows that this sample complexity bound least as large as our upper bound, see Appendix A.5 for the proof.
Corollary 2.16. Recall that uniforr
min min r(c, m. (e)) r(c, a). For any 6n > 0 we have that aEC acA
1. PII,co I 2|A1
en (co/ Auniform):
2. PIT,ro I 21A (ea).
co
Moreover, for all 6o 2 0 we huve thut Pil,co 3o whenever Apol == V(T.) maxx5 V(*) > 0.
3 Optimal Algorithms for Contextual Bandits
3.1 Reduction to linear realizability and a simple elimination scheme
The astute reader may have noticed that if we ignore computation, Theorem 2.4 is actually an immediate corollary of Theorem 2. 14 by taking Φ(c, a) = vec(e.e, E R where e; is one-hot encoded vector so that r(c. a) = (Ø(c, a), 0.) with 6. E R|AH|A This observation is key to sample complexity results. Recalling &z Een (6(c, [cc)] from Definition 2.1
have that ((r) = Eew (r., (c)) = Eecyy (o(c, (C)),, = (Φr,0,) 0.). We stress that C can be uncountable, and thus would never actually instantiate any of the vectors o(c,a).
For notational convenience, define the feasible set (context, action) probability distributions as AA defines probability distribution over actions. Also define A(w) := Ec,o We,a a ()p(c)(.)))))) (c a) for any w E f2 Under this notation, recalling the right hand side from Theorems 2.13 and
Ω {wv ACxA Me EncA - Note that for each context, Pe (We.aVve
have 1 6x. 11 B.... [E.e Po. (lc.))(cc.a
|| on. [|2(w)) (1r, - Φr, 0.)2 V V P.EAA VoEC xell)m
min max well xlllix.
min
max
(IT,.
Φr,
0n.0.y
0.)2 0.)2vo V2
To show that the sample complexity of Theorem 2.4 is a corollary of Theorem 2.14 it suffices to show that equation ① and the above display are equal. To see this, observe
|| - Φr. (12( = (vece, - vecle (c0)))
= =cco wo,a
(1fT(c) = 1 (c) = = (1
= -Eewe
[ (e.ite)
11++0 Pe.m.
1 (Tx * x(()}]
Due to this equivalence, the lower bound of Theorem 2.2 also corollary of Theorem 2.13 The lower bound of Theorem follows almost immediately from the lower bound argument in 13
The conclusion of this section is that from sample complexity analysis alone, all that is left is to prove Theorem 2.14 In the next section we propose an algorithm that achieves this sample complexity but assumes precise knowledge of the context distribution (this is relaxed in following sections). While the algorithm is highly impractical for a number of reasons, its analysis provides a great deal of intuition and motivation for final algorithm.
3.2 A simple, impractical, elimination-style algorithm
Algorithm I provides an initial elimination based method for the PAC-contextual bandit problem.
The algorithm runs in stages. Before the start of each stage & N, the algorithm defines distribution (i)
pe AA for each e E C. At each successive time [ne], plays random action a, pa in response to context C ~ and receives random reward with Elro/c,, a.) (ó(ce, oz), 0.).
(6)
Observe that
(0) E (e(ee,)))))) ax) EoEc, w (()o(c))) A(w(())
7

---

using the identity Wi,a := VePr.o. Thus, if we set O, A -M a ar then B[O,] - 0.. A straightforward calculation also shows that Cov(O,) A(w(9)
(2)
(2)
is perturbed with additive unit variance noise. Thus, an unbiased estimator of ( ) == (T.)) ((T) = (Øx, - 2x, O,) is simply {Ø+T. 2xx md E. Oc) which has variance
11 if )
- ni 11 0x 0x ((w()))- Intuitively, (0..
on - (t) = (dx. 2R, 0.) +
Φn A(w(())- so we can safely conclude that a me
policy x is sub-optimal (i.e.. π * TT) if there cxists any policy x' such that (Ø.r Pa: 1
O₂)
V | - dx ll A( This is the intuition behind Contextual RAGE (Algorithm D. which inherits its name from the best-arm identification algorithm of that inspired its strategy.
However, while (Øx. - ΦT. ne E, Oi) is unbiased and has controlled variance, it is potentially (8) heavy-tailed because We.a can be arbitrarily small. Instead of trying to control (4) and appealing to Bernstein's 's inequality, in line we use the robust mean estimator of Catoni 2X We can then show:
1
Lemma 3.1. T. II. and max (0+. Φn. 0*) S for all i >>> 1 w.p. at least 1 - 5.
The lemma states that if IT is the active set of policies still under consideration, the optimal policy n, is never discarded from HT, and moreover, the quality of all policies remaining in I7 is getting better and better. We are now ready to state the main sample complexity result, with proof in Appendix B
Theorem 3.2. Fix any policy class II { - A) distribution over contexts v, 5 E (0, 1), 2 O, and feature map & C A + I& such that r(c, a) (ø(c, a), (w.l.o.g. one can always take ΦCc, = v) With probability at least 1 - 5, if Φx = Eewv jo(c, x())]] and
TT. = arg max, (Øx, 0.) then Contextual-RAGE returns a policy ãt E II such that V V(R) 2 V (T.)- -6
after taking at most
| कT. 11a_11
mmin max wEll TEll
((xx. - Φx, 0*) Vej² log(log((A Ve) ve) 11) ve)
samples, where e is an absolute constant and A = mim V(T-) - (T²)
3.3 Towards a more efficient algorithm
One major issue with Algorithm is that explicitly maintains set of policies 11, from round to round. Since II could be exponential in [A], this is non-starter for any implementation. As a motivation for our approach, we consider a non-elimination algorithm, Algorithm step. It does not maintain II; and instead just solves the optimization problem
2 as an intermediate
2 over II. The design computed in 2 is chosen to ensure that for all E II, Á (IT, m A(a, < 2 + A n.) with high probability (Lemma C.3 Equivalently, we estimate gaps up to a constant factor for policies with A(T,, TT) > Ee, while our gap estimates are bounded by Eg for those policies satisfying A(T, T.). S <e. This ensures that our choice of म. is good enough, i.e. satisfies
V(H.)= - (ite) S < with high probability. The full proof is in Appendix C
2 introduces additional problems. It is not clear whether solving 2 is computationally efficient. Also, we need to find an estimator Å that is computationally efficient even if the policy space 11 is infinite. In addition, it requires precise knowledge of to even define the domain of distributions Ω optimized over, and store the solution w E C x A explicitly. But in general, such precise knowledge will not be available and is only estimable using past data (Assumption
Unfortunately, Algorithm
3.4 An instance-optimal and computationally efficient algorithm.
In this section we provide Algorithm 3 which witnesses the guarantees of Theorem 2.14 for the general agnostic contextual bandit problem. We now address the caveats of the previous approaches.
Access to Offline Data. By Assumption we have access to a large amount of sampled offline contexts D, where each c, E D is drawn III from v. Having access to D allows us to approximate E [.] with expectations over the empirical distribution Eo-ep [:], where uD the uniform distribu- tion over historical data D. The number of offline contexts we need only scales logarithmically over the size of the policy set IT, more specifically, poly ( -1, log((IT)), log(1/5). We quantify the precise number of samples needed in Appendix D.2
8

---

Algorithm 1 Elimination Contextual RAGE
Algorithm 2 Non-elimination Contextual RAGE
Input: II, P: C x A RR E 10
Input: II, Φ C x - IR, 5 (0,
I: Initialize 111 = II
1: Initialize: Tu E II arbitrarily
2: for 8= 1.2,
[log (1/e)] do
2: for E t= 1,2,
[ do
3: c; 2 2- by == (1I)
3: c: 2 8g == 5/(2é* [T])
4: Let ne be the minimum value s.t.:
4: Let ne be the minimum value s.t.:
1 2r Blacoy- (og(1/6))
min max wen
- m-
min max well v., g.
S
11 (1 lox(1/6)) 2110
with solution (0)
S (2)
ne
5: For each & E [ne]. get ~ v. pull ~ pec observe reward ri
with solution ((
Compute O = 1(w(0))) (aa0000))((((00000 ())..
5: For each E [nu]]. get ea us pull as Pei (9) observe reward Compute O = (0) "(),,,
7: For n. E ITg
6:
Se(x, m = Cat(l - C+,, 01)
7:
For each π E I1, let
Update
Ae - Cat([lixx 0F, 0i) 0,)3
Ih-11 = -IA E III,
max: xElle
(e > e
8: Set ß. == arg min ÂelT, 9t-1)
(3)
9: end for Output: IT.11
9: end for Output: Rt
Computing the design efficiently. As described, the context space C may be infinite maintaining a distribution 3 E S2 ACxA is not possible. To overcome this issue, we consider the dual problem
of equation 2 We can remove the square root by noticing that 2 /ry miny 72 + y 7'
and
introducing additional minimization over the variable Yr; π E II. Then, the dual problem becomes
maxλеΑn min min,,20 Σxen AM (-Â--1(T, -1) + " | ΦzL 1 A(w) +
log(1/6)) 27
Exchanging the order of the minimums on w and 7, somewhat surprisingly we have the close-form expression (Lemma E.6
minwen Eren 7x 6s. (1:2(w)- = -Eroe [(oraa [ ((eeaV(Ae))TT (5 (T-
where for n' II, (7') E 10, with [1. == ((((c)= a, (c) * aa} (x((c) *
a, T (c) = a} and [ == Ar7 Interestingly, this value achieved at sampling distribution w, which a non-linear function of À rather than a convex combination over policies (as in (3). Because we have an expectation over contexts, this expectation can be replaced by an empirical estimate using historical data, thus avoiding any issues with an infinite context space. The final algorithm utilizing these observations found is in Algorithm g
The main challenge is finding a solution to the design (5) First, problem over (A,7) by considering only a dyadic sequence of n E {2 : h E N). We use an alternating ascent/descent method, with the caveat that À lives in simplex, and in box. Both spaces are defined over a potentially infinite set of policies IT (in the worst case exponential in (C).
reduce it to saddle point
To handle this, we use the Frafe-Wolfe (FW) method on X. Referring to the iterates of FW as X5, FW guarantees that the size of the support of in each iterate grows by at most 1. Thus, initialized as a 1-sparse vector, we only need to maintain a sparse X in each iteration. Each iterate of FW computes
arg max Taaxx/VAe Vhe(A,, 7, n))..
#Ell
To do so, we show that we can appeal a constrained argmax oracle (AMO) run the Trank-Wolft algorithm, similar approach to [ To optimize over y we use gradient descent procedure. We show that each iterate, the support of y is contained in that of X, and we can quantify the number of steps of gradient descent needed to find an e-good solution. Though hy 7, n) might not be convex in 7, we nevertheless are able to argue that has a unique minima and that gradient descent converges to this minima. We introduce our subroutine and further discuss the above claims in Appendix D

---

use robust mean estimator as in equation 5 this estimator impractical with a very large number of policies II. Instead, we use regularized IPS estimator that can be computed using historical data and an argmax oracle.
Regularized Estimator. While Algorithms | and 2
Algorithm 3 Contextual Oracle-efficient Dualized Algorithm (CODA)
Input: policies {iT : C - A)... feature map Ø: x A Rd, ò E (0, 1), historical data D {v.}. I: initiate uo E II arbitrarily, Åo eso AT(TT) 7o. 7wins Tixa appropriately
for:= 1. ...
3: q== 2 8, = 8/ (1
4: Define
(.). = = Exen d (- (-S71T' "0-''TT,, m-1)
log(L/62) Pen
+ EOwED
}
5:
Let L' FII |A|, a.) These are the solutions to
ny = min(n E N:
max NEAn Wellaannn (maxx]
min
1u lu(,,,,11 S cr)
(S)
For E [mu]] get es ~ vs pull a, ~ pe; where pe a (1) (fi-1) observe rewards rss 7: For each π E II, define the IPS estimator
37" (T,
(1(5)-1(cs) a.} -(x((c.) am))
Pe + mm]
set
क arg min A7 (T. -1- + Eawup
(nnj +
[nile
hzsh 1(f-((()) # x((]] ())
+
log(1/6)) Inleny
(6)
9: end for Output: कh
Algorithm S puts all the pieces together and Theorem 3.3 shows our main result. Note that for exposition purposes, have omitted some additional regularization terms in the optimization prob- lems that have no effect on the sample complexity, but ensure finite-time convergence. Appendix B shows the full algorithm and the proof. In what follows, poly, ( loggg(()))) log [1] and poly2((AA),e) log(1/ 18), log(I are polynomials in their arguments.
Theorem 3.3. Fix set of policies II, context distribution v and reward function r(c, a) (0, 1]. With
probability at least 1 1-5, provided history 'D whose size exceeds poly (IA), ( ,og((1 (8)))
Algorithm 3 returns a policy satisfying V (T.) - (Ā) S. e in a number of samples not exceeding Ope, log( [1I) (og.(1/A.)/)) log, (1/A.) where A. == max(e, minxen V(T.) (T)).
In addition, Algorithm p log((1/)) log( calls to a constrained argmax oracle.
computationally efficient and requires at most
Conclusion. This work provides the first instance-dependen lower bounds for the 6)-AA contextual bandit problem. One limitation of this work is that our analysis of Algorithm 3 does not immediately extend to the realizable linear setting. That is, a computationally efficient algorithm that achieves the same bound is not known to exist. In the general agnostic settings discussed in this work, we proposed a computationally efficient algorithm. A second limitation is the assumption that we have access information about the context distribution, it is not clear how one would completely remove such an assumption and achieve the same sample complexity bounds. As with any recommender system, there is the potential for unintended consequences from optimizing just a single metric. Moreover, other potential pitfalls can arise, such as negative feedback loops, if our assumptions fail to hold in real-world environments. Such consequences can be mitigated by tracking a diverse set of metrics.
large pool of offline data. Because it seems necessary to plan with some
Acknowledgement and Disclosure of Funding 1907907.
This work supported, in part, by NSF award
10

---

References
[1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In International Conference on Machine Learning, pages 60-69. PMLR, 2018.
[3] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: fast and simple algorithm for contextual bandits. International Conference Machine Leurning, pages 1638-1646. PMLR, 2014.
[4] Aymen Al Marjani and Alexandre Proutiere. Adaptive sampling for best policy identification in markov decision processes. In International Conference on Machine Learning, pages 7459- 7468. PMLR, 2021.
[5] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77) 2002.
[6] Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford, and Bianca Zadrozny. Error limiting reductions between classification tasks. In Proceedings of the 22nd international conference on Machine learning, pages 49-56, 2005.
[7] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357, 2015.
[8] Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, and Scungil You. Training gell-generalizing classifiers for fairness metrics and other data-dependent constraints. In International Conference on Machine Learning, pages 1397-1405. PMLR, 2019.
[9] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear handits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020.
[10] Aniket Anand Deshmukh, Srinagesh Sharma, James W Cutler, Mark Moldwin, and Clayton Scott. Simple regret minimization for contextual bandits. arXiv preprint arXiv: 1810.0777,, 2018.
[11] Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Sevemth Conference on Uncertainty in Artificial Intelligence, pages 169-178, 2011.
[12] Tanner Fiez, Sergio Gamez, Arick Chen, Houssam Nassif, and Lalit Jain. Adaptive experimental design and counterfactual inference. In Workshops of Conference on Recommender Systems (RecSys), 2022.
[13] Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. In Advances in Newral Information Processing Systems, 2019.
[14] Dylan Foster, Alekh Agarwal, Miroslav Dudik, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pages 1539-1548. PMLR, 2018
[15] Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference Machine Learning, pages 3199-3210. PMLR, 2020.
[16] Dylan Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. Instance instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-baset perspective. In Conference on Learning Theory, pages 2059-2059. PMLR, 2021.
[17] Dylan Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487 2021.
11

---

[18] Steve Hanneke et al. Theory of disagreement- based active learning. Foundations and Trends@ in Machine Learning, 7(2-3):131-309, 2014.
[19] Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit. In International Conference on Artificial Intelligence and Statistics, pages 3536-3545. PMLR, 2020.
[20] Tzu-Kuo Huang, Alekh Agarwal, Daniel Hsu, John Langford, and Robert Schapire. Efficient and parsimonious agnostic active learning, Advances in Neural Information Processing Systems, 28, 2015.
[21] Martin Jaggi. Revisiting frank-wolfe: Projection- free sparse convex optimization. In Interna- tional Conference on Machine Learning, pages 427-435. PMLR, 2013.
[22] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1-29, 2021.
[23] Kwang-Sung Jun, Lalit Jain, Blake Mason, and Houssam Nassif. Improved confidence bounds for the linear logistic model and applications to bandits. In International Conference on Machine Learning (ICML), pages 5148-5157, 2021.
[24] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 2016.
[25] Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. In International Conference on Machine Learning, pages 1915- 1924. PMLR, 2017.
[26] John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. Advances in neural information processing systems, 20, 2007.
[27] Lihong Li, Wei Chu, John Langford, and Robert Schapire, A contextual-bane approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[28] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5):114--115) 2019.
[29] Shie Mannor and John N Tsitsiklis. Lower bounds on the sample complexity of exploration in the multi-armed bandit problem. In Learning Theory and Kernel Machines, pages 418-432. Springer, 2003.
[30] John Milnor and David W Weaver. Topology from the differentiable viewpoint, volume 21. Princeton university press, 1997.
[31] Sareh Nabi, Houssam Nassif, Joseph Hong, Hamed Mamani, and Guido Imbens. Bayesian meta-prior learning using Empirical Bayes. Management Science, 683))1737-1155, 2022.
[32] Fabian Pedregosa, Geoffrey Negiar, Armin Askari, and Martin Jaggi. Linearly convergent frank-wolfe with backtracking line-search. In Proceedings of the 23rdInternational Conference on Artificial Intelligence and Statistics, 2020.
[33] Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pages 1417-1418, 2016.
[34] David Simchi-Levi and Yunzong Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 2021.
[35] Marta Soare, Alessandro Lazaric and Rémi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
12

---

[36] Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. Advances in Neural Information Processing Systems, 33:1417-1427, 2020.
[37] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[38] Roman Vershynin. High-dimeensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[39] Andrew Wagenmaker and Kevin Jamieson. denende-deeendent near-optimal policy identifica- tion linear mdps via online experiment design. arXiv preprint arXiv:2207.0255 022275. 2022.
[40] Andrew Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance- dependent pac reinforcement learning. In Conference Learning Theory, pages 358-415 PMLR, 2022.
[41] Andrea Zanette, Kefan Dong, Jonathan Lee, and Emma Brunskill. Design of experiments for stochastic contextual linear bandits. Advances Neural Information Processing Systems, 34, 2021.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section.
Did you include the license the code and datasets? [No] The code and the data proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Please see our conclusion.
(c) Did you discuss any potential negative societal impacts your work? [Yes] Please see conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "i05Uim6zM1v", "reviewer": "Reviewer_wogP", "summary": "This paper analyzes the sample complexity of contextual bandit optimization in several setting.\n- When the reward and the policy class are both linear, the sample complexity of $(\\epsilon, \\delta)$-optimal algorithm is upper and lower bounded. The lower bounds are for $\\epsilon = 0$.\n- Roughly similar analysis is given for when the policy class is linear but no assumption about the reward class has been made. In this case, it is assumed that an empirical distribution over the contexts is known. \nIn doing so, the paper establishes how realizability reduces sample complexity. \n\nAuthors further establish that min-max optimal algorithms can not be simultaneously instance optimal. By giving a lower bound on the sample complexity of an $\\alpha$-minmax optimal algorithm.\n\nLastly, two algorithms that are nearly min-max instance optimal are introduced (without empirical evaluation).", "questions": "Questions: \n\n- Regarding $\\rho_{\\pi, \\epsilon}$:\n    - I don't understand why and how $p_c$ in Def 2.1 depends on $c$. Is this just notation redundancy (e.g. it should read $p_{\\pi(c)}$) or am I missing something?\n    - Can you give some intuition into equation (1)? In particular, where the terms arise from? Generally, since all the bounds are given in this term, I think it can use more attention and interpretation. \n    - Viewed as a measure of complexity, how does this quantity relate to other notions of complexity for sequential learning? (e.g. ED coefficient [Foster et al 2021], Eluder dimension, Information gain,  Sequential Rademacher complexity, etc)\n\n- How does it (or respectively the bounds) compare to the sample complexity of best-arm identification? In particular the $\\epsilon$ and $\\delta$ dependency. How much harder is optimality for linear contextual bandits compared to best-arm identification in multi armed bandits?\n\nSmall errors:\n- Line 20: $r(c_t, a_t)$ is the expectation of the reward. The \"$r_t := r_t(c_t, a_t)$\" part should be fixed.\n\n\nRef:\n- Foster, Dylan J., et al. \"The statistical complexity of interactive decision making.\" arXiv preprint arXiv:2112.13487 (2021).\n", "limitations": "Perhaps the fact that Assumption 1 is required for the agnostic setup should be mentioned earlier.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Analyzing complexity of sequential learning through sample complexity is a promising area of research, in particular because it leads to design of classes of algorithms. Further, formalized performance of algorithms via instance-dependent bound rather than minmax (aka worst case) bounds is far more informative. This paper combines both and presents a thorough analysis in the two cases of linear and agnostic reward class. The lower bounds are useful for designing new algorithms, and the upper bounds are useful for evaluating existing algorithms. I find the problem of interest to be indeed relevant to community, and I hope that it inspires more work in this area. I am not actively aware of the current state of research on sample complexity in sequential setting. This being said, it seems to me that this paper makes a significant contribution to earlier result on best arm identification, and to other results on instance-dependant regret bounds. \n\nWhile minmax algorithms, e.g. the vanilla UCB method, are not sample optimal, they perform quite well in practice. I would be curious if the minmax sample optimality is reflected in practice. Perhaps this is something that the paper lacks, but of course, empirical evidence is not a necessity, just a nice addition. \n\nI think the presentation of the paper could be improved, so that it addresses a broader audience. Some terms that are not-so-well defined outside this field are commonly used. This can make it an unfriendly read to someone outside the immediate community.\n\nI am not familiar enough with the literature to be able to verify the soundness of the results in limited time. Although simple sanity checks of the bounds all go through. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FnbwpwM13cW", "reviewer": "Reviewer_KmpH", "summary": "This paper is concerned with instance-optimal PAC property for contextual bandits. Both agnostic and realizable cases are investigated. One advantage is that the algorithm is computationally efficient.", "questions": "After skimming through the paper, I found I'm not confident to review the paper as it is outside my expertise. I do not have bandwidth to read more about the literature and further evaluate the paper.\n\nMaybe one related work is https://arxiv.org/pdf/2108.02717.pdf. Can you comment on the comparison to such work?", "limitations": "Nan", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "N/A", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9bQMWKM2ZYV", "reviewer": "Reviewer_3g7m", "summary": "This paper designs instance-optimal PAC algorithms for contextual bandits in both agonistic and linear realizable settings. This paper proves matching upper and lower instance-optimal bounds for any PAC algorithms. The proposed algorithm is oracle efficient and optimal up to logarithmic factors. Interestingly, this paper also proves that, on some instances, algorithms with minimax-optimal regret guarantees cannot be PAC instance-optimal.", "questions": "Some high-level questions and comments:\n- Intuitively, the instance-optimal bounds should be better than the minimax bounds. Are there examples of instances where $\\rho_{\\Pi,\\epsilon}$ is strictly smaller than the minimax bound?\n- The lower bound only considers the case when $\\epsilon=0$, and thus mismatches the upper bound slightly ($\\rho_{\\Pi,0}$ vs. $\\rho_{\\Pi,\\epsilon}$).  Is it possible to get a lower bound for $\\epsilon>0$? Is it possible that $\\rho_{\\Pi,0}$ and $\\rho_{\\Pi,\\epsilon}$ are significantly different?\n\nSome details seem to be missing in the first 9 pages of this paper:\n- In Definition 2.1, if I understand correctly, the PAC algorithm must find an \\epsilon-optimal policy on *every* instance. It’s better to emphasize this because this is critical to prove the lower bound (Theorem 2.2).\n- Both the lower and upper bounds require an additive Gaussian noise, which is never mentioned in the first 9 pages.\n- In Definition 2.5, the distribution of context is missing.\n- The Catoni estimator and its properties are not formally defined in this paper. \n\nMinor issues:\n- In Theorem 2.6, the second max should be over $\\mu’$\n- Line 4 of Algorithm 1: the RHS should be $\\epsilon_\\ell^2$.\n- In Appendix B, some of the notations are not defined. E.g., $w_\\ell,\\tau_\\ell$.\n- Line 585: the inline equation seems to be incomplete.\n", "limitations": "The authors adequately addressed the limitations and potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality & Significance. While minimax optimal results are well-studied in contextual bandit settings, this paper proves a matching PAC instance-optimal upper bound and lower bound, which is much more desirable because the sample complexity of every PAC algorithm is at least $\\rho_{\\Pi,0}\\log(1/\\delta).$ In other words, the proposed algorithm outperforms (or at least matches) every other PAC algorithms (up to logarithmic factors). I believe the results of this paper are important and potentially have a large impact.\n\nThe analysis of Contextual-RAGE algorithm is novel and easy-to-follow. The use of the Catoni estimator is neat and simplifies the proof.\n\nQuality. The results are sound and solid. This paper clearly states the strength and limitation in the conclusion.\n\nClarity. While the paper is well-written in general, some of the details could be further improved (see below). On a high level, it would be better to provide more intuition of Alg. 1 & 2. In particular, it’s unclear why the elimination is necessary without reading the full proof.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5yGGBYbzaOc", "reviewer": "Reviewer_SFQZ", "summary": "This paper characterizes the instance-dependent PAC sample complexity of contextual bandits based on a designed quantity. Matching upper and lower bounds are showed based on this quantity for both agnostic and contextual linear cases. In addition, the paper constructs an instance under which any minimax-optimal regret minimization algorithm suffers from sample complexity that scales quadratically with the optimal sample complexity. The paper further proposes an algorithm with near-optimal sample complexity that only needs a polynomial number of calls to an argmax oracle.", "questions": "1. For the complexity quantity between lines 98-99, why \\Pi is a subscript as well as in the bracket?\n\n2. The lower bound in Theorem 2.2 has the complexity quantity \\rho_{\\Pi,0}, which could be infinite without further assumption, right? Similarly, the lower bound in Theorem 2.13 could be infinite?\n\n3. The definition of \\delta-PAC in the literature usually requires almost-surely finite stopping time, while in Definition 2.1 requires the expected stopping time is finite. Do the results still only hold for PAC definition with almost-surely finite stopping time?\n\n4. I am not sure I understand the connection between line 73 and line 74. Could the author elaborate more on this?\n\n5. The analysis of Algorithm 3 cannot be directly extended to the realizable linear setting, so what settings can the analysis be applied to?\n\n6. I understand this is a theoretical paper, but I think it is better to discuss the practicability of the proposed algorithms?", "limitations": "The paper describes the limitations in the conclusion (btw, I think conclusion can be a single section, not just a paragraph). As discussed, one is the limited applicability of the analysis of Algorithm 3, and the other is that Assumption 1 is pretty strong.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper presents a bag of theoretical results and I think they are sound. Maybe it is better to organize them in a more structured way, for example, having more sections instead of many subsections. In my opinion, Assumption 1 (access to offline data) is a strong assumption. Although it might be satisfied by some practical problems, it is a strong assumption in terms of deriving theoretical results. \n\nThere are several relevant papers. [1] also studies pure exploration in contextual bandit, and the results therein probably need to be discussed and compared. [2] and references therein also show that regret minimization algorithms have undesirable sample complexity for pure exploration objective. Last but not least, I think the literature of policy learning (e.g., [3] and references therein) studies a similar problem.\n\n[1] Aniket Anand Deshmukh, Srinagesh Sharma, James W. Cutler, Mark Moldwin, Clayton Scott, Simple Regret Minimization for Contextual Bandits\n\n[2] Zixin Zhong, Wang Chi Cheung, and Vincent Y. F. Tan, On the Pareto Frontier of Regret Minimization and Best Arm Identification in Stochastic Bandits\n\n[3] Ruohan Zhan, Zhimei Ren, Susan Athey, Zhengyuan Zhou, Policy Learning with Adaptively Collected Data\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept