Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper provides a new set of assumptions under which,  given a realizable Q-function / V-function class, one can efficiently find an almost optimal policy. They define the notion of bellman eluder (BE) dimension and provide regret bounds for RL problems for which the BE dimension is bounded. In particular, the regret bounds do not depend on the size of the state space |S|, and only scale with BE dimension, H and log(|F|), where F denotes the given realizable value function class. Their algorithm is based on optimism with local confidence intervals. 

They also show that almost all the RL settings where we know how to get a sample efficient algorithm have small BE dimensions. In addition to this, they also provide an example setting (kernel reactive POMDPs) where BE dimension is small and hence their algorithm is sample efficient, but we did not know any algorithm for this setting before the paper. 
main_review: I support accepting the paper. However, I have a few concerns and would be open to increase my score depending on the feedback: 

(1. ) Can we test Assumption 2 ? Given a realizable value function class, how can I test whether Assumption 2 holds and if I can run GOLF? 

(2.) What happens when F is not realizable. Suppose it is \epsilon-approximately realizable. What kind of guarantees can we hope for in this case? 

(3.) Can GOLF be implemented efficiently for any RL setting? What about tabular RL? 

(4.)  Is there any RL problem setting where we know how to solve it as a stand alone problem, but the BE dimension is not small? 

(5.) From what I understand, Kernel reactive POMDPs is the only problem class which was not captured by bi-linear classes framework of [41]. All other problems are captured by the framework of [41] as well. Do you / they have a proof that Kernel reactive POMDPs are not captured by the framework of [41]? I worry that the framework of [41] is equally general. In that case, the framework of BE dimension seems to add nothing new. 

(6.) Can we compare the BE dimension with the distribution class D_{F} and D_{\Delta}. Is one always larger than the other?  

The paper is very well written. Minor typo: Line 338: discusses -> discuss. 

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies a new complexity measure, Bellman Eluder dimension, for provably efficient reinforcement learning. The authors propose algorithms that provably find near-optimal policies whose sample complexity can be upper bounded in terms of the Bellman Eluder dimension. The authors further show that for a large class of RL problems that admit sample-efficient algorithms, their Bellman Eluder dimension is bounded. 
main_review: Recently, we have seen lots of progress on provably efficient RL. Existing work have already introduced a large set of structural assumptions on the underlying problem. Given this, an important open problem in this field is to unify existing assumptions and define new complexity measures that generalize existing assumptions. In this paper, the authors make important progress on this problem by defining the Bellman Eluder dimension which generalize a large set of existing assumptions. 

Technically, Bellman Eluder dimension is defined as the (distributional version of) the eluder dimension of the Bellman residuals induced by the function class under consideration. Notable examples include function classes with bounded eluder dimension + Bellman completeness, and problems with low Bellman rank. 

Overall, this is a great paper. It's pretty clear that it should be accepted. I will fight for its acceptance. 

Comments

1. In Figure 1, why does LQR have bounded eluder dimension? It is known that LQRs satisfy Bellman completeness with linear function approximation. However, I don't see any reason why LQRs themselves have bounded eluder dimension.

2. Line 104. Generalized linear functions with unknown activations seem to be a bad example here. Latest version of [41] can indeed handle such functions (though [41] was updated after the NeurIPS submission due). Consider using other examples.

3. When discussing existing results, it could be helpful to mention the computation efficiency of the algorithms. E.g., although the algorithms in [7] and [17] require stronger representation conditions and achieve worst regret guarantee, they are computationally efficient assuming access to regression oracles. On the other hand, there is no existing computationally-efficient algorithm that achieves nearly optimal regret bound or only requires the weaker version of completeness.

4. It might be helpful to discuss problems that cannot be handle by the current framework. Notable examples include deterministic linear realizability (and its stochastic variants) [1-4]. 

[1] Efficient exploration and value function generalization in deterministic systems

[2] Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle

[3] Agnostic Q-learning with Function Approximation in Deterministic Systems: Near-Optimal Bounds on Approximation Error and Sample Complexity

