Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 
This 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.

 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.

strengths_and_weaknesses: 
Strengths:

1. 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.
2. The writing is good in this paper. 

Weakness:

1. 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.
2. 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.
3. The proof are simple and combinatorial, which means it might not bring many new techniques or intuitions for future work.


questions: N/A
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
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.)

Originality: moderate.

Quality: above bar

Clarity: above bar

Significance: moderate

The 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. 

-----
after 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.
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.

other comments

* THeorem 7: should R here be $R^2$?
* What is Ldim? (littlestone dimension? I was not able to find the definition.)
* L308-309: why suddenly poly() here? The sentence here seems out of context..
limitations: None.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.

strengths_and_weaknesses: Strengths:
- This paper addresses an important problem: understanding the insight of the eluder dimension in bandits and reinforcement learning with function approximation.
- The generalized notion of rank seems novel.  The results of the comparison of this notion and the eluder dimensions are interesting.
- The obtained results of this paper are original.

Weaknesses:
- The organization and the writing are not very clear to follow.
-  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? 
- Obtained results are not significant enough for the understanding of the eluder dimensions in existing works. 

questions: I have some questions for the authors:
- Does the comparison between the $\sigma$-rank and the eluder dimension help understanding when the eluder dimension is bounded?
- 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?
- When the function class lies in an RKHS, is there any equivalence between the eluder dimension and the generalized rank?   
limitations: Yes
review_title: null

Meta-review: metareview: All reviewers and AC believe this paper is valuable contribution to the theoretical understanding of reinforcement learning.
confidence: Certain
Decision: Accept