Understanding the Eluder Dimension
Authors: Gene Li
Pritish Kamath
Dylan J Foster
Nathan Srebro
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
eluder dimension

Abstract: We provide new insights on eluder dimension, a complexity measure that has been extensively used to bound the regret of algorithms for online bandits and reinforcement learning with function approximation. First, we study the relationship between the eluder dimension for a function class and a generalized notion of \emph{rank}, defined for any monotone ``activation'' $\sigma : \mathbb{R}\to \mathbb{R}$, which corresponds to the minimal dimension required to represent the class as a generalized linear model. It is known that when $\sigma$ has derivatives bounded away from $0$, $\sigma$-rank gives rise to an upper bound on eluder dimension for any function class; we show however that eluder dimension can be exponentially smaller than $\sigma$-rank. We also show that the condition on the derivative is necessary; namely, when $\sigma$ is the $\mathsf{relu}$ activation, the eluder dimension can be exponentially larger than $\sigma$-rank. For Boolean-valued function classes, we obtain a characterization of the eluder dimension in terms of star number and threshold dimension, quantities which are relevant in active learning and online learning respectively.

Understanding the Eluder Dimension
Gene Li Toyota Technological Institute at Chicago gene@ttic edu
Pritish Kamath
Google Research
pritish@alum mit. edu
Dylan J. Foster
Nathan Srebro
Microsoft Research
Toyota Technological Institute at Chicago nati ieti@tttic.ede edu
dy anf oomforemimmii wwwsoft. www.errmicooorottoooomm com
Abstract
We provide new insights on eluder dimension, complexity measure that has been extensively used to bound the regret of algorithms for online bandits and rein- forcement learning with function approximation, First, we study the relationship between the eluder dimension for function class and generalized notion of rank, defined for any monotone "activation" a R - R, which corresponds to the minimal dimension required to represent the class It is known that when a has derivatives bounded away from O, o-rank gives rise to an upper bound on eluder dimension for any function class; we show however that eluder dimension can be exponentially smaller than o-rank. We also show that the condition the derivative is necessary; namely, when is the relu activation, the eluder dimension can be exponentially larger than ø-rank. For binary-valued function classes, obtain characterization of the eluder dimension in terms star number and threshold dimension, quantities which are relevant in active learning and online learning respectively.
generalized linear model.
Introduction
Russo and Van Roy [37] introduced the notion of eluder dimension for function class and used to analyze algorithms (based on the Upper Confidence Bound (UCB) and Thompson Sampling paradigms) for the multi-armed bandit problem with function approximation. Since then, eluder dimension has been extensively used to construct and analyze the regret of algorithms for contextual bandits and reinforcement learning (RL) with function approximation [see, e.g., 46, 36, 44, 6, 14, 19, 12, 16, 26, 24]. Even though the eluder dimension has become a central technique for reinforcement learning theory, little is known about when exactly it is bounded. This paper makes progress toward filling this gap in our knowledge.
Russo and Van Roy [37] established upper bounds cluder dimension for (i) function classes for which inputs have finite cardinality (the "tabular" setting), (ii) linear functions over Id of bounded norm, and (iii) generalized linear functions over Rd of bounded norm, with any activation that has derivatives bounded away from O. Apart from these function classes (and those that can be embedded into these), understanding of eluder dimension has been limited. Indeed, might wonder whether a function class has "small" eluder dimension only if it can be realized as a class of (generalized) linear functions! This leads us our first motivating question:
Question 1. Are all function classes with small eluder dimension essentially generalized linear models?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Answering this question has substantial ramifications on the scope of prior work. An answer of "yes" would imply that the results in the aforementioned work which gives regret guarantees in terms of eluder dimension do not go beyond already-establishee regret guarantees for generalized linear bandit or RI. settings [see, e.g. 17, 32, 45, 31]. An answer of "no" can be construed as a positive result for RL theory, as it would indicate that existing (and future) results which use the eluder dimension apply to a richer set of function classes than generalized linear models.
To answer Question 1, we first formally define what it means for a function class to be written as a generalized linear model (GLM). Informally, for an activation σ E - R and function class F FC (X' + R), we define the o-rank to be the smallest dimension d needed to express every function in F as a generalized linear function in Rd with activation a (see Definition 3). Intuitively, the ø-rank captures the best possible upper bound eluder dimension that the results from Russo and Van Roy [37] can give for a given F by treating it as a GLM with activation a. We ask how the eluder dimension of any function class relates to o-rank for various activations a. We show that the answer to Question I is indeed "no", i.c., there exists a function class with eluder dimension d but the o-rank for any monotone o is at least (d))) Thus, while Russo and Van Roy [37] show that the set of function classes with small eluder dimension is a superser of the set of GLM function classes, we (roughly speaking) show that the set of function classes with small eluder dimension is strictly larger than the set of GLM function classes.
We also prove that the requirement from Russo and Van Roy [37] that the derivative of the activation is bounded away from 0 is necessary in order to bound the eluder dimension of GLMs. The upper bound in the paper [37] becomes vacuous when the activation function has zero derivative; we show a lower bound which indicates this requirement cannot be dropped. Namely, when a is the relu activation, we show that eluder dimension can be exponentially larger than o-rank.
In a second line of inquiry. we study a combinatorial version of eluder dimension. The original definition of Russo and Van Roy [37] is defined for real-valued function classes, but one can specialize the definition to binary-valued function classes, leading to a so-called combinatorial eluder dimension. Thus, our second motivating question is:
Question 2. Can we bound the combinatorial eluder dimension, perhaps in terms of more familiar Saaming-theoretie quantities?
One might wonder: if the combinatorial eluder dimension is just special case of the scale-sensitive version, why study it at all? Our reasons are threefold.
The first and most immediate reason is that we are able to show new characterizations of eluder dimension once we move to the combinatorial definition. We elucidate a fundamental connection between eluder dimension and two other well-studied -ehrning-theoretic quantities: (1) star number, a quantity that characterizes the label complexity of pool-based active learning [21]. (2) threshold dimension, a quantity that characterizes the regret of online learning [3]. We believe that this new result may help us better understand how different learning tasks relate to each other.
The second reason is that the combinatorial cluder dimension (or a multi-class variant of it) has already been studied for policy-based learning for contextual bandits and RL [see, e.g., 19, 34]. Thus, understanding the combinatorial eluder dimension may shed light on the challenges of pasec RL.
Our last reason has more philosophical bent. Historically, the discovery of VC dimension placed statistical learning theory on solid footing. Specifically, the fundamental theorem of statistical learning allows us to precisely characterize the statistical complexity of PAC learnability in terms of the combinatorial VC dimension. The insights from understanding the role of VC dimension in classification have led researchers to develop scale-sensitive complexity measures such as fat shattering dimension to provide sharper guarantees on learning. While we do not claim that the eluder dimension is fundamental to online RI. and bandit settings, we believe that better combinatorial understanding can lead to a better understanding of online decision making. In some sense, we are "working backwards" from the original scale-sensitive definition of eluder dimension to understand its combinatorial properties.
Finiteness of the threshold dimension is equivalent finiteness of Littlestone dimension [40, 22, 3].

---

1.1 Main contributions
In this work, we provide several results which show when eluder dimension can be bounded (or is unbounded). Our results can be separated into two categories: (1) those pertaining to the (scale- sensitive) eluder dimension (as originally defined by Russo and Van Roy [37]): (2) those pertaining to the combinatorial eluder dimension, defined for binary-valued function classes.
First, we investigate the relationship between eluder dimension and our notion of generalized rank that captures the realizability of any function class as a GLM. In Section 2, we formally introduce the eluder dimension (as well as a related quantity of the scale-sensitive formalize the notion of "generalized rank". In Section 4, we provide several results.
number). In Section we
1. We show that eluder dimension can be exponentially smaller than o-rank for any monotone activation not just those with derivatives bounded away from 0 (Theorem 6).
2. We show that the condition on the derivative being bounded away from is necessary for o-rank to be upper bound on eluder dimension. Namely, when is the relu activation, show that eluder dimension can be exponentially larger than o-rank (Theorem 7).2
In Section we specialize the eluder dimension to the binary-valued setting and present our results on the combinatorial eluder dimension.
1. We show that eluder dimension is finite if and only if both star number and threshold dimension are finite. Specifically, in Theorem we show the following:
max(Sdim(F)) [F) < Edim(F) S (xpp(((mx((Sdmm(33 Tdim(F))))
Furthermore, demonstrate that both inequalities be tight (see Theorem 9 and discussion above it).
2. We investigate the comparison between eluder dimension and sign-rk and prove stronger sepa- rations than in the scale-sensitive case; namely we show examples where one quantity is finite while the other is infinite (Theorem 10).
1.2 Related work
In this section, we highlight several related works.
Bounds on eluder dimension. Several papers provide bounds eluder dimension for various function classes. The original bounds on tabular, linear, and generalized linear functions were proved by Russo and Van Roy [37] (and later generalized by Osband and Van Roy [36]). Mou et al. [34] provide several bounds for the combinatorial eluder dimension. mostly focusing on linear function classes. When the function class lies an RKHS, Huang et al. [25] show that the eluder dimension is equivalent to the notion of information gain [41, 38], which can be seen as an infinite dimensional generalization of the fact that the eluder dimension for linear functions over IRd is ②(d). In concurrent work, Dong et al. [12] also prove an exponential lower bound on the eluder dimension for ReLU networks.
Applications of eluder dimension. The main application of the eluder dimension is design algorithms and prove regret guarantees for contextual bandits and reinforcement learning. A few examples include the papers [46, 36, 44, 6, 14, 19, 28, 16. 26, 24, 34]. While the majority of papers prove upper bounds via eluder dimension, Foster et al. [19] provided lower bounds for contextual bandits in terms of eluder dimension, if one hoping for instance- -epeendeed regret bounds. In addition, several works observe that eluder dimension sometimes does not characterize the sample complexity, as the guarantee via eluder dimension can too loose [23, 20J. Beyond the online RL setting, eluder dimension has been applied to risk sensitive RL [15], Markov games [24, 29], representation learning [47], and active online learning [10].
Other complexity measures for RL, We also touch upon other complexity measures which have been suggested for RL. One category is Bellman/Witnes rank approach [see e.g. 27, 11, 42), which is generalized to bilinear classes [13]. These complexity measures capture an interplay between
? Thii result was independently established by Dong al. [12].
3

---

the MDP dynamics and the function approximator class; in contrast, eluder dimension is purely a property of the function approximator class and can be stated (and studied) without referring to an online RL problem. Jin et al. [28] define a Bellman-Eluder dimension which captures function classes which have small Bellman rank or eluder dimension. Lastly, Foster et [20] propose ArrisionnEstimatiinn Coefficient and prove that it is necessary and sufficient for sample-efficient interactive learning.
Notions of rank. The notion of rank we propose a generalization of the classical notion of sign rank, also called dimension complexity. Sign rank has been studied extensively in combinatorics, learning theory, and communication complexity [see e.g. 1, 18, 5, 2, and references therein]. The norm requirements in our definition of arrank are related to the notion of margin complexity [5, 7, 30].
Eluder dimension and star number
Eluder dimension is a "sequential" notion of complexity for function classes, originally defined by Russo and Van Roy [37]. Informally speaking, it characterizes the longest sequence of adversarially chosen points one must observe in order to accurately estimate the function value at any other point. We consider variant of the original definition, proposed by Foster et al. [19], that is never larger and sufficient to analyze all the applications of eluder dimension in literature.
Definition 1. For any fanction class F S (X + RR). f F, and scale & 2 O, the exact eluder dimension Edim y. (F,e) is the largest such that there exists (I1, (Fmm fm) E X' x F satisfying for all i [m]]
[1(())) - (" and ((
(1)
JEi
Then for all 8 >>>000 0:
the eluder dimension Edimm-(JF = =uupere Edimy y. (F,
-Edim(F,s) eF Edim y- (F, and Edim(F, su Edim (F,
This definition is never larger than the original definition of Russo and Van Roy [37], which asks for a witnessing pair of functions fi, f E F (the above restricts = ("). Hence, all lower bounds on our variant of eluder dimension immediately apply the original definition. Moreover, all upper bounds on eluder dimension in this paper can also be shown to hold for the other definition (unless stated otherwise).
We also consider the closely related notion of star number defined by Foster et al. [19], which generalizes combinatorial parameter introduced in the active learning literature by Hanneke and Yang [21] (we will denote as Sdim for consistency). We study the combinatorial star number in more detail in Section 5. The only difference between the definitions of eluder dimension and star number is that D is replaced by Ejfr which makes the star number a "non-sequential" notion of complexity.
Definition 2. For any function class F S - R), E F, and scale E 2 O, the exact star number Sdim (F,=) is the largest such that there exists (I1, f1)...... (Imi fm) E X F satisfying for all i [m]:
[f((;;) - f*(a)) and -((())
i#1
Then for all E >> 0:
the star number is Sdimy- (F,8) sup= Sdim y (F,
Sdim(J, +) :- supp Sdim (F, 8) and Sdim (F, ) == supyrer Sdimy- (Fimy-(FFe5
immediately follows from these definitions that the star number never larger than eluder dimension. On the other hand, the star number can be arbitrarily smaller than cluder dimension.

---

Proposition 1. For all f E F and scale 2 0, it holds thar'
Sdimy- (F,e) I E (F,e) I min (121, 13.
Proposition 2 (simplified from Foster et al. [19, Prop 2.3]). For the class of threshold functions given as Fth = {fi : [m] + {0.
+ []], where fi(x) := 1 {ar 2 i), and for f fn+1, 1,
(F,e) holds for all < that 5dimy- y. (F, = 2 and (F,e)
3 Generalized rank
Dimension complexity has been studied extensively in combinatorics, learning theory, and communi- cation complexity [see e-g. 1, 18, 5, 2]. The classical notion of dimension complexity, also known as sign rank, corresponds to the smallest dimension required to embed the input space such that all hypotheses in the function class under consideration are realizable halfspaces. We consider generalized notion of rank that is specified for any particular activation a + R, and captures to the smallest dimension required to represent the function class GLM when is the activation. In what follows, we let Ba Rt = {i E IRd | 22 I RJ.
Definition 3. For any a R - R. the o-rank of a function class F S (X + R.) at scale R > 0, denoted as o-rk(F, R), the smallest dimension di for which there exists mappings Φ : X Ba(1) and w F - Ba(R) such that'
for all xXx f(x) o(w(f))
or oo if no such d exists. For a collection of activattion actitition,uunctionss E S (R - IR), the E-rank is
E-rk(F, R) = min R).
Examples. We present some examples of E-rk that motivate our definition above.
1. Threshold activation. sign(z) yields the classic notion of sign-rank (equivalent to dimen- sion complexity, already mentioned). In this case, the scale R is irrelevant, note sign-rk(F) ;= sign-rk(F, R) for any R. Note that this quantity is meaningful only for F C (-1,
de-
2. Identity activation. For (2) := id-rk(F, RR) is the smallest dimension needed to represent each f E F a hoom--o linear function. We abbreviate
id-rk, as this corresponds to the standard notion of rank of the matrix (f(z))z,f (albeit with the additional norm constraint).
3. Monotone activations. For L 2 μ 2 0, MI. consists of all activations such that for all 2',
it holds that μ S a(s')-o(s) < L (for differentiable this is equivalent to μ S. a'(2) L for all
z E IR).5 An important special case is when μ = 0, and a particular a E MM of interest the rectified linear unit (ReLU) defined as relu(z) = max {z, 0}. For ease of notation, we denote
M₁ == MM.
While we will always be explicit about the Lipschitz constant, note that the scale of the Lipschitz constant L (and p) is interchangable with the scale of R. In particular,
My M R)
(LL,
4. All activations. yall consists of all activations We mention this notion of rank only in passing, and we will not focus on for the rest of the paper.
We present result which relates the aforementioned quantities (proof in Appendix A).
è For the definition eluder dimension considered by [37], upper bound of min (121) ((2") holds, which can be tight. This upper bound holds because the witnessing pair of functions (fi, f() has to be distinct for each
Note that only the product of the scales of & and w is relevant. The definition remains equivalent if we let Φ: X + Ba(Rs) ) and w F - Ba(R...) ( for any R₃ and R... such that ft = R₃ R...
*To prove upper bounds on eluder dimension, suffices for this condition to hold only when |a| S Rt [see e.g. 37J. Since we fix in our definition first and then consider o-rank at different scales H, this weaker condition complicates our definitions. Note that at specific scale R, we can always modify o to satisfy the required constraint everywhere extending linearly whenever [z] H.
5

---

rk
My-tk
Mo-rk
Edim
Sdim
M
Mn-tk
Feep
Mo-rk
Freel
Freiu
Edim
Mo-rk
Edim
Sdim
FEth
Sdim
(b)
Figure 1: (a) Each arrow M1 - M2 indicates that M1(F) S M2(F) for all F, where the dependence on R and is suppressed for clarity (see Propositions 1,3, 4 for precise bounds). Whenever M2 M1 arrow is missing, there is an example class JF where (F(F) < M2(F). (b) An entry F in (Mi, M2) means that (F) & (F. Green cells indicate that (F) (F( for all F.
Proposition 3. For all F (2 R). R> and E (0, 1}, we have:
rk(F,R) 2 M2,tk(F,RR) Z Mo-rk(FF RR 2 sign-rk(FF 1,
where the last inequality meaningful only for J (X - + (-1,1)). Moreover, for each inequality above, there exists function class F which exhibits an infinite gap between the two quantities.
4 Eluder dimension versus generalized rank
In this section, we compare eluder dimension and star number with each notion of generalized rank: rk, Mf-rk (for 0) and Mo-rk. Our results summarized in Figure 1.
Eluder vs. rk and -,. Russo and Van Roy [37] and Osband and Van Roy [36] provided upper bounds eluder dimension for linear and generalized linear function classes. For completeness, we restate this result, with a slight improvement and include the proof with precise dependence on problem parameters in Appendix B. Intuitively, the generalized linear rank allows the tightest possible upper bound that the guarantees in the papers [37, 36] can provide on eluder dimension.
capture
Proposition 4 (ef. [37], Prop. 6, 7: [36], Prop. 4). For any function class F C (X R) and
E <>0 0:
(i) For all R > 0, Edim(F F,e) < rk(F, R) (log B).
(ii) For all L, R 0, Edi < MH.rk(F,R R) O ( log RL
This result has been used to prove upper bounds eluder dimension of various function classes beyond GLMs; for example, the class of bounded degree polynomials, by taking the feature map d(x) be the vector of low degree monomials. The upper bound in Part (i) fact tight (up constants) for the class of linear functions, as shown in Proposition 5 below. This trivially implies the optimality of the bound in Part (ii) up to the factor of (L/p)² which the best of our knowledge is open.
Proposition 5 ([33]). For any R. 0, X' (1(1) and F = (fo + (0,z) Ba(R)), holds that:
Edim Edim(F,s) 2 S Id ())
For completeness, we include the proof in Appendix C.
Eluder vs. Mo-rk. turns out that eluder dimension and Mo-rk are incomparable. That is, there exists function class for which eluder dimension is exponentially smaller than Mo-rk (and hence -f.rr and by Proposition 3). Moreover, there exists different function class for which eluder dimension (even the star number) is exponentially larger than relu-rk (and hence Mo-rk).

---

First, we show that the eluder dimension can be exponentially smaller than Mo-rk for the class of parities over d bits. Thus, parities over d bits exhibits an example where the eluder dimension is exponentially smaller than the best possible bound one can derive using the existing results of Proposition 4.
Theorem 6. For X = {-1,1} and J {Ss x
Ilis S S [d]]. it holds that
(i) Ma R) 2d/2 1 for all R. O.
(i) (d E) Edim (F@ .)) S for all & 2 0.
Proof. Part (i). From Proposition 3, we have that Ma-rk(Fe, R) 2 sign-rk(F#) - for any a Mo. The proof is now complete by noting a well known result that sign-rk( 2 24/2 [18].
Part (ii). For any E 11,,1] consider its 0-1 representation ã E TV (representing +1 by and by 1). All functions in F can be simply viewed as linear functions over Fz. Namely, any parity function is indexed by vector E Fy. with (ar = (-1) (a,
Note that Edim E) 0 for all 2 2. For any < 2, suppose Edim (Fo, m, witnessed by Sai, (Im, Sa..) E 1) and f far. We have
fo, + fa (3:;,, and
. (xz) = fa- (2z) for all j < i: since Ejes(fa far (x,))² < < < 4 iff all terms are 0.
Thus, we have (a, a", ,² 0 for all T E Rg-span((E)).. .......,,.1))) Ti-1)). But (a; _a",,.) = 1 and hence ã4 is linearly independent of (TI,..., 3 over Fy. Thus, (ă1,.... Jm} are all linearly independent over Fg. and hence m I d.
The bound in part (ii) of Theorem 6 was also calculated by Mou et al. [34, Prop. 3).
Next, show separation in the other direction for eluder dimension vs. Mo-rk using the ReLU function class. Thus, we cannot hope to remove the requirement for the activation function o to be strictly monotonically increasing in Proposition 4 (ii) for bounding the eluder dimension.
Theorem 7. Let R > O and X = Ba(.). Define
Freeuu = [oob : x +
b) |1012 + + = R*).
holds that
(i) Mo-rk(FFrel R) < Belu-rk(Frrhhy R) < d 1,
(ii) Edim(Frelu .) N Sdim (Frrel
.)
d/2 for all E (0, R).
Proof. Part (i) is immediate from the definition. We show Part (ii) in the special case of R = 2: the general case follows by relatively scaling E, since relu is homogeneous, namely, relu(ar) relu(z). Consider any U C X' such that ||u]| = and (u, v) I 1 1 E for all u, v E U. It holds that Sdim,. (Frelu, e) 2 [U] when f is the identically zero function, since the function fa(x)) = relu((u, - ()) is such that fv( = 0 for all v E U X fu). whereas f. = E. standard sphere packing argument shows that such set U exists with [U] > (1/28)4/2 for all E < 1/2. In particular, the ő-packing number of the unit sphere is at least (1/8)d [43, Cor. 4.2.13). Thus, we can find (1/8)² points such that each pair u, v satisfies ||u - ell 2 6, or equivalently (u, v) < 1 82/2. Setting /ee proves the claimed lower bound.
Theorem 7 was independently shown by Dong et al. [12, Thm. 5.1].
We remark that while we considered the variant of eluder dimension as defined by Foster et al. [19]. the lower bound on eluder dimension in Theorem 7 immediately holds for the notion defined by Russo and Van Roy [37]. On the other hand, the upper bound on eluder dimension in Theorem 6 can be shown to hold even with the definition of Russo and Van Roy [37] (by replacing every instance of a' by a.).
7

---

f1
fa
F4
f6
f6
F2
f4
f6
f6
f1
J2
f4
16
86
0
0
371
0
0
0
0
0
0
0
4/2
0
0
0
32
0
0
0
0
22
0
0
0
0
33
0
0
0
23
0
0
124
0
0
*
Eluder sequence
Star sequence
Threshold sequence
Figure 2: Illustration of witnessing sequences of length 6 for eluder dimension, star number and threshold dimension with respect to f* O (we use the 0/1 representation of functions for clarity). in the eluder witness sequence refers to free value, either 0 or
Relationships between combinatorial measures
In this section, specialize the eluder dimension binary-valued function classes and prove several additional characterizations that relate this combinatorial eluder dimension to other learning- -tteorecc quantities. First, we (re)define these learning-theorede combinatorial eluder dimension and star number respectively) are the specialization of the scale- sensitive versions (cf. Definition I and 2) the binary-valued function setting. We abuse notation by dropping the argument e from previous definitions in order to be consistent.
quantities. The first two definitions (of
Definition 4. Fix any function class F S (X + {1,-1}) and any f F.
The combinatorial eluder dimension w.r.t. ft, denoted Edim,- (F), is defined as the largest such that there exists f1),, -Frm Jm) E X x F satisfying for all i E [m]:
f((x)) # (x:). and for all j <i: f((2,) (zz))
The star number w.rl. 8r, denoted Sdim (F)), is defined as the largest mn such that there exists (Imo mm) E x F sutisfying for all i E [m]:
f((.)) # fo (xi), and for all j +i: =
The threshold dimension W.E.t. f*, denoted Tdim,- (F), is defined as the largest m such that there exists f1),f)).... (Ims E X satisfying for all E [m]]
for all k 2 i: f((xx) (*x), and for all <i: M(r))=
As before, define the combinatorial eluder dimension (resp. star number and threshold dimension) to be Edim(F) == sup Edimy (Sdim(F) and [F) are defined similarly).
Let us pause to unpack these definitions and give some background. In fact, the star number definition stated above is the original definition of Hanneke and Yang [21]. who give tight upper and lower bounds on the label complexity of pool-based active learning via the star number Sdim(F) and show that almost every previously proposed complexity measure for active learning takes a worst case value equal the star number. Roughly speaking, the star number corresponds the number of "singletons" one can embed in function class; that is, the maximum number of functions that differ from base function f* at exactly one point among subset of the domain (31,..., Tm X.
The threshold dimension has recently gained attention due to its role in proving an equivalence relationship between private PAC learning and online learning [see, e.g., 3, 9]. We slightly generalize the definition of Alon et al. [3] to allow for any base function f*, in the spirit of the other two definitions. A classical result in model theory provides link between the threshold dimension and Littlestone dimension (which we denote Ldim), quantity which is both necessary and sufficient for online learnability [8, 4]. particular, results by Shelah [40] and Hodges et al. [22] show that for any binury-valued F and any f* F:F:
[log Tdim,- (F) < Ldim < Tdim (F)

---

A combinatorial proof of this fact can be found in Thm. 3 of Alon et al. [3]. Thus, finiteness of threshold dimension necessary and sufficient for online learnability (albeit in much weaker, "qualitative" sense).
5.1 A qualitative equivalence
Now, we prove a rather surprising characterization that closely ties all three quantities in Definition together. Our result implies that for any binary-valued -vlledd function class, finiteness of the combinatorial cluder dimension is equivalent to finiteness of both star number and threshold dimension.
Theorem 8. For any function class F C (X + (1, -13) and any f E F,, the following holds:
max{Sdim (F), Tdimy. (F)) < Edim (F) s 4 m (F).Tdimy- (F))
The proof of Theorem 8 can be found in Appendix D. The lower bound is trivial by examining Definition 4. To prove the upper bound, we rely on novel connection Ramsey theory. In partieular, we show that sequences (1)........ (Tmm fm) which witness Edimy. = m form a bijection with red- blue colorings of the complete graph Km. while subsequences of the witnessing eluder sequence that are valid star number witnesses or threshold dimension witnesses can be interpreted as monochromatic colorings of subgraphs of K,, (see Figure 2). Thus, applying classical bounds from Ramsey theory implies the result.
Theorem 8 has an exponential gap between the upper and lower bounds. Can we improve either of the inequalities? The lower bound cannot be improved, by considering the simple examples over X = [m] of the singleton class F = {ar + 1(x = i} i E [n + 1]} and the threshold class Fth = {ir + 1x 2 i} i E [n + 1]}. We also show that the upper bound cannot be improved, for example, to Edim(F) S poly(Sdim(F), (F) in general.
Theorem 9, For every N > O, there exists a function class FN such that Edim(Fx) = N and [F) (dim
max(Sdim(F),
logg N, where >> 1/2 is some absolute namerical constant.
The proof of Theorem 9 can be found in Appendix F. It relies on the probabilistic method to show the existence of randomly constructed F which satisfies the desired properties.
5.2 Comparisons with sign-rk
In this section, we investigate the comparison of these combinatorial quantities (eluder, star, threshold) with sign-rk, and examine whether we can prove stronger separations. One direction is clear; for the class of linear classifiers in Rd,, the combinatorial eluder dimension, star number, and threshold dimension are all infinite. However, we ask if the other separation also possible: can we construct F where eluder/star/threshold are finite but sign-rk exponential separation: Theorem shows that for the function class Fe, we had Edim(F =
oc? We have already provided an explicit
Sdim(F = but sign-rk(F > 24/2, (One can also show that Tdim( = d.) We are able to show stronger (but nonconstructive) separations by extending the probabilistic techniques of Alon et al. [2], who recently provided similar separations for VC dimension versus sign-rk. In view of Proposition 3, this result also provides separation for the scale- sensitive Definition 1.
Theorem 10. For every N >> 0, there exists function class FN S ([N) + (1,-1)) such that Edim, (Fx) = 4 and sign-rk(Fw) 2 9(N1/9 /log N), where is shorthand for the all Is function.
The proof of Theorem 10 can be found in Appendix F. It straightforward to replace the reference function (xxx with any fixed reference function f* [N] (1, (1,-1). First,
Lemma 22 of Alon et al. [2] which bounds the number of distinct matrices with sign-rk = r: then using a probabilistic argument show that there must be many (more) matrices with Edim, 4, at least one of them must have large sign-rk.
The careful reader might notice that we do not prove the existence of function class where Edim(F) constant and the sign-rk is infinite; instead we prove the weaker statement that function class exists with Edim w.r.t. any fixed function f* is bounded. We conjecture that the stronger statement holds; see Appendix F.I for more details.
Allon et al. [3] prove the result for (x) -1, but it is easy extend their proof to hold for any f*

---

5.3 Back to scale-sensitive?
natural to ask if our results can be extended back the scale-sensitive definitions. First, we require a scale-sensitive version of threshold dimension. One proposal is the following:
Definition 5. For any function class F S (X + R), f E F, and scale & 2 0, the exact threshold dimension Tdim (F,e) the largest m such that there exists (x1, f(),, ..... (Im; X F satisfying for all [m]]:
vj 2 i -()))) e, and -((()))) SE.
ja
Then for all 0:
the threshold dimension is Tdimy- (F,E) supe Tdim yr (F,
Tdim(F, : EF T (F,e) and Tdim(F,e) sup Tdimy- (F,e).
Definition 5 mirrors the scale-sensitive definitions for eluder and star; it also recovers the combi- natorial definition when FF is binary-valued. By definition, the relationship that (Fi 2 max(Sdim, y (F, e), Tdimy. (F, for every F. f" E F, 0 is trivial. However, cannot hope to prove the corresponding upper bound under this definition. For example, for any >> 0, take the function class which represented by the N N matrix:
i < i =
fz(2)) =
E
0.99c i> j.
It is easy to that Edimo N, while Sdimo(F,e) 2 and Tdim, 1. Notice that this class is still "threshold-ikke. but Definition does not capture this for said value of e. Generally speaking, it unclear how carry over the intuition from Ramsey theory that applies in the combinatorial case to the scale-sensitive case; we leave this to future work.
Acknowledgments and Disclosure of Funding
We thank Gaurav Mahajan for allowing us include the proof of Proposition [33]. We thank Akshay Krishnamurthy. Tengyu Ma, and Ruosong Wang for helpful discussions. GL was partially supported by NSF award IIS-1764033 PK was partially supported by NSF BIGDATA award 1546500. Part of this work was done while GL, PK, and DF were participating in the Simons program on the Theoretical Foundations of Reinforcement Learning.
10

---

References
[1] N. Alon, P. Frankl, and V. Rödl. Geometrical realization of set systems and probabilistic communication complexity. In 26th Anmual Symposium Foundations Computer Science, pages 277-280. IEEE Computer Society, 1985. URL https://doi.org//1... wwt.010///FF...110 198.....9......
[2] N. Alon, S. Moran, and A. Yehudayoff. Sign rank versus VC dimension. In 29th An- nual Conference on Learning Theory, volume 49 of PMLR, pages 47-80, 2016. URL
[3] N. Alon, R. Livni, M. Malliaris, and S. Moran. Private pac learning implies finite litrlestone dimension. In Proceedings of the st Annual ACM SIGACT Symposium on Theory of Com- puting, STOC 2019, page 852-860, New York, NY, USA, 2019. Association for Computing Machinery. URL https:://oi..rgg/ 0.
http://00o....111.111/3333333333 0111111411377633111688 6312..
[4] N. Alon, O. Ben-Eliezer, Y. Dagan, S. Moran, M. Naor, and E. Yogev, Adversarial laws of large numbers and optimal regret online classification. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theooy of Computing, pages 447-455, 2021.
[5] R. I. Arriaga and S. S. Vempala. algorithmic theory of learning: Robust concepts and random projection. Mach. Learn., 63(2):161-182, 2006. URL https::/doo.org/10.00077 s s10994- 00006265--
[6] A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang. Model-based reinforcement learning with value-targeted regression. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of PMLR, pages 463-474, 2020. URL http://pooeeddnnns.mmrrrrsssssss ayoub20a.html
[7] S. Ben-David, N. Eiron, and H. U. Simon. Limitations of learning via embeddings in euclidean half spaces. Journal of Machine Learning Research, 3(Nov):441-461 2002.
[8] S. Ben-David, D. Pál, and Shalev-Shwartz. Agnostic online learning. In COLT, volume page 1, 2009.
[9] M. Bun, R. Livni, and S. Moran. An equivalence between private classification and online prediction. In 2020 JEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 389-402. IEEE, 2020.
[10] Y. Chen, H. Luo, T. Ma, and C. Zhang. Active online learning with hidden shifting domains. In International Conference on Artificial Intelligence and Statistics, pages 2053-2061. PMIR, 2021.
[11] K. Dong, J. Peng, Y. Wang, and Y. Zhou. Root-n-regret for learning in markov decision processes with function approximation and low bellman rank. In Conference Learning Theory, pages 1554-1557. PMLR, 2020.
[12] K. Dong, J.
Yang, and T. Ma. Provable model-based nonlinear bandit and reinforcement learning: Shelve optimism, embrace virtual curvature, arXiv, 2102.04168, 2021. URL https: /aaxvw.rgg/abs/2122.04488
[13] S. Du, S. Kakade, J. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-2836. PMLR, 2021.
[14] S. S. Du, J. D. Lee, G. Mahajan, and R. Wang. Agnostic Q-learning with function approx- imation in deterministic systems: Near-optimal bounds approximation error and sample complexity. In Advances Neural Information Processing Systems, volume 33, pages 22327- 22337. Curran Associates, Inc., 2020. URL
[15] Y. Fei, Z. Yang, and Z. Wang. Risk-sensitive reinforcement learning with function approx- imation: A debiasing approach. In International Conference on Machine Learning, pages PMLR, 2021.
11

---

[16] F. Feng, W. Yin. A. Agarwal, and L. Yang. Provably correct optimization and exploration with non-linee policies. In International Conference on Machine Learning, pages 3263-3273. PMLR, 2021.
[17] S. Filippi, O. Cappe, A. Garivier, and C. Szepesvári. Parametric bandits: The gen- eralized linear case. In Advances in Neural Information Processing Systems, vol- ume 23. Curran Associates, Inc., 2010. URL httpss/ppocceliinnseerrppccapppp c2826i850600ea77775111bboee 14bba0477777111bbbb4466666---- pat.baaeeee..444--ap.p.......
[18] J. Forster. A linear lower bound on the unbounded error probabillistic com.umiiiiicccimimiiiiiiiioonoo compexxit. J. Comput. Syst. Sci., 65(4):612-625 2002. URL https://daloog///o10eee000000000 00019-3.
[19] D. J. Foster, A. Rakhlin, D. Simchi-Levi, and Y. Xu. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreemment-based perspective. arXiv, 2010.03104, 2020, URL
[20] D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13487, 2021.
[21] S. Hanneke and L. Yang. Minimax analysis of active learning. Journal of Machine Learning Research, 14900))34877333 2015. URL http::/jmml.org/papprrss 6/hanneke 1 55.html.
[22] W. Hodges et al. A shorter model theory. Cambridge university press, 1997.
[23] B. Huang, K. Huang, S. Kakade, J. D. Lee, Q. Lei, R. Wang, and J. Yang. Going beyond linear
rl: Sample efficient neural function approximation. Advances in Neural Information Processing Systems, 34, 2021.
[24] B. Huang, J. D. Lee, Z. Wang, and Z. Yang. Towards general function approximation in zero-sum markov games. arXiv preprint 100V::207,,14722, 2021.
[25] K. Huang, S. M. Kakade, J. D. Lee, and Q. Lei. A short note on the relationship of information gain and eluder dimension. arXiv preprint urXiv:2107.023377 2021.
[26] H. Ishfaq, Q Cui, V. Nguyen, A. Ayoub, Z. Yang. Z. Wang, D. Precup, and L. Yang. Ran- domized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning. pages 4607 4616. PMLR, 2021.
[27] N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Leurning Research, pages 1704-1713, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL
[28] C. Jin, Q. Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficiens algorithms. arXiv, 2102.00815, 2021. URL https::/anxiv.orr/abs//2202 00815.
[29] C. Jin, Q. Liu, and T. Yu. The power of exploiter: Provable multi-agent rl in large state spaces. arXiv preprint arXiv:2106.0333 2021.
[30] P. Kamath, O. Montasser, and N. Srebro. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference on Learning Theory, pages 2236-2262. PMLR, 2020.
[31] B. Kveton, M. Zaheer, C. Szepesvari, L. Li, M. Ghavamzadeh, and C. Boutilier. Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 2066-2078 PMLR, 2020.
[32] L. Li, Y. Lu, and D. Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2071-2080. PMLR, 06-11 Aug 2017. URL http://pooeeedddngg.....rresssss 7ch.h/.
12

---

[37] D. Russo and B. Van Roy. Eluder dimension and the sample complexity of op- timistic exploration. In Advances in Neural Information Processing Systems, vol- ume 26. Curran Associates, Inc., 2013. URL http:///ccoonoonererreppcppppppp haw.cebbb1t0bee755cf444555555500 [33] G. Mahajan and S. Lovett. Personal communication. 2021.
[34] W. Mou, Z. Wen, and X. Chen. On the sample complexity of reinforcement learning with policy space generalization. arXiv preprint arXiv:2008. 073533, 2020.
[35] D. Mubayi and A. Suk. A survey quantitative bounds for hypergraph ramsey problems. arxiv e-prints (july 2017). arXiv preprint (aath./00/77000422399 2017.
[36] I. Osband and B. Van Roy. Model-based reinforcement learning and the eluder dimension. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL httpss/pooceeelinnseeeeiippppppp
11419 1500000005500002220000000000
[38] D. Russo and B. Van Roy. An information theorretict analysis of thompson sampling. The Journal of Machine Learning Research, (71):2442-24471 2016.
[39] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. URL https//www.cc..hj..alll-------a
UntertaaddingMachnnleeennn.
[40] S. Shelah. Classification theory: and the number of non-isomorphic models. Elsevier, 1990.
[41] N. Srinivas, Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:09/2.3995, 2009.
[42] W. Sun, N. Jiang, A. Krishnamurthy, A. Agarwal, and J. Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference learning theory, pages 29333. PMLR, 2019.
[43] R. Vershynin. High-dimensional probability: An introdaction with applications in data science, volume 47. Cambridge university press, 2018. URL wookk/DDPbbok.....
[44] R. Wang, R. R. Salakhutdinov, and L. Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimen- sion. In Advances in Neural Information Processing Systems, volume 33, pages 6123- 6135. Curran Associates, Inc., 2020. URL. http:///pccceeoons..eeerrccccppp
449244558000000336669222220 pappssae
[45] Y. Wang, R. Wang, S. S. Du, and A. Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint 1IXhv:1912.04136, 2019.
[46] Z. Wen and B. Van Roy. Efficient exploration and value function generalization in deterministic systems. In Advances in Neural Information Processing Systems, vol- 26. Curran Associates, Inc., 2013. URL http://pppeeeiiisseeeeeepppppppp
[47] Z. Xu and A. Tewari. Representation learning beyond linear prediction functions. Advances in Neural Information Processing Systems, 34, 2021.
13

---

Checklist
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]
(c) Did you discuss any potential negative societal impacts of your work? [NIA] Since this a theory paper regarding several notions of complexity for learning problems, we do not foresee any immediate potential negalive impacts.
(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 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 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 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, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite 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 a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) 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 participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "vX_lCYP21AC", "reviewer": "Reviewer_kWVT", "summary": "This paper provides new insights on the eluder dimension which is a complexity measure extensively used for bandits and reinforcement learning with function approximation. The paper studies the eluder dimension in relation to a new complexity measure proposed by the authors called $\\sigma$-rank which is the minimal dimension required to represent the class as a generalized linear model.  The authors show that in some cases, the eluder dimension can be exponentially smaller than $\\sigma$-rank. In some other cases where $\\sigma$ is ReLu, the eluder dimension can be exponentially larger than $\\sigma$-rank. Further, for binary-valued function classes, the authors provide a characterization of the eluder dimension in terms of star number and threshold dimension.\n", "questions": "I have some questions for the authors:\n- Does the comparison between the $\\sigma$-rank and the eluder dimension help understanding when the eluder dimension is bounded?\n- In some cases, the eluder dimension can be exponentially smaller than $\\sigma$-rank and otherwise. The authors can explain what is the consequence of this fact?\n- When the function class lies in an RKHS, is there any equivalence between the eluder dimension and the generalized rank?   ", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper addresses an important problem: understanding the insight of the eluder dimension in bandits and reinforcement learning with function approximation.\n- The generalized notion of rank seems novel.  The results of the comparison of this notion and the eluder dimensions are interesting.\n- The obtained results of this paper are original.\n\nWeaknesses:\n- The organization and the writing are not very clear to follow.\n-  Although the paper addresses an insight into the eluder dimension, however, the questions raised in the Introduction section toward this insight are not convinced. Question 1 seems strange to me. Whether all function classes with small eluder dimensions are essentially generalized linear models is an \"important\" question? In [37], in a generalized linear setting, Russo and Van Roy provided an upper bound on the eluder dimension. This upper bound may be small or even infinite depending on the $\\sigma$ function. Thus, we cannot require that the eluder dimension is small in generalized linear models. The answer \"No\" of Question 1 does not contrast with the result of Russo and Van Roy. I think that a more important question to answer is when the eluder dimension is bounded? \n- Obtained results are not significant enough for the understanding of the eluder dimensions in existing works. \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": "uTnscUU_nxt", "reviewer": "Reviewer_82U6", "summary": "The authors study eluder dimension, its relationship with other measures like sigma-rk, and their binary versions. Specifically, they compare eluder/star dimension with various sigma-rk's and report their findings on which one is larger in general and when one can be much bigger than the other. ", "questions": "I did not follow Eq (3). the condition implies that $\\mu/L \\le \\frac{ \\sigma(z')/L - \\sigma(z)/L}{z'-z} \\le 1$. The authors' claim makes sense if $\\sigma$ is identity. Otherwise, I don't see how it is true; the range R is applied to the input of $\\sigma$, but $L$ is on the gradient of $z$, so the the constant $R$ and $L$ are bounds for two different spaces.\n\nother comments\n\n* THeorem 7: should R here be $R^2$?\n* What is Ldim? (littlestone dimension? I was not able to find the definition.)\n* L308-309: why suddenly poly() here? The sentence here seems out of context..", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(Please provide a thorough assessment of the strengths and weaknesses of the paper, touching on each of the following dimensions: originality, quality, clarity and significance. You can incorporate Markdown and Latex into your review. See /faq.)\n\nOriginality: moderate.\n\nQuality: above bar\n\nClarity: above bar\n\nSignificance: moderate\n\nThe strength is the improved understand of various complexity measures. The weakness is that it is quite a theoretical work that does not have much implications about algorithms and the fundamental difficulty of learning problems. \n\n-----\nafter the rebuttal period, I feel I have a better understanding of the contribution. Indeed, showing that EDim can be a strictly better complexity measure than sigma rank is quit meaningful and what researchers have been missing. Thus, I have raised the score.", "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": "uDC8rPWmAO", "reviewer": "Reviewer_4vAv", "summary": "\nThis paper gives an in-depth investigation on the notion of eluder dimension. Eluder dimension is a widely accepted complexity measure of function classes in bandits and reinforcement learning. However, it is previously unknown whether there is a separation between (function classes with) finite eluder dimension and generalized linear models. This paper is the first to show the separation.\n\n To show this, they defined $\\Sigma$-rank, a new complexity measure that characterizes the generalized linear models. The paper first shows a chain inequality to link $\\Sigma$-rank classes for different $\\Sigma$. The paper then shows the place of Edim in the $\\Sigma$-rank chain. Next, the paper narrows down the focus from real-valued functions to binary functions. Then the paper introduces combinatorial Edim, Sdim, Tdim, and shows an important tight characterization of Edim via Sdim and Tdim, via a connection to the Ramsey theory. At last, the paper asked if the results for binary (combinatorial) Edim can be brought back to real-valued functions, and they leave it as future work.\n", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n\n1. This paper identifies an important problem: is Edim different from generalized lienar models? Indeed, this is an important question that are less studied in the literature. Most papers just take the notion of Edim as granted and prove results based on Edim. But when asked about examples of Edim, they are elusive or just give generalized linear models as example.\n2. The writing is good in this paper. \n\nWeakness:\n\n1. There are too many definitions of complexity measures in this paper. For better presentation, I would prefer them to be aggregated in a single section/appendix, which could help readers find and compare the definitions. It makes me hard to locate and figure out the definitions of different measures.\n2. The paper might have less impact because recently, RL theory community are turning their focus from Edim to new definitions like Bellman rank and bilinear classes. Once people are proving results based on these two new defintions, it might be less interested to show results on Edim.\n3. The proof are simple and combinatorial, which means it might not bring many new techniques or intuitions for future work.\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