[4] On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function


limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper provides a solid and insightful analysis of the theoretical study of reinforcement learning. The reviewers think the contributions of the new definitions and techniques meet the standard of NeurIPS.
main_review: This paper proposes an extended version of the concept of the eluder dimension, which is originally used in bandit problems and later utilized in explorations in MDPs by several recent works. There are generally two branches of methods in this area, one models the value function, with the other modeling the transition kernel, by a general function set and characterizes the eluder dimension of such a function class. The new definition of the Bellman eluder dimension in this paper seems to connect these two cases as the definition involves both the value function class and the Bell operator. It is proved by the paper that the class of MDPs with structures defined by the Bellman eluder dimension is strictly more general than the previous classes, while the regret upper bound has the same form of $O(poly(H)\sqrt{Kd})$.

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a new notion of dimension (i.e., the BE dimension) to measure the complexity of a function class when applied to RL problems. The BE dimension summarizes two previously prevailing notions: the Bellman rank and the Eluder dimension, and is also able to cover more tractable cases than before. An algorithm is proposed to be provably efficient with a low BE dimension which improves previous results based on low Bellman rank and low Eluder dimension.
main_review: I enjoy reading this paper. It is well-written. I especially like the authors' interpretations of each definition and the high-level explanation of the algorithm and the proof. I mainly have three points to comment on:

1. About the BE dimension

In my opinion, the construction of the BE dimension and the fact that it covers the Bellman rank and the Eluder dimension are not surprising. Please correct me if my understanding is wrong:

The main difference between the Bellman rank and the Eluder dimension is the underlying distribution (D_F or D_delta) and whether allowing non-linearity. BE dimension unifies them by introducing the freedom of selecting the distribution space. Once chosen proper distribution space and function space, BE dimension covers the Bellman rank due to a stronger constraint (see the below (b) ) and covers the eluder dimension with a smaller function space (F-TF \subset F-F). 

What I find interesting/important is that BE covers more. In Proposition 13, the example illustrates two things:

a) F-TF can be much smaller than F-F and especially can exclude some pathological functions which can make the Eluder dimension explode. If the algorithm is of a Bellman-update fashion, analyzing F-TF is sufficient instead of going back to F-F. 

b) BE dimension arouses stronger control than Bellman rank: Bellman rank is similar to \sqrt{\sum_{i=1}^{t-1} <q_t,w_i>^2 }\leq \sqrt(t-1)\epsilon and |<q_t, w_t>|>\epsilon (if we regard the inner product as projection), which relaxes the constraint in BE dimension to a scale of \sqrt{t}, therefore, allows more freedom. This might inspire future studies on how we should impose constraining conditions to determine a function.

Do you have any intuitive explanation on how BE covers more than bellman rank and eluder except for the freedom of selecting distributions?  

2. About the benefit of BE.

What I care about most is: whether BE-based algorithms are more efficient than the other two; whether algorithms based on the other two can be transferred to BE-based versions. It seems that at least for Bellman-update type algorithms, BE dim is more satisfying than the other two. But for algorithms with on-policy critic fitting, e.g., ENIAC (https://arxiv.org/pdf/2103.11559.pdf), I wonder if BE can provide a better sample complexity than the Eluder dimension.

3. Strong condition on distributions. 

Both D_F and D_\Delta contain possibly numerous distributions. I wonder if there is any idea on how to shrink the distribution set?

Minors:
1. At Line 221, an RL problem, not a.
2. For the Line 3 in Algo. 1, what does it mean by f(s_1, \pi_f(s_1))? Isn't f:= f_1 x f_2 ... x f_h? Or do you mean f_1(s_1, \pi_f(s_1))?
3. At line 217, should there be no comma in front of which?

limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper introduces a new structural assumption for provably efficient online reinforcement learning. The authors provided a characterization of the new Bellman Eluder Dimension, showing that it generalizes a large part of existing structural assumptions while preserving efficient learning. Overall, the paper is novel, well written and technically solid. I think it should be accepted.
Decision: Accept (Spotlight)